/*
* 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 java.util;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
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
* capacity is the number of key/value pairs the Hashtable can hold. The load
* factor is a float value which determines how full the Hashtable gets before
* expanding the capacity. If the load factor of the Hashtable is exceeded, the
* capacity is doubled.
*
* @see Enumeration
* @see java.io.Serializable
* @see java.lang.Object#equals
* @see java.lang.Object#hashCode
* @since Android 1.0
*/
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 <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 final class HashIterator<E> implements Iterator<E> {
private int position, expectedModCount;
private final MapEntry.Type<E, K, V> type;
private Entry<K, V> lastEntry;
private int lastPosition;
private boolean canRemove = false;
HashIterator(MapEntry.Type<E, K, V> value) {
type = value;
position = lastSlot;
expectedModCount = modCount;
}
public boolean hasNext() {
if (lastEntry != null && lastEntry.next != null) {
return true;
}
while (position >= firstSlot) {
if (elementData[position] == null) {
position--;
} else {
return true;
}
}
return false;
}
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();
}
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();
}
}
private final class HashEnumerator<E> implements Enumeration<E> {
boolean key;
int start;
Entry<K, V> entry;
HashEnumerator(boolean isKey) {
key = isKey;
start = lastSlot + 1;
}
public boolean hasMoreElements() {
if (entry != null) {
return true;
}
while (--start >= firstSlot) {
if (elementData[start] != null) {
entry = elementData[start];
return true;
}
}
return false;
}
@SuppressWarnings("unchecked")
public E nextElement() {
if (hasMoreElements()) {
Object result = key ? entry.key : entry.value;
entry = entry.next;
return (E) result;
}
throw new NoSuchElementException();
}
}
/**
* Constructs a new {@code Hashtable} using the default capacity and load
* factor.
*
* @since Android 1.0
*/
public Hashtable() {
this(11);
}
/**
* Constructs a new {@code Hashtable} using the specified capacity and the
* default load factor.
*
* @param capacity
* the initial capacity.
* @since Android 1.0
*/
public Hashtable(int capacity) {
if (capacity >= 0) {
elementCount = 0;
elementData = newElementArray(capacity == 0 ? 1 : capacity);
firstSlot = elementData.length;
loadFactor = 0.75f;
computeMaxSize();
} else {
throw new IllegalArgumentException();
}
}
/**
* Constructs a new {@code Hashtable} using the specified capacity and load
* factor.
*
* @param capacity
* the initial capacity.
* @param loadFactor
* the initial load factor.
* @since Android 1.0
*/
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();
}
}
/**
* Constructs a new instance of {@code Hashtable} containing the mappings
* from the specified map.
*
* @param map
* the mappings to add.
* @since Android 1.0
*/
public Hashtable(Map<? extends K, ? extends V> map) {
this(map.size() < 6 ? 11 : (map.size() * 4 / 3) + 11);
putAll(map);
}
@SuppressWarnings("unchecked")
private Entry<K, V>[] newElementArray(int size) {
return new Entry[size];
}
/**
* Removes all key/value pairs from this {@code Hashtable}, leaving the
* size zero and the capacity unchanged.
*
* @see #isEmpty
* @see #size
* @since Android 1.0
*/
public synchronized void clear() {
elementCount = 0;
Arrays.fill(elementData, null);
modCount++;
}
/**
* Returns a new {@code Hashtable} with the same key/value pairs, capacity
* and load factor.
*
* @return a shallow copy of this {@code Hashtable}.
* @see java.lang.Cloneable
* @since Android 1.0
*/
@Override
@SuppressWarnings("unchecked")
public synchronized Object clone() {
try {
Hashtable<K, V> hashtable = (Hashtable<K, V>) super.clone();
hashtable.elementData = elementData.clone();
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;
} catch (CloneNotSupportedException e) {
return null;
}
}
private void computeMaxSize() {
threshold = (int) (elementData.length * loadFactor);
}
/**
* Returns true if this {@code Hashtable} contains the specified object as
* the value of at least one of the 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},
* {@code false} otherwise.
* @see #containsKey
* @see java.lang.Object#equals
* @since Android 1.0
*/
public synchronized boolean contains(Object value) {
if (value == null) {
throw new NullPointerException();
}
for (int i = elementData.length; --i >= 0;) {
Entry<K, V> entry = elementData[i];
while (entry != null) {
if (value.equals(entry.value)) {
return true;
}
entry = entry.next;
}
}
return false;
}
/**
* Returns true if this {@code Hashtable} contains the specified object as a
* key of one of the key/value pairs.
*
* @param key
* the object to look for as a key in this {@code Hashtable}.
* @return {@code true} if object is a key in this {@code Hashtable},
* {@code false} otherwise.
* @see #contains
* @see java.lang.Object#equals
* @since Android 1.0
*/
public synchronized boolean containsKey(Object key) {
return getEntry(key) != null;
}
/**
* Searches this {@code Hashtable} for the specified value.
*
* @param value
* the object to search for.
* @return {@code true} if {@code value} is a value of this
* {@code Hashtable}, {@code false} otherwise.
* @since Android 1.0
*/
public boolean containsValue(Object value) {
return contains(value);
}
/**
* 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 an enumeration of the values of this {@code Hashtable}.
* @see #keys
* @see #size
* @see Enumeration
* @since Android 1.0
*/
@Override
@SuppressWarnings("unchecked")
public synchronized Enumeration<V> elements() {
if (elementCount == 0) {
return (Enumeration<V>) EMPTY_ENUMERATION;
}
return new HashEnumerator<V>(false);
}
/**
* 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.
* @since Android 1.0
*/
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() {
synchronized (Hashtable.this) {
return elementCount;
}
}
@Override
public void clear() {
Hashtable.this.clear();
}
@Override
@SuppressWarnings("unchecked")
public boolean remove(Object object) {
synchronized (Hashtable.this) {
if (contains(object)) {
Hashtable.this
.remove(((Map.Entry<K, V>) object)
.getKey());
return true;
}
return false;
}
}
@Override
@SuppressWarnings("unchecked")
public boolean contains(Object object) {
synchronized (Hashtable.this) {
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);
}
/**
* 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 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
* @since Android 1.0
*/
@Override
public synchronized boolean equals(Object object) {
if (this == object) {
return true;
}
if (object instanceof Map) {
Map<?, ?> map = (Map<?, ?>) object;
if (size() != map.size()) {
return false;
}
Set<Map.Entry<K, V>> entries = entrySet();
for (Map.Entry<?, ?> e : map.entrySet()) {
if (!entries.contains(e)) {
return false;
}
}
return true;
}
return false;
}
/**
* 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
* @since Android 1.0
*/
@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;
}
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;
}
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();
Object value = entry.getValue();
int hash = (key != this ? key.hashCode() : 0)
^ (value != this ? (value != null ? value.hashCode() : 0)
: 0);
result += hash;
}
return result;
}
/**
* Returns true if this {@code Hashtable} has no key/value pairs.
*
* @return {@code true} if this {@code Hashtable} has no key/value pairs,
* {@code false} otherwise.
* @see #size
* @since Android 1.0
*/
@Override
public synchronized boolean isEmpty() {
return elementCount == 0;
}
/**
* 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.
*
* @return an enumeration of the keys of this {@code Hashtable}.
* @see #elements
* @see #size
* @see Enumeration
* @since Android 1.0
*/
@Override
@SuppressWarnings("unchecked")
public synchronized Enumeration<K> keys() {
if (elementCount == 0) {
return (Enumeration<K>) EMPTY_ENUMERATION;
}
return new HashEnumerator<K>(true);
}
/**
* 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.
* @since Android 1.0
*/
public Set<K> keySet() {
return new Collections.SynchronizedSet<K>(new AbstractSet<K>() {
@Override
public boolean contains(Object object) {
synchronized (Hashtable.this) {
return containsKey(object);
}
}
@Override
public int size() {
synchronized (Hashtable.this) {
return elementCount;
}
}
@Override
public void clear() {
Hashtable.this.clear();
}
@Override
public boolean remove(Object key) {
synchronized (Hashtable.this) {
if (containsKey(key)) {
Hashtable.this.remove(key);
return true;
}
return false;
}
}
@Override
public Iterator<K> iterator() {
return new HashIterator<K>(new MapEntry.Type<K, K, V>() {
public K get(MapEntry<K, V> entry) {
return entry.key;
}
});
}
}, this);
}
/**
* 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
* @since Android 1.0
*/
@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();
}
/**
* Copies every mapping to this {@code Hashtable} from the specified map.
*
* @param map
* the map to copy mappings from.
* @since Android 1.0
*/
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());
}
}
/**
* Increases the capacity of this {@code Hashtable}. This method is called
* when the size of this {@code Hashtable} exceeds the load factor.
*
* @since Android 1.0
*/
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;
}
if (index > newLast) {
newLast = index;
}
Entry<K, V> next = entry.next;
entry.next = newData[index];
newData[index] = entry;
entry = next;
}
}
firstSlot = newFirst;
lastSlot = newLast;
elementData = newData;
computeMaxSize();
}
/**
* Removes the key/value pair with the specified key from this
* {@code Hashtable}.
*
* @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
* @since Android 1.0
*/
@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;
}
elementCount--;
V result = entry.value;
entry.value = null;
return result;
}
return null;
}
/**
* 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
* @since Android 1.0
*/
@Override
public synchronized int size() {
return elementCount;
}
/**
* Returns the string representation of this {@code Hashtable}.
*
* @return the string representation of this {@code Hashtable}.
* @since Android 1.0
*/
@Override
public synchronized String toString() {
if (isEmpty()) {
return "{}"; //$NON-NLS-1$
}
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;
}
}
// Remove the last ", "
if (elementCount > 0) {
buffer.setLength(buffer.length() - 2);
}
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.
* @since Android 1.0
*/
public Collection<V> values() {
return new Collections.SynchronizedCollection<V>(
new AbstractCollection<V>() {
@Override
public boolean contains(Object object) {
synchronized (Hashtable.this) {
return Hashtable.this.contains(object);
}
}
@Override
public int size() {
synchronized (Hashtable.this) {
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 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;
}
}
}
@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;
}
}
}
|
