Mercurial > hg > blitz_stable

comparison src/com/go/trove/util/FlyweightSet.java @ 0:3dc0c5604566

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
-1:000000000000 0:3dc0c5604566
1 /*
2 * FlyweightSet.java
3 *
4 * Copyright (c) 2000 Starwave Corporation. All Rights Reserved.
5 *
6 * Original author: Brian S O'Neill
7 *
8 * $Workfile:: FlyweightSet.java $
9 * $Author: dan $
10 * $Revision: 1.1 $
11 * $Date: Mon, 13 Oct 2003 12:20:39 +0100 $
12 */
13
14 package com.go.trove.util;
15
16 import java.lang.ref.*;
17 import java.util.*;
18
19 /******************************************************************************
20 * A thread-safe Set that manages flyweights: sharable objects that are usually
21 * immutable. Call the {@link #get get} method for supplying the FlyweightSet
22 * with candidate flyweight instances.
23 * <p>
24 * Objects that do not customize the hashCode and equals methods don't make
25 * sense to use as flyweights because each instance will be considered unique.
26 * The object returned from the {@link #get get} method will always be the same
27 * as the one passed in.
28 *
29 * @author Brian S O'Neill
30 * @version
31 * <!--$$Revision: 1.1 $-->, <!--$$JustDate:--> 00/12/18 <!-- $-->
32 * @see Utils#intern
33 */
34 public class FlyweightSet extends AbstractSet {
35 // This implementation is basically a stripped down version of
36 // IdentityMap in which the entries contain only a referenced key and
37 // no value.
38
39 private Entry mTable[];
40 private int mCount;
41 private int mThreshold;
42 private float mLoadFactor;
43
44 public FlyweightSet() {
45 final int initialCapacity = 101;
46 final float loadFactor = 0.75f;
47 mLoadFactor = loadFactor;
48 mTable = new Entry[initialCapacity];
49 mThreshold = (int)(initialCapacity * loadFactor);
50 }
51
52 /**
53 * Pass in a candidate flyweight object and get a unique instance from this
54 * set. The returned object will always be of the same type as that passed
55 * in. If the object passed in does not equal any object currently in the
56 * set, it will be added to the set, becoming a flyweight.
57 *
58 * @param obj candidate flyweight; null is also accepted
59 */
60 public synchronized Object put(Object obj) {
61 // This implementation is based on the IdentityMap.put method.
62
63 if (obj == null) {
64 return null;
65 }
66
67 Entry tab[] = mTable;
68 int hash = hashCode(obj);
69 int index = (hash & 0x7FFFFFFF) % tab.length;
70
71 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
72 Object iobj = e.get();
73 if (iobj == null) {
74 // Clean up after a cleared Reference.
75 if (prev != null) {
76 prev.mNext = e.mNext;
77 }
78 else {
79 tab[index] = e.mNext;
80 }
81 mCount--;
82 }
83 else if (e.mHash == hash &&
84 obj.getClass() == iobj.getClass() &&
85 equals(obj, iobj)) {
86 // Found flyweight instance.
87 return iobj;
88 }
89 else {
90 prev = e;
91 }
92 }
93
94 if (mCount >= mThreshold) {
95 // Cleanup the table if the threshold is exceeded.
96 cleanup();
97 }
98
99 if (mCount >= mThreshold) {
100 // Rehash the table if the threshold is still exceeded.
101 rehash();
102 tab = mTable;
103 index = (hash & 0x7FFFFFFF) % tab.length;
104 }
105
106 // Create a new entry.
107 tab[index] = new Entry(obj, hash, tab[index]);
108 mCount++;
109 return obj;
110 }
111
112 public Iterator iterator() {
113 return new SetIterator();
114 }
115
116 public int size() {
117 return mCount;
118 }
119
120 public boolean contains(Object obj) {
121 if (obj == null) {
122 return false;
123 }
124
125 Entry tab[] = mTable;
126 int hash = hashCode(obj);
127 int index = (hash & 0x7FFFFFFF) % tab.length;
128
129 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
130 Object iobj = e.get();
131 if (iobj == null) {
132 // Clean up after a cleared Reference.
133 if (prev != null) {
134 prev.mNext = e.mNext;
135 }
136 else {
137 tab[index] = e.mNext;
138 }
139 mCount--;
140 }
141 else if (e.mHash == hash &&
142 obj.getClass() == iobj.getClass() &&
143 equals(obj, iobj)) {
144 // Found flyweight instance.
145 return true;
146 }
147 else {
148 prev = e;
149 }
150 }
151
152 return false;
153 }
154
155 public String toString() {
156 return IdentityMap.toString(this);
157 }
158
159 protected int hashCode(Object obj) {
160 return obj.hashCode();
161 }
162
163 protected boolean equals(Object a, Object b) {
164 return a.equals(b);
165 }
166
167 private void cleanup() {
168 Entry tab[] = mTable;
169 for (int i = tab.length; i-- > 0; ) {
170 for (Entry e = tab[i], prev = null; e != null; e = e.mNext) {
171 if (e.get() == null) {
172 // Clean up after a cleared Reference.
173 if (prev != null) {
174 prev.mNext = e.mNext;
175 }
176 else {
177 tab[i] = e.mNext;
178 }
179 mCount--;
180 }
181 else {
182 prev = e;
183 }
184 }
185 }
186 }
187
188 private void rehash() {
189 int oldCapacity = mTable.length;
190 Entry[] tab = mTable;
191
192 int newCapacity = oldCapacity * 2 + 1;
193 Entry[] newTab = new Entry[newCapacity];
194
195 mThreshold = (int)(newCapacity * mLoadFactor);
196 mTable = newTab;
197
198 for (int i = oldCapacity; i-- > 0; ) {
199 for (Entry old = tab[i]; old != null; ) {
200 Entry e = old;
201 old = old.mNext;
202
203 // Only copy entry if it hasn't been cleared.
204 if (e.get() == null) {
205 mCount--;
206 }
207 else {
208 int index = (e.mHash & 0x7FFFFFFF) % newCapacity;
209 e.mNext = newTab[index];
210 newTab[index] = e;
211 }
212 }
213 }
214 }
215
216 private static class Entry extends WeakReference {
217 int mHash;
218 Entry mNext;
219
220 Entry(Object flyweight, int hash, Entry next) {
221 super(flyweight);
222 mHash = hash;
223 mNext = next;
224 }
225 }
226
227 private class SetIterator implements Iterator {
228 private Entry[] mTable = FlyweightSet.this.mTable;
229 private int mIndex = mTable.length;
230 private Entry mEntry;
231 // To ensure that the iterator doesn't return cleared entries, keep a
232 // hard reference to the flyweight. Its existence will prevent the weak
233 // reference from being cleared.
234 private Object mEntryFlyweight;
235 private Entry mLastReturned;
236
237 public boolean hasNext() {
238 while (mEntry == null ||
239 (mEntryFlyweight = mEntry.get()) == null) {
240 if (mEntry != null) {
241 // Skip past a cleared Reference.
242 mEntry = mEntry.mNext;
243 }
244 else {
245 if (mIndex <= 0) {
246 return false;
247 }
248 else {
249 mEntry = mTable[--mIndex];
250 }
251 }
252 }
253
254 return true;
255 }
256
257 public Object next() {
258 if (!hasNext()) {
259 throw new NoSuchElementException();
260 }
261
262 mEntry = mEntry.mNext;
263 return mEntryFlyweight;
264 }
265
266 public void remove() {
267 throw new UnsupportedOperationException();
268 }
269 }
270 }