0001: /*
0002: * Licensed to the Apache Software Foundation (ASF) under one
0003: * or more contributor license agreements. See the NOTICE file
0004: * distributed with this work for additional information
0005: * regarding copyright ownership. The ASF licenses this file
0006: * to you under the Apache License, Version 2.0 (the
0007: * "License"); you may not use this file except in compliance
0008: * with the License. You may obtain a copy of the License at
0009: *
0010: * http://www.apache.org/licenses/LICENSE-2.0
0011: *
0012: * Unless required by applicable law or agreed to in writing,
0013: * software distributed under the License is distributed on an
0014: * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
0015: * KIND, either express or implied. See the License for the
0016: * specific language governing permissions and limitations
0017: * under the License.
0018: */
0019: package org.apache.openjpa.lib.util.concurrent;
0020:
0021: import java.lang.ref.ReferenceQueue;
0022: import java.lang.ref.SoftReference;
0023: import java.lang.ref.WeakReference;
0024: import java.util.AbstractMap;
0025: import java.util.Collection;
0026: import java.util.Iterator;
0027: import java.util.Map;
0028: import java.util.NoSuchElementException;
0029: import java.util.Random;
0030: import java.util.Set;
0031:
0032: import org.apache.openjpa.lib.util.ReferenceMap;
0033: import org.apache.openjpa.lib.util.SizedMap;
0034:
0035: /**
0036: * This class implements a HashMap which has limited synchronization
0037: * and reference keys or values(but not both). In particular mutators are
0038: * generally synchronized while accessors are generally not. Additionally the
0039: * Iterators returned by this class are not "fail-fast", but instead try to
0040: * continue to iterate over the data structure after changes have been
0041: * made. Finally purging of the reference queue is only done inside mutators.
0042: * Null keys are not supported if keys use references. Null values are not
0043: * supported if values use references.
0044: * This class is based heavily on the WeakHashMap class in the Java
0045: * collections package.
0046: */
0047: public class ConcurrentReferenceHashMap extends AbstractMap implements
0048: ConcurrentMap, ReferenceMap, SizedMap, Cloneable {
0049:
0050: /**
0051: * Cache of random numbers used in "random" methods, since generating them
0052: * is expensive. We hope each map changes enough between cycling through
0053: * this list that the overall effect is random enough.
0054: */
0055: static final double[] RANDOMS = new double[1000];
0056:
0057: static {
0058: Random random = new Random();
0059: for (int i = 0; i < RANDOMS.length; i++)
0060: RANDOMS[i] = random.nextDouble();
0061: }
0062:
0063: /**
0064: * The hash table data.
0065: */
0066: private transient Entry[] table;
0067:
0068: /**
0069: * The total number of entries in the hash table.
0070: */
0071: private transient int count;
0072:
0073: /**
0074: * Rehashes the table when count exceeds this threshold.
0075: */
0076: private int threshold;
0077:
0078: /**
0079: * The load factor for the HashMap.
0080: */
0081: private float loadFactor;
0082:
0083: /**
0084: * The key reference type.
0085: */
0086: private int keyType;
0087:
0088: /**
0089: * The value reference type.
0090: */
0091: private int valueType;
0092:
0093: /**
0094: * Reference queue for cleared Entries
0095: */
0096: private final ReferenceQueue queue = new ReferenceQueue();
0097:
0098: /**
0099: * Spread "random" removes and iteration.
0100: */
0101: private int randomEntry = 0;
0102:
0103: /**
0104: * Maximum entries.
0105: */
0106: private int maxSize = Integer.MAX_VALUE;
0107:
0108: /**
0109: * Compare two objects. These might be keys, values, or Entry instances.
0110: * This implementation uses a normal null-safe object equality algorithm.
0111: *
0112: * @since 1.0.0
0113: */
0114: protected boolean eq(Object x, Object y) {
0115: return x == y || (x != null && x.equals(y));
0116: }
0117:
0118: /**
0119: * Obtain the hashcode of an object. The object might be a key, a value,
0120: * or an Entry. This implementation just delegates to
0121: * {@link Object#hashCode}
0122: *
0123: * @since 1.0.0
0124: */
0125: protected int hc(Object o) {
0126: return o == null ? 0 : o.hashCode();
0127: }
0128:
0129: /**
0130: * Constructs a new, empty HashMap with the specified initial
0131: * capacity and the specified load factor.
0132: *
0133: * @param keyType the reference type of map keys
0134: * @param valueType the reference type of map values
0135: * @param initialCapacity the initial capacity of the HashMap.
0136: * @param loadFactor a number between 0.0 and 1.0.
0137: * @throws IllegalArgumentException if neither keys nor values use hard
0138: * references, if the initial capacity is less than or equal to zero, or if
0139: * the load factor is less than or equal to zero
0140: */
0141: public ConcurrentReferenceHashMap(int keyType, int valueType,
0142: int initialCapacity, float loadFactor) {
0143: if (initialCapacity < 0) {
0144: throw new IllegalArgumentException(
0145: "Illegal Initial Capacity: " + initialCapacity);
0146: }
0147: if ((loadFactor > 1) || (loadFactor <= 0)) {
0148: throw new IllegalArgumentException("Illegal Load factor: "
0149: + loadFactor);
0150: }
0151: if (keyType != HARD && valueType != HARD) {
0152: throw new IllegalArgumentException(
0153: "Either keys or values must "
0154: + "use hard references.");
0155: }
0156: this .keyType = keyType;
0157: this .valueType = valueType;
0158: this .loadFactor = loadFactor;
0159: table = new Entry[initialCapacity];
0160: threshold = (int) (initialCapacity * loadFactor);
0161: }
0162:
0163: /**
0164: * Constructs a new, empty HashMap with the specified initial capacity
0165: * and default load factor.
0166: *
0167: * @param keyType the reference type of map keys
0168: * @param valueType the reference type of map values
0169: * @param initialCapacity the initial capacity of the HashMap.
0170: */
0171: public ConcurrentReferenceHashMap(int keyType, int valueType,
0172: int initialCapacity) {
0173: this (keyType, valueType, initialCapacity, 0.75f);
0174: }
0175:
0176: /**
0177: * Constructs a new, empty HashMap with a default capacity and load factor.
0178: *
0179: * @param keyType the reference type of map keys
0180: * @param valueType the reference type of map values
0181: */
0182: public ConcurrentReferenceHashMap(int keyType, int valueType) {
0183: this (keyType, valueType, 11, 0.75f);
0184: }
0185:
0186: /**
0187: * Constructs a new HashMap with the same mappings as the given
0188: * Map. The HashMap is created with a capacity of thrice the number
0189: * of entries in the given Map or 11 (whichever is greater), and a
0190: * default load factor.
0191: *
0192: * @param keyType the reference type of map keys
0193: * @param valueType the reference type of map values
0194: */
0195: public ConcurrentReferenceHashMap(int keyType, int valueType, Map t) {
0196: this (keyType, valueType, Math.max(3 * t.size(), 11), 0.75f);
0197: putAll(t);
0198: }
0199:
0200: public int getMaxSize() {
0201: return maxSize;
0202: }
0203:
0204: public void setMaxSize(int maxSize) {
0205: this .maxSize = (maxSize < 0) ? Integer.MAX_VALUE : maxSize;
0206: if (this .maxSize != Integer.MAX_VALUE)
0207: removeOverflow(this .maxSize);
0208: }
0209:
0210: public boolean isFull() {
0211: return maxSize != Integer.MAX_VALUE && size() >= maxSize;
0212: }
0213:
0214: public void overflowRemoved(Object key, Object value) {
0215: }
0216:
0217: /**
0218: * Returns the number of key-value mappings in this Map. This
0219: * result is a snapshot, and may not reflect unprocessed entries
0220: * that will be removed before next attempted access because they
0221: * are no longer referenced.
0222: */
0223: public int size() {
0224: return count;
0225: }
0226:
0227: /**
0228: * Returns true if this Map contains no key-value mappings. This
0229: * result is a snapshot, and may not reflect unprocessed entries
0230: * that will be removed before next attempted access because they
0231: * are no longer referenced.
0232: */
0233: public boolean isEmpty() {
0234: return count == 0;
0235: }
0236:
0237: /**
0238: * Returns true if this HashMap maps one or more keys to the specified
0239: * value.
0240: *
0241: * @param value value whose presence in this Map is to be tested.
0242: */
0243: public boolean containsValue(Object value) {
0244: Entry[] tab = table;
0245:
0246: if (value == null) {
0247: if (valueType != HARD)
0248: return false;
0249: for (int i = tab.length; i-- > 0;)
0250: for (Entry e = tab[i]; e != null; e = e.getNext())
0251: if (e.getValue() == null)
0252: return true;
0253: } else {
0254: for (int i = tab.length; i-- > 0;)
0255: for (Entry e = tab[i]; e != null; e = e.getNext())
0256: if (eq(value, e.getValue()))
0257: return true;
0258: }
0259: return false;
0260: }
0261:
0262: /**
0263: * Returns true if this HashMap contains a mapping for the specified key.
0264: *
0265: * @param key key whose presence in this Map is to be tested.
0266: */
0267: public boolean containsKey(Object key) {
0268: if (key == null && keyType != HARD)
0269: return false;
0270:
0271: Entry[] tab = table;
0272: int hash = hc(key);
0273: int index = (hash & 0x7FFFFFFF) % tab.length;
0274: for (Entry e = tab[index]; e != null; e = e.getNext())
0275: if (e.getHash() == hash && eq(key, e.getKey()))
0276: return true;
0277: return false;
0278: }
0279:
0280: /**
0281: * Returns the value to which this HashMap maps the specified key.
0282: * Returns null if the HashMap contains no mapping for this key.
0283: *
0284: * @param key key whose associated value is to be returned.
0285: */
0286: public Object get(Object key) {
0287: if (key == null && keyType != HARD)
0288: return null;
0289:
0290: Entry[] tab = table;
0291: int hash = hc(key);
0292: int index = (hash & 0x7FFFFFFF) % tab.length;
0293: for (Entry e = tab[index]; e != null; e = e.getNext())
0294: if ((e.getHash() == hash) && eq(key, e.getKey()))
0295: return e.getValue();
0296:
0297: return null;
0298: }
0299:
0300: /**
0301: * Rehashes the contents of the HashMap into a HashMap with a
0302: * larger capacity. This method is called automatically when the
0303: * number of keys in the HashMap exceeds this HashMap's capacity
0304: * and load factor.
0305: */
0306: private void rehash() {
0307: int oldCapacity = table.length;
0308: Entry oldMap[] = table;
0309:
0310: int newCapacity = oldCapacity * 2 + 1;
0311: Entry newMap[] = new Entry[newCapacity];
0312:
0313: for (int i = oldCapacity; i-- > 0;) {
0314: for (Entry old = oldMap[i]; old != null;) {
0315: if ((keyType != HARD && old.getKey() == null)
0316: || valueType != HARD && old.getValue() == null) {
0317: Entry e = old;
0318: old = old.getNext();
0319: e.setNext(null);
0320: count--;
0321: } else {
0322: Entry e = (Entry) old.clone(queue);
0323: old = old.getNext();
0324:
0325: int index = (e.getHash() & 0x7FFFFFFF)
0326: % newCapacity;
0327: e.setNext(newMap[index]);
0328: newMap[index] = e;
0329: }
0330: }
0331: }
0332:
0333: threshold = (int) (newCapacity * loadFactor);
0334: table = newMap;
0335: }
0336:
0337: /**
0338: * Associates the specified value with the specified key in this HashMap.
0339: * If the HashMap previously contained a mapping for this key, the old
0340: * value is replaced.
0341: *
0342: * @param key key with which the specified value is to be associated.
0343: * @param value value to be associated with the specified key.
0344: * @return previous value associated with specified key, or null if there
0345: * was no mapping for key. A null return can also indicate that
0346: * the HashMap previously associated null with the specified key.
0347: */
0348: public Object put(Object key, Object value) {
0349: if ((key == null && keyType != HARD)
0350: || (value == null && valueType != HARD))
0351: throw new IllegalArgumentException(
0352: "Null references not supported");
0353:
0354: int hash = hc(key);
0355: synchronized (this ) {
0356: expungeStaleEntries();
0357:
0358: Entry[] tab = table;
0359: int index = 0;
0360:
0361: index = (hash & 0x7FFFFFFF) % tab.length;
0362: for (Entry e = tab[index], prev = null; e != null; prev = e, e = e
0363: .getNext()) {
0364: if ((e.getHash() == hash) && eq(key, e.getKey())) {
0365: Object old = e.getValue();
0366: if (valueType == HARD)
0367: e.setValue(value);
0368: else {
0369: e = newEntry(hash, e.getKey(), value, e
0370: .getNext());
0371: if (prev == null)
0372: tab[index] = e;
0373: else
0374: prev.setNext(e);
0375: }
0376: return old;
0377: }
0378: }
0379:
0380: if (count >= threshold) {
0381: // Rehash the table if the threshold is exceeded
0382: rehash();
0383:
0384: tab = table;
0385: index = (hash & 0x7FFFFFFF) % tab.length;
0386: }
0387:
0388: if (maxSize != Integer.MAX_VALUE)
0389: removeOverflow(maxSize - 1);
0390: tab[index] = newEntry(hash, key, value, tab[index]);
0391: count++;
0392: }
0393: return null;
0394: }
0395:
0396: /**
0397: * Creates a new entry.
0398: */
0399: private Entry newEntry(int hash, Object key, Object value,
0400: Entry next) {
0401: int refType = (keyType != HARD) ? keyType : valueType;
0402: switch (refType) {
0403: case WEAK:
0404: return new WeakEntry(hash, key, value, refType == keyType,
0405: next, queue);
0406: case SOFT:
0407: return new SoftEntry(hash, key, value, refType == keyType,
0408: next, queue);
0409: default:
0410: return new HardEntry(hash, key, value, next);
0411: }
0412: }
0413:
0414: /**
0415: * Remove any entries equal to or over the max size.
0416: */
0417: private void removeOverflow(int maxSize) {
0418: while (count > maxSize) {
0419: Map.Entry entry = removeRandom();
0420: if (entry == null)
0421: break;
0422: overflowRemoved(entry.getKey(), entry.getValue());
0423: }
0424: }
0425:
0426: /**
0427: * Removes the mapping for this key from this HashMap if present.
0428: *
0429: * @param key key whose mapping is to be removed from the Map.
0430: * @return previous value associated with specified key, or null if there
0431: * was no mapping for key. A null return can also indicate that
0432: * the HashMap previously associated null with the specified key.
0433: */
0434: public Object remove(Object key) {
0435: if (key == null && keyType != HARD)
0436: return null;
0437:
0438: int hash = hc(key);
0439: synchronized (this ) {
0440: expungeStaleEntries();
0441:
0442: Entry[] tab = table;
0443:
0444: int index = (hash & 0x7FFFFFFF) % tab.length;
0445: for (Entry e = tab[index], prev = null; e != null; prev = e, e = e
0446: .getNext()) {
0447: if ((e.getHash() == hash) && eq(key, e.getKey())) {
0448: if (prev != null)
0449: prev.setNext(e.getNext());
0450: // otherwise put the bucket after us
0451: else
0452: tab[index] = e.getNext();
0453:
0454: count--;
0455: return e.getValue();
0456: }
0457: }
0458: }
0459: return null;
0460: }
0461:
0462: public void removeExpired() {
0463: synchronized (this ) {
0464: expungeStaleEntries();
0465: }
0466: }
0467:
0468: public void keyExpired(Object value) {
0469: }
0470:
0471: public void valueExpired(Object key) {
0472: }
0473:
0474: /**
0475: * Return an arbitrary entry index.
0476: */
0477: private int randomEntryIndex() {
0478: if (randomEntry == RANDOMS.length)
0479: randomEntry = 0;
0480: return (int) (RANDOMS[randomEntry++] * table.length);
0481: }
0482:
0483: public Map.Entry removeRandom() {
0484: synchronized (this ) {
0485: expungeStaleEntries();
0486: if (count == 0)
0487: return null;
0488:
0489: int random = randomEntryIndex();
0490: int index = findEntry(random, random % 2 == 0, false);
0491: if (index == -1)
0492: return null;
0493: Entry rem = table[index];
0494: table[index] = rem.getNext();
0495: count--;
0496: return rem;
0497: }
0498: }
0499:
0500: /**
0501: * Find the index of the entry nearest the given index, starting in the
0502: * given direction.
0503: */
0504: private int findEntry(int start, boolean forward,
0505: boolean searchedOther) {
0506: if (forward) {
0507: for (int i = start; i < table.length; i++)
0508: if (table[i] != null)
0509: return i;
0510: return (searchedOther || start == 0) ? -1 : findEntry(
0511: start - 1, false, true);
0512: } else {
0513: for (int i = start; i >= 0; i--)
0514: if (table[i] != null)
0515: return i;
0516: return (searchedOther || start == table.length - 1) ? -1
0517: : findEntry(start + 1, true, true);
0518: }
0519: }
0520:
0521: public Iterator randomEntryIterator() {
0522: // pass index so calculated before iterator refs table, in case table
0523: // gets replace with a larger one
0524: return new HashIterator(ENTRIES, randomEntryIndex());
0525: }
0526:
0527: /**
0528: * Copies all of the mappings from the specified Map to this HashMap
0529: * These mappings will replace any mappings that this HashMap had for any
0530: * of the keys currently in the specified Map.
0531: *
0532: * @param t Mappings to be stored in this Map.
0533: */
0534: public void putAll(Map t) {
0535: Iterator i = t.entrySet().iterator();
0536: while (i.hasNext()) {
0537: Map.Entry e = (Map.Entry) i.next();
0538: put(e.getKey(), e.getValue());
0539: }
0540: }
0541:
0542: /**
0543: * Removes all mappings from this HashMap.
0544: */
0545: public synchronized void clear() {
0546: // clear out ref queue. We don't need to expunge entries
0547: // since table is getting cleared.
0548: while (queue.poll() != null)
0549: ;
0550: table = new Entry[table.length];
0551: count = 0;
0552: // Allocation of array may have caused GC, which may have caused
0553: // additional entries to go stale. Removing these entries from
0554: // the reference queue will make them eligible for reclamation.
0555: while (queue.poll() != null)
0556: ;
0557: }
0558:
0559: /**
0560: * Returns a shallow copy of this HashMap. The keys and values
0561: * themselves are not cloned.
0562: */
0563: public synchronized Object clone() {
0564: try {
0565: expungeStaleEntries();
0566:
0567: ConcurrentReferenceHashMap t = (ConcurrentReferenceHashMap) super
0568: .clone();
0569: t.table = new Entry[table.length];
0570: for (int i = table.length; i-- > 0;) {
0571: Entry e = table[i];
0572: if (e != null) {
0573: t.table[i] = (Entry) e.clone(t.queue);
0574: e = e.getNext();
0575: for (Entry k = t.table[i]; e != null; e = e
0576: .getNext()) {
0577: k.setNext((Entry) e.clone(t.queue));
0578: k = k.getNext();
0579: }
0580: }
0581: }
0582: t.keySet = null;
0583: t.entrySet = null;
0584: t.values = null;
0585: return t;
0586: } catch (CloneNotSupportedException e) {
0587: // this shouldn't happen, since we are Cloneable
0588: throw new InternalError();
0589: }
0590: }
0591:
0592: // Views
0593:
0594: private transient Set keySet = null;
0595: private transient Set entrySet = null;
0596: private transient Collection values = null;
0597:
0598: /**
0599: * Returns a Set view of the keys contained in this HashMap. The Set is
0600: * backed by the HashMap, so changes to the HashMap are reflected in the
0601: * Set, and vice-versa. The Set supports element removal, which removes
0602: * the corresponding mapping from the HashMap, via the Iterator.remove,
0603: * Set.remove, removeAll retainAll, and clear operations. It does not
0604: * support the add or addAll operations.
0605: */
0606: public Set keySet() {
0607: if (keySet == null) {
0608: keySet = new java.util.AbstractSet() {
0609: public Iterator iterator() {
0610: return new HashIterator(KEYS, table.length - 1);
0611: }
0612:
0613: public int size() {
0614: return count;
0615: }
0616:
0617: public boolean contains(Object o) {
0618: return containsKey(o);
0619: }
0620:
0621: public boolean remove(Object o) {
0622: return ConcurrentReferenceHashMap.this .remove(o) != null;
0623: }
0624:
0625: public void clear() {
0626: ConcurrentReferenceHashMap.this .clear();
0627: }
0628: };
0629: }
0630: return keySet;
0631: }
0632:
0633: /**
0634: * Returns a Collection view of the values contained in this HashMap.
0635: * The Collection is backed by the HashMap, so changes to the HashMap are
0636: * reflected in the Collection, and vice-versa. The Collection supports
0637: * element removal, which removes the corresponding mapping from the
0638: * HashMap, via the Iterator.remove, Collection.remove, removeAll,
0639: * retainAll and clear operations. It does not support the add or addAll
0640: * operations.
0641: */
0642: public Collection values() {
0643: if (values == null) {
0644: values = new java.util.AbstractCollection() {
0645: public Iterator iterator() {
0646: return new HashIterator(VALUES, table.length - 1);
0647: }
0648:
0649: public int size() {
0650: return count;
0651: }
0652:
0653: public boolean contains(Object o) {
0654: return containsValue(o);
0655: }
0656:
0657: public void clear() {
0658: ConcurrentReferenceHashMap.this .clear();
0659: }
0660: };
0661: }
0662: return values;
0663: }
0664:
0665: /**
0666: * Returns a Collection view of the mappings contained in this HashMap.
0667: * Each element in the returned collection is a Map.Entry. The Collection
0668: * is backed by the HashMap, so changes to the HashMap are reflected in the
0669: * Collection, and vice-versa. The Collection supports element removal,
0670: * which removes the corresponding mapping from the HashMap, via the
0671: * Iterator.remove, Collection.remove, removeAll, retainAll and clear
0672: * operations. It does not support the add or addAll operations.
0673: *
0674: * @see Map.Entry
0675: */
0676: public Set entrySet() {
0677: if (entrySet == null) {
0678: entrySet = new java.util.AbstractSet() {
0679: public Iterator iterator() {
0680: return new HashIterator(ENTRIES, table.length - 1);
0681: }
0682:
0683: public boolean contains(Object o) {
0684: if (!(o instanceof Map.Entry))
0685: return false;
0686: Map.Entry entry = (Map.Entry) o;
0687: Object key = entry.getKey();
0688: Entry[] tab = table;
0689: int hash = hc(key);
0690: int index = (hash & 0x7FFFFFFF) % tab.length;
0691:
0692: for (Entry e = tab[index]; e != null; e = e
0693: .getNext())
0694: if (e.getHash() == hash && eq(e, entry))
0695: return true;
0696: return false;
0697: }
0698:
0699: public boolean remove(Object o) {
0700: if (!(o instanceof Map.Entry))
0701: return false;
0702: Map.Entry entry = (Map.Entry) o;
0703: Object key = entry.getKey();
0704: synchronized (ConcurrentReferenceHashMap.this ) {
0705: Entry[] tab = table;
0706: int hash = hc(key);
0707: int index = (hash & 0x7FFFFFFF) % tab.length;
0708:
0709: for (Entry e = tab[index], prev = null; e != null; prev = e, e = e
0710: .getNext()) {
0711: if (e.getHash() == hash && eq(e, entry)) {
0712: if (prev != null)
0713: prev.setNext(e.getNext());
0714: else
0715: tab[index] = e.getNext();
0716:
0717: count--;
0718: return true;
0719: }
0720: }
0721: return false;
0722: }
0723: }
0724:
0725: public int size() {
0726: return count;
0727: }
0728:
0729: public void clear() {
0730: ConcurrentReferenceHashMap.this .clear();
0731: }
0732: };
0733: }
0734:
0735: return entrySet;
0736: }
0737:
0738: /**
0739: * Expunge stale entries from the table.
0740: */
0741: private void expungeStaleEntries() {
0742: Object r;
0743: while ((r = queue.poll()) != null) {
0744: Entry entry = (Entry) r;
0745: int hash = entry.getHash();
0746: Entry[] tab = table;
0747: int index = (hash & 0x7FFFFFFF) % tab.length;
0748:
0749: for (Entry e = tab[index], prev = null; e != null; prev = e, e = e
0750: .getNext()) {
0751: if (e == entry) {
0752: if (prev != null)
0753: prev.setNext(e.getNext());
0754: // otherwise put the bucket after us
0755: else
0756: tab[index] = e.getNext();
0757:
0758: count--;
0759: if (keyType == HARD)
0760: valueExpired(e.getKey());
0761: else
0762: keyExpired(e.getValue());
0763: }
0764: }
0765: }
0766: }
0767:
0768: /**
0769: * HashMap collision list entry.
0770: */
0771: private static interface Entry extends Map.Entry {
0772:
0773: public int getHash();
0774:
0775: public Entry getNext();
0776:
0777: public void setNext(Entry next);
0778:
0779: public Object clone(ReferenceQueue queue);
0780: }
0781:
0782: /**
0783: * Hard entry.
0784: */
0785: private class HardEntry implements Entry {
0786:
0787: private int hash;
0788: private Object key;
0789: private Object value;
0790: private Entry next;
0791:
0792: HardEntry(int hash, Object key, Object value, Entry next) {
0793: this .hash = hash;
0794: this .key = key;
0795: this .value = value;
0796: this .next = next;
0797: }
0798:
0799: public int getHash() {
0800: return hash;
0801: }
0802:
0803: public Entry getNext() {
0804: return next;
0805: }
0806:
0807: public void setNext(Entry next) {
0808: this .next = next;
0809: }
0810:
0811: public Object clone(ReferenceQueue queue) {
0812: // It is the callers responsibility to set the next field
0813: // correctly.
0814: return new HardEntry(hash, key, value, null);
0815: }
0816:
0817: // Map.Entry Ops
0818:
0819: public Object getKey() {
0820: return key;
0821: }
0822:
0823: public Object getValue() {
0824: return value;
0825: }
0826:
0827: public Object setValue(Object value) {
0828: Object oldValue = this .value;
0829: this .value = value;
0830: return oldValue;
0831: }
0832:
0833: public boolean equals(Object o) {
0834: if (!(o instanceof Map.Entry))
0835: return false;
0836: Map.Entry e = (Map.Entry) o;
0837:
0838: Object k1 = key;
0839: Object k2 = e.getKey();
0840:
0841: return (k1 == null ? k2 == null : eq(k1, k2))
0842: && (value == null ? e.getValue() == null : eq(
0843: value, e.getValue()));
0844: }
0845:
0846: public int hashCode() {
0847: return hash ^ (value == null ? 0 : value.hashCode());
0848: }
0849:
0850: public String toString() {
0851: return key + "=" + value.toString();
0852: }
0853: }
0854:
0855: /**
0856: * Weak entry.
0857: */
0858: private class WeakEntry extends WeakReference implements Entry {
0859:
0860: private int hash;
0861: private Object hard;
0862: private boolean keyRef;
0863: private Entry next;
0864:
0865: WeakEntry(int hash, Object key, Object value, boolean keyRef,
0866: Entry next, ReferenceQueue queue) {
0867: super ((keyRef) ? key : value, queue);
0868: this .hash = hash;
0869: this .hard = (keyRef) ? value : key;
0870: this .keyRef = keyRef;
0871: this .next = next;
0872: }
0873:
0874: public int getHash() {
0875: return hash;
0876: }
0877:
0878: public Entry getNext() {
0879: return next;
0880: }
0881:
0882: public void setNext(Entry next) {
0883: this .next = next;
0884: }
0885:
0886: public Object clone(ReferenceQueue queue) {
0887: // It is the callers responsibility to set the next field
0888: // correctly.
0889: return new WeakEntry(hash, getKey(), getValue(), keyRef,
0890: null, queue);
0891: }
0892:
0893: // Map.Entry Ops
0894:
0895: public Object getKey() {
0896: return (keyRef) ? super .get() : hard;
0897: }
0898:
0899: public Object getValue() {
0900: return (keyRef) ? hard : super .get();
0901: }
0902:
0903: public Object setValue(Object value) {
0904: if (!keyRef)
0905: throw new Error("Attempt to reset reference value.");
0906:
0907: Object oldValue = hard;
0908: hard = value;
0909: return oldValue;
0910: }
0911:
0912: public boolean equals(Object o) {
0913: if (!(o instanceof Map.Entry))
0914: return false;
0915: Map.Entry e = (Map.Entry) o;
0916: return eq(getKey(), e.getKey())
0917: && eq(getValue(), e.getValue());
0918: }
0919:
0920: public int hashCode() {
0921: Object val = getValue();
0922: return hash ^ (val == null ? 0 : val.hashCode());
0923: }
0924:
0925: public String toString() {
0926: return getKey() + "=" + getValue();
0927: }
0928: }
0929:
0930: /**
0931: * Soft entry.
0932: */
0933: private class SoftEntry extends SoftReference implements Entry {
0934:
0935: private int hash;
0936: private Object hard;
0937: private boolean keyRef;
0938: private Entry next;
0939:
0940: SoftEntry(int hash, Object key, Object value, boolean keyRef,
0941: Entry next, ReferenceQueue queue) {
0942: super ((keyRef) ? key : value, queue);
0943: this .hash = hash;
0944: this .hard = (keyRef) ? value : key;
0945: this .keyRef = keyRef;
0946: this .next = next;
0947: }
0948:
0949: public int getHash() {
0950: return hash;
0951: }
0952:
0953: public Entry getNext() {
0954: return next;
0955: }
0956:
0957: public void setNext(Entry next) {
0958: this .next = next;
0959: }
0960:
0961: public Object clone(ReferenceQueue queue) {
0962: // It is the callers responsibility to set the next field
0963: // correctly.
0964: return new SoftEntry(hash, getKey(), getValue(), keyRef,
0965: null, queue);
0966: }
0967:
0968: // Map.Entry Ops
0969:
0970: public Object getKey() {
0971: return (keyRef) ? super .get() : hard;
0972: }
0973:
0974: public Object getValue() {
0975: return (keyRef) ? hard : super .get();
0976: }
0977:
0978: public Object setValue(Object value) {
0979: if (!keyRef)
0980: throw new Error("Attempt to reset reference value.");
0981:
0982: Object oldValue = hard;
0983: hard = value;
0984: return oldValue;
0985: }
0986:
0987: public boolean equals(Object o) {
0988: if (!(o instanceof Map.Entry))
0989: return false;
0990: Map.Entry e = (Map.Entry) o;
0991: return eq(getKey(), e.getKey())
0992: && eq(getValue(), e.getValue());
0993: }
0994:
0995: public int hashCode() {
0996: Object val = getValue();
0997: return hash ^ (val == null ? 0 : val.hashCode());
0998: }
0999:
1000: public String toString() {
1001: return getKey() + "=" + getValue();
1002: }
1003: }
1004:
1005: // Types of Enumerations/Iterations
1006: private static final int KEYS = 0;
1007: private static final int VALUES = 1;
1008: private static final int ENTRIES = 2;
1009:
1010: /**
1011: * Map iterator.
1012: */
1013: private class HashIterator implements Iterator {
1014:
1015: final Entry[] table = ConcurrentReferenceHashMap.this .table;
1016: final int type;
1017: int startIndex;
1018: int stopIndex = 0;
1019: int index;
1020: Entry entry = null;
1021: Entry lastReturned = null;
1022:
1023: HashIterator(int type, int startIndex) {
1024: this .type = type;
1025: this .startIndex = startIndex;
1026: index = startIndex;
1027: }
1028:
1029: public boolean hasNext() {
1030: if (entry != null) {
1031: return true;
1032: }
1033: while (index >= stopIndex) {
1034: if ((entry = table[index--]) != null) {
1035: return true;
1036: }
1037: }
1038: if (stopIndex == 0) {
1039: index = table.length - 1;
1040: stopIndex = startIndex + 1;
1041: while (index >= stopIndex) {
1042: if ((entry = table[index--]) != null) {
1043: return true;
1044: }
1045: }
1046: }
1047: return false;
1048: }
1049:
1050: public Object next() {
1051: if (!hasNext())
1052: throw new NoSuchElementException();
1053: Entry e = lastReturned = entry;
1054: entry = e.getNext();
1055: return type == KEYS ? e.getKey() : (type == VALUES ? e
1056: .getValue() : e);
1057: }
1058:
1059: public void remove() {
1060: if (lastReturned == null)
1061: throw new IllegalStateException();
1062: synchronized (ConcurrentReferenceHashMap.this ) {
1063: Entry[] tab = ConcurrentReferenceHashMap.this .table;
1064: int index = (lastReturned.getHash() & 0x7FFFFFFF)
1065: % tab.length;
1066:
1067: for (Entry e = tab[index], prev = null; e != null; prev = e, e = e
1068: .getNext()) {
1069: if (e == lastReturned) {
1070: if (prev == null)
1071: tab[index] = e.getNext();
1072: else
1073: prev.setNext(e.getNext());
1074: count--;
1075: lastReturned = null;
1076: return;
1077: }
1078: }
1079: throw new Error("Iterated off table when doing remove");
1080: }
1081: }
1082: }
1083:
1084: int capacity() {
1085: return table.length;
1086: }
1087:
1088: float loadFactor() {
1089: return loadFactor;
1090: }
1091: }
|