bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/IntHash.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 org.simantics.db.Resource;\r
  15 import org.simantics.db.exception.DatabaseException;\r
  16 import org.simantics.db.impl.ClusterI;\r
  17 import org.simantics.db.impl.IntAllocatorI;\r
  18 import org.simantics.db.impl.Modifier;\r
  19 import org.simantics.db.impl.ResourceImpl;\r
  20 import org.simantics.db.impl.graph.ReadGraphImpl;\r
  21 import org.simantics.db.procedure.AsyncContextMultiProcedure;\r
  22 import org.simantics.db.procedure.AsyncMultiProcedure;\r
  23 \r
  24 import gnu.trove.impl.PrimeFinder;\r
  25 \r
  26 public class IntHash extends IntHashTrait {\r
  27     static final int HeaderSize = 4;\r
  28     private static final int REAL_SIZE = -4; // Number of allocated slots.\r
  29     private static final int USED_SIZE = -3; // Number of used slots.\r
  30     private static final int FREE_SIZE = -2; // Number of free slots.\r
  31     private static final int MAX_SIZE = -1; // Max number of used slots.\r
  32 \r
  33     public static int getRealSize(int[] table, int hashBase) {\r
  34         return table[hashBase + REAL_SIZE];\r
  35     }\r
  36 \r
  37     private static void setRealSize(int[] table, int hashBase, int realSize) {\r
  38         assert(realSize > 0);\r
  39         table[hashBase + REAL_SIZE] = realSize;\r
  40     }\r
  41 \r
  42     public static int getUsedSize(int[] table, int hashBase) {\r
  43         return table[hashBase + USED_SIZE];\r
  44     }\r
  45 \r
  46     static void setUsedSize(int[] table, int hashBase, int usedSize) {\r
  47         assert(usedSize >= 0);\r
  48         table[hashBase + USED_SIZE] = usedSize;\r
  49     }\r
  50 \r
  51     // return value after decrement\r
  52     static int decUsedSize(int[] table, int hashBase) {\r
  53         table[hashBase + USED_SIZE] -= 1;\r
  54         return table[hashBase + USED_SIZE];\r
  55     }\r
  56 \r
  57     // return value after increment\r
  58     static int incUsedSize(int[] table, int hashBase) {\r
  59         table[hashBase + USED_SIZE] += 1;\r
  60         return table[hashBase + USED_SIZE];\r
  61     }\r
  62     static void setUsedAndRealSize(int[] table, int hashBase, int used, int real) {\r
  63         setUsedSize(table, hashBase, used);\r
  64         setRealSize(table, hashBase, real);\r
  65     }\r
  66     static int getFreeSize(int[] table, int hashBase) {\r
  67         return table[hashBase + FREE_SIZE];\r
  68     }\r
  69 \r
  70     static void setFreeSize(int[] table, int hashBase, int freeSize) {\r
  71         assert(freeSize >= 0);\r
  72         table[hashBase + FREE_SIZE] = freeSize;\r
  73     }\r
  74 \r
  75     static void decFreeSize(int[] table, int hashBase) {\r
  76         table[hashBase + FREE_SIZE] -= 1;\r
  77     }\r
  78     \r
  79     static int getMaxSize(int[] table, int hashBase) {\r
  80         return table[hashBase + MAX_SIZE];\r
  81     }\r
  82 \r
  83     static void setMaxSize(int[] table, int hashBase, int maxSize) {\r
  84         assert(maxSize > 0);\r
  85         table[hashBase + MAX_SIZE] = maxSize;\r
  86     }\r
  87     \r
  88     static void setMaxAndFreeSize(int[] table, int hashBase, int max, int free) {\r
  89         setMaxSize(table, hashBase, max);\r
  90         setFreeSize(table, hashBase, free);\r
  91     }\r
  92 \r
  93     public static int getAllocatedSize(int[] table, int hashBase) {\r
  94         return getRealSize(table, hashBase) + HeaderSize;\r
  95     }\r
  96     public static int create(int[] ints, IntAllocatorI allocator) {\r
  97         assert(ints.length > 0);\r
  98         int desiredSize = ints.length;\r
  99         int hashBase = create(desiredSize, allocator);\r
 100         for (int i=0; i<desiredSize; ++i)\r
 101             hashBase = add(allocator.getTable(), hashBase, ints[i], allocator);\r
 102         return hashBase;\r
 103     }\r
 104     public static int create(int desiredSize, IntAllocatorI allocator) {\r
 105         int capacity = PrimeFinder.nextPrime((desiredSize << 1) + 1);\r
 106         int hashBase = allocator.allocate(capacity + HeaderSize) + HeaderSize;\r
 107         int[] table = allocator.getTable();\r
 108         setUsedAndRealSize(table, hashBase, 0, capacity);\r
 109         setMaxAndFreeSize(table, hashBase, capacity >> 1, capacity);\r
 110         return hashBase;\r
 111     }\r
 112 \r
 113     public static int add(int[] table, int hashBase, int a, IntAllocatorI allocator) {\r
 114         int index = insertionIndex(table, hashBase, a);\r
 115         if (index < 0)\r
 116             return 0; // already present in set, nothing to add\r
 117         int previousState = table[index];\r
 118         assert(isFull(a));\r
 119         table[index] = a;\r
 120         return postInsertHook(table, hashBase, isFree(previousState), allocator);\r
 121     }\r
 122 \r
 123     public static boolean remove(int[] table, int hashBase, int a) {\r
 124         int index = index(table, hashBase, a);\r
 125         if (index >= 0) {\r
 126             table[index] = setRemoved();\r
 127             decUsedSize(table, hashBase);\r
 128             return true; // yes, we removed something\r
 129         }\r
 130         return false; // not in set, nothing to remove\r
 131     }\r
 132 \r
 133     public static int removeLast(int[] table, int hashBase)\r
 134     throws DatabaseException {\r
 135         final int size = getUsedSize(table, hashBase);\r
 136         if (size != 1)\r
 137             throw new DatabaseException("Illegal call of IntHash.removeLast.");\r
 138         int capacity = getRealSize(table, hashBase);\r
 139         int count = 0;\r
 140         for (int i = capacity + hashBase;\r
 141             (count < size) && (i-- > hashBase);) {\r
 142             int o = table[i];\r
 143             if (isFull(o)) {\r
 144                 table[i] = setRemoved();\r
 145                 decUsedSize(table, hashBase);\r
 146                 return o;\r
 147             }\r
 148         }\r
 149         throw new DatabaseException("IntHash.removeLast call failed.");\r
 150     }\r
 151 \r
 152     public static boolean contains(int[] table, int hashBase, int a) {\r
 153         return index(table, hashBase, a) >= 0;\r
 154     }\r
 155 \r
 156     public static boolean isEmpty(int[] table, int hashBase) {\r
 157         return 0 == getUsedSize(table, hashBase);\r
 158     }\r
 159 \r
 160     public static void clear(int[] table, int hashBase) {\r
 161         int[] set = table;\r
 162         int free = setFree();\r
 163         int capacity = getRealSize(table, hashBase);\r
 164         for (int i = capacity; i-- > 0;) {\r
 165             set[hashBase + i] = free;\r
 166         }\r
 167         setUsedSize(table, hashBase, 0);\r
 168         setFreeSize(table, hashBase, capacity);\r
 169     }\r
 170     \r
 171     /**\r
 172      * Ensure that this hashtable has sufficient capacity to hold\r
 173      * <tt>desiredCapacity<tt> <b>additional</b> elements without\r
 174      * requiring a rehash.  This is a tuning method you can call\r
 175      * before doing a large insert.\r
 176      *\r
 177      * @param desiredSize an <code>int</code> value\r
 178      */\r
 179     public static boolean ensureSize(int[] table, int hashBase, int desiredSize, IntAllocatorI allocator) {\r
 180         int size = getUsedSize(table, hashBase);\r
 181         if (desiredSize > (getMaxSize(table, hashBase) - size)) {\r
 182             int newCapacity = ((desiredSize + size) << 1) + 1;\r
 183             rehash(table, hashBase, PrimeFinder.nextPrime(newCapacity), allocator);\r
 184             return true;\r
 185         }\r
 186         return false;\r
 187     }\r
 188 \r
 189     /**\r
 190      * Compresses the hashtable to the minimum prime size (as defined by\r
 191      * PrimeFinder) that will hold all of the elements currently in the table.\r
 192      * If you have done a lot of <tt>remove</tt> operations and plan to do a\r
 193      * lot of queries or insertions or iteration, it is a good idea to invoke\r
 194      * this method. Doing so will accomplish two things:\r
 195      * \r
 196      * <ol>\r
 197      * <li> You'll free memory allocated to the table but no longer needed\r
 198      * because of the remove()s.</li>\r
 199      * \r
 200      * <li> You'll get better query/insert/iterator performance because there\r
 201      * won't be any <tt>REMOVED</tt> slots to skip over when probing for\r
 202      * indices in the table.</li>\r
 203      * </ol>\r
 204      */\r
 205     public static void compact(int[] table, int hashBase, IntAllocatorI allocator) {\r
 206         // need at least one free spot for open addressing\r
 207         rehash(table, hashBase, PrimeFinder.nextPrime((getUsedSize(table, hashBase) << 1) + 1), allocator);\r
 208     }\r
 209 \r
 210     \r
 211     static void foreachInt(final ReadGraphImpl graph, int[] table, int base, final AsyncMultiProcedure<Resource> procedure, Modifier modifier) throws DatabaseException {\r
 212 \r
 213         int capacity = getRealSize(table, base);\r
 214         final int size = getUsedSize(table, base);\r
 215 //        final int threadMask = graph.state.threadMask;\r
 216 //\r
 217 //        int callerThread = graph.callerThread;\r
 218         \r
 219         int count = 0;\r
 220 //        AtomicInteger ready = null;\r
 221         \r
 222         for (int i = capacity + base;\r
 223             (count < size) && (i-- > base);) {\r
 224             int o = table[i];\r
 225             if (isFull(o)) {\r
 226 \r
 227                 final int actual = modifier.execute(o);\r
 228                 \r
 229 //              int suggestSchedule = (actual>>16) & threadMask;\r
 230 //                if(callerThread == suggestSchedule) {\r
 231                         \r
 232                         procedure.execute(graph, new ResourceImpl(graph.getResourceSupport(), actual));\r
 233                         count++;\r
 234                         \r
 235 //                } else {\r
 236 //\r
 237 //                      if(ready == null) ready = new AtomicInteger(1);\r
 238 //                      ready.incrementAndGet();\r
 239 //                      final AtomicInteger r = ready;\r
 240 //                      \r
 241 //                      graph.state.barrier.inc();\r
 242 //                      graph.processor.processor.schedule(callerThread, new SessionTask(suggestSchedule) {\r
 243 //              \r
 244 //                              @Override\r
 245 //                              public void run(int thread) {\r
 246 //                                      \r
 247 //                              procedure.execute(graph.newAsync(thread), new ResourceImpl(null, actual));\r
 248 //                              if(r.decrementAndGet() == 0) {\r
 249 //                                      procedure.finished(graph);\r
 250 //                              }\r
 251 //                              graph.state.barrier.dec();\r
 252 //                              \r
 253 //                              }\r
 254 //              \r
 255 //                      });\r
 256 //                      \r
 257 //                }\r
 258 \r
 259 //                  procedure.execute(graph, new ResourceImpl(null, modifier.execute(o)));\r
 260                 \r
 261 ////                    if (size == ++count) {\r
 262 //                    if(ready == null) {\r
 263 //                              procedure.finished(graph);\r
 264 //                    } else {\r
 265 //                      if(ready.decrementAndGet() == 0) {\r
 266 //                              procedure.finished(graph);\r
 267 //                      }\r
 268 //                    }\r
 269 //                      graph.dec();\r
 270 //                      return;\r
 271 ////                    }\r
 272                 \r
 273             }\r
 274             \r
 275         }\r
 276         // Execution was not deferred\r
 277 //        if(ready == null) {\r
 278                 procedure.finished(graph);\r
 279 //        } else {\r
 280 //              if(ready.decrementAndGet() == 0) {\r
 281 //                      procedure.finished(graph);\r
 282 //              }\r
 283 //        }\r
 284 //              graph.dec();\r
 285         assert(size == count);\r
 286     }\r
 287 \r
 288     static <C> void foreachInt(final ReadGraphImpl graph, int[] table, int base, C context, final AsyncContextMultiProcedure<C, Resource> procedure, Modifier modifier) throws DatabaseException {\r
 289 \r
 290         int capacity = getRealSize(table, base);\r
 291         final int size = getUsedSize(table, base);\r
 292 \r
 293         int count = 0;\r
 294 \r
 295         for (int i = capacity + base;\r
 296         (count < size) && (i-- > base);) {\r
 297                 int o = table[i];\r
 298                 if (isFull(o)) {\r
 299 \r
 300                         final int actual = modifier.execute(o);\r
 301                         procedure.execute(graph, context, new ResourceImpl(graph.getResourceSupport(), actual));\r
 302                         count++;\r
 303                 }\r
 304 \r
 305         }\r
 306         \r
 307         procedure.finished(graph);\r
 308 //      graph.dec();\r
 309         assert(size == count);\r
 310         \r
 311     }\r
 312     \r
 313     static int getSingleInt(int[] table, int base, Modifier modifier) throws DatabaseException {\r
 314         int result = 0;\r
 315         int capacity = getRealSize(table, base);\r
 316         final int size = getUsedSize(table, base);\r
 317         int count = 0;\r
 318         for (int i = capacity + base;\r
 319             (count < size) && (i-- > base);) {\r
 320             int o = table[i];\r
 321             if (isFull(o)) {\r
 322                 int value;\r
 323                 if (null != modifier)\r
 324                         value = modifier.execute(o);\r
 325                 else\r
 326                         value = o;\r
 327                 \r
 328                 if(result == 0) result = value;\r
 329                 else result = -1;\r
 330                 \r
 331                 if (size == ++count) break;\r
 332                 \r
 333             }\r
 334         }\r
 335         assert(size == count);\r
 336         \r
 337         return result;\r
 338 //        if(result == -1) return 0;\r
 339 //        else return result;\r
 340         \r
 341     }\r
 342     \r
 343     static <Context> boolean foreachInt(int[] table, int base\r
 344                 , ClusterI.ObjectProcedure<Context> procedure, Context context, Modifier modifier) throws DatabaseException {\r
 345         int capacity = getRealSize(table, base);\r
 346         final int size = getUsedSize(table, base);\r
 347         int count = 0;\r
 348         for (int i = capacity + base;\r
 349             (count < size) && (i-- > base);) {\r
 350             int o = table[i];\r
 351             if (isFull(o)) {\r
 352                 int value;\r
 353                 if (null != modifier)\r
 354                         value = modifier.execute(o);\r
 355                 else\r
 356                         value = o;\r
 357                     if (procedure.execute(context, value))\r
 358                         return true; // loop was broken by procedure\r
 359                 if (size == ++count)\r
 360                         return false; // loop finished\r
 361             }\r
 362         }\r
 363         assert(size == count);\r
 364         return false; // loop finished\r
 365     }\r
 366 \r
 367     /**\r
 368      * Expands the set to accomodate new values.\r
 369      * \r
 370      * @param newCapacity\r
 371      *            an <code>int</code> value\r
 372      */\r
 373     private static final int rehash(int[] oldtable, int oldHashBase, int newCapacity,\r
 374             IntAllocatorI allocator) {\r
 375         assert(PrimeFinder.nextPrime(newCapacity) == newCapacity);\r
 376         int oldCapacity = getRealSize(oldtable, oldHashBase);\r
 377         int oldSize = getUsedSize(oldtable, oldHashBase);\r
 378         // new hash base is initialized to freeSet()\r
 379         int newHashBase = allocator.allocate(newCapacity + HeaderSize) + HeaderSize;\r
 380         int[] newtable = allocator.getTable();\r
 381         \r
 382         setUsedAndRealSize(newtable, newHashBase, oldSize, newCapacity);\r
 383         setMaxAndFreeSize(newtable, newHashBase, newCapacity>>1, newCapacity - oldSize);\r
 384         \r
 385         for (int i = oldCapacity + oldHashBase; i-- > oldHashBase;) {\r
 386             int o = oldtable[i];\r
 387             if (isFull(o)) {\r
 388                 int index = insertionIndex(newtable, newHashBase, o);\r
 389                 newtable[index] = o;\r
 390             }\r
 391         }\r
 392         return newHashBase;\r
 393     }\r
 394 \r
 395     /**\r
 396      * After an insert, this hook is called to adjust the size/free values of\r
 397      * the set and to perform rehashing if necessary.\r
 398      */\r
 399     private static final int postInsertHook(int[] table, int hashBase,\r
 400             boolean usedFreeSlot, IntAllocatorI allocator) {\r
 401         if (usedFreeSlot) {\r
 402             decFreeSize(table, hashBase);\r
 403         }\r
 404 \r
 405         // rehash whenever we exhaust the available space in the table\r
 406         if (incUsedSize(table, hashBase) > getMaxSize(table, hashBase)\r
 407                 || getFreeSize(table, hashBase) == 0) {\r
 408             // choose a new capacity suited to the new state of the table\r
 409             // if we've grown beyond our maximum size, double capacity;\r
 410             // if we've exhausted the free spots, rehash to the same capacity,\r
 411             // which will free up any stale removed slots for reuse.\r
 412             int newCapacity = getUsedSize(table, hashBase) > getMaxSize(table,\r
 413                     hashBase) ? PrimeFinder.nextPrime(getRealSize(table,\r
 414                     hashBase) << 1) : getRealSize(table, hashBase);\r
 415             return rehash(table, hashBase, newCapacity, allocator);\r
 416         }\r
 417         return hashBase;\r
 418     }\r
 419 \r
 420     /**\r
 421      * Locates the index of <tt>val</tt>.\r
 422      * \r
 423      * @param val\r
 424      *            an <code>int</code> value\r
 425      * @return the index of <tt>val</tt> or -1 if it isn't in the set.\r
 426      */\r
 427     private static int index(int[] table, int hashBase, int a) {\r
 428         int hash, probe, index, length, hashIndex;\r
 429         int[] set = table;\r
 430         length = getRealSize(table, hashBase);\r
 431         hash = computeHashCode(a);\r
 432         index = hash % length;\r
 433         hashIndex = hashBase + index;\r
 434 \r
 435         if (!isFree(set[hashIndex])\r
 436                 && (isRemoved(set[hashIndex]) || set[hashIndex] != a)) {\r
 437             // see Knuth, p. 529\r
 438             probe = 1 + (hash % (length - 2));\r
 439 \r
 440             do {\r
 441                 index -= probe;\r
 442                 if (index < 0) {\r
 443                     index += length;\r
 444                 }\r
 445                 hashIndex = hashBase + index;\r
 446             } while (!isFree(set[hashIndex])\r
 447                     && (isRemoved(set[hashIndex]) || set[hashIndex] != a));\r
 448         }\r
 449 \r
 450         return isFree(set[hashIndex]) ? -1  : hashIndex;\r
 451     }\r
 452 \r
 453     /**\r
 454      * Locates the index at which <tt>val</tt> can be inserted. if there is\r
 455      * already a value equal()ing <tt>val</tt> in the set, returns that value\r
 456      * as a negative integer.\r
 457      * \r
 458      * @param val\r
 459      *            an <code>int</code> value\r
 460      * @return an <code>int</code> value\r
 461      */\r
 462     private static final int insertionIndex(int[] table, int hashBase, int a) {\r
 463         int hash, probe, index, length, hashIndex;\r
 464         int[] set = table;\r
 465         length = getRealSize(table, hashBase);\r
 466         hash = computeHashCode(a);\r
 467         index = hash % length;\r
 468         assert(0 != hashBase);\r
 469         hashIndex = hashBase + index;\r
 470         \r
 471 //        int used = getUsedSize(table, hashBase);\r
 472 //        int max = getMaxSize(table, hashBase);\r
 473 //        assert(used > max);\r
 474 //        \r
 475         if (isFree(set[hashIndex])) {\r
 476             return hashIndex; // empty, all done\r
 477         } else if (isFull(set[hashIndex]) && set[hashIndex] == a) {\r
 478             return -hashIndex; // already stored\r
 479         } else { // already FULL or REMOVED, must probe\r
 480             // compute the double hash\r
 481             probe = 1 + (hash % (length - 2));\r
 482 \r
 483             // if the slot we landed on is FULL (but not removed), probe\r
 484             // until we find an empty slot, a REMOVED slot, or an element\r
 485             // equal to the one we are trying to insert.\r
 486             // finding an empty slot means that the value is not present\r
 487             // and that we should use that slot as the insertion point;\r
 488             // finding a REMOVED slot means that we need to keep searching,\r
 489             // however we want to remember the offset of that REMOVED slot\r
 490             // so we can reuse it in case a "new" insertion (i.e. not an update)\r
 491             // is possible.\r
 492             // finding a matching value means that we've found that our desired\r
 493             // key is already in the table\r
 494 \r
 495             if (!isRemoved(set[hashIndex])) {\r
 496                 // starting at the natural offset, probe until we find an\r
 497                 // offset that isn't full.\r
 498                 do {\r
 499                     index -= probe;\r
 500                     if (index < 0) {\r
 501                         index += length;\r
 502                     }\r
 503                     hashIndex = hashBase + index;\r
 504                 } while (isFull(set[hashIndex]) && set[hashIndex] != a);\r
 505             }\r
 506 \r
 507             // if the index we found was removed: continue probing until we\r
 508             // locate a free location or an element which equal()s the\r
 509             // one we have.\r
 510             if (isRemoved(set[hashIndex])) {\r
 511                 int firstRemoved = hashIndex;\r
 512                 while (!isFree(set[hashIndex])\r
 513                         && (isRemoved(set[hashIndex]) || set[hashIndex] != a)) {\r
 514                     index -= probe;\r
 515                     if (index < 0) {\r
 516                         index += length;\r
 517                     }\r
 518                     hashIndex = hashBase + index;\r
 519                 }\r
 520                 return isFull(set[hashIndex]) ? -hashIndex : firstRemoved;\r
 521             }\r
 522             // if it's full, the key is already stored\r
 523             return isFull(set[hashIndex]) ? -hashIndex : hashIndex;\r
 524         }\r
 525     }\r
 526 \r
 527     private static final int computeHashCode(int aKey) {\r
 528         int hash = aKey * 31;\r
 529         return hash & 0x7fffffff; // Top bit reserved.\r
 530     }\r
 531 }\r