-/*******************************************************************************\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
+/*******************************************************************************
+ * 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
+ * <tt>desiredCapacity<tt> <b>additional</b> elements without
+ * requiring a rehash. This is a tuning method you can call
+ * before doing a large insert.
+ *
+ * @param desiredSize an <code>int</code> 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 <tt>remove</tt> 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:
+ *
+ * <ol>
+ * <li> You'll free memory allocated to the table but no longer needed
+ * because of the remove()s.</li>
+ *
+ * <li> You'll get better query/insert/iterator performance because there
+ * won't be any <tt>REMOVED</tt> slots to skip over when probing for
+ * indices in the table.</li>
+ * </ol>
+ */
+ 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 <code>int</code> 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 <tt>val</tt>.
+ *
+ * @param val
+ * an <code>long</code> value
+ * @return the index of <tt>val</tt> 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 <tt>val</tt> can be inserted. if there is
+ * already a value equal()ing <tt>val</tt> in the set, returns that value
+ * as a negative integer.
+ *
+ * @param val
+ * an <code>long</code> value
+ * @return an <code>int</code> 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;
+ }
+}
+
Code Review / simantics / platform.git / blobdiff