diff options
Diffstat (limited to 'luni/src')
16 files changed, 2472 insertions, 2059 deletions
diff --git a/luni/src/main/java/java/util/HashMap.java b/luni/src/main/java/java/util/HashMap.java index 999063d..af24d86 100644 --- a/luni/src/main/java/java/util/HashMap.java +++ b/luni/src/main/java/java/util/HashMap.java @@ -1,10 +1,10 @@ /* * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with + * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at + * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * @@ -15,279 +15,102 @@ * limitations under the License. */ +// BEGIN android-note +// Completely different implementation from harmony. Runs much faster. +// BEGIN android-note + package java.util; import java.io.IOException; +import java.io.InvalidObjectException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; +import java.io.ObjectStreamField; import java.io.Serializable; /** * HashMap is an implementation of Map. All optional operations (adding and * removing) are supported. Keys and values can be any objects. + * + * @param <K> the type of keys maintained by this map + * @param <V> the type of mapped values */ -public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, - Cloneable, Serializable { - - private static final long serialVersionUID = 362498820763181265L; - - /* - * Actual count of entries +public class HashMap<K, V> extends AbstractMap<K, V> + implements Cloneable, Serializable, Map<K, V> { + /** + * Min capacity (other than zero) for a HashMap. Must be a power of two + * greater than 1 (and less than 1 << 30). */ - transient int elementCount; + private static final int MINIMUM_CAPACITY = 4; - /* - * The internal data structure to hold Entries + /** + * Max capacity for a HashMap. Must be a power of two >= MINIMUM_CAPACITY. */ - transient Entry<K, V>[] elementData; + private static final int MAXIMUM_CAPACITY = 1 << 30; - /* - * modification count, to keep track of structural modifications between the - * HashMap and the iterator + /** + * An empty table shared by all zero-capacity maps (typically from default + * constructor). It is never written to, and replaced on first put. Its size + * is set to half the minimum, so that the first resize will create a + * minimum-sized table. */ - transient int modCount = 0; + private static final Entry[] EMPTY_TABLE + = new HashMapEntry[MINIMUM_CAPACITY >>> 1]; - /* - * default size that an HashMap created using the default constructor would - * have. + /** + * The default load factor. Note that this implementation ignores the + * load factor, but cannot do away with it entirely because it's + * metioned in the API. + * + * <p>Note that this constant has no impact on the behavior of the program, + * but it is emitted as part of the serialized form. The load factor of + * .75 is hardwired into the program, which uses cheap shifts in place of + * expensive division. */ - private static final int DEFAULT_SIZE = 16; + static final float DEFAULT_LOAD_FACTOR = .75F; - /* - * maximum ratio of (stored elements)/(storage size) which does not lead to - * rehash + /** + * The hash table. If this hash map contains a mapping for null, it is + * not represented this hash table. */ - final float loadFactor; + transient HashMapEntry<K, V>[] table; - /* - * maximum number of elements that can be put in this map before having to - * rehash + /** + * The entry representing the null key, or null if there's no such mapping. */ - int threshold; - - static class Entry<K, V> extends MapEntry<K, V> { - final int origKeyHash; - - Entry<K, V> next; + transient HashMapEntry<K, V> entryForNullKey; - Entry(K theKey, int hash) { - super(theKey, null); - this.origKeyHash = hash; - } - - Entry(K theKey, V theValue) { - super(theKey, theValue); - origKeyHash = (theKey == null ? 0 : computeHashCode(theKey)); - } - - @Override - @SuppressWarnings("unchecked") - public Object clone() { - Entry<K, V> entry = (Entry<K, V>) super.clone(); - if (next != null) { - entry.next = (Entry<K, V>) next.clone(); - } - return entry; - } - } - - private static class AbstractMapIterator<K, V> { - private int position = 0; - int expectedModCount; - Entry<K, V> futureEntry; - Entry<K, V> currentEntry; - Entry<K, V> prevEntry; - - final HashMap<K, V> associatedMap; - - AbstractMapIterator(HashMap<K, V> hm) { - associatedMap = hm; - expectedModCount = hm.modCount; - futureEntry = null; - } - - public boolean hasNext() { - if (futureEntry != null) { - return true; - } - // BEGIN android-changed - Entry<K, V>[] elementData = associatedMap.elementData; - int length = elementData.length; - int newPosition = position; - boolean result = false; - - while (newPosition < length) { - if (elementData[newPosition] == null) { - newPosition++; - } else { - result = true; - break; - } - } - - position = newPosition; - return result; - // END android-changed - } - - final void checkConcurrentMod() throws ConcurrentModificationException { - if (expectedModCount != associatedMap.modCount) { - throw new ConcurrentModificationException(); - } - } - - final void makeNext() { - // BEGIN android-changed - // inline checkConcurrentMod() - if (expectedModCount != associatedMap.modCount) { - throw new ConcurrentModificationException(); - } - // END android-changed - if (!hasNext()) { - throw new NoSuchElementException(); - } - if (futureEntry == null) { - currentEntry = associatedMap.elementData[position++]; - futureEntry = currentEntry.next; - prevEntry = null; - } else { - if(currentEntry!=null){ - prevEntry = currentEntry; - } - currentEntry = futureEntry; - futureEntry = futureEntry.next; - } - } - - public final void remove() { - checkConcurrentMod(); - if (currentEntry==null) { - throw new IllegalStateException(); - } - if(prevEntry==null){ - int index = currentEntry.origKeyHash & (associatedMap.elementData.length - 1); - associatedMap.elementData[index] = associatedMap.elementData[index].next; - } else { - prevEntry.next = currentEntry.next; - } - currentEntry = null; - expectedModCount++; - associatedMap.modCount++; - associatedMap.elementCount--; - - } - } - - - private static class EntryIterator <K, V> extends AbstractMapIterator<K, V> implements Iterator<Map.Entry<K, V>> { - - EntryIterator (HashMap<K, V> map) { - super(map); - } - - public Map.Entry<K, V> next() { - makeNext(); - return currentEntry; - } - } - - private static class KeyIterator <K, V> extends AbstractMapIterator<K, V> implements Iterator<K> { - - KeyIterator (HashMap<K, V> map) { - super(map); - } - - public K next() { - makeNext(); - return currentEntry.key; - } - } - - private static class ValueIterator <K, V> extends AbstractMapIterator<K, V> implements Iterator<V> { - - ValueIterator (HashMap<K, V> map) { - super(map); - } - - public V next() { - makeNext(); - return currentEntry.value; - } - } - - static class HashMapEntrySet<KT, VT> extends AbstractSet<Map.Entry<KT, VT>> { - private final HashMap<KT, VT> associatedMap; - - public HashMapEntrySet(HashMap<KT, VT> hm) { - associatedMap = hm; - } - - HashMap<KT, VT> hashMap() { - return associatedMap; - } - - @Override - public int size() { - return associatedMap.elementCount; - } - - @Override - public void clear() { - associatedMap.clear(); - } - - @Override - public boolean remove(Object object) { - if (object instanceof Map.Entry) { - Map.Entry<?, ?> oEntry = (Map.Entry<?, ?>) object; - Entry<KT,VT> entry = associatedMap.getEntry(oEntry.getKey()); - if(valuesEq(entry, oEntry)) { - associatedMap.removeEntry(entry); - return true; - } - } - return false; - } - - @Override - public boolean contains(Object object) { - if (object instanceof Map.Entry) { - Map.Entry<?, ?> oEntry = (Map.Entry<?, ?>) object; - Entry<KT, VT> entry = associatedMap.getEntry(oEntry.getKey()); - return valuesEq(entry, oEntry); - } - return false; - } - - private static boolean valuesEq(Entry entry, Map.Entry<?, ?> oEntry) { - return (entry != null) && - ((entry.value == null) ? - (oEntry.getValue() == null) : - (areEqualValues(entry.value, oEntry.getValue()))); - } + /** + * The number of mappings in this hash map. + */ + transient int size; - @Override - public Iterator<Map.Entry<KT, VT>> iterator() { - return new EntryIterator<KT,VT> (associatedMap); - } - } + /** + * Incremented by "structural modifications" to allow (best effort) + * detection of concurrent modification. + */ + transient int modCount; /** - * Create a new element array - * - * @param s - * @return Reference to the element array + * The table is rehashed when its size exceeds this threshold. + * The value of this field is generally .75 * capacity, except when + * the capacity is zero, as described in the EMPTY_TABLE declaration + * above. */ - @SuppressWarnings("unchecked") - Entry<K, V>[] newElementArray(int s) { - return new Entry[s]; - } + private transient int threshold; + + // Views - lazily initialized + private transient Set<K> keySet; + private transient Set<Entry<K, V>> entrySet; + private transient Collection<V> values; /** * Constructs a new empty {@code HashMap} instance. */ + @SuppressWarnings("unchecked") public HashMap() { - this(DEFAULT_SIZE); + table = (HashMapEntry<K, V>[]) EMPTY_TABLE; + threshold = -1; // Forces first put invocation to replace EMPTY_TABLE } /** @@ -299,34 +122,26 @@ public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, * when the capacity is less than zero. */ public HashMap(int capacity) { - this(capacity, 0.75f); // default load factor of 0.75 + if (capacity < 0) { + throw new IllegalArgumentException("Capacity: " + capacity); } - /** - * Calculates the capacity of storage required for storing given number of - * elements - * - * @param x - * number of elements - * @return storage size - */ - private static final int calculateCapacity(int x) { - if(x >= 1 << 30){ - return 1 << 30; + if (capacity == 0) { + @SuppressWarnings("unchecked") + HashMapEntry<K, V>[] tab = (HashMapEntry<K, V>[]) EMPTY_TABLE; + table = tab; + threshold = -1; // Forces first put() to replace EMPTY_TABLE + return; } - if(x == 0){ - return 16; + + if (capacity < MINIMUM_CAPACITY) { + capacity = MINIMUM_CAPACITY; + } else if (capacity > MAXIMUM_CAPACITY) { + capacity = MAXIMUM_CAPACITY; + } else { + capacity = roundUpToPowerOfTwo(capacity); } - // BEGIN android-note - // this may be better optimized as Integer.highestOneBit(x) - // END android-note - x = x -1; - x |= x >> 1; - x |= x >> 2; - x |= x >> 4; - x |= x >> 8; - x |= x >> 16; - return x + 1; + makeTable(capacity); } /** @@ -339,18 +154,20 @@ public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, * the initial load factor. * @throws IllegalArgumentException * when the capacity is less than zero or the load factor is - * less or equal to zero. + * less or equal to zero or NaN. */ public HashMap(int capacity, float loadFactor) { - if (capacity >= 0 && loadFactor > 0) { - capacity = calculateCapacity(capacity); - elementCount = 0; - elementData = newElementArray(capacity); - this.loadFactor = loadFactor; - computeThreshold(); - } else { - throw new IllegalArgumentException(); + this(capacity); + + if (loadFactor <= 0 || Float.isNaN(loadFactor)) { + throw new IllegalArgumentException("Load factor: " + loadFactor); } + + /* + * Note that this implementation ignores loadFactor; it always uses + * a load facator of 3/4. This simplifies the code and generally + * improves performance. + */ } /** @@ -361,118 +178,92 @@ public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, * the mappings to add. */ public HashMap(Map<? extends K, ? extends V> map) { - this(calculateCapacity(map.size())); - putAllImpl(map); + this(capacityForInitSize(map.size())); + constructorPutAll(map); } /** - * Removes all mappings from this hash map, leaving it empty. - * - * @see #isEmpty - * @see #size + * Inserts all of the elements of map into this HashMap in a manner + * suitable for use by constructors and pseudocostructors (i.e., clone, + * readObject). Also used by LinkedHashMap. */ - @Override - public void clear() { - // BEGIN android-changed - internalClear(); - // END android-changed + final void constructorPutAll(Map<? extends K, ? extends V> map) { + for (Entry<? extends K, ? extends V> e : map.entrySet()) { + constructorPut(e.getKey(), e.getValue()); + } } - // BEGIN android-added - void internalClear() { - if (elementCount > 0) { - elementCount = 0; - Arrays.fill(elementData, null); - modCount++; - } + /** + * Returns an appropriate capacity for the specified initial size. Does + * not round the result up to a power of two; the caller must do this! + * The returned value will be between 0 and MAXIMUM_CAPACITY (inclusive). + */ + static int capacityForInitSize(int size) { + int result = (size >> 1) + size; // Multiply by 3/2 to allow for growth + + // boolean expr is equivalent to result >= 0 && result<MAXIMUM_CAPACITY + return (result & ~(MAXIMUM_CAPACITY-1))==0 ? result : MAXIMUM_CAPACITY; } - // END android-added /** * Returns a shallow copy of this map. * * @return a shallow copy of this map. */ - @Override @SuppressWarnings("unchecked") - public Object clone() { + @Override public Object clone() { + /* + * This could be made more efficient. It unnecessarily hashes all of + * the elements in the map. + */ + HashMap<K, V> result; try { - HashMap<K, V> map = (HashMap<K, V>) super.clone(); - map.elementCount = 0; - map.elementData = newElementArray(elementData.length); - map.putAll(this); - - return map; + result = (HashMap<K, V>) super.clone(); } catch (CloneNotSupportedException e) { - return null; + throw new AssertionError(e); } - } - /** - * Computes the threshold for rehashing - */ - private void computeThreshold() { - threshold = (int) (elementData.length * loadFactor); + // Restore clone to empty state, retaining our capacity and threshold + result.makeTable(table.length); + result.entryForNullKey = null; + result.size = 0; + result.keySet = null; + result.entrySet = null; + result.values = null; + + result.init(); // Give subclass a chance to initialize itself + result.constructorPutAll(this); // Calls method overridden in subclass!! + return result; } /** - * Returns whether this map contains the specified key. - * - * @param key - * the key to search for. - * @return {@code true} if this map contains the specified key, - * {@code false} otherwise. + * This method is called from the pseudo-constructors (clone and readObject) + * prior to invoking constructorPut/constructorPutAll, which invoke the + * overriden constructorNewEntry method. Normally it is a VERY bad idea to + * invoke an overridden method from a pseudo-constructor (Effective Java + * Item 17). In this cases it is unavoidable, and the init method provides a + * workaround. */ - @Override - public boolean containsKey(Object key) { - Entry<K, V> m = getEntry(key); - return m != null; - } + void init() { } /** - * Returns whether this map contains the specified value. + * Returns whether this map is empty. * - * @param value - * the value to search for. - * @return {@code true} if this map contains the specified value, - * {@code false} otherwise. + * @return {@code true} if this map has no elements, {@code false} + * otherwise. + * @see #size() */ - @Override - public boolean containsValue(Object value) { - if (value != null) { - for (int i = 0; i < elementData.length; i++) { - Entry<K, V> entry = elementData[i]; - while (entry != null) { - if (areEqualValues(value, entry.value)) { - return true; - } - entry = entry.next; - } - } - } else { - for (int i = 0; i < elementData.length; i++) { - Entry<K, V> entry = elementData[i]; - while (entry != null) { - if (entry.value == null) { - return true; - } - entry = entry.next; - } - } - } - return false; + @Override public boolean isEmpty() { + return size == 0; } /** - * Returns a set containing all of the mappings in this map. Each mapping is - * an instance of {@link Map.Entry}. As the set is backed by this map, - * changes in one will be reflected in the other. + * Returns the number of elements in this map. * - * @return a set of the mappings. + * @return the number of elements in this map. */ - @Override - public Set<Map.Entry<K, V>> entrySet() { - return new HashMapEntrySet<K, V>(this); + @Override public int size() { + return size; } /** @@ -483,104 +274,88 @@ public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, * @return the value of the mapping with the specified key, or {@code null} * if no mapping for the specified key is found. */ - @Override public V get(Object key) { - Entry<K, V> m = getEntry(key); - if (m != null) { - return m.value; - } - return null; - } - - final Entry<K, V> getEntry(Object key) { - Entry<K, V> m; if (key == null) { - m = findNullKeyEntry(); - } else { - int hash = computeHashCode(key); - int index = hash & (elementData.length - 1); - m = findNonNullKeyEntry(key, index, hash); + HashMapEntry<K, V> e = entryForNullKey; + return e == null ? null : e.value; } - return m; - } - - final Entry<K,V> findNonNullKeyEntry(Object key, int index, int keyHash) { - Entry<K,V> m = elementData[index]; - // BEGIN android-changed - // The VM can optimize String.equals but not Object.equals - if (key instanceof String) { - String keyString = (String) key; - while (m != null && (m.origKeyHash != keyHash || !keyString.equals(m.key))) { - m = m.next; - } - } else { - while (m != null && (m.origKeyHash != keyHash || !areEqualKeys(key, m.key))) { - m = m.next; + // Doug Lea's supplemental secondaryHash function (inlined) + int hash = key.hashCode(); + hash ^= (hash >>> 20) ^ (hash >>> 12); + hash ^= (hash >>> 7) ^ (hash >>> 4); + + HashMapEntry<K, V>[] tab = table; + for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)]; + e != null; e = e.next) { + K eKey = e.key; + if (eKey == key || (e.hash == hash && key.equals(eKey))) { + return e.value; } } - return m; - // END android-changed - } - - final Entry<K,V> findNullKeyEntry() { - Entry<K,V> m = elementData[0]; - while (m != null && m.key != null) - m = m.next; - return m; + return null; } /** - * Returns whether this map is empty. + * Returns whether this map contains the specified key. * - * @return {@code true} if this map has no elements, {@code false} - * otherwise. - * @see #size() + * @param key + * the key to search for. + * @return {@code true} if this map contains the specified key, + * {@code false} otherwise. */ - @Override - public boolean isEmpty() { - return elementCount == 0; + @Override public boolean containsKey(Object key) { + if (key == null) { + return entryForNullKey != null; + } + + // Doug Lea's supplemental secondaryHash function (inlined) + int hash = key.hashCode(); + hash ^= (hash >>> 20) ^ (hash >>> 12); + hash ^= (hash >>> 7) ^ (hash >>> 4); + + HashMapEntry<K, V>[] tab = table; + for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)]; + e != null; e = e.next) { + K eKey = e.key; + if (eKey == key || (e.hash == hash && key.equals(eKey))) { + return true; + } + } + return false; } /** - * Returns a set of the keys contained in this map. The set is backed by - * this map so changes to one are reflected by the other. The set does not - * support adding. + * Returns whether this map contains the specified value. * - * @return a set of the keys. + * @param value + * the value to search for. + * @return {@code true} if this map contains the specified value, + * {@code false} otherwise. */ - @Override - public Set<K> keySet() { - if (keySet == null) { - keySet = new AbstractSet<K>() { - @Override - public boolean contains(Object object) { - return containsKey(object); - } - - @Override - public int size() { - return HashMap.this.size(); - } - - @Override - public void clear() { - HashMap.this.clear(); - } - - @Override - public boolean remove(Object key) { - Entry<K, V> entry = HashMap.this.removeEntry(key); - return entry != null; + @Override public boolean containsValue(Object value) { + HashMapEntry[] tab = table; + int len = tab.length; + if (value == null) { + for (int i = 0; i < len; i++) { + for (HashMapEntry e = tab[i]; e != null; e = e.next) { + if (e.value == null) { + return true; + } } + } + return entryForNullKey != null && entryForNullKey.value == null; + } - @Override - public Iterator<K> iterator() { - return new KeyIterator<K,V> (HashMap.this); + // value is non-null + for (int i = 0; i < len; i++) { + for (HashMapEntry e = tab[i]; e != null; e = e.next) { + if (value.equals(e.value)) { + return true; } - }; + } } - return keySet; + return entryForNullKey != null && value.equals(entryForNullKey.value); } /** @@ -593,53 +368,110 @@ public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, * @return the value of any previous mapping with the specified key or * {@code null} if there was no such mapping. */ - @Override - public V put(K key, V value) { - return putImpl(key, value); - } + @Override public V put(K key, V value) { + if (key == null) { + return putValueForNullKey(value); + } - V putImpl(K key, V value) { - Entry<K,V> entry; - if(key == null) { - entry = findNullKeyEntry(); - if (entry == null) { - modCount++; - if (++elementCount > threshold) { - rehash(); - } - entry = createHashedEntry(null, 0, 0); + int hash = secondaryHash(key.hashCode()); + HashMapEntry<K, V>[] tab = table; + int index = hash & (tab.length - 1); + HashMapEntry<K, V> first = tab[index]; + for (HashMapEntry<K, V> e = first; e != null; e = e.next) { + if (e.hash == hash && key.equals(e.key)) { + preModify(e); + V oldValue = e.value; + e.value = value; + return oldValue; } + } + + // No entry for (non-null) key is present; create one + modCount++; + if (size++ > threshold) { + tab = doubleCapacity(); + index = hash & (tab.length - 1); + first = tab[index]; + } + tab[index] = newEntry(key, value, hash, first); + return null; + } + + private V putValueForNullKey(V value) { + HashMapEntry<K, V> entry = entryForNullKey; + if (entry == null) { + entryForNullKey = newEntry(null, value, 0, null); + size++; + modCount++; + return null; } else { - int hash = computeHashCode(key); - int index = hash & (elementData.length - 1); - entry = findNonNullKeyEntry(key, index, hash); + preModify(entry); + V oldValue = entry.value; + entry.value = value; + return oldValue; + } + } + + /** + * Give LinkedHashMap a chance to take action when we modify an exisitng + * entry. + * + * @param e the entry we're about to modify. + */ + void preModify(HashMapEntry<K, V> e) { } + + /** + * This method is just like put, except that it doesn't do things that + * are inappropriate or unnecessary for constructors and pseudo-constructors + * (i.e., clone, readObject). In particular, this method does not check to + * ensure that capacity is sufficient, and does not increment modCount. + */ + private void constructorPut(K key, V value) { + if (key == null) { + HashMapEntry<K, V> entry = entryForNullKey; if (entry == null) { - modCount++; - if (++elementCount > threshold) { - rehash(); - index = hash & (elementData.length - 1); - } - entry = createHashedEntry(key, index, hash); + entryForNullKey = constructorNewEntry(null, value, 0, null); + size++; + } else { + entry.value = value; } + return; } - V result = entry.value; - entry.value = value; - return result; + int hash = secondaryHash(key.hashCode()); + HashMapEntry<K, V>[] tab = table; + int index = hash & (tab.length - 1); + HashMapEntry<K, V> first = tab[index]; + for (HashMapEntry<K, V> e = first; e != null; e = e.next) { + if (e.hash == hash && key.equals(e.key)) { + e.value = value; + return; + } + } + + // No entry for (non-null) key is present; create one + tab[index] = constructorNewEntry(key, value, hash, first); + size++; } - Entry<K, V> createEntry(K key, int index, V value) { - Entry<K, V> entry = new Entry<K, V>(key, value); - entry.next = elementData[index]; - elementData[index] = entry; - return entry; + /** + * Creates a new entry for the given key, value, hash, and successor entry. + * This method is called by put (and indirectly, putAll), and overridden by + * LinkedHashMap. The hash must incorporate the secondary hash function. + */ + HashMapEntry<K, V> newEntry( + K key, V value, int hash, HashMapEntry<K, V> next) { + return new HashMapEntry<K, V>(key, value, hash, next); } - Entry<K,V> createHashedEntry(K key, int index, int hash) { - Entry<K,V> entry = new Entry<K,V>(key,hash); - entry.next = elementData[index]; - elementData[index] = entry; - return entry; + /** + * Like newEntry, but does not perform any activity that would be + * unnecessary or inappropriate for constructors. In this class, the + * two methods behave identically; in LinkedHashMap, they differ. + */ + HashMapEntry<K, V> constructorNewEntry( + K key, V value, int hash, HashMapEntry<K, V> first) { + return new HashMapEntry<K, V>(key, value, hash, first); } /** @@ -649,46 +481,108 @@ public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, * * @param map * the map to copy mappings from. - * @throws NullPointerException - * if {@code map} is {@code null}. */ - @Override - public void putAll(Map<? extends K, ? extends V> map) { - if (!map.isEmpty()) { - putAllImpl(map); - } + @Override public void putAll(Map<? extends K, ? extends V> map) { + ensureCapacity(map.size()); + super.putAll(map); } - private void putAllImpl(Map<? extends K, ? extends V> map) { - int capacity = elementCount + map.size(); - if (capacity > threshold) { - rehash(capacity); + /** + * Ensures that the hash table has sufficient capacity to store the + * specified number of mappings, with room to grow. If not, it increases the + * capacity as appropriate. Like doubleCapacity, this method moves existing + * entries to new buckets as appropriate. Unlike doubleCapacity, this method + * can grow the table by factors of 2^n for n > 1. Hopefully, a single call + * to this method will be faster than multiple calls to doubleCapacity. + * + * <p>This method is called only by putAll. + */ + private void ensureCapacity(int numMappings) { + int newCapacity = roundUpToPowerOfTwo(capacityForInitSize(numMappings)); + HashMapEntry<K, V>[] oldTable = table; + int oldCapacity = oldTable.length; + if (newCapacity <= oldCapacity) { + return; } - for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { - putImpl(entry.getKey(), entry.getValue()); + if (newCapacity == oldCapacity << 1) { + doubleCapacity(); + return; } - } - - void rehash(int capacity) { - int length = calculateCapacity((capacity == 0 ? 1 : capacity << 1)); - Entry<K, V>[] newData = newElementArray(length); - for (int i = 0; i < elementData.length; i++) { - Entry<K, V> entry = elementData[i]; - while (entry != null) { - int index = entry.origKeyHash & (length - 1); - Entry<K, V> next = entry.next; - entry.next = newData[index]; - newData[index] = entry; - entry = next; + // We're growing by at least 4x, rehash in the obvious way + HashMapEntry<K, V>[] newTable = makeTable(newCapacity); + if (size != 0) { + int newMask = newCapacity - 1; + for (int i = 0; i < oldCapacity; i++) { + for (HashMapEntry<K, V> e = oldTable[i]; e != null;) { + HashMapEntry<K, V> oldNext = e.next; + int newIndex = e.hash & newMask; + HashMapEntry<K, V> newNext = newTable[newIndex]; + newTable[newIndex] = e; + e.next = newNext; + e = oldNext; + } } } - elementData = newData; - computeThreshold(); } - void rehash() { - rehash(elementData.length); + /** + * Allocate a table of the given capacity and set the threshold accordingly. + * @param newCapacity must be a power of two + */ + private HashMapEntry<K, V>[] makeTable(int newCapacity) { + @SuppressWarnings("unchecked") HashMapEntry<K, V>[] newTable + = (HashMapEntry<K, V>[]) new HashMapEntry[newCapacity]; + table = newTable; + threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity + return newTable; + } + + /** + * Doubles the capacity of the hash table. Existing entries are placed in + * the correct bucket on the enlarged table. If the current capacity is, + * MAXIMUM_CAPACITY, this method is a no-op. Returns the table, which + * will be new unless we were already at MAXIMUM_CAPACITY. + */ + private HashMapEntry<K, V>[] doubleCapacity() { + HashMapEntry<K, V>[] oldTable = table; + int oldCapacity = oldTable.length; + if (oldCapacity == MAXIMUM_CAPACITY) { + return oldTable; + } + int newCapacity = oldCapacity << 1; + HashMapEntry<K, V>[] newTable = makeTable(newCapacity); + if (size == 0) { + return newTable; + } + + for (int j = 0; j < oldCapacity; j++) { + /* + * Rehash the bucket using the minimum number of field writes. + * This is the most subtle and delicate code in the class. + */ + HashMapEntry<K, V> e = oldTable[j]; + if (e == null) { + continue; + } + int highBit = e.hash & oldCapacity; + HashMapEntry<K, V> broken = null; + newTable[j | highBit] = e; + for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) { + int nextHighBit = n.hash & oldCapacity; + if (nextHighBit != highBit) { + if (broken == null) + newTable[j | nextHighBit] = n; + else + broken.next = n; + broken = e; + highBit = nextHighBit; + } + } + if (broken != null) + broken.next = null; + } + return newTable; } /** @@ -699,75 +593,72 @@ public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, * @return the value of the removed mapping or {@code null} if no mapping * for the specified key was found. */ - @Override - public V remove(Object key) { - Entry<K, V> entry = removeEntry(key); - if (entry != null) { - return entry.value; + @Override public V remove(Object key) { + if (key == null) { + return removeNullKey(); + } + int hash = secondaryHash(key.hashCode()); + HashMapEntry<K, V>[] tab = table; + int index = hash & (tab.length - 1); + for (HashMapEntry<K, V> e = tab[index], prev = null; + e != null; prev = e, e = e.next) { + if (e.hash == hash && key.equals(e.key)) { + if (prev == null) { + tab[index] = e.next; + } else { + prev.next = e.next; + } + modCount++; + size--; + postRemove(e); + return e.value; + } } return null; } - /* - * Remove the given entry from the hashmap. - * Assumes that the entry is in the map. - */ - final void removeEntry(Entry<K, V> entry) { - int index = entry.origKeyHash & (elementData.length - 1); - Entry<K, V> m = elementData[index]; - if (m == entry) { - elementData[index] = entry.next; - } else { - while (m.next != entry) { - m = m.next; - } - m.next = entry.next; - - } - modCount++; - elementCount--; - } - - final Entry<K, V> removeEntry(Object key) { - int index = 0; - Entry<K, V> entry; - Entry<K, V> last = null; - if (key != null) { - int hash = computeHashCode(key); - index = hash & (elementData.length - 1); - entry = elementData[index]; - while (entry != null && !(entry.origKeyHash == hash && areEqualKeys(key, entry.key))) { - last = entry; - entry = entry.next; - } - } else { - entry = elementData[0]; - while (entry != null && entry.key != null) { - last = entry; - entry = entry.next; - } - } - if (entry == null) { + private V removeNullKey() { + HashMapEntry<K, V> e = entryForNullKey; + if (e == null) { return null; } - if (last == null) { - elementData[index] = entry.next; - } else { - last.next = entry.next; - } + entryForNullKey = null; modCount++; - elementCount--; - return entry; + size--; + postRemove(e); + return e.value; } /** - * Returns the number of elements in this map. + * Subclass overrides this method to unlink entry. + */ + void postRemove(HashMapEntry<K, V> e) { } + + /** + * Removes all mappings from this hash map, leaving it empty. * - * @return the number of elements in this map. + * @see #isEmpty + * @see #size + */ + @Override public void clear() { + if (size != 0) { + Arrays.fill(table, null); + entryForNullKey = null; + modCount++; + size = 0; + } + } + + /** + * Returns a set of the keys contained in this map. The set is backed by + * this map so changes to one are reflected by the other. The set does not + * support adding. + * + * @return a set of the keys. */ - @Override - public int size() { - return elementCount; + @Override public Set<K> keySet() { + Set<K> ks = keySet; + return (ks != null) ? ks : (keySet = new KeySet()); } /** @@ -781,83 +672,363 @@ public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, * "wrapper object" over the iterator of map's entrySet(). The {@code size} * method wraps the map's size method and the {@code contains} method wraps * the map's containsValue method. + * </p> * <p> * The collection is created when this method is called for the first time * and returned in response to all subsequent calls. This method may return * different collections when multiple concurrent calls occur, since no * synchronization is performed. + * </p> * * @return a collection of the values contained in this map. */ - @Override - public Collection<V> values() { - if (valuesCollection == null) { - valuesCollection = new AbstractCollection<V>() { - @Override - public boolean contains(Object object) { - return containsValue(object); - } + @Override public Collection<V> values() { + Collection<V> vs = values; + return (vs != null) ? vs : (values = new Values()); + } - @Override - public int size() { - return HashMap.this.size(); - } + /** + * Returns a set containing all of the mappings in this map. Each mapping is + * an instance of {@link Map.Entry}. As the set is backed by this map, + * changes in one will be reflected in the other. + * + * @return a set of the mappings. + */ + public Set<Entry<K, V>> entrySet() { + Set<Entry<K, V>> es = entrySet; + return (es != null) ? es : (entrySet = new EntrySet()); + } - @Override - public void clear() { - HashMap.this.clear(); + static class HashMapEntry<K, V> implements Entry<K, V> { + final K key; + V value; + final int hash; + HashMapEntry<K, V> next; + + HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) { + this.key = key; + this.value = value; + this.hash = hash; + this.next = next; + } + + public final K getKey() { + return key; + } + + public final V getValue() { + return value; + } + + public final V setValue(V value) { + V oldValue = this.value; + this.value = value; + return oldValue; + } + + @Override public final boolean equals(Object o) { + if (!(o instanceof Entry)) { + return false; + } + Entry<?, ?> e = (Entry<?, ?>) o; + return HashMap.equals(e.getKey(), key) + && HashMap.equals(e.getValue(), value); + } + + @Override public final int hashCode() { + return (key == null ? 0 : key.hashCode()) ^ + (value == null ? 0 : value.hashCode()); + } + + @Override public final String toString() { + return key + "=" + value; + } + } + + private abstract class HashIterator { + int nextIndex; + HashMapEntry<K, V> nextEntry = entryForNullKey; + HashMapEntry<K, V> lastEntryReturned; + int expectedModCount = modCount; + + HashIterator() { + if (nextEntry == null) { + HashMapEntry<K, V>[] tab = table; + HashMapEntry<K, V> next = null; + while (next == null && nextIndex < tab.length) { + next = tab[nextIndex++]; } + nextEntry = next; + } + } + + public boolean hasNext() { + return nextEntry != null; + } + + HashMapEntry<K, V> nextEntry() { + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + if (nextEntry == null) + throw new NoSuchElementException(); + + HashMapEntry<K, V> entryToReturn = nextEntry; + HashMapEntry<K, V>[] tab = table; + HashMapEntry<K, V> next = entryToReturn.next; + while (next == null && nextIndex < tab.length) { + next = tab[nextIndex++]; + } + nextEntry = next; + return lastEntryReturned = entryToReturn; + } + + public void remove() { + if (lastEntryReturned == null) + throw new IllegalStateException(); + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + HashMap.this.remove(lastEntryReturned.key); + lastEntryReturned = null; + expectedModCount = modCount; + } + } + + private final class KeyIterator extends HashIterator + implements Iterator<K> { + public K next() { return nextEntry().key; } + } - @Override - public Iterator<V> iterator() { - return new ValueIterator<K,V> (HashMap.this); + private final class ValueIterator extends HashIterator + implements Iterator<V> { + public V next() { return nextEntry().value; } + } + + private final class EntryIterator extends HashIterator + implements Iterator<Entry<K, V>> { + public Entry<K, V> next() { return nextEntry(); } + } + + /** + * Returns true if this map contains the specified mapping. + */ + private boolean containsMapping(Object key, Object value) { + if (key == null) { + HashMapEntry<K, V> e = entryForNullKey; + return e != null && equals(value, e.value); + } + + int hash = secondaryHash(key.hashCode()); + HashMapEntry<K, V>[] tab = table; + int index = hash & (tab.length - 1); + for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) { + if (e.hash == hash && key.equals(e.key)) { + return equals(value, e.value); + } + } + return false; // No entry for key + } + + /** + * Removes the mapping from key to value and returns true if this mapping + * exists; otherwise, returns does nothing and returns false. + */ + private boolean removeMapping(Object key, Object value) { + if (key == null) { + HashMapEntry<K, V> e = entryForNullKey; + if (e == null || !equals(value, e.value)) { + return false; + } + entryForNullKey = null; + modCount++; + size--; + postRemove(e); + return true; + } + + int hash = secondaryHash(key.hashCode()); + HashMapEntry<K, V>[] tab = table; + int index = hash & (tab.length - 1); + for (HashMapEntry<K, V> e = tab[index], prev = null; + e != null; prev = e, e = e.next) { + if (e.hash == hash && key.equals(e.key)) { + if (!equals(value, e.value)) { + return false; // Map has wrong value for key } - }; + if (prev == null) { + tab[index] = e.next; + } else { + prev.next = e.next; + } + modCount++; + size--; + postRemove(e); + return true; + } } - return valuesCollection; + return false; // No entry for key } - private void writeObject(ObjectOutputStream stream) throws IOException { - stream.defaultWriteObject(); - stream.writeInt(elementData.length); - stream.writeInt(elementCount); - Iterator<?> iterator = entrySet().iterator(); - while (iterator.hasNext()) { - Entry<?, ?> entry = (Entry<?, ?>) iterator.next(); - stream.writeObject(entry.key); - stream.writeObject(entry.value); - entry = entry.next; + private static boolean equals(Object o1, Object o2) { + return o1 == o2 || (o1 != null && o1.equals(o2)); + } + + // Subclass (LinkedHashMap) overrrides these for correct iteration order + Iterator<K> newKeyIterator() { return new KeyIterator(); } + Iterator<V> newValueIterator() { return new ValueIterator(); } + Iterator<Entry<K, V>> newEntryIterator() { return new EntryIterator(); } + + private final class KeySet extends AbstractSet<K> { + public Iterator<K> iterator() { + return newKeyIterator(); + } + public int size() { + return size; + } + public boolean isEmpty() { + return size == 0; + } + public boolean contains(Object o) { + return containsKey(o); + } + public boolean remove(Object o) { + int oldSize = size; + HashMap.this.remove(o); + return size != oldSize; + } + public void clear() { + HashMap.this.clear(); } } - @SuppressWarnings("unchecked") - private void readObject(ObjectInputStream stream) throws IOException, - ClassNotFoundException { - stream.defaultReadObject(); - int length = stream.readInt(); - elementData = newElementArray(length); - elementCount = stream.readInt(); - for (int i = elementCount; --i >= 0;) { - K key = (K) stream.readObject(); - int index = (null == key) ? 0 : (computeHashCode(key) & (length - 1)); - createEntry(key, index, (V) stream.readObject()); + private final class Values extends AbstractCollection<V> { + public Iterator<V> iterator() { + return newValueIterator(); + } + public int size() { + return size; + } + public boolean isEmpty() { + return size == 0; + } + public boolean contains(Object o) { + return containsValue(o); + } + public void clear() { + HashMap.this.clear(); + } + } + + private final class EntrySet extends AbstractSet<Entry<K, V>> { + public Iterator<Entry<K, V>> iterator() { + return newEntryIterator(); + } + public boolean contains(Object o) { + if (!(o instanceof Entry)) + return false; + Entry<?, ?> e = (Entry<?, ?>) o; + return containsMapping(e.getKey(), e.getValue()); + } + public boolean remove(Object o) { + if (!(o instanceof Entry)) + return false; + Entry<?, ?> e = (Entry<?, ?>)o; + return removeMapping(e.getKey(), e.getValue()); + } + public int size() { + return size; + } + public boolean isEmpty() { + return size == 0; + } + public void clear() { + HashMap.this.clear(); } } - /* - * Contract-related functionality + /** + * Applies a supplemental hash function to a given hashCode, which defends + * against poor quality hash functions. This is critical because HashMap + * uses power-of-two length hash tables, that otherwise encounter collisions + * for hashCodes that do not differ in lower or upper bits. */ - static int computeHashCode(Object key) { - return key.hashCode(); -} + private static int secondaryHash(int h) { + // Doug Lea's supplemental hash function + h ^= (h >>> 20) ^ (h >>> 12); + return h ^ (h >>> 7) ^ (h >>> 4); + } + + /** + * Returns the smallest power of two >= its argument, with several caveats: + * If the argument is negative but not Integer.MIN_VALUE, the method returns + * zero. If the argument is > 2^30 or equal to Integer.MIN_VALUE, the method + * returns Integer.MIN_VALUE. If the argument is zero, the method returns + * zero. + */ + private static int roundUpToPowerOfTwo(int i) { + i--; // If input is a power of two, shift its high-order bit right + + // "Smear" the high-order bit all the way to the right + i |= i >>> 1; + i |= i >>> 2; + i |= i >>> 4; + i |= i >>> 8; + i |= i >>> 16; - static boolean areEqualKeys(Object key1, Object key2) { - return (key1 == key2) || key1.equals(key2); + return i + 1; } - static boolean areEqualValues(Object value1, Object value2) { - return (value1 == value2) || value1.equals(value2); + private static final long serialVersionUID = 362498820763181265L; + + /** + * Serializable fields. + * + * @serialField loadFactor float + * load factor for this HashMap + */ + private static final ObjectStreamField[] serialPersistentFields = { + new ObjectStreamField("loadFactor", Float.TYPE) + }; + + private void writeObject(ObjectOutputStream stream) throws IOException { + // Emulate loadFactor field for other implementations to read + ObjectOutputStream.PutField fields = stream.putFields(); + fields.put("loadFactor", DEFAULT_LOAD_FACTOR); + stream.writeFields(); + + stream.writeInt(table.length); // Capacity + stream.writeInt(size); + for (Entry<K, V> e : entrySet()) { + stream.writeObject(e.getKey()); + stream.writeObject(e.getValue()); + } } + private void readObject(ObjectInputStream stream) throws IOException, + ClassNotFoundException { + stream.defaultReadObject(); + int capacity = stream.readInt(); + if (capacity < 0) { + throw new InvalidObjectException("Capacity: " + capacity); + } + if (capacity < MINIMUM_CAPACITY) { + capacity = MINIMUM_CAPACITY; + } else if (capacity > MAXIMUM_CAPACITY) { + capacity = MAXIMUM_CAPACITY; + } else { + capacity = roundUpToPowerOfTwo(capacity); + } + makeTable(capacity); + + int size = stream.readInt(); + if (size < 0) { + throw new InvalidObjectException("Size: " + size); + } + init(); // Give subclass (LinkedHashMap) a chance to initialize itself + for (int i = 0; i < size; i++) { + @SuppressWarnings("unchecked") K key = (K) stream.readObject(); + @SuppressWarnings("unchecked") V val = (V) stream.readObject(); + constructorPut(key, val); + } + } } diff --git a/luni/src/main/java/java/util/HashSet.java b/luni/src/main/java/java/util/HashSet.java index dca764f..4c97ca5 100644 --- a/luni/src/main/java/java/util/HashSet.java +++ b/luni/src/main/java/java/util/HashSet.java @@ -185,15 +185,11 @@ public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, private void writeObject(ObjectOutputStream stream) throws IOException { stream.defaultWriteObject(); - stream.writeInt(backingMap.elementData.length); - stream.writeFloat(backingMap.loadFactor); - stream.writeInt(backingMap.elementCount); - for (int i = backingMap.elementData.length; --i >= 0;) { - HashMap.Entry<E, HashSet<E>> entry = backingMap.elementData[i]; - while (entry != null) { - stream.writeObject(entry.key); - entry = entry.next; - } + stream.writeInt(backingMap.table.length); + stream.writeFloat(HashMap.DEFAULT_LOAD_FACTOR); + stream.writeInt(size()); + for (E e : this) { + stream.writeObject(e); } } diff --git a/luni/src/main/java/java/util/Hashtable.java b/luni/src/main/java/java/util/Hashtable.java index b23364d..ead0db3 100644 --- a/luni/src/main/java/java/util/Hashtable.java +++ b/luni/src/main/java/java/util/Hashtable.java @@ -15,15 +15,19 @@ * limitations under the License. */ +// BEGIN android-note +// Completely different implementation from harmony. Runs much faster. +// BEGIN android-note + package java.util; import java.io.IOException; +import java.io.InvalidObjectException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; +import java.io.ObjectStreamField; import java.io.Serializable; -import org.apache.harmony.luni.internal.nls.Messages; - /** * Hashtable associates keys with values. Both keys and values cannot be null. * The size of the Hashtable is the number of key/value pairs it contains. The @@ -32,212 +36,86 @@ import org.apache.harmony.luni.internal.nls.Messages; * expanding the capacity. If the load factor of the Hashtable is exceeded, the * capacity is doubled. * + * @param <K> the type of keys maintained by this map + * @param <V> the type of mapped values + * * @see Enumeration * @see java.io.Serializable * @see java.lang.Object#equals * @see java.lang.Object#hashCode */ -public class Hashtable<K, V> extends Dictionary<K, V> implements Map<K, V>, - Cloneable, Serializable { - - private static final long serialVersionUID = 1421746759512286392L; - - transient int elementCount; - - transient Entry<K, V>[] elementData; - - private float loadFactor; - - private int threshold; - - transient int firstSlot; - - transient int lastSlot = -1; - - transient int modCount; - - private static final Enumeration<?> EMPTY_ENUMERATION = new Enumeration<Object>() { - public boolean hasMoreElements() { - return false; - } - - public Object nextElement() { - throw new NoSuchElementException(); - } - }; - - private static final Iterator<?> EMPTY_ITERATOR = new Iterator<Object>() { - - public boolean hasNext() { - return false; - } - - public Object next() { - throw new NoSuchElementException(); - } - - public void remove() { - throw new IllegalStateException(); - } - }; - - private static <K, V> Entry<K, V> newEntry(K key, V value, int hash) { - return new Entry<K, V>(key, value); - } - - private static class Entry<K, V> extends MapEntry<K, V> { - Entry<K, V> next; - - final int hashcode; - - Entry(K theKey, V theValue) { - super(theKey, theValue); - hashcode = theKey.hashCode(); - } - - @Override - @SuppressWarnings("unchecked") - public Object clone() { - Entry<K, V> entry = (Entry<K, V>) super.clone(); - if (next != null) { - entry.next = (Entry<K, V>) next.clone(); - } - return entry; - } - - @Override - public V setValue(V object) { - if (object == null) { - throw new NullPointerException(); - } - V result = value; - value = object; - return result; - } - - public int getKeyHash() { - return key.hashCode(); - } - - public boolean equalsKey(Object aKey, int hash) { - // BEGIN android-changed - // The VM can inline String.equals - return hashcode == aKey.hashCode() - && (key instanceof String - ? ((String) key).equals(aKey) : key.equals(aKey)); - // END android-changed - } - - @Override - public String toString() { - return key + "=" + value; //$NON-NLS-1$ - } - } - - private class HashIterator<E> implements Iterator<E> { - int position, expectedModCount; +public class Hashtable<K, V> extends Dictionary<K, V> + implements Map<K, V>, Cloneable, Serializable { + /** + * Min capacity (other than zero) for a Hashtable. Must be a power of two + * greater than 1 (and less than 1 << 30). + */ + private static final int MINIMUM_CAPACITY = 4; - final MapEntry.Type<E, K, V> type; + /** + * Max capacity for a Hashtable. Must be a power of two >= MINIMUM_CAPACITY. + */ + private static final int MAXIMUM_CAPACITY = 1 << 30; - Entry<K, V> lastEntry; + /** + * An empty table shared by all zero-capacity maps (typically from default + * constructor). It is never written to, and replaced on first put. Its size + * is set to half the minimum, so that the first resize will create a + * minimum-sized table. + */ + private static final Entry[] EMPTY_TABLE + = new HashtableEntry[MINIMUM_CAPACITY >>> 1]; - int lastPosition; + /** + * The default load factor. Note that this implementation ignores the + * load factor, but cannot do away with it entirely because it's + * metioned in the API. + * + * <p>Note that this constant has no impact on the behavior of the program, + * but it is emitted as part of the serialized form. The load factor of + * .75 is hardwired into the program, which uses cheap shifts in place of + * expensive division. + */ + private static final float DEFAULT_LOAD_FACTOR = .75F; - boolean canRemove = false; + /** + * The hash table. + */ + private transient HashtableEntry<K, V>[] table; - HashIterator(MapEntry.Type<E, K, V> value) { - type = value; - position = lastSlot; - expectedModCount = modCount; - } + /** + * The number of mappings in this hash map. + */ + private transient int size; - public boolean hasNext() { - if (lastEntry != null && lastEntry.next != null) { - return true; - } - while (position >= firstSlot) { - if (elementData[position] == null) { - position--; - } else { - return true; - } - } - return false; - } + /** + * Incremented by "structural modifications" to allow (best effort) + * detection of concurrent modification. + */ + private transient int modCount; - public E next() { - if (expectedModCount == modCount) { - if (lastEntry != null) { - lastEntry = lastEntry.next; - } - if (lastEntry == null) { - while (position >= firstSlot - && (lastEntry = elementData[position]) == null) { - position--; - } - if (lastEntry != null) { - lastPosition = position; - // decrement the position so we don't find the same slot - // next time - position--; - } - } - if (lastEntry != null) { - canRemove = true; - return type.get(lastEntry); - } - throw new NoSuchElementException(); - } - throw new ConcurrentModificationException(); - } + /** + * The table is rehashed when its size exceeds this threshold. + * The value of this field is generally .75 * capacity, except when + * the capacity is zero, as described in the EMPTY_TABLE declaration + * above. + */ + private transient int threshold; - public void remove() { - if (expectedModCount == modCount) { - if (canRemove) { - canRemove = false; - synchronized (Hashtable.this) { - boolean removed = false; - Entry<K, V> entry = elementData[lastPosition]; - if (entry == lastEntry) { - elementData[lastPosition] = entry.next; - removed = true; - } else { - while (entry != null && entry.next != lastEntry) { - entry = entry.next; - } - if (entry != null) { - entry.next = lastEntry.next; - removed = true; - } - } - if (removed) { - modCount++; - elementCount--; - expectedModCount++; - return; - } - // the entry must have been (re)moved outside of the - // iterator - // but this condition wasn't caught by the modCount - // check - // throw ConcurrentModificationException() outside of - // synchronized block - } - } else { - throw new IllegalStateException(); - } - } - throw new ConcurrentModificationException(); - } - } + // Views - lazily initialized + private transient Set<K> keySet; + private transient Set<Entry<K, V>> entrySet; + private transient Collection<V> values; /** * Constructs a new {@code Hashtable} using the default capacity and load * factor. */ + @SuppressWarnings("unchecked") public Hashtable() { - this(11); + table = (HashtableEntry<K, V>[]) EMPTY_TABLE; + threshold = -1; // Forces first put invocation to replace EMPTY_TABLE } /** @@ -248,15 +126,26 @@ public class Hashtable<K, V> extends Dictionary<K, V> implements Map<K, V>, * the initial capacity. */ public Hashtable(int capacity) { - if (capacity >= 0) { - elementCount = 0; - elementData = newElementArray(capacity == 0 ? 1 : capacity); - firstSlot = elementData.length; - loadFactor = 0.75f; - computeMaxSize(); + if (capacity < 0) { + throw new IllegalArgumentException("Capacity: " + capacity); + } + + if (capacity == 0) { + @SuppressWarnings("unchecked") + HashtableEntry<K, V>[] tab = (HashtableEntry<K, V>[]) EMPTY_TABLE; + table = tab; + threshold = -1; // Forces first put() to replace EMPTY_TABLE + return; + } + + if (capacity < MINIMUM_CAPACITY) { + capacity = MINIMUM_CAPACITY; + } else if (capacity > MAXIMUM_CAPACITY) { + capacity = MAXIMUM_CAPACITY; } else { - throw new IllegalArgumentException(); + capacity = roundUpToPowerOfTwo(capacity); } + makeTable(capacity); } /** @@ -269,15 +158,17 @@ public class Hashtable<K, V> extends Dictionary<K, V> implements Map<K, V>, * the initial load factor. */ public Hashtable(int capacity, float loadFactor) { - if (capacity >= 0 && loadFactor > 0) { - elementCount = 0; - firstSlot = capacity; - elementData = newElementArray(capacity == 0 ? 1 : capacity); - this.loadFactor = loadFactor; - computeMaxSize(); - } else { - throw new IllegalArgumentException(); + this(capacity); + + if (loadFactor <= 0 || Float.isNaN(loadFactor)) { + throw new IllegalArgumentException("Load factor: " + loadFactor); } + + /* + * Note that this implementation ignores loadFactor; it always uses + * a load facator of 3/4. This simplifies the code and generally + * improves performance. + */ } /** @@ -288,26 +179,31 @@ public class Hashtable<K, V> extends Dictionary<K, V> implements Map<K, V>, * the mappings to add. */ public Hashtable(Map<? extends K, ? extends V> map) { - this(map.size() < 6 ? 11 : (map.size() * 4 / 3) + 11); - putAll(map); + this(capacityForInitSize(map.size())); + constructorPutAll(map); } - @SuppressWarnings("unchecked") - private Entry<K, V>[] newElementArray(int size) { - return new Entry[size]; + /** + * Inserts all of the elements of map into this Hashtable in a manner + * suitable for use by constructors and pseudocostructors (i.e., clone, + * readObject). + */ + private void constructorPutAll(Map<? extends K, ? extends V> map) { + for (Entry<? extends K, ? extends V> e : map.entrySet()) { + constructorPut(e.getKey(), e.getValue()); + } } /** - * Removes all key/value pairs from this {@code Hashtable}, leaving the - * size zero and the capacity unchanged. - * - * @see #isEmpty - * @see #size + * Returns an appropriate capacity for the specified initial size. Does + * not round the result up to a power of two; the caller must do this! + * The returned value will be between 0 and MAXIMUM_CAPACITY (inclusive). */ - public synchronized void clear() { - elementCount = 0; - Arrays.fill(elementData, null); - modCount++; + private static int capacityForInitSize(int size) { + int result = (size >> 1) + size; // Multiply by 3/2 to allow for growth + + // boolean expr is equivalent to result >= 0 && result<MAXIMUM_CAPACITY + return (result & ~(MAXIMUM_CAPACITY-1))==0 ? result : MAXIMUM_CAPACITY; } /** @@ -317,54 +213,77 @@ public class Hashtable<K, V> extends Dictionary<K, V> implements Map<K, V>, * @return a shallow copy of this {@code Hashtable}. * @see java.lang.Cloneable */ - @Override @SuppressWarnings("unchecked") - public synchronized Object clone() { + @Override public synchronized Object clone() { + /* + * This could be made more efficient. It unnecessarily hashes all of + * the elements in the map. + */ + Hashtable<K, V> result; try { - Hashtable<K, V> hashtable = (Hashtable<K, V>) super.clone(); - hashtable.elementData = new Entry[elementData.length]; - Entry<K, V> entry; - for (int i = elementData.length; --i >= 0;) { - if ((entry = elementData[i]) != null) { - hashtable.elementData[i] = (Entry<K, V>) entry.clone(); - } - } - return hashtable; + result = (Hashtable<K, V>) super.clone(); } catch (CloneNotSupportedException e) { - return null; + throw new AssertionError(e); } - } - private void computeMaxSize() { - threshold = (int) (elementData.length * loadFactor); + // Restore clone to empty state, retaining our capacity and threshold + result.makeTable(table.length); + result.size = 0; + result.keySet = null; + result.entrySet = null; + result.values = null; + + result.constructorPutAll(this); + return result; } /** - * Returns true if this {@code Hashtable} contains the specified object as - * the value of at least one of the key/value pairs. + * Returns true if this {@code Hashtable} has no key/value pairs. * - * @param value - * the object to look for as a value in this {@code Hashtable}. - * @return {@code true} if object is a value in this {@code Hashtable}, + * @return {@code true} if this {@code Hashtable} has no key/value pairs, * {@code false} otherwise. - * @see #containsKey - * @see java.lang.Object#equals + * @see #size */ - public synchronized boolean contains(Object value) { - if (value == null) { - throw new NullPointerException(); - } + public synchronized boolean isEmpty() { + return size == 0; + } - for (int i = elementData.length; --i >= 0;) { - Entry<K, V> entry = elementData[i]; - while (entry != null) { - if (entry.value.equals(value)) { - return true; - } - entry = entry.next; + /** + * Returns the number of key/value pairs in this {@code Hashtable}. + * + * @return the number of key/value pairs in this {@code Hashtable}. + * @see #elements + * @see #keys + */ + public synchronized int size() { + return size; + } + + /** + * Returns the value associated with the specified key in this + * {@code Hashtable}. + * + * @param key + * the key of the value returned. + * @return the value associated with the specified key, or {@code null} if + * the specified key does not exist. + * @see #put + */ + public synchronized V get(Object key) { + // Doug Lea's supplemental secondaryHash function (inlined) + int hash = key.hashCode(); + hash ^= (hash >>> 20) ^ (hash >>> 12); + hash ^= (hash >>> 7) ^ (hash >>> 4); + + HashtableEntry<K, V>[] tab = table; + for (HashtableEntry<K, V> e = tab[hash & (tab.length - 1)]; + e != null; e = e.next) { + K eKey = e.key; + if (eKey == key || (e.hash == hash && key.equals(eKey))) { + return e.value; } } - return false; + return null; } /** @@ -379,7 +298,20 @@ public class Hashtable<K, V> extends Dictionary<K, V> implements Map<K, V>, * @see java.lang.Object#equals */ public synchronized boolean containsKey(Object key) { - return getEntry(key) != null; + // Doug Lea's supplemental secondaryHash function (inlined) + int hash = key.hashCode(); + hash ^= (hash >>> 20) ^ (hash >>> 12); + hash ^= (hash >>> 7) ^ (hash >>> 4); + + HashtableEntry<K, V>[] tab = table; + for (HashtableEntry<K, V> e = tab[hash & (tab.length - 1)]; + e != null; e = e.next) { + K eKey = e.key; + if (eKey == key || (e.hash == hash && key.equals(eKey))) { + return true; + } + } + return false; } /** @@ -390,190 +322,319 @@ public class Hashtable<K, V> extends Dictionary<K, V> implements Map<K, V>, * @return {@code true} if {@code value} is a value of this * {@code Hashtable}, {@code false} otherwise. */ - public boolean containsValue(Object value) { - return contains(value); + public synchronized boolean containsValue(Object value) { + if (value == null) { + throw new NullPointerException(); + } + + HashtableEntry[] tab = table; + int len = tab.length; + + for (int i = 0; i < len; i++) { + for (HashtableEntry e = tab[i]; e != null; e = e.next) { + if (value.equals(e.value)) { + return true; + } + } + } + return false; } /** - * Returns an enumeration on the values of this {@code Hashtable}. The - * results of the Enumeration may be affected if the contents of this - * {@code Hashtable} are modified. + * Returns true if this {@code Hashtable} contains the specified object as + * the value of at least one of the key/value pairs. * - * @return an enumeration of the values of this {@code Hashtable}. + * @param value + * the object to look for as a value in this {@code Hashtable}. + * @return {@code true} if object is a value in this {@code Hashtable}, + * {@code false} otherwise. + * @see #containsKey + * @see java.lang.Object#equals + */ + public boolean contains(Object value) { + return containsValue(value); + } + + /** + * Associate the specified value with the specified key in this + * {@code Hashtable}. If the key already exists, the old value is replaced. + * The key and value cannot be null. + * + * @param key + * the key to add. + * @param value + * the value to add. + * @return the old value associated with the specified key, or {@code null} + * if the key did not exist. + * @see #elements + * @see #get * @see #keys - * @see #size - * @see Enumeration + * @see java.lang.Object#equals */ - @Override - @SuppressWarnings("unchecked") - public synchronized Enumeration<V> elements() { - if (elementCount == 0) { - return (Enumeration<V>) EMPTY_ENUMERATION; + public synchronized V put(K key, V value) { + if (value == null) { + throw new NullPointerException(); } - return new HashEnumIterator<V>(new MapEntry.Type<V, K, V>() { - public V get(MapEntry<K, V> entry) { - return entry.value; + int hash = secondaryHash(key.hashCode()); + HashtableEntry<K, V>[] tab = table; + int index = hash & (tab.length - 1); + HashtableEntry<K, V> first = tab[index]; + for (HashtableEntry<K, V> e = first; e != null; e = e.next) { + if (e.hash == hash && key.equals(e.key)) { + V oldValue = e.value; + e.value = value; + return oldValue; } - }, true); + } + + // No entry for key is present; create one + modCount++; + if (size++ > threshold) { + rehash(); // Does nothing!! + tab = doubleCapacity(); + index = hash & (tab.length - 1); + first = tab[index]; + } + tab[index] = new HashtableEntry<K, V>(key, value, hash, first); + return null; } /** - * Returns a set of the mappings contained in this {@code Hashtable}. Each - * element in the set is a {@link Map.Entry}. The set is backed by this - * {@code Hashtable} so changes to one are reflected by the other. The set - * does not support adding. + * This method is just like put, except that it doesn't do things that + * are inappropriate or unnecessary for constructors and pseudo-constructors + * (i.e., clone, readObject). In particular, this method does not check to + * ensure that capacity is sufficient, and does not increment modCount. + */ + private void constructorPut(K key, V value) { + if (value == null) { + throw new NullPointerException(); + } + int hash = secondaryHash(key.hashCode()); + HashtableEntry<K, V>[] tab = table; + int index = hash & (tab.length - 1); + HashtableEntry<K, V> first = tab[index]; + for (HashtableEntry<K, V> e = first; e != null; e = e.next) { + if (e.hash == hash && key.equals(e.key)) { + e.value = value; + return; + } + } + + // No entry for key is present; create one + tab[index] = new HashtableEntry<K, V>(key, value, hash, first); + size++; + } + + /** + * Copies every mapping to this {@code Hashtable} from the specified map. * - * @return a set of the mappings. + * @param map + * the map to copy mappings from. */ - public Set<Map.Entry<K, V>> entrySet() { - return new Collections.SynchronizedSet<Map.Entry<K, V>>( - new AbstractSet<Map.Entry<K, V>>() { - @Override - public int size() { - return elementCount; - } - - @Override - public void clear() { - Hashtable.this.clear(); - } - - @Override - @SuppressWarnings("unchecked") - public boolean remove(Object object) { - if (contains(object)) { - Hashtable.this.remove(((Map.Entry<K, V>) object) - .getKey()); - return true; - } - return false; - } - - @Override - @SuppressWarnings("unchecked") - public boolean contains(Object object) { - Entry<K, V> entry = getEntry(((Map.Entry<K, V>) object) - .getKey()); - return object.equals(entry); - } - - @Override - public Iterator<Map.Entry<K, V>> iterator() { - return new HashIterator<Map.Entry<K, V>>( - new MapEntry.Type<Map.Entry<K, V>, K, V>() { - public Map.Entry<K, V> get( - MapEntry<K, V> entry) { - return entry; - } - }); - } - }, this); + public synchronized void putAll(Map<? extends K, ? extends V> map) { + ensureCapacity(map.size()); + for (Entry<? extends K, ? extends V> e : map.entrySet()) { + put(e.getKey(), e.getValue()); + } } /** - * Compares this {@code Hashtable} with the specified object and indicates - * if they are equal. In order to be equal, {@code object} must be an - * instance of Map and contain the same key/value pairs. + * Ensures that the hash table has sufficient capacity to store the + * specified number of mappings, with room to grow. If not, it increases the + * capacity as appropriate. Like doubleCapacity, this method moves existing + * entries to new buckets as appropriate. Unlike doubleCapacity, this method + * can grow the table by factors of 2^n for n > 1. Hopefully, a single call + * to this method will be faster than multiple calls to doubleCapacity. * - * @param object - * the object to compare with this object. - * @return {@code true} if the specified object is equal to this Map, - * {@code false} otherwise. - * @see #hashCode + * <p>This method is called only by putAll. */ - @Override - public synchronized boolean equals(Object object) { - if (this == object) { - return true; + private void ensureCapacity(int numMappings) { + int newCapacity = roundUpToPowerOfTwo(capacityForInitSize(numMappings)); + HashtableEntry<K, V>[] oldTable = table; + int oldCapacity = oldTable.length; + if (newCapacity <= oldCapacity) { + return; } - if (object instanceof Map) { - Map<?, ?> map = (Map<?, ?>) object; - if (size() != map.size()) { - return false; + + rehash(); // Does nothing!! + + if (newCapacity == oldCapacity << 1) { + doubleCapacity(); + return; + } + + // We're growing by at least 4x, rehash in the obvious way + HashtableEntry<K, V>[] newTable = makeTable(newCapacity); + if (size != 0) { + int newMask = newCapacity - 1; + for (int i = 0; i < oldCapacity; i++) { + for (HashtableEntry<K, V> e = oldTable[i]; e != null;) { + HashtableEntry<K, V> oldNext = e.next; + int newIndex = e.hash & newMask; + HashtableEntry<K, V> newNext = newTable[newIndex]; + newTable[newIndex] = e; + e.next = newNext; + e = oldNext; + } } + } + } + + /** + * Increases the capacity of this {@code Hashtable}. This method is called + * when the size of this {@code Hashtable} exceeds the load factor. + */ + protected void rehash() { + /* + * This method has no testable semantics, other than that it gets + * called from time to time. + */ + } + + /** + * Allocate a table of the given capacity and set the threshold accordingly. + * @param newCapacity must be a power of two + */ + private HashtableEntry<K, V>[] makeTable(int newCapacity) { + @SuppressWarnings("unchecked") HashtableEntry<K, V>[] newTable + = (HashtableEntry<K, V>[]) new HashtableEntry[newCapacity]; + table = newTable; + threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity + return newTable; + } + + /** + * Doubles the capacity of the hash table. Existing entries are placed in + * the correct bucket on the enlarged table. If the current capacity is, + * MAXIMUM_CAPACITY, this method is a no-op. Returns the table, which + * will be new unless we were already at MAXIMUM_CAPACITY. + */ + private HashtableEntry<K, V>[] doubleCapacity() { + HashtableEntry<K, V>[] oldTable = table; + int oldCapacity = oldTable.length; + if (oldCapacity == MAXIMUM_CAPACITY) { + return oldTable; + } + int newCapacity = oldCapacity << 1; + HashtableEntry<K, V>[] newTable = makeTable(newCapacity); + if (size == 0) { + return newTable; + } - Set<Map.Entry<K, V>> entries = entrySet(); - for (Map.Entry<?, ?> e : map.entrySet()) { - if (!entries.contains(e)) { - return false; + for (int j = 0; j < oldCapacity; j++) { + /* + * Rehash the bucket using the minimum number of field writes. + * This is the most subtle and delicate code in the class. + */ + HashtableEntry<K, V> e = oldTable[j]; + if (e == null) { + continue; + } + int highBit = e.hash & oldCapacity; + HashtableEntry<K, V> broken = null; + newTable[j | highBit] = e; + for (HashtableEntry<K,V> n = e.next; n != null; e = n, n = n.next) { + int nextHighBit = n.hash & oldCapacity; + if (nextHighBit != highBit) { + if (broken == null) + newTable[j | nextHighBit] = n; + else + broken.next = n; + broken = e; + highBit = nextHighBit; } } - return true; + if (broken != null) + broken.next = null; } - return false; + return newTable; } /** - * Returns the value associated with the specified key in this + * Removes the key/value pair with the specified key from this * {@code Hashtable}. * * @param key - * the key of the value returned. + * the key to remove. * @return the value associated with the specified key, or {@code null} if - * the specified key does not exist. + * the specified key did not exist. + * @see #get * @see #put */ - @Override - public synchronized V get(Object key) { - int hash = key.hashCode(); - int index = (hash & 0x7FFFFFFF) % elementData.length; - Entry<K, V> entry = elementData[index]; - while (entry != null) { - if (entry.equalsKey(key, hash)) { - return entry.value; + public synchronized V remove(Object key) { + int hash = secondaryHash(key.hashCode()); + HashtableEntry<K, V>[] tab = table; + int index = hash & (tab.length - 1); + for (HashtableEntry<K, V> e = tab[index], prev = null; + e != null; prev = e, e = e.next) { + if (e.hash == hash && key.equals(e.key)) { + if (prev == null) { + tab[index] = e.next; + } else { + prev.next = e.next; + } + modCount++; + size--; + return e.value; } - entry = entry.next; } return null; } - Entry<K, V> getEntry(Object key) { - int hash = key.hashCode(); - int index = (hash & 0x7FFFFFFF) % elementData.length; - Entry<K, V> entry = elementData[index]; - while (entry != null) { - if (entry.equalsKey(key, hash)) { - return entry; - } - entry = entry.next; + /** + * Removes all key/value pairs from this {@code Hashtable}, leaving the + * size zero and the capacity unchanged. + * + * @see #isEmpty + * @see #size + */ + public synchronized void clear() { + if (size != 0) { + Arrays.fill(table, null); + modCount++; + size = 0; } - return null; } - @Override - public synchronized int hashCode() { - int result = 0; - Iterator<Map.Entry<K, V>> it = entrySet().iterator(); - while (it.hasNext()) { - Map.Entry<K, V> entry = it.next(); - Object key = entry.getKey(); - if (key == this) { - continue; - } - Object value = entry.getValue(); - if (value == this) { - continue; - } - int hash = (key != null ? key.hashCode() : 0) - ^ (value != null ? value.hashCode() : 0); - result += hash; - } - return result; + /** + * Returns a set of the keys contained in this {@code Hashtable}. The set + * is backed by this {@code Hashtable} so changes to one are reflected by + * the other. The set does not support adding. + * + * @return a set of the keys. + */ + public synchronized Set<K> keySet() { + Set<K> ks = keySet; + return (ks != null) ? ks : (keySet = new KeySet()); } /** - * Returns true if this {@code Hashtable} has no key/value pairs. + * Returns a collection of the values contained in this {@code Hashtable}. + * The collection is backed by this {@code Hashtable} so changes to one are + * reflected by the other. The collection does not support adding. * - * @return {@code true} if this {@code Hashtable} has no key/value pairs, - * {@code false} otherwise. - * @see #size + * @return a collection of the values. */ - @Override - public synchronized boolean isEmpty() { - return elementCount == 0; + public synchronized Collection<V> values() { + Collection<V> vs = values; + return (vs != null) ? vs : (values = new Values()); } /** + * Returns a set of the mappings contained in this {@code Hashtable}. Each + * element in the set is a {@link Map.Entry}. The set is backed by this + * {@code Hashtable} so changes to one are reflected by the other. The set + * does not support adding. + * + * @return a set of the mappings. + */ + public synchronized Set<Entry<K, V>> entrySet() { + Set<Entry<K, V>> es = entrySet; + return (es != null) ? es : (entrySet = new EntrySet()); + } + + + /** * Returns an enumeration on the keys of this {@code Hashtable} instance. * The results of the enumeration may be affected if the contents of this * {@code Hashtable} are modified. @@ -583,400 +644,517 @@ public class Hashtable<K, V> extends Dictionary<K, V> implements Map<K, V>, * @see #size * @see Enumeration */ - @Override - @SuppressWarnings("unchecked") public synchronized Enumeration<K> keys() { - if (elementCount == 0) { - return (Enumeration<K>) EMPTY_ENUMERATION; - } - return new HashEnumIterator<K>(new MapEntry.Type<K, K, V>() { - public K get(MapEntry<K, V> entry) { - return entry.key; - } - }, true); + return new KeyEnumeration(); } /** - * Returns a set of the keys contained in this {@code Hashtable}. The set - * is backed by this {@code Hashtable} so changes to one are reflected by - * the other. The set does not support adding. + * Returns an enumeration on the values of this {@code Hashtable}. The + * results of the Enumeration may be affected if the contents of this + * {@code Hashtable} are modified. * - * @return a set of the keys. + * @return an enumeration of the values of this {@code Hashtable}. + * @see #keys + * @see #size + * @see Enumeration */ - public Set<K> keySet() { - return new Collections.SynchronizedSet<K>(new AbstractSet<K>() { - @Override - public boolean contains(Object object) { - return containsKey(object); - } + public synchronized Enumeration<V> elements() { + return new ValueEnumeration(); + } - @Override - public int size() { - return elementCount; - } + /** + * Note: technically the methods of this class should synchronize the + * backing map. However, this would require them to have a reference + * to it, which would cause consiserable bloat. Moreover, the RI + * behaves the same way. + */ + private static class HashtableEntry<K, V> implements Entry<K, V> { + final K key; + V value; + final int hash; + HashtableEntry<K, V> next; + + HashtableEntry(K key, V value, int hash, HashtableEntry<K, V> next) { + this.key = key; + this.value = value; + this.hash = hash; + this.next = next; + } - @Override - public void clear() { - Hashtable.this.clear(); - } + public final K getKey() { + return key; + } - @Override - public boolean remove(Object key) { - if (containsKey(key)) { - Hashtable.this.remove(key); - return true; - } - return false; - } + public final V getValue() { + return value; + } - @Override - public Iterator<K> iterator() { - if (this.size() == 0) { - return (Iterator<K>) EMPTY_ITERATOR; - } - return new HashEnumIterator<K>(new MapEntry.Type<K, K, V>() { - public K get(MapEntry<K, V> entry) { - return entry.key; - } - }); + public final V setValue(V value) { + if (value == null) { + throw new NullPointerException(); } - }, this); - } - - class HashEnumIterator<E> extends HashIterator<E> implements Enumeration<E> { - - private boolean isEnumeration = false; - - int start; + V oldValue = this.value; + this.value = value; + return oldValue; + } - Entry<K, V> entry; + @Override public final boolean equals(Object o) { + if (!(o instanceof Entry)) { + return false; + } + Entry<?, ?> e = (Entry<?, ?>) o; + return key.equals(e.getKey()) && value.equals(e.getValue()); + } - HashEnumIterator(MapEntry.Type<E, K, V> value) { - super(value); + @Override public final int hashCode() { + return key.hashCode() ^ value.hashCode(); } - HashEnumIterator(MapEntry.Type<E, K, V> value, boolean isEnumeration) { - super(value); - this.isEnumeration = isEnumeration; - start = lastSlot + 1; + @Override public final String toString() { + return key + "=" + value; } + } - public boolean hasMoreElements() { - if (isEnumeration) { - if (entry != null) { - return true; - } - while (start > firstSlot) { - if (elementData[--start] != null) { - entry = elementData[start]; - return true; - } - } - return false; + private abstract class HashIterator { + int nextIndex; + HashtableEntry<K, V> nextEntry; + HashtableEntry<K, V> lastEntryReturned; + int expectedModCount = modCount; + + HashIterator() { + HashtableEntry<K, V>[] tab = table; + HashtableEntry<K, V> next = null; + while (next == null && nextIndex < tab.length) { + next = tab[nextIndex++]; } - // iterator - return super.hasNext(); + nextEntry = next; } public boolean hasNext() { - if (isEnumeration) { - return hasMoreElements(); - } - // iterator - return super.hasNext(); + return nextEntry != null; } - public E next() { - if (isEnumeration) { - if (expectedModCount == modCount) { - return nextElement(); - } else { - throw new ConcurrentModificationException(); - } + HashtableEntry<K, V> nextEntry() { + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + if (nextEntry == null) + throw new NoSuchElementException(); + + HashtableEntry<K, V> entryToReturn = nextEntry; + HashtableEntry<K, V>[] tab = table; + HashtableEntry<K, V> next = entryToReturn.next; + while (next == null && nextIndex < tab.length) { + next = tab[nextIndex++]; } - // iterator - return super.next(); + nextEntry = next; + return lastEntryReturned = entryToReturn; } - @SuppressWarnings("unchecked") - public E nextElement() { - if (isEnumeration) { - if (hasMoreElements()) { - Object result = type.get(entry); - entry = entry.next; - return (E) result; - } + HashtableEntry<K, V> nextEntryNotFailFast() { + if (nextEntry == null) throw new NoSuchElementException(); + + HashtableEntry<K, V> entryToReturn = nextEntry; + HashtableEntry<K, V>[] tab = table; + HashtableEntry<K, V> next = entryToReturn.next; + while (next == null && nextIndex < tab.length) { + next = tab[nextIndex++]; } - // iterator - return super.next(); + nextEntry = next; + return lastEntryReturned = entryToReturn; } public void remove() { - if (isEnumeration) { - throw new UnsupportedOperationException(); - } else { - super.remove(); - } + if (lastEntryReturned == null) + throw new IllegalStateException(); + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + Hashtable.this.remove(lastEntryReturned.key); + lastEntryReturned = null; + expectedModCount = modCount; } } - /** - * Associate the specified value with the specified key in this - * {@code Hashtable}. If the key already exists, the old value is replaced. - * The key and value cannot be null. - * - * @param key - * the key to add. - * @param value - * the value to add. - * @return the old value associated with the specified key, or {@code null} - * if the key did not exist. - * @see #elements - * @see #get - * @see #keys - * @see java.lang.Object#equals - */ - @Override - public synchronized V put(K key, V value) { - if (key != null && value != null) { - int hash = key.hashCode(); - int index = (hash & 0x7FFFFFFF) % elementData.length; - Entry<K, V> entry = elementData[index]; - while (entry != null && !entry.equalsKey(key, hash)) { - entry = entry.next; - } - if (entry == null) { - modCount++; - if (++elementCount > threshold) { - rehash(); - index = (hash & 0x7FFFFFFF) % elementData.length; - } - if (index < firstSlot) { - firstSlot = index; - } - if (index > lastSlot) { - lastSlot = index; - } - entry = newEntry(key, value, hash); - entry.next = elementData[index]; - elementData[index] = entry; - return null; - } - V result = entry.value; - entry.value = value; - return result; - } - throw new NullPointerException(); + private final class KeyIterator extends HashIterator + implements Iterator<K> { + public K next() { return nextEntry().key; } + } + + private final class ValueIterator extends HashIterator + implements Iterator<V> { + public V next() { return nextEntry().value; } + } + + private final class EntryIterator extends HashIterator + implements Iterator<Entry<K, V>> { + public Entry<K, V> next() { return nextEntry(); } + } + + private final class KeyEnumeration extends HashIterator + implements Enumeration<K> { + public boolean hasMoreElements() { return hasNext(); } + public K nextElement() { return nextEntryNotFailFast().key; } + } + + private final class ValueEnumeration extends HashIterator + implements Enumeration<V> { + public boolean hasMoreElements() { return hasNext(); } + public V nextElement() { return nextEntryNotFailFast().value; } } /** - * Copies every mapping to this {@code Hashtable} from the specified map. - * - * @param map - * the map to copy mappings from. + * Returns true if this map contains the specified mapping. */ - public synchronized void putAll(Map<? extends K, ? extends V> map) { - for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { - put(entry.getKey(), entry.getValue()); + private synchronized boolean containsMapping(Object key, Object value) { + int hash = secondaryHash(key.hashCode()); + HashtableEntry<K, V>[] tab = table; + int index = hash & (tab.length - 1); + for (HashtableEntry<K, V> e = tab[index]; e != null; e = e.next) { + if (e.hash == hash && e.key.equals(key)) { + return e.value.equals(value); + } } + return false; // No entry for key } /** - * Increases the capacity of this {@code Hashtable}. This method is called - * when the size of this {@code Hashtable} exceeds the load factor. + * Removes the mapping from key to value and returns true if this mapping + * exists; otherwise, returns does nothing and returns false. */ - protected void rehash() { - int length = (elementData.length << 1) + 1; - if (length == 0) { - length = 1; - } - int newFirst = length; - int newLast = -1; - Entry<K, V>[] newData = newElementArray(length); - for (int i = lastSlot + 1; --i >= firstSlot;) { - Entry<K, V> entry = elementData[i]; - while (entry != null) { - int index = (entry.getKeyHash() & 0x7FFFFFFF) % length; - if (index < newFirst) { - newFirst = index; + private synchronized boolean removeMapping(Object key, Object value) { + int hash = secondaryHash(key.hashCode()); + HashtableEntry<K, V>[] tab = table; + int index = hash & (tab.length - 1); + for (HashtableEntry<K, V> e = tab[index], prev = null; + e != null; prev = e, e = e.next) { + if (e.hash == hash && e.key.equals(key)) { + if (!e.value.equals(value)) { + return false; // Map has wrong value for key } - if (index > newLast) { - newLast = index; + if (prev == null) { + tab[index] = e.next; + } else { + prev.next = e.next; } - Entry<K, V> next = entry.next; - entry.next = newData[index]; - newData[index] = entry; - entry = next; + modCount++; + size--; + return true; } } - firstSlot = newFirst; - lastSlot = newLast; - elementData = newData; - computeMaxSize(); + return false; // No entry for key } /** - * Removes the key/value pair with the specified key from this - * {@code Hashtable}. + * Compares this {@code Hashtable} with the specified object and indicates + * if they are equal. In order to be equal, {@code object} must be an + * instance of Map and contain the same key/value pairs. * - * @param key - * the key to remove. - * @return the value associated with the specified key, or {@code null} if - * the specified key did not exist. - * @see #get - * @see #put + * @param object + * the object to compare with this object. + * @return {@code true} if the specified object is equal to this Map, + * {@code false} otherwise. + * @see #hashCode */ - @Override - public synchronized V remove(Object key) { - int hash = key.hashCode(); - int index = (hash & 0x7FFFFFFF) % elementData.length; - Entry<K, V> last = null; - Entry<K, V> entry = elementData[index]; - while (entry != null && !entry.equalsKey(key, hash)) { - last = entry; - entry = entry.next; - } - if (entry != null) { - modCount++; - if (last == null) { - elementData[index] = entry.next; - } else { - last.next = entry.next; + @Override public synchronized boolean equals(Object object) { + return (object instanceof Map) && + entrySet().equals(((Map<?, ?>)object).entrySet()); + } + + @Override public synchronized int hashCode() { + int result = 0; + for (Entry<K, V> e : entrySet()) { + K key = e.getKey(); + V value = e.getValue(); + if (key == this || value == this) { + continue; } - elementCount--; - V result = entry.value; - entry.value = null; - return result; + result += (key != null ? key.hashCode() : 0) + ^ (value != null ? value.hashCode() : 0); } - return null; + return result; } /** - * Returns the number of key/value pairs in this {@code Hashtable}. - * - * @return the number of key/value pairs in this {@code Hashtable}. - * @see #elements - * @see #keys + * A rough estimate of the number of characters per entry, for use + * when creating a string buffer in the toString method. */ - @Override - public synchronized int size() { - return elementCount; - } + private static final int CHARS_PER_ENTRY = 15; /** * Returns the string representation of this {@code Hashtable}. * * @return the string representation of this {@code Hashtable}. */ - @Override - public synchronized String toString() { - if (isEmpty()) { - return "{}"; //$NON-NLS-1$ + @Override public synchronized String toString() { + StringBuilder result = new StringBuilder(CHARS_PER_ENTRY * size); + result.append('{'); + Iterator<Entry<K, V>> i = entrySet().iterator(); + boolean hasMore = i.hasNext(); + while (hasMore) { + Entry<K, V> entry = i.next(); + + K key = entry.getKey(); + result.append(key == this ? "(this Map)" : key.toString()); + + result.append('='); + + V value = entry.getValue(); + result.append(value == this ? "(this Map)" : value.toString()); + + if (hasMore = i.hasNext()) { + result.append(", "); + } } - StringBuilder buffer = new StringBuilder(size() * 28); - buffer.append('{'); - for (int i = lastSlot; i >= firstSlot; i--) { - Entry<K, V> entry = elementData[i]; - while (entry != null) { - if (entry.key != this) { - buffer.append(entry.key); - } else { - // luni.04=this Map - buffer.append("(" + Messages.getString("luni.04") + ")"); //$NON-NLS-1$//$NON-NLS-2$//$NON-NLS-3$ - } - buffer.append('='); - if (entry.value != this) { - buffer.append(entry.value); - } else { - // luni.04=this Map - buffer.append("(" + Messages.getString("luni.04") + ")"); //$NON-NLS-1$//$NON-NLS-2$//$NON-NLS-3$ - } - buffer.append(", "); //$NON-NLS-1$ - entry = entry.next; + result.append('}'); + return result.toString(); + } + + private final class KeySet extends AbstractSet<K> { + public Iterator<K> iterator() { + return new KeyIterator(); + } + public int size() { + return Hashtable.this.size(); + } + public boolean contains(Object o) { + return containsKey(o); + } + public boolean remove(Object o) { + synchronized (Hashtable.this) { + int oldSize = size; + Hashtable.this.remove(o); + return size != oldSize; + } + } + public void clear() { + Hashtable.this.clear(); + } + public boolean removeAll(Collection<?> collection) { + synchronized (Hashtable.this) { + return super.removeAll(collection); + } + } + public boolean retainAll(Collection<?> collection) { + synchronized (Hashtable.this) { + return super.retainAll(collection); + } + } + public boolean containsAll(Collection<?> collection) { + synchronized (Hashtable.this) { + return super.containsAll(collection); } } - // Remove the last ", " - if (elementCount > 0) { - buffer.setLength(buffer.length() - 2); + public boolean equals(Object object) { + synchronized (Hashtable.this) { + return super.equals(object); + } + } + public int hashCode() { + synchronized (Hashtable.this) { + return super.hashCode(); + } + } + public String toString() { + synchronized (Hashtable.this) { + return super.toString(); + } + } + public Object[] toArray() { + synchronized (Hashtable.this) { + return super.toArray(); + } + } + public <T> T[] toArray(T[] a) { + synchronized (Hashtable.this) { + return super.toArray(a); + } + } + } + + private final class Values extends AbstractCollection<V> { + public Iterator<V> iterator() { + return new ValueIterator(); + } + public int size() { + return Hashtable.this.size(); + } + public boolean contains(Object o) { + return containsValue(o); + } + public void clear() { + Hashtable.this.clear(); + } + public boolean containsAll(Collection<?> collection) { + synchronized (Hashtable.this) { + return super.containsAll(collection); + } + } + public String toString() { + synchronized (Hashtable.this) { + return super.toString(); + } + } + public Object[] toArray() { + synchronized (Hashtable.this) { + return super.toArray(); + } + } + public <T> T[] toArray(T[] a) { + synchronized (Hashtable.this) { + return super.toArray(a); + } + } + } + + private final class EntrySet extends AbstractSet<Entry<K, V>> { + public Iterator<Entry<K, V>> iterator() { + return new EntryIterator(); + } + public boolean contains(Object o) { + if (!(o instanceof Entry)) + return false; + Entry<?, ?> e = (Entry<?, ?>) o; + return containsMapping(e.getKey(), e.getValue()); + } + public boolean remove(Object o) { + if (!(o instanceof Entry)) + return false; + Entry<?, ?> e = (Entry<?, ?>)o; + return removeMapping(e.getKey(), e.getValue()); + } + public int size() { + return Hashtable.this.size(); + } + public void clear() { + Hashtable.this.clear(); + } + public boolean removeAll(Collection<?> collection) { + synchronized (Hashtable.this) { + return super.removeAll(collection); + } + } + public boolean retainAll(Collection<?> collection) { + synchronized (Hashtable.this) { + return super.retainAll(collection); + } + } + public boolean containsAll(Collection<?> collection) { + synchronized (Hashtable.this) { + return super.containsAll(collection); + } + } + public boolean equals(Object object) { + synchronized (Hashtable.this) { + return super.equals(object); + } + } + public int hashCode() { + return Hashtable.this.hashCode(); + } + public String toString() { + synchronized (Hashtable.this) { + return super.toString(); + } + } + public Object[] toArray() { + synchronized (Hashtable.this) { + return super.toArray(); + } + } + public <T> T[] toArray(T[] a) { + synchronized (Hashtable.this) { + return super.toArray(a); + } } - buffer.append('}'); - return buffer.toString(); } /** - * Returns a collection of the values contained in this {@code Hashtable}. - * The collection is backed by this {@code Hashtable} so changes to one are - * reflected by the other. The collection does not support adding. - * - * @return a collection of the values. + * Applies a supplemental hash function to a given hashCode, which defends + * against poor quality hash functions. This is critical because Hashtable + * uses power-of-two length hash tables, that otherwise encounter collisions + * for hashCodes that do not differ in lower or upper bits. + */ + private static int secondaryHash(int h) { + // Doug Lea's supplemental hash function + h ^= (h >>> 20) ^ (h >>> 12); + return h ^ (h >>> 7) ^ (h >>> 4); + } + + /** + * Returns the smallest power of two >= its argument, with several caveats: + * If the argument is negative but not Integer.MIN_VALUE, the method returns + * zero. If the argument is > 2^30 or equal to Integer.MIN_VALUE, the method + * returns Integer.MIN_VALUE. If the argument is zero, the method returns + * zero. */ - public Collection<V> values() { - return new Collections.SynchronizedCollection<V>( - new AbstractCollection<V>() { - @Override - public boolean contains(Object object) { - return Hashtable.this.contains(object); - } - - @Override - public int size() { - return elementCount; - } - - @Override - public void clear() { - Hashtable.this.clear(); - } - - @Override - public Iterator<V> iterator() { - return new HashIterator<V>( - new MapEntry.Type<V, K, V>() { - public V get(MapEntry<K, V> entry) { - return entry.value; - } - }); - } - }, this); + private static int roundUpToPowerOfTwo(int i) { + i--; // If input is a power of two, shift its high-order bit right + + // "Smear" the high-order bit all the way to the right + i |= i >>> 1; + i |= i >>> 2; + i |= i >>> 4; + i |= i >>> 8; + i |= i >>> 16; + + return i + 1; } + private static final long serialVersionUID = 1421746759512286392L; + + /** + * Serializable fields. + * + * @serialField loadFactor float + * load factor for this Hashtable + */ + private static final ObjectStreamField[] serialPersistentFields = { + new ObjectStreamField("threshold", Integer.TYPE), + new ObjectStreamField("loadFactor", Float.TYPE) + }; + private synchronized void writeObject(ObjectOutputStream stream) throws IOException { - stream.defaultWriteObject(); - stream.writeInt(elementData.length); - stream.writeInt(elementCount); - for (int i = elementData.length; --i >= 0;) { - Entry<K, V> entry = elementData[i]; - while (entry != null) { - stream.writeObject(entry.key); - stream.writeObject(entry.value); - entry = entry.next; - } + // Emulate loadFactor field for other implementations to read + ObjectOutputStream.PutField fields = stream.putFields(); + fields.put("threshold", (int) (DEFAULT_LOAD_FACTOR * table.length)); + fields.put("loadFactor", DEFAULT_LOAD_FACTOR); + stream.writeFields(); + + stream.writeInt(table.length); // Capacity + stream.writeInt(size); + for (Entry<K, V> e : entrySet()) { + stream.writeObject(e.getKey()); + stream.writeObject(e.getValue()); } } - @SuppressWarnings("unchecked") private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { stream.defaultReadObject(); - int length = stream.readInt(); - elementData = newElementArray(length); - elementCount = stream.readInt(); - for (int i = elementCount; --i >= 0;) { - Object key = stream.readObject(); - int hash = key.hashCode(); - int index = (hash & 0x7FFFFFFF) % length; - if (index < firstSlot) { - firstSlot = index; - } - if (index > lastSlot) { - lastSlot = index; - } - Entry<K, V> entry = newEntry((K) key, (V) stream.readObject(), hash); - entry.next = elementData[index]; - elementData[index] = entry; + int capacity = stream.readInt(); + if (capacity < 0) { + throw new InvalidObjectException("Capacity: " + capacity); + } + if (capacity < MINIMUM_CAPACITY) { + capacity = MINIMUM_CAPACITY; + } else if (capacity > MAXIMUM_CAPACITY) { + capacity = MAXIMUM_CAPACITY; + } else { + capacity = roundUpToPowerOfTwo(capacity); + } + makeTable(capacity); + + int size = stream.readInt(); + if (size < 0) { + throw new InvalidObjectException("Size: " + size); + } + + for (int i = 0; i < size; i++) { + @SuppressWarnings("unchecked") K key = (K) stream.readObject(); + @SuppressWarnings("unchecked") V val = (V) stream.readObject(); + constructorPut(key, val); } } } diff --git a/luni/src/main/java/java/util/LinkedHashMap.java b/luni/src/main/java/java/util/LinkedHashMap.java index ed526d8..4e2fb3c 100644 --- a/luni/src/main/java/java/util/LinkedHashMap.java +++ b/luni/src/main/java/java/util/LinkedHashMap.java @@ -1,10 +1,10 @@ /* * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with + * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at + * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * @@ -15,6 +15,10 @@ * limitations under the License. */ +// BEGIN android-note +// Completely different implementation from harmony. Runs much faster. +// BEGIN android-note + package java.util; /** @@ -45,69 +49,68 @@ package java.util; * elements during iteration. It is not possible to guarantee that this * mechanism works in all cases of unsynchronized concurrent modification. It * should only be used for debugging purposes. - * - * @since 1.4 */ public class LinkedHashMap<K, V> extends HashMap<K, V> { - private static final long serialVersionUID = 3801124242820219131L; + /** + * A dummy entry in the circular linked list of entries in the map. + * The first real entry is header.nxt, and the last is header.prv. + * If the map is empty, header.nxt == header && header.prv == header. + */ + private transient LinkedEntry<K, V> header; + /** + * True if access ordered, false if insertion ordered. + */ private final boolean accessOrder; - transient private LinkedHashMapEntry<K, V> head, tail; - /** * Constructs a new empty {@code LinkedHashMap} instance. */ public LinkedHashMap() { super(); + init(); accessOrder = false; - head = null; } /** * Constructs a new {@code LinkedHashMap} instance with the specified * capacity. * - * @param s + * @param initialCapacity * the initial capacity of this map. - * @throws IllegalArgumentException - * if the capacity is less than zero. + * @exception IllegalArgumentException + * when the capacity is less than zero. */ - public LinkedHashMap(int s) { - super(s); - accessOrder = false; - head = null; + public LinkedHashMap(int initialCapacity) { + this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * Constructs a new {@code LinkedHashMap} instance with the specified * capacity and load factor. * - * @param s + * @param initialCapacity * the initial capacity of this map. - * @param lf + * @param loadFactor * the initial load factor. * @throws IllegalArgumentException * when the capacity is less than zero or the load factor is * less or equal to zero. */ - public LinkedHashMap(int s, float lf) { - super(s, lf); - accessOrder = false; - head = null; - tail = null; + public LinkedHashMap(int initialCapacity, float loadFactor) { + this(initialCapacity, loadFactor, false); } /** * Constructs a new {@code LinkedHashMap} instance with the specified * capacity, load factor and a flag specifying the ordering behavior. * - * @param s + * @param initialCapacity * the initial capacity of this hash map. - * @param lf + * @param loadFactor * the initial load factor. - * @param order + * @param accessOrder * {@code true} if the ordering should be done based on the last * access (from least-recently accessed to most-recently * accessed), and {@code false} if the ordering should be the @@ -116,197 +119,75 @@ public class LinkedHashMap<K, V> extends HashMap<K, V> { * when the capacity is less than zero or the load factor is * less or equal to zero. */ - public LinkedHashMap(int s, float lf, boolean order) { - super(s, lf); - accessOrder = order; - head = null; - tail = null; + public LinkedHashMap( + int initialCapacity, float loadFactor, boolean accessOrder) { + super(initialCapacity, loadFactor); + init(); + this.accessOrder = accessOrder; } /** * Constructs a new {@code LinkedHashMap} instance containing the mappings * from the specified map. The order of the elements is preserved. * - * @param m + * @param map * the mappings to add. */ - public LinkedHashMap(Map<? extends K, ? extends V> m) { - accessOrder = false; - head = null; - tail = null; - putAll(m); + public LinkedHashMap(Map<? extends K, ? extends V> map) { + this(capacityForInitSize(map.size())); + constructorPutAll(map); } - private static class AbstractMapIterator<K, V> { - int expectedModCount; - LinkedHashMapEntry<K, V> futureEntry; - LinkedHashMapEntry<K, V> currentEntry; - final LinkedHashMap<K, V> associatedMap; - - AbstractMapIterator(LinkedHashMap<K, V> map) { - expectedModCount = map.modCount; - futureEntry = map.head; - associatedMap = map; - } - - public boolean hasNext() { - return (futureEntry != null); - } - - final void checkConcurrentMod() throws ConcurrentModificationException { - if (expectedModCount != associatedMap.modCount) { - throw new ConcurrentModificationException(); - } - } - - final void makeNext() { - checkConcurrentMod(); - if (!hasNext()) { - throw new NoSuchElementException(); - } - currentEntry = futureEntry; - futureEntry = futureEntry.chainForward; - } - - public void remove() { - checkConcurrentMod(); - if (currentEntry==null) { - throw new IllegalStateException(); - } - associatedMap.removeEntry(currentEntry); - LinkedHashMapEntry<K, V> lhme = currentEntry; - LinkedHashMapEntry<K, V> p = lhme.chainBackward; - LinkedHashMapEntry<K, V> n = lhme.chainForward; - LinkedHashMap<K, V> lhm = associatedMap; - if (p != null) { - p.chainForward = n; - if (n != null) { - n.chainBackward = p; - } else { - lhm.tail = p; - } - } else { - lhm.head = n; - if (n != null) { - n.chainBackward = null; - } else { - lhm.tail = null; - } - } - currentEntry = null; - expectedModCount++; - } + @Override void init(){ + header = new LinkedEntry<K, V>(null, null, 0, null, null, null); + header.nxt = header.prv = header; } - private static class EntryIterator <K, V> extends AbstractMapIterator<K, V> implements Iterator<Map.Entry<K, V>> { - - EntryIterator (LinkedHashMap<K, V> map) { - super(map); - } - - public Map.Entry<K, V> next() { - makeNext(); - return currentEntry; - } - } - - private static class KeyIterator <K, V> extends AbstractMapIterator<K, V> implements Iterator<K> { - - KeyIterator (LinkedHashMap<K, V> map) { - super(map); - } - - public K next() { - makeNext(); - return currentEntry.key; - } - } - - private static class ValueIterator <K, V> extends AbstractMapIterator<K, V> implements Iterator<V> { - - ValueIterator (LinkedHashMap<K, V> map) { - super(map); - } - - public V next() { - makeNext(); - return currentEntry.value; - } - } - - static final class LinkedHashMapEntrySet<KT, VT> extends - HashMapEntrySet<KT, VT> { - public LinkedHashMapEntrySet(LinkedHashMap<KT, VT> lhm) { - super(lhm); - } - - @Override - public Iterator<Map.Entry<KT, VT>> iterator() { - return new EntryIterator<KT,VT>((LinkedHashMap<KT, VT>) hashMap()); - } - } - - static final class LinkedHashMapEntry<K, V> extends Entry<K, V> { - LinkedHashMapEntry<K, V> chainForward, chainBackward; - - LinkedHashMapEntry(K theKey, V theValue) { - super(theKey, theValue); - chainForward = null; - chainBackward = null; - } - - LinkedHashMapEntry(K theKey, int hash) { - super(theKey, hash); - chainForward = null; - chainBackward = null; - } + /** + * LinkedEntry adds nxt/prv double-links to plain HashMapEntry. + */ + static class LinkedEntry<K, V> extends HashMapEntry<K, V> { + LinkedEntry<K, V> nxt; + LinkedEntry<K, V> prv; - @Override - @SuppressWarnings("unchecked") - public Object clone() { - LinkedHashMapEntry<K, V> entry = (LinkedHashMapEntry<K, V>) super - .clone(); - entry.chainBackward = chainBackward; - entry.chainForward = chainForward; - LinkedHashMapEntry<K, V> lnext = (LinkedHashMapEntry<K, V>) entry.next; - if (lnext != null) { - entry.next = (LinkedHashMapEntry<K, V>) lnext.clone(); - } - return entry; + LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next, + LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) { + super(key, value, hash, next); + this.nxt = nxt; + this.prv = prv; } } - @Override - public boolean containsValue(Object value) { - LinkedHashMapEntry<K, V> entry = head; - if (null == value) { - while (null != entry) { - if (null == entry.value) { - return true; - } - entry = entry.chainForward; - } - } else { - while (null != entry) { - if (value.equals(entry.value)) { - return true; - } - entry = entry.chainForward; - } - } - return false; + /** + * Evicts eldest entry if instructed, creates a new entry and links it in + * as head of linked list. This method should call constructorNewEntry + * (instead of duplicating code) if the performance of your VM permits. + */ + @Override LinkedEntry<K, V> newEntry( + K key, V value, int hash, HashMapEntry<K, V> next) { + // Remove eldest entry if instructed to do so. + LinkedEntry<K, V> eldest = header.nxt; + if (eldest != header && removeEldestEntry(eldest)) + remove(eldest.key); + + // Create new entry and link it on to list + LinkedEntry<K, V> header = this.header; + LinkedEntry<K, V> oldTail = header.prv; + LinkedEntry<K, V> newTail + = new LinkedEntry<K,V>(key, value, hash, next, header, oldTail); + return oldTail.nxt = header.prv = newTail; } /** - * Create a new element array - * - * @param s - * @return Reference to the element array + * As above, but without eviction. */ - @Override - @SuppressWarnings("unchecked") - Entry<K, V>[] newElementArray(int s) { - return new LinkedHashMapEntry[s]; + @Override HashMapEntry<K, V> constructorNewEntry( + K key, V value, int hash, HashMapEntry<K, V> next) { + LinkedEntry<K, V> header = this.header; + LinkedEntry<K, V> oldTail = header.prv; + LinkedEntry<K, V> newTail + = new LinkedEntry<K,V>(key, value, hash, next, header, oldTail); + return oldTail.nxt = header.prv = newTail; } /** @@ -317,338 +198,167 @@ public class LinkedHashMap<K, V> extends HashMap<K, V> { * @return the value of the mapping with the specified key, or {@code null} * if no mapping for the specified key is found. */ - @Override - public V get(Object key) { - LinkedHashMapEntry<K, V> m; + @Override public V get(Object key) { + /* + * This method is overridden to eliminate the need for a polymorphic + * invocation in superclass at the expense of code duplication. + */ if (key == null) { - m = (LinkedHashMapEntry<K, V>) findNullKeyEntry(); - } else { - int hash = key.hashCode(); - int index = (hash & 0x7FFFFFFF) % elementData.length; - m = (LinkedHashMapEntry<K, V>) findNonNullKeyEntry(key, index, hash); - } - if (m == null) { - return null; - } - if (accessOrder && tail != m) { - // BEGIN android-added - modCount++; - // END android-added - LinkedHashMapEntry<K, V> p = m.chainBackward; - LinkedHashMapEntry<K, V> n = m.chainForward; - n.chainBackward = p; - if (p != null) { - p.chainForward = n; - } else { - head = n; + HashMapEntry<K, V> e = entryForNullKey; + if (e == null) + return null; + if (accessOrder) + makeTail((LinkedEntry<K, V>) e); + return e.value; + } + + // Doug Lea's supplemental secondaryHash function (inlined) + int hash = key.hashCode(); + hash ^= (hash >>> 20) ^ (hash >>> 12); + hash ^= (hash >>> 7) ^ (hash >>> 4); + + HashMapEntry<K, V>[] tab = table; + for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)]; + e != null; e = e.next) { + K eKey = e.key; + if (eKey == key || (e.hash == hash && key.equals(eKey))) { + if (accessOrder) + makeTail((LinkedEntry<K, V>) e); + return e.value; } - m.chainForward = null; - m.chainBackward = tail; - tail.chainForward = m; - tail = m; } - return m.value; - } - - /* - * @param key @param index @return Entry - */ - @Override - Entry<K, V> createEntry(K key, int index, V value) { - LinkedHashMapEntry<K, V> m = new LinkedHashMapEntry<K, V>(key, value); - m.next = elementData[index]; - elementData[index] = m; - linkEntry(m); - return m; - } - - Entry<K, V> createHashedEntry(K key, int index, int hash) { - LinkedHashMapEntry<K, V> m = new LinkedHashMapEntry<K, V>(key, hash); - m.next = elementData[index]; - elementData[index] = m; - linkEntry(m); - return m; + return null; } /** - * Maps the specified key to the specified value. - * - * @param key - * the key. - * @param value - * the value. - * @return the value of any previous mapping with the specified key or - * {@code null} if there was no such mapping. + * Relinks the given entry to the tail of the list. Under access ordering, + * this method is invoked whenever the value of a pre-existing entry is + * read by Map.get or modified by Map.put. */ - @Override - public V put(K key, V value) { - V result = putImpl(key, value); - - if (removeEldestEntry(head)) { - remove(head.key); - } - - return result; + private void makeTail(LinkedEntry<K, V> e) { + // Unlink e + e.prv.nxt = e.nxt; + e.nxt.prv = e.prv; + + // Relink e as tail + LinkedEntry<K, V> header = this.header; + LinkedEntry<K, V> oldTail = header.prv; + e.nxt = header; + e.prv = oldTail; + oldTail.nxt = header.prv = e; + modCount++; } - V putImpl(K key, V value) { - LinkedHashMapEntry<K, V> m; - if (elementCount == 0) { - head = tail = null; - } - if (key == null) { - m = (LinkedHashMapEntry<K, V>) findNullKeyEntry(); - if (m == null) { - modCount++; - // Check if we need to remove the oldest entry. The check - // includes accessOrder since an accessOrder LinkedHashMap does - // not record the oldest member in 'head'. - if (++elementCount > threshold) { - rehash(); - } - m = (LinkedHashMapEntry<K, V>) createHashedEntry(null, 0, 0); - } else { - linkEntry(m); - } - } else { - int hash = key.hashCode(); - int index = (hash & 0x7FFFFFFF) % elementData.length; - m = (LinkedHashMapEntry<K, V>) findNonNullKeyEntry(key, index, hash); - if (m == null) { - modCount++; - if (++elementCount > threshold) { - rehash(); - index = (hash & 0x7FFFFFFF) % elementData.length; - } - m = (LinkedHashMapEntry<K, V>) createHashedEntry(key, index, - hash); - } else { - linkEntry(m); - } + @Override void preModify(HashMapEntry<K, V> e) { + if (accessOrder) { + makeTail((LinkedEntry<K, V>) e); } + } - V result = m.value; - m.value = value; - return result; + @Override void postRemove(HashMapEntry<K, V> e) { + LinkedEntry<K, V> le = (LinkedEntry<K, V>) e; + le.prv.nxt = le.nxt; + le.nxt.prv = le.prv; + le.nxt = le.prv = null; // Help the GC (for performance) } - /* - * @param m + /** + * This override is done for LinkedHashMap performance: iteration is cheaper + * via LinkedHashMap nxt links. */ - void linkEntry(LinkedHashMapEntry<K, V> m) { - if (tail == m) { - return; - } - - if (head == null) { - // Check if the map is empty - head = tail = m; - return; - } - - // we need to link the new entry into either the head or tail - // of the chain depending on if the LinkedHashMap is accessOrder or not - LinkedHashMapEntry<K, V> p = m.chainBackward; - LinkedHashMapEntry<K, V> n = m.chainForward; - if (p == null) { - if (n != null) { - // The entry must be the head but not the tail - if (accessOrder) { - head = n; - n.chainBackward = null; - m.chainBackward = tail; - m.chainForward = null; - tail.chainForward = m; - tail = m; + @Override public boolean containsValue(Object value) { + if (value == null) { + for (LinkedEntry<K, V> header = this.header, e = header.nxt; + e != header; e = e.nxt) { + if (e.value == null) { + return true; } - } else { - // This is a new entry - m.chainBackward = tail; - m.chainForward = null; - tail.chainForward = m; - tail = m; } - return; + return entryForNullKey != null && entryForNullKey.value == null; } - if (n == null) { - // The entry must be the tail so we can't get here - return; - } - - // The entry is neither the head nor tail - if (accessOrder) { - p.chainForward = n; - n.chainBackward = p; - m.chainForward = null; - m.chainBackward = tail; - tail.chainForward = m; - tail = m; + // value is non-null + for (LinkedEntry<K, V> header = this.header, e = header.nxt; + e != header; e = e.nxt) { + if (value.equals(e.value)) { + return true; + } } + return entryForNullKey != null && value.equals(entryForNullKey.value); } - - /** - * Returns a set containing all of the mappings in this map. Each mapping is - * an instance of {@link Map.Entry}. As the set is backed by this map, - * changes in one will be reflected in the other. - * - * @return a set of the mappings. - */ - @Override - public Set<Map.Entry<K, V>> entrySet() { - return new LinkedHashMapEntrySet<K, V>(this); + + public void clear() { + super.clear(); + + // Clear all links to help GC + LinkedEntry<K, V> header = this.header; + LinkedEntry<K, V> e = header; + do { + LinkedEntry<K, V> nxt = e.nxt; + e.nxt = e.prv = null; + e = nxt; + } while(e != header); + + header.nxt = header.prv = header; } - /** - * Returns a set of the keys contained in this map. The set is backed by - * this map so changes to one are reflected by the other. The set does not - * support adding. - * - * @return a set of the keys. - */ - @Override - public Set<K> keySet() { - if (keySet == null) { - keySet = new AbstractSet<K>() { - @Override - public boolean contains(Object object) { - return containsKey(object); - } + private abstract class LinkedHashIterator<T> implements Iterator<T> { + LinkedEntry<K, V> next = header.nxt; + LinkedEntry<K, V> lastReturned = null; + int expectedModCount = modCount; - @Override - public int size() { - return LinkedHashMap.this.size(); - } - - @Override - public void clear() { - LinkedHashMap.this.clear(); - } + public final boolean hasNext() { + return next != header; + } - @Override - public boolean remove(Object key) { - if (containsKey(key)) { - LinkedHashMap.this.remove(key); - return true; - } - return false; - } + final LinkedEntry<K, V> nextEntry() { + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + LinkedEntry<K, V> e = next; + if (e == header) + throw new NoSuchElementException(); + next = e.nxt; + return lastReturned = e; + } - @Override - public Iterator<K> iterator() { - return new KeyIterator<K,V>(LinkedHashMap.this); - } - }; + public final void remove() { + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + if (lastReturned == null) + throw new IllegalStateException(); + LinkedHashMap.this.remove(lastReturned.key); + lastReturned = null; + expectedModCount = modCount; } - return keySet; } - /** - * Returns a collection of the values contained in this map. The collection - * is backed by this map so changes to one are reflected by the other. The - * collection supports remove, removeAll, retainAll and clear operations, - * and it does not support add or addAll operations. - * <p> - * This method returns a collection which is the subclass of - * AbstractCollection. The iterator method of this subclass returns a - * "wrapper object" over the iterator of map's entrySet(). The size method - * wraps the map's size method and the contains method wraps the map's - * containsValue method. - * <p> - * The collection is created when this method is called for the first time - * and returned in response to all subsequent calls. This method may return - * different collections when multiple concurrent calls occur, since no - * synchronization is performed. - * - * @return a collection of the values contained in this map. - */ - @Override - public Collection<V> values() { - if (valuesCollection == null) { - valuesCollection = new AbstractCollection<V>() { - @Override - public boolean contains(Object object) { - return containsValue(object); - } - - @Override - public int size() { - return LinkedHashMap.this.size(); - } + private final class KeyIterator extends LinkedHashIterator<K> { + public final K next() { return nextEntry().key; } + } - @Override - public void clear() { - LinkedHashMap.this.clear(); - } + private final class ValueIterator extends LinkedHashIterator<V> { + public final V next() { return nextEntry().value; } + } - @Override - public Iterator<V> iterator() { - return new ValueIterator<K,V>(LinkedHashMap.this); - } - }; - } - return valuesCollection; + private final class EntryIterator + extends LinkedHashIterator<Map.Entry<K, V>> { + public final Map.Entry<K, V> next() { return nextEntry(); } } - /** - * Removes the mapping with the specified key from this map. - * - * @param key - * the key of the mapping to remove. - * @return the value of the removed mapping or {@code null} if no mapping - * for the specified key was found. - */ - @Override - public V remove(Object key) { - LinkedHashMapEntry<K, V> m = (LinkedHashMapEntry<K, V>) removeEntry(key); - if (m == null) { - return null; - } - LinkedHashMapEntry<K, V> p = m.chainBackward; - LinkedHashMapEntry<K, V> n = m.chainForward; - if (p != null) { - p.chainForward = n; - } else { - head = n; - } - if (n != null) { - n.chainBackward = p; - } else { - tail = p; - } - return m.value; + // Override view iterator methods to generate correct iteration order + @Override Iterator<K> newKeyIterator() { + return new KeyIterator(); + } + @Override Iterator<V> newValueIterator() { + return new ValueIterator(); + } + @Override Iterator<Map.Entry<K, V>> newEntryIterator() { + return new EntryIterator(); } - /** - * This method is queried from the put and putAll methods to check if the - * eldest member of the map should be deleted before adding the new member. - * If this map was created with accessOrder = true, then the result of - * removeEldestEntry is assumed to be false. - * - * @param eldest - * the entry to check if it should be removed. - * @return {@code true} if the eldest member should be removed. - */ protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return false; } - // BEGIN android-changed - /** - * Removes all elements from this map, leaving it empty. - * - * @see #isEmpty() - * @see #size() - */ - @Override - public void clear() { - internalClear(); - } - - @Override - void internalClear() { - super.internalClear(); - head = tail = null; - } - // END android-changed + private static final long serialVersionUID = 3801124242820219131L; } diff --git a/luni/src/main/native/java_net_InetAddress.cpp b/luni/src/main/native/java_net_InetAddress.cpp index 8724817..90a88ee 100644 --- a/luni/src/main/native/java_net_InetAddress.cpp +++ b/luni/src/main/native/java_net_InetAddress.cpp @@ -111,11 +111,6 @@ static jobjectArray getAllByNameUsingDns(JNIEnv* env, const char* name, jobjectArray addressArray = NULL; memset(&hints, 0, sizeof(hints)); - /* - * IPv4 only for now until the socket code supports IPv6; otherwise, the - * resolver will create two separate requests, one for IPv4 and one, - * currently unnecessary, for IPv6. - */ hints.ai_family = AF_UNSPEC; hints.ai_flags = AI_ADDRCONFIG; /* @@ -233,7 +228,9 @@ jobjectArray InetAddress_getallbyname(JNIEnv* env, jobject obj, } if (!out) { +#if LOG_DNS LOGI("Unknown host %s, throwing UnknownHostException", name); +#endif jniThrowException(env, "java/net/UnknownHostException", name); } env->ReleaseStringUTFChars(javaName, name); @@ -241,6 +238,14 @@ jobjectArray InetAddress_getallbyname(JNIEnv* env, jobject obj, } +/** + * Looks up the name corresponding to an IP address. + * + * @param javaAddress: a byte array containing the raw IP address bytes. Must be + * 4 or 16 bytes long. + * @return the hostname. + * @throws UnknownHostException: the IP address has no associated hostname. + */ static jstring InetAddress_gethostbyaddr(JNIEnv* env, jobject obj, jbyteArray javaAddress) { @@ -257,57 +262,45 @@ static jstring InetAddress_gethostbyaddr(JNIEnv* env, jobject obj, } // Convert the raw address bytes into a socket address structure. + int ret = 0; struct sockaddr_storage ss; struct sockaddr_in *sin = (struct sockaddr_in *) &ss; struct sockaddr_in6 *sin6 = (struct sockaddr_in6 *) &ss; size_t socklen; + memset(&ss, 0, sizeof(ss)); switch (addrlen) { case 4: socklen = sizeof(struct sockaddr_in); - memset(sin, 0, sizeof(struct sockaddr_in)); sin->sin_family = AF_INET; - memcpy(&sin->sin_addr.s_addr, rawAddress, 4); + memcpy(&sin->sin_addr.s_addr, rawAddress, addrlen); env->ReleaseByteArrayElements(javaAddress, rawAddress, JNI_ABORT); break; case 16: socklen = sizeof(struct sockaddr_in6); - memset(sin6, 0, sizeof(struct sockaddr_in6)); sin6->sin6_family = AF_INET6; - memcpy(&sin6->sin6_addr.s6_addr, rawAddress, 16); + memcpy(&sin6->sin6_addr.s6_addr, rawAddress, addrlen); env->ReleaseByteArrayElements(javaAddress, rawAddress, JNI_ABORT); break; default: + // The caller already throws an exception in this case. Don't worry + // about it here. env->ReleaseByteArrayElements(javaAddress, rawAddress, JNI_ABORT); - jniThrowException(env, "java/net/UnknownHostException", - "Invalid address length"); return NULL; } - - // Convert the socket address structure to an IP string for logging. - int ret; - char ipstr[INET6_ADDRSTRLEN]; - ret = getnameinfo((struct sockaddr *) &ss, socklen, ipstr, sizeof(ipstr), - NULL, 0, NI_NUMERICHOST); - if (ret) { - LOGE("gethostbyaddr: getnameinfo: %s", gai_strerror(ret)); - return NULL; + // Look up the host name from the IP address. + char name[NI_MAXHOST]; + if (ret == 0) { + ret = getnameinfo((struct sockaddr *) &ss, socklen, name, sizeof(name), + NULL, 0, NI_NAMEREQD); } - // Look up the IP address from the socket address structure. - jstring result = NULL; - char name[NI_MAXHOST]; - ret = getnameinfo((struct sockaddr *) &ss, socklen, name, sizeof(name), - NULL, 0, 0); if (ret == 0) { - LOGI("gethostbyaddr: getnameinfo: %s = %s", ipstr, name); - result = env->NewStringUTF(name); - } else { - LOGE("gethostbyaddr: getnameinfo: unknown host %s: %s", ipstr, - gai_strerror(ret)); + return env->NewStringUTF(name); } - return result; + jniThrowException(env, "java/net/UnknownHostException", gai_strerror(ret)); + return NULL; } /* diff --git a/luni/src/main/native/org_apache_harmony_luni_platform_OSMemory.cpp b/luni/src/main/native/org_apache_harmony_luni_platform_OSMemory.cpp index 3e31743..2e814cc 100644 --- a/luni/src/main/native/org_apache_harmony_luni_platform_OSMemory.cpp +++ b/luni/src/main/native/org_apache_harmony_luni_platform_OSMemory.cpp @@ -172,12 +172,10 @@ static void harmony_nio_putBytesImpl(JNIEnv *_env, jobject _this, } static void -swapShorts(jshort *shorts, int numBytes) { +swapShorts(jshort *shorts, int count) { jbyte *src = (jbyte *) shorts; jbyte *dst = src; - int i; - - for (i = 0; i < numBytes; i+=2) { + for (int i = 0; i < count; ++i) { jbyte b0 = *src++; jbyte b1 = *src++; *dst++ = b1; @@ -186,11 +184,10 @@ swapShorts(jshort *shorts, int numBytes) { } static void -swapInts(jint *ints, int numBytes) { +swapInts(jint *ints, int count) { jbyte *src = (jbyte *) ints; jbyte *dst = src; - int i; - for (i = 0; i < numBytes; i+=4) { + for (int i = 0; i < count; ++i) { jbyte b0 = *src++; jbyte b1 = *src++; jbyte b2 = *src++; @@ -204,48 +201,30 @@ swapInts(jint *ints, int numBytes) { /* * Class: org_apache_harmony_luni_platform_OSMemory - * Method: putShortsImpl + * Method: setShortArrayImpl * Signature: (I[SIIZ)V */ -static void harmony_nio_putShortsImpl(JNIEnv *_env, jobject _this, +static void harmony_nio_setShortArrayImpl(JNIEnv *_env, jobject _this, jint pointer, jshortArray src, jint offset, jint length, jboolean swap) { - - offset = offset << 1; - length = length << 1; - - jshort *src_ = - (jshort *)_env->GetPrimitiveArrayCritical(src, (jboolean *)0); - if (swap) { - swapShorts(src_ + offset, length); - } - memcpy((jbyte *)pointer, (jbyte *)src_ + offset, length); + jshort* dst = reinterpret_cast<jshort*>(static_cast<uintptr_t>(pointer)); + _env->GetShortArrayRegion(src, offset, length, dst); if (swap) { - swapShorts(src_ + offset, length); + swapShorts(dst, length); } - _env->ReleasePrimitiveArrayCritical(src, src_, JNI_ABORT); } /* * Class: org_apache_harmony_luni_platform_OSMemory - * Method: putIntsImpl + * Method: setIntArrayImpl * Signature: (I[IIIZ)V */ -static void harmony_nio_putIntsImpl(JNIEnv *_env, jobject _this, +static void harmony_nio_setIntArrayImpl(JNIEnv *_env, jobject _this, jint pointer, jintArray src, jint offset, jint length, jboolean swap) { - - offset = offset << 2; - length = length << 2; - - jint *src_ = - (jint *)_env->GetPrimitiveArrayCritical(src, (jboolean *)0); + jint* dst = reinterpret_cast<jint*>(static_cast<uintptr_t>(pointer)); + _env->GetIntArrayRegion(src, offset, length, dst); if (swap) { - swapInts(src_ + offset, length); + swapInts(dst, length); } - memcpy((jbyte *)pointer, (jbyte *)src_ + offset, length); - if (swap) { - swapInts(src_ + offset, length); - } - _env->ReleasePrimitiveArrayCritical(src, src_, JNI_ABORT); } /* @@ -588,8 +567,8 @@ static JNINativeMethod gMethods[] = { { "memmove", "(IIJ)V", (void*) harmony_nio_memmove }, { "getByteArray", "(I[BII)V",(void*) harmony_nio_getBytesImpl }, { "setByteArray", "(I[BII)V",(void*) harmony_nio_putBytesImpl }, - { "setShortArray", "(I[SIIZ)V",(void*) harmony_nio_putShortsImpl }, - { "setIntArray", "(I[IIIZ)V",(void*) harmony_nio_putIntsImpl }, + { "setShortArray", "(I[SIIZ)V",(void*) harmony_nio_setShortArrayImpl }, + { "setIntArray", "(I[IIIZ)V",(void*) harmony_nio_setIntArrayImpl }, { "getByte", "(I)B", (void*) harmony_nio_getByteImpl }, { "setByte", "(IB)V", (void*) harmony_nio_putByteImpl }, { "getShort", "(I)S", (void*) harmony_nio_getShortImpl }, @@ -653,4 +632,3 @@ int register_org_apache_harmony_luni_platform_OSMemory(JNIEnv *_env) { "org/apache/harmony/luni/platform/OSMemory", gMethods, NELEM(gMethods)); } - diff --git a/luni/src/main/native/org_apache_harmony_luni_platform_OSNetworkSystem.cpp b/luni/src/main/native/org_apache_harmony_luni_platform_OSNetworkSystem.cpp index cce822a..22d1cd4 100644 --- a/luni/src/main/native/org_apache_harmony_luni_platform_OSNetworkSystem.cpp +++ b/luni/src/main/native/org_apache_harmony_luni_platform_OSNetworkSystem.cpp @@ -156,8 +156,9 @@ struct CachedFields { jfieldID fd_descriptor; jclass iaddr_class; - jmethodID iaddr_class_init; jmethodID iaddr_getbyaddress; + jclass i4addr_class; + jmethodID i4addr_class_init; jfieldID iaddr_ipaddress; jclass genericipmreq_class; jclass integer_class; @@ -1401,23 +1402,27 @@ static void osNetworkSystem_oneTimeInitializationImpl(JNIEnv* env, jobject obj, // initializing InetAddress jclass iaddrclass = env->FindClass("java/net/InetAddress"); - if (iaddrclass == NULL) { jniThrowException(env, "java/lang/ClassNotFoundException", "java.net.InetAddress"); return; } - gCachedFields.iaddr_class = (jclass) env->NewGlobalRef(iaddrclass); - jmethodID iaddrclassinit = env->GetMethodID(iaddrclass, "<init>", "()V"); - - if (iaddrclassinit == NULL) { - jniThrowException(env, "java/lang/NoSuchMethodError", "InetAddress.<init>()"); + jclass i4addrclass = env->FindClass("java/net/Inet4Address"); + if (i4addrclass == NULL) { + jniThrowException(env, "java/lang/ClassNotFoundException", + "java.net.Inet4Address"); return; } + gCachedFields.i4addr_class = (jclass) env->NewGlobalRef(i4addrclass); - gCachedFields.iaddr_class_init = iaddrclassinit; + jmethodID i4addrclassinit = env->GetMethodID(i4addrclass, "<init>", "([B)V"); + if (i4addrclassinit == NULL) { + jniThrowException(env, "java/lang/NoSuchMethodError", "Inet4Address.<init>(byte[])"); + return; + } + gCachedFields.i4addr_class_init = i4addrclassinit; jmethodID iaddrgetbyaddress = env->GetStaticMethodID(iaddrclass, "getByAddress", "([B)Ljava/net/InetAddress;"); @@ -1431,13 +1436,11 @@ static void osNetworkSystem_oneTimeInitializationImpl(JNIEnv* env, jobject obj, gCachedFields.iaddr_getbyaddress = iaddrgetbyaddress; jfieldID iaddripaddress = env->GetFieldID(iaddrclass, "ipaddress", "[B"); - if (iaddripaddress == NULL) { jniThrowException(env, "java/lang/NoSuchFieldError", "Can't find field InetAddress.ipaddress"); return; } - gCachedFields.iaddr_ipaddress = iaddripaddress; // get the GenericIPMreq class @@ -3621,8 +3624,10 @@ static jobject osNetworkSystem_inheritedChannelImpl(JNIEnv* env, jobject obj) { ntohs(local_addr.sin_port)); // new and set remote addr - addr_object = env->NewObject(gCachedFields.iaddr_class, - gCachedFields.iaddr_class_init); + addr_array = env->NewByteArray((jsize)4); + env->SetByteArrayRegion(addr_array, (jsize)0, (jsize)4, address); + addr_object = env->NewObject(gCachedFields.i4addr_class, + gCachedFields.i4addr_class_init, addr_array); if (NULL == addr_object) { goto clean; } @@ -3634,13 +3639,6 @@ static jobject osNetworkSystem_inheritedChannelImpl(JNIEnv* env, jobject obj) { if (NULL == socketaddr_object) { goto clean; } - addr_field = env->GetFieldID(socketaddr_class, "addr", - "Ljava/net/InetAddress;"); - env->SetObjectField(socketaddr_object, addr_field, addr_object); - addr_array = env->NewByteArray((jsize)4); - env->SetByteArrayRegion(addr_array, (jsize)0, (jsize)4, address); - env->SetObjectField(addr_object, gCachedFields.iaddr_ipaddress, - addr_array); // localAddr socketaddr_class = env->FindClass("java/net/InetSocketAddress"); @@ -3650,9 +3648,11 @@ static jobject osNetworkSystem_inheritedChannelImpl(JNIEnv* env, jobject obj) { socketaddr_field); localAddr_field = env->GetFieldID(channel_class, "localAddress", - "Ljava/net/InetAddress;"); - localAddr_object = env->NewObject(gCachedFields.iaddr_class, - gCachedFields.iaddr_class_init); + "Ljava/net/Inet4Address;"); + addr_array = env->NewByteArray((jsize)4); + env->SetByteArrayRegion(addr_array, (jsize)0, (jsize)4, localAddr); + localAddr_object = env->NewObject(gCachedFields.i4addr_class, + gCachedFields.i4addr_class_init, addr_array); jfieldID socketaddr_field = env->GetFieldID(channel_class, "connectAddress", "Ljava/net/InetSocketAddress;"); jobject socketaddr_object = env->GetObjectField(channel_object, @@ -3662,10 +3662,6 @@ static jobject osNetworkSystem_inheritedChannelImpl(JNIEnv* env, jobject obj) { if (NULL == localAddr_object) { goto clean; } - addr_array = env->NewByteArray((jsize)4); - env->SetByteArrayRegion(addr_array, (jsize)0, (jsize)4, localAddr); - env->SetObjectField(localAddr_object, gCachedFields.iaddr_ipaddress, - addr_array); // set port @@ -3720,8 +3716,10 @@ static jobject osNetworkSystem_inheritedChannelImpl(JNIEnv* env, jobject obj) { localAddr_field = env->GetFieldID(channel_class, "localAddress", "Ljava/net/InetAddress;"); - localAddr_object = env->NewObject(gCachedFields.iaddr_class, - gCachedFields.iaddr_class_init); + memset(address, 0, 4); + env->SetByteArrayRegion(addr_array, (jsize)0, (jsize)4, address); + localAddr_object = env->NewObject(gCachedFields.i4addr_class, + gCachedFields.i4addr_class_init, addr_array); if (NULL == localAddr_object) { goto clean; } @@ -3768,8 +3766,10 @@ static jobject osNetworkSystem_inheritedChannelImpl(JNIEnv* env, jobject obj) { env->SetIntField(channel_object, port_field, ntohs(local_addr.sin_port)); // new and set remote addr + addr_array = env->NewByteArray((jsize)4); + env->SetByteArrayRegion(addr_array, (jsize)0, (jsize)4, address); addr_object = env->NewObject(gCachedFields.iaddr_class, - gCachedFields.iaddr_class_init); + gCachedFields.i4addr_class_init, addr_array); if (NULL == addr_object) { goto clean; } @@ -3780,12 +3780,6 @@ static jobject osNetworkSystem_inheritedChannelImpl(JNIEnv* env, jobject obj) { if (NULL == socketaddr_object) { goto clean; } - addr_field = env->GetFieldID(socketaddr_class, "addr", - "Ljava/net/InetAddress;"); - env->SetObjectField(socketaddr_object, addr_field, addr_object); - addr_array = env->NewByteArray((jsize)4); - env->SetByteArrayRegion(addr_array, (jsize)0, (jsize)4, address); - env->SetObjectField(addr_object, gCachedFields.iaddr_ipaddress, addr_array); // set bound if (0 != local_addr.sin_port) { diff --git a/luni/src/test/java/org/apache/harmony/luni/platform/AllTests.java b/luni/src/test/java/org/apache/harmony/luni/platform/AllTests.java new file mode 100644 index 0000000..be28d41 --- /dev/null +++ b/luni/src/test/java/org/apache/harmony/luni/platform/AllTests.java @@ -0,0 +1,36 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.harmony.luni.platform; + +import junit.framework.Test; +import junit.framework.TestSuite; +import junit.textui.TestRunner; + +public class AllTests { + public static void run() { + TestRunner.main(new String[] { AllTests.class.getName() }); + } + + public static final Test suite() { + TestSuite suite = tests.TestSuiteFactory.createTestSuite("Tests for org.apache.harmony.luni.platform"); + + suite.addTestSuite(OSMemoryTest.class); + + return suite; + } +} diff --git a/luni/src/test/java/org/apache/harmony/luni/platform/OSMemoryTest.java b/luni/src/test/java/org/apache/harmony/luni/platform/OSMemoryTest.java new file mode 100644 index 0000000..a546289 --- /dev/null +++ b/luni/src/test/java/org/apache/harmony/luni/platform/OSMemoryTest.java @@ -0,0 +1,164 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.harmony.luni.platform; + +import dalvik.annotation.TestLevel; +import dalvik.annotation.TestTargetNew; +import dalvik.annotation.TestTargetClass; +import dalvik.annotation.AndroidOnly; + +import junit.framework.TestCase; + +/** + * Tests org.apache.harmony.luni.platform.OSMemory (via IMemorySystem). + */ +@TestTargetClass(org.apache.harmony.luni.platform.OSMemory.class) +public class OSMemoryTest extends TestCase { + @TestTargetNew( + level = TestLevel.PARTIAL_COMPLETE, + notes = "", + method = "memset", + args = {} + ) + public void testMemset() { + IMemorySystem memory = Platform.getMemorySystem(); + + int byteCount = 32; + int ptr = memory.malloc(byteCount); + try { + // Ensure our newly-allocated block isn't zeroed. + memory.setByte(ptr, (byte) 1); + assertEquals((byte) 1, memory.getByte(ptr)); + // Check that we can clear memory. + memory.memset(ptr, (byte) 0, byteCount); + assertBytesEqual((byte) 0, ptr, byteCount); + // Check that we can set an arbitrary value. + memory.memset(ptr, (byte) 1, byteCount); + assertBytesEqual((byte) 1, ptr, byteCount); + } finally { + memory.free(ptr); + } + } + + void assertBytesEqual(byte value, int ptr, int byteCount) { + IMemorySystem memory = Platform.getMemorySystem(); + for (int i = 0; i < byteCount; ++i) { + assertEquals(value, memory.getByte(ptr + i)); + } + } + + @TestTargetNew( + level = TestLevel.PARTIAL_COMPLETE, + notes = "", + method = "setIntArray", + args = {} + ) + public void testSetIntArray() { + IMemorySystem memory = Platform.getMemorySystem(); + + int[] values = { 3, 7, 31, 127, 8191, 131071, 524287, 2147483647 }; + int[] swappedValues = new int[values.length]; + for (int i = 0; i < values.length; ++i) { + swappedValues[i] = swapInt(values[i]); + } + + int scale = ICommonDataTypes.SIZEOF_JINT; + int ptr = memory.malloc(scale * values.length); + try { + // Regular copy. Memset first so we start from a known state. + memory.memset(ptr, (byte) 0, scale * values.length); + memory.setIntArray(ptr, values, 0, values.length, false); + assertIntsEqual(values, ptr); + + // Swapped copy. + memory.memset(ptr, (byte) 0, scale * values.length); + memory.setIntArray(ptr, values, 0, values.length, true); + assertIntsEqual(swappedValues, ptr); + + // Swapped copies of slices (to ensure we test non-zero offsets). + memory.memset(ptr, (byte) 0, scale * values.length); + for (int i = 0; i < values.length; ++i) { + memory.setIntArray(ptr + i * scale, values, i, 1, true); + } + assertIntsEqual(swappedValues, ptr); + } finally { + memory.free(ptr); + } + } + + private void assertIntsEqual(int[] expectedValues, int ptr) { + IMemorySystem memory = Platform.getMemorySystem(); + for (int i = 0; i < expectedValues.length; ++i) { + assertEquals(expectedValues[i], memory.getInt(ptr + ICommonDataTypes.SIZEOF_JINT * i)); + } + } + + private static int swapInt(int n) { + return (((n >> 0) & 0xff) << 24) | + (((n >> 8) & 0xff) << 16) | + (((n >> 16) & 0xff) << 8) | + (((n >> 24) & 0xff) << 0); + } + + @TestTargetNew( + level = TestLevel.PARTIAL_COMPLETE, + notes = "", + method = "setShortArray", + args = {} + ) + public void testSetShortArray() { + IMemorySystem memory = Platform.getMemorySystem(); + + short[] values = { 0x0001, 0x0020, 0x0300, 0x4000 }; + short[] swappedValues = { 0x0100, 0x2000, 0x0003, 0x0040 }; + + int scale = ICommonDataTypes.SIZEOF_JSHORT; + int ptr = memory.malloc(scale * values.length); + try { + // Regular copy. Memset first so we start from a known state. + memory.memset(ptr, (byte) 0, scale * values.length); + memory.setShortArray(ptr, values, 0, values.length, false); + assertShortsEqual(values, ptr); + + // Swapped copy. + memory.memset(ptr, (byte) 0, scale * values.length); + memory.setShortArray(ptr, values, 0, values.length, true); + assertShortsEqual(swappedValues, ptr); + + // Swapped copies of slices (to ensure we test non-zero offsets). + memory.memset(ptr, (byte) 0, scale * values.length); + for (int i = 0; i < values.length; ++i) { + memory.setShortArray(ptr + i * scale, values, i, 1, true); + } + assertShortsEqual(swappedValues, ptr); + } finally { + memory.free(ptr); + } + } + + private void assertShortsEqual(short[] expectedValues, int ptr) { + IMemorySystem memory = Platform.getMemorySystem(); + for (int i = 0; i < expectedValues.length; ++i) { + assertEquals(expectedValues[i], memory.getShort(ptr + ICommonDataTypes.SIZEOF_JSHORT * i)); + } + } + + private static short swapShort(short n) { + return (short) ((((n >> 0) & 0xff) << 8) | (((n >> 8) & 0xff) << 0)); + } +} diff --git a/luni/src/test/java/tests/AllTests.java b/luni/src/test/java/tests/AllTests.java index 26e58c1..893cdf0 100644 --- a/luni/src/test/java/tests/AllTests.java +++ b/luni/src/test/java/tests/AllTests.java @@ -54,6 +54,8 @@ public class AllTests suite.addTest(tests.xml.AllTests.suite()); suite.addTest(tests.xnet.AllTests.suite()); + suite.addTest(org.apache.harmony.luni.platform.AllTests.suite()); + return suite; } } diff --git a/luni/src/test/java/tests/api/java/lang/reflect/ConstructorTest.java b/luni/src/test/java/tests/api/java/lang/reflect/ConstructorTest.java index 6bdb55a..e9554dd 100644 --- a/luni/src/test/java/tests/api/java/lang/reflect/ConstructorTest.java +++ b/luni/src/test/java/tests/api/java/lang/reflect/ConstructorTest.java @@ -104,7 +104,11 @@ public class ConstructorTest extends junit.framework.TestCase { public GenericConstructorTestHelper(T t, S s) {} public GenericConstructorTestHelper() throws E{} } - + + static class NoPublicConstructorTestHelper { + // This class has no public constructor. + } + // Used to test synthetic constructor. // // static class Outer { @@ -479,7 +483,6 @@ public class ConstructorTest extends junit.framework.TestCase { } catch (Exception e) { fail("Exception during getGenericExceptionTypes test:" + e.toString()); } - System.out.println(Arrays.toString(types)); assertEquals("Wrong number of exception types returned", 1, types.length); @@ -555,7 +558,35 @@ public class ConstructorTest extends junit.framework.TestCase { .equals( "public tests.api.java.lang.reflect.ConstructorTest$ConstructorTestHelper(java.lang.Object)")); } - + + /** + * @tests java.lang.reflect.Constructor#getConstructor((Class[]) null) + */ + @TestTargetNew( + level = TestLevel.COMPLETE, + notes = "", + method = "getConstructor", + args = {} + ) + public void test_getConstructor() throws Exception { + // Passing new Class[0] should be equivalent to (Class[]) null. + Class<ConstructorTestHelper> c2 = ConstructorTestHelper.class; + assertEquals(c2.getConstructor(new Class[0]), c2.getConstructor((Class[]) null)); + assertEquals(c2.getDeclaredConstructor(new Class[0]), + c2.getDeclaredConstructor((Class[]) null)); + + // We can get a non-public constructor via getDeclaredConstructor... + Class<NoPublicConstructorTestHelper> c1 = NoPublicConstructorTestHelper.class; + c1.getDeclaredConstructor((Class[]) null); + // ...but not with getConstructor (which only returns public constructors). + try { + c1.getConstructor((Class[]) null); + fail("Should throw NoSuchMethodException"); + } catch (NoSuchMethodException ex) { + // Expected. + } + } + /** * Sets up the fixture, for example, open a network connection. This method * is called before a test is executed. @@ -570,4 +601,3 @@ public class ConstructorTest extends junit.framework.TestCase { protected void tearDown() { } } - diff --git a/luni/src/test/java/tests/api/java/lang/reflect/MethodTest.java b/luni/src/test/java/tests/api/java/lang/reflect/MethodTest.java index 884bc8c..506d173 100644 --- a/luni/src/test/java/tests/api/java/lang/reflect/MethodTest.java +++ b/luni/src/test/java/tests/api/java/lang/reflect/MethodTest.java @@ -226,7 +226,41 @@ public class MethodTest extends junit.framework.TestCase { } assertTrue("Inherited method returned not-equal", m1.equals(m2)); } - + + /** + * @tests java.lang.Class#getMethod(java.lang.String, java.lang.Class[]) + */ + @TestTargetNew( + level = TestLevel.COMPLETE, + notes = "", + method = "getMethod", + args = {java.lang.String.class, java.lang.Class[].class}, + clazz = java.lang.Class.class + ) + public void test_getMethod() throws NoSuchMethodException, SecurityException { + // Check that getMethod treats null parameterTypes the same as an empty array. + Method m1 = TestMethod.class.getMethod("invokeInstanceTest", new Class[0]); + Method m2 = TestMethod.class.getMethod("invokeInstanceTest", (Class[]) null); + assertEquals(m1, m2); + } + + /** + * @tests java.lang.Class#getDeclaredMethod(java.lang.String, java.lang.Class[]) + */ + @TestTargetNew( + level = TestLevel.COMPLETE, + notes = "", + method = "getDeclaredMethod", + args = {java.lang.String.class, java.lang.Class[].class}, + clazz = java.lang.Class.class + ) + public void test_getDeclaredMethod() throws NoSuchMethodException, SecurityException { + // Check that getDeclaredMethod treats null parameterTypes the same as an empty array. + Method m1 = TestMethod.class.getDeclaredMethod("invokeInstanceTest", new Class[0]); + Method m2 = TestMethod.class.getDeclaredMethod("invokeInstanceTest", (Class[]) null); + assertEquals(m1, m2); + } + /** * @tests java.lang.reflect.Method#getDeclaringClass() */ diff --git a/luni/src/test/java/tests/api/java/util/CollectionsTest.java b/luni/src/test/java/tests/api/java/util/CollectionsTest.java index b75898b..2b1b47e 100644 --- a/luni/src/test/java/tests/api/java/util/CollectionsTest.java +++ b/luni/src/test/java/tests/api/java/util/CollectionsTest.java @@ -1435,11 +1435,7 @@ public class CollectionsTest extends junit.framework.TestCase { .indexOfSubList(src, sub2)); } - /** - * @param string2 - * @param string1 - * @param index - */ + private void testwithCharList(int count, String string1, String string2, boolean first) { char[] chars = string1.toCharArray(); @@ -2379,9 +2375,11 @@ public class CollectionsTest extends junit.framework.TestCase { m.put("one", "1"); m.put("two", "2"); Map um = Collections.unmodifiableMap(m); - assertEquals("{one=1, two=2}", um.toString()); + assertTrue("{one=1, two=2}".equals(um.toString()) || + "{two=2, one=1}".equals(um.toString())); } + @TestTargetNew( level = TestLevel.COMPLETE, notes = "", diff --git a/luni/src/test/java/tests/api/java/util/HashMapTest.java b/luni/src/test/java/tests/api/java/util/HashMapTest.java index 1d726ea..af73c0a 100644 --- a/luni/src/test/java/tests/api/java/util/HashMapTest.java +++ b/luni/src/test/java/tests/api/java/util/HashMapTest.java @@ -20,17 +20,9 @@ package tests.api.java.util; import dalvik.annotation.TestTargetNew; import dalvik.annotation.TestTargets; import dalvik.annotation.TestLevel; -import dalvik.annotation.TestTargetClass; - -import java.util.AbstractMap; -import java.util.ArrayList; -import java.util.Arrays; -import java.util.Collection; -import java.util.HashMap; -import java.util.Iterator; -import java.util.Map; -import java.util.Set; -import java.util.TreeMap; +import dalvik.annotation.TestTargetClass; + +import java.util.*; import tests.support.Support_MapTest2; import tests.support.Support_UnmodifiableCollectionTest; @@ -39,7 +31,7 @@ import tests.support.Support_UnmodifiableCollectionTest; public class HashMapTest extends junit.framework.TestCase { class MockMap extends AbstractMap { public Set entrySet() { - return null; + return Collections.EMPTY_SET; } public int size(){ return 0; @@ -151,14 +143,10 @@ public class HashMapTest extends junit.framework.TestCase { for (int counter = 0; counter < hmSize; counter++) assertTrue("Failed to construct correct HashMap", hm .get(objArray2[counter]) == hm2.get(objArray2[counter])); - - try { - Map mockMap = new MockMap(); - hm = new HashMap(mockMap); - fail("Should throw NullPointerException"); - } catch (NullPointerException e) { - //empty - } + + Map mockMap = new MockMap(); + hm = new HashMap(mockMap); + assertEquals(hm, mockMap); } /** @@ -296,6 +284,40 @@ public class HashMapTest extends junit.framework.TestCase { } /** + * @tests java.util.HashMap#entrySet() + */ + @TestTargetNew( + level = TestLevel.PARTIAL_COMPLETE, + notes = "", + method = "entrySet", + args = {} + ) + public void test_entrySetEquals() { + Set s1 = hm.entrySet(); + Set s2 = new HashMap(hm).entrySet(); + assertEquals(s1, s2); + } + + /** + * @tests java.util.HashMap#entrySet() + */ + @TestTargetNew( + level = TestLevel.PARTIAL_COMPLETE, + notes = "", + method = "entrySet", + args = {} + ) + public void test_removeFromViews() { + hm.put("A", null); + hm.put("B", null); + assertTrue(hm.keySet().remove("A")); + + Map<String, String> m2 = new HashMap<String, String>(); + m2.put("B", null); + assertTrue(hm.entrySet().remove(m2.entrySet().iterator().next())); + } + + /** * @tests java.util.HashMap#get(java.lang.Object) */ @TestTargetNew( @@ -479,7 +501,39 @@ public class HashMapTest extends junit.framework.TestCase { } catch (NullPointerException e) { // expected. } - } + } + + @TestTargetNew( + level = TestLevel.PARTIAL_COMPLETE, + notes = "Checks putAll that causes map to resize", + method = "putAll", + args = {java.util.Map.class} + ) + public void test_putAllLjava_util_Map_Resize() { + Random rnd = new Random(666); + + Map<Integer,Integer> m1 = new HashMap<Integer, Integer>(); + int MID = 10000; + for (int i = 0; i < MID; i++) { + Integer j = rnd.nextInt(); + m1.put(j, j); + } + + Map<Integer,Integer> m2 = new HashMap<Integer, Integer>(); + int HI = 30000; + for (int i = MID; i < HI; i++) { + Integer j = rnd.nextInt(); + m2.put(j, j); + } + + m1.putAll(m2); + + rnd = new Random(666); + for (int i = 0; i < HI; i++) { + Integer j = rnd.nextInt(); + assertEquals(j, m1.get(j)); + } + } /** * @tests java.util.HashMap#remove(java.lang.Object) diff --git a/luni/src/test/java/tests/api/java/util/HashtableTest.java b/luni/src/test/java/tests/api/java/util/HashtableTest.java index bbdad50..6c50f1b 100644 --- a/luni/src/test/java/tests/api/java/util/HashtableTest.java +++ b/luni/src/test/java/tests/api/java/util/HashtableTest.java @@ -35,6 +35,7 @@ import java.util.NoSuchElementException; import java.util.Set; import java.util.TreeMap; import java.util.Vector; +import java.util.Collections; import tests.api.java.util.HashMapTest.ReusableKey; import tests.support.Support_MapTest2; @@ -166,6 +167,24 @@ public class HashtableTest extends junit.framework.TestCase { } /** + * @tests java.util.Hashtable#Hashtable(java.util.Map) + */ + @TestTargetNew( + level = TestLevel.COMPLETE, + notes = "", + method = "Hashtable", + args = {java.util.Map.class} + ) + public void test_ConversionConstructorNullValue() { + Map<String, Void> map = Collections.singletonMap("Dog", null); + try { + new Hashtable<String, Void>(map); + fail("NullPointerException expected"); + } catch (NullPointerException e) { + //expected + } + } + /** * @tests java.util.Hashtable#clear() */ @TestTargetNew( @@ -310,46 +329,49 @@ public class HashtableTest extends junit.framework.TestCase { assertEquals("All keys not retrieved", 10, ht10.size()); } - /** - * @tests java.util.Hashtable#elements() - */ - @TestTargetNew( - level = TestLevel.COMPLETE, - notes = "", - method = "elements", - args = {} - ) - public void test_elements_subtest0() { - // this is the reference implementation behavior - final Hashtable ht = new Hashtable(7); - ht.put("1", "a"); - // these three elements hash to the same bucket in a 7 element Hashtable - ht.put("2", "b"); - ht.put("9", "c"); - ht.put("12", "d"); - // Hashtable looks like: - // 0: "1" - // 1: "12" -> "9" -> "2" - Enumeration en = ht.elements(); - // cache the first entry - en.hasMoreElements(); - ht.remove("12"); - ht.remove("9"); - boolean exception = false; - try { - // cached "12" - Object result = en.nextElement(); - assertNull("unexpected: " + result, result); - // next is removed "9" - result = en.nextElement(); - assertNull("unexpected: " + result, result); - result = en.nextElement(); - assertTrue("unexpected: " + result, "b".equals(result)); - } catch (NoSuchElementException e) { - exception = true; - } - assertTrue("unexpected NoSuchElementException", !exception); - } +// BEGIN android-removed +// implementation dependent +// /** +// * @tests java.util.Hashtable#elements() +// */ +// @TestTargetNew( +// level = TestLevel.COMPLETE, +// notes = "", +// method = "elements", +// args = {} +// ) +// public void test_elements_subtest0() { +// // this is the reference implementation behavior +// final Hashtable ht = new Hashtable(7); +// ht.put("1", "a"); +// // these three elements hash to the same bucket in a 7 element Hashtable +// ht.put("2", "b"); +// ht.put("9", "c"); +// ht.put("12", "d"); +// // Hashtable looks like: +// // 0: "1" +// // 1: "12" -> "9" -> "2" +// Enumeration en = ht.elements(); +// // cache the first entry +// en.hasMoreElements(); +// ht.remove("12"); +// ht.remove("9"); +// boolean exception = false; +// try { +// // cached "12" +// Object result = en.nextElement(); +// assertNull("unexpected: " + result, result); +// // next is removed "9" +// result = en.nextElement(); +// assertNull("unexpected: " + result, result); +// result = en.nextElement(); +// assertTrue("unexpected: " + result, "b".equals(result)); +// } catch (NoSuchElementException e) { +// exception = true; +// } +// assertTrue("unexpected NoSuchElementException", !exception); +// } +// END android-removed /** * @tests java.util.Hashtable#entrySet() @@ -371,9 +393,11 @@ public class HashtableTest extends junit.framework.TestCase { while (e.hasMoreElements()) assertTrue("Returned incorrect entry set", s2.contains(e .nextElement())); - - assertEquals("Not synchronized", - "java.util.Collections$SynchronizedSet", s.getClass().getName()); +// BEGIN android-removed +// implementation dependent +// assertEquals("Not synchronized", +// "java.util.Collections$SynchronizedSet", s.getClass().getName()); +// END android-removed boolean exception = false; try { @@ -417,26 +441,28 @@ public class HashtableTest extends junit.framework.TestCase { Hashtable h = hashtableClone(htfull); assertEquals("Could not retrieve element", "FVal 2", ((String) h.get("FKey 2")) ); - - - // Regression for HARMONY-262 - ReusableKey k = new ReusableKey(); - Hashtable h2 = new Hashtable(); - k.setKey(1); - h2.put(k, "value1"); - - k.setKey(13); - assertNull(h2.get(k)); - - k.setKey(12); - assertNull(h2.get(k)); - try { - h2.get(null); - fail("NullPointerException expected"); - } catch (NullPointerException e) { - //expected - } +// BEGIN android-removed +// implementation dependent +// // Regression for HARMONY-262 +// ReusableKey k = new ReusableKey(); +// Hashtable h2 = new Hashtable(); +// k.setKey(1); +// h2.put(k, "value1"); +// +// k.setKey(13); +// assertNull(h2.get(k)); +// +// k.setKey(12); +// assertNull(h2.get(k)); +// +// try { +// h2.get(null); +// fail("NullPointerException expected"); +// } catch (NullPointerException e) { +// //expected +// } +// END android-removed } /** @@ -569,9 +595,12 @@ public class HashtableTest extends junit.framework.TestCase { assertTrue("Returned incorrect key set", s .contains(e.nextElement())); - assertEquals("Not synchronized", - "java.util.Collections$SynchronizedSet", s.getClass().getName()); - +// BEGIN android-removed +// implementation dependent +// assertEquals("Not synchronized", +// "java.util.Collections$SynchronizedSet", s.getClass().getName()); +// END android-removed + Map map = new Hashtable(101); map.put(new Integer(1), "1"); map.put(new Integer(102), "102"); @@ -651,54 +680,57 @@ public class HashtableTest extends junit.framework.TestCase { } } - /** - * @tests java.util.Hashtable#keySet() - */ - @TestTargetNew( - level = TestLevel.PARTIAL_COMPLETE, - notes = "", - method = "keySet", - args = {} - ) - public void test_keySet_subtest1() { - // this is the reference implementation behavior - final Hashtable ht = new Hashtable(7); - ht.put("1", "a"); - // these three elements hash to the same bucket in a 7 element Hashtable - ht.put("2", "b"); - ht.put("9", "c"); - ht.put("12", "d"); - // Hashtable looks like: - // 0: "1" - // 1: "12" -> "9" -> "2" - Enumeration en = ht.elements(); - // cache the first entry - en.hasMoreElements(); - Iterator it = ht.keySet().iterator(); - // this is mostly a copy of the test in test_elements_subtest0() - // test removing with the iterator does not null the values - while (it.hasNext()) { - String key = (String) it.next(); - if ("12".equals(key) || "9".equals(key)) { - it.remove(); - } - } - it.remove(); - boolean exception = false; - try { - // cached "12" - Object result = en.nextElement(); - assertTrue("unexpected: " + result, "d".equals(result)); - // next is removed "9" - result = en.nextElement(); - assertTrue("unexpected: " + result, "c".equals(result)); - result = en.nextElement(); - assertTrue("unexpected: " + result, "b".equals(result)); - } catch (NoSuchElementException e) { - exception = true; - } - assertTrue("unexpected NoSuchElementException", !exception); - } +// BEGIN android-removed +// implementation dependent +// /** +// * @tests java.util.Hashtable#keySet() +// */ +// @TestTargetNew( +// level = TestLevel.PARTIAL_COMPLETE, +// notes = "", +// method = "keySet", +// args = {} +// ) +// public void test_keySet_subtest1() { +// // this is the reference implementation behavior +// final Hashtable ht = new Hashtable(7); +// ht.put("1", "a"); +// // these three elements hash to the same bucket in a 7 element Hashtable +// ht.put("2", "b"); +// ht.put("9", "c"); +// ht.put("12", "d"); +// // Hashtable looks like: +// // 0: "1" +// // 1: "12" -> "9" -> "2" +// Enumeration en = ht.elements(); +// // cache the first entry +// en.hasMoreElements(); +// Iterator it = ht.keySet().iterator(); +// // this is mostly a copy of the test in test_elements_subtest0() +// // test removing with the iterator does not null the values +// while (it.hasNext()) { +// String key = (String) it.next(); +// if ("12".equals(key) || "9".equals(key)) { +// it.remove(); +// } +// } +// it.remove(); +// boolean exception = false; +// try { +// // cached "12" +// Object result = en.nextElement(); +// assertTrue("unexpected: " + result, "d".equals(result)); +// // next is removed "9" +// result = en.nextElement(); +// assertTrue("unexpected: " + result, "c".equals(result)); +// result = en.nextElement(); +// assertTrue("unexpected: " + result, "b".equals(result)); +// } catch (NoSuchElementException e) { +// exception = true; +// } +// assertTrue("unexpected NoSuchElementException", !exception); +// } +// END android-removed /** * @tests java.util.Hashtable#put(java.lang.Object, java.lang.Object) @@ -871,9 +903,12 @@ public class HashtableTest extends junit.framework.TestCase { while (e.hasMoreElements()) assertTrue("Returned incorrect values", c.contains(e.nextElement())); - assertEquals("Not synchronized", - "java.util.Collections$SynchronizedCollection", c.getClass().getName()); - +// BEGIN android-removed +// implementation dependent +// assertEquals("Not synchronized", +// "java.util.Collections$SynchronizedCollection", c.getClass().getName()); +// END android-removed + Hashtable myHashtable = new Hashtable(); for (int i = 0; i < 100; i++) myHashtable.put(new Integer(i), new Integer(i)); diff --git a/luni/src/test/java/tests/api/java/util/LinkedHashMapTest.java b/luni/src/test/java/tests/api/java/util/LinkedHashMapTest.java index bfa474b..f3d0a7b 100644 --- a/luni/src/test/java/tests/api/java/util/LinkedHashMapTest.java +++ b/luni/src/test/java/tests/api/java/util/LinkedHashMapTest.java @@ -209,6 +209,26 @@ public class LinkedHashMapTest extends junit.framework.TestCase { new Integer(0))); } + + @TestTargetNew( + level = TestLevel.PARTIAL_COMPLETE, + notes = "test that put on an already present key causes entry to move to tail.", + method = "put", + args = {java.lang.Object.class, java.lang.Object.class} + ) + public void test_putPresent() { + Map<String, String> m = new LinkedHashMap<String, String>(8, .75f, true); + m.put("KEY", "VALUE"); + m.put("WOMBAT", "COMBAT"); + m.put("KEY", "VALUE"); + Map.Entry newest = null; + for (Map.Entry<String, String> e : m.entrySet()) { + newest = e; + } + assertEquals("KEY", newest.getKey()); + assertEquals("VALUE", newest.getValue()); + } + /** * @tests java.util.LinkedHashMap#putAll(java.util.Map) */ @@ -275,6 +295,26 @@ public class LinkedHashMapTest extends junit.framework.TestCase { } } + @TestTargetNew( + level = TestLevel.COMPLETE, + notes = "Test that remove removes the entry from the linked list", + method = "entrySet", + args = {} + ) + public void test_entrySetRemove() { + entrySetRemoveHelper("military", "intelligence"); + entrySetRemoveHelper(null, "hypothesis"); + } + private void entrySetRemoveHelper(String key, String value) { + Map<String, String> m1 = new LinkedHashMap<String, String>(); + m1.put(key, value); + m1.put("jumbo", "shrimp"); + LinkedHashMap<String, String> m2 = new LinkedHashMap<String, String>(m1); + Set<Map.Entry<String, String>> s1 = m1.entrySet(); + s1.remove(m2.entrySet().iterator().next()); + assertEquals("jumbo", s1.iterator().next().getKey()); + } + /** * @tests java.util.LinkedHashMap#keySet() */ |