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 }