You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by sc...@apache.org on 2003/01/18 15:03:28 UTC
cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections FastTreeMap.java
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: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>