001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package java.util;
019:
020: import java.lang.ref.ReferenceQueue;
021: import java.lang.ref.WeakReference;
022:
023: /**
024: * WeakHashMap is an implementation of Map with keys which are WeakReferences.
025: * The key/value mapping is removed when the key is no longer referenced. All
026: * optional operations are supported, adding and removing. Keys and values can
027: * be any objects.
028: *
029: * @since 1.2
030: * @see HashMap
031: * @see WeakReference
032: */
033: public class WeakHashMap<K, V> extends AbstractMap<K, V> implements
034: Map<K, V> {
035:
036: private static final int DEFAULT_SIZE = 16;
037:
038: private final ReferenceQueue<K> referenceQueue;
039:
040: int elementCount;
041:
042: Entry<K, V>[] elementData;
043:
044: private final int loadFactor;
045:
046: private int threshold;
047:
048: volatile int modCount;
049:
050: // Simple utility method to isolate unchecked cast for array creation
051: @SuppressWarnings("unchecked")
052: private static <K, V> Entry<K, V>[] newEntryArray(int size) {
053: return new Entry[size];
054: }
055:
056: private static final class Entry<K, V> extends WeakReference<K>
057: implements Map.Entry<K, V> {
058: int hash;
059:
060: boolean isNull;
061:
062: V value;
063:
064: Entry<K, V> next;
065:
066: interface Type<R, K, V> {
067: R get(Map.Entry<K, V> entry);
068: }
069:
070: Entry(K key, V object, ReferenceQueue<K> queue) {
071: super (key, queue);
072: isNull = key == null;
073: hash = isNull ? 0 : key.hashCode();
074: value = object;
075: }
076:
077: public K getKey() {
078: return super .get();
079: }
080:
081: public V getValue() {
082: return value;
083: }
084:
085: public V setValue(V object) {
086: V result = value;
087: value = object;
088: return result;
089: }
090:
091: @Override
092: public boolean equals(Object other) {
093: if (!(other instanceof Map.Entry)) {
094: return false;
095: }
096: Map.Entry<?, ?> entry = (Map.Entry<?, ?>) other;
097: Object key = super .get();
098: return (key == null ? key == entry.getKey() : key
099: .equals(entry.getKey()))
100: && (value == null ? value == entry.getValue()
101: : value.equals(entry.getValue()));
102: }
103:
104: @Override
105: public int hashCode() {
106: return hash + (value == null ? 0 : value.hashCode());
107: }
108:
109: @Override
110: public String toString() {
111: return super .get() + "=" + value; //$NON-NLS-1$
112: }
113: }
114:
115: class HashIterator<R> implements Iterator<R> {
116: private int position = 0, expectedModCount;
117:
118: private Entry<K, V> currentEntry, nextEntry;
119:
120: private K nextKey;
121:
122: final Entry.Type<R, K, V> type;
123:
124: HashIterator(Entry.Type<R, K, V> type) {
125: this .type = type;
126: expectedModCount = modCount;
127: }
128:
129: public boolean hasNext() {
130: if (nextEntry != null
131: && (nextKey != null || nextEntry.isNull)) {
132: return true;
133: }
134: while (true) {
135: if (nextEntry == null) {
136: while (position < elementData.length) {
137: if ((nextEntry = elementData[position++]) != null) {
138: break;
139: }
140: }
141: if (nextEntry == null) {
142: return false;
143: }
144: }
145: // ensure key of next entry is not gc'ed
146: nextKey = nextEntry.get();
147: if (nextKey != null || nextEntry.isNull) {
148: return true;
149: }
150: nextEntry = nextEntry.next;
151: }
152: }
153:
154: public R next() {
155: if (expectedModCount == modCount) {
156: if (hasNext()) {
157: currentEntry = nextEntry;
158: nextEntry = currentEntry.next;
159: R result = type.get(currentEntry);
160: // free the key
161: nextKey = null;
162: return result;
163: }
164: throw new NoSuchElementException();
165: }
166: throw new ConcurrentModificationException();
167: }
168:
169: public void remove() {
170: if (expectedModCount == modCount) {
171: if (currentEntry != null) {
172: removeEntry(currentEntry);
173: currentEntry = null;
174: expectedModCount++;
175: // cannot poll() as that would change the expectedModCount
176: } else {
177: throw new IllegalStateException();
178: }
179: } else {
180: throw new ConcurrentModificationException();
181: }
182: }
183: }
184:
185: /**
186: * Constructs a new empty instance of WeakHashMap.
187: */
188: public WeakHashMap() {
189: this (DEFAULT_SIZE);
190: }
191:
192: /**
193: * Constructs a new instance of WeakHashMap with the specified capacity.
194: *
195: * @param capacity
196: * the initial capacity of this WeakHashMap
197: *
198: * @exception IllegalArgumentException
199: * when the capacity is less than zero
200: */
201: public WeakHashMap(int capacity) {
202: if (capacity >= 0) {
203: elementCount = 0;
204: elementData = newEntryArray(capacity == 0 ? 1 : capacity);
205: loadFactor = 7500; // Default load factor of 0.75
206: computeMaxSize();
207: referenceQueue = new ReferenceQueue<K>();
208: } else {
209: throw new IllegalArgumentException();
210: }
211: }
212:
213: /**
214: * Constructs a new instance of WeakHashMap with the specified capacity and
215: * load factor.
216: *
217: * @param capacity
218: * the initial capacity
219: * @param loadFactor
220: * the initial load factor
221: *
222: * @exception IllegalArgumentException
223: * when the capacity is less than zero or the load factor is
224: * less or equal to zero
225: */
226: public WeakHashMap(int capacity, float loadFactor) {
227: if (capacity >= 0 && loadFactor > 0) {
228: elementCount = 0;
229: elementData = newEntryArray(capacity == 0 ? 1 : capacity);
230: this .loadFactor = (int) (loadFactor * 10000);
231: computeMaxSize();
232: referenceQueue = new ReferenceQueue<K>();
233: } else {
234: throw new IllegalArgumentException();
235: }
236: }
237:
238: /**
239: * Constructs a new instance of HashMap containing the mappings from the
240: * specified Map.
241: *
242: * @param map
243: * the mappings to add
244: */
245: public WeakHashMap(Map<? extends K, ? extends V> map) {
246: this (map.size() < 6 ? 11 : map.size() * 2);
247: putAllImpl(map);
248: }
249:
250: /**
251: * Removes all mappings from this WeakHashMap, leaving it empty.
252: *
253: * @see #isEmpty
254: * @see #size
255: */
256: @Override
257: public void clear() {
258: if (elementCount > 0) {
259: elementCount = 0;
260: Arrays.fill(elementData, null);
261: modCount++;
262: while (referenceQueue.poll() != null) {
263: // do nothing
264: }
265: }
266: }
267:
268: private void computeMaxSize() {
269: threshold = (int) ((long) elementData.length * loadFactor / 10000);
270: }
271:
272: /**
273: * Searches this WeakHashMap for the specified key.
274: *
275: * @param key
276: * the object to search for
277: * @return true if <code>key</code> is a key of this WeakHashMap, false
278: * otherwise
279: */
280: @Override
281: public boolean containsKey(Object key) {
282: return getEntry(key) != null;
283: }
284:
285: /**
286: * Answers a Set of the mappings contained in this WeakHashMap. Each element
287: * in the set is a Map.Entry. The set is backed by this WeakHashMap so
288: * changes to one are reflected by the other. The set does not support
289: * adding.
290: *
291: * @return a Set of the mappings
292: */
293: @Override
294: public Set<Map.Entry<K, V>> entrySet() {
295: poll();
296: return new AbstractSet<Map.Entry<K, V>>() {
297: @Override
298: public int size() {
299: return WeakHashMap.this .size();
300: }
301:
302: @Override
303: public void clear() {
304: WeakHashMap.this .clear();
305: }
306:
307: @Override
308: public boolean remove(Object object) {
309: if (contains(object)) {
310: WeakHashMap.this .remove(((Map.Entry<?, ?>) object)
311: .getKey());
312: return true;
313: }
314: return false;
315: }
316:
317: @Override
318: public boolean contains(Object object) {
319: if (object instanceof Map.Entry) {
320: Entry<?, ?> entry = getEntry(((Map.Entry<?, ?>) object)
321: .getKey());
322: if (entry != null) {
323: Object key = entry.get();
324: if (key != null || entry.isNull) {
325: return object.equals(entry);
326: }
327: }
328: }
329: return false;
330: }
331:
332: @Override
333: public Iterator<Map.Entry<K, V>> iterator() {
334: return new HashIterator<Map.Entry<K, V>>(
335: new Entry.Type<Map.Entry<K, V>, K, V>() {
336: public Map.Entry<K, V> get(
337: Map.Entry<K, V> entry) {
338: return entry;
339: }
340: });
341: }
342: };
343: }
344:
345: /**
346: * Answers a Set of the keys contained in this WeakHashMap. The set is
347: * backed by this WeakHashMap so changes to one are reflected by the other.
348: * The set does not support adding.
349: *
350: * @return a Set of the keys
351: */
352: @Override
353: public Set<K> keySet() {
354: poll();
355: if (keySet == null) {
356: keySet = new AbstractSet<K>() {
357: @Override
358: public boolean contains(Object object) {
359: return containsKey(object);
360: }
361:
362: @Override
363: public int size() {
364: return WeakHashMap.this .size();
365: }
366:
367: @Override
368: public void clear() {
369: WeakHashMap.this .clear();
370: }
371:
372: @Override
373: public boolean remove(Object key) {
374: if (containsKey(key)) {
375: WeakHashMap.this .remove(key);
376: return true;
377: }
378: return false;
379: }
380:
381: @Override
382: public Iterator<K> iterator() {
383: return new HashIterator<K>(
384: new Entry.Type<K, K, V>() {
385: public K get(Map.Entry<K, V> entry) {
386: return entry.getKey();
387: }
388: });
389: }
390:
391: @Override
392: public Object[] toArray() {
393: Collection<K> coll = new ArrayList<K>(size());
394:
395: for (Iterator<K> iter = iterator(); iter.hasNext();) {
396: coll.add(iter.next());
397: }
398: return coll.toArray();
399: }
400:
401: @Override
402: public <T> T[] toArray(T[] contents) {
403: Collection<K> coll = new ArrayList<K>(size());
404:
405: for (Iterator<K> iter = iterator(); iter.hasNext();) {
406: coll.add(iter.next());
407: }
408: return coll.toArray(contents);
409: }
410: };
411: }
412: return keySet;
413: }
414:
415: /**
416: * Answers a Collection of the values contained in this WeakHashMap. The
417: * collection is backed by this WeakHashMap so changes to one are reflected
418: * by the other. The collection does not support adding.
419: *
420: * @return a Collection of the values
421: */
422: @Override
423: public Collection<V> values() {
424: poll();
425: if (valuesCollection == null) {
426: valuesCollection = new AbstractCollection<V>() {
427: @Override
428: public int size() {
429: return WeakHashMap.this .size();
430: }
431:
432: @Override
433: public void clear() {
434: WeakHashMap.this .clear();
435: }
436:
437: @Override
438: public boolean contains(Object object) {
439: return containsValue(object);
440: }
441:
442: @Override
443: public Iterator<V> iterator() {
444: return new HashIterator<V>(
445: new Entry.Type<V, K, V>() {
446: public V get(Map.Entry<K, V> entry) {
447: return entry.getValue();
448: }
449: });
450: }
451: };
452: }
453: return valuesCollection;
454: }
455:
456: /**
457: * Answers the value of the mapping with the specified key.
458: *
459: * @param key
460: * the key
461: * @return the value of the mapping with the specified key
462: */
463: @Override
464: public V get(Object key) {
465: poll();
466: if (key != null) {
467: int index = (key.hashCode() & 0x7FFFFFFF)
468: % elementData.length;
469: Entry<K, V> entry = elementData[index];
470: while (entry != null) {
471: if (key.equals(entry.get())) {
472: return entry.value;
473: }
474: entry = entry.next;
475: }
476: return null;
477: }
478: Entry<K, V> entry = elementData[0];
479: while (entry != null) {
480: if (entry.isNull) {
481: return entry.value;
482: }
483: entry = entry.next;
484: }
485: return null;
486: }
487:
488: Entry<K, V> getEntry(Object key) {
489: poll();
490: if (key != null) {
491: int index = (key.hashCode() & 0x7FFFFFFF)
492: % elementData.length;
493: Entry<K, V> entry = elementData[index];
494: while (entry != null) {
495: if (key.equals(entry.get())) {
496: return entry;
497: }
498: entry = entry.next;
499: }
500: return null;
501: }
502: Entry<K, V> entry = elementData[0];
503: while (entry != null) {
504: if (entry.isNull) {
505: return entry;
506: }
507: entry = entry.next;
508: }
509: return null;
510: }
511:
512: /**
513: * Searches this WeakHashMap for the specified value, and returns true, if
514: * at least one entry has this object as its value.
515: *
516: * @param value
517: * the object to search for
518: * @return true if <code>value</code> is a value in this WeakHashMap,
519: * false otherwise
520: */
521: @Override
522: public boolean containsValue(Object value) {
523: poll();
524: if (value != null) {
525: for (int i = elementData.length; --i >= 0;) {
526: Entry<K, V> entry = elementData[i];
527: while (entry != null) {
528: K key = entry.get();
529: if ((key != null || entry.isNull)
530: && value.equals(entry.value)) {
531: return true;
532: }
533: entry = entry.next;
534: }
535: }
536: } else {
537: for (int i = elementData.length; --i >= 0;) {
538: Entry<K, V> entry = elementData[i];
539: while (entry != null) {
540: K key = entry.get();
541: if ((key != null || entry.isNull)
542: && entry.value == null) {
543: return true;
544: }
545: entry = entry.next;
546: }
547: }
548: }
549: return false;
550: }
551:
552: /**
553: * Answers if this WeakHashMap has no elements, a size of zero.
554: *
555: * @return true if this HashMap has no elements, false otherwise
556: *
557: * @see #size
558: */
559: @Override
560: public boolean isEmpty() {
561: return size() == 0;
562: }
563:
564: @SuppressWarnings("unchecked")
565: void poll() {
566: Entry<K, V> toRemove;
567: while ((toRemove = (Entry<K, V>) referenceQueue.poll()) != null) {
568: removeEntry(toRemove);
569: }
570: }
571:
572: void removeEntry(Entry<K, V> toRemove) {
573: Entry<K, V> entry, last = null;
574: int index = (toRemove.hash & 0x7FFFFFFF) % elementData.length;
575: entry = elementData[index];
576: // Ignore queued entries which cannot be found, the user could
577: // have removed them before they were queued, i.e. using clear()
578: while (entry != null) {
579: if (toRemove == entry) {
580: modCount++;
581: if (last == null) {
582: elementData[index] = entry.next;
583: } else {
584: last.next = entry.next;
585: }
586: elementCount--;
587: break;
588: }
589: last = entry;
590: entry = entry.next;
591: }
592: }
593:
594: /**
595: * Maps the specified key to the specified value.
596: *
597: * @param key
598: * the key
599: * @param value
600: * the value
601: * @return the value of any previous mapping with the specified key or null
602: * if there was no mapping
603: */
604: @Override
605: public V put(K key, V value) {
606: poll();
607: int index = 0;
608: Entry<K, V> entry;
609: if (key != null) {
610: index = (key.hashCode() & 0x7FFFFFFF) % elementData.length;
611: entry = elementData[index];
612: while (entry != null && !key.equals(entry.get())) {
613: entry = entry.next;
614: }
615: } else {
616: entry = elementData[0];
617: while (entry != null && !entry.isNull) {
618: entry = entry.next;
619: }
620: }
621: if (entry == null) {
622: modCount++;
623: if (++elementCount > threshold) {
624: rehash();
625: index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
626: % elementData.length;
627: }
628: entry = new Entry<K, V>(key, value, referenceQueue);
629: entry.next = elementData[index];
630: elementData[index] = entry;
631: return null;
632: }
633: V result = entry.value;
634: entry.value = value;
635: return result;
636: }
637:
638: private void rehash() {
639: int length = elementData.length << 1;
640: if (length == 0) {
641: length = 1;
642: }
643: Entry<K, V>[] newData = newEntryArray(length);
644: for (int i = 0; i < elementData.length; i++) {
645: Entry<K, V> entry = elementData[i];
646: while (entry != null) {
647: int index = entry.isNull ? 0
648: : (entry.hash & 0x7FFFFFFF) % length;
649: Entry<K, V> next = entry.next;
650: entry.next = newData[index];
651: newData[index] = entry;
652: entry = next;
653: }
654: }
655: elementData = newData;
656: computeMaxSize();
657: }
658:
659: /**
660: * Copies all the mappings in the given map to this map. These mappings will
661: * replace all mappings that this map had for any of the keys currently in
662: * the given map.
663: *
664: * @param map
665: * the Map to copy mappings from
666: * @throws NullPointerException
667: * if the given map is null
668: */
669: @Override
670: public void putAll(Map<? extends K, ? extends V> map) {
671: putAllImpl(map);
672: }
673:
674: /**
675: * Removes a mapping with the specified key from this WeakHashMap.
676: *
677: * @param key
678: * the key of the mapping to remove
679: * @return the value of the removed mapping or null if key is not a key in
680: * this WeakHashMap
681: */
682: @Override
683: public V remove(Object key) {
684: poll();
685: int index = 0;
686: Entry<K, V> entry, last = null;
687: if (key != null) {
688: index = (key.hashCode() & 0x7FFFFFFF) % elementData.length;
689: entry = elementData[index];
690: while (entry != null && !key.equals(entry.get())) {
691: last = entry;
692: entry = entry.next;
693: }
694: } else {
695: entry = elementData[0];
696: while (entry != null && !entry.isNull) {
697: last = entry;
698: entry = entry.next;
699: }
700: }
701: if (entry != null) {
702: modCount++;
703: if (last == null) {
704: elementData[index] = entry.next;
705: } else {
706: last.next = entry.next;
707: }
708: elementCount--;
709: return entry.value;
710: }
711: return null;
712: }
713:
714: /**
715: * Answers the number of mappings in this WeakHashMap.
716: *
717: * @return the number of mappings in this WeakHashMap
718: */
719: @Override
720: public int size() {
721: poll();
722: return elementCount;
723: }
724:
725: private void putAllImpl(Map<? extends K, ? extends V> map) {
726: if (map.entrySet() != null) {
727: super.putAll(map);
728: }
729: }
730: }
|