backends/pluggable/EntryIDSet.java

	EntryIDSet.java revision 763a75aeed1a7731ddb95b99496aa7c1bf206ed0
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at legal-notices/CDDLv1_0.txt
 * or http://forgerock.org/license/CDDLv1.0.html.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at legal-notices/CDDLv1_0.txt.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information:
 *      Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 *
 *
 *      Copyright 2006-2008 Sun Microsystems, Inc.
 *      Portions Copyright 2014-2015 ForgeRock AS
 */
package org.opends.server.backends.pluggable;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;

import org.forgerock.opendj.ldap.ByteSequence;
import org.forgerock.opendj.ldap.ByteSequenceReader;
import org.forgerock.opendj.ldap.ByteString;
import org.forgerock.opendj.ldap.ByteStringBuilder;

/**
 * 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>
{

  /**
   * The IDs are stored here in an array in ascending order.
   * A null array implies not defined, rather than zero IDs.
   */
  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()
  {
    this(Long.MAX_VALUE);
  }

  /**
   * Create a new undefined set with a initial size.
   *
   * @param size The undefined size for this set.
   */
  EntryIDSet(long size)
  {
    this.key = null;
    this.undefinedSize = size;
  }

  /**
   * Create a new entry ID set from the raw database value.
   *
   * @param key
   *          The database key that contains this value.
   * @param bytes
   *          The database value, or null if there are no entry IDs.
   */
  EntryIDSet(ByteSequence key, ByteString bytes)
  {
    this.key = key;

    if (bytes == null)
    {
      values = new long[0];
    }
    else if (bytes.length() == 0)
    {
      // Entry limit has exceeded and there is no encoded undefined set size.
      undefinedSize = Long.MAX_VALUE;
    }
    else if ((bytes.byteAt(0) & 0x80) == 0x80)
    {
      // Entry limit has exceeded and there is an encoded undefined set size.
      undefinedSize = decodeUndefinedSize(bytes);
    }
    else
    {
      // Seems like entry limit has not been exceeded and the bytes is a
      // list of entry IDs.
      values = decodeEntryIDList(bytes);
    }
  }

  /**
   * 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)
  {
    return bytes.length() == 8
            ? bytes.toLong() & Long.MAX_VALUE // remove top bit
            : Long.MAX_VALUE;
  }

  /**
   * 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++)
    {
      entryIDList[i] = reader.getLong();
    }
    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);
  }

  /**
   * 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.
   * @return The union of the provided entry ID sets.
   */
  static EntryIDSet unionOfSets(ArrayList<EntryIDSet> sets,
                                         boolean allowDuplicates)
  {
    int count = 0;

    boolean undefined = false;
    for (EntryIDSet l : sets)
    {
      if (!l.isDefined())
      {
        if(l.undefinedSize == Long.MAX_VALUE)
        {
          return new EntryIDSet();
        }
        undefined = true;
      }
      count += l.size();
    }

    if(undefined)
    {
      return new EntryIDSet(count);
    }

    boolean needSort = false;
    long[] n = new long[count];
    int pos = 0;
    for (EntryIDSet l : sets)
    {
      if (l.values.length != 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;
      }
    }
    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;
    for (long l : n)
    {
      if (l != last)
      {
        last = n1[j++] = l;
      }
    }
    if (j == n1.length)
    {
      EntryIDSet ret = new EntryIDSet();
      ret.values = n1;
      return ret;
    }
    else
    {
      return new EntryIDSet(n1, 0, j);
    }
  }

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

  /**
   * Convert to a short string to aid with debugging.
   *
   * @param buffer The string is appended to this string builder.
   */
  void toString(StringBuilder buffer)
  {
    if (!isDefined())
    {
      if (key != null)
      {
        // The index entry limit was exceeded
        if(undefinedSize == Long.MAX_VALUE)
        {
          buffer.append("[LIMIT-EXCEEDED]");
        }
        else
        {
          buffer.append("[LIMIT-EXCEEDED:");
          buffer.append(undefinedSize);
          buffer.append("]");
        }
      }
      else
      {
        // Not indexed
        buffer.append("[NOT-INDEXED]");
      }
    }
    else
    {
      buffer.append("[COUNT:");
      buffer.append(size());
      buffer.append("]");
    }
  }

  /**
   * Determine whether this set of IDs is defined.
   *
   * @return true if the set of IDs is defined.
   */
  boolean isDefined()
  {
    return values != null;
  }

  /**
   * Get a database representation of this object.
   * @return A database representation of this object as a byte array.
   */
  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);
    }
  }

  /**
   * 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.
   */
  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;
  }

  /**
   * 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.
   */
  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;
  }

  /**
   * 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.
   */
  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;
    }
  }

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

  /**
   * Delete all IDs in this set that are in a given set.
   *
   * @param that The set of IDs to be deleted. It MUST be defined.
   */
  void deleteAll(EntryIDSet that)
  {
    if(!that.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++;
      } else {
        ai++;
        bi++;
      }
    }

    System.arraycopy(a, ai, n, ni, a.length - ai);
    ni += a.length - ai;

    if (ni < a.length)
    {
      values = Arrays.copyOf(n, ni);
    }
    else
    {
      values = n;
    }
  }

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

  /**
   * 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.
   *
   * @return An EntryID iterator.
   */
  Iterator<EntryID> iterator(EntryID begin)
  {
    if (values != null)
    {
      // The set is defined.
      return new IDSetIterator(values, begin);
    }
    // The set is not defined.
    return new IDSetIterator(new long[0]);
  }

}