/*
* Copyright (c) 2002, 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.
*
* 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 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
* remove 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 remove operation).
*
* @param value new value to be stored in this entry.
* @return old value corresponding to the entry.
*
* @throws UnsupportedOperationException if the put 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
* null values, and the specified value is
* null.
*/
Object setValue(Object value) {
Object oldValue = this.value;
this.value = value;
return oldValue;
}
/**
* Compares the specified object with this entry for equality.
* Returns true if the given object is also a map entry and
* the two entries represent the same mapping. More formally, two
* entries e1 and e2 represent the same mapping
* if
* (e1.getKey()==null ?
* e2.getKey()==null : e1.getKey().equals(e2.getKey())) &&
* (e1.getValue()==null ?
* e2.getValue()==null : e1.getValue().equals(e2.getValue()))
*
* This ensures that the equals method works properly across
* different implementations of the Map.Entry interface.
*
* @param o object to be compared for equality with this map entry.
* @return true 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 e is defined to be:
* (e.getKey()==null ? 0 : e.getKey().hashCode()) ^
* (e.getValue()==null ? 0 : e.getValue().hashCode())
*
* This ensures that e1.equals(e2) implies that
* e1.hashCode()==e2.hashCode() for any two Entries
* e1 and e2, as required by the general
* contract of Object.hashCode.
*
* @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 0.75.
*
* @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 0.75.
*/
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 true if this map contains no key-value mappings.
*
* @return true 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
* null if the map contains no mapping for this key. A return
* value of null does not necessarily indicate that the
* map contains no mapping for the key; it's also possible that the map
* explicitly maps the key to null. The containsKey
* 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 true if this map contains a mapping for the specified
* key.
*
* @return true 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 true 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 true 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 null
* if there was no mapping for key. A null return can
* also indicate that the HashMap previously associated
* null 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 null
* if there was no mapping for key. A null return can
* also indicate that the map previously associated null
* 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 HashMap 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;
}
}