69450de7c8efc045e6aa6bab583e1c668f5a3507
[simantics/platform.git] / 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);
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 }