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%2FStableHashMap.java;h=aed464ac4dfc90e893f98bb0e87f7358ab78d7e3;hp=9e01b16f39702f067e021f2fd32504a0f45b02f6;hb=c4d9561b1b35a0e8e594158fbb01a9c632997808;hpb=969bd23cab98a79ca9101af33334000879fb60c5 diff --git a/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/StableHashMap.java b/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/StableHashMap.java index 9e01b16f3..aed464ac4 100644 --- a/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/StableHashMap.java +++ b/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/StableHashMap.java @@ -1,582 +1,582 @@ -/******************************************************************************* - * 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 extends StableObjectHash implements Map, Externalizable { - static final long serialVersionUID = 1L; - - /** the values of the map */ - protected transient V[] _values; - - /** - * Creates a new THashMap instance with the default - * capacity and load factor. - */ - public StableHashMap() { - super(); - } - -// /** -// * Creates a new THashMap instance with a prime -// * capacity equal to or greater than initialCapacity and -// * with the default load factor. -// * -// * @param initialCapacity an int value -// */ -// public StableHashMap(int initialCapacity) { -// super(initialCapacity); -// } - -// /** -// * Creates a new THashMap instance with a prime -// * capacity equal to or greater than initialCapacity and -// * with the default load factor. -// * -// * @param initialCapacity an int value -// * @param strategy used to compute hash codes and to compare objects. -// */ -// public StableHashMap(int initialCapacity, TObjectHashingStrategy strategy) { -// super(initialCapacity, strategy); -// } - -// /** -// * Creates a new THashMap instance with a prime -// * capacity equal to or greater than initialCapacity and -// * with the specified load factor. -// * -// * @param initialCapacity an int value -// * @param loadFactor a float value -// */ -// public StableHashMap(int initialCapacity, float loadFactor) { -// super(initialCapacity, loadFactor); -// } - -// /** -// * Creates a new THashMap instance with a prime -// * capacity equal to or greater than initialCapacity and -// * with the specified load factor. -// * -// * @param initialCapacity an int value -// * @param loadFactor a float value -// * @param strategy used to compute hash codes and to compare objects. -// */ -// public StableHashMap(int initialCapacity, float loadFactor, TObjectHashingStrategy strategy) { -// super(initialCapacity, loadFactor, strategy); -// } - -// /** -// * Creates a new THashMap instance which contains the -// * key/value pairs in map. -// * -// * @param map a Map value -// */ -// public StableHashMap(Map map) { -// this(map.size()); -// putAll(map); -// } -// -// /** -// * Creates a new THashMap instance which contains the -// * key/value pairs in map. -// * -// * @param map a Map value -// * @param strategy used to compute hash codes and to compare objects. -// */ -// public StableHashMap(Map map, TObjectHashingStrategy strategy) { -// this(map.size(), strategy); -// putAll(map); -// } - - /** - * @return a shallow clone of this collection - */ - public StableHashMap clone() { - StableHashMap m = (StableHashMap)super.clone(); - m._values = this._values.clone(); - return m; - } - - /** - * initialize the value array of the map. - * - * @param initialCapacity an int value - * @return an int 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 Object value - * @param value an Object value - * @return the previous value associated with key, - * 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 Object value - * @param value an Object value - * @return the previous value associated with key, - * 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 Object value - * @return a boolean value - */ - public boolean equals(Object other) { - if (! (other instanceof Map)) { - return false; - } - Map that = (Map)other; - if (that.size() != this.size()) { - return false; - } - return forEachEntry(new EqProcedure(that)); - } - - public int hashCode() { - HashProcedure p = new HashProcedure(); - forEachEntry(p); - return p.getHashCode(); - } - - public String toString() { - final StringBuilder buf = new StringBuilder("{"); - forEachEntry(new TObjectObjectProcedure() { - 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 { - 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 implements TObjectObjectProcedure { - private final Map _otherMap; - - EqProcedure(Map 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 procedure for each key in the map. - * - * @param procedure a TObjectProcedure value - * @return false if the loop over the keys terminated because - * the procedure returned false for some key. - */ - public boolean forEachKey(TObjectProcedure procedure) { - return forEach(procedure); - } - - /** - * Executes procedure for each value in the map. - * - * @param procedure a TObjectProcedure value - * @return false if the loop over the values terminated because - * the procedure returned false for some value. - */ - public boolean forEachValue(TObjectProcedure 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 procedure for each key/value entry in the - * map. - * - * @param procedure a TObjectObjectProcedure value - * @return false if the loop over the entries terminated because - * the procedure returned false for some entry. - */ - public boolean forEachEntry(TObjectObjectProcedure 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 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 function. - * - * @param function a TObjectFunction value - */ - public void transformValues(TObjectFunction 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 int 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 key - * - * @param key an Object value - * @return the value of key 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 Object value - * @return an Object 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 index from the map. - * - * @param index an int 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 Collection value - */ - public Collection values() { - - Collection result = new ArrayList(); - - 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 Set value - */ - public Set keySet() { - throw new UnsupportedOperationException(); - } - - /** - * Returns a Set view on the entries of the map. - * - * @return a Set value - */ - public Set> entrySet() { - throw new UnsupportedOperationException(); - } - - /** - * checks for the presence of val in the values of the map. - * - * @param val an Object value - * @return a boolean 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 key in the keys of the map. - * - * @param key an Object value - * @return a boolean value - */ - public boolean containsKey(Object key) { - return contains(key); - } - - /** - * copies the key/value mappings in map into this map. - * - * @param map a Map value - */ - public void putAll(Map map) { - ensureCapacity(map.size()); - // could optimize this for cases when map instanceof THashMap - for (Iterator> i = map.entrySet().iterator(); i.hasNext();) { - Map.Entry e = i.next(); - put(e.getKey(),e.getValue()); - } - } - -} // THashMap +/******************************************************************************* + * 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 extends StableObjectHash implements Map, Externalizable { + static final long serialVersionUID = 1L; + + /** the values of the map */ + protected transient V[] _values; + + /** + * Creates a new THashMap instance with the default + * capacity and load factor. + */ + public StableHashMap() { + super(); + } + +// /** +// * Creates a new THashMap instance with a prime +// * capacity equal to or greater than initialCapacity and +// * with the default load factor. +// * +// * @param initialCapacity an int value +// */ +// public StableHashMap(int initialCapacity) { +// super(initialCapacity); +// } + +// /** +// * Creates a new THashMap instance with a prime +// * capacity equal to or greater than initialCapacity and +// * with the default load factor. +// * +// * @param initialCapacity an int value +// * @param strategy used to compute hash codes and to compare objects. +// */ +// public StableHashMap(int initialCapacity, TObjectHashingStrategy strategy) { +// super(initialCapacity, strategy); +// } + +// /** +// * Creates a new THashMap instance with a prime +// * capacity equal to or greater than initialCapacity and +// * with the specified load factor. +// * +// * @param initialCapacity an int value +// * @param loadFactor a float value +// */ +// public StableHashMap(int initialCapacity, float loadFactor) { +// super(initialCapacity, loadFactor); +// } + +// /** +// * Creates a new THashMap instance with a prime +// * capacity equal to or greater than initialCapacity and +// * with the specified load factor. +// * +// * @param initialCapacity an int value +// * @param loadFactor a float value +// * @param strategy used to compute hash codes and to compare objects. +// */ +// public StableHashMap(int initialCapacity, float loadFactor, TObjectHashingStrategy strategy) { +// super(initialCapacity, loadFactor, strategy); +// } + +// /** +// * Creates a new THashMap instance which contains the +// * key/value pairs in map. +// * +// * @param map a Map value +// */ +// public StableHashMap(Map map) { +// this(map.size()); +// putAll(map); +// } +// +// /** +// * Creates a new THashMap instance which contains the +// * key/value pairs in map. +// * +// * @param map a Map value +// * @param strategy used to compute hash codes and to compare objects. +// */ +// public StableHashMap(Map map, TObjectHashingStrategy strategy) { +// this(map.size(), strategy); +// putAll(map); +// } + + /** + * @return a shallow clone of this collection + */ + public StableHashMap clone() { + StableHashMap m = (StableHashMap)super.clone(); + m._values = this._values.clone(); + return m; + } + + /** + * initialize the value array of the map. + * + * @param initialCapacity an int value + * @return an int 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 Object value + * @param value an Object value + * @return the previous value associated with key, + * 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 Object value + * @param value an Object value + * @return the previous value associated with key, + * 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 Object value + * @return a boolean value + */ + public boolean equals(Object other) { + if (! (other instanceof Map)) { + return false; + } + Map that = (Map)other; + if (that.size() != this.size()) { + return false; + } + return forEachEntry(new EqProcedure(that)); + } + + public int hashCode() { + HashProcedure p = new HashProcedure(); + forEachEntry(p); + return p.getHashCode(); + } + + public String toString() { + final StringBuilder buf = new StringBuilder("{"); + forEachEntry(new TObjectObjectProcedure() { + 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 { + 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 implements TObjectObjectProcedure { + private final Map _otherMap; + + EqProcedure(Map 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 procedure for each key in the map. + * + * @param procedure a TObjectProcedure value + * @return false if the loop over the keys terminated because + * the procedure returned false for some key. + */ + public boolean forEachKey(TObjectProcedure procedure) { + return forEach(procedure); + } + + /** + * Executes procedure for each value in the map. + * + * @param procedure a TObjectProcedure value + * @return false if the loop over the values terminated because + * the procedure returned false for some value. + */ + public boolean forEachValue(TObjectProcedure 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 procedure for each key/value entry in the + * map. + * + * @param procedure a TObjectObjectProcedure value + * @return false if the loop over the entries terminated because + * the procedure returned false for some entry. + */ + public boolean forEachEntry(TObjectObjectProcedure 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 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 function. + * + * @param function a TObjectFunction value + */ + public void transformValues(TObjectFunction 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 int 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 key + * + * @param key an Object value + * @return the value of key 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 Object value + * @return an Object 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 index from the map. + * + * @param index an int 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 Collection value + */ + public Collection values() { + + Collection result = new ArrayList(); + + 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 Set value + */ + public Set keySet() { + throw new UnsupportedOperationException(); + } + + /** + * Returns a Set view on the entries of the map. + * + * @return a Set value + */ + public Set> entrySet() { + throw new UnsupportedOperationException(); + } + + /** + * checks for the presence of val in the values of the map. + * + * @param val an Object value + * @return a boolean 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 key in the keys of the map. + * + * @param key an Object value + * @return a boolean value + */ + public boolean containsKey(Object key) { + return contains(key); + } + + /** + * copies the key/value mappings in map into this map. + * + * @param map a Map value + */ + public void putAll(Map map) { + ensureCapacity(map.size()); + // could optimize this for cases when map instanceof THashMap + for (Iterator> i = map.entrySet().iterator(); i.hasNext();) { + Map.Entry e = i.next(); + put(e.getKey(),e.getValue()); + } + } + +} // THashMap