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 gnu.trove.impl.PrimeFinder;
16 import org.simantics.db.exception.DatabaseException;
17 import org.simantics.db.impl.ClusterI;
18 import org.simantics.db.impl.IntAllocatorI;
19 import org.simantics.db.impl.Modifier;
21 final class IntHash2 extends IntHashTrait {
22 static final int HeaderSize = 4;
23 private static final int REAL_SIZE = -4; // Number of allocated slots.
24 private static final int USED_SIZE = -3; // Number of used slots.
25 private static final int FREE_SIZE = -2; // Number of free slots.
26 private static final int MAX_SIZE = -1; // Max number of used slots.
28 public static int getRealSize(int[] table, int hashBase) {
29 return table[hashBase + REAL_SIZE];
32 private static void setRealSize(int[] table, int hashBase, int realSize) {
34 table[hashBase + REAL_SIZE] = realSize;
37 public static int getUsedSize(int[] table, int hashBase) {
38 return table[hashBase + USED_SIZE];
41 static void setUsedSize(int[] table, int hashBase, int usedSize) {
42 assert(usedSize >= 0);
43 table[hashBase + USED_SIZE] = usedSize;
46 // return value after decrement
47 static int decUsedSize(int[] table, int hashBase) {
48 table[hashBase + USED_SIZE] -= 1;
49 return table[hashBase + USED_SIZE];
52 // return value after increment
53 static int incUsedSize(int[] table, int hashBase) {
54 table[hashBase + USED_SIZE] += 1;
55 return table[hashBase + USED_SIZE];
57 static void setUsedAndRealSize(int[] table, int hashBase, int used, int real) {
58 setUsedSize(table, hashBase, used);
59 setRealSize(table, hashBase, real);
61 static int getFreeSize(int[] table, int hashBase) {
62 return table[hashBase + FREE_SIZE];
65 static void setFreeSize(int[] table, int hashBase, int freeSize) {
66 assert(freeSize >= 0);
67 table[hashBase + FREE_SIZE] = freeSize;
70 static void decFreeSize(int[] table, int hashBase) {
71 table[hashBase + FREE_SIZE] -= 1;
74 static int getMaxSize(int[] table, int hashBase) {
75 return table[hashBase + MAX_SIZE];
78 static void setMaxSize(int[] table, int hashBase, int maxSize) {
80 table[hashBase + MAX_SIZE] = maxSize;
83 static void setMaxAndFreeSize(int[] table, int hashBase, int max, int free) {
84 setMaxSize(table, hashBase, max);
85 setFreeSize(table, hashBase, free);
88 public static int getAllocatedSize(int[] table, int hashBase) {
89 return getRealSize(table, hashBase)*2 + HeaderSize;
91 public static int create(int[] keys, int[] vals, IntAllocatorI allocator) {
92 assert(keys.length > 0);
93 assert(keys.length == vals.length);
94 int desiredSize = keys.length;
95 int hashBase = create(desiredSize, allocator);
96 for (int i=0; i<desiredSize; ++i)
97 hashBase = add(allocator.getTable(), hashBase, keys[i], vals[i], allocator);
100 private static int create(int desiredSize, IntAllocatorI allocator) {
101 int capacity = PrimeFinder.nextPrime((desiredSize << 1) + 1);
102 int hashBase = allocator.allocate(capacity*2 + HeaderSize) + HeaderSize;
103 int[] table = allocator.getTable();
104 setUsedAndRealSize(table, hashBase, 0, capacity);
105 setMaxAndFreeSize(table, hashBase, capacity >> 1, capacity);
108 public static int add(int[] table, int hashBase, int key, int val, IntAllocatorI allocator) {
110 int index = insertionIndex(table, hashBase, key);
112 int realIndex = -index;
113 assert(table[realIndex] == key);
114 if (table[realIndex+1] == val)
115 return 0; // value not modified
116 table[realIndex+1] = val;
117 return hashBase; // value modified
119 int previousState = table[index];
121 table[index+1] = val;
122 return postInsertHook(table, hashBase, isFree(previousState), allocator);
125 public static boolean remove(int[] table, int hashBase, int a) {
126 int index = index(table, hashBase, a);
128 table[index] = setRemoved();
129 table[index+1] = setFree();
130 decUsedSize(table, hashBase);
131 return true; // yes, we removed something
133 return false; // not in set, nothing to remove
136 public static int get(int[] table, int hashBase, int a) {
137 int index = index(table, hashBase, a);
140 return table[index+1];
143 public static boolean contains(int[] table, int hashBase, int a) {
144 return index(table, hashBase, a) >= 0;
147 public static boolean isEmpty(int[] table, int hashBase) {
148 return 0 == getUsedSize(table, hashBase);
151 public static void clear(int[] table, int hashBase) {
153 int free = setFree();
154 int capacity = getRealSize(table, hashBase);
155 for (int i = hashBase + capacity*2; i-- > hashBase;) {
158 setUsedSize(table, hashBase, 0);
159 setFreeSize(table, hashBase, capacity);
163 * Ensure that this hashtable has sufficient capacity to hold
164 * <tt>desiredCapacity<tt> <b>additional</b> elements without
165 * requiring a rehash. This is a tuning method you can call
166 * before doing a large insert.
168 * @param desiredSize an <code>int</code> value
170 public static boolean ensureSize(int[] table, int hashBase, int desiredSize, IntAllocatorI allocator) {
171 int size = getUsedSize(table, hashBase);
172 if (desiredSize > (getMaxSize(table, hashBase) - size)) {
173 int newCapacity = ((desiredSize + size) << 1) + 1;
174 rehash(table, hashBase, PrimeFinder.nextPrime(newCapacity), allocator);
181 * Compresses the hashtable to the minimum prime size (as defined by
182 * PrimeFinder) that will hold all of the elements currently in the table.
183 * If you have done a lot of <tt>remove</tt> operations and plan to do a
184 * lot of queries or insertions or iteration, it is a good idea to invoke
185 * this method. Doing so will accomplish two things:
188 * <li> You'll free memory allocated to the table but no longer needed
189 * because of the remove()s.</li>
191 * <li> You'll get better query/insert/iterator performance because there
192 * won't be any <tt>REMOVED</tt> slots to skip over when probing for
193 * indices in the table.</li>
196 public static void compact(int[] table, int hashBase, IntAllocatorI allocator) {
197 // need at least one free spot for open addressing
198 rehash(table, hashBase, PrimeFinder.nextPrime((getUsedSize(table, hashBase) << 1) + 1), allocator);
201 static <Context> boolean foreachInt(int[] table, int base
202 , ClusterI.PredicateProcedure<Context> procedure, Context context, Modifier modifier) throws DatabaseException {
203 int capacity = getRealSize(table, base);
204 final int size = getUsedSize(table, base);
206 for (int i = capacity*2 + base;
207 (count < size) && (i-- > base);) {
212 if (null != modifier)
213 key = modifier.execute(o);
216 if (procedure.execute(context, key, v))
217 return true; // loop was broken by procedure
219 return false; // loop finished
222 assert(size == count);
223 return false; // loop finished
227 * Expands the set to accomodate new values.
230 * an <code>int</code> value
232 private static final int rehash(int[] oldTable, int oldHashBase, int newCapacity,
233 IntAllocatorI allocator) {
234 assert(PrimeFinder.nextPrime(newCapacity) == newCapacity);
235 int oldCapacity = getRealSize(oldTable, oldHashBase);
236 int oldSize = getUsedSize(oldTable, oldHashBase);
237 // new hash base is initialized to freeSet()
238 int newHashBase = allocator.allocate(newCapacity*2 + HeaderSize) + HeaderSize;
239 int[] newtable = allocator.getTable();
240 setUsedAndRealSize(newtable, newHashBase, oldSize, newCapacity);
241 setMaxAndFreeSize(newtable, newHashBase, newCapacity>>1, newCapacity - oldSize);
242 for (int i = oldCapacity*2 + oldHashBase; i-- > oldHashBase;) {
244 int o = oldTable[--i];
246 int index = insertionIndex(newtable, newHashBase, o);
248 newtable[index+1] = v;
255 * After an insert, this hook is called to adjust the size/free values of
256 * the set and to perform rehashing if necessary.
258 private static final int postInsertHook(int[] table, int hashBase,
259 boolean usedFreeSlot, IntAllocatorI allocator) {
261 decFreeSize(table, hashBase);
264 // rehash whenever we exhaust the available space in the table
265 if (incUsedSize(table, hashBase) > getMaxSize(table, hashBase)
266 || getFreeSize(table, hashBase) == 0) {
267 // choose a new capacity suited to the new state of the table
268 // if we've grown beyond our maximum size, double capacity;
269 // if we've exhausted the free spots, rehash to the same capacity,
270 // which will free up any stale removed slots for reuse.
271 int newCapacity = getUsedSize(table, hashBase) > getMaxSize(table,
272 hashBase) ? PrimeFinder.nextPrime(getRealSize(table,
273 hashBase) << 1) : getRealSize(table, hashBase);
274 return rehash(table, hashBase, newCapacity, allocator);
280 * Locates the index of <tt>val</tt>.
283 * an <code>int</code> value
284 * @return the index of <tt>val</tt> or -1 if it isn't in the set.
286 private static int index(int[] table, int hashBase, int a) {
287 int hash, probe, index, length, hashIndex;
289 length = getRealSize(table, hashBase);
290 hash = computeHashCode(a);
291 index = hash % length;
292 hashIndex = hashBase + index*2;
294 if (!isFree(set[hashIndex])
295 && (isRemoved(set[hashIndex]) || set[hashIndex] != a)) {
297 probe = 1 + (hash % (length - 2));
304 hashIndex = hashBase + index*2;
305 } while (!isFree(set[hashIndex])
306 && (isRemoved(set[hashIndex]) || set[hashIndex] != a));
309 return isFree(set[hashIndex]) ? -1 : hashIndex;
313 * Locates the index at which <tt>val</tt> can be inserted. if there is
314 * already a value equal()ing <tt>val</tt> in the set, returns that value
315 * as a negative integer.
318 * an <code>int</code> value
319 * @return an <code>int</code> value
321 private static final int insertionIndex(int[] table, int hashBase, int a) {
322 int hash, probe, index, length, hashIndex;
324 length = getRealSize(table, hashBase);
325 hash = computeHashCode(a);
326 index = hash % length;
327 assert(0 != hashBase);
328 hashIndex = hashBase + index*2;
330 if (isFree(set[hashIndex])) {
331 return hashIndex; // empty, all done
332 } else if (isFull(set[hashIndex]) && set[hashIndex] == a) {
333 return -hashIndex; // already stored
334 } else { // already FULL or REMOVED, must probe
335 // compute the double hash
336 probe = 1 + (hash % (length - 2));
338 // if the slot we landed on is FULL (but not removed), probe
339 // until we find an empty slot, a REMOVED slot, or an element
340 // equal to the one we are trying to insert.
341 // finding an empty slot means that the value is not present
342 // and that we should use that slot as the insertion point;
343 // finding a REMOVED slot means that we need to keep searching,
344 // however we want to remember the offset of that REMOVED slot
345 // so we can reuse it in case a "new" insertion (i.e. not an update)
347 // finding a matching value means that we've found that our desired
348 // key is already in the table
350 if (!isRemoved(set[hashIndex])) {
351 // starting at the natural offset, probe until we find an
352 // offset that isn't full.
358 hashIndex = hashBase + index*2;
359 } while (isFull(set[hashIndex]) && set[hashIndex] != a);
362 // if the index we found was removed: continue probing until we
363 // locate a free location or an element which equal()s the
365 if (isRemoved(set[hashIndex])) {
366 int firstRemoved = hashIndex;
367 while (!isFree(set[hashIndex])
368 && (isRemoved(set[hashIndex]) || set[hashIndex] != a)) {
373 hashIndex = hashBase + index*2;
375 return isFull(set[hashIndex]) ? -hashIndex : firstRemoved;
377 // if it's full, the key is already stored
378 return isFull(set[hashIndex]) ? -hashIndex : hashIndex;
382 private static final int computeHashCode(int aKey) {
383 int hash = aKey * 31;
384 return hash & 0x7fffffff; // Top bit reserved.