bundles/org.simantics.scenegraph/src/gnu/trove/TPrimitiveHash.java

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
   3 //
   4 // This library is free software; you can redistribute it and/or
   5 // modify it under the terms of the GNU Lesser General Public
   6 // License as published by the Free Software Foundation; either
   7 // version 2.1 of the License, or (at your option) any later version.
   8 //
   9 // This library is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Lesser General Public
  15 // License along with this program; if not, write to the Free Software
  16 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  17 ///////////////////////////////////////////////////////////////////////////////
  18
  19 package gnu.trove;
  20
  21 /**
  22  * The base class for hashtables of primitive values.  Since there is
  23  * no notion of object equality for primitives, it isn't possible to
  24  * use a `REMOVED' object to track deletions in an open-addressed table.
  25  * So, we have to resort to using a parallel `bookkeeping' array of bytes,
  26  * in which flags can be set to indicate that a particular slot in the
  27  * hash table is FREE, FULL, or REMOVED.
  28  *
  29  * Created: Fri Jan 11 18:55:16 2002
  30  *
  31  * @author Eric D. Friedman
  32  * @version $Id: TPrimitiveHash.java,v 1.5 2008/10/08 16:39:10 robeden Exp $
  33  */
  34
  35 abstract public class TPrimitiveHash extends THash  {
  36     /** flags indicating whether each position in the hash is
  37      * FREE, FULL, or REMOVED */
  38     protected transient byte[] _states;
  39
  40     /* constants used for state flags */
  41
  42     /** flag indicating that a slot in the hashtable is available */
  43     protected static final byte FREE = 0;
  44
  45     /** flag indicating that a slot in the hashtable is occupied */
  46     protected static final byte FULL = 1;
  47
  48     /** flag indicating that the value of a slot in the hashtable
  49      * was deleted */
  50     protected static final byte REMOVED = 2;
  51
  52     /**
  53      * Creates a new <code>THash</code> instance with the default
  54      * capacity and load factor.
  55      */
  56     public TPrimitiveHash() {
  57         super();
  58     }
  59
  60     /**
  61      * Creates a new <code>TPrimitiveHash</code> instance with a prime
  62      * capacity at or near the specified capacity and with the default
  63      * load factor.
  64      *
  65      * @param initialCapacity an <code>int</code> value
  66      */
  67     public TPrimitiveHash(int initialCapacity) {
  68         this(initialCapacity, DEFAULT_LOAD_FACTOR);
  69     }
  70
  71     /**
  72      * Creates a new <code>TPrimitiveHash</code> instance with a prime
  73      * capacity at or near the minimum needed to hold
  74      * <tt>initialCapacity<tt> elements with load factor
  75      * <tt>loadFactor</tt> without triggering a rehash.
  76      *
  77      * @param initialCapacity an <code>int</code> value
  78      * @param loadFactor a <code>float</code> value
  79      */
  80     public TPrimitiveHash(int initialCapacity, float loadFactor) {
  81         super();
  82         _loadFactor = loadFactor;
  83         setUp(HashFunctions.fastCeil(initialCapacity / loadFactor));
  84     }
  85
  86     public Object clone() {
  87         TPrimitiveHash h = (TPrimitiveHash)super.clone();
  88         h._states = (byte[])this._states.clone();
  89         return h;
  90     }
  91
  92     /**
  93      * Returns the capacity of the hash table.  This is the true
  94      * physical capacity, without adjusting for the load factor.
  95      *
  96      * @return the physical capacity of the hash table.
  97      */
  98     protected int capacity() {
  99         return _states.length;
 100     }
 101
 102     /**
 103      * Delete the record at <tt>index</tt>.
 104      *
 105      * @param index an <code>int</code> value
 106      */
 107     protected void removeAt(int index) {
 108         _states[index] = REMOVED;
 109         super.removeAt(index);
 110     }
 111
 112     /**
 113      * initializes the hashtable to a prime capacity which is at least
 114      * <tt>initialCapacity + 1</tt>.
 115      *
 116      * @param initialCapacity an <code>int</code> value
 117      * @return the actual capacity chosen
 118      */
 119     protected int setUp(int initialCapacity) {
 120         int capacity;
 121
 122         capacity = super.setUp(initialCapacity);
 123         _states = new byte[capacity];
 124         return capacity;
 125     }
 126 } // TPrimitiveHash