This page is part of an archival collection and is no longer actively maintained.

It may contain outdated information and may not meet current or future WCAG accessibility standards. We provide this content, its subpages, and associated links for historical reference only. If you need assistance, please contact support@cs.washington.edu

com.dautelle.util
Class FastMap

java.lang.Object
  com.dautelle.realtime.RealtimeObject
      com.dautelle.util.FastMap

All Implemented Interfaces:

java.lang.Cloneable, java.util.Map, Realtime, java.io.Serializable

public class FastMap

extends RealtimeObject

implements java.util.Map, java.lang.Cloneable

This class represents a Map 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 extremely fast and consistent.

To avoid dynamic memory allocations, FastMap maintains an internal pool of Map.Entry 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.

Instances of this class can be allocated from the current thread stack using the newInstance(int) factory method (e.g. for throw-away maps to avoid the creation cost).

FastMap has a predictable iteration order, which is the order in which keys were inserted into the map (similar to java.util.LinkedHashMap collection class). Furthermore, iterators on the map's entries, the map's keys or the map's values are all real-time compliant (allocated from the "stack" when executing in a PoolContex).

Applications may change the resizing policy of FastMap by overriding the sizeChanged() method. For example, to reduce memory footprint, the map's capacity could be maitained at ±50% of the current map's size.

This implementation is not synchronized. Multiple threads accessing or modifying the collection must be synchronized externally.

This class is public domain (not copyrighted).

Version:

6.0, March 24 2004

Author:

Jean-Marie Dautelle

See Also:

Serialized Form

Nested Class Summary

Nested classes inherited from class com.dautelle.realtime.RealtimeObject

RealtimeObject.Factory

Nested classes inherited from class java.util.Map

java.util.Map.Entry

Constructor Summary

FastMap()
Creates a FastMap with a default capacity.

FastMap(int capacity)
Creates a FastMap with the specified capacity.

FastMap(java.util.Map map)
Creates a FastMap, copy of the specified Map.

Method Summary

int	capacity() Returns the capacity of this FastMap.
void	clear() Removes all mappings from this FastMap.
java.lang.Object	clone() Returns a shallow copy of this FastMap allocated on the heap.
boolean	containsKey(java.lang.Object key) Indicates if this FastMap contains a mapping for the specified key.
boolean	containsValue(java.lang.Object value) Indicates if this FastMap maps one or more keys to the specified value.
java.util.Set	entrySet() Returns a collection view of the mappings contained in this FastMap.
boolean	equals(java.lang.Object obj) Compares the specified object with this FastMap for equality.
java.lang.Object	export() Exports this object out of the current pool context.
java.lang.Object	get(java.lang.Object key) Returns the value to which this FastMap maps the specified key.
java.util.Map.Entry	getEntry(java.lang.Object key) Returns the entry with the specified key.
int	hashCode() Returns the hash code value for this FastMap.
boolean	isEmpty() Indicates if this FastMap contains no key-value mappings.
java.util.Set	keySet() Returns a set view of the keys contained in this FastMap.
static FastMap	newInstance(int capacity) Returns a FastMap of specified minimum capacity allocated from the current stack (or the heap if not in a pool context).
java.lang.Object	put(java.lang.Object key, java.lang.Object value) Associates the specified value with the specified key in this FastMap.
void	putAll(java.util.Map map) Copies all of the mappings from the specified map to this FastMap.
java.lang.Object	remove(java.lang.Object key) Removes the mapping for this key from this FastMap if present.
void	setCapacity(int newCapacity) Changes the current capacity of this FastMap.
int	size() Returns the number of key-value mappings in this FastMap.
protected void	sizeChanged() This methods is being called when the size of this FastMap has changed.
java.lang.Object	toHeap() Moves this object to the heap.
java.lang.String	toString() Returns a String representation of this FastMap.
java.util.Collection	values() Returns a collection view of the values contained in this FastMap.

Methods inherited from class com.dautelle.realtime.RealtimeObject

isLocalObject, isPoolObject, recycle

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

FastMap

public FastMap()

Creates a FastMap with a default capacity.

FastMap

public FastMap(java.util.Map map)

Creates a FastMap, copy of the specified Map. 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:

     TreeMap dictionary = ...;
     FastMap dictionaryLookup = new FastMap(dictionary);
 

Parameters:

map - the map whose mappings are to be placed in this map.

FastMap

public FastMap(int capacity)

Creates a 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.

Parameters:

capacity - the number of buckets in the hash table; it also defines the number of pre-allocated entries.

Method Detail

newInstance

public static FastMap newInstance(int capacity)

Returns a FastMap of specified minimum capacity allocated from the current stack (or the heap if not in a pool context). 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. Upon recycling, the map is cleared and its initial capacity restored.

Parameters:

capacity - the minimum capacity of the map to return.

Returns:

a new or recycled map instance.

See Also:

clear(), setCapacity(int)

size

public int size()

Returns the number of key-value mappings in this FastMap.

Specified by:

size in interface java.util.Map

Returns:

this map's size.

capacity

public int capacity()

Returns the capacity of this 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.

Returns:

this map's capacity.

isEmpty

public boolean isEmpty()

Indicates if this FastMap contains no key-value mappings.

Specified by:

isEmpty in interface java.util.Map

Returns:

true if this map contains no key-value mappings; false otherwise.

containsKey

public boolean containsKey(java.lang.Object key)

Indicates if this FastMap contains a mapping for the specified key.

Specified by:

containsKey in interface java.util.Map

Parameters:

key - the key whose presence in this map is to be tested.

Returns:

true if this map contains a mapping for the specified key; false otherwise.

Throws:

java.lang.NullPointerException - if the key is null.

containsValue

public boolean containsValue(java.lang.Object value)

Indicates if this FastMap maps one or more keys to the specified value.

Specified by:

containsValue in interface java.util.Map

Parameters:

value - the value whose presence in this map is to be tested.

Returns:

true if this map maps one or more keys to the specified value.

Throws:

java.lang.NullPointerException - if the key is null.

get

public java.lang.Object get(java.lang.Object key)

Returns the value to which this FastMap maps the specified key.

Specified by:

get in interface java.util.Map

Parameters:

key - the key whose associated value is to be returned.

Returns:

the value to which this map maps the specified key, or null if there is no mapping for the key.

Throws:

java.lang.NullPointerException - if key is null.

getEntry

public java.util.Map.Entry getEntry(java.lang.Object key)

Returns the entry with the specified key.

Parameters:

key - the key whose associated entry is to be returned.

Returns:

the entry for the specified key or null if none.

put

public java.lang.Object put(java.lang.Object key,
                            java.lang.Object value)

Associates the specified value with the specified key in this FastMap. If the FastMap previously contained a mapping for this key, the old value is replaced.

Specified by:

put in interface java.util.Map

Parameters:

key - the key with which the specified value is to be associated.

value - the value to be associated with the specified key.

Returns:

the 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.

Throws:

java.lang.NullPointerException - if the key is null.

putAll

public void putAll(java.util.Map map)

Copies all of the mappings from the specified map to this FastMap.

Specified by:

putAll in interface java.util.Map

Parameters:

map - the mappings to be stored in this map.

Throws:

java.lang.NullPointerException - the specified map is null, or the specified map contains null keys.

remove

public java.lang.Object remove(java.lang.Object key)

Removes the mapping for this key from this FastMap if present.

Specified by:

remove in interface java.util.Map

Parameters:

key - the key whose mapping is to be removed from the map.

Returns:

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.

Throws:

java.lang.NullPointerException - if the key is null.

clear

public void clear()

Removes all mappings from this FastMap.

Specified by:

clear in interface java.util.Map

setCapacity

public void setCapacity(int newCapacity)

Changes the current capacity of this 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 garbage collected eventually). The capacity also determined the number of buckets for the hash table.

Parameters:

newCapacity - the new capacity of this map.

clone

public java.lang.Object clone()

Returns a shallow copy of this FastMap allocated on the heap. The keys and the values themselves are not cloned but moved to the heap as well (heap objects cannot refer to pool objects).

Overrides:

clone in class RealtimeObject

Returns:

a shallow copy of this map.

equals

public boolean equals(java.lang.Object obj)

Compares the specified object with this FastMap for equality. Returns true if the given object is also a map and the two maps represent the same mappings (regardless of collection iteration order).

Specified by:

equals in interface java.util.Map

Parameters:

obj - the object to be compared for equality with this map.

Returns:

true if the specified object is equal to this map; false otherwise.

hashCode

public int hashCode()

Returns the hash code value for this FastMap.

Specified by:

hashCode in interface java.util.Map

Returns:

the hash code value for this map.

toString

public java.lang.String toString()

Returns a String representation of this FastMap.

Returns:

this.entrySet().toString();

values

public java.util.Collection values()

Returns a collection view of the values contained in this 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 Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.

Specified by:

values in interface java.util.Map

Returns:

a collection view of the values contained in this map.

entrySet

public java.util.Set entrySet()

Returns a collection view of the mappings contained in this FastMap. Each element in the returned collection is a Map.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.

Specified by:

entrySet in interface java.util.Map

Returns:

a collection view of the mappings contained in this map.

keySet

public java.util.Set keySet()

Returns a set view of the keys contained in this 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 Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.

Specified by:

keySet in interface java.util.Map

Returns:

a set view of the keys contained in this map.

sizeChanged

protected void sizeChanged()

This methods is being called when the size of this FastMap has changed. The default behavior is to double the map's capacity when the map's size exceeds the current map's capacity. Sub-class may override this method to implement custom resizing policies or to disable automatic resizing. For example:

     Map fixedCapacityMap = new FastMap(256) { 
           protected sizeChanged() {
               // Do nothing, automatic resizing disabled.
           }
     };

See Also:

setCapacity(int)

export

public java.lang.Object export()

Description copied from interface: Realtime

Exports this object out of the current pool context. Realtime members are exported as well (recursion). This method affects only objects belonging to the current pool context. To avoid pool depletion, a "free" object from the outer pool is moved to replace the object being exported.

Specified by:

export in interface Realtime

Overrides:

export in class RealtimeObject

toHeap

public java.lang.Object toHeap()

Description copied from interface: Realtime

Moves this object to the heap. Realtime members are moved to the heap as well (recursion). This method affects only objects belonging to a pool context (current or not).

Specified by:

toHeap in interface Realtime

Overrides:

toHeap in class RealtimeObject