--- jsr166/src/jsr166x/ConcurrentSkipListMap.java 2004/08/11 10:58:15 1.1
+++ jsr166/src/jsr166x/ConcurrentSkipListMap.java 2004/10/16 14:49:45 1.4
@@ -11,11 +11,11 @@ import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
/**
- * A scalable {@link SortedMap} and {@link ConcurrentMap}
- * implementation. This class maintains a map in ascending key order,
- * sorted according to the natural order for the key's class
- * (see {@link Comparable}), or by the {@link Comparator} provided at
- * creation time, depending on which constructor is used.
+ * A scalable {@link ConcurrentNavigableMap} implementation. This
+ * class maintains a map in ascending key order, sorted according to
+ * the natural order for the key's class (see {@link
+ * Comparable}), or by the {@link Comparator} provided at creation
+ * time, depending on which constructor is used.
*
* This class implements a concurrent variant of SkipLists providing
@@ -29,35 +29,22 @@ import java.util.concurrent.atomic.*;
* ConcurrentModificationException}, and may proceed concurrently with
* other operations.
*
- *
This class provides extended SortedMap methods
- * returning Map.Entry key-value pairs that may be useful in
- * searching for closest matches. Methods lowerEntry,
- * floorEntry, ceilingEntry, and
- * higherEntry return entries associated with keys
- * respectively less, less than or equal, greater than or equal, and
- * greater than a given key, returning null if there is no such key.
- * These methods are designed for locating, not traversing entries. To
- * traverse, use view iterators and/or submap. The class
- * additionally supports method removeFirstEntry that
- * atomically returns and removes the first mapping (i.e., with least
- * key), if one exists.
- *
- *
All Map.Entry pairs returned by methods in this class
+ *
All Map.Entry pairs returned by methods in this class
* and its views represent snapshots of mappings at the time they were
* produced. They do not support the Entry.setValue
* method. (Note however that it is possible to change mappings in the
* associated map using put, putIfAbsent, or
* replace, depending on exactly which effect you need.)
*
- *
The {@link ConcurrentSkipListSubMap} objects returned by methods
- * submap, headMap, and tailMap support the
- * same extended set of operations as this class, but operate on their
- * designated subrange of mappings.
- *
*
Beware that, unlike in most collections, the size
* method is not a constant-time operation. Because of the
* asynchronous nature of these maps, determining the current number
- * of elements requires a traversal of the elements.
+ * of elements requires a traversal of the elements. Additionally,
+ * the bulk operations putAll, equals, and
+ * clear are not guaranteed to be performed
+ * atomically. For example, an iterator operating concurrently with a
+ * putAll operation might view only some of the added
+ * elements.
*
*
This class and its views and iterators implement all of the
* optional methods of the {@link Map} and {@link Iterator}
@@ -71,8 +58,7 @@ import java.util.concurrent.atomic.*;
* @param the type of mapped values
*/
public class ConcurrentSkipListMap extends AbstractMap
- implements ConcurrentMap,
- SortedMap,
+ implements ConcurrentNavigableMap,
Cloneable,
java.io.Serializable {
/*
@@ -87,7 +73,7 @@ public class ConcurrentSkipListMap
* possible list with 2 levels of index:
*
* Head nodes Index nodes
- * +-+ right +-+ +-+
+ * +-+ right +-+ +-+
* |2|---------------->| |--------------------->| |->null
* +-+ +-+ +-+
* | down | |
@@ -95,21 +81,22 @@ public class ConcurrentSkipListMap
* +-+ +-+ +-+ +-+ +-+ +-+
* |1|----------->| |->| |------>| |----------->| |------>| |->null
* +-+ +-+ +-+ +-+ +-+ +-+
- * | | | | | |
- * v Nodes v v v v v
+ * v | | | | |
+ * Nodes next v v v v v
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
*
* The base lists use a variant of the HM linked ordered set
- * algorithm (See Tim Harris, "A pragmatic implementation of
+ * algorithm. See Tim Harris, "A pragmatic implementation of
* non-blocking linked lists"
* http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged
* Michael "High Performance Dynamic Lock-Free Hash Tables and
* List-Based Sets"
- * http://www.research.ibm.com/people/m/michael/pubs.htm). The
- * basic idea in these lists is to mark pointers of deleted nodes
- * when deleting, and when traversing to keep track of triples
+ * http://www.research.ibm.com/people/m/michael/pubs.htm. The
+ * basic idea in these lists is to mark the "next" pointers of
+ * deleted nodes when deleting to avoid conflicts with concurrent
+ * insertions, and when traversing to keep track of triples
* (predecessor, node, successor) in order to detect when and how
* to unlink these deleted nodes.
*
@@ -136,7 +123,8 @@ public class ConcurrentSkipListMap
* space by defining marker nodes not to have key/value fields, it
* isn't worth the extra type-testing overhead. The deletion
* markers are rarely encountered during traversal and are
- * normally quickly garbage collected.
+ * normally quickly garbage collected. (Note that this technique
+ * would not work well in systems without garbage collection.)
*
* In addition to using deletion markers, the lists also use
* nullness of value fields to indicate deletion, in a style
@@ -276,8 +264,9 @@ public class ConcurrentSkipListMap
*
* For explanation of algorithms sharing at least a couple of
* features with this one, see Mikhail Fomitchev's thesis
- * (http://www.cs.yorku.ca/~mikhail/) and Keir Fraser's thesis
- * (http://www.cl.cam.ac.uk/users/kaf24/).
+ * (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
+ * (http://www.cl.cam.ac.uk/users/kaf24/), and papers by
+ * Håkan Sundell (http://www.cs.chalmers.se/~phs/).
*
* Given the use of tree-like index nodes, you might wonder why
* this doesn't use some kind of search tree instead, which would
@@ -512,16 +501,7 @@ public class ConcurrentSkipListMap
volatile Index right;
/**
- * Creates index node with unknown right pointer
- */
- Index(Node node, Index down) {
- this.node = node;
- this.key = node.key;
- this.down = down;
- }
-
- /**
- * Creates index node with known right pointer
+ * Creates index node with given values
*/
Index(Node node, Index down, Index right) {
this.node = node;
@@ -583,8 +563,7 @@ public class ConcurrentSkipListMap
*/
static final class HeadIndex extends Index {
final int level;
- HeadIndex(Node node, Index down, Index right,
- int level) {
+ HeadIndex(Node node, Index down, Index right, int level) {
super(node, down, right);
this.level = level;
}
@@ -724,7 +703,8 @@ public class ConcurrentSkipListMap
/**
* Return true if given key greater than or equal to least and
- * strictly less than fence. Needed mainly in submap operations.
+ * strictly less than fence, bypassing either test if least or
+ * fence oare null. Needed mainly in submap operations.
*/
boolean inHalfOpenRange(K key, K least, K fence) {
if (key == null)
@@ -814,8 +794,8 @@ public class ConcurrentSkipListMap
* links, and so will retry anyway.
*
* The traversal loops in doPut, doRemove, and findNear all
- * include with the same three kinds of checks. And specialized
- * versions appear in doRemoveFirstEntry, findFirst, and
+ * include the same three kinds of checks. And specialized
+ * versions appear in doRemoveFirst, doRemoveLast, findFirst, and
* findLast. They can't easily share code because each uses the
* reads of fields held in locals occurring in the orders they
* were performed.
@@ -910,8 +890,11 @@ public class ConcurrentSkipListMap
* @return the value, or null if absent
*/
private V getUsingFindNode(Comparable key) {
- // Loop needed here and elsewhere to protect against value
- // field going null just as it is about to be returned.
+ /*
+ * Loop needed here and elsewhere in case value field goes
+ * null just as it is about to be returned, in which case we
+ * lost a race with a deletion, so must retry.
+ */
for (;;) {
Node n = findNode(key);
if (n == null)
@@ -1009,7 +992,7 @@ public class ConcurrentSkipListMap
if (level <= max) {
Index idx = null;
for (int i = 1; i <= level; ++i)
- idx = new Index(z, idx);
+ idx = new Index(z, idx, null);
addIndex(idx, h, level);
} else { // Add a new level
@@ -1025,7 +1008,7 @@ public class ConcurrentSkipListMap
Index[] idxs = (Index[])new Index[level+1];
Index idx = null;
for (int i = 1; i <= level; ++i)
- idxs[i] = idx = new Index(z, idx);
+ idxs[i] = idx = new Index(z, idx, null);
HeadIndex oldh;
int k;
@@ -1175,8 +1158,8 @@ public class ConcurrentSkipListMap
* Possibly reduce head level if it has no nodes. This method can
* (rarely) make mistakes, in which case levels can disappear even
* though they are about to contain index nodes. This impacts
- * performance, not correctness. To minimize mistakes and also to
- * reduce hysteresis, the level is reduced by one only if the
+ * performance, not correctness. To minimize mistakes as well as
+ * to reduce hysteresis, the level is reduced by one only if the
* topmost three levels look empty. Also, if the removed level
* looks non-empty after CAS, we try to change it back quick
* before anyone notices our mistake! (This trick works pretty
@@ -1207,15 +1190,14 @@ public class ConcurrentSkipListMap
}
- /* ---------------- Positional operations -------------- */
+ /* ---------------- Finding and removing first element -------------- */
/**
- * Specialized version of find to get first valid node
+ * Specialized variant of findNode to get first valid node
* @return first node or null if empty
*/
Node findFirst() {
for (;;) {
- // cheaper checks because we know head is never deleted
Node b = head.node;
Node n = b.next;
if (n == null)
@@ -1227,40 +1209,12 @@ public class ConcurrentSkipListMap
}
/**
- * Remove first entry; return its key or null if empty.
- * Used by ConcurrentSkipListSet
- */
- K removeFirstKey() {
- for (;;) {
- Node b = head.node;
- Node n = b.next;
- if (n == null)
- return null;
- Node f = n.next;
- if (n != b.next)
- continue;
- Object v = n.value;
- if (v == null) {
- n.helpDelete(b, f);
- continue;
- }
- if (!n.casValue(v, null))
- continue;
- if (!n.appendMarker(f) || !b.casNext(n, f))
- findFirst(); // retry
- clearIndexToFirst();
- return n.key;
- }
- }
-
- /**
- * Remove first entry; return SnapshotEntry or null if empty.
+ * Remove first entry; return either its key or a snapshot.
+ * @param keyOnly if true return key, else return SnapshotEntry
+ * (This is a little ugly, but avoids code duplication.)
+ * @return null if empty, first key if keyOnly true, else key,value entry
*/
- private SnapshotEntry doRemoveFirstEntry() {
- /*
- * This must be mostly duplicated from removeFirstKey because we
- * need to save the last value read before it is nulled out
- */
+ Object doRemoveFirst(boolean keyOnly) {
for (;;) {
Node b = head.node;
Node n = b.next;
@@ -1279,13 +1233,14 @@ public class ConcurrentSkipListMap
if (!n.appendMarker(f) || !b.casNext(n, f))
findFirst(); // retry
clearIndexToFirst();
- return new SnapshotEntry(n.key, (V)v);
+ K key = n.key;
+ return (keyOnly)? key : new SnapshotEntry(key, (V)v);
}
}
/**
* Clear out index nodes associated with deleted first entry.
- * Needed by removeFirstKey and removeFirstEntry
+ * Needed by doRemoveFirst
*/
private void clearIndexToFirst() {
for (;;) {
@@ -1303,6 +1258,8 @@ public class ConcurrentSkipListMap
}
}
+ /* ---------------- Finding and removing last element -------------- */
+
/**
* Specialized version of find to get last valid node
* @return last node or null if empty
@@ -1349,6 +1306,85 @@ public class ConcurrentSkipListMap
}
}
+
+ /**
+ * Specialized version of doRemove for last entry.
+ * @param keyOnly if true return key, else return SnapshotEntry
+ * @return null if empty, last key if keyOnly true, else key,value entry
+ */
+ Object doRemoveLast(boolean keyOnly) {
+ for (;;) {
+ Node b = findPredecessorOfLast();
+ Node n = b.next;
+ if (n == null) {
+ if (b.isBaseHeader()) // empty
+ return null;
+ else
+ continue; // all b's successors are deleted; retry
+ }
+ for (;;) {
+ Node f = n.next;
+ if (n != b.next) // inconsistent read
+ break;
+ Object v = n.value;
+ if (v == null) { // n is deleted
+ n.helpDelete(b, f);
+ break;
+ }
+ if (v == n || b.value == null) // b is deleted
+ break;
+ if (f != null) {
+ b = n;
+ n = f;
+ continue;
+ }
+ if (!n.casValue(v, null))
+ break;
+ K key = n.key;
+ Comparable ck = comparable(key);
+ if (!n.appendMarker(f) || !b.casNext(n, f))
+ findNode(ck); // Retry via findNode
+ else {
+ findPredecessor(ck); // Clean index
+ if (head.right == null)
+ tryReduceLevel();
+ }
+ return (keyOnly)? key : new SnapshotEntry(key, (V)v);
+ }
+ }
+ }
+
+ /**
+ * Specialized variant of findPredecessor to get predecessor of
+ * last valid node. Needed by doRemoveLast. It is possible that
+ * all successors of returned node will have been deleted upon
+ * return, in which case this method can be retried.
+ * @return likely predecessor of last node.
+ */
+ private Node findPredecessorOfLast() {
+ for (;;) {
+ Index q = head;
+ for (;;) {
+ Index d, r;
+ if ((r = q.right) != null) {
+ if (r.indexesDeletedNode()) {
+ q.unlink(r);
+ break; // must restart
+ }
+ // proceed as far across as possible without overshooting
+ if (r.node.next != null) {
+ q = r;
+ continue;
+ }
+ }
+ if ((d = q.down) != null)
+ q = d;
+ else
+ return q.node;
+ }
+ }
+ }
+
/* ---------------- Relational operations -------------- */
// Control values OR'ed as arguments to findNear
@@ -1440,7 +1476,7 @@ public class ConcurrentSkipListMap
* @param m the map whose mappings are to be placed in this map.
* @throws ClassCastException if the keys in m are not Comparable, or
* are not mutually comparable.
- * @throws NullPointerException if the specified map is null.
+ * @throws NullPointerException if the specified map is null.
*/
public ConcurrentSkipListMap(Map m) {
this.comparator = null;
@@ -1451,9 +1487,10 @@ public class ConcurrentSkipListMap
/**
* Constructs a new map containing the same mappings as the given
* SortedMap, sorted according to the same ordering.
- * @param m the sorted map whose mappings are to be placed in this map,
- * and whose comparator is to be used to sort this map.
- * @throws NullPointerException if the specified sorted map is null.
+ * @param m the sorted map whose mappings are to be placed in this
+ * map, and whose comparator is to be used to sort this map.
+ * @throws NullPointerException if the specified sorted map is
+ * null.
*/
public ConcurrentSkipListMap(SortedMap m) {
this.comparator = m.comparator();
@@ -1521,7 +1558,7 @@ public class ConcurrentSkipListMap
if (j > 0) {
Index idx = null;
for (int i = 1; i <= j; ++i) {
- idx = new Index(z, idx);
+ idx = new Index(z, idx, null);
if (i > h.level)
h = new HeadIndex(h.node, h, idx, i);
@@ -1574,7 +1611,7 @@ public class ConcurrentSkipListMap
initialize();
/*
- * This is basically identical to buildFromSorted, but is
+ * This is nearly identical to buildFromSorted, but is
* distinct because readObject calls can't be nicely adapted
* as the kind of iterator needed by buildFromSorted. (They
* can be, but doing so requires type cheats and/or creation
@@ -1609,7 +1646,7 @@ public class ConcurrentSkipListMap
if (j > 0) {
Index idx = null;
for (int i = 1; i <= j; ++i) {
- idx = new Index(z, idx);
+ idx = new Index(z, idx, null);
if (i > h.level)
h = new HeadIndex(h.node, h, idx, i);
@@ -1831,6 +1868,53 @@ public class ConcurrentSkipListMap
return (es != null) ? es : (entrySet = new EntrySet());
}
+ /* ---------------- AbstractMap Overrides -------------- */
+
+ /**
+ * Compares the specified object with this map for equality.
+ * Returns true if the given object is also a map and the
+ * two maps represent the same mappings. More formally, two maps
+ * t1 and t2 represent the same mappings if
+ * t1.keySet().equals(t2.keySet()) and for every key
+ * k in t1.keySet(), (t1.get(k)==null ?
+ * t2.get(k)==null : t1.get(k).equals(t2.get(k))) . This
+ * operation may return misleading results if either map is
+ * concurrently modified during execution of this method.
+ *
+ * @param o object to be compared for equality with this map.
+ * @return true if the specified object is equal to this map.
+ */
+ public boolean equals(Object o) {
+ if (o == this)
+ return true;
+ if (!(o instanceof Map))
+ return false;
+ Map t = (Map) o;
+ try {
+ return (containsAllMappings(this, t) &&
+ containsAllMappings(t, this));
+ } catch(ClassCastException unused) {
+ return false;
+ } catch(NullPointerException unused) {
+ return false;
+ }
+ }
+
+ /**
+ * Helper for equals -- check for containment, avoiding nulls.
+ */
+ static boolean containsAllMappings(Map a, Map b) {
+ Iterator> it = b.entrySet().iterator();
+ while (it.hasNext()) {
+ Entry e = it.next();
+ Object k = e.getKey();
+ Object v = e.getValue();
+ if (k == null || v == null || !v.equals(a.get(k)))
+ return false;
+ }
+ return true;
+ }
+
/* ------ ConcurrentMap API methods ------ */
/**
@@ -1843,7 +1927,7 @@ public class ConcurrentSkipListMap
* else
* return map.get(key);
*
- * Except that the action is performed atomically.
+ * except that the action is performed atomically.
* @param key key with which the specified value is to be associated.
* @param value value to be associated with the specified key.
* @return previous value associated with specified key, or null
@@ -2010,27 +2094,27 @@ public class ConcurrentSkipListMap
* @throws NullPointerException if fromKey or toKey is
* null.
*/
- public ConcurrentSkipListSubMap subMap(K fromKey, K toKey) {
+ public ConcurrentNavigableMap subMap(K fromKey, K toKey) {
if (fromKey == null || toKey == null)
throw new NullPointerException();
return new ConcurrentSkipListSubMap(this, fromKey, toKey);
}
/**
- * Returns a view of the portion of this map whose keys are strictly less
- * than toKey. The returned sorted map is backed by this map, so
- * changes in the returned sorted map are reflected in this map, and
- * vice-versa.
+ * Returns a view of the portion of this map whose keys are
+ * strictly less than toKey. The returned sorted map is
+ * backed by this map, so changes in the returned sorted map are
+ * reflected in this map, and vice-versa.
* @param toKey high endpoint (exclusive) of the headMap.
- * @return a view of the portion of this map whose keys are strictly
- * less than toKey.
+ * @return a view of the portion of this map whose keys are
+ * strictly less than toKey.
*
* @throws ClassCastException if toKey is not compatible
- * with this map's comparator (or, if the map has no comparator,
- * if toKey does not implement Comparable).
+ * with this map's comparator (or, if the map has no comparator,
+ * if toKey does not implement Comparable).
* @throws NullPointerException if toKey is null.
*/
- public ConcurrentSkipListSubMap headMap(K toKey) {
+ public ConcurrentNavigableMap headMap(K toKey) {
if (toKey == null)
throw new NullPointerException();
return new ConcurrentSkipListSubMap(this, null, toKey);
@@ -2042,14 +2126,15 @@ public class ConcurrentSkipListMap
* map is backed by this map, so changes in the returned sorted
* map are reflected in this map, and vice-versa.
* @param fromKey low endpoint (inclusive) of the tailMap.
- * @return a view of the portion of this map whose keys are greater
- * than or equal to fromKey.
- * @throws ClassCastException if fromKey is not compatible
- * with this map's comparator (or, if the map has no comparator,
- * if fromKey does not implement Comparable).
+ * @return a view of the portion of this map whose keys are
+ * greater than or equal to fromKey.
+ * @throws ClassCastException if fromKey is not
+ * compatible with this map's comparator (or, if the map has no
+ * comparator, if fromKey does not implement
+ * Comparable).
* @throws NullPointerException if fromKey is null.
*/
- public ConcurrentSkipListSubMap tailMap(K fromKey) {
+ public ConcurrentNavigableMap tailMap(K fromKey) {
if (fromKey == null)
throw new NullPointerException();
return new ConcurrentSkipListSubMap(this, fromKey, null);
@@ -2059,15 +2144,15 @@ public class ConcurrentSkipListMap
/**
* Returns a key-value mapping associated with the least key
- * greater than or equal to the given key, or null if there is
- * no such entry. The returned entry does not support
- * the Entry.setValue method.
+ * greater than or equal to the given key, or null if
+ * there is no such entry. The returned entry does not
+ * support the Entry.setValue method.
*
* @param key the key.
- * @return an Entry associated with ceiling of given key, or null
- * if there is no such Entry.
- * @throws ClassCastException if key cannot be compared with the keys
- * currently in the map.
+ * @return an Entry associated with ceiling of given key, or
+ * null if there is no such Entry.
+ * @throws ClassCastException if key cannot be compared with the
+ * keys currently in the map.
* @throws NullPointerException if key is null.
*/
public Map.Entry ceilingEntry(K key) {
@@ -2076,13 +2161,13 @@ public class ConcurrentSkipListMap
/**
* Returns a key-value mapping associated with the greatest
- * key strictly less than the given key, or null if there is no
+ * key strictly less than the given key, or null if there is no
* such entry. The returned entry does not support
* the Entry.setValue method.
*
* @param key the key.
* @return an Entry with greatest key less than the given
- * key, or null if there is no such Entry.
+ * key, or null if there is no such Entry.
* @throws ClassCastException if key cannot be compared with the keys
* currently in the map.
* @throws NullPointerException if key is null.
@@ -2092,13 +2177,13 @@ public class ConcurrentSkipListMap
}
/**
- * Returns a key-value mapping associated with the greatest
- * key less than or equal to the given key, or null if there is no
- * such entry. The returned entry does not support
+ * Returns a key-value mapping associated with the greatest key
+ * less than or equal to the given key, or null if there
+ * is no such entry. The returned entry does not support
* the Entry.setValue method.
*
* @param key the key.
- * @return an Entry associated with floor of given key, or null
+ * @return an Entry associated with floor of given key, or null
* if there is no such Entry.
* @throws ClassCastException if key cannot be compared with the keys
* currently in the map.
@@ -2109,14 +2194,14 @@ public class ConcurrentSkipListMap
}
/**
- * Returns a key-value mapping associated with the least
- * key strictly greater than the given key, or null if there is no
- * such entry. The returned entry does not support
+ * Returns a key-value mapping associated with the least key
+ * strictly greater than the given key, or null if there
+ * is no such entry. The returned entry does not support
* the Entry.setValue method.
*
* @param key the key.
* @return an Entry with least key greater than the given key, or
- * null if there is no such Entry.
+ * null if there is no such Entry.
* @throws ClassCastException if key cannot be compared with the keys
* currently in the map.
* @throws NullPointerException if key is null.
@@ -2127,11 +2212,11 @@ public class ConcurrentSkipListMap
/**
* Returns a key-value mapping associated with the least
- * key in this map, or null if the map is empty.
+ * key in this map, or null if the map is empty.
* The returned entry does not support
* the Entry.setValue method.
*
- * @return an Entry with least key, or null
+ * @return an Entry with least key, or null
* if the map is empty.
*/
public Map.Entry firstEntry() {
@@ -2147,11 +2232,11 @@ public class ConcurrentSkipListMap
/**
* Returns a key-value mapping associated with the greatest
- * key in this map, or null if the map is empty.
+ * key in this map, or null if the map is empty.
* The returned entry does not support
* the Entry.setValue method.
*
- * @return an Entry with greatest key, or null
+ * @return an Entry with greatest key, or null
* if the map is empty.
*/
public Map.Entry lastEntry() {
@@ -2167,15 +2252,28 @@ public class ConcurrentSkipListMap
/**
* Removes and returns a key-value mapping associated with
- * the least key in this map, or null if the map is empty.
+ * the least key in this map, or null if the map is empty.
* The returned entry does not support
* the Entry.setValue method.
*
- * @return the removed first entry of this map, or null
+ * @return the removed first entry of this map, or null
* if the map is empty.
*/
- public Map.Entry removeFirstEntry() {
- return doRemoveFirstEntry();
+ public Map.Entry pollFirstEntry() {
+ return (SnapshotEntry)doRemoveFirst(false);
+ }
+
+ /**
+ * Removes and returns a key-value mapping associated with
+ * the greatest key in this map, or null if the map is empty.
+ * The returned entry does not support
+ * the Entry.setValue method.
+ *
+ * @return the removed last entry of this map, or null
+ * if the map is empty.
+ */
+ public Map.Entry pollLastEntry() {
+ return (SnapshotEntry)doRemoveLast(false);
}
/* ---------------- Iterators -------------- */
@@ -2206,8 +2304,8 @@ public class ConcurrentSkipListMap
/**
* Create a submap iterator starting at given least key, or
- * first node if least is null, but not greater or equal to
- * fence, or end if fence is null.
+ * first node if least is null, but not greater or equal to
+ * fence, or end if fence is null.
*/
ConcurrentSkipListMapIterator(K least, K fence) {
for (;;) {
@@ -2438,13 +2536,27 @@ public class ConcurrentSkipListMap
}
/**
+ * Remove first entry; return key or null if empty.
+ */
+ K removeFirstKey() {
+ return (K)doRemoveFirst(true);
+ }
+
+ /**
+ * Remove last entry; return key or null if empty.
+ */
+ K removeLastKey() {
+ return (K)doRemoveLast(true);
+ }
+
+ /**
* Return SnapshotEntry for results of findNear ofter screening
* to ensure result is in given range. Needed by submaps.
* @param kkey the key
* @param rel the relation -- OR'ed combination of EQ, LT, GT
* @param least minimum allowed key value
* @param fence key greater than maximum allowed key value
- * @return Entry fitting relation, or null if no such
+ * @return Entry fitting relation, or null if no such
*/
SnapshotEntry getNear(K kkey, int rel, K least, K fence) {
K key = kkey;
@@ -2469,14 +2581,14 @@ public class ConcurrentSkipListMap
// Methods expanding out relational operations for submaps
/**
- * Return ceiling, or first node if key is null
+ * Return ceiling, or first node if key is null
*/
Node findCeiling(K key) {
return (key == null)? findFirst() : findNear(key, GT|EQ);
}
/**
- * Return lower node, or last node if key is null
+ * Return lower node, or last node if key is null
*/
Node findLower(K key) {
return (key == null)? findLast() : findNear(key, LT);
@@ -2499,6 +2611,25 @@ public class ConcurrentSkipListMap
}
}
+
+ /**
+ * Find and remove greatest element of subrange.
+ */
+ SnapshotEntry removeLastEntryOfSubrange(K least, K fence) {
+ for (;;) {
+ Node n = findLower(fence);
+ if (n == null)
+ return null;
+ K k = n.key;
+ if (least != null && compare(k, least) < 0)
+ return null;
+ V v = doRemove(k, null);
+ if (v != null)
+ return new SnapshotEntry(k,v);
+ }
+ }
+
+
SnapshotEntry getCeiling(K key, K least, K fence) {
return getNear(key, GT|EQ, least, fence);
}
@@ -2628,7 +2759,8 @@ public class ConcurrentSkipListMap
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
- return ConcurrentSkipListMap.this.remove(e.getKey(), e.getValue());
+ return ConcurrentSkipListMap.this.remove(e.getKey(),
+ e.getValue());
}
public boolean isEmpty() {
return ConcurrentSkipListMap.this.isEmpty();
@@ -2659,4 +2791,822 @@ public class ConcurrentSkipListMap
return c.toArray(a);
}
}
+
+ /**
+ * Submaps returned by {@link ConcurrentSkipListMap} submap operations
+ * represent a subrange of mappings of their underlying
+ * maps. Instances of this class support all methods of their
+ * underlying maps, differing in that mappings outside their range are
+ * ignored, and attempts to add mappings outside their ranges result
+ * in {@link IllegalArgumentException}. Instances of this class are
+ * constructed only using the subMap, headMap, and
+ * tailMap methods of their underlying maps.
+ */
+ static class ConcurrentSkipListSubMap extends AbstractMap
+ implements ConcurrentNavigableMap, java.io.Serializable {
+
+ private static final long serialVersionUID = -7647078645895051609L;
+
+ /** Underlying map */
+ private final ConcurrentSkipListMap m;
+ /** lower bound key, or null if from start */
+ private final K least;
+ /** upper fence key, or null if to end */
+ private final K fence;
+ // Lazily initialized view holders
+ private transient Set keySetView;
+ private transient Set> entrySetView;
+ private transient Collection valuesView;
+
+ /**
+ * Creates a new submap.
+ * @param least inclusive least value, or null if from start
+ * @param fence exclusive upper bound or null if to end
+ * @throws IllegalArgumentException if least and fence nonnull
+ * and least greater than fence
+ */
+ ConcurrentSkipListSubMap(ConcurrentSkipListMap map,
+ K least, K fence) {
+ if (least != null &&
+ fence != null &&
+ map.compare(least, fence) > 0)
+ throw new IllegalArgumentException("inconsistent range");
+ this.m = map;
+ this.least = least;
+ this.fence = fence;
+ }
+
+ /* ---------------- Utilities -------------- */
+
+ boolean inHalfOpenRange(K key) {
+ return m.inHalfOpenRange(key, least, fence);
+ }
+
+ boolean inOpenRange(K key) {
+ return m.inOpenRange(key, least, fence);
+ }
+
+ ConcurrentSkipListMap.Node firstNode() {
+ return m.findCeiling(least);
+ }
+
+ ConcurrentSkipListMap.Node lastNode() {
+ return m.findLower(fence);
+ }
+
+ boolean isBeforeEnd(ConcurrentSkipListMap.Node n) {
+ return (n != null &&
+ (fence == null ||
+ n.key == null || // pass by markers and headers
+ m.compare(fence, n.key) > 0));
+ }
+
+ void checkKey(K key) throws IllegalArgumentException {
+ if (!inHalfOpenRange(key))
+ throw new IllegalArgumentException("key out of range");
+ }
+
+ /**
+ * Returns underlying map. Needed by ConcurrentSkipListSet
+ * @return the backing map
+ */
+ ConcurrentSkipListMap getMap() {
+ return m;
+ }
+
+ /**
+ * Returns least key. Needed by ConcurrentSkipListSet
+ * @return least key or null if from start
+ */
+ K getLeast() {
+ return least;
+ }
+
+ /**
+ * Returns fence key. Needed by ConcurrentSkipListSet
+ * @return fence key or null of to end
+ */
+ K getFence() {
+ return fence;
+ }
+
+ /**
+ * Non-exception throwing version of firstKey needed by
+ * ConcurrentSkipListSubSet
+ * @return first key, or null if empty
+ */
+ K lowestKey() {
+ ConcurrentSkipListMap.Node n = firstNode();
+ if (isBeforeEnd(n))
+ return n.key;
+ else
+ return null;
+ }
+
+ /**
+ * Non-exception throwing version of highestKey needed by
+ * ConcurrentSkipListSubSet
+ * @return last key, or null if empty
+ */
+ K highestKey() {
+ ConcurrentSkipListMap.Node n = lastNode();
+ if (isBeforeEnd(n))
+ return n.key;
+ else
+ return null;
+ }
+
+ /* ---------------- Map API methods -------------- */
+
+ /**
+ * Returns true if this map contains a mapping for
+ * the specified key.
+ * @param key key whose presence in this map is to be tested.
+ * @return true if this map contains a mapping for
+ * the specified key.
+ * @throws ClassCastException if the key cannot be compared
+ * with the keys currently in the map.
+ * @throws NullPointerException if the key is null.
+ */
+ public boolean containsKey(Object key) {
+ K k = (K)key;
+ return inHalfOpenRange(k) && m.containsKey(k);
+ }
+
+ /**
+ * Returns the value to which this map maps the specified key.
+ * Returns null if the map contains no mapping for
+ * this key.
+ *
+ * @param key key whose associated value is to be returned.
+ * @return the value to which this map maps the specified key,
+ * or null if the map contains no mapping for the
+ * key.
+ * @throws ClassCastException if the key cannot be compared
+ * with the keys currently in the map.
+ * @throws NullPointerException if the key is null.
+ */
+ public V get(Object key) {
+ K k = (K)key;
+ return ((!inHalfOpenRange(k)) ? null : m.get(k));
+ }
+
+ /**
+ * Associates 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.
+ *
+ * @param key key with which the specified value is to be associated.
+ * @param value value to be associated with the specified key.
+ *
+ * @return previous value associated with specified key, or
+ * null if there was no mapping for key.
+ * @throws ClassCastException if the key cannot be compared
+ * with the keys currently in the map.
+ * @throws IllegalArgumentException if key outside range of
+ * this submap.
+ * @throws NullPointerException if the key or value are null.
+ */
+ public V put(K key, V value) {
+ checkKey(key);
+ return m.put(key, value);
+ }
+
+ /**
+ * Removes the mapping for this key from this Map if present.
+ *
+ * @param key key for which mapping should be removed
+ * @return previous value associated with specified key, or
+ * null if there was no mapping for key.
+ *
+ * @throws ClassCastException if the key cannot be compared
+ * with the keys currently in the map.
+ * @throws NullPointerException if the key is null.
+ */
+ public V remove(Object key) {
+ K k = (K)key;
+ return (!inHalfOpenRange(k))? null : m.remove(k);
+ }
+
+ /**
+ * Returns the number of elements in this map. If this map
+ * contains more than Integer.MAX_VALUE elements, it
+ * returns Integer.MAX_VALUE.
+ *
+ * Beware that, unlike in most collections, this method is
+ * NOT a constant-time operation. Because of the
+ * asynchronous nature of these maps, determining the current
+ * number of elements requires traversing them all to count them.
+ * Additionally, it is possible for the size to change during
+ * execution of this method, in which case the returned result
+ * will be inaccurate. Thus, this method is typically not very
+ * useful in concurrent applications.
+ *
+ * @return the number of elements in this map.
+ */
+ public int size() {
+ long count = 0;
+ for (ConcurrentSkipListMap.Node n = firstNode();
+ isBeforeEnd(n);
+ n = n.next) {
+ if (n.getValidValue() != null)
+ ++count;
+ }
+ return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count;
+ }
+
+ /**
+ * Returns true if this map contains no key-value mappings.
+ * @return true if this map contains no key-value mappings.
+ */
+ public boolean isEmpty() {
+ return !isBeforeEnd(firstNode());
+ }
+
+ /**
+ * Returns true if this map maps one or more keys to the
+ * specified value. This operation requires time linear in the
+ * Map size.
+ *
+ * @param value value whose presence in this Map is to be tested.
+ * @return true if a mapping to value exists;
+ * false otherwise.
+ * @throws NullPointerException if the value is null.
+ */
+ public boolean containsValue(Object value) {
+ if (value == null)
+ throw new NullPointerException();
+ for (ConcurrentSkipListMap.Node n = firstNode();
+ isBeforeEnd(n);
+ n = n.next) {
+ V v = n.getValidValue();
+ if (v != null && value.equals(v))
+ return true;
+ }
+ return false;
+ }
+
+ /**
+ * Removes all mappings from this map.
+ */
+ public void clear() {
+ for (ConcurrentSkipListMap.Node n = firstNode();
+ isBeforeEnd(n);
+ n = n.next) {
+ if (n.getValidValue() != null)
+ m.remove(n.key);
+ }
+ }
+
+ /* ---------------- ConcurrentMap API methods -------------- */
+
+ /**
+ * If the specified key is not already associated
+ * with a value, associate it with the given value.
+ * This is equivalent to
+ *
+ * if (!map.containsKey(key))
+ * return map.put(key, value);
+ * else
+ * return map.get(key);
+ *
+ * Except that the action is performed atomically.
+ * @param key key with which the specified value is to be associated.
+ * @param value value to be associated with the specified key.
+ * @return previous value associated with specified key, or
+ * null if there was no mapping for key.
+ *
+ * @throws ClassCastException if the key cannot be compared
+ * with the keys currently in the map.
+ * @throws IllegalArgumentException if key outside range of
+ * this submap.
+ * @throws NullPointerException if the key or value are null.
+ */
+ public V putIfAbsent(K key, V value) {
+ checkKey(key);
+ return m.putIfAbsent(key, value);
+ }
+
+ /**
+ * Remove entry for key only if currently mapped to given value.
+ * Acts as
+ *
+ * if ((map.containsKey(key) && map.get(key).equals(value)) {
+ * map.remove(key);
+ * return true;
+ * } else return false;
+ *
+ * except that the action is performed atomically.
+ * @param key key with which the specified value is associated.
+ * @param value value associated with the specified key.
+ * @return true if the value was removed, false otherwise
+ * @throws ClassCastException if the key cannot be compared
+ * with the keys currently in the map.
+ * @throws NullPointerException if the key or value are
+ * null.
+ */
+ public boolean remove(Object key, Object value) {
+ K k = (K)key;
+ return inHalfOpenRange(k) && m.remove(k, value);
+ }
+
+ /**
+ * Replace entry for key only if currently mapped to given value.
+ * Acts as
+ *
+ * if ((map.containsKey(key) && map.get(key).equals(oldValue)) {
+ * map.put(key, newValue);
+ * return true;
+ * } else return false;
+ *
+ * except that the action is performed atomically.
+ * @param key key with which the specified value is associated.
+ * @param oldValue value expected to be associated with the
+ * specified key.
+ * @param newValue value to be associated with the specified key.
+ * @return true if the value was replaced
+ * @throws ClassCastException if the key cannot be compared
+ * with the keys currently in the map.
+ * @throws IllegalArgumentException if key outside range of
+ * this submap.
+ * @throws NullPointerException if key, oldValue or newValue
+ * are null.
+ */
+ public boolean replace(K key, V oldValue, V newValue) {
+ checkKey(key);
+ return m.replace(key, oldValue, newValue);
+ }
+
+ /**
+ * Replace entry for key only if currently mapped to some value.
+ * Acts as
+ *
+ * if ((map.containsKey(key)) {
+ * return map.put(key, value);
+ * } else return null;
+ *
+ * except that the action is performed atomically.
+ * @param key key with which the specified value is associated.
+ * @param value value to be associated with the specified key.
+ * @return previous value associated with specified key, or
+ * null if there was no mapping for key.
+ * @throws ClassCastException if the key cannot be compared
+ * with the keys currently in the map.
+ * @throws IllegalArgumentException if key outside range of
+ * this submap.
+ * @throws NullPointerException if the key or value are
+ * null.
+ */
+ public V replace(K key, V value) {
+ checkKey(key);
+ return m.replace(key, value);
+ }
+
+ /* ---------------- SortedMap API methods -------------- */
+
+ /**
+ * Returns the comparator used to order this map, or null
+ * if this map uses its keys' natural order.
+ *
+ * @return the comparator associated with this map, or
+ * null if it uses its keys' natural sort method.
+ */
+ public Comparator comparator() {
+ return m.comparator();
+ }
+
+ /**
+ * Returns the first (lowest) key currently in this map.
+ *
+ * @return the first (lowest) key currently in this map.
+ * @throws NoSuchElementException Map is empty.
+ */
+ public K firstKey() {
+ ConcurrentSkipListMap.Node n = firstNode();
+ if (isBeforeEnd(n))
+ return n.key;
+ else
+ throw new NoSuchElementException();
+ }
+
+ /**
+ * Returns the last (highest) key currently in this map.
+ *
+ * @return the last (highest) key currently in this map.
+ * @throws NoSuchElementException Map is empty.
+ */
+ public K lastKey() {
+ ConcurrentSkipListMap.Node n = lastNode();
+ if (n != null) {
+ K last = n.key;
+ if (inHalfOpenRange(last))
+ return last;
+ }
+ throw new NoSuchElementException();
+ }
+
+ /**
+ * Returns a view of the portion of this map whose keys range
+ * from fromKey, inclusive, to toKey,
+ * exclusive. (If fromKey and toKey are
+ * equal, the returned sorted map is empty.) The returned
+ * sorted map is backed by this map, so changes in the
+ * returned sorted map are reflected in this map, and
+ * vice-versa.
+
+ * @param fromKey low endpoint (inclusive) of the subMap.
+ * @param toKey high endpoint (exclusive) of the subMap.
+ *
+ * @return a view of the portion of this map whose keys range
+ * from fromKey, inclusive, to toKey,
+ * exclusive.
+ *
+ * @throws ClassCastException if fromKey and
+ * toKey cannot be compared to one another using this
+ * map's comparator (or, if the map has no comparator, using
+ * natural ordering).
+ * @throws IllegalArgumentException if fromKey is
+ * greater than toKey or either key is outside of
+ * the range of this submap.
+ * @throws NullPointerException if fromKey or
+ * toKey is null.
+ */
+ public ConcurrentNavigableMap subMap(K fromKey, K toKey) {
+ if (fromKey == null || toKey == null)
+ throw new NullPointerException();
+ if (!inOpenRange(fromKey) || !inOpenRange(toKey))
+ throw new IllegalArgumentException("key out of range");
+ return new ConcurrentSkipListSubMap(m, fromKey, toKey);
+ }
+
+ /**
+ * Returns a view of the portion of this map whose keys are
+ * strictly less than toKey. The returned sorted map
+ * is backed by this map, so changes in the returned sorted
+ * map are reflected in this map, and vice-versa.
+ * @param toKey high endpoint (exclusive) of the headMap.
+ * @return a view of the portion of this map whose keys are
+ * strictly less than toKey.
+ *
+ * @throws ClassCastException if toKey is not
+ * compatible with this map's comparator (or, if the map has
+ * no comparator, if toKey does not implement
+ * Comparable).
+ * @throws IllegalArgumentException if toKey is
+ * outside of the range of this submap.
+ * @throws NullPointerException if toKey is
+ * null.
+ */
+ public ConcurrentNavigableMap headMap(K toKey) {
+ if (toKey == null)
+ throw new NullPointerException();
+ if (!inOpenRange(toKey))
+ throw new IllegalArgumentException("key out of range");
+ return new ConcurrentSkipListSubMap(m, least, toKey);
+ }
+
+ /**
+ * Returns a view of the portion of this map whose keys are
+ * greater than or equal to fromKey. The returned sorted
+ * map is backed by this map, so changes in the returned sorted
+ * map are reflected in this map, and vice-versa.
+ * @param fromKey low endpoint (inclusive) of the tailMap.
+ * @return a view of the portion of this map whose keys are
+ * greater than or equal to fromKey.
+ * @throws ClassCastException if fromKey is not
+ * compatible with this map's comparator (or, if the map has
+ * no comparator, if fromKey does not implement
+ * Comparable).
+ * @throws IllegalArgumentException if fromKey is
+ * outside of the range of this submap.
+ * @throws NullPointerException if fromKey is
+ * null.
+ */
+ public ConcurrentNavigableMap tailMap(K fromKey) {
+ if (fromKey == null)
+ throw new NullPointerException();
+ if (!inOpenRange(fromKey))
+ throw new IllegalArgumentException("key out of range");
+ return new ConcurrentSkipListSubMap(m, fromKey, fence);
+ }
+
+ /* ---------------- Relational methods -------------- */
+
+ /**
+ * Returns a key-value mapping associated with the least key
+ * greater than or equal to the given key, or null if
+ * there is no such entry. The returned entry does
+ * not support the Entry.setValue method.
+ *
+ * @param key the key.
+ * @return an Entry associated with ceiling of given key, or
+ * null if there is no such Entry.
+ * @throws ClassCastException if key cannot be compared with the keys
+ * currently in the map.
+ * @throws NullPointerException if key is null.
+ */
+ public Map.Entry ceilingEntry(K key) {
+ return m.getCeiling(key, least, fence);
+ }
+
+ /**
+ * Returns a key-value mapping associated with the greatest
+ * key strictly less than the given key, or null if
+ * there is no such entry. The returned entry does
+ * not support the Entry.setValue method.
+ *
+ * @param key the key.
+ * @return an Entry with greatest key less than the given
+ * key, or null if there is no such Entry.
+ * @throws ClassCastException if key cannot be compared with
+ * the keys currently in the map.
+ * @throws NullPointerException if key is null.
+ */
+ public Map.Entry lowerEntry(K key) {
+ return m.getLower(key, least, fence);
+ }
+
+ /**
+ * Returns a key-value mapping associated with the greatest
+ * key less than or equal to the given key, or null
+ * if there is no such entry. The returned entry does
+ * not support the Entry.setValue method.
+ *
+ * @param key the key.
+ * @return an Entry associated with floor of given key, or
+ * null if there is no such Entry.
+ * @throws ClassCastException if key cannot be compared with
+ * the keys currently in the map.
+ * @throws NullPointerException if key is null.
+ */
+ public Map.Entry floorEntry(K key) {
+ return m.getFloor(key, least, fence);
+ }
+
+ /**
+ * Returns a key-value mapping associated with the least key
+ * strictly greater than the given key, or null if
+ * there is no such entry. The returned entry does
+ * not support the Entry.setValue method.
+ *
+ * @param key the key.
+ * @return an Entry with least key greater than the given key, or
+ * null if there is no such Entry.
+ * @throws ClassCastException if key cannot be compared with
+ * the keys currently in the map.
+ * @throws NullPointerException if key is null.
+ */
+ public Map.Entry higherEntry(K key) {
+ return m.getHigher(key, least, fence);
+ }
+
+ /**
+ * Returns a key-value mapping associated with the least
+ * key in this map, or null if the map is empty.
+ * The returned entry does not support
+ * the Entry.setValue method.
+ *
+ * @return an Entry with least key, or null
+ * if the map is empty.
+ */
+ public Map.Entry firstEntry() {
+ for (;;) {
+ ConcurrentSkipListMap.Node n = firstNode();
+ if (!isBeforeEnd(n))
+ return null;
+ Map.Entry e = n.createSnapshot();
+ if (e != null)
+ return e;
+ }
+ }
+
+ /**
+ * Returns a key-value mapping associated with the greatest
+ * key in this map, or null if the map is empty.
+ * The returned entry does not support
+ * the Entry.setValue method.
+ *
+ * @return an Entry with greatest key, or null
+ * if the map is empty.
+ */
+ public Map.Entry lastEntry() {
+ for (;;) {
+ ConcurrentSkipListMap.Node n = lastNode();
+ if (n == null || !inHalfOpenRange(n.key))
+ return null;
+ Map.Entry e = n.createSnapshot();
+ if (e != null)
+ return e;
+ }
+ }
+
+ /**
+ * Removes and returns a key-value mapping associated with
+ * the least key in this map, or null if the map is empty.
+ * The returned entry does not support
+ * the Entry.setValue method.
+ *
+ * @return the removed first entry of this map, or null
+ * if the map is empty.
+ */
+ public Map.Entry pollFirstEntry() {
+ return m.removeFirstEntryOfSubrange(least, fence);
+ }
+
+ /**
+ * Removes and returns a key-value mapping associated with the
+ * greatest key in this map, or null if the map is
+ * empty. The returned entry does not support the
+ * Entry.setValue method.
+ *
+ * @return the removed last entry of this map, or null
+ * if the map is empty.
+ */
+ public Map.Entry pollLastEntry() {
+ return m.removeLastEntryOfSubrange(least, fence);
+ }
+
+ /* ---------------- Submap Views -------------- */
+
+ /**
+ * Returns a set view of the keys contained in this map. The
+ * set is backed by the map, so changes to the map are
+ * reflected in the set, and vice-versa. The set supports
+ * element removal, which removes the corresponding mapping
+ * from this map, via the Iterator.remove,
+ * Set.remove, removeAll,
+ * retainAll, and clear operations. It does
+ * not support the add or addAll operations.
+ * The view's iterator is a "weakly consistent"
+ * iterator that will never throw {@link
+ * java.util.ConcurrentModificationException}, and guarantees
+ * to traverse elements as they existed upon construction of
+ * the iterator, and may (but is not guaranteed to) reflect
+ * any modifications subsequent to construction.
+ *
+ * @return a set view of the keys contained in this map.
+ */
+ public Set keySet() {
+ Set ks = keySetView;
+ return (ks != null) ? ks : (keySetView = new KeySetView());
+ }
+
+ class KeySetView extends AbstractSet {
+ public Iterator iterator() {
+ return m.subMapKeyIterator(least, fence);
+ }
+ public int size() {
+ return ConcurrentSkipListSubMap.this.size();
+ }
+ public boolean isEmpty() {
+ return ConcurrentSkipListSubMap.this.isEmpty();
+ }
+ public boolean contains(Object k) {
+ return ConcurrentSkipListSubMap.this.containsKey(k);
+ }
+ public Object[] toArray() {
+ Collection c = new ArrayList();
+ for (Iterator i = iterator(); i.hasNext(); )
+ c.add(i.next());
+ return c.toArray();
+ }
+ public T[] toArray(T[] a) {
+ Collection c = new ArrayList();
+ for (Iterator i = iterator(); i.hasNext(); )
+ c.add(i.next());
+ return c.toArray(a);
+ }
+ }
+
+ /**
+ * Returns a collection view of the values contained in this
+ * map. The collection is backed by the map, so changes to
+ * the map are reflected in the collection, and vice-versa.
+ * The collection supports element removal, which removes the
+ * corresponding mapping from this map, via the
+ * Iterator.remove, Collection.remove,
+ * removeAll, retainAll, and clear
+ * operations. It does not support the add or
+ * addAll operations. The view's iterator
+ * is a "weakly consistent" iterator that will never throw
+ * {@link java.util.ConcurrentModificationException}, and
+ * guarantees to traverse elements as they existed upon
+ * construction of the iterator, and may (but is not
+ * guaranteed to) reflect any modifications subsequent to
+ * construction.
+ *
+ * @return a collection view of the values contained in this map.
+ */
+ public Collection values() {
+ Collection vs = valuesView;
+ return (vs != null) ? vs : (valuesView = new ValuesView());
+ }
+
+ class ValuesView extends AbstractCollection {
+ public Iterator iterator() {
+ return m.subMapValueIterator(least, fence);
+ }
+ public int size() {
+ return ConcurrentSkipListSubMap.this.size();
+ }
+ public boolean isEmpty() {
+ return ConcurrentSkipListSubMap.this.isEmpty();
+ }
+ public boolean contains(Object v) {
+ return ConcurrentSkipListSubMap.this.containsValue(v);
+ }
+ public Object[] toArray() {
+ Collection c = new ArrayList();
+ for (Iterator i = iterator(); i.hasNext(); )
+ c.add(i.next());
+ return c.toArray();
+ }
+ public T[] toArray(T[] a) {
+ Collection c = new ArrayList();
+ for (Iterator i = iterator(); i.hasNext(); )
+ c.add(i.next());
+ return c.toArray(a);
+ }
+ }
+
+ /**
+ * Returns a collection view of the mappings contained in this
+ * map. Each element in the returned collection is a
+ * Map.Entry. The collection is backed by the map,
+ * so changes to the map are reflected in the collection, and
+ * vice-versa. The collection supports element removal, which
+ * removes the corresponding mapping from the map, via the
+ * Iterator.remove, Collection.remove,
+ * removeAll, retainAll, and clear
+ * operations. It does not support the add or
+ * addAll operations. The view's iterator
+ * is a "weakly consistent" iterator that will never throw
+ * {@link java.util.ConcurrentModificationException}, and
+ * guarantees to traverse elements as they existed upon
+ * construction of the iterator, and may (but is not
+ * guaranteed to) reflect any modifications subsequent to
+ * construction. The Map.Entry elements returned by
+ * iterator.next() do not support the
+ * setValue operation.
+ *
+ * @return a collection view of the mappings contained in this map.
+ */
+ public Set> entrySet() {
+ Set> es = entrySetView;
+ return (es != null) ? es : (entrySetView = new EntrySetView());
+ }
+
+ class EntrySetView extends AbstractSet> {
+ public Iterator> iterator() {
+ return m.subMapEntryIterator(least, fence);
+ }
+ public int size() {
+ return ConcurrentSkipListSubMap.this.size();
+ }
+ public boolean isEmpty() {
+ return ConcurrentSkipListSubMap.this.isEmpty();
+ }
+ public boolean contains(Object o) {
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry e = (Map.Entry) o;
+ K key = e.getKey();
+ if (!inHalfOpenRange(key))
+ return false;
+ V v = m.get(key);
+ return v != null && v.equals(e.getValue());
+ }
+ public boolean remove(Object o) {
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry e = (Map.Entry) o;
+ K key = e.getKey();
+ if (!inHalfOpenRange(key))
+ return false;
+ return m.remove(key, e.getValue());
+ }
+ public Object[] toArray() {
+ Collection> c = new ArrayList>();
+ for (ConcurrentSkipListMap.Node n = firstNode();
+ isBeforeEnd(n);
+ n = n.next) {
+ Map.Entry e = n.createSnapshot();
+ if (e != null)
+ c.add(e);
+ }
+ return c.toArray();
+ }
+ public T[] toArray(T[] a) {
+ Collection> c = new ArrayList>();
+ for (ConcurrentSkipListMap.Node n = firstNode();
+ isBeforeEnd(n);
+ n = n.next) {
+ Map.Entry e = n.createSnapshot();
+ if (e != null)
+ c.add(e);
+ }
+ return c.toArray(a);
+ }
+ }
+ }
}