Mercurial > hg > blitz_stable
comparison 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 |
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 } |