This class represents a hash map with real-time behavior; * smooth capacity increase and thread-safe without external * synchronization when {@link #isShared shared}.
*
*
* {@link FastMap} has a predictable iteration order, which is the order in
* which keys are inserted into the map (similar to
* java.util.LinkedHashMap collection class). If the map is
* marked {@link #setShared(boolean) shared} then all operations are
* thread-safe including iterations over the map's collections.
* Unlike ConcurrentHashMap, {@link #get(Object) access} never
* blocks; retrieval reflects the map state not older than the last time the
* accessing threads have been synchronized (for multi-processors systems
* synchronizing ensures that the CPU internal cache is not stale).
{@link FastMap} may use custom key comparators; the default comparator is * either {@link FastComparator#DIRECT DIRECT} or * {@link FastComparator#REHASH REHASH} based upon the current Javolution * Configuration. Users may explicitly set the key comparator to * {@link FastComparator#DIRECT DIRECT} for optimum performance * when the hash codes are well distributed for all run-time platforms * (e.g. calculated hash codes).
* *Custom key comparators are extremely useful for value retrieval when * map's keys and argument keys are not of the same class (such as * {@link String} and {@link javolution.text.Text Text} * ({@link FastComparator#LEXICAL LEXICAL})), to substitute more efficient * hash code calculations ({@link FastComparator#STRING STRING}) * or for identity maps ({@link FastComparator#IDENTITY IDENTITY}):[code] * FastMap identityMap = new FastMap().setKeyComparator(FastComparator.IDENTITY); * [/code]
* * {@link FastMap.Entry} can quickly be iterated over (forward or backward)
* without using iterators. For example:[code]
* FastMap
Custom map implementations may override the {@link #newEntry} method * in order to return their own {@link Entry} implementation (with * additional fields for example).
* * {@link FastMap} are {@link Reusable reusable}; they maintain an
* internal pool of Map.Entry objects. When an entry is removed
* from a map, it is automatically restored to its pool (unless the map
* is shared in which case the removed entry is candidate for garbage
* collection as it cannot be safely recycled).
Shared maps do not use internal synchronization, except in case of
* concurrent modifications of the map structure (entry added/deleted).
* Reads and iterations are never synchronized and never blocking.
* With regards to the memory model, shared maps are equivalent to shared
* non-volatile variables (no "happen before" guarantee). There are
* typically used as lookup tables. For example:[code]
* public class Unit {
* static FastMap
Implementation Note: To maintain time-determinism, rehash/resize * is performed only when the map's size is small (see chart). For large * maps (size > 512), the collection is divided recursively into (64) * smaller sub-maps. The cost of the dispatching (based upon hashcode * value) has been measured to be at most 20% of the access time * (and most often way less).
* * @author Jean-Marie Dautelle * @version 5.2, September 11, 2007 */ public class FastMap/*head().getNext() holds
* the first map entry.
*/
public final Entry/*tail().getPrevious()
* holds the last map entry.
*/
public final Entry/*Note: If concurrent updates are performed, application should not * rely upon the size during iterations.
* * @return this map's size. */ public final int size() { if (!_useSubMaps) return _entryCount; int sum = 0; for (int i = 0; i < _subMaps.length;) { sum += _subMaps[i++].size(); } return sum; } /** * Indicates if this map contains no key-value mappings. * * @returntrue if this map contains no key-value mappings;
* false otherwise.
*/
public final boolean isEmpty() {
return _head._next == _tail;
}
/**
* Indicates if this map contains a mapping for the specified key.
*
* @param key the key whose presence in this map is to be tested.
* @return true if this map contains a mapping for the
* specified key; false otherwise.
* @throws NullPointerException if the key is null.
*/
public final boolean containsKey(Object key) {
return getEntry(key) != null;
}
/**
* Indicates if this map associates one or more keys to the specified value.
*
* @param value the value whose presence in this map is to be tested.
* @return true if this map maps one or more keys to the
* specified value.
* @throws NullPointerException if the key is null.
*/
public final boolean containsValue(Object value) {
return values().contains(value);
}
/**
* Returns the value to which this map associates the specified key.
* This method is always thread-safe regardless whether or not the map
* is marked {@link #isShared() shared}.
*
* @param key the key whose associated value is to be returned.
* @return the value to which this map maps the specified key, or
* null if there is no mapping for the key.
* @throws NullPointerException if key is null.
*/
public final Object/*{V}*/get(Object key) {
Entry/*null if none.
*/
public final Entry/*null if there was no mapping for key. A
* null return can also indicate that the map
* previously associated null with the specified key.
* @throws NullPointerException if the key is null.
*/
public final Object/*{V}*/put(Object/*{K}*/key, Object/*{V}*/value) {
return (Object/*{V}*/) put(key, value, _isDirectKeyComparator ? key
.hashCode() : _keyComparator.hashCodeOf(key), _isShared, false);
}
private final Object put(Object key, Object value, int keyHash,
boolean concurrent, boolean noReplace) {
final FastMap map = getSubMap(keyHash);
final Entry[] entries = map._entries; // Atomic.
final int mask = entries.length - 1;
int slot = -1;
for (int i = keyHash >> map._keyShift;; i++) {
Entry entry = entries[i & mask];
if (entry == null) {
slot = slot < 0 ? i & mask : slot;
break;
} else if (entry == Entry.NULL) {
slot = slot < 0 ? i & mask : slot;
} else if ((key == entry._key)
|| ((keyHash == entry._keyHash) && (_isDirectKeyComparator ? key
.equals(entry._key)
: _keyComparator.areEqual(key, entry._key)))) {
if (noReplace)
return entry._value;
Object prevValue = entry._value;
entry._value = value;
return prevValue;
}
}
// Add new entry (synchronize if concurrent).
if (concurrent) {
synchronized (this) {
return put(key, value, keyHash, false, noReplace);
}
}
// Setup entry.
final Entry entry = _tail;
entry._key = key;
entry._value = value;
entry._keyHash = keyHash;
if (entry._next == null) {
createNewEntries();
}
entries[slot] = entry;
map._entryCount += ONE_VOLATILE; // Prevents reordering.
_tail = _tail._next;
if (map._entryCount + map._nullCount > (entries.length >> 1)) { // Table more than half empty.
map.resizeTable(_isShared);
}
return null;
}
private void createNewEntries() { // Increase the number of entries.
MemoryArea.getMemoryArea(this).executeInArea(new Runnable() {
public void run() {
Entry previous = _tail;
for (int i = 0; i < 8; i++) { // Creates 8 entries at a time.
Entry/*null,
* or the specified map contains null keys.
*/
public final void putAll(Map/**/map) {
for (Iterator i = map.entrySet().iterator(); i.hasNext();) {
Map.Entry/*null if there was no mapping for key. A
* null return can also indicate that the map
* previously associated null with the specified key.
* @throws NullPointerException if the key is null.
*/
public final Object/*{V}*/putIfAbsent(Object/*{K}*/key,
Object/*{V}*/value) {
return (Object/*{V}*/) put(key, value, _isDirectKeyComparator ? key
.hashCode() : _keyComparator.hashCodeOf(key), _isShared, true);
}
/**
* Removes the entry for the specified key if present. The entry
* is recycled if the map is not marked as {@link #isShared shared};
* otherwise the entry is candidate for garbage collection.
*
* Note: Shared maps in ImmortalMemory (e.g. static) should not remove
* their entries as it could cause a memory leak (ImmortalMemory
* is never garbage collected), instead they should set their
* entry values to null.
null if there was no mapping for key. A
* null return can also indicate that the map
* previously associated null with the specified key.
* @throws NullPointerException if the key is null.
*/
public final Object/*{V}*/remove(Object key) {
return (Object/*{V}*/) remove(key, _isDirectKeyComparator ? key
.hashCode() : _keyComparator.hashCodeOf(key), _isShared);
}
private final Object remove(Object key, int keyHash, boolean concurrent) {
final FastMap map = getSubMap(keyHash);
final Entry[] entries = map._entries; // Atomic.
final int mask = entries.length - 1;
for (int i = keyHash >> map._keyShift;; i++) {
Entry entry = entries[i & mask];
if (entry == null)
return null; // No entry.
if ((key == entry._key)
|| ((keyHash == entry._keyHash) && (_isDirectKeyComparator ? key
.equals(entry._key)
: _keyComparator.areEqual(key, entry._key)))) {
// Found the entry.
if (concurrent) {
synchronized (this) {
return remove(key, keyHash, false);
}
}
// Detaches entry from list.
entry._previous._next = entry._next;
entry._next._previous = entry._previous;
// Removes from table.
entries[i & mask] = Entry.NULL;
map._nullCount++;
map._entryCount--;
Object prevValue = entry._value;
if (!_isShared) { // Clears key/value and recycle.
entry._key = null;
entry._value = null;
final Entry next = _tail._next;
entry._previous = _tail;
entry._next = next;
_tail._next = entry;
if (next != null) {
next._previous = entry;
}
}
return prevValue;
}
}
}
/**
* Sets the shared status of this map (whether the map is thread-safe * or not). Shared maps are typically used for lookup table (e.g. static * instances in ImmortalMemory). They support concurrent access * (e.g. iterations) without synchronization, the maps updates * themselves are synchronized internally.
* Unlike ConcurrentHashMap access to a shared map never
* blocks. Retrieval reflects the map state not older than the last
* time the accessing thread has been synchronized (for multi-processors
* systems synchronizing ensures that the CPU internal cache is not
* stale).
true if this map is shared and thread-safe;
* false otherwise.
* @return this
*/
public FastMap/*true if this map is thread-safe; false
* otherwise.
*/
public boolean isShared() {
return _isShared;
}
/**
* Sets the key comparator for this fast map.
*
* @param keyComparator the key comparator.
* @return this
*/
public FastMap/*this
*/
public FastMap/* Note: Shared maps in ImmortalMemory (e.g. static) should not remove
* their entries as it could cause a memory leak (ImmortalMemory
* is never garbage collected), instead they should set their
* entry values to null.
true 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 true if the specified object is equal to this map;
* false otherwise.
*/
public boolean equals(Object obj) {
if (obj == this) {
return true;
} else if (obj instanceof Map) {
Map/**/that = (Map) obj;
return this.entrySet().equals(that.entrySet());
} else {
return false;
}
}
/**
* Returns the hash code value for this map.
*
* @return the hash code value for this map.
*/
public int hashCode() {
int code = 0;
for (Entry e = _head, end = _tail; (e = e._next) != end;) {
code += e.hashCode();
}
return code;
}
/**
* Returns the textual representation of this map.
*
* @return the textual representation of the entry set.
*/
public Text toText() {
return Text.valueOf(entrySet());
}
/**
* Returns the String representation of this
* {@link FastMap}.
*
* @return toText().toString()
*/
public final String toString() {
return toText().toString();
}
/**
* Returns a new entry for this map; this method can be overriden by
* custom map implementations.
*
* @return a new entry.
*/
protected Entry/*System.out)
*/
public void printStatistics(PrintStream out) {
long sum = this.getSumDistance();
int size = this.size();
int avgDistancePercent = size != 0 ? (int) (100 * sum / size) : 0;
synchronized (out) {
out.print("SIZE: " + size);
out.print(", ENTRIES: " + getCapacity());
out.print(", SLOTS: " + getTableLength());
out.print(", USE SUB-MAPS: " + _useSubMaps);
out.print(", SUB-MAPS DEPTH: " + getSubMapDepth());
out.print(", NULL COUNT: " + _nullCount);
out.print(", IS SHARED: " + _isShared);
out.print(", AVG DISTANCE: " + avgDistancePercent + "%");
out.print(", MAX DISTANCE: " + getMaximumDistance());
out.println();
}
}
private int getTableLength() {
if (_useSubMaps) {
int sum = 0;
for (int i = 0; i < C2; i++) {
sum += _subMaps[i].getTableLength();
}
return sum;
} else {
return _entries.length;
}
}
private int getCapacity() {
int capacity = 0;
for (Entry e = _head; (e = e._next) != null;) {
capacity++;
}
return capacity - 1;
}
private int getMaximumDistance() {
int max = 0;
if (_useSubMaps) {
for (int i = 0; i < C2; i++) {
int subMapMax = _subMaps[i].getMaximumDistance();
max = MathLib.max(max, subMapMax);
}
return max;
}
for (int i = 0; i < _entries.length; i++) {
Entry entry = _entries[i];
if ((entry != null) && (entry != Entry.NULL)) {
int slot = (entry._keyHash >> _keyShift)
& (_entries.length - 1);
int distanceToSlot = i - slot;
if (distanceToSlot < 0)
distanceToSlot += _entries.length;
if (distanceToSlot > max) {
max = distanceToSlot;
}
}
}
return max;
}
private long getSumDistance() {
long sum = 0;
if (_useSubMaps) {
for (int i = 0; i < C2; i++) {
sum += _subMaps[i].getSumDistance();
}
return sum;
}
for (int i = 0; i < _entries.length; i++) {
Entry entry = _entries[i];
if ((entry != null) && (entry != Entry.NULL)) {
int slot = (entry._keyHash >> _keyShift)
& (_entries.length - 1);
int distanceToSlot = i - slot;
if (distanceToSlot < 0)
distanceToSlot += _entries.length;
sum += distanceToSlot;
}
}
return sum;
}
private int getSubMapDepth() {
if (_useSubMaps) {
int depth = 0;
for (int i = 0; i < C2; i++) {
int subMapDepth = _subMaps[i].getSubMapDepth();
depth = MathLib.max(depth, subMapDepth);
}
return depth + 1;
} else {
return 0;
}
}
/**
* Returns a {@link FastCollection} view of the values contained in this
* map. 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 Iterator.remove,
* Collection.remove, removeAll,
* retainAll and clear operations.
* It does not support the add or addAll
* operations.
*
* @return a collection view of the values contained in this map
* (instance of {@link FastCollection}).
*/
public final Collection/*FastMap.Entry. 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 Iterator.remove,
* Collection.remove,removeAll,
* retainAll, and clear operations. It does
* not support the add or addAll operations.
*
* @return a collection view of the mappings contained in this map
* (instance of {@link FastCollection}).
*/
public final Set/*Iterator.remove,
Collection.remove,removeAll,
* retainAll, and clear operations. It does
* not support the add or addAll operations.
*
* @return a set view of the keys contained in this map
* (instance of {@link FastCollection}).
*/
public final Set/**/keySet() {
if (_keySet == null) {
MemoryArea.getMemoryArea(this).executeInArea(new Runnable() {
public void run() {
_keySet = new KeySet();
}
});
}
return _keySet;
}
private final class KeySet extends FastCollection implements Set {
public int size() {
return FastMap.this.size();
}
public void clear() {
FastMap.this.clear();
}
public boolean contains(Object obj) { // Optimization.
return FastMap.this.containsKey(obj);
}
public boolean remove(Object obj) { // Optimization.
return FastMap.this.remove(obj) != null;
}
public Record head() {
return FastMap.this._head;
}
public Record tail() {
return FastMap.this._tail;
}
public Object valueOf(Record record) {
return ((Entry) record)._key;
}
public void delete(Record record) {
FastMap.this.remove(((Entry) record).getKey());
}
public FastComparator getValueComparator() {
return _keyComparator;
}
public Iterator iterator() {
return KeyIterator.valueOf(FastMap.this);
}
}
// Entry iterator optimization.
private static final class KeyIterator implements Iterator {
private static final ObjectFactory FACTORY = new ObjectFactory() {
protected Object create() {
return new KeyIterator();
}
protected void cleanup(Object obj) {
KeyIterator iterator = (KeyIterator) obj;
iterator._map = null;
iterator._current = null;
iterator._next = null;
iterator._tail = null;
}
};
private FastMap _map;
private Entry _current;
private Entry _next;
private Entry _tail;
public static KeyIterator valueOf(FastMap map) {
KeyIterator iterator = (KeyIterator) KeyIterator.FACTORY.object();
iterator._map = map;
iterator._next = map._head._next;
iterator._tail = map._tail;
return iterator;
}
private KeyIterator() {
}
public boolean hasNext() {
return (_next != _tail);
}
public Object next() {
if (_next == _tail)
throw new NoSuchElementException();
_current = _next;
_next = _next._next;
return _current._key;
}
public void remove() {
if (_current != null) {
_next = _current._next;
_map.remove(_current._key);
_current = null;
} else {
throw new IllegalStateException();
}
}
}
/**
* Returns the unmodifiable view associated to this map.
* Attempts to modify the returned map or to directly access its
* (modifiable) map entries (e.g. unmodifiable().entrySet())
* result in an {@link UnsupportedOperationException} being thrown.
* Unmodifiable {@link FastCollection} views of this map keys and values
* are nonetheless obtainable (e.g. unmodifiable().keySet(),
* unmodifiable().values()).
*
* @return an unmodifiable view of this map.
*/
public final Map/**/unmodifiable() {
if (_unmodifiable == null) {
MemoryArea.getMemoryArea(this).executeInArea(new Runnable() {
public void run() {
_unmodifiable = new Unmodifiable();
}
});
}
return _unmodifiable;
}
// Implements Reusable.
public void reset() {
setShared(false); // A shared map can only be reset if no thread use it.
clear(); // In which case, it is safe to recycle the entries.
setKeyComparator(FastComparator.DEFAULT);
setValueComparator(FastComparator.DEFAULT);
}
/**
* 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 {
setKeyComparator((FastComparator) stream.readObject());
setValueComparator((FastComparator) stream.readObject());
setShared(stream.readBoolean());
final int size = stream.readInt();
setup(size);
for (int i = 0; i < size; i++) {
Object/*{K}*/key = (Object/*{K}*/) stream.readObject();
Object/*{V}*/value = (Object/*{V}*/) stream.readObject();
put(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.writeObject(getKeyComparator());
stream.writeObject(getValueComparator());
stream.writeBoolean(_isShared);
stream.writeInt(size());
for (Entry e = _head, end = _tail; (e = e._next) != end;) {
stream.writeObject(e._key);
stream.writeObject(e._value);
}
}
/**
* This class represents a {@link FastMap} entry.
* Custom {@link FastMap} may use a derived implementation.
* For example:[code]
* static class MyMap extends FastMap {
* protected MyEntry newEntry() {
* return new MyEntry();
* }
* class MyEntry extends Entry {
* X xxx; // Additional entry field (e.g. cross references).
* }
* }[/code]
*/
public static class Entry/**/implements Map.Entry/**/, Record {
/**
* Holds NULL entries (to fill empty hole).
*/
public static final Entry NULL = new Entry();
/**
* Holds the next node.
*/
private Entry/**/_next;
/**
* Holds the previous node.
*/
private Entry/**/_previous;
/**
* Holds the entry key.
*/
private Object/*{K}*/_key;
/**
* Holds the entry value.
*/
private Object/*{V}*/_value;
/**
* Holds the key hash code.
*/
private int _keyHash;
/**
* Default constructor.
*/
protected Entry() {
}
/**
* Returns the entry after this one.
*
* @return the next entry.
*/
public final Record/*Entry*/getNext() {
return _next;
}
/**
* Returns the entry before this one.
*
* @return the previous entry.
*/
public final Record/*Entry*/getPrevious() {
return _previous;
}
/**
* Returns the key for this entry.
*
* @return the entry key.
*/
public final Object/*{K}*/getKey() {
return _key;
}
/**
* Returns the value for this entry.
*
* @return the entry value.
*/
public final Object/*{V}*/getValue() {
return _value;
}
/**
* Sets the value for this entry.
*
* @param value the new value.
* @return the previous value.
*/
public final Object/*{V}*/setValue(Object/*{V}*/value) {
Object/*{V}*/old = _value;
_value = value;
return old;
}
/**
* Indicates if this entry is considered equals to the specified entry
* (using default value and key equality comparator to ensure symetry).
*
* @param that the object to test for equality.
* @return true if both entry have equal keys and values.
* false otherwise.
*/
public boolean equals(Object that) {
if (that instanceof Map.Entry) {
Map.Entry entry = (Map.Entry) that;
return FastComparator.DEFAULT.areEqual(_key, entry.getKey())
&& FastComparator.DEFAULT.areEqual(_value, entry
.getValue());
} else {
return false;
}
}
/**
* Returns the hash code for this entry.
*
* @return this entry hash code.
*/
public int hashCode() {
return ((_key != null) ? _key.hashCode() : 0)
^ ((_value != null) ? _value.hashCode() : 0);
}
}
/**
* This class represents an read-only view over a {@link FastMap}.
*/
private final class Unmodifiable implements Map, Serializable {
public boolean equals(Object obj) {
return FastMap.this.equals(obj);
}
public int hashCode() {
return FastMap.this.hashCode();
}
public Text toText() {
return FastMap.this.toText();
}
public int size() {
return FastMap.this.size();
}
public boolean isEmpty() {
return FastMap.this.isEmpty();
}
public boolean containsKey(Object key) {
return FastMap.this.containsKey(key);
}
public boolean containsValue(Object value) {
return FastMap.this.containsValue(value);
}
public Object get(Object key) {
return FastMap.this.get(key);
}
public Object put(Object key, Object value) {
throw new UnsupportedOperationException("Unmodifiable map");
}
public Object remove(Object key) {
throw new UnsupportedOperationException("Unmodifiable map");
}
public void putAll(Map map) {
throw new UnsupportedOperationException("Unmodifiable map");
}
public void clear() {
throw new UnsupportedOperationException("Unmodifiable map");
}
public Set keySet() {
return (Set) ((KeySet) FastMap.this.keySet()).unmodifiable();
}
public Collection values() {
return ((Values) FastMap.this.values()).unmodifiable();
}
public Set entrySet() {
throw new UnsupportedOperationException(
"Direct view over unmodifiable map entries is not supported "
+ " (to prevent access to Entry.setValue(Object) method). "
+ "To iterate over unmodifiable map entries, applications may "
+ "use the keySet() and values() fast collection views "
+ "in conjonction.");
}
}
// Holds the map factory.
private static final ObjectFactory FACTORY = new ObjectFactory() {
public Object create() {
return new FastMap();
}
public void cleanup(Object obj) {
((FastMap) obj).reset();
}
};
// Reset the specified table.
private static void reset(Object[] entries) {
for (int i = 0; i < entries.length;) {
int count = MathLib.min(entries.length - i, C1);
System.arraycopy(NULL_ENTRIES, 0, entries, i, count);
i += count;
}
}
private static final Entry[] NULL_ENTRIES = new Entry[C1];
static volatile int ONE_VOLATILE = 1; // To prevent reordering.
private static final long serialVersionUID = 1L;
}