]> gerrit.simantics Code Review - simantics/platform.git/blob - bundles/org.simantics.scl.compiler/src/org/cojen/util/WeakCanonicalSet.java
Added another sampling method to HistorySampler
[simantics/platform.git] / bundles / org.simantics.scl.compiler / src / org / cojen / util / WeakCanonicalSet.java
1 /*
2  *  Copyright 2004-2010 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 import java.util.AbstractSet;
23 import java.util.Iterator;
24 import java.util.NoSuchElementException;
25
26 /**
27  * A thread-safe Set that manages canonical objects: sharable objects that are
28  * typically immutable. Call the {@link #put put} method for supplying the
29  * WeakCanonicalSet with candidate canonical instances.
30  * <p>
31  * Objects that do not customize the hashCode and equals methods don't make
32  * sense to be canonicalized because each instance will be considered unique.
33  * The object returned from the {@link #put put} method will always be the same
34  * as the one passed in.
35  *
36  * @author Brian S O'Neill
37  */
38 @SuppressWarnings({ "unchecked", "rawtypes" })
39 public class WeakCanonicalSet<T> extends AbstractSet<T> {
40     private Entry<T>[] table;
41     private int count;
42     private int threshold;
43     private final float loadFactor;
44     private final ReferenceQueue<T> 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<T>();
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 <U extends T> U put(U obj) {
64         // This implementation is based on the WeakIdentityMap.put method.
65
66         if (obj == null) {
67             return null;
68         }
69
70         Entry<T>[] 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<T> 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<T> e = tab[index], prev = null; e != null; e = e.next) {
99             T 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 (U) 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<T>(obj, this.queue, hash, tab[index]);
127         this.count++;
128         return obj;
129     }
130
131     public Iterator<T> 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<T>[] tab = this.table;
145         int hash = hashCode(obj);
146         int index = (hash & 0x7fffffff) % tab.length;
147
148         for (Entry<T> 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<T>[] tab = this.table;
186
187         int newCapacity = oldCapacity * 2 + 1;
188         Entry<T>[] 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<T> old = tab[i]; old != null; ) {
195                 Entry<T> 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<T> extends WeakReference<T> {
211         int hash;
212         Entry<T> next;
213
214         Entry(T canonical, ReferenceQueue<T> queue, int hash, Entry<T> next) {
215             super(canonical, queue);
216             this.hash = hash;
217             this.next = next;
218         }
219     }
220
221     private class SetIterator implements Iterator<T> {
222         private final Entry<T>[] 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 T entryCanonical;
230         private Entry<T> 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 T 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 }