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