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%2FStableObjectHash.java;h=8bd6ab2abb8953272a4e1d01a35f901df8902068;hp=5f8de85ddbd275741581c91e98fc0167d5f62bac;hb=HEAD;hpb=969bd23cab98a79ca9101af33334000879fb60c5 diff --git a/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/StableObjectHash.java b/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/StableObjectHash.java index 5f8de85dd..8bd6ab2ab 100644 --- a/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/StableObjectHash.java +++ b/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/StableObjectHash.java @@ -1,481 +1,481 @@ -/******************************************************************************* - * 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; - -/////////////////////////////////////////////////////////////////////////////// -//Copyright (c) 2001, Eric D. Friedman All Rights Reserved. -// -//This library is free software; you can redistribute it and/or -//modify it under the terms of the GNU Lesser General Public -//License as published by the Free Software Foundation; either -//version 2.1 of the License, or (at your option) any later version. -// -//This library is distributed in the hope that it will be useful, -//but WITHOUT ANY WARRANTY; without even the implied warranty of -//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -//GNU General Public License for more details. -// -//You should have received a copy of the GNU Lesser General Public -//License along with this program; if not, write to the Free Software -//Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. -/////////////////////////////////////////////////////////////////////////////// - -import gnu.trove.impl.hash.THash; -import gnu.trove.procedure.TObjectProcedure; -import gnu.trove.strategy.HashingStrategy; - -import java.io.IOException; -import java.io.ObjectInput; -import java.io.ObjectOutput; -import java.util.Arrays; - - -/** -* An open addressed hashing implementation for Object types. -* -* Created: Sun Nov 4 08:56:06 2001 -* -* @author Eric D. Friedman -* @version $Id: TObjectHash.java,v 1.26 2008/05/07 21:25:45 robeden Exp $ -*/ -abstract public class StableObjectHash extends THash - implements HashingStrategy { - - static final long serialVersionUID = -3461112548087185871L; - - - /** the set of Objects */ - protected transient Object[] _set; - - /** the strategy used to hash objects in this collection. */ - protected HashingStrategy _hashingStrategy; - - protected static final Object REMOVED = new Object(), FREE = new Object(); - - /** - * Creates a new TObjectHash instance with the - * default capacity and load factor. - */ - public StableObjectHash() { - super(DEFAULT_CAPACITY, 0.75f); - this._hashingStrategy = this; - } - -// /** -// * Creates a new TObjectHash instance with the -// * default capacity and load factor and a custom hashing strategy. -// * -// * @param strategy used to compute hash codes and to compare objects. -// */ -// public StableObjectHash(TObjectHashingStrategy strategy) { -// super(); -// this._hashingStrategy = strategy; -// } -// -// /** -// * Creates a new TObjectHash instance whose capacity -// * is the next highest prime above initialCapacity + 1 -// * unless that value is already prime. -// * -// * @param initialCapacity an int value -// */ -// public StableObjectHash(int initialCapacity) { -// super(initialCapacity); -// this._hashingStrategy = this; -// } -// -// /** -// * Creates a new TObjectHash instance whose capacity -// * is the next highest prime above initialCapacity + 1 -// * unless that value is already prime. Uses the specified custom -// * hashing strategy. -// * -// * @param initialCapacity an int value -// * @param strategy used to compute hash codes and to compare objects. -// */ -// public StableObjectHash(int initialCapacity, TObjectHashingStrategy strategy) { -// super(initialCapacity); -// this._hashingStrategy = strategy; -// } -// -// /** -// * Creates a new TObjectHash instance with a prime -// * value at or near the specified capacity and load factor. -// * -// * @param initialCapacity used to find a prime capacity for the table. -// * @param loadFactor used to calculate the threshold over which -// * rehashing takes place. -// */ -// public StableObjectHash(int initialCapacity, float loadFactor) { -// super(initialCapacity, loadFactor); -// this._hashingStrategy = this; -// } -// -// /** -// * Creates a new TObjectHash instance with a prime -// * value at or near the specified capacity and load factor. Uses -// * the specified custom hashing strategy. -// * -// * @param initialCapacity used to find a prime capacity for the table. -// * @param loadFactor used to calculate the threshold over which -// * rehashing takes place. -// * @param strategy used to compute hash codes and to compare objects. -// */ -// public StableObjectHash(int initialCapacity, float loadFactor, TObjectHashingStrategy strategy) { -// super(initialCapacity, loadFactor); -// this._hashingStrategy = strategy; -// } - - /** - * @return a shallow clone of this collection - */ - public StableObjectHash clone() { - StableObjectHash h; - try { - h = (StableObjectHash)super.clone(); - } catch (CloneNotSupportedException e) { - // It's supported - throw new Error(e); - } - h._set = (Object[])this._set.clone(); - return h; - } - - 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 - */ - protected int setUp(int initialCapacity) { - int capacity; - - capacity = super.setUp(initialCapacity); - _set = new Object[capacity]; - Arrays.fill(_set,FREE); - return capacity; - } - - /** - * Executes procedure for each element in the set. - * - * @param procedure a TObjectProcedure value - * @return false if the loop over the set terminated because - * the procedure returned false for some value. - */ - public boolean forEach(TObjectProcedure procedure) { - Object[] set = _set; - for (int i = set.length; i-- > 0;) { - if (set[i] != FREE - && set[i] != REMOVED - && ! procedure.execute((T) set[i])) { - return false; - } - } - return true; - } - - /** - * Searches the set for obj - * - * @param obj an Object value - * @return a boolean value - */ - public boolean contains(Object obj) { - throw new UnsupportedOperationException(); - } - - /** - * Locates the index of obj. - * - * @param obj an Object value - * @return the index of obj or -1 if it isn't in the set. - */ - protected int index(T obj, Object[] _set) { - - final Object[] set = _set; - final int length = set.length; - final int hash = obj.hashCode() & 0x7fffffff; - int index = hash % length; - Object cur = set[index]; - - if ( cur == FREE ) return -1; - - // NOTE: here it has to be REMOVED or FULL (some user-given value) - if ( cur == REMOVED || !obj.equals(cur)) { - // see Knuth, p. 529 - final int probe = 1 + (hash % (length - 2)); - - do { - index -= probe; - if (index < 0) { - index += length; - } - cur = set[index]; - } while (cur != FREE - && (cur == REMOVED || !obj.equals(cur))); - } - - return cur == FREE ? -1 : index; - } - - protected int index(T obj, int hash_, Object[] _set) { - - final Object[] set = _set; - final int length = set.length; - final int hash = hash_ & 0x7fffffff; - int index = hash % length; - Object cur = set[index]; - - if ( cur == FREE ) return -1; - - // NOTE: here it has to be REMOVED or FULL (some user-given value) - if ( cur == REMOVED || !obj.equals(cur)) { - // see Knuth, p. 529 - final int probe = 1 + (hash % (length - 2)); - - do { - index -= probe; - if (index < 0) { - index += length; - } - cur = set[index]; - } while (cur != FREE - && (cur == REMOVED || !obj.equals(cur))); - } - - return cur == FREE ? -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. - */ - protected int insertionIndex(T obj) { - - final Object[] set = _set; - final int length = set.length; - final int hash = obj.hashCode() & 0x7fffffff; - int index = hash % length; - Object cur = set[index]; - - if (cur == FREE) { - return index; // empty, all done - } else if (cur != REMOVED && obj.equals((T) cur)) { - 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 != FREE - && cur != REMOVED - && ! obj.equals((T) cur)); - } - - // 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 != FREE - && (cur == REMOVED || ! obj.equals((T) cur))) { - index -= probe; - if (index < 0) { - index += length; - } - cur = set[index]; - } - // NOTE: cur cannot == REMOVED in this block - return (cur != FREE) ? -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 != FREE) ? -index -1 : index; - } - } - - protected int insertionIndex(T obj, int hash_) { - - final Object[] set = _set; - final int length = set.length; - final int hash = hash_ & 0x7fffffff; - int index = hash % length; - Object cur = set[index]; - - if (cur == FREE) { - return index; // empty, all done - } else if (cur != REMOVED && obj.equals((T) cur)) { - 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 != FREE - && cur != REMOVED - && ! obj.equals((T) cur)); - } - - // 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 != FREE - && (cur == REMOVED || ! obj.equals((T) cur))) { - index -= probe; - if (index < 0) { - index += length; - } - cur = set[index]; - } - // NOTE: cur cannot == REMOVED in this block - return (cur != FREE) ? -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 != FREE) ? -index -1 : index; - } - } - - /** - * This is the default implementation of TObjectHashingStrategy: - * it delegates hashing to the Object's hashCode method. - * - * @param o for which the hashcode is to be computed - * @return the hashCode - * @see Object#hashCode() - */ - public final int computeHashCode(T o) { - return o == null ? 0 : o.hashCode(); - } - - /** - * This is the default implementation of TObjectHashingStrategy: - * it delegates equality comparisons to the first parameter's - * equals() method. - * - * @param o1 an Object value - * @param o2 an Object value - * @return true if the objects are equal - * @see Object#equals(Object) - */ - public final boolean equals(T o1, T o2) { - return o1 == null ? o2 == null : o1.equals(o2); - } - - /** - * 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 #2 =" + o2); - } - - - @Override - public void writeExternal( ObjectOutput out ) throws IOException { - super.writeExternal( out ); - - // VERSION - out.writeByte( 0 ); - - // HASHING STRATEGY - out.writeObject( _hashingStrategy ); - } - - @Override - public void readExternal( ObjectInput in ) - throws IOException, ClassNotFoundException { - - super.readExternal( in ); - - // VERSION - in.readByte(); - - // HASHING STRATEGY - //noinspection unchecked - _hashingStrategy = ( HashingStrategy ) in.readObject(); - } -} // 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; + +/////////////////////////////////////////////////////////////////////////////// +//Copyright (c) 2001, Eric D. Friedman All Rights Reserved. +// +//This library is free software; you can redistribute it and/or +//modify it under the terms of the GNU Lesser General Public +//License as published by the Free Software Foundation; either +//version 2.1 of the License, or (at your option) any later version. +// +//This library is distributed in the hope that it will be useful, +//but WITHOUT ANY WARRANTY; without even the implied warranty of +//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +//GNU General Public License for more details. +// +//You should have received a copy of the GNU Lesser General Public +//License along with this program; if not, write to the Free Software +//Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +/////////////////////////////////////////////////////////////////////////////// + +import gnu.trove.impl.hash.THash; +import gnu.trove.procedure.TObjectProcedure; +import gnu.trove.strategy.HashingStrategy; + +import java.io.IOException; +import java.io.ObjectInput; +import java.io.ObjectOutput; +import java.util.Arrays; + + +/** +* An open addressed hashing implementation for Object types. +* +* Created: Sun Nov 4 08:56:06 2001 +* +* @author Eric D. Friedman +* @version $Id: TObjectHash.java,v 1.26 2008/05/07 21:25:45 robeden Exp $ +*/ +abstract public class StableObjectHash extends THash + implements HashingStrategy { + + static final long serialVersionUID = -3461112548087185871L; + + + /** the set of Objects */ + protected transient Object[] _set; + + /** the strategy used to hash objects in this collection. */ + protected HashingStrategy _hashingStrategy; + + protected static final Object REMOVED = new Object(), FREE = new Object(); + + /** + * Creates a new TObjectHash instance with the + * default capacity and load factor. + */ + public StableObjectHash() { + super(DEFAULT_CAPACITY, 0.75f); + this._hashingStrategy = this; + } + +// /** +// * Creates a new TObjectHash instance with the +// * default capacity and load factor and a custom hashing strategy. +// * +// * @param strategy used to compute hash codes and to compare objects. +// */ +// public StableObjectHash(TObjectHashingStrategy strategy) { +// super(); +// this._hashingStrategy = strategy; +// } +// +// /** +// * Creates a new TObjectHash instance whose capacity +// * is the next highest prime above initialCapacity + 1 +// * unless that value is already prime. +// * +// * @param initialCapacity an int value +// */ +// public StableObjectHash(int initialCapacity) { +// super(initialCapacity); +// this._hashingStrategy = this; +// } +// +// /** +// * Creates a new TObjectHash instance whose capacity +// * is the next highest prime above initialCapacity + 1 +// * unless that value is already prime. Uses the specified custom +// * hashing strategy. +// * +// * @param initialCapacity an int value +// * @param strategy used to compute hash codes and to compare objects. +// */ +// public StableObjectHash(int initialCapacity, TObjectHashingStrategy strategy) { +// super(initialCapacity); +// this._hashingStrategy = strategy; +// } +// +// /** +// * Creates a new TObjectHash instance with a prime +// * value at or near the specified capacity and load factor. +// * +// * @param initialCapacity used to find a prime capacity for the table. +// * @param loadFactor used to calculate the threshold over which +// * rehashing takes place. +// */ +// public StableObjectHash(int initialCapacity, float loadFactor) { +// super(initialCapacity, loadFactor); +// this._hashingStrategy = this; +// } +// +// /** +// * Creates a new TObjectHash instance with a prime +// * value at or near the specified capacity and load factor. Uses +// * the specified custom hashing strategy. +// * +// * @param initialCapacity used to find a prime capacity for the table. +// * @param loadFactor used to calculate the threshold over which +// * rehashing takes place. +// * @param strategy used to compute hash codes and to compare objects. +// */ +// public StableObjectHash(int initialCapacity, float loadFactor, TObjectHashingStrategy strategy) { +// super(initialCapacity, loadFactor); +// this._hashingStrategy = strategy; +// } + + /** + * @return a shallow clone of this collection + */ + public StableObjectHash clone() { + StableObjectHash h; + try { + h = (StableObjectHash)super.clone(); + } catch (CloneNotSupportedException e) { + // It's supported + throw new Error(e); + } + h._set = (Object[])this._set.clone(); + return h; + } + + 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 + */ + protected int setUp(int initialCapacity) { + int capacity; + + capacity = super.setUp(initialCapacity); + _set = new Object[capacity]; + Arrays.fill(_set,FREE); + return capacity; + } + + /** + * Executes procedure for each element in the set. + * + * @param procedure a TObjectProcedure value + * @return false if the loop over the set terminated because + * the procedure returned false for some value. + */ + public boolean forEach(TObjectProcedure procedure) { + Object[] set = _set; + for (int i = set.length; i-- > 0;) { + if (set[i] != FREE + && set[i] != REMOVED + && ! procedure.execute((T) set[i])) { + return false; + } + } + return true; + } + + /** + * Searches the set for obj + * + * @param obj an Object value + * @return a boolean value + */ + public boolean contains(Object obj) { + throw new UnsupportedOperationException(); + } + + /** + * Locates the index of obj. + * + * @param obj an Object value + * @return the index of obj or -1 if it isn't in the set. + */ + protected int index(T obj, Object[] _set) { + + final Object[] set = _set; + final int length = set.length; + final int hash = obj.hashCode() & 0x7fffffff; + int index = hash % length; + Object cur = set[index]; + + if ( cur == FREE ) return -1; + + // NOTE: here it has to be REMOVED or FULL (some user-given value) + if ( cur == REMOVED || !obj.equals(cur)) { + // see Knuth, p. 529 + final int probe = 1 + (hash % (length - 2)); + + do { + index -= probe; + if (index < 0) { + index += length; + } + cur = set[index]; + } while (cur != FREE + && (cur == REMOVED || !obj.equals(cur))); + } + + return cur == FREE ? -1 : index; + } + + protected int index(T obj, int hash_, Object[] _set) { + + final Object[] set = _set; + final int length = set.length; + final int hash = hash_ & 0x7fffffff; + int index = hash % length; + Object cur = set[index]; + + if ( cur == FREE ) return -1; + + // NOTE: here it has to be REMOVED or FULL (some user-given value) + if ( cur == REMOVED || !obj.equals(cur)) { + // see Knuth, p. 529 + final int probe = 1 + (hash % (length - 2)); + + do { + index -= probe; + if (index < 0) { + index += length; + } + cur = set[index]; + } while (cur != FREE + && (cur == REMOVED || !obj.equals(cur))); + } + + return cur == FREE ? -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. + */ + protected int insertionIndex(T obj) { + + final Object[] set = _set; + final int length = set.length; + final int hash = obj.hashCode() & 0x7fffffff; + int index = hash % length; + Object cur = set[index]; + + if (cur == FREE) { + return index; // empty, all done + } else if (cur != REMOVED && obj.equals((T) cur)) { + 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 != FREE + && cur != REMOVED + && ! obj.equals((T) cur)); + } + + // 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 != FREE + && (cur == REMOVED || ! obj.equals((T) cur))) { + index -= probe; + if (index < 0) { + index += length; + } + cur = set[index]; + } + // NOTE: cur cannot == REMOVED in this block + return (cur != FREE) ? -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 != FREE) ? -index -1 : index; + } + } + + protected int insertionIndex(T obj, int hash_) { + + final Object[] set = _set; + final int length = set.length; + final int hash = hash_ & 0x7fffffff; + int index = hash % length; + Object cur = set[index]; + + if (cur == FREE) { + return index; // empty, all done + } else if (cur != REMOVED && obj.equals((T) cur)) { + 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 != FREE + && cur != REMOVED + && ! obj.equals((T) cur)); + } + + // 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 != FREE + && (cur == REMOVED || ! obj.equals((T) cur))) { + index -= probe; + if (index < 0) { + index += length; + } + cur = set[index]; + } + // NOTE: cur cannot == REMOVED in this block + return (cur != FREE) ? -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 != FREE) ? -index -1 : index; + } + } + + /** + * This is the default implementation of TObjectHashingStrategy: + * it delegates hashing to the Object's hashCode method. + * + * @param o for which the hashcode is to be computed + * @return the hashCode + * @see Object#hashCode() + */ + public final int computeHashCode(T o) { + return o == null ? 0 : o.hashCode(); + } + + /** + * This is the default implementation of TObjectHashingStrategy: + * it delegates equality comparisons to the first parameter's + * equals() method. + * + * @param o1 an Object value + * @param o2 an Object value + * @return true if the objects are equal + * @see Object#equals(Object) + */ + public final boolean equals(T o1, T o2) { + return o1 == null ? o2 == null : o1.equals(o2); + } + + /** + * 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 #2 =" + o2); + } + + + @Override + public void writeExternal( ObjectOutput out ) throws IOException { + super.writeExternal( out ); + + // VERSION + out.writeByte( 0 ); + + // HASHING STRATEGY + out.writeObject( _hashingStrategy ); + } + + @Override + public void readExternal( ObjectInput in ) + throws IOException, ClassNotFoundException { + + super.readExternal( in ); + + // VERSION + in.readByte(); + + // HASHING STRATEGY + //noinspection unchecked + _hashingStrategy = ( HashingStrategy ) in.readObject(); + } +} // TObjectHash