obtained gcc-4.6.4.tar.bz2 from upstream website;upstream

verified gcc-4.6.4.tar.bz2.sig;
imported gcc-4.6.4 source tree from verified upstream tarball.

downloading a git-generated archive based on the 'upstream' tag
should provide you with a source tree that is binary identical
to the one extracted from the above tarball.

if you have obtained the source via the command 'git clone',
however, do note that line-endings of files in your working
directory might differ from line-endings of the respective
files in the upstream repository.

1 files changed, 907 insertions, 0 deletions

diff --git a/libjava/classpath/java/util/HashMap.java b/libjava/classpath/java/util/HashMap.java
new file mode 100644
index 000000000..55d81c620
--- /dev/null
+++ b/libjava/classpath/java/util/HashMap.java
@@ -0,0 +1,907 @@
+/* HashMap.java -- a class providing a basic hashtable data structure,
+   mapping Object --> Object
+   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005  Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301 USA.
+
+Linking this library statically or dynamically with other modules is
+making a combined work based on this library.  Thus, the terms and
+conditions of the GNU General Public License cover the whole
+combination.
+
+As a special exception, the copyright holders of this library give you
+permission to link this library with independent modules to produce an
+executable, regardless of the license terms of these independent
+modules, and to copy and distribute the resulting executable under
+terms of your choice, provided that you also meet, for each linked
+independent module, the terms and conditions of the license of that
+module.  An independent module is a module which is not derived from
+or based on this library.  If you modify this library, you may extend
+this exception to your version of the library, but you are not
+obligated to do so.  If you do not wish to do so, delete this
+exception statement from your version. */
+
+
+package java.util;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+
+// NOTE: This implementation is very similar to that of Hashtable. If you fix
+// a bug in here, chances are you should make a similar change to the Hashtable
+// code.
+
+// NOTE: This implementation has some nasty coding style in order to
+// support LinkedHashMap, which extends this.
+
+/**
+ * This class provides a hashtable-backed implementation of the
+ * Map interface.
+ * <p>
+ *
+ * It uses a hash-bucket approach; that is, hash collisions are handled
+ * by linking the new node off of the pre-existing node (or list of
+ * nodes).  In this manner, techniques such as linear probing (which
+ * can cause primary clustering) and rehashing (which does not fit very
+ * well with Java's method of precomputing hash codes) are avoided.
+ * <p>
+ *
+ * Under ideal circumstances (no collisions), HashMap offers O(1)
+ * performance on most operations (<code>containsValue()</code> is,
+ * of course, O(n)).  In the worst case (all keys map to the same
+ * hash code -- very unlikely), most operations are O(n).
+ * <p>
+ *
+ * HashMap is part of the JDK1.2 Collections API.  It differs from
+ * Hashtable in that it accepts the null key and null values, and it
+ * does not support "Enumeration views." Also, it is not synchronized;
+ * if you plan to use it in multiple threads, consider using:<br>
+ * <code>Map m = Collections.synchronizedMap(new HashMap(...));</code>
+ * <p>
+ *
+ * The iterators are <i>fail-fast</i>, meaning that any structural
+ * modification, except for <code>remove()</code> called on the iterator
+ * itself, cause the iterator to throw a
+ * <code>ConcurrentModificationException</code> rather than exhibit
+ * non-deterministic behavior.
+ *
+ * @author Jon Zeppieri
+ * @author Jochen Hoenicke
+ * @author Bryce McKinlay
+ * @author Eric Blake (ebb9@email.byu.edu)
+ * @see Object#hashCode()
+ * @see Collection
+ * @see Map
+ * @see TreeMap
+ * @see LinkedHashMap
+ * @see IdentityHashMap
+ * @see Hashtable
+ * @since 1.2
+ * @status updated to 1.4
+ */
+public class HashMap<K, V> extends AbstractMap<K, V>
+  implements Map<K, V>, Cloneable, Serializable
+{
+  /**
+   * Default number of buckets. This is the value the JDK 1.3 uses. Some
+   * early documentation specified this value as 101. That is incorrect.
+   * Package visible for use by HashSet.
+   */
+  static final int DEFAULT_CAPACITY = 11;
+
+  /**
+   * The default load factor; this is explicitly specified by the spec.
+   * Package visible for use by HashSet.
+   */
+  static final float DEFAULT_LOAD_FACTOR = 0.75f;
+
+  /**
+   * Compatible with JDK 1.2.
+   */
+  private static final long serialVersionUID = 362498820763181265L;
+
+  /**
+   * The rounded product of the capacity and the load factor; when the number
+   * of elements exceeds the threshold, the HashMap calls
+   * <code>rehash()</code>.
+   * @serial the threshold for rehashing
+   */
+  private int threshold;
+
+  /**
+   * Load factor of this HashMap:  used in computing the threshold.
+   * Package visible for use by HashSet.
+   * @serial the load factor
+   */
+  final float loadFactor;
+
+  /**
+   * Array containing the actual key-value mappings.
+   * Package visible for use by nested and subclasses.
+   */
+  transient HashEntry<K, V>[] buckets;
+
+  /**
+   * Counts the number of modifications this HashMap has undergone, used
+   * by Iterators to know when to throw ConcurrentModificationExceptions.
+   * Package visible for use by nested and subclasses.
+   */
+  transient int modCount;
+
+  /**
+   * The size of this HashMap:  denotes the number of key-value pairs.
+   * Package visible for use by nested and subclasses.
+   */
+  transient int size;
+
+  /**
+   * The cache for {@link #entrySet()}.
+   */
+  private transient Set<Map.Entry<K, V>> entries;
+
+  /**
+   * Class to represent an entry in the hash table. Holds a single key-value
+   * pair. Package visible for use by subclass.
+   *
+   * @author Eric Blake (ebb9@email.byu.edu)
+   */
+  static class HashEntry<K, V> extends AbstractMap.SimpleEntry<K, V>
+  {
+    /**
+     * The next entry in the linked list. Package visible for use by subclass.
+     */
+    HashEntry<K, V> next;
+
+    /**
+     * Simple constructor.
+     * @param key the key
+     * @param value the value
+     */
+    HashEntry(K key, V value)
+    {
+      super(key, value);
+    }
+
+    /**
+     * Called when this entry is accessed via {@link #put(Object, Object)}.
+     * This version does nothing, but in LinkedHashMap, it must do some
+     * bookkeeping for access-traversal mode.
+     */
+    void access()
+    {
+    }
+
+    /**
+     * Called when this entry is removed from the map. This version simply
+     * returns the value, but in LinkedHashMap, it must also do bookkeeping.
+     *
+     * @return the value of this key as it is removed
+     */
+    V cleanup()
+    {
+      return value;
+    }
+  }
+
+  /**
+   * Construct a new HashMap with the default capacity (11) and the default
+   * load factor (0.75).
+   */
+  public HashMap()
+  {
+    this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
+  }
+
+  /**
+   * Construct a new HashMap from the given Map, with initial capacity
+   * the greater of the size of <code>m</code> or the default of 11.
+   * <p>
+   *
+   * Every element in Map m will be put into this new HashMap.
+   *
+   * @param m a Map whose key / value pairs will be put into the new HashMap.
+   *        <b>NOTE: key / value pairs are not cloned in this constructor.</b>
+   * @throws NullPointerException if m is null
+   */
+  public HashMap(Map<? extends K, ? extends V> m)
+  {
+    this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
+    putAll(m);
+  }
+
+  /**
+   * Construct a new HashMap with a specific inital capacity and
+   * default load factor of 0.75.
+   *
+   * @param initialCapacity the initial capacity of this HashMap (&gt;=0)
+   * @throws IllegalArgumentException if (initialCapacity &lt; 0)
+   */
+  public HashMap(int initialCapacity)
+  {
+    this(initialCapacity, DEFAULT_LOAD_FACTOR);
+  }
+
+  /**
+   * Construct a new HashMap with a specific inital capacity and load factor.
+   *
+   * @param initialCapacity the initial capacity (&gt;=0)
+   * @param loadFactor the load factor (&gt; 0, not NaN)
+   * @throws IllegalArgumentException if (initialCapacity &lt; 0) ||
+   *                                     ! (loadFactor &gt; 0.0)
+   */
+  public HashMap(int initialCapacity, float loadFactor)
+  {
+    if (initialCapacity < 0)
+      throw new IllegalArgumentException("Illegal Capacity: "
+                                         + initialCapacity);
+    if (! (loadFactor > 0)) // check for NaN too
+      throw new IllegalArgumentException("Illegal Load: " + loadFactor);
+
+    if (initialCapacity == 0)
+      initialCapacity = 1;
+    buckets = (HashEntry<K, V>[]) new HashEntry[initialCapacity];
+    this.loadFactor = loadFactor;
+    threshold = (int) (initialCapacity * loadFactor);
+  }
+
+  /**
+   * Returns the number of kay-value mappings currently in this Map.
+   *
+   * @return the size
+   */
+  public int size()
+  {
+    return size;
+  }
+
+  /**
+   * Returns true if there are no key-value mappings currently in this Map.
+   *
+   * @return <code>size() == 0</code>
+   */
+  public boolean isEmpty()
+  {
+    return size == 0;
+  }
+
+  /**
+   * Return the value in this HashMap associated with the supplied key,
+   * or <code>null</code> if the key maps to nothing.  NOTE: Since the value
+   * could also be null, you must use containsKey to see if this key
+   * actually maps to something.
+   *
+   * @param key the key for which to fetch an associated value
+   * @return what the key maps to, if present
+   * @see #put(Object, Object)
+   * @see #containsKey(Object)
+   */
+  public V get(Object key)
+  {
+    int idx = hash(key);
+    HashEntry<K, V> e = buckets[idx];
+    while (e != null)
+      {
+        if (equals(key, e.key))
+          return e.value;
+        e = e.next;
+      }
+    return null;
+  }
+
+  /**
+   * Returns true if the supplied object <code>equals()</code> a key
+   * in this HashMap.
+   *
+   * @param key the key to search for in this HashMap
+   * @return true if the key is in the table
+   * @see #containsValue(Object)
+   */
+  public boolean containsKey(Object key)
+  {
+    int idx = hash(key);
+    HashEntry<K, V> e = buckets[idx];
+    while (e != null)
+      {
+        if (equals(key, e.key))
+          return true;
+        e = e.next;
+      }
+    return false;
+  }
+
+  /**
+   * Puts the supplied value into the Map, mapped by the supplied key.
+   * The value may be retrieved by any object which <code>equals()</code>
+   * this key. NOTE: Since the prior value could also be null, you must
+   * first use containsKey if you want to see if you are replacing the
+   * key's mapping.
+   *
+   * @param key the key used to locate the value
+   * @param value the value to be stored in the HashMap
+   * @return the prior mapping of the key, or null if there was none
+   * @see #get(Object)
+   * @see Object#equals(Object)
+   */
+  public V put(K key, V value)
+  {
+    int idx = hash(key);
+    HashEntry<K, V> e = buckets[idx];
+
+    while (e != null)
+      {
+        if (equals(key, e.key))
+          {
+            e.access(); // Must call this for bookkeeping in LinkedHashMap.
+            V r = e.value;
+            e.value = value;
+            return r;
+          }
+        else
+          e = e.next;
+      }
+
+    // At this point, we know we need to add a new entry.
+    modCount++;
+    if (++size > threshold)
+      {
+        rehash();
+        // Need a new hash value to suit the bigger table.
+        idx = hash(key);
+      }
+
+    // LinkedHashMap cannot override put(), hence this call.
+    addEntry(key, value, idx, true);
+    return null;
+  }
+
+  /**
+   * Copies all elements of the given map into this hashtable.  If this table
+   * already has a mapping for a key, the new mapping replaces the current
+   * one.
+   *
+   * @param m the map to be hashed into this
+   */
+  public void putAll(Map<? extends K, ? extends V> m)
+  {
+    final Map<K,V> addMap = (Map<K,V>) m;
+    final Iterator<Map.Entry<K,V>> it = addMap.entrySet().iterator();
+    while (it.hasNext())
+      {
+        final Map.Entry<K,V> e = it.next();
+        // Optimize in case the Entry is one of our own.
+        if (e instanceof AbstractMap.SimpleEntry)
+          {
+            AbstractMap.SimpleEntry<? extends K, ? extends V> entry
+              = (AbstractMap.SimpleEntry<? extends K, ? extends V>) e;
+            put(entry.key, entry.value);
+          }
+        else
+          put(e.getKey(), e.getValue());
+      }
+  }
+
+  /**
+   * Removes from the HashMap and returns the value which is mapped by the
+   * supplied key. If the key maps to nothing, then the HashMap remains
+   * unchanged, and <code>null</code> is returned. NOTE: Since the value
+   * could also be null, you must use containsKey to see if you are
+   * actually removing a mapping.
+   *
+   * @param key the key used to locate the value to remove
+   * @return whatever the key mapped to, if present
+   */
+  public V remove(Object key)
+  {
+    int idx = hash(key);
+    HashEntry<K, V> e = buckets[idx];
+    HashEntry<K, V> last = null;
+
+    while (e != null)
+      {
+        if (equals(key, e.key))
+          {
+            modCount++;
+            if (last == null)
+              buckets[idx] = e.next;
+            else
+              last.next = e.next;
+            size--;
+            // Method call necessary for LinkedHashMap to work correctly.
+            return e.cleanup();
+          }
+        last = e;
+        e = e.next;
+      }
+    return null;
+  }
+
+  /**
+   * Clears the Map so it has no keys. This is O(1).
+   */
+  public void clear()
+  {
+    if (size != 0)
+      {
+        modCount++;
+        Arrays.fill(buckets, null);
+        size = 0;
+      }
+  }
+
+  /**
+   * Returns true if this HashMap contains a value <code>o</code>, such that
+   * <code>o.equals(value)</code>.
+   *
+   * @param value the value to search for in this HashMap
+   * @return true if at least one key maps to the value
+   * @see #containsKey(Object)
+   */
+  public boolean containsValue(Object value)
+  {
+    for (int i = buckets.length - 1; i >= 0; i--)
+      {
+        HashEntry<K, V> e = buckets[i];
+        while (e != null)
+          {
+            if (equals(value, e.value))
+              return true;
+            e = e.next;
+          }
+      }
+    return false;
+  }
+
+  /**
+   * Returns a shallow clone of this HashMap. The Map itself is cloned,
+   * but its contents are not.  This is O(n).
+   *
+   * @return the clone
+   */
+  public Object clone()
+  {
+    HashMap<K, V> copy = null;
+    try
+      {
+        copy = (HashMap<K, V>) super.clone();
+      }
+    catch (CloneNotSupportedException x)
+      {
+        // This is impossible.
+      }
+    copy.buckets = (HashEntry<K, V>[]) new HashEntry[buckets.length];
+    copy.putAllInternal(this);
+    // Clear the entry cache. AbstractMap.clone() does the others.
+    copy.entries = null;
+    return copy;
+  }
+
+  /**
+   * Returns a "set view" of this HashMap's keys. The set is backed by the
+   * HashMap, so changes in one show up in the other.  The set supports
+   * element removal, but not element addition.
+   *
+   * @return a set view of the keys
+   * @see #values()
+   * @see #entrySet()
+   */
+  public Set<K> keySet()
+  {
+    if (keys == null)
+      // Create an AbstractSet with custom implementations of those methods
+      // that can be overridden easily and efficiently.
+      keys = new AbstractSet<K>()
+      {
+        public int size()
+        {
+          return size;
+        }
+
+        public Iterator<K> iterator()
+        {
+          // Cannot create the iterator directly, because of LinkedHashMap.
+          return HashMap.this.iterator(KEYS);
+        }
+
+        public void clear()
+        {
+          HashMap.this.clear();
+        }
+
+        public boolean contains(Object o)
+        {
+          return containsKey(o);
+        }
+
+        public boolean remove(Object o)
+        {
+          // Test against the size of the HashMap to determine if anything
+          // really got removed. This is necessary because the return value
+          // of HashMap.remove() is ambiguous in the null case.
+          int oldsize = size;
+          HashMap.this.remove(o);
+          return oldsize != size;
+        }
+      };
+    return keys;
+  }
+
+  /**
+   * Returns a "collection view" (or "bag view") of this HashMap's values.
+   * The collection is backed by the HashMap, so changes in one show up
+   * in the other.  The collection supports element removal, but not element
+   * addition.
+   *
+   * @return a bag view of the values
+   * @see #keySet()
+   * @see #entrySet()
+   */
+  public Collection<V> values()
+  {
+    if (values == null)
+      // We don't bother overriding many of the optional methods, as doing so
+      // wouldn't provide any significant performance advantage.
+      values = new AbstractCollection<V>()
+      {
+        public int size()
+        {
+          return size;
+        }
+
+        public Iterator<V> iterator()
+        {
+          // Cannot create the iterator directly, because of LinkedHashMap.
+          return HashMap.this.iterator(VALUES);
+        }
+
+        public void clear()
+        {
+          HashMap.this.clear();
+        }
+      };
+    return values;
+  }
+
+  /**
+   * Returns a "set view" of this HashMap's entries. The set is backed by
+   * the HashMap, so changes in one show up in the other.  The set supports
+   * element removal, but not element addition.<p>
+   *
+   * Note that the iterators for all three views, from keySet(), entrySet(),
+   * and values(), traverse the HashMap in the same sequence.
+   *
+   * @return a set view of the entries
+   * @see #keySet()
+   * @see #values()
+   * @see Map.Entry
+   */
+  public Set<Map.Entry<K, V>> entrySet()
+  {
+    if (entries == null)
+      // Create an AbstractSet with custom implementations of those methods
+      // that can be overridden easily and efficiently.
+      entries = new AbstractSet<Map.Entry<K, V>>()
+      {
+        public int size()
+        {
+          return size;
+        }
+
+        public Iterator<Map.Entry<K, V>> iterator()
+        {
+          // Cannot create the iterator directly, because of LinkedHashMap.
+          return HashMap.this.iterator(ENTRIES);
+        }
+
+        public void clear()
+        {
+          HashMap.this.clear();
+        }
+
+        public boolean contains(Object o)
+        {
+          return getEntry(o) != null;
+        }
+
+        public boolean remove(Object o)
+        {
+          HashEntry<K, V> e = getEntry(o);
+          if (e != null)
+            {
+              HashMap.this.remove(e.key);
+              return true;
+            }
+          return false;
+        }
+      };
+    return entries;
+  }
+
+  /**
+   * Helper method for put, that creates and adds a new Entry.  This is
+   * overridden in LinkedHashMap for bookkeeping purposes.
+   *
+   * @param key the key of the new Entry
+   * @param value the value
+   * @param idx the index in buckets where the new Entry belongs
+   * @param callRemove whether to call the removeEldestEntry method
+   * @see #put(Object, Object)
+   */
+  void addEntry(K key, V value, int idx, boolean callRemove)
+  {
+    HashEntry<K, V> e = new HashEntry<K, V>(key, value);
+    e.next = buckets[idx];
+    buckets[idx] = e;
+  }
+
+  /**
+   * Helper method for entrySet(), which matches both key and value
+   * simultaneously.
+   *
+   * @param o the entry to match
+   * @return the matching entry, if found, or null
+   * @see #entrySet()
+   */
+  // Package visible, for use in nested classes.
+  final HashEntry<K, V> getEntry(Object o)
+  {
+    if (! (o instanceof Map.Entry))
+      return null;
+    Map.Entry<K, V> me = (Map.Entry<K, V>) o;
+    K key = me.getKey();
+    int idx = hash(key);
+    HashEntry<K, V> e = buckets[idx];
+    while (e != null)
+      {
+        if (equals(e.key, key))
+          return equals(e.value, me.getValue()) ? e : null;
+        e = e.next;
+      }
+    return null;
+  }
+
+  /**
+   * Helper method that returns an index in the buckets array for `key'
+   * based on its hashCode().  Package visible for use by subclasses.
+   *
+   * @param key the key
+   * @return the bucket number
+   */
+  final int hash(Object key)
+  {
+    return key == null ? 0 : Math.abs(key.hashCode() % buckets.length);
+  }
+
+  /**
+   * Generates a parameterized iterator.  Must be overrideable, since
+   * LinkedHashMap iterates in a different order.
+   *
+   * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
+   * @return the appropriate iterator
+   */
+  <T> Iterator<T> iterator(int type)
+  {
+    // FIXME: bogus cast here.
+    return new HashIterator<T>(type);
+  }
+
+  /**
+   * A simplified, more efficient internal implementation of putAll(). clone()
+   * should not call putAll or put, in order to be compatible with the JDK
+   * implementation with respect to subclasses.
+   *
+   * @param m the map to initialize this from
+   */
+  void putAllInternal(Map<? extends K, ? extends V> m)
+  {
+    final Map<K,V> addMap = (Map<K,V>) m;
+    final Iterator<Map.Entry<K,V>> it = addMap.entrySet().iterator();
+    size = 0;
+    while (it.hasNext())
+      {
+        final Map.Entry<K,V> e = it.next();
+        size++;
+        K key = e.getKey();
+        int idx = hash(key);
+        addEntry(key, e.getValue(), idx, false);
+      }
+  }
+
+  /**
+   * Increases the size of the HashMap and rehashes all keys to new
+   * array indices; this is called when the addition of a new value
+   * would cause size() &gt; threshold. Note that the existing Entry
+   * objects are reused in the new hash table.
+   *
+   * <p>This is not specified, but the new size is twice the current size
+   * plus one; this number is not always prime, unfortunately.
+   */
+  private void rehash()
+  {
+    HashEntry<K, V>[] oldBuckets = buckets;
+
+    int newcapacity = (buckets.length * 2) + 1;
+    threshold = (int) (newcapacity * loadFactor);
+    buckets = (HashEntry<K, V>[]) new HashEntry[newcapacity];
+
+    for (int i = oldBuckets.length - 1; i >= 0; i--)
+      {
+        HashEntry<K, V> e = oldBuckets[i];
+        while (e != null)
+          {
+            int idx = hash(e.key);
+            HashEntry<K, V> dest = buckets[idx];
+            HashEntry<K, V> next = e.next;
+            e.next = buckets[idx];
+            buckets[idx] = e;
+            e = next;
+          }
+      }
+  }
+
+  /**
+   * Serializes this object to the given stream.
+   *
+   * @param s the stream to write to
+   * @throws IOException if the underlying stream fails
+   * @serialData the <i>capacity</i>(int) that is the length of the
+   *             bucket array, the <i>size</i>(int) of the hash map
+   *             are emitted first.  They are followed by size entries,
+   *             each consisting of a key (Object) and a value (Object).
+   */
+  private void writeObject(ObjectOutputStream s) throws IOException
+  {
+    // Write the threshold and loadFactor fields.
+    s.defaultWriteObject();
+
+    s.writeInt(buckets.length);
+    s.writeInt(size);
+    // Avoid creating a wasted Set by creating the iterator directly.
+    Iterator<HashEntry<K, V>> it = iterator(ENTRIES);
+    while (it.hasNext())
+      {
+        HashEntry<K, V> entry = it.next();
+        s.writeObject(entry.key);
+        s.writeObject(entry.value);
+      }
+  }
+
+  /**
+   * Deserializes this object from the given stream.
+   *
+   * @param s the stream to read from
+   * @throws ClassNotFoundException if the underlying stream fails
+   * @throws IOException if the underlying stream fails
+   * @serialData the <i>capacity</i>(int) that is the length of the
+   *             bucket array, the <i>size</i>(int) of the hash map
+   *             are emitted first.  They are followed by size entries,
+   *             each consisting of a key (Object) and a value (Object).
+   */
+  private void readObject(ObjectInputStream s)
+    throws IOException, ClassNotFoundException
+  {
+    // Read the threshold and loadFactor fields.
+    s.defaultReadObject();
+
+    // Read and use capacity, followed by key/value pairs.
+    buckets = (HashEntry<K, V>[]) new HashEntry[s.readInt()];
+    int len = s.readInt();
+    size = len;
+    while (len-- > 0)
+      {
+        Object key = s.readObject();
+        addEntry((K) key, (V) s.readObject(), hash(key), false);
+      }
+  }
+
+  /**
+   * Iterate over HashMap's entries.
+   * This implementation is parameterized to give a sequential view of
+   * keys, values, or entries.
+   *
+   * @author Jon Zeppieri
+   */
+  private final class HashIterator<T> implements Iterator<T>
+  {
+    /**
+     * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
+     * or {@link #ENTRIES}.
+     */
+    private final int type;
+    /**
+     * The number of modifications to the backing HashMap that we know about.
+     */
+    private int knownMod = modCount;
+    /** The number of elements remaining to be returned by next(). */
+    private int count = size;
+    /** Current index in the physical hash table. */
+    private int idx = buckets.length;
+    /** The last Entry returned by a next() call. */
+    private HashEntry last;
+    /**
+     * The next entry that should be returned by next(). It is set to something
+     * if we're iterating through a bucket that contains multiple linked
+     * entries. It is null if next() needs to find a new bucket.
+     */
+    private HashEntry next;
+
+    /**
+     * Construct a new HashIterator with the supplied type.
+     * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
+     */
+    HashIterator(int type)
+    {
+      this.type = type;
+    }
+
+    /**
+     * Returns true if the Iterator has more elements.
+     * @return true if there are more elements
+     */
+    public boolean hasNext()
+    {
+      return count > 0;
+    }
+
+    /**
+     * Returns the next element in the Iterator's sequential view.
+     * @return the next element
+     * @throws ConcurrentModificationException if the HashMap was modified
+     * @throws NoSuchElementException if there is none
+     */
+    public T next()
+    {
+      if (knownMod != modCount)
+        throw new ConcurrentModificationException();
+      if (count == 0)
+        throw new NoSuchElementException();
+      count--;
+      HashEntry e = next;
+
+      while (e == null)
+        e = buckets[--idx];
+
+      next = e.next;
+      last = e;
+      if (type == VALUES)
+        return (T) e.value;
+      if (type == KEYS)
+        return (T) e.key;
+      return (T) e;
+    }
+
+    /**
+     * Removes from the backing HashMap the last element which was fetched
+     * with the <code>next()</code> method.
+     * @throws ConcurrentModificationException if the HashMap was modified
+     * @throws IllegalStateException if called when there is no last element
+     */
+    public void remove()
+    {
+      if (knownMod != modCount)
+        throw new ConcurrentModificationException();
+      if (last == null)
+        throw new IllegalStateException();
+
+      HashMap.this.remove(last.key);
+      last = null;
+      knownMod++;
+    }
+  }
+}