Coverage Report - org.codehaus.plexus.util.FastMap
 
Classes in this File Line Coverage Branch Coverage Complexity
FastMap
0%
0/229
0%
0/92
2.228
FastMap$1
N/A
N/A
2.228
FastMap$EntryImpl
0%
0/12
0%
0/12
2.228
FastMap$EntrySet
0%
0/15
0%
0/8
2.228
FastMap$EntrySet$1
0%
0/8
0%
0/2
2.228
FastMap$KeySet
0%
0/7
0%
0/2
2.228
FastMap$KeySet$1
0%
0/8
0%
0/2
2.228
FastMap$Values
0%
0/6
N/A
2.228
FastMap$Values$1
0%
0/8
0%
0/2
2.228
 
 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  0
 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  0
     {
 100  0
         initialize( 256 );
 101  0
     }
 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  0
     {
 117  0
         int capacity = ( map instanceof FastMap ) ? ( (FastMap) map ).capacity() : map.size();
 118  0
         initialize( capacity );
 119  0
         putAll( map );
 120  0
     }
 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  0
     {
 131  0
         initialize( capacity );
 132  0
     }
 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  0
         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  0
         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  0
         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  0
         EntryImpl entry = _entries[keyHash( key ) & _mask];
 175  0
         while ( entry != null )
 176  
         {
 177  0
             if ( key.equals( entry._key ) )
 178  
             {
 179  0
                 return true;
 180  
             }
 181  0
             entry = entry._next;
 182  
         }
 183  0
         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  0
         EntryImpl entry = _mapFirst;
 196  0
         while ( entry != null )
 197  
         {
 198  0
             if ( value.equals( entry._value ) )
 199  
             {
 200  0
                 return true;
 201  
             }
 202  0
             entry = entry._after;
 203  
         }
 204  0
         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  0
         EntryImpl<K, V> entry = _entries[keyHash( key ) & _mask];
 218  0
         while ( entry != null )
 219  
         {
 220  0
             if ( key.equals( entry._key ) )
 221  
             {
 222  0
                 return entry._value;
 223  
             }
 224  0
             entry = entry._next;
 225  
         }
 226  0
         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  0
         EntryImpl entry = _entries[keyHash( key ) & _mask];
 238  0
         while ( entry != null )
 239  
         {
 240  0
             if ( key.equals( entry._key ) )
 241  
             {
 242  0
                 return entry;
 243  
             }
 244  0
             entry = entry._next;
 245  
         }
 246  0
         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  0
         EntryImpl entry = _entries[keyHash( key ) & _mask];
 263  0
         while ( entry != null )
 264  
         {
 265  0
             if ( key.equals( entry._key ) )
 266  
             {
 267  0
                 Object prevValue = entry._value;
 268  0
                 entry._value = value;
 269  0
                 return prevValue;
 270  
             }
 271  0
             entry = entry._next;
 272  
         }
 273  
         // No previous mapping.
 274  0
         addEntry( key, value );
 275  0
         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  0
         for ( Entry<? extends K, ? extends V> entry : map.entrySet() )
 288  
         {
 289  0
             addEntry( entry.getKey(), entry.getValue() );
 290  0
         }
 291  0
     }
 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  0
         EntryImpl<K, V> entry = _entries[keyHash( key ) & _mask];
 305  0
         while ( entry != null )
 306  
         {
 307  0
             if ( key.equals( entry._key ) )
 308  
             {
 309  0
                 V prevValue = entry._value;
 310  0
                 removeEntry( entry );
 311  0
                 return prevValue;
 312  
             }
 313  0
             entry = entry._next;
 314  
         }
 315  0
         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  0
         for ( EntryImpl entry = _mapFirst; entry != null; entry = entry._after )
 325  
         {
 326  0
             entry._key = null;
 327  0
             entry._value = null;
 328  0
             entry._before = null;
 329  0
             entry._next = null;
 330  0
             if ( entry._previous == null )
 331  
             { // First in bucket.
 332  0
                 _entries[entry._index] = null;
 333  
             }
 334  
             else
 335  
             {
 336  0
                 entry._previous = null;
 337  
             }
 338  
         }
 339  
 
 340  
         // Recycles all entries.
 341  0
         if ( _mapLast != null )
 342  
         {
 343  0
             _mapLast._after = _poolFirst; // Connects to pool.
 344  0
             _poolFirst = _mapFirst;
 345  0
             _mapFirst = null;
 346  0
             _mapLast = null;
 347  0
             _size = 0;
 348  0
             sizeChanged();
 349  
         }
 350  0
     }
 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  0
         if ( newCapacity > _capacity )
 362  
         { // Capacity increases.
 363  0
             for ( int i = _capacity; i < newCapacity; i++ )
 364  
             {
 365  0
                 EntryImpl entry = new EntryImpl();
 366  0
                 entry._after = _poolFirst;
 367  0
                 _poolFirst = entry;
 368  
             }
 369  
         }
 370  0
         else if ( newCapacity < _capacity )
 371  
         { // Capacity decreases.
 372  0
             for ( int i = newCapacity; ( i < _capacity ) && ( _poolFirst != null ); i++ )
 373  
             {
 374  
                 // Disconnects the entry for gc to do its work.
 375  0
                 EntryImpl entry = _poolFirst;
 376  0
                 _poolFirst = entry._after;
 377  0
                 entry._after = null; // All pointers are now null!
 378  
             }
 379  
         }
 380  
         // Find a power of 2 >= capacity
 381  0
         int tableLength = 16;
 382  0
         while ( tableLength < newCapacity )
 383  
         {
 384  0
             tableLength <<= 1;
 385  
         }
 386  
         // Checks if the hash table has to be re-sized.
 387  0
         if ( _entries.length != tableLength )
 388  
         {
 389  0
             _entries = new EntryImpl[tableLength];
 390  0
             _mask = tableLength - 1;
 391  
 
 392  
             // Repopulates the hash table.
 393  0
             EntryImpl entry = _mapFirst;
 394  0
             while ( entry != null )
 395  
             {
 396  0
                 int index = keyHash( entry._key ) & _mask;
 397  0
                 entry._index = index;
 398  
 
 399  
                 // Connects to bucket.
 400  0
                 entry._previous = null; // Resets previous.
 401  0
                 EntryImpl next = _entries[index];
 402  0
                 entry._next = next;
 403  0
                 if ( next != null )
 404  
                 {
 405  0
                     next._previous = entry;
 406  
                 }
 407  0
                 _entries[index] = entry;
 408  
 
 409  0
                 entry = entry._after;
 410  0
             }
 411  
         }
 412  0
         _capacity = newCapacity;
 413  0
     }
 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  0
             FastMap clone = (FastMap) super.clone();
 425  0
             clone.initialize( _capacity );
 426  0
             clone.putAll( this );
 427  0
             return clone;
 428  
         }
 429  0
         catch ( CloneNotSupportedException e )
 430  
         {
 431  
             // Should not happen, since we are Cloneable.
 432  0
             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  0
         if ( obj == this )
 446  
         {
 447  0
             return true;
 448  
         }
 449  0
         else if ( obj instanceof Map )
 450  
         {
 451  0
             Map that = (Map) obj;
 452  0
             if ( this.size() == that.size() )
 453  
             {
 454  0
                 EntryImpl entry = _mapFirst;
 455  0
                 while ( entry != null )
 456  
                 {
 457  0
                     if ( !that.entrySet().contains( entry ) )
 458  
                     {
 459  0
                         return false;
 460  
                     }
 461  0
                     entry = entry._after;
 462  
                 }
 463  0
                 return true;
 464  
             }
 465  
             else
 466  
             {
 467  0
                 return false;
 468  
             }
 469  
         }
 470  
         else
 471  
         {
 472  0
             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  0
         int code = 0;
 484  0
         EntryImpl entry = _mapFirst;
 485  0
         while ( entry != null )
 486  
         {
 487  0
             code += entry.hashCode();
 488  0
             entry = entry._after;
 489  
         }
 490  0
         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  0
         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  0
         return _values;
 515  
     }
 516  
 
 517  
     private transient Values _values;
 518  
 
 519  0
     private class Values
 520  
         extends AbstractCollection
 521  
     {
 522  
         public Iterator iterator()
 523  
         {
 524  0
             return new Iterator()
 525  0
             {
 526  0
                 EntryImpl after = _mapFirst;
 527  
 
 528  
                 EntryImpl before;
 529  
 
 530  
                 public void remove()
 531  
                 {
 532  0
                     removeEntry( before );
 533  0
                 }
 534  
 
 535  
                 public boolean hasNext()
 536  
                 {
 537  0
                     return after != null;
 538  
                 }
 539  
 
 540  
                 public Object next()
 541  
                 {
 542  0
                     before = after;
 543  0
                     after = after._after;
 544  0
                     return before._value;
 545  
                 }
 546  
             };
 547  
         }
 548  
 
 549  
         public int size()
 550  
         {
 551  0
             return _size;
 552  
         }
 553  
 
 554  
         public boolean contains( Object o )
 555  
         {
 556  0
             return containsValue( o );
 557  
         }
 558  
 
 559  
         public void clear()
 560  
         {
 561  0
             FastMap.this.clear();
 562  0
         }
 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  0
         return _entrySet;
 578  
     }
 579  
 
 580  
     private transient EntrySet _entrySet;
 581  
 
 582  0
     private class EntrySet
 583  
         extends AbstractSet
 584  
     {
 585  
         public Iterator iterator()
 586  
         {
 587  0
             return new Iterator()
 588  0
             {
 589  0
                 EntryImpl after = _mapFirst;
 590  
 
 591  
                 EntryImpl before;
 592  
 
 593  
                 public void remove()
 594  
                 {
 595  0
                     removeEntry( before );
 596  0
                 }
 597  
 
 598  
                 public boolean hasNext()
 599  
                 {
 600  0
                     return after != null;
 601  
                 }
 602  
 
 603  
                 public Object next()
 604  
                 {
 605  0
                     before = after;
 606  0
                     after = after._after;
 607  0
                     return before;
 608  
                 }
 609  
             };
 610  
         }
 611  
 
 612  
         public int size()
 613  
         {
 614  0
             return _size;
 615  
         }
 616  
 
 617  
         public boolean contains( Object obj )
 618  
         { // Optimization.
 619  0
             if ( obj instanceof Map.Entry )
 620  
             {
 621  0
                 Map.Entry entry = (Map.Entry) obj;
 622  0
                 Map.Entry mapEntry = getEntry( entry.getKey() );
 623  0
                 return entry.equals( mapEntry );
 624  
             }
 625  
             else
 626  
             {
 627  0
                 return false;
 628  
             }
 629  
         }
 630  
 
 631  
         public boolean remove( Object obj )
 632  
         { // Optimization.
 633  0
             if ( obj instanceof Map.Entry )
 634  
             {
 635  0
                 Map.Entry entry = (Map.Entry) obj;
 636  0
                 EntryImpl mapEntry = (EntryImpl) getEntry( entry.getKey() );
 637  0
                 if ( ( mapEntry != null ) && ( entry.getValue() ).equals( mapEntry._value ) )
 638  
                 {
 639  0
                     removeEntry( mapEntry );
 640  0
                     return true;
 641  
                 }
 642  
             }
 643  0
             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  0
         return _keySet;
 659  
     }
 660  
 
 661  
     private transient KeySet _keySet;
 662  
 
 663  0
     private class KeySet
 664  
         extends AbstractSet
 665  
     {
 666  
         public Iterator iterator()
 667  
         {
 668  0
             return new Iterator()
 669  0
             {
 670  0
                 EntryImpl after = _mapFirst;
 671  
 
 672  
                 EntryImpl before;
 673  
 
 674  
                 public void remove()
 675  
                 {
 676  0
                     removeEntry( before );
 677  0
                 }
 678  
 
 679  
                 public boolean hasNext()
 680  
                 {
 681  0
                     return after != null;
 682  
                 }
 683  
 
 684  
                 public Object next()
 685  
                 {
 686  0
                     before = after;
 687  0
                     after = after._after;
 688  0
                     return before._key;
 689  
                 }
 690  
             };
 691  
         }
 692  
 
 693  
         public int size()
 694  
         {
 695  0
             return _size;
 696  
         }
 697  
 
 698  
         public boolean contains( Object obj )
 699  
         { // Optimization.
 700  0
             return FastMap.this.containsKey( obj );
 701  
         }
 702  
 
 703  
         public boolean remove( Object obj )
 704  
         { // Optimization.
 705  0
             return FastMap.this.remove( obj ) != null;
 706  
         }
 707  
 
 708  
         public void clear()
 709  
         { // Optimization.
 710  0
             FastMap.this.clear();
 711  0
         }
 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  0
         if ( size() > capacity() )
 734  
         {
 735  0
             setCapacity( capacity() * 2 );
 736  
         }
 737  0
     }
 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  0
         int hashCode = key.hashCode();
 750  0
         hashCode += ~( hashCode << 9 );
 751  0
         hashCode ^= ( hashCode >>> 14 );
 752  0
         hashCode += ( hashCode << 4 );
 753  0
         hashCode ^= ( hashCode >>> 10 );
 754  0
         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  0
         EntryImpl entry = _poolFirst;
 766  0
         if ( entry != null )
 767  
         {
 768  0
             _poolFirst = entry._after;
 769  0
             entry._after = null;
 770  
         }
 771  
         else
 772  
         { // Pool empty.
 773  0
             entry = new EntryImpl();
 774  
         }
 775  
 
 776  
         // Setup entry parameters.
 777  0
         entry._key = key;
 778  0
         entry._value = value;
 779  0
         int index = keyHash( key ) & _mask;
 780  0
         entry._index = index;
 781  
 
 782  
         // Connects to bucket.
 783  0
         EntryImpl next = _entries[index];
 784  0
         entry._next = next;
 785  0
         if ( next != null )
 786  
         {
 787  0
             next._previous = entry;
 788  
         }
 789  0
         _entries[index] = entry;
 790  
 
 791  
         // Connects to collection.
 792  0
         if ( _mapLast != null )
 793  
         {
 794  0
             entry._before = _mapLast;
 795  0
             _mapLast._after = entry;
 796  
         }
 797  
         else
 798  
         {
 799  0
             _mapFirst = entry;
 800  
         }
 801  0
         _mapLast = entry;
 802  
 
 803  
         // Updates size.
 804  0
         _size++;
 805  0
         sizeChanged();
 806  0
     }
 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  0
         EntryImpl previous = entry._previous;
 818  0
         EntryImpl next = entry._next;
 819  0
         if ( previous != null )
 820  
         {
 821  0
             previous._next = next;
 822  0
             entry._previous = null;
 823  
         }
 824  
         else
 825  
         { // First in bucket.
 826  0
             _entries[entry._index] = next;
 827  
         }
 828  0
         if ( next != null )
 829  
         {
 830  0
             next._previous = previous;
 831  0
             entry._next = null;
 832  
         } // Else do nothing, no last pointer.
 833  
 
 834  
         // Removes from collection.
 835  0
         EntryImpl before = entry._before;
 836  0
         EntryImpl after = entry._after;
 837  0
         if ( before != null )
 838  
         {
 839  0
             before._after = after;
 840  0
             entry._before = null;
 841  
         }
 842  
         else
 843  
         { // First in collection.
 844  0
             _mapFirst = after;
 845  
         }
 846  0
         if ( after != null )
 847  
         {
 848  0
             after._before = before;
 849  
         }
 850  
         else
 851  
         { // Last in collection.
 852  0
             _mapLast = before;
 853  
         }
 854  
 
 855  
         // Clears value and key.
 856  0
         entry._key = null;
 857  0
         entry._value = null;
 858  
 
 859  
         // Recycles.
 860  0
         entry._after = _poolFirst;
 861  0
         _poolFirst = entry;
 862  
 
 863  
         // Updates size.
 864  0
         _size--;
 865  0
         sizeChanged();
 866  0
     }
 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  0
         int tableLength = 16;
 878  0
         while ( tableLength < capacity )
 879  
         {
 880  0
             tableLength <<= 1;
 881  
         }
 882  
         // Allocates hash table.
 883  0
         _entries = new EntryImpl[tableLength];
 884  0
         _mask = tableLength - 1;
 885  0
         _capacity = capacity;
 886  0
         _size = 0;
 887  
         // Allocates views.
 888  0
         _values = new Values();
 889  0
         _entrySet = new EntrySet();
 890  0
         _keySet = new KeySet();
 891  
         // Resets pointers.
 892  0
         _poolFirst = null;
 893  0
         _mapFirst = null;
 894  0
         _mapLast = null;
 895  
         // Allocates entries.
 896  0
         for ( int i = 0; i < capacity; i++ )
 897  
         {
 898  0
             EntryImpl entry = new EntryImpl();
 899  0
             entry._after = _poolFirst;
 900  0
             _poolFirst = entry;
 901  
         }
 902  0
     }
 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  0
         int capacity = stream.readInt();
 915  0
         initialize( capacity );
 916  0
         int size = stream.readInt();
 917  0
         for ( int i = 0; i < size; i++ )
 918  
         {
 919  0
             Object key = stream.readObject();
 920  0
             Object value = stream.readObject();
 921  0
             addEntry( key, value );
 922  
         }
 923  0
     }
 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  0
         stream.writeInt( _capacity );
 935  0
         stream.writeInt( _size );
 936  0
         int count = 0;
 937  0
         EntryImpl entry = _mapFirst;
 938  0
         while ( entry != null )
 939  
         {
 940  0
             stream.writeObject( entry._key );
 941  0
             stream.writeObject( entry._value );
 942  0
             count++;
 943  0
             entry = entry._after;
 944  
         }
 945  0
         if ( count != _size )
 946  
         {
 947  0
             throw new IOException( "FastMap Corrupted" );
 948  
         }
 949  0
     }
 950  
 
 951  
     /**
 952  
      * This class represents a {@link FastMap} entry.
 953  
      */
 954  0
     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  0
             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  0
             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  0
             V old = _value;
 1022  0
             _value = value;
 1023  0
             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  0
             if ( that instanceof Map.Entry )
 1035  
             {
 1036  0
                 Map.Entry entry = (Map.Entry) that;
 1037  0
                 return ( _key.equals( entry.getKey() ) )
 1038  
                     && ( ( _value != null ) ? _value.equals( entry.getValue() ) : ( entry.getValue() == null ) );
 1039  
             }
 1040  
             else
 1041  
             {
 1042  0
                 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  0
             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  0
             return _key + "=" + _value;
 1064  
         }
 1065  
     }
 1066  
 }