mirror of https://github.com/OpenIdentityPlatform/OpenDJ.git
opendj-sdk/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(); } }
@@ -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; } } opendj-sdk/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)]; int index1, index2, ci; for (index1 = 0, index2 = 0, ci = 0; index1 < set1.length && index2 < set2.length;) { if (set1[index1] == set2[index2]) { target[ci++] = set1[index1++]; index2++; } else if (set1[index1] > set2[index2]) { index2++; } else { index1++; } } /** * 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) if (ci < target.length) { 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(); target = Arrays.copyOf(target, ci); } 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); 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("]"); checkNotNull(buffer, "buffer must not be null"); concreteImpl.toString(buffer); } 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]"); } @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) { // The set is defined. return new IDSetIterator(values, begin); return concreteImpl.iterator(begin); } // The set is not defined. return new IDSetIterator(new long[0]); 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) { a = set1; b = set2; } 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; } } } opendj-sdk/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryIDSetSorter.java
File was deleted opendj-sdk/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IDSetIterator.java
File was deleted opendj-sdk/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; opendj-sdk/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(); } }
@@ -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); } opendj-sdk/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) results = applyFiltersUntilThreshold(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, 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); } } } opendj-sdk/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; } opendj-sdk/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); opendj-sdk/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 opendj-sdk/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); } /** opendj-sdk/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()) { opendj-sdk/opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/EntryIDSetTest.java
New file @@ -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); } } opendj-sdk/opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/Utils.java
New file @@ -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 } }
