-/*******************************************************************************\r
- * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
- * in Industry THTH ry.\r
- * All rights reserved. This program and the accompanying materials\r
- * are made available under the terms of the Eclipse Public License v1.0\r
- * which accompanies this distribution, and is available at\r
- * http://www.eclipse.org/legal/epl-v10.html\r
- *\r
- * Contributors:\r
- * VTT Technical Research Centre of Finland - initial API and implementation\r
- *******************************************************************************/\r
-package org.simantics.db.impl.query;\r
-\r
-import gnu.trove.impl.hash.THash;\r
-\r
-import java.lang.reflect.Array;\r
-\r
-import org.simantics.db.impl.graph.ReadGraphImpl;\r
-\r
-\r
-/**\r
- * An open addressed hashing implementation for Object types.\r
- *\r
- * Created: Sun Nov 4 08:56:06 2001\r
- *\r
- * @author Eric D. Friedman\r
- * @version $Id: BinaryQueryHash.java,v 1.2 2008/03/14 11:38:53 tuoksk Exp $\r
- */\r
-abstract public class BinaryQueryHash<Procedure> extends THash {\r
- static final long serialVersionUID = -3461112548087185871L;\r
-\r
- /** the set of Objects */\r
- protected transient BinaryQuery<Procedure>[] _set;\r
-\r
- protected final BinaryQuery<Procedure> REMOVED = new BinaryQuery<Procedure>(-1, -1) {\r
-\r
- @Override\r
- public void computeForEach(ReadGraphImpl graph, QueryProcessor provider, Object procedure, boolean store) {\r
- throw new Error("Not possible!");\r
- }\r
-\r
- @Override\r
- public void putEntry(QueryProcessor provider) {\r
- throw new Error("Not possible!");\r
- }\r
-\r
- @Override\r
- public BinaryQuery<Procedure> getEntry(QueryProcessor provider) {\r
- throw new Error("Not possible!");\r
- }\r
-\r
- @Override\r
- public void recompute(ReadGraphImpl graph, QueryProcessor provider) {\r
- throw new Error("Not possible!");\r
- }\r
-\r
- @Override\r
- public void removeEntry(QueryProcessor provider) {\r
- throw new Error("Not possible!");\r
- }\r
-\r
-// @Override\r
-// public ICacheEntry2 cachedEntry(Object provider) {\r
-// throw new Error("Not possible!");\r
-// }\r
-//\r
-// @Override\r
-// public void computeForEach(int callerThread, Object provider, ICacheEntry2 parent, Object procedure) {\r
-// throw new Error("Not possible!");\r
-// }\r
-\r
- @Override\r
- public int type() {\r
- throw new Error("Not possible!");\r
- }\r
-\r
-// @Override\r
-// public void reset() {\r
-// throw new Error("Not possible!");\r
-// }\r
-\r
- @Override\r
- public void performFromCache(ReadGraphImpl graph, QueryProcessor provider,\r
- Procedure procedure) {\r
- throw new Error("Not possible!");\r
- }\r
-\r
-// @Override\r
-// public void performFromCache(int callerThread, Object provider,\r
-// Object procedure) {\r
-// throw new Error("Not possible!");\r
-// }\r
-\r
- @Override\r
- public void performFromCache(ReadGraphImpl graph, Object provider,\r
- Object procedure) {\r
- throw new Error("Not possible!");\r
- }\r
- \r
- };\r
-\r
- /**\r
- * Creates a new <code>TObjectHash</code> instance with the\r
- * default capacity and load factor.\r
- */\r
- public BinaryQueryHash() {\r
- super(DEFAULT_CAPACITY, 0.75f);\r
- }\r
-\r
- public int capacity() {\r
- return _set.length;\r
- }\r
-\r
- protected void removeAt(int index) {\r
- _set[index] = REMOVED;\r
- super.removeAt(index);\r
- }\r
-\r
- /**\r
- * initializes the Object set of this hash table.\r
- *\r
- * @param initialCapacity an <code>int</code> value\r
- * @return an <code>int</code> value\r
- */\r
- @SuppressWarnings("unchecked")\r
- protected int setUp(int initialCapacity) {\r
- int capacity;\r
-\r
- capacity = super.setUp(initialCapacity);\r
- _set = (BinaryQuery[])Array.newInstance(BinaryQuery.class, capacity);\r
- return capacity;\r
- \r
- }\r
-\r
- final protected int index(final long id) {\r
-\r
- final BinaryQuery<Procedure>[] set = _set;\r
- final int length = set.length;\r
- final int hash = ((31 * ((int)(id>>>32)) + (int)id) )& 0x7fffffff;\r
- int index = hash % length;\r
- BinaryQuery<Procedure> cur = set[index];\r
-\r
- if ( cur == null ) return -1;\r
-\r
- // NOTE: here it has to be REMOVED or FULL (some user-given value)\r
- if ( cur == REMOVED || !(id == cur.id)) {\r
- // see Knuth, p. 529\r
- final int probe = 1 + (hash % (length - 2));\r
-\r
- do {\r
- index -= probe;\r
- if (index < 0) {\r
- index += length;\r
- }\r
- cur = set[index];\r
- } while (cur != null\r
- && (cur == REMOVED || !(id == cur.id)));\r
- }\r
-\r
- return cur == null ? -1 : index;\r
- \r
- }\r
- \r
-\r
- /**\r
- * Locates the index at which <tt>obj</tt> can be inserted. if\r
- * there is already a value equal()ing <tt>obj</tt> in the set,\r
- * returns that value's index as <tt>-index - 1</tt>.\r
- *\r
- * @param obj an <code>Object</code> value\r
- * @return the index of a FREE slot at which obj can be inserted\r
- * or, if obj is already stored in the hash, the negative value of\r
- * that index, minus 1: -index -1.\r
- */\r
- final protected int insertionIndex(final long id) {\r
-\r
- final BinaryQuery<Procedure>[] set = _set;\r
- final int length = set.length;\r
- final int hash = (31 * ((int)(id>>>32)) + (int)id) & 0x7fffffff;\r
- int index = hash % length;\r
- BinaryQuery<Procedure> cur = set[index];\r
-\r
- if (cur == null) {\r
- return index; // empty, all done\r
- } else if (cur != REMOVED && (id == cur.id)) {\r
- return -index -1; // already stored\r
- } else { // already FULL or REMOVED, must probe\r
- // compute the double hash\r
- final int probe = 1 + (hash % (length - 2));\r
-\r
- // if the slot we landed on is FULL (but not removed), probe\r
- // until we find an empty slot, a REMOVED slot, or an element\r
- // equal to the one we are trying to insert.\r
- // finding an empty slot means that the value is not present\r
- // and that we should use that slot as the insertion point;\r
- // finding a REMOVED slot means that we need to keep searching,\r
- // however we want to remember the offset of that REMOVED slot\r
- // so we can reuse it in case a "new" insertion (i.e. not an update)\r
- // is possible.\r
- // finding a matching value means that we've found that our desired\r
- // key is already in the table\r
- if (cur != REMOVED) {\r
- // starting at the natural offset, probe until we find an\r
- // offset that isn't full.\r
- do {\r
- index -= probe;\r
- if (index < 0) {\r
- index += length;\r
- }\r
- cur = set[index];\r
- } while (cur != null\r
- && cur != REMOVED\r
- && ! (id == cur.id));\r
- }\r
-\r
- // if the index we found was removed: continue probing until we\r
- // locate a free location or an element which equal()s the\r
- // one we have.\r
- if (cur == REMOVED) {\r
- int firstRemoved = index;\r
- while (cur != null\r
- && (cur == REMOVED || ! (id == cur.id))) {\r
- index -= probe;\r
- if (index < 0) {\r
- index += length;\r
- }\r
- cur = set[index];\r
- }\r
- // NOTE: cur cannot == REMOVED in this block\r
- return (cur != null) ? -index -1 : firstRemoved;\r
- }\r
- // if it's full, the key is already stored\r
- // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)\r
- return (cur != null) ? -index -1 : index;\r
- }\r
- }\r
-\r
- /**\r
- * Convenience methods for subclasses to use in throwing exceptions about\r
- * badly behaved user objects employed as keys. We have to throw an\r
- * IllegalArgumentException with a rather verbose message telling the\r
- * user that they need to fix their object implementation to conform\r
- * to the general contract for java.lang.Object.\r
- *\r
- * @param o1 the first of the equal elements with unequal hash codes.\r
- * @param o2 the second of the equal elements with unequal hash codes.\r
- * @exception IllegalArgumentException the whole point of this method.\r
- */\r
- protected final void throwObjectContractViolation(Object o1, Object o2)\r
- throws IllegalArgumentException {\r
- throw new IllegalArgumentException("Equal objects must have equal hashcodes. "\r
- + "During rehashing, Trove discovered that "\r
- + "the following two objects claim to be "\r
- + "equal (as in java.lang.Object.equals()) "\r
- + "but their hashCodes (or those calculated by "\r
- + "your TObjectHashingStrategy) are not equal."\r
- + "This violates the general contract of "\r
- + "java.lang.Object.hashCode(). See bullet point two "\r
- + "in that method's documentation. "\r
- + "object #1 =" + o1 + " object #1 hash = " + o1.hashCode() + " object #1 id = " + System.identityHashCode(o1)\r
- + "; object #2 =" + o2 + " object #2 hash = " + o2.hashCode() + " object #2 id = " + System.identityHashCode(o2));\r
- }\r
-} // TObjectHash\r
+/*******************************************************************************
+ * Copyright (c) 2007, 2010 Association for Decentralized Information Management
+ * in Industry THTH ry.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * VTT Technical Research Centre of Finland - initial API and implementation
+ *******************************************************************************/
+package org.simantics.db.impl.query;
+
+import gnu.trove.impl.hash.THash;
+
+import java.lang.reflect.Array;
+
+import org.simantics.db.exception.DatabaseException;
+import org.simantics.db.impl.graph.ReadGraphImpl;
+
+
+/**
+ * An open addressed hashing implementation for Object types.
+ *
+ * Created: Sun Nov 4 08:56:06 2001
+ *
+ * @author Eric D. Friedman
+ * @version $Id: BinaryQueryHash.java,v 1.2 2008/03/14 11:38:53 tuoksk Exp $
+ */
+abstract public class BinaryQueryHash<Procedure> extends THash {
+ static final long serialVersionUID = -3461112548087185871L;
+
+ /** the set of Objects */
+ protected transient BinaryQuery<Procedure>[] _set;
+
+ protected final BinaryQuery<Procedure> REMOVED = new BinaryQuery<Procedure>(-1, -1) {
+
+ @Override
+ public void removeEntry(QueryProcessor provider) {
+ throw new Error("Not possible!");
+ }
+
+ @Override
+ public int type() {
+ throw new Error("Not possible!");
+ }
+
+ @Override
+ Object performFromCache(ReadGraphImpl graph, Procedure procedure) throws DatabaseException {
+ throw new Error("Not possible!");
+ }
+
+ @Override
+ public void recompute(ReadGraphImpl graph) throws DatabaseException {
+ throw new Error("Not possible!");
+ }
+
+ };
+
+ /**
+ * Creates a new <code>TObjectHash</code> instance with the
+ * default capacity and load factor.
+ */
+ public BinaryQueryHash() {
+ super(DEFAULT_CAPACITY, 0.75f);
+ }
+
+ public int capacity() {
+ return _set.length;
+ }
+
+ protected void removeAt(int index) {
+ _set[index] = REMOVED;
+ super.removeAt(index);
+ }
+
+ /**
+ * initializes the Object set of this hash table.
+ *
+ * @param initialCapacity an <code>int</code> value
+ * @return an <code>int</code> value
+ */
+ @SuppressWarnings("unchecked")
+ protected int setUp(int initialCapacity) {
+ int capacity;
+
+ capacity = super.setUp(initialCapacity);
+ _set = (BinaryQuery[])Array.newInstance(BinaryQuery.class, capacity);
+ return capacity;
+
+ }
+
+ final protected int index(final long id) {
+
+ final BinaryQuery<Procedure>[] set = _set;
+ final int length = set.length;
+ final int hash = ((31 * ((int)(id>>>32)) + (int)id) )& 0x7fffffff;
+ int index = hash % length;
+ BinaryQuery<Procedure> cur = set[index];
+
+ if ( cur == null ) return -1;
+
+ // NOTE: here it has to be REMOVED or FULL (some user-given value)
+ if ( cur == REMOVED || !(id == cur.id)) {
+ // see Knuth, p. 529
+ final int probe = 1 + (hash % (length - 2));
+
+ do {
+ index -= probe;
+ if (index < 0) {
+ index += length;
+ }
+ cur = set[index];
+ } while (cur != null
+ && (cur == REMOVED || !(id == cur.id)));
+ }
+
+ return cur == null ? -1 : index;
+
+ }
+
+
+ /**
+ * Locates the index at which <tt>obj</tt> can be inserted. if
+ * there is already a value equal()ing <tt>obj</tt> in the set,
+ * returns that value's index as <tt>-index - 1</tt>.
+ *
+ * @param obj an <code>Object</code> value
+ * @return the index of a FREE slot at which obj can be inserted
+ * or, if obj is already stored in the hash, the negative value of
+ * that index, minus 1: -index -1.
+ */
+ final protected int insertionIndex(final long id) {
+
+ final BinaryQuery<Procedure>[] set = _set;
+ final int length = set.length;
+ final int hash = (31 * ((int)(id>>>32)) + (int)id) & 0x7fffffff;
+ int index = hash % length;
+ BinaryQuery<Procedure> cur = set[index];
+
+ if (cur == null) {
+ return index; // empty, all done
+ } else if (cur != REMOVED && (id == cur.id)) {
+ return -index -1; // already stored
+ } else { // already FULL or REMOVED, must probe
+ // compute the double hash
+ final int probe = 1 + (hash % (length - 2));
+
+ // if the slot we landed on is FULL (but not removed), probe
+ // until we find an empty slot, a REMOVED slot, or an element
+ // equal to the one we are trying to insert.
+ // finding an empty slot means that the value is not present
+ // and that we should use that slot as the insertion point;
+ // finding a REMOVED slot means that we need to keep searching,
+ // however we want to remember the offset of that REMOVED slot
+ // so we can reuse it in case a "new" insertion (i.e. not an update)
+ // is possible.
+ // finding a matching value means that we've found that our desired
+ // key is already in the table
+ if (cur != REMOVED) {
+ // starting at the natural offset, probe until we find an
+ // offset that isn't full.
+ do {
+ index -= probe;
+ if (index < 0) {
+ index += length;
+ }
+ cur = set[index];
+ } while (cur != null
+ && cur != REMOVED
+ && ! (id == cur.id));
+ }
+
+ // if the index we found was removed: continue probing until we
+ // locate a free location or an element which equal()s the
+ // one we have.
+ if (cur == REMOVED) {
+ int firstRemoved = index;
+ while (cur != null
+ && (cur == REMOVED || ! (id == cur.id))) {
+ index -= probe;
+ if (index < 0) {
+ index += length;
+ }
+ cur = set[index];
+ }
+ // NOTE: cur cannot == REMOVED in this block
+ return (cur != null) ? -index -1 : firstRemoved;
+ }
+ // if it's full, the key is already stored
+ // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)
+ return (cur != null) ? -index -1 : index;
+ }
+ }
+
+ /**
+ * Convenience methods for subclasses to use in throwing exceptions about
+ * badly behaved user objects employed as keys. We have to throw an
+ * IllegalArgumentException with a rather verbose message telling the
+ * user that they need to fix their object implementation to conform
+ * to the general contract for java.lang.Object.
+ *
+ * @param o1 the first of the equal elements with unequal hash codes.
+ * @param o2 the second of the equal elements with unequal hash codes.
+ * @exception IllegalArgumentException the whole point of this method.
+ */
+ protected final void throwObjectContractViolation(Object o1, Object o2)
+ throws IllegalArgumentException {
+ throw new IllegalArgumentException("Equal objects must have equal hashcodes. "
+ + "During rehashing, Trove discovered that "
+ + "the following two objects claim to be "
+ + "equal (as in java.lang.Object.equals()) "
+ + "but their hashCodes (or those calculated by "
+ + "your TObjectHashingStrategy) are not equal."
+ + "This violates the general contract of "
+ + "java.lang.Object.hashCode(). See bullet point two "
+ + "in that method's documentation. "
+ + "object #1 =" + o1 + " object #1 hash = " + o1.hashCode() + " object #1 id = " + System.identityHashCode(o1)
+ + "; object #2 =" + o2 + " object #2 hash = " + o2.hashCode() + " object #2 id = " + System.identityHashCode(o2));
+ }
+} // TObjectHash
Code Review / simantics / platform.git / blobdiff