scolebourne 2003/01/18 06:03:28 Modified: collections/src/java/org/apache/commons/collections FastTreeMap.java Log: Improve performance of clear() Update licence Javadoc and formatting Revision Changes Path 1.11 +249 -269 jakarta-commons/collections/src/java/org/apache/commons/collections/FastTreeMap.java Index: FastTreeMap.java =================================================================== RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/FastTreeMap.java,v retrieving revision 1.10 retrieving revision 1.11 diff -u -r1.10 -r1.11 --- FastTreeMap.java 12 Oct 2002 22:15:18 -0000 1.10 +++ FastTreeMap.java 18 Jan 2003 14:03:28 -0000 1.11 @@ -1,13 +1,10 @@ /* * $Header$ - * $Revision$ - * $Date$ - * * ==================================================================== * * The Apache Software License, Version 1.1 * - * Copyright (c) 1999-2002 The Apache Software Foundation. All rights + * Copyright (c) 1999-2003 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without @@ -23,11 +20,11 @@ * distribution. * * 3. The end-user documentation included with the redistribution, if - * any, must include the following acknowlegement: + * any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." - * Alternately, this acknowlegement may appear in the software itself, - * if and wherever such third-party acknowlegements normally appear. + * Alternately, this acknowledgment may appear in the software itself, + * if and wherever such third-party acknowledgments normally appear. * * 4. The names "The Jakarta Project", "Commons", and "Apache Software * Foundation" must not be used to endorse or promote products derived @@ -36,7 +33,7 @@ * * 5. Products derived from this software may not be called "Apache" * nor may "Apache" appear in their names without prior written - * permission of the Apache Group. + * permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES @@ -58,11 +55,8 @@ * <http://www.apache.org/>. * */ - - package org.apache.commons.collections; - import java.util.Collection; import java.util.Comparator; import java.util.ConcurrentModificationException; @@ -72,7 +66,6 @@ import java.util.SortedMap; import java.util.TreeMap; - /** * <p>A customized implementation of <code>java.util.TreeMap</code> designed * to operate in a multithreaded environment where the large majority of @@ -108,85 +101,70 @@ * Double-Checked Locking Idiom Is Broken Declartion</A>.</P> * * @since 1.0 - * @author Craig R. McClanahan * @version $Revision$ $Date$ + * + * @author Craig R. McClanahan + * @author Stephen Colebourne */ - public class FastTreeMap extends TreeMap { + /** + * The underlying map we are managing. + */ + protected TreeMap map = null; - // ----------------------------------------------------------- Constructors + /** + * Are we operating in "fast" mode? + */ + protected boolean fast = false; + // Constructors + // ---------------------------------------------------------------------- + /** * Construct a an empty map. */ public FastTreeMap() { - super(); this.map = new TreeMap(); - } - /** * Construct an empty map with the specified comparator. * - * @param comparator The comparator to use for ordering tree elements + * @param comparator the comparator to use for ordering tree elements */ public FastTreeMap(Comparator comparator) { - super(); this.map = new TreeMap(comparator); - } - /** * Construct a new map with the same mappings as the specified map, * sorted according to the keys's natural order * - * @param map The map whose mappings are to be copied + * @param map the map whose mappings are to be copied */ public FastTreeMap(Map map) { - super(); this.map = new TreeMap(map); - } - /** * Construct a new map with the same mappings as the specified map, * sorted according to the same ordering * - * @param map The map whose mappings are to be copied + * @param map the map whose mappings are to be copied */ public FastTreeMap(SortedMap map) { - super(); this.map = new TreeMap(map); - } - // ----------------------------------------------------- Instance Variables - - - /** - * The underlying map we are managing. - */ - protected TreeMap map = null; - - - // ------------------------------------------------------------- Properties - - - /** - * Are we operating in "fast" mode? - */ - protected boolean fast = false; - + // Property access + // ---------------------------------------------------------------------- /** * Returns true if this map is operating in fast mode. @@ -207,74 +185,68 @@ } - // --------------------------------------------------------- Public Methods - + // Map access + // ---------------------------------------------------------------------- + // These methods can forward straight to the wrapped Map in 'fast' mode. + // (because they are query methods) /** - * Remove all mappings from this map. + * Return the value to which this map maps the specified key. Returns + * <code>null</code> if the map contains no mapping for this key, or if + * there is a mapping with a value of <code>null</code>. Use the + * <code>containsKey()</code> method to disambiguate these cases. + * + * @param key the key whose value is to be returned + * @return the value mapped to that key, or null */ - public void clear() { - + public Object get(Object key) { if (fast) { - synchronized (this) { - TreeMap temp = (TreeMap) map.clone(); - temp.clear(); - map = temp; - } + return (map.get(key)); } else { synchronized (map) { - map.clear(); + return (map.get(key)); } } - } - /** - * Return a shallow copy of this <code>FastTreeMap</code> instance. - * The keys and values themselves are not copied. + * Return the number of key-value mappings in this map. + * + * @return the current size of the map */ - public Object clone() { - - FastTreeMap results = null; + public int size() { if (fast) { - results = new FastTreeMap(map); + return (map.size()); } else { synchronized (map) { - results = new FastTreeMap(map); + return (map.size()); } } - results.setFast(getFast()); - return (results); - } - /** - * Return the comparator used to order this map, or <code>null</code> - * if this map uses its keys' natural order. + * Return <code>true</code> if this map contains no mappings. + * + * @return is the map currently empty */ - public Comparator comparator() { - + public boolean isEmpty() { if (fast) { - return (map.comparator()); + return (map.isEmpty()); } else { synchronized (map) { - return (map.comparator()); + return (map.isEmpty()); } } - } - /** * Return <code>true</code> if this map contains a mapping for the * specified key. * - * @param key Key to be searched for + * @param key the key to be searched for + * @return true if the map contains the key */ public boolean containsKey(Object key) { - if (fast) { return (map.containsKey(key)); } else { @@ -282,18 +254,16 @@ return (map.containsKey(key)); } } - } - /** * Return <code>true</code> if this map contains one or more keys mapping * to the specified value. * - * @param value Value to be searched for + * @param value the value to be searched for + * @return true if the map contains the value */ public boolean containsValue(Object value) { - if (fast) { return (map.containsValue(value)); } else { @@ -301,83 +271,30 @@ return (map.containsValue(value)); } } - } - /** - * Return a collection view of the mappings contained in this map. Each - * element in the returned collection is a <code>Map.Entry</code>. - */ - public Set entrySet() { - return new EntrySet(); - } - - - /** - * Compare the specified object with this list for equality. This - * implementation uses exactly the code that is used to define the - * list equals function in the documentation for the - * <code>Map.equals</code> method. - * - * @param o Object to be compared to this list + * Return the comparator used to order this map, or <code>null</code> + * if this map uses its keys' natural order. + * + * @return the comparator used to order the map, or null if natural order */ - public boolean equals(Object o) { - - // Simple tests that require no synchronization - if (o == this) - return (true); - else if (!(o instanceof Map)) - return (false); - Map mo = (Map) o; - - // Compare the two maps for equality + public Comparator comparator() { if (fast) { - if (mo.size() != map.size()) - return (false); - java.util.Iterator i = map.entrySet().iterator(); - while (i.hasNext()) { - Map.Entry e = (Map.Entry) i.next(); - Object key = e.getKey(); - Object value = e.getValue(); - if (value == null) { - if (!(mo.get(key) == null && mo.containsKey(key))) - return (false); - } else { - if (!value.equals(mo.get(key))) - return (false); - } - } - return (true); + return (map.comparator()); } else { synchronized (map) { - if (mo.size() != map.size()) - return (false); - java.util.Iterator i = map.entrySet().iterator(); - while (i.hasNext()) { - Map.Entry e = (Map.Entry) i.next(); - Object key = e.getKey(); - Object value = e.getValue(); - if (value == null) { - if (!(mo.get(key) == null && mo.containsKey(key))) - return (false); - } else { - if (!value.equals(mo.get(key))) - return (false); - } - } - return (true); + return (map.comparator()); } } - } - /** * Return the first (lowest) key currently in this sorted map. + * + * @return the first key in the map */ public Object firstKey() { - if (fast) { return (map.firstKey()); } else { @@ -385,105 +302,14 @@ return (map.firstKey()); } } - - } - - - /** - * Return the value to which this map maps the specified key. Returns - * <code>null</code> if the map contains no mapping for this key, or if - * there is a mapping with a value of <code>null</code>. Use the - * <code>containsKey()</code> method to disambiguate these cases. - * - * @param key Key whose value is to be returned - */ - public Object get(Object key) { - - if (fast) { - return (map.get(key)); - } else { - synchronized (map) { - return (map.get(key)); - } - } - - } - - - /** - * Return the hash code value for this map. This implementation uses - * exactly the code that is used to define the list hash function in the - * documentation for the <code>Map.hashCode</code> method. - */ - public int hashCode() { - - if (fast) { - int h = 0; - java.util.Iterator i = map.entrySet().iterator(); - while (i.hasNext()) - h += i.next().hashCode(); - return (h); - } else { - synchronized (map) { - int h = 0; - java.util.Iterator i = map.entrySet().iterator(); - while (i.hasNext()) - h += i.next().hashCode(); - return (h); - } - } - } - - /** - * Return a view of the portion of this map whose keys are strictly - * less than the specified key. - * - * @param key Key higher than any in the returned map - */ - public SortedMap headMap(Object key) { - - if (fast) { - return (map.headMap(key)); - } else { - synchronized (map) { - return (map.headMap(key)); - } - } - - } - - - /** - * Test if this list has no elements. - */ - public boolean isEmpty() { - - if (fast) { - return (map.isEmpty()); - } else { - synchronized (map) { - return (map.isEmpty()); - } - } - - } - - - /** - * Return a set view of the keys contained in this map. - */ - public Set keySet() { - return new KeySet(); - } - - /** * Return the last (highest) key currently in this sorted map. + * + * @return the last key in the map */ public Object lastKey() { - if (fast) { return (map.lastKey()); } else { @@ -491,20 +317,25 @@ return (map.lastKey()); } } - } + // Map modification + // ---------------------------------------------------------------------- + // These methods perform special behaviour in 'fast' mode. + // The map is cloned, updated and then assigned back. + // See the comments at the top as to why this won't always work. + /** * Associate the specified value with the specified key in this map. * If the map previously contained a mapping for this key, the old * value is replaced and returned. * - * @param key The key with which the value is to be associated - * @param value The value to be associated with this key + * @param key the key with which the value is to be associated + * @param value the value to be associated with this key + * @return the value previously mapped to the key, or null */ public Object put(Object key, Object value) { - if (fast) { synchronized (this) { TreeMap temp = (TreeMap) map.clone(); @@ -517,18 +348,15 @@ return (map.put(key, value)); } } - } - /** * Copy all of the mappings from the specified map to this one, replacing * any mappings with the same keys. * - * @param in Map whose mappings are to be copied + * @param in the map whose mappings are to be copied */ public void putAll(Map in) { - if (fast) { synchronized (this) { TreeMap temp = (TreeMap) map.clone(); @@ -540,18 +368,16 @@ map.putAll(in); } } - } - /** * Remove any mapping for this key, and return any previously * mapped value. * - * @param key Key whose mapping is to be removed + * @param key the key whose mapping is to be removed + * @return the value removed, or null */ public Object remove(Object key) { - if (fast) { synchronized (this) { TreeMap temp = (TreeMap) map.clone(); @@ -564,35 +390,167 @@ return (map.remove(key)); } } + } + /** + * Remove all mappings from this map. + */ + public void clear() { + if (fast) { + synchronized (this) { + map = new TreeMap(); + } + } else { + synchronized (map) { + map.clear(); + } + } } + + + // Basic object methods + // ---------------------------------------------------------------------- + + /** + * Compare the specified object with this list for equality. This + * implementation uses exactly the code that is used to define the + * list equals function in the documentation for the + * <code>Map.equals</code> method. + * + * @param o the object to be compared to this list + * @return true if the two maps are equal + */ + public boolean equals(Object o) { + // Simple tests that require no synchronization + if (o == this) { + return (true); + } else if (!(o instanceof Map)) { + return (false); + } + Map mo = (Map) o; + // Compare the two maps for equality + if (fast) { + if (mo.size() != map.size()) { + return (false); + } + Iterator i = map.entrySet().iterator(); + while (i.hasNext()) { + Map.Entry e = (Map.Entry) i.next(); + Object key = e.getKey(); + Object value = e.getValue(); + if (value == null) { + if (!(mo.get(key) == null && mo.containsKey(key))) { + return (false); + } + } else { + if (!value.equals(mo.get(key))) { + return (false); + } + } + } + return (true); + } else { + synchronized (map) { + if (mo.size() != map.size()) { + return (false); + } + Iterator i = map.entrySet().iterator(); + while (i.hasNext()) { + Map.Entry e = (Map.Entry) i.next(); + Object key = e.getKey(); + Object value = e.getValue(); + if (value == null) { + if (!(mo.get(key) == null && mo.containsKey(key))) { + return (false); + } + } else { + if (!value.equals(mo.get(key))) { + return (false); + } + } + } + return (true); + } + } + } /** - * Return the number of key-value mappings in this map. + * Return the hash code value for this map. This implementation uses + * exactly the code that is used to define the list hash function in the + * documentation for the <code>Map.hashCode</code> method. + * + * @return a suitable integer hashcode */ - public int size() { - + public int hashCode() { if (fast) { - return (map.size()); + int h = 0; + Iterator i = map.entrySet().iterator(); + while (i.hasNext()) { + h += i.next().hashCode(); + } + return (h); } else { synchronized (map) { - return (map.size()); + int h = 0; + Iterator i = map.entrySet().iterator(); + while (i.hasNext()) { + h += i.next().hashCode(); + } + return (h); } } + } + /** + * Return a shallow copy of this <code>FastTreeMap</code> instance. + * The keys and values themselves are not copied. + * + * @return a clone of this map + */ + public Object clone() { + FastTreeMap results = null; + if (fast) { + results = new FastTreeMap(map); + } else { + synchronized (map) { + results = new FastTreeMap(map); + } + } + results.setFast(getFast()); + return (results); } + // Sub map views + // ---------------------------------------------------------------------- + + /** + * Return a view of the portion of this map whose keys are strictly + * less than the specified key. + * + * @param key Key higher than any in the returned map + * @return a head map + */ + public SortedMap headMap(Object key) { + if (fast) { + return (map.headMap(key)); + } else { + synchronized (map) { + return (map.headMap(key)); + } + } + } + /** * Return a view of the portion of this map whose keys are in the * range fromKey (inclusive) to toKey (exclusive). * * @param fromKey Lower limit of keys for the returned map * @param toKey Upper limit of keys for the returned map + * @return a sub map */ public SortedMap subMap(Object fromKey, Object toKey) { - if (fast) { return (map.subMap(fromKey, toKey)); } else { @@ -600,18 +558,16 @@ return (map.subMap(fromKey, toKey)); } } - } - /** * Return a view of the portion of this map whose keys are greater than * or equal to the specified key. * * @param key Key less than or equal to any in the returned map + * @return a tail map */ public SortedMap tailMap(Object key) { - if (fast) { return (map.tailMap(key)); } else { @@ -619,9 +575,26 @@ return (map.tailMap(key)); } } + } + + // Map views + // ---------------------------------------------------------------------- + + /** + * Return a collection view of the mappings contained in this map. Each + * element in the returned collection is a <code>Map.Entry</code>. + */ + public Set entrySet() { + return new EntrySet(); } + /** + * Return a set view of the keys contained in this map. + */ + public Set keySet() { + return new KeySet(); + } /** * Return a collection view of the values contained in this map. @@ -630,8 +603,12 @@ return new Values(); } + // Map view inner classes + // ---------------------------------------------------------------------- - + /** + * Abstract collection implementation shared by ketSet(), values() and entrySet(). + */ private abstract class CollectionView implements Collection { public CollectionView() { @@ -644,9 +621,7 @@ public void clear() { if (fast) { synchronized (FastTreeMap.this) { - TreeMap temp = (TreeMap) map.clone(); - get(temp).clear(); - map = temp; + map = new TreeMap(); } } else { synchronized (map) { @@ -842,7 +817,9 @@ } } - + /** + * Set implementation over the keys of the FastTreeMap + */ private class KeySet extends CollectionView implements Set { protected Collection get(Map map) { @@ -855,7 +832,9 @@ } - + /** + * Collection implementation over the values of the FastTreeMap + */ private class Values extends CollectionView { protected Collection get(Map map) { @@ -867,7 +846,9 @@ } } - + /** + * Set implementation over the entries of the FastTreeMap + */ private class EntrySet extends CollectionView implements Set { protected Collection get(Map map) { @@ -880,6 +861,5 @@ } } - }
-- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>