From d9fd7154ec7908eff8bbbce75651eccf51064ac1 Mon Sep 17 00:00:00 2001 From: Bryce McKinlay Date: Sat, 15 Dec 2001 07:47:03 +0000 Subject: Collections drop from Classpath: 2001-12-15 Bryce McKinlay * java/util/BitSet.java (and): Fix off-by-one bug, don't skip part of the bitset. (andNot): Likewise. (xor): Likewise. 2001-12-15 Bryce McKinlay * java/util/LinkedList.java (LinkedListItr.add): Don't skip the next entry. 2001-12-15 Eric Blake * java/util/TreeMap.java (removeNode): Fix bug in node removal. 2001-12-15 Bryce McKinlay * java/util/AbstractCollection.java (containsAll): Use size of the correct collection for loop bound. * java/util/AbstractList.java (iterator.next): Increment pos after calling get on backing list. (listIterator.next): Likewise. * java/util/LinkedList.java (addLastEntry): Don't increment size before checking for size == 0. (addFirstEntry): Rearrange to match addLastEntry. (add): Do not increment size before inserting the new entry. * java/util/AbstractCollection.java (addAll): Use size of the correct collection for loop bound. 2001-12-15 Bryce McKinlay * java/util/AbstractSet.java (removeAll): Fix scoping thinko. * java/util/HashMap.java (putAllInternal): Set size here. * java/util/Hashtable.java (putAllInternal): New method. Copy contents of a map efficiently without calling put() or putAll(). (Hashtable (map)): Use putAllInternal. (clone): Likewise. 2001-12-15 Eric Blake * java/util/Collections.java: * java/util/Vector.java: * java/util/WeakHashMap.java: Fix spelling errors. 2001-12-15 Eric Blake * java/util/AbstractCollection.java (removeAllInternal), (retainAllInternal): Add hooks for use by ArrayList. * java/util/AbstractList.java: Minor code updates. Fix some scoping. * java/util/AbstractMap.java: ditto * java/util/ArrayList.java (readObject, writeObject): ditto (removeAllInternal, retainAllInternal): Optimize. * java/util/Arrays.java: ditto * java/util/Collections.java: ditto. Change order of parameters to equals(Object, Object) to match specs. * java/util/Dictionary.java: Improve javadoc. (Dictionary): Add explicit constructor. * java/util/HashMap.java: Improve javadoc. Rearrange methods to follow order in JDK. Cleanups related to recent code migration to AbstractMap. Fix some scoping. (entrySet): Cache the result. (modCount): Ensure that this is updated correctly. * java/util/HashSet.java: Improve javadoc. Fix some scoping. (init): Add hooks for LinkedHashSet. (map): Use "" instead of Boolean.TRUE in backing map. Use package-private API where possible for less overhead. (readObject, writeObject): Fix serialization. * java/util/Hashtable.java: Improve javadoc. Fix some scoping. (entrySet, keySet, values): Cache the result. (modCount): Ensure that this is updated correctly. (contains, remove): Fix NullPointer checking to match specs. (class Enumeration): Make more like HashIterator. * java/util/IdentityHashMap.java: Minor code updates. (modCount): Ensure that this is updated correctly. (readObject, writeObject): Fix serialization. * java/util/LinkedHashMap.java: Minor code updates. Cleanups related to recent code migration to AbstractMap. * java/util/LinkedHashSet.java: New file. * java/util/LinkedList.java: (readObject, writeObject): Fix serialization. * java/util/Makefile.am: List recently added files. * java/util/Stack.java: Minor code updates. * java/util/TreeMap.java: Improve javadoc. Overhaul the class to be more efficient. Fix some scoping. Rearrange the methods. (nil): Ensure that this can be thread-safe, and make it a static final. Initialize it to be more useful as a sentinal node. (Node): Specify color in constructor. (deleteFixup, insertFixup): Improve comments and algorithm. (fabricateTree): Redesign with less overhead. (lowestGreaterThan): Add parameter first to make SubMap easier. (removeNode): Patch hole where nil was being modified. Choose predecessor instead of successor so in-place swap works. (class VerifyResult, verifyTree, verifySub, verifyError): Remove this dead code after verifying the class works. (class SubMap): Rewrite several algorithms to avoid problems with comparing nil. * java/util/TreeSet.java: Improve javadoc. Fix some scoping. (clone): Fix ClassCastException when cloning subSet(). (readObject, writeObject): Fix serialization. * java/util/WeakHashMap.java: Improve javadoc. Fix some scoping. (NULL_KEY): Make it compare as null, for ease elsewhere. (Class WeakEntry): Rename from Entry, to avoid shadowing Map.Entry. Add missing toString. (modCount): Ensure that this is updated correctly. (clear, containsValue, keySet, putAll, values, WeakHashMap(Map)): Add missing methods and constructor. 2001-12-15 Eric Blake * java/util/ArrayList.java (checkBoundExclusive), (checkBoundInclusive): Rename from range??clusive, to match AbstractList. * java/util/LinkedList.java (checkBoundsExclusive), (checkBoundsInclusive): ditto * java/util/Vector.java (checkBoundExclusive), (checkBoundInclusive): Move bounds checking into common methods. 2001-12-15 Eric Blake * java/util/AbstractList.java: (modCount): Make sure it is updated in all needed places. * java/util/ArrayList.java: Improve javadoc. Implements RandomAccess. Add serialVersionUID. Reorder methods. (modCount): Make sure it is updated in all needed places. (rangeExclusive, rangeInclusive): Add common methods for bounds check. (isEmpty): Add missing method. * java/util/Collections.java: (class SynchronizedList): Make package visible. * java/util/ConcurrentModificationException.java: Improve javadoc. * java/util/EmptyStackException.java: Improve javadoc. * java/util/LinkedList.java: Improve javadoc. (modCount): Make sure it is updated in all needed places. (rangeExclusive, rangeInclusive): Add common methods for bounds check. * java/util/NoSuchElementException.java: Improve javadoc. * java/util/Stack.java: Improve javadoc. Fix synchronization issues. (modCount): Make sure it is updated in all needed places. * java/util/Vector.java: Improve javadoc. Fix synchronization issues. Implements RandomAccess. Reorder methods. (modCount): Make sure it is updated in all needed places. (setSize): Fix according to specifications: this does not dictate the backing array size. (removeAll, retainAll): Faster implementations. 2001-12-15 Eric Blake * java/util/BitSet.java: Improve javadoc. (cardinality(), clear(), clear(int, int), flip(int)), (flip(int, int), get(int, int), intersects(BitSet), isEmpty()), (nextClearBit(int), nextSetBit(int), set(int, boolean)), (set(int, int), set(int, int, boolean)): Add new JDK 1.4 methods. (clone): Fix so subclasses clone correctly. 2001-12-15 Eric Blake * java/util/AbstractCollection.java: Improve javadoc. (AbstractCollection()): Make constructor protected. (equals(Object, Object), hashCode(Object)): Add utility methods. * java/util/AbstractList.java: Improve javadoc. (AbstractList()): Make constructor protected. (indexOf(Object)): Call listIterator(), not listIterator(int). (iterator()): Follow Sun's requirement to not use listIterator(0). (listIterator(int)): Make AbstractListItr anonymous. (subList(int, int)): Add support for RandomAccess. (SubList.add(int, Object), SubList.remove(Object)): Fix bug with modCount tracking. (SubList.addAll(Collection)): Add missing method. (SubList.listIterator(int)): Fix bugs in indexing, modCount tracking. (class RandomAccessSubList): Add new class. * java/util/AbstractMap.java: Improve javadoc. (keys, values, KEYS, VALUES, ENTRIES): Consolidate common map fields. (AbstractMap()): Make constructor protected. (equals(Object, Object), hashCode(Object)): Add utility methods. (equals(Object)): Change algorithm to entrySet().equals(m.entrySet()), as documented by Sun. (keySet(), values()): Cache the collections. * java/util/AbstractSequentialList.java: Improve javadoc. (AbstractSequentialList()): Make constructor protected. * java/util/AbstractSet.java: Improve javadoc. (AbstractSet()): Make constructor protected. (removeAll(Collection)): Add missing method. * java/util/Arrays.java: Improve javadoc, rearrange method orders. (defaultComparator): Remove, in favor of Collections.compare(Object, Object, Comparator). (binarySearch, equals, sort): Fix natural order comparison of floats and doubles. Also improve Object comparison - when comparator is null, use natural order. (fill, sort): Add missing checks for IllegalArgumentException. (sort, qsort): Fix sorting bugs, rework the code for more legibility. (mergeSort): Inline into sort(Object[], int, int, Comparator). (class ArrayList): Rename from ListImpl, and make compatible with JDK serialization. Add methods which more efficiently override those of AbstractList. * java/util/Collections: Improve javadoc. (isSequential(List)): Add and use a method for deciding between RandomAccess and sequential algorithms on lists. (class Empty*, class Synchronized*, class Unmodifiable*): Make compliant with JDK serializability. (class Singleton*, class CopiesList, class RevereseComparator), (class UnmodifiableMap.UnmodifiableEntrySet), (class *RandomAccessList): New classes for serial compatibility. (class Empty*, class Singleton*, class CopiesList): Add methods which more efficiently override those of Abstract*. (search): Inline into binarySearch(List, Object, Comparator). (binarySearch): Make sequential search only do log(n) comparisons, instead of n. (copy(List, List)): Do bounds checking before starting. (indexOfSubList, lastIndexOfSubList, list, replaceAll, rotate), (swap): Add new JDK 1.4 methods. (binarySearch, max, min, sort): Allow null comparator to represent natural ordering. (reverse(List)): Avoid unnecessary swap. (shuffle(List, Random)): Do shuffle in-place for RandomAccess lists. (SingletonList.get): Fix logic bug. (SingletonMap.entrySet): Make the entry immutable, and cache the returned set. (SynchronizedCollection, SynchronizedMap, UnmodifiableCollection), (UnmodifiableMap): Detect null pointer in construction. (SynchronizedMap, UnmodifiableMap): Cache collection views. * java/util/BasicMapEntry: Improve javadoc. From-SVN: r48035 --- libjava/java/util/Hashtable.java | 512 +++++++++++++++++++++------------------ 1 file changed, 270 insertions(+), 242 deletions(-) (limited to 'libjava/java/util/Hashtable.java') diff --git a/libjava/java/util/Hashtable.java b/libjava/java/util/Hashtable.java index 2a90244..0133269 100644 --- a/libjava/java/util/Hashtable.java +++ b/libjava/java/util/Hashtable.java @@ -66,7 +66,9 @@ import java.io.ObjectOutputStream; * Unlike HashMap, Hashtable does not accept `null' as a key value. Also, * all accesses are synchronized: in a single thread environment, this is * expensive, but in a multi-thread environment, this saves you the effort - * of extra synchronization. + * of extra synchronization. However, the old-style enumerators are not + * synchronized, because they can lead to unspecified behavior even if + * they were synchronized. You have been warned. *

* * The iterators are fail-fast, meaning that any structural @@ -84,6 +86,7 @@ import java.io.ObjectOutputStream; * @see IdentityHashMap * @see LinkedHashMap * @since 1.0 + * @status updated to 1.4 */ public class Hashtable extends Dictionary implements Map, Cloneable, Serializable @@ -93,6 +96,12 @@ public class Hashtable extends Dictionary */ 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. */ @@ -106,39 +115,57 @@ public class Hashtable extends Dictionary /** * The rounded product of the capacity and the load factor; when the number * of elements exceeds the threshold, the Hashtable calls - * 

rehash()
. + * rehash(). * @serial */ - int threshold; + private int threshold; /** * Load factor of this Hashtable: used in computing the threshold. * @serial */ - final float loadFactor; + private final float loadFactor; /** * Array containing the actual key-value mappings. */ + // Package visible for use by nested classes. transient HashEntry[] buckets; /** * Counts the number of modifications this Hashtable has undergone, used * by Iterators to know when to throw ConcurrentModificationExceptions. */ + // Package visible for use by nested classes. transient int modCount; /** * The size of this Hashtable: denotes the number of key-value pairs. */ + // Package visible for use by nested classes. transient int size; /** + * The cache for {@link #keySet()}. + */ + private transient Set keys; + + /** + * The cache for {@link #values()}. + */ + private transient Collection values; + + /** + * The cache for {@link #entrySet()}. + */ + private transient Set entries; + + /** * Class to represent an entry in the hash table. Holds a single key-value * pair. A Hashtable Entry is identical to a HashMap Entry, except that * `null' is not allowed for keys and values. */ - static class HashEntry extends BasicMapEntry + private static final class HashEntry extends BasicMapEntry { /** The next entry in the linked list. */ HashEntry next; @@ -159,7 +186,7 @@ public class Hashtable extends Dictionary * @return the prior value * @throws NullPointerException if newVal is null */ - public final Object setValue(Object newVal) + public Object setValue(Object newVal) { if (newVal == null) throw new NullPointerException(); @@ -193,15 +220,15 @@ public class Hashtable extends Dictionary public Hashtable(Map m) { this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR); - putAll(m); + putAllInternal(m); } /** * Construct a new Hashtable with a specific inital capacity and * default load factor of 0.75. * - * @param initialCapacity the initial capacity of this Hashtable (>=0) - * @throws IllegalArgumentException if (initialCapacity < 0) + * @param initialCapacity the initial capacity of this Hashtable (>= 0) + * @throws IllegalArgumentException if (initialCapacity < 0) */ public Hashtable(int initialCapacity) { @@ -212,10 +239,10 @@ public class Hashtable extends Dictionary * Construct a new Hashtable with a specific initial capacity and * load factor. * - * @param initialCapacity the initial capacity (>=0) - * @param loadFactor the load factor (>0, not NaN) - * @throws IllegalArgumentException if (initialCapacity < 0) || - * ! (loadFactor > 0.0) + * @param initialCapacity the initial capacity (>= 0) + * @param loadFactor the load factor (> 0, not NaN) + * @throws IllegalArgumentException if (initialCapacity < 0) || + * ! (loadFactor > 0.0) */ public Hashtable(int initialCapacity, float loadFactor) { @@ -251,30 +278,36 @@ public class Hashtable extends Dictionary } /** - * Return an enumeration of the keys of this table. + * Return an enumeration of the keys of this table. There's no point + * in synchronizing this, as you have already been warned that the + * enumeration is not specified to be thread-safe. + * * @return the keys * @see #elements() * @see #keySet() */ - public synchronized Enumeration keys() + public Enumeration keys() { - return new Enumerator(Enumerator.KEYS); + return new Enumerator(KEYS); } /** - * Return an enumeration of the values of this table. + * Return an enumeration of the values of this table. There's no point + * in synchronizing this, as you have already been warned that the + * enumeration is not specified to be thread-safe. + * * @return the values * @see #keys() * @see #values() */ - public synchronized Enumeration elements() + public Enumeration elements() { - return new Enumerator(Enumerator.VALUES); + return new Enumerator(VALUES); } /** - * Returns true if this Hashtable contains a value 
o
, - * such that 
o.equals(value)
. This is the same as + * Returns true if this Hashtable contains a value o, + * such that o.equals(value). This is the same as * containsValue(), and is O(n). *

* @@ -284,48 +317,46 @@ public class Hashtable extends Dictionary * * @param value the value to search for in this Hashtable * @return true if at least one key maps to the value - * @throws NullPointerException if 

value
is null + * @throws NullPointerException if value is null * @see #containsValue(Object) * @see #containsKey(Object) */ public synchronized boolean contains(Object value) { - // Check if value is null in case Hashtable is empty. + // Check if value is null. if (value == null) throw new NullPointerException(); - - for (int i = buckets.length - 1; i >= 0; i--) - { - HashEntry e = buckets[i]; - while (e != null) - { - if (value.equals(e.value)) - return true; - e = e.next; - } - } - return false; + return containsValue(value); } /** - * Returns true if this Hashtable contains a value 
o
, such that - * 
o.equals(value)
. This is the new API for the old - * contains(). + * Returns true if this Hashtable contains a value o, such that + * o.equals(value). This is the new API for the old + * contains(), except that it is forgiving of null. * * @param value the value to search for in this Hashtable * @return true if at least one key maps to the value - * @throws NullPointerException if 
value
is null * @see #contains(Object) * @see #containsKey(Object) * @since 1.2 */ public boolean containsValue(Object value) { - return contains(value); + for (int i = buckets.length - 1; i >= 0; i--) + { + HashEntry e = buckets[i]; + while (e != null) + { + if (AbstractCollection.equals(value, e.value)) + return true; + e = e.next; + } + } + return false; } /** - * Returns true if the supplied object 
equals()
a key + * Returns true if the supplied object equals() a key * in this Hashtable. * * @param key the key to search for in this Hashtable @@ -348,7 +379,7 @@ public class Hashtable extends Dictionary /** * Return the value in this Hashtable associated with the supplied key, - * or 
null
if the key maps to nothing. + * or null if the key maps to nothing. * * @param key the key for which to fetch an associated value * @return what the key maps to, if present @@ -383,7 +414,6 @@ public class Hashtable extends Dictionary */ public synchronized Object put(Object key, Object value) { - modCount++; int idx = hash(key); HashEntry e = buckets[idx]; @@ -407,6 +437,7 @@ public class Hashtable extends Dictionary } // At this point, we know we need to add a new entry. + modCount++; if (++size > threshold) { rehash(); @@ -425,15 +456,18 @@ public class Hashtable extends Dictionary /** * Removes from the table and returns the value which is mapped by the * supplied key. If the key maps to nothing, then the table remains - * unchanged, and 
null
is returned. + * unchanged, and null is returned. + * NOTE:Map.remove and Dictionary.remove disagree whether null + * is a valid parameter; at the moment, this implementation obeys Map.remove, + * and silently ignores null. * * @param key the key used to locate the value to remove * @return whatever the key mapped to, if present - * @throws NullPointerException if key is null */ public synchronized Object remove(Object key) { - modCount++; + if (key == null) + return null; int idx = hash(key); HashEntry e = buckets[idx]; HashEntry last = null; @@ -442,6 +476,7 @@ public class Hashtable extends Dictionary { if (key.equals(e.key)) { + modCount++; if (last == null) buckets[idx] = e.next; else @@ -488,9 +523,12 @@ public class Hashtable extends Dictionary */ public synchronized void clear() { - modCount++; - Arrays.fill(buckets, null); - size = 0; + if (size > 0) + { + modCount++; + Arrays.fill(buckets, null); + size = 0; + } } /** @@ -511,36 +549,18 @@ public class Hashtable extends Dictionary // This is impossible. } copy.buckets = new HashEntry[buckets.length]; - - for (int i = buckets.length - 1; i >= 0; i--) - { - HashEntry e = buckets[i]; - HashEntry last = null; - - while (e != null) - { - if (last == null) - { - last = new HashEntry(e.key, e.value); - copy.buckets[i] = last; - } - else - { - last.next = new HashEntry(e.key, e.value); - last = last.next; - } - e = e.next; - } - } + copy.putAllInternal(this); + // Clear the caches. + copy.keys = null; + copy.values = null; + copy.entries = null; return copy; } /** - * Converts this Hashtable to a String, surrounded by braces (
'{'
- * and 
'}'
), key/value pairs listed with an equals sign between, - * (
'='
), and pairs separated by comma and space - * (
", "
). - *

+ * Converts this Hashtable to a String, surrounded by braces, and with + * key/value pairs listed with an equals sign between, separated by a + * comma and space. For example, "{a=1, b=2}".

* * NOTE: if the toString() method of any key or value * throws an exception, this will fail for the same reason. @@ -552,7 +572,7 @@ public class Hashtable extends Dictionary // 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(HashIterator.ENTRIES); + Iterator entries = new HashIterator(ENTRIES); StringBuffer r = new StringBuffer("{"); for (int pos = size; pos > 0; pos--) { @@ -568,9 +588,11 @@ public class Hashtable extends Dictionary * Returns a "set view" of this Hashtable's keys. The set is backed by * the hashtable, so changes in one show up in the other. The set supports * element removal, but not element addition. The set is properly - * synchronized on the original hashtable. The set will throw a - * {@link NullPointerException} if null is passed to contains, - * remove, or related methods. + * synchronized on the original hashtable. Sun has not documented the + * proper interaction of null with this set, but has inconsistent behavior + * in the JDK. Therefore, in this implementation, contains, remove, + * containsAll, retainAll, removeAll, and equals just ignore a null key + * rather than throwing a {@link NullPointerException}. * * @return a set view of the keys * @see #values() @@ -579,50 +601,56 @@ public class Hashtable extends Dictionary */ public Set keySet() { - // Create a synchronized AbstractSet with custom implementations of those - // methods that can be overridden easily and efficiently. - Set r = new AbstractSet() - { - public int size() + if (keys == null) { - return size; - } + // Create a synchronized AbstractSet with custom implementations of + // those methods that can be overridden easily and efficiently. + Set r = new AbstractSet() + { + public int size() + { + return size; + } - public Iterator iterator() - { - return new HashIterator(HashIterator.KEYS); - } + public Iterator iterator() + { + return new HashIterator(KEYS); + } - public void clear() - { - Hashtable.this.clear(); - } + public void clear() + { + Hashtable.this.clear(); + } - public boolean contains(Object o) - { - return Hashtable.this.containsKey(o); - } + public boolean contains(Object o) + { + if (o == null) + return false; + return containsKey(o); + } - public boolean remove(Object o) - { - return (Hashtable.this.remove(o) != null); + public boolean remove(Object o) + { + return Hashtable.this.remove(o) != null; + } + }; + // We must specify the correct object to synchronize upon, hence the + // use of a non-public API + keys = new Collections.SynchronizedSet(this, r); } - }; - - // We must specify the correct object to synchronize upon, hence the - // use of a non-public API - return new Collections.SynchronizedSet(this, r); + return keys; } - /** * Returns a "collection view" (or "bag view") of this Hashtable's values. * The collection is backed by the hashtable, so changes in one show up * in the other. The collection supports element removal, but not element * addition. The collection is properly synchronized on the original - * hashtable. The collection will throw a {@link NullPointerException} - * if null is passed to contains or related methods, but not - * if passed to remove or related methods. + * hashtable. Sun has not documented the proper interaction of null with + * this set, but has inconsistent behavior in the JDK. Therefore, in this + * implementation, contains, remove, containsAll, retainAll, removeAll, and + * equals just ignore a null value rather than throwing a + * {@link NullPointerException}. * * @return a bag view of the values * @see #keySet() @@ -631,46 +659,45 @@ public class Hashtable extends Dictionary */ public Collection values() { - // We don't bother overriding many of the optional methods, as doing so - // wouldn't provide any significant performance advantage. - Collection r = new AbstractCollection() - { - public int size() - { - return size; - } - - public Iterator iterator() + if (values == null) { - return new HashIterator(HashIterator.VALUES); - } + // We don't bother overriding many of the optional methods, as doing so + // wouldn't provide any significant performance advantage. + Collection r = new AbstractCollection() + { + public int size() + { + return size; + } - public void clear() - { - Hashtable.this.clear(); - } + public Iterator iterator() + { + return new HashIterator(VALUES); + } - // Override this so that we check for null - public boolean contains(Object o) - { - return Hashtable.this.contains(o); + public void clear() + { + Hashtable.this.clear(); + } + }; + // We must specify the correct object to synchronize upon, hence the + // use of a non-public API + values = new Collections.SynchronizedCollection(this, r); } - }; - - // We must specify the correct object to synchronize upon, hence the - // use of a non-public API - return new Collections.SynchronizedCollection(this, r); + return values; } /** * Returns a "set view" of this Hashtable's entries. The set is backed by * the hashtable, so changes in one show up in the other. The set supports * element removal, but not element addition. The set is properly - * synchronized on the original hashtable. The set will throw a - * {@link NullPointerException} if the Map.Entry passed to - * contains, remove, or related methods returns - * null for getKey, but not if the Map.Entry is null or - * returns null for getValue. + * synchronized on the original hashtable. Sun has not documented the + * proper interaction of null with this set, but has inconsistent behavior + * in the JDK. Therefore, in this implementation, contains, remove, + * containsAll, retainAll, removeAll, and equals just ignore a null entry, + * or an entry with a null key or value, rather than throwing a + * {@link NullPointerException}. However, calling entry.setValue(null) + * will fail. *

* * Note that the iterators for all three views, from keySet(), entrySet(), @@ -684,49 +711,52 @@ public class Hashtable extends Dictionary */ public Set entrySet() { - // Create an AbstractSet with custom implementations of those methods that - // can be overridden easily and efficiently. - Set r = new AbstractSet() - { - public int size() + if (entries == null) { - return size; - } + // Create an AbstractSet with custom implementations of those methods + // that can be overridden easily and efficiently. + Set r = new AbstractSet() + { + public int size() + { + return size; + } - public Iterator iterator() - { - return new HashIterator(HashIterator.ENTRIES); - } + public Iterator iterator() + { + return new HashIterator(ENTRIES); + } - public void clear() - { - Hashtable.this.clear(); - } + public void clear() + { + Hashtable.this.clear(); + } - public boolean contains(Object o) - { - return getEntry(o) != null; - } + public boolean contains(Object o) + { + return getEntry(o) != null; + } - public boolean remove(Object o) - { - HashEntry e = getEntry(o); - if (e != null) + public boolean remove(Object o) { - Hashtable.this.remove(e.key); - return true; + HashEntry e = getEntry(o); + if (e != null) + { + Hashtable.this.remove(e.key); + return true; + } + return false; } - return false; + }; + // We must specify the correct object to synchronize upon, hence the + // use of a non-public API + entries = new Collections.SynchronizedSet(this, r); } - }; - - // We must specify the correct object to synchronize upon, hence the - // use of a non-public API - return new Collections.SynchronizedSet(this, r); + return entries; } /** - * Returns true if this Hashtable equals the supplied Object 

o
. + * Returns true if this Hashtable equals the supplied Object o. * As specified by Map, this is: * 
    * (o instanceof Map) && entrySet().equals(((Map) o).entrySet());
@@ -759,7 +789,7 @@ public class Hashtable extends Dictionary
     // 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(HashIterator.ENTRIES);
+    Iterator itr = new HashIterator(ENTRIES);
     int hashcode = 0;
     for (int pos = size; pos > 0; pos--)
       hashcode += itr.next().hashCode();
@@ -782,23 +812,25 @@ public class Hashtable extends Dictionary
 
   /**
    * Helper method for entrySet(), which matches both key and value
-   * simultaneously.
+   * simultaneously. Ignores null, as mentioned in entrySet().
    *
    * @param o the entry to match
    * @return the matching entry, if found, or null
-   * @throws NullPointerException if me.getKey() returns null
    * @see #entrySet()
    */
   private HashEntry getEntry(Object o)
   {
-    if (!(o instanceof Map.Entry))
+    if (! (o instanceof Map.Entry))
+      return null;
+    Object key = ((Map.Entry) o).getKey();
+    if (key == null)
       return null;
-    Map.Entry me = (Map.Entry) o;
-    int idx = hash(me.getKey());
+
+    int idx = hash(key);
     HashEntry e = buckets[idx];
     while (e != null)
       {
-        if (e.equals(me))
+        if (o.equals(e))
           return e;
         e = e.next;
       }
@@ -806,6 +838,30 @@ public class Hashtable extends Dictionary
   }
 
   /**
+   * A simplified, more efficient internal implementation of putAll(). The 
+   * Map constructor and clone() should not call putAll or put, in order to 
+   * be compatible with the JDK implementation with respect to subclasses.
+   *
+   * @param m the map to initialize this from
+   */
+  void putAllInternal(Map m)
+  {
+    Iterator itr = m.entrySet().iterator();
+    int msize = m.size();
+    this.size = msize;
+
+    for (; msize > 0; msize--)
+      {
+	Map.Entry e = (Map.Entry) itr.next();
+	Object key = e.getKey();
+	int idx = hash(key);
+	HashEntry he = new HashEntry(key, e.getValue());
+	he.next = buckets[idx];
+	buckets[idx] = he;
+      }
+  }
+
+  /**
    * Increases the size of the Hashtable and rehashes all keys to new array
    * indices; this is called when the addition of a new value would cause
    * size() > threshold. Note that the existing Entry objects are reused in
@@ -813,7 +869,8 @@ public class Hashtable extends Dictionary
    * 

    *
    * This is not specified, but the new size is twice the current size plus
-   * one; this number is not always prime, unfortunately.
+   * one; this number is not always prime, unfortunately. This implementation
+   * is not synchronized, as it is only invoked from synchronized methods.
    */
   protected void rehash()
   {
@@ -854,8 +911,8 @@ public class Hashtable extends Dictionary
    *
    * @param s the stream to write to
    * @throws IOException if the underlying stream fails
-   * @serialData the capacity(int) that is the length of the
-   *             bucket array, the size(int) of the hash map
+   * @serialData the capacity (int) that is the length of the
+   *             bucket array, the size (int) of the hash map
    *             are emitted first.  They are followed by size entries,
    *             each consisting of a key (Object) and a value (Object).
    */
@@ -870,7 +927,7 @@ public class Hashtable extends Dictionary
     // 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(HashIterator.ENTRIES);
+    Iterator it = new HashIterator(ENTRIES);
     while (it.hasNext())
       {
         HashEntry entry = (HashEntry) it.next();
@@ -885,8 +942,8 @@ public class Hashtable extends Dictionary
    * @param s the stream to read from
    * @throws ClassNotFoundException if the underlying stream fails
    * @throws IOException if the underlying stream fails
-   * @serialData the capacity(int) that is the length of the
-   *             bucket array, the size(int) of the hash map
+   * @serialData the capacity (int) that is the length of the
+   *             bucket array, the size (int) of the hash map
    *             are emitted first.  They are followed by size entries,
    *             each consisting of a key (Object) and a value (Object).
    */
@@ -901,7 +958,8 @@ public class Hashtable extends Dictionary
     int len = s.readInt();
 
     // Read and use key/value pairs.
-    for ( ; len > 0; len--)
+    // TODO: should we be defensive programmers, and check for illegal nulls?
+    while (--len >= 0)
       put(s.readObject(), s.readObject());
   }
 
@@ -916,13 +974,8 @@ public class Hashtable extends Dictionary
    *
    * @author Jon Zeppieri
    */
-  class HashIterator implements Iterator
+  private final class HashIterator implements Iterator
   {
-    /** "enum" of iterator types. */
-    static final int KEYS = 0,
-                     VALUES = 1,
-                     ENTRIES = 2;
-
     /**
      * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
      * or {@link #ENTRIES}.
@@ -988,14 +1041,14 @@ public class Hashtable extends Dictionary
       last = e;
       if (type == VALUES)
         return e.value;
-      else if (type == KEYS)
+      if (type == KEYS)
         return e.key;
       return e;
     }
 
     /**
      * Removes from the backing Hashtable the last element which was fetched
-     * with the 
next()
 method.
+     * with the next() method.
      * @throws ConcurrentModificationException if the hashtable was modified
      * @throws IllegalStateException if called when there is no last element
      */
@@ -1007,10 +1060,10 @@ public class Hashtable extends Dictionary
         throw new IllegalStateException();
 
       Hashtable.this.remove(last.key);
-      knownMod++;
       last = null;
+      knownMod++;
     }
-  }
+  } // class HashIterator
 
 
   /**
@@ -1027,21 +1080,21 @@ public class Hashtable extends Dictionary
    *
    * @author Jon Zeppieri
    */
-  class Enumerator implements Enumeration
+  private final class Enumerator implements Enumeration
   {
-    /** "enum" of iterator types. */
-    static final int KEYS = 0,
-                     VALUES = 1;
-
     /**
      * The type of this Iterator: {@link #KEYS} or {@link #VALUES}.
      */
-    int type;
+    final int type;
+    /** The number of elements remaining to be returned by next(). */
+    int count = size;
     /** Current index in the physical hash table. */
-    int idx;
-    /** The last Entry returned by nextEntry(). */
-    HashEntry last;
-    /** Entry which will be returned by the next nextElement() call. */
+    int idx = buckets.length;
+    /**
+     * Entry which will be returned by the next nextElement() call. It is
+     * set if we are iterating through a bucket with multiple entries, or null
+     * if we must look in the next bucket.
+     */
     HashEntry next;
 
     /**
@@ -1051,25 +1104,6 @@ public class Hashtable extends Dictionary
     Enumerator(int type)
     {
       this.type = type;
-      this.idx = buckets.length;
-    }
-
-    /**
-     * Helper method to find the next entry.
-     * @return the next entry, or null
-     */
-    private HashEntry nextEntry()
-    {
-      HashEntry e = null;
-
-      if (last != null)
-        e = last.next;
-
-      while (e == null && idx > 0)
-        e = buckets[--idx];
-
-      last = e;
-      return e;
     }
 
     /**
@@ -1078,10 +1112,7 @@ public class Hashtable extends Dictionary
      */
     public boolean hasMoreElements()
     {
-      if (next != null)
-        return true;
-      next = nextEntry();
-      return next != null;
+      return count > 0;
     }
 
     /**
@@ -1091,19 +1122,16 @@ public class Hashtable extends Dictionary
      */
     public Object nextElement()
     {
-      HashEntry e;
-      if (next != null)
-        {
-          e = next;
-          next = null;
-        }
-      else
-        e = nextEntry();
-      if (e == null)
+      if (count == 0)
         throw new NoSuchElementException("Hashtable Enumerator");
-      if (type == VALUES)
-        return e.value;
-      return e.key;
+      count--;
+      HashEntry e = next;
+
+      while (e == null)
+        e = buckets[--idx];
+
+      next = e.next;
+      return type == VALUES ? e.value : e.key;
     }
-  }
+  } // class Enumerator
 }
-- 
cgit v1.1