http://codehaus-plexus.github.io/plexus-utils/: A collection of various utility classes to ease working with strings, files, command lines, XML and more. (Codehaus Plexus)
  • Jason van Zyl
  • Pete Kazmier ()
  • James Taylor ()
  • Dan Diephouse (Envoi solutions)
  • Kasper Nielsen ()
  • Ben Walding (Walding Consulting Services)
  • Mark Wilkinson
  • Michal Maczka
  • Emmanuel Venisse
  • Trygve Laugstøl
  • Kenney Westerhof
  • Carlos Sanchez
  • Brett Porter
  • John Casey
  • Andrew Williams
  • Rahul Thakur
  • Joakim Erdfelt
  • Olivier Lamy
  • Hervé Boutemy
  • Oleg Gusakov
  • Vincent Siveton
  • Kristian Rosenvold
  • Andreas Gudian
  • Karl Heinz Marbaise
  • Michael Osipov 
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.util.Collection;
import java.util.Collections;
import java.util.Map;
import java.util.Set;



This class provides cache access to Map collections.




Instance of this class can be used as "proxy" for any collection implementing the java.util.Map
interface.



 Typically, CachedMap are used to accelerate access to large collections when the access to the collection is not evenly distributed (associative cache). The performance gain is about 50% for the fastest hash map collections (e.g. FastMap). For slower collections such as java.util.TreeMap, non-resizable FastMap (real-time) or database access, performance can be of several orders of magnitude. 



Note: The keys used to access elements of a CachedMap do not need to be immutable as they are not stored in the cache (only keys specified by the put method are). In other words, access can be performed using mutable keys as long as these keys can be compared for equality with the real map's keys (e.g. same hashCode values).




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




 This class is public domain (not copyrighted).



Author:Jean-Marie Dautelle
Version:5.3, October 30, 2003
/**
 * <p>
 * This class provides cache access to <code>Map</code> collections.
 * </p>
 * <p>
 * Instance of this class can be used as "proxy" for any collection implementing the <code>java.util.Map</code>
 * interface.
 * </p>
 * <p>
 * Typically, {@link CachedMap} are used to accelerate access to large collections when the access to the collection is
 * not evenly distributed (associative cache). The performance gain is about 50% for the fastest hash map collections
 * (e.g. {@link FastMap}). For slower collections such as <code>java.util.TreeMap</code>, non-resizable {@link FastMap}
 * (real-time) or database access, performance can be of several orders of magnitude.
 * </p>
 * <p>
 * <b>Note:</b> The keys used to access elements of a {@link CachedMap} do not need to be immutable as they are not
 * stored in the cache (only keys specified by the {@link #put} method are). In other words, access can be performed
 * using mutable keys as long as these keys can be compared for equality with the real map's keys (e.g. same
 * <code>hashCode</code> values).
 * </p>
 * <p>
 * This implementation is not synchronized. Multiple threads accessing or modifying the collection must be synchronized
 * externally.
 * </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 30, 2003
 */
public final class CachedMap
    implements Map
{

    
Holds the FastMap backing this collection (null if generic backing map).

/**
     * Holds the FastMap backing this collection (<code>null</code> if generic backing map).
     */
    private final FastMap _backingFastMap;

    
Holds the generic map backing this collection.

/**
     * Holds the generic map backing this collection.
     */
    private final Map _backingMap;

    
Holds the keys of the backing map (key-to-key mapping). (null if FastMap backing map).

/**
     * Holds the keys of the backing map (key-to-key mapping). (<code>null</code> if FastMap backing map).
     */
    private final FastMap _keysMap;

    
Holds the cache's mask (capacity - 1).

/**
     * Holds the cache's mask (capacity - 1).
     */
    private final int _mask;

    
Holds the keys being cached.

/**
     * Holds the keys being cached.
     */
    private final Object[] _keys;

    
Holds the values being cached.

/**
     * Holds the values being cached.
     */
    private final Object[] _values;

    
Creates a cached map backed by a FastMap. The default cache size and map capacity is set to 256 entries.

/**
     * Creates a cached map backed by a {@link FastMap}. The default cache size and map capacity is set to
     * <code>256</code> entries.
     */
    public CachedMap()
    {
        this( 256, new FastMap() );
    }

    
Creates a cached map backed by a FastMap and having the specified cache size. 
Params:
  • cacheSize – the cache size, the actual cache size is the first power of 2 greater or equal to
           cacheSize. This is also the initial capacity of the backing map.
/**
     * Creates a cached map backed by a {@link FastMap} and having the specified cache size.
     *
     * @param cacheSize the cache size, the actual cache size is the first power of 2 greater or equal to
     *            <code>cacheSize</code>. This is also the initial capacity of the backing map.
     */
    public CachedMap( int cacheSize )
    {
        this( cacheSize, new FastMap( cacheSize ) );
    }

    
Creates a cached map backed by the specified map and having the specified cache size. In order to maintain cache
veracity, it is critical that all update to the backing map is accomplished through the CachedMap instance; otherwise flush has to be called. 
Params:
  • cacheSize – the cache size, the actual cache size is the first power of 2 greater or equal to
           cacheSize.
  • backingMap – the backing map to be "wrapped" in a cached map.
/**
     * Creates a cached map backed by the specified map and having the specified cache size. In order to maintain cache
     * veracity, it is critical that <b>all</b> update to the backing map is accomplished through the {@link CachedMap}
     * instance; otherwise {@link #flush} has to be called.
     *
     * @param cacheSize the cache size, the actual cache size is the first power of 2 greater or equal to
     *            <code>cacheSize</code>.
     * @param backingMap the backing map to be "wrapped" in a cached map.
     */
    public CachedMap( int cacheSize, Map backingMap )
    {

        // Find a power of 2 >= minimalCache
        int actualCacheSize = 1;
        while ( actualCacheSize < cacheSize )
        {
            actualCacheSize <<= 1;
        }

        // Sets up cache.
        _keys = new Object[actualCacheSize];
        _values = new Object[actualCacheSize];
        _mask = actualCacheSize - 1;

        // Sets backing map references.
        if ( backingMap instanceof FastMap )
        {
            _backingFastMap = (FastMap) backingMap;
            _backingMap = _backingFastMap;
            _keysMap = null;
        }
        else
        {
            _backingFastMap = null;
            _backingMap = backingMap;
            _keysMap = new FastMap( backingMap.size() );
            for ( Object key : backingMap.keySet() )
            {
                _keysMap.put( key, key );
            }
        }
    }

    
Returns the actual cache size.

Returns:the cache size (power of 2).
/**
     * Returns the actual cache size.
     *
     * @return the cache size (power of 2).
     */
    public int getCacheSize()
    {
        return _keys.length;
    }

    
Returns the backing map. If the backing map is modified directly, this CachedMap has to be flushed. 
See Also:
Returns:the backing map.
/**
     * Returns the backing map. If the backing map is modified directly, this {@link CachedMap} has to be flushed.
     *
     * @return the backing map.
     * @see #flush
     */
    public Map getBackingMap()
    {
        return ( _backingFastMap != null ) ? _backingFastMap : _backingMap;
    }

    
Flushes the key/value pairs being cached. This method should be called if the backing map is externally modified.

/**
     * Flushes the key/value pairs being cached. This method should be called if the backing map is externally modified.
     */
    public void flush()
    {
        for ( int i = 0; i < _keys.length; i++ )
        {
            _keys[i] = null;
            _values[i] = null;
        }

        if ( _keysMap != null )
        {
            // Re-populates keys from backing map.
            for ( Object key : _backingMap.keySet() )
            {
                _keysMap.put( key, key );
            }
        }
    }

    
Returns the value to which this map maps the specified key. First, the cache is being checked, then if the cache
does not contains the specified key, the backing map is accessed and the key/value pair is stored in the cache.

Params:
  • key – the key whose associated value is to be returned.
Throws:
Returns:the value to which this map maps the specified key, or null if the map contains no mapping
        for this key.
/**
     * Returns the value to which this map maps the specified key. First, the cache is being checked, then if the cache
     * does not contains the specified key, the backing map is accessed and the key/value pair is stored in the cache.
     *
     * @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 the map contains no mapping
     *         for this key.
     * @throws ClassCastException if the key is of an inappropriate type for the backing map (optional).
     * @throws NullPointerException if the key is <code>null</code>.
     */
    public Object get( Object key )
    {
        int index = key.hashCode() & _mask;
        return key.equals( _keys[index] ) ? _values[index] : getCacheMissed( key, index );
    }

    private Object getCacheMissed( Object key, int index )
    {
        if ( _backingFastMap != null )
        {
            Map.Entry entry = _backingFastMap.getEntry( key );
            if ( entry != null )
            {
                _keys[index] = entry.getKey();
                Object value = entry.getValue();
                _values[index] = value;
                return value;
            }
            else
            {
                return null;
            }
        }
        else
        { // Generic backing map.
            Object mapKey = _keysMap.get( key );
            if ( mapKey != null )
            {
                _keys[index] = mapKey;
                Object value = _backingMap.get( key );
                _values[index] = value;
                return value;
            }
            else
            {
                return null;
            }
        }
    }

    
Associates the specified value with the specified key in this map.

Params:
  • key – the key with which the specified value is to be associated.
  • value – the value to be associated with the specified key.
Throws:
Returns:the previous value associated with specified key, or null if there was no mapping for the
        key.
/**
     * Associates the specified value with the specified key in this map.
     *
     * @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 the
     *         key.
     * @throws UnsupportedOperationException if the <code>put</code> operation is not supported by the backing map.
     * @throws ClassCastException if the class of the specified key or value prevents it from being stored in this map.
     * @throws IllegalArgumentException if some aspect of this key or value prevents it from being stored in this map.
     * @throws NullPointerException if the key is <code>null</code>.
     */
    public Object put( Object key, Object value )
    {
        // Updates the cache.
        int index = key.hashCode() & _mask;
        if ( key.equals( _keys[index] ) )
        {
            _values[index] = value;
        }
        else if ( _keysMap != null )
        { // Possibly a new key.
            _keysMap.put( key, key );
        }

        // Updates the backing map.
        return _backingMap.put( key, value );
    }

    
Removes the mapping for this key from this map if it is present.

Params:
  • key – key whose mapping is to be removed from the map.
Throws:
Returns:previous value associated with specified key, or null if there was no mapping for key.
/**
     * Removes the mapping for this key from this map if it is present.
     *
     * @param key 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.
     * @throws ClassCastException if the key is of an inappropriate type for the backing map (optional).
     * @throws NullPointerException if the key is <code>null</code>.
     * @throws UnsupportedOperationException if the <code>remove</code> method is not supported by the backing map.
     */
    public Object remove( Object key )
    {
        // Removes from cache.
        int index = key.hashCode() & _mask;
        if ( key.equals( _keys[index] ) )
        {
            _keys[index] = null;
        }
        // Removes from key map.
        if ( _keysMap != null )
        {
            _keysMap.remove( key );
        }
        // Removes from backing map.
        return _backingMap.remove( key );
    }

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

Params:
  • 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.
/**
     * 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 <code>true</code> if this map contains a mapping for the specified key; <code>false</code> otherwise.
     */
    public boolean containsKey( Object key )
    {
        // Checks the cache.
        int index = key.hashCode() & _mask;
        if ( key.equals( _keys[index] ) )
        {
            return true;
        }
        else
        { // Checks the backing map.
            return _backingMap.containsKey( key );
        }
    }

    
Returns the number of key-value mappings in this map. If the map contains more than
Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

Returns:the number of key-value mappings in this map.
/**
     * Returns the number of key-value mappings in this map. If the map contains more than
     * <code>Integer.MAX_VALUE</code> elements, returns <code>Integer.MAX_VALUE</code>.
     *
     * @return the number of key-value mappings in this map.
     */
    public int size()
    {
        return _backingMap.size();
    }

    
Returns true if this map contains no key-value mappings.

Returns:true if this map contains no key-value mappings.
/**
     * Returns <code>true</code> if this map contains no key-value mappings.
     *
     * @return <code>true</code> if this map contains no key-value mappings.
     */
    public boolean isEmpty()
    {
        return _backingMap.isEmpty();
    }

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

Params:
  • value – value whose presence in this map is to be tested.
Throws:
  • ClassCastException – if the value is of an inappropriate type for the backing map (optional).
  • NullPointerException – if the value is null and the backing map does not not permit
            null values.
Returns:true if this map maps one or more keys to the specified value.
/**
     * Returns <code>true</code> 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 <code>true</code> if this map maps one or more keys to the specified value.
     * @throws ClassCastException if the value is of an inappropriate type for the backing map (optional).
     * @throws NullPointerException if the value is <code>null</code> and the backing map does not not permit
     *             <code>null</code> values.
     */
    public boolean containsValue( Object value )
    {
        return _backingMap.containsValue( value );
    }

    
Copies all of the mappings from the specified map to this map (optional operation). This method automatically
flushes the cache.

Params:
  • map – the mappings to be stored in this map.
Throws:
  • UnsupportedOperationException – if the putAll method is not supported by the backing map.
  • ClassCastException – if the class of a key or value in the specified map prevents it from being stored in
            this map.
  • IllegalArgumentException – some aspect of a key or value in the specified map prevents it from being stored
            in this map.
  • NullPointerException – the specified map is null, or if the backing map does not permit
            null keys or values, and the specified map contains null keys or values.
/**
     * Copies all of the mappings from the specified map to this map (optional operation). This method automatically
     * flushes the cache.
     *
     * @param map the mappings to be stored in this map.
     * @throws UnsupportedOperationException if the <code>putAll</code> method is not supported by the backing map.
     * @throws ClassCastException if the class of a key or value in the specified map prevents it from being stored in
     *             this map.
     * @throws IllegalArgumentException some aspect of a key or value in the specified map prevents it from being stored
     *             in this map.
     * @throws NullPointerException the specified map is <code>null</code>, or if the backing map does not permit
     *             <code>null</code> keys or values, and the specified map contains <code>null</code> keys or values.
     */
    public void putAll( Map map )
    {
        _backingMap.putAll( map );
        flush();
    }

    
Removes all mappings from this map (optional operation). This method automatically flushes the cache.

Throws:
  • UnsupportedOperationException – if clear is not supported by the backing map.
/**
     * Removes all mappings from this map (optional operation). This method automatically flushes the cache.
     *
     * @throws UnsupportedOperationException if clear is not supported by the backing map.
     */
    public void clear()
    {
        _backingMap.clear();
        flush();
    }

    
Returns an unmodifiable view of the keys contained in this map.

Returns:an unmodifiable view of the keys contained in this map.
/**
     * Returns an <b>unmodifiable</b> view of the keys contained in this map.
     *
     * @return an unmodifiable view of the keys contained in this map.
     */
    public Set keySet()
    {
        return Collections.unmodifiableSet( _backingMap.keySet() );
    }

    
Returns an unmodifiable view of the values contained in this map.

Returns:an unmodifiable view of the values contained in this map.
/**
     * Returns an <b>unmodifiable</b> view of the values contained in this map.
     *
     * @return an unmodifiable view of the values contained in this map.
     */
    public Collection values()
    {
        return Collections.unmodifiableCollection( _backingMap.values() );
    }

    
Returns an unmodifiable view of the mappings contained in this map. Each element in the returned set is a
Map.Entry.

Returns:an unmodifiable view of the mappings contained in this map.
/**
     * Returns an <b>unmodifiable</b> view of the mappings contained in this map. Each element in the returned set is a
     * <code>Map.Entry</code>.
     *
     * @return an unmodifiable view of the mappings contained in this map.
     */
    public Set entrySet()
    {
        return Collections.unmodifiableSet( _backingMap.entrySet() );
    }

    
Compares the specified object with this map for equality. Returns true if the given object is also a map
and the two Maps represent the same mappings.

Params:
  • o – object to be compared for equality with this map.
Returns:true if the specified object is equal to this map.
/**
     * Compares the specified object with this map for equality. Returns <tt>true</tt> if the given object is also a map
     * and the two Maps represent the same mappings.
     *
     * @param o object to be compared for equality with this map.
     * @return <code>true</code> if the specified object is equal to this map.
     */
    public boolean equals( Object o )
    {
        return _backingMap.equals( o );
    }

    
Returns the hash code value for this map.

Returns:the hash code value for this map.
/**
     * Returns the hash code value for this map.
     *
     * @return the hash code value for this map.
     */
    public int hashCode()
    {
        return _backingMap.hashCode();
    }
}