OPENDJ-1866: Make EntryIDSet more maintainable.

Yannick Lecaillez

16.36.2015 42fbf08eb02ea8464a6b03fc47b75ad400bed44f

OPENDJ-1866: Make EntryIDSet more maintainable.

 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();
    }
  }


 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;
  }

}

 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;
    }
  }

}

 opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/EntryIDSetSorter.java

File was deleted

 opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/IDSetIterator.java

File was deleted

 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-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();
    }
  }


 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);
      }

 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);
    }
  }
}

 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-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-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-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-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-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-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
  }


}