001: /*
002: * Copyright 2004 Brian S O'Neill
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016:
017: package org.cojen.util;
018:
019: import java.lang.ref.Reference;
020: import java.lang.ref.ReferenceQueue;
021: import java.lang.ref.WeakReference;
022:
023: import java.util.AbstractSet;
024: import java.util.Iterator;
025: import java.util.NoSuchElementException;
026:
027: /**
028: * A thread-safe Set that manages canonical objects: sharable objects that are
029: * typically immutable. Call the {@link #put put} method for supplying the
030: * WeakCanonicalSet with candidate canonical instances.
031: * <p>
032: * Objects that do not customize the hashCode and equals methods don't make
033: * sense to be canonicalized because each instance will be considered unique.
034: * The object returned from the {@link #put put} method will always be the same
035: * as the one passed in.
036: *
037: * @author Brian S O'Neill
038: */
039: public class WeakCanonicalSet extends AbstractSet {
040: private Entry[] table;
041: private int count;
042: private int threshold;
043: private final float loadFactor;
044: private final ReferenceQueue queue;
045:
046: public WeakCanonicalSet() {
047: final int initialCapacity = 101;
048: final float loadFactor = 0.75f;
049: this .loadFactor = loadFactor;
050: this .table = new Entry[initialCapacity];
051: this .threshold = (int) (initialCapacity * loadFactor);
052: this .queue = new ReferenceQueue();
053: }
054:
055: /**
056: * Pass in a candidate canonical object and get a unique instance from this
057: * set. The returned object will always be of the same type as that passed
058: * in. If the object passed in does not equal any object currently in the
059: * set, it will be added to the set, becoming canonical.
060: *
061: * @param obj candidate canonical object; null is also accepted
062: */
063: public synchronized Object put(Object obj) {
064: // This implementation is based on the WeakIdentityMap.put method.
065:
066: if (obj == null) {
067: return null;
068: }
069:
070: Entry[] tab = this .table;
071:
072: // Cleanup after cleared References.
073: {
074: ReferenceQueue queue = this .queue;
075: Reference ref;
076: while ((ref = queue.poll()) != null) {
077: // Since buckets are single-linked, traverse entire list and
078: // cleanup all cleared references in it.
079: int index = (((Entry) ref).hash & 0x7fffffff)
080: % tab.length;
081: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
082: if (e.get() == null) {
083: if (prev != null) {
084: prev.next = e.next;
085: } else {
086: tab[index] = e.next;
087: }
088: this .count--;
089: } else {
090: prev = e;
091: }
092: }
093: }
094: }
095:
096: int hash = hashCode(obj);
097: int index = (hash & 0x7fffffff) % tab.length;
098:
099: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
100: Object iobj = e.get();
101: if (iobj == null) {
102: // Clean up after a cleared Reference.
103: if (prev != null) {
104: prev.next = e.next;
105: } else {
106: tab[index] = e.next;
107: }
108: this .count--;
109: } else if (e.hash == hash
110: && obj.getClass() == iobj.getClass()
111: && equals(obj, iobj)) {
112: // Found canonical instance.
113: return iobj;
114: } else {
115: prev = e;
116: }
117: }
118:
119: if (this .count >= this .threshold) {
120: // Rehash the table if the threshold is exceeded.
121: rehash();
122: tab = this .table;
123: index = (hash & 0x7fffffff) % tab.length;
124: }
125:
126: // Create a new entry.
127: tab[index] = new Entry(obj, this .queue, hash, tab[index]);
128: this .count++;
129: return obj;
130: }
131:
132: public Iterator iterator() {
133: return new SetIterator();
134: }
135:
136: public int size() {
137: return this .count;
138: }
139:
140: public synchronized boolean contains(Object obj) {
141: if (obj == null) {
142: return false;
143: }
144:
145: Entry[] tab = this .table;
146: int hash = hashCode(obj);
147: int index = (hash & 0x7fffffff) % tab.length;
148:
149: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
150: Object iobj = e.get();
151: if (iobj == null) {
152: // Clean up after a cleared Reference.
153: if (prev != null) {
154: prev.next = e.next;
155: } else {
156: tab[index] = e.next;
157: }
158: this .count--;
159: } else if (e.hash == hash
160: && obj.getClass() == iobj.getClass()
161: && equals(obj, iobj)) {
162: // Found canonical instance.
163: return true;
164: } else {
165: prev = e;
166: }
167: }
168:
169: return false;
170: }
171:
172: public synchronized String toString() {
173: return WeakIdentityMap.toString(this );
174: }
175:
176: protected int hashCode(Object obj) {
177: return obj.hashCode();
178: }
179:
180: protected boolean equals(Object a, Object b) {
181: return a.equals(b);
182: }
183:
184: private void rehash() {
185: int oldCapacity = this .table.length;
186: Entry[] tab = this .table;
187:
188: int newCapacity = oldCapacity * 2 + 1;
189: Entry[] newTab = new Entry[newCapacity];
190:
191: this .threshold = (int) (newCapacity * this .loadFactor);
192: this .table = newTab;
193:
194: for (int i = oldCapacity; i-- > 0;) {
195: for (Entry old = tab[i]; old != null;) {
196: Entry e = old;
197: old = old.next;
198:
199: // Only copy entry if it hasn't been cleared.
200: if (e.get() == null) {
201: this .count--;
202: } else {
203: int index = (e.hash & 0x7fffffff) % newCapacity;
204: e.next = newTab[index];
205: newTab[index] = e;
206: }
207: }
208: }
209: }
210:
211: private static class Entry extends WeakReference {
212: int hash;
213: Entry next;
214:
215: Entry(Object canonical, ReferenceQueue queue, int hash,
216: Entry next) {
217: super (canonical, queue);
218: this .hash = hash;
219: this .next = next;
220: }
221: }
222:
223: private class SetIterator implements Iterator {
224: private final Entry[] table;
225:
226: private int index;
227:
228: // To ensure that the iterator doesn't return cleared entries, keep a
229: // hard reference to the canonical object. Its existence will prevent
230: // the weak reference from being cleared.
231: private Object entryCanonical;
232: private Entry entry;
233:
234: SetIterator() {
235: this .table = WeakCanonicalSet.this .table;
236: this .index = table.length;
237: }
238:
239: public boolean hasNext() {
240: while (this .entry == null
241: || (this .entryCanonical = this .entry.get()) == null) {
242: if (this .entry != null) {
243: // Skip past a cleared Reference.
244: this .entry = this .entry.next;
245: } else {
246: if (this .index <= 0) {
247: return false;
248: } else {
249: this .entry = this .table[--this .index];
250: }
251: }
252: }
253:
254: return true;
255: }
256:
257: public Object next() {
258: if (!hasNext()) {
259: throw new NoSuchElementException();
260: }
261:
262: this .entry = this .entry.next;
263: return this .entryCanonical;
264: }
265:
266: public void remove() {
267: throw new UnsupportedOperationException();
268: }
269: }
270: }
|