The problem of Hashtable/Enumerator implementation of Classpath

[Wu, Gansha]

        We have modified GNU Classpath so that ORP with Classpath can run 
SpecJVM98/Javac. Here is the patch we want to submit for evaluation.
        The problem is when we run ORP with Classpath, NoSuchElementException 
is throwed, but JDK won't. We guess the problem resides in Hashtable/Enumerator.
        In principle, NoSuchElementException shouldn't be throwed if 
hasMoreElements() is called before nextElement(). But After inserting trace 
facilities into Enumerator, hasMoreElements() is really called before calling 
nextElement() each time.
        We finally identified the problem resides in the Enumerator of 
Hashtable. If we put new (key,value) pairs into hashtable when navigating in 
enumeration of it, NoSuchElementException will be throwed unexpectedly.
        According to "Java Class Libraries, Second Edition, Volume 1": "Whether 
modifications to this hash table during enumeration affect the results of the 
enumeration depends on where the modifications occur.  For example, if a new 
key/element pair is added to the front of the hash table and the enumeration is 
nearing the end of the table, the newly added element will not be returned by 
this enumeration." Maybe it's OK to throw NoSuchElementException if you happen 
to remove the element that the enumeration points to, but It sounds 
unreasonable to throw NoSuchElementException if a new key/value is added to the 
hash table.
        Java 2 deals with this type of problem in the Java 2 collection classes 
by throwing a ConcurrentModificationException if a collection is modified in 
between 2 calls to an iterator on that collection.  This is nice because the 
behavior is well defined.  It looks like from the libraries book that in the 
non-Java 2 collections, the behavior is undefined. 
        We wrote test cases to observe the behavior under GNU Classpath and JDK 
library(abbr. as JDK), and found JDK behaves more elegantly than Classpath.
        The difference of JDK with Classpath is:
        1. Classpath will throw NoSuchElementException but JDK won't. As we 
have said, it's unreasonable.
        2. JDK will find the changing status much earlier and end enumeration 
soon after new pairs put in. But Classpath will continue enumerating until 
throwing exception. It's not efficient in Javac benchmarks. We found Javac will 
re-enumerate to check whether last enumeration exits abnormally, so Classpath 
will spend more costs in enumerate-exception-reenumerate cycles. The latest 
snapshot of Classpath redesigned Hashtable implementation and behaves somewhat 
similar to JDK.
        After explored Classpath's implementation, this exception will be 
throwed when hasMoreElements() returns true, but nextElement() finds no element 
left. The problem is hasMoreElements() is under the impact of new elements put 
in, considering its implementation:
        return count < Hashtable.this.size; //When new elements put in, 
Hashtable.this.size increments, but count keeps untouched
        So its assumption is nextElements() will also find these new elements. 
But nextElement() navigates forward under the estimation of current idx, while 
new elements might be put in the buckets this enumeration has visited(those 
with buckets index greater than idx). Then when idx of nextElements() has 
reached 0, but hasMoreElements() indicts there're still elements hasn't been 
enumerated. Exception happens.
        A sematically correct implementation must have hasMoreElements() do the 
same thing as nextElement to check whether iteration will continue. We can also 
do some housekeeping work to prevent the redundant enumeration cost.
        The following is our implementation of Enumerator for your evaluation. 
The context compare result below is based on gnu classpath cvs snapshot of June 
22.Note that revision number is different from public CVS.

===================================================================
RCS file: /cvsroot/classpath/java/util/Hashtable.java,v
retrieving revision 1.1.1.1
diff -c -r1.1.1.1 Hashtable.java
*** java/util/Hashtable.java    2001/06/25 01:13:33     1.1.1.1
--- java/util/Hashtable.java    2001/06/28 02:49:20
***************
*** 827,876 ****
     *
     * @author       Jon Zeppieri
     */
!   class Enumerator implements Enumeration
!   {
!     static final int KEYS = 0;
!     static final int VALUES = 1;
!
!     int type;
!     // The total number of elements returned by nextElement(). Used to
!     // determine if there are more elements remaining.
!     int count;
!     // current index in the physical hash table.
!     int idx;
!     // the last Entry returned.
!     Entry last;
!
!     Enumerator(int type)
!     {
!       this.type = type;
!       this.count = 0;
!       this.idx = buckets.length;
!     }
!
!     public boolean hasMoreElements()
!     {
!       return count < Hashtable.this.size;
!     }
!
!     public Object nextElement()
!     {
!       if (count >= size)
!         throw new NoSuchElementException();
!       count++;
!       Entry e = null;
!       if (last != null)
!         e = last.next;
!
!       while (e == null)
!         {
!         e = buckets[--idx];
!       }
!
!       last = e;
!       if (type == VALUES)
!         return e.value;
!       return e.key;
!     }
!   }
! }
--- 827,904 ----
     *
     * @author       Jon Zeppieri
     */
!    class Enumerator implements Enumeration
!    {
!       static final int KEYS = 0;
!       static final int VALUES = 1;
!
!       int type;
!       int idx;
!       // the last Entry returned.
!       Entry last;
!       // the cursor of hasMoreElements()

!       int vidx;
!       // If hasMoreElements() has been called before nextElement(), 
nextElement()
!       //    needn't re-navigate the bucket/list, just use visited of 
hasMoreElements()
!       Entry visited;
!
!       Enumerator(int type)
!       {
!          this.type = type;
!          this.count = 0;
!          this.idx = buckets.length;
!       }
!
!       public boolean hasMoreElements()
!       {
!          Entry e = null;
!          if (last != null){
!            e = last.next;
!          }
!
!          vidx = idx;
!        while (e == null && vidx > 0)
!        {
!            e = buckets[--vidx];
!        }
!
!          visited = e;
!
!          return e != null;
!      }
!
!      public Object nextElement()
!      {
!          if(visited != null)
!          {
!            // hasMoreElements() has navigated to next element
!            last = visited;
!            idx = vidx;
!            visited = null;
!          }
!          else
!          {
!            Entry e = null;
!            if (last != null){
!               e = last.next;
!            }
!
!            while (e == null  && idx > 0)
!            {
!               e = buckets[--idx];
!            }
!
!            if(e == null){
!               throw new NoSuchElementException();
!            }
!
!            last = e;
!          }
!
!          if (type == VALUES)
!             return last.value;
!
!          return last.key;
!     }
!   }
! }