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 private transient Entry<K, V>[] table;
50 private transient int count;
51 private int threshold;
52 private final float loadFactor;
53 private transient volatile int modCount;
57 private transient Set<K> keySet;
58 private transient Set<Map.Entry<K, V>> entrySet;
59 private transient Collection<V> values;
62 * Constructs a new, empty map with the specified initial
63 * capacity and the specified load factor.
65 * @param initialCapacity the initial capacity of the HashMap.
66 * @param loadFactor the load factor of the HashMap
67 * @throws IllegalArgumentException if the initial capacity is less
68 * than zero, or if the load factor is nonpositive.
70 public ReferencedValueHashMap(int initialCapacity, float loadFactor) {
71 if (initialCapacity < 0) {
72 throw new IllegalArgumentException("Illegal Initial Capacity: "+
76 if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
77 throw new IllegalArgumentException("Illegal Load factor: "+
81 if (initialCapacity == 0) {
85 this.loadFactor = loadFactor;
86 this.table = new Entry[initialCapacity];
87 this.threshold = (int)(initialCapacity * loadFactor);
91 * Constructs a new, empty map with the specified initial capacity
92 * and default load factor, which is <tt>0.75</tt>.
94 * @param initialCapacity the initial capacity of the HashMap.
95 * @throws IllegalArgumentException if the initial capacity is less
98 public ReferencedValueHashMap(int initialCapacity) {
99 this(initialCapacity, 0.75f);
103 * Constructs a new, empty map with a default capacity and load
104 * factor, which is <tt>0.75</tt>.
106 public ReferencedValueHashMap() {
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>.
116 public ReferencedValueHashMap(Map<? extends K, ? extends V> t) {
117 this(Math.max(2 * t.size(), 11), 0.75f);
125 public boolean isEmpty() {
126 return this.count == 0;
129 public boolean containsValue(Object value) {
131 value = KeyFactory.NULL;
134 Entry[] tab = this.table;
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();
140 if (entryValue == null) {
141 // Clean up after a cleared Reference.
149 } else if (value.equals(entryValue)) {
160 public boolean containsKey(Object key) {
161 Entry<K, V>[] tab = this.table;
164 int hash = key.hashCode();
165 int index = (hash & 0x7fffffff) % tab.length;
166 for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
167 if (e.get() == null) {
168 // Clean up after a cleared Reference.
176 } else if (e.hash == hash && key.equals(e.key)) {
183 for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
184 if (e.get() == null) {
185 // Clean up after a cleared Reference.
193 } else if (e.key == null) {
204 public V get(Object key) {
205 Entry<K, V>[] tab = this.table;
208 int hash = key.hashCode();
209 int index = (hash & 0x7fffffff) % tab.length;
211 for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
212 V entryValue = e.get();
214 if (entryValue == null) {
215 // Clean up after a cleared Reference.
223 } else if (e.hash == hash && key.equals(e.key)) {
224 return (entryValue == KeyFactory.NULL) ? null : entryValue;
230 for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
231 V entryValue = e.get();
233 if (entryValue == null) {
234 // Clean up after a cleared Reference.
243 } else if (e.key == null) {
244 return (entryValue == KeyFactory.NULL) ? null : entryValue;
255 * Scans the contents of this map, removing all entries that have a
256 * cleared soft value.
258 private void cleanup() {
259 Entry<K, V>[] tab = this.table;
261 for (int i = tab.length ; i-- > 0 ;) {
262 for (Entry<K, V> e = tab[i], prev = null; e != null; e = e.next) {
263 if (e.get() == null) {
264 // Clean up after a cleared Reference.
280 * Rehashes the contents of this map into a new <tt>HashMap</tt> instance
281 * with a larger capacity. This method is called automatically when the
282 * number of keys in this map exceeds its capacity and load factor.
284 private void rehash() {
285 int oldCapacity = this.table.length;
286 Entry<K, V>[] oldMap = this.table;
288 int newCapacity = oldCapacity * 2 + 1;
289 Entry<K, V>[] newMap = new Entry[newCapacity];
292 this.threshold = (int)(newCapacity * this.loadFactor);
295 for (int i = oldCapacity ; i-- > 0 ;) {
296 for (Entry<K, V> old = oldMap[i] ; old != null ; ) {
300 // Only copy entry if its value hasn't been cleared.
301 if (e.get() == null) {
304 int index = (e.hash & 0x7fffffff) % newCapacity;
305 e.next = newMap[index];
312 public V put(K key, V value) {
314 value = (V) KeyFactory.NULL;
317 // Makes sure the key is not already in the HashMap.
318 Entry<K, V>[] tab = this.table;
323 hash = key.hashCode();
324 index = (hash & 0x7fffffff) % tab.length;
325 for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
326 V entryValue = e.get();
328 if (entryValue == null) {
329 // Clean up after a cleared Reference.
337 } else if (e.hash == hash && key.equals(e.key)) {
339 return (entryValue == KeyFactory.NULL) ? null : entryValue;
347 for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
348 V entryValue = e.get();
350 if (entryValue == null) {
351 // Clean up after a cleared Reference.
359 } else if (e.key == null) {
361 return (entryValue == KeyFactory.NULL) ? null : entryValue;
370 if (this.count >= this.threshold) {
371 // Cleanup the table if the threshold is exceeded.
375 if (this.count >= this.threshold) {
376 // Rehash the table if the threshold is still exceeded.
379 index = (hash & 0x7fffffff) % tab.length;
382 // Creates the new entry.
383 Entry<K, V> e = newEntry(hash, key, (V)value, tab[index]);
389 public V remove(Object key) {
390 Entry<K, V>[] tab = this.table;
393 int hash = key.hashCode();
394 int index = (hash & 0x7fffffff) % tab.length;
396 for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
397 V entryValue = e.get();
399 if (entryValue == null) {
400 // Clean up after a cleared Reference.
408 } else if (e.hash == hash && key.equals(e.key)) {
418 return (entryValue == KeyFactory.NULL) ? null : entryValue;
424 for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
425 V entryValue = e.get();
427 if (entryValue == null) {
428 // Clean up after a cleared Reference.
436 } else if (e.key == null) {
446 return (entryValue == KeyFactory.NULL) ? null : entryValue;
456 public void putAll(Map<? extends K, ? extends V> t) {
457 Iterator i = t.entrySet().iterator();
458 while (i.hasNext()) {
459 Map.Entry<K, V> e = (Map.Entry<K, V>) i.next();
460 put(e.getKey(), e.getValue());
464 public void clear() {
465 Entry[] tab = this.table;
467 for (int index = tab.length; --index >= 0; ) {
473 public Object clone() {
475 ReferencedValueHashMap t = (ReferencedValueHashMap)super.clone();
476 t.table = new Entry[this.table.length];
477 for (int i = this.table.length ; i-- > 0 ; ) {
478 t.table[i] = (this.table[i] != null)
479 ? (Entry)this.table[i].clone() : null;
486 } catch (CloneNotSupportedException e) {
487 // this shouldn't happen, since we are Cloneable
488 throw new InternalError();
492 public Set<K> keySet() {
493 if (this.keySet == null) {
494 this.keySet = new AbstractSet<K>() {
495 public Iterator iterator() {
496 return createHashIterator(WeakIdentityMap.KEYS);
499 return ReferencedValueHashMap.this.count;
501 public boolean contains(Object o) {
502 return containsKey(o);
504 public boolean remove(Object o) {
506 if (ReferencedValueHashMap.this.containsKey(null)) {
507 ReferencedValueHashMap.this.remove(null);
513 return ReferencedValueHashMap.this.remove(o) != null;
516 public void clear() {
517 ReferencedValueHashMap.this.clear();
519 public String toString() {
520 return WeakIdentityMap.toString(this);
527 public Collection<V> values() {
528 if (this.values==null) {
529 this.values = new AbstractCollection<V>() {
530 public Iterator iterator() {
531 return createHashIterator(WeakIdentityMap.VALUES);
534 return ReferencedValueHashMap.this.count;
536 public boolean contains(Object o) {
537 return containsValue(o);
539 public void clear() {
540 ReferencedValueHashMap.this.clear();
542 public String toString() {
543 return WeakIdentityMap.toString(this);
550 public Set<Map.Entry<K, V>> entrySet() {
551 if (this.entrySet==null) {
552 this.entrySet = new AbstractSet<Map.Entry<K, V>>() {
553 public Iterator iterator() {
554 return createHashIterator(WeakIdentityMap.ENTRIES);
557 public boolean contains(Object o) {
558 if (!(o instanceof Map.Entry)) {
561 Map.Entry entry = (Map.Entry)o;
562 Object key = entry.getKey();
564 Entry[] tab = ReferencedValueHashMap.this.table;
565 int hash = key == null ? 0 : key.hashCode();
566 int index = (hash & 0x7fffffff) % tab.length;
568 for (Entry e = tab[index], prev = null; e != null; e = e.next) {
569 Object entryValue = e.get();
571 if (entryValue == null) {
572 // Clean up after a cleared Reference.
573 ReferencedValueHashMap.this.modCount++;
579 ReferencedValueHashMap.this.count--;
580 } else if (e.hash == hash && e.equals(entry)) {
590 public boolean remove(Object o) {
591 if (!(o instanceof Map.Entry)) {
594 Map.Entry entry = (Map.Entry)o;
595 Object key = entry.getKey();
596 Entry[] tab = ReferencedValueHashMap.this.table;
597 int hash = key == null ? 0 : key.hashCode();
598 int index = (hash & 0x7fffffff) % tab.length;
600 for (Entry e = tab[index], prev = null; e != null; e = e.next) {
601 Object entryValue = e.get();
603 if (entryValue == null) {
604 // Clean up after a cleared Reference.
605 ReferencedValueHashMap.this.modCount++;
611 ReferencedValueHashMap.this.count--;
612 } else if (e.hash == hash && e.equals(entry)) {
613 ReferencedValueHashMap.this.modCount++;
619 ReferencedValueHashMap.this.count--;
631 return ReferencedValueHashMap.this.count;
634 public void clear() {
635 ReferencedValueHashMap.this.clear();
638 public String toString() {
639 return WeakIdentityMap.toString(this);
644 return this.entrySet;
647 public String toString() {
648 // Cleanup stale entries first, so as not to allocate a larger than
649 // necessary StringBuffer.
651 return WeakIdentityMap.toString(this);
654 abstract Entry<K, V> newEntry(int hash, K key, V value, Entry<K, V> next);
656 private Iterator createHashIterator(int type) {
657 if (this.count == 0) {
658 return Collections.EMPTY_SET.iterator();
660 return new HashIterator(type);
665 * Collision list entry.
667 abstract static class Entry<K, V> implements Map.Entry<K, V> {
672 private Reference<V> value;
674 Entry(int hash, K key, V value, Entry<K, V> next) {
677 this.value = newReference(value);
681 Entry(int hash, K key, Reference<V> value, Entry<K, V> next) {
694 public V getValue() {
695 V value = this.value.get();
696 return value == KeyFactory.NULL ? null : value;
699 public V setValue(V value) {
700 V oldValue = getValue();
701 this.value = newReference(value == null ? ((V) KeyFactory.NULL) : value);
705 public boolean equals(Object obj) {
706 if (!(obj instanceof Map.Entry)) {
709 return equals((Map.Entry)obj);
712 boolean equals(Map.Entry e) {
713 Object thisValue = get();
714 if (thisValue == null) {
716 } else if (thisValue == KeyFactory.NULL) {
719 return (this.key == null ? e.getKey() == null : this.key.equals(e.getKey())) &&
720 (thisValue == null ? e.getValue() == null : thisValue.equals(e.getValue()));
723 public int hashCode() {
724 return this.hash ^ get().hashCode();
727 public String toString() {
728 return this.key + "=" + getValue();
731 protected Object clone() {
732 return newEntry(this.hash, this.key, (Reference)this.value,
733 (this.next == null ? null : (Entry)this.next.clone()));
736 abstract Entry newEntry(int hash, K key, Reference<V> value, Entry<K, V> next);
738 abstract Reference<V> newReference(V value);
740 // Like getValue(), except does not convert NULL to null.
742 return this.value.get();
746 private class HashIterator implements Iterator {
747 private final int type;
748 private final Entry[] table;
752 // To ensure that the iterator doesn't return cleared entries, keep a
753 // hard reference to the value. Its existence will prevent the soft
754 // value from being cleared.
755 private Object entryValue;
761 * The modCount value that the iterator believes that the backing
762 * List should have. If this expectation is violated, the iterator
763 * has detected concurrent modification.
765 private int expectedModCount = ReferencedValueHashMap.this.modCount;
767 HashIterator(int type) {
768 this.table = ReferencedValueHashMap.this.table;
770 this.index = table.length;
773 public boolean hasNext() {
774 while (this.entry == null || (this.entryValue = this.entry.get()) == null) {
775 if (this.entry != null) {
776 // Clean up after a cleared Reference.
778 this.entry = this.entry.next;
781 if (this.entry == null) {
782 if (this.index <= 0) {
785 this.entry = this.table[--this.index];
793 public Object next() {
794 if (ReferencedValueHashMap.this.modCount != expectedModCount) {
795 throw new ConcurrentModificationException();
799 throw new NoSuchElementException();
802 this.last = this.entry;
803 this.entry = this.entry.next;
805 return this.type == WeakIdentityMap.KEYS ? this.last.getKey() :
806 (this.type == WeakIdentityMap.VALUES ? this.last.getValue() : this.last);
809 public void remove() {
810 if (this.last == null) {
811 throw new IllegalStateException();
813 if (ReferencedValueHashMap.this.modCount != expectedModCount) {
814 throw new ConcurrentModificationException();
820 private void remove(Entry toRemove) {
821 Entry[] tab = this.table;
822 int index = (toRemove.hash & 0x7fffffff) % tab.length;
824 for (Entry e = tab[index], prev = null; e != null; e = e.next) {
826 ReferencedValueHashMap.this.modCount++;
833 ReferencedValueHashMap.this.count--;
839 throw new ConcurrentModificationException();