]> gerrit.simantics Code Review - simantics/platform.git/blobdiff - bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/LongHash.java
Migrated source code from Simantics SVN
[simantics/platform.git] / bundles / org.simantics.db.procore / src / org / simantics / db / procore / cluster / LongHash.java
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
new file mode 100644 (file)
index 0000000..77f5d89
--- /dev/null
@@ -0,0 +1,479 @@
+/*******************************************************************************\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