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%2FIntHash.java;fp=bundles%2Forg.simantics.db.procore%2Fsrc%2Forg%2Fsimantics%2Fdb%2Fprocore%2Fcluster%2FIntHash.java;h=c50b517713484f418183efa73be8f7e9665f0e09;hp=0000000000000000000000000000000000000000;hb=969bd23cab98a79ca9101af33334000879fb60c5;hpb=866dba5cd5a3929bbeae85991796acb212338a08 diff --git a/bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/IntHash.java b/bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/IntHash.java new file mode 100644 index 000000000..c50b51771 --- /dev/null +++ b/bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/IntHash.java @@ -0,0 +1,531 @@ +/******************************************************************************* + * 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> 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 + * desiredCapacity additional elements without + * requiring a rehash. This is a tuning method you can call + * before doing a large insert. + * + * @param desiredSize an int 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 remove 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: + * + *
    + *
  1. You'll free memory allocated to the table but no longer needed + * because of the remove()s.
    2. + * + *
  2. You'll get better query/insert/iterator performance because there + * won't be any REMOVED slots to skip over when probing for + * indices in the table.
    3. + *
+ */ + 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 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 void foreachInt(final ReadGraphImpl graph, int[] table, int base, C context, final AsyncContextMultiProcedure 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); +// 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 boolean foreachInt(int[] table, int base + , ClusterI.ObjectProcedure 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 int 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 val. + * + * @param val + * an int value + * @return the index of val 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 val can be inserted. if there is + * already a value equal()ing val in the set, returns that value + * as a negative integer. + * + * @param val + * an int value + * @return an int 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. + } +}