001: package com.jofti.util;
002:
003: import java.util.AbstractSet;
004: import java.util.Collection;
005: import java.util.ConcurrentModificationException;
006: import java.util.HashMap;
007: import java.util.Iterator;
008: import java.util.LinkedHashMap;
009: import java.util.LinkedHashSet;
010: import java.util.Map;
011: import java.util.NoSuchElementException;
012:
013: import java.io.Serializable;
014: import java.lang.ref.SoftReference;
015:
016: /**
017: *
018: * This is a specific implementation of a Set (heavily based on the HashMap code) that provides for quicker and cached
019: * return of entries in the toArray method. </p>
020: * Once a call to the toArray has been made, the resulting Object[] is cached for future calls. </p>
021: *
022: * Any mutator method called on the set will clear the cached array. In addition, the cached array is held as a SoftReference so the
023: * Garbage Collector can clear the value if it needs to. </p>
024: * The degenerate behaviour without the cache is around 50% of the Hashset implementation.
025: *
026: * @author swoodcock
027: *
028: */
029: public class FastSet extends AbstractSet implements Cloneable,
030: Serializable {
031: transient SoftReference lookupArray = null;
032:
033: /**
034: * The default initial capacity - MUST be a power of two.
035: */
036: static final int DEFAULT_INITIAL_CAPACITY = 2;
037:
038: /**
039: * The maximum capacity, used if a higher value is implicitly specified
040: * by either of the constructors with arguments.
041: * MUST be a power of two <= 1<<30.
042: */
043: static final int MAXIMUM_CAPACITY = 1 << 30;
044:
045: /**
046: * The load factor used when none specified in constructor.
047: **/
048: static final float DEFAULT_LOAD_FACTOR = 0.75f;
049:
050: /**
051: * The table, resized as necessary. Length MUST Always be a power of two.
052: */
053: transient Entry[] table;
054:
055: /**
056: * The number of key-value mappings contained in this identity hash map.
057: */
058: transient int size;
059:
060: /**
061: * The next size value at which to resize (capacity * load factor).
062: * @serial
063: */
064: int threshold;
065:
066: /**
067: * The load factor for the hash table.
068: *
069: * @serial
070: */
071: float loadFactor;
072:
073: /**
074: * The number of times this HashMap has been structurally modified
075: * Structural modifications are those that change the number of mappings in
076: * the HashMap or otherwise modify its internal structure (e.g.,
077: * rehash). This field is used to make iterators on Collection-views of
078: * the HashMap fail-fast. (See ConcurrentModificationException).
079: */
080: transient volatile int modCount;
081:
082: /**
083: * Constructs an empty <tt>HashMap</tt> with the default initial
084: * capacity and the default load factor (0.75).
085: *
086: * @throws IllegalArgumentException if the initial capacity is negative.
087: */
088: public FastSet() {
089: this .loadFactor = DEFAULT_LOAD_FACTOR;
090: threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
091: table = new Entry[DEFAULT_INITIAL_CAPACITY];
092: }
093:
094: /**
095: * Value representing null keys inside tables.
096: */
097: static final Object NULL_KEY = new Object();
098:
099: static Object maskNull(Object key) {
100: return (key == null ? NULL_KEY : key);
101: }
102:
103: /**
104: * Returns key represented by specified internal representation.
105: */
106: static Object unmaskNull(Object key) {
107: return (key == NULL_KEY ? null : key);
108: }
109:
110: static class Entry {
111: Object value;
112: final int hash;
113: Entry next;
114:
115: /**
116: * Create new entry.
117: */
118: Entry(int h, Object k, Entry n) {
119: next = n;
120: value = k;
121: hash = h;
122: }
123:
124: public Object getValue() {
125: return unmaskNull(value);
126: }
127:
128: public Object setValue(Object newValue) {
129: Object oldValue = value;
130: value = newValue;
131: return oldValue;
132: }
133:
134: public boolean equals(Object o) {
135: if (!(o instanceof Map.Entry))
136: return false;
137: Entry e = (Entry) o;
138: Object k1 = value;
139: Object k2 = e.value;
140: if (k1 == k2 || (k1 != null && k1.equals(k2))) {
141: return true;
142: }
143: return false;
144: }
145:
146: public int hashCode() {
147: return (value == NULL_KEY ? 0 : value.hashCode());
148: }
149:
150: public String toString() {
151: return getValue().toString();
152: }
153:
154: /**
155: * This method is invoked whenever the value in an entry is
156: * overwritten by an invocation of put(k,v) for a key k that's already
157: * in the HashMap.
158: */
159: void recordAccess(HashMap m) {
160: }
161:
162: /**
163: * This method is invoked whenever the entry is
164: * removed from the table.
165: */
166: void recordRemoval(HashMap m) {
167: }
168: }
169:
170: public Iterator iterator() {
171: return new KeyIterator();
172: }
173:
174: public int size() {
175: return size;
176: }
177:
178: public boolean isEmpty() {
179: return size == 0;
180: }
181:
182: static int hash(Object x) {
183: int h = x.hashCode();
184:
185: h += ~(h << 9);
186: h ^= (h >>> 14);
187: h += (h << 4);
188: h ^= (h >>> 10);
189: return h;
190: }
191:
192: /**
193: * Check for equality of non-null reference x and possibly-null y.
194: */
195: static boolean eq(Object x, Object y) {
196: return x == y || x.equals(y);
197: }
198:
199: /**
200: * Returns index for hash code h.
201: */
202: static int indexFor(int h, int length) {
203: return h & (length - 1);
204: }
205:
206: public boolean contains(Object o) {
207:
208: Object k = maskNull(o);
209: int hash = hash(k);
210: int i = indexFor(hash, table.length);
211: Entry e = table[i];
212: while (e != null) {
213: if (e.hash == hash && eq(k, e.value))
214: return true;
215: e = e.next;
216: }
217: return false;
218: }
219:
220: private void clearCache() {
221: lookupArray = new SoftReference(null);
222:
223: }
224:
225: public boolean add(Object o) {
226: // set toArray cache to be null
227: clearCache();
228:
229: Object k = maskNull(o);
230: int hash = hash(k);
231: int i = indexFor(hash, table.length);
232:
233: for (Entry e = table[i]; e != null; e = e.next) {
234: if (e.hash == hash && eq(k, e.value)) {
235: Object oldValue = e.value;
236: e.value = k;
237:
238: return oldValue == null;
239: }
240: }
241:
242: modCount++;
243: addEntry(hash, k, i);
244: return false;
245:
246: }
247:
248: public boolean remove(Object o) {
249:
250: Entry e = removeEntryForKey(o);
251: return (e == null ? false : true);
252: }
253:
254: /**
255: * Removes and returns the entry associated with the specified key
256: * in the HashMap. Returns null if the HashMap contains no mapping
257: * for this key.
258: */
259: Entry removeEntryForKey(Object value) {
260: Object k = maskNull(value);
261: int hash = hash(k);
262: int i = indexFor(hash, table.length);
263: Entry prev = table[i];
264: Entry e = prev;
265:
266: while (e != null) {
267: Entry next = e.next;
268: if (e.hash == hash && eq(k, e.value)) {
269: modCount++;
270: size--;
271: if (prev == e)
272: table[i] = next;
273: else
274: prev.next = next;
275: return e;
276: }
277: prev = e;
278: e = next;
279: }
280: if (e != null) {
281: clearCache();
282: }
283: return e;
284: }
285:
286: public void clear() {
287: // set toArray cache to be null
288: clearCache();
289: modCount++;
290: Entry tab[] = table;
291: for (int i = 0; i < tab.length; i++)
292: tab[i] = null;
293: size = 0;
294: }
295:
296: public boolean removeAll(Collection c) {
297: boolean modified = false;
298: clearCache();
299: if (size() > c.size()) {
300: for (Iterator i = c.iterator(); i.hasNext();)
301: modified |= remove(i.next());
302: } else {
303: for (Iterator i = iterator(); i.hasNext();) {
304: if (c.contains(i.next())) {
305: i.remove();
306: modified = true;
307: }
308: }
309: }
310: return modified;
311:
312: }
313:
314: /**
315: * Add a new entry with the specified key, value and hash code to
316: * the specified bucket. It is the responsibility of this
317: * method to resize the table if appropriate.
318: *
319: * Subclass overrides this to alter the behavior of put method.
320: */
321: void addEntry(int hash, Object value, int bucketIndex) {
322: table[bucketIndex] = new Entry(hash, value, table[bucketIndex]);
323: if (size++ >= threshold)
324: resize(2 * table.length);
325: }
326:
327: void resize(int newCapacity) {
328: Entry[] oldTable = table;
329: int oldCapacity = oldTable.length;
330: if (oldCapacity == MAXIMUM_CAPACITY) {
331: threshold = Integer.MAX_VALUE;
332: return;
333: }
334:
335: Entry[] newTable = new Entry[newCapacity];
336: transfer(newTable);
337: table = newTable;
338: threshold = (int) (newCapacity * loadFactor);
339: }
340:
341: /**
342: * Transfer all entries from current table to newTable.
343: */
344: void transfer(Entry[] newTable) {
345: Entry[] src = table;
346: int newCapacity = newTable.length;
347: for (int j = 0; j < src.length; j++) {
348: Entry e = src[j];
349: if (e != null) {
350: src[j] = null;
351: do {
352: Entry next = e.next;
353: int i = indexFor(e.hash, newCapacity);
354: e.next = newTable[i];
355: newTable[i] = e;
356: e = next;
357: } while (e != null);
358: }
359: }
360: }
361:
362: public Object[] toArray() {
363: Object[] result = null;
364: if (lookupArray != null) {
365: result = (Object[]) lookupArray.get();
366: }
367:
368: if (result == null) {
369: result = new Object[size];
370: int resultCounter = 0;
371: Entry n = null;
372: int length = table.length - 1;
373: for (int i = length; i >= 0; i--) {
374: n = table[i];
375: while (n != null) {
376: result[resultCounter++] = n.value;
377: n = n.next;
378: }
379:
380: }
381: lookupArray = new SoftReference(result);
382: }
383: return result;
384: }
385:
386: public boolean containsAll(Collection c) {
387: Iterator e = c.iterator();
388: while (e.hasNext())
389: if (!contains(e.next()))
390: return false;
391:
392: return true;
393: }
394:
395: private class KeyIterator extends HashIterator {
396: public Object next() {
397: return nextEntry().getValue();
398: }
399: }
400:
401: private abstract class HashIterator implements Iterator {
402: Entry next; // next entry to return
403: int expectedModCount; // For fast-fail
404: int index; // current slot
405: Entry current; // current entry
406:
407: HashIterator() {
408: expectedModCount = modCount;
409: Entry[] t = table;
410: if (t == null) {
411:
412: }
413: int i = t.length;
414: Entry n = null;
415: if (size != 0) { // advance to first entry
416: while (i > 0 && (n = t[--i]) == null)
417: ;
418: }
419: next = n;
420: index = i;
421: }
422:
423: public boolean hasNext() {
424: return next != null;
425: }
426:
427: Entry nextEntry() {
428: if (modCount != expectedModCount)
429: throw new ConcurrentModificationException();
430: Entry e = next;
431: if (e == null)
432: throw new NoSuchElementException();
433:
434: Entry n = e.next;
435: Entry[] t = table;
436: int i = index;
437: while (n == null && i > 0)
438: n = t[--i];
439: index = i;
440: next = n;
441: return current = e;
442: }
443:
444: public void remove() {
445:
446: if (current == null)
447: throw new IllegalStateException();
448: if (modCount != expectedModCount)
449: throw new ConcurrentModificationException();
450: // set toArray cache to be null
451: clearCache();
452: Object k = current.value;
453: current = null;
454: removeEntryForKey(k);
455: expectedModCount = modCount;
456: }
457:
458: }
459:
460: private void writeObject(java.io.ObjectOutputStream s)
461: throws java.io.IOException {
462: // Write out any hidden serialization magic
463: s.defaultWriteObject();
464:
465: // Write out HashMap capacity and load factor
466: s.writeFloat(loadFactor);
467:
468: // Write out size
469: s.writeInt(size);
470:
471: // Write out all elements in the proper order.
472: for (Iterator i = new KeyIterator(); i.hasNext();)
473: s.writeObject(i.next());
474: }
475:
476: /**
477: * Reconstitute the <tt>HashSet</tt> instance from a stream (that is,
478: * deserialize it).
479: */
480: private void readObject(java.io.ObjectInputStream s)
481: throws java.io.IOException, ClassNotFoundException {
482: // Read in any hidden serialization magic
483: s.defaultReadObject();
484:
485: // Read in HashMap capacity and load factor and create backing HashMap
486: float loadFactor = s.readFloat();
487:
488: this .loadFactor = DEFAULT_LOAD_FACTOR;
489: threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
490: table = new Entry[DEFAULT_INITIAL_CAPACITY];
491:
492: // Read in size
493: int size = s.readInt();
494:
495: // Read in all elements in the proper order.
496: for (int i = 0; i < size; i++) {
497: Object e = s.readObject();
498: add(e);
499: }
500: }
501:
502: }
|