/* * Copyright (c) 1998, 2000, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. Oracle designates this * particular file as subject to the "Classpath" exception as provided * by Oracle in the LICENSE file that accompanied this code. * * This code 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 * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ package com.sun.tools.jdi; import java.io.*; import java.util.*; /** * Hash table based implementation of the Map interface. This implementation * provides all of the optional Map operations, and permits null values and * the null key. (HashMap is roughly equivalent to Hashtable, except that it * is unsynchronized and permits nulls.) In addition, elements in the map are * ordered and doubly linked together. *

* This implementation provides constant-time performance for the basic * operations (get and put), assuming the the hash function disperses the * elements properly among the buckets. Iteration over Collection views * requires time proportional to its size (the number of key-value mappings) * and returns elements in the order they are linked. In a HashMap the * iteration would require time proportional to the capacity of the map * plus the map size. *

* An instance of LinkedHashMap has two parameters that affect its efficiency: * its capacity and its load factor. The load factor should be * between 0.0 and 1.0. When the number of mappings in the LinkedHashMap exceeds * the product of the load factor and the current capacity, the capacity is * increased by calling the rehash method which requires time proportional * to the number of key-value mappings in the map. Larger load factors * use memory more efficiently, at the expense of larger expected time per * lookup. *

* If many mappings are to be stored in a LinkedHashMap, creating it with a * sufficiently large capacity will allow the mappings to be stored more * efficiently than letting it perform automatic rehashing as needed to grow * the table. *

* Note that this implementation is not synchronized. If * multiple threads access a LinkedHashMap concurrently, and at least one of the * threads modifies the LinkedHashMap structurally, it must be * synchronized externally. (A structural modification is any operation that * adds or deletes one or more mappings; merely changing the value associated * with a key that is already contained in the Table is not a structural * modification.) This is typically accomplished by synchronizing on some * object that naturally encapsulates the LinkedHashMap. If no such object * exists, the LinkedHashMap should be "wrapped" using the * Collections.synchronizedSet method. This is best done at creation time, to * prevent accidental unsynchronized access to the LinkedHashMap: *

 *      Map m = Collections.synchronizedMap(new LinkedHashMap(...));
 * 
*

* The Iterators returned by the iterator methods of the Collections returned * by all of LinkedHashMap's "collection view methods" are fail-fast: * if the LinkedHashMap is structurally modified at any time after the Iterator * is created, in any way except through the Iterator's own remove or add * methods, the Iterator will throw a ConcurrentModificationException. Thus, * in the face of concurrent modification, the Iterator fails quickly and * cleanly, rather than risking arbitrary, non-deterministic behavior at an * undetermined time in the future. * * @author Josh Bloch * @author Arthur van Hoff * @author Zhenghua Li * @see Object#hashCode() * @see java.util.Collection * @see java.util.Map * @see java.util.TreeMap * @see java.util.Hashtable * @see java.util.HashMap */ import java.io.Serializable; public class LinkedHashMap extends AbstractMap implements Map, Serializable { /** * The hash table data. */ private transient Entry table[]; /** * The head of the double linked list. */ private transient Entry header; /** * The total number of mappings in the hash table. */ private transient int count; /** * Rehashes the table when count exceeds this threshold. */ private int threshold; /** * The load factor for the LinkedHashMap. */ private float loadFactor; /** * The number of times this LinkedHashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the LinkedHashMap or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the LinkedHashMap fail-fast. (See ConcurrentModificationException). */ private transient int modCount = 0; /** * Constructs a new, empty LinkedHashMap with the specified initial * capacity and the specified load factor. * * @param initialCapacity the initial capacity of the LinkedHashMap. * @param loadFactor a number between 0.0 and 1.0. * @exception IllegalArgumentException if the initial capacity is less * than or equal to zero, or if the load factor is less than * or equal to zero. */ public LinkedHashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Initial Capacity: "+ initialCapacity); if ((loadFactor > 1) || (loadFactor <= 0)) throw new IllegalArgumentException("Illegal Load factor: "+ loadFactor); if (initialCapacity==0) initialCapacity = 1; this.loadFactor = loadFactor; table = new Entry[initialCapacity]; threshold = (int)(initialCapacity * loadFactor); header = new Entry(-1, null, null, null); header.before = header.after = header; } /** * Constructs a new, empty LinkedHashMap with the specified initial capacity * and default load factor. * * @param initialCapacity the initial capacity of the LinkedHashMap. */ public LinkedHashMap(int initialCapacity) { this(initialCapacity, 0.75f); } /** * Constructs a new, empty LinkedHashMap with a default capacity and load * factor. */ public LinkedHashMap() { this(101, 0.75f); } /** * Constructs a new LinkedHashMap with the same mappings as the given * Map. The LinkedHashMap is created with a capacity of thrice the number * of mappings in the given Map or 11 (whichever is greater), and a * default load factor. */ public LinkedHashMap(Map t) { this(Math.max(3*t.size(), 11), 0.75f); putAll(t); } /** * Returns the number of key-value mappings in this Map. */ public int size() { return count; } /** * Returns true if this Map contains no key-value mappings. */ public boolean isEmpty() { return count == 0; } /** * Returns true if this LinkedHashMap maps one or more keys to the specified * value. * * @param value value whose presence in this Map is to be tested. */ public boolean containsValue(Object value) { if (value==null) { for (Entry e = header.after; e != header; e = e.after) if (e.value==null) return true; } else { for (Entry e = header.after; e != header; e = e.after) if (value.equals(e.value)) return true; } return false; } /** * Returns true if this LinkedHashMap contains a mapping for the specified * key. * * @param key key whose presence in this Map is to be tested. */ public boolean containsKey(Object key) { Entry tab[] = table; if (key != null) { int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry e = tab[index]; e != null; e = e.next) if (e.hash==hash && e.key.equals(key)) return true; } else { for (Entry e = tab[0]; e != null; e = e.next) if (e.key==null) return true; } return false; } /** * Returns the value to which this LinkedHashMap maps the specified key. * Returns null if the LinkedHashMap contains no mapping for this key. * A return value of null does not necessarily indicate that the * LinkedHashMap contains no mapping for the key; it's also possible that * the LinkedHashMap explicitly maps the key to null. The containsKey * operation may be used to distinguish these two cases. * * @param key key whose associated value is to be returned. */ public Object get(Object key) { Entry e = getEntry(key); return e==null ? null : e.value; } /** * Returns the entry associated with the specified key in the LinkedHashMap. * Returns null if the LinkedHashMap contains no mapping for this key. */ private Entry getEntry(Object key) { Entry tab[] = table; if (key != null) { int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry e = tab[index]; e != null; e = e.next) if ((e.hash == hash) && e.key.equals(key)) return e; } else { for (Entry e = tab[0]; e != null; e = e.next) if (e.key==null) return e; } return null; } /** * Rehashes the contents of the LinkedHashMap into a LinkedHashMap with a * larger capacity. This method is called automatically when the * number of keys in the LinkedHashMap exceeds this LinkedHashMap's capacity * and load factor. */ private void rehash() { int oldCapacity = table.length; Entry oldMap[] = table; int newCapacity = oldCapacity * 2 + 1; Entry newMap[] = new Entry[newCapacity]; modCount++; threshold = (int)(newCapacity * loadFactor); table = newMap; for (Entry e = header.after; e != header; e = e.after) { int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = newMap[index]; newMap[index] = e; } } /** * Remove an entry from the linked list. */ private void listRemove(Entry entry) { if (entry == null) { return; } entry.before.after = entry.after; entry.after.before = entry.before; } /** * Add the specified entry before the specified existing entry to * the linked list. */ private void listAddBefore(Entry entry, Entry existEntry) { entry.after = existEntry; entry.before = existEntry.before; entry.before.after = entry; entry.after.before = entry; } /** * Returns the position of the mapping for the specified key * in the ordered map. * * @param key the specified key. * @return index of the key mapping. */ public int indexOf(Object key) { int i = 0; if (key == null) { for (Entry e = header.after; e != header; e = e.after, i++) if (e.key == null) return i; } else { for (Entry e = header.after; e != header; e = e.after, i++) if(key.equals(e.key)) return i; } return -1; } /** * Associates the specified value with the specified key in this * LinkedHashMap. If the LinkedHashMap previously contained a mapping for * this key, the old value is replaced and the position of this mapping * entry in the double linked list remains the same. Otherwise, a new * mapping entry is created and inserted into the list before the specified * existing mapping entry. The method returns the previous value associated * with the specified key, or null if there was no mapping for key. A null * return can also indicate that the LinkedHashMap previously associated * null with the specified key. */ private Object putAhead(Object key, Object value, Entry existEntry) { // Makes sure the key is not already in the LinkedHashMap. Entry tab[] = table; int hash = 0; int index = 0; if (key != null) { hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; for (Entry e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { Object old = e.value; e.value = value; return old; } } } else { for (Entry e = tab[0] ; e != null ; e = e.next) { if (e.key == null) { Object old = e.value; e.value = value; return old; } } } modCount++; if (count >= threshold) { // Rehash the table if the threshold is exceeded rehash(); tab = table; index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. Entry e = new Entry(hash, key, value, tab[index]); tab[index] = e; listAddBefore(e, existEntry); count++; return null; } /** * Associates the specified value with the specified key in this * LinkedHashMap and position the mapping at the specified index. * If the LinkedHashMap previously contained a mapping for this key, * the old value is replaced and the position of this mapping entry * in the double linked list remains the same. Otherwise, a new mapping * entry is created and inserted into the list at the specified * position. * * @param index the position to put the key-value mapping. * @param key key with which the specified value is to be associated. * @param value value to be associated with the specified key. * @return previous value associated with specified key, or null if there * was no mapping for key. A null return can also indicate that * the LinkedHashMap previously associated null with the specified * key. */ public Object put(int index, Object key, Object value) { if (index < 0 || index > count) throw new IndexOutOfBoundsException(); Entry e = header.after; if (index == count) return putAhead(key, value, header); //fast approach for append else { for (int i = 0; i < index; i++) e = e.after; return putAhead(key, value, e); } } /** * Associates the specified value with the specified key in this * LinkedHashMap. If the LinkedHashMap previously contained a mapping for * this key, the old value is replaced. The mapping entry is also appended * to the end of the ordered linked list. * * @param key key with which the specified value is to be associated. * @param value value to be associated with the specified key. * @return previous value associated with specified key, or null if there * was no mapping for key. A null return can also indicate that * the LinkedHashMap previously associated null with the specified * key. */ public Object put(Object key, Object value) { return putAhead(key, value, header); } /** * Removes the mapping for this key from this LinkedHashMap if present. * The mapping would also be removed from the double linked list. * * @param key key whose mapping is to be removed from the Map. * @return previous value associated with specified key, or null if there * was no mapping for key. A null return can also indicate that * the LinkedHashMap previously associated null with the specified * key. */ public Object remove(Object key) { Entry tab[] = table; if (key != null) { int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { modCount++; if (prev != null) prev.next = e.next; else tab[index] = e.next; count--; Object oldValue = e.value; e.value = null; listRemove(e); return oldValue; } } } else { for (Entry e = tab[0], prev = null; e != null; prev = e, e = e.next) { if (e.key == null) { modCount++; if (prev != null) prev.next = e.next; else tab[0] = e.next; count--; Object oldValue = e.value; e.value = null; listRemove(e); return oldValue; } } } return null; } /** * Copies all of the mappings from the specified Map to this LinkedHashMap * These mappings will replace any mappings that this LinkedHashMap had for * any of the keys currently in the specified Map. * * @param t Mappings to be stored in this Map. */ public void putAll(Map t) { Iterator i = t.entrySet().iterator(); while (i.hasNext()) { Map.Entry e = (Map.Entry) i.next(); put(e.getKey(), e.getValue()); } } /** * Removes all mappings from this LinkedHashMap. */ public void clear() { Entry tab[] = table; modCount++; for (int index = tab.length; --index >= 0; ) tab[index] = null; count = 0; header.before = header.after = header; } /** * Returns a shallow copy of this LinkedHashMap. The keys and values * themselves are not cloned. */ public Object clone() { return new LinkedHashMap(this); } // Views private transient Set keySet = null; private transient Set entries = null; private transient Collection values = null; /** * Returns a Set view of the keys contained in this LinkedHashMap. The Set * is backed by the LinkedHashMap, so changes to the LinkedHashMap are * reflected in the Set, and vice-versa. The Set supports element removal, * which removes the corresponding mapping from the LinkedHashMap, via the * Iterator.remove, Set.remove, removeAll retainAll, and clear operations. * It does not support the add or addAll operations. */ public Set keySet() { if (keySet == null) { keySet = new AbstractSet() { public Iterator iterator() { return new HashIterator(KEYS); } public int size() { return count; } public boolean contains(Object o) { return containsKey(o); } public boolean remove(Object o) { return LinkedHashMap.this.remove(o) != null; } public void clear() { LinkedHashMap.this.clear(); } }; } return keySet; } /** * Returns a Collection view of the values contained in this LinkedHashMap. * The Collection is backed by the LinkedHashMap, so changes to the * LinkedHashMap are reflected in the Collection, and vice-versa. The * Collection supports element removal, which removes the corresponding * mapping from the LinkedHashMap, via the Iterator.remove, * Collection.remove, removeAll, retainAll and clear operations. It does * not support the add or addAll operations. */ public Collection values() { if (values==null) { values = new AbstractCollection() { public Iterator iterator() { return new HashIterator(VALUES); } public int size() { return count; } public boolean contains(Object o) { return containsValue(o); } public void clear() { LinkedHashMap.this.clear(); } }; } return values; } /** * Returns a Collection view of the mappings contained in this * LinkedHashMap. Each element in the returned collection is a Map.Entry. * The Collection is backed by the LinkedHashMap, so changes to the * LinkedHashMap are reflected in the Collection, and vice-versa. The * Collection supports element removal, which removes the corresponding * mapping from the LinkedHashMap, via the Iterator.remove, * Collection.remove, removeAll, retainAll and clear operations. It does * not support the add or addAll operations. * * @see java.util.Map.Entry */ public Set entrySet() { if (entries==null) { entries = new AbstractSet() { public Iterator iterator() { return new HashIterator(ENTRIES); } public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry entry = (Map.Entry)o; Object key = entry.getKey(); Entry tab[] = table; int hash = (key==null ? 0 : key.hashCode()); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry e = tab[index]; e != null; e = e.next) if (e.hash==hash && e.equals(entry)) return true; return false; } public boolean remove(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry entry = (Map.Entry)o; Object key = entry.getKey(); Entry tab[] = table; int hash = (key==null ? 0 : key.hashCode()); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) { if (e.hash==hash && e.equals(entry)) { modCount++; if (prev != null) prev.next = e.next; else tab[index] = e.next; count--; e.value = null; listRemove(e); return true; } } return false; } public int size() { return count; } public void clear() { LinkedHashMap.this.clear(); } }; } return entries; } /** * Compares the specified Object with this Map for equality. * Returns true if the given object is also a LinkedHashMap and the two * Maps represent the same mappings in the same order. More formally, * two Maps t1 and t2 represent the same mappings * if t1.keySet().equals(t2.keySet()) and for every * key k in t1.keySet(), * (t1.get(k)==null ? t2.get(k)==null : t1.get(k).equals(t2.get(k))) * . *

* This implementation first checks if the specified Object is this Map; * if so it returns true. Then, it checks if the specified Object is * a Map whose size is identical to the size of this Set; if not, it * it returns false. If so, it iterates over this Map and the specified * Map's entrySet() Collection, and checks that the specified Map contains * each mapping that this Map contains at the same position. If the * specified Map fails to contain such a mapping in the right order, false * is returned. If the iteration completes, true is returned. * * @param o Object to be compared for equality with this Map. * @return true if the specified Object is equal to this Map. * */ public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof LinkedHashMap)) return false; LinkedHashMap t = (LinkedHashMap) o; if (t.size() != size()) return false; Iterator i1 = entrySet().iterator(); Iterator i2 = t.entrySet().iterator(); while (i1.hasNext()) { Entry e1 = (Entry) i1.next(); Entry e2 = (Entry) i2.next(); Object key1 = e1.getKey(); Object value1 = e1.getValue(); Object key2 = e2.getKey(); Object value2 = e2.getValue(); if ((key1 == null ? key2 == null : key1.equals(key2)) && (value1 == null ? value2 == null : value1.equals(value2))) { continue; } else { return false; } } return true; } /** * LinkedHashMap collision list entry. */ private static class Entry implements Map.Entry { int hash; Object key; Object value; Entry next; // These fields comprise the doubly linked list that is used for // iteration. Entry before, after; Entry(int hash, Object key, Object value, Entry next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } // Map.Entry Ops public Object getKey() { return key; } public Object getValue() { return value; } public Object setValue(Object value) { Object oldValue = this.value; this.value = value; return oldValue; } public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; return (key==null ? e.getKey()==null : key.equals(e.getKey())) && (value==null ? e.getValue()==null : value.equals(e.getValue())); } public int hashCode() { return hash ^ (value==null ? 0 : value.hashCode()); } public String toString() { return key+"="+value; } } // Types of Iterators private static final int KEYS = 0; private static final int VALUES = 1; private static final int ENTRIES = 2; private class HashIterator implements Iterator { private Entry[] table = LinkedHashMap.this.table; private Entry entry = null; private Entry lastReturned = null; private int type; /** * The modCount value that the iterator believes that the backing * List should have. If this expectation is violated, the iterator * has detected concurrent modification. */ private int expectedModCount = modCount; HashIterator(int type) { this.type = type; this.entry = LinkedHashMap.this.header.after; } public boolean hasNext() { return entry != header; } public Object next() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (entry == LinkedHashMap.this.header) throw new NoSuchElementException(); Entry e = lastReturned = entry; entry = e.after; return type == KEYS ? e.key : (type == VALUES ? e.value : e); } public void remove() { if (lastReturned == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry[] tab = LinkedHashMap.this.table; int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length; for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) { if (e == lastReturned) { modCount++; expectedModCount++; if (prev == null) tab[index] = e.next; else prev.next = e.next; count--; listRemove(e); lastReturned = null; return; } } throw new ConcurrentModificationException(); } } /** * Save the state of the LinkedHashMap to a stream (i.e., serialize it). * The objects will be written out in the order they are linked * in the list. */ private void writeObject(java.io.ObjectOutputStream s) throws IOException { // Write out the threshold, loadfactor, and any hidden stuff s.defaultWriteObject(); // Write out number of buckets s.writeInt(table.length); // Write out size (number of Mappings) s.writeInt(count); // Write out keys and values (alternating) for (Entry e = header.after; e != header; e = e.after) { s.writeObject(e.key); s.writeObject(e.value); } } /** * Reconstitute the LinkedHashMap from a stream (i.e., deserialize it). */ private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { // Read in the threshold, loadfactor, and any hidden stuff s.defaultReadObject(); // Read in number of buckets and allocate the bucket array; int numBuckets = s.readInt(); table = new Entry[numBuckets]; header = new Entry(-1, null, null, null); header.before = header; header.after = header; // Read in size (number of Mappings) int size = s.readInt(); // Read the keys and values, and put the mappings in the LinkedHashMap for (int i=0; i