]> gerrit.simantics Code Review - simantics/platform.git/blob - bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/BinaryQueryHash.java
Fail safe import fixes made by Antti
[simantics/platform.git] / bundles / org.simantics.db.impl / src / org / simantics / db / impl / query / BinaryQueryHash.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.impl.query;
13
14 import gnu.trove.impl.hash.THash;
15
16 import java.lang.reflect.Array;
17
18 import org.simantics.db.impl.graph.ReadGraphImpl;
19
20
21 /**
22  * An open addressed hashing implementation for Object types.
23  *
24  * Created: Sun Nov  4 08:56:06 2001
25  *
26  * @author Eric D. Friedman
27  * @version $Id: BinaryQueryHash.java,v 1.2 2008/03/14 11:38:53 tuoksk Exp $
28  */
29 abstract public class BinaryQueryHash<Procedure> extends THash {
30     static final long serialVersionUID = -3461112548087185871L;
31
32     /** the set of Objects */
33     protected transient BinaryQuery<Procedure>[] _set;
34
35     protected final BinaryQuery<Procedure> REMOVED = new BinaryQuery<Procedure>(-1, -1) {
36
37         @Override
38         public void computeForEach(ReadGraphImpl graph, QueryProcessor provider, Object procedure, boolean store) {
39             throw new Error("Not possible!");
40         }
41
42         @Override
43         public void putEntry(QueryProcessor provider) {
44             throw new Error("Not possible!");
45         }
46
47         @Override
48         public BinaryQuery<Procedure> getEntry(QueryProcessor provider) {
49             throw new Error("Not possible!");
50         }
51
52         @Override
53         public void recompute(ReadGraphImpl graph, QueryProcessor provider) {
54             throw new Error("Not possible!");
55         }
56
57         @Override
58         public void removeEntry(QueryProcessor provider) {
59             throw new Error("Not possible!");
60         }
61
62 //        @Override
63 //        public ICacheEntry2 cachedEntry(Object provider) {
64 //            throw new Error("Not possible!");
65 //        }
66 //
67 //        @Override
68 //        public void computeForEach(int callerThread, Object provider, ICacheEntry2 parent, Object procedure) {
69 //            throw new Error("Not possible!");
70 //        }
71
72         @Override
73         public int type() {
74             throw new Error("Not possible!");
75         }
76
77 //        @Override
78 //        public void reset() {
79 //            throw new Error("Not possible!");
80 //        }
81
82                 @Override
83                 public void performFromCache(ReadGraphImpl graph, QueryProcessor provider,
84                                 Procedure procedure) {
85             throw new Error("Not possible!");
86                 }
87
88 //              @Override
89 //              public void performFromCache(int callerThread, Object provider,
90 //                              Object procedure) {
91 //            throw new Error("Not possible!");
92 //              }
93
94                 @Override
95                 public void performFromCache(ReadGraphImpl graph, Object provider,
96                                 Object procedure) {
97             throw new Error("Not possible!");
98                 }
99         
100     };
101
102     /**
103      * Creates a new <code>TObjectHash</code> instance with the
104      * default capacity and load factor.
105      */
106     public BinaryQueryHash() {
107         super(DEFAULT_CAPACITY, 0.75f);
108     }
109
110     public int capacity() {
111         return _set.length;
112     }
113
114     protected void removeAt(int index) {
115         _set[index] = REMOVED;
116         super.removeAt(index);
117     }
118
119     /**
120      * initializes the Object set of this hash table.
121      *
122      * @param initialCapacity an <code>int</code> value
123      * @return an <code>int</code> value
124      */
125     @SuppressWarnings("unchecked")
126         protected int setUp(int initialCapacity) {
127         int capacity;
128
129         capacity = super.setUp(initialCapacity);
130         _set = (BinaryQuery[])Array.newInstance(BinaryQuery.class, capacity);
131         return capacity;
132         
133     }
134
135     final protected int index(final long id) {
136
137         final BinaryQuery<Procedure>[] set = _set;
138         final int length = set.length;
139         final int hash = ((31 * ((int)(id>>>32)) + (int)id) )& 0x7fffffff;
140         int index = hash % length;
141         BinaryQuery<Procedure> cur = set[index];
142
143         if ( cur == null ) return -1;
144
145         // NOTE: here it has to be REMOVED or FULL (some user-given value)
146         if ( cur == REMOVED || !(id == cur.id)) {
147             // see Knuth, p. 529
148             final int probe = 1 + (hash % (length - 2));
149
150             do {
151                 index -= probe;
152                 if (index < 0) {
153                     index += length;
154                 }
155                 cur = set[index];
156             } while (cur != null
157                  && (cur == REMOVED || !(id == cur.id)));
158         }
159
160         return cur == null ? -1 : index;
161         
162     }
163     
164
165     /**
166      * Locates the index at which <tt>obj</tt> can be inserted.  if
167      * there is already a value equal()ing <tt>obj</tt> in the set,
168      * returns that value's index as <tt>-index - 1</tt>.
169      *
170      * @param obj an <code>Object</code> value
171      * @return the index of a FREE slot at which obj can be inserted
172      * or, if obj is already stored in the hash, the negative value of
173      * that index, minus 1: -index -1.
174      */
175     final protected int insertionIndex(final long id) {
176
177         final BinaryQuery<Procedure>[] set = _set;
178         final int length = set.length;
179         final int hash = (31 * ((int)(id>>>32)) + (int)id) & 0x7fffffff;
180         int index = hash % length;
181         BinaryQuery<Procedure> cur = set[index];
182
183         if (cur == null) {
184             return index;       // empty, all done
185         } else if (cur != REMOVED && (id == cur.id)) {
186             return -index -1;   // already stored
187         } else {                // already FULL or REMOVED, must probe
188             // compute the double hash
189             final int probe = 1 + (hash % (length - 2));
190
191             // if the slot we landed on is FULL (but not removed), probe
192             // until we find an empty slot, a REMOVED slot, or an element
193             // equal to the one we are trying to insert.
194             // finding an empty slot means that the value is not present
195             // and that we should use that slot as the insertion point;
196             // finding a REMOVED slot means that we need to keep searching,
197             // however we want to remember the offset of that REMOVED slot
198             // so we can reuse it in case a "new" insertion (i.e. not an update)
199             // is possible.
200             // finding a matching value means that we've found that our desired
201             // key is already in the table
202             if (cur != REMOVED) {
203                 // starting at the natural offset, probe until we find an
204                 // offset that isn't full.
205                 do {
206                     index -= probe;
207                     if (index < 0) {
208                         index += length;
209                     }
210                     cur = set[index];
211                 } while (cur != null
212                          && cur != REMOVED
213                          && ! (id == cur.id));
214             }
215
216             // if the index we found was removed: continue probing until we
217             // locate a free location or an element which equal()s the
218             // one we have.
219             if (cur == REMOVED) {
220                 int firstRemoved = index;
221                 while (cur != null
222                        && (cur == REMOVED || ! (id == cur.id))) {
223                     index -= probe;
224                     if (index < 0) {
225                         index += length;
226                     }
227                     cur = set[index];
228                 }
229                 // NOTE: cur cannot == REMOVED in this block
230                 return (cur != null) ? -index -1 : firstRemoved;
231             }
232             // if it's full, the key is already stored
233             // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)
234             return (cur != null) ? -index -1 : index;
235         }
236     }
237
238     /**
239      * Convenience methods for subclasses to use in throwing exceptions about
240      * badly behaved user objects employed as keys.  We have to throw an
241      * IllegalArgumentException with a rather verbose message telling the
242      * user that they need to fix their object implementation to conform
243      * to the general contract for java.lang.Object.
244      *
245      * @param o1 the first of the equal elements with unequal hash codes.
246      * @param o2 the second of the equal elements with unequal hash codes.
247      * @exception IllegalArgumentException the whole point of this method.
248      */
249     protected final void throwObjectContractViolation(Object o1, Object o2)
250         throws IllegalArgumentException {
251         throw new IllegalArgumentException("Equal objects must have equal hashcodes. "
252                                            + "During rehashing, Trove discovered that "
253                                            + "the following two objects claim to be "
254                                            + "equal (as in java.lang.Object.equals()) "
255                                            + "but their hashCodes (or those calculated by "
256                                            + "your TObjectHashingStrategy) are not equal."
257                                            + "This violates the general contract of "
258                                            + "java.lang.Object.hashCode().  See bullet point two "
259                                            + "in that method's documentation. "
260                                            + "object #1 =" + o1 + " object #1 hash = " + o1.hashCode() + " object #1 id = " + System.identityHashCode(o1)
261                                            + "; object #2 =" + o2 + " object #2 hash = " + o2.hashCode() + " object #2 id = " + System.identityHashCode(o2));
262     }
263 } // TObjectHash