--- jsr166/src/jsr166x/ConcurrentSkipListMap.java 2004/08/11 10:58:15 1.1
+++ jsr166/src/jsr166x/ConcurrentSkipListMap.java 2010/09/01 20:12:39 1.10
@@ -4,18 +4,18 @@
* http://creativecommons.org/licenses/publicdomain
*/
-package jsr166x;
+package jsr166x;
import java.util.*;
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
@@ -27,37 +27,25 @@ import java.util.concurrent.atomic.*;
* elements reflecting the state of the map at some point at or since
* the creation of the iterator. They do not throw {@link
* ConcurrentModificationException}, and may proceed concurrently with
- * other operations.
+ * other operations. Ascending key ordered views and their iterators
+ * are faster than descending ones.
*
- *
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}
@@ -68,12 +56,11 @@ import java.util.concurrent.atomic.*;
*
* @author Doug Lea
* @param the type of keys maintained by this map
- * @param the type of mapped values
+ * @param the type of mapped values
*/
-public class ConcurrentSkipListMap extends AbstractMap
- implements ConcurrentMap,
- SortedMap,
- Cloneable,
+public class ConcurrentSkipListMap extends AbstractMap
+ implements ConcurrentNavigableMap,
+ Cloneable,
java.io.Serializable {
/*
* This class implements a tree-like two-dimensionally linked skip
@@ -87,29 +74,30 @@ public class ConcurrentSkipListMap
* possible list with 2 levels of index:
*
* Head nodes Index nodes
- * +-+ right +-+ +-+
+ * +-+ right +-+ +-+
* |2|---------------->| |--------------------->| |->null
- * +-+ +-+ +-+
+ * +-+ +-+ +-+
* | down | |
* v v v
- * +-+ +-+ +-+ +-+ +-+ +-+
+ * +-+ +-+ +-+ +-+ +-+ +-+
* |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 +124,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
@@ -156,9 +145,9 @@ public class ConcurrentSkipListMap
* Here's the sequence of events for a deletion of node n with
* predecessor b and successor f, initially:
*
- * +------+ +------+ +------+
+ * +------+ +------+ +------+
* ... | b |------>| n |----->| f | ...
- * +------+ +------+ +------+
+ * +------+ +------+ +------+
*
* 1. CAS n's value field from non-null to null.
* From this point on, no public operations encountering
@@ -172,15 +161,15 @@ public class ConcurrentSkipListMap
*
* +------+ +------+ +------+ +------+
* ... | b |------>| n |----->|marker|------>| f | ...
- * +------+ +------+ +------+ +------+
+ * +------+ +------+ +------+ +------+
*
* 3. CAS b's next pointer over both n and its marker.
* From this point on, no new traversals will encounter n,
* and it can eventually be GCed.
* +------+ +------+
* ... | b |----------------------------------->| f | ...
- * +------+ +------+
- *
+ * +------+ +------+
+ *
* A failure at step 1 leads to simple retry due to a lost race
* with another operation. Steps 2-3 can fail because some other
* thread noticed during a traversal a node with null value and
@@ -199,7 +188,7 @@ public class ConcurrentSkipListMap
* nodes. This doesn't change the basic algorithm except for the
* need to make sure base traversals start at predecessors (here,
* b) that are not (structurally) deleted, otherwise retrying
- * after processing the deletion.
+ * after processing the deletion.
*
* Index levels are maintained as lists with volatile next fields,
* using CAS to link and unlink. Races are allowed in index-list
@@ -276,8 +265,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 Hakan Sundell's
+ * thesis (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
@@ -302,11 +292,11 @@ public class ConcurrentSkipListMap
/**
* Special value used to identify base-level header
- */
+ */
private static final Object BASE_HEADER = new Object();
/**
- * The topmost head index of the skiplist.
+ * The topmost head index of the skiplist.
*/
private transient volatile HeadIndex head;
@@ -329,6 +319,10 @@ public class ConcurrentSkipListMap
private transient EntrySet entrySet;
/** Lazily initialized values collection */
private transient Values values;
+ /** Lazily initialized descending key set */
+ private transient DescendingKeySet descendingKeySet;
+ /** Lazily initialized descending entry set */
+ private transient DescendingEntrySet descendingEntrySet;
/**
* Initialize or reset state. Needed by constructors, clone,
@@ -337,16 +331,18 @@ public class ConcurrentSkipListMap
*/
final void initialize() {
keySet = null;
- entrySet = null;
+ entrySet = null;
values = null;
+ descendingEntrySet = null;
+ descendingKeySet = null;
randomSeed = (int) System.nanoTime();
head = new HeadIndex(new Node(null, BASE_HEADER, null),
null, null, 1);
}
/** Updater for casHead */
- private static final
- AtomicReferenceFieldUpdater
+ private static final
+ AtomicReferenceFieldUpdater
headUpdater = AtomicReferenceFieldUpdater.newUpdater
(ConcurrentSkipListMap.class, HeadIndex.class, "head");
@@ -394,16 +390,15 @@ public class ConcurrentSkipListMap
}
/** Updater for casNext */
- static final AtomicReferenceFieldUpdater
+ static final AtomicReferenceFieldUpdater
nextUpdater = AtomicReferenceFieldUpdater.newUpdater
(Node.class, Node.class, "next");
/** Updater for casValue */
- static final AtomicReferenceFieldUpdater
+ static final AtomicReferenceFieldUpdater
valueUpdater = AtomicReferenceFieldUpdater.newUpdater
(Node.class, Object.class, "value");
-
/**
* compareAndSet value field
*/
@@ -471,7 +466,7 @@ public class ConcurrentSkipListMap
/**
* Return value if this node contains a valid key-value pair,
- * else null.
+ * else null.
* @return this node's value if it isn't a marker or header or
* is deleted, else null.
*/
@@ -512,17 +507,8 @@ 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;
this.key = node.key;
@@ -531,7 +517,7 @@ public class ConcurrentSkipListMap
}
/** Updater for casRight */
- static final AtomicReferenceFieldUpdater
+ static final AtomicReferenceFieldUpdater
rightUpdater = AtomicReferenceFieldUpdater.newUpdater
(Index.class, Index.class, "right");
@@ -560,7 +546,7 @@ public class ConcurrentSkipListMap
*/
final boolean link(Index succ, Index newSucc) {
Node n = node;
- newSucc.right = succ;
+ newSucc.right = succ;
return n.value != null && casRight(succ, newSucc);
}
@@ -583,12 +569,11 @@ 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;
}
- }
+ }
/* ---------------- Map.Entry support -------------- */
@@ -596,10 +581,10 @@ public class ConcurrentSkipListMap
* An immutable representation of a key-value mapping as it
* existed at some point in time. This class does not
* support the Map.Entry.setValue method.
- */
+ */
static class SnapshotEntry implements Map.Entry {
- private final K key;
- private final V value;
+ private final K key;
+ private final V value;
/**
* Creates a new entry representing the given key and value.
@@ -607,31 +592,31 @@ public class ConcurrentSkipListMap
* @param value the value
*/
SnapshotEntry(K key, V value) {
- this.key = key;
- this.value = value;
- }
-
- /**
- * Returns the key corresponding to this entry.
- *
- * @return the key corresponding to this entry.
- */
+ this.key = key;
+ this.value = value;
+ }
+
+ /**
+ * Returns the key corresponding to this entry.
+ *
+ * @return the key corresponding to this entry.
+ */
public K getKey() {
return key;
}
- /**
- * Returns the value corresponding to this entry.
- *
- * @return the value corresponding to this entry.
- */
+ /**
+ * Returns the value corresponding to this entry.
+ *
+ * @return the value corresponding to this entry.
+ */
public V getValue() {
- return value;
+ return value;
}
- /**
- * Always fails, throwing UnsupportedOperationException.
- * @throws UnsupportedOperationException always.
+ /**
+ * Always fails, throwing UnsupportedOperationException.
+ * @throws UnsupportedOperationException always.
*/
public V setValue(V value) {
throw new UnsupportedOperationException();
@@ -664,7 +649,7 @@ public class ConcurrentSkipListMap
* @return a String representation of this entry.
*/
public String toString() {
- return getKey() + "=" + getValue();
+ return getKey() + "=" + getValue();
}
}
@@ -703,10 +688,10 @@ public class ConcurrentSkipListMap
* which is propagated back to caller.
*/
private Comparable comparable(Object key) throws ClassCastException {
- if (key == null)
+ if (key == null)
throw new NullPointerException();
- return (comparator != null)
- ? new ComparableUsingComparator(key, comparator)
+ return (comparator != null)
+ ? new ComparableUsingComparator(key, comparator)
: (Comparable)key;
}
@@ -724,10 +709,11 @@ 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)
+ if (key == null)
throw new NullPointerException();
return ((least == null || compare(key, least) >= 0) &&
(fence == null || compare(key, fence) < 0));
@@ -738,7 +724,7 @@ public class ConcurrentSkipListMap
* or equal to fence. Needed mainly in submap operations.
*/
boolean inOpenRange(K key, K least, K fence) {
- if (key == null)
+ if (key == null)
throw new NullPointerException();
return ((least == null || compare(key, least) >= 0) &&
(fence == null || compare(key, fence) <= 0));
@@ -752,7 +738,7 @@ public class ConcurrentSkipListMap
* unlinks indexes to deleted nodes found along the way. Callers
* rely on this side-effect of clearing indices to deleted nodes.
* @param key the key
- * @return a predecessor of key
+ * @return a predecessor of key
*/
private Node findPredecessor(Comparable key) {
for (;;) {
@@ -771,7 +757,7 @@ public class ConcurrentSkipListMap
continue;
}
}
- if ((d = q.down) != null)
+ if ((d = q.down) != null)
q = d;
else
return q.node;
@@ -801,7 +787,7 @@ public class ConcurrentSkipListMap
* here because doing so would not usually outweigh cost of
* restarting.
*
- * (3) n is a marker or n's predecessor's value field is null,
+ * (3) n is a marker or n's predecessor's value field is null,
* indicating (among other possibilities) that
* findPredecessor returned a deleted node. We can't unlink
* the node because we don't know its predecessor, so rely
@@ -814,12 +800,12 @@ 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.
- *
+ *
* @param key the key
* @return node holding key, or null if no such.
*/
@@ -828,7 +814,7 @@ public class ConcurrentSkipListMap
Node b = findPredecessor(key);
Node n = b.next;
for (;;) {
- if (n == null)
+ if (n == null)
return null;
Node f = n.next;
if (n != b.next) // inconsistent read
@@ -843,7 +829,7 @@ public class ConcurrentSkipListMap
int c = key.compareTo(n.key);
if (c < 0)
return null;
- if (c == 0)
+ if (c == 0)
return n;
b = n;
n = f;
@@ -851,8 +837,8 @@ public class ConcurrentSkipListMap
}
}
- /**
- * Specialized variant of findNode to perform map.get. Does a weak
+ /**
+ * Specialized variant of findNode to perform Map.get. Does a weak
* traversal, not bothering to fix any deleted index nodes,
* returning early if it happens to see key in index, and passing
* over any deleted base nodes, falling back to getUsingFindNode
@@ -870,7 +856,7 @@ public class ConcurrentSkipListMap
for (;;) {
K rk;
Index d, r;
- if ((r = q.right) != null &&
+ if ((r = q.right) != null &&
(rk = r.key) != null && rk != bound) {
int c = key.compareTo(rk);
if (c > 0) {
@@ -883,7 +869,7 @@ public class ConcurrentSkipListMap
}
bound = rk;
}
- if ((d = q.down) != null)
+ if ((d = q.down) != null)
q = d;
else {
for (Node n = q.node.next; n != null; n = n.next) {
@@ -910,8 +896,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)
@@ -927,7 +916,7 @@ public class ConcurrentSkipListMap
/**
* Main insertion method. Adds element if not present, or
* replaces value if present and onlyIfAbsent is false.
- * @param kkey the key
+ * @param kkey the key
* @param value the value that must be associated with key
* @param onlyIfAbsent if should not insert if already present
* @return the old value, or null if newly inserted
@@ -941,7 +930,7 @@ public class ConcurrentSkipListMap
if (n != null) {
Node f = n.next;
if (n != b.next) // inconsistent read
- break;;
+ break;
Object v = n.value;
if (v == null) { // n is deleted
n.helpDelete(b, f);
@@ -963,12 +952,12 @@ public class ConcurrentSkipListMap
}
// else c < 0; fall through
}
-
+
Node z = new Node(kkey, value, n);
- if (!b.casNext(n, z))
+ if (!b.casNext(n, z))
break; // restart if lost race to append to b
- int level = randomLevel();
- if (level > 0)
+ int level = randomLevel();
+ if (level > 0)
insertIndex(z, level);
return null;
}
@@ -990,8 +979,8 @@ public class ConcurrentSkipListMap
int level = 0;
int r = randomSeed;
randomSeed = r * 134775813 + 1;
- if (r < 0) {
- while ((r <<= 1) > 0)
+ if (r < 0) {
+ while ((r <<= 1) > 0)
++level;
}
return level;
@@ -1009,7 +998,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
@@ -1024,8 +1013,8 @@ public class ConcurrentSkipListMap
level = max + 1;
Index[] idxs = (Index[])new Index[level+1];
Index idx = null;
- for (int i = 1; i <= level; ++i)
- idxs[i] = idx = new Index(z, idx);
+ for (int i = 1; i <= level; ++i)
+ idxs[i] = idx = new Index(z, idx, null);
HeadIndex oldh;
int k;
@@ -1038,7 +1027,7 @@ public class ConcurrentSkipListMap
}
HeadIndex newh = oldh;
Node oldbase = oldh.node;
- for (int j = oldLevel+1; j <= level; ++j)
+ for (int j = oldLevel+1; j <= level; ++j)
newh = new HeadIndex(oldbase, newh, idxs[j], j);
if (casHead(oldh, newh)) {
k = oldLevel;
@@ -1076,7 +1065,7 @@ public class ConcurrentSkipListMap
if (q.unlink(r))
continue;
else
- break;
+ break;
}
if (c > 0) {
q = r;
@@ -1090,17 +1079,17 @@ public class ConcurrentSkipListMap
findNode(key); // cleans up
return;
}
- if (!q.link(r, t))
+ if (!q.link(r, t))
break; // restart
if (--insertionLevel == 0) {
// need final deletion check before return
- if (t.indexesDeletedNode())
- findNode(key);
+ if (t.indexesDeletedNode())
+ findNode(key);
return;
}
}
- if (j > insertionLevel && j <= indexLevel)
+ if (j > insertionLevel && j <= indexLevel)
t = t.down;
q = q.down;
--j;
@@ -1115,14 +1104,14 @@ public class ConcurrentSkipListMap
* deletion marker, unlinks predecessor, removes associated index
* nodes, and possibly reduces head index level.
*
- * Index node are cleared out simply by calling findPredecessor.
+ * Index nodes are cleared out simply by calling findPredecessor.
* which unlinks indexes to deleted nodes found along path to key,
* which will include the indexes to this node. This is done
* unconditionally. We can't check beforehand whether there are
* index nodes because it might be the case that some or all
* indexes hadn't been inserted yet for this node during initial
* search for it, and we'd like to ensure lack of garbage
- * retention, so must call to be sure.
+ * retention, so must call to be sure.
*
* @param okey the key
* @param value if non-null, the value that must be
@@ -1131,11 +1120,11 @@ public class ConcurrentSkipListMap
*/
private V doRemove(Object okey, Object value) {
Comparable key = comparable(okey);
- for (;;) {
+ for (;;) {
Node b = findPredecessor(key);
Node n = b.next;
for (;;) {
- if (n == null)
+ if (n == null)
return null;
Node f = n.next;
if (n != b.next) // inconsistent read
@@ -1155,15 +1144,15 @@ public class ConcurrentSkipListMap
n = f;
continue;
}
- if (value != null && !value.equals(v))
- return null;
- if (!n.casValue(v, null))
+ if (value != null && !value.equals(v))
+ return null;
+ if (!n.casValue(v, null))
break;
- if (!n.appendMarker(f) || !b.casNext(n, f))
+ if (!n.appendMarker(f) || !b.casNext(n, f))
findNode(key); // Retry via findNode
else {
findPredecessor(key); // Clean index
- if (head.right == null)
+ if (head.right == null)
tryReduceLevel();
}
return (V)v;
@@ -1175,8 +1164,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
@@ -1196,75 +1185,52 @@ public class ConcurrentSkipListMap
HeadIndex d;
HeadIndex e;
if (h.level > 3 &&
- (d = (HeadIndex)h.down) != null &&
- (e = (HeadIndex)d.down) != null &&
- e.right == null &&
- d.right == null &&
+ (d = (HeadIndex)h.down) != null &&
+ (e = (HeadIndex)d.down) != null &&
+ e.right == null &&
+ d.right == null &&
h.right == null &&
casHead(h, d) && // try to set
h.right != null) // recheck
casHead(d, h); // try to backout
}
+ /**
+ * Version of remove with boolean return. Needed by view classes
+ */
+ boolean removep(Object key) {
+ return doRemove(key, null) != null;
+ }
- /* ---------------- 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)
return null;
- if (n.value != null)
+ if (n.value != null)
return n;
n.helpDelete(b, n.next);
}
}
/**
- * 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
- */
- for (;;) {
+ Object doRemoveFirst(boolean keyOnly) {
+ for (;;) {
Node b = head.node;
Node n = b.next;
- if (n == null)
+ if (n == null)
return null;
Node f = n.next;
if (n != b.next)
@@ -1279,13 +1245,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 (;;) {
@@ -1293,9 +1260,9 @@ public class ConcurrentSkipListMap
for (;;) {
Index r = q.right;
if (r != null && r.indexesDeletedNode() && !q.unlink(r))
- break;
+ break;
if ((q = q.down) == null) {
- if (head.right == null)
+ if (head.right == null)
tryReduceLevel();
return;
}
@@ -1303,6 +1270,15 @@ public class ConcurrentSkipListMap
}
}
+ /**
+ * Remove first entry; return key or null if empty.
+ */
+ K pollFirstKey() {
+ return (K)doRemoveFirst(true);
+ }
+
+ /* ---------------- Finding and removing last element -------------- */
+
/**
* Specialized version of find to get last valid node
* @return last node or null if empty
@@ -1320,7 +1296,7 @@ public class ConcurrentSkipListMap
if (r.indexesDeletedNode()) {
q.unlink(r);
q = head; // restart
- }
+ }
else
q = r;
} else if ((d = q.down) != null) {
@@ -1329,7 +1305,7 @@ public class ConcurrentSkipListMap
Node b = q.node;
Node n = b.next;
for (;;) {
- if (n == null)
+ if (n == null)
return (b.isBaseHeader())? null : b;
Node f = n.next; // inconsistent read
if (n != b.next)
@@ -1349,13 +1325,99 @@ 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;
+ }
+ }
+ }
+
+ /**
+ * Remove last entry; return key or null if empty.
+ */
+ K pollLastKey() {
+ return (K)doRemoveLast(true);
+ }
+
/* ---------------- Relational operations -------------- */
// Control values OR'ed as arguments to findNear
private static final int EQ = 1;
private static final int LT = 2;
- private static final int GT = 0;
+ private static final int GT = 0; // Actually checked as !LT
/**
* Utility for ceiling, floor, lower, higher methods.
@@ -1369,7 +1431,7 @@ public class ConcurrentSkipListMap
Node b = findPredecessor(key);
Node n = b.next;
for (;;) {
- if (n == null)
+ if (n == null)
return ((rel & LT) == 0 || b.isBaseHeader())? null : b;
Node f = n.next;
if (n != b.next) // inconsistent read
@@ -1410,11 +1472,98 @@ public class ConcurrentSkipListMap
}
}
+ /**
+ * 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
+ */
+ Node findLower(K key) {
+ return (key == null)? findLast() : findNear(key, LT);
+ }
+
+ /**
+ * Return SnapshotEntry or key 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
+ * @param keyOnly if true return key, else return SnapshotEntry
+ * @return Key or Entry fitting relation, or null if no such
+ */
+ Object getNear(K kkey, int rel, K least, K fence, boolean keyOnly) {
+ K key = kkey;
+ // Don't return keys less than least
+ if ((rel & LT) == 0) {
+ if (compare(key, least) < 0) {
+ key = least;
+ rel = rel | EQ;
+ }
+ }
+
+ for (;;) {
+ Node n = findNear(key, rel);
+ if (n == null || !inHalfOpenRange(n.key, least, fence))
+ return null;
+ K k = n.key;
+ V v = n.getValidValue();
+ if (v != null)
+ return keyOnly? k : new SnapshotEntry(k, v);
+ }
+ }
+
+ /**
+ * Find and remove least element of subrange.
+ * @param least minimum allowed key value
+ * @param fence key greater than maximum allowed key value
+ * @param keyOnly if true return key, else return SnapshotEntry
+ * @return least Key or Entry, or null if no such
+ */
+ Object removeFirstEntryOfSubrange(K least, K fence, boolean keyOnly) {
+ for (;;) {
+ Node n = findCeiling(least);
+ if (n == null)
+ return null;
+ K k = n.key;
+ if (fence != null && compare(k, fence) >= 0)
+ return null;
+ V v = doRemove(k, null);
+ if (v != null)
+ return (keyOnly)? k : new SnapshotEntry(k, v);
+ }
+ }
+
+ /**
+ * Find and remove greatest element of subrange.
+ * @param least minimum allowed key value
+ * @param fence key greater than maximum allowed key value
+ * @param keyOnly if true return key, else return SnapshotEntry
+ * @return least Key or Entry, or null if no such
+ */
+ Object removeLastEntryOfSubrange(K least, K fence, boolean keyOnly) {
+ 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 (keyOnly)? k : new SnapshotEntry(k, v);
+ }
+ }
+
/* ---------------- Constructors -------------- */
/**
* Constructs a new empty map, sorted according to the keys' natural
- * order.
+ * order.
*/
public ConcurrentSkipListMap() {
this.comparator = null;
@@ -1435,12 +1584,12 @@ public class ConcurrentSkipListMap
/**
* Constructs a new map containing the same mappings as the given map,
- * sorted according to the keys' natural order.
+ * sorted according to the keys' natural order.
*
* @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 extends K, ? extends V> m) {
this.comparator = null;
@@ -1450,10 +1599,11 @@ 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.
+ * 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.
*/
public ConcurrentSkipListMap(SortedMap m) {
this.comparator = m.comparator();
@@ -1497,7 +1647,7 @@ public class ConcurrentSkipListMap
ArrayList> preds = new ArrayList>();
// initialize
- for (int i = 0; i <= h.level; ++i)
+ for (int i = 0; i <= h.level; ++i)
preds.add(null);
Index q = h;
for (int i = h.level; i > 0; --i) {
@@ -1505,7 +1655,7 @@ public class ConcurrentSkipListMap
q = q.down;
}
- Iterator extends Map.Entry extends K, ? extends V>> it =
+ Iterator extends Map.Entry extends K, ? extends V>> it =
map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry extends K, ? extends V> e = it.next();
@@ -1521,8 +1671,8 @@ public class ConcurrentSkipListMap
if (j > 0) {
Index idx = null;
for (int i = 1; i <= j; ++i) {
- idx = new Index(z, idx);
- if (i > h.level)
+ idx = new Index(z, idx, null);
+ if (i > h.level)
h = new HeadIndex(h.node, h, idx, i);
if (i < preds.size()) {
@@ -1542,7 +1692,7 @@ public class ConcurrentSkipListMap
* Save the state of the Map instance to a stream.
*
* @serialData The key (Object) and value (Object) for each
- * key-value mapping represented by the Map, followed by
+ * key-value mapping represented by the Map, followed by
* null. The key-value mappings are emitted in key-order
* (as determined by the Comparator, or by the keys' natural
* ordering if no Comparator).
@@ -1573,8 +1723,8 @@ public class ConcurrentSkipListMap
// Reset transients
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
@@ -1584,7 +1734,7 @@ public class ConcurrentSkipListMap
HeadIndex h = head;
Node basepred = h.node;
ArrayList> preds = new ArrayList>();
- for (int i = 0; i <= h.level; ++i)
+ for (int i = 0; i <= h.level; ++i)
preds.add(null);
Index q = h;
for (int i = h.level; i > 0; --i) {
@@ -1597,7 +1747,7 @@ public class ConcurrentSkipListMap
if (k == null)
break;
Object v = s.readObject();
- if (v == null)
+ if (v == null)
throw new NullPointerException();
K key = (K) k;
V val = (V) v;
@@ -1609,8 +1759,8 @@ public class ConcurrentSkipListMap
if (j > 0) {
Index idx = null;
for (int i = 1; i <= j; ++i) {
- idx = new Index(z, idx);
- if (i > h.level)
+ idx = new Index(z, idx, null);
+ if (i > h.level)
h = new HeadIndex(h.node, h, idx, i);
if (i < preds.size()) {
@@ -1642,7 +1792,7 @@ public class ConcurrentSkipListMap
/**
* Returns the value to which this map maps the specified key. Returns
- * null if the map contains no mapping for this key.
+ * 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
@@ -1664,13 +1814,13 @@ public class ConcurrentSkipListMap
* @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.
+ * 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 or value are null.
*/
public V put(K key, V value) {
- if (value == null)
+ if (value == null)
throw new NullPointerException();
return doPut(key, value, false);
}
@@ -1680,7 +1830,7 @@ public class ConcurrentSkipListMap
*
* @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.
+ * if there was no mapping for key.
*
* @throws ClassCastException if the key cannot be compared with the keys
* currently in the map.
@@ -1697,11 +1847,11 @@ public class ConcurrentSkipListMap
*
* @param value value whose presence in this Map is to be tested.
* @return true if a mapping to value exists;
- * false otherwise.
+ * false otherwise.
* @throws NullPointerException if the value is null.
- */
+ */
public boolean containsValue(Object value) {
- if (value == null)
+ if (value == null)
throw new NullPointerException();
for (Node n = findFirst(); n != null; n = n.next) {
V v = n.getValidValue();
@@ -1782,6 +1932,37 @@ public class ConcurrentSkipListMap
}
/**
+ * Returns a set view of the keys contained in this map in
+ * descending order. 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 descendingKeySet() {
+ /*
+ * Note: Lazy intialization works here and for other views
+ * because view classes are stateless/immutable so it doesn't
+ * matter wrt correctness if more than one is created (which
+ * will only rarely happen). Even so, the following idiom
+ * conservatively ensures that the method returns the one it
+ * created if it does so, not one created by another racing
+ * thread.
+ */
+ DescendingKeySet ks = descendingKeySet;
+ return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
+ }
+
+ /**
* 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
@@ -1831,6 +2012,80 @@ public class ConcurrentSkipListMap
return (es != null) ? es : (entrySet = new EntrySet());
}
+ /**
+ * Returns a collection view of the mappings contained in this
+ * map, in descending order. 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> descendingEntrySet() {
+ DescendingEntrySet es = descendingEntrySet;
+ return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
+ }
+
+ /* ---------------- 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 ------ */
/**
@@ -1838,23 +2093,23 @@ public class ConcurrentSkipListMap
* with a value, associate it with the given value.
* This is equivalent to
*
- * if (!map.containsKey(key))
+ * if (!map.containsKey(key))
* return map.put(key, value);
* 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
- * if there was no mapping for key.
+ * 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 or value are null.
*/
public V putIfAbsent(K key, V value) {
- if (value == null)
+ if (value == null)
throw new NullPointerException();
return doPut(key, value, true);
}
@@ -1862,7 +2117,7 @@ public class ConcurrentSkipListMap
/**
* 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;
@@ -1877,7 +2132,7 @@ public class ConcurrentSkipListMap
* @throws NullPointerException if the key or value are null.
*/
public boolean remove(Object key, Object value) {
- if (value == null)
+ if (value == null)
throw new NullPointerException();
return doRemove(key, value) != null;
}
@@ -1885,7 +2140,7 @@ public class ConcurrentSkipListMap
/**
* 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;
@@ -1902,7 +2157,7 @@ public class ConcurrentSkipListMap
* null.
*/
public boolean replace(K key, V oldValue, V newValue) {
- if (oldValue == null || newValue == null)
+ if (oldValue == null || newValue == null)
throw new NullPointerException();
Comparable k = comparable(key);
for (;;) {
@@ -1922,7 +2177,7 @@ public class ConcurrentSkipListMap
/**
* 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;
@@ -1931,13 +2186,13 @@ public class ConcurrentSkipListMap
* @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.
+ * 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 or value are null.
*/
public V replace(K key, V value) {
- if (value == null)
+ if (value == null)
throw new NullPointerException();
Comparable k = comparable(key);
for (;;) {
@@ -1969,7 +2224,7 @@ public class ConcurrentSkipListMap
* @return the first (lowest) key currently in this map.
* @throws NoSuchElementException Map is empty.
*/
- public K firstKey() {
+ public K firstKey() {
Node n = findFirst();
if (n == null)
throw new NoSuchElementException();
@@ -2010,27 +2265,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 +2297,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 +2315,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) {
@@ -2075,14 +2331,30 @@ public class ConcurrentSkipListMap
}
/**
+ * Returns least key greater than or equal to the given key, or
+ * null if there is no such key.
+ *
+ * @param key the key.
+ * @return the ceiling key, or null
+ * if there is no such key.
+ * @throws ClassCastException if key cannot be compared with the keys
+ * currently in the map.
+ * @throws NullPointerException if key is null.
+ */
+ public K ceilingKey(K key) {
+ Node n = findNear(key, GT|EQ);
+ return (n == null)? null : n.key;
+ }
+
+ /**
* 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 +2364,29 @@ 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 the greatest key strictly less than the given key, or
+ * null if there is no such key.
+ *
+ * @param key the key.
+ * @return the greatest key less than the given
+ * key, or null if there is no such key.
+ * @throws ClassCastException if key cannot be compared with the keys
+ * currently in the map.
+ * @throws NullPointerException if key is null.
+ */
+ public K lowerKey(K key) {
+ Node n = findNear(key, LT);
+ return (n == null)? null : n.key;
+ }
+
+ /**
+ * 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 +2397,31 @@ 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 the greatest key
+ * less than or equal to the given key, or null if there
+ * is no such key.
+ *
+ * @param key the key.
+ * @return the floor of given key, or null if there is no
+ * such key.
+ * @throws ClassCastException if key cannot be compared with the keys
+ * currently in the map.
+ * @throws NullPointerException if key is null.
+ */
+ public K floorKey(K key) {
+ Node n = findNear(key, LT|EQ);
+ return (n == null)? null : n.key;
+ }
+
+ /**
+ * 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.
@@ -2126,18 +2431,34 @@ public class ConcurrentSkipListMap
}
/**
+ * Returns the least key strictly greater than the given key, or
+ * null if there is no such key.
+ *
+ * @param key the key.
+ * @return the least key greater than the given key, or
+ * null if there is no such key.
+ * @throws ClassCastException if key cannot be compared with the keys
+ * currently in the map.
+ * @throws NullPointerException if key is null.
+ */
+ public K higherKey(K key) {
+ Node n = findNear(key, GT);
+ return (n == null)? null : n.key;
+ }
+
+ /**
* 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() {
for (;;) {
Node n = findFirst();
- if (n == null)
+ if (n == null)
return null;
SnapshotEntry e = n.createSnapshot();
if (e != null)
@@ -2147,17 +2468,17 @@ 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() {
for (;;) {
Node n = findLast();
- if (n == null)
+ if (n == null)
return null;
SnapshotEntry e = n.createSnapshot();
if (e != null)
@@ -2167,35 +2488,90 @@ 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