Mercurial > hg > blitz_condensed
diff src/com/go/trove/util/FlyweightSet.java @ 0:3dc0c5604566
Initial checkin of blitz 2.0 fcs - no installer yet.
author | Dan Creswell <dan.creswell@gmail.com> |
---|---|
date | Sat, 21 Mar 2009 11:00:06 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/com/go/trove/util/FlyweightSet.java Sat Mar 21 11:00:06 2009 +0000 @@ -0,0 +1,270 @@ +/* + * FlyweightSet.java + * + * Copyright (c) 2000 Starwave Corporation. All Rights Reserved. + * + * Original author: Brian S O'Neill + * + * $Workfile:: FlyweightSet.java $ + * $Author: dan $ + * $Revision: 1.1 $ + * $Date: Mon, 13 Oct 2003 12:20:39 +0100 $ + */ + +package com.go.trove.util; + +import java.lang.ref.*; +import java.util.*; + +/****************************************************************************** + * A thread-safe Set that manages flyweights: sharable objects that are usually + * immutable. Call the {@link #get get} method for supplying the FlyweightSet + * with candidate flyweight instances. + * <p> + * Objects that do not customize the hashCode and equals methods don't make + * sense to use as flyweights because each instance will be considered unique. + * The object returned from the {@link #get get} method will always be the same + * as the one passed in. + * + * @author Brian S O'Neill + * @version + * <!--$$Revision: 1.1 $-->, <!--$$JustDate:--> 00/12/18 <!-- $--> + * @see Utils#intern + */ +public class FlyweightSet extends AbstractSet { + // This implementation is basically a stripped down version of + // IdentityMap in which the entries contain only a referenced key and + // no value. + + private Entry mTable[]; + private int mCount; + private int mThreshold; + private float mLoadFactor; + + public FlyweightSet() { + final int initialCapacity = 101; + final float loadFactor = 0.75f; + mLoadFactor = loadFactor; + mTable = new Entry[initialCapacity]; + mThreshold = (int)(initialCapacity * loadFactor); + } + + /** + * Pass in a candidate flyweight object and get a unique instance from this + * set. The returned object will always be of the same type as that passed + * in. If the object passed in does not equal any object currently in the + * set, it will be added to the set, becoming a flyweight. + * + * @param obj candidate flyweight; null is also accepted + */ + public synchronized Object put(Object obj) { + // This implementation is based on the IdentityMap.put method. + + if (obj == null) { + return null; + } + + Entry tab[] = mTable; + int hash = hashCode(obj); + int index = (hash & 0x7FFFFFFF) % tab.length; + + for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { + Object iobj = e.get(); + if (iobj == null) { + // Clean up after a cleared Reference. + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[index] = e.mNext; + } + mCount--; + } + else if (e.mHash == hash && + obj.getClass() == iobj.getClass() && + equals(obj, iobj)) { + // Found flyweight instance. + return iobj; + } + else { + prev = e; + } + } + + if (mCount >= mThreshold) { + // Cleanup the table if the threshold is exceeded. + cleanup(); + } + + if (mCount >= mThreshold) { + // Rehash the table if the threshold is still exceeded. + rehash(); + tab = mTable; + index = (hash & 0x7FFFFFFF) % tab.length; + } + + // Create a new entry. + tab[index] = new Entry(obj, hash, tab[index]); + mCount++; + return obj; + } + + public Iterator iterator() { + return new SetIterator(); + } + + public int size() { + return mCount; + } + + public boolean contains(Object obj) { + if (obj == null) { + return false; + } + + Entry tab[] = mTable; + int hash = hashCode(obj); + int index = (hash & 0x7FFFFFFF) % tab.length; + + for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { + Object iobj = e.get(); + if (iobj == null) { + // Clean up after a cleared Reference. + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[index] = e.mNext; + } + mCount--; + } + else if (e.mHash == hash && + obj.getClass() == iobj.getClass() && + equals(obj, iobj)) { + // Found flyweight instance. + return true; + } + else { + prev = e; + } + } + + return false; + } + + public String toString() { + return IdentityMap.toString(this); + } + + protected int hashCode(Object obj) { + return obj.hashCode(); + } + + protected boolean equals(Object a, Object b) { + return a.equals(b); + } + + private void cleanup() { + Entry tab[] = mTable; + for (int i = tab.length; i-- > 0; ) { + for (Entry e = tab[i], prev = null; e != null; e = e.mNext) { + if (e.get() == null) { + // Clean up after a cleared Reference. + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[i] = e.mNext; + } + mCount--; + } + else { + prev = e; + } + } + } + } + + private void rehash() { + int oldCapacity = mTable.length; + Entry[] tab = mTable; + + int newCapacity = oldCapacity * 2 + 1; + Entry[] newTab = new Entry[newCapacity]; + + mThreshold = (int)(newCapacity * mLoadFactor); + mTable = newTab; + + for (int i = oldCapacity; i-- > 0; ) { + for (Entry old = tab[i]; old != null; ) { + Entry e = old; + old = old.mNext; + + // Only copy entry if it hasn't been cleared. + if (e.get() == null) { + mCount--; + } + else { + int index = (e.mHash & 0x7FFFFFFF) % newCapacity; + e.mNext = newTab[index]; + newTab[index] = e; + } + } + } + } + + private static class Entry extends WeakReference { + int mHash; + Entry mNext; + + Entry(Object flyweight, int hash, Entry next) { + super(flyweight); + mHash = hash; + mNext = next; + } + } + + private class SetIterator implements Iterator { + private Entry[] mTable = FlyweightSet.this.mTable; + private int mIndex = mTable.length; + private Entry mEntry; + // To ensure that the iterator doesn't return cleared entries, keep a + // hard reference to the flyweight. Its existence will prevent the weak + // reference from being cleared. + private Object mEntryFlyweight; + private Entry mLastReturned; + + public boolean hasNext() { + while (mEntry == null || + (mEntryFlyweight = mEntry.get()) == null) { + if (mEntry != null) { + // Skip past a cleared Reference. + mEntry = mEntry.mNext; + } + else { + if (mIndex <= 0) { + return false; + } + else { + mEntry = mTable[--mIndex]; + } + } + } + + return true; + } + + public Object next() { + if (!hasNext()) { + throw new NoSuchElementException(); + } + + mEntry = mEntry.mNext; + return mEntryFlyweight; + } + + public void remove() { + throw new UnsupportedOperationException(); + } + } +}