jni.cc: Include IdentityHashMap.h, not Hashtable.h.

	* jni.cc: Include IdentityHashMap.h, not Hashtable.h.
	(local_ref_table, global_ref_table): Now IdentityHashMap.
	(_Jv_JNI_Init): Updated for new types.
	(mark_for_gc): Likewise.
	(unmark_for_gc): Likewise.
	* gcj/javaprims.h: Rebuilt class list.
	* Makefile.in: Rebuilt.
	* Makefile.am (core_java_source_files): Added new file.
	* java/util/IdentityHashMap.java: New file.

From-SVN: r44929

7 files changed, 442 insertions, 11 deletions

diff --git a/libjava/ChangeLog b/libjava/ChangeLog
index 81acaa9..b78bcf3 100644
--- a/libjava/ChangeLog
+++ b/libjava/ChangeLog
@@ -1,5 +1,15 @@
 2001-08-15  Tom Tromey  <tromey@redhat.com>
 
+	* jni.cc: Include IdentityHashMap.h, not Hashtable.h.
+	(local_ref_table, global_ref_table): Now IdentityHashMap.
+	(_Jv_JNI_Init): Updated for new types.
+	(mark_for_gc): Likewise.
+	(unmark_for_gc): Likewise.
+	* gcj/javaprims.h: Rebuilt class list.
+	* Makefile.in: Rebuilt.
+	* Makefile.am (core_java_source_files): Added new file.
+	* java/util/IdentityHashMap.java: New file.
+
 	* gnu/gcj/convert/natIconv.cc (read): Handle EINVAL and E2BIG
 	correctly.
 
diff --git a/libjava/Makefile.am b/libjava/Makefile.am
index 628203d..382d4ef 100644
--- a/libjava/Makefile.am
+++ b/libjava/Makefile.am
@@ -947,6 +947,7 @@ java/util/GregorianCalendar.java \
 java/util/HashMap.java \
 java/util/HashSet.java \
 java/util/Hashtable.java \
+java/util/IdentityHashMap.java \
 java/util/Iterator.java	\
 java/util/LinkedList.java \
 java/util/List.java \
diff --git a/libjava/Makefile.in b/libjava/Makefile.in
index d90bb6e..26f0877 100644
--- a/libjava/Makefile.in
+++ b/libjava/Makefile.in
@@ -717,6 +717,7 @@ java/util/GregorianCalendar.java \
 java/util/HashMap.java \
 java/util/HashSet.java \
 java/util/Hashtable.java \
+java/util/IdentityHashMap.java \
 java/util/Iterator.java	\
 java/util/LinkedList.java \
 java/util/List.java \
@@ -1859,10 +1860,11 @@ DEP_FILES =  .deps/$(srcdir)/$(CONVERT_DIR)/gen-from-JIS.P \
 .deps/java/util/EventListener.P .deps/java/util/EventObject.P \
 .deps/java/util/GregorianCalendar.P .deps/java/util/HashMap.P \
 .deps/java/util/HashSet.P .deps/java/util/Hashtable.P \
-.deps/java/util/Iterator.P .deps/java/util/LinkedList.P \
-.deps/java/util/List.P .deps/java/util/ListIterator.P \
-.deps/java/util/ListResourceBundle.P .deps/java/util/Locale.P \
-.deps/java/util/Map.P .deps/java/util/MissingResourceException.P \
+.deps/java/util/IdentityHashMap.P .deps/java/util/Iterator.P \
+.deps/java/util/LinkedList.P .deps/java/util/List.P \
+.deps/java/util/ListIterator.P .deps/java/util/ListResourceBundle.P \
+.deps/java/util/Locale.P .deps/java/util/Map.P \
+.deps/java/util/MissingResourceException.P \
 .deps/java/util/NoSuchElementException.P .deps/java/util/Observable.P \
 .deps/java/util/Observer.P .deps/java/util/Properties.P \
 .deps/java/util/PropertyPermission.P \
diff --git a/libjava/gcj/javaprims.h b/libjava/gcj/javaprims.h
index 5608aed..2ecf230 100644
--- a/libjava/gcj/javaprims.h
+++ b/libjava/gcj/javaprims.h
@@ -280,6 +280,8 @@ extern "Java"
       class Hashtable$Entry;
       class Hashtable$Enumerator;
       class Hashtable$HashIterator;
+      class IdentityHashMap;
+      class IdentityHashMap$IdentityIterator;
       class Iterator;
       class LinkedList;
       class LinkedList$Entry;
diff --git a/libjava/java/util/IdentityHashMap.java b/libjava/java/util/IdentityHashMap.java
new file mode 100644
index 0000000..374f09e
--- /dev/null
+++ b/libjava/java/util/IdentityHashMap.java
@@ -0,0 +1,415 @@
+/* IdentityHashMap.java -- a class providing a hashtable data structure,
+   mapping Object --> Object, which uses object identity for hashing.
+   Copyright (C) 2001 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., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+package java.util;
+
+import java.io.*;
+
+/**
+ * This class provides a hashtable-backed implementation of the
+ * Map interface.  Unlike HashMap, it uses object identity to
+ * do its hashing.  Also, it uses a linear-probe hash table.
+ *
+ * @author Tom Tromey <tromey@redhat.com>
+ * @since 1.4
+ */
+public class IdentityHashMap extends AbstractMap
+  implements Map, Serializable, Cloneable
+{
+  private static final int DEFAULT_CAPACITY = 21;
+
+  /** Create a new IdentityHashMap with the default capacity (21
+   * entries).
+   */
+  public IdentityHashMap ()
+  {
+    this (DEFAULT_CAPACITY);
+  }
+
+  /** Create a new IdentityHashMap with the indicated number of
+   * entries.  If the number of elements added to this hash map
+   * exceeds this maximum, the map will grow itself; however, that
+   * incurs a performance penalty.
+   * @param max Initial size
+   */
+  public IdentityHashMap (int max)
+  {
+    if (max < 0)
+      throw new IllegalArgumentException ();
+    table = new Object[2 * max];
+    Arrays.fill (table, emptyslot);
+    size = 0;
+  }
+
+  /** Create a new IdentityHashMap whose contents are taken from the
+   * given Map.
+   * @param m The map whose elements are to be put in this map.
+   */
+  public IdentityHashMap (Map m)
+  {
+    int len = 2 * Math.max (m.size (), DEFAULT_CAPACITY);
+    table = new Object[len];
+    Arrays.fill (table, emptyslot);
+    putAll (m);
+  }
+
+  public void clear ()
+  {
+    Arrays.fill (table, emptyslot);
+    size = 0;
+  }
+
+  public Object clone ()
+  {
+    IdentityHashMap copy = (IdentityHashMap) super.clone ();
+    copy.table = (Object[]) table.clone ();
+    return copy;
+  }
+
+  public boolean containsKey (Object key)
+  {
+    int h = Math.abs (2 * System.identityHashCode (key) % table.length);
+    int save = h;
+    while (true)
+      {
+	if (table[h] == key)
+	  return true;
+	if (table[h] == emptyslot)
+	  return false;
+	h += 2;
+	if (h > table.length)
+	  h = 0;
+	if (h == save)
+	  return false;
+      }
+  }
+
+  public boolean containsValue (Object value)
+  {
+    for (int i = 1; i < table.length; i += 2)
+      if (table[i] == value)
+	return true;
+    return false;
+  }
+
+  public Set entrySet ()
+  {
+    return new AbstractSet ()
+    {
+      public int size ()
+      {
+	return size;
+      }
+
+      public Iterator iterator ()
+      {
+	return new IdentityIterator (IdentityIterator.ENTRIES);
+      }
+
+      public void clear ()
+      {
+	IdentityHashMap.this.clear ();
+      }
+
+      public boolean contains (Object o)
+      {
+	if (! (o instanceof Map.Entry))
+	  return false;
+	Map.Entry m = (Map.Entry) o;
+	return (IdentityHashMap.this.containsKey (m.getKey ())
+		&& IdentityHashMap.this.get (m.getKey ()) == m.getValue ());
+      }
+
+      public boolean remove (Object o)
+      {
+	if (! (o instanceof Map.Entry))
+	  return false;
+	Map.Entry m = (Map.Entry) o;
+	if (IdentityHashMap.this.containsKey (m.getKey ())
+	    && IdentityHashMap.this.get (m.getKey ()) == m.getValue ())
+	  {
+	    int oldsize = size;
+	    IdentityHashMap.this.remove (m.getKey ());
+	    return oldsize != size;
+	  }
+	return false;
+      }
+    };
+  }
+
+  public Object get (Object key)
+  {
+    int h = Math.abs (2 * System.identityHashCode (key) % table.length);
+    int save = h;
+    while (true)
+      {
+	if (table[h] == key)
+	  return table[h + 1];
+	if (table[h] == emptyslot)
+	  return null;
+	h += 2;
+	if (h > table.length)
+	  h = 0;
+	if (h == save)
+	  return null;
+      }
+  }
+
+  public boolean isEmpty ()
+  {
+    return size == 0;
+  }
+
+  public Set keySet ()
+  {
+    return new AbstractSet ()
+    {
+      public int size ()
+      {
+	return size;
+      }
+
+      public Iterator iterator ()
+      {
+	return new IdentityIterator (IdentityIterator.KEYS);
+      }
+
+      public void clear ()
+      {
+	IdentityHashMap.this.clear ();
+      }
+
+      public boolean contains (Object o)
+      {
+	return IdentityHashMap.this.containsKey (o);
+      }
+
+      public boolean remove (Object o)
+      {
+	int oldsize = size;
+	IdentityHashMap.this.remove (o);
+	return oldsize != size;
+      }
+    };
+  }
+
+  public Object put (Object key, Object value)
+  {
+    // Rehash is the load factor is too high.
+    if (size * 3 / 2 > 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)
+	  {
+	    if (old[i] != tombstone && old[i] != emptyslot)
+	      {
+		// Just use put.  This isn't very efficient, but it is
+		// ok.
+		put (old[i], old[i + 1]);
+	      }
+	  }
+      }
+
+    int h = Math.abs (2 * System.identityHashCode (key) % table.length);
+    int save = h;
+    int del = -1;
+    while (true)
+      {
+	if (table[h] == key)
+	  {
+	    Object r = table[h + 1];
+	    table[h + 1] = value;
+	    return r;
+	  }
+	else if (table[h] == tombstone && del == -1)
+	  del = h;
+	else if (table[h] == emptyslot)
+	  {
+	    if (del == -1)
+	      del = h;
+	    break;
+	  }
+	h += 2;
+	if (h > table.length)
+	  h = 0;
+	if (h == save)
+	  break;
+      }
+
+    if (del != -1)
+      {
+	table[del] = key;
+	table[del + 1] = value;
+	++size;
+	return null;
+      }
+
+    // This is an error.
+    return null;
+  }
+
+  public Object remove (Object key)
+  {
+    int h = Math.abs (2 * System.identityHashCode (key) % table.length);
+    int save = h;
+    while (true)
+      {
+	if (table[h] == key)
+	  {
+	    Object r = table[h + 1];
+	    table[h] = tombstone;
+	    table[h + 1] = tombstone;
+	    --size;
+	    return r;
+	  }
+	h += 2;
+	if (h > table.length)
+	  h = 0;
+	if (h == save)
+	  break;
+      }
+
+    return null;
+  }
+
+  public int size ()
+  {
+    return size;
+  }
+
+  public Collection values ()
+  {
+    return new AbstractCollection ()
+    {
+      public int size ()
+      {
+	return size;
+      }
+
+      public Iterator iterator ()
+      {
+	return new IdentityIterator (IdentityIterator.VALUES);
+      }
+
+      public void clear ()
+      {
+	IdentityHashMap.this.clear ();
+      }
+    };
+  }
+
+  private class IdentityIterator implements Iterator
+  {
+    static final int KEYS = 0;
+    static final int VALUES = 1;
+    static final int ENTRIES = 2;
+
+    // Type of iterator.
+    int type;
+    // Location in the table.
+    int loc;
+    // How many items we've seen.
+    int seen;
+
+    IdentityIterator (int type)
+    {
+      this.type = type;
+      loc = 0;
+      seen = 0;
+    }
+
+    public boolean hasNext ()
+    {
+      return seen < size;
+    }
+
+    public Object next ()
+    {
+      while (true)
+	{
+	  loc += 2;
+	  if (loc >= table.length)
+	    throw new NoSuchElementException ();
+	  if (table[loc] != tombstone && table[loc] != emptyslot)
+	    {
+	      ++seen;
+	      return table[loc];
+	    }
+	}
+    }
+
+    public void remove ()
+    {
+      if (loc >= table.length
+	  || table[loc] == tombstone
+	  || table[loc] == emptyslot)
+	throw new IllegalStateException ();
+      table[loc] = tombstone;
+      table[loc + 1] = tombstone;
+      --size;
+    }
+  }
+
+  private void readObject (ObjectInputStream s)
+    throws IOException, ClassNotFoundException
+  {
+    int num = s.readInt ();
+    for (int i = 0; i < num; ++i)
+      {
+	Object key = s.readObject ();
+	Object value = s.readObject ();
+	put (key, value);
+      }
+  }
+
+  private void writeObject (ObjectOutputStream s)
+    throws IOException
+  {
+    s.writeInt (size);
+    Iterator it = entrySet ().iterator ();
+    while (it.hasNext ())
+      {
+	Map.Entry entry = (Map.Entry) it.next ();
+	s.writeObject (entry.getKey ());
+	s.writeObject (entry.getValue ());
+      }
+  }
+
+  // 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 ();
+  // This object is used to mark empty slots.  We need this because
+  // using null is ambiguous.
+  private Object emptyslot = new Object ();
+}
diff --git a/libjava/jni.cc b/libjava/jni.cc
index c8ccee7..7b82908 100644
--- a/libjava/jni.cc
+++ b/libjava/jni.cc
@@ -37,7 +37,7 @@ details.  */
 #include <java/lang/reflect/Method.h>
 #include <java/lang/reflect/Modifier.h>
 #include <java/lang/OutOfMemoryError.h>
-#include <java/util/Hashtable.h>
+#include <java/util/IdentityHashMap.h>
 #include <java/lang/Integer.h>
 #include <java/lang/ThreadGroup.h>
 #include <java/lang/Thread.h>
@@ -91,9 +91,9 @@ struct _Jv_JNI_LocalFrame
 };
 
 // This holds a reference count for all local references.
-static java::util::Hashtable *local_ref_table;
+static java::util::IdentityHashMap *local_ref_table;
 // This holds a reference count for all global references.
-static java::util::Hashtable *global_ref_table;
+static java::util::IdentityHashMap *global_ref_table;
 
 // The only VM.
 static JavaVM *the_vm;
@@ -148,8 +148,8 @@ jvmpiDisableEvent (jint event_type, void *)
 void
 _Jv_JNI_Init (void)
 {
-  local_ref_table = new java::util::Hashtable;
-  global_ref_table = new java::util::Hashtable;
+  local_ref_table = new java::util::IdentityHashMap;
+  global_ref_table = new java::util::IdentityHashMap;
 
 #ifdef ENABLE_JVMPI
   _Jv_JVMPI_Interface.version = 1;
@@ -163,7 +163,7 @@ _Jv_JNI_Init (void)
 
 // Tell the GC that a certain pointer is live.
 static void
-mark_for_gc (jobject obj, java::util::Hashtable *ref_table)
+mark_for_gc (jobject obj, java::util::IdentityHashMap *ref_table)
 {
   JvSynchronize sync (ref_table);
 
@@ -176,7 +176,7 @@ mark_for_gc (jobject obj, java::util::Hashtable *ref_table)
 
 // Unmark a pointer.
 static void
-unmark_for_gc (jobject obj, java::util::Hashtable *ref_table)
+unmark_for_gc (jobject obj, java::util::IdentityHashMap *ref_table)
 {
   JvSynchronize sync (ref_table);
 
diff --git a/libjava/testsuite/Makefile.in b/libjava/testsuite/Makefile.in
index 6905ab3..6fada16 100644
--- a/libjava/testsuite/Makefile.in
+++ b/libjava/testsuite/Makefile.in
@@ -95,6 +95,7 @@ LIBGCJTESTSPEC = @LIBGCJTESTSPEC@
 LIBGCJ_CFLAGS = @LIBGCJ_CFLAGS@
 LIBGCJ_CXXFLAGS = @LIBGCJ_CXXFLAGS@
 LIBGCJ_JAVAFLAGS = @LIBGCJ_JAVAFLAGS@
+LIBICONV = @LIBICONV@
 LIBLTDL = @LIBLTDL@
 LIBTOOL = @LIBTOOL@
 LN_S = @LN_S@