/* * 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. * <p> * 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. * <p> * An instance of LinkedHashMap has two parameters that affect its efficiency: * its <i>capacity</i> and its <i>load factor</i>. 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. * <p> * 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. * <p> * <strong>Note that this implementation is not synchronized.</strong> If * multiple threads access a LinkedHashMap concurrently, and at least one of the * threads modifies the LinkedHashMap structurally, it <em>must</em> 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: * <pre> *      Map m = Collections.synchronizedMap(new LinkedHashMap(...)); * </pre> * <p> * The Iterators returned by the iterator methods of the Collections returned * by all of LinkedHashMap's "collection view methods" are <em>fail-fast</em>: * 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 <em>necessarily</em> 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;                }            }        } 

Lines 1–500 of 904. Load more