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