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;
! }
! }
! }
_______________________________________________
Classpath mailing list
[EMAIL PROTECTED]
http://mail.gnu.org/mailman/listinfo/classpath
