1 /*******************************************************************************
2 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
10 * VTT Technical Research Centre of Finland - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.db.procore.cluster;
14 import org.simantics.db.Resource;
15 import org.simantics.db.exception.DatabaseException;
16 import org.simantics.db.impl.ClusterI;
17 import org.simantics.db.impl.IntAllocatorI;
18 import org.simantics.db.impl.Modifier;
19 import org.simantics.db.impl.ResourceImpl;
20 import org.simantics.db.impl.graph.ReadGraphImpl;
21 import org.simantics.db.procedure.AsyncContextMultiProcedure;
22 import org.simantics.db.procedure.AsyncMultiProcedure;
24 import gnu.trove.impl.PrimeFinder;
26 public class IntHash extends IntHashTrait {
27 static final int HeaderSize = 4;
28 private static final int REAL_SIZE = -4; // Number of allocated slots.
29 private static final int USED_SIZE = -3; // Number of used slots.
30 private static final int FREE_SIZE = -2; // Number of free slots.
31 private static final int MAX_SIZE = -1; // Max number of used slots.
33 public static int getRealSize(int[] table, int hashBase) {
34 return table[hashBase + REAL_SIZE];
37 private static void setRealSize(int[] table, int hashBase, int realSize) {
39 table[hashBase + REAL_SIZE] = realSize;
42 public static int getUsedSize(int[] table, int hashBase) {
43 return table[hashBase + USED_SIZE];
46 static void setUsedSize(int[] table, int hashBase, int usedSize) {
47 assert(usedSize >= 0);
48 table[hashBase + USED_SIZE] = usedSize;
51 // return value after decrement
52 static int decUsedSize(int[] table, int hashBase) {
53 table[hashBase + USED_SIZE] -= 1;
54 return table[hashBase + USED_SIZE];
57 // return value after increment
58 static int incUsedSize(int[] table, int hashBase) {
59 table[hashBase + USED_SIZE] += 1;
60 return table[hashBase + USED_SIZE];
62 static void setUsedAndRealSize(int[] table, int hashBase, int used, int real) {
63 setUsedSize(table, hashBase, used);
64 setRealSize(table, hashBase, real);
66 static int getFreeSize(int[] table, int hashBase) {
67 return table[hashBase + FREE_SIZE];
70 static void setFreeSize(int[] table, int hashBase, int freeSize) {
71 assert(freeSize >= 0);
72 table[hashBase + FREE_SIZE] = freeSize;
75 static void decFreeSize(int[] table, int hashBase) {
76 table[hashBase + FREE_SIZE] -= 1;
79 static int getMaxSize(int[] table, int hashBase) {
80 return table[hashBase + MAX_SIZE];
83 static void setMaxSize(int[] table, int hashBase, int maxSize) {
85 table[hashBase + MAX_SIZE] = maxSize;
88 static void setMaxAndFreeSize(int[] table, int hashBase, int max, int free) {
89 setMaxSize(table, hashBase, max);
90 setFreeSize(table, hashBase, free);
93 public static int getAllocatedSize(int[] table, int hashBase) {
94 return getRealSize(table, hashBase) + HeaderSize;
96 public static int create(int[] ints, IntAllocatorI allocator) {
97 assert(ints.length > 0);
98 int desiredSize = ints.length;
99 int hashBase = create(desiredSize, allocator);
100 for (int i=0; i<desiredSize; ++i)
101 hashBase = add(allocator.getTable(), hashBase, ints[i], allocator);
104 public static int create(int desiredSize, IntAllocatorI allocator) {
105 int capacity = PrimeFinder.nextPrime((desiredSize << 1) + 1);
106 int hashBase = allocator.allocate(capacity + HeaderSize) + HeaderSize;
107 int[] table = allocator.getTable();
108 setUsedAndRealSize(table, hashBase, 0, capacity);
109 setMaxAndFreeSize(table, hashBase, capacity >> 1, capacity);
113 public static int add(int[] table, int hashBase, int a, IntAllocatorI allocator) {
114 int index = insertionIndex(table, hashBase, a);
116 return 0; // already present in set, nothing to add
117 int previousState = table[index];
120 return postInsertHook(table, hashBase, isFree(previousState), allocator);
123 public static boolean remove(int[] table, int hashBase, int a) {
124 int index = index(table, hashBase, a);
126 table[index] = setRemoved();
127 decUsedSize(table, hashBase);
128 return true; // yes, we removed something
130 return false; // not in set, nothing to remove
133 public static int removeLast(int[] table, int hashBase)
134 throws DatabaseException {
135 final int size = getUsedSize(table, hashBase);
137 throw new DatabaseException("Illegal call of IntHash.removeLast.");
138 int capacity = getRealSize(table, hashBase);
140 for (int i = capacity + hashBase;
141 (count < size) && (i-- > hashBase);) {
144 table[i] = setRemoved();
145 decUsedSize(table, hashBase);
149 throw new DatabaseException("IntHash.removeLast call failed.");
152 public static boolean contains(int[] table, int hashBase, int a) {
153 return index(table, hashBase, a) >= 0;
156 public static boolean isEmpty(int[] table, int hashBase) {
157 return 0 == getUsedSize(table, hashBase);
160 public static void clear(int[] table, int hashBase) {
162 int free = setFree();
163 int capacity = getRealSize(table, hashBase);
164 for (int i = capacity; i-- > 0;) {
165 set[hashBase + i] = free;
167 setUsedSize(table, hashBase, 0);
168 setFreeSize(table, hashBase, capacity);
172 * Ensure that this hashtable has sufficient capacity to hold
173 * <tt>desiredCapacity<tt> <b>additional</b> elements without
174 * requiring a rehash. This is a tuning method you can call
175 * before doing a large insert.
177 * @param desiredSize an <code>int</code> value
179 public static boolean ensureSize(int[] table, int hashBase, int desiredSize, IntAllocatorI allocator) {
180 int size = getUsedSize(table, hashBase);
181 if (desiredSize > (getMaxSize(table, hashBase) - size)) {
182 int newCapacity = ((desiredSize + size) << 1) + 1;
183 rehash(table, hashBase, PrimeFinder.nextPrime(newCapacity), allocator);
190 * Compresses the hashtable to the minimum prime size (as defined by
191 * PrimeFinder) that will hold all of the elements currently in the table.
192 * If you have done a lot of <tt>remove</tt> operations and plan to do a
193 * lot of queries or insertions or iteration, it is a good idea to invoke
194 * this method. Doing so will accomplish two things:
197 * <li> You'll free memory allocated to the table but no longer needed
198 * because of the remove()s.</li>
200 * <li> You'll get better query/insert/iterator performance because there
201 * won't be any <tt>REMOVED</tt> slots to skip over when probing for
202 * indices in the table.</li>
205 public static void compact(int[] table, int hashBase, IntAllocatorI allocator) {
206 // need at least one free spot for open addressing
207 rehash(table, hashBase, PrimeFinder.nextPrime((getUsedSize(table, hashBase) << 1) + 1), allocator);
211 static void foreachInt(final ReadGraphImpl graph, int[] table, int base, final AsyncMultiProcedure<Resource> procedure, Modifier modifier) throws DatabaseException {
213 int capacity = getRealSize(table, base);
214 final int size = getUsedSize(table, base);
215 // final int threadMask = graph.state.threadMask;
217 // int callerThread = graph.callerThread;
220 // AtomicInteger ready = null;
222 for (int i = capacity + base;
223 (count < size) && (i-- > base);) {
227 final int actual = modifier.execute(o);
229 // int suggestSchedule = (actual>>16) & threadMask;
230 // if(callerThread == suggestSchedule) {
232 procedure.execute(graph, new ResourceImpl(graph.getResourceSupport(), actual));
237 // if(ready == null) ready = new AtomicInteger(1);
238 // ready.incrementAndGet();
239 // final AtomicInteger r = ready;
241 // graph.state.barrier.inc();
242 // graph.processor.processor.schedule(callerThread, new SessionTask(suggestSchedule) {
245 // public void run(int thread) {
247 // procedure.execute(graph.newAsync(thread), new ResourceImpl(null, actual));
248 // if(r.decrementAndGet() == 0) {
249 // procedure.finished(graph);
251 // graph.state.barrier.dec();
259 // procedure.execute(graph, new ResourceImpl(null, modifier.execute(o)));
261 //// if (size == ++count) {
262 // if(ready == null) {
263 // procedure.finished(graph);
265 // if(ready.decrementAndGet() == 0) {
266 // procedure.finished(graph);
276 // Execution was not deferred
277 // if(ready == null) {
278 procedure.finished(graph);
280 // if(ready.decrementAndGet() == 0) {
281 // procedure.finished(graph);
285 assert(size == count);
288 static <C> void foreachInt(final ReadGraphImpl graph, int[] table, int base, C context, final AsyncContextMultiProcedure<C, Resource> procedure, Modifier modifier) throws DatabaseException {
290 int capacity = getRealSize(table, base);
291 final int size = getUsedSize(table, base);
295 for (int i = capacity + base;
296 (count < size) && (i-- > base);) {
300 final int actual = modifier.execute(o);
301 procedure.execute(graph, context, new ResourceImpl(graph.getResourceSupport(), actual));
307 procedure.finished(graph, context);
309 assert(size == count);
313 static int getSingleInt(int[] table, int base, Modifier modifier) throws DatabaseException {
315 int capacity = getRealSize(table, base);
316 final int size = getUsedSize(table, base);
318 for (int i = capacity + base;
319 (count < size) && (i-- > base);) {
323 if (null != modifier)
324 value = modifier.execute(o);
328 if(result == 0) result = value;
331 if (size == ++count) break;
335 assert(size == count);
338 // if(result == -1) return 0;
339 // else return result;
343 static <Context> boolean foreachInt(int[] table, int base
344 , ClusterI.ObjectProcedure<Context> procedure, Context context, Modifier modifier) throws DatabaseException {
345 int capacity = getRealSize(table, base);
346 final int size = getUsedSize(table, base);
348 for (int i = capacity + base;
349 (count < size) && (i-- > base);) {
353 if (null != modifier)
354 value = modifier.execute(o);
357 if (procedure.execute(context, value))
358 return true; // loop was broken by procedure
360 return false; // loop finished
363 assert(size == count);
364 return false; // loop finished
368 * Expands the set to accomodate new values.
371 * an <code>int</code> value
373 private static final int rehash(int[] oldtable, int oldHashBase, int newCapacity,
374 IntAllocatorI allocator) {
375 assert(PrimeFinder.nextPrime(newCapacity) == newCapacity);
376 int oldCapacity = getRealSize(oldtable, oldHashBase);
377 int oldSize = getUsedSize(oldtable, oldHashBase);
378 // new hash base is initialized to freeSet()
379 int newHashBase = allocator.allocate(newCapacity + HeaderSize) + HeaderSize;
380 int[] newtable = allocator.getTable();
382 setUsedAndRealSize(newtable, newHashBase, oldSize, newCapacity);
383 setMaxAndFreeSize(newtable, newHashBase, newCapacity>>1, newCapacity - oldSize);
385 for (int i = oldCapacity + oldHashBase; i-- > oldHashBase;) {
388 int index = insertionIndex(newtable, newHashBase, o);
396 * After an insert, this hook is called to adjust the size/free values of
397 * the set and to perform rehashing if necessary.
399 private static final int postInsertHook(int[] table, int hashBase,
400 boolean usedFreeSlot, IntAllocatorI allocator) {
402 decFreeSize(table, hashBase);
405 // rehash whenever we exhaust the available space in the table
406 if (incUsedSize(table, hashBase) > getMaxSize(table, hashBase)
407 || getFreeSize(table, hashBase) == 0) {
408 // choose a new capacity suited to the new state of the table
409 // if we've grown beyond our maximum size, double capacity;
410 // if we've exhausted the free spots, rehash to the same capacity,
411 // which will free up any stale removed slots for reuse.
412 int newCapacity = getUsedSize(table, hashBase) > getMaxSize(table,
413 hashBase) ? PrimeFinder.nextPrime(getRealSize(table,
414 hashBase) << 1) : getRealSize(table, hashBase);
415 return rehash(table, hashBase, newCapacity, allocator);
421 * Locates the index of <tt>val</tt>.
424 * an <code>int</code> value
425 * @return the index of <tt>val</tt> or -1 if it isn't in the set.
427 private static int index(int[] table, int hashBase, int a) {
428 int hash, probe, index, length, hashIndex;
430 length = getRealSize(table, hashBase);
431 hash = computeHashCode(a);
432 index = hash % length;
433 hashIndex = hashBase + index;
435 if (!isFree(set[hashIndex])
436 && (isRemoved(set[hashIndex]) || set[hashIndex] != a)) {
438 probe = 1 + (hash % (length - 2));
445 hashIndex = hashBase + index;
446 } while (!isFree(set[hashIndex])
447 && (isRemoved(set[hashIndex]) || set[hashIndex] != a));
450 return isFree(set[hashIndex]) ? -1 : hashIndex;
454 * Locates the index at which <tt>val</tt> can be inserted. if there is
455 * already a value equal()ing <tt>val</tt> in the set, returns that value
456 * as a negative integer.
459 * an <code>int</code> value
460 * @return an <code>int</code> value
462 private static final int insertionIndex(int[] table, int hashBase, int a) {
463 int hash, probe, index, length, hashIndex;
465 length = getRealSize(table, hashBase);
466 hash = computeHashCode(a);
467 index = hash % length;
468 assert(0 != hashBase);
469 hashIndex = hashBase + index;
471 // int used = getUsedSize(table, hashBase);
472 // int max = getMaxSize(table, hashBase);
473 // assert(used > max);
475 if (isFree(set[hashIndex])) {
476 return hashIndex; // empty, all done
477 } else if (isFull(set[hashIndex]) && set[hashIndex] == a) {
478 return -hashIndex; // already stored
479 } else { // already FULL or REMOVED, must probe
480 // compute the double hash
481 probe = 1 + (hash % (length - 2));
483 // if the slot we landed on is FULL (but not removed), probe
484 // until we find an empty slot, a REMOVED slot, or an element
485 // equal to the one we are trying to insert.
486 // finding an empty slot means that the value is not present
487 // and that we should use that slot as the insertion point;
488 // finding a REMOVED slot means that we need to keep searching,
489 // however we want to remember the offset of that REMOVED slot
490 // so we can reuse it in case a "new" insertion (i.e. not an update)
492 // finding a matching value means that we've found that our desired
493 // key is already in the table
495 if (!isRemoved(set[hashIndex])) {
496 // starting at the natural offset, probe until we find an
497 // offset that isn't full.
503 hashIndex = hashBase + index;
504 } while (isFull(set[hashIndex]) && set[hashIndex] != a);
507 // if the index we found was removed: continue probing until we
508 // locate a free location or an element which equal()s the
510 if (isRemoved(set[hashIndex])) {
511 int firstRemoved = hashIndex;
512 while (!isFree(set[hashIndex])
513 && (isRemoved(set[hashIndex]) || set[hashIndex] != a)) {
518 hashIndex = hashBase + index;
520 return isFull(set[hashIndex]) ? -hashIndex : firstRemoved;
522 // if it's full, the key is already stored
523 return isFull(set[hashIndex]) ? -hashIndex : hashIndex;
527 private static final int computeHashCode(int aKey) {
528 int hash = aKey * 31;
529 return hash & 0x7fffffff; // Top bit reserved.