From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- libjava/classpath/java/util/HashMap.java | 907 +++++++++++++++++++++++++++++++ 1 file changed, 907 insertions(+) create mode 100644 libjava/classpath/java/util/HashMap.java (limited to 'libjava/classpath/java/util/HashMap.java') diff --git a/libjava/classpath/java/util/HashMap.java b/libjava/classpath/java/util/HashMap.java new file mode 100644 index 000000000..55d81c620 --- /dev/null +++ b/libjava/classpath/java/util/HashMap.java @@ -0,0 +1,907 @@ +/* HashMap.java -- a class providing a basic hashtable data structure, + mapping Object --> Object + Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. + +This file is part of GNU Classpath. + +GNU Classpath is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU Classpath is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Classpath; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301 USA. + +Linking this library statically or dynamically with other modules is +making a combined work based on this library. Thus, the terms and +conditions of the GNU General Public License cover the whole +combination. + +As a special exception, the copyright holders of this library give you +permission to link this library with independent modules to produce an +executable, regardless of the license terms of these independent +modules, and to copy and distribute the resulting executable under +terms of your choice, provided that you also meet, for each linked +independent module, the terms and conditions of the license of that +module. An independent module is a module which is not derived from +or based on this library. If you modify this library, you may extend +this exception to your version of the library, but you are not +obligated to do so. If you do not wish to do so, delete this +exception statement from your version. */ + + +package java.util; + +import java.io.IOException; +import java.io.ObjectInputStream; +import java.io.ObjectOutputStream; +import java.io.Serializable; + +// NOTE: This implementation is very similar to that of Hashtable. If you fix +// a bug in here, chances are you should make a similar change to the Hashtable +// code. + +// NOTE: This implementation has some nasty coding style in order to +// support LinkedHashMap, which extends this. + +/** + * This class provides a hashtable-backed implementation of the + * Map interface. + *

+ * + * It uses a hash-bucket approach; that is, hash collisions are handled + * by linking the new node off of the pre-existing node (or list of + * nodes). In this manner, techniques such as linear probing (which + * can cause primary clustering) and rehashing (which does not fit very + * well with Java's method of precomputing hash codes) are avoided. + *

+ * + * Under ideal circumstances (no collisions), HashMap offers O(1) + * performance on most operations (containsValue() is, + * of course, O(n)). In the worst case (all keys map to the same + * hash code -- very unlikely), most operations are O(n). + *

+ * + * HashMap is part of the JDK1.2 Collections API. It differs from + * Hashtable in that it accepts the null key and null values, and it + * does not support "Enumeration views." Also, it is not synchronized; + * if you plan to use it in multiple threads, consider using:
+ * Map m = Collections.synchronizedMap(new HashMap(...)); + *

+ * + * The iterators are fail-fast, meaning that any structural + * modification, except for remove() called on the iterator + * itself, cause the iterator to throw a + * ConcurrentModificationException rather than exhibit + * non-deterministic behavior. + * + * @author Jon Zeppieri + * @author Jochen Hoenicke + * @author Bryce McKinlay + * @author Eric Blake (ebb9@email.byu.edu) + * @see Object#hashCode() + * @see Collection + * @see Map + * @see TreeMap + * @see LinkedHashMap + * @see IdentityHashMap + * @see Hashtable + * @since 1.2 + * @status updated to 1.4 + */ +public class HashMap extends AbstractMap + implements Map, Cloneable, Serializable +{ + /** + * Default number of buckets. This is the value the JDK 1.3 uses. Some + * early documentation specified this value as 101. That is incorrect. + * Package visible for use by HashSet. + */ + static final int DEFAULT_CAPACITY = 11; + + /** + * The default load factor; this is explicitly specified by the spec. + * Package visible for use by HashSet. + */ + static final float DEFAULT_LOAD_FACTOR = 0.75f; + + /** + * Compatible with JDK 1.2. + */ + private static final long serialVersionUID = 362498820763181265L; + + /** + * The rounded product of the capacity and the load factor; when the number + * of elements exceeds the threshold, the HashMap calls + * rehash(). + * @serial the threshold for rehashing + */ + private int threshold; + + /** + * Load factor of this HashMap: used in computing the threshold. + * Package visible for use by HashSet. + * @serial the load factor + */ + final float loadFactor; + + /** + * Array containing the actual key-value mappings. + * Package visible for use by nested and subclasses. + */ + transient HashEntry[] buckets; + + /** + * Counts the number of modifications this HashMap has undergone, used + * by Iterators to know when to throw ConcurrentModificationExceptions. + * Package visible for use by nested and subclasses. + */ + transient int modCount; + + /** + * The size of this HashMap: denotes the number of key-value pairs. + * Package visible for use by nested and subclasses. + */ + transient int size; + + /** + * The cache for {@link #entrySet()}. + */ + private transient Set> entries; + + /** + * Class to represent an entry in the hash table. Holds a single key-value + * pair. Package visible for use by subclass. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + static class HashEntry extends AbstractMap.SimpleEntry + { + /** + * The next entry in the linked list. Package visible for use by subclass. + */ + HashEntry next; + + /** + * Simple constructor. + * @param key the key + * @param value the value + */ + HashEntry(K key, V value) + { + super(key, value); + } + + /** + * Called when this entry is accessed via {@link #put(Object, Object)}. + * This version does nothing, but in LinkedHashMap, it must do some + * bookkeeping for access-traversal mode. + */ + void access() + { + } + + /** + * Called when this entry is removed from the map. This version simply + * returns the value, but in LinkedHashMap, it must also do bookkeeping. + * + * @return the value of this key as it is removed + */ + V cleanup() + { + return value; + } + } + + /** + * Construct a new HashMap with the default capacity (11) and the default + * load factor (0.75). + */ + public HashMap() + { + this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); + } + + /** + * Construct a new HashMap from the given Map, with initial capacity + * the greater of the size of m or the default of 11. + *

+ * + * Every element in Map m will be put into this new HashMap. + * + * @param m a Map whose key / value pairs will be put into the new HashMap. + * NOTE: key / value pairs are not cloned in this constructor. + * @throws NullPointerException if m is null + */ + public HashMap(Map m) + { + this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR); + putAll(m); + } + + /** + * Construct a new HashMap with a specific inital capacity and + * default load factor of 0.75. + * + * @param initialCapacity the initial capacity of this HashMap (>=0) + * @throws IllegalArgumentException if (initialCapacity < 0) + */ + public HashMap(int initialCapacity) + { + this(initialCapacity, DEFAULT_LOAD_FACTOR); + } + + /** + * Construct a new HashMap with a specific inital capacity and load factor. + * + * @param initialCapacity the initial capacity (>=0) + * @param loadFactor the load factor (> 0, not NaN) + * @throws IllegalArgumentException if (initialCapacity < 0) || + * ! (loadFactor > 0.0) + */ + public HashMap(int initialCapacity, float loadFactor) + { + if (initialCapacity < 0) + throw new IllegalArgumentException("Illegal Capacity: " + + initialCapacity); + if (! (loadFactor > 0)) // check for NaN too + throw new IllegalArgumentException("Illegal Load: " + loadFactor); + + if (initialCapacity == 0) + initialCapacity = 1; + buckets = (HashEntry[]) new HashEntry[initialCapacity]; + this.loadFactor = loadFactor; + threshold = (int) (initialCapacity * loadFactor); + } + + /** + * Returns the number of kay-value mappings currently in this Map. + * + * @return the size + */ + public int size() + { + return size; + } + + /** + * Returns true if there are no key-value mappings currently in this Map. + * + * @return size() == 0 + */ + public boolean isEmpty() + { + return size == 0; + } + + /** + * Return the value in this HashMap associated with the supplied key, + * or null if the key maps to nothing. NOTE: Since the value + * could also be null, you must use containsKey to see if this key + * actually maps to something. + * + * @param key the key for which to fetch an associated value + * @return what the key maps to, if present + * @see #put(Object, Object) + * @see #containsKey(Object) + */ + public V get(Object key) + { + int idx = hash(key); + HashEntry e = buckets[idx]; + while (e != null) + { + if (equals(key, e.key)) + return e.value; + e = e.next; + } + return null; + } + + /** + * Returns true if the supplied object equals() a key + * in this HashMap. + * + * @param key the key to search for in this HashMap + * @return true if the key is in the table + * @see #containsValue(Object) + */ + public boolean containsKey(Object key) + { + int idx = hash(key); + HashEntry e = buckets[idx]; + while (e != null) + { + if (equals(key, e.key)) + return true; + e = e.next; + } + return false; + } + + /** + * Puts the supplied value into the Map, mapped by the supplied key. + * The value may be retrieved by any object which equals() + * this key. NOTE: Since the prior value could also be null, you must + * first use containsKey if you want to see if you are replacing the + * key's mapping. + * + * @param key the key used to locate the value + * @param value the value to be stored in the HashMap + * @return the prior mapping of the key, or null if there was none + * @see #get(Object) + * @see Object#equals(Object) + */ + public V put(K key, V value) + { + int idx = hash(key); + HashEntry e = buckets[idx]; + + while (e != null) + { + if (equals(key, e.key)) + { + e.access(); // Must call this for bookkeeping in LinkedHashMap. + V r = e.value; + e.value = value; + return r; + } + else + e = e.next; + } + + // At this point, we know we need to add a new entry. + modCount++; + if (++size > threshold) + { + rehash(); + // Need a new hash value to suit the bigger table. + idx = hash(key); + } + + // LinkedHashMap cannot override put(), hence this call. + addEntry(key, value, idx, true); + return null; + } + + /** + * Copies all elements of the given map into this hashtable. If this table + * already has a mapping for a key, the new mapping replaces the current + * one. + * + * @param m the map to be hashed into this + */ + public void putAll(Map m) + { + final Map addMap = (Map) m; + final Iterator> it = addMap.entrySet().iterator(); + while (it.hasNext()) + { + final Map.Entry e = it.next(); + // Optimize in case the Entry is one of our own. + if (e instanceof AbstractMap.SimpleEntry) + { + AbstractMap.SimpleEntry entry + = (AbstractMap.SimpleEntry) e; + put(entry.key, entry.value); + } + else + put(e.getKey(), e.getValue()); + } + } + + /** + * Removes from the HashMap and returns the value which is mapped by the + * supplied key. If the key maps to nothing, then the HashMap remains + * unchanged, and null is returned. NOTE: Since the value + * could also be null, you must use containsKey to see if you are + * actually removing a mapping. + * + * @param key the key used to locate the value to remove + * @return whatever the key mapped to, if present + */ + public V remove(Object key) + { + int idx = hash(key); + HashEntry e = buckets[idx]; + HashEntry last = null; + + while (e != null) + { + if (equals(key, e.key)) + { + modCount++; + if (last == null) + buckets[idx] = e.next; + else + last.next = e.next; + size--; + // Method call necessary for LinkedHashMap to work correctly. + return e.cleanup(); + } + last = e; + e = e.next; + } + return null; + } + + /** + * Clears the Map so it has no keys. This is O(1). + */ + public void clear() + { + if (size != 0) + { + modCount++; + Arrays.fill(buckets, null); + size = 0; + } + } + + /** + * Returns true if this HashMap contains a value o, such that + * o.equals(value). + * + * @param value the value to search for in this HashMap + * @return true if at least one key maps to the value + * @see #containsKey(Object) + */ + public boolean containsValue(Object value) + { + for (int i = buckets.length - 1; i >= 0; i--) + { + HashEntry e = buckets[i]; + while (e != null) + { + if (equals(value, e.value)) + return true; + e = e.next; + } + } + return false; + } + + /** + * Returns a shallow clone of this HashMap. The Map itself is cloned, + * but its contents are not. This is O(n). + * + * @return the clone + */ + public Object clone() + { + HashMap copy = null; + try + { + copy = (HashMap) super.clone(); + } + catch (CloneNotSupportedException x) + { + // This is impossible. + } + copy.buckets = (HashEntry[]) new HashEntry[buckets.length]; + copy.putAllInternal(this); + // Clear the entry cache. AbstractMap.clone() does the others. + copy.entries = null; + return copy; + } + + /** + * Returns a "set view" of this HashMap's keys. The set is backed by the + * HashMap, so changes in one show up in the other. The set supports + * element removal, but not element addition. + * + * @return a set view of the keys + * @see #values() + * @see #entrySet() + */ + public Set keySet() + { + if (keys == null) + // Create an AbstractSet with custom implementations of those methods + // that can be overridden easily and efficiently. + keys = new AbstractSet() + { + public int size() + { + return size; + } + + public Iterator iterator() + { + // Cannot create the iterator directly, because of LinkedHashMap. + return HashMap.this.iterator(KEYS); + } + + public void clear() + { + HashMap.this.clear(); + } + + public boolean contains(Object o) + { + return containsKey(o); + } + + public boolean remove(Object o) + { + // Test against the size of the HashMap to determine if anything + // really got removed. This is necessary because the return value + // of HashMap.remove() is ambiguous in the null case. + int oldsize = size; + HashMap.this.remove(o); + return oldsize != size; + } + }; + return keys; + } + + /** + * Returns a "collection view" (or "bag view") of this HashMap's values. + * The collection is backed by the HashMap, so changes in one show up + * in the other. The collection supports element removal, but not element + * addition. + * + * @return a bag view of the values + * @see #keySet() + * @see #entrySet() + */ + public Collection values() + { + if (values == null) + // We don't bother overriding many of the optional methods, as doing so + // wouldn't provide any significant performance advantage. + values = new AbstractCollection() + { + public int size() + { + return size; + } + + public Iterator iterator() + { + // Cannot create the iterator directly, because of LinkedHashMap. + return HashMap.this.iterator(VALUES); + } + + public void clear() + { + HashMap.this.clear(); + } + }; + return values; + } + + /** + * Returns a "set view" of this HashMap's entries. The set is backed by + * the HashMap, so changes in one show up in the other. The set supports + * element removal, but not element addition.

+ * + * Note that the iterators for all three views, from keySet(), entrySet(), + * and values(), traverse the HashMap in the same sequence. + * + * @return a set view of the entries + * @see #keySet() + * @see #values() + * @see Map.Entry + */ + public Set> entrySet() + { + if (entries == null) + // Create an AbstractSet with custom implementations of those methods + // that can be overridden easily and efficiently. + entries = new AbstractSet>() + { + public int size() + { + return size; + } + + public Iterator> iterator() + { + // Cannot create the iterator directly, because of LinkedHashMap. + return HashMap.this.iterator(ENTRIES); + } + + public void clear() + { + HashMap.this.clear(); + } + + public boolean contains(Object o) + { + return getEntry(o) != null; + } + + public boolean remove(Object o) + { + HashEntry e = getEntry(o); + if (e != null) + { + HashMap.this.remove(e.key); + return true; + } + return false; + } + }; + return entries; + } + + /** + * Helper method for put, that creates and adds a new Entry. This is + * overridden in LinkedHashMap for bookkeeping purposes. + * + * @param key the key of the new Entry + * @param value the value + * @param idx the index in buckets where the new Entry belongs + * @param callRemove whether to call the removeEldestEntry method + * @see #put(Object, Object) + */ + void addEntry(K key, V value, int idx, boolean callRemove) + { + HashEntry e = new HashEntry(key, value); + e.next = buckets[idx]; + buckets[idx] = e; + } + + /** + * Helper method for entrySet(), which matches both key and value + * simultaneously. + * + * @param o the entry to match + * @return the matching entry, if found, or null + * @see #entrySet() + */ + // Package visible, for use in nested classes. + final HashEntry getEntry(Object o) + { + if (! (o instanceof Map.Entry)) + return null; + Map.Entry me = (Map.Entry) o; + K key = me.getKey(); + int idx = hash(key); + HashEntry e = buckets[idx]; + while (e != null) + { + if (equals(e.key, key)) + return equals(e.value, me.getValue()) ? e : null; + e = e.next; + } + return null; + } + + /** + * Helper method that returns an index in the buckets array for `key' + * based on its hashCode(). Package visible for use by subclasses. + * + * @param key the key + * @return the bucket number + */ + final int hash(Object key) + { + return key == null ? 0 : Math.abs(key.hashCode() % buckets.length); + } + + /** + * Generates a parameterized iterator. Must be overrideable, since + * LinkedHashMap iterates in a different order. + * + * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} + * @return the appropriate iterator + */ + Iterator iterator(int type) + { + // FIXME: bogus cast here. + return new HashIterator(type); + } + + /** + * A simplified, more efficient internal implementation of putAll(). clone() + * should not call putAll or put, in order to be compatible with the JDK + * implementation with respect to subclasses. + * + * @param m the map to initialize this from + */ + void putAllInternal(Map m) + { + final Map addMap = (Map) m; + final Iterator> it = addMap.entrySet().iterator(); + size = 0; + while (it.hasNext()) + { + final Map.Entry e = it.next(); + size++; + K key = e.getKey(); + int idx = hash(key); + addEntry(key, e.getValue(), idx, false); + } + } + + /** + * Increases the size of the HashMap and rehashes all keys to new + * array indices; this is called when the addition of a new value + * would cause size() > threshold. Note that the existing Entry + * objects are reused in the new hash table. + * + *

This is not specified, but the new size is twice the current size + * plus one; this number is not always prime, unfortunately. + */ + private void rehash() + { + HashEntry[] oldBuckets = buckets; + + int newcapacity = (buckets.length * 2) + 1; + threshold = (int) (newcapacity * loadFactor); + buckets = (HashEntry[]) new HashEntry[newcapacity]; + + for (int i = oldBuckets.length - 1; i >= 0; i--) + { + HashEntry e = oldBuckets[i]; + while (e != null) + { + int idx = hash(e.key); + HashEntry dest = buckets[idx]; + HashEntry next = e.next; + e.next = buckets[idx]; + buckets[idx] = e; + e = next; + } + } + } + + /** + * Serializes this object to the given stream. + * + * @param s the stream to write to + * @throws IOException if the underlying stream fails + * @serialData the capacity(int) that is the length of the + * bucket array, the size(int) of the hash map + * are emitted first. They are followed by size entries, + * each consisting of a key (Object) and a value (Object). + */ + private void writeObject(ObjectOutputStream s) throws IOException + { + // Write the threshold and loadFactor fields. + s.defaultWriteObject(); + + s.writeInt(buckets.length); + s.writeInt(size); + // Avoid creating a wasted Set by creating the iterator directly. + Iterator> it = iterator(ENTRIES); + while (it.hasNext()) + { + HashEntry entry = it.next(); + s.writeObject(entry.key); + s.writeObject(entry.value); + } + } + + /** + * Deserializes this object from the given stream. + * + * @param s the stream to read from + * @throws ClassNotFoundException if the underlying stream fails + * @throws IOException if the underlying stream fails + * @serialData the capacity(int) that is the length of the + * bucket array, the size(int) of the hash map + * are emitted first. They are followed by size entries, + * each consisting of a key (Object) and a value (Object). + */ + private void readObject(ObjectInputStream s) + throws IOException, ClassNotFoundException + { + // Read the threshold and loadFactor fields. + s.defaultReadObject(); + + // Read and use capacity, followed by key/value pairs. + buckets = (HashEntry[]) new HashEntry[s.readInt()]; + int len = s.readInt(); + size = len; + while (len-- > 0) + { + Object key = s.readObject(); + addEntry((K) key, (V) s.readObject(), hash(key), false); + } + } + + /** + * Iterate over HashMap's entries. + * This implementation is parameterized to give a sequential view of + * keys, values, or entries. + * + * @author Jon Zeppieri + */ + private final class HashIterator implements Iterator + { + /** + * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, + * or {@link #ENTRIES}. + */ + private final int type; + /** + * The number of modifications to the backing HashMap that we know about. + */ + private int knownMod = modCount; + /** The number of elements remaining to be returned by next(). */ + private int count = size; + /** Current index in the physical hash table. */ + private int idx = buckets.length; + /** The last Entry returned by a next() call. */ + private HashEntry last; + /** + * The next entry that should be returned by next(). It is set to something + * if we're iterating through a bucket that contains multiple linked + * entries. It is null if next() needs to find a new bucket. + */ + private HashEntry next; + + /** + * Construct a new HashIterator with the supplied type. + * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} + */ + HashIterator(int type) + { + this.type = type; + } + + /** + * Returns true if the Iterator has more elements. + * @return true if there are more elements + */ + public boolean hasNext() + { + return count > 0; + } + + /** + * Returns the next element in the Iterator's sequential view. + * @return the next element + * @throws ConcurrentModificationException if the HashMap was modified + * @throws NoSuchElementException if there is none + */ + public T next() + { + if (knownMod != modCount) + throw new ConcurrentModificationException(); + if (count == 0) + throw new NoSuchElementException(); + count--; + HashEntry e = next; + + while (e == null) + e = buckets[--idx]; + + next = e.next; + last = e; + if (type == VALUES) + return (T) e.value; + if (type == KEYS) + return (T) e.key; + return (T) e; + } + + /** + * Removes from the backing HashMap the last element which was fetched + * with the next() method. + * @throws ConcurrentModificationException if the HashMap was modified + * @throws IllegalStateException if called when there is no last element + */ + public void remove() + { + if (knownMod != modCount) + throw new ConcurrentModificationException(); + if (last == null) + throw new IllegalStateException(); + + HashMap.this.remove(last.key); + last = null; + knownMod++; + } + } +} -- cgit v1.2.3