1 /*******************************************************************************
2 * Copyright (c) 2007, 2018 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.impl.query;
14 import gnu.trove.impl.hash.THash;
16 import java.lang.reflect.Array;
18 import org.simantics.db.exception.DatabaseException;
19 import org.simantics.db.impl.graph.ReadGraphImpl;
23 * An open addressed hashing implementation for Object types.
25 * Created: Sun Nov 4 08:56:06 2001
27 * @author Eric D. Friedman
28 * @version $Id: UnaryQueryHash.java,v 1.2 2008/03/14 11:38:53 tuoksk Exp $
30 abstract public class UnaryQueryHash<Procedure> extends THash {
31 static final long serialVersionUID = -3461112548087185871L;
33 /** the set of Objects */
34 protected transient UnaryQuery<Procedure>[] _set;
36 protected final UnaryQuery<Procedure> REMOVED = new UnaryQuery<Procedure>(-1) {
39 public void removeEntry(QueryProcessor provider) {
40 throw new Error("Not possible.");
45 throw new Error("Not possible.");
49 public void recompute(ReadGraphImpl graph) throws DatabaseException {
50 throw new Error("Not possible.");
54 Object performFromCache(ReadGraphImpl graph, Procedure procedure) throws DatabaseException {
55 throw new Error("Not possible.");
61 * Creates a new <code>TObjectHash</code> instance with the
62 * default capacity and load factor.
64 public UnaryQueryHash() {
65 super(DEFAULT_CAPACITY, 0.75f);
68 public int capacity() {
72 protected void removeAt(int index) {
73 _set[index] = REMOVED;
74 super.removeAt(index);
78 * initializes the Object set of this hash table.
80 * @param initialCapacity an <code>int</code> value
81 * @return an <code>int</code> value
83 @SuppressWarnings("unchecked")
84 protected int setUp(int initialCapacity) {
87 capacity = super.setUp(initialCapacity);
88 _set = (UnaryQuery[])Array.newInstance(UnaryQuery.class, capacity);
93 protected int index(final int id) {
95 final UnaryQuery<Procedure>[] set = _set;
96 final int length = set.length;
97 final int hash = (31 * id) & 0x7fffffff;
98 int index = hash % length;
99 UnaryQuery<Procedure> cur = set[index];
101 if ( cur == null ) return -1;
103 // NOTE: here it has to be REMOVED or FULL (some user-given value)
104 if ( cur == REMOVED || !(id == cur.id)) {
106 final int probe = 1 + (hash % (length - 2));
115 && (cur == REMOVED || !(id == cur.id)));
118 return cur == null ? -1 : index;
122 final protected UnaryQuery<Procedure> index2(final int id) {
124 final UnaryQuery<Procedure>[] set = _set;
125 final int length = set.length;
126 final int hash = (31 * id) & 0x7fffffff;
127 int index = hash % length;
128 UnaryQuery<Procedure> cur = set[index];
130 if ( cur == null ) return null;
132 // NOTE: here it has to be REMOVED or FULL (some user-given value)
133 if ( cur == REMOVED || (id != cur.id)) {
135 final int probe = 1 + (hash % (length - 2));
144 && (cur == REMOVED || (id != cur.id)));
153 * Locates the index at which <tt>obj</tt> can be inserted. if
154 * there is already a value equal()ing <tt>obj</tt> in the set,
155 * returns that value's index as <tt>-index - 1</tt>.
157 * @param obj an <code>Object</code> value
158 * @return the index of a FREE slot at which obj can be inserted
159 * or, if obj is already stored in the hash, the negative value of
160 * that index, minus 1: -index -1.
162 protected int insertionIndex(final int id) {
164 final UnaryQuery<Procedure>[] set = _set;
165 final int length = set.length;
166 final int hash = (31 * id) & 0x7fffffff;
167 int index = hash % length;
168 UnaryQuery<Procedure> cur = set[index];
171 return index; // empty, all done
172 } else if (cur != REMOVED && (id == cur.id)) {
173 return -index -1; // already stored
174 } else { // already FULL or REMOVED, must probe
175 // compute the double hash
176 final int probe = 1 + (hash % (length - 2));
178 // if the slot we landed on is FULL (but not removed), probe
179 // until we find an empty slot, a REMOVED slot, or an element
180 // equal to the one we are trying to insert.
181 // finding an empty slot means that the value is not present
182 // and that we should use that slot as the insertion point;
183 // finding a REMOVED slot means that we need to keep searching,
184 // however we want to remember the offset of that REMOVED slot
185 // so we can reuse it in case a "new" insertion (i.e. not an update)
187 // finding a matching value means that we've found that our desired
188 // key is already in the table
189 if (cur != REMOVED) {
190 // starting at the natural offset, probe until we find an
191 // offset that isn't full.
200 && ! (id == cur.id));
203 // if the index we found was removed: continue probing until we
204 // locate a free location or an element which equal()s the
206 if (cur == REMOVED) {
207 int firstRemoved = index;
209 && (cur == REMOVED || ! (id == cur.id))) {
216 // NOTE: cur cannot == REMOVED in this block
217 return (cur != null) ? -index -1 : firstRemoved;
219 // if it's full, the key is already stored
220 // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)
221 return (cur != null) ? -index -1 : index;
225 protected int insertionIndex2(final int id, final UnaryQuery<Procedure>[] set) {
227 final int length = set.length;
228 final int hash = (31 * id) & 0x7fffffff;
229 int index = hash % length;
230 UnaryQuery<Procedure> cur = set[index];
233 return index; // empty, all done
234 } else if (cur != REMOVED && (id == cur.id)) {
235 return -index -1; // already stored
236 } else { // already FULL or REMOVED, must probe
237 // compute the double hash
238 final int probe = 1 + (hash % (length - 2));
240 // if the slot we landed on is FULL (but not removed), probe
241 // until we find an empty slot, a REMOVED slot, or an element
242 // equal to the one we are trying to insert.
243 // finding an empty slot means that the value is not present
244 // and that we should use that slot as the insertion point;
245 // finding a REMOVED slot means that we need to keep searching,
246 // however we want to remember the offset of that REMOVED slot
247 // so we can reuse it in case a "new" insertion (i.e. not an update)
249 // finding a matching value means that we've found that our desired
250 // key is already in the table
251 if (cur != REMOVED) {
252 // starting at the natural offset, probe until we find an
253 // offset that isn't full.
262 && ! (id == cur.id));
265 // if the index we found was removed: continue probing until we
266 // locate a free location or an element which equal()s the
268 if (cur == REMOVED) {
269 int firstRemoved = index;
271 && (cur == REMOVED || ! (id == cur.id))) {
278 // NOTE: cur cannot == REMOVED in this block
279 return (cur != null) ? -index -1 : firstRemoved;
281 // if it's full, the key is already stored
282 // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)
283 return (cur != null) ? -index -1 : index;
288 * Convenience methods for subclasses to use in throwing exceptions about
289 * badly behaved user objects employed as keys. We have to throw an
290 * IllegalArgumentException with a rather verbose message telling the
291 * user that they need to fix their object implementation to conform
292 * to the general contract for java.lang.Object.
294 * @param o1 the first of the equal elements with unequal hash codes.
295 * @param o2 the second of the equal elements with unequal hash codes.
296 * @exception IllegalArgumentException the whole point of this method.
298 protected final void throwObjectContractViolation(Object o1, Object o2)
299 throws IllegalArgumentException {
300 throw new IllegalArgumentException("Equal objects must have equal hashcodes. "
301 + "During rehashing, Trove discovered that "
302 + "the following two objects claim to be "
303 + "equal (as in java.lang.Object.equals()) "
304 + "but their hashCodes (or those calculated by "
305 + "your TObjectHashingStrategy) are not equal."
306 + "This violates the general contract of "
307 + "java.lang.Object.hashCode(). See bullet point two "
308 + "in that method's documentation. "
310 + "; object #2 =" + o2);