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