FastMap.java
package org.codehaus.plexus.util;
/*
* J.A.D.E. Java(TM) Addition to Default Environment.
* Latest release available at http://jade.dautelle.com/
* This class is public domain (not copyrighted).
*/
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.AbstractCollection;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
/**
* <p>
* This class represents a <code>Map</code> collection with real-time behavior. Unless the map's size exceeds its
* current capacity, no dynamic memory allocation is ever performed and response time is <b>extremely fast</b> and
* <b>consistent</b>.
* </p>
* <p>
* Our <a href="http://jade.dautelle.com/doc/benchmark.txt">benchmark</a> indicates that {@link FastMap#put
* FastMap.put(key, value)} is up to <b>5x faster</b> than <code>java.util.HashMap.put(key, value)</code>. This
* difference is mostly due to the cost of the <code>Map.Entry</code> allocations that {@link FastMap} avoids by
* recycling its entries (see note below).
* </p>
* <p>
* {@link FastMap} has a predictable iteration order, which is the order in which keys were inserted into the map
* (similar to <code>java.util.LinkedHashMap</code> collection class).
* </p>
* <p>
* Applications may change the resizing policy of {@link FastMap} by overriding the {@link #sizeChanged} method. For
* example, to improve predictability, automatic resizing can be disabled.
* </p>
* <p>
* This implementation is not synchronized. Multiple threads accessing or modifying the collection must be synchronized
* externally.
* </p>
* <p>
* <b>Note:</b> To avoid dynamic memory allocations, {@link FastMap} maintains an internal pool of
* <code>Map.Entry</code> objects. The size of the pool is determined by the map's capacity. When an entry is removed
* from the map, it is automatically restored to the pool.
* </p>
* <p>
* <i> This class is <b>public domain</b> (not copyrighted).</i>
* </p>
*
* @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
* @version 5.3, October 31 2003
*/
public class FastMap<K, V> implements Map<K, V>, Cloneable, Serializable {
/**
* Holds the map's hash table.
*/
private transient EntryImpl[] _entries;
/**
* Holds the map's current capacity.
*/
private transient int _capacity;
/**
* Holds the hash code mask.
*/
private transient int _mask;
/**
* Holds the first pool entry (linked list).
*/
private transient EntryImpl _poolFirst;
/**
* Holds the first map entry (linked list).
*/
private transient EntryImpl _mapFirst;
/**
* Holds the last map entry (linked list).
*/
private transient EntryImpl _mapLast;
/**
* Holds the current size.
*/
private transient int _size;
/**
* Creates a {@link FastMap} with a capacity of <code>256</code> entries.
*/
public FastMap() {
initialize(256);
}
/**
* Creates a {@link FastMap}, copy of the specified <code>Map</code>. If the specified map is not an instance of
* {@link FastMap}, the newly created map has a capacity set to the specified map's size. The copy has the same
* order as the original, regardless of the original map's implementation:
*
* <pre>
* TreeMap dictionary = ...;
* FastMap dictionaryLookup = new FastMap(dictionary);
* </pre>
*
* @param map the map whose mappings are to be placed in this map.
*/
public FastMap(Map map) {
int capacity = (map instanceof FastMap) ? ((FastMap) map).capacity() : map.size();
initialize(capacity);
putAll(map);
}
/**
* Creates a {@link FastMap} with the specified capacity. Unless the capacity is exceeded, operations on this map do
* not allocate entries. For optimum performance, the capacity should be of the same order of magnitude or larger
* than the expected map's size.
*
* @param capacity the number of buckets in the hash table; it also defines the number of pre-allocated entries.
*/
public FastMap(int capacity) {
initialize(capacity);
}
/**
* Returns the number of key-value mappings in this {@link FastMap}.
*
* @return this map's size.
*/
@Override
public int size() {
return _size;
}
/**
* Returns the capacity of this {@link FastMap}. The capacity defines the number of buckets in the hash table, as
* well as the maximum number of entries the map may contain without allocating memory.
*
* @return this map's capacity.
*/
public int capacity() {
return _capacity;
}
/**
* Indicates if this {@link FastMap} contains no key-value mappings.
*
* @return <code>true</code> if this map contains no key-value mappings; <code>false</code> otherwise.
*/
@Override
public boolean isEmpty() {
return _size == 0;
}
/**
* Indicates if this {@link FastMap} contains a mapping for the specified key.
*
* @param key the key whose presence in this map is to be tested.
* @return <code>true</code> if this map contains a mapping for the specified key; <code>false</code> otherwise.
* @throws NullPointerException if the key is <code>null</code>.
*/
@Override
public boolean containsKey(Object key) {
EntryImpl entry = _entries[keyHash(key) & _mask];
while (entry != null) {
if (key.equals(entry._key)) {
return true;
}
entry = entry._next;
}
return false;
}
/**
* Indicates if this {@link FastMap} maps one or more keys to the specified value.
*
* @param value the value whose presence in this map is to be tested.
* @return <code>true</code> if this map maps one or more keys to the specified value.
* @throws NullPointerException if the key is <code>null</code>.
*/
@Override
public boolean containsValue(Object value) {
EntryImpl entry = _mapFirst;
while (entry != null) {
if (value.equals(entry._value)) {
return true;
}
entry = entry._after;
}
return false;
}
/**
* Returns the value to which this {@link FastMap} maps the specified key.
*
* @param key the key whose associated value is to be returned.
* @return the value to which this map maps the specified key, or <code>null</code> if there is no mapping for the
* key.
* @throws NullPointerException if key is <code>null</code>.
*/
@Override
public V get(Object key) {
EntryImpl<K, V> entry = _entries[keyHash(key) & _mask];
while (entry != null) {
if (key.equals(entry._key)) {
return entry._value;
}
entry = entry._next;
}
return null;
}
/**
* Returns the entry with the specified key.
*
* @param key the key whose associated entry is to be returned.
* @return the entry for the specified key or <code>null</code> if none.
*/
public Map.Entry getEntry(Object key) {
EntryImpl entry = _entries[keyHash(key) & _mask];
while (entry != null) {
if (key.equals(entry._key)) {
return entry;
}
entry = entry._next;
}
return null;
}
/**
* Associates the specified value with the specified key in this {@link FastMap}. If the {@link FastMap} previously
* contained a mapping for this key, the old value is replaced.
*
* @param key the key with which the specified value is to be associated.
* @param value the value to be associated with the specified key.
* @return the previous value associated with specified key, or <code>null</code> if there was no mapping for key. A
* <code>null</code> return can also indicate that the map previously associated <code>null</code> with the
* specified key.
* @throws NullPointerException if the key is <code>null</code>.
*/
@Override
public Object put(Object key, Object value) {
EntryImpl entry = _entries[keyHash(key) & _mask];
while (entry != null) {
if (key.equals(entry._key)) {
Object prevValue = entry._value;
entry._value = value;
return prevValue;
}
entry = entry._next;
}
// No previous mapping.
addEntry(key, value);
return null;
}
/**
* Copies all of the mappings from the specified map to this {@link FastMap}.
*
* @param map the mappings to be stored in this map.
* @throws NullPointerException the specified map is <code>null</code>, or the specified map contains
* <code>null</code> keys.
*/
@Override
public void putAll(Map<? extends K, ? extends V> map) {
for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
addEntry(entry.getKey(), entry.getValue());
}
}
/**
* Removes the mapping for this key from this {@link FastMap} if present.
*
* @param key the key whose mapping is to be removed from the map.
* @return previous value associated with specified key, or <code>null</code> if there was no mapping for key. A
* <code>null</code> return can also indicate that the map previously associated <code>null</code> with the
* specified key.
* @throws NullPointerException if the key is <code>null</code>.
*/
@Override
public V remove(Object key) {
EntryImpl<K, V> entry = _entries[keyHash(key) & _mask];
while (entry != null) {
if (key.equals(entry._key)) {
V prevValue = entry._value;
removeEntry(entry);
return prevValue;
}
entry = entry._next;
}
return null;
}
/**
* Removes all mappings from this {@link FastMap}.
*/
@Override
public void clear() {
// Clears all keys, values and buckets linked lists.
for (EntryImpl entry = _mapFirst; entry != null; entry = entry._after) {
entry._key = null;
entry._value = null;
entry._before = null;
entry._next = null;
if (entry._previous == null) { // First in bucket.
_entries[entry._index] = null;
} else {
entry._previous = null;
}
}
// Recycles all entries.
if (_mapLast != null) {
_mapLast._after = _poolFirst; // Connects to pool.
_poolFirst = _mapFirst;
_mapFirst = null;
_mapLast = null;
_size = 0;
sizeChanged();
}
}
/**
* Changes the current capacity of this {@link FastMap}. If the capacity is increased, new entries are allocated and
* added to the pool. If the capacity is decreased, entries from the pool are deallocated (and are eventually
* garbage collected). The capacity also determined the number of buckets for the hash table.
*
* @param newCapacity the new capacity of this map.
*/
public void setCapacity(int newCapacity) {
if (newCapacity > _capacity) { // Capacity increases.
for (int i = _capacity; i < newCapacity; i++) {
EntryImpl entry = new EntryImpl();
entry._after = _poolFirst;
_poolFirst = entry;
}
} else if (newCapacity < _capacity) { // Capacity decreases.
for (int i = newCapacity; (i < _capacity) && (_poolFirst != null); i++) {
// Disconnects the entry for gc to do its work.
EntryImpl entry = _poolFirst;
_poolFirst = entry._after;
entry._after = null; // All pointers are now null!
}
}
// Find a power of 2 >= capacity
int tableLength = 16;
while (tableLength < newCapacity) {
tableLength <<= 1;
}
// Checks if the hash table has to be re-sized.
if (_entries.length != tableLength) {
_entries = new EntryImpl[tableLength];
_mask = tableLength - 1;
// Repopulates the hash table.
EntryImpl entry = _mapFirst;
while (entry != null) {
int index = keyHash(entry._key) & _mask;
entry._index = index;
// Connects to bucket.
entry._previous = null; // Resets previous.
EntryImpl next = _entries[index];
entry._next = next;
if (next != null) {
next._previous = entry;
}
_entries[index] = entry;
entry = entry._after;
}
}
_capacity = newCapacity;
}
/**
* Returns a shallow copy of this {@link FastMap}. The keys and the values themselves are not cloned.
*
* @return a shallow copy of this map.
*/
@Override
public Object clone() {
try {
FastMap clone = (FastMap) super.clone();
clone.initialize(_capacity);
clone.putAll(this);
return clone;
} catch (CloneNotSupportedException e) {
// Should not happen, since we are Cloneable.
throw new InternalError();
}
}
/**
* Compares the specified object with this {@link FastMap} for equality. Returns <code>true</code> if the given
* object is also a map and the two maps represent the same mappings (regardless of collection iteration order).
*
* @param obj the object to be compared for equality with this map.
* @return <code>true</code> if the specified object is equal to this map; <code>false</code> otherwise.
*/
@Override
public boolean equals(Object obj) {
if (obj == this) {
return true;
} else if (obj instanceof Map) {
Map that = (Map) obj;
if (this.size() == that.size()) {
EntryImpl entry = _mapFirst;
while (entry != null) {
if (!that.entrySet().contains(entry)) {
return false;
}
entry = entry._after;
}
return true;
} else {
return false;
}
} else {
return false;
}
}
/**
* Returns the hash code value for this {@link FastMap}.
*
* @return the hash code value for this map.
*/
@Override
public int hashCode() {
int code = 0;
EntryImpl entry = _mapFirst;
while (entry != null) {
code += entry.hashCode();
entry = entry._after;
}
return code;
}
/**
* Returns a <code>String</code> representation of this {@link FastMap}.
*
* @return <code>this.entrySet().toString();</code>
*/
@Override
public String toString() {
return entrySet().toString();
}
/**
* Returns a collection view of the values contained in this {@link FastMap}. The collection is backed by the map,
* so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal,
* which removes the corresponding mapping from this map, via the <code>Iterator.remove</code>,
* <code>Collection.remove</code>, <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code>
* operations. It does not support the <code>add</code> or <code>addAll</code> operations.
*
* @return a collection view of the values contained in this map.
*/
@Override
public Collection values() {
return _values;
}
private transient Values _values;
private class Values extends AbstractCollection {
@Override
public Iterator iterator() {
return new Iterator() {
EntryImpl after = _mapFirst;
EntryImpl before;
@Override
public void remove() {
removeEntry(before);
}
@Override
public boolean hasNext() {
return after != null;
}
@Override
public Object next() {
before = after;
after = after._after;
return before._value;
}
};
}
@Override
public int size() {
return _size;
}
@Override
public boolean contains(Object o) {
return containsValue(o);
}
@Override
public void clear() {
FastMap.this.clear();
}
}
/**
* Returns a collection view of the mappings contained in this {@link FastMap}. Each element in the returned
* collection is a <code>Map.Entry</code>. The collection is backed by the map, so changes to the map are reflected
* in the collection, and vice-versa. The collection supports element removal, which removes the corresponding
* mapping from this map, via the <code>Iterator.remove</code>, <code>Collection.remove</code>,
* <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code> operations. It does not support the
* <code>add</code> or <code>addAll</code> operations.
*
* @return a collection view of the mappings contained in this map.
*/
@Override
public Set entrySet() {
return _entrySet;
}
private transient EntrySet _entrySet;
private class EntrySet extends AbstractSet {
@Override
public Iterator iterator() {
return new Iterator() {
EntryImpl after = _mapFirst;
EntryImpl before;
@Override
public void remove() {
removeEntry(before);
}
@Override
public boolean hasNext() {
return after != null;
}
@Override
public Object next() {
before = after;
after = after._after;
return before;
}
};
}
@Override
public int size() {
return _size;
}
@Override
public boolean contains(Object obj) { // Optimization.
if (obj instanceof Map.Entry) {
Map.Entry entry = (Map.Entry) obj;
Map.Entry mapEntry = getEntry(entry.getKey());
return entry.equals(mapEntry);
} else {
return false;
}
}
@Override
public boolean remove(Object obj) { // Optimization.
if (obj instanceof Map.Entry) {
Map.Entry entry = (Map.Entry) obj;
EntryImpl mapEntry = (EntryImpl) getEntry(entry.getKey());
if ((mapEntry != null) && (entry.getValue()).equals(mapEntry._value)) {
removeEntry(mapEntry);
return true;
}
}
return false;
}
}
/**
* Returns a set view of the keys contained in this {@link FastMap}. The set is backed by the map, so changes to the
* map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding
* mapping from this map, via the <code>Iterator.remove</code>, <code>Collection.remove</code>,
* <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code> operations. It does not support the
* <code>add</code> or <code>addAll</code> operations.
*
* @return a set view of the keys contained in this map.
*/
@Override
public Set keySet() {
return _keySet;
}
private transient KeySet _keySet;
private class KeySet extends AbstractSet {
@Override
public Iterator iterator() {
return new Iterator() {
EntryImpl after = _mapFirst;
EntryImpl before;
@Override
public void remove() {
removeEntry(before);
}
@Override
public boolean hasNext() {
return after != null;
}
@Override
public Object next() {
before = after;
after = after._after;
return before._key;
}
};
}
@Override
public int size() {
return _size;
}
@Override
public boolean contains(Object obj) { // Optimization.
return FastMap.this.containsKey(obj);
}
@Override
public boolean remove(Object obj) { // Optimization.
return FastMap.this.remove(obj) != null;
}
@Override
public void clear() { // Optimization.
FastMap.this.clear();
}
}
/**
* This methods is being called when the size of this {@link FastMap} has changed. The default behavior is to double
* the map's capacity when the map's size reaches the current map's capacity. Sub-class may override this method to
* implement custom resizing policies or to disable automatic resizing. For example:
*
* <pre>
* Map fixedCapacityMap = new FastMap( 256 )
* {
* protected sizeChanged()
* {
* // Do nothing, automatic resizing disabled.
* }
* };
* </pre>
*
* @see #setCapacity
*/
protected void sizeChanged() {
if (size() > capacity()) {
setCapacity(capacity() * 2);
}
}
/**
* Returns the hash code for the specified key. The formula being used is identical to the formula used by
* <code>java.util.HashMap</code> (ensures similar behavior for ill-conditioned hashcode keys).
*
* @param key the key to calculate the hashcode for.
* @return the hash code for the specified key.
*/
private static int keyHash(Object key) {
// From HashMap.hash(Object) function.
int hashCode = key.hashCode();
hashCode += ~(hashCode << 9);
hashCode ^= (hashCode >>> 14);
hashCode += (hashCode << 4);
hashCode ^= (hashCode >>> 10);
return hashCode;
}
/**
* Adds a new entry for the specified key and value.
*
* @param key the entry's key.
* @param value the entry's value.
*/
private void addEntry(Object key, Object value) {
EntryImpl entry = _poolFirst;
if (entry != null) {
_poolFirst = entry._after;
entry._after = null;
} else { // Pool empty.
entry = new EntryImpl();
}
// Setup entry parameters.
entry._key = key;
entry._value = value;
int index = keyHash(key) & _mask;
entry._index = index;
// Connects to bucket.
EntryImpl next = _entries[index];
entry._next = next;
if (next != null) {
next._previous = entry;
}
_entries[index] = entry;
// Connects to collection.
if (_mapLast != null) {
entry._before = _mapLast;
_mapLast._after = entry;
} else {
_mapFirst = entry;
}
_mapLast = entry;
// Updates size.
_size++;
sizeChanged();
}
/**
* Removes the specified entry from the map.
*
* @param entry the entry to be removed.
*/
private void removeEntry(EntryImpl entry) {
// Removes from bucket.
EntryImpl previous = entry._previous;
EntryImpl next = entry._next;
if (previous != null) {
previous._next = next;
entry._previous = null;
} else { // First in bucket.
_entries[entry._index] = next;
}
if (next != null) {
next._previous = previous;
entry._next = null;
} // Else do nothing, no last pointer.
// Removes from collection.
EntryImpl before = entry._before;
EntryImpl after = entry._after;
if (before != null) {
before._after = after;
entry._before = null;
} else { // First in collection.
_mapFirst = after;
}
if (after != null) {
after._before = before;
} else { // Last in collection.
_mapLast = before;
}
// Clears value and key.
entry._key = null;
entry._value = null;
// Recycles.
entry._after = _poolFirst;
_poolFirst = entry;
// Updates size.
_size--;
sizeChanged();
}
/**
* Initializes this instance for the specified capacity. Once initialized, operations on this map should not create
* new objects (unless the map's size exceeds the specified capacity).
*
* @param capacity the initial capacity.
*/
private void initialize(int capacity) {
// Find a power of 2 >= capacity
int tableLength = 16;
while (tableLength < capacity) {
tableLength <<= 1;
}
// Allocates hash table.
_entries = new EntryImpl[tableLength];
_mask = tableLength - 1;
_capacity = capacity;
_size = 0;
// Allocates views.
_values = new Values();
_entrySet = new EntrySet();
_keySet = new KeySet();
// Resets pointers.
_poolFirst = null;
_mapFirst = null;
_mapLast = null;
// Allocates entries.
for (int i = 0; i < capacity; i++) {
EntryImpl entry = new EntryImpl();
entry._after = _poolFirst;
_poolFirst = entry;
}
}
/**
* Requires special handling during de-serialization process.
*
* @param stream the object input stream.
* @throws IOException if an I/O error occurs.
* @throws ClassNotFoundException if the class for the object de-serialized is not found.
*/
private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
int capacity = stream.readInt();
initialize(capacity);
int size = stream.readInt();
for (int i = 0; i < size; i++) {
Object key = stream.readObject();
Object value = stream.readObject();
addEntry(key, value);
}
}
/**
* Requires special handling during serialization process.
*
* @param stream the object output stream.
* @throws IOException if an I/O error occurs.
*/
private void writeObject(ObjectOutputStream stream) throws IOException {
stream.writeInt(_capacity);
stream.writeInt(_size);
int count = 0;
EntryImpl entry = _mapFirst;
while (entry != null) {
stream.writeObject(entry._key);
stream.writeObject(entry._value);
count++;
entry = entry._after;
}
if (count != _size) {
throw new IOException("FastMap Corrupted");
}
}
/**
* This class represents a {@link FastMap} entry.
*/
private static final class EntryImpl<K, V> implements Map.Entry<K, V> {
/**
* Holds the entry key (null when in pool).
*/
private K _key;
/**
* Holds the entry value (null when in pool).
*/
private V _value;
/**
* Holds the bucket index (undefined when in pool).
*/
private int _index;
/**
* Holds the previous entry in the same bucket (null when in pool).
*/
private EntryImpl _previous;
/**
* Holds the next entry in the same bucket (null when in pool).
*/
private EntryImpl _next;
/**
* Holds the entry added before this entry (null when in pool).
*/
private EntryImpl _before;
/**
* Holds the entry added after this entry or the next available entry when in pool.
*/
private EntryImpl _after;
/**
* Returns the key for this entry.
*
* @return the entry's key.
*/
@Override
public K getKey() {
return _key;
}
/**
* Returns the value for this entry.
*
* @return the entry's value.
*/
@Override
public V getValue() {
return _value;
}
/**
* Sets the value for this entry.
*
* @param value the new value.
* @return the previous value.
*/
@Override
public V setValue(V value) {
V old = _value;
_value = value;
return old;
}
/**
* Indicates if this entry is considered equals to the specified entry.
*
* @param that the object to test for equality.
* @return <code>true<code> if both entry are considered equal; <code>false<code> otherwise.
*/
@Override
public boolean equals(Object that) {
if (that instanceof Map.Entry) {
Map.Entry entry = (Map.Entry) that;
return (_key.equals(entry.getKey()))
&& ((_value != null) ? _value.equals(entry.getValue()) : (entry.getValue() == null));
} else {
return false;
}
}
/**
* Returns the hash code for this entry.
*
* @return this entry's hash code.
*/
@Override
public int hashCode() {
return _key.hashCode() ^ ((_value != null) ? _value.hashCode() : 0);
}
/**
* Returns the text representation of this entry.
*
* @return this entry's textual representation.
*/
@Override
public String toString() {
return _key + "=" + _value;
}
}
}