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