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