From 42fbf08eb02ea8464a6b03fc47b75ad400bed44f Mon Sep 17 00:00:00 2001
From: Yannick Lecaillez <yannick.lecaillez@forgerock.com>
Date: Mon, 16 Mar 2015 09:36:32 +0000
Subject: [PATCH] OPENDJ-1866: Make EntryIDSet more maintainable.
---
opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexQueryFactoryImpl.java | 3
opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/ImportIDSet.java | 15
opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/EntryIDSetTest.java | 356 +++++++++
opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VerifyJob.java | 31
opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/Index.java | 75 +
opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/AttributeIndex.java | 3
opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VLVIndex.java | 3
/dev/null | 133 ---
opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexFilter.java | 108 +-
opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryContainer.java | 247 +++++
opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexBuffer.java | 6
opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/Utils.java | 61 +
opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryIDSet.java | 1221 +++++++++++++++++++------------
opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexQuery.java | 10
opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/NullIndex.java | 6
15 files changed, 1,524 insertions(+), 754 deletions(-)
diff --git a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/AttributeIndex.java b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/AttributeIndex.java
index 0f60dc7..0a56ee4 100644
--- a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/AttributeIndex.java
+++ b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/AttributeIndex.java
@@ -30,6 +30,7 @@
import static org.opends.messages.JebMessages.*;
import static org.opends.server.util.ServerConstants.*;
import static org.opends.server.util.StaticUtils.*;
+import static org.opends.server.backends.pluggable.EntryIDSet.newUndefinedSet;
import java.io.Closeable;
import java.util.*;
@@ -514,7 +515,7 @@
catch (DecodeException e)
{
logger.traceException(e);
- return new EntryIDSet();
+ return newUndefinedSet();
}
}
diff --git a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryContainer.java b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryContainer.java
index 91c78b2..8b96d8f 100644
--- a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryContainer.java
+++ b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryContainer.java
@@ -28,20 +28,27 @@
package org.opends.server.backends.pluggable;
import static org.forgerock.util.Utils.closeSilently;
+import static org.forgerock.util.Reject.checkNotNull;
import static org.opends.messages.JebMessages.*;
import static org.opends.server.backends.pluggable.JebFormat.*;
import static org.opends.server.core.DirectoryServer.*;
import static org.opends.server.protocols.ldap.LDAPResultCode.*;
+import static org.opends.server.backends.pluggable.IndexFilter.CURSOR_ENTRY_LIMIT;
import static org.opends.server.types.AdditionalLogItem.*;
import static org.opends.server.util.StaticUtils.*;
+import static org.opends.server.backends.pluggable.EntryIDSet.newUndefinedSet;
+import static org.opends.server.backends.pluggable.EntryIDSet.newDefinedSet;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
+import java.util.LinkedList;
import java.util.List;
import java.util.Map;
+import java.util.TreeMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
@@ -80,12 +87,14 @@
import org.opends.server.controls.ServerSideSortResponseControl;
import org.opends.server.controls.SubtreeDeleteControl;
import org.opends.server.controls.VLVRequestControl;
+import org.opends.server.controls.VLVResponseControl;
import org.opends.server.core.AddOperation;
import org.opends.server.core.DeleteOperation;
import org.opends.server.core.DirectoryServer;
import org.opends.server.core.ModifyDNOperation;
import org.opends.server.core.ModifyOperation;
import org.opends.server.core.SearchOperation;
+import org.opends.server.protocols.ldap.LDAPResultCode;
import org.opends.server.types.Attribute;
import org.opends.server.types.AttributeType;
import org.opends.server.types.Attributes;
@@ -100,6 +109,7 @@
import org.opends.server.types.RDN;
import org.opends.server.types.SearchFilter;
import org.opends.server.types.SortKey;
+import org.opends.server.types.SortOrder;
import org.opends.server.types.VirtualAttributeRule;
import org.opends.server.util.ServerConstants;
import org.opends.server.util.StaticUtils;
@@ -853,7 +863,7 @@
debugBuffer = new StringBuilder();
}
- EntryIDSet entryIDList = null;
+ EntryIDSet entryIDSet = null;
boolean candidatesAreInScope = false;
if (sortRequest != null)
{
@@ -861,8 +871,8 @@
{
try
{
- entryIDList = vlvIndex.evaluate(null, searchOperation, sortRequest, vlvRequest, debugBuffer);
- if (entryIDList != null)
+ entryIDSet = vlvIndex.evaluate(null, searchOperation, sortRequest, vlvRequest, debugBuffer);
+ if (entryIDSet != null)
{
searchOperation.addResponseControl(new ServerSideSortResponseControl(SUCCESS, null));
candidatesAreInScope = true;
@@ -882,7 +892,7 @@
}
}
- if (entryIDList == null)
+ if (entryIDSet == null)
{
if (processSearchWithVirtualAttributeRule(searchOperation, true))
{
@@ -894,10 +904,10 @@
EntryContainer.this, txn, searchOperation, debugBuffer, rootContainer.getMonitorProvider());
// Evaluate the filter against the attribute indexes.
- entryIDList = indexFilter.evaluate();
+ entryIDSet = indexFilter.evaluate();
// Evaluate the search scope against the id2children and id2subtree indexes
- if (entryIDList.size() > IndexFilter.FILTER_CANDIDATE_THRESHOLD)
+ if (entryIDSet.size() > IndexFilter.FILTER_CANDIDATE_THRESHOLD)
{
// Read the ID from dn2id.
EntryID baseID = dn2id.get(txn, aBaseDN);
@@ -909,27 +919,27 @@
}
ByteString baseIDData = baseID.toByteString();
- EntryIDSet scopeList;
+ EntryIDSet scopeSet;
if (searchScope == SearchScope.SINGLE_LEVEL)
{
- scopeList = id2children.read(txn, baseIDData);
+ scopeSet = id2children.read(txn, baseIDData);
}
else
{
- scopeList = id2subtree.read(txn, baseIDData);
+ scopeSet = id2subtree.read(txn, baseIDData);
if (searchScope == SearchScope.WHOLE_SUBTREE)
{
// The id2subtree list does not include the base entry ID.
- scopeList.add(baseID);
+ scopeSet.add(baseID);
}
}
- entryIDList.retainAll(scopeList);
+ entryIDSet.retainAll(scopeSet);
if (debugBuffer != null)
{
debugBuffer.append(" scope=").append(searchScope);
- scopeList.toString(debugBuffer);
+ scopeSet.toString(debugBuffer);
}
- if (scopeList.isDefined())
+ if (scopeSet.isDefined())
{
// In this case we know that every candidate is in scope.
candidatesAreInScope = true;
@@ -943,9 +953,7 @@
// If the sort key is not present, the sorting will generate the
// default ordering. VLV search request goes through as if
// this sort key was not found in the user entry.
- entryIDList =
- EntryIDSetSorter.sort(EntryContainer.this, txn, entryIDList, searchOperation,
- sortRequest.getSortOrder(), vlvRequest);
+ entryIDSet = sort(txn, entryIDSet, searchOperation, sortRequest.getSortOrder(), vlvRequest);
if (sortRequest.containsSortKeys())
{
searchOperation.addResponseControl(new ServerSideSortResponseControl(SUCCESS, null));
@@ -980,17 +988,17 @@
if (debugBuffer != null)
{
debugBuffer.append(" final=");
- entryIDList.toString(debugBuffer);
+ entryIDSet.toString(debugBuffer);
Entry debugEntry = buildDebugSearchIndexEntry(debugBuffer);
searchOperation.returnEntry(debugEntry, null);
return null;
}
- if (entryIDList.isDefined())
+ if (entryIDSet.isDefined())
{
rootContainer.getMonitorProvider().updateIndexedSearchCount();
- searchIndexed(txn, entryIDList, candidatesAreInScope, searchOperation, pageRequest);
+ searchIndexed(txn, entryIDSet, candidatesAreInScope, searchOperation, pageRequest);
}
else
{
@@ -1314,7 +1322,7 @@
* <li>return entry if it matches the filter
* </ul>
*
- * @param entryIDList The candidate entry IDs.
+ * @param entryIDSet The candidate entry IDs.
* @param candidatesAreInScope true if it is certain that every candidate
* entry is in the search scope.
* @param searchOperation The search operation.
@@ -1322,7 +1330,7 @@
* @throws DirectoryException If an error prevented the search from being
* processed.
*/
- private void searchIndexed(ReadableStorage txn, EntryIDSet entryIDList, boolean candidatesAreInScope,
+ private void searchIndexed(ReadableStorage txn, EntryIDSet entryIDSet, boolean candidatesAreInScope,
SearchOperation searchOperation, PagedResultsControl pageRequest) throws DirectoryException,
CanceledOperationException
{
@@ -1357,7 +1365,7 @@
// Make sure the candidate list is smaller than the lookthrough limit
int lookthroughLimit =
searchOperation.getClientConnection().getLookthroughLimit();
- if(lookthroughLimit > 0 && entryIDList.size() > lookthroughLimit)
+ if(lookthroughLimit > 0 && entryIDSet.size() > lookthroughLimit)
{
//Lookthrough limit exceeded
searchOperation.setResultCode(ResultCode.ADMIN_LIMIT_EXCEEDED);
@@ -1370,7 +1378,7 @@
if (continueSearch)
{
final SearchFilter filter = searchOperation.getFilter();
- for (Iterator<EntryID> it = entryIDList.iterator(begin); it.hasNext();)
+ for (Iterator<EntryID> it = entryIDSet.iterator(begin); it.hasNext();)
{
final EntryID id = it.next();
@@ -3154,8 +3162,7 @@
*/
Index newIndexForAttribute(WriteableStorage txn, TreeName indexName, Indexer indexer, int indexEntryLimit)
{
- final int cursorEntryLimit = 100000;
- return new Index(indexName, indexer, state, indexEntryLimit, cursorEntryLimit, false, txn, this);
+ return new Index(indexName, indexer, state, indexEntryLimit, CURSOR_ENTRY_LIMIT, false, txn, this);
}
@@ -3231,6 +3238,195 @@
return baseEntry;
}
+ private EntryIDSet sort(ReadableStorage txn, EntryIDSet entryIDSet, SearchOperation searchOperation,
+ SortOrder sortOrder, VLVRequestControl vlvRequest) throws DirectoryException
+ {
+ if (!entryIDSet.isDefined())
+ {
+ return newUndefinedSet();
+ }
+
+ final DN baseDN = searchOperation.getBaseDN();
+ final SearchScope scope = searchOperation.getScope();
+ final SearchFilter filter = searchOperation.getFilter();
+
+ final TreeMap<SortValues, Long> sortMap = new TreeMap<SortValues, Long>();
+ for (EntryID id : entryIDSet)
+ {
+ try
+ {
+ Entry e = getEntry(txn, id);
+ if (e.matchesBaseAndScope(baseDN, scope) && filter.matchesEntry(e))
+ {
+ sortMap.put(new SortValues(id, e, sortOrder), id.longValue());
+ }
+ }
+ catch (Exception e)
+ {
+ LocalizableMessage message = ERR_ENTRYIDSORTER_CANNOT_EXAMINE_ENTRY.get(id, getExceptionMessage(e));
+ throw new DirectoryException(DirectoryServer.getServerErrorResultCode(), message, e);
+ }
+ }
+
+ // See if there is a VLV request to further pare down the set of results, and if there is where it should be
+ // processed by offset or assertion value.
+ if (vlvRequest == null)
+ {
+ return newDefinedSet(toArray(sortMap.values()));
+ }
+
+ if (vlvRequest.getTargetType() == VLVRequestControl.TYPE_TARGET_BYOFFSET)
+ {
+ return sortByOffset(searchOperation, vlvRequest, sortMap);
+ }
+
+ return sortByGreaterThanOrEqualAssertion(searchOperation, vlvRequest, sortMap);
+ }
+
+ // FIXME: Might be moved into a util.Longs class
+ private static final long[] toArray(Collection<? extends Number> collection)
+ {
+ checkNotNull(collection, "collection must not be null");
+ final long[] array = new long[collection.size()];
+ int i = 0;
+ for (Number number : collection)
+ {
+ array[i++] = number.longValue();
+ }
+ return array;
+ }
+
+ private static final EntryIDSet sortByGreaterThanOrEqualAssertion(SearchOperation searchOperation,
+ VLVRequestControl vlvRequest, final TreeMap<SortValues, Long> sortMap)
+ {
+ ByteString assertionValue = vlvRequest.getGreaterThanOrEqualAssertion();
+
+ boolean targetFound = false;
+ int targetOffset = 0;
+ int includedBeforeCount = 0;
+ int includedAfterCount = 0;
+
+ LinkedList<Long> idList = new LinkedList<Long>();
+ for (Map.Entry<SortValues, Long> entry : sortMap.entrySet())
+ {
+ SortValues sortValues = entry.getKey();
+ long id = entry.getValue().longValue();
+
+ if (targetFound)
+ {
+ idList.add(id);
+ includedAfterCount++;
+ if (includedAfterCount >= vlvRequest.getBeforeCount())
+ {
+ break;
+ }
+ }
+ else
+ {
+ targetFound = sortValues.compareTo(assertionValue) >= 0;
+ targetOffset++;
+
+ if (targetFound)
+ {
+ idList.add(id);
+ }
+ else if (vlvRequest.getBeforeCount() > 0)
+ {
+ idList.add(id);
+ includedBeforeCount++;
+ if (includedBeforeCount > vlvRequest.getBeforeCount())
+ {
+ idList.removeFirst();
+ includedBeforeCount--;
+ }
+ }
+ }
+ }
+
+ if (!targetFound)
+ {
+ // No entry was found to be greater than or equal to the sort key, so the target offset will be one greater
+ // than the content count.
+ targetOffset = sortMap.size() + 1;
+ }
+
+ searchOperation.addResponseControl(new VLVResponseControl(targetOffset, sortMap.size(), LDAPResultCode.SUCCESS));
+
+ return newDefinedSet(toArray(idList));
+ }
+
+ private static final EntryIDSet sortByOffset(SearchOperation searchOperation, VLVRequestControl vlvRequest,
+ TreeMap<SortValues, Long> sortMap) throws DirectoryException
+ {
+ int targetOffset = vlvRequest.getOffset();
+ if (targetOffset < 0)
+ {
+ // The client specified a negative target offset. This
+ // should never be allowed.
+ searchOperation.addResponseControl(new VLVResponseControl(targetOffset, sortMap.size(),
+ LDAPResultCode.OFFSET_RANGE_ERROR));
+
+ LocalizableMessage message = ERR_ENTRYIDSORTER_NEGATIVE_START_POS.get();
+ throw new DirectoryException(ResultCode.VIRTUAL_LIST_VIEW_ERROR, message);
+ }
+
+ // 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 = (targetOffset == 0) ? 1 : targetOffset;
+
+ int beforeCount = vlvRequest.getBeforeCount();
+ int afterCount = vlvRequest.getAfterCount();
+ int listOffset = targetOffset - 1; // VLV offsets start at 1, not 0.
+ int startPos = listOffset - beforeCount;
+ 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;
+ beforeCount = listOffset;
+ }
+ else if (startPos >= sortMap.size())
+ {
+ // 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.
+ targetOffset = sortMap.size() + 1;
+ listOffset = sortMap.size();
+ startPos = listOffset - beforeCount;
+ afterCount = 0;
+ }
+
+ int count = 1 + beforeCount + afterCount;
+
+ long[] sortedIDs = new long[count];
+
+ int treePos = 0;
+ int arrayPos = 0;
+ for (Long id : sortMap.values())
+ {
+ if (treePos++ < startPos)
+ {
+ continue;
+ }
+
+ sortedIDs[arrayPos++] = id.longValue();
+ if (arrayPos >= count)
+ {
+ break;
+ }
+ }
+
+ if (arrayPos < count)
+ {
+ // We don't have enough entries in the set to meet the requested page size, so we'll need to shorten the
+ // array.
+ sortedIDs = Arrays.copyOf(sortedIDs, arrayPos);
+ }
+
+ searchOperation.addResponseControl(new VLVResponseControl(targetOffset, sortMap.size(), LDAPResultCode.SUCCESS));
+
+ return newDefinedSet(sortedIDs);
+ }
+
/** Get the exclusive lock. */
void lock()
{
@@ -3248,4 +3444,5 @@
public String toString() {
return databasePrefix;
}
+
}
diff --git a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryIDSet.java b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryIDSet.java
index 8be2c3e..ca0c65f 100644
--- a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryIDSet.java
+++ b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryIDSet.java
@@ -26,55 +26,485 @@
*/
package org.opends.server.backends.pluggable;
-import java.util.ArrayList;
+import static org.forgerock.util.Reject.checkNotNull;
+
import java.util.Arrays;
import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
import org.forgerock.opendj.ldap.ByteSequence;
import org.forgerock.opendj.ldap.ByteSequenceReader;
import org.forgerock.opendj.ldap.ByteString;
import org.forgerock.opendj.ldap.ByteStringBuilder;
+import org.forgerock.util.Reject;
+
+import com.forgerock.opendj.util.Iterators;
/**
- * Represents a set of Entry IDs. It can represent a set where the IDs are
- * not defined, for example when the index entry limit has been exceeded.
+ * Represents a set of Entry IDs. It can represent a set where the IDs are not defined, for example when the index entry
+ * limit has been exceeded.
*/
-class EntryIDSet implements Iterable<EntryID>
+final class EntryIDSet implements Iterable<EntryID>
{
+ public static final ByteSequence NO_KEY = ByteString.valueOf("<none>");
/**
- * The IDs are stored here in an array in ascending order.
- * A null array implies not defined, rather than zero IDs.
+ * Interface for EntryIDSet concrete implementations
*/
- private long[] values;
-
- /**
- * The size of the set when it is not defined. This value is only maintained
- * when the set is undefined.
- */
- private long undefinedSize = Long.MAX_VALUE;
-
- /**
- * The database key containing this set, if the set was constructed
- * directly from the database.
- */
- private final ByteSequence key;
-
- /** Create a new undefined set. */
- public EntryIDSet()
+ private interface EntryIDSetImplementor extends Iterable<EntryID>
{
- this(Long.MAX_VALUE);
+ long size();
+
+ void toString(StringBuilder buffer);
+
+ boolean isDefined();
+
+ ByteString toByteString();
+
+ long[] getRange();
+
+ long[] getIDs();
+
+ boolean add(EntryID entryID);
+
+ boolean remove(EntryID entryID);
+
+ boolean contains(EntryID entryID);
+
+ void addAll(EntryIDSet that);
+
+ void removeAll(EntryIDSet that);
+
+ @Override
+ Iterator<EntryID> iterator();
+
+ Iterator<EntryID> iterator(EntryID begin);
+ }
+
+ /**
+ * Concrete implements representing a set of EntryIDs, sorted in ascending order.
+ */
+ private static final class DefinedImpl implements EntryIDSetImplementor
+ {
+ /**
+ * The IDs are stored here in an array in ascending order. A null array implies not defined, rather than zero IDs.
+ */
+ private long[] entryIDs;
+
+ DefinedImpl(long... entryIDs)
+ {
+ this.entryIDs = entryIDs;
+ }
+
+ @Override
+ public long size()
+ {
+ return entryIDs.length;
+ }
+
+ @Override
+ public void toString(StringBuilder buffer)
+ {
+ buffer.append("[COUNT:").append(size()).append("]");
+ }
+
+ @Override
+ public boolean isDefined()
+ {
+ return true;
+ }
+
+ @Override
+ public ByteString toByteString()
+ {
+ final ByteStringBuilder builder = new ByteStringBuilder(8 * entryIDs.length);
+ for (long value : entryIDs)
+ {
+ builder.append(value);
+ }
+ return builder.toByteString();
+ }
+
+ @Override
+ public boolean add(EntryID entryID)
+ {
+ long id = entryID.longValue();
+ if (entryIDs.length == 0)
+ {
+ entryIDs = new long[] { id };
+ }
+ else if (id > entryIDs[entryIDs.length - 1])
+ {
+ long[] updatedValues = Arrays.copyOf(entryIDs, entryIDs.length + 1);
+ updatedValues[entryIDs.length] = id;
+ entryIDs = updatedValues;
+ }
+ else
+ {
+ int pos = Arrays.binarySearch(entryIDs, id);
+ if (pos >= 0)
+ {
+ // The ID is already present.
+ return false;
+ }
+
+ // For a negative return value r, the index -(r+1) gives the array
+ // index at which the specified value can be inserted to maintain
+ // the sorted order of the array.
+ pos = -(pos + 1);
+
+ long[] updatedValues = new long[entryIDs.length + 1];
+ System.arraycopy(entryIDs, 0, updatedValues, 0, pos);
+ System.arraycopy(entryIDs, pos, updatedValues, pos + 1, entryIDs.length - pos);
+ updatedValues[pos] = id;
+ entryIDs = updatedValues;
+ }
+ return true;
+ }
+
+ @Override
+ public boolean remove(EntryID entryID)
+ {
+ // Binary search to locate the ID.
+ final int pos = Arrays.binarySearch(entryIDs, entryID.longValue());
+ if (pos >= 0)
+ {
+ // Found it.
+ final long[] updatedValues = new long[entryIDs.length - 1];
+ System.arraycopy(entryIDs, 0, updatedValues, 0, pos);
+ System.arraycopy(entryIDs, pos + 1, updatedValues, pos, entryIDs.length - pos - 1);
+ entryIDs = updatedValues;
+ return true;
+ }
+ // Not found.
+ return false;
+ }
+
+ @Override
+ public boolean contains(EntryID entryID)
+ {
+ return Arrays.binarySearch(entryIDs, entryID.longValue()) >= 0;
+ }
+
+ @Override
+ public void addAll(EntryIDSet anotherEntryIDSet)
+ {
+ if (anotherEntryIDSet.size() == 0)
+ {
+ return;
+ }
+
+ if (entryIDs.length == 0)
+ {
+ entryIDs = Arrays.copyOf(anotherEntryIDSet.getIDs(), anotherEntryIDSet.getIDs().length);
+ return;
+ }
+
+ final int overlap = compareForOverlap(getRange(), anotherEntryIDSet.getRange());
+ if (overlap < 0)
+ {
+ entryIDs = concatIdsFrom(entryIDs, anotherEntryIDSet.getIDs());
+ }
+ else if (overlap > 0)
+ {
+ entryIDs = concatIdsFrom(anotherEntryIDSet.getIDs(), entryIDs);
+ }
+ else
+ {
+ entryIDs = mergeOverlappingEntryIDSet(entryIDs, anotherEntryIDSet.getIDs());
+ }
+ }
+
+ @Override
+ public void removeAll(EntryIDSet that)
+ {
+ if (compareForOverlap(getRange(), that.getRange()) == 0)
+ {
+ // Set overlaps
+ final long[] newEntryIds = new long[entryIDs.length];
+ final long[] entriesToRemove = that.getIDs();
+
+ int sourceIndex, toRemoveIndex, targetIndex;
+ for (sourceIndex = 0, targetIndex = 0, toRemoveIndex = 0; sourceIndex < entryIDs.length
+ && toRemoveIndex < entriesToRemove.length;)
+ {
+ if (entryIDs[sourceIndex] < entriesToRemove[toRemoveIndex])
+ {
+ newEntryIds[targetIndex++] = entryIDs[sourceIndex++];
+ }
+ else if (entriesToRemove[toRemoveIndex] < entryIDs[sourceIndex])
+ {
+ toRemoveIndex++;
+ }
+ else
+ {
+ sourceIndex++;
+ toRemoveIndex++;
+ }
+ }
+
+ System.arraycopy(entryIDs, sourceIndex, newEntryIds, targetIndex, entryIDs.length - sourceIndex);
+ targetIndex += entryIDs.length - sourceIndex;
+
+ if (targetIndex < entryIDs.length)
+ {
+ entryIDs = Arrays.copyOf(newEntryIds, targetIndex);
+ }
+ else
+ {
+ entryIDs = newEntryIds;
+ }
+ }
+ }
+
+ @Override
+ public Iterator<EntryID> iterator()
+ {
+ return new IDSetIterator(entryIDs);
+ }
+
+ @Override
+ public Iterator<EntryID> iterator(EntryID begin)
+ {
+ return new IDSetIterator(entryIDs, begin == null ? 0 : begin.longValue());
+ }
+
+ @Override
+ public long[] getRange()
+ {
+ if (entryIDs.length == 0)
+ {
+ return new long[] { 0, 0 };
+ }
+ else
+ {
+ return new long[] { entryIDs[0], entryIDs[entryIDs.length - 1] };
+ }
+ }
+
+ @Override
+ public long[] getIDs()
+ {
+ return entryIDs;
+ }
+ }
+
+ /**
+ * Concrete implementation the EntryIDs are not defined, for example when the index entry limit has been exceeded.
+ */
+ private static final class UndefinedImpl implements EntryIDSetImplementor
+ {
+ /**
+ * The number of entry IDs in the set if the size is being maintained, otherwise Long.MAX_VALUE
+ */
+ private long undefinedSize;
+
+ /**
+ * The database key containing this set, if the set was constructed directly from the database.
+ */
+ private final ByteSequence databaseKey;
+
+ UndefinedImpl(ByteSequence key, long size)
+ {
+ databaseKey = checkNotNull(key, "key must not be null");
+ undefinedSize = size;
+ }
+
+ @Override
+ public long size()
+ {
+ return undefinedSize;
+ }
+
+ @Override
+ public void toString(StringBuilder buffer)
+ {
+ if (databaseKey == NO_KEY)
+ {
+ buffer.append("[NOT-INDEXED]");
+ }
+ else if (maintainUndefinedSize())
+ {
+ buffer.append("[LIMIT-EXCEEDED:").append(undefinedSize).append("]");
+ }
+ else
+ {
+ buffer.append("[LIMIT-EXCEEDED]");
+ }
+ }
+
+ private boolean maintainUndefinedSize()
+ {
+ return undefinedSize != Long.MAX_VALUE;
+ }
+
+ @Override
+ public boolean isDefined()
+ {
+ return false;
+ }
+
+ @Override
+ public ByteString toByteString()
+ {
+ // Set top bit.
+ return ByteString.valueOf(undefinedSize | Long.MIN_VALUE);
+ }
+
+ @Override
+ public boolean add(EntryID entryID)
+ {
+ if (maintainUndefinedSize())
+ {
+ undefinedSize++;
+ }
+ return true;
+ }
+
+ @Override
+ public boolean remove(EntryID entryID)
+ {
+ if (maintainUndefinedSize() && undefinedSize > 0)
+ {
+ undefinedSize--;
+ }
+ return true;
+ }
+
+ @Override
+ public boolean contains(EntryID entryID)
+ {
+ return true;
+ }
+
+ @Override
+ public void addAll(EntryIDSet that)
+ {
+ // Assume there are no overlap between IDs in that set with this set
+ if (maintainUndefinedSize())
+ {
+ undefinedSize += that.size();
+ }
+ }
+
+ @Override
+ public void removeAll(EntryIDSet that)
+ {
+ // Assume all IDs in the given set exists in this set.
+ if (maintainUndefinedSize())
+ {
+ undefinedSize = Math.max(0, undefinedSize - that.size());
+ }
+ }
+
+ @Override
+ public Iterator<EntryID> iterator()
+ {
+ return Iterators.emptyIterator();
+ }
+
+ @Override
+ public Iterator<EntryID> iterator(EntryID begin)
+ {
+ return Iterators.emptyIterator();
+ }
+
+ @Override
+ public long[] getRange()
+ {
+ return new long[] { 0, 0 };
+ }
+
+ @Override
+ public long[] getIDs()
+ {
+ return new long[0];
+ }
+
+ }
+
+ /**
+ * Iterator for a set of Entry IDs. It must return values in order of ID.
+ */
+ private static final class IDSetIterator implements Iterator<EntryID>
+ {
+ private final long[] entryIDList;
+ private int currentIndex;
+
+ IDSetIterator(long[] entryIDList)
+ {
+ this.entryIDList = entryIDList;
+ }
+
+ IDSetIterator(long[] entryIDList, long begin)
+ {
+ this(entryIDList);
+ currentIndex = Math.max(0, Arrays.binarySearch(entryIDList, begin));
+ }
+
+ @Override
+ public boolean hasNext()
+ {
+ return currentIndex < entryIDList.length;
+ }
+
+ @Override
+ public EntryID next()
+ {
+ if (hasNext())
+ {
+ return new EntryID(entryIDList[currentIndex++]);
+ }
+ throw new NoSuchElementException();
+ }
+
+ @Override
+ public void remove()
+ {
+ throw new UnsupportedOperationException();
+ }
+ }
+
+ /**
+ * Create a new undefined set
+ */
+ public static EntryIDSet newUndefinedSet()
+ {
+ return new EntryIDSet(new UndefinedImpl(NO_KEY, Long.MAX_VALUE));
+ }
+
+ /**
+ * Create a new undefined set
+ */
+ public static EntryIDSet newUndefinedSetWithKey(ByteSequence key)
+ {
+ return newUndefinedSetWithSize(key, Long.MAX_VALUE);
}
/**
* Create a new undefined set with a initial size.
*
- * @param size The undefined size for this set.
+ * @param size
+ * The undefined size for this set.
*/
- EntryIDSet(long size)
+ public static EntryIDSet newUndefinedSetWithSize(ByteSequence key, long undefinedSize)
{
- this.key = null;
- this.undefinedSize = size;
+ return new EntryIDSet(new UndefinedImpl(key, undefinedSize));
+ }
+
+ /**
+ * Create a new defined entry ID set with the specified ids.
+ *
+ * @param ids
+ * Entry IDs contained in the set.
+ * @throws NullPointerException
+ * if ids is null
+ */
+ public static EntryIDSet newDefinedSet(long... ids)
+ {
+ checkNotNull(ids, "ids must not be null");
+ return new EntryIDSet(new DefinedImpl(ids));
}
/**
@@ -84,111 +514,94 @@
* The database key that contains this value.
* @param bytes
* The database value, or null if there are no entry IDs.
+ * @throws NullPointerException
+ * if either key or value is null
*/
- EntryIDSet(ByteSequence key, ByteString bytes)
+ public static EntryIDSet newSetFromBytes(ByteSequence key, ByteString value)
{
- this.key = key;
+ checkNotNull(key, "key must not be null");
+ checkNotNull(value, "value must not be null");
- if (bytes == null)
- {
- values = new long[0];
- }
- else if (bytes.length() == 0)
+ if (value.isEmpty())
{
// Entry limit has exceeded and there is no encoded undefined set size.
- undefinedSize = Long.MAX_VALUE;
+ return newUndefinedSetWithKey(key);
}
- else if ((bytes.byteAt(0) & 0x80) == 0x80)
+ else if ((value.byteAt(0) & 0x80) == 0x80)
{
// Entry limit has exceeded and there is an encoded undefined set size.
- undefinedSize = decodeUndefinedSize(bytes);
+ return newUndefinedSetWithSize(key, decodeUndefinedSize(value));
}
else
{
- // Seems like entry limit has not been exceeded and the bytes is a
- // list of entry IDs.
- values = decodeEntryIDList(bytes);
+ // Seems like entry limit has not been exceeded and the bytes is a list of entry IDs.
+ return newDefinedSet(decodeEntryIDList(value));
}
}
- /**
- * Decodes and returns the undefined size out of the provided byte string.
- *
- * @param bytes
- * the encoded undefined size
- * @return the undefined size
- */
- static long decodeUndefinedSize(ByteString bytes)
+ private static long[] intersection(long[] set1, long[] set2)
{
- return bytes.length() == 8
- ? bytes.toLong() & Long.MAX_VALUE // remove top bit
- : Long.MAX_VALUE;
- }
+ long[] target = new long[Math.min(set1.length, set2.length)];
- /**
- * Decodes and returns the entryID list out of the provided byte sequence.
- *
- * @param bytes
- * the encoded entryID list
- * @return a long array representing the entryID list
- */
- static long[] decodeEntryIDList(ByteSequence bytes)
- {
- final ByteSequenceReader reader = bytes.asReader();
- final int count = bytes.length() / 8;
- final long[] entryIDList = new long[count];
- for (int i = 0; i < count; i++)
+ int index1, index2, ci;
+ for (index1 = 0, index2 = 0, ci = 0; index1 < set1.length && index2 < set2.length;)
{
- entryIDList[i] = reader.getLong();
+ if (set1[index1] == set2[index2])
+ {
+ target[ci++] = set1[index1++];
+ index2++;
+ }
+ else if (set1[index1] > set2[index2])
+ {
+ index2++;
+ }
+ else
+ {
+ index1++;
+ }
}
- return entryIDList;
- }
- /**
- * Construct an EntryIDSet from an array of longs.
- *
- * @param values The array of IDs represented as longs.
- * @param pos The position of the first ID to take from the array.
- * @param len the number of IDs to take from the array.
- */
- EntryIDSet(long[] values, int pos, int len)
- {
- this.key = null;
- this.values = new long[len];
- System.arraycopy(values, pos, this.values, 0, len);
+ if (ci < target.length)
+ {
+ target = Arrays.copyOf(target, ci);
+ }
+ return target;
}
/**
* Create a new set of entry IDs that is the union of several entry ID sets.
*
- * @param sets A list of entry ID sets.
- * @param allowDuplicates true if duplicate IDs are allowed in the resulting
- * set, or if the provided sets are sure not to overlap; false if
- * duplicates should be eliminated.
+ * @param sets
+ * A list of entry ID sets.
* @return The union of the provided entry ID sets.
*/
- static EntryIDSet unionOfSets(ArrayList<EntryIDSet> sets,
- boolean allowDuplicates)
+ public static EntryIDSet newSetFromUnion(List<EntryIDSet> sets)
{
+ checkNotNull(sets, "sets must not be null");
+
+ // FIXME: Benchmarks shown that its possible to have a 5x performance gain if we sort the non overlapping sets. To
+ // do that, we can use compareForOverlap(). In case sets are unordered and non overlapping, this optimization allow
+ // to skip the final sort() applied on the resulting set.
+
int count = 0;
- boolean undefined = false;
+ boolean containsUndefinedSet = false;
for (EntryIDSet l : sets)
{
if (!l.isDefined())
{
- if(l.undefinedSize == Long.MAX_VALUE)
+ if (l.size() == Long.MAX_VALUE)
{
- return new EntryIDSet();
+ return newUndefinedSet();
}
- undefined = true;
+ containsUndefinedSet = true;
}
count += l.size();
}
- if(undefined)
+ if (containsUndefinedSet)
{
- return new EntryIDSet(count);
+ return newUndefinedSetWithSize(null, count);
}
boolean needSort = false;
@@ -196,26 +609,18 @@
int pos = 0;
for (EntryIDSet l : sets)
{
- if (l.values.length != 0)
+ if (l.size() != 0)
{
- if (!needSort && pos > 0 && l.values[0] < n[pos-1])
- {
- needSort = true;
- }
- System.arraycopy(l.values, 0, n, pos, l.values.length);
- pos += l.values.length;
+ needSort |= pos > 0 && l.iterator().next().longValue() < n[pos - 1];
+ System.arraycopy(l.getIDs(), 0, n, pos, l.getIDs().length);
+ pos += l.size();
}
}
if (needSort)
{
Arrays.sort(n);
}
- if (allowDuplicates)
- {
- EntryIDSet ret = new EntryIDSet();
- ret.values = n;
- return ret;
- }
+
long[] n1 = new long[n.length];
long last = -1;
int j = 0;
@@ -228,67 +633,81 @@
}
if (j == n1.length)
{
- EntryIDSet ret = new EntryIDSet();
- ret.values = n1;
- return ret;
+ return newDefinedSet(n1);
}
else
{
- return new EntryIDSet(n1, 0, j);
+ return newDefinedSet(Arrays.copyOf(n1, j));
}
}
/**
+ * Decodes and returns the entryID list out of the provided byte sequence.
+ *
+ * @param bytes
+ * the encoded entryID list
+ * @return a long array representing the entryID list
+ */
+ public static long[] decodeEntryIDList(ByteSequence bytes)
+ {
+ final ByteSequenceReader reader = bytes.asReader();
+ final int count = bytes.length() / 8;
+ final long[] entryIDList = new long[count];
+ for (int i = 0; i < count; i++)
+ {
+ entryIDList[i] = reader.getLong();
+ }
+ return entryIDList;
+ }
+
+ /**
+ * Decodes and returns the undefined size out of the provided byte string.
+ *
+ * @param bytes
+ * the encoded undefined size
+ * @return the undefined size
+ */
+ public static long decodeUndefinedSize(ByteString bytes)
+ {
+ return bytes.length() == 8 ? bytes.toLong() & Long.MAX_VALUE : Long.MAX_VALUE; // remove top bit
+ }
+
+ private EntryIDSetImplementor concreteImpl;
+
+ private EntryIDSet(EntryIDSetImplementor concreteImpl)
+ {
+ this.concreteImpl = concreteImpl;
+ }
+
+ /**
* Get the size of this entry ID set.
*
* @return The number of IDs in the set.
*/
public long size()
{
- if (values != null)
- {
- return values.length;
- }
- return undefinedSize;
- }
-
- /**
- * Get a string representation of this object.
- * @return A string representation of this object.
- */
- @Override
- public String toString()
- {
- StringBuilder buffer = new StringBuilder(16);
- toString(buffer);
- return buffer.toString();
+ return concreteImpl.size();
}
/**
* Convert to a short string to aid with debugging.
*
- * @param sb The string is appended to this string builder.
+ * @param buffer
+ * The string is appended to this string builder.
+ * @throws NullPointerException
+ * if buffer is null
*/
- void toString(StringBuilder sb)
+ public void toString(StringBuilder buffer)
{
- if (isDefined())
- {
- sb.append("[COUNT:").append(size()).append("]");
- }
- else if (key != null)
- {
- // The index entry limit was exceeded
- sb.append("[LIMIT-EXCEEDED");
- if (undefinedSize < Long.MAX_VALUE)
- {
- sb.append(":").append(undefinedSize);
- }
- sb.append("]");
- }
- else
- {
- sb.append("[NOT-INDEXED]");
- }
+ checkNotNull(buffer, "buffer must not be null");
+ concreteImpl.toString(buffer);
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder builder = new StringBuilder(16);
+ toString(builder);
+ return builder.toString();
}
/**
@@ -296,396 +715,268 @@
*
* @return true if the set of IDs is defined.
*/
- boolean isDefined()
+ public boolean isDefined()
{
- return values != null;
+ return concreteImpl.isDefined();
}
/**
* Get a database representation of this object.
+ *
* @return A database representation of this object as a byte array.
*/
- ByteString toByteString()
+ public ByteString toByteString()
{
- if (isDefined())
- {
- final ByteStringBuilder builder = new ByteStringBuilder(8 * values.length);
- for (long value : values)
- {
- builder.append(value);
- }
- return builder.toByteString();
- }
- else
- {
- // Set top bit.
- return ByteString.valueOf(undefinedSize | Long.MIN_VALUE);
- }
+ return concreteImpl.toByteString();
}
/**
* Insert an ID into this set.
*
- * @param entryID The ID to be inserted.
- * @return true if the set was changed, false if it was not changed,
- * for example if the set is undefined or the ID was already present.
+ * @param entryID
+ * The ID to be inserted.
+ * @return true if the set was changed, false if it was not changed, for example if the set is undefined or the ID was
+ * already present.
+ * @throws NullPointerException
+ * if entryID is null
*/
public boolean add(EntryID entryID)
{
- if (values == null)
- {
- if(undefinedSize != Long.MAX_VALUE)
- {
- undefinedSize++;
- }
- return true;
- }
-
- long id = entryID.longValue();
- if (values.length == 0)
- {
- values = new long[] { id };
- return true;
- }
-
- if (id > values[values.length-1])
- {
- long[] updatedValues = Arrays.copyOf(values, values.length + 1);
- updatedValues[values.length] = id;
- values = updatedValues;
- }
- else
- {
- int pos = Arrays.binarySearch(values, id);
- if (pos >= 0)
- {
- // The ID is already present.
- return false;
- }
-
- // For a negative return value r, the index -(r+1) gives the array
- // index at which the specified value can be inserted to maintain
- // the sorted order of the array.
- pos = -(pos+1);
-
- long[] updatedValues = new long[values.length+1];
- System.arraycopy(values, 0, updatedValues, 0, pos);
- System.arraycopy(values, pos, updatedValues, pos+1, values.length-pos);
- updatedValues[pos] = id;
- values = updatedValues;
- }
-
- return true;
+ checkNotNull(entryID, "entryID must not be null");
+ return concreteImpl.add(entryID);
}
/**
* Remove an ID from this set.
*
- * @param entryID The ID to be removed
- * @return true if the set was changed, false if it was not changed,
- * for example if the set was undefined or the ID was not present.
+ * @param entryID
+ * The ID to be removed
+ * @return true if the set was changed, false if it was not changed, for example if the set was undefined or the ID
+ * was not present.
+ * @throws NullPointerException
+ * if entryID is null
*/
public boolean remove(EntryID entryID)
{
- if (values == null)
- {
- if(undefinedSize != Long.MAX_VALUE)
- {
- undefinedSize--;
- }
- return true;
- }
-
- if (values.length == 0)
- {
- return false;
- }
-
- // Binary search to locate the ID.
- long id = entryID.longValue();
- int pos = Arrays.binarySearch(values, id);
- if (pos >= 0)
- {
- // Found it.
- long[] updatedValues = new long[values.length-1];
- System.arraycopy(values, 0, updatedValues, 0, pos);
- System.arraycopy(values, pos+1, updatedValues, pos, values.length-pos-1);
- values = updatedValues;
- return true;
- }
- // Not found.
- return false;
+ checkNotNull(entryID, "entryID must not be null");
+ return concreteImpl.remove(entryID);
}
/**
* Check whether this set of entry IDs contains a given ID.
*
- * @param entryID The ID to be checked.
- * @return true if this set contains the given ID,
- * or if the set is undefined.
+ * @param entryID
+ * The ID to be checked.
+ * @return true if this set contains the given ID, or if the set is undefined.
+ * @throws NullPointerException
+ * if entryID is null
*/
- boolean contains(EntryID entryID)
+ public boolean contains(EntryID entryID)
{
- if (values == null)
- {
- return true;
- }
-
- final long id = entryID.longValue();
- return values.length != 0
- && id <= values[values.length - 1]
- && Arrays.binarySearch(values, id) >= 0;
- }
-
- /**
- * Takes the intersection of this set with another.
- * Retain those IDs that appear in the given set.
- *
- * @param that The set of IDs that are to be retained from this object.
- */
- void retainAll(EntryIDSet that)
- {
- if (!isDefined())
- {
- this.values = that.values;
- this.undefinedSize = that.undefinedSize;
- return;
- }
-
- if (!that.isDefined())
- {
- return;
- }
-
- // TODO Perhaps Arrays.asList and retainAll list method are more efficient?
-
- long[] a = this.values;
- long[] b = that.values;
-
- int ai = 0, bi = 0, ci = 0;
- long[] c = new long[Math.min(a.length,b.length)];
- while (ai < a.length && bi < b.length)
- {
- if (a[ai] == b[bi])
- {
- c[ci] = a[ai];
- ai++;
- bi++;
- ci++;
- }
- else if (a[ai] > b[bi])
- {
- bi++;
- }
- else
- {
- ai++;
- }
- }
- if (ci < c.length)
- {
- values = Arrays.copyOf(c, ci);
- }
- else
- {
- values = c;
- }
+ checkNotNull(entryID, "entryID must not be null");
+ return concreteImpl.contains(entryID);
}
/**
* Add all the IDs from a given set that are not already present.
*
- * @param that The set of IDs to be added. It MUST be defined
+ * @param that
+ * The set of IDs to be added. It MUST be defined
+ * @throws NullPointerException
+ * if that is null
+ * @throws IllegalArgumentException
+ * if that is undefined.
*/
public void addAll(EntryIDSet that)
{
- if(!that.isDefined())
- {
- return;
- }
-
- if (!isDefined())
- {
- // Assume there are no overlap between IDs in that set with this set
- if(undefinedSize != Long.MAX_VALUE)
- {
- undefinedSize += that.size();
- }
- return;
- }
-
- long[] a = this.values;
- long[] b = that.values;
-
- if (a.length == 0)
- {
- values = b;
- return;
- }
-
- if (b.length == 0)
- {
- return;
- }
-
- // Optimize for case where the two sets are sure to have no overlap.
- if (b[0] > a[a.length-1])
- {
- // All IDs in 'b' are greater than those in 'a'.
- long[] n = new long[a.length + b.length];
- System.arraycopy(a, 0, n, 0, a.length);
- System.arraycopy(b, 0, n, a.length, b.length);
- values = n;
- return;
- }
-
- if (a[0] > b[b.length-1])
- {
- // All IDs in 'a' are greater than those in 'b'.
- long[] n = new long[a.length + b.length];
- System.arraycopy(b, 0, n, 0, b.length);
- System.arraycopy(a, 0, n, b.length, a.length);
- values = n;
- return;
- }
-
- long[] n;
- if ( b.length < a.length ) {
- n = a;
- a = b;
- b = n;
- }
-
- n = new long[a.length + b.length];
-
- int ai, bi, ni;
- for ( ni = 0, ai = 0, bi = 0; ai < a.length && bi < b.length; ) {
- if ( a[ai] < b[bi] ) {
- n[ni++] = a[ai++];
- } else if ( b[bi] < a[ai] ) {
- n[ni++] = b[bi++];
- } else {
- n[ni++] = a[ai];
- ai++;
- bi++;
- }
- }
-
- // Copy any remainder from the first array.
- int aRemain = a.length - ai;
- if (aRemain > 0)
- {
- System.arraycopy(a, ai, n, ni, aRemain);
- ni += aRemain;
- }
-
- // Copy any remainder from the second array.
- int bRemain = b.length - bi;
- if (bRemain > 0)
- {
- System.arraycopy(b, bi, n, ni, bRemain);
- ni += bRemain;
- }
-
- if (ni < n.length)
- {
- values = Arrays.copyOf(n, ni);
- }
- else
- {
- values = n;
- }
+ checkNotNull(that, "that must not be null");
+ Reject.ifFalse(that.isDefined(), "that must be defined");
+ concreteImpl.addAll(that);
}
/**
- * Delete all IDs in this set that are in a given set.
+ * Takes the intersection of this set with another. Retain those IDs that appear in the given set.
*
- * @param that The set of IDs to be deleted. It MUST be defined.
+ * @param that
+ * The set of IDs that are to be retained from this object.
+ * @throws NullPointerException
+ * if that is null
*/
- void deleteAll(EntryIDSet that)
+ public void retainAll(EntryIDSet that)
{
- if(!that.isDefined())
+ checkNotNull(that, "that must not be null");
+ if (!concreteImpl.isDefined())
{
- return;
- }
-
- if (!isDefined())
- {
- // Assume all IDs in the given set exists in this set.
- if(undefinedSize != Long.MAX_VALUE)
- {
- undefinedSize -= that.size();
- }
- return;
- }
-
- long[] a = this.values;
- long[] b = that.values;
-
- if (a.length == 0 || b.length == 0
- // Optimize for cases where the two sets are sure to have no overlap.
- || b[0] > a[a.length-1]
- || a[0] > b[b.length-1])
- {
- return;
- }
-
- long[] n = new long[a.length];
-
- int ai, bi, ni;
- for ( ni = 0, ai = 0, bi = 0; ai < a.length && bi < b.length; ) {
- if ( a[ai] < b[bi] ) {
- n[ni++] = a[ai++];
- } else if ( b[bi] < a[ai] ) {
- bi++;
+ if ( that.isDefined() ) {
+ // NOTE: It's ok to share the same array instance here thanks to the copy-on-write
+ // performed by the implementation.
+ concreteImpl = new DefinedImpl(that.getIDs());
} else {
- ai++;
- bi++;
+ concreteImpl = new UndefinedImpl(NO_KEY, that.size());
}
+ return;
}
- System.arraycopy(a, ai, n, ni, a.length - ai);
- ni += a.length - ai;
-
- if (ni < a.length)
- {
- values = Arrays.copyOf(n, ni);
+ if ( !that.isDefined() ) {
+ return;
}
- else
+
+ final boolean thatSetOverlap = (compareForOverlap(getRange(), that.getRange()) == 0);
+ if (thatSetOverlap)
{
- values = n;
+ concreteImpl = new DefinedImpl(intersection(concreteImpl.getIDs(), that.getIDs()));
+ }
+ else if (size() != 0)
+ {
+ concreteImpl = new DefinedImpl();
}
}
/**
- * Create an iterator over the set or an empty iterator
- * if the set is not defined.
+ * Remove all IDs in this set that are in a given set.
+ *
+ * @param that
+ * The set of IDs to be deleted. It MUST be defined.
+ * @throws NullPointerException
+ * if that is null
+ * @throws IllegalArgumentException
+ * if that is undefined.
+ */
+ public void removeAll(EntryIDSet that)
+ {
+ checkNotNull(that, "that must not be null");
+ Reject.ifFalse(that.isDefined(), "that must be defined");
+ concreteImpl.removeAll(that);
+ }
+
+ /**
+ * Create an iterator over the set or an empty iterator if the set is not defined.
*
* @return An EntryID iterator.
*/
@Override
public Iterator<EntryID> iterator()
{
- return iterator(null);
+ return concreteImpl.iterator();
}
/**
- * Create an iterator over the set or an empty iterator
- * if the set is not defined.
+ * Create an iterator over the set or an empty iterator if the set is not defined.
*
- * @param begin The entry ID of the first entry to return in the list.
- *
+ * @param begin
+ * The entry ID of the first entry to return in the list.
* @return An EntryID iterator.
*/
- Iterator<EntryID> iterator(EntryID begin)
+ public Iterator<EntryID> iterator(EntryID begin)
{
- if (values != null)
+ return concreteImpl.iterator(begin);
+ }
+
+ private long[] getIDs()
+ {
+ return concreteImpl.getIDs();
+ }
+
+ private long[] getRange()
+ {
+ return concreteImpl.getRange();
+ }
+
+ private static long[] mergeOverlappingEntryIDSet(long set1[], long set2[])
+ {
+ final long[] a, b;
+ if (set1.length >= set2.length)
{
- // The set is defined.
- return new IDSetIterator(values, begin);
+ a = set1;
+ b = set2;
}
- // The set is not defined.
- return new IDSetIterator(new long[0]);
+ else
+ {
+ a = set2;
+ b = set1;
+ }
+
+ final long newEntryIDs[] = new long[a.length + b.length];
+ int sourceAIndex, sourceBIndex, targetIndex;
+ for (sourceAIndex = 0, sourceBIndex = 0, targetIndex = 0; sourceAIndex < a.length && sourceBIndex < b.length;)
+ {
+ if (a[sourceAIndex] < b[sourceBIndex])
+ {
+ newEntryIDs[targetIndex++] = a[sourceAIndex++];
+ }
+ else if (b[sourceBIndex] < a[sourceAIndex])
+ {
+ newEntryIDs[targetIndex++] = b[sourceBIndex++];
+ }
+ else
+ {
+ newEntryIDs[targetIndex++] = a[sourceAIndex];
+ sourceAIndex++;
+ sourceBIndex++;
+ }
+ }
+
+ targetIndex = copyRemainder(a, newEntryIDs, sourceAIndex, targetIndex);
+ targetIndex = copyRemainder(b, newEntryIDs, sourceBIndex, targetIndex);
+
+ if (targetIndex < newEntryIDs.length)
+ {
+ return Arrays.copyOf(newEntryIDs, targetIndex);
+ }
+ else
+ {
+ return newEntryIDs;
+ }
+ }
+
+ private static int copyRemainder(long[] sourceIDSet, final long[] newEntryIDs, int offset, int remainerIndex)
+ {
+ final int currentRemainder = sourceIDSet.length - offset;
+ if (currentRemainder > 0)
+ {
+ System.arraycopy(sourceIDSet, offset, newEntryIDs, remainerIndex, currentRemainder);
+ return remainerIndex + currentRemainder;
+ }
+ return remainerIndex;
+ }
+
+ private static long[] concatIdsFrom(long[] first, long[] second)
+ {
+ long[] ids = new long[first.length + second.length];
+ System.arraycopy(first, 0, ids, 0, first.length);
+ System.arraycopy(second, 0, ids, first.length, second.length);
+ return ids;
+ }
+
+ /**
+ * @return -1 if o1 < o2, 0 if o1 overlap o2, +1 if o1 > o2
+ */
+ private static final int compareForOverlap(long[] o1, long[] o2)
+ {
+ if (o1 == null && o2 == null)
+ {
+ return 0;
+ }
+ else if (o1 == null)
+ {
+ return 1;
+ }
+ else if (o2 == null)
+ {
+ return -1;
+ }
+ else if (o1[1] < o2[0])
+ {
+ return -1;
+ }
+ else if (o1[0] > o2[1])
+ {
+ return 1;
+ }
+ else
+ {
+ return 0;
+ }
}
}
diff --git a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryIDSetSorter.java b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryIDSetSorter.java
deleted file mode 100644
index 49b3ad6..0000000
--- a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryIDSetSorter.java
+++ /dev/null
@@ -1,271 +0,0 @@
-/*
- * 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
- * or http://forgerock.org/license/CDDLv1.0.html.
- * 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 2008 Sun Microsystems, Inc.
- * Portions Copyright 2011-2015 ForgeRock AS
- */
-package org.opends.server.backends.pluggable;
-
-import java.util.Iterator;
-import java.util.LinkedList;
-import java.util.Map;
-import java.util.TreeMap;
-
-import org.forgerock.i18n.LocalizableMessage;
-import org.forgerock.opendj.ldap.ByteString;
-import org.forgerock.opendj.ldap.ResultCode;
-import org.forgerock.opendj.ldap.SearchScope;
-import org.opends.server.backends.pluggable.spi.ReadableStorage;
-import org.opends.server.controls.VLVRequestControl;
-import org.opends.server.controls.VLVResponseControl;
-import org.opends.server.core.DirectoryServer;
-import org.opends.server.core.SearchOperation;
-import org.opends.server.protocols.ldap.LDAPResultCode;
-import org.opends.server.types.*;
-
-import static org.opends.messages.JebMessages.*;
-import static org.opends.server.util.StaticUtils.*;
-
-/**
- * This class provides a mechanism for sorting the contents of an entry ID set
- * based on a given sort order.
- */
-class EntryIDSetSorter
-{
- /**
- * Creates a new entry ID set which is a sorted representation of the provided
- * set using the given sort order.
- *
- * @param entryContainer The entry container with which the ID list is associated.
- * @param txn The database transaction
- * @param entryIDSet The entry ID set to be sorted.
- * @param searchOperation The search operation being processed.
- * @param sortOrder The sort order to use for the entry ID set.
- * @param vlvRequest The VLV request control included in the search
- * request, or {@code null} if there was none.
- * @return A new entry ID set which is a sorted representation of the
- * provided set using the given sort order.
- * @throws DirectoryException If an error occurs while performing the sort.
- */
- public static EntryIDSet sort(EntryContainer entryContainer,
- ReadableStorage txn,
- EntryIDSet entryIDSet,
- SearchOperation searchOperation,
- SortOrder sortOrder,
- VLVRequestControl vlvRequest)
- throws DirectoryException
- {
- if (! entryIDSet.isDefined())
- {
- return new EntryIDSet();
- }
-
- DN baseDN = searchOperation.getBaseDN();
- SearchScope scope = searchOperation.getScope();
- SearchFilter filter = searchOperation.getFilter();
-
- TreeMap<SortValues,EntryID> sortMap = new TreeMap<SortValues,EntryID>();
- for (EntryID id : entryIDSet)
- {
- try
- {
- Entry e = entryContainer.getEntry(txn, id);
- if (e.matchesBaseAndScope(baseDN, scope) && filter.matchesEntry(e))
- {
- sortMap.put(new SortValues(id, e, sortOrder), id);
- }
- }
- catch (Exception e)
- {
- LocalizableMessage message = ERR_ENTRYIDSORTER_CANNOT_EXAMINE_ENTRY.get(id, getExceptionMessage(e));
- throw new DirectoryException(DirectoryServer.getServerErrorResultCode(), message, e);
- }
- }
-
-
- // See if there is a VLV request to further pare down the set of results,
- // and if there is where it should be processed by offset or assertion value.
- long[] sortedIDs;
- if (vlvRequest != null)
- {
- int beforeCount = vlvRequest.getBeforeCount();
- int afterCount = vlvRequest.getAfterCount();
-
- if (vlvRequest.getTargetType() == VLVRequestControl.TYPE_TARGET_BYOFFSET)
- {
- int targetOffset = vlvRequest.getOffset();
- if (targetOffset < 0)
- {
- // The client specified a negative target offset. This should never be allowed.
- searchOperation.addResponseControl(
- new VLVResponseControl(targetOffset, sortMap.size(),
- LDAPResultCode.OFFSET_RANGE_ERROR));
-
- LocalizableMessage message = ERR_ENTRYIDSORTER_NEGATIVE_START_POS.get();
- throw new DirectoryException(ResultCode.VIRTUAL_LIST_VIEW_ERROR,
- 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;
- }
-
- int listOffset = targetOffset - 1; // VLV offsets start at 1, not 0.
- int startPos = listOffset - beforeCount;
- 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;
- beforeCount = listOffset;
- }
- else if (startPos >= sortMap.size())
- {
- // 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.
- targetOffset = sortMap.size() + 1;
- listOffset = sortMap.size();
- startPos = listOffset - beforeCount;
- afterCount = 0;
- }
-
- int count = 1 + beforeCount + afterCount;
- sortedIDs = new long[count];
-
- int treePos = 0;
- int arrayPos = 0;
- for (EntryID id : sortMap.values())
- {
- if (treePos++ < startPos)
- {
- continue;
- }
-
- sortedIDs[arrayPos++] = id.longValue();
- if (arrayPos >= count)
- {
- break;
- }
- }
-
- if (arrayPos < 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[arrayPos];
- System.arraycopy(sortedIDs, 0, newIDArray, 0, arrayPos);
- sortedIDs = newIDArray;
- }
-
- searchOperation.addResponseControl(
- new VLVResponseControl(targetOffset, sortMap.size(),
- LDAPResultCode.SUCCESS));
- }
- else
- {
- ByteString assertionValue = vlvRequest.getGreaterThanOrEqualAssertion();
-
- boolean targetFound = false;
- int targetOffset = 0;
- int includedBeforeCount = 0;
- int includedAfterCount = 0;
- int listSize = 0;
- LinkedList<EntryID> idList = new LinkedList<EntryID>();
- for (Map.Entry<SortValues, EntryID> entry : sortMap.entrySet())
- {
- SortValues sortValues = entry.getKey();
- EntryID id = entry.getValue();
-
- if (targetFound)
- {
- idList.add(id);
- listSize++;
- includedAfterCount++;
- if (includedAfterCount >= afterCount)
- {
- break;
- }
- }
- else
- {
- targetFound = sortValues.compareTo(assertionValue) >= 0;
- targetOffset++;
-
- if (targetFound)
- {
- idList.add(id);
- listSize++;
- }
- else if (beforeCount > 0)
- {
- idList.add(id);
- includedBeforeCount++;
- if (includedBeforeCount > beforeCount)
- {
- idList.removeFirst();
- includedBeforeCount--;
- }
- else
- {
- listSize++;
- }
- }
- }
- }
-
- if (! targetFound)
- {
- // No entry was found to be greater than or equal to the sort key, so
- // the target offset will be one greater than the content count.
- targetOffset = sortMap.size() + 1;
- }
-
- sortedIDs = new long[listSize];
- Iterator<EntryID> idIterator = idList.iterator();
- for (int i=0; i < listSize; i++)
- {
- sortedIDs[i] = idIterator.next().longValue();
- }
-
- searchOperation.addResponseControl(
- new VLVResponseControl(targetOffset, sortMap.size(),
- LDAPResultCode.SUCCESS));
- }
- }
- else
- {
- sortedIDs = new long[sortMap.size()];
- int i=0;
- for (EntryID id : sortMap.values())
- {
- sortedIDs[i++] = id.longValue();
- }
- }
-
- return new EntryIDSet(sortedIDs, 0, sortedIDs.length);
- }
-}
diff --git a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IDSetIterator.java b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IDSetIterator.java
deleted file mode 100644
index 2962bf5..0000000
--- a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IDSetIterator.java
+++ /dev/null
@@ -1,133 +0,0 @@
-/*
- * 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
- * or http://forgerock.org/license/CDDLv1.0.html.
- * 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 2014-2015 ForgeRock AS
- */
-package org.opends.server.backends.pluggable;
-
-import java.util.Iterator;
-import java.util.NoSuchElementException;
-
-/**
- * Iterator for a set of Entry IDs. It must return values in order of ID.
- */
-class IDSetIterator implements Iterator<EntryID>
-{
- /**
- * An array of ID values in order of ID.
- */
- private final long[] entryIDList;
-
- /**
- * Current position of the iterator as an index into the array of IDs.
- */
- private int i;
-
- /**
- * Create a new iterator for a given array of entry IDs.
- * @param entryIDList An array of IDs in order or ID.
- */
- IDSetIterator(long[] entryIDList)
- {
- this.entryIDList = entryIDList;
- }
-
- /**
- * Create a new iterator for a given array of entry IDs.
- * @param entryIDList An array of IDs in order or ID.
- * @param begin The entry ID of the first entry that should be returned, or
- * {@code null} if it should start at the beginning of the list.
- */
- IDSetIterator(long[] entryIDList, EntryID begin)
- {
- this.entryIDList = entryIDList;
-
- if (begin == null)
- {
- i = 0;
- }
- else
- {
- for (i=0; i < entryIDList.length; i++)
- {
- if (entryIDList[i] == begin.longValue())
- {
- break;
- }
- }
-
- if (i >= entryIDList.length)
- {
- i = 0;
- }
- }
- }
-
- /**
- * Returns <tt>true</tt> if the iteration has more elements. (In other
- * words, returns <tt>true</tt> if <tt>next</tt> would return an element
- * rather than throwing an exception.)
- *
- * @return <tt>true</tt> if the iterator has more elements.
- */
- public boolean hasNext()
- {
- return i < entryIDList.length;
- }
-
- /**
- * Returns the next element in the iteration. Calling this method
- * repeatedly until the {@link #hasNext()} method returns false will
- * return each element in the underlying collection exactly once.
- *
- * @return the next element in the iteration.
- * @throws java.util.NoSuchElementException
- * iteration has no more elements.
- */
- public EntryID next()
- throws NoSuchElementException
- {
- if (i < entryIDList.length)
- {
- return new EntryID(entryIDList[i++]);
- }
- throw new NoSuchElementException();
- }
-
- /**
- *
- * Removes from the underlying collection the last element returned by the
- * iterator (optional operation). This method can be called only once per
- * call to <tt>next</tt>. The behavior of an iterator is unspecified if
- * the underlying collection is modified while the iteration is in
- * progress in any way other than by calling this method.
- *
- * @exception UnsupportedOperationException if the <tt>remove</tt>
- * operation is not supported by this Iterator.
- */
- public void remove() throws UnsupportedOperationException
- {
- throw new UnsupportedOperationException();
- }
-}
diff --git a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/ImportIDSet.java b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/ImportIDSet.java
index 717a3cc..f138cc1 100644
--- a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/ImportIDSet.java
+++ b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/ImportIDSet.java
@@ -26,6 +26,9 @@
*/
package org.opends.server.backends.pluggable;
+import static org.opends.server.backends.pluggable.EntryIDSet.decodeEntryIDList;
+import static org.opends.server.backends.pluggable.EntryIDSet.decodeUndefinedSize;
+
import org.forgerock.opendj.ldap.ByteSequence;
import org.forgerock.opendj.ldap.ByteString;
import org.forgerock.opendj.ldap.ByteStringBuilder;
@@ -147,18 +150,18 @@
boolean dbUndefined = isDBUndefined(dBbytes);
if (dbUndefined && !importIdSet.isDefined()) {
- undefinedSize = EntryIDSet.decodeUndefinedSize(dBbytes) + importIdSet.undefinedSize;
+ undefinedSize = decodeUndefinedSize(dBbytes) + importIdSet.undefinedSize;
isDefined=false;
} else if (dbUndefined && importIdSet.isDefined()) {
- undefinedSize = EntryIDSet.decodeUndefinedSize(dBbytes) + importIdSet.size();
+ undefinedSize = decodeUndefinedSize(dBbytes) + importIdSet.size();
isDefined=false;
} else if(!importIdSet.isDefined()) {
- int dbSize = EntryIDSet.decodeEntryIDList(dBbytes).length;
+ int dbSize = decodeEntryIDList(dBbytes).length;
undefinedSize = dbSize + importIdSet.undefinedSize;
isDefined = false;
incrementLimitCount = true;
} else {
- array = EntryIDSet.decodeEntryIDList(dBbytes);
+ array = decodeEntryIDList(dBbytes);
if (array.length + importIdSet.size() > indexEntryLimit) {
undefinedSize = array.length + importIdSet.size();
isDefined=false;
@@ -187,7 +190,7 @@
isDefined=false;
undefinedSize = Long.MAX_VALUE;
} else {
- array = EntryIDSet.decodeEntryIDList(bytes);
+ array = decodeEntryIDList(bytes);
if (array.length - importIdSet.size() > indexEntryLimit) {
isDefined=false;
count = 0;
@@ -226,7 +229,7 @@
undefinedSize = Long.MAX_VALUE;
count = 0;
} else {
- array = EntryIDSet.decodeEntryIDList(bytes);
+ array = decodeEntryIDList(bytes);
if (array.length + importIdSet.size() > indexEntryLimit) {
isDefined = false;
incrementLimitCount = true;
diff --git a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/Index.java b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/Index.java
index 8b5b7d8..a90edd3 100644
--- a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/Index.java
+++ b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/Index.java
@@ -26,7 +26,12 @@
*/
package org.opends.server.backends.pluggable;
-import static org.opends.messages.JebMessages.*;
+import static org.opends.messages.JebMessages.ERR_JEB_INDEX_CORRUPT_REQUIRES_REBUILD;
+import static org.opends.server.backends.pluggable.EntryIDSet.newDefinedSet;
+import static org.opends.server.backends.pluggable.EntryIDSet.newSetFromBytes;
+import static org.opends.server.backends.pluggable.EntryIDSet.newSetFromUnion;
+import static org.opends.server.backends.pluggable.EntryIDSet.newUndefinedSetWithSize;
+import static org.opends.server.backends.pluggable.EntryIDSet.newUndefinedSet;
import java.util.ArrayList;
import java.util.HashSet;
@@ -246,8 +251,8 @@
ByteString value = txn.read(getName(), key);
if (value != null)
{
- EntryIDSet entryIDList = new EntryIDSet(key, value);
- if (entryIDList.isDefined())
+ EntryIDSet entryIDSet = newSetFromBytes(key, value);
+ if (entryIDSet.isDefined())
{
updateKeyWithRMW(txn, key, deletedIDs, addedIDs);
} // else the record exists but we've hit all IDs.
@@ -285,8 +290,8 @@
final ByteString value = txn.getRMW(getName(), key);
if (value != null)
{
- EntryIDSet entryIDList = computeEntryIDList(key, value, deletedIDs, addedIDs);
- ByteString after = entryIDList.toByteString();
+ EntryIDSet entryIDSet = computeEntryIDList(key, value, deletedIDs, addedIDs);
+ ByteString after = entryIDSet.toByteString();
if (!after.isEmpty())
{
txn.create(getName(), key, after);
@@ -316,25 +321,25 @@
private EntryIDSet computeEntryIDList(ByteString key, ByteString value, EntryIDSet deletedIDs,
EntryIDSet addedIDs)
{
- EntryIDSet entryIDList = new EntryIDSet(key, value);
+ EntryIDSet entryIDSet = newSetFromBytes(key, value);
if(addedIDs != null)
{
- if(entryIDList.isDefined() && indexEntryLimit > 0)
+ if(entryIDSet.isDefined() && indexEntryLimit > 0)
{
long idCountDelta = addedIDs.size();
if(deletedIDs != null)
{
idCountDelta -= deletedIDs.size();
}
- if(idCountDelta + entryIDList.size() >= indexEntryLimit)
+ if(idCountDelta + entryIDSet.size() >= indexEntryLimit)
{
if(maintainCount)
{
- entryIDList = new EntryIDSet(entryIDList.size() + idCountDelta);
+ entryIDSet = newUndefinedSetWithSize(key, entryIDSet.size() + idCountDelta);
}
else
{
- entryIDList = new EntryIDSet();
+ entryIDSet = newUndefinedSet();
}
entryLimitExceededCount++;
@@ -350,27 +355,27 @@
}
else
{
- entryIDList.addAll(addedIDs);
+ entryIDSet.addAll(addedIDs);
if(deletedIDs != null)
{
- entryIDList.deleteAll(deletedIDs);
+ entryIDSet.removeAll(deletedIDs);
}
}
}
else
{
- entryIDList.addAll(addedIDs);
+ entryIDSet.addAll(addedIDs);
if(deletedIDs != null)
{
- entryIDList.deleteAll(deletedIDs);
+ entryIDSet.removeAll(deletedIDs);
}
}
}
else if(deletedIDs != null)
{
- entryIDList.deleteAll(deletedIDs);
+ entryIDSet.removeAll(deletedIDs);
}
- return entryIDList;
+ return entryIDSet;
}
final void removeID(IndexBuffer buffer, ByteString keyBytes, EntryID entryID)
@@ -426,12 +431,12 @@
ByteString value = txn.read(getName(), key);
if (value != null)
{
- EntryIDSet entryIDList = new EntryIDSet(key, value);
- if (!entryIDList.isDefined())
+ EntryIDSet entryIDSet = newSetFromBytes(key, value);
+ if (!entryIDSet.isDefined())
{
return ConditionResult.UNDEFINED;
}
- return ConditionResult.valueOf(entryIDList.contains(entryID));
+ return ConditionResult.valueOf(entryIDSet.contains(entryID));
}
else if (trusted)
{
@@ -447,7 +452,7 @@
{
if(rebuildRunning)
{
- return new EntryIDSet();
+ return newUndefinedSet();
}
try
@@ -457,19 +462,19 @@
{
if(trusted)
{
- return new EntryIDSet(key, null);
+ return newDefinedSet();
}
else
{
- return new EntryIDSet();
+ return newUndefinedSet();
}
}
- return new EntryIDSet(key, value);
+ return newSetFromBytes(key, value);
}
catch (StorageRuntimeException e)
{
logger.traceException(e);
- return new EntryIDSet();
+ return newUndefinedSet();
}
}
@@ -502,7 +507,7 @@
// If this index is not trusted, then just return an undefined id set.
if(rebuildRunning || !trusted)
{
- return new EntryIDSet();
+ return newUndefinedSet();
}
try
@@ -510,7 +515,7 @@
// Total number of IDs found so far.
int totalIDCount = 0;
- ArrayList<EntryIDSet> lists = new ArrayList<EntryIDSet>();
+ ArrayList<EntryIDSet> sets = new ArrayList<EntryIDSet>();
Cursor cursor = txn.openCursor(getName());
try
@@ -537,7 +542,7 @@
if (!success)
{
// There are no values.
- return new EntryIDSet(lowerIncluded ? lower : null, null);
+ return newDefinedSet();
}
// Step through the keys until we hit the upper bound or the last key.
@@ -553,23 +558,23 @@
}
}
- EntryIDSet list = new EntryIDSet(cursor.getKey(), cursor.getValue());
- if (!list.isDefined())
+ EntryIDSet set = newSetFromBytes(cursor.getKey(), cursor.getValue());
+ if (!set.isDefined())
{
// There is no point continuing.
- return list;
+ return set;
}
- totalIDCount += list.size();
+ totalIDCount += set.size();
if (cursorEntryLimit > 0 && totalIDCount > cursorEntryLimit)
{
// There are too many. Give up and return an undefined list.
- return new EntryIDSet();
+ return newUndefinedSet();
}
- lists.add(list);
+ sets.add(set);
success = cursor.next();
}
- return EntryIDSet.unionOfSets(lists, false);
+ return newSetFromUnion(sets);
}
finally
{
@@ -579,7 +584,7 @@
catch (StorageRuntimeException e)
{
logger.traceException(e);
- return new EntryIDSet();
+ return newUndefinedSet();
}
}
diff --git a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexBuffer.java b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexBuffer.java
index c8fd193..d954acc 100644
--- a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexBuffer.java
+++ b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexBuffer.java
@@ -26,6 +26,8 @@
*/
package org.opends.server.backends.pluggable;
+import static org.opends.server.backends.pluggable.EntryIDSet.newDefinedSet;
+
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
@@ -82,7 +84,7 @@
{
if (this.addedIDs == null)
{
- this.addedIDs = new EntryIDSet(keyBytes, null);
+ this.addedIDs = newDefinedSet();
}
this.addedIDs.add(entryID);
}
@@ -100,7 +102,7 @@
{
if (this.deletedIDs == null)
{
- this.deletedIDs = new EntryIDSet(keyBytes, null);
+ this.deletedIDs = newDefinedSet();
}
this.deletedIDs.add(entryID);
}
diff --git a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexFilter.java b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexFilter.java
index d73902a..63a9fb6 100644
--- a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexFilter.java
+++ b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexFilter.java
@@ -26,6 +26,10 @@
*/
package org.opends.server.backends.pluggable;
+import static org.opends.messages.JebMessages.INFO_JEB_INDEX_FILTER_INDEX_TYPE_DISABLED;
+import static org.opends.server.backends.pluggable.EntryIDSet.newSetFromUnion;
+import static org.opends.server.backends.pluggable.EntryIDSet.newUndefinedSet;
+
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
@@ -37,8 +41,6 @@
import org.opends.server.types.FilterType;
import org.opends.server.types.SearchFilter;
-import static org.opends.messages.JebMessages.*;
-
/**
* An index filter is used to apply a search operation to a set of indexes
* to generate a set of candidate entries.
@@ -51,6 +53,11 @@
*/
static final int FILTER_CANDIDATE_THRESHOLD = 10;
+ /**
+ * Limit on the number of entry IDs that may be retrieved by cursoring through an index.
+ */
+ static final int CURSOR_ENTRY_LIMIT = 100000;
+
/** The entry container holding the attribute indexes. */
private final EntryContainer entryContainer;
private final ReadableStorage txn;
@@ -96,10 +103,7 @@
*/
EntryIDSet evaluate()
{
- if (buffer != null)
- {
- buffer.append("filter=");
- }
+ appendToDebugBuffer("filter=");
return evaluateFilter(searchOp.getFilter());
}
@@ -124,27 +128,15 @@
switch (filter.getFilterType())
{
case AND:
- if (buffer != null)
- {
- buffer.append("(&");
- }
+ appendToDebugBuffer("(&");
final EntryIDSet res1 = evaluateLogicalAndFilter(filter);
- if (buffer != null)
- {
- buffer.append(")");
- }
+ appendToDebugBuffer(")");
return res1;
case OR:
- if (buffer != null)
- {
- buffer.append("(|");
- }
+ appendToDebugBuffer("(|");
final EntryIDSet res2 = evaluateLogicalOrFilter(filter);
- if (buffer != null)
- {
- buffer.append(")");
- }
+ appendToDebugBuffer(")");
return res2;
case EQUALITY:
@@ -179,7 +171,7 @@
filter.toString(buffer);
}
//NYI
- return new EntryIDSet();
+ return newUndefinedSet();
}
}
@@ -191,9 +183,6 @@
*/
private EntryIDSet evaluateLogicalAndFilter(SearchFilter andFilter)
{
- // Start off with an undefined set.
- EntryIDSet results = new EntryIDSet();
-
// Put the slow range filters (greater-or-equal, less-or-equal)
// into a hash map, the faster components (equality, presence, approx)
// into one list and the remainder into another list.
@@ -230,13 +219,13 @@
}
}
+ EntryIDSet results = newUndefinedSet();
// First, process the fast components.
- if (evaluateFilters(results, fastComps)
- // Next, process the other (non-range) components.
- || evaluateFilters(results, otherComps)
- // Are there any range component pairs like (cn>=A)(cn<=B) ?
- || rangeComps.isEmpty())
- {
+ results = applyFiltersUntilThreshold(results, fastComps);
+ // Next, process the other (non-range) components.
+ results = applyFiltersUntilThreshold(results, otherComps);
+
+ if ( isBelowFilterThreshold(results) || rangeComps.isEmpty() ) {
return results;
}
@@ -268,7 +257,8 @@
{
monitor.updateStats(SearchFilter.createANDFilter(rangeList), set.size());
}
- if (retainAll(results, set))
+ results.retainAll(set);
+ if (isBelowFilterThreshold(results))
{
return results;
}
@@ -281,39 +271,23 @@
}
// Finally, process the remaining slow range components.
- evaluateFilters(results, remainComps);
+ return applyFiltersUntilThreshold(results, remainComps);
+ }
+ private EntryIDSet applyFiltersUntilThreshold(EntryIDSet results, ArrayList<SearchFilter> filters)
+ {
+ for(SearchFilter filter : filters) {
+ if (isBelowFilterThreshold(results)) {
+ return results;
+ }
+ results.retainAll(evaluateFilter(filter));
+ }
return results;
}
- private boolean evaluateFilters(EntryIDSet results, ArrayList<SearchFilter> filters)
+ private boolean isBelowFilterThreshold(EntryIDSet set)
{
- for (SearchFilter filter : filters)
- {
- final EntryIDSet filteredSet = evaluateFilter(filter);
- if (retainAll(results, filteredSet))
- {
- return true;
- }
- }
- return false;
- }
-
- /**
- * Retain all IDs in a given set that appear in a second set.
- *
- * @param a The set of entry IDs to be updated.
- * @param b Only those IDs that are in this set are retained.
- * @return true if the number of IDs in the updated set is now below
- * the filter candidate threshold.
- */
- private boolean retainAll(EntryIDSet a, EntryIDSet b)
- {
- a.retainAll(b);
-
- // We may have reached the point of diminishing returns where
- // it is quicker to stop now and process the current small number of candidates.
- return a.isDefined() && a.size() <= FILTER_CANDIDATE_THRESHOLD;
+ return set.isDefined() && set.size() <= FILTER_CANDIDATE_THRESHOLD;
}
/**
@@ -337,7 +311,7 @@
}
candidateSets.add(set);
}
- return EntryIDSet.unionOfSets(candidateSets, false);
+ return newSetFromUnion(candidateSets);
}
private EntryIDSet evaluateFilterWithDiagnostic(IndexFilterType indexFilterType, SearchFilter filter)
@@ -363,7 +337,7 @@
monitor.updateStats(filter, INFO_JEB_INDEX_FILTER_INDEX_TYPE_DISABLED.get(
indexFilterType.toString(), filter.getAttributeType().getNameOrOID()));
}
- return new EntryIDSet();
+ return newUndefinedSet();
}
/**
@@ -390,4 +364,12 @@
}
return IndexQuery.createNullIndexQuery().evaluate(null);
}
+
+ private void appendToDebugBuffer(String content)
+ {
+ if (buffer != null)
+ {
+ buffer.append(content);
+ }
+ }
}
diff --git a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexQuery.java b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexQuery.java
index ac34069..42dd2bc 100644
--- a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexQuery.java
+++ b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexQuery.java
@@ -26,7 +26,9 @@
*/
package org.opends.server.backends.pluggable;
-import static org.opends.server.backends.pluggable.IndexFilter.*;
+import static org.opends.server.backends.pluggable.EntryIDSet.newUndefinedSet;
+import static org.opends.server.backends.pluggable.IndexFilter.CURSOR_ENTRY_LIMIT;
+import static org.opends.server.backends.pluggable.IndexFilter.FILTER_CANDIDATE_THRESHOLD;
import java.util.Collection;
@@ -91,7 +93,6 @@
return new NullIndexQuery();
}
-
/**
* This class creates a Null IndexQuery. It is used when there is no
* record in the index. It may also be used when the index contains
@@ -103,7 +104,7 @@
@Override
public EntryIDSet evaluate(LocalizableMessageBuilder debugMessage)
{
- return new EntryIDSet();
+ return newUndefinedSet();
}
@Override
@@ -194,8 +195,7 @@
{
entryIDs.addAll(query.evaluate(debugMessage));
}
- if (entryIDs.isDefined()
- && entryIDs.size() <= FILTER_CANDIDATE_THRESHOLD)
+ if (entryIDs.isDefined() && entryIDs.size() >= CURSOR_ENTRY_LIMIT)
{
break;
}
diff --git a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexQueryFactoryImpl.java b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexQueryFactoryImpl.java
index 51ea65a..713b3f8 100644
--- a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexQueryFactoryImpl.java
+++ b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IndexQueryFactoryImpl.java
@@ -27,6 +27,7 @@
package org.opends.server.backends.pluggable;
import static org.opends.messages.JebMessages.*;
+import static org.opends.server.backends.pluggable.EntryIDSet.newUndefinedSet;
import java.util.Collection;
@@ -182,7 +183,7 @@
{
debugMessage.append(INFO_JEB_INDEX_FILTER_INDEX_TYPE_DISABLED.get(indexID, ""));
}
- return new EntryIDSet();
+ return newUndefinedSet();
}
final EntryIDSet entrySet = index.read(txn, PresenceIndexer.presenceKey);
diff --git a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/NullIndex.java b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/NullIndex.java
index dbf5d52..8e1ca67 100644
--- a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/NullIndex.java
+++ b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/NullIndex.java
@@ -24,6 +24,8 @@
*/
package org.opends.server.backends.pluggable;
+import static org.opends.server.backends.pluggable.EntryIDSet.newUndefinedSet;
+
import java.util.List;
import java.util.Set;
@@ -76,14 +78,14 @@
@Override
EntryIDSet read(ReadableStorage txn, ByteSequence key)
{
- return new EntryIDSet();
+ return newUndefinedSet();
}
@Override
EntryIDSet readRange(ReadableStorage txn, ByteSequence lower, ByteSequence upper, boolean lowerIncluded,
boolean upperIncluded)
{
- return new EntryIDSet();
+ return newUndefinedSet();
}
@Override
diff --git a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VLVIndex.java b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VLVIndex.java
index 002a33e..d324545 100644
--- a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VLVIndex.java
+++ b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VLVIndex.java
@@ -28,6 +28,7 @@
import static org.opends.messages.JebMessages.*;
import static org.opends.server.util.StaticUtils.*;
+import static org.opends.server.backends.pluggable.EntryIDSet.newDefinedSet;
import java.io.Closeable;
import java.util.Iterator;
@@ -915,7 +916,7 @@
debugBuilder.append("]");
}
}
- return new EntryIDSet(selectedIDs, 0, selectedIDs.length);
+ return newDefinedSet(selectedIDs);
}
/**
diff --git a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VerifyJob.java b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VerifyJob.java
index 35e8f02..a49be7b 100644
--- a/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VerifyJob.java
+++ b/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VerifyJob.java
@@ -28,6 +28,7 @@
import static org.opends.messages.JebMessages.*;
import static org.opends.server.backends.pluggable.JebFormat.*;
+import static org.opends.server.backends.pluggable.EntryIDSet.newSetFromBytes;
import java.util.AbstractSet;
import java.util.ArrayList;
@@ -597,11 +598,11 @@
continue;
}
- EntryIDSet entryIDList;
+ EntryIDSet entryIDSet;
try
{
- entryIDList = new EntryIDSet(key, value);
+ entryIDSet = newSetFromBytes(key, value);
}
catch (Exception e)
{
@@ -616,9 +617,9 @@
continue;
}
- updateIndexStats(entryIDList);
+ updateIndexStats(entryIDSet);
- if (entryIDList.isDefined())
+ if (entryIDSet.isDefined())
{
Entry entry;
try
@@ -642,7 +643,7 @@
continue;
}
- for (EntryID id : entryIDList)
+ for (EntryID id : entryIDSet)
{
Entry childEntry;
try
@@ -723,10 +724,10 @@
continue;
}
- EntryIDSet entryIDList;
+ EntryIDSet entryIDSet;
try
{
- entryIDList = new EntryIDSet(key, value);
+ entryIDSet = newSetFromBytes(key, value);
}
catch (Exception e)
{
@@ -741,9 +742,9 @@
continue;
}
- updateIndexStats(entryIDList);
+ updateIndexStats(entryIDSet);
- if (entryIDList.isDefined())
+ if (entryIDSet.isDefined())
{
Entry entry;
try
@@ -767,7 +768,7 @@
continue;
}
- for (EntryID id : entryIDList)
+ for (EntryID id : entryIDSet)
{
Entry subordEntry;
try
@@ -994,10 +995,10 @@
final ByteString key = cursor.getKey();
ByteString value = cursor.getValue();
- EntryIDSet entryIDList;
+ EntryIDSet entryIDSet;
try
{
- entryIDList = new EntryIDSet(key, value);
+ entryIDSet = newSetFromBytes(key, value);
}
catch (Exception e)
{
@@ -1012,13 +1013,13 @@
continue;
}
- updateIndexStats(entryIDList);
+ updateIndexStats(entryIDSet);
- if (entryIDList.isDefined())
+ if (entryIDSet.isDefined())
{
EntryID prevID = null;
- for (EntryID id : entryIDList)
+ for (EntryID id : entryIDSet)
{
if (prevID != null && id.equals(prevID) && logger.isTraceEnabled())
{
diff --git a/opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/EntryIDSetTest.java b/opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/EntryIDSetTest.java
new file mode 100644
index 0000000..b7510b5
--- /dev/null
+++ b/opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/EntryIDSetTest.java
@@ -0,0 +1,356 @@
+/*
+ * 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
+ * or http://forgerock.org/license/CDDLv1.0.html.
+ * 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 2015 ForgeRock AS
+ */
+package org.opends.server.backends.pluggable;
+
+import static org.assertj.core.api.Assertions.assertThat;
+import static org.opends.server.backends.pluggable.EntryIDSet.decodeEntryIDList;
+import static org.opends.server.backends.pluggable.EntryIDSet.newDefinedSet;
+import static org.opends.server.backends.pluggable.EntryIDSet.newSetFromBytes;
+import static org.opends.server.backends.pluggable.EntryIDSet.newSetFromUnion;
+import static org.opends.server.backends.pluggable.EntryIDSet.newUndefinedSetWithKey;
+import static org.opends.server.backends.pluggable.EntryIDSet.newUndefinedSetWithSize;
+import static org.opends.server.backends.pluggable.EntryIDSet.newUndefinedSet;
+import static org.opends.server.backends.pluggable.Utils.assertIdsEquals;
+
+import java.util.Arrays;
+
+import org.forgerock.opendj.ldap.ByteString;
+import org.opends.server.DirectoryServerTestCase;
+import org.testng.annotations.Test;
+
+@Test(groups = { "precommit", "pluggablebackend" }, sequential=true)
+public class EntryIDSetTest extends DirectoryServerTestCase
+{
+
+ private final static int UNDEFINED_INITIAL_SIZE = 10;
+ private final static ByteString KEY = ByteString.valueOf("test");
+
+ @Test(expectedExceptions = NullPointerException.class)
+ public void testDefinedCannotCreateWithNull()
+ {
+ newDefinedSet(null);
+ }
+
+ @Test
+ public void testDefinedAdd()
+ {
+ EntryIDSet set = newDefinedSet(6, 8, 10, 12);
+
+ assertThat(set.add(new EntryID(4))).isTrue();
+ assertIdsEquals(set, 4L, 6, 8, 10, 12);
+
+ assertThat(set.add(new EntryID(14L))).isTrue();
+ assertIdsEquals(set, 4L, 6, 8, 10, 12, 14L);
+
+ assertThat(set.add(new EntryID(11))).isTrue();
+ assertIdsEquals(set, 4L, 6, 8, 10, 11, 12, 14L);
+
+ assertThat(set.add(new EntryID(10))).isFalse();
+ assertIdsEquals(set, 4L, 6, 8, 10, 11, 12, 14);
+ }
+
+ @Test
+ public void testDefinedAddAll()
+ {
+ EntryIDSet set = newDefinedSet(10, 12);
+
+ // Add nothing
+ set.addAll(newDefinedSet());
+ assertIdsEquals(set, 10, 12);
+
+ // Prepend
+ set.addAll(newDefinedSet(6, 8));
+ assertIdsEquals(set, 6, 8, 10, 12);
+
+ // Append
+ set.addAll(newDefinedSet(14, 16));
+ assertIdsEquals(set, 6, 8, 10, 12, 14, 16);
+
+ // Prepend & middle
+ set.addAll(newDefinedSet(2, 4, 6, 8, 9));
+ assertIdsEquals(set, 2, 4, 6, 8, 9, 10, 12, 14, 16);
+
+ // Middle & append
+ set.addAll(newDefinedSet(13, 14, 16, 18, 20));
+ assertIdsEquals(set, 2, 4, 6, 8, 9, 10, 12, 13, 14, 16, 18, 20);
+
+ // Fully overlapping
+ set.addAll(newDefinedSet(1, 2, 4, 6, 8, 9, 10, 12, 13, 14, 16, 18, 20, 21));
+ assertIdsEquals(set, 1, 2, 4, 6, 8, 9, 10, 12, 13, 14, 16, 18, 20, 21);
+ }
+
+ @Test
+ public void testDefinedRemove()
+ {
+ EntryIDSet set = newDefinedSet(4, 6, 8, 10, 12, 14);
+
+ assertThat(set.remove(new EntryID(4))).isTrue();
+ assertIdsEquals(set, 6, 8, 10, 12, 14);
+
+ assertThat(set.remove(new EntryID(14))).isTrue();
+ assertIdsEquals(set, 6, 8, 10, 12);
+
+ assertThat(set.remove(new EntryID(10))).isTrue();
+ assertIdsEquals(set, 6, 8, 12);
+
+ assertThat(set.remove(new EntryID(10))).isFalse();
+ assertIdsEquals(set, 6, 8, 12);
+ }
+
+ @Test
+ public void testDefinedRemoveAll()
+ {
+ EntryIDSet set = newDefinedSet(1, 2, 4, 6, 8, 9, 10, 12, 13, 14, 16, 18, 20, 21);
+
+ // Remove nothing
+ set.removeAll(newDefinedSet());
+ assertIdsEquals(set, 1, 2, 4, 6, 8, 9, 10, 12, 13, 14, 16, 18, 20, 21);
+
+ // Sequential from the beginning
+ set.removeAll(newDefinedSet(0, 1, 2));
+ assertIdsEquals(set, 4, 6, 8, 9, 10, 12, 13, 14, 16, 18, 20, 21);
+
+ // Sequential from the end
+ set.removeAll(newDefinedSet(20, 21, 22));
+ assertIdsEquals(set, 4, 6, 8, 9, 10, 12, 13, 14, 16, 18);
+
+ // Random in the middle
+ set.removeAll(newDefinedSet(9, 13));
+ assertIdsEquals(set, 4, 6, 8, 10, 12, 14, 16, 18);
+
+ // All missing
+ set.removeAll(newDefinedSet(1, 5, 11, 17));
+ assertIdsEquals(set, 4, 6, 8, 10, 12, 14, 16, 18);
+ }
+
+ @Test
+ public void testDefinedContain()
+ {
+ EntryIDSet set = newDefinedSet(4, 6, 8, 10, 12, 14);
+
+ assertThat(set.contains(new EntryID(2))).isFalse();
+ assertThat(set.contains(new EntryID(4))).isTrue();
+
+ assertThat(set.contains(new EntryID(9))).isFalse();
+ assertThat(set.contains(new EntryID(10))).isTrue();
+
+ assertThat(set.contains(new EntryID(14))).isTrue();
+ assertThat(set.contains(new EntryID(16))).isFalse();
+ }
+
+ @Test
+ public void testDefinedIterator()
+ {
+ assertIdsEquals(newDefinedSet(4, 6, 8, 10, 12).iterator(), 4L, 6L, 8L, 10L, 12L);
+ }
+
+ @Test
+ public void testDefinedIteratorWithBegin()
+ {
+ EntryIDSet set = newDefinedSet(4, 6, 8, 10, 12);
+
+ assertIdsEquals(set.iterator(new EntryID(4)), 4L, 6L, 8L, 10L, 12L);
+ assertIdsEquals(set.iterator(new EntryID(8)), 8L, 10L, 12L);
+ assertIdsEquals(set.iterator(new EntryID(12)), 12L);
+ assertIdsEquals(set.iterator(new EntryID(13)), 4L, 6L, 8L, 10L, 12L);
+ }
+
+ @Test
+ public void testDefinedByteString()
+ {
+ ByteString string = newDefinedSet(4, 6, 8, 10, 12).toByteString();
+ assertThat(decodeEntryIDList(string)).containsExactly(4, 6, 8, 10, 12);
+
+ string = newDefinedSet().toByteString();
+ assertThat(decodeEntryIDList(string)).isEmpty();
+ }
+
+ @Test(expectedExceptions = NullPointerException.class)
+ public void testUndefinedCannotCreateWithNull()
+ {
+ newUndefinedSetWithSize(null, 1);
+ }
+
+ @Test
+ public void testUndefinedAdd()
+ {
+ EntryIDSet undefined = newUndefinedWithInitialSize();
+
+ assertThat(undefined.add(new EntryID(4))).isTrue();
+ assertThat(undefined.size()).isEqualTo(UNDEFINED_INITIAL_SIZE + 1);
+ }
+
+ @Test
+ public void testUndefinedAddAll()
+ {
+ EntryIDSet undefined = newUndefinedWithInitialSize();
+
+ undefined.addAll(newDefinedSet());
+ assertThat(newUndefinedWithInitialSize().size()).isEqualTo(UNDEFINED_INITIAL_SIZE);
+
+ undefined.addAll(newDefinedSet(2, 4, 6));
+ assertThat(undefined.size()).isEqualTo(UNDEFINED_INITIAL_SIZE + 3);
+ }
+
+ @Test
+ public void testUndefinedRemove()
+ {
+ EntryIDSet undefined = newUndefinedWithInitialSize();
+
+ assertThat(undefined.remove(new EntryID(4))).isTrue();
+ assertThat(undefined.size()).isEqualTo(UNDEFINED_INITIAL_SIZE - 1);
+ }
+
+ @Test
+ public void testUndefinedRemoveUnderflow()
+ {
+ EntryIDSet undefined = newUndefinedSetWithSize(ByteString.valueOf("test"), 0);
+
+ assertThat(undefined.remove(new EntryID(4))).isTrue();
+ assertThat(undefined.size()).isEqualTo(0);
+ }
+
+ @Test
+ public void testUndefinedDeleteAll()
+ {
+ EntryIDSet undefined = newUndefinedWithInitialSize();
+
+ undefined.removeAll(newDefinedSet(20, 21, 22));
+ assertThat(undefined.size()).isEqualTo(UNDEFINED_INITIAL_SIZE - 3);
+ }
+
+ @Test
+ public void testUndefinedDeleteAllUnderflow()
+ {
+ EntryIDSet undefined = newUndefinedSetWithSize(ByteString.valueOf("test"), 0);
+
+ undefined.removeAll(newDefinedSet(20, 21, 22));
+ assertThat(undefined.size()).isEqualTo(0);
+ }
+
+ @Test
+ public void testUndefinedContain()
+ {
+ assertThat(newUndefinedWithInitialSize().contains(new EntryID(4))).isTrue();
+ }
+
+ @Test
+ public void testUndefinedIterator()
+ {
+ assertThat(newUndefinedWithInitialSize().iterator().hasNext()).isFalse();
+ }
+
+ @Test
+ public void testUndefinedIteratorWithBegin()
+ {
+ assertThat(newUndefinedWithInitialSize().iterator(new EntryID(8)).hasNext()).isFalse();
+ }
+
+ @Test
+ public void testUndefinedByteString()
+ {
+ assertThat(newUndefinedWithInitialSize().toByteString()).isEqualTo(
+ ByteString.valueOf(UNDEFINED_INITIAL_SIZE | Long.MIN_VALUE));
+ }
+
+ @Test
+ public void testNewEmptySet()
+ {
+ assertThat(newDefinedSet().isDefined()).isTrue();
+ assertThat(newDefinedSet().size()).isEqualTo(0);
+ }
+
+ @Test
+ public void testNewSetFromBytes()
+ {
+ assertThat(newSetFromBytes(KEY, ByteString.empty()).isDefined()).isFalse();
+ assertThat(newSetFromBytes(KEY, ByteString.valueOf(42 | Long.MIN_VALUE)).isDefined()).isFalse();
+ assertThat(newSetFromBytes(KEY, ByteString.valueOf(42 | Long.MIN_VALUE)).size()).isEqualTo(42);
+
+ assertThat(newSetFromBytes(KEY, newDefinedSet(1, 2, 3).toByteString()).isDefined()).isTrue();
+ assertThat(newSetFromBytes(KEY, newDefinedSet(1, 2, 3).toByteString()).size()).isEqualTo(3);
+ }
+
+ @Test
+ public void testNewSetWIthIDs()
+ {
+ assertThat(newDefinedSet().isDefined()).isTrue();
+ assertThat(newDefinedSet().size()).isEqualTo(0);
+
+ assertThat(newDefinedSet(1, 2, 3).isDefined()).isTrue();
+ assertThat(newDefinedSet(1, 2, 3).size()).isEqualTo(3);
+ }
+
+ @Test
+ public void testNewUndefinedSet()
+ {
+ assertThat(newUndefinedSet().isDefined()).isFalse();
+ assertThat(newUndefinedSetWithKey(KEY).isDefined()).isFalse();
+ assertThat(newUndefinedSetWithKey(KEY).size()).isEqualTo(Long.MAX_VALUE);
+
+ assertThat(newUndefinedSetWithSize(KEY, 42).isDefined()).isFalse();
+ assertThat(newUndefinedSetWithSize(KEY, 42).size()).isEqualTo(42);
+ }
+
+ @Test
+ public void testNewSetFromUnions()
+ {
+ EntryIDSet union =
+ newSetFromUnion(Arrays.asList(newDefinedSet(1, 2, 3), newDefinedSet(4, 5, 6), newDefinedSet(3, 4)));
+ assertIdsEquals(union, 1, 2, 3, 4, 5, 6);
+
+ union = newSetFromUnion(Arrays.asList(newDefinedSet(), newDefinedSet(4, 5, 6), newDefinedSet(3, 4)));
+ assertIdsEquals(union, 3, 4, 5, 6);
+
+ union = newSetFromUnion(Arrays.asList(newDefinedSet(), newDefinedSet(4, 5, 6), newUndefinedSet()));
+ assertThat(union.isDefined()).isFalse();
+ }
+
+ @Test
+ public void testRetainAll()
+ {
+ EntryIDSet retained = newDefinedSet(2, 4, 6, 8);
+ retained.retainAll(newDefinedSet(1, 2, 3, 5, 6, 7, 8));
+ assertThat(retained.isDefined()).isTrue();
+ assertIdsEquals(retained, 2, 6, 8);
+
+ retained = newDefinedSet(2, 4, 6, 8);
+ retained.retainAll(newDefinedSet(1, 3, 5, 7, 9));
+ assertThat(retained.isDefined()).isTrue();
+ assertIdsEquals(retained);
+
+ retained = newUndefinedSet();
+ retained.retainAll(newDefinedSet(1, 3, 5, 7, 9));
+ assertThat(retained.isDefined()).isTrue();
+ assertIdsEquals(retained, 1, 3, 5, 7, 9);
+ }
+
+ private static EntryIDSet newUndefinedWithInitialSize()
+ {
+ return newUndefinedSetWithSize(ByteString.valueOf("test"), UNDEFINED_INITIAL_SIZE);
+ }
+
+}
diff --git a/opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/Utils.java b/opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/Utils.java
new file mode 100644
index 0000000..96de7a8
--- /dev/null
+++ b/opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/Utils.java
@@ -0,0 +1,61 @@
+/*
+ * 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
+ * or http://forgerock.org/license/CDDLv1.0.html.
+ * 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
+ *
+ *
+ * Portions Copyright 2013-2015 ForgeRock AS
+ */
+package org.opends.server.backends.pluggable;
+
+import static org.assertj.core.api.Assertions.assertThat;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+
+final class Utils
+{
+ public static void assertIdsEquals(Iterator<EntryID> actual, long... expected)
+ {
+ assertThat(actual).containsAll(asList(expected));
+ }
+
+ public static void assertIdsEquals(EntryIDSet actual, long... expected)
+ {
+ assertIdsEquals(actual.iterator(), expected);
+ }
+
+ private static List<EntryID> asList(long... array) {
+ List<EntryID> list = new ArrayList<EntryID>(array.length);
+ for(long l : array) {
+ list.add(new EntryID(l));
+ }
+ return list;
+ }
+
+ private Utils()
+ {
+ // Hide consutrctor
+ }
+
+
+}
--
Gitblit v1.10.0