Hi there,
I would like to propose the following patch that was written by my
collegue Fridjof. Basically, it replaces the parameterized Iterator and
Enumerator classes with normal classes for values/entries/keys. The
EntryIterator and EntryEnumerator are just like the previous
HashIterator and Enumerator, the other two versions are small classes
derived from these two, that only return the key vs. values.
Not only is that a cleaner OO design (IMO), it improves analyzability by
data flow analysis tools, which can not (always) handle parameterized
classes very well.
Note that this also includes a small improvement in the rehash() method.
See the ChangeLog and the code for details.
So, should I check this in?
2006-01-10 Roman Kennke <[EMAIL PROTECTED]>
Reported by: Fridjof Siebert <[EMAIL PROTECTED]>
* java/util/Hashtable.java
(KEYS): Removed unneeded field.
(VALUES): Removed unneeded field.
(ENTRIES): Removed unneeded field.
(keys): Return a KeyEnumerator instance.
(elements): Returns a ValueEnumerator instance.
(toString): Use an EntryIterator instance.
(keySet): Return a KeyIterator instance.
(values): Return a ValueIterator instance.
(entrySet): Return an EntryIterator instance.
(hashCode): Use EntryIterator instance.
(rehash): Changed this loop to avoid redundant reads and make
it obvious that null checking is not needed.
(writeObject): Use EntryIterator instance.
(HashIterator): Removed class.
(Enumerator): Removed class.
(EntryIterator): New class.
(KeyIterator): New class.
(ValueIterator): New class.
(EntryEnumerator): New class.
(KeyEnumerator): New class.
(ValueEnumerator): New class.
Cheers, Roman
Index: java/util/Hashtable.java
===================================================================
RCS file: /cvsroot/classpath/classpath/java/util/Hashtable.java,v
retrieving revision 1.36
diff -u -r1.36 Hashtable.java
--- java/util/Hashtable.java 10 Jan 2006 07:53:45 -0000 1.36
+++ java/util/Hashtable.java 10 Jan 2006 15:47:28 -0000
@@ -111,12 +111,6 @@
*/
private static final int DEFAULT_CAPACITY = 11;
- /** An "enum" of iterator types. */
- // Package visible for use by nested classes.
- static final int KEYS = 0,
- VALUES = 1,
- ENTRIES = 2;
-
/**
* The default load factor; this is explicitly specified by the spec.
*/
@@ -303,7 +297,7 @@
*/
public Enumeration keys()
{
- return new Enumerator(KEYS);
+ return new KeyEnumerator();
}
/**
@@ -317,7 +311,7 @@
*/
public Enumeration elements()
{
- return new Enumerator(VALUES);
+ return new ValueEnumerator();
}
/**
@@ -581,8 +575,8 @@
{
// Since we are already synchronized, and entrySet().iterator()
// would repeatedly re-lock/release the monitor, we directly use the
- // unsynchronized HashIterator instead.
- Iterator entries = new HashIterator(ENTRIES);
+ // unsynchronized EntryIterator instead.
+ Iterator entries = new EntryIterator();
StringBuffer r = new StringBuffer("{");
for (int pos = size; pos > 0; pos--)
{
@@ -624,7 +618,7 @@
public Iterator iterator()
{
- return new HashIterator(KEYS);
+ return new KeyIterator();
}
public void clear()
@@ -682,7 +676,7 @@
public Iterator iterator()
{
- return new HashIterator(VALUES);
+ return new ValueIterator();
}
public void clear()
@@ -734,7 +728,7 @@
public Iterator iterator()
{
- return new HashIterator(ENTRIES);
+ return new EntryIterator();
}
public void clear()
@@ -798,8 +792,8 @@
{
// Since we are already synchronized, and entrySet().iterator()
// would repeatedly re-lock/release the monitor, we directly use the
- // unsynchronized HashIterator instead.
- Iterator itr = new HashIterator(ENTRIES);
+ // unsynchronized EntryIterator instead.
+ Iterator itr = new EntryIterator();
int hashcode = 0;
for (int pos = size; pos > 0; pos--)
hashcode += itr.next().hashCode();
@@ -904,8 +898,12 @@
if (dest != null)
{
- while (dest.next != null)
- dest = dest.next;
+ HashEntry next = dest.next;
+ while (next != null)
+ {
+ dest = next;
+ next = dest.next;
+ }
dest.next = e;
}
else
@@ -940,8 +938,8 @@
s.writeInt(size);
// Since we are already synchronized, and entrySet().iterator()
// would repeatedly re-lock/release the monitor, we directly use the
- // unsynchronized HashIterator instead.
- Iterator it = new HashIterator(ENTRIES);
+ // unsynchronized EntryIterator instead.
+ Iterator it = new EntryIterator();
while (it.hasNext())
{
HashEntry entry = (HashEntry) it.next();
@@ -980,22 +978,18 @@
/**
* A class which implements the Iterator interface and is used for
* iterating over Hashtables.
- * This implementation is parameterized to give a sequential view of
- * keys, values, or entries; it also allows the removal of elements,
- * as per the Javasoft spec. Note that it is not synchronized; this is
- * a performance enhancer since it is never exposed externally and is
- * only used within synchronized blocks above.
+ * This implementation iterates entries. Subclasses are used to
+ * iterate key and values. It also allows the removal of elements,
+ * as per the Javasoft spec. Note that it is not synchronized; this
+ * is a performance enhancer since it is never exposed externally
+ * and is only used within synchronized blocks above.
*
* @author Jon Zeppieri
+ * @author Fridjof Siebert
*/
- private final class HashIterator implements Iterator
+ private class EntryIterator implements Iterator
{
/**
- * The type of this Iterator: [EMAIL PROTECTED] #KEYS}, [EMAIL PROTECTED] #VALUES},
- * or [EMAIL PROTECTED] #ENTRIES}.
- */
- final int type;
- /**
* The number of modifications to the backing Hashtable that we know about.
*/
int knownMod = modCount;
@@ -1013,14 +1007,13 @@
HashEntry next;
/**
- * Construct a new HashIterator with the supplied type.
- * @param type [EMAIL PROTECTED] #KEYS}, [EMAIL PROTECTED] #VALUES}, or [EMAIL PROTECTED] #ENTRIES}
+ * Construct a new EtryIterator
*/
- HashIterator(int type)
+ EntryIterator()
{
- this.type = type;
}
+
/**
* Returns true if the Iterator has more elements.
* @return true if there are more elements
@@ -1049,14 +1042,19 @@
HashEntry e = next;
while (e == null)
- e = buckets[--idx];
+ if (idx <= 0) /* added this test to avoid
+ * ArrayIndexOutOfBounds when Hashtable is
+ * modified concurrently, return null in this
+ * case. see test
+ * com.aicas.jamaica.testlet.bugdb.JB00310.EnumerateAndModify
+ * --Fridi.
+ */
+ return null;
+ else
+ e = buckets[--idx];
next = e.next;
last = e;
- if (type == VALUES)
- return e.value;
- if (type == KEYS)
- return e.key;
return e;
}
@@ -1077,13 +1075,57 @@
last = null;
knownMod++;
}
- } // class HashIterator
+ } // class EntryIterator
+
+ /**
+ * A class which implements the Iterator interface and is used for
+ * iterating over keys in Hashtables.
+ *
+ * @author Fridtjof Siebert
+ */
+ private class KeyIterator extends EntryIterator
+ {
+ /**
+ * Returns the next element in the Iterator's sequential view.
+ *
+ * @return the next element
+ *
+ * @throws ConcurrentModificationException if the hashtable was modified
+ * @throws NoSuchElementException if there is none
+ */
+ public Object next()
+ {
+ return ((HashEntry)super.next()).key;
+ }
+ } // class KeyIterator
+
/**
- * Enumeration view of this Hashtable, providing sequential access to its
- * elements; this implementation is parameterized to provide access either
- * to the keys or to the values in the Hashtable.
+ * A class which implements the Iterator interface and is used for
+ * iterating over values in Hashtables.
+ *
+ * @author Fridtjof Siebert
+ */
+ private class ValueIterator extends EntryIterator
+ {
+ /**
+ * Returns the next element in the Iterator's sequential view.
+ *
+ * @return the next element
+ *
+ * @throws ConcurrentModificationException if the hashtable was modified
+ * @throws NoSuchElementException if there is none
+ */
+ public Object next()
+ {
+ return ((HashEntry)super.next()).value;
+ }
+ } // class ValueIterator
+
+ /**
+ * Enumeration view of the entries in this Hashtable, providing
+ * sequential access to its elements.
*
* <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
* as this could cause a rehash and we'd completely lose our place. Even
@@ -1093,13 +1135,10 @@
* hashtable during enumeration causes indeterminate results. Don't do it!
*
* @author Jon Zeppieri
+ * @author Fridjof Siebert
*/
- private final class Enumerator implements Enumeration
+ private class EntryEnumerator implements Enumeration
{
- /**
- * The type of this Iterator: [EMAIL PROTECTED] #KEYS} or [EMAIL PROTECTED] #VALUES}.
- */
- final int type;
/** The number of elements remaining to be returned by next(). */
int count = size;
/** Current index in the physical hash table. */
@@ -1113,11 +1152,10 @@
/**
* Construct the enumeration.
- * @param type either [EMAIL PROTECTED] #KEYS} or [EMAIL PROTECTED] #VALUES}.
*/
- Enumerator(int type)
+ EntryEnumerator()
{
- this.type = type;
+ // Nothing to do here.
}
/**
@@ -1142,10 +1180,70 @@
HashEntry e = next;
while (e == null)
- e = buckets[--idx];
+ if (idx <= 0)
+ return null;
+ else
+ e = buckets[--idx];
next = e.next;
- return type == VALUES ? e.value : e.key;
+ return e;
+ }
+ } // class EntryEnumerator
+
+
+ /**
+ * Enumeration view of this Hashtable, providing sequential access to its
+ * elements.
+ *
+ * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
+ * as this could cause a rehash and we'd completely lose our place. Even
+ * without a rehash, it is undetermined if a new element added would
+ * appear in the enumeration. The spec says nothing about this, but
+ * the "Java Class Libraries" book infers that modifications to the
+ * hashtable during enumeration causes indeterminate results. Don't do it!
+ *
+ * @author Jon Zeppieri
+ * @author Fridjof Siebert
+ */
+ private final class KeyEnumerator extends EntryEnumerator
+ {
+ /**
+ * Returns the next element.
+ * @return the next element
+ * @throws NoSuchElementException if there is none.
+ */
+ public Object nextElement()
+ {
+ return ((HashEntry)super.nextElement()).key;
+ }
+ } // class KeyEnumerator
+
+
+ /**
+ * Enumeration view of this Hashtable, providing sequential access to its
+ * values.
+ *
+ * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
+ * as this could cause a rehash and we'd completely lose our place. Even
+ * without a rehash, it is undetermined if a new element added would
+ * appear in the enumeration. The spec says nothing about this, but
+ * the "Java Class Libraries" book infers that modifications to the
+ * hashtable during enumeration causes indeterminate results. Don't do it!
+ *
+ * @author Jon Zeppieri
+ * @author Fridjof Siebert
+ */
+ private final class ValueEnumerator extends EntryEnumerator
+ {
+ /**
+ * Returns the next element.
+ * @return the next element
+ * @throws NoSuchElementException if there is none.
+ */
+ public Object nextElement()
+ {
+ return ((HashEntry)super.nextElement()).value;
}
- } // class Enumerator
+ } // class ValueEnumerator
+
} // class Hashtable
_______________________________________________
Classpath-patches mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/classpath-patches
