--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/agent/src/share/classes/sun/jvm/hotspot/debugger/LongHashMap.java	Sat Dec 01 00:00:00 2007 +0000
@@ -0,0 +1,464 @@
+/*
+ * Copyright 2002 Sun Microsystems, Inc.  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.
+ *
+ * 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ *
+ */
+
+package sun.jvm.hotspot.debugger;
+
+import java.util.*;
+
+/**
+ * This is a copy of java.util.HashMap which uses longs as keys
+ * instead of Objects. It turns out that using this in the PageCache
+ * implementation speeds up heap traversals by a factor of three.
+ *
+ * @author  Josh Bloch
+ * @author Arthur van Hoff
+ */
+
+public class LongHashMap
+{
+    static class Entry {
+        private int    hash;
+        private long   key;
+        private Object value;
+        private Entry  next;
+
+        Entry(int hash, long key, Object value, Entry next) {
+            this.hash  = hash;
+            this.key   = key;
+            this.value = value;
+            this.next  = next;
+        }
+
+        /**
+         * Returns the key corresponding to this entry.
+         *
+         * @return the key corresponding to this entry.
+         */
+        long getKey() { return key; }
+
+        /**
+         * Returns the value corresponding to this entry.  If the mapping
+         * has been removed from the backing map (by the iterator's
+         * <tt>remove</tt> operation), the results of this call are undefined.
+         *
+         * @return the value corresponding to this entry.
+         */
+        Object getValue() { return value; }
+
+        /**
+         * Replaces the value corresponding to this entry with the specified
+         * value (optional operation).  (Writes through to the map.)  The
+         * behavior of this call is undefined if the mapping has already been
+         * removed from the map (by the iterator's <tt>remove</tt> operation).
+         *
+         * @param value new value to be stored in this entry.
+         * @return old value corresponding to the entry.
+         *
+         * @throws UnsupportedOperationException if the <tt>put</tt> operation
+         *            is not supported by the backing map.
+         * @throws ClassCastException if the class of the specified value
+         *            prevents it from being stored in the backing map.
+         * @throws    IllegalArgumentException if some aspect of this value
+         *            prevents it from being stored in the backing map.
+         * @throws NullPointerException the backing map does not permit
+         *            <tt>null</tt> values, and the specified value is
+         *            <tt>null</tt>.
+         */
+        Object setValue(Object value) {
+            Object oldValue = this.value;
+            this.value = value;
+            return oldValue;
+        }
+
+        /**
+         * Compares the specified object with this entry for equality.
+         * Returns <tt>true</tt> if the given object is also a map entry and
+         * the two entries represent the same mapping.  More formally, two
+         * entries <tt>e1</tt> and <tt>e2</tt> represent the same mapping
+         * if<pre>
+         *     (e1.getKey()==null ?
+         *      e2.getKey()==null : e1.getKey().equals(e2.getKey()))  &&
+         *     (e1.getValue()==null ?
+         *      e2.getValue()==null : e1.getValue().equals(e2.getValue()))
+         * </pre>
+         * This ensures that the <tt>equals</tt> method works properly across
+         * different implementations of the <tt>Map.Entry</tt> interface.
+         *
+         * @param o object to be compared for equality with this map entry.
+         * @return <tt>true</tt> if the specified object is equal to this map
+         *         entry.
+         */
+        public boolean equals(Object o) {
+            if (!(o instanceof Entry))
+                return false;
+            Entry e = (Entry)o;
+            return (key == e.getKey()) && eq(value, e.getValue());
+        }
+
+        /**
+         * Returns the hash code value for this map entry.  The hash code
+         * of a map entry <tt>e</tt> is defined to be: <pre>
+         *     (e.getKey()==null   ? 0 : e.getKey().hashCode()) ^
+         *     (e.getValue()==null ? 0 : e.getValue().hashCode())
+         * </pre>
+         * This ensures that <tt>e1.equals(e2)</tt> implies that
+         * <tt>e1.hashCode()==e2.hashCode()</tt> for any two Entries
+         * <tt>e1</tt> and <tt>e2</tt>, as required by the general
+         * contract of <tt>Object.hashCode</tt>.
+         *
+         * @return the hash code value for this map entry.
+         * @see Object#hashCode()
+         * @see Object#equals(Object)
+         * @see #equals(Object)
+         */
+        public int hashCode() {
+            return hash ^ (value==null ? 0 : value.hashCode());
+        }
+    }
+
+    /**
+     * The hash table data.
+     */
+    transient Entry table[];
+
+    /**
+     * The total number of mappings in the hash table.
+     */
+    transient int size;
+
+    /**
+     * The table is rehashed when its size exceeds this threshold.  (The
+     * value of this field is (int)(capacity * loadFactor).)
+     *
+     * @serial
+     */
+    int threshold;
+
+    /**
+     * The load factor for the hash table.
+     *
+     * @serial
+     */
+    final float loadFactor;
+
+    /**
+     * The number of times this HashMap has been structurally modified
+     * Structural modifications are those that change the number of mappings in
+     * the HashMap or otherwise modify its internal structure (e.g.,
+     * rehash).  This field is used to make iterators on Collection-views of
+     * the HashMap fail-fast.  (See ConcurrentModificationException).
+     */
+    transient int modCount = 0;
+
+    /**
+     * Constructs a new, empty map with the specified initial
+     * capacity and the specified load factor.
+     *
+     * @param      initialCapacity   the initial capacity of the HashMap.
+     * @param      loadFactor        the load factor of the HashMap
+     * @throws     IllegalArgumentException  if the initial capacity is less
+     *               than zero, or if the load factor is nonpositive.
+     */
+    public LongHashMap(int initialCapacity, float loadFactor) {
+        if (initialCapacity < 0)
+            throw new IllegalArgumentException("Illegal Initial Capacity: "+
+                                               initialCapacity);
+        if (loadFactor <= 0 || Float.isNaN(loadFactor))
+            throw new IllegalArgumentException("Illegal Load factor: "+
+                                               loadFactor);
+        if (initialCapacity==0)
+            initialCapacity = 1;
+        this.loadFactor = loadFactor;
+        table = new Entry[initialCapacity];
+        threshold = (int)(initialCapacity * loadFactor);
+    }
+
+    /**
+     * Constructs a new, empty map with the specified initial capacity
+     * and default load factor, which is <tt>0.75</tt>.
+     *
+     * @param   initialCapacity   the initial capacity of the HashMap.
+     * @throws    IllegalArgumentException if the initial capacity is less
+     *              than zero.
+     */
+    public LongHashMap(int initialCapacity) {
+        this(initialCapacity, 0.75f);
+    }
+
+    /**
+     * Constructs a new, empty map with a default capacity and load
+     * factor, which is <tt>0.75</tt>.
+     */
+    public LongHashMap() {
+        this(11, 0.75f);
+    }
+
+    /**
+     * Returns the number of key-value mappings in this map.
+     *
+     * @return the number of key-value mappings in this map.
+     */
+    public int size() {
+        return size;
+    }
+
+    /**
+     * Returns <tt>true</tt> if this map contains no key-value mappings.
+     *
+     * @return <tt>true</tt> if this map contains no key-value mappings.
+     */
+    public boolean isEmpty() {
+        return size == 0;
+    }
+
+    /**
+     * Returns the value to which this map maps the specified key.  Returns
+     * <tt>null</tt> if the map contains no mapping for this key.  A return
+     * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
+     * map contains no mapping for the key; it's also possible that the map
+     * explicitly maps the key to <tt>null</tt>.  The <tt>containsKey</tt>
+     * operation may be used to distinguish these two cases.
+     *
+     * @return the value to which this map maps the specified key.
+     * @param key key whose associated value is to be returned.
+     */
+    public Object get(long key) {
+        Entry e = getEntry(key);
+        return (e == null ? null : e.value);
+    }
+
+    /**
+     * Returns <tt>true</tt> if this map contains a mapping for the specified
+     * key.
+     *
+     * @return <tt>true</tt> if this map contains a mapping for the specified
+     * key.
+     * @param key key whose presence in this Map is to be tested.
+     */
+    public boolean containsKey(long key) {
+        return getEntry(key) != null;
+    }
+
+    /**
+     * Returns the entry associated with the specified key in the
+     * HashMap.  Returns null if the HashMap contains no mapping
+     * for this key.
+     */
+    Entry getEntry(long key) {
+        Entry tab[] = table;
+        int hash = (int) key;
+        int index = (hash & 0x7FFFFFFF) % tab.length;
+
+        for (Entry e = tab[index]; e != null; e = e.next)
+            if (e.hash == hash && e.key ==key)
+                return e;
+
+        return null;
+    }
+
+    /**
+     * Returns <tt>true</tt> if this map maps one or more keys to the
+     * specified value.
+     *
+     * @param value value whose presence in this map is to be tested.
+     * @return <tt>true</tt> if this map maps one or more keys to the
+     *         specified value.
+     */
+    public boolean containsValue(Object value) {
+        Entry tab[] = table;
+
+        if (value==null) {
+            for (int i = tab.length ; i-- > 0 ;)
+                for (Entry e = tab[i] ; e != null ; e = e.next)
+                    if (e.value==null)
+                        return true;
+        } else {
+            for (int i = tab.length ; i-- > 0 ;)
+                for (Entry e = tab[i] ; e != null ; e = e.next)
+                    if (value.equals(e.value))
+                        return true;
+        }
+
+        return false;
+    }
+
+    /**
+     * Associates the specified value with the specified key in this map.
+     * If the map previously contained a mapping for this key, the old
+     * value is replaced.
+     *
+     * @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 <tt>null</tt>
+     *         if there was no mapping for key.  A <tt>null</tt> return can
+     *         also indicate that the HashMap previously associated
+     *         <tt>null</tt> with the specified key.
+     */
+    public Object put(long key, Object value) {
+        Entry tab[] = table;
+        int hash = (int) key;
+        int index = (hash & 0x7FFFFFFF) % tab.length;
+
+        // Look for entry in hash table
+        for (Entry e = tab[index] ; e != null ; e = e.next) {
+            if (e.hash == hash && e.key == key) {
+                Object oldValue = e.value;
+                e.value = value;
+                return oldValue;
+            }
+        }
+
+        // It's not there; grow the hash table if necessary...
+        modCount++;
+        if (size >= threshold) {
+            rehash();
+            tab = table;
+            index = (hash & 0x7FFFFFFF) % tab.length;
+        }
+
+        // ...and add the entry
+        size++;
+        tab[index] = newEntry(hash, key, value, tab[index]);
+        return null;
+    }
+
+    /**
+     * Removes the mapping for this key from this map if present.
+     *
+     * @param key key whose mapping is to be removed from the map.
+     * @return previous value associated with specified key, or <tt>null</tt>
+     *         if there was no mapping for key.  A <tt>null</tt> return can
+     *         also indicate that the map previously associated <tt>null</tt>
+     *         with the specified key.
+     */
+    public Object remove(long key) {
+        Entry e = removeEntryForKey(key);
+        return (e == null ? null : e.value);
+    }
+
+    /**
+     * Removes and returns the entry associated with the specified key
+     * in the HashMap.  Returns null if the HashMap contains no mapping
+     * for this key.
+     */
+    Entry removeEntryForKey(long key) {
+        Entry tab[] = table;
+        int hash = (int) key;
+        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 == key) {
+                modCount++;
+                if (prev != null)
+                    prev.next = e.next;
+                else
+                    tab[index] = e.next;
+
+                size--;
+                return e;
+            }
+        }
+
+        return null;
+    }
+
+    /**
+     * Removes the specified entry from this HashMap (and increments modCount).
+     *
+     * @throws ConcurrentModificationException if the entry is not in the Map
+     */
+    void removeEntry(Entry doomed) {
+        Entry[] tab = table;
+        int index = (doomed.hash & 0x7FFFFFFF) % tab.length;
+
+        for (Entry e = tab[index], prev = null; e != null;
+             prev = e, e = e.next) {
+            if (e == doomed) {
+                modCount++;
+                if (prev == null)
+                    tab[index] = e.next;
+                else
+                    prev.next = e.next;
+                size--;
+                return;
+            }
+        }
+        throw new ConcurrentModificationException();
+    }
+
+    /**
+     * Removes all mappings from this map.
+     */
+    public void clear() {
+        Entry tab[] = table;
+        modCount++;
+        for (int index = tab.length; --index >= 0; )
+            tab[index] = null;
+        size = 0;
+    }
+
+    /**
+     * Rehashes the contents of this map into a new <tt>HashMap</tt> instance
+     * with a larger capacity. This method is called automatically when the
+     * number of keys in this map exceeds its capacity and load factor.
+     */
+    void rehash() {
+        Entry oldTable[] = table;
+        int oldCapacity = oldTable.length;
+        int newCapacity = oldCapacity * 2 + 1;
+        Entry newTable[] = new Entry[newCapacity];
+
+        modCount++;
+        threshold = (int)(newCapacity * loadFactor);
+        table = newTable;
+
+        for (int i = oldCapacity ; i-- > 0 ;) {
+            for (Entry old = oldTable[i] ; old != null ; ) {
+                Entry e = old;
+                old = old.next;
+
+                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
+                e.next = newTable[index];
+                newTable[index] = e;
+            }
+        }
+    }
+
+    static boolean eq(Object o1, Object o2) {
+        return (o1==null ? o2==null : o1.equals(o2));
+    }
+
+    Entry newEntry(int hash, long key, Object value, Entry next) {
+        return new Entry(hash, key, value, next);
+    }
+
+    int capacity() {
+        return table.length;
+    }
+
+    float loadFactor() {
+        return loadFactor;
+    }
+}