bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/IntHash2.java

   1 /*******************************************************************************\r
   2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
   3  * in Industry THTH ry.\r
   4  * All rights reserved. This program and the accompanying materials\r
   5  * are made available under the terms of the Eclipse Public License v1.0\r
   6  * which accompanies this distribution, and is available at\r
   7  * http://www.eclipse.org/legal/epl-v10.html\r
   8  *\r
   9  * Contributors:\r
  10  *     VTT Technical Research Centre of Finland - initial API and implementation\r
  11  *******************************************************************************/\r
  12 package org.simantics.db.procore.cluster;\r
  13 \r
  14 import gnu.trove.impl.PrimeFinder;\r
  15 \r
  16 import org.simantics.db.exception.DatabaseException;\r
  17 import org.simantics.db.impl.ClusterI;\r
  18 import org.simantics.db.impl.IntAllocatorI;\r
  19 import org.simantics.db.impl.Modifier;\r
  20 \r
  21 final class IntHash2 extends IntHashTrait {\r
  22     static final int HeaderSize = 4;\r
  23     private static final int REAL_SIZE = -4; // Number of allocated slots.\r
  24     private static final int USED_SIZE = -3; // Number of used slots.\r
  25     private static final int FREE_SIZE = -2; // Number of free slots.\r
  26     private static final int MAX_SIZE = -1; // Max number of used slots.\r
  27 \r
  28     public static int getRealSize(int[] table, int hashBase) {\r
  29         return table[hashBase + REAL_SIZE];\r
  30     }\r
  31 \r
  32     private static void setRealSize(int[] table, int hashBase, int realSize) {\r
  33         assert(realSize > 0);\r
  34         table[hashBase + REAL_SIZE] = realSize;\r
  35     }\r
  36 \r
  37     public static int getUsedSize(int[] table, int hashBase) {\r
  38         return table[hashBase + USED_SIZE];\r
  39     }\r
  40 \r
  41     static void setUsedSize(int[] table, int hashBase, int usedSize) {\r
  42         assert(usedSize >= 0);\r
  43         table[hashBase + USED_SIZE] = usedSize;\r
  44     }\r
  45 \r
  46     // return value after decrement\r
  47     static int decUsedSize(int[] table, int hashBase) {\r
  48         table[hashBase + USED_SIZE] -= 1;\r
  49         return table[hashBase + USED_SIZE];\r
  50     }\r
  51 \r
  52     // return value after increment\r
  53     static int incUsedSize(int[] table, int hashBase) {\r
  54         table[hashBase + USED_SIZE] += 1;\r
  55         return table[hashBase + USED_SIZE];\r
  56     }\r
  57     static void setUsedAndRealSize(int[] table, int hashBase, int used, int real) {\r
  58         setUsedSize(table, hashBase, used);\r
  59         setRealSize(table, hashBase, real);\r
  60     }\r
  61     static int getFreeSize(int[] table, int hashBase) {\r
  62         return table[hashBase + FREE_SIZE];\r
  63     }\r
  64 \r
  65     static void setFreeSize(int[] table, int hashBase, int freeSize) {\r
  66         assert(freeSize >= 0);\r
  67         table[hashBase + FREE_SIZE] = freeSize;\r
  68     }\r
  69 \r
  70     static void decFreeSize(int[] table, int hashBase) {\r
  71         table[hashBase + FREE_SIZE] -= 1;\r
  72     }\r
  73     \r
  74     static int getMaxSize(int[] table, int hashBase) {\r
  75         return table[hashBase + MAX_SIZE];\r
  76     }\r
  77 \r
  78     static void setMaxSize(int[] table, int hashBase, int maxSize) {\r
  79         assert(maxSize > 0);\r
  80         table[hashBase + MAX_SIZE] = maxSize;\r
  81     }\r
  82     \r
  83     static void setMaxAndFreeSize(int[] table, int hashBase, int max, int free) {\r
  84         setMaxSize(table, hashBase, max);\r
  85         setFreeSize(table, hashBase, free);\r
  86     }\r
  87 \r
  88     public static int getAllocatedSize(int[] table, int hashBase) {\r
  89         return getRealSize(table, hashBase)*2 + HeaderSize;\r
  90     }\r
  91     public static int create(int[] keys, int[] vals, IntAllocatorI allocator) {\r
  92         assert(keys.length > 0);\r
  93         assert(keys.length == vals.length);\r
  94         int desiredSize = keys.length;\r
  95         int hashBase = create(desiredSize, allocator);\r
  96         for (int i=0; i<desiredSize; ++i)\r
  97             hashBase = add(allocator.getTable(), hashBase, keys[i], vals[i], allocator);\r
  98         return hashBase;\r
  99     }\r
 100     private static int create(int desiredSize, IntAllocatorI allocator) {\r
 101         int capacity = PrimeFinder.nextPrime((desiredSize << 1) + 1);\r
 102         int hashBase = allocator.allocate(capacity*2 + HeaderSize) + HeaderSize;\r
 103         int[] table = allocator.getTable();\r
 104         setUsedAndRealSize(table, hashBase, 0, capacity);\r
 105         setMaxAndFreeSize(table, hashBase, capacity >> 1, capacity);\r
 106         return hashBase;\r
 107     }\r
 108     public static int add(int[] table, int hashBase, int key, int val, IntAllocatorI allocator) {\r
 109         assert(isFull(key));\r
 110         int index = insertionIndex(table, hashBase, key);\r
 111         if (index < 0) {\r
 112             int realIndex = -index;\r
 113             assert(table[realIndex] == key);\r
 114             if (table[realIndex+1] == val)\r
 115                 return 0; // value not modified\r
 116             table[realIndex+1] = val;\r
 117             return hashBase; // value modified\r
 118         }\r
 119         int previousState = table[index];\r
 120         table[index] = key;\r
 121         table[index+1] = val;\r
 122         return postInsertHook(table, hashBase, isFree(previousState), allocator);\r
 123     }\r
 124 \r
 125     public static boolean remove(int[] table, int hashBase, int a) {\r
 126         int index = index(table, hashBase, a);\r
 127         if (index >= 0) {\r
 128             table[index] = setRemoved();\r
 129             table[index+1] = setFree();\r
 130             decUsedSize(table, hashBase);\r
 131             return true; // yes, we removed something\r
 132         }\r
 133         return false; // not in set, nothing to remove\r
 134     }\r
 135 \r
 136     public static int get(int[] table, int hashBase, int a) {\r
 137         int index = index(table, hashBase, a);\r
 138         if (index < 0)\r
 139             return setFree();\r
 140         return table[index+1];\r
 141     }\r
 142 \r
 143     public static boolean contains(int[] table, int hashBase, int a) {\r
 144         return index(table, hashBase, a) >= 0;\r
 145     }\r
 146 \r
 147     public static boolean isEmpty(int[] table, int hashBase) {\r
 148         return 0 == getUsedSize(table, hashBase);\r
 149     }\r
 150 \r
 151     public static void clear(int[] table, int hashBase) {\r
 152         int[] set = table;\r
 153         int free = setFree();\r
 154         int capacity = getRealSize(table, hashBase);\r
 155         for (int i = hashBase + capacity*2; i-- > hashBase;) {\r
 156             set[i] = free;\r
 157         }\r
 158         setUsedSize(table, hashBase, 0);\r
 159         setFreeSize(table, hashBase, capacity);\r
 160     }\r
 161     \r
 162     /**\r
 163      * Ensure that this hashtable has sufficient capacity to hold\r
 164      * <tt>desiredCapacity<tt> <b>additional</b> elements without\r
 165      * requiring a rehash.  This is a tuning method you can call\r
 166      * before doing a large insert.\r
 167      *\r
 168      * @param desiredSize an <code>int</code> value\r
 169      */\r
 170     public static boolean ensureSize(int[] table, int hashBase, int desiredSize, IntAllocatorI allocator) {\r
 171         int size = getUsedSize(table, hashBase);\r
 172         if (desiredSize > (getMaxSize(table, hashBase) - size)) {\r
 173             int newCapacity = ((desiredSize + size) << 1) + 1;\r
 174             rehash(table, hashBase, PrimeFinder.nextPrime(newCapacity), allocator);\r
 175             return true;\r
 176         }\r
 177         return false;\r
 178     }\r
 179 \r
 180     /**\r
 181      * Compresses the hashtable to the minimum prime size (as defined by\r
 182      * PrimeFinder) that will hold all of the elements currently in the table.\r
 183      * If you have done a lot of <tt>remove</tt> operations and plan to do a\r
 184      * lot of queries or insertions or iteration, it is a good idea to invoke\r
 185      * this method. Doing so will accomplish two things:\r
 186      * \r
 187      * <ol>\r
 188      * <li> You'll free memory allocated to the table but no longer needed\r
 189      * because of the remove()s.</li>\r
 190      * \r
 191      * <li> You'll get better query/insert/iterator performance because there\r
 192      * won't be any <tt>REMOVED</tt> slots to skip over when probing for\r
 193      * indices in the table.</li>\r
 194      * </ol>\r
 195      */\r
 196     public static void compact(int[] table, int hashBase, IntAllocatorI allocator) {\r
 197         // need at least one free spot for open addressing\r
 198         rehash(table, hashBase, PrimeFinder.nextPrime((getUsedSize(table, hashBase) << 1) + 1), allocator);\r
 199     }\r
 200 \r
 201     static <Context> boolean foreachInt(int[] table, int base\r
 202                 , ClusterI.PredicateProcedure<Context> procedure, Context context, Modifier modifier) throws DatabaseException {\r
 203         int capacity = getRealSize(table, base);\r
 204         final int size = getUsedSize(table, base);\r
 205         int count = 0;\r
 206         for (int i = capacity*2 + base;\r
 207             (count < size) && (i-- > base);) {\r
 208             int v = table[i];\r
 209             int o = table[--i];\r
 210             if (isFull(o)) {\r
 211                 int key;\r
 212                 if (null != modifier)\r
 213                         key = modifier.execute(o);\r
 214                 else\r
 215                         key = o;\r
 216                     if (procedure.execute(context, key, v))\r
 217                         return true; // loop was broken by procedure\r
 218                 if (size == ++count)\r
 219                         return false; // loop finished\r
 220             }\r
 221         }\r
 222         assert(size == count);\r
 223         return false; // loop finished\r
 224     }\r
 225 \r
 226     /**\r
 227      * Expands the set to accomodate new values.\r
 228      * \r
 229      * @param newCapacity\r
 230      *            an <code>int</code> value\r
 231      */\r
 232     private static final int rehash(int[] oldTable, int oldHashBase, int newCapacity,\r
 233             IntAllocatorI allocator) {\r
 234         assert(PrimeFinder.nextPrime(newCapacity) == newCapacity);\r
 235         int oldCapacity = getRealSize(oldTable, oldHashBase);\r
 236         int oldSize = getUsedSize(oldTable, oldHashBase);\r
 237         // new hash base is initialized to freeSet()\r
 238         int newHashBase = allocator.allocate(newCapacity*2 + HeaderSize) + HeaderSize;\r
 239         int[] newtable = allocator.getTable();\r
 240         setUsedAndRealSize(newtable, newHashBase, oldSize, newCapacity);\r
 241         setMaxAndFreeSize(newtable, newHashBase, newCapacity>>1, newCapacity - oldSize);\r
 242         for (int i = oldCapacity*2 + oldHashBase; i-- > oldHashBase;) {\r
 243             int v = oldTable[i];\r
 244             int o = oldTable[--i];\r
 245             if (isFull(o)) {\r
 246                 int index = insertionIndex(newtable, newHashBase, o);\r
 247                 newtable[index] = o;\r
 248                 newtable[index+1] = v;\r
 249             }\r
 250         }\r
 251         return newHashBase;\r
 252     }\r
 253 \r
 254     /**\r
 255      * After an insert, this hook is called to adjust the size/free values of\r
 256      * the set and to perform rehashing if necessary.\r
 257      */\r
 258     private static final int postInsertHook(int[] table, int hashBase,\r
 259             boolean usedFreeSlot, IntAllocatorI allocator) {\r
 260         if (usedFreeSlot) {\r
 261             decFreeSize(table, hashBase);\r
 262         }\r
 263 \r
 264         // rehash whenever we exhaust the available space in the table\r
 265         if (incUsedSize(table, hashBase) > getMaxSize(table, hashBase)\r
 266                 || getFreeSize(table, hashBase) == 0) {\r
 267             // choose a new capacity suited to the new state of the table\r
 268             // if we've grown beyond our maximum size, double capacity;\r
 269             // if we've exhausted the free spots, rehash to the same capacity,\r
 270             // which will free up any stale removed slots for reuse.\r
 271             int newCapacity = getUsedSize(table, hashBase) > getMaxSize(table,\r
 272                     hashBase) ? PrimeFinder.nextPrime(getRealSize(table,\r
 273                     hashBase) << 1) : getRealSize(table, hashBase);\r
 274             return rehash(table, hashBase, newCapacity, allocator);\r
 275         }\r
 276         return hashBase;\r
 277     }\r
 278 \r
 279     /**\r
 280      * Locates the index of <tt>val</tt>.\r
 281      * \r
 282      * @param val\r
 283      *            an <code>int</code> value\r
 284      * @return the index of <tt>val</tt> or -1 if it isn't in the set.\r
 285      */\r
 286     private static int index(int[] table, int hashBase, int a) {\r
 287         int hash, probe, index, length, hashIndex;\r
 288         int[] set = table;\r
 289         length = getRealSize(table, hashBase);\r
 290         hash = computeHashCode(a);\r
 291         index = hash % length;\r
 292         hashIndex = hashBase + index*2;\r
 293 \r
 294         if (!isFree(set[hashIndex])\r
 295                 && (isRemoved(set[hashIndex]) || set[hashIndex] != a)) {\r
 296             // see Knuth, p. 529\r
 297             probe = 1 + (hash % (length - 2));\r
 298 \r
 299             do {\r
 300                 index -= probe;\r
 301                 if (index < 0) {\r
 302                     index += length;\r
 303                 }\r
 304                 hashIndex = hashBase + index*2;\r
 305             } while (!isFree(set[hashIndex])\r
 306                     && (isRemoved(set[hashIndex]) || set[hashIndex] != a));\r
 307         }\r
 308 \r
 309         return isFree(set[hashIndex]) ? -1  : hashIndex;\r
 310     }\r
 311 \r
 312     /**\r
 313      * Locates the index at which <tt>val</tt> can be inserted. if there is\r
 314      * already a value equal()ing <tt>val</tt> in the set, returns that value\r
 315      * as a negative integer.\r
 316      * \r
 317      * @param val\r
 318      *            an <code>int</code> value\r
 319      * @return an <code>int</code> value\r
 320      */\r
 321     private static final int insertionIndex(int[] table, int hashBase, int a) {\r
 322         int hash, probe, index, length, hashIndex;\r
 323         int[] set = table;\r
 324         length = getRealSize(table, hashBase);\r
 325         hash = computeHashCode(a);\r
 326         index = hash % length;\r
 327         assert(0 != hashBase);\r
 328         hashIndex = hashBase + index*2;\r
 329         \r
 330         if (isFree(set[hashIndex])) {\r
 331             return hashIndex; // empty, all done\r
 332         } else if (isFull(set[hashIndex]) && set[hashIndex] == a) {\r
 333             return -hashIndex; // already stored\r
 334         } else { // already FULL or REMOVED, must probe\r
 335             // compute the double hash\r
 336             probe = 1 + (hash % (length - 2));\r
 337 \r
 338             // if the slot we landed on is FULL (but not removed), probe\r
 339             // until we find an empty slot, a REMOVED slot, or an element\r
 340             // equal to the one we are trying to insert.\r
 341             // finding an empty slot means that the value is not present\r
 342             // and that we should use that slot as the insertion point;\r
 343             // finding a REMOVED slot means that we need to keep searching,\r
 344             // however we want to remember the offset of that REMOVED slot\r
 345             // so we can reuse it in case a "new" insertion (i.e. not an update)\r
 346             // is possible.\r
 347             // finding a matching value means that we've found that our desired\r
 348             // key is already in the table\r
 349 \r
 350             if (!isRemoved(set[hashIndex])) {\r
 351                 // starting at the natural offset, probe until we find an\r
 352                 // offset that isn't full.\r
 353                 do {\r
 354                     index -= probe;\r
 355                     if (index < 0) {\r
 356                         index += length;\r
 357                     }\r
 358                     hashIndex = hashBase + index*2;\r
 359                 } while (isFull(set[hashIndex]) && set[hashIndex] != a);\r
 360             }\r
 361 \r
 362             // if the index we found was removed: continue probing until we\r
 363             // locate a free location or an element which equal()s the\r
 364             // one we have.\r
 365             if (isRemoved(set[hashIndex])) {\r
 366                 int firstRemoved = hashIndex;\r
 367                 while (!isFree(set[hashIndex])\r
 368                         && (isRemoved(set[hashIndex]) || set[hashIndex] != a)) {\r
 369                     index -= probe;\r
 370                     if (index < 0) {\r
 371                         index += length;\r
 372                     }\r
 373                     hashIndex = hashBase + index*2;\r
 374                 }\r
 375                 return isFull(set[hashIndex]) ? -hashIndex : firstRemoved;\r
 376             }\r
 377             // if it's full, the key is already stored\r
 378             return isFull(set[hashIndex]) ? -hashIndex : hashIndex;\r
 379         }\r
 380     }\r
 381 \r
 382     private static final int computeHashCode(int aKey) {\r
 383         int hash = aKey * 31;\r
 384         return hash & 0x7fffffff; // Top bit reserved.\r
 385     }\r
 386 }\r