You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by sm...@apache.org on 2006/05/19 05:50:08 UTC
svn commit: r407700 [1/2] - in
/incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util:
HashMap.java LinkedHashMap.java WeakHashMap.java
Author: smishura
Date: Thu May 18 20:50:08 2006
New Revision: 407700
URL: http://svn.apache.org/viewvc?rev=407700&view=rev
Log:
Reformatting code to 4 space indent
Modified:
incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java
incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/LinkedHashMap.java
incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/WeakHashMap.java
Modified: incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java?rev=407700&r1=407699&r2=407700&view=diff
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java (original)
+++ incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java Thu May 18 20:50:08 2006
@@ -24,620 +24,620 @@
* HashMap is an implementation of Map. All optional operations are supported,
* adding and removing. Keys and values can be any objects.
*/
-public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,
- Cloneable, Serializable {
- private static final long serialVersionUID = 362498820763181265L;
-
- transient int elementCount;
-
- transient Entry[] elementData;
-
- final float loadFactor;
-
- int threshold;
-
- transient int modCount = 0;
-
- private static final int DEFAULT_SIZE = 16;
-
- static class Entry<K,V> extends MapEntry<K,V> {
- final int hash;
-
- Entry<K,V> next;
-
- Entry(K theKey, V theValue) {
- super(theKey, theValue);
- this.hash = (theKey == null) ? 0 : theKey.hashCode();
- }
-
- public Object clone() {
- Entry entry = (Entry) super.clone();
- if (next != null)
- entry.next = (Entry) next.clone();
- return entry;
- }
-
- public String toString() {
- return key + "=" + value;
- }
-
- public int hashCode() {
- return hash;
- }
- }
-
- static class HashMapIterator implements Iterator {
- private int position = 0;
-
- int expectedModCount;
-
- final MapEntry.Type type;
-
- boolean canRemove = false;
-
- Entry entry;
-
- Entry lastEntry;
-
- final HashMap associatedMap;
-
- HashMapIterator(MapEntry.Type value, HashMap hm) {
- associatedMap = hm;
- type = value;
- expectedModCount = hm.modCount;
- }
-
- public boolean hasNext() {
- if (entry != null)
- return true;
- while (position < associatedMap.elementData.length) {
- if (associatedMap.elementData[position] == null)
- position++;
- else
- return true;
- }
- return false;
- }
-
- void checkConcurrentMod() throws ConcurrentModificationException {
- if (expectedModCount != associatedMap.modCount)
- throw new ConcurrentModificationException();
- }
-
- public Object next() {
- checkConcurrentMod();
- if (!hasNext())
- throw new NoSuchElementException();
-
- Entry result;
- if (entry == null) {
- result = lastEntry = associatedMap.elementData[position++];
- entry = lastEntry.next;
- } else {
- if (lastEntry.next != entry)
- lastEntry = lastEntry.next;
- result = entry;
- entry = entry.next;
- }
- canRemove = true;
- return type.get(result);
- }
-
- public void remove() {
- checkConcurrentMod();
- if (!canRemove)
- throw new IllegalStateException();
-
- canRemove = false;
- associatedMap.modCount++;
- if (lastEntry.next == entry) {
- while (associatedMap.elementData[--position] == null)
- ;
- associatedMap.elementData[position] = associatedMap.elementData[position].next;
- entry = null;
- } else
- lastEntry.next = entry;
- associatedMap.elementCount--;
- expectedModCount++;
- }
- }
-
- static class HashMapEntrySet extends AbstractSet {
- private final HashMap associatedMap;
-
- public HashMapEntrySet(HashMap hm) {
- associatedMap = hm;
- }
-
- HashMap hashMap() {
- return associatedMap;
- }
-
- public int size() {
- return associatedMap.elementCount;
- }
-
- public void clear() {
- associatedMap.clear();
- }
-
- public boolean remove(Object object) {
- if (contains(object)) {
- associatedMap.remove(((Map.Entry) object).getKey());
- return true;
- }
- return false;
- }
-
- public boolean contains(Object object) {
- if (object instanceof Map.Entry) {
- Entry entry = associatedMap.getEntry(((Map.Entry) object)
- .getKey());
- return object.equals(entry);
- }
- return false;
- }
-
- public Iterator iterator() {
- return new HashMapIterator(new MapEntry.Type() {
- public Object get(MapEntry entry) {
- return entry;
- }
- }, associatedMap);
- }
- }
-
- /**
- * Create a new element array
- *
- * @param s
- * @return Reference to the element array
- */
- Entry[] newElementArray(int s) {
- return new Entry[s];
- }
-
- /**
- * Contructs a new empty instance of HashMap.
- *
- */
- public HashMap() {
- this(DEFAULT_SIZE);
- }
-
- /**
- * Constructs a new instance of HashMap with the specified capacity.
- *
- * @param capacity
- * the initial capacity of this HashMap
- *
- * @exception IllegalArgumentException
- * when the capacity is less than zero
- */
- public HashMap(int capacity) {
- if (capacity >= 0) {
- elementCount = 0;
- elementData = newElementArray(capacity == 0 ? 1 : capacity);
- loadFactor = 0.75f; // Default load factor of 0.75
- computeMaxSize();
- } else
- throw new IllegalArgumentException();
- }
-
- /**
- * Constructs a new instance of HashMap with the specified capacity and load
- * factor.
- *
- *
- * @param capacity
- * the initial capacity
- * @param loadFactor
- * the initial load factor
- *
- * @exception IllegalArgumentException
- * when the capacity is less than zero or the load factor is
- * less or equal to zero
- */
- public HashMap(int capacity, float loadFactor) {
- if (capacity >= 0 && loadFactor > 0) {
- elementCount = 0;
- elementData = newElementArray(capacity == 0 ? 1 : capacity);
- this.loadFactor = loadFactor;
- computeMaxSize();
- } else
- throw new IllegalArgumentException();
- }
-
- /**
- * Constructs a new instance of HashMap containing the mappings from the
- * specified Map.
- *
- * @param map
- * the mappings to add
- */
- public HashMap(Map map) {
- this(map.size() < 6 ? 11 : map.size() * 2);
- putAll(map);
- }
-
- /**
- * Removes all mappings from this HashMap, leaving it empty.
- *
- * @see #isEmpty
- * @see #size
- */
- public void clear() {
- if (elementCount > 0) {
- elementCount = 0;
- Arrays.fill(elementData, null);
- modCount++;
- }
- }
-
- /**
- * Answers a new HashMap with the same mappings and size as this HashMap.
- *
- * @return a shallow copy of this HashMap
- *
- * @see java.lang.Cloneable
- */
- public Object clone() {
- try {
- HashMap map = (HashMap) super.clone();
- map.elementData = newElementArray(elementData.length);
- Entry entry;
- for (int i = 0; i < elementData.length; i++) {
- if ((entry = elementData[i]) != null)
- map.elementData[i] = (Entry) entry.clone();
- }
- return map;
- } catch (CloneNotSupportedException e) {
- return null;
- }
- }
-
- private void computeMaxSize() {
- threshold = (int) (elementData.length * loadFactor);
- }
-
- /**
- * Searches this HashMap for the specified key.
- *
- * @param key
- * the object to search for
- * @return true if <code>key</code> is a key of this HashMap, false
- * otherwise
- */
- public boolean containsKey(Object key) {
- return getEntry(key) != null;
- }
-
- /**
- * Tests two keys for equality. This method just calls key.equals but can be
- * overridden.
- *
- * @param k1
- * first key to compare
- * @param k2
- * second key to compare
- * @return true iff the keys are considered equal
- */
- boolean keysEqual(Object k1, Entry entry) {
- return entry.hashCode() == k1.hashCode() && k1.equals(entry.key);
- }
-
- /**
- * Searches this HashMap for the specified value.
- *
- * @param value
- * the object to search for
- * @return true if <code>value</code> is a value of this HashMap, false
- * otherwise
- */
- public boolean containsValue(Object value) {
- if (value != null) {
- for (int i = elementData.length; --i >= 0;) {
- Entry entry = elementData[i];
- while (entry != null) {
- if (value.equals(entry.value))
- return true;
- entry = entry.next;
- }
- }
- } else {
- for (int i = elementData.length; --i >= 0;) {
- Entry entry = elementData[i];
- while (entry != null) {
- if (entry.value == null)
- return true;
- entry = entry.next;
- }
- }
- }
- return false;
- }
-
- /**
- * Answers a Set of the mappings contained in this HashMap. Each element in
- * the set is a Map.Entry. The set is backed by this HashMap so changes to
- * one are relected by the other. The set does not support adding.
- *
- * @return a Set of the mappings
- */
- public Set entrySet() {
- return new HashMapEntrySet(this);
- }
-
- /**
- * Answers the value of the mapping with the specified key.
- *
- * @param key
- * the key
- * @return the value of the mapping with the specified key
- */
- public V get(Object key) {
- Entry<K,V> m = getEntry(key);
- if (m != null) {
- return m.value;
- }
- return null;
- }
-
- Entry getEntry(Object key) {
- int index = getModuloHash(key);
- return findEntry(key, index);
- }
-
- int getModuloHash(Object key) {
- if (key == null)
- return 0;
- return (key.hashCode() & 0x7FFFFFFF) % elementData.length;
- }
-
- Entry findEntry(Object key, int index) {
- Entry m;
- m = elementData[index];
- if (key != null) {
- while(m != null && !keysEqual(key,m)){
- m = m.next;
- }
- } else {
- while (m != null && m.key != null)
- m = m.next;
- }
- return m;
- }
-
- /**
- * Answers if this HashMap has no elements, a size of zero.
- *
- * @return true if this HashMap has no elements, false otherwise
- *
- * @see #size
- */
- public boolean isEmpty() {
- return elementCount == 0;
- }
-
- /**
- * Answers a Set of the keys contained in this HashMap. The set is backed by
- * this HashMap so changes to one are relected by the other. The set does
- * not support adding.
- *
- * @return a Set of the keys
- */
- public Set<K> keySet() {
- if (keySet == null) {
- keySet = new AbstractSet() {
- public boolean contains(Object object) {
- return containsKey(object);
- }
-
- public int size() {
- return HashMap.this.size();
- }
-
- public void clear() {
- HashMap.this.clear();
- }
-
- public boolean remove(Object key) {
- if (containsKey(key)) {
- HashMap.this.remove(key);
- return true;
- }
- return false;
- }
-
- public Iterator iterator() {
- return new HashMapIterator(new MapEntry.Type() {
- public Object get(MapEntry entry) {
- return entry.key;
- }
- }, HashMap.this);
- }
- };
- }
- return keySet;
- }
-
- /**
- * Maps the specified key to the specified value.
- *
- * @param key
- * the key
- * @param value
- * the value
- * @return the value of any previous mapping with the specified key or null
- * if there was no mapping
- */
- public Object put(Object key, Object value) {
- int index = getModuloHash(key);
- Entry entry = findEntry(key, index);
-
- if (entry == null) {
- modCount++;
- if (++elementCount > threshold) {
- rehash();
- index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
- % elementData.length;
- }
- entry = createEntry(key, index, null);
- }
- Object result = entry.value;
- entry.value = value;
- return result;
- }
-
- Entry createEntry(Object key, int index, Object value) {
- Entry entry = new Entry(key, value);
- entry.next = elementData[index];
- elementData[index] = entry;
- return entry;
- }
-
- /**
- * Copies every mapping in the specified Map to this HashMap.
- *
- * @param map
- * the Map to copy mappings from
- */
- public void putAll(Map map) {
- super.putAll(map);
- }
-
- void rehash() {
- int length = elementData.length << 1;
- if (length == 0)
- length = 1;
- Entry[] newData = newElementArray(length);
- for (int i = 0; i < elementData.length; i++) {
- Entry entry = elementData[i];
- while (entry != null) {
- Object key = entry.key;
- int index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
- % length;
- Entry next = entry.next;
- entry.next = newData[index];
- newData[index] = entry;
- entry = next;
- }
- }
- elementData = newData;
- computeMaxSize();
- }
-
- /**
- * Removes a mapping with the specified key from this HashMap.
- *
- * @param key
- * the key of the mapping to remove
- * @return the value of the removed mapping or null if key is not a key in
- * this HashMap
- */
- public V remove(Object key) {
- Entry<K,V> entry = removeEntry(key);
- if (entry != null) {
- return entry.value;
- }
- return null;
- }
-
- Entry removeEntry(Object key) {
- int index = 0;
- Entry entry;
- Entry last = null;
- if (key != null) {
- index = (key.hashCode() & 0x7FFFFFFF) % elementData.length;
- entry = elementData[index];
- while (entry != null && !keysEqual(key, entry)) {
- last = entry;
- entry = entry.next;
- }
- } else {
- entry = elementData[0];
- while (entry != null && entry.key != null) {
- last = entry;
- entry = entry.next;
- }
- }
- if (entry == null)
- return null;
- if (last == null)
- elementData[index] = entry.next;
- else
- last.next = entry.next;
- modCount++;
- elementCount--;
- return entry;
- }
-
- /**
- * Answers the number of mappings in this HashMap.
- *
- * @return the number of mappings in this HashMap
- */
- public int size() {
- return elementCount;
- }
-
- /**
- * Answers a Collection of the values contained in this HashMap. The
- * collection is backed by this HashMap so changes to one are relected by
- * the other. The collection does not support adding.
- *
- * @return a Collection of the values
- */
- public Collection<V> values() {
- if (valuesCollection == null) {
- valuesCollection = new AbstractCollection() {
- public boolean contains(Object object) {
- return containsValue(object);
- }
-
- public int size() {
- return HashMap.this.size();
- }
-
- public void clear() {
- HashMap.this.clear();
- }
-
- public Iterator iterator() {
- return new HashMapIterator(new MapEntry.Type() {
- public Object get(MapEntry entry) {
- return entry.value;
- }
- }, HashMap.this);
- }
- };
- }
- return valuesCollection;
- }
-
- private void writeObject(ObjectOutputStream stream) throws IOException {
- stream.defaultWriteObject();
- stream.writeInt(elementData.length);
- stream.writeInt(elementCount);
- Iterator iterator = entrySet().iterator();
- while (iterator.hasNext()) {
- Entry entry = (Entry) iterator.next();
- stream.writeObject(entry.key);
- stream.writeObject(entry.value);
- entry = entry.next;
- }
- }
-
- private void readObject(ObjectInputStream stream) throws IOException,
- ClassNotFoundException {
- stream.defaultReadObject();
- int length = stream.readInt();
- elementData = new Entry[length];
- elementCount = stream.readInt();
- for (int i = elementCount; --i >= 0;) {
- Object key = stream.readObject();
- int index = (key.hashCode() & 0x7FFFFFFF) % length;
- createEntry(key, index, stream.readObject());
- }
- }
+public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>,
+ Cloneable, Serializable {
+ private static final long serialVersionUID = 362498820763181265L;
+
+ transient int elementCount;
+
+ transient Entry[] elementData;
+
+ final float loadFactor;
+
+ int threshold;
+
+ transient int modCount = 0;
+
+ private static final int DEFAULT_SIZE = 16;
+
+ static class Entry<K, V> extends MapEntry<K, V> {
+ final int hash;
+
+ Entry<K, V> next;
+
+ Entry(K theKey, V theValue) {
+ super(theKey, theValue);
+ this.hash = (theKey == null) ? 0 : theKey.hashCode();
+ }
+
+ public Object clone() {
+ Entry entry = (Entry) super.clone();
+ if (next != null)
+ entry.next = (Entry) next.clone();
+ return entry;
+ }
+
+ public String toString() {
+ return key + "=" + value;
+ }
+
+ public int hashCode() {
+ return hash;
+ }
+ }
+
+ static class HashMapIterator implements Iterator {
+ private int position = 0;
+
+ int expectedModCount;
+
+ final MapEntry.Type type;
+
+ boolean canRemove = false;
+
+ Entry entry;
+
+ Entry lastEntry;
+
+ final HashMap associatedMap;
+
+ HashMapIterator(MapEntry.Type value, HashMap hm) {
+ associatedMap = hm;
+ type = value;
+ expectedModCount = hm.modCount;
+ }
+
+ public boolean hasNext() {
+ if (entry != null)
+ return true;
+ while (position < associatedMap.elementData.length) {
+ if (associatedMap.elementData[position] == null)
+ position++;
+ else
+ return true;
+ }
+ return false;
+ }
+
+ void checkConcurrentMod() throws ConcurrentModificationException {
+ if (expectedModCount != associatedMap.modCount)
+ throw new ConcurrentModificationException();
+ }
+
+ public Object next() {
+ checkConcurrentMod();
+ if (!hasNext())
+ throw new NoSuchElementException();
+
+ Entry result;
+ if (entry == null) {
+ result = lastEntry = associatedMap.elementData[position++];
+ entry = lastEntry.next;
+ } else {
+ if (lastEntry.next != entry)
+ lastEntry = lastEntry.next;
+ result = entry;
+ entry = entry.next;
+ }
+ canRemove = true;
+ return type.get(result);
+ }
+
+ public void remove() {
+ checkConcurrentMod();
+ if (!canRemove)
+ throw new IllegalStateException();
+
+ canRemove = false;
+ associatedMap.modCount++;
+ if (lastEntry.next == entry) {
+ while (associatedMap.elementData[--position] == null)
+ ;
+ associatedMap.elementData[position] = associatedMap.elementData[position].next;
+ entry = null;
+ } else
+ lastEntry.next = entry;
+ associatedMap.elementCount--;
+ expectedModCount++;
+ }
+ }
+
+ static class HashMapEntrySet extends AbstractSet {
+ private final HashMap associatedMap;
+
+ public HashMapEntrySet(HashMap hm) {
+ associatedMap = hm;
+ }
+
+ HashMap hashMap() {
+ return associatedMap;
+ }
+
+ public int size() {
+ return associatedMap.elementCount;
+ }
+
+ public void clear() {
+ associatedMap.clear();
+ }
+
+ public boolean remove(Object object) {
+ if (contains(object)) {
+ associatedMap.remove(((Map.Entry) object).getKey());
+ return true;
+ }
+ return false;
+ }
+
+ public boolean contains(Object object) {
+ if (object instanceof Map.Entry) {
+ Entry entry = associatedMap.getEntry(((Map.Entry) object)
+ .getKey());
+ return object.equals(entry);
+ }
+ return false;
+ }
+
+ public Iterator iterator() {
+ return new HashMapIterator(new MapEntry.Type() {
+ public Object get(MapEntry entry) {
+ return entry;
+ }
+ }, associatedMap);
+ }
+ }
+
+ /**
+ * Create a new element array
+ *
+ * @param s
+ * @return Reference to the element array
+ */
+ Entry[] newElementArray(int s) {
+ return new Entry[s];
+ }
+
+ /**
+ * Contructs a new empty instance of HashMap.
+ *
+ */
+ public HashMap() {
+ this(DEFAULT_SIZE);
+ }
+
+ /**
+ * Constructs a new instance of HashMap with the specified capacity.
+ *
+ * @param capacity
+ * the initial capacity of this HashMap
+ *
+ * @exception IllegalArgumentException
+ * when the capacity is less than zero
+ */
+ public HashMap(int capacity) {
+ if (capacity >= 0) {
+ elementCount = 0;
+ elementData = newElementArray(capacity == 0 ? 1 : capacity);
+ loadFactor = 0.75f; // Default load factor of 0.75
+ computeMaxSize();
+ } else
+ throw new IllegalArgumentException();
+ }
+
+ /**
+ * Constructs a new instance of HashMap with the specified capacity and load
+ * factor.
+ *
+ *
+ * @param capacity
+ * the initial capacity
+ * @param loadFactor
+ * the initial load factor
+ *
+ * @exception IllegalArgumentException
+ * when the capacity is less than zero or the load factor is
+ * less or equal to zero
+ */
+ public HashMap(int capacity, float loadFactor) {
+ if (capacity >= 0 && loadFactor > 0) {
+ elementCount = 0;
+ elementData = newElementArray(capacity == 0 ? 1 : capacity);
+ this.loadFactor = loadFactor;
+ computeMaxSize();
+ } else
+ throw new IllegalArgumentException();
+ }
+
+ /**
+ * Constructs a new instance of HashMap containing the mappings from the
+ * specified Map.
+ *
+ * @param map
+ * the mappings to add
+ */
+ public HashMap(Map map) {
+ this(map.size() < 6 ? 11 : map.size() * 2);
+ putAll(map);
+ }
+
+ /**
+ * Removes all mappings from this HashMap, leaving it empty.
+ *
+ * @see #isEmpty
+ * @see #size
+ */
+ public void clear() {
+ if (elementCount > 0) {
+ elementCount = 0;
+ Arrays.fill(elementData, null);
+ modCount++;
+ }
+ }
+
+ /**
+ * Answers a new HashMap with the same mappings and size as this HashMap.
+ *
+ * @return a shallow copy of this HashMap
+ *
+ * @see java.lang.Cloneable
+ */
+ public Object clone() {
+ try {
+ HashMap map = (HashMap) super.clone();
+ map.elementData = newElementArray(elementData.length);
+ Entry entry;
+ for (int i = 0; i < elementData.length; i++) {
+ if ((entry = elementData[i]) != null)
+ map.elementData[i] = (Entry) entry.clone();
+ }
+ return map;
+ } catch (CloneNotSupportedException e) {
+ return null;
+ }
+ }
+
+ private void computeMaxSize() {
+ threshold = (int) (elementData.length * loadFactor);
+ }
+
+ /**
+ * Searches this HashMap for the specified key.
+ *
+ * @param key
+ * the object to search for
+ * @return true if <code>key</code> is a key of this HashMap, false
+ * otherwise
+ */
+ public boolean containsKey(Object key) {
+ return getEntry(key) != null;
+ }
+
+ /**
+ * Tests two keys for equality. This method just calls key.equals but can be
+ * overridden.
+ *
+ * @param k1
+ * first key to compare
+ * @param k2
+ * second key to compare
+ * @return true iff the keys are considered equal
+ */
+ boolean keysEqual(Object k1, Entry entry) {
+ return entry.hashCode() == k1.hashCode() && k1.equals(entry.key);
+ }
+
+ /**
+ * Searches this HashMap for the specified value.
+ *
+ * @param value
+ * the object to search for
+ * @return true if <code>value</code> is a value of this HashMap, false
+ * otherwise
+ */
+ public boolean containsValue(Object value) {
+ if (value != null) {
+ for (int i = elementData.length; --i >= 0;) {
+ Entry entry = elementData[i];
+ while (entry != null) {
+ if (value.equals(entry.value))
+ return true;
+ entry = entry.next;
+ }
+ }
+ } else {
+ for (int i = elementData.length; --i >= 0;) {
+ Entry entry = elementData[i];
+ while (entry != null) {
+ if (entry.value == null)
+ return true;
+ entry = entry.next;
+ }
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Answers a Set of the mappings contained in this HashMap. Each element in
+ * the set is a Map.Entry. The set is backed by this HashMap so changes to
+ * one are relected by the other. The set does not support adding.
+ *
+ * @return a Set of the mappings
+ */
+ public Set entrySet() {
+ return new HashMapEntrySet(this);
+ }
+
+ /**
+ * Answers the value of the mapping with the specified key.
+ *
+ * @param key
+ * the key
+ * @return the value of the mapping with the specified key
+ */
+ public V get(Object key) {
+ Entry<K, V> m = getEntry(key);
+ if (m != null) {
+ return m.value;
+ }
+ return null;
+ }
+
+ Entry getEntry(Object key) {
+ int index = getModuloHash(key);
+ return findEntry(key, index);
+ }
+
+ int getModuloHash(Object key) {
+ if (key == null)
+ return 0;
+ return (key.hashCode() & 0x7FFFFFFF) % elementData.length;
+ }
+
+ Entry findEntry(Object key, int index) {
+ Entry m;
+ m = elementData[index];
+ if (key != null) {
+ while (m != null && !keysEqual(key, m)) {
+ m = m.next;
+ }
+ } else {
+ while (m != null && m.key != null)
+ m = m.next;
+ }
+ return m;
+ }
+
+ /**
+ * Answers if this HashMap has no elements, a size of zero.
+ *
+ * @return true if this HashMap has no elements, false otherwise
+ *
+ * @see #size
+ */
+ public boolean isEmpty() {
+ return elementCount == 0;
+ }
+
+ /**
+ * Answers a Set of the keys contained in this HashMap. The set is backed by
+ * this HashMap so changes to one are relected by the other. The set does
+ * not support adding.
+ *
+ * @return a Set of the keys
+ */
+ public Set<K> keySet() {
+ if (keySet == null) {
+ keySet = new AbstractSet() {
+ public boolean contains(Object object) {
+ return containsKey(object);
+ }
+
+ public int size() {
+ return HashMap.this.size();
+ }
+
+ public void clear() {
+ HashMap.this.clear();
+ }
+
+ public boolean remove(Object key) {
+ if (containsKey(key)) {
+ HashMap.this.remove(key);
+ return true;
+ }
+ return false;
+ }
+
+ public Iterator iterator() {
+ return new HashMapIterator(new MapEntry.Type() {
+ public Object get(MapEntry entry) {
+ return entry.key;
+ }
+ }, HashMap.this);
+ }
+ };
+ }
+ return keySet;
+ }
+
+ /**
+ * Maps the specified key to the specified value.
+ *
+ * @param key
+ * the key
+ * @param value
+ * the value
+ * @return the value of any previous mapping with the specified key or null
+ * if there was no mapping
+ */
+ public Object put(Object key, Object value) {
+ int index = getModuloHash(key);
+ Entry entry = findEntry(key, index);
+
+ if (entry == null) {
+ modCount++;
+ if (++elementCount > threshold) {
+ rehash();
+ index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
+ % elementData.length;
+ }
+ entry = createEntry(key, index, null);
+ }
+ Object result = entry.value;
+ entry.value = value;
+ return result;
+ }
+
+ Entry createEntry(Object key, int index, Object value) {
+ Entry entry = new Entry(key, value);
+ entry.next = elementData[index];
+ elementData[index] = entry;
+ return entry;
+ }
+
+ /**
+ * Copies every mapping in the specified Map to this HashMap.
+ *
+ * @param map
+ * the Map to copy mappings from
+ */
+ public void putAll(Map map) {
+ super.putAll(map);
+ }
+
+ void rehash() {
+ int length = elementData.length << 1;
+ if (length == 0)
+ length = 1;
+ Entry[] newData = newElementArray(length);
+ for (int i = 0; i < elementData.length; i++) {
+ Entry entry = elementData[i];
+ while (entry != null) {
+ Object key = entry.key;
+ int index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
+ % length;
+ Entry next = entry.next;
+ entry.next = newData[index];
+ newData[index] = entry;
+ entry = next;
+ }
+ }
+ elementData = newData;
+ computeMaxSize();
+ }
+
+ /**
+ * Removes a mapping with the specified key from this HashMap.
+ *
+ * @param key
+ * the key of the mapping to remove
+ * @return the value of the removed mapping or null if key is not a key in
+ * this HashMap
+ */
+ public V remove(Object key) {
+ Entry<K, V> entry = removeEntry(key);
+ if (entry != null) {
+ return entry.value;
+ }
+ return null;
+ }
+
+ Entry removeEntry(Object key) {
+ int index = 0;
+ Entry entry;
+ Entry last = null;
+ if (key != null) {
+ index = (key.hashCode() & 0x7FFFFFFF) % elementData.length;
+ entry = elementData[index];
+ while (entry != null && !keysEqual(key, entry)) {
+ last = entry;
+ entry = entry.next;
+ }
+ } else {
+ entry = elementData[0];
+ while (entry != null && entry.key != null) {
+ last = entry;
+ entry = entry.next;
+ }
+ }
+ if (entry == null)
+ return null;
+ if (last == null)
+ elementData[index] = entry.next;
+ else
+ last.next = entry.next;
+ modCount++;
+ elementCount--;
+ return entry;
+ }
+
+ /**
+ * Answers the number of mappings in this HashMap.
+ *
+ * @return the number of mappings in this HashMap
+ */
+ public int size() {
+ return elementCount;
+ }
+
+ /**
+ * Answers a Collection of the values contained in this HashMap. The
+ * collection is backed by this HashMap so changes to one are relected by
+ * the other. The collection does not support adding.
+ *
+ * @return a Collection of the values
+ */
+ public Collection<V> values() {
+ if (valuesCollection == null) {
+ valuesCollection = new AbstractCollection() {
+ public boolean contains(Object object) {
+ return containsValue(object);
+ }
+
+ public int size() {
+ return HashMap.this.size();
+ }
+
+ public void clear() {
+ HashMap.this.clear();
+ }
+
+ public Iterator iterator() {
+ return new HashMapIterator(new MapEntry.Type() {
+ public Object get(MapEntry entry) {
+ return entry.value;
+ }
+ }, HashMap.this);
+ }
+ };
+ }
+ return valuesCollection;
+ }
+
+ private void writeObject(ObjectOutputStream stream) throws IOException {
+ stream.defaultWriteObject();
+ stream.writeInt(elementData.length);
+ stream.writeInt(elementCount);
+ Iterator iterator = entrySet().iterator();
+ while (iterator.hasNext()) {
+ Entry entry = (Entry) iterator.next();
+ stream.writeObject(entry.key);
+ stream.writeObject(entry.value);
+ entry = entry.next;
+ }
+ }
+
+ private void readObject(ObjectInputStream stream) throws IOException,
+ ClassNotFoundException {
+ stream.defaultReadObject();
+ int length = stream.readInt();
+ elementData = new Entry[length];
+ elementCount = stream.readInt();
+ for (int i = elementCount; --i >= 0;) {
+ Object key = stream.readObject();
+ int index = (key.hashCode() & 0x7FFFFFFF) % length;
+ createEntry(key, index, stream.readObject());
+ }
+ }
}
Modified: incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/LinkedHashMap.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/LinkedHashMap.java?rev=407700&r1=407699&r2=407700&view=diff
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/LinkedHashMap.java (original)
+++ incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/LinkedHashMap.java Thu May 18 20:50:08 2006
@@ -29,488 +29,486 @@
*
*/
public class LinkedHashMap extends HashMap {
-
- private static final long serialVersionUID = 3801124242820219131L;
- private final boolean accessOrder;
+ private static final long serialVersionUID = 3801124242820219131L;
- transient private LinkedHashMapEntry head, tail;
+ private final boolean accessOrder;
- /**
- * Contructs a new empty instance of LinkedHashMap.
- */
- public LinkedHashMap() {
- super();
- accessOrder = false;
- head = null;
- }
-
- /**
- * Constructor with specified size.
- *
- * @param s
- * Size of LinkedHashMap required
- */
- public LinkedHashMap(int s) {
- super(s);
- accessOrder = false;
- head = null;
- }
-
- /**
- * Constructor with specified size and load factor.
- *
- * @param s
- * Size of LinkedHashMap required
- * @param lf
- * Load factor
- */
- public LinkedHashMap(int s, float lf) {
- super(s, lf);
- accessOrder = false;
- head = null;
- tail = null;
- }
-
- /**
- * Constructor with specified size, load factor and access order
- *
- * @param s
- * Size of LinkedHashmap required
- * @param lf
- * Load factor
- * @param order
- * If true indicates that traversal order should begin with most
- * recently accessed
- */
- public LinkedHashMap(int s, float lf, boolean order) {
- super(s, lf);
- accessOrder = order;
- head = null;
- tail = null;
- }
-
- /**
- * Constructor with input map
- *
- * @param m
- * Input map
- */
- public LinkedHashMap(Map m) {
- accessOrder = false;
- head = null;
- tail = null;
- putAll(m);
- }
-
- static final class LinkedHashIterator extends HashMapIterator {
- LinkedHashIterator(MapEntry.Type value, LinkedHashMap hm) {
- super(value, hm);
- entry = hm.head;
- }
-
- public boolean hasNext() {
- return (entry != null);
- }
-
- public Object next() {
- checkConcurrentMod();
- if (!hasNext())
- throw new NoSuchElementException();
- Object result = type.get(entry);
- lastEntry = entry;
- entry = ((LinkedHashMapEntry) entry).chainForward;
- canRemove = true;
- return result;
- }
-
- public void remove() {
- checkConcurrentMod();
- if (!canRemove)
- throw new IllegalStateException();
-
- canRemove = false;
- associatedMap.modCount++;
-
- int index = associatedMap.getModuloHash(lastEntry.key);
- LinkedHashMapEntry m = (LinkedHashMapEntry) associatedMap.elementData[index];
- if (m == lastEntry) {
- associatedMap.elementData[index] = lastEntry.next;
- } else {
- while (m.next != null) {
- if (m.next == lastEntry)
- break;
- m = (LinkedHashMapEntry) m.next;
- }
- // assert m.next == entry
- m.next = lastEntry.next;
- }
- LinkedHashMapEntry lhme = (LinkedHashMapEntry) lastEntry;
- LinkedHashMapEntry p = lhme.chainBackward;
- LinkedHashMapEntry n = lhme.chainForward;
- LinkedHashMap lhm = (LinkedHashMap) associatedMap;
- if (p != null) {
- p.chainForward = n;
- if (n != null)
- n.chainBackward = p;
- else
- lhm.tail = p;
- } else {
- lhm.head = n;
- if (n != null)
- n.chainBackward = null;
- else
- lhm.tail = null;
- }
- associatedMap.elementCount--;
- expectedModCount++;
- }
- }
-
- static final class LinkedHashMapEntrySet extends HashMapEntrySet {
- public LinkedHashMapEntrySet(LinkedHashMap lhm) {
- super(lhm);
- }
-
- public Iterator iterator() {
- return new LinkedHashIterator(new MapEntry.Type() {
- public Object get(MapEntry entry) {
- return entry;
- }
- }, (LinkedHashMap) hashMap());
- }
- }
-
- static final class LinkedHashMapEntry extends Entry {
- LinkedHashMapEntry chainForward, chainBackward;
-
- LinkedHashMapEntry(Object theKey, Object theValue) {
- super(theKey, theValue);
- chainForward = null;
- chainBackward = null;
- }
-
- public Object clone() {
- LinkedHashMapEntry entry = (LinkedHashMapEntry) super.clone();
- entry.chainBackward = chainBackward;
- entry.chainForward = chainForward;
- LinkedHashMapEntry lnext = (LinkedHashMapEntry) entry.next;
- if (lnext != null)
- entry.next = (LinkedHashMapEntry) lnext.clone();
- return entry;
- }
- }
-
- /**
- * Create a new element array
- *
- * @param s
- * @return Reference to the element array
- */
- Entry[] newElementArray(int s) {
- return new LinkedHashMapEntry[s];
- }
-
- /**
- * Retrieve the map value corresponding to the given key.
- *
- * @param key
- * Key value
- * @return mapped value or null if the key is not in the map
- */
- public Object get(Object key) {
- LinkedHashMapEntry m = (LinkedHashMapEntry) getEntry(key);
- if (m == null)
- return null;
- if (accessOrder && tail != m) {
- LinkedHashMapEntry p = m.chainBackward;
- LinkedHashMapEntry n = m.chainForward;
- n.chainBackward = p;
- if (p != null)
- p.chainForward = n;
- else
- head = n;
- m.chainForward = null;
- m.chainBackward = tail;
- tail.chainForward = m;
- tail = m;
- }
- return m.value;
- }
-
- /*
- * @param key
- * @param index
- * @return Entry
- */
- Entry createEntry(Object key, int index, Object value) {
- LinkedHashMapEntry m = new LinkedHashMapEntry(key, value);
- m.next = elementData[index];
- elementData[index] = m;
- linkEntry(m);
- return m;
- }
-
- /**
- * Set the mapped value for the given key to the given value.
- *
- * @param key
- * Key value
- * @param value
- * New mapped value
- * @return The old value if the key was already in the map or null
- * otherwise.
- */
- public Object put(Object key, Object value) {
- int index = getModuloHash(key);
- LinkedHashMapEntry m = (LinkedHashMapEntry) findEntry(key, index);
-
- if (m == null) {
- modCount++;
- // Check if we need to remove the oldest entry
- // The check includes accessOrder since an accessOrder LinkedHashMap
- // does not record
- // the oldest member in 'head'.
- if (++elementCount > threshold) {
- rehash();
- index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
- % elementData.length;
- }
- m = (LinkedHashMapEntry) createEntry(key, index, null);
- } else {
- linkEntry(m);
- }
-
- Object result = m.value;
- m.value = value;
-
- if (removeEldestEntry(head))
- remove(head.key);
-
- return result;
- }
-
- /*
- * @param m
- */
- void linkEntry(LinkedHashMapEntry m) {
- if (tail == m) {
- return;
- }
-
- if (head == null) {
- // Check if the map is empty
- head = tail = m;
- return;
- }
-
- // we need to link the new entry into either the head or tail
- // of the chain depending on if the LinkedHashMap is accessOrder or not
- LinkedHashMapEntry p = m.chainBackward;
- LinkedHashMapEntry n = m.chainForward;
- if (p == null) {
- if (n != null) {
- // The entry must be the head but not the tail
- if (accessOrder) {
- head = n;
- n.chainBackward = null;
- m.chainBackward = tail;
- m.chainForward = null;
- tail.chainForward = m;
- tail = m;
- }
- } else {
- // This is a new entry
- m.chainBackward = tail;
- m.chainForward = null;
- tail.chainForward = m;
- tail = m;
- }
- return;
- }
-
- if (n == null) {
- // The entry must be the tail so we can't get here
- return;
- }
-
- // The entry is neither the head nor tail
- if (accessOrder) {
- p.chainForward = n;
- n.chainBackward = p;
- m.chainForward = null;
- m.chainBackward = tail;
- tail.chainForward = m;
- tail = m;
- }
-
- }
-
- /**
- * Put all entries from the given map into the LinkedHashMap
- *
- * @param m
- * Input map
- */
- public void putAll(Map m) {
- Iterator i = m.entrySet().iterator();
- while (i.hasNext()) {
- Map.Entry e = (MapEntry) i.next();
- put(e.getKey(), e.getValue());
- }
- }
-
- /**
- * Answers a Set of the mappings contained in this HashMap. Each element in
- * the set is a Map.Entry. The set is backed by this HashMap so changes to
- * one are relected by the other. The set does not support adding.
- *
- * @return a Set of the mappings
- */
- public Set entrySet() {
- return new LinkedHashMapEntrySet(this);
- }
-
- /**
- * Answers a Set of the keys contained in this HashMap. The set is backed by
- * this HashMap so changes to one are relected by the other. The set does
- * not support adding.
- *
- * @return a Set of the keys
- */
- public Set keySet() {
- if (keySet == null) {
- keySet = new AbstractSet() {
- public boolean contains(Object object) {
- return containsKey(object);
- }
-
- public int size() {
- return LinkedHashMap.this.size();
- }
-
- public void clear() {
- LinkedHashMap.this.clear();
- }
-
- public boolean remove(Object key) {
- if (containsKey(key)) {
- LinkedHashMap.this.remove(key);
- return true;
- }
- return false;
- }
-
- public Iterator iterator() {
- return new LinkedHashIterator(new MapEntry.Type() {
- public Object get(MapEntry entry) {
- return entry.key;
- }
- }, LinkedHashMap.this);
- }
- };
- }
- return keySet;
- }
-
- /**
- * Answers a Collection of the values contained in this HashMap. The
- * collection is backed by this HashMap so changes to one are relected by
- * the other. The collection does not support adding.
- *
- * @return a Collection of the values
- */
- public Collection values() {
- if (valuesCollection == null) {
- valuesCollection = new AbstractCollection() {
- public boolean contains(Object object) {
- return containsValue(object);
- }
-
- public int size() {
- return LinkedHashMap.this.size();
- }
-
- public void clear() {
- LinkedHashMap.this.clear();
- }
-
- public Iterator iterator() {
- return new LinkedHashIterator(new MapEntry.Type() {
- public Object get(MapEntry entry) {
- return entry.value;
- }
- }, LinkedHashMap.this);
- }
- };
- }
- return valuesCollection;
- }
-
- /**
- * Remove the entry corresponding to the given key.
- *
- * @param key
- * the key
- * @return the value associated with the key or null if the key was no in
- * the map
- */
- public Object remove(Object key) {
- LinkedHashMapEntry m = (LinkedHashMapEntry) removeEntry(key);
- if (m == null)
- return null;
- LinkedHashMapEntry p = m.chainBackward;
- LinkedHashMapEntry n = m.chainForward;
- if (p != null)
- p.chainForward = n;
- else
- head = n;
- if (n != null)
- n.chainBackward = p;
- else
- tail = p;
- return m.value;
- }
-
- /**
- * This method is queried from the put and putAll methods to check if the
- * eldest member of the map should be deleted before adding the new member.
- * If this map was created with accessOrder = true, then the result of
- * removeEldesrEntry is assumed to be false.
- *
- * @param eldest
- * @return true if the eldest member should be removed
- */
- protected boolean removeEldestEntry(Map.Entry eldest) {
- return false;
- }
-
- /**
- * Removes all mappings from this HashMap, leaving it empty.
- *
- * @see #isEmpty()
- * @see #size()
- */
- public void clear() {
- super.clear();
- head = tail = null;
- }
-
- /**
- * Answers a new HashMap with the same mappings and size as this HashMap.
- *
- * @return a shallow copy of this HashMap
- *
- * @see java.lang.Cloneable
- */
- public Object clone() {
- LinkedHashMap map = (LinkedHashMap) super.clone();
- map.clear();
- Iterator entries = entrySet().iterator();
- while (entries.hasNext()) {
- Map.Entry entry = (Map.Entry) entries.next();
- map.put(entry.getKey(), entry.getValue());
- }
- return map;
- }
+ transient private LinkedHashMapEntry head, tail;
+
+ /**
+ * Contructs a new empty instance of LinkedHashMap.
+ */
+ public LinkedHashMap() {
+ super();
+ accessOrder = false;
+ head = null;
+ }
+
+ /**
+ * Constructor with specified size.
+ *
+ * @param s
+ * Size of LinkedHashMap required
+ */
+ public LinkedHashMap(int s) {
+ super(s);
+ accessOrder = false;
+ head = null;
+ }
+
+ /**
+ * Constructor with specified size and load factor.
+ *
+ * @param s
+ * Size of LinkedHashMap required
+ * @param lf
+ * Load factor
+ */
+ public LinkedHashMap(int s, float lf) {
+ super(s, lf);
+ accessOrder = false;
+ head = null;
+ tail = null;
+ }
+
+ /**
+ * Constructor with specified size, load factor and access order
+ *
+ * @param s
+ * Size of LinkedHashmap required
+ * @param lf
+ * Load factor
+ * @param order
+ * If true indicates that traversal order should begin with most
+ * recently accessed
+ */
+ public LinkedHashMap(int s, float lf, boolean order) {
+ super(s, lf);
+ accessOrder = order;
+ head = null;
+ tail = null;
+ }
+
+ /**
+ * Constructor with input map
+ *
+ * @param m
+ * Input map
+ */
+ public LinkedHashMap(Map m) {
+ accessOrder = false;
+ head = null;
+ tail = null;
+ putAll(m);
+ }
+
+ static final class LinkedHashIterator extends HashMapIterator {
+ LinkedHashIterator(MapEntry.Type value, LinkedHashMap hm) {
+ super(value, hm);
+ entry = hm.head;
+ }
+
+ public boolean hasNext() {
+ return (entry != null);
+ }
+
+ public Object next() {
+ checkConcurrentMod();
+ if (!hasNext())
+ throw new NoSuchElementException();
+ Object result = type.get(entry);
+ lastEntry = entry;
+ entry = ((LinkedHashMapEntry) entry).chainForward;
+ canRemove = true;
+ return result;
+ }
+
+ public void remove() {
+ checkConcurrentMod();
+ if (!canRemove)
+ throw new IllegalStateException();
+
+ canRemove = false;
+ associatedMap.modCount++;
+
+ int index = associatedMap.getModuloHash(lastEntry.key);
+ LinkedHashMapEntry m = (LinkedHashMapEntry) associatedMap.elementData[index];
+ if (m == lastEntry) {
+ associatedMap.elementData[index] = lastEntry.next;
+ } else {
+ while (m.next != null) {
+ if (m.next == lastEntry)
+ break;
+ m = (LinkedHashMapEntry) m.next;
+ }
+ // assert m.next == entry
+ m.next = lastEntry.next;
+ }
+ LinkedHashMapEntry lhme = (LinkedHashMapEntry) lastEntry;
+ LinkedHashMapEntry p = lhme.chainBackward;
+ LinkedHashMapEntry n = lhme.chainForward;
+ LinkedHashMap lhm = (LinkedHashMap) associatedMap;
+ if (p != null) {
+ p.chainForward = n;
+ if (n != null)
+ n.chainBackward = p;
+ else
+ lhm.tail = p;
+ } else {
+ lhm.head = n;
+ if (n != null)
+ n.chainBackward = null;
+ else
+ lhm.tail = null;
+ }
+ associatedMap.elementCount--;
+ expectedModCount++;
+ }
+ }
+
+ static final class LinkedHashMapEntrySet extends HashMapEntrySet {
+ public LinkedHashMapEntrySet(LinkedHashMap lhm) {
+ super(lhm);
+ }
+
+ public Iterator iterator() {
+ return new LinkedHashIterator(new MapEntry.Type() {
+ public Object get(MapEntry entry) {
+ return entry;
+ }
+ }, (LinkedHashMap) hashMap());
+ }
+ }
+
+ static final class LinkedHashMapEntry extends Entry {
+ LinkedHashMapEntry chainForward, chainBackward;
+
+ LinkedHashMapEntry(Object theKey, Object theValue) {
+ super(theKey, theValue);
+ chainForward = null;
+ chainBackward = null;
+ }
+
+ public Object clone() {
+ LinkedHashMapEntry entry = (LinkedHashMapEntry) super.clone();
+ entry.chainBackward = chainBackward;
+ entry.chainForward = chainForward;
+ LinkedHashMapEntry lnext = (LinkedHashMapEntry) entry.next;
+ if (lnext != null)
+ entry.next = (LinkedHashMapEntry) lnext.clone();
+ return entry;
+ }
+ }
+
+ /**
+ * Create a new element array
+ *
+ * @param s
+ * @return Reference to the element array
+ */
+ Entry[] newElementArray(int s) {
+ return new LinkedHashMapEntry[s];
+ }
+
+ /**
+ * Retrieve the map value corresponding to the given key.
+ *
+ * @param key
+ * Key value
+ * @return mapped value or null if the key is not in the map
+ */
+ public Object get(Object key) {
+ LinkedHashMapEntry m = (LinkedHashMapEntry) getEntry(key);
+ if (m == null)
+ return null;
+ if (accessOrder && tail != m) {
+ LinkedHashMapEntry p = m.chainBackward;
+ LinkedHashMapEntry n = m.chainForward;
+ n.chainBackward = p;
+ if (p != null)
+ p.chainForward = n;
+ else
+ head = n;
+ m.chainForward = null;
+ m.chainBackward = tail;
+ tail.chainForward = m;
+ tail = m;
+ }
+ return m.value;
+ }
+
+ /*
+ * @param key @param index @return Entry
+ */
+ Entry createEntry(Object key, int index, Object value) {
+ LinkedHashMapEntry m = new LinkedHashMapEntry(key, value);
+ m.next = elementData[index];
+ elementData[index] = m;
+ linkEntry(m);
+ return m;
+ }
+
+ /**
+ * Set the mapped value for the given key to the given value.
+ *
+ * @param key
+ * Key value
+ * @param value
+ * New mapped value
+ * @return The old value if the key was already in the map or null
+ * otherwise.
+ */
+ public Object put(Object key, Object value) {
+ int index = getModuloHash(key);
+ LinkedHashMapEntry m = (LinkedHashMapEntry) findEntry(key, index);
+
+ if (m == null) {
+ modCount++;
+ // Check if we need to remove the oldest entry
+ // The check includes accessOrder since an accessOrder LinkedHashMap
+ // does not record
+ // the oldest member in 'head'.
+ if (++elementCount > threshold) {
+ rehash();
+ index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
+ % elementData.length;
+ }
+ m = (LinkedHashMapEntry) createEntry(key, index, null);
+ } else {
+ linkEntry(m);
+ }
+
+ Object result = m.value;
+ m.value = value;
+
+ if (removeEldestEntry(head))
+ remove(head.key);
+
+ return result;
+ }
+
+ /*
+ * @param m
+ */
+ void linkEntry(LinkedHashMapEntry m) {
+ if (tail == m) {
+ return;
+ }
+
+ if (head == null) {
+ // Check if the map is empty
+ head = tail = m;
+ return;
+ }
+
+ // we need to link the new entry into either the head or tail
+ // of the chain depending on if the LinkedHashMap is accessOrder or not
+ LinkedHashMapEntry p = m.chainBackward;
+ LinkedHashMapEntry n = m.chainForward;
+ if (p == null) {
+ if (n != null) {
+ // The entry must be the head but not the tail
+ if (accessOrder) {
+ head = n;
+ n.chainBackward = null;
+ m.chainBackward = tail;
+ m.chainForward = null;
+ tail.chainForward = m;
+ tail = m;
+ }
+ } else {
+ // This is a new entry
+ m.chainBackward = tail;
+ m.chainForward = null;
+ tail.chainForward = m;
+ tail = m;
+ }
+ return;
+ }
+
+ if (n == null) {
+ // The entry must be the tail so we can't get here
+ return;
+ }
+
+ // The entry is neither the head nor tail
+ if (accessOrder) {
+ p.chainForward = n;
+ n.chainBackward = p;
+ m.chainForward = null;
+ m.chainBackward = tail;
+ tail.chainForward = m;
+ tail = m;
+ }
+
+ }
+
+ /**
+ * Put all entries from the given map into the LinkedHashMap
+ *
+ * @param m
+ * Input map
+ */
+ public void putAll(Map m) {
+ Iterator i = m.entrySet().iterator();
+ while (i.hasNext()) {
+ Map.Entry e = (MapEntry) i.next();
+ put(e.getKey(), e.getValue());
+ }
+ }
+
+ /**
+ * Answers a Set of the mappings contained in this HashMap. Each element in
+ * the set is a Map.Entry. The set is backed by this HashMap so changes to
+ * one are relected by the other. The set does not support adding.
+ *
+ * @return a Set of the mappings
+ */
+ public Set entrySet() {
+ return new LinkedHashMapEntrySet(this);
+ }
+
+ /**
+ * Answers a Set of the keys contained in this HashMap. The set is backed by
+ * this HashMap so changes to one are relected by the other. The set does
+ * not support adding.
+ *
+ * @return a Set of the keys
+ */
+ public Set keySet() {
+ if (keySet == null) {
+ keySet = new AbstractSet() {
+ public boolean contains(Object object) {
+ return containsKey(object);
+ }
+
+ public int size() {
+ return LinkedHashMap.this.size();
+ }
+
+ public void clear() {
+ LinkedHashMap.this.clear();
+ }
+
+ public boolean remove(Object key) {
+ if (containsKey(key)) {
+ LinkedHashMap.this.remove(key);
+ return true;
+ }
+ return false;
+ }
+
+ public Iterator iterator() {
+ return new LinkedHashIterator(new MapEntry.Type() {
+ public Object get(MapEntry entry) {
+ return entry.key;
+ }
+ }, LinkedHashMap.this);
+ }
+ };
+ }
+ return keySet;
+ }
+
+ /**
+ * Answers a Collection of the values contained in this HashMap. The
+ * collection is backed by this HashMap so changes to one are relected by
+ * the other. The collection does not support adding.
+ *
+ * @return a Collection of the values
+ */
+ public Collection values() {
+ if (valuesCollection == null) {
+ valuesCollection = new AbstractCollection() {
+ public boolean contains(Object object) {
+ return containsValue(object);
+ }
+
+ public int size() {
+ return LinkedHashMap.this.size();
+ }
+
+ public void clear() {
+ LinkedHashMap.this.clear();
+ }
+
+ public Iterator iterator() {
+ return new LinkedHashIterator(new MapEntry.Type() {
+ public Object get(MapEntry entry) {
+ return entry.value;
+ }
+ }, LinkedHashMap.this);
+ }
+ };
+ }
+ return valuesCollection;
+ }
+
+ /**
+ * Remove the entry corresponding to the given key.
+ *
+ * @param key
+ * the key
+ * @return the value associated with the key or null if the key was no in
+ * the map
+ */
+ public Object remove(Object key) {
+ LinkedHashMapEntry m = (LinkedHashMapEntry) removeEntry(key);
+ if (m == null)
+ return null;
+ LinkedHashMapEntry p = m.chainBackward;
+ LinkedHashMapEntry n = m.chainForward;
+ if (p != null)
+ p.chainForward = n;
+ else
+ head = n;
+ if (n != null)
+ n.chainBackward = p;
+ else
+ tail = p;
+ return m.value;
+ }
+
+ /**
+ * This method is queried from the put and putAll methods to check if the
+ * eldest member of the map should be deleted before adding the new member.
+ * If this map was created with accessOrder = true, then the result of
+ * removeEldesrEntry is assumed to be false.
+ *
+ * @param eldest
+ * @return true if the eldest member should be removed
+ */
+ protected boolean removeEldestEntry(Map.Entry eldest) {
+ return false;
+ }
+
+ /**
+ * Removes all mappings from this HashMap, leaving it empty.
+ *
+ * @see #isEmpty()
+ * @see #size()
+ */
+ public void clear() {
+ super.clear();
+ head = tail = null;
+ }
+
+ /**
+ * Answers a new HashMap with the same mappings and size as this HashMap.
+ *
+ * @return a shallow copy of this HashMap
+ *
+ * @see java.lang.Cloneable
+ */
+ public Object clone() {
+ LinkedHashMap map = (LinkedHashMap) super.clone();
+ map.clear();
+ Iterator entries = entrySet().iterator();
+ while (entries.hasNext()) {
+ Map.Entry entry = (Map.Entry) entries.next();
+ map.put(entry.getKey(), entry.getValue());
+ }
+ return map;
+ }
}