/** * $RCSfile: LongHashMap.java,v $ * $Revision: 1.1 $ * $Date: 2002/06/24 18:51:23 $ * * This class was adapted directly from the Colt sources by CoolServlets Inc. * The changes involved modifying the code so that the functionality could be * encapsulated in a single class file. * * As such, the original copyright is left intact and this file is distributed * under the original Colt license as seen below. Please visit the Colt * homepage for more information about the excellent package: * http://tilde-hoschek.home.cern.ch/~hoschek/colt/index.htm * --------------------------------------------------------------------------- * Copyright ?? 1999 CERN - European Organization for Nuclear Research. * Permission to use, copy, modify, distribute and sell this software and its * documentation for any purpose is hereby granted without fee, provided that * the above copyright notice appear in all copies and that both that copyright * notice and this permission notice appear in supporting documentation. CERN * makes no representations about the suitability of this software for any * purpose. It is provided "as is" without expressed or implied warranty. */package com.struts2.framework.util;/** * Hash map holding (key,value) associations of type <tt>(long-->Object)</tt>; * Automatically grows and shrinks as needed; Implemented using open addressing * with double hashing.<p> * * Adapted from the Colt package by CoolServlets. Please visit the Colt * homepage at: http://tilde-hoschek.home.cern.ch/~hoschek/colt/index.htm * * @author wolfgang.hoschek@cern.ch */public final class LongHashMap {    //The hash table keys.    protected long table[];    //The hash table values.    protected Object values[];    //The state of each hash table entry (FREE, FULL, REMOVED).    protected byte state[];    //The number of table entries in state==FREE.    protected int freeEntries;    //The number of distinct associations in the map; its "size()".    protected int distinct;    /**     * The table capacity c=table.length always satisfies the invariant     * <tt>c * minLoadFactor <= s <= c * maxLoadFactor</tt>, where s=size() is     * the number of associations currently contained. The term     * "c * minLoadFactor" is called the "lowWaterMark", "c * maxLoadFactor" is     * called the "highWaterMark". In other words, the table capacity (and     * proportionally the memory used by this class) oscillates within these     * constraints. The terms are precomputed and cached to avoid recalculating     * them each time put(..) or removeKey(...) is called.     */    protected int lowWaterMark;    protected int highWaterMark;    //The minimum load factor for the hashtable.    protected double minLoadFactor;    //The maximum load factor for the hashtable.    protected double maxLoadFactor;    protected static final int DEFAULT_CAPACITY = 277;    protected static final double DEFAULT_MIN_LOAD_FACTOR = 0.2;    protected static final double DEFAULT_MAX_LOAD_FACTOR = 0.6;    protected static final byte FREE = 0;    protected static final byte FULL = 1;    protected static final byte REMOVED = 2;    /**     * Constructs an empty map with default capacity and default load factors.     */    public LongHashMap() {        this(DEFAULT_CAPACITY);    }    /**     * Constructs an empty map with the specified initial capacity and default     * load factors.     *     * @param      initialCapacity   the initial capacity of the map.     * @throws     IllegalArgumentException if the initial capacity is less     *             than zero.     */    public LongHashMap(int initialCapacity) {        this(initialCapacity, DEFAULT_MIN_LOAD_FACTOR, DEFAULT_MAX_LOAD_FACTOR);    }    /**     * Constructs an empty map with the specified initial capacity and the     * specified minimum and maximum load factor.     *     * @param      initialCapacity   the initial capacity.     * @param      minLoadFactor        the minimum load factor.     * @param      maxLoadFactor        the maximum load factor.     * @throws	IllegalArgumentException if <tt>initialCapacity < 0 ||     *      (minLoadFactor < 0.0 || minLoadFactor >= 1.0) ||     *      (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) ||     *      (minLoadFactor >= maxLoadFactor)</tt>.     */    public LongHashMap(int initialCapacity, double minLoadFactor, double maxLoadFactor) {        setUp(initialCapacity,minLoadFactor,maxLoadFactor);    }    /**     * Removes all (key,value) associations from the receiver.     * Implicitly calls <tt>trimToSize()</tt>.     */    public void clear() {        for (int i=0; i<state.length; i++) {            state[i] = FREE;        }        for (int i=0; i<values.length-1; i++) {            values[i] = null;        }        this.distinct = 0;        this.freeEntries = table.length; // delta        trimToSize();    }    /**     * Returns <tt>true</tt> if the receiver contains the specified key.     *     * @return <tt>true</tt> if the receiver contains the specified key.     */    public boolean containsKey(long key) {        return indexOfKey(key) >= 0;    }    /**     * Returns <tt>true</tt> if the receiver contains the specified value.    *     * @return <tt>true</tt> if the receiver contains the specified value.     */    public boolean containsValue(Object value) {        return indexOfValue(value) >= 0;    }    /**     * Ensures that the receiver can hold at least the specified number of     * associations without needing to allocate new internal memory. If     * necessary, allocates new internal memory and increases the capacity of     * the receiver.<p>     *     * This method never need be called; it is for performance tuning only.     * Calling this method before <tt>put()</tt>ing a large number of     * associations boosts performance, because the receiver will grow only     * once instead of potentially many times and hash collisions get less     * probable.     *     * @param minCapacity the desired minimum capacity.     */    public void ensureCapacity(int minCapacity) {        if (table.length < minCapacity) {            int newCapacity = nextPrime(minCapacity);            rehash(newCapacity);        }    }    /**     * Returns the value associated with the specified key.     * It is often a good idea to first check with {@link #containsKey(long)}     * whether the given key has a value associated or not, i.e. whether there     * exists an association for the given key or not.     *     * @param key the key to be searched for.     * @return the value associated with the specified key; <tt>null</tt> if no     *      such key is present.     */    public final Object get(long key) {        int i = indexOfKey(key);        //If not in the map return null        if (i<0) {            return null;        }        else {            return values[i];        }    }    /**     * Returns the index where the key would need to be inserted, if it is not     * already contained. Returns -index-1 if the key is already contained     * at slot index. Therefore, if the returned index < 0, then it is     * already contained at slot -index-1. If the returned index >= 0,     * then it is NOT already contained and should be inserted at slot index.     *     * @param key the key to be added to the receiver.     * @return the index where the key would need to be inserted.     */    private final int indexOfInsertion(long key) {        final long tab[] = table;        final byte stat[] = state;        final int length = tab.length;        final int hash = ((int)(key ^ (key >> 32))) & 0x7FFFFFFF;        int i = hash % length;        // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html        int decrement = (hash) % (length-2);        //OLD CODE: int decrement = (hash / length) % length;        if (decrement == 0) decrement = 1;        // stop if we find a removed or free slot, or if we find the key itself        // do NOT skip over removed slots (yes, open addressing is like that...)        while (stat[i] == FULL && tab[i] != key) {        i -= decrement;            //hashCollisions++;            if (i<0) i+=length;        }        if (stat[i] == REMOVED) {            // stop if we find a free slot, or if we find the key itself.            // do skip over removed slots (yes, open addressing is like that...)            // assertion: there is at least one FREE slot.            int j = i;            while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) {                i -= decrement;                //hashCollisions++;                if (i<0) i+=length;            }            if (stat[i] == FREE) i = j;        }        if (stat[i] == FULL) {            // key already contained at slot i.            // return a negative number identifying the slot.            return -i-1;        }        // not already contained, should be inserted at slot i.        // return a number >= 0 identifying the slot.        return i;    }    /**     * @param key the key to be searched in the receiver.     * @return the index where the key is contained in the receiver, returns -1     *      if the key was not found.     */    private final int indexOfKey(long key) {        final long tab[] = table;        final byte stat[] = state;        final int length = tab.length;        final int hash = ((int)(key ^ (key >> 32))) & 0x7FFFFFFF;        int i = hash % length;        // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html        int decrement = (hash) % (length-2);        //OLD CODE: int decrement = (hash / length) % length;        if (decrement == 0) decrement = 1;        // stop if we find a free slot, or if we find the key itself.        // do skip over removed slots (yes, open addressing is like that...)        while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) {            i -= decrement;            //hashCollisions++;            if (i<0) i+=length;        }        if (stat[i] == FREE) return -1; // not found        return i; //found, return index where key is contained    }    /**     * @param value the value to be searched in the receiver.     * @return the index where the value is contained in the receiver,     *      returns -1 if the value was not found.     */    protected int indexOfValue(Object value) {        final Object val[] = values;        final byte stat[] = state;        for (int i=stat.length; --i >= 0;) {            if (stat[i]==FULL && val[i]==value) return i;        }        return -1; // not found    }    /**     * Returns the first key the given value is associated with.     *     * @param value the value to search for.     * @return the first key for which holds <tt>get(key) == value</tt>;     *		   returns <tt>Long.MIN_VALUE</tt> if no such key exists.     */    public long keyOf(Object value) {        //returns the first key found; there may be more matching keys, however.        int i = indexOfValue(value);        if (i<0) return Long.MIN_VALUE;        return table[i];    }    /**     * Returns all the keys in the map.     */    public long[] keys() {        long[] elements = new long[distinct];        long[] tab = table;        byte[] stat = state;        int j=0;        for (int i = tab.length ; i-- > 0 ;) {            if (stat[i]==FULL) {                elements[j++]=tab[i];            }        }        return elements;    }    /**     * Associates the given key with the given value. Replaces any old     * <tt>(key,someOtherValue)</tt> association, if existing.     *     * @param key the key the value shall be associated with.     * @param value the value to be associated.     * @return <tt>true</tt> if the receiver did not already contain such a key;     *      <tt>false</tt> if the receiver did already contain such a key - the     *      new value has now replaced the formerly associated value.     */    public boolean put(long key, Object value) {        int i = indexOfInsertion(key);        if (i<0) { //already contained            i = -i -1;            this.values[i]=value;            return false;        }        if (this.distinct > this.highWaterMark) {            int newCapacity = chooseGrowCapacity(                    this.distinct+1,                    this.minLoadFactor,                    this.maxLoadFactor                );            rehash(newCapacity);            return put(key, value);        }        this.table[i]=key;        this.values[i]=value;        if (this.state[i]==FREE) this.freeEntries--;        this.state[i]=FULL;