-/*******************************************************************************\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.function.TObjectFunction;\r
-import gnu.trove.procedure.TObjectObjectProcedure;\r
-import gnu.trove.procedure.TObjectProcedure;\r
-\r
-import java.io.Externalizable;\r
-import java.util.ArrayList;\r
-import java.util.Arrays;\r
-import java.util.Collection;\r
-import java.util.Iterator;\r
-import java.util.Map;\r
-import java.util.Set;\r
-\r
-/**\r
- * An implementation of the Map interface which uses an open addressed\r
- * hash table to store its contents.\r
- *\r
- * Created: Sun Nov 4 08:52:45 2001\r
- *\r
- * @author Eric D. Friedman\r
- * @version $Id: THashMap.java,v 1.33 2008/05/08 17:42:55 robeden Exp $\r
- */\r
-public class StableHashMap<K,V> extends StableObjectHash<K> implements Map<K,V>, Externalizable {\r
- static final long serialVersionUID = 1L;\r
-\r
- /** the values of the map */\r
- protected transient V[] _values;\r
-\r
- /**\r
- * Creates a new <code>THashMap</code> instance with the default\r
- * capacity and load factor.\r
- */\r
- public StableHashMap() {\r
- super();\r
- }\r
-\r
-// /**\r
-// * Creates a new <code>THashMap</code> instance with a prime\r
-// * capacity equal to or greater than <tt>initialCapacity</tt> and\r
-// * with the default load factor.\r
-// *\r
-// * @param initialCapacity an <code>int</code> value\r
-// */\r
-// public StableHashMap(int initialCapacity) {\r
-// super(initialCapacity);\r
-// }\r
-\r
-// /**\r
-// * Creates a new <code>THashMap</code> instance with a prime\r
-// * capacity equal to or greater than <tt>initialCapacity</tt> and\r
-// * with the default load factor.\r
-// *\r
-// * @param initialCapacity an <code>int</code> value\r
-// * @param strategy used to compute hash codes and to compare objects.\r
-// */\r
-// public StableHashMap(int initialCapacity, TObjectHashingStrategy<K> strategy) {\r
-// super(initialCapacity, strategy);\r
-// }\r
-\r
-// /**\r
-// * Creates a new <code>THashMap</code> instance with a prime\r
-// * capacity equal to or greater than <tt>initialCapacity</tt> and\r
-// * with the specified load factor.\r
-// *\r
-// * @param initialCapacity an <code>int</code> value\r
-// * @param loadFactor a <code>float</code> value\r
-// */\r
-// public StableHashMap(int initialCapacity, float loadFactor) {\r
-// super(initialCapacity, loadFactor);\r
-// }\r
-\r
-// /**\r
-// * Creates a new <code>THashMap</code> instance with a prime\r
-// * capacity equal to or greater than <tt>initialCapacity</tt> and\r
-// * with the specified load factor.\r
-// *\r
-// * @param initialCapacity an <code>int</code> value\r
-// * @param loadFactor a <code>float</code> value\r
-// * @param strategy used to compute hash codes and to compare objects.\r
-// */\r
-// public StableHashMap(int initialCapacity, float loadFactor, TObjectHashingStrategy<K> strategy) {\r
-// super(initialCapacity, loadFactor, strategy);\r
-// }\r
-\r
-// /**\r
-// * Creates a new <code>THashMap</code> instance which contains the\r
-// * key/value pairs in <tt>map</tt>.\r
-// *\r
-// * @param map a <code>Map</code> value\r
-// */\r
-// public StableHashMap(Map<K,V> map) {\r
-// this(map.size());\r
-// putAll(map);\r
-// }\r
-//\r
-// /**\r
-// * Creates a new <code>THashMap</code> instance which contains the\r
-// * key/value pairs in <tt>map</tt>.\r
-// *\r
-// * @param map a <code>Map</code> value\r
-// * @param strategy used to compute hash codes and to compare objects.\r
-// */\r
-// public StableHashMap(Map<K,V> map, TObjectHashingStrategy<K> strategy) {\r
-// this(map.size(), strategy);\r
-// putAll(map);\r
-// }\r
-\r
- /**\r
- * @return a shallow clone of this collection\r
- */\r
- public StableHashMap<K,V> clone() {\r
- StableHashMap<K,V> m = (StableHashMap<K,V>)super.clone();\r
- m._values = this._values.clone();\r
- return m;\r
- }\r
-\r
- /**\r
- * initialize the value array of the map.\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
- //noinspection unchecked\r
- _values = (V[]) new Object[capacity];\r
- return capacity;\r
- }\r
-\r
- /**\r
- * Inserts a key/value pair into the map.\r
- *\r
- * @param key an <code>Object</code> value\r
- * @param value an <code>Object</code> value\r
- * @return the previous value associated with <tt>key</tt>,\r
- * or {@code null} if none was found.\r
- */\r
- public V put(K key, V value) {\r
- int index = insertionIndex(key);\r
- return doPut(key, value, index);\r
- }\r
-\r
- public V put(K key, V value, int hash) {\r
- int index = insertionIndex(key, hash);\r
- return doPut(key, value, index);\r
- }\r
- \r
- /**\r
- * Inserts a key/value pair into the map if the specified key is not already\r
- * associated with a value.\r
- * \r
- * @param key an <code>Object</code> value\r
- * @param value an <code>Object</code> value\r
- * @return the previous value associated with <tt>key</tt>,\r
- * or {@code null} if none was found.\r
- */\r
- public V putIfAbsent(K key, V value) {\r
- int index = insertionIndex(key);\r
- if (index < 0)\r
- return _values[-index - 1];\r
- return doPut(key, value, index);\r
- }\r
-\r
- private V doPut(K key, V value, int index) {\r
- V previous = null;\r
- Object oldKey;\r
- boolean isNewMapping = true;\r
- if (index < 0) {\r
- index = -index -1;\r
- previous = _values[index];\r
- isNewMapping = false;\r
- }\r
- oldKey = _set[index];\r
- _set[index] = key;\r
- _values[index] = value;\r
- if (isNewMapping) {\r
- postInsertHook(oldKey == FREE);\r
- }\r
-\r
- return previous;\r
- }\r
-\r
- /**\r
- * Compares this map with another map for equality of their stored\r
- * entries.\r
- *\r
- * @param other an <code>Object</code> value\r
- * @return a <code>boolean</code> value\r
- */\r
- public boolean equals(Object other) {\r
- if (! (other instanceof Map)) {\r
- return false;\r
- }\r
- Map<K, V> that = (Map<K, V>)other;\r
- if (that.size() != this.size()) {\r
- return false;\r
- }\r
- return forEachEntry(new EqProcedure<K,V>(that));\r
- }\r
-\r
- public int hashCode() {\r
- HashProcedure p = new HashProcedure();\r
- forEachEntry(p);\r
- return p.getHashCode();\r
- }\r
-\r
- public String toString() {\r
- final StringBuilder buf = new StringBuilder("{");\r
- forEachEntry(new TObjectObjectProcedure<K,V>() {\r
- private boolean first = true;\r
- public boolean execute(K key, V value) {\r
- if ( first ) first = false;\r
- else buf.append( "," );\r
-\r
- buf.append(key);\r
- buf.append("=");\r
- buf.append(value);\r
- return true;\r
- }\r
- });\r
- buf.append("}");\r
- return buf.toString();\r
- }\r
-\r
- private final class HashProcedure implements TObjectObjectProcedure<K,V> {\r
- private int h = 0;\r
-\r
- public int getHashCode() {\r
- return h;\r
- }\r
-\r
- public final boolean execute(K key, V value) {\r
- h += _hashingStrategy.computeHashCode(key) ^ (value == null ? 0 : value.hashCode());\r
- return true;\r
- }\r
- }\r
-\r
- private static final class EqProcedure<K,V> implements TObjectObjectProcedure<K,V> {\r
- private final Map<K,V> _otherMap;\r
-\r
- EqProcedure(Map<K,V> otherMap) {\r
- _otherMap = otherMap;\r
- }\r
-\r
- public final boolean execute(K key, V value) {\r
- // Check to make sure the key is there. This avoids problems that come up with\r
- // null values. Since it is only caused in that cause, only do this when the\r
- // value is null (to avoid extra work).\r
- if (value == null && !_otherMap.containsKey(key)) return false;\r
-\r
- V oValue = _otherMap.get(key);\r
- return oValue == value || (oValue != null && oValue.equals(value));\r
- }\r
- }\r
-\r
- /**\r
- * Executes <tt>procedure</tt> for each key in the map.\r
- *\r
- * @param procedure a <code>TObjectProcedure</code> value\r
- * @return false if the loop over the keys terminated because\r
- * the procedure returned false for some key.\r
- */\r
- public boolean forEachKey(TObjectProcedure<K> procedure) {\r
- return forEach(procedure);\r
- }\r
-\r
- /**\r
- * Executes <tt>procedure</tt> for each value in the map.\r
- *\r
- * @param procedure a <code>TObjectProcedure</code> value\r
- * @return false if the loop over the values terminated because\r
- * the procedure returned false for some value.\r
- */\r
- public boolean forEachValue(TObjectProcedure<V> procedure) {\r
- V[] values = _values;\r
- Object[] set = _set;\r
- for (int i = values.length; i-- > 0;) {\r
- if (set[i] != FREE\r
- && set[i] != REMOVED\r
- && ! procedure.execute(values[i])) {\r
- return false;\r
- }\r
- }\r
- return true;\r
- }\r
-\r
- /**\r
- * Executes <tt>procedure</tt> for each key/value entry in the\r
- * map.\r
- *\r
- * @param procedure a <code>TObjectObjectProcedure</code> value\r
- * @return false if the loop over the entries terminated because\r
- * the procedure returned false for some entry.\r
- */\r
- public boolean forEachEntry(TObjectObjectProcedure<K,V> procedure) {\r
- Object[] keys = _set;\r
- V[] values = _values;\r
- for (int i = keys.length; i-- > 0;) {\r
- if (keys[i] != FREE\r
- && keys[i] != REMOVED\r
- && ! procedure.execute((K) keys[i],values[i])) {\r
- return false;\r
- }\r
- }\r
- return true;\r
- }\r
-\r
- /**\r
- * Retains only those entries in the map for which the procedure\r
- * returns a true value.\r
- *\r
- * @param procedure determines which entries to keep\r
- * @return true if the map was modified.\r
- */\r
- public boolean retainEntries(TObjectObjectProcedure<K,V> procedure) {\r
- boolean modified = false;\r
- Object[] keys = _set;\r
- V[] values = _values;\r
-\r
- // Temporarily disable compaction. This is a fix for bug #1738760\r
- tempDisableAutoCompaction();\r
- try {\r
- for (int i = keys.length; i-- > 0;) {\r
- if (keys[i] != FREE\r
- && keys[i] != REMOVED\r
- && ! procedure.execute((K) keys[i],values[i])) {\r
- removeAt(i);\r
- modified = true;\r
- }\r
- }\r
- }\r
- finally {\r
- reenableAutoCompaction(true);\r
- }\r
-\r
- return modified;\r
- }\r
-\r
- /**\r
- * Transform the values in this map using <tt>function</tt>.\r
- *\r
- * @param function a <code>TObjectFunction</code> value\r
- */\r
- public void transformValues(TObjectFunction<V,V> function) {\r
- V[] values = _values;\r
- Object[] set = _set;\r
- for (int i = values.length; i-- > 0;) {\r
- if (set[i] != FREE && set[i] != REMOVED) {\r
- values[i] = function.execute(values[i]);\r
- }\r
- }\r
- }\r
-\r
- /**\r
- * rehashes the map to the new capacity.\r
- *\r
- * @param newCapacity an <code>int</code> value\r
- */\r
- protected void rehash(int newCapacity) {\r
- int oldCapacity = _set.length;\r
- Object oldKeys[] = _set;\r
- V oldVals[] = _values;\r
-\r
- _set = new Object[newCapacity];\r
- Arrays.fill(_set, FREE);\r
- _values = (V[]) new Object[newCapacity];\r
-\r
- for (int i = oldCapacity; i-- > 0;) {\r
- if(oldKeys[i] != FREE && oldKeys[i] != REMOVED) {\r
- Object o = oldKeys[i];\r
- int index = insertionIndex((K) o);\r
- if (index < 0) {\r
- throwObjectContractViolation(_set[(-index -1)], o);\r
- }\r
- _set[index] = o;\r
- _values[index] = oldVals[i];\r
- }\r
- }\r
- }\r
-\r
- /**\r
- * retrieves the value for <tt>key</tt>\r
- *\r
- * @param key an <code>Object</code> value\r
- * @return the value of <tt>key</tt> or null if no such mapping exists.\r
- */\r
- public V get(Object key) {\r
- Object[] set = _set;\r
- V[] values = _values;\r
- int index = index((K) key, set);\r
- return index < 0 ? null : values[index];\r
- }\r
-\r
- public V get(Object key, int hash) {\r
- Object[] set = _set;\r
- V[] values = _values;\r
- int index = index((K) key, hash, set);\r
- return index < 0 ? null : values[index];\r
- }\r
- \r
- /**\r
- * Empties the map.\r
- *\r
- */\r
- public void clear() {\r
- if (size() == 0) return; // optimization\r
-\r
- super.clear();\r
-\r
- Arrays.fill(_set, 0, _set.length, FREE);\r
- Arrays.fill(_values, 0, _values.length, null);\r
- }\r
-\r
- /**\r
- * Deletes a key/value pair from the map.\r
- *\r
- * @param key an <code>Object</code> value\r
- * @return an <code>Object</code> value\r
- */\r
- public V remove(Object key) {\r
- Object[] set = _set;\r
- V[] values = _values;\r
- V prev = null;\r
- int index = index((K) key, set);\r
- if (index >= 0) {\r
- prev = values[index];\r
- removeAt(index); // clear key,state; adjust size\r
- }\r
- return prev;\r
- }\r
- \r
- protected void removeAt(int index) {\r
- _values[index] = null;\r
- super.removeAt(index); // clear key, state; adjust size\r
- }\r
-\r
- /**\r
- * removes the mapping at <tt>index</tt> from the map.\r
- *\r
- * @param index an <code>int</code> value\r
- */\r
- protected void removeAt(int index, V[] values) {\r
- values[index] = null;\r
- super.removeAt(index); // clear key, state; adjust size\r
- }\r
-\r
- public void values(int level, CacheCollectionResult result) {\r
-\r
- for (int i = _set.length; i-- > 0;) {\r
- if(_set[i] != null && _set[i] != REMOVED && _set[i] != FREE) {\r
- CacheEntryBase e = (CacheEntryBase)_values[i];\r
- if(e.getLevel() <= level)\r
- result.add(e);\r
- }\r
- }\r
-\r
- }\r
- \r
- /**\r
- * Returns a view on the values of the map.\r
- *\r
- * @return a <code>Collection</code> value\r
- */\r
- public Collection<V> values() {\r
-\r
- Collection<V> result = new ArrayList<V>();\r
-\r
- for (int i = _set.length; i-- > 0;) {\r
- if(_set[i] != null && _set[i] != REMOVED && _set[i] != FREE) {\r
- result.add((V)_values[i]);\r
- }\r
- }\r
-\r
- return result;\r
- \r
- }\r
-\r
- /**\r
- * returns a Set view on the keys of the map.\r
- *\r
- * @return a <code>Set</code> value\r
- */\r
- public Set<K> keySet() {\r
- throw new UnsupportedOperationException();\r
- }\r
-\r
- /**\r
- * Returns a Set view on the entries of the map.\r
- *\r
- * @return a <code>Set</code> value\r
- */\r
- public Set<Map.Entry<K,V>> entrySet() {\r
- throw new UnsupportedOperationException();\r
- }\r
-\r
- /**\r
- * checks for the presence of <tt>val</tt> in the values of the map.\r
- *\r
- * @param val an <code>Object</code> value\r
- * @return a <code>boolean</code> value\r
- */\r
- public boolean containsValue(Object val) {\r
- Object[] set = _set;\r
- V[] vals = _values;\r
-\r
- // special case null values so that we don't have to\r
- // perform null checks before every call to equals()\r
- if (null == val) {\r
- for (int i = vals.length; i-- > 0;) {\r
- if ((set[i] != FREE && set[i] != REMOVED) &&\r
- val == vals[i]) {\r
- return true;\r
- }\r
- }\r
- } else {\r
- for (int i = vals.length; i-- > 0;) {\r
- if ((set[i] != FREE && set[i] != REMOVED) &&\r
- (val == vals[i] || val.equals(vals[i]))) {\r
- return true;\r
- }\r
- }\r
- } // end of else\r
- return false;\r
- }\r
-\r
- /**\r
- * checks for the present of <tt>key</tt> in the keys of the map.\r
- *\r
- * @param key an <code>Object</code> value\r
- * @return a <code>boolean</code> value\r
- */\r
- public boolean containsKey(Object key) {\r
- return contains(key);\r
- }\r
-\r
- /**\r
- * copies the key/value mappings in <tt>map</tt> into this map.\r
- *\r
- * @param map a <code>Map</code> value\r
- */\r
- public void putAll(Map<? extends K, ? extends V> map) {\r
- ensureCapacity(map.size());\r
- // could optimize this for cases when map instanceof THashMap\r
- for (Iterator<? extends Map.Entry<? extends K,? extends V>> i = map.entrySet().iterator(); i.hasNext();) {\r
- Map.Entry<? extends K,? extends V> e = i.next();\r
- put(e.getKey(),e.getValue());\r
- }\r
- }\r
- \r
-} // THashMap\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;
+
+///////////////////////////////////////////////////////////////////////////////
+//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.function.TObjectFunction;
+import gnu.trove.procedure.TObjectObjectProcedure;
+import gnu.trove.procedure.TObjectProcedure;
+
+import java.io.Externalizable;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * An implementation of the Map interface which uses an open addressed
+ * hash table to store its contents.
+ *
+ * Created: Sun Nov 4 08:52:45 2001
+ *
+ * @author Eric D. Friedman
+ * @version $Id: THashMap.java,v 1.33 2008/05/08 17:42:55 robeden Exp $
+ */
+public class StableHashMap<K,V> extends StableObjectHash<K> implements Map<K,V>, Externalizable {
+ static final long serialVersionUID = 1L;
+
+ /** the values of the map */
+ protected transient V[] _values;
+
+ /**
+ * Creates a new <code>THashMap</code> instance with the default
+ * capacity and load factor.
+ */
+ public StableHashMap() {
+ super();
+ }
+
+// /**
+// * Creates a new <code>THashMap</code> instance with a prime
+// * capacity equal to or greater than <tt>initialCapacity</tt> and
+// * with the default load factor.
+// *
+// * @param initialCapacity an <code>int</code> value
+// */
+// public StableHashMap(int initialCapacity) {
+// super(initialCapacity);
+// }
+
+// /**
+// * Creates a new <code>THashMap</code> instance with a prime
+// * capacity equal to or greater than <tt>initialCapacity</tt> and
+// * with the default load factor.
+// *
+// * @param initialCapacity an <code>int</code> value
+// * @param strategy used to compute hash codes and to compare objects.
+// */
+// public StableHashMap(int initialCapacity, TObjectHashingStrategy<K> strategy) {
+// super(initialCapacity, strategy);
+// }
+
+// /**
+// * Creates a new <code>THashMap</code> instance with a prime
+// * capacity equal to or greater than <tt>initialCapacity</tt> and
+// * with the specified load factor.
+// *
+// * @param initialCapacity an <code>int</code> value
+// * @param loadFactor a <code>float</code> value
+// */
+// public StableHashMap(int initialCapacity, float loadFactor) {
+// super(initialCapacity, loadFactor);
+// }
+
+// /**
+// * Creates a new <code>THashMap</code> instance with a prime
+// * capacity equal to or greater than <tt>initialCapacity</tt> and
+// * with the specified load factor.
+// *
+// * @param initialCapacity an <code>int</code> value
+// * @param loadFactor a <code>float</code> value
+// * @param strategy used to compute hash codes and to compare objects.
+// */
+// public StableHashMap(int initialCapacity, float loadFactor, TObjectHashingStrategy<K> strategy) {
+// super(initialCapacity, loadFactor, strategy);
+// }
+
+// /**
+// * Creates a new <code>THashMap</code> instance which contains the
+// * key/value pairs in <tt>map</tt>.
+// *
+// * @param map a <code>Map</code> value
+// */
+// public StableHashMap(Map<K,V> map) {
+// this(map.size());
+// putAll(map);
+// }
+//
+// /**
+// * Creates a new <code>THashMap</code> instance which contains the
+// * key/value pairs in <tt>map</tt>.
+// *
+// * @param map a <code>Map</code> value
+// * @param strategy used to compute hash codes and to compare objects.
+// */
+// public StableHashMap(Map<K,V> map, TObjectHashingStrategy<K> strategy) {
+// this(map.size(), strategy);
+// putAll(map);
+// }
+
+ /**
+ * @return a shallow clone of this collection
+ */
+ public StableHashMap<K,V> clone() {
+ StableHashMap<K,V> m = (StableHashMap<K,V>)super.clone();
+ m._values = this._values.clone();
+ return m;
+ }
+
+ /**
+ * initialize the value array of the map.
+ *
+ * @param initialCapacity an <code>int</code> value
+ * @return an <code>int</code> value
+ */
+ protected int setUp(int initialCapacity) {
+ int capacity;
+
+ capacity = super.setUp(initialCapacity);
+ //noinspection unchecked
+ _values = (V[]) new Object[capacity];
+ return capacity;
+ }
+
+ /**
+ * Inserts a key/value pair into the map.
+ *
+ * @param key an <code>Object</code> value
+ * @param value an <code>Object</code> value
+ * @return the previous value associated with <tt>key</tt>,
+ * or {@code null} if none was found.
+ */
+ public V put(K key, V value) {
+ int index = insertionIndex(key);
+ return doPut(key, value, index);
+ }
+
+ public V put(K key, V value, int hash) {
+ int index = insertionIndex(key, hash);
+ return doPut(key, value, index);
+ }
+
+ /**
+ * Inserts a key/value pair into the map if the specified key is not already
+ * associated with a value.
+ *
+ * @param key an <code>Object</code> value
+ * @param value an <code>Object</code> value
+ * @return the previous value associated with <tt>key</tt>,
+ * or {@code null} if none was found.
+ */
+ public V putIfAbsent(K key, V value) {
+ int index = insertionIndex(key);
+ if (index < 0)
+ return _values[-index - 1];
+ return doPut(key, value, index);
+ }
+
+ private V doPut(K key, V value, int index) {
+ V previous = null;
+ Object oldKey;
+ boolean isNewMapping = true;
+ if (index < 0) {
+ index = -index -1;
+ previous = _values[index];
+ isNewMapping = false;
+ }
+ oldKey = _set[index];
+ _set[index] = key;
+ _values[index] = value;
+ if (isNewMapping) {
+ postInsertHook(oldKey == FREE);
+ }
+
+ return previous;
+ }
+
+ /**
+ * Compares this map with another map for equality of their stored
+ * entries.
+ *
+ * @param other an <code>Object</code> value
+ * @return a <code>boolean</code> value
+ */
+ public boolean equals(Object other) {
+ if (! (other instanceof Map)) {
+ return false;
+ }
+ Map<K, V> that = (Map<K, V>)other;
+ if (that.size() != this.size()) {
+ return false;
+ }
+ return forEachEntry(new EqProcedure<K,V>(that));
+ }
+
+ public int hashCode() {
+ HashProcedure p = new HashProcedure();
+ forEachEntry(p);
+ return p.getHashCode();
+ }
+
+ public String toString() {
+ final StringBuilder buf = new StringBuilder("{");
+ forEachEntry(new TObjectObjectProcedure<K,V>() {
+ private boolean first = true;
+ public boolean execute(K key, V value) {
+ if ( first ) first = false;
+ else buf.append( "," );
+
+ buf.append(key);
+ buf.append("=");
+ buf.append(value);
+ return true;
+ }
+ });
+ buf.append("}");
+ return buf.toString();
+ }
+
+ private final class HashProcedure implements TObjectObjectProcedure<K,V> {
+ private int h = 0;
+
+ public int getHashCode() {
+ return h;
+ }
+
+ public final boolean execute(K key, V value) {
+ h += _hashingStrategy.computeHashCode(key) ^ (value == null ? 0 : value.hashCode());
+ return true;
+ }
+ }
+
+ private static final class EqProcedure<K,V> implements TObjectObjectProcedure<K,V> {
+ private final Map<K,V> _otherMap;
+
+ EqProcedure(Map<K,V> otherMap) {
+ _otherMap = otherMap;
+ }
+
+ public final boolean execute(K key, V value) {
+ // Check to make sure the key is there. This avoids problems that come up with
+ // null values. Since it is only caused in that cause, only do this when the
+ // value is null (to avoid extra work).
+ if (value == null && !_otherMap.containsKey(key)) return false;
+
+ V oValue = _otherMap.get(key);
+ return oValue == value || (oValue != null && oValue.equals(value));
+ }
+ }
+
+ /**
+ * Executes <tt>procedure</tt> for each key in the map.
+ *
+ * @param procedure a <code>TObjectProcedure</code> value
+ * @return false if the loop over the keys terminated because
+ * the procedure returned false for some key.
+ */
+ public boolean forEachKey(TObjectProcedure<K> procedure) {
+ return forEach(procedure);
+ }
+
+ /**
+ * Executes <tt>procedure</tt> for each value in the map.
+ *
+ * @param procedure a <code>TObjectProcedure</code> value
+ * @return false if the loop over the values terminated because
+ * the procedure returned false for some value.
+ */
+ public boolean forEachValue(TObjectProcedure<V> procedure) {
+ V[] values = _values;
+ Object[] set = _set;
+ for (int i = values.length; i-- > 0;) {
+ if (set[i] != FREE
+ && set[i] != REMOVED
+ && ! procedure.execute(values[i])) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Executes <tt>procedure</tt> for each key/value entry in the
+ * map.
+ *
+ * @param procedure a <code>TObjectObjectProcedure</code> value
+ * @return false if the loop over the entries terminated because
+ * the procedure returned false for some entry.
+ */
+ public boolean forEachEntry(TObjectObjectProcedure<K,V> procedure) {
+ Object[] keys = _set;
+ V[] values = _values;
+ for (int i = keys.length; i-- > 0;) {
+ if (keys[i] != FREE
+ && keys[i] != REMOVED
+ && ! procedure.execute((K) keys[i],values[i])) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Retains only those entries in the map for which the procedure
+ * returns a true value.
+ *
+ * @param procedure determines which entries to keep
+ * @return true if the map was modified.
+ */
+ public boolean retainEntries(TObjectObjectProcedure<K,V> procedure) {
+ boolean modified = false;
+ Object[] keys = _set;
+ V[] values = _values;
+
+ // Temporarily disable compaction. This is a fix for bug #1738760
+ tempDisableAutoCompaction();
+ try {
+ for (int i = keys.length; i-- > 0;) {
+ if (keys[i] != FREE
+ && keys[i] != REMOVED
+ && ! procedure.execute((K) keys[i],values[i])) {
+ removeAt(i);
+ modified = true;
+ }
+ }
+ }
+ finally {
+ reenableAutoCompaction(true);
+ }
+
+ return modified;
+ }
+
+ /**
+ * Transform the values in this map using <tt>function</tt>.
+ *
+ * @param function a <code>TObjectFunction</code> value
+ */
+ public void transformValues(TObjectFunction<V,V> function) {
+ V[] values = _values;
+ Object[] set = _set;
+ for (int i = values.length; i-- > 0;) {
+ if (set[i] != FREE && set[i] != REMOVED) {
+ values[i] = function.execute(values[i]);
+ }
+ }
+ }
+
+ /**
+ * rehashes the map to the new capacity.
+ *
+ * @param newCapacity an <code>int</code> value
+ */
+ protected void rehash(int newCapacity) {
+ int oldCapacity = _set.length;
+ Object oldKeys[] = _set;
+ V oldVals[] = _values;
+
+ _set = new Object[newCapacity];
+ Arrays.fill(_set, FREE);
+ _values = (V[]) new Object[newCapacity];
+
+ for (int i = oldCapacity; i-- > 0;) {
+ if(oldKeys[i] != FREE && oldKeys[i] != REMOVED) {
+ Object o = oldKeys[i];
+ int index = insertionIndex((K) o);
+ if (index < 0) {
+ throwObjectContractViolation(_set[(-index -1)], o);
+ }
+ _set[index] = o;
+ _values[index] = oldVals[i];
+ }
+ }
+ }
+
+ /**
+ * retrieves the value for <tt>key</tt>
+ *
+ * @param key an <code>Object</code> value
+ * @return the value of <tt>key</tt> or null if no such mapping exists.
+ */
+ public V get(Object key) {
+ Object[] set = _set;
+ V[] values = _values;
+ int index = index((K) key, set);
+ return index < 0 ? null : values[index];
+ }
+
+ public V get(Object key, int hash) {
+ Object[] set = _set;
+ V[] values = _values;
+ int index = index((K) key, hash, set);
+ return index < 0 ? null : values[index];
+ }
+
+ /**
+ * Empties the map.
+ *
+ */
+ public void clear() {
+ if (size() == 0) return; // optimization
+
+ super.clear();
+
+ Arrays.fill(_set, 0, _set.length, FREE);
+ Arrays.fill(_values, 0, _values.length, null);
+ }
+
+ /**
+ * Deletes a key/value pair from the map.
+ *
+ * @param key an <code>Object</code> value
+ * @return an <code>Object</code> value
+ */
+ public V remove(Object key) {
+ Object[] set = _set;
+ V[] values = _values;
+ V prev = null;
+ int index = index((K) key, set);
+ if (index >= 0) {
+ prev = values[index];
+ removeAt(index); // clear key,state; adjust size
+ }
+ return prev;
+ }
+
+ protected void removeAt(int index) {
+ _values[index] = null;
+ super.removeAt(index); // clear key, state; adjust size
+ }
+
+ /**
+ * removes the mapping at <tt>index</tt> from the map.
+ *
+ * @param index an <code>int</code> value
+ */
+ protected void removeAt(int index, V[] values) {
+ values[index] = null;
+ super.removeAt(index); // clear key, state; adjust size
+ }
+
+ public void values(int level, CacheCollectionResult result) {
+
+ for (int i = _set.length; i-- > 0;) {
+ if(_set[i] != null && _set[i] != REMOVED && _set[i] != FREE) {
+ CacheEntryBase e = (CacheEntryBase)_values[i];
+ if(e.getLevel() <= level)
+ result.add(e);
+ }
+ }
+
+ }
+
+ /**
+ * Returns a view on the values of the map.
+ *
+ * @return a <code>Collection</code> value
+ */
+ public Collection<V> values() {
+
+ Collection<V> result = new ArrayList<V>();
+
+ for (int i = _set.length; i-- > 0;) {
+ if(_set[i] != null && _set[i] != REMOVED && _set[i] != FREE) {
+ result.add((V)_values[i]);
+ }
+ }
+
+ return result;
+
+ }
+
+ /**
+ * returns a Set view on the keys of the map.
+ *
+ * @return a <code>Set</code> value
+ */
+ public Set<K> keySet() {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * Returns a Set view on the entries of the map.
+ *
+ * @return a <code>Set</code> value
+ */
+ public Set<Map.Entry<K,V>> entrySet() {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * checks for the presence of <tt>val</tt> in the values of the map.
+ *
+ * @param val an <code>Object</code> value
+ * @return a <code>boolean</code> value
+ */
+ public boolean containsValue(Object val) {
+ Object[] set = _set;
+ V[] vals = _values;
+
+ // special case null values so that we don't have to
+ // perform null checks before every call to equals()
+ if (null == val) {
+ for (int i = vals.length; i-- > 0;) {
+ if ((set[i] != FREE && set[i] != REMOVED) &&
+ val == vals[i]) {
+ return true;
+ }
+ }
+ } else {
+ for (int i = vals.length; i-- > 0;) {
+ if ((set[i] != FREE && set[i] != REMOVED) &&
+ (val == vals[i] || val.equals(vals[i]))) {
+ return true;
+ }
+ }
+ } // end of else
+ return false;
+ }
+
+ /**
+ * checks for the present of <tt>key</tt> in the keys of the map.
+ *
+ * @param key an <code>Object</code> value
+ * @return a <code>boolean</code> value
+ */
+ public boolean containsKey(Object key) {
+ return contains(key);
+ }
+
+ /**
+ * copies the key/value mappings in <tt>map</tt> into this map.
+ *
+ * @param map a <code>Map</code> value
+ */
+ public void putAll(Map<? extends K, ? extends V> map) {
+ ensureCapacity(map.size());
+ // could optimize this for cases when map instanceof THashMap
+ for (Iterator<? extends Map.Entry<? extends K,? extends V>> i = map.entrySet().iterator(); i.hasNext();) {
+ Map.Entry<? extends K,? extends V> e = i.next();
+ put(e.getKey(),e.getValue());
+ }
+ }
+
+} // THashMap