--- jsr166/src/jsr166x/ConcurrentSkipListMap.java 2004/09/06 17:01:54 1.2 +++ jsr166/src/jsr166x/ConcurrentSkipListMap.java 2010/09/01 20:12:39 1.10 @@ -4,7 +4,7 @@ * http://creativecommons.org/licenses/publicdomain */ -package jsr166x; +package jsr166x; import java.util.*; import java.util.concurrent.*; @@ -27,9 +27,10 @@ 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. * - *

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 @@ -39,7 +40,12 @@ import java.util.concurrent.atomic.*; *

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} @@ -50,11 +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 +public class ConcurrentSkipListMap extends AbstractMap implements ConcurrentNavigableMap, - Cloneable, + Cloneable, java.io.Serializable { /* * This class implements a tree-like two-dimensionally linked skip @@ -68,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. * @@ -138,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 @@ -154,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 @@ -181,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 @@ -259,8 +266,8 @@ 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/), Keir Fraser's thesis - * (http://www.cl.cam.ac.uk/users/kaf24/), and papers by - * Håkan Sundell (http://www.cs.chalmers.se/~phs/). + * (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 @@ -285,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; @@ -312,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, @@ -320,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"); @@ -377,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 */ @@ -454,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. */ @@ -495,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; @@ -514,7 +517,7 @@ public class ConcurrentSkipListMap } /** Updater for casRight */ - static final AtomicReferenceFieldUpdater + static final AtomicReferenceFieldUpdater rightUpdater = AtomicReferenceFieldUpdater.newUpdater (Index.class, Index.class, "right"); @@ -543,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); } @@ -566,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 -------------- */ @@ -579,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. @@ -590,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(); @@ -647,7 +649,7 @@ public class ConcurrentSkipListMap * @return a String representation of this entry. */ public String toString() { - return getKey() + "=" + getValue(); + return getKey() + "=" + getValue(); } } @@ -686,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; } @@ -707,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)); @@ -721,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)); @@ -735,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 (;;) { @@ -754,7 +757,7 @@ public class ConcurrentSkipListMap continue; } } - if ((d = q.down) != null) + if ((d = q.down) != null) q = d; else return q.node; @@ -784,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 @@ -797,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. */ @@ -811,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 @@ -826,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; @@ -834,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 @@ -853,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) { @@ -866,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) { @@ -893,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) @@ -910,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 @@ -924,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); @@ -946,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; } @@ -973,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; @@ -992,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 @@ -1007,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; @@ -1021,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; @@ -1059,7 +1065,7 @@ public class ConcurrentSkipListMap if (q.unlink(r)) continue; else - break; + break; } if (c > 0) { q = r; @@ -1073,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; @@ -1098,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 @@ -1114,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 @@ -1138,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; @@ -1158,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 @@ -1179,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 + * 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 */ - 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. - */ - 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) @@ -1262,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 (;;) { @@ -1276,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; } @@ -1286,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 @@ -1303,7 +1296,7 @@ public class ConcurrentSkipListMap if (r.indexesDeletedNode()) { q.unlink(r); q = head; // restart - } + } else q = r; } else if ((d = q.down) != null) { @@ -1312,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) @@ -1332,19 +1325,23 @@ public class ConcurrentSkipListMap } } + /** - * Temporary helper method for two-pass implementation of - * removeLastEntry, mostly pasted from doRemove. - * TODO: replace with one-pass implementation + * 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 */ - private Object removeIfLast(K kkey) { - Comparable key = comparable(kkey); - for (;;) { - Node b = findPredecessor(key); + Object doRemoveLast(boolean keyOnly) { + for (;;) { + Node b = findPredecessorOfLast(); Node n = b.next; - for (;;) { - if (n == null) + 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; @@ -1355,57 +1352,63 @@ public class ConcurrentSkipListMap } if (v == n || b.value == null) // b is deleted break; - int c = key.compareTo(n.key); - if (c < 0) - return null; - if (c > 0) { + if (f != null) { b = n; n = f; continue; } - if (f != null) // fail if n not last - return null; - if (!n.casValue(v, null)) - return null; - if (!n.appendMarker(f) || !b.casNext(n, f)) - findNode(key); // Retry via findNode + 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(key); // Clean index - if (head.right == null) + findPredecessor(ck); // Clean index + if (head.right == null) tryReduceLevel(); } - return v; + return (keyOnly)? key : new SnapshotEntry(key, (V)v); } } } /** - * Remove last entry; return SnapshotEntry or null if empty. + * 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 SnapshotEntry doRemoveLastEntry() { + private Node findPredecessorOfLast() { for (;;) { - Node l = findLast(); - if (l == null) - return null; - K k = l.key; - Object v = removeIfLast(k); - if (v != null) - return new SnapshotEntry(k, (V)v); + 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. + * Remove last entry; return key or null if empty. */ - K removeLastKey() { - for (;;) { - Node l = findLast(); - if (l == null) - return null; - K k = l.key; - if (removeIfLast(k) != null) - return k; - } + K pollLastKey() { + return (K)doRemoveLast(true); } /* ---------------- Relational operations -------------- */ @@ -1414,7 +1417,7 @@ public class ConcurrentSkipListMap 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. @@ -1428,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 @@ -1469,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; @@ -1494,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 m) { this.comparator = null; @@ -1509,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(); @@ -1556,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) { @@ -1564,7 +1655,7 @@ public class ConcurrentSkipListMap q = q.down; } - Iterator> it = + Iterator> it = map.entrySet().iterator(); while (it.hasNext()) { Map.Entry e = it.next(); @@ -1580,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()) { @@ -1601,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). @@ -1632,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 @@ -1643,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) { @@ -1656,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; @@ -1668,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()) { @@ -1701,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 @@ -1723,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); } @@ -1739,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. @@ -1756,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(); @@ -1841,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 @@ -1890,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 ------ */ /** @@ -1897,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); } @@ -1921,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;
@@ -1936,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;
     }
@@ -1944,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;
@@ -1961,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 (;;) {
@@ -1981,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;
@@ -1990,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 (;;) {
@@ -2028,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();
@@ -2076,17 +2272,17 @@ public class ConcurrentSkipListMap
     }
 
     /**
-     * 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 ConcurrentNavigableMap headMap(K toKey) {
@@ -2101,11 +2297,12 @@ 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 ConcurrentNavigableMap  tailMap(K fromKey) {
@@ -2118,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) {
@@ -2134,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.
@@ -2151,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.
@@ -2168,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.
@@ -2185,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)
@@ -2206,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)
@@ -2226,48 +2488,56 @@ 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 pollFirstEntry() {
-        return doRemoveFirstEntry();
+        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 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
+     *
+     * @return the removed last entry of this map, or null
      * if the map is empty.
      */
     public Map.Entry pollLastEntry() {
-        return doRemoveLastEntry();
+        return (SnapshotEntry)doRemoveLast(false);
     }
 
+
     /* ---------------- Iterators -------------- */
 
     /**
-     * Base of iterator classes.
-     * (Six kinds: {key, value, entry} X {map, submap})
+     * Base of ten kinds of iterator classes:
+     *   ascending:  {map, submap} X {key, value, entry}
+     *   descending: {map, submap} X {key, entry}
      */
-    abstract class ConcurrentSkipListMapIterator {
+    abstract class Iter {
         /** the last node returned by next() */
         Node last;
         /** the next node to return from next(); */
         Node next;
-	/** Cache of next value field to maintain weak consistency */
-	Object nextValue;
+        /** Cache of next value field to maintain weak consistency */
+        Object nextValue;
+
+        Iter() {}
+
+        public final boolean hasNext() {
+            return next != null;
+        }
 
-        /** Create normal iterator for entire range  */
-        ConcurrentSkipListMapIterator() {
+        /** initialize ascending iterator for entire range  */
+        final void initAscending() {
             for (;;) {
-		next = findFirst();
+                next = findFirst();
                 if (next == null)
                     break;
                 nextValue = next.value;
@@ -2276,14 +2546,14 @@ 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.
+        /**
+         * initialize ascending 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.
          */
-        ConcurrentSkipListMapIterator(K least, K fence) { 
+        final void initAscending(K least, K fence) {
             for (;;) {
-		next = findCeiling(least);
+                next = findCeiling(least);
                 if (next == null)
                     break;
                 nextValue = next.value;
@@ -2296,16 +2566,82 @@ public class ConcurrentSkipListMap
                 }
             }
         }
+        /** advance next to higher entry */
+        final void ascend() {
+            if ((last = next) == null)
+                throw new NoSuchElementException();
+            for (;;) {
+                next = next.next;
+                if (next == null)
+                    break;
+                nextValue = next.value;
+                if (nextValue != null && nextValue != next)
+                    break;
+            }
+        }
 
-        public final boolean hasNext() { 
-            return next != null; 
+        /**
+         * Version of ascend for submaps to stop at fence
+         */
+        final void ascend(K fence) {
+            if ((last = next) == null)
+                throw new NoSuchElementException();
+            for (;;) {
+                next = next.next;
+                if (next == null)
+                    break;
+                nextValue = next.value;
+                if (nextValue != null && nextValue != next) {
+                    if (fence != null && compare(fence, next.key) <= 0) {
+                        next = null;
+                        nextValue = null;
+                    }
+                    break;
+                }
+            }
         }
 
-        final void advance() {
+        /** initialize descending iterator for entire range  */
+        final void initDescending() {
+            for (;;) {
+                next = findLast();
+                if (next == null)
+                    break;
+                nextValue = next.value;
+                if (nextValue != null && nextValue != next)
+                    break;
+            }
+        }
+
+        /**
+         * initialize descending iterator starting at key less
+         * than or equal to given fence key, or
+         * last node if fence is null, but not less than
+         * least, or beginning if lest is null.
+         */
+        final void initDescending(K least, K fence) {
+            for (;;) {
+                next = findLower(fence);
+                if (next == null)
+                    break;
+                nextValue = next.value;
+                if (nextValue != null && nextValue != next) {
+                    if (least != null && compare(least, next.key) > 0) {
+                        next = null;
+                        nextValue = null;
+                    }
+                    break;
+                }
+            }
+        }
+
+        /** advance next to lower entry */
+        final void descend() {
             if ((last = next) == null)
                 throw new NoSuchElementException();
+            K k = last.key;
             for (;;) {
-		next = next.next;
+                next = findNear(k, LT);
                 if (next == null)
                     break;
                 nextValue = next.value;
@@ -2315,18 +2651,19 @@ public class ConcurrentSkipListMap
         }
 
         /**
-         * Version of advance for submaps to stop at fence
+         * Version of descend for submaps to stop at least
          */
-        final void advance(K fence) {
+        final void descend(K least) {
             if ((last = next) == null)
                 throw new NoSuchElementException();
+            K k = last.key;
             for (;;) {
-		next = next.next;
+                next = findNear(k, LT);
                 if (next == null)
                     break;
                 nextValue = next.value;
                 if (nextValue != null && nextValue != next) {
-                    if (fence != null && compare(fence, next.key) <= 0) {
+                    if (least != null && compare(least, next.key) > 0) {
                         next = null;
                         nextValue = null;
                     }
@@ -2343,22 +2680,80 @@ public class ConcurrentSkipListMap
             // unlink from here. Using remove is fast enough.
             ConcurrentSkipListMap.this.remove(l.key);
         }
+
     }
 
-    final class ValueIterator extends ConcurrentSkipListMapIterator 
-        implements Iterator {
-        public V next() { 
+    final class ValueIterator extends Iter implements Iterator {
+        ValueIterator() {
+            initAscending();
+        }
+        public V next() {
             Object v = nextValue;
-            advance();
+            ascend();
             return (V)v;
         }
     }
 
-    final class KeyIterator extends ConcurrentSkipListMapIterator 
-        implements Iterator {
-        public K next() { 
+    final class KeyIterator extends Iter implements Iterator {
+        KeyIterator() {
+            initAscending();
+        }
+        public K next() {
+            Node n = next;
+            ascend();
+            return n.key;
+        }
+    }
+
+    class SubMapValueIterator extends Iter implements Iterator {
+        final K fence;
+        SubMapValueIterator(K least, K fence) {
+            initAscending(least, fence);
+            this.fence = fence;
+        }
+
+        public V next() {
+            Object v = nextValue;
+            ascend(fence);
+            return (V)v;
+        }
+    }
+
+    final class SubMapKeyIterator extends Iter implements Iterator {
+        final K fence;
+        SubMapKeyIterator(K least, K fence) {
+            initAscending(least, fence);
+            this.fence = fence;
+        }
+
+        public K next() {
+            Node n = next;
+            ascend(fence);
+            return n.key;
+        }
+    }
+
+    final class DescendingKeyIterator extends Iter implements Iterator {
+        DescendingKeyIterator() {
+            initDescending();
+        }
+        public K next() {
             Node n = next;
-            advance();
+            descend();
+            return n.key;
+        }
+    }
+
+    final class DescendingSubMapKeyIterator extends Iter implements Iterator {
+        final K least;
+        DescendingSubMapKeyIterator(K least, K fence) {
+            initDescending(least, fence);
+            this.least = least;
+        }
+
+        public K next() {
+            Node n = next;
+            descend(least);
             return n.key;
         }
     }
@@ -2368,23 +2763,11 @@ public class ConcurrentSkipListMap
      * elsewhere of using the iterator itself to represent entries,
      * thus avoiding having to create entry objects in next().
      */
-    class EntryIterator extends ConcurrentSkipListMapIterator 
-        implements Map.Entry, Iterator>  {
+    abstract class EntryIter extends Iter implements Map.Entry {
         /** Cache of last value returned */
         Object lastValue;
 
-        EntryIterator() { 
-            super(); 
-        }
-
-        EntryIterator(K least, K fence) { 
-            super(least, fence); 
-        }
-
-        public Map.Entry next() { 
-            lastValue = nextValue;
-            advance();
-            return this;
+        EntryIter() {
         }
 
         public K getKey() {
@@ -2398,7 +2781,7 @@ public class ConcurrentSkipListMap
             Object v = lastValue;
             if (last == null || v == null)
                 throw new IllegalStateException();
-	    return (V)v;
+            return (V)v;
         }
 
         public V setValue(V value) {
@@ -2427,60 +2810,64 @@ public class ConcurrentSkipListMap
             // If not acting as entry, just use default.
             if (last == null)
                 return super.toString();
-	    return getKey() + "=" + getValue();
+            return getKey() + "=" + getValue();
         }
     }
 
-    /**
-     * Submap iterators start at given starting point at beginning of
-     * submap range, and advance until they are at end of range.
-     */
-    class SubMapEntryIterator extends EntryIterator {
+    final class EntryIterator extends EntryIter
+        implements Iterator> {
+        EntryIterator() {
+            initAscending();
+        }
+        public Map.Entry next() {
+            lastValue = nextValue;
+            ascend();
+            return this;
+        }
+    }
+
+    final class SubMapEntryIterator extends EntryIter
+        implements Iterator> {
         final K fence;
         SubMapEntryIterator(K least, K fence) {
-            super(least, fence);
+            initAscending(least, fence);
             this.fence = fence;
         }
 
-        public Map.Entry next() { 
+        public Map.Entry next() {
             lastValue = nextValue;
-            advance(fence);
+            ascend(fence);
             return this;
         }
     }
 
-    class SubMapValueIterator extends ConcurrentSkipListMapIterator 
-        implements Iterator {
-        final K fence;
-        SubMapValueIterator(K least, K fence) {
-            super(least, fence);
-            this.fence = fence;
+    final class DescendingEntryIterator extends EntryIter
+        implements Iterator>  {
+        DescendingEntryIterator() {
+            initDescending();
         }
-
-        public V next() { 
-            Object v = nextValue;
-            advance(fence);
-            return (V)v;
+        public Map.Entry next() {
+            lastValue = nextValue;
+            descend();
+            return this;
         }
     }
 
-    class SubMapKeyIterator extends ConcurrentSkipListMapIterator 
-        implements Iterator {
-        final K fence;
-        SubMapKeyIterator(K least, K fence) {
-            super(least, fence);
-            this.fence = fence;
+    final class DescendingSubMapEntryIterator extends EntryIter
+        implements Iterator>  {
+        final K least;
+        DescendingSubMapEntryIterator(K least, K fence) {
+            initDescending(least, fence);
+            this.least = least;
         }
 
-        public K next() { 
-            Node n = next;
-            advance(fence);
-            return n.key;
+        public Map.Entry next() {
+            lastValue = nextValue;
+            descend(least);
+            return this;
         }
     }
 
-    /* ---------------- Utilities for views, sets, submaps -------------- */
-    
     // Factory methods for iterators needed by submaps and/or
     // ConcurrentSkipListSet
 
@@ -2488,159 +2875,33 @@ public class ConcurrentSkipListMap
         return new KeyIterator();
     }
 
-    SubMapEntryIterator subMapEntryIterator(K least, K fence) {
-        return new SubMapEntryIterator(least, fence);
-    }
-
-    SubMapKeyIterator subMapKeyIterator(K least, K fence) {
-        return new SubMapKeyIterator(least, fence);
-    }
-
-    SubMapValueIterator subMapValueIterator(K least, K fence) {
-        return new SubMapValueIterator(least, fence);
-    }
-
-
-    /**
-     * Version of remove with boolean return. Needed by 
-     * view classes and ConcurrentSkipListSet
-     */
-    boolean removep(Object key) {
-        return doRemove(key, null) != null;
-    }
-
-    /**
-     * 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
-     */
-    SnapshotEntry getNear(K kkey, int rel, K least, K fence) {
-        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;
-            SnapshotEntry e = n.createSnapshot();
-            if (e != null)
-                return e;
-        }
-    }
-
-    // Methods expanding out relational operations for submaps
-
-    /**
-     * 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);
-    }
-
-    /**
-     * Find and remove least element of subrange.
-     */
-    SnapshotEntry removeFirstEntryOfSubrange(K least, K fence) {
-        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 new SnapshotEntry(k,v);
-        }
-    }
-
-
-    /**
-     * 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);
-    }
-
-    SnapshotEntry getLower(K key, K least, K fence) {
-        return getNear(key, LT, least, fence);
-    }
-
-    SnapshotEntry getFloor(K key, K least, K fence) {
-        return getNear(key, LT|EQ, least, fence);
-    }
-
-    SnapshotEntry getHigher(K key, K least, K fence) {
-        return getNear(key, GT, least, fence);
-    }
-
-    // Key-returning relational methods for ConcurrentSkipListSet
-
-    K ceilingKey(K key) {
-        Node n = findNear(key, GT|EQ);
-        return (n == null)? null : n.key;
+    Iterator descendingKeyIterator() {
+        return new DescendingKeyIterator();
     }
 
-    K lowerKey(K key) {
-        Node n = findNear(key, LT);
-        return (n == null)? null : n.key;
+    SubMapEntryIterator subMapEntryIterator(K least, K fence) {
+        return new SubMapEntryIterator(least, fence);
     }
 
-    K floorKey(K key) {
-        Node n = findNear(key, LT|EQ);
-        return (n == null)? null : n.key;
+    DescendingSubMapEntryIterator descendingSubMapEntryIterator(K least, K fence) {
+        return new DescendingSubMapEntryIterator(least, fence);
     }
 
-    K higherKey(K key) {
-        Node n = findNear(key, GT);
-        return (n == null)? null : n.key;
+    SubMapKeyIterator subMapKeyIterator(K least, K fence) {
+        return new SubMapKeyIterator(least, fence);
     }
 
-    K lowestKey() { 
-        Node n = findFirst();
-        return (n == null)? null : n.key;
+    DescendingSubMapKeyIterator descendingSubMapKeyIterator(K least, K fence) {
+        return new DescendingSubMapKeyIterator(least, fence);
     }
 
-    K highestKey() { 
-        Node n = findLast();
-        return (n == null)? null : n.key;
+    SubMapValueIterator subMapValueIterator(K least, K fence) {
+        return new SubMapValueIterator(least, fence);
     }
 
     /* ---------------- Views -------------- */
 
-    final class KeySet extends AbstractSet {
+    class KeySet extends AbstractSet {
         public Iterator iterator() {
             return new KeyIterator();
         }
@@ -2673,6 +2934,11 @@ public class ConcurrentSkipListMap
         }
     }
 
+    class DescendingKeySet extends KeySet {
+        public Iterator iterator() {
+            return new DescendingKeyIterator();
+        }
+    }
 
     final class Values extends AbstractCollection {
         public Iterator iterator() {
@@ -2704,7 +2970,7 @@ public class ConcurrentSkipListMap
         }
     }
 
-    final class EntrySet extends AbstractSet> {
+    class EntrySet extends AbstractSet> {
         public Iterator> iterator() {
             return new EntryIterator();
         }
@@ -2719,7 +2985,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();
@@ -2733,24 +3000,24 @@ public class ConcurrentSkipListMap
 
         public Object[] toArray() {
             Collection> c = new ArrayList>();
-            for (Node n = findFirst(); n != null; n = n.next) {
-                Map.Entry e = n.createSnapshot();
-                if (e != null) 
-                    c.add(e);
-            }
+            for (Map.Entry e : this)
+                c.add(new SnapshotEntry(e.getKey(), e.getValue()));
             return c.toArray();
         }
         public  T[] toArray(T[] a) {
             Collection> c = new ArrayList>();
-            for (Node n = findFirst(); n != null; n = n.next) {
-                Map.Entry e = n.createSnapshot();
-                if (e != null) 
-                    c.add(e);
-            }
+            for (Map.Entry e : this)
+                c.add(new SnapshotEntry(e.getKey(), e.getValue()));
             return c.toArray(a);
         }
     }
 
+    class DescendingEntrySet extends EntrySet {
+        public Iterator> iterator() {
+            return new DescendingEntryIterator();
+        }
+    }
+
     /**
      * Submaps returned by {@link ConcurrentSkipListMap} submap operations
      * represent a subrange of mappings of their underlying
@@ -2769,24 +3036,28 @@ public class ConcurrentSkipListMap
         /** Underlying map */
         private final ConcurrentSkipListMap m;
         /** lower bound key, or null if from start */
-        private final K least; 
+        private final K least;
         /** upper fence key, or null if to end */
-        private final K fence;   
+        private final K fence;
         // Lazily initialized view holders
         private transient Set keySetView;
         private transient Set> entrySetView;
         private transient Collection valuesView;
+        private transient Set descendingKeySetView;
+        private transient Set> descendingEntrySetView;
 
         /**
-         * Creates a new submap. 
-         * @param least inclusive least value, or null if from start
-         * @param fence exclusive upper bound or null if to end
+         * 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, 
+        ConcurrentSkipListSubMap(ConcurrentSkipListMap map,
                                  K least, K fence) {
-            if (least != null && fence != null && map.compare(least, fence) > 0)
+            if (least != null &&
+                fence != null &&
+                map.compare(least, fence) > 0)
                 throw new IllegalArgumentException("inconsistent range");
             this.m = map;
             this.least = least;
@@ -2812,8 +3083,8 @@ public class ConcurrentSkipListMap
         }
 
         boolean isBeforeEnd(ConcurrentSkipListMap.Node n) {
-            return (n != null && 
-                    (fence == null || 
+            return (n != null &&
+                    (fence == null ||
                      n.key == null || // pass by markers and headers
                      m.compare(fence, n.key) > 0));
         }
@@ -2833,7 +3104,7 @@ public class ConcurrentSkipListMap
 
         /**
          * Returns least key. Needed by ConcurrentSkipListSet
-         * @return least key or null if from start
+         * @return least key or null if from start
          */
         K getLeast() {
             return least;
@@ -2841,130 +3112,39 @@ public class ConcurrentSkipListMap
 
         /**
          * Returns fence key. Needed by ConcurrentSkipListSet
-         * @return fence key or null of to end
+         * @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); 
+            for (ConcurrentSkipListMap.Node n = firstNode();
+                 isBeforeEnd(n);
                  n = n.next) {
                 if (n.getValidValue() != null)
                     ++count;
@@ -2972,29 +3152,15 @@ public class ConcurrentSkipListMap
             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) 
+            if (value == null)
                 throw new NullPointerException();
-            for (ConcurrentSkipListMap.Node n = firstNode(); 
-                 isBeforeEnd(n); 
+            for (ConcurrentSkipListMap.Node n = firstNode();
+                 isBeforeEnd(n);
                  n = n.next) {
                 V v = n.getValidValue();
                 if (v != null && value.equals(v))
@@ -3003,12 +3169,9 @@ public class ConcurrentSkipListMap
             return false;
         }
 
-        /**
-         * Removes all mappings from this map.
-         */
         public void clear() {
-            for (ConcurrentSkipListMap.Node n = firstNode(); 
-                 isBeforeEnd(n); 
+            for (ConcurrentSkipListMap.Node n = firstNode();
+                 isBeforeEnd(n);
                  n = n.next) {
                 if (n.getValidValue() != null)
                     m.remove(n.key);
@@ -3017,102 +3180,21 @@ public class ConcurrentSkipListMap
 
         /* ----------------  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);
@@ -3120,23 +3202,10 @@ public class ConcurrentSkipListMap
 
         /* ----------------  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))
@@ -3145,12 +3214,6 @@ public class ConcurrentSkipListMap
                 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) {
@@ -3161,32 +3224,6 @@ public class ConcurrentSkipListMap
             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();
@@ -3195,24 +3232,6 @@ public class ConcurrentSkipListMap
             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();
@@ -3221,23 +3240,6 @@ public class ConcurrentSkipListMap
             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();
@@ -3248,87 +3250,51 @@ public class ConcurrentSkipListMap
 
         /* ----------------  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);
+            return (SnapshotEntry)
+                m.getNear(key, m.GT|m.EQ, least, fence, false);
+        }
+
+        public K ceilingKey(K key) {
+            return (K)
+                m.getNear(key, m.GT|m.EQ, least, fence, true);
         }
 
-        /**
-         * 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);
+            return (SnapshotEntry)
+                m.getNear(key, m.LT, least, fence, false);
+        }
+
+        public K lowerKey(K key) {
+            return (K)
+                m.getNear(key, m.LT, least, fence, true);
         }
 
-        /**
-         * 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);
+            return (SnapshotEntry)
+                m.getNear(key, m.LT|m.EQ, least, fence, false);
         }
-        
-        /**
-         * 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 K floorKey(K key) {
+            return (K)
+                m.getNear(key, m.LT|m.EQ, least, fence, true);
+        }
+
+
         public Map.Entry higherEntry(K key) {
-            return m.getHigher(key, least, fence);
+            return (SnapshotEntry)
+                m.getNear(key, m.GT, least, fence, false);
+        }
+
+        public K higherKey(K key) {
+            return (K)
+                m.getNear(key, m.GT, least, fence, true);
         }
 
-        /**
-         * 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)) 
+                if (!isBeforeEnd(n))
                     return null;
                 Map.Entry e = n.createSnapshot();
                 if (e != null)
@@ -3336,15 +3302,6 @@ public class ConcurrentSkipListMap
             }
         }
 
-        /**
-         * 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();
@@ -3356,52 +3313,18 @@ 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 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);
+            return (SnapshotEntry)
+                m.removeFirstEntryOfSubrange(least, fence, 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 m.removeLastEntryOfSubrange(least, fence);
+            return (SnapshotEntry)
+                m.removeLastEntryOfSubrange(least, fence, false);
         }
 
         /* ---------------- 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());
@@ -3434,25 +3357,17 @@ public class ConcurrentSkipListMap
             }
         }
 
-        /**
-         * 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 Set descendingKeySet() {
+            Set ks = descendingKeySetView;
+            return (ks != null) ? ks : (descendingKeySetView = new DescendingKeySetView());
+        }
+
+        class DescendingKeySetView extends KeySetView {
+            public Iterator iterator() {
+                return m.descendingSubMapKeyIterator(least, fence);
+            }
+        }
+
         public Collection values() {
             Collection vs = valuesView;
             return (vs != null) ? vs : (valuesView = new ValuesView());
@@ -3485,28 +3400,6 @@ public class ConcurrentSkipListMap
             }
         }
 
-        /**
-         * 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());
@@ -3543,27 +3436,27 @@ public class ConcurrentSkipListMap
             }
             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);
-                }
+                for (Map.Entry e : this)
+                    c.add(new SnapshotEntry(e.getKey(), e.getValue()));
                 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);
-                }
+                for (Map.Entry e : this)
+                    c.add(new SnapshotEntry(e.getKey(), e.getValue()));
                 return c.toArray(a);
             }
         }
-    }
 
+        public Set> descendingEntrySet() {
+            Set> es = descendingEntrySetView;
+            return (es != null) ? es : (descendingEntrySetView = new DescendingEntrySetView());
+        }
+
+        class DescendingEntrySetView extends EntrySetView {
+            public Iterator> iterator() {
+                return m.descendingSubMapEntryIterator(least, fence);
+            }
+        }
+    }
 }