View Javadoc
1   package org.codehaus.plexus.util;
2   
3   /*
4    * J.A.D.E. Java(TM) Addition to Default Environment.
5    * Latest release available at http://jade.dautelle.com/
6    * This class is public domain (not copyrighted).
7    */
8   
9   import java.io.IOException;
10  import java.io.ObjectInputStream;
11  import java.io.ObjectOutputStream;
12  import java.io.Serializable;
13  import java.util.AbstractCollection;
14  import java.util.AbstractSet;
15  import java.util.Collection;
16  import java.util.Iterator;
17  import java.util.Map;
18  import java.util.Set;
19  
20  /**
21   * <p>
22   * This class represents a <code>Map</code> collection with real-time behavior. Unless the map's size exceeds its
23   * current capacity, no dynamic memory allocation is ever performed and response time is <b>extremely fast</b> and
24   * <b>consistent</b>.
25   * </p>
26   * <p>
27   * Our <a href="http://jade.dautelle.com/doc/benchmark.txt">benchmark</a> indicates that {@link FastMap#put
28   * FastMap.put(key, value)} is up to <b>5x faster</b> than <code>java.util.HashMap.put(key, value)</code>. This
29   * difference is mostly due to the cost of the <code>Map.Entry</code> allocations that {@link FastMap} avoids by
30   * recycling its entries (see note below).
31   * </p>
32   * <p>
33   * {@link FastMap} has a predictable iteration order, which is the order in which keys were inserted into the map
34   * (similar to <code>java.util.LinkedHashMap</code> collection class).
35   * </p>
36   * <p>
37   * Applications may change the resizing policy of {@link FastMap} by overriding the {@link #sizeChanged} method. For
38   * example, to improve predictability, automatic resizing can be disabled.
39   * </p>
40   * <p>
41   * This implementation is not synchronized. Multiple threads accessing or modifying the collection must be synchronized
42   * externally.
43   * </p>
44   * <p>
45   * <b>Note:</b> To avoid dynamic memory allocations, {@link FastMap} maintains an internal pool of
46   * <code>Map.Entry</code> objects. The size of the pool is determined by the map's capacity. When an entry is removed
47   * from the map, it is automatically restored to the pool.
48   * </p>
49   * <p>
50   * <i> This class is <b>public domain</b> (not copyrighted).</i>
51   * </p>
52   * 
53   * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
54   * @version 5.3, October 31 2003
55   */
56  public class FastMap<K, V>
57      implements Map<K, V>, Cloneable, Serializable
58  {
59  
60      /**
61       * Holds the map's hash table.
62       */
63      private transient EntryImpl[] _entries;
64  
65      /**
66       * Holds the map's current capacity.
67       */
68      private transient int _capacity;
69  
70      /**
71       * Holds the hash code mask.
72       */
73      private transient int _mask;
74  
75      /**
76       * Holds the first pool entry (linked list).
77       */
78      private transient EntryImpl _poolFirst;
79  
80      /**
81       * Holds the first map entry (linked list).
82       */
83      private transient EntryImpl _mapFirst;
84  
85      /**
86       * Holds the last map entry (linked list).
87       */
88      private transient EntryImpl _mapLast;
89  
90      /**
91       * Holds the current size.
92       */
93      private transient int _size;
94  
95      /**
96       * Creates a {@link FastMap} with a capacity of <code>256</code> entries.
97       */
98      public FastMap()
99      {
100         initialize( 256 );
101     }
102 
103     /**
104      * Creates a {@link FastMap}, copy of the specified <code>Map</code>. If the specified map is not an instance of
105      * {@link FastMap}, the newly created map has a capacity set to the specified map's size. The copy has the same
106      * order as the original, regardless of the original map's implementation:
107      * 
108      * <pre>
109      *     TreeMap dictionary = ...;
110      *     FastMap dictionaryLookup = new FastMap(dictionary);
111      * </pre>
112      * 
113      * @param map the map whose mappings are to be placed in this map.
114      */
115     public FastMap( Map map )
116     {
117         int capacity = ( map instanceof FastMap ) ? ( (FastMap) map ).capacity() : map.size();
118         initialize( capacity );
119         putAll( map );
120     }
121 
122     /**
123      * Creates a {@link FastMap} with the specified capacity. Unless the capacity is exceeded, operations on this map do
124      * not allocate entries. For optimum performance, the capacity should be of the same order of magnitude or larger
125      * than the expected map's size.
126      * 
127      * @param capacity the number of buckets in the hash table; it also defines the number of pre-allocated entries.
128      */
129     public FastMap( int capacity )
130     {
131         initialize( capacity );
132     }
133 
134     /**
135      * Returns the number of key-value mappings in this {@link FastMap}.
136      *
137      * @return this map's size.
138      */
139     public int size()
140     {
141         return _size;
142     }
143 
144     /**
145      * Returns the capacity of this {@link FastMap}. The capacity defines the number of buckets in the hash table, as
146      * well as the maximum number of entries the map may contain without allocating memory.
147      *
148      * @return this map's capacity.
149      */
150     public int capacity()
151     {
152         return _capacity;
153     }
154 
155     /**
156      * Indicates if this {@link FastMap} contains no key-value mappings.
157      *
158      * @return <code>true</code> if this map contains no key-value mappings; <code>false</code> otherwise.
159      */
160     public boolean isEmpty()
161     {
162         return _size == 0;
163     }
164 
165     /**
166      * Indicates if this {@link FastMap} contains a mapping for the specified key.
167      *
168      * @param key the key whose presence in this map is to be tested.
169      * @return <code>true</code> if this map contains a mapping for the specified key; <code>false</code> otherwise.
170      * @throws NullPointerException if the key is <code>null</code>.
171      */
172     public boolean containsKey( Object key )
173     {
174         EntryImpl entry = _entries[keyHash( key ) & _mask];
175         while ( entry != null )
176         {
177             if ( key.equals( entry._key ) )
178             {
179                 return true;
180             }
181             entry = entry._next;
182         }
183         return false;
184     }
185 
186     /**
187      * Indicates if this {@link FastMap} maps one or more keys to the specified value.
188      *
189      * @param value the value whose presence in this map is to be tested.
190      * @return <code>true</code> if this map maps one or more keys to the specified value.
191      * @throws NullPointerException if the key is <code>null</code>.
192      */
193     public boolean containsValue( Object value )
194     {
195         EntryImpl entry = _mapFirst;
196         while ( entry != null )
197         {
198             if ( value.equals( entry._value ) )
199             {
200                 return true;
201             }
202             entry = entry._after;
203         }
204         return false;
205     }
206 
207     /**
208      * Returns the value to which this {@link FastMap} maps the specified key.
209      *
210      * @param key the key whose associated value is to be returned.
211      * @return the value to which this map maps the specified key, or <code>null</code> if there is no mapping for the
212      *         key.
213      * @throws NullPointerException if key is <code>null</code>.
214      */
215     public V get( Object key )
216     {
217         EntryImpl<K, V> entry = _entries[keyHash( key ) & _mask];
218         while ( entry != null )
219         {
220             if ( key.equals( entry._key ) )
221             {
222                 return entry._value;
223             }
224             entry = entry._next;
225         }
226         return null;
227     }
228 
229     /**
230      * Returns the entry with the specified key.
231      * 
232      * @param key the key whose associated entry is to be returned.
233      * @return the entry for the specified key or <code>null</code> if none.
234      */
235     public Map.Entry getEntry( Object key )
236     {
237         EntryImpl entry = _entries[keyHash( key ) & _mask];
238         while ( entry != null )
239         {
240             if ( key.equals( entry._key ) )
241             {
242                 return entry;
243             }
244             entry = entry._next;
245         }
246         return null;
247     }
248 
249     /**
250      * Associates the specified value with the specified key in this {@link FastMap}. If the {@link FastMap} previously
251      * contained a mapping for this key, the old value is replaced.
252      *
253      * @param key the key with which the specified value is to be associated.
254      * @param value the value to be associated with the specified key.
255      * @return the previous value associated with specified key, or <code>null</code> if there was no mapping for key. A
256      *         <code>null</code> return can also indicate that the map previously associated <code>null</code> with the
257      *         specified key.
258      * @throws NullPointerException if the key is <code>null</code>.
259      */
260     public Object put( Object key, Object value )
261     {
262         EntryImpl entry = _entries[keyHash( key ) & _mask];
263         while ( entry != null )
264         {
265             if ( key.equals( entry._key ) )
266             {
267                 Object prevValue = entry._value;
268                 entry._value = value;
269                 return prevValue;
270             }
271             entry = entry._next;
272         }
273         // No previous mapping.
274         addEntry( key, value );
275         return null;
276     }
277 
278     /**
279      * Copies all of the mappings from the specified map to this {@link FastMap}.
280      *
281      * @param map the mappings to be stored in this map.
282      * @throws NullPointerException the specified map is <code>null</code>, or the specified map contains
283      *             <code>null</code> keys.
284      */
285     public void putAll( Map<? extends K, ? extends V> map )
286     {
287         for ( Entry<? extends K, ? extends V> entry : map.entrySet() )
288         {
289             addEntry( entry.getKey(), entry.getValue() );
290         }
291     }
292 
293     /**
294      * Removes the mapping for this key from this {@link FastMap} if present.
295      *
296      * @param key the key whose mapping is to be removed from the map.
297      * @return previous value associated with specified key, or <code>null</code> if there was no mapping for key. A
298      *         <code>null</code> return can also indicate that the map previously associated <code>null</code> with the
299      *         specified key.
300      * @throws NullPointerException if the key is <code>null</code>.
301      */
302     public V remove( Object key )
303     {
304         EntryImpl<K, V> entry = _entries[keyHash( key ) & _mask];
305         while ( entry != null )
306         {
307             if ( key.equals( entry._key ) )
308             {
309                 V prevValue = entry._value;
310                 removeEntry( entry );
311                 return prevValue;
312             }
313             entry = entry._next;
314         }
315         return null;
316     }
317 
318     /**
319      * Removes all mappings from this {@link FastMap}.
320      */
321     public void clear()
322     {
323         // Clears all keys, values and buckets linked lists.
324         for ( EntryImpl entry = _mapFirst; entry != null; entry = entry._after )
325         {
326             entry._key = null;
327             entry._value = null;
328             entry._before = null;
329             entry._next = null;
330             if ( entry._previous == null )
331             { // First in bucket.
332                 _entries[entry._index] = null;
333             }
334             else
335             {
336                 entry._previous = null;
337             }
338         }
339 
340         // Recycles all entries.
341         if ( _mapLast != null )
342         {
343             _mapLast._after = _poolFirst; // Connects to pool.
344             _poolFirst = _mapFirst;
345             _mapFirst = null;
346             _mapLast = null;
347             _size = 0;
348             sizeChanged();
349         }
350     }
351 
352     /**
353      * Changes the current capacity of this {@link FastMap}. If the capacity is increased, new entries are allocated and
354      * added to the pool. If the capacity is decreased, entries from the pool are deallocated (and are eventually
355      * garbage collected). The capacity also determined the number of buckets for the hash table.
356      * 
357      * @param newCapacity the new capacity of this map.
358      */
359     public void setCapacity( int newCapacity )
360     {
361         if ( newCapacity > _capacity )
362         { // Capacity increases.
363             for ( int i = _capacity; i < newCapacity; i++ )
364             {
365                 EntryImpl entry = new EntryImpl();
366                 entry._after = _poolFirst;
367                 _poolFirst = entry;
368             }
369         }
370         else if ( newCapacity < _capacity )
371         { // Capacity decreases.
372             for ( int i = newCapacity; ( i < _capacity ) && ( _poolFirst != null ); i++ )
373             {
374                 // Disconnects the entry for gc to do its work.
375                 EntryImpl entry = _poolFirst;
376                 _poolFirst = entry._after;
377                 entry._after = null; // All pointers are now null!
378             }
379         }
380         // Find a power of 2 >= capacity
381         int tableLength = 16;
382         while ( tableLength < newCapacity )
383         {
384             tableLength <<= 1;
385         }
386         // Checks if the hash table has to be re-sized.
387         if ( _entries.length != tableLength )
388         {
389             _entries = new EntryImpl[tableLength];
390             _mask = tableLength - 1;
391 
392             // Repopulates the hash table.
393             EntryImpl entry = _mapFirst;
394             while ( entry != null )
395             {
396                 int index = keyHash( entry._key ) & _mask;
397                 entry._index = index;
398 
399                 // Connects to bucket.
400                 entry._previous = null; // Resets previous.
401                 EntryImpl next = _entries[index];
402                 entry._next = next;
403                 if ( next != null )
404                 {
405                     next._previous = entry;
406                 }
407                 _entries[index] = entry;
408 
409                 entry = entry._after;
410             }
411         }
412         _capacity = newCapacity;
413     }
414 
415     /**
416      * Returns a shallow copy of this {@link FastMap}. The keys and the values themselves are not cloned.
417      *
418      * @return a shallow copy of this map.
419      */
420     public Object clone()
421     {
422         try
423         {
424             FastMap clone = (FastMap) super.clone();
425             clone.initialize( _capacity );
426             clone.putAll( this );
427             return clone;
428         }
429         catch ( CloneNotSupportedException e )
430         {
431             // Should not happen, since we are Cloneable.
432             throw new InternalError();
433         }
434     }
435 
436     /**
437      * Compares the specified object with this {@link FastMap} for equality. Returns <code>true</code> if the given
438      * object is also a map and the two maps represent the same mappings (regardless of collection iteration order).
439      *
440      * @param obj the object to be compared for equality with this map.
441      * @return <code>true</code> if the specified object is equal to this map; <code>false</code> otherwise.
442      */
443     public boolean equals( Object obj )
444     {
445         if ( obj == this )
446         {
447             return true;
448         }
449         else if ( obj instanceof Map )
450         {
451             Map that = (Map) obj;
452             if ( this.size() == that.size() )
453             {
454                 EntryImpl entry = _mapFirst;
455                 while ( entry != null )
456                 {
457                     if ( !that.entrySet().contains( entry ) )
458                     {
459                         return false;
460                     }
461                     entry = entry._after;
462                 }
463                 return true;
464             }
465             else
466             {
467                 return false;
468             }
469         }
470         else
471         {
472             return false;
473         }
474     }
475 
476     /**
477      * Returns the hash code value for this {@link FastMap}.
478      *
479      * @return the hash code value for this map.
480      */
481     public int hashCode()
482     {
483         int code = 0;
484         EntryImpl entry = _mapFirst;
485         while ( entry != null )
486         {
487             code += entry.hashCode();
488             entry = entry._after;
489         }
490         return code;
491     }
492 
493     /**
494      * Returns a <code>String</code> representation of this {@link FastMap}.
495      *
496      * @return <code>this.entrySet().toString();</code>
497      */
498     public String toString()
499     {
500         return entrySet().toString();
501     }
502 
503     /**
504      * Returns a collection view of the values contained in this {@link FastMap}. The collection is backed by the map,
505      * so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal,
506      * which removes the corresponding mapping from this map, via the <code>Iterator.remove</code>,
507      * <code>Collection.remove</code>, <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code>
508      * operations. It does not support the <code>add</code> or <code>addAll</code> operations.
509      *
510      * @return a collection view of the values contained in this map.
511      */
512     public Collection values()
513     {
514         return _values;
515     }
516 
517     private transient Values _values;
518 
519     private class Values
520         extends AbstractCollection
521     {
522         public Iterator iterator()
523         {
524             return new Iterator()
525             {
526                 EntryImpl after = _mapFirst;
527 
528                 EntryImpl before;
529 
530                 public void remove()
531                 {
532                     removeEntry( before );
533                 }
534 
535                 public boolean hasNext()
536                 {
537                     return after != null;
538                 }
539 
540                 public Object next()
541                 {
542                     before = after;
543                     after = after._after;
544                     return before._value;
545                 }
546             };
547         }
548 
549         public int size()
550         {
551             return _size;
552         }
553 
554         public boolean contains( Object o )
555         {
556             return containsValue( o );
557         }
558 
559         public void clear()
560         {
561             FastMap.this.clear();
562         }
563     }
564 
565     /**
566      * Returns a collection view of the mappings contained in this {@link FastMap}. Each element in the returned
567      * collection is a <code>Map.Entry</code>. The collection is backed by the map, so changes to the map are reflected
568      * in the collection, and vice-versa. The collection supports element removal, which removes the corresponding
569      * mapping from this map, via the <code>Iterator.remove</code>, <code>Collection.remove</code>,
570      * <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code> operations. It does not support the
571      * <code>add</code> or <code>addAll</code> operations.
572      *
573      * @return a collection view of the mappings contained in this map.
574      */
575     public Set entrySet()
576     {
577         return _entrySet;
578     }
579 
580     private transient EntrySet _entrySet;
581 
582     private class EntrySet
583         extends AbstractSet
584     {
585         public Iterator iterator()
586         {
587             return new Iterator()
588             {
589                 EntryImpl after = _mapFirst;
590 
591                 EntryImpl before;
592 
593                 public void remove()
594                 {
595                     removeEntry( before );
596                 }
597 
598                 public boolean hasNext()
599                 {
600                     return after != null;
601                 }
602 
603                 public Object next()
604                 {
605                     before = after;
606                     after = after._after;
607                     return before;
608                 }
609             };
610         }
611 
612         public int size()
613         {
614             return _size;
615         }
616 
617         public boolean contains( Object obj )
618         { // Optimization.
619             if ( obj instanceof Map.Entry )
620             {
621                 Map.Entry entry = (Map.Entry) obj;
622                 Map.Entry mapEntry = getEntry( entry.getKey() );
623                 return entry.equals( mapEntry );
624             }
625             else
626             {
627                 return false;
628             }
629         }
630 
631         public boolean remove( Object obj )
632         { // Optimization.
633             if ( obj instanceof Map.Entry )
634             {
635                 Map.Entry entry = (Map.Entry) obj;
636                 EntryImpl mapEntry = (EntryImpl) getEntry( entry.getKey() );
637                 if ( ( mapEntry != null ) && ( entry.getValue() ).equals( mapEntry._value ) )
638                 {
639                     removeEntry( mapEntry );
640                     return true;
641                 }
642             }
643             return false;
644         }
645     }
646 
647     /**
648      * Returns a set view of the keys contained in this {@link FastMap}. The set is backed by the map, so changes to the
649      * map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding
650      * mapping from this map, via the <code>Iterator.remove</code>, <code>Collection.remove</code>,
651      * <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code> operations. It does not support the
652      * <code>add</code> or <code>addAll</code> operations.
653      *
654      * @return a set view of the keys contained in this map.
655      */
656     public Set keySet()
657     {
658         return _keySet;
659     }
660 
661     private transient KeySet _keySet;
662 
663     private class KeySet
664         extends AbstractSet
665     {
666         public Iterator iterator()
667         {
668             return new Iterator()
669             {
670                 EntryImpl after = _mapFirst;
671 
672                 EntryImpl before;
673 
674                 public void remove()
675                 {
676                     removeEntry( before );
677                 }
678 
679                 public boolean hasNext()
680                 {
681                     return after != null;
682                 }
683 
684                 public Object next()
685                 {
686                     before = after;
687                     after = after._after;
688                     return before._key;
689                 }
690             };
691         }
692 
693         public int size()
694         {
695             return _size;
696         }
697 
698         public boolean contains( Object obj )
699         { // Optimization.
700             return FastMap.this.containsKey( obj );
701         }
702 
703         public boolean remove( Object obj )
704         { // Optimization.
705             return FastMap.this.remove( obj ) != null;
706         }
707 
708         public void clear()
709         { // Optimization.
710             FastMap.this.clear();
711         }
712     }
713 
714     /**
715      * This methods is being called when the size of this {@link FastMap} has changed. The default behavior is to double
716      * the map's capacity when the map's size reaches the current map's capacity. Sub-class may override this method to
717      * implement custom resizing policies or to disable automatic resizing. For example:
718      * 
719      * <pre>
720      * Map fixedCapacityMap = new FastMap( 256 )
721      * {
722      *     protected sizeChanged()
723      *     {
724      *         // Do nothing, automatic resizing disabled.
725      *     }
726      * };
727      * </pre>
728      * 
729      * @see #setCapacity
730      */
731     protected void sizeChanged()
732     {
733         if ( size() > capacity() )
734         {
735             setCapacity( capacity() * 2 );
736         }
737     }
738 
739     /**
740      * Returns the hash code for the specified key. The formula being used is identical to the formula used by
741      * <code>java.util.HashMap</code> (ensures similar behavior for ill-conditioned hashcode keys).
742      * 
743      * @param key the key to calculate the hashcode for.
744      * @return the hash code for the specified key.
745      */
746     private static int keyHash( Object key )
747     {
748         // From HashMap.hash(Object) function.
749         int hashCode = key.hashCode();
750         hashCode += ~( hashCode << 9 );
751         hashCode ^= ( hashCode >>> 14 );
752         hashCode += ( hashCode << 4 );
753         hashCode ^= ( hashCode >>> 10 );
754         return hashCode;
755     }
756 
757     /**
758      * Adds a new entry for the specified key and value.
759      * 
760      * @param key the entry's key.
761      * @param value the entry's value.
762      */
763     private void addEntry( Object key, Object value )
764     {
765         EntryImpl entry = _poolFirst;
766         if ( entry != null )
767         {
768             _poolFirst = entry._after;
769             entry._after = null;
770         }
771         else
772         { // Pool empty.
773             entry = new EntryImpl();
774         }
775 
776         // Setup entry parameters.
777         entry._key = key;
778         entry._value = value;
779         int index = keyHash( key ) & _mask;
780         entry._index = index;
781 
782         // Connects to bucket.
783         EntryImpl next = _entries[index];
784         entry._next = next;
785         if ( next != null )
786         {
787             next._previous = entry;
788         }
789         _entries[index] = entry;
790 
791         // Connects to collection.
792         if ( _mapLast != null )
793         {
794             entry._before = _mapLast;
795             _mapLast._after = entry;
796         }
797         else
798         {
799             _mapFirst = entry;
800         }
801         _mapLast = entry;
802 
803         // Updates size.
804         _size++;
805         sizeChanged();
806     }
807 
808     /**
809      * Removes the specified entry from the map.
810      * 
811      * @param entry the entry to be removed.
812      */
813     private void removeEntry( EntryImpl entry )
814     {
815 
816         // Removes from bucket.
817         EntryImpl previous = entry._previous;
818         EntryImpl next = entry._next;
819         if ( previous != null )
820         {
821             previous._next = next;
822             entry._previous = null;
823         }
824         else
825         { // First in bucket.
826             _entries[entry._index] = next;
827         }
828         if ( next != null )
829         {
830             next._previous = previous;
831             entry._next = null;
832         } // Else do nothing, no last pointer.
833 
834         // Removes from collection.
835         EntryImpl before = entry._before;
836         EntryImpl after = entry._after;
837         if ( before != null )
838         {
839             before._after = after;
840             entry._before = null;
841         }
842         else
843         { // First in collection.
844             _mapFirst = after;
845         }
846         if ( after != null )
847         {
848             after._before = before;
849         }
850         else
851         { // Last in collection.
852             _mapLast = before;
853         }
854 
855         // Clears value and key.
856         entry._key = null;
857         entry._value = null;
858 
859         // Recycles.
860         entry._after = _poolFirst;
861         _poolFirst = entry;
862 
863         // Updates size.
864         _size--;
865         sizeChanged();
866     }
867 
868     /**
869      * Initializes this instance for the specified capacity. Once initialized, operations on this map should not create
870      * new objects (unless the map's size exceeds the specified capacity).
871      * 
872      * @param capacity the initial capacity.
873      */
874     private void initialize( int capacity )
875     {
876         // Find a power of 2 >= capacity
877         int tableLength = 16;
878         while ( tableLength < capacity )
879         {
880             tableLength <<= 1;
881         }
882         // Allocates hash table.
883         _entries = new EntryImpl[tableLength];
884         _mask = tableLength - 1;
885         _capacity = capacity;
886         _size = 0;
887         // Allocates views.
888         _values = new Values();
889         _entrySet = new EntrySet();
890         _keySet = new KeySet();
891         // Resets pointers.
892         _poolFirst = null;
893         _mapFirst = null;
894         _mapLast = null;
895         // Allocates entries.
896         for ( int i = 0; i < capacity; i++ )
897         {
898             EntryImpl entry = new EntryImpl();
899             entry._after = _poolFirst;
900             _poolFirst = entry;
901         }
902     }
903 
904     /**
905      * Requires special handling during de-serialization process.
906      *
907      * @param stream the object input stream.
908      * @throws IOException if an I/O error occurs.
909      * @throws ClassNotFoundException if the class for the object de-serialized is not found.
910      */
911     private void readObject( ObjectInputStream stream )
912         throws IOException, ClassNotFoundException
913     {
914         int capacity = stream.readInt();
915         initialize( capacity );
916         int size = stream.readInt();
917         for ( int i = 0; i < size; i++ )
918         {
919             Object key = stream.readObject();
920             Object value = stream.readObject();
921             addEntry( key, value );
922         }
923     }
924 
925     /**
926      * Requires special handling during serialization process.
927      *
928      * @param stream the object output stream.
929      * @throws IOException if an I/O error occurs.
930      */
931     private void writeObject( ObjectOutputStream stream )
932         throws IOException
933     {
934         stream.writeInt( _capacity );
935         stream.writeInt( _size );
936         int count = 0;
937         EntryImpl entry = _mapFirst;
938         while ( entry != null )
939         {
940             stream.writeObject( entry._key );
941             stream.writeObject( entry._value );
942             count++;
943             entry = entry._after;
944         }
945         if ( count != _size )
946         {
947             throw new IOException( "FastMap Corrupted" );
948         }
949     }
950 
951     /**
952      * This class represents a {@link FastMap} entry.
953      */
954     private static final class EntryImpl<K, V>
955         implements Map.Entry<K, V>
956     {
957 
958         /**
959          * Holds the entry key (null when in pool).
960          */
961         private K _key;
962 
963         /**
964          * Holds the entry value (null when in pool).
965          */
966         private V _value;
967 
968         /**
969          * Holds the bucket index (undefined when in pool).
970          */
971         private int _index;
972 
973         /**
974          * Holds the previous entry in the same bucket (null when in pool).
975          */
976         private EntryImpl _previous;
977 
978         /**
979          * Holds the next entry in the same bucket (null when in pool).
980          */
981         private EntryImpl _next;
982 
983         /**
984          * Holds the entry added before this entry (null when in pool).
985          */
986         private EntryImpl _before;
987 
988         /**
989          * Holds the entry added after this entry or the next available entry when in pool.
990          */
991         private EntryImpl _after;
992 
993         /**
994          * Returns the key for this entry.
995          * 
996          * @return the entry's key.
997          */
998         public K getKey()
999         {
1000             return _key;
1001         }
1002 
1003         /**
1004          * Returns the value for this entry.
1005          * 
1006          * @return the entry's value.
1007          */
1008         public V getValue()
1009         {
1010             return _value;
1011         }
1012 
1013         /**
1014          * Sets the value for this entry.
1015          * 
1016          * @param value the new value.
1017          * @return the previous value.
1018          */
1019         public V setValue( V value )
1020         {
1021             V old = _value;
1022             _value = value;
1023             return old;
1024         }
1025 
1026         /**
1027          * Indicates if this entry is considered equals to the specified entry.
1028          * 
1029          * @param that the object to test for equality.
1030          * @return <code>true<code> if both entry are considered equal; <code>false<code> otherwise.
1031          */
1032         public boolean equals( Object that )
1033         {
1034             if ( that instanceof Map.Entry )
1035             {
1036                 Map.Entry entry = (Map.Entry) that;
1037                 return ( _key.equals( entry.getKey() ) )
1038                     && ( ( _value != null ) ? _value.equals( entry.getValue() ) : ( entry.getValue() == null ) );
1039             }
1040             else
1041             {
1042                 return false;
1043             }
1044         }
1045 
1046         /**
1047          * Returns the hash code for this entry.
1048          * 
1049          * @return this entry's hash code.
1050          */
1051         public int hashCode()
1052         {
1053             return _key.hashCode() ^ ( ( _value != null ) ? _value.hashCode() : 0 );
1054         }
1055 
1056         /**
1057          * Returns the text representation of this entry.
1058          * 
1059          * @return this entry's textual representation.
1060          */
1061         public String toString()
1062         {
1063             return _key + "=" + _value;
1064         }
1065     }
1066 }