KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > go > trove > util > FlyweightSet


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:: Briano $
10  * $Revision:: 1 $
11  * $Date:: 00/12/18 10:29a $
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 <!-- $-->, <!--$$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 JavaDoc put(Object JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc toString() {
156         return IdentityMap.toString(this);
157     }
158
159     protected int hashCode(Object JavaDoc obj) {
160         return obj.hashCode();
161     }
162
163     protected boolean equals(Object JavaDoc a, Object JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc();
268         }
269     }
270 }
271
Popular Tags