/******************************************************************************* * 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, 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 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. } }