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%2FIntHash2.java;fp=bundles%2Forg.simantics.db.procore%2Fsrc%2Forg%2Fsimantics%2Fdb%2Fprocore%2Fcluster%2FIntHash2.java;h=3d07e51546ff0b0c4aac52f57db831cc7feb33b5;hp=e47ac60c6c0b655cdb3a0e7377a6a40977e1604a;hb=0ae2b770234dfc3cbb18bd38f324125cf0faca07;hpb=24e2b34260f219f0d1644ca7a138894980e25b14 diff --git a/bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/IntHash2.java b/bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/IntHash2.java index e47ac60c6..3d07e5154 100644 --- a/bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/IntHash2.java +++ b/bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/IntHash2.java @@ -1,386 +1,386 @@ -/******************************************************************************* - * 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 gnu.trove.impl.PrimeFinder; - -import org.simantics.db.exception.DatabaseException; -import org.simantics.db.impl.ClusterI; -import org.simantics.db.impl.IntAllocatorI; -import org.simantics.db.impl.Modifier; - -final class IntHash2 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)*2 + HeaderSize; - } - public static int create(int[] keys, int[] vals, IntAllocatorI allocator) { - assert(keys.length > 0); - assert(keys.length == vals.length); - int desiredSize = keys.length; - int hashBase = create(desiredSize, allocator); - for (int i=0; i> 1, capacity); - return hashBase; - } - public static int add(int[] table, int hashBase, int key, int val, IntAllocatorI allocator) { - assert(isFull(key)); - int index = insertionIndex(table, hashBase, key); - if (index < 0) { - int realIndex = -index; - assert(table[realIndex] == key); - if (table[realIndex+1] == val) - return 0; // value not modified - table[realIndex+1] = val; - return hashBase; // value modified - } - int previousState = table[index]; - table[index] = key; - table[index+1] = val; - 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(); - table[index+1] = setFree(); - decUsedSize(table, hashBase); - return true; // yes, we removed something - } - return false; // not in set, nothing to remove - } - - public static int get(int[] table, int hashBase, int a) { - int index = index(table, hashBase, a); - if (index < 0) - return setFree(); - return table[index+1]; - } - - 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 = hashBase + capacity*2; i-- > hashBase;) { - set[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 boolean foreachInt(int[] table, int base - , ClusterI.PredicateProcedure 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*2 + base; - (count < size) && (i-- > base);) { - int v = table[i]; - int o = table[--i]; - if (isFull(o)) { - int key; - if (null != modifier) - key = modifier.execute(o); - else - key = o; - if (procedure.execute(context, key, v)) - 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*2 + HeaderSize) + HeaderSize; - int[] newtable = allocator.getTable(); - setUsedAndRealSize(newtable, newHashBase, oldSize, newCapacity); - setMaxAndFreeSize(newtable, newHashBase, newCapacity>>1, newCapacity - oldSize); - for (int i = oldCapacity*2 + oldHashBase; i-- > oldHashBase;) { - int v = oldTable[i]; - int o = oldTable[--i]; - if (isFull(o)) { - int index = insertionIndex(newtable, newHashBase, o); - newtable[index] = o; - newtable[index+1] = v; - } - } - 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*2; - - 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*2; - } 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*2; - - 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*2; - } 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*2; - } - 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. - } -} +/******************************************************************************* + * 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 gnu.trove.impl.PrimeFinder; + +import org.simantics.db.exception.DatabaseException; +import org.simantics.db.impl.ClusterI; +import org.simantics.db.impl.IntAllocatorI; +import org.simantics.db.impl.Modifier; + +final class IntHash2 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)*2 + HeaderSize; + } + public static int create(int[] keys, int[] vals, IntAllocatorI allocator) { + assert(keys.length > 0); + assert(keys.length == vals.length); + int desiredSize = keys.length; + int hashBase = create(desiredSize, allocator); + for (int i=0; i> 1, capacity); + return hashBase; + } + public static int add(int[] table, int hashBase, int key, int val, IntAllocatorI allocator) { + assert(isFull(key)); + int index = insertionIndex(table, hashBase, key); + if (index < 0) { + int realIndex = -index; + assert(table[realIndex] == key); + if (table[realIndex+1] == val) + return 0; // value not modified + table[realIndex+1] = val; + return hashBase; // value modified + } + int previousState = table[index]; + table[index] = key; + table[index+1] = val; + 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(); + table[index+1] = setFree(); + decUsedSize(table, hashBase); + return true; // yes, we removed something + } + return false; // not in set, nothing to remove + } + + public static int get(int[] table, int hashBase, int a) { + int index = index(table, hashBase, a); + if (index < 0) + return setFree(); + return table[index+1]; + } + + 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 = hashBase + capacity*2; i-- > hashBase;) { + set[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 boolean foreachInt(int[] table, int base + , ClusterI.PredicateProcedure 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*2 + base; + (count < size) && (i-- > base);) { + int v = table[i]; + int o = table[--i]; + if (isFull(o)) { + int key; + if (null != modifier) + key = modifier.execute(o); + else + key = o; + if (procedure.execute(context, key, v)) + 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*2 + HeaderSize) + HeaderSize; + int[] newtable = allocator.getTable(); + setUsedAndRealSize(newtable, newHashBase, oldSize, newCapacity); + setMaxAndFreeSize(newtable, newHashBase, newCapacity>>1, newCapacity - oldSize); + for (int i = oldCapacity*2 + oldHashBase; i-- > oldHashBase;) { + int v = oldTable[i]; + int o = oldTable[--i]; + if (isFull(o)) { + int index = insertionIndex(newtable, newHashBase, o); + newtable[index] = o; + newtable[index+1] = v; + } + } + 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*2; + + 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*2; + } 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*2; + + 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*2; + } 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*2; + } + 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. + } +}