diff options
27 files changed, 2892 insertions, 2129 deletions
diff --git a/luni-kernel/src/main/java/java/lang/Class.java b/luni-kernel/src/main/java/java/lang/Class.java index 6adf4db..b8e3903 100644 --- a/luni-kernel/src/main/java/java/lang/Class.java +++ b/luni-kernel/src/main/java/java/lang/Class.java @@ -469,6 +469,7 @@ public final class Class<T> implements Serializable, AnnotatedElement, GenericDe * * @param parameterTypes * the parameter types of the requested constructor. + * {@code (Class[]) null} is equivalent to the empty array. * @return the constructor described by {@code parameterTypes}. * @throws NoSuchMethodException * if the constructor can not be found. @@ -587,6 +588,7 @@ public final class Class<T> implements Serializable, AnnotatedElement, GenericDe * * @param parameterTypes * the parameter types of the requested constructor. + * {@code (Class[]) null} is equivalent to the empty array. * @return the constructor described by {@code parameterTypes}. * @throws NoSuchMethodException * if the requested constructor can not be found. @@ -659,12 +661,14 @@ public final class Class<T> implements Serializable, AnnotatedElement, GenericDe sb.append(getSimpleName()); sb.append('('); boolean first = true; - for (Class<?> p : parameterTypes) { - if (!first) { - sb.append(','); + if (parameterTypes != null) { + for (Class<?> p : parameterTypes) { + if (!first) { + sb.append(','); + } + first = false; + sb.append(p.getSimpleName()); } - first = false; - sb.append(p.getSimpleName()); } sb.append(')'); throw new NoSuchMethodException(sb.toString()); @@ -741,6 +745,7 @@ public final class Class<T> implements Serializable, AnnotatedElement, GenericDe * the requested method's name. * @param parameterTypes * the parameter types of the requested method. + * {@code (Class[]) null} is equivalent to the empty array. * @return the method described by {@code name} and {@code parameterTypes}. * @throws NoSuchMethodException * if the requested constructor can not be found. @@ -991,6 +996,7 @@ public final class Class<T> implements Serializable, AnnotatedElement, GenericDe * the requested method's name. * @param parameterTypes * the parameter types of the requested method. + * {@code (Class[]) null} is equivalent to the empty array. * @return the public field specified by {@code name}. * @throws NoSuchMethodException * if the method can not be found. diff --git a/luni-kernel/src/main/java/java/lang/Thread.java b/luni-kernel/src/main/java/java/lang/Thread.java index 484c258..4f9f988 100644 --- a/luni-kernel/src/main/java/java/lang/Thread.java +++ b/luni-kernel/src/main/java/java/lang/Thread.java @@ -922,9 +922,7 @@ public class Thread implements Runnable { * @since Android 1.0 */ public final boolean isAlive() { - Thread.State state = getState(); - - return (state != Thread.State.TERMINATED && state != Thread.State.NEW); + return (vmThread != null); } /** 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() */ diff --git a/regex/src/main/java/java/util/regex/Pattern.java b/regex/src/main/java/java/util/regex/Pattern.java index c058db8..2853bbe 100644 --- a/regex/src/main/java/java/util/regex/Pattern.java +++ b/regex/src/main/java/java/util/regex/Pattern.java @@ -356,28 +356,33 @@ public final class Pattern implements Serializable { } /** - * Splits the given input sequence around occurrences of the {@code Pattern}. - * The function first determines all occurrences of the {@code Pattern} - * inside the input sequence. It then builds an array of the - * "remaining" strings before, in-between, and after these - * occurrences. An additional parameter determines the maximal number of - * entries in the resulting array and the handling of trailing empty - * strings. + * Splits the given input sequence at occurrences of this {@code Pattern}. + * + * If this {@code Pattern} does not occur in the input, the result is an + * array containing the input (converted from a {@code CharSequence} to + * a {@code String}). + * + * Otherwise, the {@code limit} parameter controls the contents of the + * returned array as described below. * * @param inputSeq * the input sequence. * @param limit - * Determines the maximal number of entries in the resulting - * array. + * Determines the maximum number of entries in the resulting + * array, and the treatment of trailing empty strings. * <ul> - * <li>For n > 0, it is guaranteed that the resulting array - * contains at most n entries. + * <li>For n > 0, the resulting array contains at most n + * entries. If this is fewer than the number of matches, the + * final entry will contain all remaining input. * <li>For n < 0, the length of the resulting array is - * exactly the number of occurrences of the {@code Pattern} +1. + * exactly the number of occurrences of the {@code Pattern} + * plus one for the text after the final separator. * All entries are included. - * <li>For n == 0, the length of the resulting array is at most - * the number of occurrences of the {@code Pattern} +1. Empty - * strings at the end of the array are not included. + * <li>For n == 0, the result is as for n < 0, except + * trailing empty strings will not be returned. (Note that + * the case where the input is itself an empty string is + * special, as described above, and the limit parameter does + * not apply there.) * </ul> * * @return the resulting array. @@ -385,6 +390,13 @@ public final class Pattern implements Serializable { * @since Android 1.0 */ public String[] split(CharSequence inputSeq, int limit) { + if (inputSeq.length() == 0) { + // Unlike Perl, which considers the result of splitting the empty + // string to be the empty array, Java returns an array containing + // the empty string. + return new String[] { "" }; + } + int maxLength = limit <= 0 ? Integer.MAX_VALUE : limit; String input = inputSeq.toString(); @@ -393,14 +405,10 @@ public final class Pattern implements Serializable { Matcher matcher = new Matcher(this, inputSeq); int savedPos = 0; - // Add text preceding each occurrence, if enough space. Only do this for - // non-empty input sequences, because otherwise we'd add the "trailing - // empty string" twice. - if (inputSeq.length() != 0) { - while(matcher.find() && list.size() + 1 < maxLength) { - list.add(input.substring(savedPos, matcher.start())); - savedPos = matcher.end(); - } + // Add text preceding each occurrence, if enough space. + while(matcher.find() && list.size() + 1 < maxLength) { + list.add(input.substring(savedPos, matcher.start())); + savedPos = matcher.end(); } // Add trailing text if enough space. @@ -412,11 +420,10 @@ public final class Pattern implements Serializable { } } - // Remove trailing spaces, if limit == 0 is requested. + // Remove trailing empty matches in the limit == 0 case. if (limit == 0) { int i = list.size() - 1; - // Don't remove 1st element, since array must not be empty. - while(i > 0 && "".equals(list.get(i))) { + while (i >= 0 && "".equals(list.get(i))) { list.remove(i); i--; } diff --git a/regex/src/test/java/org/apache/harmony/regex/tests/java/util/regex/SplitTest.java b/regex/src/test/java/org/apache/harmony/regex/tests/java/util/regex/SplitTest.java index ea615c0..894dfff 100644 --- a/regex/src/test/java/org/apache/harmony/regex/tests/java/util/regex/SplitTest.java +++ b/regex/src/test/java/org/apache/harmony/regex/tests/java/util/regex/SplitTest.java @@ -32,12 +32,62 @@ public class SplitTest extends TestCase { Pattern p = Pattern.compile("/"); String[] results = p.split("have/you/done/it/right"); String[] expected = new String[] { "have", "you", "done", "it", "right" }; - assertEquals(expected.length, results.length); + assertArraysEqual(expected, results); + } + + @TestTargets({ + @TestTargetNew( + level = TestLevel.PARTIAL_COMPLETE, + notes = "Verifies the basic functionality of split with empty matches.", + method = "split", + args = {java.lang.CharSequence.class} + ) + }) + public void testEmptySplits() { + // Trailing empty matches are removed. + assertArraysEqual(new String[0], "hello".split(".")); + assertArraysEqual(new String[] { "1", "2" }, "1:2:".split(":")); + // ...including when that results in an empty result. + assertArraysEqual(new String[0], ":".split(":")); + // ...but not when limit < 0. + assertArraysEqual(new String[] { "1", "2", "" }, "1:2:".split(":", -1)); + + // Leading empty matches are retained. + assertArraysEqual(new String[] { "", "", "o" }, "hello".split("..")); + + // A separator that doesn't occur in the input gets you the input. + assertArraysEqual(new String[] { "hello" }, "hello".split("not-present-in-test")); + // ...including when the input is the empty string. + // (Perl returns an empty list instead.) + assertArraysEqual(new String[] { "" }, "".split("not-present-in-test")); + assertArraysEqual(new String[] { "" }, "".split("A?")); + + // The limit argument controls the size of the result. + // If l == 0, the result is as long as needed, except trailing empty matches are dropped. + // If l < 0, the result is as long as needed, and trailing empty matches are retained. + // If l > 0, the result contains the first l matches, plus one string containing the remaining input. + // Examples without a trailing separator (and hence without a trailing empty match): + assertArraysEqual(new String[] { "a", "b", "c" }, "a,b,c".split(",", 0)); + assertArraysEqual(new String[] { "a,b,c" }, "a,b,c".split(",", 1)); + assertArraysEqual(new String[] { "a", "b,c" }, "a,b,c".split(",", 2)); + assertArraysEqual(new String[] { "a", "b", "c" }, "a,b,c".split(",", 3)); + assertArraysEqual(new String[] { "a", "b", "c" }, "a,b,c".split(",", Integer.MAX_VALUE)); + // Examples with a trailing separator (and hence possibly with a trailing empty match): + assertArraysEqual(new String[] { "a", "b", "c" }, "a,b,c,".split(",", 0)); + assertArraysEqual(new String[] { "a,b,c," }, "a,b,c,".split(",", 1)); + assertArraysEqual(new String[] { "a", "b,c," }, "a,b,c,".split(",", 2)); + assertArraysEqual(new String[] { "a", "b", "c," }, "a,b,c,".split(",", 3)); + assertArraysEqual(new String[] { "a", "b", "c", "" }, "a,b,c,".split(",", Integer.MAX_VALUE)); + assertArraysEqual(new String[] { "a", "b", "c", "" }, "a,b,c,".split(",", -1)); + } + + private void assertArraysEqual(String[] expected, String[] actual) { + assertEquals(expected.length, actual.length); for (int i = 0; i < expected.length; i++) { - assertEquals(results[i], expected[i]); + assertEquals(Integer.toString(i), expected[i], actual[i]); } } - + @TestTargetNew( level = TestLevel.PARTIAL_COMPLETE, notes = "Verifies the functionality of split(java.lang.CharSequence). Test uses not empty pattern.", diff --git a/security/src/main/files/cacerts.bks b/security/src/main/files/cacerts.bks Binary files differindex bbcc080..36f4919 100644 --- a/security/src/main/files/cacerts.bks +++ b/security/src/main/files/cacerts.bks diff --git a/security/src/main/files/cacerts/3e7271e8.0 b/security/src/main/files/cacerts/3e7271e8.0 new file mode 100644 index 0000000..62b5b22 --- /dev/null +++ b/security/src/main/files/cacerts/3e7271e8.0 @@ -0,0 +1,85 @@ +Certificate: + Data: + Version: 3 (0x2) + Serial Number: 946059622 (0x3863b966) + Signature Algorithm: sha1WithRSAEncryption + Issuer: O=Entrust.net, OU=www.entrust.net/CPS_2048 incorp. by ref. (limits liab.), OU=(c) 1999 Entrust.net Limited, CN=Entrust.net Certification Authority (2048) + Validity + Not Before: Dec 24 17:50:51 1999 GMT + Not After : Dec 24 18:20:51 2019 GMT + Subject: O=Entrust.net, OU=www.entrust.net/CPS_2048 incorp. by ref. (limits liab.), OU=(c) 1999 Entrust.net Limited, CN=Entrust.net Certification Authority (2048) + Subject Public Key Info: + Public Key Algorithm: rsaEncryption + RSA Public Key: (2048 bit) + Modulus (2048 bit): + 00:ad:4d:4b:a9:12:86:b2:ea:a3:20:07:15:16:64: + 2a:2b:4b:d1:bf:0b:4a:4d:8e:ed:80:76:a5:67:b7: + 78:40:c0:73:42:c8:68:c0:db:53:2b:dd:5e:b8:76: + 98:35:93:8b:1a:9d:7c:13:3a:0e:1f:5b:b7:1e:cf: + e5:24:14:1e:b1:81:a9:8d:7d:b8:cc:6b:4b:03:f1: + 02:0c:dc:ab:a5:40:24:00:7f:74:94:a1:9d:08:29: + b3:88:0b:f5:87:77:9d:55:cd:e4:c3:7e:d7:6a:64: + ab:85:14:86:95:5b:97:32:50:6f:3d:c8:ba:66:0c: + e3:fc:bd:b8:49:c1:76:89:49:19:fd:c0:a8:bd:89: + a3:67:2f:c6:9f:bc:71:19:60:b8:2d:e9:2c:c9:90: + 76:66:7b:94:e2:af:78:d6:65:53:5d:3c:d6:9c:b2: + cf:29:03:f9:2f:a4:50:b2:d4:48:ce:05:32:55:8a: + fd:b2:64:4c:0e:e4:98:07:75:db:7f:df:b9:08:55: + 60:85:30:29:f9:7b:48:a4:69:86:e3:35:3f:1e:86: + 5d:7a:7a:15:bd:ef:00:8e:15:22:54:17:00:90:26: + 93:bc:0e:49:68:91:bf:f8:47:d3:9d:95:42:c1:0e: + 4d:df:6f:26:cf:c3:18:21:62:66:43:70:d6:d5:c0: + 07:e1 + Exponent: 65537 (0x10001) + X509v3 extensions: + Netscape Cert Type: + SSL CA, S/MIME CA, Object Signing CA + X509v3 Authority Key Identifier: + keyid:55:E4:81:D1:11:80:BE:D8:89:B9:08:A3:31:F9:A1:24:09:16:B9:70 + + X509v3 Subject Key Identifier: + 55:E4:81:D1:11:80:BE:D8:89:B9:08:A3:31:F9:A1:24:09:16:B9:70 + 1.2.840.113533.7.65.0: + 0...V5.0:4.0.... + Signature Algorithm: sha1WithRSAEncryption + 59:47:ac:21:84:8a:17:c9:9c:89:53:1e:ba:80:85:1a:c6:3c: + 4e:3e:b1:9c:b6:7c:c6:92:5d:18:64:02:e3:d3:06:08:11:61: + 7c:63:e3:2b:9d:31:03:70:76:d2:a3:28:a0:f4:bb:9a:63:73: + ed:6d:e5:2a:db:ed:14:a9:2b:c6:36:11:d0:2b:eb:07:8b:a5: + da:9e:5c:19:9d:56:12:f5:54:29:c8:05:ed:b2:12:2a:8d:f4: + 03:1b:ff:e7:92:10:87:b0:3a:b5:c3:9d:05:37:12:a3:c7:f4: + 15:b9:d5:a4:39:16:9b:53:3a:23:91:f1:a8:82:a2:6a:88:68: + c1:79:02:22:bc:aa:a6:d6:ae:df:b0:14:5f:b8:87:d0:dd:7c: + 7f:7b:ff:af:1c:cf:e6:db:07:ad:5e:db:85:9d:d0:2b:0d:33: + db:04:d1:e6:49:40:13:2b:76:fb:3e:e9:9c:89:0f:15:ce:18: + b0:85:78:21:4f:6b:4f:0e:fa:36:67:cd:07:f2:ff:08:d0:e2: + de:d9:bf:2a:af:b8:87:86:21:3c:04:ca:b7:94:68:7f:cf:3c: + e9:98:d7:38:ff:ec:c0:d9:50:f0:2e:4b:58:ae:46:6f:d0:2e: + c3:60:da:72:55:72:bd:4c:45:9e:61:ba:bf:84:81:92:03:d1: + d2:69:7c:c5 +-----BEGIN CERTIFICATE----- +MIIEXDCCA0SgAwIBAgIEOGO5ZjANBgkqhkiG9w0BAQUFADCBtDEUMBIGA1UEChML +RW50cnVzdC5uZXQxQDA+BgNVBAsUN3d3dy5lbnRydXN0Lm5ldC9DUFNfMjA0OCBp +bmNvcnAuIGJ5IHJlZi4gKGxpbWl0cyBsaWFiLikxJTAjBgNVBAsTHChjKSAxOTk5 +IEVudHJ1c3QubmV0IExpbWl0ZWQxMzAxBgNVBAMTKkVudHJ1c3QubmV0IENlcnRp +ZmljYXRpb24gQXV0aG9yaXR5ICgyMDQ4KTAeFw05OTEyMjQxNzUwNTFaFw0xOTEy +MjQxODIwNTFaMIG0MRQwEgYDVQQKEwtFbnRydXN0Lm5ldDFAMD4GA1UECxQ3d3d3 +LmVudHJ1c3QubmV0L0NQU18yMDQ4IGluY29ycC4gYnkgcmVmLiAobGltaXRzIGxp +YWIuKTElMCMGA1UECxMcKGMpIDE5OTkgRW50cnVzdC5uZXQgTGltaXRlZDEzMDEG +A1UEAxMqRW50cnVzdC5uZXQgQ2VydGlmaWNhdGlvbiBBdXRob3JpdHkgKDIwNDgp +MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEArU1LqRKGsuqjIAcVFmQq +K0vRvwtKTY7tgHalZ7d4QMBzQshowNtTK91euHaYNZOLGp18EzoOH1u3Hs/lJBQe +sYGpjX24zGtLA/ECDNyrpUAkAH90lKGdCCmziAv1h3edVc3kw37XamSrhRSGlVuX +MlBvPci6Zgzj/L24ScF2iUkZ/cCovYmjZy/Gn7xxGWC4LeksyZB2ZnuU4q941mVT +XTzWnLLPKQP5L6RQstRIzgUyVYr9smRMDuSYB3Xbf9+5CFVghTAp+XtIpGmG4zU/ +HoZdenoVve8AjhUiVBcAkCaTvA5JaJG/+EfTnZVCwQ5N328mz8MYIWJmQ3DW1cAH +4QIDAQABo3QwcjARBglghkgBhvhCAQEEBAMCAAcwHwYDVR0jBBgwFoAUVeSB0RGA +vtiJuQijMfmhJAkWuXAwHQYDVR0OBBYEFFXkgdERgL7YibkIozH5oSQJFrlwMB0G +CSqGSIb2fQdBAAQQMA4bCFY1LjA6NC4wAwIEkDANBgkqhkiG9w0BAQUFAAOCAQEA +WUesIYSKF8mciVMeuoCFGsY8Tj6xnLZ8xpJdGGQC49MGCBFhfGPjK50xA3B20qMo +oPS7mmNz7W3lKtvtFKkrxjYR0CvrB4ul2p5cGZ1WEvVUKcgF7bISKo30Axv/55IQ +h7A6tcOdBTcSo8f0FbnVpDkWm1M6I5HxqIKiaohowXkCIryqptau37AUX7iH0N18 +f3v/rxzP5tsHrV7bhZ3QKw0z2wTR5klAEyt2+z7pnIkPFc4YsIV4IU9rTw76NmfN +B/L/CNDi3tm/Kq+4h4YhPATKt5Rof8886ZjXOP/swNlQ8C5LWK5Gb9Auw2DaclVy +vUxFnmG6v4SBkgPR0ml8xQ== +-----END CERTIFICATE----- diff --git a/security/src/main/files/cacerts/ab86d4de.0 b/security/src/main/files/cacerts/ab86d4de.0 new file mode 100644 index 0000000..c6f241f --- /dev/null +++ b/security/src/main/files/cacerts/ab86d4de.0 @@ -0,0 +1,104 @@ +Certificate: + Data: + Version: 3 (0x2) + Serial Number: 946062766 (0x3863c5ae) + Signature Algorithm: sha1WithRSAEncryption + Issuer: O=Entrust.net, OU=www.entrust.net/CPS_2048 incorp. by ref. (limits liab.), OU=(c) 1999 Entrust.net Limited, CN=Entrust.net Certification Authority (2048) + Validity + Not Before: Aug 25 18:14:26 2008 GMT + Not After : Aug 25 18:44:26 2018 GMT + Subject: C=US, O=Entrust, Inc., OU=AND ADDITIONAL TERMS GOVERNING USE AND RELIANCE, OU=CPS CONTAINS IMPORTANT LIMITATIONS OF WARRANTIES AND LIABILITY, OU=www.entrust.net/CPS is incorporated by reference, OU=(c) 2008 Entrust, Inc., CN=Entrust Certification Authority - L1B + Subject Public Key Info: + Public Key Algorithm: rsaEncryption + RSA Public Key: (2048 bit) + Modulus (2048 bit): + 00:dc:21:f5:68:f9:7a:ce:87:f2:78:df:d8:3b:4d: + 06:7d:c6:24:e4:a9:cd:9d:01:56:e4:f6:71:17:aa: + 7f:75:22:18:e4:74:6d:1b:3e:56:d5:b1:a6:1e:dd: + 59:26:53:ca:06:e6:ba:0b:6f:37:bb:a8:c6:9c:15: + 3b:06:1b:87:0c:c2:1a:4d:d3:81:ae:db:50:65:a5: + 3a:64:4f:30:34:9a:2b:a9:1f:fd:2b:d1:38:71:19: + 68:f2:8e:eb:7b:c9:40:3c:48:c4:19:b1:b7:10:25: + ef:44:a7:e6:77:9b:7d:22:9a:de:d8:5e:d9:c3:ce: + c9:71:22:bb:ae:ef:05:d6:f2:17:e7:56:78:e1:53: + 05:4a:26:73:b8:c7:49:67:93:23:0f:56:b2:8f:dd: + c9:59:05:e5:63:15:b4:87:7e:40:46:e9:b5:00:7b: + 03:b4:0d:e4:96:67:2c:de:1b:59:0b:1a:1f:b8:63: + 44:ae:c1:d7:44:87:c4:91:59:9c:00:43:6d:c6:df: + 0a:b0:b1:04:cd:fe:be:30:5e:3a:25:72:dd:a2:3e: + ed:46:3a:c7:a4:5c:5c:e4:25:f2:13:07:e8:ae:da: + 9b:19:9b:a2:d9:60:9d:ce:90:47:6a:61:7b:40:e8: + 14:c2:fe:2f:84:5a:66:17:c0:97:d3:49:38:de:63: + 02:9f + Exponent: 65537 (0x10001) + X509v3 extensions: + X509v3 Key Usage: critical + Certificate Sign, CRL Sign + X509v3 Basic Constraints: critical + CA:TRUE + Authority Information Access: + OCSP - URI:http://ocsp.entrust.net + + X509v3 CRL Distribution Points: + URI:http://crl.entrust.net/2048ca.crl + + X509v3 Certificate Policies: + Policy: X509v3 Any Policy + CPS: http://www.entrust.net/CPS + + X509v3 Subject Key Identifier: + F5:F2:96:88:7D:0D:F3:2A:F9:4E:E7:34:A0:BD:46:7E:13:D6:16:C8 + X509v3 Authority Key Identifier: + keyid:55:E4:81:D1:11:80:BE:D8:89:B9:08:A3:31:F9:A1:24:09:16:B9:70 + + 1.2.840.113533.7.65.0: + 0 +..V7.1.... + Signature Algorithm: sha1WithRSAEncryption + 0b:25:3c:58:fa:8e:dc:a2:42:3b:76:71:6e:6c:d4:4f:2b:b9: + 53:5c:b2:58:b9:b1:dc:6f:1a:e4:e3:c4:50:f2:41:82:ba:f4: + 7d:c7:c1:f9:fa:8c:53:bf:b9:62:b7:49:e3:1d:0a:fc:1f:d6: + c4:76:6a:93:cb:77:1e:2c:7f:d0:3f:16:63:4c:72:4c:67:60: + 0f:f8:80:d6:a7:9a:ca:a2:33:91:0f:44:b2:66:3d:8e:68:0c: + 40:85:12:37:91:b9:82:77:34:59:2d:5c:df:82:6e:2c:b6:7a: + d2:04:90:67:68:4b:70:fc:2d:b8:ff:90:64:6f:7e:91:f7:d1: + 47:33:f3:5b:b8:58:2e:21:d8:75:60:1b:13:cc:f8:b2:a8:fa: + 6a:a9:2a:5a:4f:45:85:40:b4:dd:34:05:b7:70:ca:01:ef:e1: + 81:e7:11:50:db:3e:e2:d7:10:2e:6a:15:7f:b7:d4:a3:62:b2: + 89:69:61:57:c6:7f:8e:9e:d4:24:7a:f3:a1:43:5f:a0:7a:89: + dc:59:cd:7d:d7:75:a7:bc:53:d5:47:35:c6:31:30:20:9f:9b: + ba:b5:83:e6:89:55:01:4d:91:3b:d6:89:35:87:3c:83:6b:7a: + 29:82:d4:4b:d4:e6:16:74:b0:01:10:ab:69:06:14:37:7b:f7: + 66:30:3a:c5 +-----BEGIN CERTIFICATE----- +MIIFkTCCBHmgAwIBAgIEOGPFrjANBgkqhkiG9w0BAQUFADCBtDEUMBIGA1UEChML +RW50cnVzdC5uZXQxQDA+BgNVBAsUN3d3dy5lbnRydXN0Lm5ldC9DUFNfMjA0OCBp +bmNvcnAuIGJ5IHJlZi4gKGxpbWl0cyBsaWFiLikxJTAjBgNVBAsTHChjKSAxOTk5 +IEVudHJ1c3QubmV0IExpbWl0ZWQxMzAxBgNVBAMTKkVudHJ1c3QubmV0IENlcnRp +ZmljYXRpb24gQXV0aG9yaXR5ICgyMDQ4KTAeFw0wODA4MjUxODE0MjZaFw0xODA4 +MjUxODQ0MjZaMIIBNDELMAkGA1UEBhMCVVMxFjAUBgNVBAoTDUVudHJ1c3QsIElu +Yy4xODA2BgNVBAsTL0FORCBBRERJVElPTkFMIFRFUk1TIEdPVkVSTklORyBVU0Ug +QU5EIFJFTElBTkNFMUcwRQYDVQQLEz5DUFMgQ09OVEFJTlMgSU1QT1JUQU5UIExJ +TUlUQVRJT05TIE9GIFdBUlJBTlRJRVMgQU5EIExJQUJJTElUWTE5MDcGA1UECxMw +d3d3LmVudHJ1c3QubmV0L0NQUyBpcyBpbmNvcnBvcmF0ZWQgYnkgcmVmZXJlbmNl +MR8wHQYDVQQLExYoYykgMjAwOCBFbnRydXN0LCBJbmMuMS4wLAYDVQQDEyVFbnRy +dXN0IENlcnRpZmljYXRpb24gQXV0aG9yaXR5IC0gTDFCMIIBIjANBgkqhkiG9w0B +AQEFAAOCAQ8AMIIBCgKCAQEA3CH1aPl6zofyeN/YO00GfcYk5KnNnQFW5PZxF6p/ +dSIY5HRtGz5W1bGmHt1ZJlPKBua6C283u6jGnBU7BhuHDMIaTdOBrttQZaU6ZE8w +NJorqR/9K9E4cRlo8o7re8lAPEjEGbG3ECXvRKfmd5t9Ipre2F7Zw87JcSK7ru8F +1vIX51Z44VMFSiZzuMdJZ5MjD1ayj93JWQXlYxW0h35ARum1AHsDtA3klmcs3htZ +CxofuGNErsHXRIfEkVmcAENtxt8KsLEEzf6+MF46JXLdoj7tRjrHpFxc5CXyEwfo +rtqbGZui2WCdzpBHamF7QOgUwv4vhFpmF8CX00k43mMCnwIDAQABo4IBJjCCASIw +DgYDVR0PAQH/BAQDAgEGMA8GA1UdEwEB/wQFMAMBAf8wMwYIKwYBBQUHAQEEJzAl +MCMGCCsGAQUFBzABhhdodHRwOi8vb2NzcC5lbnRydXN0Lm5ldDAyBgNVHR8EKzAp +MCegJaAjhiFodHRwOi8vY3JsLmVudHJ1c3QubmV0LzIwNDhjYS5jcmwwOwYDVR0g +BDQwMjAwBgRVHSAAMCgwJgYIKwYBBQUHAgEWGmh0dHA6Ly93d3cuZW50cnVzdC5u +ZXQvQ1BTMB0GA1UdDgQWBBT18paIfQ3zKvlO5zSgvUZ+E9YWyDAfBgNVHSMEGDAW +gBRV5IHREYC+2Im5CKMx+aEkCRa5cDAZBgkqhkiG9n0HQQAEDDAKGwRWNy4xAwIA +gTANBgkqhkiG9w0BAQUFAAOCAQEACyU8WPqO3KJCO3ZxbmzUTyu5U1yyWLmx3G8a +5OPEUPJBgrr0fcfB+fqMU7+5YrdJ4x0K/B/WxHZqk8t3Hix/0D8WY0xyTGdgD/iA +1qeayqIzkQ9EsmY9jmgMQIUSN5G5gnc0WS1c34JuLLZ60gSQZ2hLcPwtuP+QZG9+ +kffRRzPzW7hYLiHYdWAbE8z4sqj6aqkqWk9FhUC03TQFt3DKAe/hgecRUNs+4tcQ +LmoVf7fUo2KyiWlhV8Z/jp7UJHrzoUNfoHqJ3FnNfdd1p7xT1Uc1xjEwIJ+burWD +5olVAU2RO9aJNYc8g2t6KYLUS9TmFnSwARCraQYUN3v3ZjA6xQ== +-----END CERTIFICATE----- diff --git a/security/src/main/files/cacerts/b0f3e76e.0 b/security/src/main/files/cacerts/b0f3e76e.0 index 05ce1ec..386b70a 100644 --- a/security/src/main/files/cacerts/b0f3e76e.0 +++ b/security/src/main/files/cacerts/b0f3e76e.0 @@ -2,12 +2,12 @@ Certificate: Data: Version: 3 (0x2) Serial Number: - 02:00:00:00:00:00:d6:78:b7:94:05 - Signature Algorithm: md5WithRSAEncryption + 04:00:00:00:00:01:15:4b:5a:c3:94 + Signature Algorithm: sha1WithRSAEncryption Issuer: C=BE, O=GlobalSign nv-sa, OU=Root CA, CN=GlobalSign Root CA Validity Not Before: Sep 1 12:00:00 1998 GMT - Not After : Jan 28 12:00:00 2014 GMT + Not After : Jan 28 12:00:00 2028 GMT Subject: C=BE, O=GlobalSign nv-sa, OU=Root CA, CN=GlobalSign Root CA Subject Public Key Info: Public Key Algorithm: rsaEncryption @@ -35,32 +35,31 @@ Certificate: X509v3 extensions: X509v3 Key Usage: critical Certificate Sign, CRL Sign - X509v3 Subject Key Identifier: - 60:7B:66:1A:45:0D:97:CA:89:50:2F:7D:04:CD:34:A8:FF:FC:FD:4B X509v3 Basic Constraints: critical CA:TRUE - Signature Algorithm: md5WithRSAEncryption - ae:aa:9f:fc:b7:d2:cb:1f:5f:39:29:28:18:9e:34:c9:6c:4f: - 6f:1a:f0:64:a2:70:4a:4f:13:86:9b:60:28:9e:e8:81:49:98: - 7d:0a:bb:e5:b0:9d:3d:36:db:8f:05:51:ff:09:31:2a:1f:dd: - 89:77:9e:0f:2e:6c:95:04:ed:86:cb:b4:00:3f:84:02:4d:80: - 6a:2a:2d:78:0b:ae:6f:2b:a2:83:44:83:1f:cd:50:82:4c:24: - af:bd:f7:a5:b4:c8:5a:0f:f4:e7:47:5e:49:8e:37:96:fe:9a: - 88:05:3a:d9:c0:db:29:87:e6:19:96:47:a7:3a:a6:8c:8b:3c: - 77:fe:46:63:a7:53:da:21:d1:ac:7e:49:a2:4b:e6:c3:67:59: - 2f:b3:8a:0e:bb:2c:bd:a9:aa:42:7c:35:c1:d8:7f:d5:a7:31: - 3a:4e:63:43:39:af:08:b0:61:34:8c:d3:98:a9:43:34:f6:0f: - 87:29:3b:9d:c2:56:58:98:77:c3:f7:1b:ac:f6:9d:f8:3e:aa: - a7:54:45:f0:f5:f9:d5:31:65:fe:6b:58:9c:71:b3:1e:d7:52: - ea:32:17:fc:40:60:1d:c9:79:24:b2:f6:6c:fd:a8:66:0e:82: - dd:98:cb:da:c2:44:4f:2e:a0:7b:f2:f7:6b:2c:76:11:84:46: - 8a:78:a3:e3 -SHA1 Fingerprint=2F:17:3F:7D:E9:96:67:AF:A5:7A:F8:0A:A2:D1:B1:2F:AC:83:03:38 + X509v3 Subject Key Identifier: + 60:7B:66:1A:45:0D:97:CA:89:50:2F:7D:04:CD:34:A8:FF:FC:FD:4B + Signature Algorithm: sha1WithRSAEncryption + d6:73:e7:7c:4f:76:d0:8d:bf:ec:ba:a2:be:34:c5:28:32:b5: + 7c:fc:6c:9c:2c:2b:bd:09:9e:53:bf:6b:5e:aa:11:48:b6:e5: + 08:a3:b3:ca:3d:61:4d:d3:46:09:b3:3e:c3:a0:e3:63:55:1b: + f2:ba:ef:ad:39:e1:43:b9:38:a3:e6:2f:8a:26:3b:ef:a0:50: + 56:f9:c6:0a:fd:38:cd:c4:0b:70:51:94:97:98:04:df:c3:5f: + 94:d5:15:c9:14:41:9c:c4:5d:75:64:15:0d:ff:55:30:ec:86: + 8f:ff:0d:ef:2c:b9:63:46:f6:aa:fc:df:bc:69:fd:2e:12:48: + 64:9a:e0:95:f0:a6:ef:29:8f:01:b1:15:b5:0c:1d:a5:fe:69: + 2c:69:24:78:1e:b3:a7:1c:71:62:ee:ca:c8:97:ac:17:5d:8a: + c2:f8:47:86:6e:2a:c4:56:31:95:d0:67:89:85:2b:f9:6c:a6: + 5d:46:9d:0c:aa:82:e4:99:51:dd:70:b7:db:56:3d:61:e4:6a: + e1:5c:d6:f6:fe:3d:de:41:cc:07:ae:63:52:bf:53:53:f4:2b: + e9:c7:fd:b6:f7:82:5f:85:d2:41:18:db:81:b3:04:1c:c5:1f: + a4:80:6f:15:20:c9:de:0c:88:0a:1d:d6:66:55:e2:fc:48:c9: + 29:26:69:e0 -----BEGIN CERTIFICATE----- -MIIDdTCCAl2gAwIBAgILAgAAAAAA1ni3lAUwDQYJKoZIhvcNAQEEBQAwVzELMAkG +MIIDdTCCAl2gAwIBAgILBAAAAAABFUtaw5QwDQYJKoZIhvcNAQEFBQAwVzELMAkG A1UEBhMCQkUxGTAXBgNVBAoTEEdsb2JhbFNpZ24gbnYtc2ExEDAOBgNVBAsTB1Jv b3QgQ0ExGzAZBgNVBAMTEkdsb2JhbFNpZ24gUm9vdCBDQTAeFw05ODA5MDExMjAw -MDBaFw0xNDAxMjgxMjAwMDBaMFcxCzAJBgNVBAYTAkJFMRkwFwYDVQQKExBHbG9i +MDBaFw0yODAxMjgxMjAwMDBaMFcxCzAJBgNVBAYTAkJFMRkwFwYDVQQKExBHbG9i YWxTaWduIG52LXNhMRAwDgYDVQQLEwdSb290IENBMRswGQYDVQQDExJHbG9iYWxT aWduIFJvb3QgQ0EwggEiMA0GCSqGSIb3DQEBAQUAA4IBDwAwggEKAoIBAQDaDuaZ jc6j40+Kfvvxi4Mla+pIH/EqsLmVEQS98GPR4mdmzxzdzxtIK+6NiY6arymAZavp @@ -68,12 +67,12 @@ xy0Sy6scTHAHoT0KMM0VjU/43dSMUBUc71DuxC73/OlS8pF94G3VNTCOXkNz8kHp 1Wrjsok6Vjk4bwY8iGlbKk3Fp1S4bInMm/k8yuX9ifUSPJJ4ltbcdG6TRGHRjcdG snUOhugZitVtbNV4FpWi6cgKOOvyJBNPc1STE4U6G7weNLWLBYy5d4ux2x8gkasJ U26Qzns3dLlwR5EiUWMWea6xrkEmCMgZK9FGqkjWZCrXgzT/LCrBbBlDSgeF59N8 -9iFo7+ryUp9/k5DPAgMBAAGjQjBAMA4GA1UdDwEB/wQEAwIABjAdBgNVHQ4EFgQU -YHtmGkUNl8qJUC99BM00qP/8/UswDwYDVR0TAQH/BAUwAwEB/zANBgkqhkiG9w0B -AQQFAAOCAQEArqqf/LfSyx9fOSkoGJ40yWxPbxrwZKJwSk8ThptgKJ7ogUmYfQq7 -5bCdPTbbjwVR/wkxKh/diXeeDy5slQTthsu0AD+EAk2AaioteAuubyuig0SDH81Q -gkwkr733pbTIWg/050deSY43lv6aiAU62cDbKYfmGZZHpzqmjIs8d/5GY6dT2iHR -rH5Jokvmw2dZL7OKDrssvamqQnw1wdh/1acxOk5jQzmvCLBhNIzTmKlDNPYPhyk7 -ncJWWJh3w/cbrPad+D6qp1RF8PX51TFl/mtYnHGzHtdS6jIX/EBgHcl5JLL2bP2o -Zg6C3ZjL2sJETy6ge/L3ayx2EYRGinij4w== +9iFo7+ryUp9/k5DPAgMBAAGjQjBAMA4GA1UdDwEB/wQEAwIBBjAPBgNVHRMBAf8E +BTADAQH/MB0GA1UdDgQWBBRge2YaRQ2XyolQL30EzTSo//z9SzANBgkqhkiG9w0B +AQUFAAOCAQEA1nPnfE920I2/7LqivjTFKDK1fPxsnCwrvQmeU79rXqoRSLblCKOz +yj1hTdNGCbM+w6DjY1Ub8rrvrTnhQ7k4o+YviiY776BQVvnGCv04zcQLcFGUl5gE +38NflNUVyRRBnMRddWQVDf9VMOyGj/8N7yy5Y0b2qvzfvGn9LhJIZJrglfCm7ymP +AbEVtQwdpf5pLGkkeB6zpxxxYu7KyJesF12KwvhHhm4qxFYxldBniYUr+WymXUad +DKqC5JlR3XC321Y9YeRq4VzW9v493kHMB65jUr9TU/Qr6cf9tveCX4XSQRjbgbME +HMUfpIBvFSDJ3gyICh3WZlXi/EjJKSZp4A== -----END CERTIFICATE----- diff --git a/security/src/main/files/cacerts/bf64f35b.0 b/security/src/main/files/cacerts/bf64f35b.0 new file mode 100644 index 0000000..389623c --- /dev/null +++ b/security/src/main/files/cacerts/bf64f35b.0 @@ -0,0 +1,92 @@ +Certificate: + Data: + Version: 3 (0x2) + Serial Number: 1116155212 (0x42872d4c) + Signature Algorithm: sha1WithRSAEncryption + Issuer: C=US, O=Entrust.net, OU=www.entrust.net/CPS incorp. by ref. (limits liab.), OU=(c) 1999 Entrust.net Limited, CN=Entrust.net Secure Server Certification Authority + Validity + Not Before: Jan 5 19:20:39 2007 GMT + Not After : Jan 5 19:50:39 2017 GMT + Subject: C=US, O=Entrust, Inc., OU=www.entrust.net/CPS is incorporated by reference, OU=(c) 2006 Entrust, Inc., CN=Entrust Root Certification Authority + Subject Public Key Info: + Public Key Algorithm: rsaEncryption + RSA Public Key: (2048 bit) + Modulus (2048 bit): + 00:b6:95:b6:43:42:fa:c6:6d:2a:6f:48:df:94:4c: + 39:57:05:ee:c3:79:11:41:68:36:ed:ec:fe:9a:01: + 8f:a1:38:28:fc:f7:10:46:66:2e:4d:1e:1a:b1:1a: + 4e:c6:d1:c0:95:88:b0:c9:ff:31:8b:33:03:db:b7: + 83:7b:3e:20:84:5e:ed:b2:56:28:a7:f8:e0:b9:40: + 71:37:c5:cb:47:0e:97:2a:68:c0:22:95:62:15:db: + 47:d9:f5:d0:2b:ff:82:4b:c9:ad:3e:de:4c:db:90: + 80:50:3f:09:8a:84:00:ec:30:0a:3d:18:cd:fb:fd: + 2a:59:9a:23:95:17:2c:45:9e:1f:6e:43:79:6d:0c: + 5c:98:fe:48:a7:c5:23:47:5c:5e:fd:6e:e7:1e:b4: + f6:68:45:d1:86:83:5b:a2:8a:8d:b1:e3:29:80:fe: + 25:71:88:ad:be:bc:8f:ac:52:96:4b:aa:51:8d:e4: + 13:31:19:e8:4e:4d:9f:db:ac:b3:6a:d5:bc:39:54: + 71:ca:7a:7a:7f:90:dd:7d:1d:80:d9:81:bb:59:26: + c2:11:fe:e6:93:e2:f7:80:e4:65:fb:34:37:0e:29: + 80:70:4d:af:38:86:2e:9e:7f:57:af:9e:17:ae:eb: + 1c:cb:28:21:5f:b6:1c:d8:e7:a2:04:22:f9:d3:da: + d8:cb + Exponent: 65537 (0x10001) + X509v3 extensions: + X509v3 Key Usage: critical + Certificate Sign, CRL Sign + X509v3 Basic Constraints: critical + CA:TRUE + Authority Information Access: + OCSP - URI:http://ocsp.entrust.net + + X509v3 CRL Distribution Points: + URI:http://crl.entrust.net/server1.crl + + X509v3 Certificate Policies: + Policy: X509v3 Any Policy + CPS: http://www.entrust.net/CPS + + X509v3 Subject Key Identifier: + 68:90:E4:67:A4:A6:53:80:C7:86:66:A4:F1:F7:4B:43:FB:84:BD:6D + X509v3 Authority Key Identifier: + keyid:F0:17:62:13:55:3D:B3:FF:0A:00:6B:FB:50:84:97:F3:ED:62:D0:1A + + 1.2.840.113533.7.65.0: + 0 +..V7.1.... + Signature Algorithm: sha1WithRSAEncryption + 0c:b0:84:7c:2d:13:fe:9a:3d:bf:18:05:95:3d:20:48:a3:16: + 81:87:15:50:15:a4:88:8d:9f:60:d4:3a:6f:eb:2d:6e:3a:86: + a4:a9:d2:c1:9d:89:7a:08:1c:a4:2d:b3:47:8e:0f:64:4a:6f: + 66:03:83:3f:4f:34:94:36:aa:29:6d:8b:8d:02:22:2b:8c:cd: + 77:a5:70:95:86:91:d1:b6:bf:52:be:33:6a:6b:99:f9:6f:e1: + 12:be:04:cb:33:bf:f5:12:1a:4e:44:ba:5b:16:4d:30:b9:f3: + b4:74:ce:6e:f2:68:56:58:dd:d8:a1:fd:54:05:f4:23:91:85: + c9:f9 +-----BEGIN CERTIFICATE----- +MIIEmzCCBASgAwIBAgIEQoctTDANBgkqhkiG9w0BAQUFADCBwzELMAkGA1UEBhMC +VVMxFDASBgNVBAoTC0VudHJ1c3QubmV0MTswOQYDVQQLEzJ3d3cuZW50cnVzdC5u +ZXQvQ1BTIGluY29ycC4gYnkgcmVmLiAobGltaXRzIGxpYWIuKTElMCMGA1UECxMc +KGMpIDE5OTkgRW50cnVzdC5uZXQgTGltaXRlZDE6MDgGA1UEAxMxRW50cnVzdC5u +ZXQgU2VjdXJlIFNlcnZlciBDZXJ0aWZpY2F0aW9uIEF1dGhvcml0eTAeFw0wNzAx +MDUxOTIwMzlaFw0xNzAxMDUxOTUwMzlaMIGwMQswCQYDVQQGEwJVUzEWMBQGA1UE +ChMNRW50cnVzdCwgSW5jLjE5MDcGA1UECxMwd3d3LmVudHJ1c3QubmV0L0NQUyBp +cyBpbmNvcnBvcmF0ZWQgYnkgcmVmZXJlbmNlMR8wHQYDVQQLExYoYykgMjAwNiBF +bnRydXN0LCBJbmMuMS0wKwYDVQQDEyRFbnRydXN0IFJvb3QgQ2VydGlmaWNhdGlv +biBBdXRob3JpdHkwggEiMA0GCSqGSIb3DQEBAQUAA4IBDwAwggEKAoIBAQC2lbZD +QvrGbSpvSN+UTDlXBe7DeRFBaDbt7P6aAY+hOCj89xBGZi5NHhqxGk7G0cCViLDJ +/zGLMwPbt4N7PiCEXu2yViin+OC5QHE3xctHDpcqaMAilWIV20fZ9dAr/4JLya0+ +3kzbkIBQPwmKhADsMAo9GM37/SpZmiOVFyxFnh9uQ3ltDFyY/kinxSNHXF79buce +tPZoRdGGg1uiio2x4ymA/iVxiK2+vI+sUpZLqlGN5BMxGehOTZ/brLNq1bw5VHHK +enp/kN19HYDZgbtZJsIR/uaT4veA5GX7NDcOKYBwTa84hi6ef1evnheu6xzLKCFf +thzY56IEIvnT2tjLAgMBAAGjggEnMIIBIzAOBgNVHQ8BAf8EBAMCAQYwDwYDVR0T +AQH/BAUwAwEB/zAzBggrBgEFBQcBAQQnMCUwIwYIKwYBBQUHMAGGF2h0dHA6Ly9v +Y3NwLmVudHJ1c3QubmV0MDMGA1UdHwQsMCowKKAmoCSGImh0dHA6Ly9jcmwuZW50 +cnVzdC5uZXQvc2VydmVyMS5jcmwwOwYDVR0gBDQwMjAwBgRVHSAAMCgwJgYIKwYB +BQUHAgEWGmh0dHA6Ly93d3cuZW50cnVzdC5uZXQvQ1BTMB0GA1UdDgQWBBRokORn +pKZTgMeGZqTx90tD+4S9bTAfBgNVHSMEGDAWgBTwF2ITVT2z/woAa/tQhJfz7WLQ +GjAZBgkqhkiG9n0HQQAEDDAKGwRWNy4xAwIAgTANBgkqhkiG9w0BAQUFAAOBgQAM +sIR8LRP+mj2/GAWVPSBIoxaBhxVQFaSIjZ9g1Dpv6y1uOoakqdLBnYl6CBykLbNH +jg9kSm9mA4M/TzSUNqopbYuNAiIrjM13pXCVhpHRtr9SvjNqa5n5b+ESvgTLM7/1 +EhpORLpbFk0wufO0dM5u8mhWWN3Yof1UBfQjkYXJ+Q== +-----END CERTIFICATE----- diff --git a/security/src/main/files/certimport.sh b/security/src/main/files/certimport.sh index 7c0fab0..c021a10 100755 --- a/security/src/main/files/certimport.sh +++ b/security/src/main/files/certimport.sh @@ -1,4 +1,5 @@ #!/bin/bash +# java version >= 1.6 is required for this script. # This script was tested to work with bouncycastle 1.32. set -x @@ -6,6 +7,14 @@ set -e CERTSTORE=cacerts.bks +# Check java version. +JAVA_VERSION=`java -version 2>&1 | head -1` +JAVA_VERSION_MINOR=`expr match "$JAVA_VERSION" "java version \"[1-9]\.\([0-9]\).*\""` +if [ $JAVA_VERSION_MINOR -lt 6 ]; then + echo "java version 1.6 or greater required for keytool usage" + exit 255 +fi + if [ -a $CERTSTORE ]; then rm $CERTSTORE || exit 1 fi diff --git a/x-net/src/main/native/org_apache_harmony_xnet_provider_jsse_OpenSSLSocketImpl.cpp b/x-net/src/main/native/org_apache_harmony_xnet_provider_jsse_OpenSSLSocketImpl.cpp index 8f36632..87f2af3 100644 --- a/x-net/src/main/native/org_apache_harmony_xnet_provider_jsse_OpenSSLSocketImpl.cpp +++ b/x-net/src/main/native/org_apache_harmony_xnet_provider_jsse_OpenSSLSocketImpl.cpp @@ -421,7 +421,7 @@ typedef struct app_data { static int sslCreateAppData(SSL* ssl) { APP_DATA* data = (APP_DATA*) malloc(sizeof(APP_DATA)); - memset(data, sizeof(APP_DATA), 0); + memset(data, 0, sizeof(APP_DATA)); data->aliveAndKicking = 1; data->waitingThreads = 0; |