2 * Copyright 2006-2010 Brian S O'Neill
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 package org.cojen.util;
19 import java.lang.ref.Reference;
20 import java.util.AbstractCollection;
21 import java.util.AbstractMap;
22 import java.util.AbstractSet;
23 import java.util.Collection;
24 import java.util.Collections;
25 import java.util.ConcurrentModificationException;
26 import java.util.Iterator;
28 import java.util.NoSuchElementException;
32 * A Map that references its values and can be used as a simple cache.
33 * Instances are not thread-safe and must be wrapped with
34 * Collections.synchronizedMap to be made thread-safe.
36 * Note: Referenced entries may be automatically removed during
37 * either accessor or mutator operations, possibly causing a concurrent
38 * modification to be detected. Therefore, even if multiple threads are only
39 * accessing this map, be sure to synchronize this map first. Also, do not
40 * rely on the value returned by size() when using an iterator from this map.
41 * The iterators may return less entries than the amount reported by size().
43 * @author Brian S O'Neill
45 @SuppressWarnings({ "rawtypes", "unused", "unchecked" })
46 public abstract class ReferencedValueHashMap<K, V> extends AbstractMap<K, V>
47 implements Map<K, V>, Cloneable
49 static final Object NULL = new Comparable() {
50 public int compareTo(Object obj) {
51 return obj == this || obj == null ? 0 : 1;
55 private transient Entry<K, V>[] table;
56 private transient int count;
57 private int threshold;
58 private final float loadFactor;
59 private transient volatile int modCount;
63 private transient Set<K> keySet;
64 private transient Set<Map.Entry<K, V>> entrySet;
65 private transient Collection<V> values;
68 * Constructs a new, empty map with the specified initial
69 * capacity and the specified load factor.
71 * @param initialCapacity the initial capacity of the HashMap.
72 * @param loadFactor the load factor of the HashMap
73 * @throws IllegalArgumentException if the initial capacity is less
74 * than zero, or if the load factor is nonpositive.
76 public ReferencedValueHashMap(int initialCapacity, float loadFactor) {
77 if (initialCapacity < 0) {
78 throw new IllegalArgumentException("Illegal Initial Capacity: "+
82 if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
83 throw new IllegalArgumentException("Illegal Load factor: "+
87 if (initialCapacity == 0) {
91 this.loadFactor = loadFactor;
92 this.table = new Entry[initialCapacity];
93 this.threshold = (int)(initialCapacity * loadFactor);
97 * Constructs a new, empty map with the specified initial capacity
98 * and default load factor, which is <tt>0.75</tt>.
100 * @param initialCapacity the initial capacity of the HashMap.
101 * @throws IllegalArgumentException if the initial capacity is less
104 public ReferencedValueHashMap(int initialCapacity) {
105 this(initialCapacity, 0.75f);
109 * Constructs a new, empty map with a default capacity and load
110 * factor, which is <tt>0.75</tt>.
112 public ReferencedValueHashMap() {
117 * Constructs a new map with the same mappings as the given map. The
118 * map is created with a capacity of twice the number of mappings in
119 * the given map or 11 (whichever is greater), and a default load factor,
120 * which is <tt>0.75</tt>.
122 public ReferencedValueHashMap(Map<? extends K, ? extends V> t) {
123 this(Math.max(2 * t.size(), 11), 0.75f);
131 public boolean isEmpty() {
132 return this.count == 0;
135 public boolean containsValue(Object value) {
140 Entry[] tab = this.table;
142 for (int i = tab.length ; i-- > 0 ;) {
143 for (Entry e = tab[i], prev = null; e != null; e = e.next) {
144 Object entryValue = e.get();
146 if (entryValue == null) {
147 // Clean up after a cleared Reference.
155 } else if (value.equals(entryValue)) {
166 public boolean containsKey(Object key) {
167 Entry<K, V>[] tab = this.table;
170 int hash = key.hashCode();
171 int index = (hash & 0x7fffffff) % tab.length;
172 for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
173 if (e.get() == null) {
174 // Clean up after a cleared Reference.
182 } else if (e.hash == hash && key.equals(e.key)) {
189 for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
190 if (e.get() == null) {
191 // Clean up after a cleared Reference.
199 } else if (e.key == null) {
210 public V get(Object key) {
211 Entry<K, V>[] tab = this.table;
214 int hash = key.hashCode();
215 int index = (hash & 0x7fffffff) % tab.length;
217 for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
218 V entryValue = e.get();
220 if (entryValue == null) {
221 // Clean up after a cleared Reference.
229 } else if (e.hash == hash && key.equals(e.key)) {
230 return (entryValue == NULL) ? null : entryValue;
236 for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
237 V entryValue = e.get();
239 if (entryValue == null) {
240 // Clean up after a cleared Reference.
249 } else if (e.key == null) {
250 return (entryValue == NULL) ? null : entryValue;
261 * Scans the contents of this map, removing all entries that have a
262 * cleared soft value.
264 private void cleanup() {
265 Entry<K, V>[] tab = this.table;
267 for (int i = tab.length ; i-- > 0 ;) {
268 for (Entry<K, V> e = tab[i], prev = null; e != null; e = e.next) {
269 if (e.get() == null) {
270 // Clean up after a cleared Reference.
286 * Rehashes the contents of this map into a new <tt>HashMap</tt> instance
287 * with a larger capacity. This method is called automatically when the
288 * number of keys in this map exceeds its capacity and load factor.
290 private void rehash() {
291 int oldCapacity = this.table.length;
292 Entry<K, V>[] oldMap = this.table;
294 int newCapacity = oldCapacity * 2 + 1;
295 Entry<K, V>[] newMap = new Entry[newCapacity];
298 this.threshold = (int)(newCapacity * this.loadFactor);
301 for (int i = oldCapacity ; i-- > 0 ;) {
302 for (Entry<K, V> old = oldMap[i] ; old != null ; ) {
306 // Only copy entry if its value hasn't been cleared.
307 if (e.get() == null) {
310 int index = (e.hash & 0x7fffffff) % newCapacity;
311 e.next = newMap[index];
318 public V put(K key, V value) {
323 // Makes sure the key is not already in the HashMap.
324 Entry<K, V>[] tab = this.table;
329 hash = key.hashCode();
330 index = (hash & 0x7fffffff) % tab.length;
331 for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
332 V entryValue = e.get();
334 if (entryValue == null) {
335 // Clean up after a cleared Reference.
343 } else if (e.hash == hash && key.equals(e.key)) {
345 return (entryValue == NULL) ? null : entryValue;
353 for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
354 V entryValue = e.get();
356 if (entryValue == null) {
357 // Clean up after a cleared Reference.
365 } else if (e.key == null) {
367 return (entryValue == NULL) ? null : entryValue;
376 if (this.count >= this.threshold) {
377 // Cleanup the table if the threshold is exceeded.
381 if (this.count >= this.threshold) {
382 // Rehash the table if the threshold is still exceeded.
385 index = (hash & 0x7fffffff) % tab.length;
388 // Creates the new entry.
389 Entry<K, V> e = newEntry(hash, key, (V)value, tab[index]);
395 public V remove(Object key) {
396 Entry<K, V>[] tab = this.table;
399 int hash = key.hashCode();
400 int index = (hash & 0x7fffffff) % tab.length;
402 for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
403 V entryValue = e.get();
405 if (entryValue == null) {
406 // Clean up after a cleared Reference.
414 } else if (e.hash == hash && key.equals(e.key)) {
424 return (entryValue == NULL) ? null : entryValue;
430 for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
431 V entryValue = e.get();
433 if (entryValue == null) {
434 // Clean up after a cleared Reference.
442 } else if (e.key == null) {
452 return (entryValue == NULL) ? null : entryValue;
462 public void putAll(Map<? extends K, ? extends V> t) {
463 Iterator i = t.entrySet().iterator();
464 while (i.hasNext()) {
465 Map.Entry<K, V> e = (Map.Entry<K, V>) i.next();
466 put(e.getKey(), e.getValue());
470 public void clear() {
471 Entry[] tab = this.table;
473 for (int index = tab.length; --index >= 0; ) {
479 public Object clone() {
481 ReferencedValueHashMap t = (ReferencedValueHashMap)super.clone();
482 t.table = new Entry[this.table.length];
483 for (int i = this.table.length ; i-- > 0 ; ) {
484 t.table[i] = (this.table[i] != null)
485 ? (Entry)this.table[i].clone() : null;
492 } catch (CloneNotSupportedException e) {
493 // this shouldn't happen, since we are Cloneable
494 throw new InternalError();
498 public Set<K> keySet() {
499 if (this.keySet == null) {
500 this.keySet = new AbstractSet<K>() {
501 public Iterator iterator() {
502 return createHashIterator(WeakIdentityMap.KEYS);
505 return ReferencedValueHashMap.this.count;
507 public boolean contains(Object o) {
508 return containsKey(o);
510 public boolean remove(Object o) {
512 if (ReferencedValueHashMap.this.containsKey(null)) {
513 ReferencedValueHashMap.this.remove(null);
519 return ReferencedValueHashMap.this.remove(o) != null;
522 public void clear() {
523 ReferencedValueHashMap.this.clear();
525 public String toString() {
526 return WeakIdentityMap.toString(this);
533 public Collection<V> values() {
534 if (this.values==null) {
535 this.values = new AbstractCollection<V>() {
536 public Iterator iterator() {
537 return createHashIterator(WeakIdentityMap.VALUES);
540 return ReferencedValueHashMap.this.count;
542 public boolean contains(Object o) {
543 return containsValue(o);
545 public void clear() {
546 ReferencedValueHashMap.this.clear();
548 public String toString() {
549 return WeakIdentityMap.toString(this);
556 public Set<Map.Entry<K, V>> entrySet() {
557 if (this.entrySet==null) {
558 this.entrySet = new AbstractSet<Map.Entry<K, V>>() {
559 public Iterator iterator() {
560 return createHashIterator(WeakIdentityMap.ENTRIES);
563 public boolean contains(Object o) {
564 if (!(o instanceof Map.Entry)) {
567 Map.Entry entry = (Map.Entry)o;
568 Object key = entry.getKey();
570 Entry[] tab = ReferencedValueHashMap.this.table;
571 int hash = key == null ? 0 : key.hashCode();
572 int index = (hash & 0x7fffffff) % tab.length;
574 for (Entry e = tab[index], prev = null; e != null; e = e.next) {
575 Object entryValue = e.get();
577 if (entryValue == null) {
578 // Clean up after a cleared Reference.
579 ReferencedValueHashMap.this.modCount++;
585 ReferencedValueHashMap.this.count--;
586 } else if (e.hash == hash && e.equals(entry)) {
596 public boolean remove(Object o) {
597 if (!(o instanceof Map.Entry)) {
600 Map.Entry entry = (Map.Entry)o;
601 Object key = entry.getKey();
602 Entry[] tab = ReferencedValueHashMap.this.table;
603 int hash = key == null ? 0 : key.hashCode();
604 int index = (hash & 0x7fffffff) % tab.length;
606 for (Entry e = tab[index], prev = null; e != null; e = e.next) {
607 Object entryValue = e.get();
609 if (entryValue == null) {
610 // Clean up after a cleared Reference.
611 ReferencedValueHashMap.this.modCount++;
617 ReferencedValueHashMap.this.count--;
618 } else if (e.hash == hash && e.equals(entry)) {
619 ReferencedValueHashMap.this.modCount++;
625 ReferencedValueHashMap.this.count--;
637 return ReferencedValueHashMap.this.count;
640 public void clear() {
641 ReferencedValueHashMap.this.clear();
644 public String toString() {
645 return WeakIdentityMap.toString(this);
650 return this.entrySet;
653 public String toString() {
654 // Cleanup stale entries first, so as not to allocate a larger than
655 // necessary StringBuffer.
657 return WeakIdentityMap.toString(this);
660 abstract Entry<K, V> newEntry(int hash, K key, V value, Entry<K, V> next);
662 private Iterator createHashIterator(int type) {
663 if (this.count == 0) {
664 return Collections.EMPTY_SET.iterator();
666 return new HashIterator(type);
671 * Collision list entry.
673 abstract static class Entry<K, V> implements Map.Entry<K, V> {
678 private Reference<V> value;
680 Entry(int hash, K key, V value, Entry<K, V> next) {
683 this.value = newReference(value);
687 Entry(int hash, K key, Reference<V> value, Entry<K, V> next) {
700 public V getValue() {
701 V value = this.value.get();
702 return value == NULL ? null : value;
705 public V setValue(V value) {
706 V oldValue = getValue();
707 this.value = newReference(value == null ? ((V) NULL) : value);
711 public boolean equals(Object obj) {
712 if (!(obj instanceof Map.Entry)) {
715 return equals((Map.Entry)obj);
718 boolean equals(Map.Entry e) {
719 Object thisValue = get();
720 if (thisValue == null) {
722 } else if (thisValue == NULL) {
725 return (this.key == null ? e.getKey() == null : this.key.equals(e.getKey())) &&
726 (thisValue == null ? e.getValue() == null : thisValue.equals(e.getValue()));
729 public int hashCode() {
730 return this.hash ^ get().hashCode();
733 public String toString() {
734 return this.key + "=" + getValue();
737 protected Object clone() {
738 return newEntry(this.hash, this.key, (Reference)this.value,
739 (this.next == null ? null : (Entry)this.next.clone()));
742 abstract Entry newEntry(int hash, K key, Reference<V> value, Entry<K, V> next);
744 abstract Reference<V> newReference(V value);
746 // Like getValue(), except does not convert NULL to null.
748 return this.value.get();
752 private class HashIterator implements Iterator {
753 private final int type;
754 private final Entry[] table;
758 // To ensure that the iterator doesn't return cleared entries, keep a
759 // hard reference to the value. Its existence will prevent the soft
760 // value from being cleared.
761 private Object entryValue;
767 * The modCount value that the iterator believes that the backing
768 * List should have. If this expectation is violated, the iterator
769 * has detected concurrent modification.
771 private int expectedModCount = ReferencedValueHashMap.this.modCount;
773 HashIterator(int type) {
774 this.table = ReferencedValueHashMap.this.table;
776 this.index = table.length;
779 public boolean hasNext() {
780 while (this.entry == null || (this.entryValue = this.entry.get()) == null) {
781 if (this.entry != null) {
782 // Clean up after a cleared Reference.
784 this.entry = this.entry.next;
787 if (this.entry == null) {
788 if (this.index <= 0) {
791 this.entry = this.table[--this.index];
799 public Object next() {
800 if (ReferencedValueHashMap.this.modCount != expectedModCount) {
801 throw new ConcurrentModificationException();
805 throw new NoSuchElementException();
808 this.last = this.entry;
809 this.entry = this.entry.next;
811 return this.type == WeakIdentityMap.KEYS ? this.last.getKey() :
812 (this.type == WeakIdentityMap.VALUES ? this.last.getValue() : this.last);
815 public void remove() {
816 if (this.last == null) {
817 throw new IllegalStateException();
819 if (ReferencedValueHashMap.this.modCount != expectedModCount) {
820 throw new ConcurrentModificationException();
826 private void remove(Entry toRemove) {
827 Entry[] tab = this.table;
828 int index = (toRemove.hash & 0x7fffffff) % tab.length;
830 for (Entry e = tab[index], prev = null; e != null; e = e.next) {
832 ReferencedValueHashMap.this.modCount++;
839 ReferencedValueHashMap.this.count--;
845 throw new ConcurrentModificationException();