diff options
Diffstat (limited to 'libjava/classpath/java/util/LinkedHashMap.java')
| -rw-r--r-- | libjava/classpath/java/util/LinkedHashMap.java | 501 |
1 files changed, 501 insertions, 0 deletions
diff --git a/libjava/classpath/java/util/LinkedHashMap.java b/libjava/classpath/java/util/LinkedHashMap.java new file mode 100644 index 0000000..8e895a9 --- /dev/null +++ b/libjava/classpath/java/util/LinkedHashMap.java @@ -0,0 +1,501 @@ +/* LinkedHashMap.java -- a class providing hashtable data structure, + mapping Object --> Object, with linked list traversal + Copyright (C) 2001, 2002, 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; + +/** + * This class provides a hashtable-backed implementation of the + * Map interface, with predictable traversal order. + * <p> + * + * 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. In + * addition, this maintains a doubly-linked list which tracks either + * insertion or access order. + * <p> + * + * In insertion order, calling <code>put</code> adds the key to the end of + * traversal, unless the key was already in the map; changing traversal order + * requires removing and reinserting a key. On the other hand, in access + * order, all calls to <code>put</code> and <code>get</code> cause the + * accessed key to move to the end of the traversal list. Note that any + * accesses to the map's contents via its collection views and iterators do + * not affect the map's traversal order, since the collection views do not + * call <code>put</code> or <code>get</code>. + * <p> + * + * One of the nice features of tracking insertion order is that you can + * copy a hashtable, and regardless of the implementation of the original, + * produce the same results when iterating over the copy. This is possible + * without needing the overhead of <code>TreeMap</code>. + * <p> + * + * When using this {@link #LinkedHashMap(int, float, boolean) constructor}, + * you can build an access-order mapping. This can be used to implement LRU + * caches, for example. By overriding {@link #removeEldestEntry(Map.Entry)}, + * you can also control the removal of the oldest entry, and thereby do + * things like keep the map at a fixed size. + * <p> + * + * Under ideal circumstances (no collisions), LinkedHashMap offers O(1) + * performance on most operations (<code>containsValue()</code> is, + * of course, O(n)). In the worst case (all keys map to the same + * hash code -- very unlikely), most operations are O(n). Traversal is + * faster than in HashMap (proportional to the map size, and not the space + * allocated for the map), but other operations may be slower because of the + * overhead of the maintaining the traversal order list. + * <p> + * + * LinkedHashMap accepts the null key and null values. It is not + * synchronized, so if you need multi-threaded access, consider using:<br> + * <code>Map m = Collections.synchronizedMap(new LinkedHashMap(...));</code> + * <p> + * + * The iterators are <i>fail-fast</i>, meaning that any structural + * modification, except for <code>remove()</code> called on the iterator + * itself, cause the iterator to throw a + * {@link ConcurrentModificationException} rather than exhibit + * non-deterministic behavior. + * + * @author Eric Blake (ebb9@email.byu.edu) + * @see Object#hashCode() + * @see Collection + * @see Map + * @see HashMap + * @see TreeMap + * @see Hashtable + * @since 1.4 + * @status updated to 1.4 + */ +public class LinkedHashMap extends HashMap +{ + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 3801124242820219131L; + + /** + * The oldest Entry to begin iteration at. + */ + transient LinkedHashEntry root; + + /** + * The iteration order of this linked hash map: <code>true</code> for + * access-order, <code>false</code> for insertion-order. + * + * @serial true for access order traversal + */ + final boolean accessOrder; + + /** + * Class to represent an entry in the hash table. Holds a single key-value + * pair and the doubly-linked insertion order list. + */ + class LinkedHashEntry extends HashEntry + { + /** + * The predecessor in the iteration list. If this entry is the root + * (eldest), pred points to the newest entry. + */ + LinkedHashEntry pred; + + /** The successor in the iteration list, null if this is the newest. */ + LinkedHashEntry succ; + + /** + * Simple constructor. + * + * @param key the key + * @param value the value + */ + LinkedHashEntry(Object key, Object value) + { + super(key, value); + if (root == null) + { + root = this; + pred = this; + } + else + { + pred = root.pred; + pred.succ = this; + root.pred = this; + } + } + + /** + * Called when this entry is accessed via put or get. This version does + * the necessary bookkeeping to keep the doubly-linked list in order, + * after moving this element to the newest position in access order. + */ + void access() + { + if (accessOrder && succ != null) + { + modCount++; + if (this == root) + { + root = succ; + pred.succ = this; + succ = null; + } + else + { + pred.succ = succ; + succ.pred = pred; + succ = null; + pred = root.pred; + pred.succ = this; + root.pred = this; + } + } + } + + /** + * Called when this entry is removed from the map. This version does + * the necessary bookkeeping to keep the doubly-linked list in order. + * + * @return the value of this key as it is removed + */ + Object cleanup() + { + if (this == root) + { + root = succ; + if (succ != null) + succ.pred = pred; + } + else if (succ == null) + { + pred.succ = null; + root.pred = pred; + } + else + { + pred.succ = succ; + succ.pred = pred; + } + return value; + } + } // class LinkedHashEntry + + /** + * Construct a new insertion-ordered LinkedHashMap with the default + * capacity (11) and the default load factor (0.75). + */ + public LinkedHashMap() + { + super(); + accessOrder = false; + } + + /** + * Construct a new insertion-ordered LinkedHashMap from the given Map, + * with initial capacity the greater of the size of <code>m</code> or + * the default of 11. + * <p> + * + * Every element in Map m will be put into this new HashMap, in the + * order of m's iterator. + * + * @param m a Map whose key / value pairs will be put into + * the new HashMap. <b>NOTE: key / value pairs + * are not cloned in this constructor.</b> + * @throws NullPointerException if m is null + */ + public LinkedHashMap(Map m) + { + super(m); + accessOrder = false; + } + + /** + * Construct a new insertion-ordered LinkedHashMap 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 LinkedHashMap(int initialCapacity) + { + super(initialCapacity); + accessOrder = false; + } + + /** + * Construct a new insertion-orderd LinkedHashMap 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 LinkedHashMap(int initialCapacity, float loadFactor) + { + super(initialCapacity, loadFactor); + accessOrder = false; + } + + /** + * Construct a new LinkedHashMap with a specific inital capacity, load + * factor, and ordering mode. + * + * @param initialCapacity the initial capacity (>=0) + * @param loadFactor the load factor (>0, not NaN) + * @param accessOrder true for access-order, false for insertion-order + * @throws IllegalArgumentException if (initialCapacity < 0) || + * ! (loadFactor > 0.0) + */ + public LinkedHashMap(int initialCapacity, float loadFactor, + boolean accessOrder) + { + super(initialCapacity, loadFactor); + this.accessOrder = accessOrder; + } + + /** + * Clears the Map so it has no keys. This is O(1). + */ + public void clear() + { + super.clear(); + root = null; + } + + /** + * Returns <code>true</code> if this HashMap contains a value + * <code>o</code>, such that <code>o.equals(value)</code>. + * + * @param value the value to search for in this HashMap + * @return <code>true</code> if at least one key maps to the value + */ + public boolean containsValue(Object value) + { + LinkedHashEntry e = root; + while (e != null) + { + if (equals(value, e.value)) + return true; + e = e.succ; + } + return false; + } + + /** + * Return the value in this Map associated with the supplied key, + * or <code>null</code> if the key maps to nothing. If this is an + * access-ordered Map and the key is found, this performs structural + * modification, moving the key to the newest end of the list. 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 Object get(Object key) + { + int idx = hash(key); + HashEntry e = buckets[idx]; + while (e != null) + { + if (equals(key, e.key)) + { + e.access(); + return e.value; + } + e = e.next; + } + return null; + } + + /** + * Returns <code>true</code> if this map should remove the eldest entry. + * This method is invoked by all calls to <code>put</code> and + * <code>putAll</code> which place a new entry in the map, providing + * the implementer an opportunity to remove the eldest entry any time + * a new one is added. This can be used to save memory usage of the + * hashtable, as well as emulating a cache, by deleting stale entries. + * <p> + * + * For example, to keep the Map limited to 100 entries, override as follows: + * <pre> + * private static final int MAX_ENTRIES = 100; + * protected boolean removeEldestEntry(Map.Entry eldest) + * { + * return size() > MAX_ENTRIES; + * } + * </pre><p> + * + * Typically, this method does not modify the map, but just uses the + * return value as an indication to <code>put</code> whether to proceed. + * However, if you override it to modify the map, you must return false + * (indicating that <code>put</code> should leave the modified map alone), + * or you face unspecified behavior. Remember that in access-order mode, + * even calling <code>get</code> is a structural modification, but using + * the collections views (such as <code>keySet</code>) is not. + * <p> + * + * This method is called after the eldest entry has been inserted, so + * if <code>put</code> was called on a previously empty map, the eldest + * entry is the one you just put in! The default implementation just + * returns <code>false</code>, so that this map always behaves like + * a normal one with unbounded growth. + * + * @param eldest the eldest element which would be removed if this + * returns true. For an access-order map, this is the least + * recently accessed; for an insertion-order map, this is the + * earliest element inserted. + * @return true if <code>eldest</code> should be removed + */ + protected boolean removeEldestEntry(Map.Entry eldest) + { + return false; + } + + /** + * Helper method called by <code>put</code>, which creates and adds a + * new Entry, followed by performing bookkeeping (like removeEldestEntry). + * + * @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) + * @see #removeEldestEntry(Map.Entry) + * @see LinkedHashEntry#LinkedHashEntry(Object, Object) + */ + void addEntry(Object key, Object value, int idx, boolean callRemove) + { + LinkedHashEntry e = new LinkedHashEntry(key, value); + e.next = buckets[idx]; + buckets[idx] = e; + if (callRemove && removeEldestEntry(root)) + remove(root.key); + } + + /** + * Helper method, called by clone() to reset the doubly-linked list. + * + * @param m the map to add entries from + * @see #clone() + */ + void putAllInternal(Map m) + { + root = null; + super.putAllInternal(m); + } + + /** + * Generates a parameterized iterator. This allows traversal to follow + * the doubly-linked list instead of the random bin order of HashMap. + * + * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} + * @return the appropriate iterator + */ + Iterator iterator(final int type) + { + return new Iterator() + { + /** The current Entry. */ + LinkedHashEntry current = root; + + /** The previous Entry returned by next(). */ + LinkedHashEntry last; + + /** The number of known modifications to the backing Map. */ + int knownMod = modCount; + + /** + * Returns true if the Iterator has more elements. + * + * @return true if there are more elements + * @throws ConcurrentModificationException if the HashMap was modified + */ + public boolean hasNext() + { + if (knownMod != modCount) + throw new ConcurrentModificationException(); + return current != null; + } + + /** + * 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 Object next() + { + if (knownMod != modCount) + throw new ConcurrentModificationException(); + if (current == null) + throw new NoSuchElementException(); + last = current; + current = current.succ; + return type == VALUES ? last.value : type == KEYS ? last.key : last; + } + + /** + * Removes from the backing HashMap the last element which was fetched + * with the <code>next()</code> 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(); + LinkedHashMap.this.remove(last.key); + last = null; + knownMod++; + } + }; + } +} // class LinkedHashMap |