fastmap.java

jboss规则引擎

package org.drools.util;

/*
 * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
 * Copyright (C) 2005 - Javolution (http://javolution.org/)
 * All rights reserved.
 * 
 * Permission to use, copy, modify, and distribute this software is
 * freely granted, provided that this notice is preserved.
 */

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.PrintStream;
import java.io.Serializable;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * <p> This class represents a hash map with real-time behavior; 
 *     smooth capacity increase and no rehashing ever performed.</p>
 *     <img src="doc-files/map-put.png"/>
 *     
 * <p> {@link FastMap} has a predictable iteration order, which is the order in
 *     which keys are inserted into the map (similar to 
 *     <code>java.util.LinkedHashMap</code> collection class).</p>
 *     
 * <p> {@link FastMap.Entry} can quickly be iterated over (forward or backward)
 *     without using iterators. For example:[code]
 *     FastMap<String, Thread> map = new FastMap<String, Thread>();
 *     for (FastMap.Entry<String, Thread> e = map.head(), end = map.tail(); (e = e.getNext()) != end;) {
 *          String key = e.getKey(); // No typecast necessary.
 *          Thread value = e.getValue(); // No typecast necessary.
 *     }[/code]</p>
 * 
 * <p> {@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 <a href=
 *     "{@docRoot}/overview-summary.html#configuration">Javolution 
 *     Configuration</a>. 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).</p>
 *     
 * <p> 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.lang.Text Text} 
 *     ({@link FastComparator#LEXICAL LEXICAL}) or for identity maps 
 *     ({@link FastComparator#IDENTITY IDENTITY}).
 *     For example:[code]
 *     FastMap identityMap = new FastMap().setKeyComparator(FastComparator.IDENTITY);
 *     [/code]</p>
 * 
 * <p> {@link FastMap} marked {@link #setShared(boolean) shared} are 
 *     thread-safe without external synchronization and are often good 
 *     substitutes for <code>ConcurrentHashMap</code>. For example:[code]
 *     // Holds the units multiplication lookup table (persistent).
 *     static final FastMap<Unit, FastMap<Unit, Unit>> MULT_LOOKUP 
 *          = new FastMap<Unit, FastMap<Unit, Unit>>("mult-unit-lookup").setShared(true);
 *     
 *     // Fast and non-blocking (no synchronization necessary).     
 *     static Unit productOf(Unit left, Unit right) {
 *          FastMap<Unit, Unit> leftTable = MULT_LOOKUP.get(left);
 *          if (leftTable == null) return calculateProductOf(left, right);
 *          Unit result = leftTable.get(right);
 *          if (result == null) return calculateProductOf(left, right);
 *          return result; // Returns cache result.
 *    }[/code]</p>
 *     
 * <p> Finally, {@link FastMap} are {@link Reusable reusable}; they maintain an 
 *     internal pool of <code>Map.Entry</code> 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).</p>
 *     
 * @author <a href="mailto:[e-mail]">Jean-Marie Dautelle </a>
 * @version 3.7, March 29, 2006
 */
public class FastMap
    /*<K,V>*/implements
    Map/*<K,V>*/,
    Serializable {

    /**
     * 
     */
    private static final long             serialVersionUID        = -4281546938715716829L;

    /**
     * Holds table higher index rotation. 
     */
    private static final int              R0                      = 5;

    /**
     * Holds the table lower index mask. 
     */
    private static final int              M0                      = (1 << FastMap.R0) - 1;

    /**
     * Holds the map's hash table.
     * Use two dimensional arrays to avoid large arrays allocations. 
     */
    private transient Entry/*<K,V>*/[][] _entries;

    /**
     * Holds the head entry to which the first entry attaches.
     * The head entry never changes (entries always added last).
     */
    private transient Entry              /*<K,V>*/_head         = new Entry();

    /**
     * Holds the tail entry to which the last entry attaches.
     * The tail entry changes as entries are added/removed.
     */
    private transient Entry              /*<K,V>*/_tail         = new Entry();

    /**
     * Holds the current size.
     */
    private transient int                 _size;

    /**
     * Holds the values view.
     */
    private transient Values              _values                 = new Values();

    /**
     * Holds the key set view.
     */
    private transient KeySet              _keySet                 = new KeySet();

    /**
     * Holds the entry set view.
     */
    private transient EntrySet            _entrySet               = new EntrySet();

    /**
     * Holds the unmodifiable view.
     */
    private transient Map                /*<K,V>*/_unmodifiable = new Unmodifiable();

    /**
     * Holds a reference to a map having the old entries when resizing.
     */
    private transient FastMap            /*<K,V>*/_oldEntries;

    /**
     * Holds the key comparator.
     */
    private transient FastComparator      _keyComparator          = FastComparator.DEFAULT;

    /**
     * Holds comparator set to <code>null</code> when equivalent to direct.
     */
    private transient FastComparator      _keyComp                = FastComparator.REHASH_SYSTEM_HASHCODE ? FastComparator.REHASH : null;

    /**
     * Indicates if this map is shared (thread-safe).
     */
    private transient boolean             _isShared;

    /**
     * Creates a fast map of small initial capacity.
     */
    public FastMap() {
        this( 4 );
    }

    /**
     * Creates a map of specified initial capacity; unless the map size 
     * reaches the specified capacity, operations on this map will not allocate
     * memory (no lazy object creation).
     * 
     * @param capacity the initial capacity.
     */
    public FastMap(final int capacity) {
        int tableLength = 1 << FastMap.R0;
        while ( tableLength < capacity ) {
            tableLength <<= 1;
        }
        this._entries = new Entry[tableLength >> FastMap.R0][];
        for ( int i = 0; i < this._entries.length; ) {
            this._entries[i++] = new Entry[1 << FastMap.R0];
        }
        this._head._next = this._tail;
        this._tail._previous = this._head;
        Entry/*<K,V>*/previous = this._tail;
        for ( int i = 0; i++ < capacity; ) {
            final Entry/*<K,V>*/newEntry = new Entry/*<K,V>*/();
            newEntry._previous = previous;
            previous._next = newEntry;
            previous = newEntry;
        }
    }

    /**
     * Creates a map containing the specified entries, in the order they
     * are returned by the map iterator.
     *
     * @param map the map whose entries are to be placed into this map.
     */
    public FastMap(final Map/*<? extends K, ? extends V>*/map) {
        this( map.size() );
        putAll( map );
    }

    /**
     * Creates a fast map having the specified entry table.
     * 
     * @param entries the entry table.
     */
    private FastMap(final Entry/*<K,V>*/[][] entries) {
        this._entries = entries;
        this._head._next = this._tail;
        this._tail._previous = this._head;
    }

    /**
     * Returns the head entry of this map.
     *
     * @return the entry such as <code>head().getNext()</code> holds 
     *         the first map entry.
     */
    public final Entry/*<K,V>*/head() {
        return this._head;
    }

    /**
     * Returns the tail entry of this map.
     *
     * @return the entry such as <code>tail().getPrevious()</code>
     *         holds the last map entry.
     */
    public final Entry/*<K,V>*/tail() {
        return this._tail;
    }

    /**
     * Returns the number of key-value mappings in this {@link FastMap}.
     * 
     * @return this map's size.
     */
    public final int size() {
        return this._size;
    }

    /**
     * Indicates if this map contains no key-value mappings.
     * 
     * @return <code>true</code> if this map contains no key-value mappings;
     *         <code>false</code> otherwise.
     */
    public final boolean isEmpty() {
        return this._head._next == this._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 <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>.
     */
    public final boolean containsKey(final 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 <code>true</code> if this map maps one or more keys to the
     *         specified value.
     * @throws NullPointerException if the key is <code>null</code>.
     */
    public final boolean containsValue(final Object value) {
        return this._values.contains( value );
    }

    /**
     * Returns the value to which this map associates 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>.
     */
    public final Object/*V*/get(final Object key) {
        final Entry/*<K,V>*/entry = getEntry( key,
                                               (this._keyComp == null) ? key.hashCode() : this._keyComp.hashCodeOf( key ) );
        return (entry != null) ? entry._value : 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 final Entry/*<K,V>*/getEntry(final Object key) {
        return getEntry( key,
                         (this._keyComp == null) ? key.hashCode() : this._keyComp.hashCodeOf( key ) );
    }

    /**
     * Associates the specified value with the specified key in this map.
     * If this map previously contained a mapping for this key, the old value
     * is replaced. For {@link #isShared() shared} map internal synchronization
     * is automatically performed.
     * 
     * @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>.
     */
    public final Object/*V*/put(final Object/*K*/key,
                                 final Object/*V*/value) {
        final int keyHash = (this._keyComp == null) ? key.hashCode() : this._keyComp.hashCodeOf( key );
        if ( this._isShared ) {
            return putShared( key,
                              value,