1 /*******************************************************************************
2 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
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
10 * VTT Technical Research Centre of Finland - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.db.procore.cluster;
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;
22 import gnu.trove.impl.PrimeFinder;
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.
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
41 hashBase = getTableBase() + HeaderSize;
42 capacitySet(capacity);
45 computeMaxInsert(capacity);
46 computeMaxRemove(maxInsertGet());
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;
53 static final boolean isFree(int v) {
54 return IntHashTrait.isFree(v);
57 static final boolean isFull(int v) {
58 return IntHashTrait.isFull(v);
61 final boolean isFullByIndex(int index) {
62 return isFull(setGet(index));
65 static final boolean isRemoved(int v) {
66 return IntHashTrait.isRemoved(v);
69 static final int setFree() {
70 return IntHashTrait.setFree();
73 static final int setFull(int v) {
74 return IntHashTrait.setFull(v);
77 static final int setRemoved() {
78 return IntHashTrait.setRemoved();
80 final int capacityGet() {
81 return ints[hashBase + Capacity];
83 final void capacitySet(int a) {
84 ints[hashBase + Capacity] = a;
87 return ints[hashBase + Size];
89 final void sizeSet(int a) {
90 ints[hashBase + Size] = a;
93 return ints[hashBase + Free];
95 final void freeSet(int a) {
96 ints[hashBase + Free] = a;
98 final int maxInsertGet() {
99 return ints[hashBase + MaxInsert];
101 final void maxInsertSet(int a) {
102 ints[hashBase + MaxInsert] = a;
104 final int maxRemoveGet() {
105 return ints[hashBase + MaxRemove];
107 void maxRemoveSet(int a) {
108 ints[hashBase + MaxRemove] = a;
110 final int setGet(final int index) {
111 return ints[hashBase + index * ENTRY_SIZE + 2];
113 final void setSet(int index, int value) {
114 ints[hashBase + index * ENTRY_SIZE + 2] = value;
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;
122 final boolean isFreeByIndex(final int index) {
123 return isFree(ints[hashBase + index * ENTRY_SIZE + 2]);
125 final boolean isRemovedByIndex(final int index) {
126 return isRemoved(ints[hashBase + index * ENTRY_SIZE + 2]);
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];
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
139 final void computeMaxRemove(int removeCapacity) {
140 maxRemoveSet((removeCapacity >> 1) + 1);
143 * retrieves the value for <tt>key</tt>
145 * @param key an <code>int</code> value
146 * @return the value of <tt>key</tt> or (int)0 if no such mapping exists.
148 final int getValue(int key1, int key2) {
149 int index = index(key1, key2);
150 return index < 0 ? 0 : setGet(index);
152 final boolean removeValue(int key1, int key2) {
153 int index = index(key1, key2);
156 setSet(index, setRemoved());
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
169 setSet(index, value);
170 isNewMapping = false;
171 } else { // new entry
172 if (isFreeByIndex(index))
173 previousStateWasFree = true;
174 setKeyAndValue(index, key1, key2, value);
177 postInsertHook(previousStateWasFree);
182 * Locates the index of <tt>akey</tt>.
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.
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))) {
197 probe = 1 + (hash % (length - 2));
203 } while (!isFreeByIndex(index) &&
204 (isRemovedByIndex(index) ||
205 !isEqualByIndex(index, akey1, akey2)));
208 return isFreeByIndex(index) ? -1 : index;
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.
215 * @param akey an <code>long</code> value
216 * @return an <code>int</code> value
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));
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)
241 // finding a matching value means that we've found that our desired
242 // key is already in the table
244 if (!isRemovedByIndex(index)) {
245 // starting at the natural offset, probe until we find an
246 // offset that isn't full.
252 } while (isFullByIndex(index) && !isEqualByIndex(index, akey1, akey2));
255 // if the index we found was removed: continue probing until we
256 // locate a free location or an element which equal()s the
258 if (isRemovedByIndex(index)) {
259 int firstRemoved = index;
260 while (!isFreeByIndex(index) &&
261 (isRemovedByIndex(index) || !isEqualByIndex(index, akey1, akey2))) {
267 return isFullByIndex(index) ? -index -1 : firstRemoved;
269 // if it's full, the key is already stored
270 return isFullByIndex(index) ? -index -1 : index;
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)
280 hash = ((int)(key1 ^ key2)) * 31;
281 return hash & 0x7fffffff;
284 * After an insert, this hook is called to adjust the size/free
285 * values of the set and to perform rehashing if necessary.
287 protected final void postInsertHook(boolean usedFreeSlot) {
289 freeSet(freeGet()-1);
291 // rehash whenever we exhaust the available space in the table
292 int size = sizeGet() + 1;
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;
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);
312 hashBase = getTableBase() + HeaderSize;
313 capacitySet(newCapacity);
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);
332 public <Context> boolean foreach(int setIndex, Procedure procedure, Context context, ClusterSupport support, Modifier modifier) throws DatabaseException {
333 throw new UnsupportedOperationException();