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.SoftReference;
021: import java.util.AbstractCollection;
022: import java.util.AbstractMap;
023: import java.util.AbstractSet;
024: import java.util.Collection;
025: import java.util.Collections;
026: import java.util.ConcurrentModificationException;
027: import java.util.Iterator;
028: import java.util.Map;
029: import java.util.NoSuchElementException;
030: import java.util.Set;
031:
032: /**
033: * A Map that softly references its values and can be used as a simple cache.
034: * SoftValuedHashMap is not thread-safe and must be wrapped with
035: * Collections.synchronizedMap to be made thread-safe.
036: * <p>
037: * Note: Softly referenced entries may be automatically removed during
038: * either accessor or mutator operations, possibly causing a concurrent
039: * modification to be detected. Therefore, even if multiple threads are only
040: * accessing this map, be sure to synchronize this map first. Also, do not
041: * rely on the value returned by size() when using an iterator from this map.
042: * The iterators may return less entries than the amount reported by size().
043: *
044: * @author Brian S O'Neill
045: */
046: public class SoftValuedHashMap extends AbstractMap implements Map,
047: Cloneable {
048:
049: private transient Entry[] table;
050: private transient int count;
051: private int threshold;
052: private final float loadFactor;
053: private transient volatile int modCount;
054:
055: // Views
056:
057: private transient Set keySet;
058: private transient Set entrySet;
059: private transient Collection values;
060:
061: /**
062: * Constructs a new, empty map with the specified initial
063: * capacity and the specified load factor.
064: *
065: * @param initialCapacity the initial capacity of the HashMap.
066: * @param loadFactor the load factor of the HashMap
067: * @throws IllegalArgumentException if the initial capacity is less
068: * than zero, or if the load factor is nonpositive.
069: */
070: public SoftValuedHashMap(int initialCapacity, float loadFactor) {
071: if (initialCapacity < 0) {
072: throw new IllegalArgumentException(
073: "Illegal Initial Capacity: " + initialCapacity);
074: }
075:
076: if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
077: throw new IllegalArgumentException("Illegal Load factor: "
078: + loadFactor);
079: }
080:
081: if (initialCapacity == 0) {
082: initialCapacity = 1;
083: }
084:
085: this .loadFactor = loadFactor;
086: this .table = new Entry[initialCapacity];
087: this .threshold = (int) (initialCapacity * loadFactor);
088: }
089:
090: /**
091: * Constructs a new, empty map with the specified initial capacity
092: * and default load factor, which is <tt>0.75</tt>.
093: *
094: * @param initialCapacity the initial capacity of the HashMap.
095: * @throws IllegalArgumentException if the initial capacity is less
096: * than zero.
097: */
098: public SoftValuedHashMap(int initialCapacity) {
099: this (initialCapacity, 0.75f);
100: }
101:
102: /**
103: * Constructs a new, empty map with a default capacity and load
104: * factor, which is <tt>0.75</tt>.
105: */
106: public SoftValuedHashMap() {
107: this (11, 0.75f);
108: }
109:
110: /**
111: * Constructs a new map with the same mappings as the given map. The
112: * map is created with a capacity of twice the number of mappings in
113: * the given map or 11 (whichever is greater), and a default load factor,
114: * which is <tt>0.75</tt>.
115: */
116: public SoftValuedHashMap(Map t) {
117: this (Math.max(2 * t.size(), 11), 0.75f);
118: putAll(t);
119: }
120:
121: public int size() {
122: return this .count;
123: }
124:
125: public boolean isEmpty() {
126: return this .count == 0;
127: }
128:
129: public boolean containsValue(Object value) {
130: if (value == null) {
131: value = KeyFactory.NULL;
132: }
133:
134: Entry[] tab = this .table;
135:
136: for (int i = tab.length; i-- > 0;) {
137: for (Entry e = tab[i], prev = null; e != null; e = e.next) {
138: Object entryValue = e.get();
139:
140: if (entryValue == null) {
141: // Clean up after a cleared Reference.
142: this .modCount++;
143: if (prev != null) {
144: prev.next = e.next;
145: } else {
146: tab[i] = e.next;
147: }
148: this .count--;
149: } else if (value.equals(entryValue)) {
150: return true;
151: } else {
152: prev = e;
153: }
154: }
155: }
156:
157: return false;
158: }
159:
160: public boolean containsKey(Object key) {
161: Entry[] tab = this .table;
162:
163: if (key != null) {
164: int hash = key.hashCode();
165: int index = (hash & 0x7fffffff) % tab.length;
166: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
167: if (e.get() == null) {
168: // Clean up after a cleared Reference.
169: this .modCount++;
170: if (prev != null) {
171: prev.next = e.next;
172: } else {
173: tab[index] = e.next;
174: }
175: this .count--;
176: } else if (e.hash == hash && key.equals(e.key)) {
177: return true;
178: } else {
179: prev = e;
180: }
181: }
182: } else {
183: for (Entry e = tab[0], prev = null; e != null; e = e.next) {
184: if (e.get() == null) {
185: // Clean up after a cleared Reference.
186: this .modCount++;
187: if (prev != null) {
188: prev.next = e.next;
189: } else {
190: tab[0] = e.next;
191: }
192: this .count--;
193: } else if (e.key == null) {
194: return true;
195: } else {
196: prev = e;
197: }
198: }
199: }
200:
201: return false;
202: }
203:
204: public Object get(Object key) {
205: Entry[] tab = this .table;
206:
207: if (key != null) {
208: int hash = key.hashCode();
209: int index = (hash & 0x7fffffff) % tab.length;
210:
211: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
212: Object entryValue = e.get();
213:
214: if (entryValue == null) {
215: // Clean up after a cleared Reference.
216: this .modCount++;
217: if (prev != null) {
218: prev.next = e.next;
219: } else {
220: tab[index] = e.next;
221: }
222: count--;
223: } else if (e.hash == hash && key.equals(e.key)) {
224: return (entryValue == KeyFactory.NULL) ? null
225: : entryValue;
226: } else {
227: prev = e;
228: }
229: }
230: } else {
231: for (Entry e = tab[0], prev = null; e != null; e = e.next) {
232: Object entryValue = e.get();
233:
234: if (entryValue == null) {
235: // Clean up after a cleared Reference.
236: this .modCount++;
237: if (prev != null) {
238: prev.next = e.next;
239: } else {
240: tab[0] = e.next;
241: }
242: this .count--;
243: } else if (e.key == null) {
244: return (entryValue == KeyFactory.NULL) ? null
245: : entryValue;
246: } else {
247: prev = e;
248: }
249: }
250: }
251:
252: return null;
253: }
254:
255: /**
256: * Scans the contents of this map, removing all entries that have a
257: * cleared soft value.
258: */
259: private void cleanup() {
260: Entry[] tab = this .table;
261:
262: for (int i = tab.length; i-- > 0;) {
263: for (Entry e = tab[i], prev = null; e != null; e = e.next) {
264: if (e.get() == null) {
265: // Clean up after a cleared Reference.
266: this .modCount++;
267: if (prev != null) {
268: prev.next = e.next;
269: } else {
270: tab[i] = e.next;
271: }
272: this .count--;
273: } else {
274: prev = e;
275: }
276: }
277: }
278: }
279:
280: /**
281: * Rehashes the contents of this map into a new <tt>HashMap</tt> instance
282: * with a larger capacity. This method is called automatically when the
283: * number of keys in this map exceeds its capacity and load factor.
284: */
285: private void rehash() {
286: int oldCapacity = this .table.length;
287: Entry[] oldMap = this .table;
288:
289: int newCapacity = oldCapacity * 2 + 1;
290: Entry[] newMap = new Entry[newCapacity];
291:
292: this .modCount++;
293: this .threshold = (int) (newCapacity * this .loadFactor);
294: this .table = newMap;
295:
296: for (int i = oldCapacity; i-- > 0;) {
297: for (Entry old = oldMap[i]; old != null;) {
298: Entry e = old;
299: old = old.next;
300:
301: // Only copy entry if its value hasn't been cleared.
302: if (e.get() == null) {
303: this .count--;
304: } else {
305: int index = (e.hash & 0x7fffffff) % newCapacity;
306: e.next = newMap[index];
307: newMap[index] = e;
308: }
309: }
310: }
311: }
312:
313: public Object put(Object key, Object value) {
314: if (value == null) {
315: value = KeyFactory.NULL;
316: }
317:
318: // Makes sure the key is not already in the HashMap.
319: Entry[] tab = this .table;
320: int hash;
321: int index;
322:
323: if (key != null) {
324: hash = key.hashCode();
325: index = (hash & 0x7fffffff) % tab.length;
326: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
327: Object entryValue = e.get();
328:
329: if (entryValue == null) {
330: // Clean up after a cleared Reference.
331: this .modCount++;
332: if (prev != null) {
333: prev.next = e.next;
334: } else {
335: tab[index] = e.next;
336: }
337: this .count--;
338: } else if (e.hash == hash && key.equals(e.key)) {
339: e.setValue(value);
340: return (entryValue == KeyFactory.NULL) ? null
341: : entryValue;
342: } else {
343: prev = e;
344: }
345: }
346: } else {
347: hash = 0;
348: index = 0;
349: for (Entry e = tab[0], prev = null; e != null; e = e.next) {
350: Object entryValue = e.get();
351:
352: if (entryValue == null) {
353: // Clean up after a cleared Reference.
354: this .modCount++;
355: if (prev != null) {
356: prev.next = e.next;
357: } else {
358: tab[0] = e.next;
359: }
360: this .count--;
361: } else if (e.key == null) {
362: e.setValue(value);
363: return (entryValue == KeyFactory.NULL) ? null
364: : entryValue;
365: } else {
366: prev = e;
367: }
368: }
369: }
370:
371: this .modCount++;
372:
373: if (this .count >= this .threshold) {
374: // Cleanup the table if the threshold is exceeded.
375: cleanup();
376: }
377:
378: if (this .count >= this .threshold) {
379: // Rehash the table if the threshold is still exceeded.
380: rehash();
381: tab = this .table;
382: index = (hash & 0x7fffffff) % tab.length;
383: }
384:
385: // Creates the new entry.
386: Entry e = new Entry(hash, key, (Object) value, tab[index]);
387: tab[index] = e;
388: this .count++;
389: return null;
390: }
391:
392: public Object remove(Object key) {
393: Entry[] tab = this .table;
394:
395: if (key != null) {
396: int hash = key.hashCode();
397: int index = (hash & 0x7fffffff) % tab.length;
398:
399: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
400: Object entryValue = e.get();
401:
402: if (entryValue == null) {
403: // Clean up after a cleared Reference.
404: this .modCount++;
405: if (prev != null) {
406: prev.next = e.next;
407: } else {
408: tab[index] = e.next;
409: }
410: this .count--;
411: } else if (e.hash == hash && key.equals(e.key)) {
412: this .modCount++;
413: if (prev != null) {
414: prev.next = e.next;
415: } else {
416: tab[index] = e.next;
417: }
418: this .count--;
419:
420: e.setValue(null);
421: return (entryValue == KeyFactory.NULL) ? null
422: : entryValue;
423: } else {
424: prev = e;
425: }
426: }
427: } else {
428: for (Entry e = tab[0], prev = null; e != null; e = e.next) {
429: Object entryValue = e.get();
430:
431: if (entryValue == null) {
432: // Clean up after a cleared Reference.
433: this .modCount++;
434: if (prev != null) {
435: prev.next = e.next;
436: } else {
437: tab[0] = e.next;
438: }
439: this .count--;
440: } else if (e.key == null) {
441: this .modCount++;
442: if (prev != null) {
443: prev.next = e.next;
444: } else {
445: tab[0] = e.next;
446: }
447: this .count--;
448:
449: e.setValue(null);
450: return (entryValue == KeyFactory.NULL) ? null
451: : entryValue;
452: } else {
453: prev = e;
454: }
455: }
456: }
457:
458: return null;
459: }
460:
461: public void putAll(Map t) {
462: Iterator i = t.entrySet().iterator();
463: while (i.hasNext()) {
464: Map.Entry e = (Map.Entry) i.next();
465: put(e.getKey(), e.getValue());
466: }
467: }
468:
469: public void clear() {
470: Entry[] tab = this .table;
471: this .modCount++;
472: for (int index = tab.length; --index >= 0;) {
473: tab[index] = null;
474: }
475: this .count = 0;
476: }
477:
478: public Object clone() {
479: try {
480: SoftValuedHashMap t = (SoftValuedHashMap) super .clone();
481: t.table = new Entry[this .table.length];
482: for (int i = this .table.length; i-- > 0;) {
483: t.table[i] = (this .table[i] != null) ? (Entry) this .table[i]
484: .clone()
485: : null;
486: }
487: t.keySet = null;
488: t.entrySet = null;
489: t.values = null;
490: t.modCount = 0;
491: return t;
492: } catch (CloneNotSupportedException e) {
493: // this shouldn't happen, since we are Cloneable
494: throw new InternalError();
495: }
496: }
497:
498: public Set keySet() {
499: if (this .keySet == null) {
500: this .keySet = new AbstractSet() {
501: public Iterator iterator() {
502: return createHashIterator(WeakIdentityMap.KEYS);
503: }
504:
505: public int size() {
506: return SoftValuedHashMap.this .count;
507: }
508:
509: public boolean contains(Object o) {
510: return containsKey(o);
511: }
512:
513: public boolean remove(Object o) {
514: if (o == null) {
515: if (SoftValuedHashMap.this .containsKey(null)) {
516: SoftValuedHashMap.this .remove(null);
517: return true;
518: } else {
519: return false;
520: }
521: } else {
522: return SoftValuedHashMap.this .remove(o) != null;
523: }
524: }
525:
526: public void clear() {
527: SoftValuedHashMap.this .clear();
528: }
529:
530: public String toString() {
531: return WeakIdentityMap.toString(this );
532: }
533: };
534: }
535: return this .keySet;
536: }
537:
538: public Collection values() {
539: if (this .values == null) {
540: this .values = new AbstractCollection() {
541: public Iterator iterator() {
542: return createHashIterator(WeakIdentityMap.VALUES);
543: }
544:
545: public int size() {
546: return SoftValuedHashMap.this .count;
547: }
548:
549: public boolean contains(Object o) {
550: return containsValue(o);
551: }
552:
553: public void clear() {
554: SoftValuedHashMap.this .clear();
555: }
556:
557: public String toString() {
558: return WeakIdentityMap.toString(this );
559: }
560: };
561: }
562: return this .values;
563: }
564:
565: public Set entrySet() {
566: if (this .entrySet == null) {
567: this .entrySet = new AbstractSet() {
568: public Iterator iterator() {
569: return createHashIterator(WeakIdentityMap.ENTRIES);
570: }
571:
572: public boolean contains(Object o) {
573: if (!(o instanceof Map.Entry)) {
574: return false;
575: }
576: Map.Entry entry = (Map.Entry) o;
577: Object key = entry.getKey();
578:
579: Entry[] tab = SoftValuedHashMap.this .table;
580: int hash = key == null ? 0 : key.hashCode();
581: int index = (hash & 0x7fffffff) % tab.length;
582:
583: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
584: Object entryValue = e.get();
585:
586: if (entryValue == null) {
587: // Clean up after a cleared Reference.
588: SoftValuedHashMap.this .modCount++;
589: if (prev != null) {
590: prev.next = e.next;
591: } else {
592: tab[index] = e.next;
593: }
594: SoftValuedHashMap.this .count--;
595: } else if (e.hash == hash && e.equals(entry)) {
596: return true;
597: } else {
598: prev = e;
599: }
600: }
601:
602: return false;
603: }
604:
605: public boolean remove(Object o) {
606: if (!(o instanceof Map.Entry)) {
607: return false;
608: }
609: Map.Entry entry = (Map.Entry) o;
610: Object key = entry.getKey();
611: Entry[] tab = SoftValuedHashMap.this .table;
612: int hash = key == null ? 0 : key.hashCode();
613: int index = (hash & 0x7fffffff) % tab.length;
614:
615: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
616: Object entryValue = e.get();
617:
618: if (entryValue == null) {
619: // Clean up after a cleared Reference.
620: SoftValuedHashMap.this .modCount++;
621: if (prev != null) {
622: prev.next = e.next;
623: } else {
624: tab[index] = e.next;
625: }
626: SoftValuedHashMap.this .count--;
627: } else if (e.hash == hash && e.equals(entry)) {
628: SoftValuedHashMap.this .modCount++;
629: if (prev != null) {
630: prev.next = e.next;
631: } else {
632: tab[index] = e.next;
633: }
634: SoftValuedHashMap.this .count--;
635:
636: e.setValue(null);
637: return true;
638: } else {
639: prev = e;
640: }
641: }
642: return false;
643: }
644:
645: public int size() {
646: return SoftValuedHashMap.this .count;
647: }
648:
649: public void clear() {
650: SoftValuedHashMap.this .clear();
651: }
652:
653: public String toString() {
654: return WeakIdentityMap.toString(this );
655: }
656: };
657: }
658:
659: return this .entrySet;
660: }
661:
662: public String toString() {
663: // Cleanup stale entries first, so as not to allocate a larger than
664: // necessary StringBuffer.
665: cleanup();
666: return WeakIdentityMap.toString(this );
667: }
668:
669: private Iterator createHashIterator(int type) {
670: if (this .count == 0) {
671: return Collections.EMPTY_SET.iterator();
672: } else {
673: return new HashIterator(type);
674: }
675: }
676:
677: /**
678: * HashMap collision list entry.
679: */
680: private static class Entry implements Map.Entry {
681: int hash;
682: Object key;
683: Entry next;
684:
685: private Reference value;
686:
687: Entry(int hash, Object key, Object value, Entry next) {
688: this .hash = hash;
689: this .key = key;
690: this .value = new SoftReference(value);
691: this .next = next;
692: }
693:
694: private Entry(int hash, Object key, Reference value, Entry next) {
695: this .hash = hash;
696: this .key = key;
697: this .value = value;
698: this .next = next;
699: }
700:
701: // Map.Entry Ops
702:
703: public Object getKey() {
704: return this .key;
705: }
706:
707: public Object getValue() {
708: Object value = this .value.get();
709: return value == KeyFactory.NULL ? null : value;
710: }
711:
712: public Object setValue(Object value) {
713: Object oldValue = getValue();
714: this .value = new SoftReference(
715: value == null ? KeyFactory.NULL : value);
716: return oldValue;
717: }
718:
719: public boolean equals(Object obj) {
720: if (!(obj instanceof Map.Entry)) {
721: return false;
722: }
723: return equals((Map.Entry) obj);
724: }
725:
726: boolean equals(Map.Entry e) {
727: Object this Value = get();
728: if (this Value == null) {
729: return false;
730: } else if (this Value == KeyFactory.NULL) {
731: this Value = null;
732: }
733: return (this .key == null ? e.getKey() == null : this .key
734: .equals(e.getKey()))
735: && (this Value == null ? e.getValue() == null
736: : this Value.equals(e.getValue()));
737: }
738:
739: public int hashCode() {
740: return this .hash ^ get().hashCode();
741: }
742:
743: public String toString() {
744: return this .key + "=" + getValue();
745: }
746:
747: protected Object clone() {
748: return new Entry(this .hash, this .key,
749: (Reference) this .value, (this .next == null ? null
750: : (Entry) this .next.clone()));
751: }
752:
753: // Like getValue(), except does not convert NULL to null.
754: Object get() {
755: return this .value.get();
756: }
757: }
758:
759: private class HashIterator implements Iterator {
760: private final int type;
761: private final Entry[] table;
762:
763: private int index;
764:
765: // To ensure that the iterator doesn't return cleared entries, keep a
766: // hard reference to the value. Its existence will prevent the soft
767: // value from being cleared.
768: private Object entryValue;
769: private Entry entry;
770:
771: private Entry last;
772:
773: /**
774: * The modCount value that the iterator believes that the backing
775: * List should have. If this expectation is violated, the iterator
776: * has detected concurrent modification.
777: */
778: private int expectedModCount = SoftValuedHashMap.this .modCount;
779:
780: HashIterator(int type) {
781: this .table = SoftValuedHashMap.this .table;
782: this .type = type;
783: this .index = table.length;
784: }
785:
786: public boolean hasNext() {
787: while (this .entry == null
788: || (this .entryValue = this .entry.get()) == null) {
789: if (this .entry != null) {
790: // Clean up after a cleared Reference.
791: remove(this .entry);
792: this .entry = this .entry.next;
793: }
794:
795: if (this .entry == null) {
796: if (this .index <= 0) {
797: return false;
798: } else {
799: this .entry = this .table[--this .index];
800: }
801: }
802: }
803:
804: return true;
805: }
806:
807: public Object next() {
808: if (SoftValuedHashMap.this .modCount != expectedModCount) {
809: throw new ConcurrentModificationException();
810: }
811:
812: if (!hasNext()) {
813: throw new NoSuchElementException();
814: }
815:
816: this .last = this .entry;
817: this .entry = this .entry.next;
818:
819: return this .type == WeakIdentityMap.KEYS ? this .last
820: .getKey()
821: : (this .type == WeakIdentityMap.VALUES ? this .last
822: .getValue() : this .last);
823: }
824:
825: public void remove() {
826: if (this .last == null) {
827: throw new IllegalStateException();
828: }
829: if (SoftValuedHashMap.this .modCount != expectedModCount) {
830: throw new ConcurrentModificationException();
831: }
832: remove(this .last);
833: this .last = null;
834: }
835:
836: private void remove(Entry toRemove) {
837: Entry[] tab = this .table;
838: int index = (toRemove.hash & 0x7fffffff) % tab.length;
839:
840: for (Entry e = tab[index], prev = null; e != null; e = e.next) {
841: if (e == toRemove) {
842: SoftValuedHashMap.this .modCount++;
843: expectedModCount++;
844: if (prev == null) {
845: tab[index] = e.next;
846: } else {
847: prev.next = e.next;
848: }
849: SoftValuedHashMap.this .count--;
850: return;
851: } else {
852: prev = e;
853: }
854: }
855: throw new ConcurrentModificationException();
856: }
857: }
858: }
|