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 public class LongHash {
17 static final int HeaderSize = 2;
18 static private final int UsedAndRealSize = -2; // Number of allocated slots.
19 static private final int MaxAndFreeSize = -1; // Number of used slots.
20 static private final int MinRealSize = 3;
21 static private final int MinRealSizeMinusOne = MinRealSize - 1;
22 private static final long FREE = 0;
23 private static final long REMOVED = -1;
25 static final boolean isFree(long a) {
29 static final boolean isFull(long a) {
33 static final boolean isRemoved(long a) {
37 static final long setFree() {
41 static final long setFull(long a) {
45 static final long setRemoved() {
49 static public int getRealSize(long[] longs, int hashBase) {
50 long desc = longs[hashBase + UsedAndRealSize];
52 int realSize = (int)desc & 0x7FFFFFFF;
53 assert (realSize > MinRealSizeMinusOne);
57 // private static void setRealSize(long[] longs, int hashBase, int realSize) {
58 // assert (realSize > MinRealSizeMinusOne);
59 // long desc = longs[hashBase + UsedAndRealSize];
61 // assert((int)desc < 0);
62 // desc = (desc & 0xFFFFFFFF80000000L) | realSize;
63 // longs[hashBase + UsedAndRealSize] = desc;
66 private static void setUsedAndRealSize(long[] longs, int hashBase, int usedSize, int realSize) {
67 assert(usedSize >= 0);
68 assert(realSize > MinRealSizeMinusOne);
69 int index = hashBase + UsedAndRealSize;
70 long desc = longs[index];
71 assert(desc <= 0); // memory is initialized to zero
72 desc = (long)usedSize << 32 | realSize | 0x8000000080000000L;
76 public static int getUsedSize(long[] longs, int hashBase) {
77 long desc = longs[hashBase + UsedAndRealSize];
79 assert((int)desc < 0);
80 return (int)(desc >> 32) & 0x7FFFFFFF;
83 static void setUsedSize(long[] longs, int hashBase, int usedSize) {
84 assert (usedSize >= 0);
85 int index = hashBase + UsedAndRealSize;
86 long desc = longs[index];
88 assert((int)desc < 0);
89 desc = (desc & 0x80000000FFFFFFFFL) | (long)usedSize << 32;
93 // return value after decrement
94 static int decUsedSize(long[] longs, int hashBase) {
95 int index = hashBase + UsedAndRealSize;
96 long desc = longs[index];
98 int usedSize = ((int)(desc >> 32) & 0x7FFFFFFF) - 1;
99 assert(usedSize >= 0);
100 desc = (desc & 0x80000000FFFFFFFFL) | (long)usedSize << 32;
105 // return value after increment
106 static int incUsedSize(long[] longs, int hashBase) {
107 int index = hashBase + UsedAndRealSize;
108 long desc = longs[index];
110 int usedSize = ((int)(desc >> 32) & 0x7FFFFFFF) + 1;
111 assert(usedSize > 0);
112 desc = (desc & 0x80000000FFFFFFFFL) | (long)usedSize << 32;
117 static int getFreeSize(long[] longs, int hashBase) {
118 long desc = longs[hashBase + MaxAndFreeSize];
120 int freeSize = (int)desc;
121 assert (freeSize >= 0);
125 static void setFreeSize(long[] longs, int hashBase, int freeSize) {
126 assert (freeSize >= 0);
127 long desc = longs[hashBase + MaxAndFreeSize];
129 assert((int)desc >= 0);
130 desc = (desc & 0xFFFFFFFF00000000L) | freeSize;
131 longs[hashBase + MaxAndFreeSize] = desc;
134 static void decFreeSize(long[] longs, int hashBase) {
135 long desc = longs[hashBase + MaxAndFreeSize];
137 int freeSize = (int)desc;
138 assert(freeSize > 0);
139 desc = (desc & 0xFFFFFFFF00000000L) | --freeSize;
140 longs[hashBase + MaxAndFreeSize] = desc;
143 private static void setMaxAndFreeSize(long[] longs, int hashBase, int maxSize, int freeSize) {
144 assert (maxSize > 0);
145 assert (freeSize >= 0);
146 int index = hashBase + MaxAndFreeSize;
147 long desc = longs[index];
148 assert(desc >= 0); // memory is initialized to zero
149 desc = ((long)maxSize << 32) | freeSize;
153 static int getMaxSize(long[] longs, int hashBase) {
154 long desc = longs[hashBase + MaxAndFreeSize];
156 assert((int)desc >= 0);
157 return (int)(desc >> 32);
160 static void setMaxSize(long[] longs, int hashBase, int maxSize) {
161 assert (maxSize > 0);
162 int index = hashBase + MaxAndFreeSize;
163 long desc = longs[index];
165 assert((int)desc >= 0);
166 desc = (desc & 0x00000000FFFFFFFFL) | (long)maxSize << 32;
170 public static boolean add(AllocatorI allocator, long a) {
171 long[] longs = allocator.getLongs();
172 int hashBase = allocator.getHashBase();
173 int index = insertionIndex(longs, hashBase, a);
175 return false; // already present in set, nothing to add
176 long previousState = longs[index];
177 assert(LongHash.isFull(a));
179 postInsertHook(longs, hashBase, LongHash.isFree(previousState), allocator);
180 return true; // yes, we added something
183 public static boolean remove(long[] longs, int hashBase, long a) {
184 int index = LongHash.index(longs, hashBase, a);
186 longs[index] = setRemoved();
187 decUsedSize(longs, hashBase);
193 public static boolean contains(long[] longs, int hashBase,long a) {
194 return index(longs, hashBase, a) >= 0;
197 public static boolean isEmpty(long[] longs, int hashBase) {
198 return 0 == getUsedSize(longs, hashBase);
201 public static void clear(long[] longs, int hashBase) {
203 long free = setFree();
204 int capacity = getRealSize(longs, hashBase);
205 for (int i = capacity; i-- > 0;) {
206 set[hashBase + i] = free;
208 setUsedSize(longs, hashBase, 0);
209 setFreeSize(longs, hashBase, capacity);
213 * Ensure that this hashtable has sufficient capacity to hold
214 * <tt>desiredCapacity<tt> <b>additional</b> elements without
215 * requiring a rehash. This is a tuning method you can call
216 * before doing a large insert.
218 * @param desiredSize an <code>int</code> value
220 public static boolean ensureSize(AllocatorI allocator, int desiredSize) {
221 long[] longs = allocator.getLongs();
222 int hashBase = allocator.getHashBase();
223 int size = getUsedSize(longs, hashBase);
224 if (desiredSize > (getMaxSize(longs, hashBase) - size)) {
225 int newCapacity = ((desiredSize + size) << 1) + 1;
226 rehash(longs, hashBase, PrimeFinder.nextPrime(newCapacity), allocator);
233 * Compresses the hashtable to the minimum prime size (as defined by
234 * PrimeFinder) that will hold all of the elements currently in the table.
235 * If you have done a lot of <tt>remove</tt> operations and plan to do a
236 * lot of queries or insertions or iteration, it is a good idea to invoke
237 * this method. Doing so will accomplish two things:
240 * <li> You'll free memory allocated to the table but no longer needed
241 * because of the remove()s.</li>
243 * <li> You'll get better query/insert/iterator performance because there
244 * won't be any <tt>REMOVED</tt> slots to skip over when probing for
245 * indices in the table.</li>
248 public static void compact(AllocatorI allocator) {
249 long[] longs = allocator.getLongs();
250 int hashBase = allocator.getHashBase();
251 // need at least one free spot for open addressing
252 rehash(longs, hashBase, PrimeFinder.nextPrime((getUsedSize(longs, hashBase) << 1) + 1), allocator);
255 public static int setUp(AllocatorI allocator, int initialCapacity) {
256 int capacity = PrimeFinder.nextPrime(initialCapacity << 1);
257 int hashBase = allocator.allocate(capacity);
258 assert(hashBase == allocator.getHashBase());
259 long[] longs = allocator.getLongs();
260 setUsedAndRealSize(longs, hashBase, 0, capacity);
261 setMaxAndFreeSize(longs, hashBase, capacity >> 1, capacity);
266 * Expands the set to accomodate new values.
269 * an <code>int</code> value
271 static final void rehash(long[] oldLongs, int oldHashBase, int newCapacity,
272 AllocatorI allocator) {
273 assert(PrimeFinder.nextPrime(newCapacity) == newCapacity);
274 int oldCapacity = getRealSize(oldLongs, oldHashBase);
275 int oldSize = getUsedSize(oldLongs, oldHashBase);
276 // new hash base is initialized to LongHash.freeSet()
277 int newHashBase = allocator.allocate(newCapacity);
278 long[] newLongs = allocator.getLongs();
279 setUsedAndRealSize(newLongs, newHashBase, oldSize, newCapacity);
280 setMaxAndFreeSize(newLongs, newHashBase, newCapacity>>1, newCapacity - oldSize);
282 for (int i = oldCapacity + oldHashBase; i-- > oldHashBase;) {
283 long o = oldLongs[i];
285 int index = insertionIndex(newLongs, newHashBase, o);
292 * After an insert, this hook is called to adjust the size/free values of
293 * the set and to perform rehashing if necessary.
295 protected static final void postInsertHook(long[] longs, int hashBase,
296 boolean usedFreeSlot, AllocatorI allocator) {
298 decFreeSize(longs, hashBase);
301 // rehash whenever we exhaust the available space in the table
302 if (incUsedSize(longs, hashBase) > getMaxSize(longs, hashBase)
303 || getFreeSize(longs, hashBase) == 0) {
304 // choose a new capacity suited to the new state of the table
305 // if we've grown beyond our maximum size, double capacity;
306 // if we've exhausted the free spots, rehash to the same capacity,
307 // which will free up any stale removed slots for reuse.
308 int newCapacity = getUsedSize(longs, hashBase) > getMaxSize(longs,
309 hashBase) ? PrimeFinder.nextPrime(getRealSize(longs,
310 hashBase) << 1) : getRealSize(longs, hashBase);
311 rehash(longs, hashBase, newCapacity, allocator);
316 * Locates the index of <tt>val</tt>.
319 * an <code>long</code> value
320 * @return the index of <tt>val</tt> or -1 if it isn't in the set.
322 static int index(long[] longs, int hashBase, long a) {
323 int hash, probe, index, length, hashIndex;
325 length = getRealSize(longs, hashBase);
326 hash = computeHashCode(a);
327 index = hash % length;
328 hashIndex = hashBase + index;
330 if (!LongHash.isFree(set[hashIndex])
331 && (LongHash.isRemoved(set[hashIndex]) || set[hashIndex] != a)) {
333 probe = 1 + (hash % (length - 2));
340 hashIndex = hashBase + index;
341 } while (!LongHash.isFree(set[hashIndex])
342 && (LongHash.isRemoved(set[hashIndex]) || set[hashIndex] != a));
345 return LongHash.isFree(set[hashIndex]) ? -1 : hashIndex;
349 * Locates the index at which <tt>val</tt> can be inserted. if there is
350 * already a value equal()ing <tt>val</tt> in the set, returns that value
351 * as a negative integer.
354 * an <code>long</code> value
355 * @return an <code>int</code> value
357 static final int insertionIndex(long[] longs, int hashBase, long a) {
358 int hash, probe, index, length, hashIndex;
360 length = getRealSize(longs, hashBase);
361 hash = computeHashCode(a);
362 index = hash % length;
363 assert(0 != hashBase);
364 hashIndex = hashBase + index;
366 if (LongHash.isFree(set[hashIndex])) {
367 return hashIndex; // empty, all done
368 } else if (LongHash.isFull(set[hashIndex]) && set[hashIndex] == a) {
369 return -hashIndex; // already stored
370 } else { // already FULL or REMOVED, must probe
371 // compute the double hash
372 probe = 1 + (hash % (length - 2));
374 // if the slot we landed on is FULL (but not removed), probe
375 // until we find an empty slot, a REMOVED slot, or an element
376 // equal to the one we are trying to insert.
377 // finding an empty slot means that the value is not present
378 // and that we should use that slot as the insertion point;
379 // finding a REMOVED slot means that we need to keep searching,
380 // however we want to remember the offset of that REMOVED slot
381 // so we can reuse it in case a "new" insertion (i.e. not an update)
383 // finding a matching value means that we've found that our desired
384 // key is already in the table
386 if (!LongHash.isRemoved(set[hashIndex])) {
387 // starting at the natural offset, probe until we find an
388 // offset that isn't full.
394 hashIndex = hashBase + index;
395 } while (LongHash.isFull(set[hashIndex]) && set[hashIndex] != a);
398 // if the index we found was removed: continue probing until we
399 // locate a free location or an element which equal()s the
401 if (LongHash.isRemoved(set[hashIndex])) {
402 int firstRemoved = hashIndex;
403 while (!LongHash.isFree(set[hashIndex])
404 && (LongHash.isRemoved(set[hashIndex]) || set[hashIndex] != a)) {
409 hashIndex = hashBase + index;
411 return LongHash.isFull(set[hashIndex]) ? -hashIndex : firstRemoved;
413 // if it's full, the key is already stored
414 return LongHash.isFull(set[hashIndex]) ? -hashIndex : hashIndex;
418 static final int computeHashCode(long aKey) {
419 int hash = ((int) (aKey ^ (aKey >> 32))) * 31;
420 return hash & 0x7fffffff; // Top bit reserved.
423 interface AllocatorI {
424 int allocate(int size); // return base address of hash table, allocates also hash header
425 long[] getLongs(); // return base address of allocator memory
426 int getHashBase(); // return base address of hash table
431 private long[] longs;
432 private int hashBase;
435 private int size; // number of elements in the set
436 private final LongHash.AllocatorI allocator;
438 public LongIterator(LongHash.AllocatorI allocator) {
439 this.allocator = allocator;
445 public void reset() {
447 LongHash.getUsedSize(longs, hashBase) != this.size ||
448 longs != allocator.getLongs() ||
449 hashBase != allocator.getHashBase()) {
450 this.longs = allocator.getLongs();
451 this.hashBase = allocator.getHashBase();
452 this.size = LongHash.getUsedSize(longs, hashBase);
454 this.index = LongHash.getRealSize(longs, hashBase);
457 if (moveToNextIndex())
458 return longs[hashBase + index];
459 return LongHash.setFree();
461 protected final boolean moveToNextIndex() {
462 // doing the assignment && < 0 in one line saves 3 opcodes...
463 if ((index = nextIndex()) < 0) {
468 protected final int nextIndex() {
469 long[] states = longs;
471 while (i-- > 0 && (!LongHash.isFull(states[hashBase + i])))
475 public boolean hasNext() {
476 return nextIndex() >= 0;