2001-09-15 Eric Blake <ebb9@email.byu.edu>

	* java/util/Hashtable.java (contains): check for null
	(Hashtable(Map)): more efficient
	(clear): more efficient
	(clone): more efficient, by adding Entry.copy
	* java/util/HashMap.java (clear): more efficient
	(HashMap(Map)): more efficient
	(clone): more efficient, by adding Entry.copy

4 files changed, 48 insertions, 53 deletions

diff --git a/AUTHORS b/AUTHORS
index 701a41eb9..68eb36436 100644
--- a/AUTHORS
+++ b/AUTHORS
@@ -13,3 +13,4 @@ Mark Wielaard (mark@klomp.org)
 Tom Tromey (tromey@cygnus.com)
 Anthony Green (green@redhat.com)
 Warren Levy (warrenl@cygnus.com)
+Eric Blake (ebb9@email.byu.edu)
diff --git a/ChangeLog b/ChangeLog
index dbdb774ec..1f1c45d7c 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2001-09-15  Eric Blake  <ebb9@email.byu.edu>
+
+	* java/util/Hashtable.java (contains): check for null
+	(Hashtable(Map)): more efficient
+	(clear): more efficient
+	(clone): more efficient, by adding Entry.copy
+	* java/util/HashMap.java (clear): more efficient
+	(HashMap(Map)): more efficient
+	(clone): more efficient, by adding Entry.copy
+
 2001-09-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>
 
 	* java/io/File.java (File(String, String)): Correct error in
diff --git a/java/util/HashMap.java b/java/util/HashMap.java
index 4bc88b755..309c08bee 100644
--- a/java/util/HashMap.java
+++ b/java/util/HashMap.java
@@ -1,6 +1,6 @@
 /* HashMap.java -- a class providing a basic hashtable data structure,
    mapping Object --> Object
-   Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
+   Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
 
 This file is part of GNU Classpath.
 
@@ -44,11 +44,11 @@ import java.io.ObjectOutputStream;
  * 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 casue primary clustering) and 
+ * 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.  
  *
- * Under ideal circumstances (no collisions, HashMap offers O(1) 
+ * Under ideal circumstances (no collisions), HashMap offers O(1) 
  * performance on most operations (<pre>containsValue()</pre> is,
  * of course, O(n)).  In the worst case (all keys map to the same 
  * hash code -- very unlikely), most operations are O(n).
@@ -60,6 +60,7 @@ import java.io.ObjectOutputStream;
  * @author         Jon Zeppieri
  * @author         Jochen Hoenicke
  * @author	   Bryce McKinlay
+ * @author         Eric Blake <ebb9@email.byu.edu>
  */
 public class HashMap extends AbstractMap
   implements Map, Cloneable, Serializable
@@ -67,7 +68,7 @@ public class HashMap extends AbstractMap
   /** Default number of buckets. This is the value the JDK 1.3 uses. Some 
     * early documentation specified this value as 101. That is incorrect. */
   private static final int DEFAULT_CAPACITY = 11;  
-  /** The defaulty load factor; this is explicitly specified by the spec. */
+  /** The default load factor; this is explicitly specified by the spec. */
   private static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
   private static final long serialVersionUID = 362498820763181265L;
@@ -110,6 +111,14 @@ public class HashMap extends AbstractMap
     {
       super(key, value);
     }
+
+    Entry copy()
+    {
+      Entry e = new Entry(key, value);
+      if (next != null)
+        e.next = next.copy();
+      return e;
+    }
   }
 
   /**
@@ -132,9 +141,7 @@ public class HashMap extends AbstractMap
    */
   public HashMap(Map m)
   {
-    int size = Math.max(m.size() * 2, DEFAULT_CAPACITY);
-    buckets = new Entry[size];
-    threshold = (int) (size * loadFactor);
+    this(Math.max(m.size() * 2, DEFAULT_CAPACITY));
     putAll(m);
   }
 
@@ -343,10 +350,7 @@ public class HashMap extends AbstractMap
   public void clear()
   {
     modCount++;
-    for (int i=0; i < buckets.length; i++)
-      {
-        buckets[i] = null;
-      }
+    buckets = new Entry[buckets.length];
     size = 0;
   }
 
@@ -369,22 +373,8 @@ public class HashMap extends AbstractMap
     for (int i=0; i < buckets.length; i++)
       {
         Entry e = buckets[i];
-	Entry last = null;
-	
-	while (e != null)
-	  {
-	    if (last == null)
-	      {
-		copy.buckets[i] = new Entry(e.key, e.value);
-		last = copy.buckets[i];
-              }
-	    else		
-              {
-	        last.next = new Entry(e.key, e.value);
-		last = last.next;
-	      }
-	    e = e.next;
-	  }
+        if (e != null)
+          copy.buckets[i] = e.copy();
       }
     return copy;
   }
@@ -644,7 +634,7 @@ public class HashMap extends AbstractMap
     // entries. It is null if next() needs to find a new bucket.
     Entry next;
 
-    /* construct a new HashtableIterator with the supllied type: 
+    /* construct a new HashtableIterator with the supplied type: 
        KEYS, VALUES, or ENTRIES */
     HashIterator(int type)
     {
diff --git a/java/util/Hashtable.java b/java/util/Hashtable.java
index 48939b25f..25bd7a789 100644
--- a/java/util/Hashtable.java
+++ b/java/util/Hashtable.java
@@ -1,6 +1,6 @@
 /* Hashtable.java -- a class providing a basic hashtable data structure,
    mapping Object --> Object
-   Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
+   Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
 
 This file is part of GNU Classpath.
 
@@ -64,6 +64,7 @@ import java.io.ObjectOutputStream;
  * @author      Jon Zeppieri
  * @author	Warren Levy
  * @author      Bryce McKinlay
+ * @author      Eric Blake <ebb9@email.byu.edu>
  */
 public class Hashtable extends Dictionary 
   implements Map, Cloneable, Serializable
@@ -71,7 +72,7 @@ public class Hashtable extends Dictionary
   /** Default number of buckets. This is the value the JDK 1.3 uses. Some 
     * early documentation specified this value as 101. That is incorrect. */
   private static final int DEFAULT_CAPACITY = 11;  
-  /** The defaulty load factor; this is explicitly specified by the spec. */
+  /** The default load factor; this is explicitly specified by the spec. */
   private static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
   private static final long serialVersionUID = 1421746759512286392L;
@@ -122,6 +123,14 @@ public class Hashtable extends Dictionary
         throw new NullPointerException();
       return super.setValue(newVal);
     }
+
+    Entry copy()
+    {
+      Entry e = new Entry(key, value);
+      if (next != null)
+        e.next = next.copy();
+      return e;
+    }
   }
 
   /**
@@ -144,9 +153,7 @@ public class Hashtable extends Dictionary
    */
   public Hashtable(Map m)
   {
-    int size = Math.max(m.size() * 2, DEFAULT_CAPACITY);
-    buckets = new Entry[size];
-    threshold = (int) (size * loadFactor);
+    this(Math.max(m.size() * 2, DEFAULT_CAPACITY));
     putAll(m);
   }
 
@@ -223,6 +230,10 @@ public class Hashtable extends Dictionary
    */
   public synchronized boolean contains(Object value)
   {
+    // if Hashtable is empty, this method doesn't dereference 
+    // `value' anywhere, so check for it explicitly.
+    if (value == null)
+      throw new NullPointerException();
     for (int i = 0; i < buckets.length; i++)
       {
 	Entry e = buckets[i];
@@ -389,10 +400,7 @@ public class Hashtable extends Dictionary
   public synchronized void clear()
   {
     modCount++;
-    for (int i=0; i < buckets.length; i++)
-      {
-        buckets[i] = null;
-      }
+    buckets = new Entry[buckets.length];
     size = 0;
   }
 
@@ -415,22 +423,8 @@ public class Hashtable extends Dictionary
     for (int i=0; i < buckets.length; i++)
       {
         Entry e = buckets[i];
-	Entry last = null;
-	
-	while (e != null)
-	  {
-	    if (last == null)
-	      {
-		copy.buckets[i] = new Entry(e.key, e.value);
-		last = copy.buckets[i];
-              }
-	    else		
-              {
-	        last.next = new Entry(e.key, e.value);
-		last = last.next;
-	      }
-	    e = e.next;
-	  }
+        if (e != null)
+          copy.buckets[i] = e.copy();
       }
     return copy;
   }