VLVIndex.java revision d73dd29ce6a19cd9f81bc4db24d50a5b53f45a3c
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (the "License"). You may not use this file except in compliance
* with the License.
*
* You can obtain a copy of the license at legal-notices/CDDLv1_0.txt
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at legal-notices/CDDLv1_0.txt.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information:
* Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*
*
* Copyright 2006-2008 Sun Microsystems, Inc.
* Portions Copyright 2011-2015 ForgeRock AS
*/
/**
* This class represents a VLV index. Each database record is a sorted list
* of entry IDs followed by sets of attribute values used to sort the entries.
* The entire set of entry IDs are broken up into sorted subsets to decrease
* the number of database retrievals needed for a range lookup. The records are
* keyed by the last entry's first sort attribute value. The list of entries
* in a particular database record maintains the property where the first sort
* attribute value is bigger then the previous key but smaller or equal
* to its own key.
*/
public class VLVIndex extends DatabaseContainer
implements ConfigurationChangeListener<BackendVLVIndexCfg>
{
/** The limit on the number of entry IDs that may be indexed by one key. */
private int sortedSetCapacity = 4000;
/** The SortOrder in use by this VLV index to sort the entries. */
/** The cached count of entries in this index. */
private final AtomicInteger count;
/**
* A flag to indicate if this vlvIndex should be trusted to be consistent
* with the entries database.
*/
private boolean trusted;
/** A flag to indicate if a rebuild process is running on this vlvIndex. */
private boolean rebuildRunning;
/** The VLV vlvIndex configuration. */
private BackendVLVIndexCfg config;
private SearchFilter filter;
private SearchScope scope;
/**
* Create a new VLV vlvIndex object.
*
* @param config The VLV index config object to use for this VLV
* index.
* @param state The state database to persist vlvIndex state info.
* @param env The JE Storage
* @param entryContainer The database entryContainer holding this vlvIndex. the sort order
* @param txn The transaction to use when creating this object
* @throws StorageRuntimeException
* If an error occurs in the JE database.
* @throws ConfigException if a error occurs while reading the VLV index
* configuration
*/
VLVIndex(BackendVLVIndexCfg config, State state, Storage env, EntryContainer entryContainer, WriteableStorage txn)
{
super(new TreeName(entryContainer.getDatabasePrefix(), "vlv." + config.getName()), env, entryContainer);
try
{
}
catch(Exception e)
{
throw new ConfigException(msg);
}
{
// If there are no entries in the entry container then there
// is no reason why this vlvIndex can't be upgraded to trusted.
setTrusted(txn, true);
}
this.config.addChangeListener(this);
}
throws ConfigException
{
{
final boolean ascending;
try
{
{
ascending = false;
}
else
{
ascending = true;
{
}
}
}
catch (Exception e)
{
}
.toLowerCase());
{
throw new ConfigException(msg);
}
}
return sortKeys;
}
{
{
{
return scope;
}
}
return null;
}
/** {@inheritDoc} */
{
try
{
{
}
}
finally
{
}
}
// Matches encoding from SortValuesSet.
{
}
/**
* Close the VLV index.
*
* @throws StorageRuntimeException if a JE database error occurs while
* closing the index.
*/
public void close() throws StorageRuntimeException
{
super.close();
this.config.removeChangeListener(this);
}
/**
* Update the vlvIndex for a new entry.
*
* @param buffer The index buffer to buffer the changes.
* @param entryID The entry ID.
* @param entry The entry to be indexed.
* @return True if the entry ID for the entry are added. False if
* the entry ID already exists.
* @throws DirectoryException If a Directory Server
* error occurs.
*/
{
if (shouldInclude(entry))
{
return true;
}
return false;
}
/**
* Update the vlvIndex for a deleted entry.
*
* @param buffer The database transaction to be used for the deletions
* @param entryID The entry ID
* @param entry The contents of the deleted entry.
* @return True if the entry was successfully removed from this VLV index
* or False otherwise.
* @throws DirectoryException If a Directory Server error occurs.
*/
{
if (shouldInclude(entry))
{
return true;
}
return false;
}
/**
* Update the vlvIndex to reflect a sequence of modifications in a Modify
* operation.
*
* @param buffer The database transaction to be used for the deletions
* @param entryID The ID of the entry that was modified.
* @param oldEntry The entry before the modifications were applied.
* @param newEntry The entry after the modifications were applied.
* @param mods The sequence of modifications in the Modify operation.
* @return True if the modification was successfully processed or False
* otherwise.
* @throws StorageRuntimeException If an error occurs during an operation on a
* JE database.
* @throws DirectoryException If a Directory Server error occurs.
*/
{
if (shouldInclude(oldEntry))
{
if (shouldInclude(newEntry))
{
// The entry should still be indexed. See if any sorted attributes are
// changed.
if (isSortAttributeModified(mods))
{
boolean success;
// Sorted attributes have changed. Reindex the entry;
return success;
}
}
else
{
// The modifications caused the new entry to be unindexed. Remove from
// vlvIndex.
}
}
else
{
if (shouldInclude(newEntry))
{
// The modifications caused the new entry to be indexed. Add to vlvIndex
}
}
// The modifications does not affect this vlvIndex
return true;
}
{
{
{
{
return true;
}
{
{
return true;
}
}
}
}
return false;
}
/**
* Get a sorted values set that should contain the entry with the given
* information.
*
* @param txn The transaction to use when retrieving the set or NULL if it is
* not required.
* @param entryID The entry ID to use.
* @param values The values to use.
* @param types The types of the values to use.
* @return The SortValuesSet that should contain the entry with the given
* information.
* @throws StorageRuntimeException If an error occurs during an operation on a
* JE database.
* @throws DirectoryException If a Directory Server error occurs.
*/
{
}
{
{
// There are no records in the database
if (logger.isTraceEnabled())
{
}
// this could not be found, so clean the key for later reuse
return new SortValuesSet(this);
}
if (logger.isTraceEnabled())
{
}
}
{
"Search Key:%s\nFound Key:%s\n",
}
/**
* Search for entries matching the entry ID and attribute values and
* return its entry ID.
*
* @param txn The JE transaction to use for database updates.
* @param entryID The entry ID to search for.
* @param values The values to search for.
* @param types The types of the values to search for.
* @return The index of the entry ID matching the values or -1 if its not
* found.
* @throws StorageRuntimeException If an error occurs during an operation on a
* JE database.
* @throws DirectoryException If a Directory Server error occurs.
*/
boolean containsValues(ReadableStorage txn, long entryID, ByteString[] values, AttributeType[] types)
{
return pos >= 0;
}
{
}
/**
* Gets the types of the attribute values to sort.
*
* @return The types of the attribute values to sort on.
*/
{
{
}
return types;
}
/**
* Update the vlvIndex with the specified values to add and delete.
*
* @param txn A database transaction, or null if none is required.
* @param addedValues The values to add to the VLV index.
* @param deletedValues The values to delete from the VLV index.
* @throws StorageRuntimeException If an error occurs in the JE database.
* @throws DirectoryException If a Directory Server
* error occurs.
*/
void updateIndex(WriteableStorage txn, TreeSet<SortValues> addedValues, TreeSet<SortValues> deletedValues)
{
// Handle cases where nothing is changed early to avoid
// DB access.
{
return;
}
if(addedValues != null)
{
}
if(deletedValues != null)
{
}
while(true)
{
final ByteString key;
{
{
// Start from the smallest values from either set.
{
}
else
{
}
}
else
{
}
}
{
}
else
{
break;
}
{
// This is the last unbounded set.
{
}
{
}
}
else
{
{
}
{
}
}
if(newSize >= sortedSetCapacity)
{
if(logger.isTraceEnabled())
{
" the entry size of %d. Spliting into two sets with " +
}
}
else if(newSize == 0)
{
}
else
{
}
}
}
{
sortValues.remove();
if (sortValues.hasNext())
{
return sortValues.next();
}
return null;
}
/**
* Evaluate a search with sort control using this VLV index.
*
* @param txn The transaction to used when reading the index or NULL if it is
* not required.
* @param searchOperation The search operation to evaluate.
* @param sortControl The sort request control to evaluate.
* @param vlvRequest The VLV request control to evaluate or NULL if VLV is not
* requested.
* @param debugBuilder If not null, a diagnostic string will be written
* which will help determine how this index contributed
* to this search.
* @return The sorted EntryIDSet containing the entry IDs that match the
* search criteria.
* @throws DirectoryException If a Directory Server error occurs.
* @throws StorageRuntimeException If an error occurs in the JE database.
*/
{
if (!trusted || rebuildRunning
{
return null;
}
if (debugBuilder != null)
{
}
long[] selectedIDs = new long[0];
if(vlvRequest != null)
{
{
if (targetOffset < 0)
{
// The client specified a negative target offset. This should never
// be allowed.
message);
}
else if (targetOffset == 0)
{
// This is an easy mistake to make, since VLV offsets start at 1
// instead of 0. We'll assume the client meant to use 1.
targetOffset = 1;
}
if (startPos < 0)
{
// This can happen if beforeCount >= offset, and in this case we'll
// just adjust the start position to ignore the range of beforeCount
// that doesn't exist.
startPos = 0;
}
else if(startPos >= currentCount)
{
// The start position is beyond the end of the list. In this case,
// we'll assume that the start position was one greater than the
// size of the list and will only return the beforeCount entries.
// The start position is beyond the end of the list. In this case,
// we'll assume that the start position was one greater than the
// size of the list and will only return the beforeCount entries.
afterCount = 0;
}
selectedIDs = new long[count];
try
{
//Locate the set that contains the target entry.
int cursorCount = 0;
int selectedPos = 0;
{
if(logger.isTraceEnabled())
{
}
i++, selectedPos++)
{
}
}
if (selectedPos < count)
{
// We don't have enough entries in the set to meet the requested
// page size, so we'll need to shorten the array.
long[] newIDArray = new long[selectedPos];
}
if(debugBuilder != null)
{
}
}
finally
{
}
}
else
{
int targetOffset = 0;
int includedBeforeCount = 0;
int includedAfterCount = 0;
try
{
{
if(logger.isTraceEnabled())
{
}
if(adjustedTargetOffset < 0)
{
// For a negative return value r, the vlvIndex -(r+1) gives the
// array index of the ID that is greater then the assertion value.
}
// Iterate through all the sort values sets before this one to find
// the target offset in the index.
while(true)
{
for(int i = lastOffset;
{
}
{
break;
}
{
}
else
{
}
}
// Set the cursor back to the position of the target entry set
// Add the target and after count entries if the target was found.
int afterIDCount = 0;
while(true)
{
for(int i = lastOffset;
i++)
{
}
{
break;
}
lastOffset = 0;
}
{
}
if(debugBuilder != null)
{
}
}
}
finally
{
}
}
}
else
{
int currentCount = 0;
try
{
{
if(logger.isTraceEnabled())
{
}
}
}
finally
{
}
selectedIDs = new long[currentCount];
int pos = 0;
{
}
if(debugBuilder != null)
{
}
}
}
/**
* Set the vlvIndex trust state.
* @param txn A database transaction, or null if none is required.
* @param trusted True if this vlvIndex should be trusted or false
* otherwise.
* @throws StorageRuntimeException If an error occurs in the JE database.
*/
throws StorageRuntimeException
{
}
/**
* Return true iff this index is trusted.
* @return the trusted state of this index
*/
public boolean isTrusted()
{
return trusted;
}
/**
* Set the rebuild status of this vlvIndex.
* @param rebuildRunning True if a rebuild process on this vlvIndex
* is running or False otherwise.
*/
public synchronized void setRebuildStatus(boolean rebuildRunning)
{
this.rebuildRunning = rebuildRunning;
}
/**
* Gets the values to sort on from the entry.
*
* @param entry The entry to get the values from.
* @return The attribute values to sort on.
*/
{
{
{
// There may be multiple versions of this attribute in the target entry
// (e.g., with different sets of options), and it may also be a
// multivalued attribute. In that case, we need to find the value that
// is the best match for the corresponding sort key (i.e., for sorting
// in ascending order, we want to find the lowest value; for sorting in
// descending order, we want to find the highest value). This is
// handled by the SortKey.compareValues method.
{
for (ByteString v : a)
{
{
sortValue = v;
}
}
}
}
}
return values;
}
/**
* Encode a VLV database key with the provided sort values.
*
* @param sv the sort values to encode
* @return The encoded bytes.
* @throws DirectoryException If a Directory Server error occurs.
*/
{
}
/**
* Encode a VLV database key with the given information.
*
* @param entryID The entry ID to encode.
* @param values The values to encode.
* @param types The types of the values to encode.
* @return The encoded bytes.
* @throws DirectoryException If a Directory Server error occurs.
*/
throws DirectoryException
{
try
{
{
final ByteString v = values[i];
if (v == null)
{
}
else
{
}
}
return builder.toByteString();
}
catch (DecodeException e)
{
throw new DirectoryException(
}
}
/**
* Decode a VLV database key.
*
* @param keyBytes The byte array to decode.
* @return The sort values represented by the key bytes.
* @throws DirectoryException If a Directory Server error occurs.
*/
{
{
return null;
}
int vBytesPos = 0;
{
{
int valueLengthBytes = valueLength;
valueLength = 0;
{
}
}
if(valueLength == 0)
{
attributeValues[i] = null;
}
else
{
}
vBytesPos += valueLength;
}
}
/**
* Indicates if the given entry should belong in this VLV index.
*
* @param entry The entry to check.
* @return True if the given entry should belong in this VLV index or False
* otherwise.
* @throws DirectoryException If a Directory Server error occurs.
*/
{
}
/** {@inheritDoc} */
public synchronized boolean isConfigurationChangeAcceptable(
{
try
{
}
catch(Exception e)
{
return false;
}
try
{
}
catch (ConfigException e)
{
return false;
}
return true;
}
/** {@inheritDoc} */
{
try
{
{
{
}
});
return ccr;
}
catch (Exception e)
{
throw new StorageRuntimeException(e);
}
}
{
// Update base DN only if changed..
{
ccr.setAdminActionRequired(true);
}
// Update scope only if changed.
{
ccr.setAdminActionRequired(true);
}
// Update sort set capacity only if changed.
{
// Require admin action only if the new capacity is larger.
// Otherwise, we will lazily update the sorted sets.
{
ccr.setAdminActionRequired(true);
}
}
// Update the filter only if changed.
{
try
{
ccr.setAdminActionRequired(true);
}
catch(Exception e)
{
}
}
// Update the sort order only if changed.
{
try
{
}
catch (ConfigException e)
{
}
// We have to close the database and open it using the new comparator.
try
{
close();
}
catch (StorageRuntimeException de)
{
}
finally
{
}
ccr.setAdminActionRequired(true);
}
if (ccr.adminActionRequired())
{
trusted = false;
try
{
}
catch(StorageRuntimeException de)
{
}
}
}
/**
* Compares the contents in the provided values set with the given values to
* determine their relative order. A null value is always considered greater
* then a non null value. If all attribute values are the same, the entry ID
* will be used to determine the ordering. If the given attribute values array
* does not contain all the values in the sort order, any missing values will
* be considered as a unknown or wildcard value instead of a non existent
* value. When comparing partial information, only values available in both
* the values set and the given values will be used to determine the ordering.
* If all available information is the same, 0 will be returned.
*
* @param set
* The sort values set to containing the values.
* @param index
* The index of the values in the set.
* @param entryID
* The entry ID to use in the comparison.
* @param values
* The values to use in the comparison.
* @return A negative integer if the values in the set should come before the
* given values in ascending order, a positive integer if the values
* in the set should come after the given values in ascending order,
* or zero if there is no difference between the values with regard to
* ordering.
* @throws StorageRuntimeException
* If an error occurs during an operation on a JE database.
* @throws DirectoryException
* If an error occurs while trying to normalize the value (e.g., if
* it is not acceptable for use with the associated equality
* matching rule).
*/
{
{
{
break;
}
{
try
{
}
catch (DecodeException e)
{
e.getMessageObject(), e);
}
}
// A null value will always come after a non-null value.
{
{
continue;
}
else
{
return 1;
}
}
{
return -1;
}
if (result != 0)
{
return result;
}
}
if (entryID != -1)
{
// If we've gotten here, then we can't tell a difference between the sets
// of values, so sort based on entry ID.
}
// If we've gotten here, then we can't tell the difference between the sets
// of available values and the entry ID is not available. Just return 0.
return 0;
}
{
if (difference < 0)
{
return -1;
}
else if (difference > 0)
{
return 1;
}
else
{
return 0;
}
}
/**
* Returns the sort order of this VLV index.
*
* @return the sort order
*/
{
return sortOrder;
}
}