VLVIndex.java revision 07e7cb84f497a907074b5ca46f3147f65488d6ed
/*
* 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 record corresponds to a single entry matching
* the VLV criteria. Keys are a sequence of the entry's normalized attribute values corresponding to
* the VLV sort order, followed by the entry's entry ID. Records do not have a "value" since all
* required information is held within the key. The entry ID is included in the key as a
* "tie-breaker" and ensures that keys correspond to one and only one entry. This ensures that all
* tree updates can be performed using lock-free operations.
*/
@SuppressWarnings("javadoc")
class VLVIndex extends AbstractTree implements ConfigurationChangeListener<BackendVLVIndexCfg>, Closeable
{
/** The VLV vlvIndex configuration. */
private BackendVLVIndexCfg config;
/** The cached count of entries in this index. */
private SearchScope scope;
private SearchFilter filter;
/** The storage associated with this index. */
/**
* A flag to indicate if this vlvIndex should be trusted to be consistent with the entries tree.
*/
private boolean trusted;
final EntryContainer entryContainer, final WriteableTransaction txn) throws StorageRuntimeException,
{
try
{
}
catch (final Exception e)
{
}
{
/*
* 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);
}
{
switch (cfgScope)
{
case BASE_OBJECT:
return SearchScope.BASE_OBJECT;
case SINGLE_LEVEL:
return SearchScope.SINGLE_LEVEL;
case SUBORDINATE_SUBTREE:
return SearchScope.SUBORDINATES;
default: // WHOLE_SUBTREE
return SearchScope.WHOLE_SUBTREE;
}
}
{
}
{
try
{
}
catch (final Exception e)
{
return false;
}
try
{
}
catch (final ConfigException e)
{
return false;
}
return true;
}
{
try
{
{
{
}
});
return ccr;
}
catch (final Exception e)
{
throw new StorageRuntimeException(e);
}
}
private synchronized void applyConfigurationChange0(
{
// Update base DN only if changed
{
ccr.setAdminActionRequired(true);
}
// Update scope only if changed
{
ccr.setAdminActionRequired(true);
}
// Update the filter only if changed
{
try
{
ccr.setAdminActionRequired(true);
}
catch (final Exception e)
{
}
}
// Update the sort order only if changed
{
try
{
}
catch (final ConfigException e)
{
}
ccr.setAdminActionRequired(true);
}
if (ccr.adminActionRequired())
{
trusted = false;
try
{
}
catch (final StorageRuntimeException de)
{
}
}
}
{
{
final boolean ascending;
try
{
{
ascending = false;
}
else
{
ascending = true;
{
}
}
}
catch (final Exception e)
{
}
{
}
}
return sortKeys;
}
public void close()
{
this.config.removeChangeListener(this);
}
boolean isTrusted()
{
return trusted;
}
synchronized void setTrusted(final WriteableTransaction txn, final boolean trusted) throws StorageRuntimeException
{
if ( trusted ) {
} else {
}
}
void addEntry(final IndexBuffer buffer, final EntryID entryID, final Entry entry) throws DirectoryException
{
if (shouldInclude(entry))
{
}
}
{
}
{
return ByteString.empty();
}
{
}
void modifyEntry(final IndexBuffer buffer, final EntryID entryID, final Entry oldEntry, final Entry newEntry,
{
if (shouldInclude(oldEntry))
{
if (shouldInclude(newEntry))
{
// The entry should still be indexed. See if any sorted attributes are changed.
if (isSortAttributeModified(mods))
{
// Sorted attributes have changed. Reindex the entry.
}
}
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
}
}
{
{
{
{
return true;
}
}
}
return false;
}
void removeEntry(final IndexBuffer buffer, final EntryID entryID, final Entry entry) throws DirectoryException
{
if (shouldInclude(entry))
{
}
}
{
// Perform all updates in key order.
{
{
}
else
{
}
}
}
{
}
{
}
{
if (!trusted ||
{
return null;
}
if (debugBuilder != null)
{
}
if (vlvRequest != null)
{
{
}
}
}
private EntryIDSet evaluateNonVLVRequest(final ReadableTransaction txn, final StringBuilder debugBuilder)
{
{
return newDefinedSet(selectedIDs);
}
}
/**
* Reads a page of entries from the VLV which includes the nearest entry corresponding to the VLV
* assertion, {@code beforeCount} entries leading up to the nearest entry, and {@code afterCount}
* entries following the nearest entry.
*/
throws DirectoryException
{
final ByteSequence encodedTargetAssertion =
{
int targetPosition = 0;
// Don't waste cycles looking for an assertion that does not match anything.
{
/*
* Unfortunately we need to iterate from the start of the index in order to correctly
* calculate the target position.
*/
boolean targetFound = false;
int includedAfter = 0;
do
{
if (!targetFound)
{
{
if (targetPosition >= beforeCount)
{
// Strip out unwanted results.
}
}
else
{
targetFound = true;
}
}
else if (includedAfter < afterCount)
{
}
else
{
break;
}
}
}
else
{
// Treat a non-matching assertion as matching beyond the end of the index.
}
}
}
{
int i = 0;
{
}
return result;
}
/** Normalize the assertion using the primary key's ordering matching rule. */
{
try
{
/*
* Over-allocate the buffer for the primary key since it will be larger than the unnormalized
* value. For example it will definitely include a trailing separator byte, but may also
* include some escaped bytes as well. 10 extra bytes should accommodate most inputs.
*/
return encodedPrimaryKey;
}
catch (final DecodeException e)
{
searchOperation.addResponseControl(new VLVResponseControl(0, resultSetSize, LDAPResultCode.OFFSET_RANGE_ERROR));
throw new DirectoryException(ResultCode.VIRTUAL_LIST_VIEW_ERROR, ERR_VLV_BAD_ASSERTION.get(attributeName));
}
}
private EntryIDSet evaluateVLVRequestByOffset(final ReadableTransaction txn, final SearchOperation searchOperation,
{
if (targetOffset < 0)
{
// The client specified a negative target offset. This should never be allowed.
}
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;
}
{
final long[] selectedIDs;
{
}
else
{
selectedIDs = new long[0];
}
searchOperation.addResponseControl(new VLVResponseControl(targetOffset, currentCount, LDAPResultCode.SUCCESS));
return newDefinedSet(selectedIDs);
}
}
final StringBuilder debugBuilder)
{
long[] selectedIDs = new long[count];
int selectedPos = 0;
if (count > 0)
{
do
{
if (logger.isTraceEnabled())
{
}
}
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.
*/
}
}
if (debugBuilder != null)
{
}
return selectedIDs;
}
{
final int sizeOfEncodedEntryID = 8;
}
{
}
throws DirectoryException
{
if (shouldInclude(entry))
{
}
return false;
}
{
return builder.toByteString();
}
{
}
private static void encodeVLVKey0(final SortOrder sortOrder, final Entry entry, final ByteStringBuilder builder)
{
{
{
{
for (ByteString v : a)
{
try
{
/*
* The RFC states that the lowest value of a multi-valued attribute should be used,
* regardless of the sort order.
*/
{
}
}
catch (final DecodeException e)
{
/*
* This shouldn't happen because the attribute should have already been validated. If
* it does then treat the value as missing.
*/
continue;
}
}
}
}
}
}
/**
* Package private for testing.
* <p>
* Keys are logically encoded as follows:
* <ul>
* <li>if the key is {@code null} then append {@code 0xff} in order to ensure that all
* {@code null} keys sort after non-{@code null} keys in ascending order
* <li>else
* <ul>
* <li>escape any bytes that look like a separator byte ({@code 0x00}) or a separator escape byte
* ({@code 0x01}) by prefixing the byte with a separator escape byte ({@code 0x01})
* <li>escape the first byte if it looks like a null key byte ({@code 0xff}) or a null key escape
* byte ({@code 0xfe}) by prefixing the byte with a null key escape byte ({@code 0xfe})
* </ul>
* <li>append a separator byte ({@code 0x00}) which will be used for distinguishing between the
* end of the key and the start of the next key
* <li>invert all the bytes if the sort order is descending.
* </ul>
*/
final boolean ascending)
{
{
final byte sortOrderMask = separator;
for (int i = 0; i < length; i++)
{
if ((b & (byte) 0x01) == b)
{
// Escape bytes that look like a separator.
}
else if (i == 0 && (b & (byte) 0xfe) == (byte) 0xfe)
{
/*
* Ensure that all keys sort before (ascending) or after (descending) null keys, by
* escaping the first byte if it looks like a null key.
*/
}
// Invert the bits if this key is in descending order.
}
}
else
{
// Ensure that null keys sort after (ascending) or before (descending) all other keys.
}
}
{
}
{
return "N/A";
}
{
close();
}
}