Java > Open Source Codes > javolution > util > FastMap


1 /*
2  * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
3  * Copyright (C) 2006 - Javolution (http://javolution.org/)
4  * All rights reserved.
5  *
6  * Permission to use, copy, modify, and distribute this software is
7  * freely granted, provided that this notice is preserved.
8  */
9 package javolution.util;
10
11 import j2me.io.ObjectInputStream;
12 import j2me.io.ObjectOutputStream;
13 import j2me.io.Serializable;
14 import j2me.lang.UnsupportedOperationException;
15 import j2me.util.Collection;
16 import j2me.util.Iterator;
17 import j2me.util.Map;
18 import j2me.util.Set;
19 import j2mex.realtime.MemoryArea;
20 import java.io.IOException ;
21 import java.io.PrintStream ;
22 import javolution.context.PersistentContext;
23 import javolution.context.Realtime;
24 import javolution.context.RealtimeObject;
25 import javolution.lang.Reusable;
26 import javolution.text.Text;
27 import javolution.text.TextBuilder;
28 import javolution.util.FastCollection.Record;
29 import javolution.xml.XMLBinding;
30 import javolution.xml.XMLFormat;
31 import javolution.xml.stream.XMLStreamException;
32
33 /**
34  * <p> This class represents a hash map with real-time behavior;
35  * smooth capacity increase and no rehashing ever performed.</p>
36  * <img SRC="doc-files/map-put.png"/>
37  *
38  * <p> {@link FastMap} has a predictable iteration order, which is the order in
39  * which keys are inserted into the map (similar to
40  * <code>java.util.LinkedHashMap</code> collection class).</p>
41  *
42  * <p> {@link FastMap.Entry} can quickly be iterated over (forward or backward)
43  * without using iterators. For example:[code]
44  * FastMap<String, Thread> map = new FastMap<String, Thread>();
45  * for (FastMap.Entry<String, Thread> e = map.head(), end = map.tail(); (e = e.getNext()) != end;) {
46  * String key = e.getKey(); // No typecast necessary.
47  * Thread value = e.getValue(); // No typecast necessary.
48  * }[/code]</p>
49  *
50  * <p> {@link FastMap} may use custom key comparators; the default comparator is
51  * either {@link FastComparator#DIRECT DIRECT} or
52  * {@link FastComparator#REHASH REHASH} based upon the current <a HREF=
53  * "{@docRoot}/overview-summary.html#configuration">Javolution
54  * Configuration</a>. Users may explicitly set the key comparator to
55  * {@link FastComparator#DIRECT DIRECT} for optimum performance
56  * when the hash codes are well distributed for all run-time platforms
57  * (e.g. calculated hash codes).</p>
58  *
59  * <p> Custom key comparators are extremely useful for value retrieval when
60  * map's keys and argument keys are not of the same class, such as
61  * {@link String} and {@link javolution.text.Text Text}
62  * ({@link FastComparator#LEXICAL LEXICAL}) or for identity maps
63  * ({@link FastComparator#IDENTITY IDENTITY}).
64  * For example:[code]
65  * FastMap identityMap = new FastMap().setKeyComparator(FastComparator.IDENTITY);
66  * [/code]</p>
67  *
68  * <p> {@link FastMap} marked {@link #setShared(boolean) shared} are
69  * thread-safe without external synchronization and are often good
70  * substitutes for <code>ConcurrentHashMap</code>. For example:[code]
71  * // Holds the units multiplication lookup table (persistent).
72  * static final FastMap<Unit, FastMap<Unit, Unit>> MULT_LOOKUP
73  * = new FastMap<Unit, FastMap<Unit, Unit>>("mult-unit-lookup").setShared(true);
74  *
75  * // Fast and non-blocking (no synchronization necessary).
76  * static Unit productOf(Unit left, Unit right) {
77  * FastMap<Unit, Unit> leftTable = MULT_LOOKUP.get(left);
78  * if (leftTable == null) return calculateProductOf(left, right);
79  * Unit result = leftTable.get(right);
80  * if (result == null) return calculateProductOf(left, right);
81  * return result; // Returns cache result.
82  * }[/code]</p>
83  *
84  * <p> Finally, {@link FastMap} are {@link Reusable reusable}; they maintain an
85  * internal pool of <code>Map.Entry</code> objects. When an entry is removed
86  * from a map, it is automatically restored to its pool (unless the map
87  * is shared in which case the removed entry is candidate for garbage
88  * collection as it cannot be safely recycled).</p>
89  *
90  * @author <a HREF="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle </a>
91  * @version 4.2, December 18, 2006
92  */
93 public class FastMap/*<K,V>*/extends RealtimeObject implements Map/*<K,V>*/,
94         Reusable, Serializable {
95
96     /**
97      * Holds the default XML representation for FastMap instances.
98      * This representation is identical to {@link XMLBinding#MAP_XML}
99      * except that it may include the key/value comparators for the map
100      * (if different from {@link FastComparator#DEFAULT}) and the
101      * {@link #isShared() "shared"} attribute.
102      */
103     protected static final XMLFormat/*<FastMap>*/XML = new XMLFormat(
104             new FastMap().getClass()) {
105
106         public void read(InputElement xml, Object obj)
107                 throws XMLStreamException {
108             final FastMap fm = (FastMap) obj;
109             fm.setShared(xml.getAttribute("shared", false));
110             FastComparator keyComparator = (FastComparator) xml
111                     .get("KeyComparator");
112             if (keyComparator != null) {
113                 fm.setKeyComparator(keyComparator);
114             }
115             FastComparator valueComparator = (FastComparator) xml
116                     .get("ValueComparator");
117             if (valueComparator != null) {
118                 fm.setValueComparator(valueComparator);
119             }
120             while (xml.hasNext()) {
121                 Object key = xml.get("Key");
122                 Object value = xml.get("Value");
123                 fm.put(key, value);
124             }
125         }
126
127         public void write(Object obj, OutputElement xml)
128                 throws XMLStreamException {
129             final FastMap fm = (FastMap) obj;
130             if (fm.isShared()) {
131                 xml.setAttribute("shared", true);
132             }
133             if (fm.getKeyComparator() != FastComparator.DEFAULT) {
134                 xml.add(fm.getKeyComparator(), "KeyComparator");
135             }
136             if (fm.getValueComparator() != FastComparator.DEFAULT) {
137                 xml.add(fm.getValueComparator(), "ValueComparator");
138             }
139             for (Entry e = fm.head(), end = fm.tail(); (e = (Entry) e.getNext()) != end;) {
140                 xml.add(e.getKey(), "Key");
141                 xml.add(e.getValue(), "Value");
142             }
143         }
144     };
145
146     /**
147      * Holds table higher index rotation.
148      */
149     private static final int R0 = 5;
150
151     /**
152      * Holds the table lower index mask.
153      */
154     private static final int M0 = (1 << R0) - 1;
155
156     /**
157      * Holds the map factory.
158      */
159     private static final Factory FACTORY = new Factory() {
160
161         public Object create() {
162             return new FastMap();
163         }
164
165         public void cleanup(Object obj) {
166             ((FastMap) obj).reset();
167         }
168     };
169
170     /**
171      * Holds the map's hash table.
172      * Use two dimensional arrays to avoid large arrays allocations.
173      */
174     private transient Entry/*<K,V>*/[][] _entries;
175
176     /**
177      * Holds the head entry to which the first entry attaches.
178      * The head entry never changes (entries always added last).
179      */
180     private transient Entry/*<K,V>*/_head;
181
182     /**
183      * Holds the tail entry to which the last entry attaches.
184      * The tail entry changes as entries are added/removed.
185      */
186     private transient Entry/*<K,V>*/_tail;
187
188     /**
189      * Holds the current size.
190      */
191     private transient int _size;
192
193     /**
194      * Holds the values view.
195      */
196     private transient Values _values;
197
198     /**
199      * Holds the key set view.
200      */
201     private transient KeySet _keySet;
202
203     /**
204      * Holds the entry set view.
205      */
206     private transient EntrySet _entrySet;
207
208     /**
209      * Holds the unmodifiable view.
210      */
211     private transient Map/*<K,V>*/_unmodifiable;
212
213     /**
214      * Holds a reference to a map having the old entries when resizing.
215      */
216     private transient FastMap/*<K,V>*/_oldEntries;
217
218     /**
219      * Holds the key comparator.
220      */
221     private transient FastComparator _keyComparator = FastComparator.DEFAULT;
222
223     /**
224      * Holds the value comparator.
225      */
226     private transient FastComparator _valueComparator = FastComparator.DEFAULT;
227
228     /**
229      * Holds comparator set to <code>null</code> when equivalent to direct.
230      */
231     private transient FastComparator _keyComp
232          = FastComparator._Rehash ? FastComparator.REHASH : null;
233
234     /**
235      * Indicates if this map is shared (thread-safe).
236      */
237     private transient boolean _isShared;
238
239     /**
240      * Creates a fast map of small initial capacity.
241      */
242     public FastMap() {
243         this(4);
244     }
245
246     /**
247      * Creates a persistent map associated to the specified unique identifier
248      * (convenience method).
249      *
250      * @param id the unique identifier for this map.
251      * @throws IllegalArgumentException if the identifier is not unique.
252      * @see javolution.context.PersistentContext.Reference
253      */
254     public FastMap(String id) {
255         this();
256         new PersistentContext.Reference(id, this) {
257             protected void notifyChange() {
258                 FastMap.this.clear();
259                 FastMap.this.putAll((FastMap) this.get());
260             }
261         };
262     }
263
264     /**
265      * Creates a map of specified initial capacity; unless the map size
266      * reaches the specified capacity, operations on this map will not allocate
267      * memory (no lazy object creation).
268      *
269      * @param capacity the initial capacity.
270      */
271     public FastMap(int capacity) {
272         setup(capacity);
273     }
274     private void setup(int capacity) {
275         int tableLength = 1 << R0;
276         while (tableLength < capacity) {
277             tableLength <<= 1;
278         }
279         _entries = (Entry/*<K,V>*/[][]) new Entry[tableLength >> R0][];
280         for (int i = 0; i < _entries.length;) {
281             _entries[i++] = (Entry/*<K,V>*/[]) new Entry[1 << R0];
282         }
283         _head = new Entry();
284         _tail = new Entry();
285         _head._next = _tail;
286         _tail._previous = _head;
287         Entry/*<K,V>*/previous = _tail;
288         for (int i = 0; i++ < capacity;) {
289             Entry/*<K,V>*/newEntry = new Entry/*<K,V>*/();
290             newEntry._previous = previous;
291             previous._next = newEntry;
292             previous = newEntry;
293         }
294     }
295
296     /**
297      * Creates a map containing the specified entries, in the order they
298      * are returned by the map iterator.
299      *
300      * @param map the map whose entries are to be placed into this map.
301      */
302     public FastMap(Map/*<? extends K, ? extends V>*/map) {
303         this(map.size());
304         putAll(map);
305     }
306
307     /**
308      * Creates a fast map having the specified entry table.
309      *
310      * @param entries the entry table.
311      */
312     private FastMap(Entry/*<K,V>*/[][] entries) {
313         _head = new Entry();
314         _tail = new Entry();
315         _head._next = _tail;
316         _tail._previous = _head;
317         _entries = entries;
318     }
319
320     /**
321      * Returns a new, preallocated or {@link #recycle recycled} map instance
322      * (on the stack when executing in a {@link javolution.context.PoolContext
323      * PoolContext}).
324      *
325      * @return a new, preallocated or recycled map instance.
326      */
327     public static/*<K,V>*/FastMap/*<K,V>*/newInstance() {
328         return (FastMap/*<K,V>*/) FACTORY.object();
329     }
330
331     /**
332      * Recycles a map {@link #newInstance() instance} immediately
333      * (on the stack when executing in a {@link javolution.context.PoolContext
334      * PoolContext}).
335      */
336     public static void recycle(FastMap instance) {
337         FACTORY.recycle(instance);
338     }
339
340     /**
341      * Returns the head entry of this map.
342      *
343      * @return the entry such as <code>head().getNext()</code> holds
344      * the first map entry.
345      */
346     public final Entry/*<K,V>*/head() {
347         return _head;
348     }
349
350     /**
351      * Returns the tail entry of this map.
352      *
353      * @return the entry such as <code>tail().getPrevious()</code>
354      * holds the last map entry.
355      */
356     public final Entry/*<K,V>*/tail() {
357         return _tail;
358     }
359
360     /**
361      * Returns the number of key-value mappings in this {@link FastMap}.
362      *
363      * @return this map's size.
364      */
365     public final int size() {
366         return _size;
367     }
368
369     /**
370      * Indicates if this map contains no key-value mappings.
371      *
372      * @return <code>true</code> if this map contains no key-value mappings;
373      * <code>false</code> otherwise.
374      */
375     public final boolean isEmpty() {
376         return _head._next == _tail;
377     }
378
379     /**
380      * Indicates if this map contains a mapping for the specified key.
381      *
382      * @param key the key whose presence in this map is to be tested.
383      * @return <code>true</code> if this map contains a mapping for the
384      * specified key; <code>false</code> otherwise.
385      * @throws NullPointerException if the key is <code>null</code>.
386      */
387     public final boolean containsKey(Object key) {
388         return getEntry(key) != null;
389     }
390
391     /**
392      * Indicates if this map associates one or more keys to the specified value.
393      *
394      * @param value the value whose presence in this map is to be tested.
395      * @return <code>true</code> if this map maps one or more keys to the
396      * specified value.
397      * @throws NullPointerException if the key is <code>null</code>.
398      */
399     public final boolean containsValue(Object value) {
400         return values().contains(value);
401     }
402
403     /**
404      * Returns the value to which this map associates the specified key.
405      *
406      * @param key the key whose associated value is to be returned.
407      * @return the value to which this map maps the specified key, or
408      * <code>null</code> if there is no mapping for the key.
409      * @throws NullPointerException if key is <code>null</code>.
410      */
411     public final Object /*{V}*/get(Object key) {
412         Entry/*<K,V>*/entry = getEntry(key, (_keyComp == null) ? key
413                 .hashCode() : _keyComp.hashCodeOf(key));
414         return (entry != null) ? entry._value : null;
415     }
416
417     /**
418      * Returns the entry with the specified key.
419      *
420      * @param key the key whose associated entry is to be returned.
421      * @return the entry for the specified key or <code>null</code> if none.
422      */
423     public final Entry/*<K,V>*/getEntry(Object key) {
424         return getEntry(key, (_keyComp == null) ? key.hashCode() : _keyComp
425                 .hashCodeOf(key));
426     }
427
428     /**
429      * Associates the specified value with the specified key in this map.
430      * If this map previously contained a mapping for this key, the old value
431      * is replaced. For {@link #isShared() shared} map, internal synchronization
432      * is performed only when new entries are created.
433      *
434      * @param key the key with which the specified value is to be associated.
435      * @param value the value to be associated with the specified key.
436      * @return the previous value associated with specified key, or
437      * <code>null</code> if there was no mapping for key. A
438      * <code>null</code> return can also indicate that the map
439      * previously associated <code>null</code> with the specified key.
440      * @throws NullPointerException if the key is <code>null</code>.
441      */
442     public final Object /*{V}*/put(Object /*{K}*/key, Object /*{V}*/value) {
443         final int keyHash = (_keyComp == null) ? key.hashCode() : _keyComp
444                 .hashCodeOf(key);
445         Entry/*<K,V>*/entry = getEntry(key, keyHash);
446         if (entry != null) {
447             Object /*{V}*/prevValue = entry._value;
448             entry._value = value;
449             return prevValue;
450         }
451         if (_isShared) // Synchronization only if shared and new entry.
452 return putShared(key, value, keyHash);
453         addEntry(keyHash, key, value);
454         return null;
455     }
456
457     private synchronized Object /*{V}*/putShared(Object /*{K}*/key,
458             Object /*{V}*/value, int keyHash) {
459         Entry/*<K,V>*/entry = getEntry(key, keyHash); // To avoid duplicates.
460 if (entry == null) { // Most likely.
461 addEntry(keyHash, key, value);
462             return null;
463         }
464         Object /*{V}*/prevValue = entry._value;
465         entry._value = value;
466         return prevValue;
467     }
468
469     /**
470      * Copies all of the mappings from the specified map to this map.
471      *
472      * @param map the mappings to be stored in this map.
473      * @throws NullPointerException the specified map is <code>null</code>,
474      * or the specified map contains <code>null</code> keys.
475      */
476     public final void putAll(Map/*<? extends K, ? extends V>*/map) {
477         if (map instanceof FastMap) { // Optimization.
478 FastMap/*<? extends K, ? extends V>*/fm = (FastMap/*<? extends K, ? extends V>*/) map;
479             for (Entry/*<? extends K, ? extends V>*/e = fm._head, end = fm._tail; (e = e._next) != end;) {
480                 put(e._key, e._value);
481             }
482         } else {
483             for (Iterator i = map.entrySet().iterator(); i.hasNext();) {
484                 Map.Entry/*<? extends K, ? extends V>*/e = (Map.Entry/*<? extends K, ? extends V>*/) i
485                         .next();
486                 put(e.getKey(), e.getValue());
487             }
488         }
489     }
490
491     /**
492      * Removes the entry for the specified key if present. The entry
493      * is recycled if the map is not marked as {@link #isShared shared};
494      * otherwise the entry is candidate for garbage collection.
495      *
496      * <p> Note: Shared maps in ImmortalMemory (e.g. static) should not remove
497      * their entries as it could cause a memory leak (ImmortalMemory
498      * is never garbage collected), instead they should set their
499      * entry values to <code>null</code>.</p>
500      *
501      * @param key the key whose mapping is to be removed from the map.
502      * @return previous value associated with specified key, or
503      * <code>null</code> if there was no mapping for key. A
504      * <code>null</code> return can also indicate that the map
505      * previously associated <code>null</code> with the specified key.
506      * @throws NullPointerException if the key is <code>null</code>.
507      */
508     public final Object /*{V}*/remove(Object key) {
509         Entry/*<K,V>*/entry = getEntry(key);
510         if (entry == null)
511             return null;
512         if (_isShared) // Synchronization only if shared and entry exists.
513 return removeShared(entry);
514         Object /*{V}*/prevValue = entry._value;
515         removeEntry(entry);
516         return prevValue;
517     }
518
519     private synchronized Object /*{V}*/removeShared(Entry/*<K,V>*/entry) {
520         _size--;
521         entry.detach();
522         return entry._value;
523     }
524
525     /**
526      * <p> Sets the shared status of this map (whether the map is thread-safe
527      * or not). Shared maps are typically used for lookup table (e.g. static
528      * instances in ImmortalMemory). They support concurrent access
529      * (e.g. iterations) without synchronization, the maps updates
530      * themselves are synchronized internally.</p>
531      * <p> Unlike <code>ConcurrentHashMap</code> access to a shared map never
532      * blocks. Retrieval reflects the map state not older than the last
533      * time the accessing thread has been synchronized (for multi-processors
534      * systems synchronizing ensures that the CPU internal cache is not
535      * stale).</p>
536      *
537      * @param isShared <code>true</code> if this map is shared and thread-safe;
538      * <code>false</code> otherwise.
539      * @return <code>this</code>
540      */
541     public FastMap/*<K,V>*/setShared(boolean isShared) {
542         _isShared = isShared;
543         return this;
544     }
545
546     /**
547      * Indicates if this map supports concurrent operations without
548      * synchronization (default unshared).
549      *
550      * @return <code>true</code> if this map is thread-safe; <code>false</code>
551      * otherwise.
552      */
553     public boolean isShared() {
554         return _isShared;
555     }
556
557     /**
558      * Sets the key comparator for this fast map.
559      *
560      * @param keyComparator the key comparator.
561      * @return <code>this</code>
562      */
563     public FastMap/*<K,V>*/setKeyComparator(FastComparator/*<? super K>*/ keyComparator) {
564         _keyComparator = keyComparator;
565         _keyComp = (keyComparator instanceof FastComparator.Default) ?
566                 (FastComparator._Rehash ? FastComparator.REHASH : null)
567                 : (keyComparator instanceof FastComparator.Direct) ? null
568                         : keyComparator;
569         return this;
570     }
571
572     /**
573      * Returns the key comparator for this fast map.
574      *
575      * @return the key comparator.
576      */
577     public FastComparator/*<? super K>*/ getKeyComparator() {
578         return _keyComparator;
579     }
580
581     /**
582      * Sets the value comparator for this map.
583      *
584      * @param valueComparator the value comparator.
585      * @return <code>this</code>
586      */
587     public FastMap/*<K,V>*/setValueComparator(FastComparator/*<? super V>*/ valueComparator) {
588         _valueComparator = valueComparator;
589         return this;
590     }
591
592     /**
593      * Returns the value comparator for this fast map.
594      *
595      * @return the value comparator.
596      */
597     public FastComparator/*<? super V>*/ getValueComparator() {
598         return _valueComparator;
599     }
600
601     /**
602      * Removes all map's entries. The entries are removed and recycled;
603      * unless this map is {@link #isShared shared} in which case the entries
604      * are candidate for garbage collection.
605      *
606      * <p> Note: Shared maps in ImmortalMemory (e.g. static) should not remove
607      * their entries as it could cause a memory leak (ImmortalMemory
608      * is never garbage collected), instead they should set their
609      * entry values to <code>null</code>.</p>
610      */
611     public final void clear() {
612         if (_isShared) {
613             clearShared();
614             return;
615         }
616         // Clears all keys, values and buckets linked lists.
617 for (Entry/*<K,V>*/e = _head, end = _tail; (e = e._next) != end;) {
618             e._key = null;
619             e._value = null;
620             final Entry/*<K,V>*/[][] table = e._table;
621             table[(e._keyHash >> R0) & (table.length - 1)][e._keyHash & M0] = null;
622         }
623         _tail = _head._next;
624         _size = 0;
625
626         // Discards old entries.
627 _oldEntries = null;
628     }
629
630     private synchronized void clearShared() {
631         for (Entry/*<K,V>*/e = _head, end = _tail; (e = e._next) != end;) {
632             final Entry/*<K,V>*/[][] table = e._table;
633             table[(e._keyHash >> R0) & (table.length - 1)][e._keyHash & M0] = null;
634         }
635         _head._next = _tail; // Does not modify current linked list.
636 _tail._previous = _head; //
637 _oldEntries = null;
638         _size = 0;
639     }
640
641     /**
642      * Compares the specified object with this map for equality.
643      * Returns <code>true</code> if the given object is also a map and the two
644      * maps represent the same mappings (regardless of collection iteration
645      * order).
646      *
647      * @param obj the object to be compared for equality with this map.
648      * @return <code>true</code> if the specified object is equal to this map;
649      * <code>false</code> otherwise.
650      */
651     public boolean equals(Object obj) {
652         if (obj == this) {
653             return true;
654         } else if (obj instanceof Map) {
655             Map/*<?,?>*/that = (Map) obj;
656             return this.entrySet().equals(that.entrySet());
657         } else {
658             return false;
659         }
660     }
661
662     /**
663      * Returns the hash code value for this map.
664      *
665      * @return the hash code value for this map.
666      */
667     public int hashCode() {
668         int code = 0;
669         for (Entry e = _head, end = _tail; (e = e._next) != end;) {
670             code += e.hashCode();
671         }
672         return code;
673     }
674
675     /**
676      * Returns the textual representation of this map.
677      *
678      * @return the textual representation of the entry set.
679      */
680     public Text toText() {
681         return Text.valueOf(entrySet());
682     }
683
684     /**
685      * Prints the current statistics on this map.
686      * This method may help identify poorly defined hash functions.
687      * An average collision of less than <code>50%</code> is typically
688      * acceptable.
689      *
690      * @param out the stream to use for output (e.g. <code>System.out</code>)
691      */
692     public void printStatistics(PrintStream out) {
693         int maxOccupancy = 0;
694         int totalCollisions = 0;
695         int size = 0;
696         for (int i = 0; i < _entries.length; i++) {
697             for (int j = 0; j < _entries[i].length; j++) {
698                 Entry entry = _entries[i][j];
699                 int occupancy = 0;
700                 while (entry != null) {
701                     occupancy++;
702                     if (occupancy > maxOccupancy) {
703                         maxOccupancy = occupancy;
704                     }
705                     if (occupancy > 1) {
706                         totalCollisions++;
707                     }
708                     entry = entry._beside;
709                     size++;
710                 }
711             }
712         }
713         TextBuilder percentCollisions = TextBuilder.newInstance();
714         if (size != 0) {
715             percentCollisions.append((100 * totalCollisions) / size);
716             percentCollisions.append('%');
717         } else {
718             percentCollisions.append("N/A");
719         }
720         synchronized (out) {
721             out.print("SIZE: " + size);
722             out
723                     .print(", TABLE LENGTH: " + _entries.length
724                             * _entries[0].length);
725             out.print(", AVG COLLISIONS: " + percentCollisions);
726             out.print(", MAX SLOT OCCUPANCY: " + maxOccupancy);
727             out.print(", KEY COMPARATOR: "
728                     + ((_keyComp == null) ? FastComparator.DIRECT : _keyComp));
729             out.print(", SHARED: " + _isShared);
730             out.println();
731             if (_oldEntries != null) {
732                 out.print(" + ");
733                 _oldEntries.printStatistics(out);
734             }
735         }
736     }
737
738     /**
739      * Returns a {@link FastCollection} view of the values contained in this
740      * map. The collection is backed by the map, so changes to the
741      * map are reflected in the collection, and vice-versa. The collection
742      * supports element removal, which removes the corresponding mapping from
743      * this map, via the <code>Iterator.remove</code>,
744      * <code>Collection.remove</code>, <code>removeAll</code>,
745      * <code>retainAll</code> and <code>clear</code> operations.
746      * It does not support the <code>add</code> or <code>addAll</code>
747      * operations.
748      *
749      * @return a collection view of the values contained in this map
750      * (instance of {@link FastCollection}).
751      */
752     public final Collection/*<V>*/values() {
753         if (_values == null) {
754             MemoryArea.getMemoryArea(this).executeInArea(new Runnable () {
755                 public void run() {
756                     _values = new Values();
757                 }
758             });
759         }
760         return _values;
761     }
762
763     private final class Values extends FastCollection {
764
765         public int size() {
766             return _size;
767         }
768
769         public void clear() {
770             FastMap.this.clear();
771         }
772
773         public Record head() {
774             return FastMap.this._head;
775         }
776
777         public Record tail() {
778             return FastMap.this._tail;
779         }
780
781         public Object valueOf(Record record) {
782             return ((Entry) record)._value;
783         }
784
785         public void delete(Record record) {
786             FastMap.this.remove(((Entry) record).getKey());
787         }
788         
789         public FastComparator getValueComparator() {
790             return _valueComparator;
791         }
792     }
793
794     /**
795      * Returns a {@link FastCollection} view of the mappings contained in this
796      * map. Each element in the returned collection is a
797      * <code>FastMap.Entry</code>. The collection is backed by the map, so
798      * changes to the map are reflected in the collection, and vice-versa. The
799      * collection supports element removal, which removes the corresponding
800      * mapping from this map, via the <code>Iterator.remove</code>,
801      * <code>Collection.remove</code>,<code>removeAll</code>,
802      * <code>retainAll</code>, and <code>clear</code> operations. It does
803      * not support the <code>add</code> or <code>addAll</code> operations.
804      *
805      * @return a collection view of the mappings contained in this map
806      * (instance of {@link FastCollection}).
807      */
808     public final Set/*<Map.Entry<K,V>>*/entrySet() {
809         if (_entrySet == null) {
810             MemoryArea.getMemoryArea(this).executeInArea(new Runnable () {
811                 public void run() {
812                     _entrySet = new EntrySet();
813                 }
814             });
815         }
816         return _entrySet;
817     }
818
819     private final class EntrySet extends FastCollection implements Set {
820
821         public int size() {
822             return _size;
823         }
824
825         public void clear() {
826             FastMap.this.clear();
827         }
828
829         public boolean contains(Object obj) { // Optimization.
830 if (obj instanceof Map.Entry) {
831                 Map.Entry thatEntry = (Entry) obj;
832                 Entry thisEntry = getEntry(thatEntry.getKey());
833                 if (thisEntry == null) return false;
834                 return _valueComparator.areEqual(thisEntry.getValue(), thatEntry.getValue());
835             } else {
836                 return false;
837             }
838         }
839
840         public Text toText() {
841             Text text = Text.valueOf('[');
842             final Text equ = Text.valueOf('=');
843             final Text sep = Text.valueOf(", ");
844             for (Entry e = _head, end = _tail; (e = e._next) != end;) {
845                 text = text.concat(Text.valueOf(e._key)).concat(equ).concat(
846                         Text.valueOf(e._value));
847                 if (e._next != end) {
848                     text = text.concat(sep);
849                 }
850             }
851             return text.concat(Text.valueOf(']'));
852         }
853
854         public Record head() {
855             return _head;
856         }
857
858         public Record tail() {
859             return _tail;
860         }
861
862         public Object valueOf(Record record) {
863             return (Map.Entry) record;
864         }
865
866         public void delete(Record record) {
867             FastMap.this.remove(((Entry) record).getKey());
868         }
869         
870         public FastComparator getValueComparator() {
871             return _entryComparator;
872         }
873         private final FastComparator _entryComparator = new FastComparator() {
874
875             public boolean areEqual(Object o1, Object o2) {
876                 if ((o1 instanceof Map.Entry) && (o2 instanceof Map.Entry)) {
877                     Map.Entry e1 = (Map.Entry) o1;
878                     Map.Entry e2 = (Map.Entry) o2;
879                     return _keyComparator.areEqual(e1.getKey(), e2.getKey()) &&
880                        _valueComparator.areEqual(e1.getValue(), e2.getValue());
881                 }
882                 return (o1 == null) && (o2 == null);
883             }
884
885             public int compare(Object o1, Object o2) {
886                 return _keyComparator.compare(o1, o2);
887             }
888
889             public int hashCodeOf(Object obj) {
890                 Map.Entry entry = (Map.Entry) obj;
891                 return _keyComparator.hashCodeOf(entry.getKey()) +
892                    _valueComparator.hashCodeOf(entry.getValue());
893             }
894         };
895     }
896
897     /**
898      * Returns a {@link FastCollection} view of the keys contained in this
899      * map. The set is backed by the map, so changes to the map are reflected
900      * in the set, and vice-versa. The set supports element removal, which
901      * removes the corresponding mapping from this map, via the
902      * <code>Iterator.remove</code>, <code>Collection.remove</code>,<code>removeAll<f/code>,
903      * <code>retainAll</code>, and <code>clear</code> operations. It does
904      * not support the <code>add</code> or <code>addAll</code> operations.
905      *
906      * @return a set view of the keys contained in this map
907      * (instance of {@link FastCollection}).
908      */
909     public final Set/*<K>*/keySet() {
910         if (_keySet == null) {
911             MemoryArea.getMemoryArea(this).executeInArea(new Runnable () {
912                 public void run() {
913                     _keySet = new KeySet();
914                 }
915             });
916         }
917         return _keySet;
918     }
919
920     private final class KeySet extends FastCollection implements Set {
921
922         public int size() {
923             return _size;
924         }
925
926         public void clear() {
927             FastMap.this.clear();
928         }
929
930         public boolean contains(Object obj) { // Optimization.
931 return FastMap.this.containsKey(obj);
932         }
933
934         public boolean remove(Object obj) { // Optimization.
935 return FastMap.this.remove(obj) != null;
936         }
937
938         public Record head() {
939             return FastMap.this._head;
940         }
941
942         public Record tail() {
943             return FastMap.this._tail;
944         }
945
946         public Object valueOf(Record record) {
947             return ((Entry) record)._key;
948         }
949
950         public void delete(Record record) {
951             FastMap.this.remove(((Entry) record).getKey());
952         }
953         
954         public FastComparator getValueComparator() {
955             return _keyComparator;
956         }
957     }
958
959     /**
960      * Returns the unmodifiable view associated to this map.
961      * Attempts to modify the returned map or to directly access its
962      * (modifiable) map entries (e.g. <code>unmodifiable().entrySet()</code>)
963      * result in an {@link UnsupportedOperationException} being thrown.
964      * Unmodifiable {@link FastCollection} views of this map keys and values
965      * are nonetheless obtainable (e.g. <code>unmodifiable().keySet(),
966      * <code>unmodifiable().values()</code>).
967      *
968      * @return an unmodifiable view of this map.
969      */
970     public final Map/*<K,V>*/unmodifiable() {
971         if (_unmodifiable == null) {
972             MemoryArea.getMemoryArea(this).executeInArea(new Runnable () {
973                 public void run() {
974                     _unmodifiable = new Unmodifiable();
975                 }
976             });
977         }
978         return _unmodifiable;
979     }
980
981     /**
982      * Returns the entry with the specified key and hash code.
983      *
984      * @param key the key whose associated entry is to be returned.
985      * @param the associated hash code (need to be calculated only once).
986      * @return the entry for the specified key or <code>null</code> if none.
987      */
988     private final Entry/*<K,V>*/getEntry(Object key, int keyHash) {
989         final Entry/*<K,V>*/[][] entries = _entries;
990         Entry/*<K,V>*/entry = entries[(keyHash >> R0) & (entries.length - 1)][keyHash
991                 & M0];
992         while (entry != null) {
993             if ((key == entry._key)
994                     || ((entry._keyHash == keyHash) && ((_keyComp == null) ? key
995                             .equals(entry._key)
996                             : _keyComp.areEqual(key, entry._key))))
997                 return entry; // Found.
998 entry = entry._beside;
999         }
1000        return (_oldEntries != null) ? _oldEntries.getEntry(key, keyHash)
1001                : null;
1002    }
1003
1004    /**
1005     * Adds a new entry for the specified key and value.
1006     *
1007     * @param hash the hash of the key, generated with {@link #keyHash}.
1008     * @param key the entry's key.
1009     * @param value the entry's value.
1010     */
1011    private void addEntry(int hash, Object /*{K}*/key, Object /*{V}*/value) {
1012        // Updates size.
1013 if ((_size++ >> R0) >= (_entries.length)) { // Check if entry table too small.
1014 increaseEntryTable();
1015        }
1016
1017        if (_tail._next == null) {
1018            increaseCapacity();
1019        }
1020        final Entry newTail = _tail._next;
1021        // Setups entry parameters.
1022 _tail._key = key;
1023        _tail._value = value;
1024        _tail._keyHash = hash;
1025        _tail._table = _entries;
1026
1027        // Connects to bucket.
1028 final int index = (hash >> R0) & (_entries.length - 1);
1029        Entry[] tmp = _entries[index];
1030        if (tmp == NULL_BLOCK) {
1031            newBlock(index);
1032            tmp = _entries[index];
1033        }
1034        Entry beside = tmp[hash & M0];
1035        _tail._beside = beside;
1036        tmp[hash & M0] = _tail;
1037
1038        // Moves tail forward.
1039 _tail = newTail;
1040    }
1041
1042    /**
1043     * Removes the specified entry from the specified map.
1044     * The entry is added to the internal pool.
1045     *
1046     * @param entry the entry to be removed.
1047     * @param the map from which the entry is removed.
1048     */
1049    private final void removeEntry(Entry entry) {
1050
1051        // Updates size.
1052 _size--;
1053
1054        // Clears value and key.
1055 entry._key = null;
1056        entry._value = null;
1057
1058        // Detaches from list and bucket.
1059 entry.detach();
1060
1061        // Re-inserts next tail.
1062 final Entry next = _tail._next;
1063        entry._previous = _tail;
1064        entry._next = next;
1065        _tail._next = entry;
1066        if (next != null) {
1067            next._previous = entry;
1068        }
1069    }
1070
1071    // Allocates a new block.
1072 private void newBlock(final int index) {
1073        MemoryArea.getMemoryArea(this).executeInArea(new Runnable () {
1074            public void run() {
1075                _entries[index] = new Entry[1 << R0];
1076            }
1077        });
1078    }
1079
1080    // Increases capacity (_tail._next == null)
1081 private void increaseCapacity() {
1082        MemoryArea.getMemoryArea(this).executeInArea(new Runnable () {
1083            public void run() {
1084                Entry/*<K,V>*/newEntry0 = new Entry/*<K,V>*/();
1085                _tail._next = newEntry0;
1086                newEntry0._previous = _tail;
1087
1088                Entry/*<K,V>*/newEntry1 = new Entry/*<K,V>*/();
1089                newEntry0._next = newEntry1;
1090                newEntry1._previous = newEntry0;
1091
1092                Entry/*<K,V>*/newEntry2 = new Entry/*<K,V>*/();
1093                newEntry1._next = newEntry2;
1094                newEntry2._previous = newEntry1;
1095
1096                Entry/*<K,V>*/newEntry3 = new Entry/*<K,V>*/();
1097                newEntry2._next = newEntry3;
1098                newEntry3._previous = newEntry2;
1099            }
1100        });
1101    }
1102
1103    // Increases the table size, the table length is multiplied by 8.
1104 // It still ensures that no more than half of the memory space is unused
1105 // (most space is being taken by the entries objects themselves).
1106 private void increaseEntryTable() {
1107        MemoryArea.getMemoryArea(this).executeInArea(new Runnable () {
1108            public void run() {
1109                final int newLength = _entries.length << 3;
1110                FastMap/*<K,V>*/tmp;
1111                if (newLength <= (1 << 3)) { //
1112 tmp = new FastMap/*<K,V>*/(new Entry[1 << 3][]); // 256
1113 } else if (newLength <= (1 << 6)) {
1114                    tmp = new FastMap/*<K,V>*/(new Entry[1 << 6][]); // 2048
1115 } else if (newLength <= (1 << 9)) {
1116                    tmp = new FastMap/*<K,V>*/(new Entry[1 << 9][]); // 16,384
1117 } else if (newLength <= (1 << 12)) {
1118                    tmp = new FastMap/*<K,V>*/(new Entry[1 << 12][]); // 131,072
1119 } else if (newLength <= (1 << 15)) {
1120                    tmp = new FastMap/*<K,V>*/(new Entry[1 << 15][]); // 1,048,576
1121 } else if (newLength <= (1 << 18)) {
1122                    tmp = new FastMap/*<K,V>*/(new Entry[1 << 18][]);
1123                } else if (newLength <= (1 << 21)) {
1124                    tmp = new FastMap/*<K,V>*/(new Entry[1 << 21][]);
1125                } else if (newLength <= (1 << 24)) {
1126                    tmp = new FastMap/*<K,V>*/(new Entry[1 << 24][]);
1127                } else if (newLength <= (1 << 27)) {
1128                    tmp = new FastMap/*<K,V>*/(new Entry[1 << 27][]);
1129                } else { // Cannot increase.
1130 return;
1131                }
1132                for (int i = 0; i < tmp._entries.length;) {
1133                    tmp._entries[i++] = NULL_BLOCK;
1134                }
1135
1136                // Takes the entry from the new map.
1137 final Entry[][] newEntries = tmp._entries;
1138
1139                // Setups what is going to be the old entries.
1140 tmp._entries = _entries;
1141                tmp._oldEntries = _oldEntries;
1142                tmp._keyComp = _keyComp;
1143                tmp._head = null;
1144                tmp._tail = null;
1145                tmp._size = -1;
1146
1147                // Swaps entries.
1148 _oldEntries = tmp;
1149                _entries = newEntries; // Use new larger entry table now.
1150
1151                // Done. We have now a much larger entry table.
1152 // Still, we keep reference to the old entries through oldEntries
1153 // until the map is cleared.
1154 }
1155        });
1156    }
1157
1158    private static final Entry[] NULL_BLOCK = new Entry[1 << R0];
1159
1160    // Overrides.
1161 public boolean move(ObjectSpace os) {
1162        if (super.move(os)) {
1163            for (Entry e = _head, end = _tail; (e = e._next) != end;) {
1164                if (e._key instanceof Realtime) {
1165                    ((Realtime) e._key).move(os);
1166                }
1167                if (e._value instanceof Realtime) {
1168                    ((Realtime) e._value).move(os);
1169                }
1170            }
1171            return true;
1172        }
1173        return false;
1174    }
1175
1176    // Implements Reusable.
1177 public void reset() {
1178        setShared(false); // A shared map can only be reset if no thread use it.
1179 clear(); // In which case, it is safe to recycle the entries.
1180 setKeyComparator(FastComparator.DEFAULT);
1181        setValueComparator(FastComparator.DEFAULT);
1182    }
1183
1184    /**
1185     * Requires special handling during de-serialization process.
1186     *
1187     * @param stream the object input stream.
1188     * @throws IOException if an I/O error occurs.
1189     * @throws ClassNotFoundException if the class for the object de-serialized
1190     * is not found.
1191     */
1192    private void readObject(ObjectInputStream stream) throws IOException ,
1193            ClassNotFoundException {
1194        setKeyComparator((FastComparator) stream.readObject());
1195        setValueComparator((FastComparator) stream.readObject());
1196        setShared(stream.readBoolean());
1197        final int size = stream.readInt();
1198        setup(size);
1199        for (int i = 0; i < size; i++) {
1200            Object /*{K}*/key = (Object /*{K}*/) stream.readObject();
1201            Object /*{V}*/value = (Object /*{V}*/) stream.readObject();
1202            addEntry(_keyComparator.hashCodeOf(key), key, value);
1203        }
1204    }
1205
1206    /**
1207     * Requires special handling during serialization process.
1208     *
1209     * @param stream the object output stream.
1210     * @throws IOException if an I/O error occurs.
1211     */
1212    private void writeObject(ObjectOutputStream stream) throws IOException {
1213        stream.writeObject(getKeyComparator());
1214        stream.writeObject(getValueComparator());
1215        stream.writeBoolean(_isShared);
1216        stream.writeInt(_size);
1217        for (Entry e = _head, end = _tail; (e = e._next) != end;) {
1218            stream.writeObject(e._key);
1219            stream.writeObject(e._value);
1220        }
1221    }
1222
1223    /**
1224     * This class represents a {@link FastMap} entry.
1225     */
1226    public static final class Entry/*<K,V>*/implements Map.Entry/*<K,V>*/,
1227            Record {
1228
1229        /**
1230         * Holds the next node.
1231         */
1232        private Entry/*<K,V>*/_next;
1233
1234        /**
1235         * Holds the previous node.
1236         */
1237        private Entry/*<K,V>*/_previous;
1238
1239        /**
1240         * Holds the entry key.
1241         */
1242        private Object /*{K}*/_key;
1243
1244        /**
1245         * Holds the entry value.
1246         */
1247        private Object /*{V}*/_value;
1248
1249        /**
1250         * Holds the next entry in the same bucket.
1251         */
1252        private Entry/*<K,V>*/_beside;
1253
1254        /**
1255         * Holds the hash table this entry belongs to.
1256         */
1257        private Entry/*<K,V>*/[][] _table;
1258
1259        /**
1260         * Holds the key hash code.
1261         */
1262        private int _keyHash;
1263
1264        /**
1265         * Default constructor.
1266         */
1267        private Entry() {
1268        }
1269
1270        /**
1271         * Returns the entry after this one.
1272         *
1273         * @return the next entry.
1274         */
1275        public final Record/*Entry<K,V>*/getNext() {
1276            return _next;
1277        }
1278
1279        /**
1280         * Returns the entry before this one.
1281         *
1282         * @return the previous entry.
1283         */
1284        public final Record/*Entry<K,V>*/getPrevious() {
1285            return _previous;
1286        }
1287
1288        /**
1289         * Returns the key for this entry.
1290         *
1291         * @return the entry key.
1292         */
1293        public final Object /*{K}*/getKey() {
1294            return _key;
1295        }
1296
1297        /**
1298         * Returns the value for this entry.
1299         *
1300         * @return the entry value.
1301         */
1302        public final Object /*{V}*/getValue() {
1303            return _value;
1304        }
1305
1306        /**
1307         * Sets the value for this entry.
1308         *
1309         * @param value the new value.
1310         * @return the previous value.
1311         */
1312        public final Object /*{V}*/setValue(Object /*{V}*/value) {
1313            Object /*{V}*/old = _value;
1314            _value = value;
1315            return old;
1316        }
1317
1318        /**
1319         * Indicates if this entry is considered equals to the specified entry
1320         * (using default value and key equality comparator to ensure symetry).
1321         *
1322         * @param that the object to test for equality.
1323         * @return <code>true<code> if both entry have equal keys and values.
1324         * <code>false<code> otherwise.
1325         */
1326        public boolean equals(Object that) {
1327            if (that instanceof Map.Entry) {
1328                Map.Entry entry = (Map.Entry) that;
1329                return _key.equals(entry.getKey())
1330                        && ((_value != null) ? _value.equals(entry.getValue())
1331                                : (entry.getValue() == null));
1332            } else {
1333                return false;
1334            }
1335        }
1336
1337        /**
1338         * Returns the hash code for this entry.
1339         *
1340         * @return this entry hash code.
1341         */
1342        public int hashCode() {
1343            return _key.hashCode() ^ ((_value != null) ? _value.hashCode() : 0);
1344        }
1345
1346        /**
1347         * Detaches this entry from the entry table and list.
1348         */
1349        private final void detach() {
1350            // Removes from list.
1351 _previous._next = _next;
1352            _next._previous = _previous;
1353
1354            // Removes from bucket.
1355 final int index = (_keyHash >> R0) & (_table.length - 1);
1356            final Entry/*<K,V>*/beside = _beside;
1357            Entry/*<K,V>*/previous = _table[index][_keyHash & M0];
1358            if (previous == this) { // First in bucket.
1359 _table[index][_keyHash & M0] = beside;
1360            } else {
1361                while (previous._beside != this) {
1362                    previous = previous._beside;
1363                }
1364                previous._beside = beside;
1365            }
1366        }
1367    }
1368
1369    /**
1370     * This class represents an read-only view over a {@link FastMap}.
1371     */
1372    private final class Unmodifiable extends RealtimeObject implements Map,
1373            Serializable {
1374
1375        public boolean equals(Object obj) {
1376            return FastMap.this.equals(obj);
1377        }
1378
1379        public int hashCode() {
1380            return FastMap.this.hashCode();
1381        }
1382
1383        public Text toText() {
1384            return FastMap.this.toText();
1385        }
1386
1387        public int size() {
1388            return FastMap.this.size();
1389        }
1390
1391        public boolean isEmpty() {
1392            return FastMap.this.isEmpty();
1393        }
1394
1395        public boolean containsKey(Object key) {
1396            return FastMap.this.containsKey(key);
1397        }
1398
1399        public boolean containsValue(Object value) {
1400            return FastMap.this.containsValue(value);
1401        }
1402
1403        public Object get(Object key) {
1404            return FastMap.this.get(key);
1405        }
1406
1407        public Object put(Object key, Object value) {
1408            throw new UnsupportedOperationException ("Unmodifiable map");
1409        }
1410
1411        public Object remove(Object key) {
1412            throw new UnsupportedOperationException ("Unmodifiable map");
1413        }
1414
1415        public void putAll(Map map) {
1416            throw new UnsupportedOperationException ("Unmodifiable map");
1417        }
1418
1419        public void clear() {
1420            throw new UnsupportedOperationException ("Unmodifiable map");
1421        }
1422
1423        public Set keySet() {
1424            return (Set) ((KeySet)FastMap.this.keySet()).unmodifiable();
1425        }
1426
1427        public Collection values() {
1428            return ((Values)FastMap.this.values()).unmodifiable();
1429        }
1430
1431        public Set entrySet() {
1432            throw new UnsupportedOperationException (
1433                    "Direct view over unmodifiable map entries is not supported "
1434                            + " (to prevent access to Entry.setValue(Object) method). "
1435                            + "To iterate over unmodifiable map entries, applications may "
1436                            + "use the keySet() and values() fast collection views "
1437                            + "in conjonction.");
1438        }
1439    }
1440
1441    private static final long serialVersionUID = 1L;
1442}

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags