bundles/org.simantics.scl.compiler/src/org/cojen/util/WeakIdentityMap.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.AbstractCollection;
  23 import java.util.AbstractMap;
  24 import java.util.AbstractSet;
  25 import java.util.Collection;
  26 import java.util.Collections;
  27 import java.util.ConcurrentModificationException;
  28 import java.util.Iterator;
  29 import java.util.Map;
  30 import java.util.NoSuchElementException;
  31 import java.util.Set;
  32
  33 /**
  34  * WeakIdentityMap is like WeakHashMap, except it uses a key's identity
  35  * hashcode and equals methods. WeakIdentityMap is not thread-safe and must be
  36  * wrapped with Collections.synchronizedMap to be made thread-safe.
  37  * <p>
  38  * The documentation for WeakHashMap states that it is intended primarily for
  39  * use with key objects whose equals methods test for object identity using the
  40  * == operator. Because WeakIdentityMap strictly follows this behavior, it is
  41  * better suited for this purpose.
  42  * <p>
  43  * Note: Weakly referenced entries may be automatically removed during
  44  * either accessor or mutator operations, possibly causing a concurrent
  45  * modification to be detected. Therefore, even if multiple threads are only
  46  * accessing this map, be sure to synchronize this map first. Also, do not
  47  * rely on the value returned by size() when using an iterator from this map.
  48  * The iterators may return less entries than the amount reported by size().
  49  *
  50  * @author Brian S O'Neill
  51  */
  52 @SuppressWarnings({ "unchecked", "rawtypes" })
  53 public class WeakIdentityMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable {
  54
  55     // Types of Iterators
  56     static final int KEYS = 0;
  57     static final int VALUES = 1;
  58     static final int ENTRIES = 2;
  59
  60     /**
  61      * Converts a collection to string, supporting collections that contain
  62      * self references
  63      */
  64     static String toString(Collection c) {
  65         if (c.size() == 0) {
  66             return "[]";
  67         }
  68         StringBuffer buf = new StringBuffer(32 * c.size());
  69         buf.append('[');
  70
  71         Iterator it = c.iterator();
  72         boolean hasNext = it.hasNext();
  73         while (hasNext) {
  74             Object obj = it.next();
  75             buf.append(obj == c ? "(this Collection)" : obj);
  76             if (hasNext = it.hasNext()) {
  77                 buf.append(", ");
  78             }
  79         }
  80         buf.append("]");
  81         return buf.toString();
  82     }
  83
  84     /**
  85      * Converts a map to string, supporting maps that contain self references
  86      */
  87     static String toString(Map m) {
  88         if (m.size() == 0) {
  89             return "{}";
  90         }
  91         StringBuffer buf = new StringBuffer(32 * m.size());
  92         buf.append('{');
  93
  94         Iterator it = m.entrySet().iterator();
  95         boolean hasNext = it.hasNext();
  96         while (hasNext) {
  97             Map.Entry entry = (Map.Entry)it.next();
  98             Object key = entry.getKey();
  99             Object value = entry.getValue();
 100             buf.append(key == m ? "(this Map)" : key)
 101                .append('=')
 102                .append(value == m ? "(this Map)" : value);
 103
 104             hasNext = it.hasNext();
 105             if (hasNext) {
 106                 buf.append(',').append(' ');
 107             }
 108         }
 109
 110         buf.append('}');
 111         return buf.toString();
 112     }
 113
 114     private transient Entry<K, V>[] table;
 115     private transient int count;
 116     private int threshold;
 117     private final float loadFactor;
 118     private final ReferenceQueue<K> queue;
 119     private transient volatile int modCount;
 120
 121     // Views
 122
 123     private transient Set<K> keySet;
 124     private transient Set<Map.Entry<K, V>> entrySet;
 125     private transient Collection<V> values;
 126
 127     public WeakIdentityMap(int initialCapacity, float loadFactor) {
 128         if (initialCapacity <= 0) {
 129             throw new IllegalArgumentException("Initial capacity must be greater than 0");
 130         }
 131         if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
 132             throw new IllegalArgumentException("Load factor must be greater than 0");
 133         }
 134         this.loadFactor = loadFactor;
 135         this.table = new Entry[initialCapacity];
 136         this.threshold = (int)(initialCapacity * loadFactor);
 137         this.queue = new ReferenceQueue();
 138     }
 139
 140     public WeakIdentityMap(int initialCapacity) {
 141         this(initialCapacity, 0.75f);
 142     }
 143
 144     public WeakIdentityMap() {
 145         this(11, 0.75f);
 146     }
 147
 148     public WeakIdentityMap(Map<? extends K, ? extends V> t) {
 149         this(Math.max(2 * t.size(), 11), 0.75f);
 150         putAll(t);
 151     }
 152
 153     public int size() {
 154         // Cleanup right before, to report a more accurate size.
 155         cleanup();
 156         return this.count;
 157     }
 158
 159     public boolean isEmpty() {
 160         return this.count == 0;
 161     }
 162
 163     public boolean containsValue(Object value) {
 164         Entry[] tab = this.table;
 165
 166         if (value == null) {
 167             for (int i = tab.length ; i-- > 0 ;) {
 168                 for (Entry e = tab[i], prev = null; e != null; e = e.next) {
 169                     if (e.get() == null) {
 170                         // Clean up after a cleared Reference.
 171                         this.modCount++;
 172                         if (prev != null) {
 173                             prev.next = e.next;
 174                         } else {
 175                             tab[i] = e.next;
 176                         }
 177                         this.count--;
 178                     } else if (e.value == null) {
 179                         return true;
 180                     } else {
 181                         prev = e;
 182                     }
 183                 }
 184             }
 185         } else {
 186             for (int i = tab.length ; i-- > 0 ;) {
 187                 for (Entry e = tab[i], prev = null; e != null; e = e.next) {
 188                     if (e.get() == null) {
 189                         // Clean up after a cleared Reference.
 190                         this.modCount++;
 191                         if (prev != null) {
 192                             prev.next = e.next;
 193                         } else {
 194                             tab[i] = e.next;
 195                         }
 196                         this.count--;
 197                     } else if (value.equals(e.value)) {
 198                         return true;
 199                     } else {
 200                         prev = e;
 201                     }
 202                 }
 203             }
 204         }
 205
 206         return false;
 207     }
 208
 209     public boolean containsKey(Object key) {
 210         if (key == null) {
 211             key = ReferencedValueHashMap.NULL;
 212         }
 213
 214         Entry[] tab = this.table;
 215         int hash = System.identityHashCode(key);
 216         int index = (hash & 0x7fffffff) % tab.length;
 217
 218         for (Entry e = tab[index], prev = null; e != null; e = e.next) {
 219             Object entryKey = e.get();
 220
 221             if (entryKey == null) {
 222                 // Clean up after a cleared Reference.
 223                 this.modCount++;
 224                 if (prev != null) {
 225                     prev.next = e.next;
 226                 } else {
 227                     tab[index] = e.next;
 228                 }
 229                 this.count--;
 230             } else if (e.hash == hash && key == entryKey) {
 231                 return true;
 232             } else {
 233                 prev = e;
 234             }
 235         }
 236
 237         return false;
 238     }
 239
 240     public V get(Object key) {
 241         if (key == null) {
 242             key = ReferencedValueHashMap.NULL;
 243         }
 244
 245         Entry<K, V>[] tab = this.table;
 246         int hash = System.identityHashCode(key);
 247         int index = (hash & 0x7fffffff) % tab.length;
 248
 249         for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
 250             Object entryKey = e.get();
 251
 252             if (entryKey == null) {
 253                 // Clean up after a cleared Reference.
 254                 this.modCount++;
 255                 if (prev != null) {
 256                     prev.next = e.next;
 257                 } else {
 258                     tab[index] = e.next;
 259                 }
 260                 this.count--;
 261             } else if (e.hash == hash && key == entryKey) {
 262                 return e.value;
 263             } else {
 264                 prev = e;
 265             }
 266         }
 267
 268         return null;
 269     }
 270
 271     private void cleanup() {
 272         // Cleanup after cleared References.
 273         Entry[] tab = this.table;
 274         ReferenceQueue queue = this.queue;
 275         Reference ref;
 276         while ((ref = queue.poll()) != null) {
 277             // Since buckets are single-linked, traverse entire list and
 278             // cleanup all cleared references in it.
 279             int index = (((Entry) ref).hash & 0x7fffffff) % tab.length;
 280             for (Entry e = tab[index], prev = null; e != null; e = e.next) {
 281                 if (e.get() == null) {
 282                     this.modCount++;
 283                     if (prev != null) {
 284                         prev.next = e.next;
 285                     } else {
 286                         tab[index] = e.next;
 287                     }
 288                     this.count--;
 289                 } else {
 290                     prev = e;
 291                 }
 292             }
 293         }
 294     }
 295
 296     private void rehash() {
 297         int oldCapacity = this.table.length;
 298         Entry[] oldMap = this.table;
 299
 300         int newCapacity = oldCapacity * 2 + 1;
 301         if (newCapacity <= 0) {
 302             // Overflow.
 303             if ((newCapacity = Integer.MAX_VALUE) == oldCapacity) {
 304                 return;
 305             }
 306         }
 307         Entry[] newMap = new Entry[newCapacity];
 308
 309         this.modCount++;
 310         this.threshold = (int)(newCapacity * this.loadFactor);
 311         this.table = newMap;
 312
 313         for (int i = oldCapacity ; i-- > 0 ;) {
 314             for (Entry old = oldMap[i] ; old != null ; ) {
 315                 Entry e = old;
 316                 old = old.next;
 317
 318                 // Only copy entry if its key hasn't been cleared.
 319                 if (e.get() == null) {
 320                     this.count--;
 321                 } else {
 322                     int index = (e.hash & 0x7fffffff) % newCapacity;
 323                     e.next = newMap[index];
 324                     newMap[index] = e;
 325                 }
 326             }
 327         }
 328     }
 329
 330     public V put(K key, V value) {
 331         if (key == null) {
 332             key = (K) ReferencedValueHashMap.NULL;
 333         }
 334
 335         cleanup();
 336
 337         // Make sure the key is not already in the WeakIdentityMap.
 338         Entry[] tab = this.table;
 339         int hash = System.identityHashCode(key);
 340         int index = (hash & 0x7fffffff) % tab.length;
 341
 342         for (Entry e = tab[index], prev = null; e != null; e = e.next) {
 343             Object entryKey = e.get();
 344
 345             if (entryKey == null) {
 346                 // Clean up after a cleared Reference.
 347                 this.modCount++;
 348                 if (prev != null) {
 349                     prev.next = e.next;
 350                 } else {
 351                     tab[index] = e.next;
 352                 }
 353                 this.count--;
 354             } else if (e.hash == hash && key == entryKey) {
 355                 Object old = e.value;
 356                 e.value = value;
 357                 return (V) old;
 358             } else {
 359                 prev = e;
 360             }
 361         }
 362
 363         this.modCount++;
 364
 365         if (this.count >= this.threshold) {
 366             // Rehash the table if the threshold is still exceeded.
 367             rehash();
 368             tab = this.table;
 369             index = (hash & 0x7fffffff) % tab.length;
 370         }
 371
 372         // Creates the new entry.
 373         Entry e = new Entry(hash, key, this.queue, value, tab[index]);
 374         tab[index] = e;
 375         this.count++;
 376         return null;
 377     }
 378
 379     public V remove(Object key) {
 380         if (key == null) {
 381             key = ReferencedValueHashMap.NULL;
 382         }
 383
 384         Entry<K, V>[] tab = this.table;
 385         int hash = System.identityHashCode(key);
 386         int index = (hash & 0x7fffffff) % tab.length;
 387
 388         for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
 389             Object entryKey = e.get();
 390
 391             if (entryKey == null) {
 392                 // Clean up after a cleared Reference.
 393                 this.modCount++;
 394                 if (prev != null) {
 395                     prev.next = e.next;
 396                 } else {
 397                     tab[index] = e.next;
 398                 }
 399                 this.count--;
 400             } else if (e.hash == hash && key == entryKey) {
 401                 this.modCount++;
 402                 if (prev != null) {
 403                     prev.next = e.next;
 404                 } else {
 405                     tab[index] = e.next;
 406                 }
 407                 this.count--;
 408
 409                 V oldValue = e.value;
 410                 e.value = null;
 411                 return oldValue;
 412             } else {
 413                 prev = e;
 414             }
 415         }
 416
 417         return null;
 418     }
 419
 420     public void putAll(Map<? extends K, ? extends V> t) {
 421         Iterator i = t.entrySet().iterator();
 422         while (i.hasNext()) {
 423             Map.Entry e = (Map.Entry) i.next();
 424             put((K) e.getKey(), (V) e.getValue());
 425         }
 426     }
 427
 428     public void clear() {
 429         Entry[] tab = this.table;
 430         this.modCount++;
 431         for (int index = tab.length; --index >= 0; ) {
 432             tab[index] = null;
 433         }
 434         this.count = 0;
 435     }
 436
 437     public Object clone() {
 438         try {
 439             WeakIdentityMap t = (WeakIdentityMap)super.clone();
 440             t.table = new Entry[this.table.length];
 441             for (int i = this.table.length ; i-- > 0 ; ) {
 442                 t.table[i] = (this.table[i] != null)
 443                     ? (Entry)this.table[i].copy(this.queue) : null;
 444             }
 445             t.keySet = null;
 446             t.entrySet = null;
 447             t.values = null;
 448             t.modCount = 0;
 449             return t;
 450         }
 451         catch (CloneNotSupportedException e) {
 452             // this shouldn't happen, since we are Cloneable
 453             throw new InternalError();
 454         }
 455     }
 456
 457     public Set<K> keySet() {
 458         if (this.keySet == null) {
 459             this.keySet = new AbstractSet<K>() {
 460                 public Iterator iterator() {
 461                     return createHashIterator(KEYS);
 462                 }
 463                 public int size() {
 464                     return WeakIdentityMap.this.count;
 465                 }
 466                 public boolean contains(Object o) {
 467                     return containsKey(o);
 468                 }
 469                 public boolean remove(Object o) {
 470                     return o == null ? false : WeakIdentityMap.this.remove(o) == o;
 471                 }
 472                 public void clear() {
 473                     WeakIdentityMap.this.clear();
 474                 }
 475                 public String toString() {
 476                     return WeakIdentityMap.toString(this);
 477                 }
 478             };
 479         }
 480         return this.keySet;
 481     }
 482
 483     public Collection<V> values() {
 484         if (this.values==null) {
 485             this.values = new AbstractCollection<V>() {
 486                 public Iterator<V> iterator() {
 487                     return createHashIterator(VALUES);
 488                 }
 489                 public int size() {
 490                     return WeakIdentityMap.this.count;
 491                 }
 492                 public boolean contains(Object o) {
 493                     return containsValue(o);
 494                 }
 495                 public void clear() {
 496                     WeakIdentityMap.this.clear();
 497                 }
 498                 public String toString() {
 499                     return WeakIdentityMap.toString(this);
 500                 }
 501             };
 502         }
 503         return this.values;
 504     }
 505
 506     public Set<Map.Entry<K, V>> entrySet() {
 507         if (this.entrySet==null) {
 508             this.entrySet = new AbstractSet<Map.Entry<K, V>>() {
 509                 public Iterator<Map.Entry<K, V>> iterator() {
 510                     return createHashIterator(ENTRIES);
 511                 }
 512
 513                 public boolean contains(Object o) {
 514                     if (!(o instanceof Map.Entry)) {
 515                         return false;
 516                     }
 517                     Map.Entry entry = (Map.Entry)o;
 518                     Object key = entry.getKey();
 519
 520                     Entry[] tab = WeakIdentityMap.this.table;
 521                     int hash = System.identityHashCode(key);
 522                     int index = (hash & 0x7fffffff) % tab.length;
 523
 524                     for (Entry e = tab[index], prev = null; e != null; e = e.next) {
 525                         Object entryKey = e.get();
 526
 527                         if (entryKey == null) {
 528                             // Clean up after a cleared Reference.
 529                             WeakIdentityMap.this.modCount++;
 530                             if (prev != null) {
 531                                 prev.next = e.next;
 532                             } else {
 533                                 tab[index] = e.next;
 534                             }
 535                             WeakIdentityMap.this.count--;
 536                         } else if (e.hash == hash && e.equals(entry)) {
 537                             return true;
 538                         } else {
 539                             prev = e;
 540                         }
 541                     }
 542
 543                     return false;
 544                 }
 545
 546                 public boolean remove(Object o) {
 547                     if (!(o instanceof Map.Entry)) {
 548                         return false;
 549                     }
 550                     Map.Entry entry = (Map.Entry)o;
 551                     Object key = entry.getKey();
 552                     Entry[] tab = WeakIdentityMap.this.table;
 553                     int hash = System.identityHashCode(key);
 554                     int index = (hash & 0x7fffffff) % tab.length;
 555
 556                     for (Entry e = tab[index], prev = null; e != null; e = e.next) {
 557                         if (e.get() == null) {
 558                             // Clean up after a cleared Reference.
 559                             WeakIdentityMap.this.modCount++;
 560                             if (prev != null) {
 561                                 prev.next = e.next;
 562                             } else {
 563                                 tab[index] = e.next;
 564                             }
 565                             WeakIdentityMap.this.count--;
 566                         } else if (e.hash == hash && e.equals(entry)) {
 567                             WeakIdentityMap.this.modCount++;
 568                             if (prev != null) {
 569                                 prev.next = e.next;
 570                             } else {
 571                                 tab[index] = e.next;
 572                             }
 573                             WeakIdentityMap.this.count--;
 574
 575                             e.value = null;
 576                             return true;
 577                         } else {
 578                             prev = e;
 579                         }
 580                     }
 581                     return false;
 582                 }
 583
 584                 public int size() {
 585                     return WeakIdentityMap.this.count;
 586                 }
 587
 588                 public void clear() {
 589                     WeakIdentityMap.this.clear();
 590                 }
 591
 592                 public String toString() {
 593                     return WeakIdentityMap.toString(this);
 594                 }
 595             };
 596         }
 597
 598         return this.entrySet;
 599     }
 600
 601     /**
 602      * Gets the map as a String.
 603      *
 604      * @return a string version of the map
 605      */
 606     public String toString() {
 607         return toString(this);
 608     }
 609
 610     private Iterator createHashIterator(int type) {
 611         if (this.count == 0) {
 612             return Collections.EMPTY_SET.iterator();
 613         } else {
 614             return new HashIterator(type);
 615         }
 616     }
 617
 618     /**
 619      * WeakIdentityMap collision list entry.
 620      */
 621     private static class Entry<K, V> extends WeakReference<K> implements Map.Entry<K, V> {
 622         int hash;
 623         V value;
 624         Entry<K, V> next;
 625
 626         Entry(int hash, K key, ReferenceQueue<K> queue, V value, Entry<K, V> next) {
 627             super(key, queue);
 628             this.hash = hash;
 629             this.value = value;
 630             this.next = next;
 631         }
 632
 633         public void clear() {
 634             // Do nothing if reference is explicity cleared. This prevents
 635             // backdoor modification of map entries.
 636         }
 637
 638         public K getKey() {
 639             K key = Entry.this.get();
 640             return key == ReferencedValueHashMap.NULL ? null : key;
 641         }
 642
 643         public V getValue() {
 644             return this.value;
 645         }
 646
 647         public V setValue(V value) {
 648             V oldValue = this.value;
 649             this.value = value;
 650             return oldValue;
 651         }
 652
 653         public boolean equals(Object obj) {
 654             if (!(obj instanceof Map.Entry)) {
 655                 return false;
 656             }
 657             return equals((Map.Entry)obj);
 658         }
 659
 660         boolean equals(Map.Entry<K, V> e) {
 661             Object thisKey = get();
 662             if (thisKey == null) {
 663                 return false;
 664             } else if (thisKey == ReferencedValueHashMap.NULL) {
 665                 thisKey = null;
 666             }
 667             return (thisKey == e.getKey()) &&
 668                 (this.value == null ? e.getValue() == null : this.value.equals(e.getValue()));
 669         }
 670
 671         public int hashCode() {
 672             return this.hash ^ (this.value == null ? 0 : this.value.hashCode());
 673         }
 674
 675         public String toString() {
 676             return getKey() + "=" + this.value;
 677         }
 678
 679         protected Object copy(ReferenceQueue queue) {
 680             return new Entry(this.hash, get(), queue, this.value,
 681                              (this.next == null ? null : (Entry)this.next.copy(queue)));
 682         }
 683     }
 684
 685     private class HashIterator implements Iterator {
 686         private final int type;
 687         private final Entry[] table;
 688
 689         private int index;
 690
 691         @SuppressWarnings("unused")
 692         // To ensure that the iterator doesn't return cleared entries, keep a
 693         // hard reference to the key. Its existence will prevent the weak
 694         // key from being cleared.
 695         Object entryKey;
 696         Entry entry;
 697
 698         Entry last;
 699
 700         /**
 701          * The modCount value that the iterator believes that the backing
 702          * List should have. If this expectation is violated, the iterator
 703          * has detected concurrent modification.
 704          */
 705         private int expectedModCount = WeakIdentityMap.this.modCount;
 706
 707         HashIterator(int type) {
 708             this.table = WeakIdentityMap.this.table;
 709             this.type = type;
 710             this.index = table.length;
 711         }
 712
 713         public boolean hasNext() {
 714             while (this.entry == null || (this.entryKey = this.entry.get()) == null) {
 715                 if (this.entry != null) {
 716                     // Clean up after a cleared Reference.
 717                     remove(this.entry);
 718                     this.entry = this.entry.next;
 719                 }
 720                 else {
 721                     if (this.index <= 0) {
 722                         return false;
 723                     }
 724                     else {
 725                         this.entry = this.table[--this.index];
 726                     }
 727                 }
 728             }
 729
 730             return true;
 731         }
 732
 733         public Object next() {
 734             if (WeakIdentityMap.this.modCount != this.expectedModCount) {
 735                 throw new ConcurrentModificationException();
 736             }
 737
 738             if (!hasNext()) {
 739                 throw new NoSuchElementException();
 740             }
 741
 742             this.last = this.entry;
 743             this.entry = this.entry.next;
 744
 745             return this.type == KEYS ? this.last.getKey() :
 746                 (this.type == VALUES ? this.last.getValue() : this.last);
 747         }
 748
 749         public void remove() {
 750             if (this.last == null) {
 751                 throw new IllegalStateException();
 752             }
 753             if (WeakIdentityMap.this.modCount != this.expectedModCount) {
 754                 throw new ConcurrentModificationException();
 755             }
 756             remove(this.last);
 757             this.last = null;
 758         }
 759
 760         private void remove(Entry toRemove) {
 761             Entry[] tab = this.table;
 762             int index = (toRemove.hash & 0x7fffffff) % tab.length;
 763
 764             for (Entry e = tab[index], prev = null; e != null; e = e.next) {
 765                 if (e == toRemove) {
 766                     WeakIdentityMap.this.modCount++;
 767                     expectedModCount++;
 768                     if (prev == null) {
 769                         tab[index] = e.next;
 770                     } else {
 771                         prev.next = e.next;
 772                     }
 773                     WeakIdentityMap.this.count--;
 774                     return;
 775                 } else {
 776                     prev = e;
 777                 }
 778             }
 779
 780             throw new ConcurrentModificationException();
 781         }
 782
 783         public String toString() {
 784             if (this.last != null) {
 785                 return "Iterator[" + this.last + ']';
 786             } else {
 787                 return "Iterator[]";
 788             }
 789         }
 790     }
 791 }