KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > cojen > util > WeakIdentityMap


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 JavaDoc;
20 import java.lang.ref.ReferenceQueue JavaDoc;
21 import java.lang.ref.WeakReference JavaDoc;
22
23 import java.util.AbstractCollection JavaDoc;
24 import java.util.AbstractMap JavaDoc;
25 import java.util.AbstractSet JavaDoc;
26 import java.util.Collection JavaDoc;
27 import java.util.Collections JavaDoc;
28 import java.util.ConcurrentModificationException JavaDoc;
29 import java.util.Iterator JavaDoc;
30 import java.util.Map JavaDoc;
31 import java.util.NoSuchElementException JavaDoc;
32 import java.util.Set JavaDoc;
33
34 /**
35  * WeakIdentityMap is like WeakHashMap, except it uses a key's identity
36  * hashcode and equals methods. WeakIdentityMap is not thread-safe and must be
37  * wrapped with Collections.synchronizedMap to be made thread-safe.
38  * <p>
39  * The documentation for WeakHashMap states that it is intended primarily for
40  * use with key objects whose equals methods test for object identity using the
41  * == operator. Because WeakIdentityMap strictly follows this behavior, it is
42  * better suited for this purpose.
43  * <p>
44  * Note: Weakly referenced entries may be automatically removed during
45  * either accessor or mutator operations, possibly causing a concurrent
46  * modification to be detected. Therefore, even if multiple threads are only
47  * accessing this map, be sure to synchronize this map first. Also, do not
48  * rely on the value returned by size() when using an iterator from this map.
49  * The iterators may return less entries than the amount reported by size().
50  *
51  * @author Brian S O'Neill
52  */

53 public class WeakIdentityMap extends AbstractMap JavaDoc implements Map JavaDoc, Cloneable JavaDoc {
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 JavaDoc toString(Collection JavaDoc c) {
65         if (c.size() == 0) {
66             return "[]";
67         }
68         StringBuffer JavaDoc buf = new StringBuffer JavaDoc(32 * c.size());
69         buf.append('[');
70
71         Iterator JavaDoc it = c.iterator();
72         boolean hasNext = it.hasNext();
73         while (hasNext) {
74             Object JavaDoc obj = it.next();
75             buf.append(obj == c ? "(this Collection)" : obj);
76             if (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 JavaDoc toString(Map JavaDoc m) {
88         if (m.size() == 0) {
89             return "{}";
90         }
91         StringBuffer JavaDoc buf = new StringBuffer JavaDoc(32 * m.size());
92         buf.append('{');
93
94         Iterator JavaDoc it = m.entrySet().iterator();
95         boolean hasNext = it.hasNext();
96         while (hasNext) {
97             Map.Entry JavaDoc entry = (Map.Entry JavaDoc)it.next();
98             Object JavaDoc key = entry.getKey();
99             Object JavaDoc 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[] table;
115     private transient int count;
116     private int threshold;
117     private final float loadFactor;
118     private final ReferenceQueue JavaDoc queue;
119     private transient volatile int modCount;
120
121     // Views
122

123     private transient Set JavaDoc keySet;
124     private transient Set JavaDoc entrySet;
125     private transient Collection JavaDoc values;
126
127     public WeakIdentityMap(int initialCapacity, float loadFactor) {
128         if (initialCapacity <= 0) {
129             throw new IllegalArgumentException JavaDoc("Initial capacity must be greater than 0");
130         }
131         if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
132             throw new IllegalArgumentException JavaDoc("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 JavaDoc();
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 JavaDoc 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 JavaDoc 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 JavaDoc key) {
210         if (key == null) {
211             key = KeyFactory.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 JavaDoc 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 Object JavaDoc get(Object JavaDoc key) {
241         if (key == null) {
242             key = KeyFactory.NULL;
243         }
244
245         Entry[] tab = this.table;
246         int hash = System.identityHashCode(key);
247         int index = (hash & 0x7fffffff) % tab.length;
248
249         for (Entry e = tab[index], prev = null; e != null; e = e.next) {
250             Object JavaDoc 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 JavaDoc queue = this.queue;
275         Reference JavaDoc 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 Object JavaDoc put(Object JavaDoc key, Object JavaDoc value) {
331         if (key == null) {
332             key = KeyFactory.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 JavaDoc 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 JavaDoc old = e.value;
356                 e.value = value;
357                 return 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 Object JavaDoc remove(Object JavaDoc key) {
380         if (key == null) {
381             key = KeyFactory.NULL;
382         }
383
384         Entry[] tab = this.table;
385         int hash = System.identityHashCode(key);
386         int index = (hash & 0x7fffffff) % tab.length;
387
388         for (Entry e = tab[index], prev = null; e != null; e = e.next) {
389             Object JavaDoc 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                 Object JavaDoc 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 JavaDoc t) {
421         Iterator JavaDoc i = t.entrySet().iterator();
422         while (i.hasNext()) {
423             Map.Entry JavaDoc e = (Map.Entry JavaDoc) i.next();
424             put(e.getKey(), 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 JavaDoc 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 JavaDoc e) {
452             // this shouldn't happen, since we are Cloneable
453
throw new InternalError JavaDoc();
454         }
455     }
456
457     public Set JavaDoc keySet() {
458         if (this.keySet == null) {
459             this.keySet = new AbstractSet JavaDoc() {
460                 public Iterator JavaDoc iterator() {
461                     return createHashIterator(KEYS);
462                 }
463                 public int size() {
464                     return WeakIdentityMap.this.count;
465                 }
466                 public boolean contains(Object JavaDoc o) {
467                     return containsKey(o);
468                 }
469                 public boolean remove(Object JavaDoc o) {
470                     return o == null ? false : WeakIdentityMap.this.remove(o) == o;
471                 }
472                 public void clear() {
473                     WeakIdentityMap.this.clear();
474                 }
475                 public String JavaDoc toString() {
476                     return WeakIdentityMap.this.toString(this);
477                 }
478             };
479         }
480         return this.keySet;
481     }
482
483     public Collection JavaDoc values() {
484         if (this.values==null) {
485             this.values = new AbstractCollection JavaDoc() {
486                 public Iterator JavaDoc iterator() {
487                     return createHashIterator(VALUES);
488                 }
489                 public int size() {
490                     return WeakIdentityMap.this.count;
491                 }
492                 public boolean contains(Object JavaDoc o) {
493                     return containsValue(o);
494                 }
495                 public void clear() {
496                     WeakIdentityMap.this.clear();
497                 }
498                 public String JavaDoc toString() {
499                     return WeakIdentityMap.this.toString(this);
500                 }
501             };
502         }
503         return this.values;
504     }
505
506     public Set JavaDoc entrySet() {
507         if (this.entrySet==null) {
508             this.entrySet = new AbstractSet JavaDoc() {
509                 public Iterator JavaDoc iterator() {
510                     return createHashIterator(ENTRIES);
511                 }
512
513                 public boolean contains(Object JavaDoc o) {
514                     if (!(o instanceof Map.Entry JavaDoc)) {
515                         return false;
516                     }
517                     Map.Entry JavaDoc entry = (Map.Entry JavaDoc)o;
518                     Object JavaDoc 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 JavaDoc 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 JavaDoc o) {
547                     if (!(o instanceof Map.Entry JavaDoc)) {
548                         return false;
549                     }
550                     Map.Entry JavaDoc entry = (Map.Entry JavaDoc)o;
551                     Object JavaDoc 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 JavaDoc 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 JavaDoc toString() {
607         return toString(this);
608     }
609
610     private Iterator JavaDoc 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 extends WeakReference JavaDoc implements Map.Entry JavaDoc {
622         int hash;
623         Object JavaDoc value;
624         Entry next;
625
626         Entry(int hash, Object JavaDoc key, ReferenceQueue JavaDoc queue, Object JavaDoc value, Entry 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 Object JavaDoc getKey() {
639             Object JavaDoc key = Entry.this.get();
640             return key == KeyFactory.NULL ? null : key;
641         }
642
643         public Object JavaDoc getValue() {
644             return this.value;
645         }
646
647         public Object JavaDoc setValue(Object JavaDoc value) {
648             Object JavaDoc oldValue = this.value;
649             this.value = value;
650             return oldValue;
651         }
652
653         public boolean equals(Object JavaDoc obj) {
654             if (!(obj instanceof Map.Entry JavaDoc)) {
655                 return false;
656             }
657             return equals((Map.Entry JavaDoc)obj);
658         }
659
660         boolean equals(Map.Entry JavaDoc e) {
661             Object JavaDoc thisKey = get();
662             if (thisKey == null) {
663                 return false;
664             } else if (thisKey == KeyFactory.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 JavaDoc toString() {
676             return getKey() + "=" + this.value;
677         }
678
679         protected Object JavaDoc copy(ReferenceQueue JavaDoc 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 JavaDoc {
686         private final int type;
687         private final Entry[] table;
688
689         private int index;
690
691         // To ensure that the iterator doesn't return cleared entries, keep a
692
// hard reference to the key. Its existence will prevent the weak
693
// key from being cleared.
694
Object JavaDoc entryKey;
695         Entry entry;
696
697         Entry last;
698
699         /**
700          * The modCount value that the iterator believes that the backing
701          * List should have. If this expectation is violated, the iterator
702          * has detected concurrent modification.
703          */

704         private int expectedModCount = WeakIdentityMap.this.modCount;
705
706         HashIterator(int type) {
707             this.table = WeakIdentityMap.this.table;
708             this.type = type;
709             this.index = table.length;
710         }
711
712         public boolean hasNext() {
713             while (this.entry == null || (this.entryKey = this.entry.get()) == null) {
714                 if (this.entry != null) {
715                     // Clean up after a cleared Reference.
716
remove(this.entry);
717                     this.entry = this.entry.next;
718                 }
719                 else {
720                     if (this.index <= 0) {
721                         return false;
722                     }
723                     else {
724                         this.entry = this.table[--this.index];
725                     }
726                 }
727             }
728
729             return true;
730         }
731
732         public Object JavaDoc next() {
733             if (WeakIdentityMap.this.modCount != this.expectedModCount) {
734                 throw new ConcurrentModificationException JavaDoc();
735             }
736
737             if (!hasNext()) {
738                 throw new NoSuchElementException JavaDoc();
739             }
740
741             this.last = this.entry;
742             this.entry = this.entry.next;
743
744             return this.type == KEYS ? this.last.getKey() :
745                 (this.type == VALUES ? this.last.getValue() : this.last);
746         }
747
748         public void remove() {
749             if (this.last == null) {
750                 throw new IllegalStateException JavaDoc();
751             }
752             if (WeakIdentityMap.this.modCount != this.expectedModCount) {
753                 throw new ConcurrentModificationException JavaDoc();
754             }
755             remove(this.last);
756             this.last = null;
757         }
758
759         private void remove(Entry toRemove) {
760             Entry[] tab = this.table;
761             int index = (toRemove.hash & 0x7fffffff) % tab.length;
762
763             for (Entry e = tab[index], prev = null; e != null; e = e.next) {
764                 if (e == toRemove) {
765                     WeakIdentityMap.this.modCount++;
766                     expectedModCount++;
767                     if (prev == null) {
768                         tab[index] = e.next;
769                     } else {
770                         prev.next = e.next;
771                     }
772                     WeakIdentityMap.this.count--;
773                     return;
774                 } else {
775                     prev = e;
776                 }
777             }
778
779             throw new ConcurrentModificationException JavaDoc();
780         }
781
782         public String JavaDoc toString() {
783             if (this.last != null) {
784                 return "Iterator[" + this.last + ']';
785             } else {
786                 return "Iterator[]";
787             }
788         }
789     }
790 }
791
Popular Tags