Source Code Cross Referenced for FastMap.java in  » Science » javolution-5.2 » javolution » util » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Science » javolution 5.2 » javolution.util 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


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:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.