harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From smish...@apache.org
Subject svn commit: r407700 [1/2] - in /incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util: HashMap.java LinkedHashMap.java WeakHashMap.java
Date Fri, 19 May 2006 03:50:08 GMT
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;
+    }
 }



Mime
View raw message