--- /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 org.simantics.db.exception.DatabaseException;\r
+import org.simantics.db.impl.ClusterI.Procedure;\r
+import org.simantics.db.impl.ClusterSupport;\r
+import org.simantics.db.impl.Modifier;\r
+import org.simantics.db.impl.Table;\r
+import org.simantics.db.impl.TableFactory;\r
+import org.simantics.db.impl.TableSizeListener;\r
+\r
+import gnu.trove.impl.PrimeFinder;\r
+\r
+class TableIntHash extends Table<int[]> {\r
+ private static final int INITIAL_SIZE = 1000;\r
+ private static final int ENTRY_SIZE = 3;\r
+ protected static final int HeaderSize = 5;\r
+ private static final int Capacity = -5; // Number of allocated slots.\r
+ private static final int Size = -4; // Number of used slots.\r
+ private static final int Free = -3; // Number of free slots.\r
+ private static final int MaxInsert = -2; // Limit for increasing number of allocated slots.\r
+ private static final int MaxRemove = -1; // Limit for removing removed slots.\r
+ protected int[] ints;\r
+ protected int hashBase;\r
+ TableIntHash(TableSizeListener sizeListener, int[] header, int headerBase) {\r
+ super(TableFactory.getIntFactory(), sizeListener, header, headerBase);\r
+ int capacity = PrimeFinder.nextPrime(INITIAL_SIZE);\r
+ int tableSize = ENTRY_SIZE * capacity + HeaderSize;\r
+ createNewTable(tableSize, tableSize, 1); // size, capacity, count\r
+ ints = getTable();\r
+ hashBase = getTableBase() + HeaderSize;\r
+ capacitySet(capacity);\r
+ sizeSet(0);\r
+ freeSet(capacity);\r
+ computeMaxInsert(capacity);\r
+ computeMaxRemove(maxInsertGet());\r
+ }\r
+ TableIntHash(TableSizeListener sizeListener, int[] header, int headerBase, int[] ints) {\r
+ super(TableFactory.getIntFactory(), sizeListener, header, headerBase, ints);\r
+ this.ints = getTable();\r
+ this.hashBase = getTableBase() + HeaderSize;\r
+ }\r
+ static final boolean isFree(int v) {\r
+ return IntHashTrait.isFree(v);\r
+ }\r
+\r
+ static final boolean isFull(int v) {\r
+ return IntHashTrait.isFull(v);\r
+ }\r
+\r
+ final boolean isFullByIndex(int index) {\r
+ return isFull(setGet(index));\r
+ }\r
+\r
+ static final boolean isRemoved(int v) {\r
+ return IntHashTrait.isRemoved(v);\r
+ }\r
+\r
+ static final int setFree() {\r
+ return IntHashTrait.setFree();\r
+ }\r
+\r
+ static final int setFull(int v) {\r
+ return IntHashTrait.setFull(v);\r
+ }\r
+\r
+ static final int setRemoved() {\r
+ return IntHashTrait.setRemoved();\r
+ }\r
+ final int capacityGet() {\r
+ return ints[hashBase + Capacity];\r
+ }\r
+ final void capacitySet(int a) {\r
+ ints[hashBase + Capacity] = a;\r
+ }\r
+ final int sizeGet() {\r
+ return ints[hashBase + Size];\r
+ }\r
+ final void sizeSet(int a) {\r
+ ints[hashBase + Size] = a;\r
+ }\r
+ final int freeGet() {\r
+ return ints[hashBase + Free];\r
+ }\r
+ final void freeSet(int a) {\r
+ ints[hashBase + Free] = a;\r
+ }\r
+ final int maxInsertGet() {\r
+ return ints[hashBase + MaxInsert];\r
+ }\r
+ final void maxInsertSet(int a) {\r
+ ints[hashBase + MaxInsert] = a;\r
+ }\r
+ final int maxRemoveGet() {\r
+ return ints[hashBase + MaxRemove];\r
+ }\r
+ void maxRemoveSet(int a) {\r
+ ints[hashBase + MaxRemove] = a;\r
+ }\r
+ final int setGet(final int index) {\r
+ return ints[hashBase + index * ENTRY_SIZE + 2];\r
+ }\r
+ final void setSet(int index, int value) {\r
+ ints[hashBase + index * ENTRY_SIZE + 2] = value;\r
+ }\r
+ final void setKeyAndValue(int index, int key1, int key2, int value) {\r
+ int realIndex = index * ENTRY_SIZE;\r
+ ints[hashBase + realIndex] = key1;\r
+ ints[hashBase + realIndex + 1] = key2;\r
+ ints[hashBase + realIndex + 2] = value;\r
+ }\r
+ final boolean isFreeByIndex(final int index) {\r
+ return isFree(ints[hashBase + index * ENTRY_SIZE + 2]);\r
+ }\r
+ final boolean isRemovedByIndex(final int index) {\r
+ return isRemoved(ints[hashBase + index * ENTRY_SIZE + 2]);\r
+ }\r
+ final boolean isEqualByIndex(final int index, final int key1, final int key2) {\r
+ int realIndex = index * ENTRY_SIZE;\r
+ return key1 == ints[hashBase + realIndex] && key2 == ints[hashBase + realIndex + 1];\r
+ }\r
+ final void computeMaxInsert(int capacity) {\r
+ // need at least one free slot for open addressing\r
+ int maxSize = Math.min(capacity - 1, capacity >> 1);\r
+ maxInsertSet(maxSize);\r
+ freeSet(capacity - sizeGet()); // reset the free element count\r
+ }\r
+ \r
+ final void computeMaxRemove(int removeCapacity) {\r
+ maxRemoveSet((removeCapacity >> 1) + 1);\r
+ }\r
+ /**\r
+ * retrieves the value for <tt>key</tt>\r
+ * \r
+ * @param key an <code>int</code> value\r
+ * @return the value of <tt>key</tt> or (int)0 if no such mapping exists.\r
+ */\r
+ final int getValue(int key1, int key2) {\r
+ int index = index(key1, key2);\r
+ return index < 0 ? 0 : setGet(index);\r
+ }\r
+ final boolean removeValue(int key1, int key2) {\r
+ int index = index(key1, key2);\r
+ if (index < 0)\r
+ return false;\r
+ setSet(index, setRemoved());\r
+ return true;\r
+ \r
+ }\r
+ final boolean setValue(int key1, int key2, int value) {\r
+ assert(!isFree(value));\r
+ assert(!isRemoved(value));\r
+ int index = insertionIndex(key1, key2);\r
+ boolean added = true;\r
+ boolean isNewMapping = true;\r
+ boolean previousStateWasFree = false;\r
+ if (index < 0) { // old entry\r
+ index = -index - 1;\r
+ setSet(index, value);\r
+ isNewMapping = false;\r
+ } else { // new entry\r
+ if (isFreeByIndex(index))\r
+ previousStateWasFree = true;\r
+ setKeyAndValue(index, key1, key2, value);\r
+ }\r
+ if (isNewMapping)\r
+ postInsertHook(previousStateWasFree);\r
+ return added;\r
+ \r
+ }\r
+ /**\r
+ * Locates the index of <tt>akey</tt>.\r
+ *\r
+ * @param akey an <code>int</code> value\r
+ * @return the index of <tt>akey</tt> or -1 if it isn't in the set.\r
+ */\r
+ final int index(final int akey1, final int akey2) {\r
+ int hash, probe, index, length;\r
+ //IntArray set = _set;\r
+ length = capacityGet();\r
+ hash = computeHashCode(akey1, akey2);\r
+ index = hash % length;\r
+ if (!isFreeByIndex(index) &&\r
+ (isRemovedByIndex(index) ||\r
+ !isEqualByIndex(index, akey1, akey2))) {\r
+ // see Knuth, p. 529\r
+ probe = 1 + (hash % (length - 2));\r
+ do {\r
+ index -= probe;\r
+ if (index < 0) {\r
+ index += length;\r
+ }\r
+ } while (!isFreeByIndex(index) &&\r
+ (isRemovedByIndex(index) ||\r
+ !isEqualByIndex(index, akey1, akey2)));\r
+ }\r
+\r
+ return isFreeByIndex(index) ? -1 : index;\r
+ }\r
+ /**\r
+ * Locates the index at which <tt>akey</tt> can be inserted. if\r
+ * there is already a key equaling <tt>akey</tt> in the set,\r
+ * returns that key as a negative integer.\r
+ *\r
+ * @param akey an <code>long</code> value\r
+ * @return an <code>int</code> value\r
+ */\r
+ final int insertionIndex(int akey1, int akey2) {\r
+ int hash, probe, index, length;\r
+ //IntArray set = _set;\r
+ length = capacityGet();\r
+ hash = computeHashCode(akey1, akey2);\r
+ index = hash % length;\r
+ if (isFreeByIndex(index)) {\r
+ return index; // empty, all done\r
+ } else if (isFullByIndex(index) && isEqualByIndex(index, akey1, akey2)) {\r
+ return -index -1; // 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 (!isRemovedByIndex(index)) {\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
+ } while (isFullByIndex(index) && !isEqualByIndex(index, akey1, akey2));\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 (isRemovedByIndex(index)) {\r
+ int firstRemoved = index;\r
+ while (!isFreeByIndex(index) &&\r
+ (isRemovedByIndex(index) || !isEqualByIndex(index, akey1, akey2))) {\r
+ index -= probe;\r
+ if (index < 0) {\r
+ index += length;\r
+ }\r
+ }\r
+ return isFullByIndex(index) ? -index -1 : firstRemoved;\r
+ }\r
+ // if it's full, the key is already stored\r
+ return isFullByIndex(index) ? -index -1 : index;\r
+ }\r
+ }\r
+\r
+ static final int computeHashCode(int key1, int key2) {\r
+ // Multiple by prime to make sure hash can't be negative (see Knuth v3, p. 515-516)\r
+ int hash;\r
+ if (key1 == key2)\r
+ hash = key1 * 31;\r
+ else\r
+ hash = ((int)(key1 ^ key2)) * 31;\r
+ return hash & 0x7fffffff;\r
+ }\r
+ /**\r
+ * After an insert, this hook is called to adjust the size/free\r
+ * values of the set and to perform rehashing if necessary.\r
+ */\r
+ protected final void postInsertHook(boolean usedFreeSlot) {\r
+ if (usedFreeSlot) {\r
+ freeSet(freeGet()-1);\r
+ }\r
+ // rehash whenever we exhaust the available space in the table\r
+ int size = sizeGet() + 1;\r
+ sizeSet(size);\r
+ int maxSize = maxInsertGet();\r
+ int capacity = capacityGet();\r
+ int free = freeGet();\r
+ if (size > maxSize || free == 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 = size > maxSize ? PrimeFinder.nextPrime(capacity << 1) : capacity;\r
+ rehash(newCapacity);\r
+ } \r
+ }\r
+ final private void rehash(int newCapacity) {\r
+ int oldCapacity = capacityGet();\r
+ int oldHashBase = hashBase;\r
+ int newTableCapacity = newCapacity*ENTRY_SIZE + HeaderSize;\r
+ int[] oldInts = createNewTable(newTableCapacity, newTableCapacity, 1);\r
+ ints = getTable();\r
+ hashBase = getTableBase() + HeaderSize;\r
+ capacitySet(newCapacity);\r
+ sizeSet(0);\r
+ freeSet(newCapacity);\r
+ computeMaxInsert(newCapacity);\r
+ computeMaxRemove(maxInsertGet());\r
+ for (int i = oldCapacity; i-- > 0;) {\r
+ int realIndex = oldHashBase + i*ENTRY_SIZE;\r
+ if (isFull(oldInts[realIndex+2])) {\r
+ int hashIndex = insertionIndex(oldInts[realIndex], oldInts[realIndex+1]);\r
+ assert(hashIndex >= 0);\r
+ int value = oldInts[realIndex+2];\r
+ assert(!isFree(value));\r
+ assert(!isRemoved(value));\r
+ setKeyAndValue(hashIndex, oldInts[realIndex], oldInts[realIndex+1], value);\r
+ }\r
+ }\r
+ }\r
+\r
+ @Override\r
+ public <Context> boolean foreach(int setIndex, Procedure procedure, Context context, ClusterSupport support, Modifier modifier) throws DatabaseException {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+}\r
Code Review / simantics / platform.git / blobdiff