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