0001: /*
0002: * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
0003: * Copyright (C) 2006 - Javolution (http://javolution.org/)
0004: * All rights reserved.
0005: *
0006: * Permission to use, copy, modify, and distribute this software is
0007: * freely granted, provided that this notice is preserved.
0008: */
0009: package javolution.util;
0010:
0011: import j2me.io.ObjectInputStream;
0012: import j2me.io.ObjectOutputStream;
0013: import j2me.io.Serializable;
0014: import j2me.lang.IllegalStateException;
0015: import j2me.lang.UnsupportedOperationException;
0016: import j2me.util.Collection;
0017: import j2me.util.Iterator;
0018: import j2me.util.Map;
0019: import j2me.util.NoSuchElementException;
0020: import j2me.util.Set;
0021: import j2mex.realtime.MemoryArea;
0022: import java.io.IOException;
0023: import java.io.PrintStream;
0024:
0025: import javolution.context.ArrayFactory;
0026: import javolution.context.LogContext;
0027: import javolution.context.ObjectFactory;
0028: import javolution.context.PersistentContext;
0029: import javolution.lang.MathLib;
0030: import javolution.lang.Realtime;
0031: import javolution.lang.Reusable;
0032: import javolution.text.Text;
0033: import javolution.util.FastCollection.Record;
0034: import javolution.xml.XMLSerializable;
0035:
0036: /**
0037: * <p> This class represents a hash map with real-time behavior;
0038: * smooth capacity increase and <i>thread-safe</i> without external
0039: * synchronization when {@link #isShared shared}.</p>
0040: * <img src="doc-files/map-put.png"/>
0041: *
0042: * <p> {@link FastMap} has a predictable iteration order, which is the order in
0043: * which keys are inserted into the map (similar to
0044: * <code>java.util.LinkedHashMap</code> collection class). If the map is
0045: * marked {@link #setShared(boolean) shared} then all operations are
0046: * thread-safe including iterations over the map's collections.
0047: * Unlike <code>ConcurrentHashMap</code>, {@link #get(Object) access} never
0048: * blocks; retrieval reflects the map state not older than the last time the
0049: * accessing threads have been synchronized (for multi-processors systems
0050: * synchronizing ensures that the CPU internal cache is not stale).</p>
0051: *
0052: * <p> {@link FastMap} may use custom key comparators; the default comparator is
0053: * either {@link FastComparator#DIRECT DIRECT} or
0054: * {@link FastComparator#REHASH REHASH} based upon the current <a href=
0055: * "{@docRoot}/overview-summary.html#configuration">Javolution
0056: * Configuration</a>. Users may explicitly set the key comparator to
0057: * {@link FastComparator#DIRECT DIRECT} for optimum performance
0058: * when the hash codes are well distributed for all run-time platforms
0059: * (e.g. calculated hash codes).</p>
0060: *
0061: * <p> Custom key comparators are extremely useful for value retrieval when
0062: * map's keys and argument keys are not of the same class (such as
0063: * {@link String} and {@link javolution.text.Text Text}
0064: * ({@link FastComparator#LEXICAL LEXICAL})), to substitute more efficient
0065: * hash code calculations ({@link FastComparator#STRING STRING})
0066: * or for identity maps ({@link FastComparator#IDENTITY IDENTITY}):[code]
0067: * FastMap identityMap = new FastMap().setKeyComparator(FastComparator.IDENTITY);
0068: * [/code]</p>
0069: *
0070: * <p> {@link FastMap.Entry} can quickly be iterated over (forward or backward)
0071: * without using iterators. For example:[code]
0072: * FastMap<String, Thread> map = ...;
0073: * for (FastMap.Entry<String, Thread> e = map.head(), end = map.tail(); (e = e.getNext()) != end;) {
0074: * String key = e.getKey(); // No typecast necessary.
0075: * Thread value = e.getValue(); // No typecast necessary.
0076: * }[/code]</p>
0077: *
0078: * <p> Custom map implementations may override the {@link #newEntry} method
0079: * in order to return their own {@link Entry} implementation (with
0080: * additional fields for example).</p>
0081: *
0082: * <p> {@link FastMap} are {@link Reusable reusable}; they maintain an
0083: * internal pool of <code>Map.Entry</code> objects. When an entry is removed
0084: * from a map, it is automatically restored to its pool (unless the map
0085: * is shared in which case the removed entry is candidate for garbage
0086: * collection as it cannot be safely recycled).</p>
0087: *
0088: * <p> Shared maps do not use internal synchronization, except in case of
0089: * concurrent modifications of the map structure (entry added/deleted).
0090: * Reads and iterations are never synchronized and never blocking.
0091: * With regards to the memory model, shared maps are equivalent to shared
0092: * non-volatile variables (no "happen before" guarantee). There are
0093: * typically used as lookup tables. For example:[code]
0094: * public class Unit {
0095: * static FastMap<Unit, String> labels = new FastMap().setShared(true);
0096: * ...
0097: * public String toString() {
0098: * String label = labels.get(this); // No synchronization.
0099: * return label != null ? label : makeLabel();
0100: * }
0101: * }[/code]</p>
0102: *
0103: * <p> <b>Implementation Note:</b> To maintain time-determinism, rehash/resize
0104: * is performed only when the map's size is small (see chart). For large
0105: * maps (size > 512), the collection is divided recursively into (64)
0106: * smaller sub-maps. The cost of the dispatching (based upon hashcode
0107: * value) has been measured to be at most 20% of the access time
0108: * (and most often way less).</p>
0109: *
0110: * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle </a>
0111: * @version 5.2, September 11, 2007
0112: */
0113: public class FastMap/*<K,V>*/implements Map/*<K,V>*/, Reusable,
0114: XMLSerializable, Realtime {
0115:
0116: // We do a full resize (and rehash) only when the capacity is less than C1.
0117: // For large maps we dispatch to sub-maps.
0118:
0119: private static final int B0 = 4; // Initial capacity in bits.
0120:
0121: private static final int C0 = 1 << B0; // Initial capacity (16)
0122:
0123: private static final int B1 = 10; // Entries array resize limit in bits.
0124:
0125: private static final int C1 = 1 << B1; // Entries array resize limit (1024).
0126:
0127: private static final int B2 = B1 - B0; // Sub-maps array length in bits.
0128:
0129: private static final int C2 = 1 << B2; // Sub-maps array length (64).
0130:
0131: /**
0132: * Holds the head entry to which the first entry attaches.
0133: * The head entry never changes (entries always added last).
0134: */
0135: private transient Entry/*<K,V>*/_head;
0136:
0137: /**
0138: * Holds the tail entry to which the last entry attaches.
0139: * The tail entry changes as entries are added/removed.
0140: */
0141: private transient Entry/*<K,V>*/_tail;
0142:
0143: /**
0144: * Holds the map's entries.
0145: */
0146: private transient Entry/*<K,V>*/[] _entries;
0147:
0148: /**
0149: * Holds the number of user entry in the entry table.
0150: */
0151: private transient int _entryCount;
0152:
0153: /**
0154: * Holds the number of NULL (when entry removed). The number has to be
0155: * taken into account to clean-up the table if too many NULL are present.
0156: */
0157: private transient int _nullCount;
0158:
0159: /**
0160: * Holds sub-maps (for large collection).
0161: */
0162: private transient FastMap[] _subMaps;
0163:
0164: /**
0165: * Indicates if sub-maps are active.
0166: */
0167: private transient boolean _useSubMaps;
0168:
0169: /**
0170: * The hash shift (for sub-maps to discard bits already taken into account).
0171: */
0172: private transient int _keyShift;
0173:
0174: /**
0175: * Holds the values view.
0176: */
0177: private transient Values _values;
0178:
0179: /**
0180: * Holds the key set view.
0181: */
0182: private transient KeySet _keySet;
0183:
0184: /**
0185: * Holds the entry set view.
0186: */
0187: private transient EntrySet _entrySet;
0188:
0189: /**
0190: * Holds the unmodifiable view.
0191: */
0192: private transient Map/*<K,V>*/_unmodifiable;
0193:
0194: /**
0195: * Holds the key comparator.
0196: */
0197: private transient FastComparator _keyComparator;
0198:
0199: /**
0200: * Indicates if key comparator is direct.
0201: */
0202: private transient boolean _isDirectKeyComparator;
0203:
0204: /**
0205: * Holds the value comparator.
0206: */
0207: private transient FastComparator _valueComparator;
0208:
0209: /**
0210: * Indicates if this map is shared (thread-safe).
0211: */
0212: private transient boolean _isShared;
0213:
0214: /**
0215: * Creates a map whose capacity increment smoothly without large resize
0216: * operations.
0217: */
0218: public FastMap() {
0219: this (4);
0220: }
0221:
0222: /**
0223: * Creates a persistent map associated to the specified unique identifier
0224: * (convenience method).
0225: *
0226: * @param id the unique identifier for this map.
0227: * @throws IllegalArgumentException if the identifier is not unique.
0228: * @see javolution.context.PersistentContext.Reference
0229: */
0230: public FastMap(String id) {
0231: this ();
0232: new PersistentContext.Reference(id, this ) {
0233: protected void notifyChange() {
0234: FastMap.this .clear();
0235: FastMap.this .putAll((FastMap) this .get());
0236: }
0237: };
0238: }
0239:
0240: /**
0241: * Creates a map of specified maximum size (a full resize may occur if the
0242: * specififed capacity is exceeded).
0243: *
0244: * @param capacity the maximum capacity.
0245: */
0246: public FastMap(int capacity) {
0247: setKeyComparator(FastComparator.DEFAULT);
0248: setValueComparator(FastComparator.DEFAULT);
0249: setup(capacity);
0250: }
0251:
0252: private void setup(int capacity) {
0253: int tableLength = C0;
0254: while (tableLength < capacity) {
0255: tableLength <<= 1;
0256: }
0257: _entries = (Entry/*<K,V>*/[]) new Entry[tableLength << 1];
0258: _head = newEntry();
0259: _tail = newEntry();
0260: _head._next = _tail;
0261: _tail._previous = _head;
0262: Entry previous = _tail;
0263: for (int i = 0; i++ < capacity;) {
0264: Entry newEntry = newEntry();
0265: newEntry._previous = previous;
0266: previous._next = newEntry;
0267: previous = newEntry;
0268: }
0269: }
0270:
0271: /**
0272: * Creates a map containing the specified entries, in the order they
0273: * are returned by the map iterator.
0274: *
0275: * @param map the map whose entries are to be placed into this map.
0276: */
0277: public FastMap(Map/*<? extends K, ? extends V>*/map) {
0278: this (map.size());
0279: putAll(map);
0280: }
0281:
0282: /**
0283: * Used solely for sub-maps (we don't need head or tail just the table).
0284: */
0285: private FastMap(Entry[] entries) {
0286: _entries = entries;
0287: }
0288:
0289: /**
0290: * Returns a potentially {@link #recycle recycled} map instance.
0291: *
0292: * @return a new, preallocated or recycled map instance.
0293: */
0294: public static/*<K,V>*/FastMap/*<K,V>*/newInstance() {
0295: return (FastMap/*<K,V>*/) FACTORY.object();
0296: }
0297:
0298: /**
0299: * Recycles the specified map instance.
0300: *
0301: * @param instance the map instance to recycle.
0302: */
0303: public static void recycle(FastMap instance) {
0304: FACTORY.recycle(instance);
0305: }
0306:
0307: /**
0308: * Returns the head entry of this map.
0309: *
0310: * @return the entry such as <code>head().getNext()</code> holds
0311: * the first map entry.
0312: */
0313: public final Entry/*<K,V>*/head() {
0314: return _head;
0315: }
0316:
0317: /**
0318: * Returns the tail entry of this map.
0319: *
0320: * @return the entry such as <code>tail().getPrevious()</code>
0321: * holds the last map entry.
0322: */
0323: public final Entry/*<K,V>*/tail() {
0324: return _tail;
0325: }
0326:
0327: /**
0328: * Returns the number of key-value mappings in this {@link FastMap}.
0329: *
0330: * <p>Note: If concurrent updates are performed, application should not
0331: * rely upon the size during iterations.</p>
0332: *
0333: * @return this map's size.
0334: */
0335: public final int size() {
0336: if (!_useSubMaps)
0337: return _entryCount;
0338: int sum = 0;
0339: for (int i = 0; i < _subMaps.length;) {
0340: sum += _subMaps[i++].size();
0341: }
0342: return sum;
0343: }
0344:
0345: /**
0346: * Indicates if this map contains no key-value mappings.
0347: *
0348: * @return <code>true</code> if this map contains no key-value mappings;
0349: * <code>false</code> otherwise.
0350: */
0351: public final boolean isEmpty() {
0352: return _head._next == _tail;
0353: }
0354:
0355: /**
0356: * Indicates if this map contains a mapping for the specified key.
0357: *
0358: * @param key the key whose presence in this map is to be tested.
0359: * @return <code>true</code> if this map contains a mapping for the
0360: * specified key; <code>false</code> otherwise.
0361: * @throws NullPointerException if the key is <code>null</code>.
0362: */
0363: public final boolean containsKey(Object key) {
0364: return getEntry(key) != null;
0365: }
0366:
0367: /**
0368: * Indicates if this map associates one or more keys to the specified value.
0369: *
0370: * @param value the value whose presence in this map is to be tested.
0371: * @return <code>true</code> if this map maps one or more keys to the
0372: * specified value.
0373: * @throws NullPointerException if the key is <code>null</code>.
0374: */
0375: public final boolean containsValue(Object value) {
0376: return values().contains(value);
0377: }
0378:
0379: /**
0380: * Returns the value to which this map associates the specified key.
0381: * This method is always thread-safe regardless whether or not the map
0382: * is marked {@link #isShared() shared}.
0383: *
0384: * @param key the key whose associated value is to be returned.
0385: * @return the value to which this map maps the specified key, or
0386: * <code>null</code> if there is no mapping for the key.
0387: * @throws NullPointerException if key is <code>null</code>.
0388: */
0389: public final Object/*{V}*/get(Object key) {
0390: Entry/*<K,V>*/entry = getEntry(key);
0391: return (entry != null) ? entry._value : null;
0392: }
0393:
0394: /**
0395: * Returns the entry with the specified key.
0396: * This method is always thread-safe without synchronization.
0397: *
0398: * @param key the key whose associated entry is to be returned.
0399: * @return the entry for the specified key or <code>null</code> if none.
0400: */
0401: public final Entry/*<K,V>*/getEntry(Object key) {
0402: return getEntry(key, _isDirectKeyComparator ? key.hashCode()
0403: : _keyComparator.hashCodeOf(key));
0404: }
0405:
0406: private final Entry getEntry(Object key, int keyHash) {
0407: final FastMap map = getSubMap(keyHash);
0408: final Entry[] entries = map._entries; // Atomic.
0409: final int mask = entries.length - 1;
0410: for (int i = keyHash >> map._keyShift;; i++) {
0411: Entry entry = entries[i & mask];
0412: if (entry == null)
0413: return null;
0414: if ((key == entry._key)
0415: || ((keyHash == entry._keyHash) && (_isDirectKeyComparator ? key
0416: .equals(entry._key)
0417: : _keyComparator.areEqual(key, entry._key))))
0418: return entry;
0419: }
0420: }
0421:
0422: private final FastMap getSubMap(int keyHash) {
0423: return _useSubMaps ? _subMaps[keyHash & (C2 - 1)]
0424: .getSubMap(keyHash >> B2) : this ;
0425: }
0426:
0427: /**
0428: * Associates the specified value with the specified key in this map.
0429: * If this map previously contained a mapping for this key, the old value
0430: * is replaced. For {@link #isShared() shared} map, internal synchronization
0431: * is performed only when new entries are created.
0432: *
0433: * @param key the key with which the specified value is to be associated.
0434: * @param value the value to be associated with the specified key.
0435: * @return the previous value associated with specified key, or
0436: * <code>null</code> if there was no mapping for key. A
0437: * <code>null</code> return can also indicate that the map
0438: * previously associated <code>null</code> with the specified key.
0439: * @throws NullPointerException if the key is <code>null</code>.
0440: */
0441: public final Object/*{V}*/put(Object/*{K}*/key,
0442: Object/*{V}*/value) {
0443: return (Object/*{V}*/) put(key, value,
0444: _isDirectKeyComparator ? key.hashCode()
0445: : _keyComparator.hashCodeOf(key), _isShared,
0446: false);
0447: }
0448:
0449: private final Object put(Object key, Object value, int keyHash,
0450: boolean concurrent, boolean noReplace) {
0451: final FastMap map = getSubMap(keyHash);
0452: final Entry[] entries = map._entries; // Atomic.
0453: final int mask = entries.length - 1;
0454: int slot = -1;
0455: for (int i = keyHash >> map._keyShift;; i++) {
0456: Entry entry = entries[i & mask];
0457: if (entry == null) {
0458: slot = slot < 0 ? i & mask : slot;
0459: break;
0460: } else if (entry == Entry.NULL) {
0461: slot = slot < 0 ? i & mask : slot;
0462: } else if ((key == entry._key)
0463: || ((keyHash == entry._keyHash) && (_isDirectKeyComparator ? key
0464: .equals(entry._key)
0465: : _keyComparator.areEqual(key, entry._key)))) {
0466: if (noReplace)
0467: return entry._value;
0468: Object prevValue = entry._value;
0469: entry._value = value;
0470: return prevValue;
0471: }
0472: }
0473:
0474: // Add new entry (synchronize if concurrent).
0475: if (concurrent) {
0476: synchronized (this ) {
0477: return put(key, value, keyHash, false, noReplace);
0478: }
0479: }
0480:
0481: // Setup entry.
0482: final Entry entry = _tail;
0483: entry._key = key;
0484: entry._value = value;
0485: entry._keyHash = keyHash;
0486: if (entry._next == null) {
0487: createNewEntries();
0488: }
0489: entries[slot] = entry;
0490: map._entryCount += ONE_VOLATILE; // Prevents reordering.
0491: _tail = _tail._next;
0492:
0493: if (map._entryCount + map._nullCount > (entries.length >> 1)) { // Table more than half empty.
0494: map.resizeTable(_isShared);
0495: }
0496: return null;
0497: }
0498:
0499: private void createNewEntries() { // Increase the number of entries.
0500: MemoryArea.getMemoryArea(this ).executeInArea(new Runnable() {
0501: public void run() {
0502: Entry previous = _tail;
0503: for (int i = 0; i < 8; i++) { // Creates 8 entries at a time.
0504: Entry/*<K,V>*/newEntry = newEntry();
0505: newEntry._previous = previous;
0506: previous._next = newEntry;
0507: previous = newEntry;
0508: }
0509: }
0510: });
0511: }
0512:
0513: // This method is called only on final sub-maps.
0514: private void resizeTable(final boolean isShared) {
0515: MemoryArea.getMemoryArea(this ).executeInArea(new Runnable() {
0516: public void run() {
0517:
0518: // Reset the NULL count (we don't copy Entry.NULL).
0519: final int nullCount = _nullCount;
0520: _nullCount = 0;
0521:
0522: // Check if we can just cleanup (remove NULL entries).
0523: if (nullCount > _entryCount) { // Yes.
0524: if (isShared) { // Replaces with a new table.
0525: Entry[] tmp = new Entry[_entries.length];
0526: copyEntries(_entries, tmp, _entries.length);
0527: _entries = tmp;
0528: } else { // We need a temporary buffer.
0529: Object[] tmp = (Object[]) ArrayFactory.OBJECTS_FACTORY
0530: .array(_entries.length);
0531: System.arraycopy(_entries, 0, tmp, 0,
0532: _entries.length);
0533: FastMap.reset(_entries); // Ok not shared.
0534: copyEntries(tmp, _entries, _entries.length);
0535: FastMap.reset(tmp); // Clear references.
0536: ArrayFactory.OBJECTS_FACTORY.recycle(tmp);
0537: }
0538: return;
0539: }
0540:
0541: // Resize if size is small.
0542: int tableLength = _entries.length << 1;
0543: if (tableLength <= C1) { // Ok to resize.
0544: Entry[] tmp = new Entry[tableLength];
0545: copyEntries(_entries, tmp, _entries.length);
0546: _entries = tmp;
0547: return;
0548: }
0549:
0550: // No choice but to use sub-maps.
0551: if (_subMaps == null) { // Creates sub-maps.
0552: _subMaps = newSubMaps(tableLength >> (B2 - 1));
0553: }
0554:
0555: // Copies the current entries to sub-maps.
0556: for (int i = 0; i < _entries.length;) {
0557: Entry entry = _entries[i++];
0558: if ((entry == null) || (entry == Entry.NULL))
0559: continue;
0560: FastMap subMap = _subMaps[(entry._keyHash >> _keyShift)
0561: & (C2 - 1)];
0562: subMap.mapEntry(entry);
0563: if (((subMap._entryCount + subMap._nullCount) << 1) >= subMap._entries.length) {
0564: // Serious problem submap already full, don't use submap just resize.
0565: LogContext
0566: .warning("Unevenly distributed hash code - Degraded Preformance");
0567: Entry[] tmp = new Entry[tableLength];
0568: copyEntries(_entries, tmp, _entries.length);
0569: _entries = tmp;
0570: _subMaps = null; // Discards sub-maps.
0571: return;
0572: }
0573: }
0574: _useSubMaps = ONE_VOLATILE == 1 ? true : false; // Prevents reordering.
0575: }
0576: });
0577: }
0578:
0579: private FastMap[] newSubMaps(int capacity) {
0580: FastMap[] subMaps = new FastMap[C2];
0581: for (int i = 0; i < C2; i++) {
0582: FastMap subMap = new FastMap(new Entry[capacity]);
0583: subMap._keyShift = B2 + _keyShift;
0584: subMaps[i] = subMap;
0585: }
0586: return subMaps;
0587: }
0588:
0589: // Adds the specified entry to this map table.
0590: private void mapEntry(Entry entry) {
0591: final int mask = _entries.length - 1;
0592: for (int i = entry._keyHash >> _keyShift;; i++) {
0593: Entry e = _entries[i & mask];
0594: if (e == null) {
0595: _entries[i & mask] = entry;
0596: break;
0597: }
0598: }
0599: _entryCount++;
0600: }
0601:
0602: // The destination table must be empty.
0603: private void copyEntries(Object[] from, Entry[] to, int count) {
0604: final int mask = to.length - 1;
0605: for (int i = 0; i < count;) {
0606: Entry entry = (Entry) from[i++];
0607: if ((entry == null) || (entry == Entry.NULL))
0608: continue;
0609: for (int j = entry._keyHash >> _keyShift;; j++) {
0610: Entry tmp = to[j & mask];
0611: if (tmp == null) {
0612: to[j & mask] = entry;
0613: break;
0614: }
0615: }
0616: }
0617: }
0618:
0619: /**
0620: * Copies all of the mappings from the specified map to this map.
0621: *
0622: * @param map the mappings to be stored in this map.
0623: * @throws NullPointerException the specified map is <code>null</code>,
0624: * or the specified map contains <code>null</code> keys.
0625: */
0626: public final void putAll(Map/*<? extends K, ? extends V>*/map) {
0627: for (Iterator i = map.entrySet().iterator(); i.hasNext();) {
0628: Map.Entry/*<K,V>*/e = (Map.Entry/*<K,V>*/) i.next();
0629: put(e.getKey(), e.getValue());
0630: }
0631: }
0632:
0633: /**
0634: * Associates the specified value only if the specified key is not already
0635: * associated. This is equivalent to:[code]
0636: * if (!map.containsKey(key))
0637: * return map.put(key, value);
0638: * else
0639: * return map.get(key);[/code]
0640: * except that for shared maps the action is performed atomically.
0641: * For shared maps, this method guarantees that if two threads try to
0642: * put the same key concurrently only one of them will succeed.
0643: *
0644: * @param key the key with which the specified value is to be associated.
0645: * @param value the value to be associated with the specified key.
0646: * @return the previous value associated with specified key, or
0647: * <code>null</code> if there was no mapping for key. A
0648: * <code>null</code> return can also indicate that the map
0649: * previously associated <code>null</code> with the specified key.
0650: * @throws NullPointerException if the key is <code>null</code>.
0651: */
0652: public final Object/*{V}*/putIfAbsent(Object/*{K}*/key,
0653: Object/*{V}*/value) {
0654: return (Object/*{V}*/) put(key, value,
0655: _isDirectKeyComparator ? key.hashCode()
0656: : _keyComparator.hashCodeOf(key), _isShared,
0657: true);
0658: }
0659:
0660: /**
0661: * Removes the entry for the specified key if present. The entry
0662: * is recycled if the map is not marked as {@link #isShared shared};
0663: * otherwise the entry is candidate for garbage collection.
0664: *
0665: * <p> Note: Shared maps in ImmortalMemory (e.g. static) should not remove
0666: * their entries as it could cause a memory leak (ImmortalMemory
0667: * is never garbage collected), instead they should set their
0668: * entry values to <code>null</code>.</p>
0669: *
0670: * @param key the key whose mapping is to be removed from the map.
0671: * @return previous value associated with specified key, or
0672: * <code>null</code> if there was no mapping for key. A
0673: * <code>null</code> return can also indicate that the map
0674: * previously associated <code>null</code> with the specified key.
0675: * @throws NullPointerException if the key is <code>null</code>.
0676: */
0677: public final Object/*{V}*/remove(Object key) {
0678: return (Object/*{V}*/) remove(key,
0679: _isDirectKeyComparator ? key.hashCode()
0680: : _keyComparator.hashCodeOf(key), _isShared);
0681: }
0682:
0683: private final Object remove(Object key, int keyHash,
0684: boolean concurrent) {
0685: final FastMap map = getSubMap(keyHash);
0686: final Entry[] entries = map._entries; // Atomic.
0687: final int mask = entries.length - 1;
0688: for (int i = keyHash >> map._keyShift;; i++) {
0689: Entry entry = entries[i & mask];
0690: if (entry == null)
0691: return null; // No entry.
0692: if ((key == entry._key)
0693: || ((keyHash == entry._keyHash) && (_isDirectKeyComparator ? key
0694: .equals(entry._key)
0695: : _keyComparator.areEqual(key, entry._key)))) {
0696: // Found the entry.
0697: if (concurrent) {
0698: synchronized (this ) {
0699: return remove(key, keyHash, false);
0700: }
0701: }
0702:
0703: // Detaches entry from list.
0704: entry._previous._next = entry._next;
0705: entry._next._previous = entry._previous;
0706:
0707: // Removes from table.
0708: entries[i & mask] = Entry.NULL;
0709: map._nullCount++;
0710: map._entryCount--;
0711:
0712: Object prevValue = entry._value;
0713: if (!_isShared) { // Clears key/value and recycle.
0714: entry._key = null;
0715: entry._value = null;
0716:
0717: final Entry next = _tail._next;
0718: entry._previous = _tail;
0719: entry._next = next;
0720: _tail._next = entry;
0721: if (next != null) {
0722: next._previous = entry;
0723: }
0724: }
0725: return prevValue;
0726: }
0727: }
0728: }
0729:
0730: /**
0731: * <p> Sets the shared status of this map (whether the map is thread-safe
0732: * or not). Shared maps are typically used for lookup table (e.g. static
0733: * instances in ImmortalMemory). They support concurrent access
0734: * (e.g. iterations) without synchronization, the maps updates
0735: * themselves are synchronized internally.</p>
0736: * <p> Unlike <code>ConcurrentHashMap</code> access to a shared map never
0737: * blocks. Retrieval reflects the map state not older than the last
0738: * time the accessing thread has been synchronized (for multi-processors
0739: * systems synchronizing ensures that the CPU internal cache is not
0740: * stale).</p>
0741: *
0742: * @param isShared <code>true</code> if this map is shared and thread-safe;
0743: * <code>false</code> otherwise.
0744: * @return <code>this</code>
0745: */
0746: public FastMap/*<K,V>*/setShared(boolean isShared) {
0747: _isShared = isShared;
0748: return this ;
0749: }
0750:
0751: /**
0752: * Indicates if this map supports concurrent operations without
0753: * synchronization (default unshared).
0754: *
0755: * @return <code>true</code> if this map is thread-safe; <code>false</code>
0756: * otherwise.
0757: */
0758: public boolean isShared() {
0759: return _isShared;
0760: }
0761:
0762: /**
0763: * Sets the key comparator for this fast map.
0764: *
0765: * @param keyComparator the key comparator.
0766: * @return <code>this</code>
0767: */
0768: public FastMap/*<K,V>*/setKeyComparator(
0769: FastComparator/*<? super K>*/keyComparator) {
0770: _keyComparator = keyComparator;
0771: _isDirectKeyComparator = (keyComparator instanceof FastComparator.Direct)
0772: || ((_keyComparator instanceof FastComparator.Default) && !FastComparator._Rehash);
0773: return this ;
0774: }
0775:
0776: /**
0777: * Returns the key comparator for this fast map.
0778: *
0779: * @return the key comparator.
0780: */
0781: public FastComparator/*<? super K>*/getKeyComparator() {
0782: return _keyComparator;
0783: }
0784:
0785: /**
0786: * Sets the value comparator for this map.
0787: *
0788: * @param valueComparator the value comparator.
0789: * @return <code>this</code>
0790: */
0791: public FastMap/*<K,V>*/setValueComparator(
0792: FastComparator/*<? super V>*/valueComparator) {
0793: _valueComparator = valueComparator;
0794: return this ;
0795: }
0796:
0797: /**
0798: * Returns the value comparator for this fast map.
0799: *
0800: * @return the value comparator.
0801: */
0802: public FastComparator/*<? super V>*/getValueComparator() {
0803: return _valueComparator;
0804: }
0805:
0806: /**
0807: * Removes all map's entries. The entries are removed and recycled;
0808: * unless this map is {@link #isShared shared} in which case the entries
0809: * are candidate for garbage collection.
0810: *
0811: * <p> Note: Shared maps in ImmortalMemory (e.g. static) should not remove
0812: * their entries as it could cause a memory leak (ImmortalMemory
0813: * is never garbage collected), instead they should set their
0814: * entry values to <code>null</code>.</p>
0815: */
0816: public final void clear() {
0817: if (_isShared) {
0818: clearShared();
0819: return;
0820: }
0821: // Clears keys, values and recycle entries.
0822: for (Entry e = _head, end = _tail; (e = e._next) != end;) {
0823: e._key = null;
0824: e._value = null;
0825: }
0826: _tail = _head._next; // Reuse linked list of entries.
0827: clearTables();
0828: }
0829:
0830: private void clearTables() {
0831: if (_useSubMaps) {
0832: for (int i = 0; i < C2;) {
0833: _subMaps[i++].clearTables();
0834: }
0835: _useSubMaps = false;
0836: }
0837: FastMap.reset(_entries);
0838: _nullCount = 0;
0839: _entryCount = 0;
0840: }
0841:
0842: private synchronized void clearShared() {
0843: // We do not modify the linked list of entries (e.g. key, values)
0844: // Concurrent iterations can still proceed unaffected.
0845: // The linked list fragment is detached from the map and will be
0846: // garbage collected once all concurrent iterations are completed.
0847: _head._next = _tail;
0848: _tail._previous = _head;
0849:
0850: // We also detach the main entry table and sub-maps.
0851: MemoryArea.getMemoryArea(this ).executeInArea(new Runnable() {
0852: public void run() {
0853: _entries = (Entry/*<K,V>*/[]) new Entry[C0];
0854: if (_useSubMaps) {
0855: _useSubMaps = false;
0856: _subMaps = newSubMaps(C0);
0857: }
0858: _entryCount = 0;
0859: _nullCount = 0;
0860: }
0861: });
0862: }
0863:
0864: /**
0865: * Compares the specified object with this map for equality.
0866: * Returns <code>true</code> if the given object is also a map and the two
0867: * maps represent the same mappings (regardless of collection iteration
0868: * order).
0869: *
0870: * @param obj the object to be compared for equality with this map.
0871: * @return <code>true</code> if the specified object is equal to this map;
0872: * <code>false</code> otherwise.
0873: */
0874: public boolean equals(Object obj) {
0875: if (obj == this ) {
0876: return true;
0877: } else if (obj instanceof Map) {
0878: Map/*<?,?>*/that = (Map) obj;
0879: return this .entrySet().equals(that.entrySet());
0880: } else {
0881: return false;
0882: }
0883: }
0884:
0885: /**
0886: * Returns the hash code value for this map.
0887: *
0888: * @return the hash code value for this map.
0889: */
0890: public int hashCode() {
0891: int code = 0;
0892: for (Entry e = _head, end = _tail; (e = e._next) != end;) {
0893: code += e.hashCode();
0894: }
0895: return code;
0896: }
0897:
0898: /**
0899: * Returns the textual representation of this map.
0900: *
0901: * @return the textual representation of the entry set.
0902: */
0903: public Text toText() {
0904: return Text.valueOf(entrySet());
0905: }
0906:
0907: /**
0908: * Returns the <code>String</code> representation of this
0909: * {@link FastMap}.
0910: *
0911: * @return <code>toText().toString()</code>
0912: */
0913: public final String toString() {
0914: return toText().toString();
0915: }
0916:
0917: /**
0918: * Returns a new entry for this map; this method can be overriden by
0919: * custom map implementations.
0920: *
0921: * @return a new entry.
0922: */
0923: protected Entry/*<K,V>*/newEntry() {
0924: return new Entry();
0925: }
0926:
0927: /**
0928: * Prints the current statistics on this map.
0929: * This method may help identify poorly defined hash functions.
0930: * The average distance should be less than 20% (most of the entries
0931: * are in their slots or close).
0932: *
0933: * @param out the stream to use for output (e.g. <code>System.out</code>)
0934: */
0935: public void printStatistics(PrintStream out) {
0936: long sum = this .getSumDistance();
0937: int size = this .size();
0938: int avgDistancePercent = size != 0 ? (int) (100 * sum / size)
0939: : 0;
0940: synchronized (out) {
0941: out.print("SIZE: " + size);
0942: out.print(", ENTRIES: " + getCapacity());
0943: out.print(", SLOTS: " + getTableLength());
0944: out.print(", USE SUB-MAPS: " + _useSubMaps);
0945: out.print(", SUB-MAPS DEPTH: " + getSubMapDepth());
0946: out.print(", NULL COUNT: " + _nullCount);
0947: out.print(", IS SHARED: " + _isShared);
0948: out.print(", AVG DISTANCE: " + avgDistancePercent + "%");
0949: out.print(", MAX DISTANCE: " + getMaximumDistance());
0950: out.println();
0951: }
0952: }
0953:
0954: private int getTableLength() {
0955: if (_useSubMaps) {
0956: int sum = 0;
0957: for (int i = 0; i < C2; i++) {
0958: sum += _subMaps[i].getTableLength();
0959: }
0960: return sum;
0961: } else {
0962: return _entries.length;
0963: }
0964: }
0965:
0966: private int getCapacity() {
0967: int capacity = 0;
0968: for (Entry e = _head; (e = e._next) != null;) {
0969: capacity++;
0970: }
0971: return capacity - 1;
0972: }
0973:
0974: private int getMaximumDistance() {
0975: int max = 0;
0976: if (_useSubMaps) {
0977: for (int i = 0; i < C2; i++) {
0978: int subMapMax = _subMaps[i].getMaximumDistance();
0979: max = MathLib.max(max, subMapMax);
0980: }
0981: return max;
0982: }
0983: for (int i = 0; i < _entries.length; i++) {
0984: Entry entry = _entries[i];
0985: if ((entry != null) && (entry != Entry.NULL)) {
0986: int slot = (entry._keyHash >> _keyShift)
0987: & (_entries.length - 1);
0988: int distanceToSlot = i - slot;
0989: if (distanceToSlot < 0)
0990: distanceToSlot += _entries.length;
0991: if (distanceToSlot > max) {
0992: max = distanceToSlot;
0993: }
0994: }
0995: }
0996: return max;
0997: }
0998:
0999: private long getSumDistance() {
1000: long sum = 0;
1001: if (_useSubMaps) {
1002: for (int i = 0; i < C2; i++) {
1003: sum += _subMaps[i].getSumDistance();
1004: }
1005: return sum;
1006: }
1007: for (int i = 0; i < _entries.length; i++) {
1008: Entry entry = _entries[i];
1009: if ((entry != null) && (entry != Entry.NULL)) {
1010: int slot = (entry._keyHash >> _keyShift)
1011: & (_entries.length - 1);
1012: int distanceToSlot = i - slot;
1013: if (distanceToSlot < 0)
1014: distanceToSlot += _entries.length;
1015: sum += distanceToSlot;
1016: }
1017: }
1018: return sum;
1019: }
1020:
1021: private int getSubMapDepth() {
1022: if (_useSubMaps) {
1023: int depth = 0;
1024: for (int i = 0; i < C2; i++) {
1025: int subMapDepth = _subMaps[i].getSubMapDepth();
1026: depth = MathLib.max(depth, subMapDepth);
1027: }
1028: return depth + 1;
1029: } else {
1030: return 0;
1031: }
1032: }
1033:
1034: /**
1035: * Returns a {@link FastCollection} view of the values contained in this
1036: * map. The collection is backed by the map, so changes to the
1037: * map are reflected in the collection, and vice-versa. The collection
1038: * supports element removal, which removes the corresponding mapping from
1039: * this map, via the <code>Iterator.remove</code>,
1040: * <code>Collection.remove</code>, <code>removeAll</code>,
1041: * <code>retainAll</code> and <code>clear</code> operations.
1042: * It does not support the <code>add</code> or <code>addAll</code>
1043: * operations.
1044: *
1045: * @return a collection view of the values contained in this map
1046: * (instance of {@link FastCollection}).
1047: */
1048: public final Collection/*<V>*/values() {
1049: if (_values == null) {
1050: MemoryArea.getMemoryArea(this ).executeInArea(
1051: new Runnable() {
1052: public void run() {
1053: _values = new Values();
1054: }
1055: });
1056: }
1057: return _values;
1058: }
1059:
1060: private final class Values extends FastCollection {
1061:
1062: public int size() {
1063: return FastMap.this .size();
1064: }
1065:
1066: public void clear() {
1067: FastMap.this .clear();
1068: }
1069:
1070: public Record head() {
1071: return FastMap.this ._head;
1072: }
1073:
1074: public Record tail() {
1075: return FastMap.this ._tail;
1076: }
1077:
1078: public Object valueOf(Record record) {
1079: return ((Entry) record)._value;
1080: }
1081:
1082: public void delete(Record record) {
1083: FastMap.this .remove(((Entry) record).getKey());
1084: }
1085:
1086: public FastComparator getValueComparator() {
1087: return _valueComparator;
1088: }
1089:
1090: public Iterator iterator() {
1091: return ValueIterator.valueOf(FastMap.this );
1092: }
1093: }
1094:
1095: // Value iterator optimization.
1096: private static final class ValueIterator implements Iterator {
1097:
1098: private static final ObjectFactory FACTORY = new ObjectFactory() {
1099: protected Object create() {
1100: return new ValueIterator();
1101: }
1102:
1103: protected void cleanup(Object obj) {
1104: ValueIterator iterator = (ValueIterator) obj;
1105: iterator._map = null;
1106: iterator._current = null;
1107: iterator._next = null;
1108: iterator._tail = null;
1109: }
1110: };
1111:
1112: private FastMap _map;
1113:
1114: private Entry _current;
1115:
1116: private Entry _next;
1117:
1118: private Entry _tail;
1119:
1120: public static ValueIterator valueOf(FastMap map) {
1121: ValueIterator iterator = (ValueIterator) ValueIterator.FACTORY
1122: .object();
1123: iterator._map = map;
1124: iterator._next = map._head._next;
1125: iterator._tail = map._tail;
1126: return iterator;
1127: }
1128:
1129: private ValueIterator() {
1130: }
1131:
1132: public boolean hasNext() {
1133: return (_next != _tail);
1134: }
1135:
1136: public Object next() {
1137: if (_next == _tail)
1138: throw new NoSuchElementException();
1139: _current = _next;
1140: _next = _next._next;
1141: return _current._value;
1142: }
1143:
1144: public void remove() {
1145: if (_current != null) {
1146: _next = _current._next;
1147: _map.remove(_current._key);
1148: _current = null;
1149: } else {
1150: throw new IllegalStateException();
1151: }
1152: }
1153: }
1154:
1155: /**
1156: * Returns a {@link FastCollection} view of the mappings contained in this
1157: * map. Each element in the returned collection is a
1158: * <code>FastMap.Entry</code>. The collection is backed by the map, so
1159: * changes to the map are reflected in the collection, and vice-versa. The
1160: * collection supports element removal, which removes the corresponding
1161: * mapping from this map, via the <code>Iterator.remove</code>,
1162: * <code>Collection.remove</code>,<code>removeAll</code>,
1163: * <code>retainAll</code>, and <code>clear</code> operations. It does
1164: * not support the <code>add</code> or <code>addAll</code> operations.
1165: *
1166: * @return a collection view of the mappings contained in this map
1167: * (instance of {@link FastCollection}).
1168: */
1169: public final Set/*<Map.Entry<K,V>>*/entrySet() {
1170: if (_entrySet == null) {
1171: MemoryArea.getMemoryArea(this ).executeInArea(
1172: new Runnable() {
1173: public void run() {
1174: _entrySet = new EntrySet();
1175: }
1176: });
1177: }
1178: return _entrySet;
1179: }
1180:
1181: private final class EntrySet extends FastCollection implements Set {
1182:
1183: public int size() {
1184: return FastMap.this .size();
1185: }
1186:
1187: public void clear() {
1188: FastMap.this .clear();
1189: }
1190:
1191: public boolean contains(Object obj) { // Optimization.
1192: if (obj instanceof Map.Entry) {
1193: Map.Entry thatEntry = (Entry) obj;
1194: Entry this Entry = getEntry(thatEntry.getKey());
1195: if (this Entry == null)
1196: return false;
1197: return _valueComparator.areEqual(this Entry.getValue(),
1198: thatEntry.getValue());
1199: } else {
1200: return false;
1201: }
1202: }
1203:
1204: public Text toText() {
1205: Text text = Text.valueOf('[');
1206: final Text equ = Text.valueOf('=');
1207: final Text sep = Text.valueOf(", ");
1208: for (Entry e = _head, end = _tail; (e = e._next) != end;) {
1209: text = text.concat(Text.valueOf(e._key)).concat(equ)
1210: .concat(Text.valueOf(e._value));
1211: if (e._next != end) {
1212: text = text.concat(sep);
1213: }
1214: }
1215: return text.concat(Text.valueOf(']'));
1216: }
1217:
1218: public Record head() {
1219: return _head;
1220: }
1221:
1222: public Record tail() {
1223: return _tail;
1224: }
1225:
1226: public Object valueOf(Record record) {
1227: return (Map.Entry) record;
1228: }
1229:
1230: public void delete(Record record) {
1231: FastMap.this .remove(((Entry) record).getKey());
1232: }
1233:
1234: public FastComparator getValueComparator() {
1235: return _entryComparator;
1236: }
1237:
1238: private final FastComparator _entryComparator = new FastComparator() {
1239:
1240: public boolean areEqual(Object o1, Object o2) {
1241: if ((o1 instanceof Map.Entry)
1242: && (o2 instanceof Map.Entry)) {
1243: Map.Entry e1 = (Map.Entry) o1;
1244: Map.Entry e2 = (Map.Entry) o2;
1245: return _keyComparator.areEqual(e1.getKey(), e2
1246: .getKey())
1247: && _valueComparator.areEqual(e1.getValue(),
1248: e2.getValue());
1249: }
1250: return (o1 == null) && (o2 == null);
1251: }
1252:
1253: public int compare(Object o1, Object o2) {
1254: return _keyComparator.compare(o1, o2);
1255: }
1256:
1257: public int hashCodeOf(Object obj) {
1258: Map.Entry entry = (Map.Entry) obj;
1259: return _keyComparator.hashCodeOf(entry.getKey())
1260: + _valueComparator.hashCodeOf(entry.getValue());
1261: }
1262: };
1263:
1264: public Iterator iterator() {
1265: return EntryIterator.valueOf(FastMap.this );
1266: }
1267: }
1268:
1269: // Entry iterator optimization.
1270: private static final class EntryIterator implements Iterator {
1271:
1272: private static final ObjectFactory FACTORY = new ObjectFactory() {
1273: protected Object create() {
1274: return new EntryIterator();
1275: }
1276:
1277: protected void cleanup(Object obj) {
1278: EntryIterator iterator = (EntryIterator) obj;
1279: iterator._map = null;
1280: iterator._current = null;
1281: iterator._next = null;
1282: iterator._tail = null;
1283: }
1284: };
1285:
1286: private FastMap _map;
1287:
1288: private Entry _current;
1289:
1290: private Entry _next;
1291:
1292: private Entry _tail;
1293:
1294: public static EntryIterator valueOf(FastMap map) {
1295: EntryIterator iterator = (EntryIterator) EntryIterator.FACTORY
1296: .object();
1297: iterator._map = map;
1298: iterator._next = map._head._next;
1299: iterator._tail = map._tail;
1300: return iterator;
1301: }
1302:
1303: private EntryIterator() {
1304: }
1305:
1306: public boolean hasNext() {
1307: return (_next != _tail);
1308: }
1309:
1310: public Object next() {
1311: if (_next == _tail)
1312: throw new NoSuchElementException();
1313: _current = _next;
1314: _next = _next._next;
1315: return _current;
1316: }
1317:
1318: public void remove() {
1319: if (_current != null) {
1320: _next = _current._next;
1321: _map.remove(_current._key);
1322: _current = null;
1323: } else {
1324: throw new IllegalStateException();
1325: }
1326: }
1327: }
1328:
1329: /**
1330: * Returns a {@link FastCollection} view of the keys contained in this
1331: * map. The set is backed by the map, so changes to the map are reflected
1332: * in the set, and vice-versa. The set supports element removal, which
1333: * removes the corresponding mapping from this map, via the
1334: * <code>Iterator.remove</code>,
1335: <code>Collection.remove</code>,<code>removeAll<f/code>,
1336: * <code>retainAll</code>, and <code>clear</code> operations. It does
1337: * not support the <code>add</code> or <code>addAll</code> operations.
1338: *
1339: * @return a set view of the keys contained in this map
1340: * (instance of {@link FastCollection}).
1341: */
1342: public final Set/*<K>*/keySet() {
1343: if (_keySet == null) {
1344: MemoryArea.getMemoryArea(this ).executeInArea(
1345: new Runnable() {
1346: public void run() {
1347: _keySet = new KeySet();
1348: }
1349: });
1350: }
1351: return _keySet;
1352: }
1353:
1354: private final class KeySet extends FastCollection implements Set {
1355:
1356: public int size() {
1357: return FastMap.this .size();
1358: }
1359:
1360: public void clear() {
1361: FastMap.this .clear();
1362: }
1363:
1364: public boolean contains(Object obj) { // Optimization.
1365: return FastMap.this .containsKey(obj);
1366: }
1367:
1368: public boolean remove(Object obj) { // Optimization.
1369: return FastMap.this .remove(obj) != null;
1370: }
1371:
1372: public Record head() {
1373: return FastMap.this ._head;
1374: }
1375:
1376: public Record tail() {
1377: return FastMap.this ._tail;
1378: }
1379:
1380: public Object valueOf(Record record) {
1381: return ((Entry) record)._key;
1382: }
1383:
1384: public void delete(Record record) {
1385: FastMap.this .remove(((Entry) record).getKey());
1386: }
1387:
1388: public FastComparator getValueComparator() {
1389: return _keyComparator;
1390: }
1391:
1392: public Iterator iterator() {
1393: return KeyIterator.valueOf(FastMap.this );
1394: }
1395: }
1396:
1397: // Entry iterator optimization.
1398: private static final class KeyIterator implements Iterator {
1399:
1400: private static final ObjectFactory FACTORY = new ObjectFactory() {
1401: protected Object create() {
1402: return new KeyIterator();
1403: }
1404:
1405: protected void cleanup(Object obj) {
1406: KeyIterator iterator = (KeyIterator) obj;
1407: iterator._map = null;
1408: iterator._current = null;
1409: iterator._next = null;
1410: iterator._tail = null;
1411: }
1412: };
1413:
1414: private FastMap _map;
1415:
1416: private Entry _current;
1417:
1418: private Entry _next;
1419:
1420: private Entry _tail;
1421:
1422: public static KeyIterator valueOf(FastMap map) {
1423: KeyIterator iterator = (KeyIterator) KeyIterator.FACTORY
1424: .object();
1425: iterator._map = map;
1426: iterator._next = map._head._next;
1427: iterator._tail = map._tail;
1428: return iterator;
1429: }
1430:
1431: private KeyIterator() {
1432: }
1433:
1434: public boolean hasNext() {
1435: return (_next != _tail);
1436: }
1437:
1438: public Object next() {
1439: if (_next == _tail)
1440: throw new NoSuchElementException();
1441: _current = _next;
1442: _next = _next._next;
1443: return _current._key;
1444: }
1445:
1446: public void remove() {
1447: if (_current != null) {
1448: _next = _current._next;
1449: _map.remove(_current._key);
1450: _current = null;
1451: } else {
1452: throw new IllegalStateException();
1453: }
1454: }
1455: }
1456:
1457: /**
1458: * Returns the unmodifiable view associated to this map.
1459: * Attempts to modify the returned map or to directly access its
1460: * (modifiable) map entries (e.g. <code>unmodifiable().entrySet()</code>)
1461: * result in an {@link UnsupportedOperationException} being thrown.
1462: * Unmodifiable {@link FastCollection} views of this map keys and values
1463: * are nonetheless obtainable (e.g. <code>unmodifiable().keySet(),
1464: * <code>unmodifiable().values()</code>).
1465: *
1466: * @return an unmodifiable view of this map.
1467: */
1468: public final Map/*<K,V>*/unmodifiable() {
1469: if (_unmodifiable == null) {
1470: MemoryArea.getMemoryArea(this ).executeInArea(
1471: new Runnable() {
1472: public void run() {
1473: _unmodifiable = new Unmodifiable();
1474: }
1475: });
1476: }
1477: return _unmodifiable;
1478: }
1479:
1480: // Implements Reusable.
1481: public void reset() {
1482: setShared(false); // A shared map can only be reset if no thread use it.
1483: clear(); // In which case, it is safe to recycle the entries.
1484: setKeyComparator(FastComparator.DEFAULT);
1485: setValueComparator(FastComparator.DEFAULT);
1486: }
1487:
1488: /**
1489: * Requires special handling during de-serialization process.
1490: *
1491: * @param stream the object input stream.
1492: * @throws IOException if an I/O error occurs.
1493: * @throws ClassNotFoundException if the class for the object de-serialized
1494: * is not found.
1495: */
1496: private void readObject(ObjectInputStream stream)
1497: throws IOException, ClassNotFoundException {
1498: setKeyComparator((FastComparator) stream.readObject());
1499: setValueComparator((FastComparator) stream.readObject());
1500: setShared(stream.readBoolean());
1501: final int size = stream.readInt();
1502: setup(size);
1503: for (int i = 0; i < size; i++) {
1504: Object/*{K}*/key = (Object/*{K}*/) stream.readObject();
1505: Object/*{V}*/value = (Object/*{V}*/) stream.readObject();
1506: put(key, value);
1507: }
1508: }
1509:
1510: /**
1511: * Requires special handling during serialization process.
1512: *
1513: * @param stream the object output stream.
1514: * @throws IOException if an I/O error occurs.
1515: */
1516: private void writeObject(ObjectOutputStream stream)
1517: throws IOException {
1518: stream.writeObject(getKeyComparator());
1519: stream.writeObject(getValueComparator());
1520: stream.writeBoolean(_isShared);
1521: stream.writeInt(size());
1522: for (Entry e = _head, end = _tail; (e = e._next) != end;) {
1523: stream.writeObject(e._key);
1524: stream.writeObject(e._value);
1525: }
1526: }
1527:
1528: /**
1529: * This class represents a {@link FastMap} entry.
1530: * Custom {@link FastMap} may use a derived implementation.
1531: * For example:[code]
1532: * static class MyMap<K,V,X> extends FastMap<K,V> {
1533: * protected MyEntry newEntry() {
1534: * return new MyEntry();
1535: * }
1536: * class MyEntry extends Entry<K,V> {
1537: * X xxx; // Additional entry field (e.g. cross references).
1538: * }
1539: * }[/code]
1540: */
1541: public static class Entry/*<K,V>*/implements Map.Entry/*<K,V>*/,
1542: Record {
1543:
1544: /**
1545: * Holds NULL entries (to fill empty hole).
1546: */
1547: public static final Entry NULL = new Entry();
1548:
1549: /**
1550: * Holds the next node.
1551: */
1552: private Entry/*<K,V>*/_next;
1553:
1554: /**
1555: * Holds the previous node.
1556: */
1557: private Entry/*<K,V>*/_previous;
1558:
1559: /**
1560: * Holds the entry key.
1561: */
1562: private Object/*{K}*/_key;
1563:
1564: /**
1565: * Holds the entry value.
1566: */
1567: private Object/*{V}*/_value;
1568:
1569: /**
1570: * Holds the key hash code.
1571: */
1572: private int _keyHash;
1573:
1574: /**
1575: * Default constructor.
1576: */
1577: protected Entry() {
1578: }
1579:
1580: /**
1581: * Returns the entry after this one.
1582: *
1583: * @return the next entry.
1584: */
1585: public final Record/*Entry<K,V>*/getNext() {
1586: return _next;
1587: }
1588:
1589: /**
1590: * Returns the entry before this one.
1591: *
1592: * @return the previous entry.
1593: */
1594: public final Record/*Entry<K,V>*/getPrevious() {
1595: return _previous;
1596: }
1597:
1598: /**
1599: * Returns the key for this entry.
1600: *
1601: * @return the entry key.
1602: */
1603: public final Object/*{K}*/getKey() {
1604: return _key;
1605: }
1606:
1607: /**
1608: * Returns the value for this entry.
1609: *
1610: * @return the entry value.
1611: */
1612: public final Object/*{V}*/getValue() {
1613: return _value;
1614: }
1615:
1616: /**
1617: * Sets the value for this entry.
1618: *
1619: * @param value the new value.
1620: * @return the previous value.
1621: */
1622: public final Object/*{V}*/setValue(Object/*{V}*/value) {
1623: Object/*{V}*/old = _value;
1624: _value = value;
1625: return old;
1626: }
1627:
1628: /**
1629: * Indicates if this entry is considered equals to the specified entry
1630: * (using default value and key equality comparator to ensure symetry).
1631: *
1632: * @param that the object to test for equality.
1633: * @return <code>true<code> if both entry have equal keys and values.
1634: * <code>false<code> otherwise.
1635: */
1636: public boolean equals(Object that) {
1637: if (that instanceof Map.Entry) {
1638: Map.Entry entry = (Map.Entry) that;
1639: return FastComparator.DEFAULT.areEqual(_key, entry
1640: .getKey())
1641: && FastComparator.DEFAULT.areEqual(_value,
1642: entry.getValue());
1643: } else {
1644: return false;
1645: }
1646: }
1647:
1648: /**
1649: * Returns the hash code for this entry.
1650: *
1651: * @return this entry hash code.
1652: */
1653: public int hashCode() {
1654: return ((_key != null) ? _key.hashCode() : 0)
1655: ^ ((_value != null) ? _value.hashCode() : 0);
1656: }
1657: }
1658:
1659: /**
1660: * This class represents an read-only view over a {@link FastMap}.
1661: */
1662: private final class Unmodifiable implements Map, Serializable {
1663:
1664: public boolean equals(Object obj) {
1665: return FastMap.this .equals(obj);
1666: }
1667:
1668: public int hashCode() {
1669: return FastMap.this .hashCode();
1670: }
1671:
1672: public Text toText() {
1673: return FastMap.this .toText();
1674: }
1675:
1676: public int size() {
1677: return FastMap.this .size();
1678: }
1679:
1680: public boolean isEmpty() {
1681: return FastMap.this .isEmpty();
1682: }
1683:
1684: public boolean containsKey(Object key) {
1685: return FastMap.this .containsKey(key);
1686: }
1687:
1688: public boolean containsValue(Object value) {
1689: return FastMap.this .containsValue(value);
1690: }
1691:
1692: public Object get(Object key) {
1693: return FastMap.this .get(key);
1694: }
1695:
1696: public Object put(Object key, Object value) {
1697: throw new UnsupportedOperationException("Unmodifiable map");
1698: }
1699:
1700: public Object remove(Object key) {
1701: throw new UnsupportedOperationException("Unmodifiable map");
1702: }
1703:
1704: public void putAll(Map map) {
1705: throw new UnsupportedOperationException("Unmodifiable map");
1706: }
1707:
1708: public void clear() {
1709: throw new UnsupportedOperationException("Unmodifiable map");
1710: }
1711:
1712: public Set keySet() {
1713: return (Set) ((KeySet) FastMap.this .keySet())
1714: .unmodifiable();
1715: }
1716:
1717: public Collection values() {
1718: return ((Values) FastMap.this .values()).unmodifiable();
1719: }
1720:
1721: public Set entrySet() {
1722: throw new UnsupportedOperationException(
1723: "Direct view over unmodifiable map entries is not supported "
1724: + " (to prevent access to Entry.setValue(Object) method). "
1725: + "To iterate over unmodifiable map entries, applications may "
1726: + "use the keySet() and values() fast collection views "
1727: + "in conjonction.");
1728: }
1729: }
1730:
1731: // Holds the map factory.
1732: private static final ObjectFactory FACTORY = new ObjectFactory() {
1733:
1734: public Object create() {
1735: return new FastMap();
1736: }
1737:
1738: public void cleanup(Object obj) {
1739: ((FastMap) obj).reset();
1740: }
1741: };
1742:
1743: // Reset the specified table.
1744: private static void reset(Object[] entries) {
1745: for (int i = 0; i < entries.length;) {
1746: int count = MathLib.min(entries.length - i, C1);
1747: System.arraycopy(NULL_ENTRIES, 0, entries, i, count);
1748: i += count;
1749: }
1750: }
1751:
1752: private static final Entry[] NULL_ENTRIES = new Entry[C1];
1753:
1754: static volatile int ONE_VOLATILE = 1; // To prevent reordering.
1755:
1756: private static final long serialVersionUID = 1L;
1757: }
|