EntryIDSet.java revision 20fdcbef0d17440c367d2943f9c5799bddfe661f
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (the "License"). You may not use this file except in compliance
* with the License.
*
* You can obtain a copy of the license at legal-notices/CDDLv1_0.txt
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at legal-notices/CDDLv1_0.txt.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information:
* Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*
*
* Copyright 2006-2008 Sun Microsystems, Inc.
* Portions Copyright 2014-2015 ForgeRock AS
*/
/**
* 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.
*/
{
private static final long[] EMPTY_LONG_ARRAY = new long[0];
/** Interface for EntryIDSet concrete implementations. */
{
long size();
boolean isDefined();
long[] getRange();
long[] getIDs();
}
/**
* Define serialization contract for EntryIDSet
*/
interface EntryIDSetCodec {
static final int INT_SIZE = 4;
static final int LONG_SIZE = 8;
}
/**
* 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)
{
}
public long size()
{
}
{
}
public boolean isDefined()
{
return true;
}
{
{
}
{
}
else
{
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.
}
return true;
}
{
// Binary search to locate the ID.
if (pos >= 0)
{
// Found it.
return true;
}
// Not found.
return false;
}
{
}
{
{
return;
}
{
return;
}
if (overlap < 0)
{
}
else if (overlap > 0)
{
}
else
{
}
}
{
{
// Set overlaps
{
{
}
{
}
else
{
sourceIndex++;
}
}
{
}
else
{
}
}
}
{
return new IDSetIterator(entryIDs);
}
{
}
public long[] getRange()
{
{
}
else
{
return NO_ENTRY_IDS_RANGE;
}
}
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;
{
}
public long size()
{
return undefinedSize;
}
{
if (databaseKey == NO_KEY)
{
}
else if (maintainUndefinedSize())
{
}
else
{
}
}
private boolean maintainUndefinedSize()
{
}
public boolean isDefined()
{
return false;
}
{
if (maintainUndefinedSize())
{
}
return true;
}
{
{
}
return true;
}
{
return true;
}
{
// Assume there are no overlap between IDs in that set with this set
if (maintainUndefinedSize())
{
}
}
{
// Assume all IDs in the given set exists in this set.
if (maintainUndefinedSize())
{
}
}
{
return Iterators.emptyIterator();
}
{
return Iterators.emptyIterator();
}
public long[] getRange()
{
return NO_ENTRY_IDS_RANGE;
}
public long[] getIDs()
{
return EMPTY_LONG_ARRAY;
}
}
/**
* Iterator for a set of Entry IDs. It must return values in order of ID.
*/
{
private final long[] entryIDSet;
private int currentIndex;
IDSetIterator(long[] entryIDSet)
{
this.entryIDSet = entryIDSet;
}
{
this(entryIDSet);
}
public boolean hasNext()
{
}
{
if (hasNext())
{
}
throw new NoSuchElementException();
}
public void remove()
{
throw new UnsupportedOperationException();
}
}
/**
* Legacy EntryIDSet codec implementation
*/
private static final class EntryIDSetCodecV1 implements EntryIDSetCodec
{
{
.getBackingArray());
}
{
{
// Entry limit has exceeded and there is no encoded undefined set size.
return newDefinedSet();
}
{
// Entry limit has exceeded and there is an encoded undefined set size.
}
else
{
// Seems like entry limit has not been exceeded and the bytes is a list of entry IDs.
}
}
{
{
}
else
{
return LONG_SIZE;
}
}
{
final long ids[] = new long[nbEntriesToDecode];
for(int i = 0 ; i < nbEntriesToDecode ; i++) {
}
return ids;
}
{
{
{
}
return builder;
}
else
{
// Set top bit.
}
}
{
// remove top bit
}
}
/**
* Compacted EntryIDSet codec implementation. Idea is to take advantages of
* org.forgerock.opendj.ldap.ByteStringBuilder#appendCompact() able to write small values of long in fewer bytes.
* Rather than storing the full list of IDs, we store only the difference of the Nth ID with the N-1th one in the hope
* that the result will be small enough to be compacted by appendCompact().
*/
private static final class EntryIDSetCodecV2 implements EntryIDSetCodec
{
private static final byte UNDEFINED_SET = (byte) 0xFF;
{
}
{
} else {
}
}
{
{
long basis = 0;
{
}
}
else
{
}
return builder;
}
{
}
{
if ( nbEntriesToDecode == 0 ) {
return EMPTY_LONG_ARRAY;
} else {
final long ids[] = new long[nbEntriesToDecode];
for(int i = 1 ; i < nbEntriesToDecode ; i++) {
}
return ids;
}
}
}
static EntryIDSet newUndefinedSet()
{
}
{
}
{
}
/**
* Creates a new defined entry ID set with the specified ids.
*
* @param ids
* Entry IDs contained in the set.
* @throws NullPointerException
* if ids is null
*/
{
}
{
{
{
index2++;
}
{
index2++;
}
else
{
index1++;
}
}
{
}
return target;
}
/**
* Creates a new set of entry IDs that is the union of several entry ID sets.
*
* @param sets
* A list of entry ID sets.
* @return The union of the provided entry ID sets.
*/
{
int count = 0;
boolean containsUndefinedSet = false;
for (EntryIDSet l : sets)
{
if (!l.isDefined())
{
{
return newUndefinedSet();
}
containsUndefinedSet = true;
}
}
if (containsUndefinedSet)
{
}
boolean needSort = false;
long[] n = new long[count];
int pos = 0;
for (EntryIDSet l : sets)
{
if (l.size() != 0)
{
}
}
if (needSort)
{
}
long last = -1;
int j = 0;
for (long l : n)
{
if (l != last)
{
}
}
{
return newDefinedSet(n1);
}
else
{
}
}
private EntryIDSetImplementor concreteImpl;
{
this.concreteImpl = concreteImpl;
}
/**
* Get the size of this entry ID set.
*
* @return The number of IDs in the set.
*/
public long size()
{
return concreteImpl.size();
}
/**
* Convert to a short string to aid with debugging.
*
* @param buffer
* The string is appended to this string builder.
* @throws NullPointerException
* if buffer is null
*/
{
}
}
/**
* Determine whether this set of IDs is defined.
*
* @return true if the set of IDs is defined.
*/
public boolean isDefined()
{
return concreteImpl.isDefined();
}
/**
* 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.
* @throws NullPointerException
* if entryID is null
*/
{
}
/**
* 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.
* @throws NullPointerException
* if entryID is null
*/
{
}
/**
* 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.
* @throws NullPointerException
* if entryID is null
*/
{
}
/**
* 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
* @throws NullPointerException
* if that is null
* @throws IllegalArgumentException
* if that is undefined.
*/
{
}
/**
* 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.
* @throws NullPointerException
* if that is null
*/
{
if (!concreteImpl.isDefined())
{
// NOTE: It's ok to share the same array instance here thanks to the copy-on-write
// performed by the implementation.
} else {
}
return;
}
return;
}
if (thatSetOverlap)
{
}
else if (size() != 0)
{
concreteImpl = new DefinedImpl();
}
}
/**
* 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.
*/
{
}
/**
* Creates an iterator over the set or an empty iterator if the set is not defined.
*
* @return An EntryID iterator.
*/
{
return concreteImpl.iterator();
}
/**
* Creates 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.
*/
{
}
private long[] getIDs()
{
return concreteImpl.getIDs();
}
private long[] getRange()
{
return concreteImpl.getRange();
}
{
final long[] a, b;
{
a = set1;
b = set2;
}
else
{
a = set2;
b = set1;
}
for (sourceAIndex = 0, sourceBIndex = 0, targetIndex = 0; sourceAIndex < a.length && sourceBIndex < b.length;)
{
if (a[sourceAIndex] < b[sourceBIndex])
{
}
else if (b[sourceBIndex] < a[sourceAIndex])
{
}
else
{
sourceAIndex++;
sourceBIndex++;
}
}
{
}
else
{
return newEntryIDs;
}
}
private static int copyRemainder(long[] sourceIDSet, final long[] newEntryIDs, int offset, int remainerIndex)
{
if (currentRemainder > 0)
{
return remainerIndex + currentRemainder;
}
return remainerIndex;
}
{
return ids;
}
/**
* @return -1 if o1 < o2, 0 if o1 overlap o2, +1 if o1 > o2
*/
{
{
return 0;
}
{
return 1;
}
{
return -1;
}
{
return -1;
}
{
return 1;
}
else
{
return 0;
}
}
}