X-Git-Url: https://gerrit.simantics.org/r/gitweb?p=simantics%2Fplatform.git;a=blobdiff_plain;f=bundles%2Forg.simantics.db.procore%2Fsrc%2Forg%2Fsimantics%2Fdb%2Fprocore%2Fcluster%2FLongHash.java;h=20ed07917d1c24827862e97df9c9965d65580bac;hp=77f5d89e72069e233cd73577693f8c2bbdfaf335;hb=e19c37f84fd1ce2d946578f7c05f3e45444ba67a;hpb=969bd23cab98a79ca9101af33334000879fb60c5 diff --git a/bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/LongHash.java b/bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/LongHash.java index 77f5d89e7..20ed07917 100644 --- a/bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/LongHash.java +++ b/bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/LongHash.java @@ -1,479 +1,479 @@ -/******************************************************************************* - * Copyright (c) 2007, 2010 Association for Decentralized Information Management - * in Industry THTH ry. - * All rights reserved. This program and the accompanying materials - * are made available under the terms of the Eclipse Public License v1.0 - * which accompanies this distribution, and is available at - * http://www.eclipse.org/legal/epl-v10.html - * - * Contributors: - * VTT Technical Research Centre of Finland - initial API and implementation - *******************************************************************************/ -package org.simantics.db.procore.cluster; - -import gnu.trove.impl.PrimeFinder; - -public class LongHash { - static final int HeaderSize = 2; - static private final int UsedAndRealSize = -2; // Number of allocated slots. - static private final int MaxAndFreeSize = -1; // Number of used slots. - static private final int MinRealSize = 3; - static private final int MinRealSizeMinusOne = MinRealSize - 1; - private static final long FREE = 0; - private static final long REMOVED = -1; - - static final boolean isFree(long a) { - return FREE == a; - } - - static final boolean isFull(long a) { - return a > FREE; - } - - static final boolean isRemoved(long a) { - return REMOVED == a; - } - - static final long setFree() { - return FREE; - } - - static final long setFull(long a) { - return a; - } - - static final long setRemoved() { - return REMOVED; - } - - static public int getRealSize(long[] longs, int hashBase) { - long desc = longs[hashBase + UsedAndRealSize]; - assert(desc < 0); - int realSize = (int)desc & 0x7FFFFFFF; - assert (realSize > MinRealSizeMinusOne); - return realSize; - } - -// private static void setRealSize(long[] longs, int hashBase, int realSize) { -// assert (realSize > MinRealSizeMinusOne); -// long desc = longs[hashBase + UsedAndRealSize]; -// assert(desc < 0); -// assert((int)desc < 0); -// desc = (desc & 0xFFFFFFFF80000000L) | realSize; -// longs[hashBase + UsedAndRealSize] = desc; -// } - - private static void setUsedAndRealSize(long[] longs, int hashBase, int usedSize, int realSize) { - assert(usedSize >= 0); - assert(realSize > MinRealSizeMinusOne); - int index = hashBase + UsedAndRealSize; - long desc = longs[index]; - assert(desc <= 0); // memory is initialized to zero - desc = (long)usedSize << 32 | realSize | 0x8000000080000000L; - longs[index] = desc; - } - - public static int getUsedSize(long[] longs, int hashBase) { - long desc = longs[hashBase + UsedAndRealSize]; - assert(desc < 0); - assert((int)desc < 0); - return (int)(desc >> 32) & 0x7FFFFFFF; - } - - static void setUsedSize(long[] longs, int hashBase, int usedSize) { - assert (usedSize >= 0); - int index = hashBase + UsedAndRealSize; - long desc = longs[index]; - assert(desc < 0); - assert((int)desc < 0); - desc = (desc & 0x80000000FFFFFFFFL) | (long)usedSize << 32; - longs[index] = desc; - } - - // return value after decrement - static int decUsedSize(long[] longs, int hashBase) { - int index = hashBase + UsedAndRealSize; - long desc = longs[index]; - assert(desc < 0); - int usedSize = ((int)(desc >> 32) & 0x7FFFFFFF) - 1; - assert(usedSize >= 0); - desc = (desc & 0x80000000FFFFFFFFL) | (long)usedSize << 32; - longs[index] = desc; - return usedSize; - } - - // return value after increment - static int incUsedSize(long[] longs, int hashBase) { - int index = hashBase + UsedAndRealSize; - long desc = longs[index]; - assert(desc < 0); - int usedSize = ((int)(desc >> 32) & 0x7FFFFFFF) + 1; - assert(usedSize > 0); - desc = (desc & 0x80000000FFFFFFFFL) | (long)usedSize << 32; - longs[index] = desc; - return usedSize; - } - - static int getFreeSize(long[] longs, int hashBase) { - long desc = longs[hashBase + MaxAndFreeSize]; - assert(desc > 0); - int freeSize = (int)desc; - assert (freeSize >= 0); - return freeSize; - } - - static void setFreeSize(long[] longs, int hashBase, int freeSize) { - assert (freeSize >= 0); - long desc = longs[hashBase + MaxAndFreeSize]; - assert(desc > 0); - assert((int)desc >= 0); - desc = (desc & 0xFFFFFFFF00000000L) | freeSize; - longs[hashBase + MaxAndFreeSize] = desc; - } - - static void decFreeSize(long[] longs, int hashBase) { - long desc = longs[hashBase + MaxAndFreeSize]; - assert(desc > 0); - int freeSize = (int)desc; - assert(freeSize > 0); - desc = (desc & 0xFFFFFFFF00000000L) | --freeSize; - longs[hashBase + MaxAndFreeSize] = desc; - } - - private static void setMaxAndFreeSize(long[] longs, int hashBase, int maxSize, int freeSize) { - assert (maxSize > 0); - assert (freeSize >= 0); - int index = hashBase + MaxAndFreeSize; - long desc = longs[index]; - assert(desc >= 0); // memory is initialized to zero - desc = ((long)maxSize << 32) | freeSize; - longs[index] = desc; - } - - static int getMaxSize(long[] longs, int hashBase) { - long desc = longs[hashBase + MaxAndFreeSize]; - assert(desc > 0); - assert((int)desc >= 0); - return (int)(desc >> 32); - } - - static void setMaxSize(long[] longs, int hashBase, int maxSize) { - assert (maxSize > 0); - int index = hashBase + MaxAndFreeSize; - long desc = longs[index]; - assert(desc > 0); - assert((int)desc >= 0); - desc = (desc & 0x00000000FFFFFFFFL) | (long)maxSize << 32; - longs[index] = desc; - } - - public static boolean add(AllocatorI allocator, long a) { - long[] longs = allocator.getLongs(); - int hashBase = allocator.getHashBase(); - int index = insertionIndex(longs, hashBase, a); - if (index < 0) - return false; // already present in set, nothing to add - long previousState = longs[index]; - assert(LongHash.isFull(a)); - longs[index] = a; - postInsertHook(longs, hashBase, LongHash.isFree(previousState), allocator); - return true; // yes, we added something - } - - public static boolean remove(long[] longs, int hashBase, long a) { - int index = LongHash.index(longs, hashBase, a); - if (index >= 0) { - longs[index] = setRemoved(); - decUsedSize(longs, hashBase); - return true; - } - return false; - } - - public static boolean contains(long[] longs, int hashBase,long a) { - return index(longs, hashBase, a) >= 0; - } - - public static boolean isEmpty(long[] longs, int hashBase) { - return 0 == getUsedSize(longs, hashBase); - } - - public static void clear(long[] longs, int hashBase) { - long[] set = longs; - long free = setFree(); - int capacity = getRealSize(longs, hashBase); - for (int i = capacity; i-- > 0;) { - set[hashBase + i] = free; - } - setUsedSize(longs, hashBase, 0); - setFreeSize(longs, hashBase, capacity); - } - - /** - * Ensure that this hashtable has sufficient capacity to hold - * desiredCapacity additional elements without - * requiring a rehash. This is a tuning method you can call - * before doing a large insert. - * - * @param desiredSize an int value - */ - public static boolean ensureSize(AllocatorI allocator, int desiredSize) { - long[] longs = allocator.getLongs(); - int hashBase = allocator.getHashBase(); - int size = getUsedSize(longs, hashBase); - if (desiredSize > (getMaxSize(longs, hashBase) - size)) { - int newCapacity = ((desiredSize + size) << 1) + 1; - rehash(longs, hashBase, PrimeFinder.nextPrime(newCapacity), allocator); - return true; - } - return false; - } - - /** - * Compresses the hashtable to the minimum prime size (as defined by - * PrimeFinder) that will hold all of the elements currently in the table. - * If you have done a lot of remove operations and plan to do a - * lot of queries or insertions or iteration, it is a good idea to invoke - * this method. Doing so will accomplish two things: - * - *
    - *
  1. You'll free memory allocated to the table but no longer needed - * because of the remove()s.
    2. - * - *
  2. You'll get better query/insert/iterator performance because there - * won't be any REMOVED slots to skip over when probing for - * indices in the table.
    3. - *
- */ - public static void compact(AllocatorI allocator) { - long[] longs = allocator.getLongs(); - int hashBase = allocator.getHashBase(); - // need at least one free spot for open addressing - rehash(longs, hashBase, PrimeFinder.nextPrime((getUsedSize(longs, hashBase) << 1) + 1), allocator); - } - - public static int setUp(AllocatorI allocator, int initialCapacity) { - int capacity = PrimeFinder.nextPrime(initialCapacity << 1); - int hashBase = allocator.allocate(capacity); - assert(hashBase == allocator.getHashBase()); - long[] longs = allocator.getLongs(); - setUsedAndRealSize(longs, hashBase, 0, capacity); - setMaxAndFreeSize(longs, hashBase, capacity >> 1, capacity); - return hashBase; - } - - /** - * Expands the set to accomodate new values. - * - * @param newCapacity - * an int value - */ - static final void rehash(long[] oldLongs, int oldHashBase, int newCapacity, - AllocatorI allocator) { - assert(PrimeFinder.nextPrime(newCapacity) == newCapacity); - int oldCapacity = getRealSize(oldLongs, oldHashBase); - int oldSize = getUsedSize(oldLongs, oldHashBase); - // new hash base is initialized to LongHash.freeSet() - int newHashBase = allocator.allocate(newCapacity); - long[] newLongs = allocator.getLongs(); - setUsedAndRealSize(newLongs, newHashBase, oldSize, newCapacity); - setMaxAndFreeSize(newLongs, newHashBase, newCapacity>>1, newCapacity - oldSize); - - for (int i = oldCapacity + oldHashBase; i-- > oldHashBase;) { - long o = oldLongs[i]; - if (isFull(o)) { - int index = insertionIndex(newLongs, newHashBase, o); - newLongs[index] = o; - } - } - } - - /** - * After an insert, this hook is called to adjust the size/free values of - * the set and to perform rehashing if necessary. - */ - protected static final void postInsertHook(long[] longs, int hashBase, - boolean usedFreeSlot, AllocatorI allocator) { - if (usedFreeSlot) { - decFreeSize(longs, hashBase); - } - - // rehash whenever we exhaust the available space in the table - if (incUsedSize(longs, hashBase) > getMaxSize(longs, hashBase) - || getFreeSize(longs, hashBase) == 0) { - // choose a new capacity suited to the new state of the table - // if we've grown beyond our maximum size, double capacity; - // if we've exhausted the free spots, rehash to the same capacity, - // which will free up any stale removed slots for reuse. - int newCapacity = getUsedSize(longs, hashBase) > getMaxSize(longs, - hashBase) ? PrimeFinder.nextPrime(getRealSize(longs, - hashBase) << 1) : getRealSize(longs, hashBase); - rehash(longs, hashBase, newCapacity, allocator); - } - } - - /** - * Locates the index of val. - * - * @param val - * an long value - * @return the index of val or -1 if it isn't in the set. - */ - static int index(long[] longs, int hashBase, long a) { - int hash, probe, index, length, hashIndex; - long[] set = longs; - length = getRealSize(longs, hashBase); - hash = computeHashCode(a); - index = hash % length; - hashIndex = hashBase + index; - - if (!LongHash.isFree(set[hashIndex]) - && (LongHash.isRemoved(set[hashIndex]) || set[hashIndex] != a)) { - // see Knuth, p. 529 - probe = 1 + (hash % (length - 2)); - - do { - index -= probe; - if (index < 0) { - index += length; - } - hashIndex = hashBase + index; - } while (!LongHash.isFree(set[hashIndex]) - && (LongHash.isRemoved(set[hashIndex]) || set[hashIndex] != a)); - } - - return LongHash.isFree(set[hashIndex]) ? -1 : hashIndex; - } - - /** - * Locates the index at which val can be inserted. if there is - * already a value equal()ing val in the set, returns that value - * as a negative integer. - * - * @param val - * an long value - * @return an int value - */ - static final int insertionIndex(long[] longs, int hashBase, long a) { - int hash, probe, index, length, hashIndex; - long[] set = longs; - length = getRealSize(longs, hashBase); - hash = computeHashCode(a); - index = hash % length; - assert(0 != hashBase); - hashIndex = hashBase + index; - - if (LongHash.isFree(set[hashIndex])) { - return hashIndex; // empty, all done - } else if (LongHash.isFull(set[hashIndex]) && set[hashIndex] == a) { - return -hashIndex; // already stored - } else { // already FULL or REMOVED, must probe - // compute the double hash - probe = 1 + (hash % (length - 2)); - - // if the slot we landed on is FULL (but not removed), probe - // until we find an empty slot, a REMOVED slot, or an element - // equal to the one we are trying to insert. - // finding an empty slot means that the value is not present - // and that we should use that slot as the insertion point; - // finding a REMOVED slot means that we need to keep searching, - // however we want to remember the offset of that REMOVED slot - // so we can reuse it in case a "new" insertion (i.e. not an update) - // is possible. - // finding a matching value means that we've found that our desired - // key is already in the table - - if (!LongHash.isRemoved(set[hashIndex])) { - // starting at the natural offset, probe until we find an - // offset that isn't full. - do { - index -= probe; - if (index < 0) { - index += length; - } - hashIndex = hashBase + index; - } while (LongHash.isFull(set[hashIndex]) && set[hashIndex] != a); - } - - // if the index we found was removed: continue probing until we - // locate a free location or an element which equal()s the - // one we have. - if (LongHash.isRemoved(set[hashIndex])) { - int firstRemoved = hashIndex; - while (!LongHash.isFree(set[hashIndex]) - && (LongHash.isRemoved(set[hashIndex]) || set[hashIndex] != a)) { - index -= probe; - if (index < 0) { - index += length; - } - hashIndex = hashBase + index; - } - return LongHash.isFull(set[hashIndex]) ? -hashIndex : firstRemoved; - } - // if it's full, the key is already stored - return LongHash.isFull(set[hashIndex]) ? -hashIndex : hashIndex; - } - } - - static final int computeHashCode(long aKey) { - int hash = ((int) (aKey ^ (aKey >> 32))) * 31; - return hash & 0x7fffffff; // Top bit reserved. - } - - interface AllocatorI { - int allocate(int size); // return base address of hash table, allocates also hash header - long[] getLongs(); // return base address of allocator memory - int getHashBase(); // return base address of hash table - } -} - -class LongIterator { - private long[] longs; - private int hashBase; - private int index; - // for reset - private int size; // number of elements in the set - private final LongHash.AllocatorI allocator; - - public LongIterator(LongHash.AllocatorI allocator) { - this.allocator = allocator; - this.reset(); - } - public int size() { - return this.size; - } - public void reset() { - if (longs == null || - LongHash.getUsedSize(longs, hashBase) != this.size || - longs != allocator.getLongs() || - hashBase != allocator.getHashBase()) { - this.longs = allocator.getLongs(); - this.hashBase = allocator.getHashBase(); - this.size = LongHash.getUsedSize(longs, hashBase); - } - this.index = LongHash.getRealSize(longs, hashBase); - } - public long next() { - if (moveToNextIndex()) - return longs[hashBase + index]; - return LongHash.setFree(); - } - protected final boolean moveToNextIndex() { - // doing the assignment && < 0 in one line saves 3 opcodes... - if ((index = nextIndex()) < 0) { - return false; - } - return true; - } - protected final int nextIndex() { - long[] states = longs; - int i = index; - while (i-- > 0 && (!LongHash.isFull(states[hashBase + i]))) - ; - return i; - } - public boolean hasNext() { - return nextIndex() >= 0; - } -} - +/******************************************************************************* + * Copyright (c) 2007, 2010 Association for Decentralized Information Management + * in Industry THTH ry. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Eclipse Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * VTT Technical Research Centre of Finland - initial API and implementation + *******************************************************************************/ +package org.simantics.db.procore.cluster; + +import gnu.trove.impl.PrimeFinder; + +public class LongHash { + static final int HeaderSize = 2; + static private final int UsedAndRealSize = -2; // Number of allocated slots. + static private final int MaxAndFreeSize = -1; // Number of used slots. + static private final int MinRealSize = 3; + static private final int MinRealSizeMinusOne = MinRealSize - 1; + private static final long FREE = 0; + private static final long REMOVED = -1; + + static final boolean isFree(long a) { + return FREE == a; + } + + static final boolean isFull(long a) { + return a > FREE; + } + + static final boolean isRemoved(long a) { + return REMOVED == a; + } + + static final long setFree() { + return FREE; + } + + static final long setFull(long a) { + return a; + } + + static final long setRemoved() { + return REMOVED; + } + + static public int getRealSize(long[] longs, int hashBase) { + long desc = longs[hashBase + UsedAndRealSize]; + assert(desc < 0); + int realSize = (int)desc & 0x7FFFFFFF; + assert (realSize > MinRealSizeMinusOne); + return realSize; + } + +// private static void setRealSize(long[] longs, int hashBase, int realSize) { +// assert (realSize > MinRealSizeMinusOne); +// long desc = longs[hashBase + UsedAndRealSize]; +// assert(desc < 0); +// assert((int)desc < 0); +// desc = (desc & 0xFFFFFFFF80000000L) | realSize; +// longs[hashBase + UsedAndRealSize] = desc; +// } + + private static void setUsedAndRealSize(long[] longs, int hashBase, int usedSize, int realSize) { + assert(usedSize >= 0); + assert(realSize > MinRealSizeMinusOne); + int index = hashBase + UsedAndRealSize; + long desc = longs[index]; + assert(desc <= 0); // memory is initialized to zero + desc = (long)usedSize << 32 | realSize | 0x8000000080000000L; + longs[index] = desc; + } + + public static int getUsedSize(long[] longs, int hashBase) { + long desc = longs[hashBase + UsedAndRealSize]; + assert(desc < 0); + assert((int)desc < 0); + return (int)(desc >> 32) & 0x7FFFFFFF; + } + + static void setUsedSize(long[] longs, int hashBase, int usedSize) { + assert (usedSize >= 0); + int index = hashBase + UsedAndRealSize; + long desc = longs[index]; + assert(desc < 0); + assert((int)desc < 0); + desc = (desc & 0x80000000FFFFFFFFL) | (long)usedSize << 32; + longs[index] = desc; + } + + // return value after decrement + static int decUsedSize(long[] longs, int hashBase) { + int index = hashBase + UsedAndRealSize; + long desc = longs[index]; + assert(desc < 0); + int usedSize = ((int)(desc >> 32) & 0x7FFFFFFF) - 1; + assert(usedSize >= 0); + desc = (desc & 0x80000000FFFFFFFFL) | (long)usedSize << 32; + longs[index] = desc; + return usedSize; + } + + // return value after increment + static int incUsedSize(long[] longs, int hashBase) { + int index = hashBase + UsedAndRealSize; + long desc = longs[index]; + assert(desc < 0); + int usedSize = ((int)(desc >> 32) & 0x7FFFFFFF) + 1; + assert(usedSize > 0); + desc = (desc & 0x80000000FFFFFFFFL) | (long)usedSize << 32; + longs[index] = desc; + return usedSize; + } + + static int getFreeSize(long[] longs, int hashBase) { + long desc = longs[hashBase + MaxAndFreeSize]; + assert(desc > 0); + int freeSize = (int)desc; + assert (freeSize >= 0); + return freeSize; + } + + static void setFreeSize(long[] longs, int hashBase, int freeSize) { + assert (freeSize >= 0); + long desc = longs[hashBase + MaxAndFreeSize]; + assert(desc > 0); + assert((int)desc >= 0); + desc = (desc & 0xFFFFFFFF00000000L) | freeSize; + longs[hashBase + MaxAndFreeSize] = desc; + } + + static void decFreeSize(long[] longs, int hashBase) { + long desc = longs[hashBase + MaxAndFreeSize]; + assert(desc > 0); + int freeSize = (int)desc; + assert(freeSize > 0); + desc = (desc & 0xFFFFFFFF00000000L) | --freeSize; + longs[hashBase + MaxAndFreeSize] = desc; + } + + private static void setMaxAndFreeSize(long[] longs, int hashBase, int maxSize, int freeSize) { + assert (maxSize > 0); + assert (freeSize >= 0); + int index = hashBase + MaxAndFreeSize; + long desc = longs[index]; + assert(desc >= 0); // memory is initialized to zero + desc = ((long)maxSize << 32) | freeSize; + longs[index] = desc; + } + + static int getMaxSize(long[] longs, int hashBase) { + long desc = longs[hashBase + MaxAndFreeSize]; + assert(desc > 0); + assert((int)desc >= 0); + return (int)(desc >> 32); + } + + static void setMaxSize(long[] longs, int hashBase, int maxSize) { + assert (maxSize > 0); + int index = hashBase + MaxAndFreeSize; + long desc = longs[index]; + assert(desc > 0); + assert((int)desc >= 0); + desc = (desc & 0x00000000FFFFFFFFL) | (long)maxSize << 32; + longs[index] = desc; + } + + public static boolean add(AllocatorI allocator, long a) { + long[] longs = allocator.getLongs(); + int hashBase = allocator.getHashBase(); + int index = insertionIndex(longs, hashBase, a); + if (index < 0) + return false; // already present in set, nothing to add + long previousState = longs[index]; + assert(LongHash.isFull(a)); + longs[index] = a; + postInsertHook(longs, hashBase, LongHash.isFree(previousState), allocator); + return true; // yes, we added something + } + + public static boolean remove(long[] longs, int hashBase, long a) { + int index = LongHash.index(longs, hashBase, a); + if (index >= 0) { + longs[index] = setRemoved(); + decUsedSize(longs, hashBase); + return true; + } + return false; + } + + public static boolean contains(long[] longs, int hashBase,long a) { + return index(longs, hashBase, a) >= 0; + } + + public static boolean isEmpty(long[] longs, int hashBase) { + return 0 == getUsedSize(longs, hashBase); + } + + public static void clear(long[] longs, int hashBase) { + long[] set = longs; + long free = setFree(); + int capacity = getRealSize(longs, hashBase); + for (int i = capacity; i-- > 0;) { + set[hashBase + i] = free; + } + setUsedSize(longs, hashBase, 0); + setFreeSize(longs, hashBase, capacity); + } + + /** + * Ensure that this hashtable has sufficient capacity to hold + * desiredCapacity additional elements without + * requiring a rehash. This is a tuning method you can call + * before doing a large insert. + * + * @param desiredSize an int value + */ + public static boolean ensureSize(AllocatorI allocator, int desiredSize) { + long[] longs = allocator.getLongs(); + int hashBase = allocator.getHashBase(); + int size = getUsedSize(longs, hashBase); + if (desiredSize > (getMaxSize(longs, hashBase) - size)) { + int newCapacity = ((desiredSize + size) << 1) + 1; + rehash(longs, hashBase, PrimeFinder.nextPrime(newCapacity), allocator); + return true; + } + return false; + } + + /** + * Compresses the hashtable to the minimum prime size (as defined by + * PrimeFinder) that will hold all of the elements currently in the table. + * If you have done a lot of remove operations and plan to do a + * lot of queries or insertions or iteration, it is a good idea to invoke + * this method. Doing so will accomplish two things: + * + *
    + *
  1. You'll free memory allocated to the table but no longer needed + * because of the remove()s.
    2. + * + *
  2. You'll get better query/insert/iterator performance because there + * won't be any REMOVED slots to skip over when probing for + * indices in the table.
    3. + *
+ */ + public static void compact(AllocatorI allocator) { + long[] longs = allocator.getLongs(); + int hashBase = allocator.getHashBase(); + // need at least one free spot for open addressing + rehash(longs, hashBase, PrimeFinder.nextPrime((getUsedSize(longs, hashBase) << 1) + 1), allocator); + } + + public static int setUp(AllocatorI allocator, int initialCapacity) { + int capacity = PrimeFinder.nextPrime(initialCapacity << 1); + int hashBase = allocator.allocate(capacity); + assert(hashBase == allocator.getHashBase()); + long[] longs = allocator.getLongs(); + setUsedAndRealSize(longs, hashBase, 0, capacity); + setMaxAndFreeSize(longs, hashBase, capacity >> 1, capacity); + return hashBase; + } + + /** + * Expands the set to accomodate new values. + * + * @param newCapacity + * an int value + */ + static final void rehash(long[] oldLongs, int oldHashBase, int newCapacity, + AllocatorI allocator) { + assert(PrimeFinder.nextPrime(newCapacity) == newCapacity); + int oldCapacity = getRealSize(oldLongs, oldHashBase); + int oldSize = getUsedSize(oldLongs, oldHashBase); + // new hash base is initialized to LongHash.freeSet() + int newHashBase = allocator.allocate(newCapacity); + long[] newLongs = allocator.getLongs(); + setUsedAndRealSize(newLongs, newHashBase, oldSize, newCapacity); + setMaxAndFreeSize(newLongs, newHashBase, newCapacity>>1, newCapacity - oldSize); + + for (int i = oldCapacity + oldHashBase; i-- > oldHashBase;) { + long o = oldLongs[i]; + if (isFull(o)) { + int index = insertionIndex(newLongs, newHashBase, o); + newLongs[index] = o; + } + } + } + + /** + * After an insert, this hook is called to adjust the size/free values of + * the set and to perform rehashing if necessary. + */ + protected static final void postInsertHook(long[] longs, int hashBase, + boolean usedFreeSlot, AllocatorI allocator) { + if (usedFreeSlot) { + decFreeSize(longs, hashBase); + } + + // rehash whenever we exhaust the available space in the table + if (incUsedSize(longs, hashBase) > getMaxSize(longs, hashBase) + || getFreeSize(longs, hashBase) == 0) { + // choose a new capacity suited to the new state of the table + // if we've grown beyond our maximum size, double capacity; + // if we've exhausted the free spots, rehash to the same capacity, + // which will free up any stale removed slots for reuse. + int newCapacity = getUsedSize(longs, hashBase) > getMaxSize(longs, + hashBase) ? PrimeFinder.nextPrime(getRealSize(longs, + hashBase) << 1) : getRealSize(longs, hashBase); + rehash(longs, hashBase, newCapacity, allocator); + } + } + + /** + * Locates the index of val. + * + * @param val + * an long value + * @return the index of val or -1 if it isn't in the set. + */ + static int index(long[] longs, int hashBase, long a) { + int hash, probe, index, length, hashIndex; + long[] set = longs; + length = getRealSize(longs, hashBase); + hash = computeHashCode(a); + index = hash % length; + hashIndex = hashBase + index; + + if (!LongHash.isFree(set[hashIndex]) + && (LongHash.isRemoved(set[hashIndex]) || set[hashIndex] != a)) { + // see Knuth, p. 529 + probe = 1 + (hash % (length - 2)); + + do { + index -= probe; + if (index < 0) { + index += length; + } + hashIndex = hashBase + index; + } while (!LongHash.isFree(set[hashIndex]) + && (LongHash.isRemoved(set[hashIndex]) || set[hashIndex] != a)); + } + + return LongHash.isFree(set[hashIndex]) ? -1 : hashIndex; + } + + /** + * Locates the index at which val can be inserted. if there is + * already a value equal()ing val in the set, returns that value + * as a negative integer. + * + * @param val + * an long value + * @return an int value + */ + static final int insertionIndex(long[] longs, int hashBase, long a) { + int hash, probe, index, length, hashIndex; + long[] set = longs; + length = getRealSize(longs, hashBase); + hash = computeHashCode(a); + index = hash % length; + assert(0 != hashBase); + hashIndex = hashBase + index; + + if (LongHash.isFree(set[hashIndex])) { + return hashIndex; // empty, all done + } else if (LongHash.isFull(set[hashIndex]) && set[hashIndex] == a) { + return -hashIndex; // already stored + } else { // already FULL or REMOVED, must probe + // compute the double hash + probe = 1 + (hash % (length - 2)); + + // if the slot we landed on is FULL (but not removed), probe + // until we find an empty slot, a REMOVED slot, or an element + // equal to the one we are trying to insert. + // finding an empty slot means that the value is not present + // and that we should use that slot as the insertion point; + // finding a REMOVED slot means that we need to keep searching, + // however we want to remember the offset of that REMOVED slot + // so we can reuse it in case a "new" insertion (i.e. not an update) + // is possible. + // finding a matching value means that we've found that our desired + // key is already in the table + + if (!LongHash.isRemoved(set[hashIndex])) { + // starting at the natural offset, probe until we find an + // offset that isn't full. + do { + index -= probe; + if (index < 0) { + index += length; + } + hashIndex = hashBase + index; + } while (LongHash.isFull(set[hashIndex]) && set[hashIndex] != a); + } + + // if the index we found was removed: continue probing until we + // locate a free location or an element which equal()s the + // one we have. + if (LongHash.isRemoved(set[hashIndex])) { + int firstRemoved = hashIndex; + while (!LongHash.isFree(set[hashIndex]) + && (LongHash.isRemoved(set[hashIndex]) || set[hashIndex] != a)) { + index -= probe; + if (index < 0) { + index += length; + } + hashIndex = hashBase + index; + } + return LongHash.isFull(set[hashIndex]) ? -hashIndex : firstRemoved; + } + // if it's full, the key is already stored + return LongHash.isFull(set[hashIndex]) ? -hashIndex : hashIndex; + } + } + + static final int computeHashCode(long aKey) { + int hash = ((int) (aKey ^ (aKey >> 32))) * 31; + return hash & 0x7fffffff; // Top bit reserved. + } + + interface AllocatorI { + int allocate(int size); // return base address of hash table, allocates also hash header + long[] getLongs(); // return base address of allocator memory + int getHashBase(); // return base address of hash table + } +} + +class LongIterator { + private long[] longs; + private int hashBase; + private int index; + // for reset + private int size; // number of elements in the set + private final LongHash.AllocatorI allocator; + + public LongIterator(LongHash.AllocatorI allocator) { + this.allocator = allocator; + this.reset(); + } + public int size() { + return this.size; + } + public void reset() { + if (longs == null || + LongHash.getUsedSize(longs, hashBase) != this.size || + longs != allocator.getLongs() || + hashBase != allocator.getHashBase()) { + this.longs = allocator.getLongs(); + this.hashBase = allocator.getHashBase(); + this.size = LongHash.getUsedSize(longs, hashBase); + } + this.index = LongHash.getRealSize(longs, hashBase); + } + public long next() { + if (moveToNextIndex()) + return longs[hashBase + index]; + return LongHash.setFree(); + } + protected final boolean moveToNextIndex() { + // doing the assignment && < 0 in one line saves 3 opcodes... + if ((index = nextIndex()) < 0) { + return false; + } + return true; + } + protected final int nextIndex() { + long[] states = longs; + int i = index; + while (i-- > 0 && (!LongHash.isFull(states[hashBase + i]))) + ; + return i; + } + public boolean hasNext() { + return nextIndex() >= 0; + } +} +