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

   1 /*******************************************************************************
   2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management
   3  * in Industry THTH ry.
   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
   8  *
   9  * Contributors:
  10  *     VTT Technical Research Centre of Finland - initial API and implementation
  11  *******************************************************************************/
  12 package org.simantics.db.procore.cluster;
  13
  14 import gnu.trove.impl.PrimeFinder;
  15
  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;
  24
  25         static final boolean isFree(long a) {
  26                 return FREE == a;
  27         }
  28
  29         static final boolean isFull(long a) {
  30                 return a > FREE;
  31         }
  32
  33         static final boolean isRemoved(long a) {
  34                 return REMOVED == a;
  35         }
  36
  37         static final long setFree() {
  38                 return FREE;
  39         }
  40
  41         static final long setFull(long a) {
  42                 return a;
  43         }
  44
  45         static final long setRemoved() {
  46                 return REMOVED;
  47         }
  48
  49         static public int getRealSize(long[] longs, int hashBase) {
  50                 long desc = longs[hashBase + UsedAndRealSize];
  51                 assert(desc < 0);
  52                 int realSize = (int)desc & 0x7FFFFFFF;
  53                 assert (realSize > MinRealSizeMinusOne);
  54                 return realSize;
  55         }
  56
  57 //      private static void setRealSize(long[] longs, int hashBase, int realSize) {
  58 //              assert (realSize > MinRealSizeMinusOne);
  59 //              long desc = longs[hashBase + UsedAndRealSize];
  60 //              assert(desc < 0);
  61 //              assert((int)desc < 0);
  62 //              desc = (desc & 0xFFFFFFFF80000000L) | realSize;
  63 //              longs[hashBase + UsedAndRealSize] = desc;
  64 //      }
  65
  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;
  73         longs[index] = desc;
  74     }
  75
  76     public static int getUsedSize(long[] longs, int hashBase) {
  77         long desc = longs[hashBase + UsedAndRealSize];
  78         assert(desc < 0);
  79         assert((int)desc < 0);
  80         return (int)(desc >> 32) & 0x7FFFFFFF;
  81     }
  82
  83         static void setUsedSize(long[] longs, int hashBase, int usedSize) {
  84                 assert (usedSize >= 0);
  85         int index = hashBase + UsedAndRealSize;
  86         long desc = longs[index];
  87         assert(desc < 0);
  88                 assert((int)desc < 0);
  89         desc = (desc & 0x80000000FFFFFFFFL) | (long)usedSize << 32;
  90         longs[index] = desc;
  91         }
  92
  93         // return value after decrement
  94         static int decUsedSize(long[] longs, int hashBase) {
  95         int index = hashBase + UsedAndRealSize;
  96         long desc = longs[index];
  97         assert(desc < 0);
  98         int usedSize = ((int)(desc >> 32) & 0x7FFFFFFF) - 1;
  99                 assert(usedSize >= 0);
 100         desc = (desc & 0x80000000FFFFFFFFL) | (long)usedSize << 32;
 101         longs[index] = desc;
 102         return usedSize;
 103         }
 104
 105         // return value after increment
 106         static int incUsedSize(long[] longs, int hashBase) {
 107         int index = hashBase + UsedAndRealSize;
 108         long desc = longs[index];
 109         assert(desc < 0);
 110         int usedSize = ((int)(desc >> 32) & 0x7FFFFFFF) + 1;
 111                 assert(usedSize > 0);
 112         desc = (desc & 0x80000000FFFFFFFFL) | (long)usedSize << 32;
 113         longs[index] = desc;
 114         return usedSize;
 115         }
 116
 117         static int getFreeSize(long[] longs, int hashBase) {
 118                 long desc = longs[hashBase + MaxAndFreeSize];
 119                 assert(desc > 0);
 120                 int freeSize = (int)desc;
 121                 assert (freeSize >= 0);
 122                 return freeSize;
 123         }
 124
 125         static void setFreeSize(long[] longs, int hashBase, int freeSize) {
 126                 assert (freeSize >= 0);
 127                 long desc = longs[hashBase + MaxAndFreeSize];
 128                 assert(desc > 0);
 129                 assert((int)desc >= 0);
 130                 desc = (desc & 0xFFFFFFFF00000000L) | freeSize;
 131                 longs[hashBase + MaxAndFreeSize] = desc;
 132         }
 133
 134         static void decFreeSize(long[] longs, int hashBase) {
 135                 long desc = longs[hashBase + MaxAndFreeSize];
 136                 assert(desc > 0);
 137                 int freeSize = (int)desc;
 138                 assert(freeSize > 0);
 139                 desc = (desc & 0xFFFFFFFF00000000L) | --freeSize;
 140                 longs[hashBase + MaxAndFreeSize] = desc;
 141         }
 142
 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;
 150         longs[index] = desc;
 151     }
 152
 153         static int getMaxSize(long[] longs, int hashBase) {
 154         long desc = longs[hashBase + MaxAndFreeSize];
 155         assert(desc > 0);
 156         assert((int)desc >= 0);
 157         return (int)(desc >> 32);
 158         }
 159
 160         static void setMaxSize(long[] longs, int hashBase, int maxSize) {
 161                 assert (maxSize > 0);
 162         int index = hashBase + MaxAndFreeSize;
 163         long desc = longs[index];
 164         assert(desc > 0);
 165                 assert((int)desc >= 0);
 166         desc = (desc & 0x00000000FFFFFFFFL) | (long)maxSize << 32;
 167         longs[index] = desc;
 168         }
 169
 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);
 174                 if (index < 0)
 175                         return false; // already present in set, nothing to add
 176                 long previousState = longs[index];
 177                 assert(LongHash.isFull(a));
 178                 longs[index] = a;
 179                 postInsertHook(longs, hashBase, LongHash.isFree(previousState), allocator);
 180                 return true; // yes, we added something
 181         }
 182
 183     public static boolean remove(long[] longs, int hashBase, long a) {
 184         int index = LongHash.index(longs, hashBase, a);
 185         if (index >= 0) {
 186                 longs[index] = setRemoved();
 187                 decUsedSize(longs, hashBase);
 188             return true;
 189         }
 190         return false;
 191     }
 192
 193     public static boolean contains(long[] longs, int hashBase,long a) {
 194         return index(longs, hashBase, a) >= 0;
 195     }
 196
 197     public static boolean isEmpty(long[] longs, int hashBase) {
 198                 return 0 == getUsedSize(longs, hashBase);
 199         }
 200
 201     public static void clear(long[] longs, int hashBase) {
 202         long[] set = longs;
 203         long free = setFree();
 204         int capacity = getRealSize(longs, hashBase);
 205         for (int i = capacity; i-- > 0;) {
 206             set[hashBase + i] = free;
 207         }
 208         setUsedSize(longs, hashBase, 0);
 209         setFreeSize(longs, hashBase, capacity);
 210     }
 211
 212         /**
 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.
 217          *
 218          * @param desiredSize an <code>int</code> value
 219          */
 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);
 227                         return true;
 228                 }
 229                 return false;
 230         }
 231
 232         /**
 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:
 238          *
 239          * <ol>
 240          * <li> You'll free memory allocated to the table but no longer needed
 241          * because of the remove()s.</li>
 242          *
 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>
 246          * </ol>
 247          */
 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);
 253         }
 254
 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);
 262                 return hashBase;
 263         }
 264
 265         /**
 266          * Expands the set to accomodate new values.
 267          *
 268          * @param newCapacity
 269          *            an <code>int</code> value
 270          */
 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);
 281
 282                 for (int i = oldCapacity + oldHashBase; i-- > oldHashBase;) {
 283                         long o = oldLongs[i];
 284                         if (isFull(o)) {
 285                                 int index = insertionIndex(newLongs, newHashBase, o);
 286                                 newLongs[index] = o;
 287                         }
 288                 }
 289         }
 290
 291         /**
 292          * After an insert, this hook is called to adjust the size/free values of
 293          * the set and to perform rehashing if necessary.
 294          */
 295         protected static final void postInsertHook(long[] longs, int hashBase,
 296                         boolean usedFreeSlot, AllocatorI allocator) {
 297                 if (usedFreeSlot) {
 298                         decFreeSize(longs, hashBase);
 299                 }
 300
 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);
 312                 }
 313         }
 314
 315         /**
 316          * Locates the index of <tt>val</tt>.
 317          *
 318          * @param val
 319          *            an <code>long</code> value
 320          * @return the index of <tt>val</tt> or -1 if it isn't in the set.
 321          */
 322         static int index(long[] longs, int hashBase, long a) {
 323                 int hash, probe, index, length, hashIndex;
 324                 long[] set = longs;
 325                 length = getRealSize(longs, hashBase);
 326                 hash = computeHashCode(a);
 327                 index = hash % length;
 328                 hashIndex = hashBase + index;
 329
 330                 if (!LongHash.isFree(set[hashIndex])
 331                                 && (LongHash.isRemoved(set[hashIndex]) || set[hashIndex] != a)) {
 332                         // see Knuth, p. 529
 333                         probe = 1 + (hash % (length - 2));
 334
 335                         do {
 336                                 index -= probe;
 337                                 if (index < 0) {
 338                                         index += length;
 339                                 }
 340                                 hashIndex = hashBase + index;
 341                         } while (!LongHash.isFree(set[hashIndex])
 342                                         && (LongHash.isRemoved(set[hashIndex]) || set[hashIndex] != a));
 343                 }
 344
 345                 return LongHash.isFree(set[hashIndex]) ? -1  : hashIndex;
 346         }
 347
 348         /**
 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.
 352          *
 353          * @param val
 354          *            an <code>long</code> value
 355          * @return an <code>int</code> value
 356          */
 357         static final int insertionIndex(long[] longs, int hashBase, long a) {
 358                 int hash, probe, index, length, hashIndex;
 359                 long[] set = longs;
 360                 length = getRealSize(longs, hashBase);
 361                 hash = computeHashCode(a);
 362                 index = hash % length;
 363                 assert(0 != hashBase);
 364                 hashIndex = hashBase + index;
 365
 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));
 373
 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)
 382                         // is possible.
 383                         // finding a matching value means that we've found that our desired
 384                         // key is already in the table
 385
 386                         if (!LongHash.isRemoved(set[hashIndex])) {
 387                                 // starting at the natural offset, probe until we find an
 388                                 // offset that isn't full.
 389                                 do {
 390                                         index -= probe;
 391                                         if (index < 0) {
 392                                                 index += length;
 393                                         }
 394                                         hashIndex = hashBase + index;
 395                                 } while (LongHash.isFull(set[hashIndex]) && set[hashIndex] != a);
 396                         }
 397
 398                         // if the index we found was removed: continue probing until we
 399                         // locate a free location or an element which equal()s the
 400                         // one we have.
 401                         if (LongHash.isRemoved(set[hashIndex])) {
 402                                 int firstRemoved = hashIndex;
 403                                 while (!LongHash.isFree(set[hashIndex])
 404                                                 && (LongHash.isRemoved(set[hashIndex]) || set[hashIndex] != a)) {
 405                                         index -= probe;
 406                                         if (index < 0) {
 407                                                 index += length;
 408                                         }
 409                                         hashIndex = hashBase + index;
 410                                 }
 411                                 return LongHash.isFull(set[hashIndex]) ? -hashIndex : firstRemoved;
 412                         }
 413                         // if it's full, the key is already stored
 414                         return LongHash.isFull(set[hashIndex]) ? -hashIndex : hashIndex;
 415                 }
 416         }
 417
 418         static final int computeHashCode(long aKey) {
 419                 int hash = ((int) (aKey ^ (aKey >> 32))) * 31;
 420                 return hash & 0x7fffffff; // Top bit reserved.
 421         }
 422
 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
 427         }
 428 }
 429
 430 class LongIterator {
 431         private long[] longs;
 432         private int hashBase;
 433         private int index;
 434         // for reset
 435         private int size; // number of elements in the set
 436         private final LongHash.AllocatorI allocator;
 437
 438         public LongIterator(LongHash.AllocatorI allocator) {
 439                 this.allocator = allocator;
 440                 this.reset();
 441     }
 442         public int size() {
 443                 return this.size;
 444         }
 445         public void reset() {
 446                 if (longs == null ||
 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);
 453                 }
 454                 this.index = LongHash.getRealSize(longs, hashBase);
 455         }
 456         public long next() {
 457         if (moveToNextIndex())
 458                 return longs[hashBase + index];
 459         return LongHash.setFree();
 460     }
 461     protected final boolean moveToNextIndex() {
 462         // doing the assignment && < 0 in one line saves 3 opcodes...
 463         if ((index = nextIndex()) < 0) {
 464             return false;
 465         }
 466         return true;
 467     }
 468     protected final int nextIndex() {
 469         long[] states = longs;
 470         int i = index;
 471         while (i-- > 0 && (!LongHash.isFull(states[hashBase + i])))
 472                         ;
 473         return i;
 474     }
 475     public boolean hasNext() {
 476         return nextIndex() >= 0;
 477     }
 478 }
 479