-/*******************************************************************************\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 org.simantics.db.Resource;\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
-import org.simantics.db.impl.ResourceImpl;\r
-import org.simantics.db.impl.graph.ReadGraphImpl;\r
-import org.simantics.db.procedure.AsyncContextMultiProcedure;\r
-import org.simantics.db.procedure.AsyncMultiProcedure;\r
-\r
-import gnu.trove.impl.PrimeFinder;\r
-\r
-public class IntHash 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) + HeaderSize;\r
- }\r
- public static int create(int[] ints, IntAllocatorI allocator) {\r
- assert(ints.length > 0);\r
- int desiredSize = ints.length;\r
- int hashBase = create(desiredSize, allocator);\r
- for (int i=0; i<desiredSize; ++i)\r
- hashBase = add(allocator.getTable(), hashBase, ints[i], allocator);\r
- return hashBase;\r
- }\r
- public static int create(int desiredSize, IntAllocatorI allocator) {\r
- int capacity = PrimeFinder.nextPrime((desiredSize << 1) + 1);\r
- int hashBase = allocator.allocate(capacity + 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
-\r
- public static int add(int[] table, int hashBase, int a, IntAllocatorI allocator) {\r
- int index = insertionIndex(table, hashBase, a);\r
- if (index < 0)\r
- return 0; // already present in set, nothing to add\r
- int previousState = table[index];\r
- assert(isFull(a));\r
- table[index] = a;\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
- 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 removeLast(int[] table, int hashBase)\r
- throws DatabaseException {\r
- final int size = getUsedSize(table, hashBase);\r
- if (size != 1)\r
- throw new DatabaseException("Illegal call of IntHash.removeLast.");\r
- int capacity = getRealSize(table, hashBase);\r
- int count = 0;\r
- for (int i = capacity + hashBase;\r
- (count < size) && (i-- > hashBase);) {\r
- int o = table[i];\r
- if (isFull(o)) {\r
- table[i] = setRemoved();\r
- decUsedSize(table, hashBase);\r
- return o;\r
- }\r
- }\r
- throw new DatabaseException("IntHash.removeLast call failed.");\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 = capacity; i-- > 0;) {\r
- set[hashBase + 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
- \r
- static void foreachInt(final ReadGraphImpl graph, int[] table, int base, final AsyncMultiProcedure<Resource> procedure, Modifier modifier) throws DatabaseException {\r
-\r
- int capacity = getRealSize(table, base);\r
- final int size = getUsedSize(table, base);\r
-// final int threadMask = graph.state.threadMask;\r
-//\r
-// int callerThread = graph.callerThread;\r
- \r
- int count = 0;\r
-// AtomicInteger ready = null;\r
- \r
- for (int i = capacity + base;\r
- (count < size) && (i-- > base);) {\r
- int o = table[i];\r
- if (isFull(o)) {\r
-\r
- final int actual = modifier.execute(o);\r
- \r
-// int suggestSchedule = (actual>>16) & threadMask;\r
-// if(callerThread == suggestSchedule) {\r
- \r
- procedure.execute(graph, new ResourceImpl(graph.getResourceSupport(), actual));\r
- count++;\r
- \r
-// } else {\r
-//\r
-// if(ready == null) ready = new AtomicInteger(1);\r
-// ready.incrementAndGet();\r
-// final AtomicInteger r = ready;\r
-// \r
-// graph.state.barrier.inc();\r
-// graph.processor.processor.schedule(callerThread, new SessionTask(suggestSchedule) {\r
-// \r
-// @Override\r
-// public void run(int thread) {\r
-// \r
-// procedure.execute(graph.newAsync(thread), new ResourceImpl(null, actual));\r
-// if(r.decrementAndGet() == 0) {\r
-// procedure.finished(graph);\r
-// }\r
-// graph.state.barrier.dec();\r
-// \r
-// }\r
-// \r
-// });\r
-// \r
-// }\r
-\r
-// procedure.execute(graph, new ResourceImpl(null, modifier.execute(o)));\r
- \r
-//// if (size == ++count) {\r
-// if(ready == null) {\r
-// procedure.finished(graph);\r
-// } else {\r
-// if(ready.decrementAndGet() == 0) {\r
-// procedure.finished(graph);\r
-// }\r
-// }\r
-// graph.dec();\r
-// return;\r
-//// }\r
- \r
- }\r
- \r
- }\r
- // Execution was not deferred\r
-// if(ready == null) {\r
- procedure.finished(graph);\r
-// } else {\r
-// if(ready.decrementAndGet() == 0) {\r
-// procedure.finished(graph);\r
-// }\r
-// }\r
-// graph.dec();\r
- assert(size == count);\r
- }\r
-\r
- static <C> void foreachInt(final ReadGraphImpl graph, int[] table, int base, C context, final AsyncContextMultiProcedure<C, Resource> procedure, Modifier modifier) throws DatabaseException {\r
-\r
- int capacity = getRealSize(table, base);\r
- final int size = getUsedSize(table, base);\r
-\r
- int count = 0;\r
-\r
- for (int i = capacity + base;\r
- (count < size) && (i-- > base);) {\r
- int o = table[i];\r
- if (isFull(o)) {\r
-\r
- final int actual = modifier.execute(o);\r
- procedure.execute(graph, context, new ResourceImpl(graph.getResourceSupport(), actual));\r
- count++;\r
- }\r
-\r
- }\r
- \r
- procedure.finished(graph);\r
-// graph.dec();\r
- assert(size == count);\r
- \r
- }\r
- \r
- static int getSingleInt(int[] table, int base, Modifier modifier) throws DatabaseException {\r
- int result = 0;\r
- int capacity = getRealSize(table, base);\r
- final int size = getUsedSize(table, base);\r
- int count = 0;\r
- for (int i = capacity + base;\r
- (count < size) && (i-- > base);) {\r
- int o = table[i];\r
- if (isFull(o)) {\r
- int value;\r
- if (null != modifier)\r
- value = modifier.execute(o);\r
- else\r
- value = o;\r
- \r
- if(result == 0) result = value;\r
- else result = -1;\r
- \r
- if (size == ++count) break;\r
- \r
- }\r
- }\r
- assert(size == count);\r
- \r
- return result;\r
-// if(result == -1) return 0;\r
-// else return result;\r
- \r
- }\r
- \r
- static <Context> boolean foreachInt(int[] table, int base\r
- , ClusterI.ObjectProcedure<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 + base;\r
- (count < size) && (i-- > base);) {\r
- int o = table[i];\r
- if (isFull(o)) {\r
- int value;\r
- if (null != modifier)\r
- value = modifier.execute(o);\r
- else\r
- value = o;\r
- if (procedure.execute(context, value))\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 + HeaderSize) + HeaderSize;\r
- int[] newtable = allocator.getTable();\r
- \r
- setUsedAndRealSize(newtable, newHashBase, oldSize, newCapacity);\r
- setMaxAndFreeSize(newtable, newHashBase, newCapacity>>1, newCapacity - oldSize);\r
- \r
- for (int i = oldCapacity + oldHashBase; i-- > oldHashBase;) {\r
- int o = oldtable[i];\r
- if (isFull(o)) {\r
- int index = insertionIndex(newtable, newHashBase, o);\r
- newtable[index] = o;\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;\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;\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;\r
- \r
-// int used = getUsedSize(table, hashBase);\r
-// int max = getMaxSize(table, hashBase);\r
-// assert(used > max);\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;\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;\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
+/*******************************************************************************
+ * 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 org.simantics.db.Resource;
+import org.simantics.db.exception.DatabaseException;
+import org.simantics.db.impl.ClusterI;
+import org.simantics.db.impl.IntAllocatorI;
+import org.simantics.db.impl.Modifier;
+import org.simantics.db.impl.ResourceImpl;
+import org.simantics.db.impl.graph.ReadGraphImpl;
+import org.simantics.db.procedure.AsyncContextMultiProcedure;
+import org.simantics.db.procedure.AsyncMultiProcedure;
+
+import gnu.trove.impl.PrimeFinder;
+
+public class IntHash extends IntHashTrait {
+ static final int HeaderSize = 4;
+ private static final int REAL_SIZE = -4; // Number of allocated slots.
+ private static final int USED_SIZE = -3; // Number of used slots.
+ private static final int FREE_SIZE = -2; // Number of free slots.
+ private static final int MAX_SIZE = -1; // Max number of used slots.
+
+ public static int getRealSize(int[] table, int hashBase) {
+ return table[hashBase + REAL_SIZE];
+ }
+
+ private static void setRealSize(int[] table, int hashBase, int realSize) {
+ assert(realSize > 0);
+ table[hashBase + REAL_SIZE] = realSize;
+ }
+
+ public static int getUsedSize(int[] table, int hashBase) {
+ return table[hashBase + USED_SIZE];
+ }
+
+ static void setUsedSize(int[] table, int hashBase, int usedSize) {
+ assert(usedSize >= 0);
+ table[hashBase + USED_SIZE] = usedSize;
+ }
+
+ // return value after decrement
+ static int decUsedSize(int[] table, int hashBase) {
+ table[hashBase + USED_SIZE] -= 1;
+ return table[hashBase + USED_SIZE];
+ }
+
+ // return value after increment
+ static int incUsedSize(int[] table, int hashBase) {
+ table[hashBase + USED_SIZE] += 1;
+ return table[hashBase + USED_SIZE];
+ }
+ static void setUsedAndRealSize(int[] table, int hashBase, int used, int real) {
+ setUsedSize(table, hashBase, used);
+ setRealSize(table, hashBase, real);
+ }
+ static int getFreeSize(int[] table, int hashBase) {
+ return table[hashBase + FREE_SIZE];
+ }
+
+ static void setFreeSize(int[] table, int hashBase, int freeSize) {
+ assert(freeSize >= 0);
+ table[hashBase + FREE_SIZE] = freeSize;
+ }
+
+ static void decFreeSize(int[] table, int hashBase) {
+ table[hashBase + FREE_SIZE] -= 1;
+ }
+
+ static int getMaxSize(int[] table, int hashBase) {
+ return table[hashBase + MAX_SIZE];
+ }
+
+ static void setMaxSize(int[] table, int hashBase, int maxSize) {
+ assert(maxSize > 0);
+ table[hashBase + MAX_SIZE] = maxSize;
+ }
+
+ static void setMaxAndFreeSize(int[] table, int hashBase, int max, int free) {
+ setMaxSize(table, hashBase, max);
+ setFreeSize(table, hashBase, free);
+ }
+
+ public static int getAllocatedSize(int[] table, int hashBase) {
+ return getRealSize(table, hashBase) + HeaderSize;
+ }
+ public static int create(int[] ints, IntAllocatorI allocator) {
+ assert(ints.length > 0);
+ int desiredSize = ints.length;
+ int hashBase = create(desiredSize, allocator);
+ for (int i=0; i<desiredSize; ++i)
+ hashBase = add(allocator.getTable(), hashBase, ints[i], allocator);
+ return hashBase;
+ }
+ public static int create(int desiredSize, IntAllocatorI allocator) {
+ int capacity = PrimeFinder.nextPrime((desiredSize << 1) + 1);
+ int hashBase = allocator.allocate(capacity + HeaderSize) + HeaderSize;
+ int[] table = allocator.getTable();
+ setUsedAndRealSize(table, hashBase, 0, capacity);
+ setMaxAndFreeSize(table, hashBase, capacity >> 1, capacity);
+ return hashBase;
+ }
+
+ public static int add(int[] table, int hashBase, int a, IntAllocatorI allocator) {
+ int index = insertionIndex(table, hashBase, a);
+ if (index < 0)
+ return 0; // already present in set, nothing to add
+ int previousState = table[index];
+ assert(isFull(a));
+ table[index] = a;
+ return postInsertHook(table, hashBase, isFree(previousState), allocator);
+ }
+
+ public static boolean remove(int[] table, int hashBase, int a) {
+ int index = index(table, hashBase, a);
+ if (index >= 0) {
+ table[index] = setRemoved();
+ decUsedSize(table, hashBase);
+ return true; // yes, we removed something
+ }
+ return false; // not in set, nothing to remove
+ }
+
+ public static int removeLast(int[] table, int hashBase)
+ throws DatabaseException {
+ final int size = getUsedSize(table, hashBase);
+ if (size != 1)
+ throw new DatabaseException("Illegal call of IntHash.removeLast.");
+ int capacity = getRealSize(table, hashBase);
+ int count = 0;
+ for (int i = capacity + hashBase;
+ (count < size) && (i-- > hashBase);) {
+ int o = table[i];
+ if (isFull(o)) {
+ table[i] = setRemoved();
+ decUsedSize(table, hashBase);
+ return o;
+ }
+ }
+ throw new DatabaseException("IntHash.removeLast call failed.");
+ }
+
+ public static boolean contains(int[] table, int hashBase, int a) {
+ return index(table, hashBase, a) >= 0;
+ }
+
+ public static boolean isEmpty(int[] table, int hashBase) {
+ return 0 == getUsedSize(table, hashBase);
+ }
+
+ public static void clear(int[] table, int hashBase) {
+ int[] set = table;
+ int free = setFree();
+ int capacity = getRealSize(table, hashBase);
+ for (int i = capacity; i-- > 0;) {
+ set[hashBase + i] = free;
+ }
+ setUsedSize(table, hashBase, 0);
+ setFreeSize(table, 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(int[] table, int hashBase, int desiredSize, IntAllocatorI allocator) {
+ int size = getUsedSize(table, hashBase);
+ if (desiredSize > (getMaxSize(table, hashBase) - size)) {
+ int newCapacity = ((desiredSize + size) << 1) + 1;
+ rehash(table, 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(int[] table, int hashBase, IntAllocatorI allocator) {
+ // need at least one free spot for open addressing
+ rehash(table, hashBase, PrimeFinder.nextPrime((getUsedSize(table, hashBase) << 1) + 1), allocator);
+ }
+
+
+ static void foreachInt(final ReadGraphImpl graph, int[] table, int base, final AsyncMultiProcedure<Resource> procedure, Modifier modifier) throws DatabaseException {
+
+ int capacity = getRealSize(table, base);
+ final int size = getUsedSize(table, base);
+// final int threadMask = graph.state.threadMask;
+//
+// int callerThread = graph.callerThread;
+
+ int count = 0;
+// AtomicInteger ready = null;
+
+ for (int i = capacity + base;
+ (count < size) && (i-- > base);) {
+ int o = table[i];
+ if (isFull(o)) {
+
+ final int actual = modifier.execute(o);
+
+// int suggestSchedule = (actual>>16) & threadMask;
+// if(callerThread == suggestSchedule) {
+
+ procedure.execute(graph, new ResourceImpl(graph.getResourceSupport(), actual));
+ count++;
+
+// } else {
+//
+// if(ready == null) ready = new AtomicInteger(1);
+// ready.incrementAndGet();
+// final AtomicInteger r = ready;
+//
+// graph.state.barrier.inc();
+// graph.processor.processor.schedule(callerThread, new SessionTask(suggestSchedule) {
+//
+// @Override
+// public void run(int thread) {
+//
+// procedure.execute(graph.newAsync(thread), new ResourceImpl(null, actual));
+// if(r.decrementAndGet() == 0) {
+// procedure.finished(graph);
+// }
+// graph.state.barrier.dec();
+//
+// }
+//
+// });
+//
+// }
+
+// procedure.execute(graph, new ResourceImpl(null, modifier.execute(o)));
+
+//// if (size == ++count) {
+// if(ready == null) {
+// procedure.finished(graph);
+// } else {
+// if(ready.decrementAndGet() == 0) {
+// procedure.finished(graph);
+// }
+// }
+// graph.dec();
+// return;
+//// }
+
+ }
+
+ }
+ // Execution was not deferred
+// if(ready == null) {
+ procedure.finished(graph);
+// } else {
+// if(ready.decrementAndGet() == 0) {
+// procedure.finished(graph);
+// }
+// }
+// graph.dec();
+ assert(size == count);
+ }
+
+ static <C> void foreachInt(final ReadGraphImpl graph, int[] table, int base, C context, final AsyncContextMultiProcedure<C, Resource> procedure, Modifier modifier) throws DatabaseException {
+
+ int capacity = getRealSize(table, base);
+ final int size = getUsedSize(table, base);
+
+ int count = 0;
+
+ for (int i = capacity + base;
+ (count < size) && (i-- > base);) {
+ int o = table[i];
+ if (isFull(o)) {
+
+ final int actual = modifier.execute(o);
+ procedure.execute(graph, context, new ResourceImpl(graph.getResourceSupport(), actual));
+ count++;
+ }
+
+ }
+
+ procedure.finished(graph, context);
+// graph.dec();
+ assert(size == count);
+
+ }
+
+ static int getSingleInt(int[] table, int base, Modifier modifier) throws DatabaseException {
+ int result = 0;
+ int capacity = getRealSize(table, base);
+ final int size = getUsedSize(table, base);
+ int count = 0;
+ for (int i = capacity + base;
+ (count < size) && (i-- > base);) {
+ int o = table[i];
+ if (isFull(o)) {
+ int value;
+ if (null != modifier)
+ value = modifier.execute(o);
+ else
+ value = o;
+
+ if(result == 0) result = value;
+ else result = -1;
+
+ if (size == ++count) break;
+
+ }
+ }
+ assert(size == count);
+
+ return result;
+// if(result == -1) return 0;
+// else return result;
+
+ }
+
+ static <Context> boolean foreachInt(int[] table, int base
+ , ClusterI.ObjectProcedure<Context> procedure, Context context, Modifier modifier) throws DatabaseException {
+ int capacity = getRealSize(table, base);
+ final int size = getUsedSize(table, base);
+ int count = 0;
+ for (int i = capacity + base;
+ (count < size) && (i-- > base);) {
+ int o = table[i];
+ if (isFull(o)) {
+ int value;
+ if (null != modifier)
+ value = modifier.execute(o);
+ else
+ value = o;
+ if (procedure.execute(context, value))
+ return true; // loop was broken by procedure
+ if (size == ++count)
+ return false; // loop finished
+ }
+ }
+ assert(size == count);
+ return false; // loop finished
+ }
+
+ /**
+ * Expands the set to accomodate new values.
+ *
+ * @param newCapacity
+ * an <code>int</code> value
+ */
+ private static final int rehash(int[] oldtable, int oldHashBase, int newCapacity,
+ IntAllocatorI allocator) {
+ assert(PrimeFinder.nextPrime(newCapacity) == newCapacity);
+ int oldCapacity = getRealSize(oldtable, oldHashBase);
+ int oldSize = getUsedSize(oldtable, oldHashBase);
+ // new hash base is initialized to freeSet()
+ int newHashBase = allocator.allocate(newCapacity + HeaderSize) + HeaderSize;
+ int[] newtable = allocator.getTable();
+
+ setUsedAndRealSize(newtable, newHashBase, oldSize, newCapacity);
+ setMaxAndFreeSize(newtable, newHashBase, newCapacity>>1, newCapacity - oldSize);
+
+ for (int i = oldCapacity + oldHashBase; i-- > oldHashBase;) {
+ int o = oldtable[i];
+ if (isFull(o)) {
+ int index = insertionIndex(newtable, newHashBase, o);
+ newtable[index] = o;
+ }
+ }
+ return newHashBase;
+ }
+
+ /**
+ * After an insert, this hook is called to adjust the size/free values of
+ * the set and to perform rehashing if necessary.
+ */
+ private static final int postInsertHook(int[] table, int hashBase,
+ boolean usedFreeSlot, IntAllocatorI allocator) {
+ if (usedFreeSlot) {
+ decFreeSize(table, hashBase);
+ }
+
+ // rehash whenever we exhaust the available space in the table
+ if (incUsedSize(table, hashBase) > getMaxSize(table, hashBase)
+ || getFreeSize(table, 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(table, hashBase) > getMaxSize(table,
+ hashBase) ? PrimeFinder.nextPrime(getRealSize(table,
+ hashBase) << 1) : getRealSize(table, hashBase);
+ return rehash(table, hashBase, newCapacity, allocator);
+ }
+ return hashBase;
+ }
+
+ /**
+ * Locates the index of <tt>val</tt>.
+ *
+ * @param val
+ * an <code>int</code> value
+ * @return the index of <tt>val</tt> or -1 if it isn't in the set.
+ */
+ private static int index(int[] table, int hashBase, int a) {
+ int hash, probe, index, length, hashIndex;
+ int[] set = table;
+ length = getRealSize(table, hashBase);
+ hash = computeHashCode(a);
+ index = hash % length;
+ hashIndex = hashBase + index;
+
+ if (!isFree(set[hashIndex])
+ && (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 (!isFree(set[hashIndex])
+ && (isRemoved(set[hashIndex]) || set[hashIndex] != a));
+ }
+
+ return 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>int</code> value
+ * @return an <code>int</code> value
+ */
+ private static final int insertionIndex(int[] table, int hashBase, int a) {
+ int hash, probe, index, length, hashIndex;
+ int[] set = table;
+ length = getRealSize(table, hashBase);
+ hash = computeHashCode(a);
+ index = hash % length;
+ assert(0 != hashBase);
+ hashIndex = hashBase + index;
+
+// int used = getUsedSize(table, hashBase);
+// int max = getMaxSize(table, hashBase);
+// assert(used > max);
+//
+ if (isFree(set[hashIndex])) {
+ return hashIndex; // empty, all done
+ } else if (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 (!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 (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 (isRemoved(set[hashIndex])) {
+ int firstRemoved = hashIndex;
+ while (!isFree(set[hashIndex])
+ && (isRemoved(set[hashIndex]) || set[hashIndex] != a)) {
+ index -= probe;
+ if (index < 0) {
+ index += length;
+ }
+ hashIndex = hashBase + index;
+ }
+ return isFull(set[hashIndex]) ? -hashIndex : firstRemoved;
+ }
+ // if it's full, the key is already stored
+ return isFull(set[hashIndex]) ? -hashIndex : hashIndex;
+ }
+ }
+
+ private static final int computeHashCode(int aKey) {
+ int hash = aKey * 31;
+ return hash & 0x7fffffff; // Top bit reserved.
+ }
+}