Patch: FYI: Fix PR 21703

[Tom Tromey <tromey at redhat dot com>]

I'm checking this in on the 4.0 branch.  I will check it in on the
trunk once it emerges from its slushy state.

We can get into an infinite loop in String.intern(), in the case where
the intern hash table has valid entries and DELETED_STRING entries,
but no NULL entries.  The fix is to notice when we've looped back to
the beginning.  Due to the rehash behavior, in this case we know there
will be a DELETED_STRING entry.

This same bug occurs in the hash table used in natReference.cc.  (We
really should have a template in a header file for this...)

The only other place where I could remember that we used this same
approach was IdentityHashMap; I looked there and it does not have this
bug.

Tom

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

	PR libgcj/21703:
	* java/lang/ref/natReference.cc (find_slot): Handle case where
	table has no NULL entries.
	* java/lang/natString.cc (_Jv_StringFindSlot): Handle case where
	table has no NULL entries.

Index: java/lang/natString.cc
===================================================================
RCS file: /cvs/gcc/gcc/libjava/java/lang/natString.cc,v
retrieving revision 1.37
diff -u -r1.37 natString.cc
--- java/lang/natString.cc 22 Apr 2005 19:02:41 -0000 1.37
+++ java/lang/natString.cc 22 May 2005 00:45:47 -0000
@@ -1,6 +1,6 @@
 // natString.cc - Implementation of java.lang.String native methods.
 
-/* Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004  Free Software Foundation
+/* Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005  Free Software Foundation
 
    This file is part of libgcj.
 
@@ -64,7 +64,7 @@
   int index = start_index;
   /* step must be non-zero, and relatively prime with strhash_size. */
   jint step = (hash ^ (hash >> 16)) | 1;
-  for (;;)
+  do
     {
       jstring* ptr = &strhash[index];
       jstring value = (jstring) UNMASK_PTR (*ptr);
@@ -81,8 +81,12 @@
 	       && memcmp(JvGetStringChars(value), data, 2*len) == 0)
 	return (ptr);
       index = (index + step) & (strhash_size - 1);
-      JvAssert (index != start_index);
     }
+  while (index != start_index);
+  // Note that we can have INDEX == START_INDEX if the table has no
+  // NULL entries but does have DELETED_STRING entries.
+  JvAssert (deleted_index >= 0);
+  return &strhash[deleted_index];
 }
 
 /* Calculate a hash code for the string starting at PTR at given LENGTH.
Index: java/lang/ref/natReference.cc
===================================================================
RCS file: /cvs/gcc/gcc/libjava/java/lang/ref/natReference.cc,v
retrieving revision 1.6
diff -u -r1.6 natReference.cc
--- java/lang/ref/natReference.cc 29 Sep 2003 21:13:55 -0000 1.6
+++ java/lang/ref/natReference.cc 22 May 2005 00:45:47 -0000
@@ -1,6 +1,6 @@
 // natReference.cc - Native code for References
 
-/* Copyright (C) 2001, 2002, 2003  Free Software Foundation
+/* Copyright (C) 2001, 2002, 2003, 2005  Free Software Foundation
 
    This file is part of libgcj.
 
@@ -78,7 +78,7 @@
   int start_index = hcode & (hash_size - 1);
   int index = start_index;
   int deleted_index = -1;
-  for (;;)
+  do
     {
       object_list *ptr = &hash[index];
       if (ptr->reference == key)
@@ -96,8 +96,12 @@
 	  JvAssert (ptr->reference == DELETED_REFERENCE);
 	}
       index = (index + step) & (hash_size - 1);
-      JvAssert (index != start_index);
     }
+  while (index != start_index);
+  // Note that we can have INDEX == START_INDEX if the table has no
+  // NULL entries but does have DELETED entries.
+  JvAssert (deleted_index >= 0);
+  return &hash[deleted_index];
 }
 
 static void