]> gerrit.simantics Code Review - simantics/platform.git/blob - bundles/org.simantics.db.procore/src/org/simantics/db/procore/cluster/TableIntHash.java
7d8256b0b3991747bdf26698099ea92f79e8f3e2
[simantics/platform.git] / 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