WeakCanonicalSet


1   /*
2    *  Copyright 2004 Brian S O'Neill
3    *
4    *  Licensed under the Apache License, Version 2.0 (the "License");
5    *  you may not use this file except in compliance with the License.
6    *  You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *  Unless required by applicable law or agreed to in writing, software
11   *  distributed under the License is distributed on an "AS IS" BASIS,
12   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *  See the License for the specific language governing permissions and
14   *  limitations under the License.
15   */
16  
17  package org.cojen.util;
18  
19  import java.lang.ref.Reference  ;
20  import java.lang.ref.ReferenceQueue  ;
21  import java.lang.ref.WeakReference  ;
22  
23  import java.util.AbstractSet  ;
24  import java.util.Iterator  ;
25  import java.util.NoSuchElementException  ;
26  
27  /**
28   * A thread-safe Set that manages canonical objects: sharable objects that are
29   * typically immutable. Call the {@link #put put} method for supplying the
30   * WeakCanonicalSet with candidate canonical instances.
31   * <p>
32   * Objects that do not customize the hashCode and equals methods don't make
33   * sense to be canonicalized because each instance will be considered unique.
34   * The object returned from the {@link #put put} method will always be the same
35   * as the one passed in.
36   *
37   * @author Brian S O'Neill
38   */
39  public class WeakCanonicalSet extends AbstractSet   {
40      private Entry[] table;
41      private int count;
42      private int threshold;
43      private final float loadFactor;
44      private final ReferenceQueue   queue;
45  
46      public WeakCanonicalSet() {
47          final int initialCapacity = 101;
48          final float loadFactor = 0.75f;
49          this.loadFactor = loadFactor;
50          this.table = new Entry[initialCapacity];
51          this.threshold = (int)(initialCapacity * loadFactor);
52          this.queue = new ReferenceQueue  ();
53      }
54  
55      /**
56       * Pass in a candidate canonical object and get a unique instance from this
57       * set. The returned object will always be of the same type as that passed
58       * in. If the object passed in does not equal any object currently in the
59       * set, it will be added to the set, becoming canonical.
60       *
61       * @param obj candidate canonical object; null is also accepted
62       */
63      public synchronized Object   put(Object   obj) {
64          // This implementation is based on the WeakIdentityMap.put method.
65  
66          if (obj == null) {
67              return null;
68          }
69  
70          Entry[] tab = this.table;
71  
72          // Cleanup after cleared References.
73          {
74              ReferenceQueue   queue = this.queue;
75              Reference   ref;
76              while ((ref = queue.poll()) != null) {
77                  // Since buckets are single-linked, traverse entire list and
78                  // cleanup all cleared references in it.
79                  int index = (((Entry) ref).hash & 0x7fffffff) % tab.length;
80                  for (Entry e = tab[index], prev = null; e != null; e = e.next) {
81                      if (e.get() == null) {
82                          if (prev != null) {
83                              prev.next = e.next;
84                          } else {
85                              tab[index] = e.next;
86                          }
87                          this.count--;
88                      } else {
89                          prev = e;
90                      }
91                  }
92              }
93          }
94  
95          int hash = hashCode(obj);
96          int index = (hash & 0x7fffffff) % tab.length;
97  
98          for (Entry e = tab[index], prev = null; e != null; e = e.next) {
99              Object   iobj = e.get();
100             if (iobj == null) {
101                 // Clean up after a cleared Reference.
102                 if (prev != null) {
103                     prev.next = e.next;
104                 } else {
105                     tab[index] = e.next;
106                 }
107                 this.count--;
108             } else if (e.hash == hash &&
109                        obj.getClass() == iobj.getClass() &&
110                        equals(obj, iobj)) {
111                 // Found canonical instance.
112                 return iobj;
113             } else {
114                 prev = e;
115             }
116         }
117 
118         if (this.count >= this.threshold) {
119             // Rehash the table if the threshold is exceeded.
120             rehash();
121             tab = this.table;
122             index = (hash & 0x7fffffff) % tab.length;
123         }
124 
125         // Create a new entry.
126         tab[index] = new Entry(obj, this.queue, hash, tab[index]);
127         this.count++;
128         return obj;
129     }
130 
131     public Iterator   iterator() {
132         return new SetIterator();
133     }
134 
135     public int size() {
136         return this.count;
137     }
138 
139     public synchronized boolean contains(Object   obj) {
140         if (obj == null) {
141             return false;
142         }
143 
144         Entry[] tab = this.table;
145         int hash = hashCode(obj);
146         int index = (hash & 0x7fffffff) % tab.length;
147 
148         for (Entry e = tab[index], prev = null; e != null; e = e.next) {
149             Object   iobj = e.get();
150             if (iobj == null) {
151                 // Clean up after a cleared Reference.
152                 if (prev != null) {
153                     prev.next = e.next;
154                 } else {
155                     tab[index] = e.next;
156                 }
157                 this.count--;
158             } else if (e.hash == hash &&
159                      obj.getClass() == iobj.getClass() &&
160                      equals(obj, iobj)) {
161                 // Found canonical instance.
162                 return true;
163             } else {
164                 prev = e;
165             }
166         }
167 
168         return false;
169     }
170 
171     public synchronized String   toString() {
172         return WeakIdentityMap.toString(this);
173     }
174 
175     protected int hashCode(Object   obj) {
176         return obj.hashCode();
177     }
178 
179     protected boolean equals(Object   a, Object   b) {
180         return a.equals(b);
181     }
182 
183     private void rehash() {
184         int oldCapacity = this.table.length;
185         Entry[] tab = this.table;
186 
187         int newCapacity = oldCapacity * 2 + 1;
188         Entry[] newTab = new Entry[newCapacity];
189 
190         this.threshold = (int)(newCapacity * this.loadFactor);
191         this.table = newTab;
192 
193         for (int i = oldCapacity; i-- > 0; ) {
194             for (Entry old = tab[i]; old != null; ) {
195                 Entry e = old;
196                 old = old.next;
197 
198                 // Only copy entry if it hasn't been cleared.
199                 if (e.get() == null) {
200                     this.count--;
201                 } else {
202                     int index = (e.hash & 0x7fffffff) % newCapacity;
203                     e.next = newTab[index];
204                     newTab[index] = e;
205                 }
206             }
207         }
208     }
209 
210     private static class Entry extends WeakReference   {
211         int hash;
212         Entry next;
213 
214         Entry(Object   canonical, ReferenceQueue   queue, int hash, Entry next) {
215             super(canonical, queue);
216             this.hash = hash;
217             this.next = next;
218         }
219     }
220 
221     private class SetIterator implements Iterator   {
222         private final Entry[] table;
223 
224         private int index;
225 
226         // To ensure that the iterator doesn't return cleared entries, keep a
227         // hard reference to the canonical object. Its existence will prevent
228         // the weak reference from being cleared.
229         private Object   entryCanonical;
230         private Entry entry;
231 
232         SetIterator() {
233             this.table = WeakCanonicalSet.this.table;
234             this.index = table.length;
235         }
236 
237         public boolean hasNext() {
238             while (this.entry == null || (this.entryCanonical = this.entry.get()) == null) {
239                 if (this.entry != null) {
240                     // Skip past a cleared Reference.
241                     this.entry = this.entry.next;
242                 } else {
243                     if (this.index <= 0) {
244                         return false;
245                     } else {
246                         this.entry = this.table[--this.index];
247                     }
248                 }
249             }
250 
251             return true;
252         }
253 
254         public Object   next() {
255             if (!hasNext()) {
256                 throw new NoSuchElementException  ();
257             }
258 
259             this.entry = this.entry.next;
260             return this.entryCanonical;
261         }
262 
263         public void remove() {
264             throw new UnsupportedOperationException  ();
265         }
266     }
267 }
268
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags