X-Git-Url: https://gerrit.simantics.org/r/gitweb?p=simantics%2Fplatform.git;a=blobdiff_plain;f=bundles%2Forg.simantics.db.impl%2Fsrc%2Forg%2Fsimantics%2Fdb%2Fimpl%2Fquery%2FBinaryQueryHash.java;h=b460a22bd06762b5d4b253b470813b9a92bc7875;hp=331e0591b58390ef227d9bfbf5af1a65cb82cda1;hb=0d9b90834ce56b292c00b1a39850ed842c3e4d42;hpb=969bd23cab98a79ca9101af33334000879fb60c5 diff --git a/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/BinaryQueryHash.java b/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/BinaryQueryHash.java index 331e0591b..b460a22bd 100644 --- a/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/BinaryQueryHash.java +++ b/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/BinaryQueryHash.java @@ -1,263 +1,221 @@ -/******************************************************************************* - * 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.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 extends THash { - static final long serialVersionUID = -3461112548087185871L; - - /** the set of Objects */ - protected transient BinaryQuery[] _set; - - protected final BinaryQuery REMOVED = new BinaryQuery(-1, -1) { - - @Override - public void computeForEach(ReadGraphImpl graph, QueryProcessor provider, Object procedure, boolean store) { - throw new Error("Not possible!"); - } - - @Override - public void putEntry(QueryProcessor provider) { - throw new Error("Not possible!"); - } - - @Override - public BinaryQuery getEntry(QueryProcessor provider) { - throw new Error("Not possible!"); - } - - @Override - public void recompute(ReadGraphImpl graph, QueryProcessor provider) { - throw new Error("Not possible!"); - } - - @Override - public void removeEntry(QueryProcessor provider) { - throw new Error("Not possible!"); - } - -// @Override -// public ICacheEntry2 cachedEntry(Object provider) { -// throw new Error("Not possible!"); -// } -// -// @Override -// public void computeForEach(int callerThread, Object provider, ICacheEntry2 parent, Object procedure) { -// throw new Error("Not possible!"); -// } - - @Override - public int type() { - throw new Error("Not possible!"); - } - -// @Override -// public void reset() { -// throw new Error("Not possible!"); -// } - - @Override - public void performFromCache(ReadGraphImpl graph, QueryProcessor provider, - Procedure procedure) { - throw new Error("Not possible!"); - } - -// @Override -// public void performFromCache(int callerThread, Object provider, -// Object procedure) { -// throw new Error("Not possible!"); -// } - - @Override - public void performFromCache(ReadGraphImpl graph, Object provider, - Object procedure) { - throw new Error("Not possible!"); - } - - }; - - /** - * Creates a new TObjectHash 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 int value - * @return an int 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[] set = _set; - final int length = set.length; - final int hash = ((31 * ((int)(id>>>32)) + (int)id) )& 0x7fffffff; - int index = hash % length; - BinaryQuery 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 obj can be inserted. if - * there is already a value equal()ing obj in the set, - * returns that value's index as -index - 1. - * - * @param obj an Object 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[] set = _set; - final int length = set.length; - final int hash = (31 * ((int)(id>>>32)) + (int)id) & 0x7fffffff; - int index = hash % length; - BinaryQuery 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 +/******************************************************************************* + * 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 extends THash { + static final long serialVersionUID = -3461112548087185871L; + + /** the set of Objects */ + protected transient BinaryQuery[] _set; + + protected final BinaryQuery REMOVED = new BinaryQuery(-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 TObjectHash 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 int value + * @return an int 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[] set = _set; + final int length = set.length; + final int hash = ((31 * ((int)(id>>>32)) + (int)id) )& 0x7fffffff; + int index = hash % length; + BinaryQuery 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 obj can be inserted. if + * there is already a value equal()ing obj in the set, + * returns that value's index as -index - 1. + * + * @param obj an Object 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[] set = _set; + final int length = set.length; + final int hash = (31 * ((int)(id>>>32)) + (int)id) & 0x7fffffff; + int index = hash % length; + BinaryQuery 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