fastmap.java

jboss规则引擎

    private final class Values extends FastCollection {

        /**
         * 
         */
        private static final long serialVersionUID = 8804295702684770940L;

        public int size() {
            return FastMap.this._size;
        }

        public void clear() {
            FastMap.this.clear();
        }

        public Record head() {
            return FastMap.this._head;
        }

        public Record tail() {
            return FastMap.this._tail;
        }

        public Object valueOf(final Record record) {
            return ((Entry) record)._value;
        }

        public void delete(final Record record) {
            FastMap.this.remove( ((Entry) record).getKey() );
        }
    }

    /**
     * Returns a {@link FastCollection} view of the mappings contained in this
     * map. Each element in the returned collection is a 
     * <code>FastMap.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
     *         (instance of {@link FastCollection}).
     */
    public final Set/*<Map.Entry<K,V>>*/entrySet() {
        return this._entrySet;
    }

    private final class EntrySet extends FastCollection
        implements
        Set {

        /**
         * 
         */
        private static final long serialVersionUID = 8729117163337735415L;

        public int size() {
            return FastMap.this._size;
        }

        public void clear() {
            FastMap.this.clear();
        }

        public boolean contains(final Object obj) { // Optimization.
            if ( obj instanceof Map.Entry ) {
                final Map.Entry entry = (Entry) obj;
                final Entry mapEntry = getEntry( entry.getKey() );
                return entry.equals( mapEntry );
            } else {
                return false;
            }
        }

        public String toString() {
            StringBuffer text = new StringBuffer( "[" );
            final String equ = "=";
            final String sep = ", ";
            for ( Entry e = FastMap.this._head, end = FastMap.this._tail; (e = e._next) != end; ) {
                text = text.append( String.valueOf( e._key ) ).append( equ ).append( String.valueOf( e._value ) );
                if ( e._next != end ) {
                    text = text.append( sep );
                }
            }
            return text.append( ']' ).toString();
        }

        public Record head() {
            return FastMap.this._head;
        }

        public Record tail() {
            return FastMap.this._tail;
        }

        public Object valueOf(final Record record) {
            return record;
        }

        public void delete(final Record record) {
            FastMap.this.remove( ((Entry) record).getKey() );
        }
    }

    /**
     * Returns a {@link FastCollection} view of the keys contained in this 
     * map. 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<f/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
     *         (instance of {@link FastCollection}).
     */
    public final Set/*<K>*/keySet() {
        return this._keySet;
    }

    private final class KeySet extends FastCollection
        implements
        Set {

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

        public int size() {
            return FastMap.this._size;
        }

        public void clear() {
            FastMap.this.clear();
        }

        public boolean contains(final Object obj) { // Optimization.
            return FastMap.this.containsKey( obj );
        }

        public boolean remove(final 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(final Record record) {
            return ((Entry) record)._key;
        }

        public void delete(final Record record) {
            FastMap.this.remove( ((Entry) record).getKey() );
        }
    }

    /**
     * Returns the unmodifiable view associated to this map.
     * Attempts to modify the returned map or to directly access its  
     * (modifiable) map entries (e.g. <code>unmodifiable().entrySet()</code>)
     * result in an {@link UnsupportedOperationException} being thrown.
     * Unmodifiable {@link FastCollection} views of this map keys and values
     * are nonetheless obtainable (e.g. <code>unmodifiable().keySet(), 
     * <code>unmodifiable().values()</code>). 
     *  
     * @return an unmodifiable view of this map.
     */
    public final Map/*<K,V>*/unmodifiable() {
        return this._unmodifiable;
    }

    /**
     * Returns the entry with the specified key and hash code.
     * 
     * @param key the key whose associated entry is to be returned.
     * @param the associated hash code (need to be calculated only once).
     * @return the entry for the specified key or <code>null</code> if none.
     */
    private final Entry/*<K,V>*/getEntry(final Object key,
                                          final int keyHash) {
        Entry/*<K,V>*/entry = this._entries[(keyHash >> FastMap.R0) & (this._entries.length - 1)][keyHash & FastMap.M0];
        while ( entry != null ) {
            if ( (key == entry._key) || ((entry._keyHash == keyHash) && ((this._keyComp == null) ? key.equals( entry._key ) : this._keyComp.areEqual( key,
                                                                                                                                                      entry._key ))) ) {
                return entry;
            }
            entry = entry._beside;
        }
        return (this._oldEntries != null) ? this._oldEntries.getEntry( key,
                                                                       keyHash ) : null;
    }

    /**
     * Adds a new entry for the specified key and value.
     * 
     * @param hash the hash of the key, generated with {@link #keyHash}.
     * @param key the entry's key.
     * @param value the entry's value.
     */
    private void addEntry(final int hash,
                          final Object/*K*/key,
                          final Object/*V*/value) {
        // Updates size.
        if ( (this._size++ >> FastMap.R0) >= this._entries.length ) { // Check if entry table too small. 
            increaseEntryTable();
        }

        if ( this._tail._next == null ) {
            increaseCapacity();
        }
        final Entry newTail = this._tail._next;
        // Setups entry parameters.
        this._tail._key = key;
        this._tail._value = value;
        this._tail._keyHash = hash;
        this._tail._table = this._entries;

        // Connects to bucket.
        final int index = (hash >> FastMap.R0) & (this._entries.length - 1);
        Entry[] tmp = this._entries[index];
        if ( tmp == FastMap.NULL_BLOCK ) {
            newBlock( index );
            tmp = this._entries[index];
        }
        final Entry beside = tmp[hash & FastMap.M0];
        this._tail._beside = beside;
        tmp[hash & FastMap.M0] = this._tail;

        // Moves tail forward.
        this._tail = newTail;
    }

    /**
     * Removes the specified entry from the specified map.
     * The entry is added to the internal pool.
     * 
     * @param entry the entry to be removed.
     * @param the map from which the entry is removed.
     */
    private final void removeEntry(final Entry entry) {

        // Updates size.
        this._size--;

        // Clears value and key.
        entry._key = null;
        entry._value = null;

        // Detaches from list and bucket.
        entry.detach();

        // Re-inserts next tail.
        final Entry next = this._tail._next;
        entry._previous = this._tail;
        entry._next = next;
        this._tail._next = entry;
        if ( next != null ) {
            next._previous = entry;
        }
    }

    // Allocates a new block.
    private void newBlock(final int index) {
        this._entries[index] = new Entry[1 << FastMap.R0];
    }

    // Increases capacity (_tail._next == null)
    private void increaseCapacity() {
        final Entry/*<K,V>*/newEntry0 = new Entry/*<K,V>*/();
        this._tail._next = newEntry0;
        newEntry0._previous = this._tail;

        final Entry/*<K,V>*/newEntry1 = new Entry/*<K,V>*/();
        newEntry0._next = newEntry1;
        newEntry1._previous = newEntry0;

        final Entry/*<K,V>*/newEntry2 = new Entry/*<K,V>*/();
        newEntry1._next = newEntry2;
        newEntry2._previous = newEntry1;

        final Entry/*<K,V>*/newEntry3 = new Entry/*<K,V>*/();
        newEntry2._next = newEntry3;
        newEntry3._previous = newEntry2;

    }

    // Increases the table size, the table length is multiplied by 8.
    // It still ensures that no more half memory space is unused 
    // (most space is being taken by the entries objects themselves).
    private void increaseEntryTable() {
        final int newLength = this._entries.length << 3;
        FastMap/*<K,V>*/tmp;
        if ( newLength <= (1 << 3) ) { //                
            tmp = new FastMap/*<K,V>*/( new Entry[1 << 3][] ); // 256
        } else if ( newLength <= (1 << 6) ) {
            tmp = new FastMap/*<K,V>*/( new Entry[1 << 6][] ); // 2048
        } else if ( newLength <= (1 << 9) ) {
            tmp = new FastMap/*<K,V>*/( new Entry[1 << 9][] ); // 16,384
        } else if ( newLength <= (1 << 12) ) {
            tmp = new FastMap/*<K,V>*/( new Entry[1 << 12][] ); // 131,072
        } else if ( newLength <= (1 << 15) ) {
            tmp = new FastMap/*<K,V>*/( new Entry[1 << 15][] ); // 1,048,576
        } else if ( newLength <= (1 << 18) ) {
            tmp = new FastMap/*<K,V>*/( new Entry[1 << 18][] );
        } else if ( newLength <= (1 << 21) ) {
            tmp = new FastMap/*<K,V>*/( new Entry[1 << 21][] );
        } else if ( newLength <= (1 << 24) ) {
            tmp = new FastMap/*<K,V>*/( new Entry[1 << 24][] );
        } else if ( newLength <= (1 << 27) ) {
            tmp = new FastMap/*<K,V>*/( new Entry[1 << 27][] );
        } else { // Cannot increase.
            return;
        }
        for ( int i = 0; i < tmp._entries.length; ) {
            tmp._entries[i++] = FastMap.NULL_BLOCK;
        }

        // Takes the entry from the new map.