KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > mondrian > util > ObjectPool


1 /*
2 // $Id: //open/mondrian/src/main/mondrian/util/ObjectPool.java#2 $
3 // This software is subject to the terms of the Common Public License
4 // Agreement, available at the following URL:
5 // http://www.opensource.org/licenses/cpl.html.
6 // Copyright (C) 2007-2007 Julian Hyde and others
7 // All Rights Reserved.
8 // You must accept the terms of that agreement to use this software.
9 */

10
11 // Copyright (c) 1999 CERN - European Organization for Nuclear Research.
12
// Permission to use, copy, modify, distribute and sell this software
13
// and its documentation for any purpose is hereby granted without fee,
14
// provided that the above copyright notice appear in all copies and
15
// that both that copyright notice and this permission notice appear in
16
// supporting documentation. CERN makes no representations about the
17
// suitability of this software for any purpose. It is provided "as is"
18
// without expressed or implied warranty.
19

20 // Created from package cern.colt.map by Richard Emberson, 2007/1/23.
21
// For the source to the Colt project, go to:
22
// http://dsd.lbl.gov/~hoschek/colt/
23

24 package mondrian.util;
25
26 import java.util.Iterator JavaDoc;
27
28 /**
29  * An <code>ObjectPool</code> is a low-memory replacement for a
30  * {@link java.util.HashSet}. A HashSet contains a {@link java.util.HashMap}
31  * which in turn has
32  * an array of Entry objects, the Entry objects themselves, and the
33  * key and value objects. An ObjectPool has simply an array of
34  * objects and the objects themselves which server as both key and value.
35  * <p>
36  * This is like the String <code>intern</code> method, but works for
37  * an Object type and whereas the String <code>intern</code> method is global
38  * an ObjectPool can be used within a context and then garbage collected.
39  * Objects can not removed from an ObjectPool except by calling the
40  * <code>clear</code> method which removes all objects.
41  * <p>
42  * Just as with a HashSet's key objects, objects to be placed into
43  * an ObjectPool must implement the <code>equals</code> and
44  * <code>hashCode</code> methods.
45  * <p>
46  * This implementation is NOT thread safe.
47  *
48  * @author Richard Emberson
49  * @version $Id: //open/mondrian/src/main/mondrian/util/ObjectPool.java#2 $
50  */

51 public class ObjectPool<T> {
52     // TODO: Use bits, the state byte array could be a bit array.
53
// The Cern code has to use bytes because they also support
54
// a REMOVE (== 2) state value but for the ObjectPool we only
55
// have FREE or FULL so the use of bits is possible; the
56
// state byte array could be a bit vector which would save
57
// some memory.
58
protected static final byte FREE = 0;
59     protected static final byte FULL = 1;
60
61     protected static final int DEFAULT_CAPACITY = 277;
62     protected static final double DEFAULT_MIN_LOAD_FACTOR = 0.2;
63     protected static final double DEFAULT_MAX_LOAD_FACTOR = 0.5;
64
65
66     /**
67      * The number of distinct associations in the map; its "size()".
68      */

69     protected int distinct;
70
71     protected int lowWaterMark;
72     protected int highWaterMark;
73
74     /**
75      * The minimum load factor for the hashtable.
76      */

77     protected double minLoadFactor;
78
79     /**
80      * The maximum load factor for the hashtable.
81      */

82     protected double maxLoadFactor;
83
84     protected T[] values;
85     /**
86      * Whether a position in the values array is FREE or FULL.
87      */

88     protected byte[] state;
89
90     /**
91      * The number of table entries in state==FREE.
92      */

93     protected int freeEntries;
94
95
96
97     public ObjectPool() {
98         this(DEFAULT_CAPACITY);
99     }
100     public ObjectPool(int initialCapacity) {
101         this(initialCapacity, DEFAULT_MIN_LOAD_FACTOR, DEFAULT_MAX_LOAD_FACTOR);
102     }
103     public ObjectPool(int initialCapacity,
104                       double minLoadFactor,
105                       double maxLoadFactor) {
106         setUp(initialCapacity,minLoadFactor,maxLoadFactor);
107     }
108
109     /**
110      * Return the number of entries in the ObjectPool.
111      *
112      * @return number of entries.
113      */

114     public int size() {
115         return distinct;
116     }
117
118     /**
119      * Reduce the size of the internal arrays to a size just big
120      * enough to hold the current set of entries. Generally, this
121      * should only be called after all entries have been added.
122      * Calling this causes a new, smaller array to be allocated, the
123      * objects are copied to the new array and then the old array is
124      * free to be garbage collected; there is a small time when both
125      * arrays are in memory.
126      */

127     public void trimToSize() {
128         // * 1.2 because open addressing's performance
129
// exponentially degrades beyond that point
130
// so that even rehashing the table can take very long
131
int newCapacity = nextPrime((int)(1 + 1.2*size()));
132         if (values.length > newCapacity) {
133             rehash(newCapacity);
134         }
135     }
136
137     /**
138      * Returns true it the Object is already in the ObjectPool and false
139      * otherwise.
140      *
141      * @param key Object to test if member already or not.
142      * @return true is already member
143      */

144     public boolean contains(T key) {
145         int i = indexOfInsertion(key);
146         return (i < 0);
147     }
148
149     /**
150      * Adds an object to the ObjectPool if it is not
151      * already in the pool or returns the object that is already in the
152      * pool that matches the object being added.
153      *
154      * @param key
155      * @return
156      */

157     public T add(T key) {
158         int i = indexOfInsertion(key);
159         if (i < 0) {
160             //already contained
161
i = -i -1;
162             return this.values[i];
163         }
164
165         if (this.distinct > this.highWaterMark) {
166             int newCapacity = chooseGrowCapacity(this.distinct+1,
167                                                  this.minLoadFactor,
168                                                  this.maxLoadFactor);
169             rehash(newCapacity);
170             return add(key);
171         }
172
173         this.values[i] = key;
174
175         if (this.state[i] == FREE) {
176             this.freeEntries--;
177         }
178         this.state[i] = FULL;
179         this.distinct++;
180
181         if (this.freeEntries < 1) {
182             //delta
183
int newCapacity = chooseGrowCapacity(this.distinct+1,
184                                                  this.minLoadFactor,
185                                                  this.maxLoadFactor);
186              rehash(newCapacity);
187         }
188
189         return key;
190     }
191
192     /**
193      * Removes all objects from the pool but keeps the current size of
194      * the internal storage.
195      */

196     public void clear() {
197         values = (T[]) new Object JavaDoc[values.length];
198         state = new byte[state.length];
199
200         this.distinct = 0;
201         this.freeEntries = values.length; // delta
202
trimToSize();
203     }
204
205     /**
206      * Returns an Iterator of this <code>ObjectPool</code>. The order of
207      * the Objects returned by the <code>Iterator</code> can not be
208      * counted on to be in the same order as they were inserted
209      * into the <code>ObjectPool</code>. The
210      * <code>Iterator</code> returned does not
211      * support the removal of <code>ObjectPool</code> members.
212      */

213     public Iterator JavaDoc iterator() {
214         return new Itr();
215     }
216
217
218
219     protected int chooseGrowCapacity(int size, double minLoad, double maxLoad) {
220         return nextPrime(Math.max(size+1,
221             (int) ((4*size / (3*minLoad+maxLoad)))));
222     }
223     protected int chooseHighWaterMark(int capacity, double maxLoad) {
224         //makes sure there is always at least one FREE slot
225
return Math.min(capacity-2, (int) (capacity * maxLoad));
226     }
227     protected int chooseLowWaterMark(int capacity, double minLoad) {
228         return (int) (capacity * minLoad);
229     }
230     protected int chooseMeanCapacity(int size, double minLoad, double maxLoad) {
231         return nextPrime(Math.max(size+1, (int) ((2*size/(minLoad+maxLoad)))));
232     }
233     protected int chooseShrinkCapacity(int size, double minLoad, double maxLoad) {
234         return nextPrime(Math.max(size+1, (int) ((4*size/(minLoad+3*maxLoad)))));
235     }
236
237     protected int nextPrime(int desiredCapacity) {
238         return PrimeFinder.nextPrime(desiredCapacity);
239     }
240
241     protected void setUp(int initialCapacity,
242                          double minLoadFactor,
243                          double maxLoadFactor) {
244         int capacity = initialCapacity;
245
246         if (initialCapacity < 0) {
247             throw new IllegalArgumentException JavaDoc(
248                 "Initial Capacity must not be less than zero: "+
249                 initialCapacity);
250         }
251         if (minLoadFactor < 0.0 || minLoadFactor >= 1.0) {
252             throw new IllegalArgumentException JavaDoc(
253                 "Illegal minLoadFactor: "+ minLoadFactor);
254         }
255         if (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) {
256             throw new IllegalArgumentException JavaDoc(
257                 "Illegal maxLoadFactor: "+ maxLoadFactor);
258         }
259         if (minLoadFactor >= maxLoadFactor) {
260             throw new IllegalArgumentException JavaDoc(
261                 "Illegal minLoadFactor: "+ minLoadFactor+
262                 " and maxLoadFactor: "+ maxLoadFactor);
263         }
264         capacity = nextPrime(capacity);
265
266         // open addressing needs at least one FREE slot at any time.
267
if (capacity == 0) {
268             capacity = 1;
269         }
270
271         //this.table = new long[capacity];
272
this.values = (T[]) new Object JavaDoc[capacity];
273         this.state = new byte[capacity];
274
275         // memory will be exhausted long before this
276
// pathological case happens, anyway.
277
this.minLoadFactor = minLoadFactor;
278         if (capacity == PrimeFinder.largestPrime) {
279             this.maxLoadFactor = 1.0;
280         } else {
281             this.maxLoadFactor = maxLoadFactor;
282         }
283
284         this.distinct = 0;
285         this.freeEntries = capacity; // delta
286
// lowWaterMark will be established upon first expansion.
287
// establishing it now (upon instance construction) would
288
// immediately make the table shrink upon first put(...).
289
// After all the idea of an "initialCapacity" implies
290
// violating lowWaterMarks when an object is young.
291
// See ensureCapacity(...)
292
this.lowWaterMark = 0;
293         this.highWaterMark = chooseHighWaterMark(capacity, this.maxLoadFactor);
294
295     }
296
297
298     protected int hash(T key) {
299         return (key == null) ? 0 : key.hashCode();
300     }
301     protected boolean equals(T t, T key) {
302         return (t != null) && t.equals(key);
303     }
304
305     protected int indexOfInsertion(T key) {
306         final T[] tab = values;
307         final byte[] stat = state;
308         final int length = tab.length;
309
310         final int hash = hash(key) & 0x7FFFFFFF;
311         int i = hash % length;
312
313         // double hashing,
314
// see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
315
int decrement = hash % (length-2);
316
317         //int decrement = (hash / length) % length;
318
if (decrement == 0) {
319             decrement = 1;
320         }
321
322         // stop if we find a free slot, or if we find the key itself
323
while ((stat[i] == FULL) && !equals(tab[i], key)) {
324             i -= decrement;
325             //hashCollisions++;
326
if (i < 0) {
327                 i += length;
328             }
329         }
330
331         // key already contained at slot i.
332
// return a negative number identifying the slot.
333
// not already contained, should be inserted at slot i.
334
// return a number >= 0 identifying the slot.
335
return (stat[i] == FULL) ? -i-1 : i;
336     }
337
338     protected void rehash(int newCapacity) {
339         int oldCapacity = values.length;
340
341         T[] oldValues = values;
342         byte[] oldState = state;
343
344         T[] newValues = (T[]) new Object JavaDoc[newCapacity];
345         byte[] newState = new byte[newCapacity];
346
347         this.lowWaterMark = chooseLowWaterMark(newCapacity,this.minLoadFactor);
348         this.highWaterMark = chooseHighWaterMark(newCapacity,this.maxLoadFactor);
349
350         this.values = newValues;
351         this.state = newState;
352         this.freeEntries = newCapacity-this.distinct; // delta
353
for (int i = oldCapacity ; i-- > 0 ;) {
354             if (oldState[i]==FULL) {
355                 T element = oldValues[i];
356                 int index = indexOfInsertion(element);
357                 newValues[index]=element;
358                 newState[index]=FULL;
359             }
360         }
361     }
362
363     private class Itr implements Iterator JavaDoc<T> {
364         int index = 0;
365         Itr() {
366         }
367         public boolean hasNext() {
368             if (index == ObjectPool.this.state.length) {
369                 return false;
370             }
371             while (ObjectPool.this.state[index] != FULL) {
372                 index++;
373                 if (index == ObjectPool.this.state.length) {
374                     return false;
375                 }
376             }
377             return (ObjectPool.this.state[index] == FULL);
378         }
379         public T next() {
380             return ObjectPool.this.values[index++];
381         }
382         public void remove() {
383             throw new UnsupportedOperationException JavaDoc("ObjectPool.Itr.remove");
384         }
385     }
386 }
387
388 // End ObjectPool.java
389
Popular Tags