001 /*
002 // $Id: //open/mondrian/src/main/mondrian/util/ObjectPool.java#8 $
003 // This software is subject to the terms of the Common Public License
004 // Agreement, available at the following URL:
005 // http://www.opensource.org/licenses/cpl.html.
006 // Copyright (C) 2007-2008 Julian Hyde and others
007 // All Rights Reserved.
008 // You must accept the terms of that agreement to use this software.
009 */
010
011 // Copyright (c) 1999-2007 CERN - European Organization for Nuclear Research.
012 // Permission to use, copy, modify, distribute and sell this software
013 // and its documentation for any purpose is hereby granted without fee,
014 // provided that the above copyright notice appear in all copies and
015 // that both that copyright notice and this permission notice appear in
016 // supporting documentation. CERN makes no representations about the
017 // suitability of this software for any purpose. It is provided "as is"
018 // without expressed or implied warranty.
019
020 // Created from package cern.colt.map by Richard Emberson, 2007/1/23.
021 // For the source to the Colt project, go to:
022 // http://dsd.lbl.gov/~hoschek/colt/
023
024 package mondrian.util;
025
026 import java.util.Iterator;
027 import java.util.NoSuchElementException;
028
029 /**
030 * An <code>ObjectPool</code> is a low-memory replacement for a
031 * {@link java.util.HashSet}. A HashSet contains a {@link java.util.HashMap}
032 * which in turn has
033 * an array of Entry objects, the Entry objects themselves, and the
034 * key and value objects. An ObjectPool has simply an array of
035 * objects and the objects themselves which server as both key and value.
036 * <p>
037 * This is like the String <code>intern</code> method, but works for
038 * an Object type and whereas the String <code>intern</code> method is global
039 * an ObjectPool can be used within a context and then garbage collected.
040 * Objects can not removed from an ObjectPool except by calling the
041 * <code>clear</code> method which removes all objects.
042 * <p>
043 * Just as with a HashSet's key objects, objects to be placed into
044 * an ObjectPool must implement the <code>equals</code> and
045 * <code>hashCode</code> methods.
046 * <p>
047 * This implementation is NOT thread safe.
048 *
049 * @author Richard Emberson
050 * @version $Id: //open/mondrian/src/main/mondrian/util/ObjectPool.java#8 $
051 */
052 public class ObjectPool<T> {
053 // TODO: Use bits, the state byte array could be a bit array.
054 // The Cern code has to use bytes because they also support
055 // a REMOVE (== 2) state value but for the ObjectPool we only
056 // have FREE or FULL so the use of bits is possible; the
057 // state byte array could be a bit vector which would save
058 // some memory.
059 protected static final byte FREE = 0;
060 protected static final byte FULL = 1;
061
062 protected static final int DEFAULT_CAPACITY = 277;
063 protected static final double DEFAULT_MIN_LOAD_FACTOR = 0.2;
064 protected static final double DEFAULT_MAX_LOAD_FACTOR = 0.5;
065
066
067 /**
068 * The number of distinct associations in the map; its "size()".
069 */
070 protected int distinct;
071
072 protected int highWaterMark;
073
074 /**
075 * The minimum load factor for the hashtable.
076 */
077 protected double minLoadFactor;
078
079 /**
080 * The maximum load factor for the hashtable.
081 */
082 protected double maxLoadFactor;
083
084 protected T[] values;
085
086 /**
087 * The number of table entries in state==FREE.
088 */
089 protected int freeEntries;
090
091 public ObjectPool() {
092 this(DEFAULT_CAPACITY);
093 }
094 public ObjectPool(int initialCapacity) {
095 this(initialCapacity, DEFAULT_MIN_LOAD_FACTOR, DEFAULT_MAX_LOAD_FACTOR);
096 }
097 public ObjectPool(int initialCapacity,
098 double minLoadFactor,
099 double maxLoadFactor) {
100 setUp(initialCapacity,minLoadFactor,maxLoadFactor);
101 }
102
103 /**
104 * Return the number of entries in the ObjectPool.
105 *
106 * @return number of entries.
107 */
108 public int size() {
109 return distinct;
110 }
111
112 /**
113 * Reduce the size of the internal arrays to a size just big
114 * enough to hold the current set of entries. Generally, this
115 * should only be called after all entries have been added.
116 * Calling this causes a new, smaller array to be allocated, the
117 * objects are copied to the new array and then the old array is
118 * free to be garbage collected; there is a small time when both
119 * arrays are in memory.
120 */
121 public void trimToSize() {
122 // * 1.2 because open addressing's performance
123 // exponentially degrades beyond that point
124 // so that even rehashing the table can take very long
125 int newCapacity = nextPrime((int)(1 + 1.2 * size()));
126 if (values.length > newCapacity) {
127 rehash(newCapacity);
128 }
129 }
130
131 /**
132 * Returns true it the Object is already in the ObjectPool and false
133 * otherwise.
134 *
135 * @param key Object to test if member already or not.
136 * @return true is already member
137 */
138 public boolean contains(T key) {
139 int i = indexOfInsertion(key);
140 return (i < 0);
141 }
142
143 /**
144 * Adds an object to the ObjectPool if it is not
145 * already in the pool or returns the object that is already in the
146 * pool that matches the object being added.
147 *
148 * @param key Object to add to pool
149 * @return Equivalent object, if it exists, otherwise key
150 */
151 public T add(T key) {
152 int i = indexOfInsertion(key);
153 if (i < 0) {
154 //already contained
155 i = -i -1;
156 return this.values[i];
157 }
158
159 if (this.distinct > this.highWaterMark) {
160 int newCapacity = chooseGrowCapacity(this.distinct + 1,
161 this.minLoadFactor,
162 this.maxLoadFactor);
163 rehash(newCapacity);
164 return add(key);
165 }
166
167 T v = this.values[i];
168 this.values[i] = key;
169
170 if (v == null) {
171 this.freeEntries--;
172 }
173 this.distinct++;
174
175 if (this.freeEntries < 1) {
176 //delta
177 int newCapacity = chooseGrowCapacity(this.distinct + 1,
178 this.minLoadFactor,
179 this.maxLoadFactor);
180 rehash(newCapacity);
181 }
182
183 return key;
184 }
185
186 /**
187 * Removes all objects from the pool but keeps the current size of
188 * the internal storage.
189 */
190 public void clear() {
191 values = (T[]) new Object[values.length];
192
193 this.distinct = 0;
194 this.freeEntries = values.length; // delta
195 trimToSize();
196 }
197
198 /**
199 * Returns an Iterator of this <code>ObjectPool</code>. The order of
200 * the Objects returned by the <code>Iterator</code> can not be
201 * counted on to be in the same order as they were inserted
202 * into the <code>ObjectPool</code>. The
203 * <code>Iterator</code> returned does not
204 * support the removal of <code>ObjectPool</code> members.
205 */
206 public Iterator<T> iterator() {
207 return new Itr();
208 }
209
210
211
212 protected int chooseGrowCapacity(int size, double minLoad, double maxLoad) {
213 return nextPrime(Math.max(size + 1,
214 (int) ((4 * size / (3 * minLoad + maxLoad)))));
215 }
216 protected final int chooseHighWaterMark(int capacity, double maxLoad) {
217 //makes sure there is always at least one FREE slot
218 return Math.min(capacity - 2, (int) (capacity * maxLoad));
219 }
220 protected final int chooseLowWaterMark(int capacity, double minLoad) {
221 return (int) (capacity * minLoad);
222 }
223 /*
224 protected int chooseMeanCapacity(int size, double minLoad, double maxLoad) {
225 return nextPrime(Math.max(size + 1, (int) ((2*size/(minLoad+maxLoad)))));
226 }
227 protected int chooseShrinkCapacity(int size, double minLoad, double maxLoad) {
228 return nextPrime(Math.max(size + 1, (int) ((4*size/(minLoad+3*maxLoad)))));
229 }
230 */
231
232 protected int nextPrime(int desiredCapacity) {
233 return PrimeFinder.nextPrime(desiredCapacity);
234 }
235
236 protected void setUp(int initialCapacity,
237 double minLoadFactor,
238 double maxLoadFactor) {
239 int capacity = initialCapacity;
240
241 if (initialCapacity < 0) {
242 throw new IllegalArgumentException(
243 "Initial Capacity must not be less than zero: "+
244 initialCapacity);
245 }
246 if (minLoadFactor < 0.0 || minLoadFactor >= 1.0) {
247 throw new IllegalArgumentException(
248 "Illegal minLoadFactor: " + minLoadFactor);
249 }
250 if (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) {
251 throw new IllegalArgumentException(
252 "Illegal maxLoadFactor: " + maxLoadFactor);
253 }
254 if (minLoadFactor >= maxLoadFactor) {
255 throw new IllegalArgumentException(
256 "Illegal minLoadFactor: " + minLoadFactor +
257 " and maxLoadFactor: " + maxLoadFactor);
258 }
259 capacity = nextPrime(capacity);
260
261 // open addressing needs at least one FREE slot at any time.
262 if (capacity == 0) {
263 capacity = 1;
264 }
265
266 //this.table = new long[capacity];
267 this.values = (T[]) new Object[capacity];
268 //this.state = new byte[capacity];
269
270 // memory will be exhausted long before this
271 // pathological case happens, anyway.
272 this.minLoadFactor = minLoadFactor;
273 if (capacity == PrimeFinder.largestPrime) {
274 this.maxLoadFactor = 1.0;
275 } else {
276 this.maxLoadFactor = maxLoadFactor;
277 }
278
279 this.distinct = 0;
280 this.freeEntries = capacity; // delta
281 this.highWaterMark = chooseHighWaterMark(capacity, this.maxLoadFactor);
282
283 }
284
285
286 protected int hash(T key) {
287 return (key == null) ? 0 : key.hashCode();
288 }
289 protected boolean equals(T t, T key) {
290 return (t != null) && t.equals(key);
291 }
292
293 protected int indexOfInsertion(T key) {
294 final T[] tab = values;
295 final int length = tab.length;
296
297 final int hash = key.hashCode() & 0x7FFFFFFF;
298 int i = hash % length;
299
300 // double hashing,
301 // see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
302 int decrement = hash % (length - 2);
303
304 //int decrement = (hash / length) % length;
305 if (decrement == 0) {
306 decrement = 1;
307 }
308
309 // stop if we find a free slot, or if we find the key itself
310 T v = tab[i];
311 while (v != null && !v.equals(key)) {
312 //hashCollisions++;
313 i -= decrement;
314 if (i < 0) {
315 i += length;
316 }
317 v = tab[i];
318 }
319
320 // key already contained at slot i.
321 // return a negative number identifying the slot.
322 // not already contained, should be inserted at slot i.
323 // return a number >= 0 identifying the slot.
324 return (v != null) ? -i - 1 : i;
325 }
326
327 protected void rehash(int newCapacity) {
328 int oldCapacity = values.length;
329
330 T[] oldValues = values;
331
332 T[] newValues = (T[]) new Object[newCapacity];
333
334 this.highWaterMark = chooseHighWaterMark(newCapacity,this.maxLoadFactor);
335
336 this.values = newValues;
337 this.freeEntries = newCapacity - this.distinct; // delta
338 for (int i = oldCapacity ; i-- > 0 ;) {
339 T v = oldValues[i];
340 if (v != null) {
341 int index = indexOfInsertion(v);
342 newValues[index] = v;
343 }
344 }
345 }
346
347 private class Itr implements Iterator<T> {
348 int index = 0;
349 Itr() {
350 }
351
352 public boolean hasNext() {
353 if (index == ObjectPool.this.values.length) {
354 return false;
355 }
356 while (ObjectPool.this.values[index] == null) {
357 index++;
358 if (index == ObjectPool.this.values.length) {
359 return false;
360 }
361 }
362 return (ObjectPool.this.values[index] != null);
363 }
364
365 public T next() {
366 if (index >= ObjectPool.this.values.length) {
367 throw new NoSuchElementException();
368 }
369 return ObjectPool.this.values[index++];
370 }
371
372 public void remove() {
373 throw new UnsupportedOperationException("ObjectPool.Itr.remove");
374 }
375 }
376 }
377
378 // End ObjectPool.java