bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/TableIntHash.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.exception.DatabaseException;
  15 import org.simantics.db.impl.ClusterI.Procedure;
  16 import org.simantics.db.impl.ClusterSupport;
  17 import org.simantics.db.impl.Modifier;
  18 import org.simantics.db.impl.Table;
  19 import org.simantics.db.impl.TableFactory;
  20 import org.simantics.db.impl.TableSizeListener;
  21
  22 import gnu.trove.impl.PrimeFinder;
  23
  24 class TableIntHash extends Table<int[]> {
  25     private static final int INITIAL_SIZE = 1000;
  26     private static final int ENTRY_SIZE = 3;
  27     protected static final int HeaderSize = 5;
  28     private static final int Capacity = -5; // Number of allocated slots.
  29     private static final int Size = -4; // Number of used slots.
  30     private static final int Free = -3; // Number of free slots.
  31     private static final int MaxInsert = -2; // Limit for increasing number of allocated slots.
  32     private static final int MaxRemove = -1; // Limit for removing removed slots.
  33     protected int[] ints;
  34     protected int hashBase;
  35     TableIntHash(TableSizeListener sizeListener, int[] header, int headerBase) {
  36         super(TableFactory.getIntFactory(), sizeListener, header, headerBase);
  37         int capacity = PrimeFinder.nextPrime(INITIAL_SIZE);
  38         int tableSize = ENTRY_SIZE * capacity + HeaderSize;
  39         createNewTable(tableSize, tableSize, 1); // size, capacity, count
  40         ints = getTable();
  41         hashBase = getTableBase() + HeaderSize;
  42         capacitySet(capacity);
  43         sizeSet(0);
  44         freeSet(capacity);
  45         computeMaxInsert(capacity);
  46         computeMaxRemove(maxInsertGet());
  47     }
  48     TableIntHash(TableSizeListener sizeListener, int[] header, int headerBase, int[] ints) {
  49         super(TableFactory.getIntFactory(), sizeListener, header, headerBase, ints);
  50         this.ints = getTable();
  51         this.hashBase = getTableBase() + HeaderSize;
  52     }
  53     static final boolean isFree(int v) {
  54         return IntHashTrait.isFree(v);
  55     }
  56
  57     static final boolean isFull(int v) {
  58         return IntHashTrait.isFull(v);
  59     }
  60
  61     final boolean isFullByIndex(int index) {
  62         return isFull(setGet(index));
  63     }
  64
  65     static final boolean isRemoved(int v) {
  66         return IntHashTrait.isRemoved(v);
  67     }
  68
  69     static final int setFree() {
  70         return IntHashTrait.setFree();
  71     }
  72
  73     static final int setFull(int v) {
  74         return IntHashTrait.setFull(v);
  75     }
  76
  77     static final int setRemoved() {
  78         return IntHashTrait.setRemoved();
  79     }
  80     final int capacityGet() {
  81         return ints[hashBase + Capacity];
  82     }
  83     final void capacitySet(int a) {
  84         ints[hashBase + Capacity] = a;
  85     }
  86     final int sizeGet() {
  87         return ints[hashBase + Size];
  88     }
  89     final void sizeSet(int a) {
  90         ints[hashBase + Size] = a;
  91     }
  92     final int freeGet() {
  93         return ints[hashBase + Free];
  94     }
  95     final void freeSet(int a) {
  96         ints[hashBase + Free] = a;
  97     }
  98     final int maxInsertGet() {
  99         return ints[hashBase + MaxInsert];
 100     }
 101     final void maxInsertSet(int a) {
 102         ints[hashBase + MaxInsert] = a;
 103     }
 104     final int maxRemoveGet() {
 105         return ints[hashBase + MaxRemove];
 106     }
 107     void maxRemoveSet(int a) {
 108         ints[hashBase + MaxRemove] = a;
 109     }
 110     final int setGet(final int index) {
 111         return ints[hashBase + index * ENTRY_SIZE + 2];
 112     }
 113     final void setSet(int index, int value) {
 114         ints[hashBase + index * ENTRY_SIZE + 2] = value;
 115     }
 116     final void setKeyAndValue(int index, int key1, int key2, int value) {
 117         int realIndex = index * ENTRY_SIZE;
 118         ints[hashBase + realIndex] = key1;
 119         ints[hashBase + realIndex + 1] = key2;
 120         ints[hashBase + realIndex + 2] = value;
 121     }
 122     final boolean isFreeByIndex(final int index) {
 123         return isFree(ints[hashBase + index * ENTRY_SIZE + 2]);
 124     }
 125     final boolean isRemovedByIndex(final int index) {
 126         return isRemoved(ints[hashBase + index * ENTRY_SIZE + 2]);
 127     }
 128     final boolean isEqualByIndex(final int index, final int key1, final int key2) {
 129         int realIndex = index * ENTRY_SIZE;
 130         return key1 == ints[hashBase + realIndex] && key2 == ints[hashBase + realIndex + 1];
 131     }
 132     final void computeMaxInsert(int capacity) {
 133         // need at least one free slot for open addressing
 134         int maxSize = Math.min(capacity - 1, capacity >> 1);
 135         maxInsertSet(maxSize);
 136         freeSet(capacity - sizeGet()); // reset the free element count
 137     }
 138
 139     final void computeMaxRemove(int removeCapacity) {
 140         maxRemoveSet((removeCapacity >> 1) + 1);
 141     }
 142     /**
 143      * retrieves the value for <tt>key</tt>
 144      *
 145      * @param key an <code>int</code> value
 146      * @return the value of <tt>key</tt> or (int)0 if no such mapping exists.
 147      */
 148     final int getValue(int key1, int key2) {
 149         int index = index(key1, key2);
 150         return index < 0 ?  0 : setGet(index);
 151     }
 152     final boolean removeValue(int key1, int key2) {
 153         int index = index(key1, key2);
 154         if (index < 0)
 155             return false;
 156         setSet(index, setRemoved());
 157         return true;
 158
 159     }
 160     final boolean setValue(int key1, int key2, int value) {
 161         assert(!isFree(value));
 162         assert(!isRemoved(value));
 163         int index = insertionIndex(key1, key2);
 164         boolean added = true;
 165         boolean isNewMapping = true;
 166         boolean previousStateWasFree = false;
 167         if (index < 0) { // old entry
 168             index = -index - 1;
 169             setSet(index, value);
 170             isNewMapping = false;
 171         } else { // new entry
 172              if (isFreeByIndex(index))
 173                  previousStateWasFree = true;
 174              setKeyAndValue(index, key1, key2, value);
 175         }
 176         if (isNewMapping)
 177             postInsertHook(previousStateWasFree);
 178         return added;
 179
 180     }
 181     /**
 182      * Locates the index of <tt>akey</tt>.
 183      *
 184      * @param akey an <code>int</code> value
 185      * @return the index of <tt>akey</tt> or -1 if it isn't in the set.
 186      */
 187     final int index(final int akey1, final int akey2) {
 188         int hash, probe, index, length;
 189         //IntArray set = _set;
 190         length = capacityGet();
 191         hash = computeHashCode(akey1, akey2);
 192         index = hash % length;
 193         if (!isFreeByIndex(index) &&
 194             (isRemovedByIndex(index) ||
 195              !isEqualByIndex(index, akey1, akey2))) {
 196             // see Knuth, p. 529
 197             probe = 1 + (hash % (length - 2));
 198             do {
 199                 index -= probe;
 200                 if (index < 0) {
 201                     index += length;
 202                 }
 203             } while (!isFreeByIndex(index) &&
 204                      (isRemovedByIndex(index) ||
 205                                  !isEqualByIndex(index, akey1, akey2)));
 206         }
 207
 208         return isFreeByIndex(index) ? -1 : index;
 209     }
 210     /**
 211      * Locates the index at which <tt>akey</tt> can be inserted.  if
 212      * there is already a key equaling <tt>akey</tt> in the set,
 213      * returns that key as a negative integer.
 214      *
 215      * @param akey an <code>long</code> value
 216      * @return an <code>int</code> value
 217      */
 218     final int insertionIndex(int akey1, int akey2) {
 219         int hash, probe, index, length;
 220         //IntArray set = _set;
 221         length = capacityGet();
 222         hash = computeHashCode(akey1, akey2);
 223         index = hash % length;
 224         if (isFreeByIndex(index)) {
 225             return index; // empty, all done
 226         } else if (isFullByIndex(index) && isEqualByIndex(index, akey1, akey2)) {
 227             return -index -1; // already stored
 228         } else { // already FULL or REMOVED, must probe
 229             // compute the double hash
 230             probe = 1 + (hash % (length - 2));
 231
 232             // if the slot we landed on is FULL (but not removed), probe
 233             // until we find an empty slot, a REMOVED slot, or an element
 234             // equal to the one we are trying to insert.
 235             // finding an empty slot means that the value is not present
 236             // and that we should use that slot as the insertion point;
 237             // finding a REMOVED slot means that we need to keep searching,
 238             // however we want to remember the offset of that REMOVED slot
 239             // so we can reuse it in case a "new" insertion (i.e. not an update)
 240             // is possible.
 241             // finding a matching value means that we've found that our desired
 242             // key is already in the table
 243
 244             if (!isRemovedByIndex(index)) {
 245                 // starting at the natural offset, probe until we find an
 246                 // offset that isn't full.
 247                 do {
 248                     index -= probe;
 249                     if (index < 0) {
 250                         index += length;
 251                     }
 252                 } while (isFullByIndex(index) && !isEqualByIndex(index, akey1, akey2));
 253             }
 254
 255             // if the index we found was removed: continue probing until we
 256             // locate a free location or an element which equal()s the
 257             // one we have.
 258             if (isRemovedByIndex(index)) {
 259                 int firstRemoved = index;
 260                 while (!isFreeByIndex(index) &&
 261                        (isRemovedByIndex(index) || !isEqualByIndex(index, akey1, akey2))) {
 262                     index -= probe;
 263                     if (index < 0) {
 264                         index += length;
 265                     }
 266                 }
 267                 return isFullByIndex(index) ? -index -1 : firstRemoved;
 268             }
 269             // if it's full, the key is already stored
 270             return isFullByIndex(index) ? -index -1 : index;
 271         }
 272     }
 273
 274     static final int computeHashCode(int key1, int key2) {
 275         // Multiple by prime to make sure hash can't be negative (see Knuth v3, p. 515-516)
 276         int hash;
 277         if (key1 == key2)
 278             hash = key1 * 31;
 279         else
 280             hash = ((int)(key1 ^ key2)) * 31;
 281         return hash & 0x7fffffff;
 282     }
 283     /**
 284      * After an insert, this hook is called to adjust the size/free
 285      * values of the set and to perform rehashing if necessary.
 286      */
 287     protected final void postInsertHook(boolean usedFreeSlot) {
 288         if (usedFreeSlot) {
 289             freeSet(freeGet()-1);
 290         }
 291         // rehash whenever we exhaust the available space in the table
 292         int size = sizeGet() + 1;
 293         sizeSet(size);
 294         int maxSize = maxInsertGet();
 295         int capacity = capacityGet();
 296         int free = freeGet();
 297         if (size >  maxSize || free == 0) {
 298             // choose a new capacity suited to the new state of the table
 299             // if we've grown beyond our maximum size, double capacity;
 300             // if we've exhausted the free spots, rehash to the same capacity,
 301             // which will free up any stale removed slots for reuse.
 302             int newCapacity = size > maxSize ? PrimeFinder.nextPrime(capacity << 1) : capacity;
 303             rehash(newCapacity);
 304         }
 305     }
 306     final private void rehash(int newCapacity) {
 307         int oldCapacity = capacityGet();
 308         int oldHashBase = hashBase;
 309         int newTableCapacity = newCapacity*ENTRY_SIZE + HeaderSize;
 310         int[] oldInts = createNewTable(newTableCapacity, newTableCapacity, 1);
 311         ints = getTable();
 312         hashBase = getTableBase() + HeaderSize;
 313         capacitySet(newCapacity);
 314         sizeSet(0);
 315         freeSet(newCapacity);
 316         computeMaxInsert(newCapacity);
 317         computeMaxRemove(maxInsertGet());
 318         for (int i = oldCapacity; i-- > 0;) {
 319             int realIndex = oldHashBase + i*ENTRY_SIZE;
 320             if (isFull(oldInts[realIndex+2])) {
 321                 int hashIndex = insertionIndex(oldInts[realIndex], oldInts[realIndex+1]);
 322                 assert(hashIndex >= 0);
 323                 int value = oldInts[realIndex+2];
 324                 assert(!isFree(value));
 325                 assert(!isRemoved(value));
 326                 setKeyAndValue(hashIndex, oldInts[realIndex], oldInts[realIndex+1], value);
 327             }
 328         }
 329     }
 330
 331     @Override
 332     public <Context> boolean foreach(int setIndex, Procedure procedure, Context context, ClusterSupport support, Modifier modifier) throws DatabaseException {
 333         throw new UnsupportedOperationException();
 334     }
 335
 336 }