jdk/src/share/classes/com/sun/tools/jdi/LinkedHashMap.java

/*
 * Copyright 1998-2000 Sun Microsystems, Inc.  All Rights Reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Sun designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Sun in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 * CA 95054 USA or visit www.sun.com if you need additional information or
 * have any questions.
 */
package com.sun.tools.jdi;

import java.io.*;
import java.util.*;

/**
 * Hash table based implementation of the Map interface.  This implementation
 * provides all of the optional Map operations, and permits null values and
 * the null key.  (HashMap is roughly equivalent to Hashtable, except that it
 * is unsynchronized and permits nulls.) In addition, elements in the map are
 * ordered and doubly linked together.
 * <p>
 * This implementation provides constant-time performance for the basic
 * operations (get and put), assuming the the hash function disperses the
 * elements properly among the buckets.  Iteration over Collection views
 * requires time proportional to its size (the number of key-value mappings)
 * and returns elements in the order they are linked. In a HashMap the
 * iteration would require time  proportional to the capacity of the map
 * plus the map size.
 * <p>
 * An instance of LinkedHashMap has two parameters that affect its efficiency:
 * its <i>capacity</i> and its <i>load factor</i>. The load factor should be
 * between 0.0 and 1.0. When the number of mappings in the LinkedHashMap exceeds
 * the product of the load factor and the current capacity, the capacity is
 * increased by calling the rehash method which requires time proportional
 * to the number of key-value mappings in the map. Larger load factors
 * use memory more efficiently, at the expense of larger expected time per
 * lookup.
 * <p>
 * If many mappings are to be stored in a LinkedHashMap, creating it with a
 * sufficiently large capacity will allow the mappings to be stored more
 * efficiently than letting it perform automatic rehashing as needed to grow
 * the table.
 * <p>
 * <strong>Note that this implementation is not synchronized.</strong> If
 * multiple threads access a LinkedHashMap concurrently, and at least one of the
 * threads modifies the LinkedHashMap structurally, it <em>must</em> be
 * synchronized externally.  (A structural modification is any operation that
 * adds or deletes one or more mappings; merely changing the value associated
 * with a key that is already contained in the Table is not a structural
 * modification.)  This is typically accomplished by synchronizing on some
 * object that naturally encapsulates the LinkedHashMap.  If no such object
 * exists, the LinkedHashMap should be "wrapped" using the
 * Collections.synchronizedSet method.  This is best done at creation time, to
 * prevent accidental unsynchronized access to the LinkedHashMap:
 * <pre>
 *      Map m = Collections.synchronizedMap(new LinkedHashMap(...));
 * </pre>
 * <p>
 * The Iterators returned by the iterator methods of the Collections returned
 * by all of LinkedHashMap's "collection view methods" are <em>fail-fast</em>:
 * if the LinkedHashMap is structurally modified at any time after the Iterator
 * is created, in any way except through the Iterator's own remove or add
 * methods, the Iterator will throw a ConcurrentModificationException.  Thus,
 * in the face of concurrent modification, the Iterator fails quickly and
 * cleanly, rather than risking arbitrary, non-deterministic behavior at an
 * undetermined time in the future.
 *
 * @author  Josh Bloch
 * @author  Arthur van Hoff
 * @author  Zhenghua Li
 * @see     Object#hashCode()
 * @see     java.util.Collection
 * @see     java.util.Map
 * @see     java.util.TreeMap
 * @see     java.util.Hashtable
 * @see     java.util.HashMap
 */

import java.io.Serializable;

public class LinkedHashMap extends AbstractMap implements Map, Serializable {
    /**
     * The hash table data.
     */
    private transient Entry table[];

    /**
     * The head of the double linked list.
     */
    private transient Entry header;

    /**
     * The total number of mappings in the hash table.
     */
    private transient int count;

    /**
     * Rehashes the table when count exceeds this threshold.
     */
    private int threshold;

    /**
     * The load factor for the LinkedHashMap.
     */
    private float loadFactor;

    /**
     * The number of times this LinkedHashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the LinkedHashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the LinkedHashMap fail-fast.  (See ConcurrentModificationException).
     */
    private transient int modCount = 0;

    /**
     * Constructs a new, empty LinkedHashMap with the specified initial
     * capacity and the specified load factor.
     *
     * @param      initialCapacity   the initial capacity of the LinkedHashMap.
     * @param      loadFactor        a number between 0.0 and 1.0.
     * @exception  IllegalArgumentException  if the initial capacity is less
     *               than or equal to zero, or if the load factor is less than
     *               or equal to zero.
     */
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Initial Capacity: "+
                                               initialCapacity);
        if ((loadFactor > 1) || (loadFactor <= 0))
            throw new IllegalArgumentException("Illegal Load factor: "+
                                               loadFactor);
        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry[initialCapacity];
        threshold = (int)(initialCapacity * loadFactor);
        header = new Entry(-1, null, null, null);
        header.before = header.after = header;
    }

    /**
     * Constructs a new, empty LinkedHashMap with the specified initial capacity
     * and default load factor.
     *
     * @param   initialCapacity   the initial capacity of the LinkedHashMap.
     */
    public LinkedHashMap(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

    /**
     * Constructs a new, empty LinkedHashMap with a default capacity and load
     * factor.
     */
    public LinkedHashMap() {
        this(101, 0.75f);
    }

    /**
     * Constructs a new LinkedHashMap with the same mappings as the given
     * Map.  The LinkedHashMap is created with a capacity of thrice the number
     * of mappings in the given Map or 11 (whichever is greater), and a
     * default load factor.
     */
    public LinkedHashMap(Map t) {
        this(Math.max(3*t.size(), 11), 0.75f);
        putAll(t);
    }

    /**
     * Returns the number of key-value mappings in this Map.
     */
    public int size() {
        return count;
    }

    /**
     * Returns true if this Map contains no key-value mappings.
     */
    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * Returns true if this LinkedHashMap maps one or more keys to the specified
     * value.
     *
     * @param value value whose presence in this Map is to be tested.
     */
    public boolean containsValue(Object value) {
        if (value==null) {
            for (Entry e = header.after; e != header; e = e.after)
                if (e.value==null)
                    return true;
        } else {
            for (Entry e = header.after; e != header; e = e.after)
                if (value.equals(e.value))
                    return true;
        }
        return false;
    }

    /**
     * Returns true if this LinkedHashMap contains a mapping for the specified
     * key.
     *
     * @param key key whose presence in this Map is to be tested.
     */
    public boolean containsKey(Object key) {
        Entry tab[] = table;
        if (key != null) {
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            for (Entry e = tab[index]; e != null; e = e.next)
                if (e.hash==hash && e.key.equals(key))
                    return true;
        } else {
            for (Entry e = tab[0]; e != null; e = e.next)
                if (e.key==null)
                    return true;
        }

        return false;
    }

    /**
     * Returns the value to which this LinkedHashMap maps the specified key.
     * Returns null if the LinkedHashMap contains no mapping for this key.
     * A return value of null does not <em>necessarily</em> indicate that the
     * LinkedHashMap contains no mapping for the key; it's also possible that
     * the LinkedHashMap explicitly maps the key to null.  The containsKey
     * operation may be used to distinguish these two cases.
     *
     * @param key key whose associated value is to be returned.
     */
    public Object get(Object key) {
        Entry e = getEntry(key);
        return e==null ? null : e.value;
    }

    /**
     * Returns the entry associated with the specified key in the LinkedHashMap.
     * Returns null if the LinkedHashMap contains no mapping for this key.
     */
    private Entry getEntry(Object key) {
        Entry tab[] = table;

        if (key != null) {
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            for (Entry e = tab[index]; e != null; e = e.next)
                if ((e.hash == hash) && e.key.equals(key))
                    return e;
        } else {
            for (Entry e = tab[0]; e != null; e = e.next)
                if (e.key==null)
                    return e;
        }

        return null;
    }

    /**
     * Rehashes the contents of the LinkedHashMap into a LinkedHashMap with a
     * larger capacity. This method is called automatically when the
     * number of keys in the LinkedHashMap exceeds this LinkedHashMap's capacity
     * and load factor.
     */
    private void rehash() {
        int oldCapacity = table.length;
        Entry oldMap[] = table;

        int newCapacity = oldCapacity * 2 + 1;
        Entry newMap[] = new Entry[newCapacity];

        modCount++;
        threshold = (int)(newCapacity * loadFactor);
        table = newMap;

        for (Entry e = header.after; e != header; e = e.after) {
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = newMap[index];
            newMap[index] = e;
        }
    }

    /**
     * Remove an entry from the linked list.
     */
    private void listRemove(Entry entry) {
        if (entry == null) {
            return;
        }
        entry.before.after = entry.after;
        entry.after.before = entry.before;
    }

   /**
    * Add the specified entry before the specified existing entry to
    * the linked list.
    */
    private void listAddBefore(Entry entry, Entry existEntry) {
        entry.after = existEntry;
        entry.before = existEntry.before;
        entry.before.after = entry;
        entry.after.before = entry;
    }

    /**
     * Returns the position of the mapping for the specified key
     * in the ordered map.
     *
     * @param key the specified key.
     * @return index of the key mapping.
     */
    public int indexOf(Object key) {
        int i = 0;
        if (key == null) {
            for (Entry e = header.after; e != header; e = e.after, i++)
                if (e.key == null)
                    return i;
        } else {
            for (Entry e = header.after; e != header; e = e.after, i++)
                if(key.equals(e.key))
                    return i;
        }
        return -1;
    }

    /**
     * Associates the specified value with the specified key in this
     * LinkedHashMap. If the LinkedHashMap previously contained a mapping for
     * this key, the old value is replaced and the position of this mapping
     * entry in the double linked list remains the same. Otherwise, a new
     * mapping entry is created and inserted into the list before the specified
     * existing mapping entry. The method returns the previous value associated
     * with the specified key, or null if there was no mapping for key.  A null
     * return can also indicate that the LinkedHashMap previously associated
     * null with the specified key.
     */
    private Object putAhead(Object key, Object value, Entry existEntry) {
        // Makes sure the key is not already in the LinkedHashMap.
        Entry tab[] = table;
        int hash = 0;
        int index = 0;

        if (key != null) {
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
            for (Entry e = tab[index] ; e != null ; e = e.next) {
                if ((e.hash == hash) && e.key.equals(key)) {
                    Object old = e.value;
                    e.value = value;
                    return old;
                }
            }
        } else {
            for (Entry e = tab[0] ; e != null ; e = e.next) {
                if (e.key == null) {
                    Object old = e.value;
                    e.value = value;
                    return old;
                }
            }
        }

        modCount++;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();
            tab = table;
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        Entry e = new Entry(hash, key, value, tab[index]);
        tab[index] = e;
        listAddBefore(e, existEntry);
        count++;
        return null;
    }

    /**
     * Associates the specified value with the specified key in this
     * LinkedHashMap and position the mapping at the specified index.
     * If the LinkedHashMap previously contained a mapping for this key,
     * the old value is replaced and the position of this mapping entry
     * in the double linked list remains the same. Otherwise, a new mapping
     * entry is created and inserted into the list at the specified
     * position.
     *
     * @param index     the position to put the key-value mapping.
     * @param key       key with which the specified value is to be associated.
     * @param value     value to be associated with the specified key.
     * @return previous value associated with specified key, or null if there
     *         was no mapping for key.  A null return can also indicate that
     *         the LinkedHashMap previously associated null with the specified
     *         key.
     */
    public Object put(int index, Object key, Object value) {
        if (index < 0 || index > count)
            throw new IndexOutOfBoundsException();
        Entry e = header.after;
        if (index == count)
            return putAhead(key, value, header); //fast approach for append
        else {
            for (int i = 0; i < index; i++)
                e = e.after;
            return putAhead(key, value, e);
        }
    }


    /**
     * Associates the specified value with the specified key in this
     * LinkedHashMap. If the LinkedHashMap previously contained a mapping for
     * this key, the old value is replaced. The mapping entry is also appended
     * to the end of the ordered linked list.
     *
     * @param key key with which the specified value is to be associated.
     * @param value value to be associated with the specified key.
     * @return previous value associated with specified key, or null if there
     *         was no mapping for key.  A null return can also indicate that
     *         the LinkedHashMap previously associated null with the specified
     *         key.
     */
    public Object put(Object key, Object value) {
        return putAhead(key, value, header);
    }

    /**
     * Removes the mapping for this key from this LinkedHashMap if present.
     * The mapping would also be removed from the double linked list.
     *
     * @param key key whose mapping is to be removed from the Map.
     * @return previous value associated with specified key, or null if there
     *         was no mapping for key.  A null return can also indicate that
     *         the LinkedHashMap previously associated null with the specified
     *         key.
     */
    public Object remove(Object key) {
        Entry tab[] = table;

        if (key != null) {
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;

            for (Entry e = tab[index], prev = null; e != null;
                 prev = e, e = e.next) {
                if ((e.hash == hash) && e.key.equals(key)) {
                    modCount++;
                    if (prev != null)
                        prev.next = e.next;
                    else
                        tab[index] = e.next;

                    count--;
                    Object oldValue = e.value;
                    e.value = null;

                    listRemove(e);
                    return oldValue;
                }
            }
        } else {
            for (Entry e = tab[0], prev = null; e != null;
                 prev = e, e = e.next) {
                if (e.key == null) {
                    modCount++;
                    if (prev != null)
                        prev.next = e.next;
                    else
                        tab[0] = e.next;

                    count--;
                    Object oldValue = e.value;
                    e.value = null;

                    listRemove(e);
                    return oldValue;
                }
            }
        }

        return null;
    }

    /**
     * Copies all of the mappings from the specified Map to this LinkedHashMap
     * These mappings will replace any mappings that this LinkedHashMap had for
     * any of the keys currently in the specified Map.
     *
      * @param t Mappings to be stored in this Map.
     */
    public void putAll(Map t) {
        Iterator i = t.entrySet().iterator();
        while (i.hasNext()) {
            Map.Entry e = (Map.Entry) i.next();
            put(e.getKey(), e.getValue());
        }
    }

    /**
     * Removes all mappings from this LinkedHashMap.
     */
    public void clear() {
        Entry tab[] = table;
        modCount++;
        for (int index = tab.length; --index >= 0; )
            tab[index] = null;
        count = 0;
        header.before = header.after = header;
    }

    /**
     * Returns a shallow copy of this LinkedHashMap. The keys and values
     * themselves are not cloned.
     */
    public Object clone() {
        return new LinkedHashMap(this);
    }

    // Views

    private transient Set keySet = null;
    private transient Set entries = null;
    private transient Collection values = null;

    /**
     * Returns a Set view of the keys contained in this LinkedHashMap.  The Set
     * is backed by the LinkedHashMap, so changes to the LinkedHashMap are
     * reflected in the Set, and vice-versa.  The Set supports element removal,
     * which removes the corresponding mapping from the LinkedHashMap, via the
     * Iterator.remove, Set.remove, removeAll retainAll, and clear operations.
     * It does not support the add or addAll operations.
     */
    public Set keySet() {
        if (keySet == null) {
            keySet = new AbstractSet() {
                public Iterator iterator() {
                    return new HashIterator(KEYS);
                }
                public int size() {
                    return count;
                }
                public boolean contains(Object o) {
                    return containsKey(o);
                }
                public boolean remove(Object o) {
                    return LinkedHashMap.this.remove(o) != null;
                }
                public void clear() {
                    LinkedHashMap.this.clear();
                }
            };
        }
        return keySet;
    }

    /**
     * Returns a Collection view of the values contained in this LinkedHashMap.
     * The Collection is backed by the LinkedHashMap, so changes to the
     * LinkedHashMap are reflected in the Collection, and vice-versa.  The
     * Collection supports element removal, which removes the corresponding
     * mapping from the LinkedHashMap, via the Iterator.remove,
     * Collection.remove, removeAll, retainAll and clear operations.  It does
     * not support the add or addAll operations.
     */
    public Collection values() {
        if (values==null) {
            values = new AbstractCollection() {
                public Iterator iterator() {
                    return new HashIterator(VALUES);
                }
                public int size() {
                    return count;
                }
                public boolean contains(Object o) {
                    return containsValue(o);
                }
                public void clear() {
                    LinkedHashMap.this.clear();
                }
            };
        }
        return values;
    }

    /**
     * Returns a Collection view of the mappings contained in this
     * LinkedHashMap. Each element in the returned collection is a Map.Entry.
     * The Collection is backed by the LinkedHashMap, so changes to the
     * LinkedHashMap are reflected in the Collection, and vice-versa.  The
     * Collection supports element removal, which removes the corresponding
     * mapping from the LinkedHashMap, via the Iterator.remove,
     * Collection.remove, removeAll, retainAll and clear operations.  It does
     * not support the add or addAll operations.
     *
     * @see   java.util.Map.Entry
     */
    public Set entrySet() {
        if (entries==null) {
            entries = new AbstractSet() {
                public Iterator iterator() {
                    return new HashIterator(ENTRIES);
                }

                public boolean contains(Object o) {
                    if (!(o instanceof Map.Entry))
                        return false;
                    Map.Entry entry = (Map.Entry)o;
                    Object key = entry.getKey();
                    Entry tab[] = table;
                    int hash = (key==null ? 0 : key.hashCode());
                    int index = (hash & 0x7FFFFFFF) % tab.length;

                    for (Entry e = tab[index]; e != null; e = e.next)
                        if (e.hash==hash && e.equals(entry))
                            return true;
                    return false;
                }

                public boolean remove(Object o) {
                    if (!(o instanceof Map.Entry))
                        return false;
                    Map.Entry entry = (Map.Entry)o;
                    Object key = entry.getKey();
                    Entry tab[] = table;
                    int hash = (key==null ? 0 : key.hashCode());
                    int index = (hash & 0x7FFFFFFF) % tab.length;

                    for (Entry e = tab[index], prev = null; e != null;
                         prev = e, e = e.next) {
                        if (e.hash==hash && e.equals(entry)) {
                            modCount++;
                            if (prev != null)
                                prev.next = e.next;
                            else
                                tab[index] = e.next;

                            count--;
                            e.value = null;
                            listRemove(e);
                            return true;
                        }
                    }
                    return false;
                }

                public int size() {
                    return count;
                }

                public void clear() {
                    LinkedHashMap.this.clear();
                }
            };
        }

        return entries;
    }

    /**
     * Compares the specified Object with this Map for equality.
     * Returns true if the given object is also a LinkedHashMap and the two
     * Maps represent the same mappings in the same order.  More formally,
     * two Maps <code>t1</code> and <code>t2</code> represent the same mappings
     * if <code>t1.keySet().equals(t2.keySet())</code> and for every
     * key <code>k</code> in <code>t1.keySet()</code>, <code>
     * (t1.get(k)==null ? t2.get(k)==null : t1.get(k).equals(t2.get(k)))
     * </code>.
     * <p>
     * This implementation first checks if the specified Object is this Map;
     * if so it returns true.  Then, it checks if the specified Object is
     * a Map whose size is identical to the size of this Set; if not, it
     * it returns false.  If so, it iterates over this Map and the specified
     * Map's entrySet() Collection, and checks that the specified Map contains
     * each mapping that this Map contains at the same position.  If the
     * specified Map fails to contain such a mapping in the right order, false
     * is returned.  If the iteration completes, true is returned.
     *
     * @param o Object to be compared for equality with this Map.
     * @return true if the specified Object is equal to this Map.
     *
     */
    public boolean equals(Object o) {
        if (o == this)
            return true;

        if (!(o instanceof LinkedHashMap))
            return false;
        LinkedHashMap t = (LinkedHashMap) o;
        if (t.size() != size())
            return false;

        Iterator i1 = entrySet().iterator();
        Iterator i2 = t.entrySet().iterator();

        while (i1.hasNext()) {
            Entry e1 = (Entry) i1.next();
            Entry e2 = (Entry) i2.next();

            Object key1 = e1.getKey();
            Object value1 = e1.getValue();
            Object key2 = e2.getKey();
            Object value2 = e2.getValue();

            if ((key1 == null ? key2 == null : key1.equals(key2)) &&
                (value1 == null ? value2 == null : value1.equals(value2))) {
                continue;
            } else {
                return false;
            }
        }
        return true;
    }

    /**
     * LinkedHashMap collision list entry.
     */
    private static class Entry implements Map.Entry {
        int hash;
        Object key;
        Object value;
        Entry next;

        // These fields comprise the doubly linked list that is used for
        // iteration.
        Entry before, after;

        Entry(int hash, Object key, Object value, Entry next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        // Map.Entry Ops

        public Object getKey() {
            return key;
        }

        public Object getValue() {
            return value;
        }

        public Object setValue(Object value) {
            Object oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;

            return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
               (value==null ? e.getValue()==null : value.equals(e.getValue()));
        }

        public int hashCode() {
            return hash ^ (value==null ? 0 : value.hashCode());
        }

        public String toString() {
            return key+"="+value;
        }
    }

    // Types of Iterators
    private static final int KEYS = 0;
    private static final int VALUES = 1;
    private static final int ENTRIES = 2;

    private class HashIterator implements Iterator {
        private Entry[] table = LinkedHashMap.this.table;
        private Entry entry = null;
        private Entry lastReturned = null;
        private int type;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        private int expectedModCount = modCount;

        HashIterator(int type) {
            this.type = type;
            this.entry = LinkedHashMap.this.header.after;
        }

        public boolean hasNext() {
            return entry != header;
        }

        public Object next() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (entry == LinkedHashMap.this.header)
                throw new NoSuchElementException();

            Entry e = lastReturned = entry;
            entry = e.after;
            return type == KEYS ? e.key : (type == VALUES ? e.value : e);
        }

        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            Entry[] tab = LinkedHashMap.this.table;
            int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;

            for (Entry e = tab[index], prev = null; e != null;
                 prev = e, e = e.next) {
                if (e == lastReturned) {
                    modCount++;
                    expectedModCount++;
                    if (prev == null)
                        tab[index] = e.next;
                    else
                        prev.next = e.next;
                    count--;
                    listRemove(e);
                    lastReturned = null;
                    return;
                }
            }
            throw new ConcurrentModificationException();
        }
    }

    /**
     * Save the state of the LinkedHashMap to a stream (i.e., serialize it).
     * The objects will be written out in the order they are linked
     * in the list.
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws IOException
    {
        // Write out the threshold, loadfactor, and any hidden stuff
        s.defaultWriteObject();

        // Write out number of buckets
        s.writeInt(table.length);

        // Write out size (number of Mappings)
        s.writeInt(count);

        // Write out keys and values (alternating)
        for (Entry e = header.after; e != header; e = e.after) {
            s.writeObject(e.key);
            s.writeObject(e.value);
        }
    }

    /**
     * Reconstitute the LinkedHashMap from a stream (i.e., deserialize it).
     */
    private void readObject(java.io.ObjectInputStream s)
         throws IOException, ClassNotFoundException
    {
        // Read in the threshold, loadfactor, and any hidden stuff
        s.defaultReadObject();

        // Read in number of buckets and allocate the bucket array;
        int numBuckets = s.readInt();
        table = new Entry[numBuckets];
        header = new Entry(-1, null, null, null);
        header.before = header;
        header.after = header;

        // Read in size (number of Mappings)
        int size = s.readInt();

        // Read the keys and values, and put the mappings in the LinkedHashMap
        for (int i=0; i<size; i++) {
            Object key = s.readObject();
            Object value = s.readObject();
            put(key, value);
        }
    }
}