--- /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
+import org.simantics.db.exception.DatabaseException;\r
+import org.simantics.db.impl.ClusterI;\r
+import org.simantics.db.impl.IntAllocatorI;\r
+import org.simantics.db.impl.Modifier;\r
+\r
+final class IntHash2 extends IntHashTrait {\r
+ static final int HeaderSize = 4;\r
+ private static final int REAL_SIZE = -4; // Number of allocated slots.\r
+ private static final int USED_SIZE = -3; // Number of used slots.\r
+ private static final int FREE_SIZE = -2; // Number of free slots.\r
+ private static final int MAX_SIZE = -1; // Max number of used slots.\r
+\r
+ public static int getRealSize(int[] table, int hashBase) {\r
+ return table[hashBase + REAL_SIZE];\r
+ }\r
+\r
+ private static void setRealSize(int[] table, int hashBase, int realSize) {\r
+ assert(realSize > 0);\r
+ table[hashBase + REAL_SIZE] = realSize;\r
+ }\r
+\r
+ public static int getUsedSize(int[] table, int hashBase) {\r
+ return table[hashBase + USED_SIZE];\r
+ }\r
+\r
+ static void setUsedSize(int[] table, int hashBase, int usedSize) {\r
+ assert(usedSize >= 0);\r
+ table[hashBase + USED_SIZE] = usedSize;\r
+ }\r
+\r
+ // return value after decrement\r
+ static int decUsedSize(int[] table, int hashBase) {\r
+ table[hashBase + USED_SIZE] -= 1;\r
+ return table[hashBase + USED_SIZE];\r
+ }\r
+\r
+ // return value after increment\r
+ static int incUsedSize(int[] table, int hashBase) {\r
+ table[hashBase + USED_SIZE] += 1;\r
+ return table[hashBase + USED_SIZE];\r
+ }\r
+ static void setUsedAndRealSize(int[] table, int hashBase, int used, int real) {\r
+ setUsedSize(table, hashBase, used);\r
+ setRealSize(table, hashBase, real);\r
+ }\r
+ static int getFreeSize(int[] table, int hashBase) {\r
+ return table[hashBase + FREE_SIZE];\r
+ }\r
+\r
+ static void setFreeSize(int[] table, int hashBase, int freeSize) {\r
+ assert(freeSize >= 0);\r
+ table[hashBase + FREE_SIZE] = freeSize;\r
+ }\r
+\r
+ static void decFreeSize(int[] table, int hashBase) {\r
+ table[hashBase + FREE_SIZE] -= 1;\r
+ }\r
+ \r
+ static int getMaxSize(int[] table, int hashBase) {\r
+ return table[hashBase + MAX_SIZE];\r
+ }\r
+\r
+ static void setMaxSize(int[] table, int hashBase, int maxSize) {\r
+ assert(maxSize > 0);\r
+ table[hashBase + MAX_SIZE] = maxSize;\r
+ }\r
+ \r
+ static void setMaxAndFreeSize(int[] table, int hashBase, int max, int free) {\r
+ setMaxSize(table, hashBase, max);\r
+ setFreeSize(table, hashBase, free);\r
+ }\r
+\r
+ public static int getAllocatedSize(int[] table, int hashBase) {\r
+ return getRealSize(table, hashBase)*2 + HeaderSize;\r
+ }\r
+ public static int create(int[] keys, int[] vals, IntAllocatorI allocator) {\r
+ assert(keys.length > 0);\r
+ assert(keys.length == vals.length);\r
+ int desiredSize = keys.length;\r
+ int hashBase = create(desiredSize, allocator);\r
+ for (int i=0; i<desiredSize; ++i)\r
+ hashBase = add(allocator.getTable(), hashBase, keys[i], vals[i], allocator);\r
+ return hashBase;\r
+ }\r
+ private static int create(int desiredSize, IntAllocatorI allocator) {\r
+ int capacity = PrimeFinder.nextPrime((desiredSize << 1) + 1);\r
+ int hashBase = allocator.allocate(capacity*2 + HeaderSize) + HeaderSize;\r
+ int[] table = allocator.getTable();\r
+ setUsedAndRealSize(table, hashBase, 0, capacity);\r
+ setMaxAndFreeSize(table, hashBase, capacity >> 1, capacity);\r
+ return hashBase;\r
+ }\r
+ public static int add(int[] table, int hashBase, int key, int val, IntAllocatorI allocator) {\r
+ assert(isFull(key));\r
+ int index = insertionIndex(table, hashBase, key);\r
+ if (index < 0) {\r
+ int realIndex = -index;\r
+ assert(table[realIndex] == key);\r
+ if (table[realIndex+1] == val)\r
+ return 0; // value not modified\r
+ table[realIndex+1] = val;\r
+ return hashBase; // value modified\r
+ }\r
+ int previousState = table[index];\r
+ table[index] = key;\r
+ table[index+1] = val;\r
+ return postInsertHook(table, hashBase, isFree(previousState), allocator);\r
+ }\r
+\r
+ public static boolean remove(int[] table, int hashBase, int a) {\r
+ int index = index(table, hashBase, a);\r
+ if (index >= 0) {\r
+ table[index] = setRemoved();\r
+ table[index+1] = setFree();\r
+ decUsedSize(table, hashBase);\r
+ return true; // yes, we removed something\r
+ }\r
+ return false; // not in set, nothing to remove\r
+ }\r
+\r
+ public static int get(int[] table, int hashBase, int a) {\r
+ int index = index(table, hashBase, a);\r
+ if (index < 0)\r
+ return setFree();\r
+ return table[index+1];\r
+ }\r
+\r
+ public static boolean contains(int[] table, int hashBase, int a) {\r
+ return index(table, hashBase, a) >= 0;\r
+ }\r
+\r
+ public static boolean isEmpty(int[] table, int hashBase) {\r
+ return 0 == getUsedSize(table, hashBase);\r
+ }\r
+\r
+ public static void clear(int[] table, int hashBase) {\r
+ int[] set = table;\r
+ int free = setFree();\r
+ int capacity = getRealSize(table, hashBase);\r
+ for (int i = hashBase + capacity*2; i-- > hashBase;) {\r
+ set[i] = free;\r
+ }\r
+ setUsedSize(table, hashBase, 0);\r
+ setFreeSize(table, 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(int[] table, int hashBase, int desiredSize, IntAllocatorI allocator) {\r
+ int size = getUsedSize(table, hashBase);\r
+ if (desiredSize > (getMaxSize(table, hashBase) - size)) {\r
+ int newCapacity = ((desiredSize + size) << 1) + 1;\r
+ rehash(table, 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(int[] table, int hashBase, IntAllocatorI allocator) {\r
+ // need at least one free spot for open addressing\r
+ rehash(table, hashBase, PrimeFinder.nextPrime((getUsedSize(table, hashBase) << 1) + 1), allocator);\r
+ }\r
+\r
+ static <Context> boolean foreachInt(int[] table, int base\r
+ , ClusterI.PredicateProcedure<Context> procedure, Context context, Modifier modifier) throws DatabaseException {\r
+ int capacity = getRealSize(table, base);\r
+ final int size = getUsedSize(table, base);\r
+ int count = 0;\r
+ for (int i = capacity*2 + base;\r
+ (count < size) && (i-- > base);) {\r
+ int v = table[i];\r
+ int o = table[--i];\r
+ if (isFull(o)) {\r
+ int key;\r
+ if (null != modifier)\r
+ key = modifier.execute(o);\r
+ else\r
+ key = o;\r
+ if (procedure.execute(context, key, v))\r
+ return true; // loop was broken by procedure\r
+ if (size == ++count)\r
+ return false; // loop finished\r
+ }\r
+ }\r
+ assert(size == count);\r
+ return false; // loop finished\r
+ }\r
+\r
+ /**\r
+ * Expands the set to accomodate new values.\r
+ * \r
+ * @param newCapacity\r
+ * an <code>int</code> value\r
+ */\r
+ private static final int rehash(int[] oldTable, int oldHashBase, int newCapacity,\r
+ IntAllocatorI allocator) {\r
+ assert(PrimeFinder.nextPrime(newCapacity) == newCapacity);\r
+ int oldCapacity = getRealSize(oldTable, oldHashBase);\r
+ int oldSize = getUsedSize(oldTable, oldHashBase);\r
+ // new hash base is initialized to freeSet()\r
+ int newHashBase = allocator.allocate(newCapacity*2 + HeaderSize) + HeaderSize;\r
+ int[] newtable = allocator.getTable();\r
+ setUsedAndRealSize(newtable, newHashBase, oldSize, newCapacity);\r
+ setMaxAndFreeSize(newtable, newHashBase, newCapacity>>1, newCapacity - oldSize);\r
+ for (int i = oldCapacity*2 + oldHashBase; i-- > oldHashBase;) {\r
+ int v = oldTable[i];\r
+ int o = oldTable[--i];\r
+ if (isFull(o)) {\r
+ int index = insertionIndex(newtable, newHashBase, o);\r
+ newtable[index] = o;\r
+ newtable[index+1] = v;\r
+ }\r
+ }\r
+ return newHashBase;\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
+ private static final int postInsertHook(int[] table, int hashBase,\r
+ boolean usedFreeSlot, IntAllocatorI allocator) {\r
+ if (usedFreeSlot) {\r
+ decFreeSize(table, hashBase);\r
+ }\r
+\r
+ // rehash whenever we exhaust the available space in the table\r
+ if (incUsedSize(table, hashBase) > getMaxSize(table, hashBase)\r
+ || getFreeSize(table, 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(table, hashBase) > getMaxSize(table,\r
+ hashBase) ? PrimeFinder.nextPrime(getRealSize(table,\r
+ hashBase) << 1) : getRealSize(table, hashBase);\r
+ return rehash(table, hashBase, newCapacity, allocator);\r
+ }\r
+ return hashBase;\r
+ }\r
+\r
+ /**\r
+ * Locates the index of <tt>val</tt>.\r
+ * \r
+ * @param val\r
+ * an <code>int</code> value\r
+ * @return the index of <tt>val</tt> or -1 if it isn't in the set.\r
+ */\r
+ private static int index(int[] table, int hashBase, int a) {\r
+ int hash, probe, index, length, hashIndex;\r
+ int[] set = table;\r
+ length = getRealSize(table, hashBase);\r
+ hash = computeHashCode(a);\r
+ index = hash % length;\r
+ hashIndex = hashBase + index*2;\r
+\r
+ if (!isFree(set[hashIndex])\r
+ && (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*2;\r
+ } while (!isFree(set[hashIndex])\r
+ && (isRemoved(set[hashIndex]) || set[hashIndex] != a));\r
+ }\r
+\r
+ return 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>int</code> value\r
+ * @return an <code>int</code> value\r
+ */\r
+ private static final int insertionIndex(int[] table, int hashBase, int a) {\r
+ int hash, probe, index, length, hashIndex;\r
+ int[] set = table;\r
+ length = getRealSize(table, hashBase);\r
+ hash = computeHashCode(a);\r
+ index = hash % length;\r
+ assert(0 != hashBase);\r
+ hashIndex = hashBase + index*2;\r
+ \r
+ if (isFree(set[hashIndex])) {\r
+ return hashIndex; // empty, all done\r
+ } else if (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 (!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*2;\r
+ } while (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 (isRemoved(set[hashIndex])) {\r
+ int firstRemoved = hashIndex;\r
+ while (!isFree(set[hashIndex])\r
+ && (isRemoved(set[hashIndex]) || set[hashIndex] != a)) {\r
+ index -= probe;\r
+ if (index < 0) {\r
+ index += length;\r
+ }\r
+ hashIndex = hashBase + index*2;\r
+ }\r
+ return isFull(set[hashIndex]) ? -hashIndex : firstRemoved;\r
+ }\r
+ // if it's full, the key is already stored\r
+ return isFull(set[hashIndex]) ? -hashIndex : hashIndex;\r
+ }\r
+ }\r
+\r
+ private static final int computeHashCode(int aKey) {\r
+ int hash = aKey * 31;\r
+ return hash & 0x7fffffff; // Top bit reserved.\r
+ }\r
+}\r
Code Review / simantics / platform.git / blobdiff