bundles/org.simantics.scenegraph/src/gnu/trove/THash.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 import java.io.Externalizable;
  22 import java.io.ObjectOutput;
  23 import java.io.IOException;
  24 import java.io.ObjectInput;
  25
  26
  27 /**
  28  * Base class for hashtables that use open addressing to resolve
  29  * collisions.
  30  *
  31  * Created: Wed Nov 28 21:11:16 2001
  32  *
  33  * @author Eric D. Friedman
  34  * @author Rob Eden (auto-compaction)
  35  *
  36  * @version $Id: THash.java,v 1.14 2008/10/08 16:39:10 robeden Exp $
  37  */
  38
  39 abstract public class THash implements Cloneable, Externalizable {
  40     static final long serialVersionUID = -1792948471915530295L;
  41
  42     /** the load above which rehashing occurs. */
  43     protected static final float DEFAULT_LOAD_FACTOR = 0.5f;
  44
  45     /** the default initial capacity for the hash table.  This is one
  46      * less than a prime value because one is added to it when
  47      * searching for a prime capacity to account for the free slot
  48      * required by open addressing. Thus, the real default capacity is
  49      * 11. */
  50     protected static final int DEFAULT_INITIAL_CAPACITY = 10;
  51
  52
  53     /** the current number of occupied slots in the hash. */
  54     protected transient int _size;
  55
  56     /** the current number of free slots in the hash. */
  57     protected transient int _free;
  58
  59     /** Determines how full the internal table can become before
  60      * rehashing is required. This must be a value in the range: 0.0 <
  61      * loadFactor < 1.0.  The default value is 0.5, which is about as
  62      * large as you can get in open addressing without hurting
  63      * performance.  Cf. Knuth, Volume 3., Chapter 6.
  64      */
  65     protected float _loadFactor;
  66
  67     /**
  68      * The maximum number of elements allowed without allocating more
  69      * space.
  70      */
  71     protected int _maxSize;
  72
  73
  74     /**
  75      * The number of removes that should be performed before an auto-compaction occurs.
  76      */
  77     protected int _autoCompactRemovesRemaining;
  78
  79     /**
  80      * The auto-compaction factor for the table.
  81      *
  82      * @see #setAutoCompactionFactor
  83      */
  84     protected float _autoCompactionFactor;
  85
  86     /**
  87      * @see #tempDisableAutoCompaction
  88      */
  89     private transient boolean _autoCompactTemporaryDisable = false;
  90
  91
  92     /**
  93      * Creates a new <code>THash</code> instance with the default
  94      * capacity and load factor.
  95      */
  96     public THash() {
  97         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
  98     }
  99
 100     /**
 101      * Creates a new <code>THash</code> instance with a prime capacity
 102      * at or near the specified capacity and with the default load
 103      * factor.
 104      *
 105      * @param initialCapacity an <code>int</code> value
 106      */
 107     public THash(int initialCapacity) {
 108         this(initialCapacity, DEFAULT_LOAD_FACTOR);
 109     }
 110
 111     /**
 112      * Creates a new <code>THash</code> instance with a prime capacity
 113      * at or near the minimum needed to hold <tt>initialCapacity</tt>
 114      * elements with load factor <tt>loadFactor</tt> without triggering
 115      * a rehash.
 116      *
 117      * @param initialCapacity an <code>int</code> value
 118      * @param loadFactor a <code>float</code> value
 119      */
 120     public THash(int initialCapacity, float loadFactor) {
 121         super();
 122         _loadFactor = loadFactor;
 123
 124         // Through testing, the load factor (especially the default load factor) has been
 125         // found to be a pretty good starting auto-compaction factor.
 126         _autoCompactionFactor = loadFactor;
 127
 128         setUp(HashFunctions.fastCeil(initialCapacity / loadFactor));
 129     }
 130
 131     public Object clone() {
 132         try {
 133             return super.clone();
 134         } catch (CloneNotSupportedException cnse) {
 135             return null; // it's supported
 136         }
 137     }
 138
 139     /**
 140      * Tells whether this set is currently holding any elements.
 141      *
 142      * @return a <code>boolean</code> value
 143      */
 144     public boolean isEmpty() {
 145         return 0 == _size;
 146     }
 147
 148     /**
 149      * Returns the number of distinct elements in this collection.
 150      *
 151      * @return an <code>int</code> value
 152      */
 153     public int size() {
 154         return _size;
 155     }
 156
 157     /**
 158      * @return the current physical capacity of the hash table.
 159      */
 160     abstract protected int capacity();
 161
 162     /**
 163      * Ensure that this hashtable has sufficient capacity to hold
 164      * <tt>desiredCapacity<tt> <b>additional</b> elements without
 165      * requiring a rehash.  This is a tuning method you can call
 166      * before doing a large insert.
 167      *
 168      * @param desiredCapacity an <code>int</code> value
 169      */
 170     public void ensureCapacity(int desiredCapacity) {
 171         if (desiredCapacity > (_maxSize - size())) {
 172             rehash(PrimeFinder.nextPrime(HashFunctions.fastCeil(
 173                 (desiredCapacity + size()) / _loadFactor) + 1));
 174             computeMaxSize(capacity());
 175         }
 176     }
 177
 178     /**
 179      * Compresses the hashtable to the minimum prime size (as defined
 180      * by PrimeFinder) that will hold all of the elements currently in
 181      * the table.  If you have done a lot of <tt>remove</tt>
 182      * operations and plan to do a lot of queries or insertions or
 183      * iteration, it is a good idea to invoke this method.  Doing so
 184      * will accomplish two things:
 185      *
 186      * <ol>
 187      * <li> You'll free memory allocated to the table but no
 188      * longer needed because of the remove()s.</li>
 189      *
 190      * <li> You'll get better query/insert/iterator performance
 191      * because there won't be any <tt>REMOVED</tt> slots to skip
 192      * over when probing for indices in the table.</li>
 193      * </ol>
 194      */
 195     public void compact() {
 196         // need at least one free spot for open addressing
 197         rehash(PrimeFinder.nextPrime(HashFunctions.fastCeil(size()/_loadFactor) + 1));
 198         computeMaxSize(capacity());
 199
 200         // If auto-compaction is enabled, re-determine the compaction interval
 201         if ( _autoCompactionFactor != 0 ) {
 202             computeNextAutoCompactionAmount(size());
 203         }
 204     }
 205
 206
 207     /**
 208      * The auto-compaction factor controls whether and when a table performs a
 209      * {@link #compact} automatically after a certain number of remove operations.
 210      * If the value is non-zero, the number of removes that need to occur for
 211      * auto-compaction is the size of table at the time of the previous compaction
 212      * (or the initial capacity) multiplied by this factor.
 213      * <p>
 214      * Setting this value to zero will disable auto-compaction.
 215      */
 216     public void setAutoCompactionFactor( float factor ) {
 217         if ( factor < 0 ) {
 218             throw new IllegalArgumentException( "Factor must be >= 0: " + factor );
 219         }
 220
 221         _autoCompactionFactor = factor;
 222     }
 223
 224     /**
 225      * @see #setAutoCompactionFactor
 226      */
 227     public float getAutoCompactionFactor() {
 228         return _autoCompactionFactor;
 229     }
 230
 231
 232     /**
 233      * This simply calls {@link #compact compact}.  It is included for
 234      * symmetry with other collection classes.  Note that the name of this
 235      * method is somewhat misleading (which is why we prefer
 236      * <tt>compact</tt>) as the load factor may require capacity above
 237      * and beyond the size of this collection.
 238      *
 239      * @see #compact
 240      */
 241     public final void trimToSize() {
 242         compact();
 243     }
 244
 245     /**
 246      * Delete the record at <tt>index</tt>.  Reduces the size of the
 247      * collection by one.
 248      *
 249      * @param index an <code>int</code> value
 250      */
 251     protected void removeAt(int index) {
 252         _size--;
 253
 254         // If auto-compaction is enabled, see if we need to compact
 255         if ( _autoCompactionFactor != 0 ) {
 256             _autoCompactRemovesRemaining--;
 257
 258             if ( !_autoCompactTemporaryDisable && _autoCompactRemovesRemaining <= 0 ) {
 259                 // Do the compact
 260                 // NOTE: this will cause the next compaction interval to be calculated
 261                 compact();
 262             }
 263         }
 264     }
 265
 266     /**
 267      * Empties the collection.
 268      */
 269     public void clear() {
 270         _size = 0;
 271         _free = capacity();
 272     }
 273
 274     /**
 275      * initializes the hashtable to a prime capacity which is at least
 276      * <tt>initialCapacity + 1</tt>.
 277      *
 278      * @param initialCapacity an <code>int</code> value
 279      * @return the actual capacity chosen
 280      */
 281     protected int setUp(int initialCapacity) {
 282         int capacity;
 283
 284         capacity = PrimeFinder.nextPrime(initialCapacity);
 285         computeMaxSize(capacity);
 286         computeNextAutoCompactionAmount(initialCapacity);
 287
 288         return capacity;
 289     }
 290
 291     /**
 292      * Rehashes the set.
 293      *
 294      * @param newCapacity an <code>int</code> value
 295      */
 296     protected abstract void rehash(int newCapacity);
 297
 298     /**
 299      * Temporarily disables auto-compaction. MUST be followed by calling
 300      * {@link #reenableAutoCompaction}.
 301      */
 302     protected void tempDisableAutoCompaction() {
 303         _autoCompactTemporaryDisable = true;
 304     }
 305
 306     /**
 307      * Re-enable auto-compaction after it was disabled via
 308      * {@link #tempDisableAutoCompaction()}.
 309      *
 310      * @param check_for_compaction      True if compaction should be performed if needed
 311      *                                  before returning. If false, no compaction will be
 312      *                                  performed.
 313      */
 314     protected void reenableAutoCompaction( boolean check_for_compaction ) {
 315         _autoCompactTemporaryDisable = false;
 316
 317         if ( check_for_compaction && _autoCompactRemovesRemaining <= 0 &&
 318             _autoCompactionFactor != 0 ) {
 319
 320             // Do the compact
 321             // NOTE: this will cause the next compaction interval to be calculated
 322             compact();
 323         }
 324     }
 325
 326
 327     /**
 328      * Computes the values of maxSize. There will always be at least
 329      * one free slot required.
 330      *
 331      * @param capacity an <code>int</code> value
 332      */
 333     private void computeMaxSize(int capacity) {
 334         // need at least one free slot for open addressing
 335         _maxSize = Math.min(capacity - 1, (int) (capacity * _loadFactor));
 336         _free = capacity - _size; // reset the free element count
 337     }
 338
 339
 340     /**
 341      * Computes the number of removes that need to happen before the next auto-compaction
 342      * will occur.
 343      */
 344     private void computeNextAutoCompactionAmount( int size ) {
 345         if ( _autoCompactionFactor != 0 ) {
 346             // NOTE: doing the round ourselves has been found to be faster than using
 347             //       Math.round.
 348             _autoCompactRemovesRemaining =
 349                 ( int ) ( ( size * _autoCompactionFactor ) + 0.5f );
 350         }
 351     }
 352
 353
 354     /**
 355      * After an insert, this hook is called to adjust the size/free
 356      * values of the set and to perform rehashing if necessary.
 357      */
 358     protected final void postInsertHook(boolean usedFreeSlot) {
 359         if (usedFreeSlot) {
 360             _free--;
 361         }
 362
 363         // rehash whenever we exhaust the available space in the table
 364         if (++_size > _maxSize || _free == 0) {
 365             // choose a new capacity suited to the new state of the table
 366             // if we've grown beyond our maximum size, double capacity;
 367             // if we've exhausted the free spots, rehash to the same capacity,
 368             // which will free up any stale removed slots for reuse.
 369             int newCapacity = _size > _maxSize ? PrimeFinder.nextPrime(capacity() << 1) : capacity();
 370             rehash(newCapacity);
 371             computeMaxSize(capacity());
 372         }
 373     }
 374
 375     protected int calculateGrownCapacity() {
 376         return capacity() << 1;
 377     }
 378
 379
 380     public void writeExternal(ObjectOutput out) throws IOException {
 381         // VERSION
 382         out.writeByte( 0 );
 383
 384         // LOAD FACTOR
 385         out.writeFloat( _loadFactor );
 386
 387         // AUTO COMPACTION LOAD FACTOR
 388         out.writeFloat( _autoCompactionFactor );
 389     }
 390
 391     public void readExternal(ObjectInput in)
 392         throws IOException, ClassNotFoundException {
 393
 394         // VERSION
 395         in.readByte();
 396
 397         // LOAD FACTOR
 398         float old_factor = _loadFactor;
 399         _loadFactor = in.readFloat();
 400
 401         // AUTO COMPACTION LOAD FACTOR
 402         _autoCompactionFactor = in.readFloat();
 403
 404
 405         // If we change the laod factor from the default, re-setup
 406         if ( old_factor != _loadFactor ) {
 407             setUp((int)Math.ceil(DEFAULT_INITIAL_CAPACITY / _loadFactor));
 408         }
 409     }
 410 }// THash