Home » commons-beanutils-1.8.3-src » org.apache.commons » collections » [javadoc | source]

    1   /*
    2    * Licensed to the Apache Software Foundation (ASF) under one or more
    3    * contributor license agreements.  See the NOTICE file distributed with
    4    * this work for additional information regarding copyright ownership.
    5    * The ASF licenses this file to You under the Apache License, Version 2.0
    6    * (the "License"); you may not use this file except in compliance with
    7    * the License.  You may obtain a copy of the License at
    8    *
    9    *      http://www.apache.org/licenses/LICENSE-2.0
   10    *
   11    * Unless required by applicable law or agreed to in writing, software
   12    * distributed under the License is distributed on an "AS IS" BASIS,
   13    * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   14    * See the License for the specific language governing permissions and
   15    * limitations under the License.
   16    */
   17   package org.apache.commons.collections;
   18   
   19   import java.util.Collection;
   20   import java.util.ConcurrentModificationException;
   21   import java.util.HashMap;
   22   import java.util.Iterator;
   23   import java.util.Map;
   24   import java.util.Set;
   25   
   26   /**
   27    * <p>A customized implementation of <code>java.util.HashMap</code> designed
   28    * to operate in a multithreaded environment where the large majority of
   29    * method calls are read-only, instead of structural changes.  When operating
   30    * in "fast" mode, read calls are non-synchronized and write calls perform the
   31    * following steps:</p>
   32    * <ul>
   33    * <li>Clone the existing collection
   34    * <li>Perform the modification on the clone
   35    * <li>Replace the existing collection with the (modified) clone
   36    * </ul>
   37    * <p>When first created, objects of this class default to "slow" mode, where
   38    * all accesses of any type are synchronized but no cloning takes place.  This
   39    * is appropriate for initially populating the collection, followed by a switch
   40    * to "fast" mode (by calling <code>setFast(true)</code>) after initialization
   41    * is complete.</p>
   42    *
   43    * <p><strong>NOTE</strong>: If you are creating and accessing a
   44    * <code>HashMap</code> only within a single thread, you should use
   45    * <code>java.util.HashMap</code> directly (with no synchronization), for
   46    * maximum performance.</p>
   47    *
   48    * <p><strong>NOTE</strong>: <i>This class is not cross-platform.  
   49    * Using it may cause unexpected failures on some architectures.</i>
   50    * It suffers from the same problems as the double-checked locking idiom.  
   51    * In particular, the instruction that clones the internal collection and the 
   52    * instruction that sets the internal reference to the clone can be executed 
   53    * or perceived out-of-order.  This means that any read operation might fail 
   54    * unexpectedly, as it may be reading the state of the internal collection
   55    * before the internal collection is fully formed.
   56    * For more information on the double-checked locking idiom, see the
   57    * <a href="http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html">
   58    * Double-Checked Locking Idiom Is Broken Declaration</a>.</p>
   59    *
   60    * @since Commons Collections 1.0
   61    * @version $Revision: 555845 $ $Date: 2007-07-13 03:52:05 +0100 (Fri, 13 Jul 2007) $
   62    * 
   63    * @author Craig R. McClanahan
   64    * @author Stephen Colebourne
   65    */
   66   public class FastHashMap extends HashMap {
   67   
   68       /**
   69        * The underlying map we are managing.
   70        */
   71       protected HashMap map = null;
   72   
   73       /**
   74        * Are we currently operating in "fast" mode?
   75        */
   76       protected boolean fast = false;
   77   
   78       // Constructors
   79       // ----------------------------------------------------------------------
   80   
   81       /**
   82        * Construct an empty map.
   83        */
   84       public FastHashMap() {
   85           super();
   86           this.map = new HashMap();
   87       }
   88   
   89       /**
   90        * Construct an empty map with the specified capacity.
   91        *
   92        * @param capacity  the initial capacity of the empty map
   93        */
   94       public FastHashMap(int capacity) {
   95           super();
   96           this.map = new HashMap(capacity);
   97       }
   98   
   99       /**
  100        * Construct an empty map with the specified capacity and load factor.
  101        *
  102        * @param capacity  the initial capacity of the empty map
  103        * @param factor  the load factor of the new map
  104        */
  105       public FastHashMap(int capacity, float factor) {
  106           super();
  107           this.map = new HashMap(capacity, factor);
  108       }
  109   
  110       /**
  111        * Construct a new map with the same mappings as the specified map.
  112        *
  113        * @param map  the map whose mappings are to be copied
  114        */
  115       public FastHashMap(Map map) {
  116           super();
  117           this.map = new HashMap(map);
  118       }
  119   
  120   
  121       // Property access
  122       // ----------------------------------------------------------------------
  123   
  124       /**
  125        *  Returns true if this map is operating in fast mode.
  126        *
  127        *  @return true if this map is operating in fast mode
  128        */
  129       public boolean getFast() {
  130           return (this.fast);
  131       }
  132   
  133       /**
  134        *  Sets whether this map is operating in fast mode.
  135        *
  136        *  @param fast true if this map should operate in fast mode
  137        */
  138       public void setFast(boolean fast) {
  139           this.fast = fast;
  140       }
  141   
  142   
  143       // Map access
  144       // ----------------------------------------------------------------------
  145       // These methods can forward straight to the wrapped Map in 'fast' mode.
  146       // (because they are query methods)
  147   
  148       /**
  149        * Return the value to which this map maps the specified key.  Returns
  150        * <code>null</code> if the map contains no mapping for this key, or if
  151        * there is a mapping with a value of <code>null</code>.  Use the
  152        * <code>containsKey()</code> method to disambiguate these cases.
  153        *
  154        * @param key  the key whose value is to be returned
  155        * @return the value mapped to that key, or null
  156        */
  157       public Object get(Object key) {
  158           if (fast) {
  159               return (map.get(key));
  160           } else {
  161               synchronized (map) {
  162                   return (map.get(key));
  163               }
  164           }
  165       }
  166   
  167       /**
  168        * Return the number of key-value mappings in this map.
  169        * 
  170        * @return the current size of the map
  171        */
  172       public int size() {
  173           if (fast) {
  174               return (map.size());
  175           } else {
  176               synchronized (map) {
  177                   return (map.size());
  178               }
  179           }
  180       }
  181   
  182       /**
  183        * Return <code>true</code> if this map contains no mappings.
  184        * 
  185        * @return is the map currently empty
  186        */
  187       public boolean isEmpty() {
  188           if (fast) {
  189               return (map.isEmpty());
  190           } else {
  191               synchronized (map) {
  192                   return (map.isEmpty());
  193               }
  194           }
  195       }
  196   
  197       /**
  198        * Return <code>true</code> if this map contains a mapping for the
  199        * specified key.
  200        *
  201        * @param key  the key to be searched for
  202        * @return true if the map contains the key
  203        */
  204       public boolean containsKey(Object key) {
  205           if (fast) {
  206               return (map.containsKey(key));
  207           } else {
  208               synchronized (map) {
  209                   return (map.containsKey(key));
  210               }
  211           }
  212       }
  213   
  214       /**
  215        * Return <code>true</code> if this map contains one or more keys mapping
  216        * to the specified value.
  217        *
  218        * @param value  the value to be searched for
  219        * @return true if the map contains the value
  220        */
  221       public boolean containsValue(Object value) {
  222           if (fast) {
  223               return (map.containsValue(value));
  224           } else {
  225               synchronized (map) {
  226                   return (map.containsValue(value));
  227               }
  228           }
  229       }
  230   
  231       // Map modification
  232       // ----------------------------------------------------------------------
  233       // These methods perform special behaviour in 'fast' mode.
  234       // The map is cloned, updated and then assigned back.
  235       // See the comments at the top as to why this won't always work.
  236   
  237       /**
  238        * Associate the specified value with the specified key in this map.
  239        * If the map previously contained a mapping for this key, the old
  240        * value is replaced and returned.
  241        *
  242        * @param key  the key with which the value is to be associated
  243        * @param value  the value to be associated with this key
  244        * @return the value previously mapped to the key, or null
  245        */
  246       public Object put(Object key, Object value) {
  247           if (fast) {
  248               synchronized (this) {
  249                   HashMap temp = (HashMap) map.clone();
  250                   Object result = temp.put(key, value);
  251                   map = temp;
  252                   return (result);
  253               }
  254           } else {
  255               synchronized (map) {
  256                   return (map.put(key, value));
  257               }
  258           }
  259       }
  260   
  261       /**
  262        * Copy all of the mappings from the specified map to this one, replacing
  263        * any mappings with the same keys.
  264        *
  265        * @param in  the map whose mappings are to be copied
  266        */
  267       public void putAll(Map in) {
  268           if (fast) {
  269               synchronized (this) {
  270                   HashMap temp = (HashMap) map.clone();
  271                   temp.putAll(in);
  272                   map = temp;
  273               }
  274           } else {
  275               synchronized (map) {
  276                   map.putAll(in);
  277               }
  278           }
  279       }
  280   
  281       /**
  282        * Remove any mapping for this key, and return any previously
  283        * mapped value.
  284        *
  285        * @param key  the key whose mapping is to be removed
  286        * @return the value removed, or null
  287        */
  288       public Object remove(Object key) {
  289           if (fast) {
  290               synchronized (this) {
  291                   HashMap temp = (HashMap) map.clone();
  292                   Object result = temp.remove(key);
  293                   map = temp;
  294                   return (result);
  295               }
  296           } else {
  297               synchronized (map) {
  298                   return (map.remove(key));
  299               }
  300           }
  301       }
  302   
  303       /**
  304        * Remove all mappings from this map.
  305        */
  306       public void clear() {
  307           if (fast) {
  308               synchronized (this) {
  309                   map = new HashMap();
  310               }
  311           } else {
  312               synchronized (map) {
  313                   map.clear();
  314               }
  315           }
  316       }
  317   
  318       // Basic object methods
  319       // ----------------------------------------------------------------------
  320       
  321       /**
  322        * Compare the specified object with this list for equality.  This
  323        * implementation uses exactly the code that is used to define the
  324        * list equals function in the documentation for the
  325        * <code>Map.equals</code> method.
  326        *
  327        * @param o  the object to be compared to this list
  328        * @return true if the two maps are equal
  329        */
  330       public boolean equals(Object o) {
  331           // Simple tests that require no synchronization
  332           if (o == this) {
  333               return (true);
  334           } else if (!(o instanceof Map)) {
  335               return (false);
  336           }
  337           Map mo = (Map) o;
  338   
  339           // Compare the two maps for equality
  340           if (fast) {
  341               if (mo.size() != map.size()) {
  342                   return (false);
  343               }
  344               Iterator i = map.entrySet().iterator();
  345               while (i.hasNext()) {
  346                   Map.Entry e = (Map.Entry) i.next();
  347                   Object key = e.getKey();
  348                   Object value = e.getValue();
  349                   if (value == null) {
  350                       if (!(mo.get(key) == null && mo.containsKey(key))) {
  351                           return (false);
  352                       }
  353                   } else {
  354                       if (!value.equals(mo.get(key))) {
  355                           return (false);
  356                       }
  357                   }
  358               }
  359               return (true);
  360               
  361           } else {
  362               synchronized (map) {
  363                   if (mo.size() != map.size()) {
  364                       return (false);
  365                   }
  366                   Iterator i = map.entrySet().iterator();
  367                   while (i.hasNext()) {
  368                       Map.Entry e = (Map.Entry) i.next();
  369                       Object key = e.getKey();
  370                       Object value = e.getValue();
  371                       if (value == null) {
  372                           if (!(mo.get(key) == null && mo.containsKey(key))) {
  373                               return (false);
  374                           }
  375                       } else {
  376                           if (!value.equals(mo.get(key))) {
  377                               return (false);
  378                           }
  379                       }
  380                   }
  381                   return (true);
  382               }
  383           }
  384       }
  385   
  386       /**
  387        * Return the hash code value for this map.  This implementation uses
  388        * exactly the code that is used to define the list hash function in the
  389        * documentation for the <code>Map.hashCode</code> method.
  390        * 
  391        * @return suitable integer hash code
  392        */
  393       public int hashCode() {
  394           if (fast) {
  395               int h = 0;
  396               Iterator i = map.entrySet().iterator();
  397               while (i.hasNext()) {
  398                   h += i.next().hashCode();
  399               }
  400               return (h);
  401           } else {
  402               synchronized (map) {
  403                   int h = 0;
  404                   Iterator i = map.entrySet().iterator();
  405                   while (i.hasNext()) {
  406                       h += i.next().hashCode();
  407                   }
  408                   return (h);
  409               }
  410           }
  411       }
  412   
  413       /**
  414        * Return a shallow copy of this <code>FastHashMap</code> instance.
  415        * The keys and values themselves are not copied.
  416        * 
  417        * @return a clone of this map
  418        */
  419       public Object clone() {
  420           FastHashMap results = null;
  421           if (fast) {
  422               results = new FastHashMap(map);
  423           } else {
  424               synchronized (map) {
  425                   results = new FastHashMap(map);
  426               }
  427           }
  428           results.setFast(getFast());
  429           return (results);
  430       }
  431   
  432       // Map views
  433       // ----------------------------------------------------------------------
  434       
  435       /**
  436        * Return a collection view of the mappings contained in this map.  Each
  437        * element in the returned collection is a <code>Map.Entry</code>.
  438        * @return the set of map Map entries
  439        */
  440       public Set entrySet() {
  441           return new EntrySet();
  442       }
  443   
  444       /**
  445        * Return a set view of the keys contained in this map.
  446        * @return the set of the Map's keys
  447        */
  448       public Set keySet() {
  449           return new KeySet();
  450       }
  451   
  452       /**
  453        * Return a collection view of the values contained in this map.
  454        * @return the set of the Map's values
  455        */
  456       public Collection values() {
  457           return new Values();
  458       }
  459   
  460       // Map view inner classes
  461       // ----------------------------------------------------------------------
  462   
  463       /**
  464        * Abstract collection implementation shared by keySet(), values() and entrySet().
  465        */
  466       private abstract class CollectionView implements Collection {
  467   
  468           public CollectionView() {
  469           }
  470   
  471           protected abstract Collection get(Map map);
  472           protected abstract Object iteratorNext(Map.Entry entry);
  473   
  474   
  475           public void clear() {
  476               if (fast) {
  477                   synchronized (FastHashMap.this) {
  478                       map = new HashMap();
  479                   }
  480               } else {
  481                   synchronized (map) {
  482                       get(map).clear();
  483                   }
  484               }
  485           }
  486   
  487           public boolean remove(Object o) {
  488               if (fast) {
  489                   synchronized (FastHashMap.this) {
  490                       HashMap temp = (HashMap) map.clone();
  491                       boolean r = get(temp).remove(o);
  492                       map = temp;
  493                       return r;
  494                   }
  495               } else {
  496                   synchronized (map) {
  497                       return get(map).remove(o);
  498                   }
  499               }
  500           }
  501   
  502           public boolean removeAll(Collection o) {
  503               if (fast) {
  504                   synchronized (FastHashMap.this) {
  505                       HashMap temp = (HashMap) map.clone();
  506                       boolean r = get(temp).removeAll(o);
  507                       map = temp;
  508                       return r;
  509                   }
  510               } else {
  511                   synchronized (map) {
  512                       return get(map).removeAll(o);
  513                   }
  514               }
  515           }
  516   
  517           public boolean retainAll(Collection o) {
  518               if (fast) {
  519                   synchronized (FastHashMap.this) {
  520                       HashMap temp = (HashMap) map.clone();
  521                       boolean r = get(temp).retainAll(o);
  522                       map = temp;
  523                       return r;
  524                   }
  525               } else {
  526                   synchronized (map) {
  527                       return get(map).retainAll(o);
  528                   }
  529               }
  530           }
  531   
  532           public int size() {
  533               if (fast) {
  534                   return get(map).size();
  535               } else {
  536                   synchronized (map) {
  537                       return get(map).size();
  538                   }
  539               }
  540           }
  541   
  542   
  543           public boolean isEmpty() {
  544               if (fast) {
  545                   return get(map).isEmpty();
  546               } else {
  547                   synchronized (map) {
  548                       return get(map).isEmpty();
  549                   }
  550               }
  551           }
  552   
  553           public boolean contains(Object o) {
  554               if (fast) {
  555                   return get(map).contains(o);
  556               } else {
  557                   synchronized (map) {
  558                       return get(map).contains(o);
  559                   }
  560               }
  561           }
  562   
  563           public boolean containsAll(Collection o) {
  564               if (fast) {
  565                   return get(map).containsAll(o);
  566               } else {
  567                   synchronized (map) {
  568                       return get(map).containsAll(o);
  569                   }
  570               }
  571           }
  572   
  573           public Object[] toArray(Object[] o) {
  574               if (fast) {
  575                   return get(map).toArray(o);
  576               } else {
  577                   synchronized (map) {
  578                       return get(map).toArray(o);
  579                   }
  580               }
  581           }
  582   
  583           public Object[] toArray() {
  584               if (fast) {
  585                   return get(map).toArray();
  586               } else {
  587                   synchronized (map) {
  588                       return get(map).toArray();
  589                   }
  590               }
  591           }
  592   
  593   
  594           public boolean equals(Object o) {
  595               if (o == this) {
  596                   return true;
  597               }
  598               if (fast) {
  599                   return get(map).equals(o);
  600               } else {
  601                   synchronized (map) {
  602                       return get(map).equals(o);
  603                   }
  604               }
  605           }
  606   
  607           public int hashCode() {
  608               if (fast) {
  609                   return get(map).hashCode();
  610               } else {
  611                   synchronized (map) {
  612                       return get(map).hashCode();
  613                   }
  614               }
  615           }
  616   
  617           public boolean add(Object o) {
  618               throw new UnsupportedOperationException();
  619           }
  620   
  621           public boolean addAll(Collection c) {
  622               throw new UnsupportedOperationException();
  623           }
  624   
  625           public Iterator iterator() {
  626               return new CollectionViewIterator();
  627           }
  628   
  629           private class CollectionViewIterator implements Iterator {
  630   
  631               private Map expected;
  632               private Map.Entry lastReturned = null;
  633               private Iterator iterator;
  634   
  635               public CollectionViewIterator() {
  636                   this.expected = map;
  637                   this.iterator = expected.entrySet().iterator();
  638               }
  639    
  640               public boolean hasNext() {
  641                   if (expected != map) {
  642                       throw new ConcurrentModificationException();
  643                   }
  644                   return iterator.hasNext();
  645               }
  646   
  647               public Object next() {
  648                   if (expected != map) {
  649                       throw new ConcurrentModificationException();
  650                   }
  651                   lastReturned = (Map.Entry)iterator.next();
  652                   return iteratorNext(lastReturned);
  653               }
  654   
  655               public void remove() {
  656                   if (lastReturned == null) {
  657                       throw new IllegalStateException();
  658                   }
  659                   if (fast) {
  660                       synchronized (FastHashMap.this) {
  661                           if (expected != map) {
  662                               throw new ConcurrentModificationException();
  663                           }
  664                           FastHashMap.this.remove(lastReturned.getKey());
  665                           lastReturned = null;
  666                           expected = map;
  667                       }
  668                   } else {
  669                       iterator.remove();
  670                       lastReturned = null;
  671                   }
  672               }
  673           }
  674       }
  675   
  676       /**
  677        * Set implementation over the keys of the FastHashMap
  678        */
  679       private class KeySet extends CollectionView implements Set {
  680       
  681           protected Collection get(Map map) {
  682               return map.keySet();
  683           }
  684       
  685           protected Object iteratorNext(Map.Entry entry) {
  686               return entry.getKey();
  687           }
  688       
  689       }
  690       
  691       /**
  692        * Collection implementation over the values of the FastHashMap
  693        */
  694       private class Values extends CollectionView {
  695       
  696           protected Collection get(Map map) {
  697               return map.values();
  698           }
  699       
  700           protected Object iteratorNext(Map.Entry entry) {
  701               return entry.getValue();
  702           }
  703       }
  704       
  705       /**
  706        * Set implementation over the entries of the FastHashMap
  707        */
  708       private class EntrySet extends CollectionView implements Set {
  709       
  710           protected Collection get(Map map) {
  711               return map.entrySet();
  712           }
  713       
  714           protected Object iteratorNext(Map.Entry entry) {
  715               return entry;
  716           }
  717       
  718       }
  719   
  720   }

Home » commons-beanutils-1.8.3-src » org.apache.commons » collections » [javadoc | source]