001: /*
002: * Copyright 2004 Brian S O'Neill
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016:
017: package org.cojen.util;
018:
019: import java.lang.ref.Reference;
020: import java.lang.ref.ReferenceQueue;
021: import java.lang.ref.WeakReference;
022:
023: import java.util.AbstractCollection;
024: import java.util.AbstractMap;
025: import java.util.AbstractSet;
026: import java.util.Collection;
027: import java.util.Collections;
028: import java.util.ConcurrentModificationException;
029: import java.util.Iterator;
030: import java.util.Map;
031: import java.util.NoSuchElementException;
032: import java.util.Set;
033:
034: /**
035: * WeakIdentityMap is like WeakHashMap, except it uses a key's identity
036: * hashcode and equals methods. WeakIdentityMap is not thread-safe and must be
037: * wrapped with Collections.synchronizedMap to be made thread-safe.
038: * <p>
039: * The documentation for WeakHashMap states that it is intended primarily for
040: * use with key objects whose equals methods test for object identity using the
041: * == operator. Because WeakIdentityMap strictly follows this behavior, it is
042: * better suited for this purpose.
043: * <p>
044: * Note: Weakly referenced entries may be automatically removed during
045: * either accessor or mutator operations, possibly causing a concurrent
046: * modification to be detected. Therefore, even if multiple threads are only
047: * accessing this map, be sure to synchronize this map first. Also, do not
048: * rely on the value returned by size() when using an iterator from this map.
049: * The iterators may return less entries than the amount reported by size().
050: *
051: * @author Brian S O'Neill
052: */
053: public class WeakIdentityMap extends AbstractMap implements Map,
054: Cloneable {
055:
056: // Types of Iterators
057: static final int KEYS = 0;
058: static final int VALUES = 1;
059: static final int ENTRIES = 2;
060:
061: /**
062: * Converts a collection to string, supporting collections that contain
063: * self references
064: */
065: static String toString(Collection c) {
066: if (c.size() == 0) {
067: return "[]";
068: }
069: StringBuffer buf = new StringBuffer(32 * c.size());
070: buf.append('[');
071:
072: Iterator it = c.iterator();
073: boolean hasNext = it.hasNext();
074: while (hasNext) {
075: Object obj = it.next();
076: buf.append(obj == c ? "(this Collection)" : obj);
077: if (hasNext) {
078: buf.append(", ");
079: }
080: }
081: buf.append("]");
082: return buf.toString();
083: }
084:
085: /**
086: * Converts a map to string, supporting maps that contain self references
087: */
088: static String toString(Map m) {
089: if (m.size() == 0) {
090: return "{}";
091: }
092: StringBuffer buf = new StringBuffer(32 * m.size());
093: buf.append('{');
094:
095: Iterator it = m.entrySet().iterator();
096: boolean hasNext = it.hasNext();
097: while (hasNext) {
098: Map.Entry entry = (Map.Entry) it.next();
099: Object key = entry.getKey();
100: Object value = entry.getValue();
101: buf.append(key == m ? "(this Map)" : key).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 queue;
119: private transient volatile int modCount;
120:
121: // Views
122:
123: private transient Set keySet;
124: private transient Set entrySet;
125: private transient Collection values;
126:
127: public WeakIdentityMap(int initialCapacity, float loadFactor) {
128: if (initialCapacity <= 0) {
129: throw new IllegalArgumentException(
130: "Initial capacity must be greater than 0");
131: }
132: if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
133: throw new IllegalArgumentException(
134: "Load factor must be greater than 0");
135: }
136: this .loadFactor = loadFactor;
137: this .table = new Entry[initialCapacity];
138: this .threshold = (int) (initialCapacity * loadFactor);
139: this .queue = new ReferenceQueue();
140: }
141:
142: public WeakIdentityMap(int initialCapacity) {
143: this (initialCapacity, 0.75f);
144: }
145:
146: public WeakIdentityMap() {
147: this (11, 0.75f);
148: }
149:
150: public WeakIdentityMap(Map t) {
151: this (Math.max(2 * t.size(), 11), 0.75f);
152: putAll(t);
153: }
154:
155: public int size() {
156: // Cleanup right before, to report a more accurate size.
157: cleanup();
158: return this .count;
159: }
160:
161: public boolean isEmpty() {
162: return this .count == 0;
163: }
164:
165: public boolean containsValue(Object value) {
166: Entry[] tab = this .table;
167:
168: if (value == null) {
169: for (int i = tab.length; i-- > 0;) {
170: for (Entry e = tab[i], prev = null; e != null; e = e.next) {
171: if (e.get() == null) {
172: // Clean up after a cleared Reference.
173: this .modCount++;
174: if (prev != null) {
175: prev.next = e.next;
176: } else {
177: tab[i] = e.next;
178: }
179: this .count--;
180: } else if (e.value == null) {
181: return true;
182: } else {
183: prev = e;
184: }
185: }
186: }
187: } else {
188: for (int i = tab.length; i-- > 0;) {
189: for (Entry e = tab[i], prev = null; e != null; e = e.next) {
190: if (e.get() == null) {
191: // Clean up after a cleared Reference.
192: this .modCount++;
193: if (prev != null) {
194: prev.next = e.next;
195: } else {
196: tab[i] = e.next;
197: }
198: this .count--;
199: } else if (value.equals(e.value)) {
200: return true;
201: } else {
202: prev = e;
203: }
204: }
205: }
206: }
207:
208: return false;
209: }
210:
211: public boolean containsKey(Object key) {
212: if (key == null) {
213: key = KeyFactory.NULL;
214: }
215:
216: Entry[] tab = this .table;
217: int hash = System.identityHashCode(key);
218: int index = (hash & 0x7fffffff) % tab.length;
219:
220: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
221: Object entryKey = e.get();
222:
223: if (entryKey == null) {
224: // Clean up after a cleared Reference.
225: this .modCount++;
226: if (prev != null) {
227: prev.next = e.next;
228: } else {
229: tab[index] = e.next;
230: }
231: this .count--;
232: } else if (e.hash == hash && key == entryKey) {
233: return true;
234: } else {
235: prev = e;
236: }
237: }
238:
239: return false;
240: }
241:
242: public Object get(Object key) {
243: if (key == null) {
244: key = KeyFactory.NULL;
245: }
246:
247: Entry[] tab = this .table;
248: int hash = System.identityHashCode(key);
249: int index = (hash & 0x7fffffff) % tab.length;
250:
251: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
252: Object entryKey = e.get();
253:
254: if (entryKey == null) {
255: // Clean up after a cleared Reference.
256: this .modCount++;
257: if (prev != null) {
258: prev.next = e.next;
259: } else {
260: tab[index] = e.next;
261: }
262: this .count--;
263: } else if (e.hash == hash && key == entryKey) {
264: return e.value;
265: } else {
266: prev = e;
267: }
268: }
269:
270: return null;
271: }
272:
273: private void cleanup() {
274: // Cleanup after cleared References.
275: Entry[] tab = this .table;
276: ReferenceQueue queue = this .queue;
277: Reference ref;
278: while ((ref = queue.poll()) != null) {
279: // Since buckets are single-linked, traverse entire list and
280: // cleanup all cleared references in it.
281: int index = (((Entry) ref).hash & 0x7fffffff) % tab.length;
282: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
283: if (e.get() == null) {
284: this .modCount++;
285: if (prev != null) {
286: prev.next = e.next;
287: } else {
288: tab[index] = e.next;
289: }
290: this .count--;
291: } else {
292: prev = e;
293: }
294: }
295: }
296: }
297:
298: private void rehash() {
299: int oldCapacity = this .table.length;
300: Entry[] oldMap = this .table;
301:
302: int newCapacity = oldCapacity * 2 + 1;
303: if (newCapacity <= 0) {
304: // Overflow.
305: if ((newCapacity = Integer.MAX_VALUE) == oldCapacity) {
306: return;
307: }
308: }
309: Entry[] newMap = new Entry[newCapacity];
310:
311: this .modCount++;
312: this .threshold = (int) (newCapacity * this .loadFactor);
313: this .table = newMap;
314:
315: for (int i = oldCapacity; i-- > 0;) {
316: for (Entry old = oldMap[i]; old != null;) {
317: Entry e = old;
318: old = old.next;
319:
320: // Only copy entry if its key hasn't been cleared.
321: if (e.get() == null) {
322: this .count--;
323: } else {
324: int index = (e.hash & 0x7fffffff) % newCapacity;
325: e.next = newMap[index];
326: newMap[index] = e;
327: }
328: }
329: }
330: }
331:
332: public Object put(Object key, Object value) {
333: if (key == null) {
334: key = KeyFactory.NULL;
335: }
336:
337: cleanup();
338:
339: // Make sure the key is not already in the WeakIdentityMap.
340: Entry[] tab = this .table;
341: int hash = System.identityHashCode(key);
342: int index = (hash & 0x7fffffff) % tab.length;
343:
344: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
345: Object entryKey = e.get();
346:
347: if (entryKey == null) {
348: // Clean up after a cleared Reference.
349: this .modCount++;
350: if (prev != null) {
351: prev.next = e.next;
352: } else {
353: tab[index] = e.next;
354: }
355: this .count--;
356: } else if (e.hash == hash && key == entryKey) {
357: Object old = e.value;
358: e.value = value;
359: return old;
360: } else {
361: prev = e;
362: }
363: }
364:
365: this .modCount++;
366:
367: if (this .count >= this .threshold) {
368: // Rehash the table if the threshold is still exceeded.
369: rehash();
370: tab = this .table;
371: index = (hash & 0x7fffffff) % tab.length;
372: }
373:
374: // Creates the new entry.
375: Entry e = new Entry(hash, key, this .queue, value, tab[index]);
376: tab[index] = e;
377: this .count++;
378: return null;
379: }
380:
381: public Object remove(Object key) {
382: if (key == null) {
383: key = KeyFactory.NULL;
384: }
385:
386: Entry[] tab = this .table;
387: int hash = System.identityHashCode(key);
388: int index = (hash & 0x7fffffff) % tab.length;
389:
390: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
391: Object entryKey = e.get();
392:
393: if (entryKey == null) {
394: // Clean up after a cleared Reference.
395: this .modCount++;
396: if (prev != null) {
397: prev.next = e.next;
398: } else {
399: tab[index] = e.next;
400: }
401: this .count--;
402: } else if (e.hash == hash && key == entryKey) {
403: this .modCount++;
404: if (prev != null) {
405: prev.next = e.next;
406: } else {
407: tab[index] = e.next;
408: }
409: this .count--;
410:
411: Object oldValue = e.value;
412: e.value = null;
413: return oldValue;
414: } else {
415: prev = e;
416: }
417: }
418:
419: return null;
420: }
421:
422: public void putAll(Map t) {
423: Iterator i = t.entrySet().iterator();
424: while (i.hasNext()) {
425: Map.Entry e = (Map.Entry) i.next();
426: put(e.getKey(), e.getValue());
427: }
428: }
429:
430: public void clear() {
431: Entry[] tab = this .table;
432: this .modCount++;
433: for (int index = tab.length; --index >= 0;) {
434: tab[index] = null;
435: }
436: this .count = 0;
437: }
438:
439: public Object clone() {
440: try {
441: WeakIdentityMap t = (WeakIdentityMap) super .clone();
442: t.table = new Entry[this .table.length];
443: for (int i = this .table.length; i-- > 0;) {
444: t.table[i] = (this .table[i] != null) ? (Entry) this .table[i]
445: .copy(this .queue)
446: : null;
447: }
448: t.keySet = null;
449: t.entrySet = null;
450: t.values = null;
451: t.modCount = 0;
452: return t;
453: } catch (CloneNotSupportedException e) {
454: // this shouldn't happen, since we are Cloneable
455: throw new InternalError();
456: }
457: }
458:
459: public Set keySet() {
460: if (this .keySet == null) {
461: this .keySet = new AbstractSet() {
462: public Iterator iterator() {
463: return createHashIterator(KEYS);
464: }
465:
466: public int size() {
467: return WeakIdentityMap.this .count;
468: }
469:
470: public boolean contains(Object o) {
471: return containsKey(o);
472: }
473:
474: public boolean remove(Object o) {
475: return o == null ? false : WeakIdentityMap.this
476: .remove(o) == o;
477: }
478:
479: public void clear() {
480: WeakIdentityMap.this .clear();
481: }
482:
483: public String toString() {
484: return WeakIdentityMap.this .toString(this );
485: }
486: };
487: }
488: return this .keySet;
489: }
490:
491: public Collection values() {
492: if (this .values == null) {
493: this .values = new AbstractCollection() {
494: public Iterator iterator() {
495: return createHashIterator(VALUES);
496: }
497:
498: public int size() {
499: return WeakIdentityMap.this .count;
500: }
501:
502: public boolean contains(Object o) {
503: return containsValue(o);
504: }
505:
506: public void clear() {
507: WeakIdentityMap.this .clear();
508: }
509:
510: public String toString() {
511: return WeakIdentityMap.this .toString(this );
512: }
513: };
514: }
515: return this .values;
516: }
517:
518: public Set entrySet() {
519: if (this .entrySet == null) {
520: this .entrySet = new AbstractSet() {
521: public Iterator iterator() {
522: return createHashIterator(ENTRIES);
523: }
524:
525: public boolean contains(Object o) {
526: if (!(o instanceof Map.Entry)) {
527: return false;
528: }
529: Map.Entry entry = (Map.Entry) o;
530: Object key = entry.getKey();
531:
532: Entry[] tab = WeakIdentityMap.this .table;
533: int hash = System.identityHashCode(key);
534: int index = (hash & 0x7fffffff) % tab.length;
535:
536: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
537: Object entryKey = e.get();
538:
539: if (entryKey == null) {
540: // Clean up after a cleared Reference.
541: WeakIdentityMap.this .modCount++;
542: if (prev != null) {
543: prev.next = e.next;
544: } else {
545: tab[index] = e.next;
546: }
547: WeakIdentityMap.this .count--;
548: } else if (e.hash == hash && e.equals(entry)) {
549: return true;
550: } else {
551: prev = e;
552: }
553: }
554:
555: return false;
556: }
557:
558: public boolean remove(Object o) {
559: if (!(o instanceof Map.Entry)) {
560: return false;
561: }
562: Map.Entry entry = (Map.Entry) o;
563: Object key = entry.getKey();
564: Entry[] tab = WeakIdentityMap.this .table;
565: int hash = System.identityHashCode(key);
566: int index = (hash & 0x7fffffff) % tab.length;
567:
568: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
569: if (e.get() == null) {
570: // Clean up after a cleared Reference.
571: WeakIdentityMap.this .modCount++;
572: if (prev != null) {
573: prev.next = e.next;
574: } else {
575: tab[index] = e.next;
576: }
577: WeakIdentityMap.this .count--;
578: } else if (e.hash == hash && e.equals(entry)) {
579: WeakIdentityMap.this .modCount++;
580: if (prev != null) {
581: prev.next = e.next;
582: } else {
583: tab[index] = e.next;
584: }
585: WeakIdentityMap.this .count--;
586:
587: e.value = null;
588: return true;
589: } else {
590: prev = e;
591: }
592: }
593: return false;
594: }
595:
596: public int size() {
597: return WeakIdentityMap.this .count;
598: }
599:
600: public void clear() {
601: WeakIdentityMap.this .clear();
602: }
603:
604: public String toString() {
605: return WeakIdentityMap.toString(this );
606: }
607: };
608: }
609:
610: return this .entrySet;
611: }
612:
613: /**
614: * Gets the map as a String.
615: *
616: * @return a string version of the map
617: */
618: public String toString() {
619: return toString(this );
620: }
621:
622: private Iterator createHashIterator(int type) {
623: if (this .count == 0) {
624: return Collections.EMPTY_SET.iterator();
625: } else {
626: return new HashIterator(type);
627: }
628: }
629:
630: /**
631: * WeakIdentityMap collision list entry.
632: */
633: private static class Entry extends WeakReference implements
634: Map.Entry {
635: int hash;
636: Object value;
637: Entry next;
638:
639: Entry(int hash, Object key, ReferenceQueue queue, Object value,
640: Entry next) {
641: super (key, queue);
642: this .hash = hash;
643: this .value = value;
644: this .next = next;
645: }
646:
647: public void clear() {
648: // Do nothing if reference is explicity cleared. This prevents
649: // backdoor modification of map entries.
650: }
651:
652: public Object getKey() {
653: Object key = Entry.this .get();
654: return key == KeyFactory.NULL ? null : key;
655: }
656:
657: public Object getValue() {
658: return this .value;
659: }
660:
661: public Object setValue(Object value) {
662: Object oldValue = this .value;
663: this .value = value;
664: return oldValue;
665: }
666:
667: public boolean equals(Object obj) {
668: if (!(obj instanceof Map.Entry)) {
669: return false;
670: }
671: return equals((Map.Entry) obj);
672: }
673:
674: boolean equals(Map.Entry e) {
675: Object this Key = get();
676: if (this Key == null) {
677: return false;
678: } else if (this Key == KeyFactory.NULL) {
679: this Key = null;
680: }
681: return (this Key == e.getKey())
682: && (this .value == null ? e.getValue() == null
683: : this .value.equals(e.getValue()));
684: }
685:
686: public int hashCode() {
687: return this .hash
688: ^ (this .value == null ? 0 : this .value.hashCode());
689: }
690:
691: public String toString() {
692: return getKey() + "=" + this .value;
693: }
694:
695: protected Object copy(ReferenceQueue queue) {
696: return new Entry(this .hash, get(), queue, this .value,
697: (this .next == null ? null : (Entry) this .next
698: .copy(queue)));
699: }
700: }
701:
702: private class HashIterator implements Iterator {
703: private final int type;
704: private final Entry[] table;
705:
706: private int index;
707:
708: // To ensure that the iterator doesn't return cleared entries, keep a
709: // hard reference to the key. Its existence will prevent the weak
710: // key from being cleared.
711: Object entryKey;
712: Entry entry;
713:
714: Entry last;
715:
716: /**
717: * The modCount value that the iterator believes that the backing
718: * List should have. If this expectation is violated, the iterator
719: * has detected concurrent modification.
720: */
721: private int expectedModCount = WeakIdentityMap.this .modCount;
722:
723: HashIterator(int type) {
724: this .table = WeakIdentityMap.this .table;
725: this .type = type;
726: this .index = table.length;
727: }
728:
729: public boolean hasNext() {
730: while (this .entry == null
731: || (this .entryKey = this .entry.get()) == null) {
732: if (this .entry != null) {
733: // Clean up after a cleared Reference.
734: remove(this .entry);
735: this .entry = this .entry.next;
736: } else {
737: if (this .index <= 0) {
738: return false;
739: } else {
740: this .entry = this .table[--this .index];
741: }
742: }
743: }
744:
745: return true;
746: }
747:
748: public Object next() {
749: if (WeakIdentityMap.this .modCount != this .expectedModCount) {
750: throw new ConcurrentModificationException();
751: }
752:
753: if (!hasNext()) {
754: throw new NoSuchElementException();
755: }
756:
757: this .last = this .entry;
758: this .entry = this .entry.next;
759:
760: return this .type == KEYS ? this .last.getKey()
761: : (this .type == VALUES ? this .last.getValue()
762: : this .last);
763: }
764:
765: public void remove() {
766: if (this .last == null) {
767: throw new IllegalStateException();
768: }
769: if (WeakIdentityMap.this .modCount != this .expectedModCount) {
770: throw new ConcurrentModificationException();
771: }
772: remove(this .last);
773: this .last = null;
774: }
775:
776: private void remove(Entry toRemove) {
777: Entry[] tab = this .table;
778: int index = (toRemove.hash & 0x7fffffff) % tab.length;
779:
780: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
781: if (e == toRemove) {
782: WeakIdentityMap.this .modCount++;
783: expectedModCount++;
784: if (prev == null) {
785: tab[index] = e.next;
786: } else {
787: prev.next = e.next;
788: }
789: WeakIdentityMap.this .count--;
790: return;
791: } else {
792: prev = e;
793: }
794: }
795:
796: throw new ConcurrentModificationException();
797: }
798:
799: public String toString() {
800: if (this .last != null) {
801: return "Iterator[" + this .last + ']';
802: } else {
803: return "Iterator[]";
804: }
805: }
806: }
807: }
|