0N/A/*
2362N/A * Copyright (c) 1998, 2000, Oracle and/or its affiliates. All rights reserved.
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
2362N/A * published by the Free Software Foundation. Oracle designates this
0N/A * particular file as subject to the "Classpath" exception as provided
2362N/A * by Oracle in the LICENSE file that accompanied this code.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
2362N/A * or visit www.oracle.com if you need additional information or have any
2362N/A * questions.
0N/A */
0N/Apackage com.sun.tools.jdi;
0N/A
0N/Aimport java.io.*;
0N/Aimport java.util.*;
0N/A
0N/A/**
0N/A * Hash table based implementation of the Map interface. This implementation
0N/A * provides all of the optional Map operations, and permits null values and
0N/A * the null key. (HashMap is roughly equivalent to Hashtable, except that it
0N/A * is unsynchronized and permits nulls.) In addition, elements in the map are
0N/A * ordered and doubly linked together.
0N/A * <p>
0N/A * This implementation provides constant-time performance for the basic
0N/A * operations (get and put), assuming the the hash function disperses the
0N/A * elements properly among the buckets. Iteration over Collection views
0N/A * requires time proportional to its size (the number of key-value mappings)
0N/A * and returns elements in the order they are linked. In a HashMap the
0N/A * iteration would require time proportional to the capacity of the map
0N/A * plus the map size.
0N/A * <p>
0N/A * An instance of LinkedHashMap has two parameters that affect its efficiency:
0N/A * its <i>capacity</i> and its <i>load factor</i>. The load factor should be
0N/A * between 0.0 and 1.0. When the number of mappings in the LinkedHashMap exceeds
0N/A * the product of the load factor and the current capacity, the capacity is
0N/A * increased by calling the rehash method which requires time proportional
0N/A * to the number of key-value mappings in the map. Larger load factors
0N/A * use memory more efficiently, at the expense of larger expected time per
0N/A * lookup.
0N/A * <p>
0N/A * If many mappings are to be stored in a LinkedHashMap, creating it with a
0N/A * sufficiently large capacity will allow the mappings to be stored more
0N/A * efficiently than letting it perform automatic rehashing as needed to grow
0N/A * the table.
0N/A * <p>
0N/A * <strong>Note that this implementation is not synchronized.</strong> If
0N/A * multiple threads access a LinkedHashMap concurrently, and at least one of the
0N/A * threads modifies the LinkedHashMap structurally, it <em>must</em> be
0N/A * synchronized externally. (A structural modification is any operation that
0N/A * adds or deletes one or more mappings; merely changing the value associated
0N/A * with a key that is already contained in the Table is not a structural
0N/A * modification.) This is typically accomplished by synchronizing on some
0N/A * object that naturally encapsulates the LinkedHashMap. If no such object
0N/A * exists, the LinkedHashMap should be "wrapped" using the
0N/A * Collections.synchronizedSet method. This is best done at creation time, to
0N/A * prevent accidental unsynchronized access to the LinkedHashMap:
0N/A * <pre>
0N/A * Map m = Collections.synchronizedMap(new LinkedHashMap(...));
0N/A * </pre>
0N/A * <p>
0N/A * The Iterators returned by the iterator methods of the Collections returned
0N/A * by all of LinkedHashMap's "collection view methods" are <em>fail-fast</em>:
0N/A * if the LinkedHashMap is structurally modified at any time after the Iterator
0N/A * is created, in any way except through the Iterator's own remove or add
0N/A * methods, the Iterator will throw a ConcurrentModificationException. Thus,
0N/A * in the face of concurrent modification, the Iterator fails quickly and
0N/A * cleanly, rather than risking arbitrary, non-deterministic behavior at an
0N/A * undetermined time in the future.
0N/A *
0N/A * @author Josh Bloch
0N/A * @author Arthur van Hoff
0N/A * @author Zhenghua Li
0N/A * @see Object#hashCode()
0N/A * @see java.util.Collection
0N/A * @see java.util.Map
0N/A * @see java.util.TreeMap
0N/A * @see java.util.Hashtable
0N/A * @see java.util.HashMap
0N/A */
0N/A
0N/Aimport java.io.Serializable;
0N/A
0N/Apublic class LinkedHashMap extends AbstractMap implements Map, Serializable {
0N/A /**
0N/A * The hash table data.
0N/A */
0N/A private transient Entry table[];
0N/A
0N/A /**
0N/A * The head of the double linked list.
0N/A */
0N/A private transient Entry header;
0N/A
0N/A /**
0N/A * The total number of mappings in the hash table.
0N/A */
0N/A private transient int count;
0N/A
0N/A /**
0N/A * Rehashes the table when count exceeds this threshold.
0N/A */
0N/A private int threshold;
0N/A
0N/A /**
0N/A * The load factor for the LinkedHashMap.
0N/A */
0N/A private float loadFactor;
0N/A
0N/A /**
0N/A * The number of times this LinkedHashMap has been structurally modified
0N/A * Structural modifications are those that change the number of mappings in
0N/A * the LinkedHashMap or otherwise modify its internal structure (e.g.,
0N/A * rehash). This field is used to make iterators on Collection-views of
0N/A * the LinkedHashMap fail-fast. (See ConcurrentModificationException).
0N/A */
0N/A private transient int modCount = 0;
0N/A
0N/A /**
0N/A * Constructs a new, empty LinkedHashMap with the specified initial
0N/A * capacity and the specified load factor.
0N/A *
0N/A * @param initialCapacity the initial capacity of the LinkedHashMap.
0N/A * @param loadFactor a number between 0.0 and 1.0.
0N/A * @exception IllegalArgumentException if the initial capacity is less
0N/A * than or equal to zero, or if the load factor is less than
0N/A * or equal to zero.
0N/A */
0N/A public LinkedHashMap(int initialCapacity, float loadFactor) {
0N/A if (initialCapacity < 0)
0N/A throw new IllegalArgumentException("Illegal Initial Capacity: "+
0N/A initialCapacity);
0N/A if ((loadFactor > 1) || (loadFactor <= 0))
0N/A throw new IllegalArgumentException("Illegal Load factor: "+
0N/A loadFactor);
0N/A if (initialCapacity==0)
0N/A initialCapacity = 1;
0N/A this.loadFactor = loadFactor;
0N/A table = new Entry[initialCapacity];
0N/A threshold = (int)(initialCapacity * loadFactor);
0N/A header = new Entry(-1, null, null, null);
0N/A header.before = header.after = header;
0N/A }
0N/A
0N/A /**
0N/A * Constructs a new, empty LinkedHashMap with the specified initial capacity
0N/A * and default load factor.
0N/A *
0N/A * @param initialCapacity the initial capacity of the LinkedHashMap.
0N/A */
0N/A public LinkedHashMap(int initialCapacity) {
0N/A this(initialCapacity, 0.75f);
0N/A }
0N/A
0N/A /**
0N/A * Constructs a new, empty LinkedHashMap with a default capacity and load
0N/A * factor.
0N/A */
0N/A public LinkedHashMap() {
0N/A this(101, 0.75f);
0N/A }
0N/A
0N/A /**
0N/A * Constructs a new LinkedHashMap with the same mappings as the given
0N/A * Map. The LinkedHashMap is created with a capacity of thrice the number
0N/A * of mappings in the given Map or 11 (whichever is greater), and a
0N/A * default load factor.
0N/A */
0N/A public LinkedHashMap(Map t) {
0N/A this(Math.max(3*t.size(), 11), 0.75f);
0N/A putAll(t);
0N/A }
0N/A
0N/A /**
0N/A * Returns the number of key-value mappings in this Map.
0N/A */
0N/A public int size() {
0N/A return count;
0N/A }
0N/A
0N/A /**
0N/A * Returns true if this Map contains no key-value mappings.
0N/A */
0N/A public boolean isEmpty() {
0N/A return count == 0;
0N/A }
0N/A
0N/A /**
0N/A * Returns true if this LinkedHashMap maps one or more keys to the specified
0N/A * value.
0N/A *
0N/A * @param value value whose presence in this Map is to be tested.
0N/A */
0N/A public boolean containsValue(Object value) {
0N/A if (value==null) {
0N/A for (Entry e = header.after; e != header; e = e.after)
0N/A if (e.value==null)
0N/A return true;
0N/A } else {
0N/A for (Entry e = header.after; e != header; e = e.after)
0N/A if (value.equals(e.value))
0N/A return true;
0N/A }
0N/A return false;
0N/A }
0N/A
0N/A /**
0N/A * Returns true if this LinkedHashMap contains a mapping for the specified
0N/A * key.
0N/A *
0N/A * @param key key whose presence in this Map is to be tested.
0N/A */
0N/A public boolean containsKey(Object key) {
0N/A Entry tab[] = table;
0N/A if (key != null) {
0N/A int hash = key.hashCode();
0N/A int index = (hash & 0x7FFFFFFF) % tab.length;
0N/A for (Entry e = tab[index]; e != null; e = e.next)
0N/A if (e.hash==hash && e.key.equals(key))
0N/A return true;
0N/A } else {
0N/A for (Entry e = tab[0]; e != null; e = e.next)
0N/A if (e.key==null)
0N/A return true;
0N/A }
0N/A
0N/A return false;
0N/A }
0N/A
0N/A /**
0N/A * Returns the value to which this LinkedHashMap maps the specified key.
0N/A * Returns null if the LinkedHashMap contains no mapping for this key.
0N/A * A return value of null does not <em>necessarily</em> indicate that the
0N/A * LinkedHashMap contains no mapping for the key; it's also possible that
0N/A * the LinkedHashMap explicitly maps the key to null. The containsKey
0N/A * operation may be used to distinguish these two cases.
0N/A *
0N/A * @param key key whose associated value is to be returned.
0N/A */
0N/A public Object get(Object key) {
0N/A Entry e = getEntry(key);
0N/A return e==null ? null : e.value;
0N/A }
0N/A
0N/A /**
0N/A * Returns the entry associated with the specified key in the LinkedHashMap.
0N/A * Returns null if the LinkedHashMap contains no mapping for this key.
0N/A */
0N/A private Entry getEntry(Object key) {
0N/A Entry tab[] = table;
0N/A
0N/A if (key != null) {
0N/A int hash = key.hashCode();
0N/A int index = (hash & 0x7FFFFFFF) % tab.length;
0N/A for (Entry e = tab[index]; e != null; e = e.next)
0N/A if ((e.hash == hash) && e.key.equals(key))
0N/A return e;
0N/A } else {
0N/A for (Entry e = tab[0]; e != null; e = e.next)
0N/A if (e.key==null)
0N/A return e;
0N/A }
0N/A
0N/A return null;
0N/A }
0N/A
0N/A /**
0N/A * Rehashes the contents of the LinkedHashMap into a LinkedHashMap with a
0N/A * larger capacity. This method is called automatically when the
0N/A * number of keys in the LinkedHashMap exceeds this LinkedHashMap's capacity
0N/A * and load factor.
0N/A */
0N/A private void rehash() {
0N/A int oldCapacity = table.length;
0N/A Entry oldMap[] = table;
0N/A
0N/A int newCapacity = oldCapacity * 2 + 1;
0N/A Entry newMap[] = new Entry[newCapacity];
0N/A
0N/A modCount++;
0N/A threshold = (int)(newCapacity * loadFactor);
0N/A table = newMap;
0N/A
0N/A for (Entry e = header.after; e != header; e = e.after) {
0N/A int index = (e.hash & 0x7FFFFFFF) % newCapacity;
0N/A e.next = newMap[index];
0N/A newMap[index] = e;
0N/A }
0N/A }
0N/A
0N/A /**
0N/A * Remove an entry from the linked list.
0N/A */
0N/A private void listRemove(Entry entry) {
0N/A if (entry == null) {
0N/A return;
0N/A }
0N/A entry.before.after = entry.after;
0N/A entry.after.before = entry.before;
0N/A }
0N/A
0N/A /**
0N/A * Add the specified entry before the specified existing entry to
0N/A * the linked list.
0N/A */
0N/A private void listAddBefore(Entry entry, Entry existEntry) {
0N/A entry.after = existEntry;
0N/A entry.before = existEntry.before;
0N/A entry.before.after = entry;
0N/A entry.after.before = entry;
0N/A }
0N/A
0N/A /**
0N/A * Returns the position of the mapping for the specified key
0N/A * in the ordered map.
0N/A *
0N/A * @param key the specified key.
0N/A * @return index of the key mapping.
0N/A */
0N/A public int indexOf(Object key) {
0N/A int i = 0;
0N/A if (key == null) {
0N/A for (Entry e = header.after; e != header; e = e.after, i++)
0N/A if (e.key == null)
0N/A return i;
0N/A } else {
0N/A for (Entry e = header.after; e != header; e = e.after, i++)
0N/A if(key.equals(e.key))
0N/A return i;
0N/A }
0N/A return -1;
0N/A }
0N/A
0N/A /**
0N/A * Associates the specified value with the specified key in this
0N/A * LinkedHashMap. If the LinkedHashMap previously contained a mapping for
0N/A * this key, the old value is replaced and the position of this mapping
0N/A * entry in the double linked list remains the same. Otherwise, a new
0N/A * mapping entry is created and inserted into the list before the specified
0N/A * existing mapping entry. The method returns the previous value associated
0N/A * with the specified key, or null if there was no mapping for key. A null
0N/A * return can also indicate that the LinkedHashMap previously associated
0N/A * null with the specified key.
0N/A */
0N/A private Object putAhead(Object key, Object value, Entry existEntry) {
0N/A // Makes sure the key is not already in the LinkedHashMap.
0N/A Entry tab[] = table;
0N/A int hash = 0;
0N/A int index = 0;
0N/A
0N/A if (key != null) {
0N/A hash = key.hashCode();
0N/A index = (hash & 0x7FFFFFFF) % tab.length;
0N/A for (Entry e = tab[index] ; e != null ; e = e.next) {
0N/A if ((e.hash == hash) && e.key.equals(key)) {
0N/A Object old = e.value;
0N/A e.value = value;
0N/A return old;
0N/A }
0N/A }
0N/A } else {
0N/A for (Entry e = tab[0] ; e != null ; e = e.next) {
0N/A if (e.key == null) {
0N/A Object old = e.value;
0N/A e.value = value;
0N/A return old;
0N/A }
0N/A }
0N/A }
0N/A
0N/A modCount++;
0N/A if (count >= threshold) {
0N/A // Rehash the table if the threshold is exceeded
0N/A rehash();
0N/A tab = table;
0N/A index = (hash & 0x7FFFFFFF) % tab.length;
0N/A }
0N/A
0N/A // Creates the new entry.
0N/A Entry e = new Entry(hash, key, value, tab[index]);
0N/A tab[index] = e;
0N/A listAddBefore(e, existEntry);
0N/A count++;
0N/A return null;
0N/A }
0N/A
0N/A /**
0N/A * Associates the specified value with the specified key in this
0N/A * LinkedHashMap and position the mapping at the specified index.
0N/A * If the LinkedHashMap previously contained a mapping for this key,
0N/A * the old value is replaced and the position of this mapping entry
0N/A * in the double linked list remains the same. Otherwise, a new mapping
0N/A * entry is created and inserted into the list at the specified
0N/A * position.
0N/A *
0N/A * @param index the position to put the key-value mapping.
0N/A * @param key key with which the specified value is to be associated.
0N/A * @param value value to be associated with the specified key.
0N/A * @return previous value associated with specified key, or null if there
0N/A * was no mapping for key. A null return can also indicate that
0N/A * the LinkedHashMap previously associated null with the specified
0N/A * key.
0N/A */
0N/A public Object put(int index, Object key, Object value) {
0N/A if (index < 0 || index > count)
0N/A throw new IndexOutOfBoundsException();
0N/A Entry e = header.after;
0N/A if (index == count)
0N/A return putAhead(key, value, header); //fast approach for append
0N/A else {
0N/A for (int i = 0; i < index; i++)
0N/A e = e.after;
0N/A return putAhead(key, value, e);
0N/A }
0N/A }
0N/A
0N/A
0N/A /**
0N/A * Associates the specified value with the specified key in this
0N/A * LinkedHashMap. If the LinkedHashMap previously contained a mapping for
0N/A * this key, the old value is replaced. The mapping entry is also appended
0N/A * to the end of the ordered linked list.
0N/A *
0N/A * @param key key with which the specified value is to be associated.
0N/A * @param value value to be associated with the specified key.
0N/A * @return previous value associated with specified key, or null if there
0N/A * was no mapping for key. A null return can also indicate that
0N/A * the LinkedHashMap previously associated null with the specified
0N/A * key.
0N/A */
0N/A public Object put(Object key, Object value) {
0N/A return putAhead(key, value, header);
0N/A }
0N/A
0N/A /**
0N/A * Removes the mapping for this key from this LinkedHashMap if present.
0N/A * The mapping would also be removed from the double linked list.
0N/A *
0N/A * @param key key whose mapping is to be removed from the Map.
0N/A * @return previous value associated with specified key, or null if there
0N/A * was no mapping for key. A null return can also indicate that
0N/A * the LinkedHashMap previously associated null with the specified
0N/A * key.
0N/A */
0N/A public Object remove(Object key) {
0N/A Entry tab[] = table;
0N/A
0N/A if (key != null) {
0N/A int hash = key.hashCode();
0N/A int index = (hash & 0x7FFFFFFF) % tab.length;
0N/A
0N/A for (Entry e = tab[index], prev = null; e != null;
0N/A prev = e, e = e.next) {
0N/A if ((e.hash == hash) && e.key.equals(key)) {
0N/A modCount++;
0N/A if (prev != null)
0N/A prev.next = e.next;
0N/A else
0N/A tab[index] = e.next;
0N/A
0N/A count--;
0N/A Object oldValue = e.value;
0N/A e.value = null;
0N/A
0N/A listRemove(e);
0N/A return oldValue;
0N/A }
0N/A }
0N/A } else {
0N/A for (Entry e = tab[0], prev = null; e != null;
0N/A prev = e, e = e.next) {
0N/A if (e.key == null) {
0N/A modCount++;
0N/A if (prev != null)
0N/A prev.next = e.next;
0N/A else
0N/A tab[0] = e.next;
0N/A
0N/A count--;
0N/A Object oldValue = e.value;
0N/A e.value = null;
0N/A
0N/A listRemove(e);
0N/A return oldValue;
0N/A }
0N/A }
0N/A }
0N/A
0N/A return null;
0N/A }
0N/A
0N/A /**
0N/A * Copies all of the mappings from the specified Map to this LinkedHashMap
0N/A * These mappings will replace any mappings that this LinkedHashMap had for
0N/A * any of the keys currently in the specified Map.
0N/A *
0N/A * @param t Mappings to be stored in this Map.
0N/A */
0N/A public void putAll(Map t) {
0N/A Iterator i = t.entrySet().iterator();
0N/A while (i.hasNext()) {
0N/A Map.Entry e = (Map.Entry) i.next();
0N/A put(e.getKey(), e.getValue());
0N/A }
0N/A }
0N/A
0N/A /**
0N/A * Removes all mappings from this LinkedHashMap.
0N/A */
0N/A public void clear() {
0N/A Entry tab[] = table;
0N/A modCount++;
0N/A for (int index = tab.length; --index >= 0; )
0N/A tab[index] = null;
0N/A count = 0;
0N/A header.before = header.after = header;
0N/A }
0N/A
0N/A /**
0N/A * Returns a shallow copy of this LinkedHashMap. The keys and values
0N/A * themselves are not cloned.
0N/A */
0N/A public Object clone() {
0N/A return new LinkedHashMap(this);
0N/A }
0N/A
0N/A // Views
0N/A
0N/A private transient Set keySet = null;
0N/A private transient Set entries = null;
0N/A private transient Collection values = null;
0N/A
0N/A /**
0N/A * Returns a Set view of the keys contained in this LinkedHashMap. The Set
0N/A * is backed by the LinkedHashMap, so changes to the LinkedHashMap are
0N/A * reflected in the Set, and vice-versa. The Set supports element removal,
0N/A * which removes the corresponding mapping from the LinkedHashMap, via the
0N/A * Iterator.remove, Set.remove, removeAll retainAll, and clear operations.
0N/A * It does not support the add or addAll operations.
0N/A */
0N/A public Set keySet() {
0N/A if (keySet == null) {
0N/A keySet = new AbstractSet() {
0N/A public Iterator iterator() {
0N/A return new HashIterator(KEYS);
0N/A }
0N/A public int size() {
0N/A return count;
0N/A }
0N/A public boolean contains(Object o) {
0N/A return containsKey(o);
0N/A }
0N/A public boolean remove(Object o) {
0N/A return LinkedHashMap.this.remove(o) != null;
0N/A }
0N/A public void clear() {
0N/A LinkedHashMap.this.clear();
0N/A }
0N/A };
0N/A }
0N/A return keySet;
0N/A }
0N/A
0N/A /**
0N/A * Returns a Collection view of the values contained in this LinkedHashMap.
0N/A * The Collection is backed by the LinkedHashMap, so changes to the
0N/A * LinkedHashMap are reflected in the Collection, and vice-versa. The
0N/A * Collection supports element removal, which removes the corresponding
0N/A * mapping from the LinkedHashMap, via the Iterator.remove,
0N/A * Collection.remove, removeAll, retainAll and clear operations. It does
0N/A * not support the add or addAll operations.
0N/A */
0N/A public Collection values() {
0N/A if (values==null) {
0N/A values = new AbstractCollection() {
0N/A public Iterator iterator() {
0N/A return new HashIterator(VALUES);
0N/A }
0N/A public int size() {
0N/A return count;
0N/A }
0N/A public boolean contains(Object o) {
0N/A return containsValue(o);
0N/A }
0N/A public void clear() {
0N/A LinkedHashMap.this.clear();
0N/A }
0N/A };
0N/A }
0N/A return values;
0N/A }
0N/A
0N/A /**
0N/A * Returns a Collection view of the mappings contained in this
0N/A * LinkedHashMap. Each element in the returned collection is a Map.Entry.
0N/A * The Collection is backed by the LinkedHashMap, so changes to the
0N/A * LinkedHashMap are reflected in the Collection, and vice-versa. The
0N/A * Collection supports element removal, which removes the corresponding
0N/A * mapping from the LinkedHashMap, via the Iterator.remove,
0N/A * Collection.remove, removeAll, retainAll and clear operations. It does
0N/A * not support the add or addAll operations.
0N/A *
0N/A * @see java.util.Map.Entry
0N/A */
0N/A public Set entrySet() {
0N/A if (entries==null) {
0N/A entries = new AbstractSet() {
0N/A public Iterator iterator() {
0N/A return new HashIterator(ENTRIES);
0N/A }
0N/A
0N/A public boolean contains(Object o) {
0N/A if (!(o instanceof Map.Entry))
0N/A return false;
0N/A Map.Entry entry = (Map.Entry)o;
0N/A Object key = entry.getKey();
0N/A Entry tab[] = table;
0N/A int hash = (key==null ? 0 : key.hashCode());
0N/A int index = (hash & 0x7FFFFFFF) % tab.length;
0N/A
0N/A for (Entry e = tab[index]; e != null; e = e.next)
0N/A if (e.hash==hash && e.equals(entry))
0N/A return true;
0N/A return false;
0N/A }
0N/A
0N/A public boolean remove(Object o) {
0N/A if (!(o instanceof Map.Entry))
0N/A return false;
0N/A Map.Entry entry = (Map.Entry)o;
0N/A Object key = entry.getKey();
0N/A Entry tab[] = table;
0N/A int hash = (key==null ? 0 : key.hashCode());
0N/A int index = (hash & 0x7FFFFFFF) % tab.length;
0N/A
0N/A for (Entry e = tab[index], prev = null; e != null;
0N/A prev = e, e = e.next) {
0N/A if (e.hash==hash && e.equals(entry)) {
0N/A modCount++;
0N/A if (prev != null)
0N/A prev.next = e.next;
0N/A else
0N/A tab[index] = e.next;
0N/A
0N/A count--;
0N/A e.value = null;
0N/A listRemove(e);
0N/A return true;
0N/A }
0N/A }
0N/A return false;
0N/A }
0N/A
0N/A public int size() {
0N/A return count;
0N/A }
0N/A
0N/A public void clear() {
0N/A LinkedHashMap.this.clear();
0N/A }
0N/A };
0N/A }
0N/A
0N/A return entries;
0N/A }
0N/A
0N/A /**
0N/A * Compares the specified Object with this Map for equality.
0N/A * Returns true if the given object is also a LinkedHashMap and the two
0N/A * Maps represent the same mappings in the same order. More formally,
0N/A * two Maps <code>t1</code> and <code>t2</code> represent the same mappings
0N/A * if <code>t1.keySet().equals(t2.keySet())</code> and for every
0N/A * key <code>k</code> in <code>t1.keySet()</code>, <code>
0N/A * (t1.get(k)==null ? t2.get(k)==null : t1.get(k).equals(t2.get(k)))
0N/A * </code>.
0N/A * <p>
0N/A * This implementation first checks if the specified Object is this Map;
0N/A * if so it returns true. Then, it checks if the specified Object is
0N/A * a Map whose size is identical to the size of this Set; if not, it
0N/A * it returns false. If so, it iterates over this Map and the specified
0N/A * Map's entrySet() Collection, and checks that the specified Map contains
0N/A * each mapping that this Map contains at the same position. If the
0N/A * specified Map fails to contain such a mapping in the right order, false
0N/A * is returned. If the iteration completes, true is returned.
0N/A *
0N/A * @param o Object to be compared for equality with this Map.
0N/A * @return true if the specified Object is equal to this Map.
0N/A *
0N/A */
0N/A public boolean equals(Object o) {
0N/A if (o == this)
0N/A return true;
0N/A
0N/A if (!(o instanceof LinkedHashMap))
0N/A return false;
0N/A LinkedHashMap t = (LinkedHashMap) o;
0N/A if (t.size() != size())
0N/A return false;
0N/A
0N/A Iterator i1 = entrySet().iterator();
0N/A Iterator i2 = t.entrySet().iterator();
0N/A
0N/A while (i1.hasNext()) {
0N/A Entry e1 = (Entry) i1.next();
0N/A Entry e2 = (Entry) i2.next();
0N/A
0N/A Object key1 = e1.getKey();
0N/A Object value1 = e1.getValue();
0N/A Object key2 = e2.getKey();
0N/A Object value2 = e2.getValue();
0N/A
0N/A if ((key1 == null ? key2 == null : key1.equals(key2)) &&
0N/A (value1 == null ? value2 == null : value1.equals(value2))) {
0N/A continue;
0N/A } else {
0N/A return false;
0N/A }
0N/A }
0N/A return true;
0N/A }
0N/A
0N/A /**
0N/A * LinkedHashMap collision list entry.
0N/A */
0N/A private static class Entry implements Map.Entry {
0N/A int hash;
0N/A Object key;
0N/A Object value;
0N/A Entry next;
0N/A
0N/A // These fields comprise the doubly linked list that is used for
0N/A // iteration.
0N/A Entry before, after;
0N/A
0N/A Entry(int hash, Object key, Object value, Entry next) {
0N/A this.hash = hash;
0N/A this.key = key;
0N/A this.value = value;
0N/A this.next = next;
0N/A }
0N/A
0N/A // Map.Entry Ops
0N/A
0N/A public Object getKey() {
0N/A return key;
0N/A }
0N/A
0N/A public Object getValue() {
0N/A return value;
0N/A }
0N/A
0N/A public Object setValue(Object value) {
0N/A Object oldValue = this.value;
0N/A this.value = value;
0N/A return oldValue;
0N/A }
0N/A
0N/A public boolean equals(Object o) {
0N/A if (!(o instanceof Map.Entry))
0N/A return false;
0N/A Map.Entry e = (Map.Entry)o;
0N/A
0N/A return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
0N/A (value==null ? e.getValue()==null : value.equals(e.getValue()));
0N/A }
0N/A
0N/A public int hashCode() {
0N/A return hash ^ (value==null ? 0 : value.hashCode());
0N/A }
0N/A
0N/A public String toString() {
0N/A return key+"="+value;
0N/A }
0N/A }
0N/A
0N/A // Types of Iterators
0N/A private static final int KEYS = 0;
0N/A private static final int VALUES = 1;
0N/A private static final int ENTRIES = 2;
0N/A
0N/A private class HashIterator implements Iterator {
0N/A private Entry[] table = LinkedHashMap.this.table;
0N/A private Entry entry = null;
0N/A private Entry lastReturned = null;
0N/A private int type;
0N/A
0N/A /**
0N/A * The modCount value that the iterator believes that the backing
0N/A * List should have. If this expectation is violated, the iterator
0N/A * has detected concurrent modification.
0N/A */
0N/A private int expectedModCount = modCount;
0N/A
0N/A HashIterator(int type) {
0N/A this.type = type;
0N/A this.entry = LinkedHashMap.this.header.after;
0N/A }
0N/A
0N/A public boolean hasNext() {
0N/A return entry != header;
0N/A }
0N/A
0N/A public Object next() {
0N/A if (modCount != expectedModCount)
0N/A throw new ConcurrentModificationException();
0N/A if (entry == LinkedHashMap.this.header)
0N/A throw new NoSuchElementException();
0N/A
0N/A Entry e = lastReturned = entry;
0N/A entry = e.after;
0N/A return type == KEYS ? e.key : (type == VALUES ? e.value : e);
0N/A }
0N/A
0N/A public void remove() {
0N/A if (lastReturned == null)
0N/A throw new IllegalStateException();
0N/A if (modCount != expectedModCount)
0N/A throw new ConcurrentModificationException();
0N/A
0N/A Entry[] tab = LinkedHashMap.this.table;
0N/A int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
0N/A
0N/A for (Entry e = tab[index], prev = null; e != null;
0N/A prev = e, e = e.next) {
0N/A if (e == lastReturned) {
0N/A modCount++;
0N/A expectedModCount++;
0N/A if (prev == null)
0N/A tab[index] = e.next;
0N/A else
0N/A prev.next = e.next;
0N/A count--;
0N/A listRemove(e);
0N/A lastReturned = null;
0N/A return;
0N/A }
0N/A }
0N/A throw new ConcurrentModificationException();
0N/A }
0N/A }
0N/A
0N/A /**
0N/A * Save the state of the LinkedHashMap to a stream (i.e., serialize it).
0N/A * The objects will be written out in the order they are linked
0N/A * in the list.
0N/A */
0N/A private void writeObject(java.io.ObjectOutputStream s)
0N/A throws IOException
0N/A {
0N/A // Write out the threshold, loadfactor, and any hidden stuff
0N/A s.defaultWriteObject();
0N/A
0N/A // Write out number of buckets
0N/A s.writeInt(table.length);
0N/A
0N/A // Write out size (number of Mappings)
0N/A s.writeInt(count);
0N/A
0N/A // Write out keys and values (alternating)
0N/A for (Entry e = header.after; e != header; e = e.after) {
0N/A s.writeObject(e.key);
0N/A s.writeObject(e.value);
0N/A }
0N/A }
0N/A
0N/A /**
0N/A * Reconstitute the LinkedHashMap from a stream (i.e., deserialize it).
0N/A */
0N/A private void readObject(java.io.ObjectInputStream s)
0N/A throws IOException, ClassNotFoundException
0N/A {
0N/A // Read in the threshold, loadfactor, and any hidden stuff
0N/A s.defaultReadObject();
0N/A
0N/A // Read in number of buckets and allocate the bucket array;
0N/A int numBuckets = s.readInt();
0N/A table = new Entry[numBuckets];
0N/A header = new Entry(-1, null, null, null);
0N/A header.before = header;
0N/A header.after = header;
0N/A
0N/A // Read in size (number of Mappings)
0N/A int size = s.readInt();
0N/A
0N/A // Read the keys and values, and put the mappings in the LinkedHashMap
0N/A for (int i=0; i<size; i++) {
0N/A Object key = s.readObject();
0N/A Object value = s.readObject();
0N/A put(key, value);
0N/A }
0N/A }
0N/A}