Patch: FYI: IdentityHashMap

[Tom Tromey <tromey at redhat dot com>]

I'm checking this in.  This fixes a bunch of bugs in IdentityHashMap.
I wrote a new IdentityHashMap Mauve test and checked it in; this patch
passes that test.

Tom

Index: ChangeLog
from  Tom Tromey  <tromey@redhat.com>

	* java/util/IdentityHashMap.java (containsKey): Use getHash.
	(get): Likewise.
	(put): Likewise.
	(remove): Likewise.
	(getHash): New method.
	(tombstone, emptyslot): Now static final.
	(put): Correctly determine when to rehash, and correctly rehash.
	(containsKey, remove): Test against table length with `>='.

Index: java/util/IdentityHashMap.java
===================================================================
RCS file: /cvs/gcc/gcc/libjava/java/util/IdentityHashMap.java,v
retrieving revision 1.3
diff -u -r1.3 IdentityHashMap.java
--- java/util/IdentityHashMap.java 2001/09/05 00:14:15 1.3
+++ java/util/IdentityHashMap.java 2001/09/27 16:47:01
@@ -103,7 +103,7 @@
 
   public boolean containsKey (Object key)
   {
-    int h = Math.abs (2 * System.identityHashCode (key) % table.length);
+    int h = getHash (key);
     int save = h;
     while (true)
       {
@@ -112,7 +112,7 @@
 	if (table[h] == emptyslot)
 	  return false;
 	h += 2;
-	if (h > table.length)
+	if (h >= table.length)
 	  h = 0;
 	if (h == save)
 	  return false;
@@ -174,7 +174,7 @@
 
   public Object get (Object key)
   {
-    int h = Math.abs (2 * System.identityHashCode (key) % table.length);
+    int h = getHash (key);
     int save = h;
     while (true)
       {
@@ -230,14 +230,15 @@
 
   public Object put (Object key, Object value)
   {
-    // Rehash is the load factor is too high.
-    if (size * 3 / 2 > table.length)
+    // Rehash if the load factor is too high.  We use a factor of 1.5
+    // -- the division by 2 is implicit on both sides.
+    if (size * 3 > table.length)
       {
 	Object[] old = table;
 	table = new Object[old.length * 2];
 	Arrays.fill (table, emptyslot);
 	size = 0;
-	for (int i = 0; i < old.length; ++i)
+	for (int i = 0; i < old.length; i += 2)
 	  {
 	    if (old[i] != tombstone && old[i] != emptyslot)
 	      {
@@ -248,7 +249,7 @@
 	  }
       }
 
-    int h = Math.abs (2 * System.identityHashCode (key) % table.length);
+    int h = getHash (key);
     int save = h;
     int del = -1;
     while (true)
@@ -288,7 +289,7 @@
 
   public Object remove (Object key)
   {
-    int h = Math.abs (2 * System.identityHashCode (key) % table.length);
+    int h = getHash (key);
     int save = h;
     while (true)
       {
@@ -301,7 +302,7 @@
 	    return r;
 	  }
 	h += 2;
-	if (h > table.length)
+	if (h >= table.length)
 	  h = 0;
 	if (h == save)
 	  break;
@@ -413,14 +414,20 @@
       }
   }
 
+  // Compute the hash value we will use for an object.
+  private int getHash (Object o)
+  {
+    return 2 * Math.abs (System.identityHashCode (o) % (table.length / 2));
+  }
+
   // Number of items in hash table.
   private int size;
   // The table itself.
   private Object[] table;
 
   // This object is used to mark deleted items.
-  private Object tombstone = new Object ();
+  private static final Object tombstone = new Object ();
   // This object is used to mark empty slots.  We need this because
   // using null is ambiguous.
-  private Object emptyslot = new Object ();
+  private static final Object emptyslot = new Object ();
 }