0001: /*
0002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
0003: *
0004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
0005: *
0006: * The contents of this file are subject to the terms of either the GNU
0007: * General Public License Version 2 only ("GPL") or the Common
0008: * Development and Distribution License("CDDL") (collectively, the
0009: * "License"). You may not use this file except in compliance with the
0010: * License. You can obtain a copy of the License at
0011: * http://www.netbeans.org/cddl-gplv2.html
0012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
0013: * specific language governing permissions and limitations under the
0014: * License. When distributing the software, include this License Header
0015: * Notice in each file and include the License file at
0016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
0017: * particular file as subject to the "Classpath" exception as provided
0018: * by Sun in the GPL Version 2 section of the License file that
0019: * accompanied this code. If applicable, add the following below the
0020: * License Header, with the fields enclosed by brackets [] replaced by
0021: * your own identifying information:
0022: * "Portions Copyrighted [year] [name of copyright owner]"
0023: *
0024: * Contributor(s):
0025: *
0026: * The Original Software is NetBeans. The Initial Developer of the Original
0027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2007 Sun
0028: * Microsystems, Inc. All Rights Reserved.
0029: *
0030: * If you wish your version of this file to be governed by only the CDDL
0031: * or only the GPL Version 2, indicate your decision by adding
0032: * "[Contributor] elects to include this software in this distribution
0033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
0034: * single choice of license, a recipient has the option to distribute
0035: * your version of this file under either the CDDL, the GPL Version 2 or
0036: * to extend the choice of license to its licensees as provided above.
0037: * However, if you add GPL Version 2 code and therefore, elected the GPL
0038: * Version 2 license, then the option applies only if the new code is
0039: * made subject to such option by the copyright holder.
0040: */
0041: /*
0042: * @(#)WeakSharedSet.java 0.2 07/02/26
0043: */
0044:
0045: package org.netbeans.modules.cnd.utils.cache;
0046:
0047: import java.io.IOException;
0048: import java.lang.ref.ReferenceQueue;
0049: import java.lang.ref.WeakReference;
0050: import java.util.AbstractCollection;
0051: import java.util.AbstractMap;
0052: import java.util.AbstractSet;
0053: import java.util.ArrayList;
0054: import java.util.Collection;
0055: import java.util.ConcurrentModificationException;
0056: import java.util.Iterator;
0057: import java.util.List;
0058: import java.util.Map;
0059: import java.util.NoSuchElementException;
0060: import java.util.Set;
0061:
0062: /**
0063: * This class provides storage functionality with Weak-referenced entries and
0064: * one new method <tt>addOrGet<tt> (backed by a hash table)
0065: * Access to set should be syncronized if used from different threads
0066: *
0067: * @see #addOrGet(Object)
0068: * @author Vladimir Voskresensky
0069: */
0070: @SuppressWarnings("unchecked")
0071: public class WeakSharedSet<E> extends AbstractSet<E> implements Set<E> {
0072: private final SharedKeyWeakHashMap<E, Boolean> m; // The backing map
0073: private transient Set<E> s; // Its keySet
0074:
0075: /**
0076: * Constructs a new, empty <tt>WeakSharedSet</tt> with the given initial
0077: * capacity and the given load factor.
0078: *
0079: * @param initialCapacity The initial capacity of the <tt>WeakSharedSet</tt>
0080: * @param loadFactor The load factor of the <tt>WeakSharedSet</tt>
0081: * @throws IllegalArgumentException if the initial capacity is negative,
0082: * or if the load factor is nonpositive.
0083: */
0084: public WeakSharedSet(int initialCapacity, float loadFactor) {
0085: m = new SharedKeyWeakHashMap<E, Boolean>(initialCapacity,
0086: loadFactor);
0087: s = m.keySet();
0088: }
0089:
0090: /**
0091: * Constructs a new, empty <tt>WeakSharedSet</tt> with the given initial
0092: * capacity and the default load factor (0.75).
0093: *
0094: * @param initialCapacity The initial capacity of the <tt>WeakSharedSet</tt>
0095: * @throws IllegalArgumentException if the initial capacity is negative
0096: */
0097: public WeakSharedSet(int initialCapacity) {
0098: this (initialCapacity, SharedKeyWeakHashMap.DEFAULT_LOAD_FACTOR);
0099: }
0100:
0101: /**
0102: * Constructs a new, empty <tt>WeakSharedSet</tt> with the default initial
0103: * capacity (16) and load factor (0.75).
0104: */
0105: public WeakSharedSet() {
0106: m = new SharedKeyWeakHashMap<E, Boolean>();
0107: s = m.keySet();
0108: }
0109:
0110: /**
0111: * Constructs a new <tt>WeakSharedSet</tt> with the same mappings as the
0112: * specified map. The <tt>WeakSharedSet</tt> is created with the default
0113: * load factor (0.75) and an initial capacity sufficient to hold the
0114: * mappings in the specified map.
0115: *
0116: * @param m the map whose mappings are to be placed in this map
0117: * @throws NullPointerException if the specified map is null
0118: */
0119: public WeakSharedSet(Set<? extends E> s) {
0120: this (
0121: Math
0122: .max(
0123: (int) (s.size() / SharedKeyWeakHashMap.DEFAULT_LOAD_FACTOR) + 1,
0124: 16),
0125: SharedKeyWeakHashMap.DEFAULT_LOAD_FACTOR);
0126: addAll(s);
0127: }
0128:
0129: @Override
0130: public void clear() {
0131: m.clear();
0132: }
0133:
0134: public int size() {
0135: return m.size();
0136: }
0137:
0138: @Override
0139: public boolean isEmpty() {
0140: return m.isEmpty();
0141: }
0142:
0143: @Override
0144: public boolean contains(Object o) {
0145: return m.containsKey(o);
0146: }
0147:
0148: @Override
0149: public boolean remove(Object o) {
0150: return m.remove(o) != null;
0151: }
0152:
0153: public void resize(int newCapacity) {
0154: if (size() == 0) {
0155: m.resize(newCapacity);
0156: }
0157: }
0158:
0159: /**
0160: * it is expected that method addOrGet is used instead of add
0161: */
0162: @Override
0163: public boolean add(E e) {
0164: return m.put(e, Boolean.TRUE) == null;
0165: }
0166:
0167: public Iterator<E> iterator() {
0168: return s.iterator();
0169: }
0170:
0171: @Override
0172: public Object[] toArray() {
0173: return s.toArray();
0174: }
0175:
0176: @Override
0177: public <T> T[] toArray(T[] a) {
0178: return s.toArray(a);
0179: }
0180:
0181: @Override
0182: public String toString() {
0183: return s.toString();
0184: }
0185:
0186: @Override
0187: public int hashCode() {
0188: return s.hashCode();
0189: }
0190:
0191: @Override
0192: public boolean equals(Object o) {
0193: return o == this || s.equals(o);
0194: }
0195:
0196: @Override
0197: public boolean containsAll(Collection<?> c) {
0198: return s.containsAll(c);
0199: }
0200:
0201: @Override
0202: public boolean removeAll(Collection<?> c) {
0203: return s.removeAll(c);
0204: }
0205:
0206: @Override
0207: public boolean retainAll(Collection<?> c) {
0208: return s.retainAll(c);
0209: }
0210:
0211: // addAll is the only inherited implementation
0212:
0213: /**
0214: * Put object in this set if equal one is not yet in set.
0215: * Returns previous set entry if equal object is already in set.
0216: *
0217: * @param e object to put in set.
0218: * @return the previous set entry equals with <tt>e</tt>, or
0219: * passed object <tt>e</tt> if there were not entry in set.
0220: */
0221: public E addOrGet(E e) {
0222: return m.putOrGet(e);
0223: }
0224:
0225: private static final long serialVersionUID = 2454657854757543876L;
0226:
0227: private void readObject(java.io.ObjectInputStream stream)
0228: throws IOException, ClassNotFoundException {
0229: stream.defaultReadObject();
0230: s = m.keySet();
0231: }
0232:
0233: // delegate class with only one special method putOrGet
0234: // all other is copied from java.util.WeakHashMap
0235: /**
0236: * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
0237: * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
0238: */
0239: private static class SharedKeyWeakHashMap<K, V> extends
0240: AbstractMap<K, V> implements Map<K, V> {
0241:
0242: /**
0243: * The default initial capacity -- MUST be a power of two.
0244: */
0245: private static final int DEFAULT_INITIAL_CAPACITY = 16;
0246:
0247: /**
0248: * The maximum capacity, used if a higher value is implicitly specified
0249: * by either of the constructors with arguments.
0250: * MUST be a power of two <= 1<<30.
0251: */
0252: private static final int MAXIMUM_CAPACITY = 1 << 30;
0253:
0254: /**
0255: * The load fast used when none specified in constructor.
0256: */
0257: private static final float DEFAULT_LOAD_FACTOR = 0.75f;
0258:
0259: /**
0260: * The table, resized as necessary. Length MUST Always be a power of two.
0261: */
0262: private Entry[] table;
0263:
0264: /**
0265: * The number of key-value mappings contained in this weak hash map.
0266: */
0267: private int size;
0268:
0269: /**
0270: * The next size value at which to resize (capacity * load factor).
0271: */
0272: private int threshold;
0273:
0274: /**
0275: * The load factor for the hash table.
0276: */
0277: private final float loadFactor;
0278:
0279: /**
0280: * Reference queue for cleared WeakEntries
0281: */
0282: private final ReferenceQueue<K> queue = new ReferenceQueue<K>();
0283:
0284: /**
0285: * The number of times this SharedKeyWeakHashMap has been structurally modified.
0286: * Structural modifications are those that change the number of
0287: * mappings in the map or otherwise modify its internal structure
0288: * (e.g., rehash). This field is used to make iterators on
0289: * Collection-views of the map fail-fast.
0290: *
0291: * @see ConcurrentModificationException
0292: */
0293: private volatile int modCount;
0294:
0295: /**
0296: * Constructs a new, empty <tt>SharedKeyWeakHashMap</tt> with the given initial
0297: * capacity and the given load factor.
0298: *
0299: * @param initialCapacity The initial capacity of the <tt>SharedKeyWeakHashMap</tt>
0300: * @param loadFactor The load factor of the <tt>SharedKeyWeakHashMap</tt>
0301: * @throws IllegalArgumentException if the initial capacity is negative,
0302: * or if the load factor is nonpositive.
0303: */
0304: public SharedKeyWeakHashMap(int initialCapacity,
0305: float loadFactor) {
0306: if (initialCapacity < 0)
0307: throw new IllegalArgumentException(
0308: "Illegal Initial Capacity: " + // NOI18N
0309: initialCapacity);
0310: if (initialCapacity > MAXIMUM_CAPACITY)
0311: initialCapacity = MAXIMUM_CAPACITY;
0312:
0313: if (loadFactor <= 0 || Float.isNaN(loadFactor))
0314: throw new IllegalArgumentException(
0315: "Illegal Load factor: " + // NOI18N
0316: loadFactor);
0317: int capacity = 1;
0318: while (capacity < initialCapacity)
0319: capacity <<= 1;
0320: table = new Entry[capacity];
0321: this .loadFactor = loadFactor;
0322: threshold = (int) (capacity * loadFactor);
0323: }
0324:
0325: /**
0326: * Constructs a new, empty <tt>SharedKeyWeakHashMap</tt> with the given initial
0327: * capacity and the default load factor (0.75).
0328: *
0329: * @param initialCapacity The initial capacity of the <tt>SharedKeyWeakHashMap</tt>
0330: * @throws IllegalArgumentException if the initial capacity is negative
0331: */
0332: public SharedKeyWeakHashMap(int initialCapacity) {
0333: this (initialCapacity, DEFAULT_LOAD_FACTOR);
0334: }
0335:
0336: /**
0337: * Constructs a new, empty <tt>SharedKeyWeakHashMap</tt> with the default initial
0338: * capacity (16) and load factor (0.75).
0339: */
0340: public SharedKeyWeakHashMap() {
0341: this .loadFactor = DEFAULT_LOAD_FACTOR;
0342: threshold = DEFAULT_INITIAL_CAPACITY;
0343: table = new Entry[DEFAULT_INITIAL_CAPACITY];
0344: }
0345:
0346: /**
0347: * Constructs a new <tt>SharedKeyWeakHashMap</tt> with the same mappings as the
0348: * specified map. The <tt>SharedKeyWeakHashMap</tt> is created with the default
0349: * load factor (0.75) and an initial capacity sufficient to hold the
0350: * mappings in the specified map.
0351: *
0352: * @param m the map whose mappings are to be placed in this map
0353: * @throws NullPointerException if the specified map is null
0354: * @since 1.3
0355: */
0356: public SharedKeyWeakHashMap(Map<? extends K, ? extends V> m) {
0357: this (Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
0358: 16), DEFAULT_LOAD_FACTOR);
0359: putAll(m);
0360: }
0361:
0362: // internal utilities
0363:
0364: /**
0365: * Value representing null keys inside tables.
0366: */
0367: private static final Object NULL_KEY = new Object();
0368:
0369: /**
0370: * Use NULL_KEY for key if it is null.
0371: */
0372: private static Object maskNull(Object key) {
0373: return (key == null ? NULL_KEY : key);
0374: }
0375:
0376: /**
0377: * Returns internal representation of null key back to caller as null.
0378: */
0379: private static <K> K unmaskNull(Object key) {
0380: return (K) (key == NULL_KEY ? null : key);
0381: }
0382:
0383: /**
0384: * Checks for equality of non-null reference x and possibly-null y. By
0385: * default uses Object.equals.
0386: */
0387: static boolean eq(Object x, Object y) {
0388: return x == y || x.equals(y);
0389: }
0390:
0391: /**
0392: * Returns index for hash code h.
0393: */
0394: static int indexFor(int h, int length) {
0395: return h & (length - 1);
0396: }
0397:
0398: /**
0399: * Expunges stale entries from the table.
0400: */
0401: private void expungeStaleEntries() {
0402: Entry<K, V> e;
0403: while ((e = (Entry<K, V>) queue.poll()) != null) {
0404: int h = e.hash;
0405: int i = indexFor(h, table.length);
0406:
0407: Entry<K, V> prev = table[i];
0408: Entry<K, V> p = prev;
0409: while (p != null) {
0410: Entry<K, V> next = p.next;
0411: if (p == e) {
0412: if (prev == e)
0413: table[i] = next;
0414: else
0415: prev.next = next;
0416: e.next = null; // Help GC
0417: e.value = null; // " "
0418: size--;
0419: break;
0420: }
0421: prev = p;
0422: p = next;
0423: }
0424: }
0425: }
0426:
0427: /**
0428: * Returns the table after first expunging stale entries.
0429: */
0430: private Entry[] getTable() {
0431: expungeStaleEntries();
0432: return table;
0433: }
0434:
0435: /**
0436: * Returns the number of key-value mappings in this map.
0437: * This result is a snapshot, and may not reflect unprocessed
0438: * entries that will be removed before next attempted access
0439: * because they are no longer referenced.
0440: */
0441: @Override
0442: public int size() {
0443: if (size == 0)
0444: return 0;
0445: expungeStaleEntries();
0446: return size;
0447: }
0448:
0449: /**
0450: * Returns <tt>true</tt> if this map contains no key-value mappings.
0451: * This result is a snapshot, and may not reflect unprocessed
0452: * entries that will be removed before next attempted access
0453: * because they are no longer referenced.
0454: */
0455: @Override
0456: public boolean isEmpty() {
0457: return size() == 0;
0458: }
0459:
0460: /**
0461: * Returns the value to which the specified key is mapped,
0462: * or {@code null} if this map contains no mapping for the key.
0463: *
0464: * <p>More formally, if this map contains a mapping from a key
0465: * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
0466: * key.equals(k))}, then this method returns {@code v}; otherwise
0467: * it returns {@code null}. (There can be at most one such mapping.)
0468: *
0469: * <p>A return value of {@code null} does not <i>necessarily</i>
0470: * indicate that the map contains no mapping for the key; it's also
0471: * possible that the map explicitly maps the key to {@code null}.
0472: * The {@link #containsKey containsKey} operation may be used to
0473: * distinguish these two cases.
0474: *
0475: * @see #put(Object, Object)
0476: */
0477: @Override
0478: public V get(Object key) {
0479: Object k = maskNull(key);
0480: int h = hash(k.hashCode());
0481: Entry[] tab = getTable();
0482: int index = indexFor(h, tab.length);
0483: Entry<K, V> e = tab[index];
0484: while (e != null) {
0485: if (e.hash == h && eq(k, e.get()))
0486: return e.value;
0487: e = e.next;
0488: }
0489: return null;
0490: }
0491:
0492: /**
0493: * Returns <tt>true</tt> if this map contains a mapping for the
0494: * specified key.
0495: *
0496: * @param key The key whose presence in this map is to be tested
0497: * @return <tt>true</tt> if there is a mapping for <tt>key</tt>;
0498: * <tt>false</tt> otherwise
0499: */
0500: @Override
0501: public boolean containsKey(Object key) {
0502: return getEntry(key) != null;
0503: }
0504:
0505: /**
0506: * Returns the entry associated with the specified key in this map.
0507: * Returns null if the map contains no mapping for this key.
0508: */
0509: Entry<K, V> getEntry(Object key) {
0510: Object k = maskNull(key);
0511: int h = hash(k.hashCode());
0512: Entry[] tab = getTable();
0513: int index = indexFor(h, tab.length);
0514: Entry<K, V> e = tab[index];
0515: while (e != null && !(e.hash == h && eq(k, e.get())))
0516: e = e.next;
0517: return e;
0518: }
0519:
0520: /**
0521: * Associates the specified value with the specified key in this map.
0522: * If the map previously contained a mapping for this key, the old
0523: * value is replaced.
0524: *
0525: * @param key key with which the specified value is to be associated.
0526: * @param value value to be associated with the specified key.
0527: * @return the previous value associated with <tt>key</tt>, or
0528: * <tt>null</tt> if there was no mapping for <tt>key</tt>.
0529: * (A <tt>null</tt> return can also indicate that the map
0530: * previously associated <tt>null</tt> with <tt>key</tt>.)
0531: */
0532: @Override
0533: public V put(K key, V value) {
0534: K k = (K) maskNull(key);
0535: int h = hash(k.hashCode());
0536: Entry[] tab = getTable();
0537: int i = indexFor(h, tab.length);
0538:
0539: for (Entry<K, V> e = tab[i]; e != null; e = e.next) {
0540: if (h == e.hash && eq(k, e.get())) {
0541: V oldValue = e.value;
0542: if (value != oldValue)
0543: e.value = value;
0544: return oldValue;
0545: }
0546: }
0547:
0548: modCount++;
0549: Entry<K, V> e = tab[i];
0550: tab[i] = new Entry<K, V>(k, value, queue, h, e);
0551: if (++size >= threshold)
0552: resize(tab.length * 2);
0553: return null;
0554: }
0555:
0556: /**
0557: * Rehashes the contents of this map into a new array with a
0558: * larger capacity. This method is called automatically when the
0559: * number of keys in this map reaches its threshold.
0560: *
0561: * If current capacity is MAXIMUM_CAPACITY, this method does not
0562: * resize the map, but sets threshold to Integer.MAX_VALUE.
0563: * This has the effect of preventing future calls.
0564: *
0565: * @param newCapacity the new capacity, MUST be a power of two;
0566: * must be greater than current capacity unless current
0567: * capacity is MAXIMUM_CAPACITY (in which case value
0568: * is irrelevant).
0569: */
0570: void resize(int newCapacity) {
0571: Entry[] oldTable = getTable();
0572: int oldCapacity = oldTable.length;
0573: if (oldCapacity == MAXIMUM_CAPACITY) {
0574: threshold = Integer.MAX_VALUE;
0575: return;
0576: }
0577:
0578: Entry[] newTable = new Entry[newCapacity];
0579: transfer(oldTable, newTable);
0580: table = newTable;
0581:
0582: /*
0583: * If ignoring null elements and processing ref queue caused massive
0584: * shrinkage, then restore old table. This should be rare, but avoids
0585: * unbounded expansion of garbage-filled tables.
0586: */
0587: if (size >= threshold / 2) {
0588: threshold = (int) (newCapacity * loadFactor);
0589: } else {
0590: expungeStaleEntries();
0591: transfer(newTable, oldTable);
0592: table = oldTable;
0593: }
0594: }
0595:
0596: /** Transfers all entries from src to dest tables */
0597: private void transfer(Entry[] src, Entry[] dest) {
0598: for (int j = 0; j < src.length; ++j) {
0599: Entry<K, V> e = src[j];
0600: src[j] = null;
0601: while (e != null) {
0602: Entry<K, V> next = e.next;
0603: Object key = e.get();
0604: if (key == null) {
0605: e.next = null; // Help GC
0606: e.value = null; // " "
0607: size--;
0608: } else {
0609: int i = indexFor(e.hash, dest.length);
0610: e.next = dest[i];
0611: dest[i] = e;
0612: }
0613: e = next;
0614: }
0615: }
0616: }
0617:
0618: /**
0619: * Copies all of the mappings from the specified map to this map.
0620: * These mappings will replace any mappings that this map had for any
0621: * of the keys currently in the specified map.
0622: *
0623: * @param m mappings to be stored in this map.
0624: * @throws NullPointerException if the specified map is null.
0625: */
0626: @Override
0627: public void putAll(Map<? extends K, ? extends V> m) {
0628: int numKeysToBeAdded = m.size();
0629: if (numKeysToBeAdded == 0)
0630: return;
0631:
0632: /*
0633: * Expand the map if the map if the number of mappings to be added
0634: * is greater than or equal to threshold. This is conservative; the
0635: * obvious condition is (m.size() + size) >= threshold, but this
0636: * condition could result in a map with twice the appropriate capacity,
0637: * if the keys to be added overlap with the keys already in this map.
0638: * By using the conservative calculation, we subject ourself
0639: * to at most one extra resize.
0640: */
0641: if (numKeysToBeAdded > threshold) {
0642: int targetCapacity = (int) (numKeysToBeAdded
0643: / loadFactor + 1);
0644: if (targetCapacity > MAXIMUM_CAPACITY)
0645: targetCapacity = MAXIMUM_CAPACITY;
0646: int newCapacity = table.length;
0647: while (newCapacity < targetCapacity)
0648: newCapacity <<= 1;
0649: if (newCapacity > table.length)
0650: resize(newCapacity);
0651: }
0652:
0653: for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
0654: put(e.getKey(), e.getValue());
0655: }
0656:
0657: /**
0658: * Removes the mapping for a key from this weak hash map if it is present.
0659: * More formally, if this map contains a mapping from key <tt>k</tt> to
0660: * value <tt>v</tt> such that <code>(key==null ? k==null :
0661: * key.equals(k))</code>, that mapping is removed. (The map can contain
0662: * at most one such mapping.)
0663: *
0664: * <p>Returns the value to which this map previously associated the key,
0665: * or <tt>null</tt> if the map contained no mapping for the key. A
0666: * return value of <tt>null</tt> does not <i>necessarily</i> indicate
0667: * that the map contained no mapping for the key; it's also possible
0668: * that the map explicitly mapped the key to <tt>null</tt>.
0669: *
0670: * <p>The map will not contain a mapping for the specified key once the
0671: * call returns.
0672: *
0673: * @param key key whose mapping is to be removed from the map
0674: * @return the previous value associated with <tt>key</tt>, or
0675: * <tt>null</tt> if there was no mapping for <tt>key</tt>
0676: */
0677: @Override
0678: public V remove(Object key) {
0679: Object k = maskNull(key);
0680: int h = hash(k.hashCode());
0681: Entry[] tab = getTable();
0682: int i = indexFor(h, tab.length);
0683: Entry<K, V> prev = tab[i];
0684: Entry<K, V> e = prev;
0685:
0686: while (e != null) {
0687: Entry<K, V> next = e.next;
0688: if (h == e.hash && eq(k, e.get())) {
0689: modCount++;
0690: size--;
0691: if (prev == e)
0692: tab[i] = next;
0693: else
0694: prev.next = next;
0695: return e.value;
0696: }
0697: prev = e;
0698: e = next;
0699: }
0700:
0701: return null;
0702: }
0703:
0704: /** Special version of remove needed by Entry set */
0705: Entry<K, V> removeMapping(Object o) {
0706: if (!(o instanceof Map.Entry))
0707: return null;
0708: Entry[] tab = getTable();
0709: Map.Entry entry = (Map.Entry) o;
0710: Object k = maskNull(entry.getKey());
0711: int h = hash(k.hashCode());
0712: int i = indexFor(h, tab.length);
0713: Entry<K, V> prev = tab[i];
0714: Entry<K, V> e = prev;
0715:
0716: while (e != null) {
0717: Entry<K, V> next = e.next;
0718: if (h == e.hash && e.equals(entry)) {
0719: modCount++;
0720: size--;
0721: if (prev == e)
0722: tab[i] = next;
0723: else
0724: prev.next = next;
0725: return e;
0726: }
0727: prev = e;
0728: e = next;
0729: }
0730:
0731: return null;
0732: }
0733:
0734: /**
0735: * Removes all of the mappings from this map.
0736: * The map will be empty after this call returns.
0737: */
0738: @Override
0739: public void clear() {
0740: // clear out ref queue. We don't need to expunge entries
0741: // since table is getting cleared.
0742: while (queue.poll() != null) {
0743: }
0744:
0745: modCount++;
0746: Entry[] tab = table;
0747: for (int i = 0; i < tab.length; ++i)
0748: tab[i] = null;
0749: size = 0;
0750:
0751: // Allocation of array may have caused GC, which may have caused
0752: // additional entries to go stale. Removing these entries from the
0753: // reference queue will make them eligible for reclamation.
0754: while (queue.poll() != null) {
0755: }
0756: }
0757:
0758: /**
0759: * Returns <tt>true</tt> if this map maps one or more keys to the
0760: * specified value.
0761: *
0762: * @param value value whose presence in this map is to be tested
0763: * @return <tt>true</tt> if this map maps one or more keys to the
0764: * specified value
0765: */
0766: @Override
0767: public boolean containsValue(Object value) {
0768: if (value == null)
0769: return containsNullValue();
0770:
0771: Entry[] tab = getTable();
0772: for (int i = tab.length; i-- > 0;) {
0773: for (Entry e = tab[i]; e != null; e = e.next) {
0774: if (value.equals(e.value)) {
0775: return true;
0776: }
0777: }
0778: }
0779: return false;
0780: }
0781:
0782: /**
0783: * Special-case code for containsValue with null argument
0784: */
0785: private boolean containsNullValue() {
0786: Entry[] tab = getTable();
0787: for (int i = tab.length; i-- > 0;) {
0788: for (Entry e = tab[i]; e != null; e = e.next) {
0789: if (e.value == null) {
0790: return true;
0791: }
0792: }
0793: }
0794: return false;
0795: }
0796:
0797: /**
0798: * The entries in this hash table extend WeakReference, using its main ref
0799: * field as the key.
0800: */
0801: private static class Entry<K, V> extends WeakReference<K>
0802: implements Map.Entry<K, V> {
0803: private V value;
0804: private final int hash;
0805: private Entry<K, V> next;
0806:
0807: /**
0808: * Creates new entry.
0809: */
0810: Entry(K key, V value, ReferenceQueue<K> queue, int hash,
0811: Entry<K, V> next) {
0812: super (key, queue);
0813: this .value = value;
0814: this .hash = hash;
0815: this .next = next;
0816: }
0817:
0818: public K getKey() {
0819: return SharedKeyWeakHashMap.<K> unmaskNull(get());
0820: }
0821:
0822: public V getValue() {
0823: return value;
0824: }
0825:
0826: public V setValue(V newValue) {
0827: V oldValue = value;
0828: value = newValue;
0829: return oldValue;
0830: }
0831:
0832: @Override
0833: public boolean equals(Object o) {
0834: if (!(o instanceof Map.Entry))
0835: return false;
0836: Map.Entry e = (Map.Entry) o;
0837: Object k1 = getKey();
0838: Object k2 = e.getKey();
0839: if (k1 == k2 || (k1 != null && k1.equals(k2))) {
0840: Object v1 = getValue();
0841: Object v2 = e.getValue();
0842: if (v1 == v2 || (v1 != null && v1.equals(v2)))
0843: return true;
0844: }
0845: return false;
0846: }
0847:
0848: @Override
0849: public int hashCode() {
0850: Object k = getKey();
0851: Object v = getValue();
0852: return ((k == null ? 0 : k.hashCode()) ^ (v == null ? 0
0853: : v.hashCode()));
0854: }
0855:
0856: @Override
0857: public String toString() {
0858: return getKey() + "=" + getValue(); // NOI18N
0859: }
0860: }
0861:
0862: /**
0863: * Have to copy AbstractMap.SimpleEntry,
0864: * since it appears only in jdk 1.6
0865: */
0866: public static class SimpleEntry<K, V> implements
0867: Map.Entry<K, V>, java.io.Serializable {
0868: private static final long serialVersionUID = -8499721149061103585L;
0869:
0870: private final K key;
0871: private V value;
0872:
0873: /**
0874: * Creates an entry representing a mapping from the specified
0875: * key to the specified value.
0876: *
0877: * @param key the key represented by this entry
0878: * @param value the value represented by this entry
0879: */
0880: public SimpleEntry(K key, V value) {
0881: this .key = key;
0882: this .value = value;
0883: }
0884:
0885: /**
0886: * Creates an entry representing the same mapping as the
0887: * specified entry.
0888: *
0889: * @param entry the entry to copy
0890: */
0891: public SimpleEntry(Map.Entry<? extends K, ? extends V> entry) {
0892: this .key = entry.getKey();
0893: this .value = entry.getValue();
0894: }
0895:
0896: /**
0897: * Returns the key corresponding to this entry.
0898: *
0899: * @return the key corresponding to this entry
0900: */
0901: public K getKey() {
0902: return key;
0903: }
0904:
0905: /**
0906: * Returns the value corresponding to this entry.
0907: *
0908: * @return the value corresponding to this entry
0909: */
0910: public V getValue() {
0911: return value;
0912: }
0913:
0914: /**
0915: * Replaces the value corresponding to this entry with the specified
0916: * value.
0917: *
0918: * @param value new value to be stored in this entry
0919: * @return the old value corresponding to the entry
0920: */
0921: public V setValue(V value) {
0922: V oldValue = this .value;
0923: this .value = value;
0924: return oldValue;
0925: }
0926:
0927: /**
0928: * Compares the specified object with this entry for equality.
0929: * Returns {@code true} if the given object is also a map entry and
0930: * the two entries represent the same mapping. More formally, two
0931: * entries {@code e1} and {@code e2} represent the same mapping
0932: * if<pre>
0933: * (e1.getKey()==null ?
0934: * e2.getKey()==null :
0935: * e1.getKey().equals(e2.getKey()))
0936: * &&
0937: * (e1.getValue()==null ?
0938: * e2.getValue()==null :
0939: * e1.getValue().equals(e2.getValue()))</pre>
0940: * This ensures that the {@code equals} method works properly across
0941: * different implementations of the {@code Map.Entry} interface.
0942: *
0943: * @param o object to be compared for equality with this map entry
0944: * @return {@code true} if the specified object is equal to this map
0945: * entry
0946: * @see #hashCode
0947: */
0948: @Override
0949: public boolean equals(Object o) {
0950: if (!(o instanceof Map.Entry))
0951: return false;
0952: Map.Entry e = (Map.Entry) o;
0953: return eq(key, e.getKey()) && eq(value, e.getValue());
0954: }
0955:
0956: /**
0957: * Returns the hash code value for this map entry. The hash code
0958: * of a map entry {@code e} is defined to be: <pre>
0959: * (e.getKey()==null ? 0 : e.getKey().hashCode()) ^
0960: * (e.getValue()==null ? 0 : e.getValue().hashCode())</pre>
0961: * This ensures that {@code e1.equals(e2)} implies that
0962: * {@code e1.hashCode()==e2.hashCode()} for any two Entries
0963: * {@code e1} and {@code e2}, as required by the general
0964: * contract of {@link Object#hashCode}.
0965: *
0966: * @return the hash code value for this map entry
0967: * @see #equals
0968: */
0969: @Override
0970: public int hashCode() {
0971: return (key == null ? 0 : key.hashCode())
0972: ^ (value == null ? 0 : value.hashCode());
0973: }
0974:
0975: /**
0976: * Returns a String representation of this map entry. This
0977: * implementation returns the string representation of this
0978: * entry's key followed by the equals character ("<tt>=</tt>")
0979: * followed by the string representation of this entry's value.
0980: *
0981: * @return a String representation of this map entry
0982: */
0983: @Override
0984: public String toString() {
0985: return key + "=" + value; // NOI18N
0986: }
0987:
0988: }
0989:
0990: private abstract class HashIterator<T> implements Iterator<T> {
0991: int index;
0992: Entry<K, V> entry = null;
0993: Entry<K, V> lastReturned = null;
0994: int expectedModCount = modCount;
0995:
0996: /**
0997: * Strong reference needed to avoid disappearance of key
0998: * between hasNext and next
0999: */
1000: Object nextKey = null;
1001:
1002: /**
1003: * Strong reference needed to avoid disappearance of key
1004: * between nextEntry() and any use of the entry
1005: */
1006: Object currentKey = null;
1007:
1008: HashIterator() {
1009: index = (size() != 0 ? table.length : 0);
1010: }
1011:
1012: public boolean hasNext() {
1013: Entry[] t = table;
1014:
1015: while (nextKey == null) {
1016: Entry<K, V> e = entry;
1017: int i = index;
1018: while (e == null && i > 0)
1019: e = t[--i];
1020: entry = e;
1021: index = i;
1022: if (e == null) {
1023: currentKey = null;
1024: return false;
1025: }
1026: nextKey = e.get(); // hold on to key in strong ref
1027: if (nextKey == null)
1028: entry = entry.next;
1029: }
1030: return true;
1031: }
1032:
1033: /** The common parts of next() across different types of iterators */
1034: protected Entry<K, V> nextEntry() {
1035: if (modCount != expectedModCount)
1036: throw new ConcurrentModificationException();
1037: if (nextKey == null && !hasNext())
1038: throw new NoSuchElementException();
1039:
1040: lastReturned = entry;
1041: entry = entry.next;
1042: currentKey = nextKey;
1043: nextKey = null;
1044: return lastReturned;
1045: }
1046:
1047: public void remove() {
1048: if (lastReturned == null)
1049: throw new IllegalStateException();
1050: if (modCount != expectedModCount)
1051: throw new ConcurrentModificationException();
1052:
1053: SharedKeyWeakHashMap.this .remove(currentKey);
1054: expectedModCount = modCount;
1055: lastReturned = null;
1056: currentKey = null;
1057: }
1058:
1059: }
1060:
1061: private class ValueIterator extends HashIterator<V> {
1062: public V next() {
1063: return nextEntry().value;
1064: }
1065: }
1066:
1067: private class KeyIterator extends HashIterator<K> {
1068: public K next() {
1069: return nextEntry().getKey();
1070: }
1071: }
1072:
1073: private class EntryIterator extends
1074: HashIterator<Map.Entry<K, V>> {
1075: public Map.Entry<K, V> next() {
1076: return nextEntry();
1077: }
1078: }
1079:
1080: // Views
1081:
1082: private transient Set<Map.Entry<K, V>> entrySet = null;
1083:
1084: /**
1085: * Returns a {@link Set} view of the keys contained in this map.
1086: * The set is backed by the map, so changes to the map are
1087: * reflected in the set, and vice-versa. If the map is modified
1088: * while an iteration over the set is in progress (except through
1089: * the iterator's own <tt>remove</tt> operation), the results of
1090: * the iteration are undefined. The set supports element removal,
1091: * which removes the corresponding mapping from the map, via the
1092: * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1093: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1094: * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
1095: * operations.
1096: */
1097: @Override
1098: public Set<K> keySet() {
1099: Set<K> ks = keySet;
1100: return (ks != null ? ks : (keySet = new KeySet()));
1101: }
1102:
1103: private class KeySet extends AbstractSet<K> {
1104: public Iterator<K> iterator() {
1105: return new KeyIterator();
1106: }
1107:
1108: public int size() {
1109: return SharedKeyWeakHashMap.this .size();
1110: }
1111:
1112: @Override
1113: public boolean contains(Object o) {
1114: return containsKey(o);
1115: }
1116:
1117: @Override
1118: public boolean remove(Object o) {
1119: if (containsKey(o)) {
1120: SharedKeyWeakHashMap.this .remove(o);
1121: return true;
1122: } else
1123: return false;
1124: }
1125:
1126: @Override
1127: public void clear() {
1128: SharedKeyWeakHashMap.this .clear();
1129: }
1130: }
1131:
1132: /**
1133: * Returns a {@link Collection} view of the values contained in this map.
1134: * The collection is backed by the map, so changes to the map are
1135: * reflected in the collection, and vice-versa. If the map is
1136: * modified while an iteration over the collection is in progress
1137: * (except through the iterator's own <tt>remove</tt> operation),
1138: * the results of the iteration are undefined. The collection
1139: * supports element removal, which removes the corresponding
1140: * mapping from the map, via the <tt>Iterator.remove</tt>,
1141: * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1142: * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
1143: * support the <tt>add</tt> or <tt>addAll</tt> operations.
1144: */
1145: @Override
1146: public Collection<V> values() {
1147: Collection<V> vs = values;
1148: return (vs != null ? vs : (values = new Values()));
1149: }
1150:
1151: private class Values extends AbstractCollection<V> {
1152: public Iterator<V> iterator() {
1153: return new ValueIterator();
1154: }
1155:
1156: public int size() {
1157: return SharedKeyWeakHashMap.this .size();
1158: }
1159:
1160: @Override
1161: public boolean contains(Object o) {
1162: return containsValue(o);
1163: }
1164:
1165: @Override
1166: public void clear() {
1167: SharedKeyWeakHashMap.this .clear();
1168: }
1169: }
1170:
1171: /**
1172: * Returns a {@link Set} view of the mappings contained in this map.
1173: * The set is backed by the map, so changes to the map are
1174: * reflected in the set, and vice-versa. If the map is modified
1175: * while an iteration over the set is in progress (except through
1176: * the iterator's own <tt>remove</tt> operation, or through the
1177: * <tt>setValue</tt> operation on a map entry returned by the
1178: * iterator) the results of the iteration are undefined. The set
1179: * supports element removal, which removes the corresponding
1180: * mapping from the map, via the <tt>Iterator.remove</tt>,
1181: * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
1182: * <tt>clear</tt> operations. It does not support the
1183: * <tt>add</tt> or <tt>addAll</tt> operations.
1184: */
1185: public Set<Map.Entry<K, V>> entrySet() {
1186: Set<Map.Entry<K, V>> es = entrySet;
1187: return es != null ? es : (entrySet = new EntrySet());
1188: }
1189:
1190: private class EntrySet extends AbstractSet<Map.Entry<K, V>> {
1191: public Iterator<Map.Entry<K, V>> iterator() {
1192: return new EntryIterator();
1193: }
1194:
1195: @Override
1196: public boolean contains(Object o) {
1197: if (!(o instanceof Map.Entry))
1198: return false;
1199: Map.Entry e = (Map.Entry) o;
1200: Object k = e.getKey();
1201: Entry candidate = getEntry(e.getKey());
1202: return candidate != null && candidate.equals(e);
1203: }
1204:
1205: @Override
1206: public boolean remove(Object o) {
1207: return removeMapping(o) != null;
1208: }
1209:
1210: public int size() {
1211: return SharedKeyWeakHashMap.this .size();
1212: }
1213:
1214: @Override
1215: public void clear() {
1216: SharedKeyWeakHashMap.this .clear();
1217: }
1218:
1219: private List<Map.Entry<K, V>> deepCopy() {
1220: List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>(
1221: size());
1222: for (Map.Entry<K, V> e : this )
1223: // have to use own class since AbstractMap.SimpleEntry is appears only in jdk 1.6
1224: list.add(new /*AbstractMap.*/SimpleEntry<K, V>(e));
1225: return list;
1226: }
1227:
1228: @Override
1229: public Object[] toArray() {
1230: return deepCopy().toArray();
1231: }
1232:
1233: @Override
1234: public <T> T[] toArray(T[] a) {
1235: return deepCopy().toArray(a);
1236: }
1237: }
1238:
1239: ////////////////////////////////////////////////////////////////////////////
1240: // new changes
1241:
1242: /**
1243: * Applies a supplemental hash function to a given hashCode, which
1244: * defends against poor quality hash functions. This is critical
1245: * because HashMap uses power-of-two length hash tables, that
1246: * otherwise encounter collisions for hashCodes that do not differ
1247: * in lower bits. Note: Null keys always map to hash 0, thus index 0.
1248: */
1249: static int hash(int h) {
1250: // This function ensures that hashCodes that differ only by
1251: // constant multiples at each bit position have a bounded
1252: // number of collisions (approximately 8 at default load factor).
1253: h ^= (h >>> 20) ^ (h >>> 12);
1254: return h ^ (h >>> 7) ^ (h >>> 4);
1255: }
1256:
1257: // Views
1258:
1259: /**
1260: * Each of these fields are initialized to contain an instance of the
1261: * appropriate view the first time this view is requested. The views are
1262: * stateless, so there's no reason to create more than one of each.
1263: */
1264: transient volatile Set<K> keySet = null;
1265: transient volatile Collection<V> values = null;
1266:
1267: /**
1268: * Put specified key in this set if key is not yet in set.
1269: * returns previous value in set if key already in set.
1270: *
1271: * @param key key to put in set.
1272: * @return the previous set entry equals with <tt>key</tt>, or
1273: * new <tt>key</tt> if there were not entry in set.
1274: */
1275: private K putOrGet(K key) {
1276: K k = (K) maskNull(key);
1277: int h = hash(k.hashCode());
1278: Entry[] tab = getTable();
1279: int i = indexFor(h, tab.length);
1280:
1281: Entry<K, V> e = tab[i];
1282: while (e != null) {
1283: if (e.hash == h) {
1284: K refedKey = e.get();
1285: if (eq(k, refedKey)) {
1286: return refedKey;
1287: }
1288: }
1289: e = e.next;
1290: }
1291:
1292: modCount++;
1293: e = tab[i];
1294: tab[i] = new Entry<K, V>(k, (V) Boolean.TRUE, queue, h, e);
1295: if (++size >= threshold)
1296: resize(tab.length * 2);
1297: return k;
1298: }
1299: }
1300: }
|