]> gerrit.simantics Code Review - simantics/platform.git/blob - bundles/org.simantics.scenegraph/src/gnu/trove/THash.java
Fix compilation problems from org.simantics.gnuplot/pom.xml
[simantics/platform.git] / 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