--- jsr166/src/jsr166x/ConcurrentSkipListMap.java 2009/08/01 22:12:59 1.7 +++ jsr166/src/jsr166x/ConcurrentSkipListMap.java 2012/11/25 21:06:56 1.19 @@ -1,10 +1,10 @@ /* * Written by Doug Lea with assistance from members of JCP JSR-166 * Expert Group and released to the public domain, as explained at - * http://creativecommons.org/licenses/publicdomain + * http://creativecommons.org/publicdomain/zero/1.0/ */ -package jsr166x; +package jsr166x; import java.util.*; import java.util.concurrent.*; @@ -56,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 @@ -74,19 +74,19 @@ 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 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 @@ -145,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 @@ -161,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 @@ -188,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 @@ -292,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; @@ -325,13 +325,13 @@ public class ConcurrentSkipListMap private transient DescendingEntrySet descendingEntrySet; /** - * Initialize or reset state. Needed by constructors, clone, + * Initializes or resets state. Needed by constructors, clone, * clear, readObject. and ConcurrentSkipListSet.clone. * (Note that comparator must be separately initialized.) */ final void initialize() { keySet = null; - entrySet = null; + entrySet = null; values = null; descendingEntrySet = null; descendingKeySet = null; @@ -341,8 +341,8 @@ public class ConcurrentSkipListMap } /** Updater for casHead */ - private static final - AtomicReferenceFieldUpdater + private static final + AtomicReferenceFieldUpdater headUpdater = AtomicReferenceFieldUpdater.newUpdater (ConcurrentSkipListMap.class, HeadIndex.class, "head"); @@ -390,12 +390,12 @@ 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"); @@ -414,7 +414,7 @@ public class ConcurrentSkipListMap } /** - * Return true if this node is a marker. This method isn't + * Returns true if this node is a marker. This method isn't * actually called in an any current code checking for markers * because callers will have already read value field and need * to use that read (not another done here) and so directly @@ -427,7 +427,7 @@ public class ConcurrentSkipListMap } /** - * Return true if this node is the header of base-level list. + * Returns true if this node is the header of base-level list. * @return true if this node is header node */ boolean isBaseHeader() { @@ -465,8 +465,8 @@ public class ConcurrentSkipListMap } /** - * Return value if this node contains a valid key-value pair, - * else null. + * Returns value if this node contains a valid key-value pair, + * else null. * @return this node's value if it isn't a marker or header or * is deleted, else null. */ @@ -478,8 +478,8 @@ public class ConcurrentSkipListMap } /** - * Create and return a new SnapshotEntry holding current - * mapping if this node holds a valid value, else null + * Creates and returns a new SnapshotEntry holding current + * mapping if this node holds a valid value, else null. * @return new entry or null */ SnapshotEntry createSnapshot() { @@ -508,7 +508,7 @@ public class ConcurrentSkipListMap /** * Creates index node with given values - */ + */ Index(Node node, Index down, Index right) { this.node = node; this.key = node.key; @@ -517,7 +517,7 @@ public class ConcurrentSkipListMap } /** Updater for casRight */ - static final AtomicReferenceFieldUpdater + static final AtomicReferenceFieldUpdater rightUpdater = AtomicReferenceFieldUpdater.newUpdater (Index.class, Index.class, "right"); @@ -546,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); } @@ -573,7 +573,7 @@ public class ConcurrentSkipListMap super(node, down, right); this.level = level; } - } + } /* ---------------- Map.Entry support -------------- */ @@ -581,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. @@ -592,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(); @@ -649,7 +649,7 @@ public class ConcurrentSkipListMap * @return a String representation of this entry. */ public String toString() { - return getKey() + "=" + getValue(); + return getKey() + "=" + getValue(); } } @@ -688,15 +688,15 @@ 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; } /** - * Compare using comparator or natural ordering. Used when the + * Compares using comparator or natural ordering. Used when the * ComparableUsingComparator approach doesn't apply. */ int compare(K k1, K k2) throws ClassCastException { @@ -708,23 +708,23 @@ public class ConcurrentSkipListMap } /** - * Return true if given key greater than or equal to least and + * Returns true if given key greater than or equal to least and * strictly less than fence, bypassing either test if least or - * fence oare null. Needed mainly in submap operations. + * fence are 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)); } /** - * Return true if given key greater than or equal to least and less + * Returns true if given key greater than or equal to least and less * 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)); @@ -733,12 +733,12 @@ public class ConcurrentSkipListMap /* ---------------- Traversal -------------- */ /** - * Return a base-level node with key strictly less than given key, + * Returns a base-level node with key strictly less than given key, * or the base-level header if there is no such node. Also * 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 (;;) { @@ -757,7 +757,7 @@ public class ConcurrentSkipListMap continue; } } - if ((d = q.down) != null) + if ((d = q.down) != null) q = d; else return q.node; @@ -766,7 +766,7 @@ public class ConcurrentSkipListMap } /** - * Return node holding key or null if no such, clearing out any + * Returns node holding key or null if no such, clearing out any * deleted nodes seen along the way. Repeatedly traverses at * base-level looking for key starting at predecessor returned * from findPredecessor, processing base-level deletions as @@ -787,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 @@ -805,7 +805,7 @@ public class ConcurrentSkipListMap * 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. */ @@ -814,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 @@ -829,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; @@ -837,7 +837,7 @@ public class ConcurrentSkipListMap } } - /** + /** * 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 @@ -856,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) { @@ -865,11 +865,11 @@ public class ConcurrentSkipListMap } if (c == 0) { Object v = r.node.value; - return (v != null)? (V)v : getUsingFindNode(key); + return (v != null) ? (V)v : getUsingFindNode(key); } 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) { @@ -878,7 +878,7 @@ public class ConcurrentSkipListMap int c = key.compareTo(nk); if (c == 0) { Object v = n.value; - return (v != null)? (V)v : getUsingFindNode(key); + return (v != null) ? (V)v : getUsingFindNode(key); } if (c < 0) return null; @@ -890,7 +890,7 @@ public class ConcurrentSkipListMap } /** - * Perform map.get via findNode. Used as a backup if doGet + * Performs map.get via findNode. Used as a backup if doGet * encounters an in-progress deletion. * @param key the key * @return the value, or null if absent @@ -916,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 @@ -952,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; } @@ -965,7 +965,7 @@ public class ConcurrentSkipListMap } /** - * Return a random level for inserting a new node. + * Returns a random level for inserting a new node. * Hardwired to k=1, p=0.5, max 31. * * This uses a cheap pseudo-random function that according to @@ -979,15 +979,15 @@ 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; } /** - * Create and add index nodes for given node. + * Creates and adds index nodes for given node. * @param z the node * @param level the level of the index */ @@ -1013,7 +1013,7 @@ public class ConcurrentSkipListMap level = max + 1; Index[] idxs = (Index[])new Index[level+1]; Index idx = null; - for (int i = 1; i <= level; ++i) + for (int i = 1; i <= level; ++i) idxs[i] = idx = new Index(z, idx, null); HeadIndex oldh; @@ -1027,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; @@ -1039,7 +1039,7 @@ public class ConcurrentSkipListMap } /** - * Add given index nodes from given level down to 1. + * Adds given index nodes from given level down to 1. * @param idx the topmost index node being inserted * @param h the value of head to use to insert. This must be * snapshotted by callers to provide correct insertion level @@ -1065,7 +1065,7 @@ public class ConcurrentSkipListMap if (q.unlink(r)) continue; else - break; + break; } if (c > 0) { q = r; @@ -1079,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; @@ -1111,7 +1111,7 @@ public class ConcurrentSkipListMap * 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 @@ -1120,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 @@ -1144,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; @@ -1185,10 +1185,10 @@ 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 @@ -1214,23 +1214,23 @@ public class ConcurrentSkipListMap 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 either its key or a snapshot. + * Removes 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 */ Object doRemoveFirst(boolean keyOnly) { - for (;;) { + 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) @@ -1246,13 +1246,13 @@ public class ConcurrentSkipListMap findFirst(); // retry clearIndexToFirst(); K key = n.key; - return (keyOnly)? key : new SnapshotEntry(key, (V)v); + return keyOnly ? key : new SnapshotEntry(key, (V)v); } } /** - * Clear out index nodes associated with deleted first entry. - * Needed by doRemoveFirst + * Clears out index nodes associated with deleted first entry. + * Needed by doRemoveFirst. */ private void clearIndexToFirst() { for (;;) { @@ -1260,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; } @@ -1271,7 +1271,7 @@ public class ConcurrentSkipListMap } /** - * Remove first entry; return key or null if empty. + * Removes first entry; return key or null if empty. */ K pollFirstKey() { return (K)doRemoveFirst(true); @@ -1296,7 +1296,7 @@ public class ConcurrentSkipListMap if (r.indexesDeletedNode()) { q.unlink(r); q = head; // restart - } + } else q = r; } else if ((d = q.down) != null) { @@ -1305,8 +1305,8 @@ public class ConcurrentSkipListMap Node b = q.node; Node n = b.next; for (;;) { - if (n == null) - return (b.isBaseHeader())? null : b; + if (n == null) + return b.isBaseHeader() ? null : b; Node f = n.next; // inconsistent read if (n != b.next) break; @@ -1332,13 +1332,13 @@ public class ConcurrentSkipListMap * @return null if empty, last key if keyOnly true, else key,value entry */ Object doRemoveLast(boolean keyOnly) { - for (;;) { + for (;;) { Node b = findPredecessorOfLast(); Node n = b.next; if (n == null) { if (b.isBaseHeader()) // empty return null; - else + else continue; // all b's successors are deleted; retry } for (;;) { @@ -1357,18 +1357,18 @@ public class ConcurrentSkipListMap n = f; continue; } - if (!n.casValue(v, null)) + if (!n.casValue(v, null)) break; K key = n.key; Comparable ck = comparable(key); - if (!n.appendMarker(f) || !b.casNext(n, f)) + if (!n.appendMarker(f) || !b.casNext(n, f)) findNode(ck); // Retry via findNode else { findPredecessor(ck); // Clean index - if (head.right == null) + if (head.right == null) tryReduceLevel(); } - return (keyOnly)? key : new SnapshotEntry(key, (V)v); + return keyOnly ? key : new SnapshotEntry(key, (V)v); } } } @@ -1378,7 +1378,7 @@ public class ConcurrentSkipListMap * 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. + * @return likely predecessor of last node. */ private Node findPredecessorOfLast() { for (;;) { @@ -1396,16 +1396,16 @@ public class ConcurrentSkipListMap continue; } } - if ((d = q.down) != null) + if ((d = q.down) != null) q = d; - else + else return q.node; } } } /** - * Remove last entry; return key or null if empty. + * Removes last entry; return key or null if empty. */ K pollLastKey() { return (K)doRemoveLast(true); @@ -1431,8 +1431,8 @@ public class ConcurrentSkipListMap Node b = findPredecessor(key); Node n = b.next; for (;;) { - if (n == null) - return ((rel & LT) == 0 || b.isBaseHeader())? null : b; + if (n == null) + return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b; Node f = n.next; if (n != b.next) // inconsistent read break; @@ -1448,7 +1448,7 @@ public class ConcurrentSkipListMap (c < 0 && (rel & LT) == 0)) return n; if ( c <= 0 && (rel & LT) != 0) - return (b.isBaseHeader())? null : b; + return b.isBaseHeader() ? null : b; b = n; n = f; } @@ -1456,7 +1456,7 @@ public class ConcurrentSkipListMap } /** - * Return SnapshotEntry for results of findNear. + * Returns SnapshotEntry for results of findNear. * @param kkey the key * @param rel the relation -- OR'ed combination of EQ, LT, GT * @return Entry fitting relation, or null if no such @@ -1473,21 +1473,21 @@ public class ConcurrentSkipListMap } /** - * Return ceiling, or first node if key is null + * Returns ceiling, or first node if key is null. */ Node findCeiling(K key) { - return (key == null)? findFirst() : findNear(key, GT|EQ); + return (key == null) ? findFirst() : findNear(key, GT|EQ); } /** - * Return lower node, or last node if key is null + * Returns lower node, or last node if key is null. */ Node findLower(K key) { - return (key == null)? findLast() : findNear(key, LT); + return (key == null) ? findLast() : findNear(key, LT); } /** - * Return SnapshotEntry or key for results of findNear ofter screening + * Returns 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 @@ -1512,13 +1512,13 @@ public class ConcurrentSkipListMap return null; K k = n.key; V v = n.getValidValue(); - if (v != null) - return keyOnly? k : new SnapshotEntry(k, v); + if (v != null) + return keyOnly ? k : new SnapshotEntry(k, v); } } /** - * Find and remove least element of subrange. + * Finds and removes 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 @@ -1534,12 +1534,12 @@ public class ConcurrentSkipListMap return null; V v = doRemove(k, null); if (v != null) - return (keyOnly)? k : new SnapshotEntry(k, v); + return keyOnly ? k : new SnapshotEntry(k, v); } } /** - * Find and remove greatest element of subrange. + * Finds and removes 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 @@ -1555,7 +1555,7 @@ public class ConcurrentSkipListMap return null; V v = doRemove(k, null); if (v != null) - return (keyOnly)? k : new SnapshotEntry(k, v); + return keyOnly ? k : new SnapshotEntry(k, v); } } @@ -1563,7 +1563,7 @@ public class ConcurrentSkipListMap /** * Constructs a new empty map, sorted according to the keys' natural - * order. + * order. */ public ConcurrentSkipListMap() { this.comparator = null; @@ -1584,7 +1584,7 @@ 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 @@ -1599,7 +1599,7 @@ public class ConcurrentSkipListMap /** * Constructs a new map containing the same mappings as the given - * SortedMap, sorted according to the same ordering. + * 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 @@ -1647,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) { @@ -1655,7 +1655,7 @@ public class ConcurrentSkipListMap q = q.down; } - Iterator> it = + Iterator> it = map.entrySet().iterator(); while (it.hasNext()) { Map.Entry e = it.next(); @@ -1672,7 +1672,7 @@ public class ConcurrentSkipListMap Index idx = null; for (int i = 1; i <= j; ++i) { idx = new Index(z, idx, null); - if (i > h.level) + if (i > h.level) h = new HeadIndex(h.node, h, idx, i); if (i < preds.size()) { @@ -1689,10 +1689,10 @@ public class ConcurrentSkipListMap /* ---------------- Serialization -------------- */ /** - * Save the state of the Map instance to a stream. + * Saves 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). @@ -1714,7 +1714,7 @@ public class ConcurrentSkipListMap } /** - * Reconstitute the Map instance from a stream. + * Reconstitutes the Map instance from a stream. */ private void readObject(final java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { @@ -1723,7 +1723,7 @@ public class ConcurrentSkipListMap // Reset transients initialize(); - /* + /* * 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 @@ -1734,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) { @@ -1747,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; @@ -1760,7 +1760,7 @@ public class ConcurrentSkipListMap Index idx = null; for (int i = 1; i <= j; ++i) { idx = new Index(z, idx, null); - if (i > h.level) + if (i > h.level) h = new HeadIndex(h.node, h, idx, i); if (i < preds.size()) { @@ -1792,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 @@ -1814,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); } @@ -1830,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. @@ -1847,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(); @@ -1883,7 +1883,7 @@ public class ConcurrentSkipListMap if (n.getValidValue() != null) ++count; } - return (count >= Integer.MAX_VALUE)? Integer.MAX_VALUE : (int)count; + return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)count; } /** @@ -2056,17 +2056,17 @@ public class ConcurrentSkipListMap * @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; + if (o == this) + return true; + if (!(o instanceof Map)) + return false; + Map t = (Map) o; try { - return (containsAllMappings(this, t) && + return (containsAllMappings(this, t) && containsAllMappings(t, this)); - } catch(ClassCastException unused) { + } catch (ClassCastException unused) { return false; - } catch(NullPointerException unused) { + } catch (NullPointerException unused) { return false; } } @@ -2080,7 +2080,7 @@ public class ConcurrentSkipListMap Entry e = it.next(); Object k = e.getKey(); Object v = e.getValue(); - if (k == null || v == null || !v.equals(a.get(k))) + if (k == null || v == null || !v.equals(a.get(k))) return false; } return true; @@ -2093,31 +2093,31 @@ public class ConcurrentSkipListMap * with a value, associate it with the given value. * This is equivalent to * 
-     *   if (!map.containsKey(key)) 
-     *      return map.put(key, value);
+     *   if (!map.containsKey(key))
+     *     return map.put(key, value);
      *   else
-     *      return map.get(key);
+     *     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. + * 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); } /** - * Remove entry for key only if currently mapped to given value. + * Removes 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;
@@ -2132,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;
     }
@@ -2140,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;
@@ -2157,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 (;;) {
@@ -2177,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;
@@ -2186,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 (;;) {
@@ -2224,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();
@@ -2250,7 +2250,7 @@ public class ConcurrentSkipListMap
      * 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.
      *
@@ -2305,7 +2305,7 @@ public class ConcurrentSkipListMap
      * Comparable).
      * @throws NullPointerException if fromKey is null.
      */
-    public ConcurrentNavigableMap  tailMap(K fromKey) {
+    public ConcurrentNavigableMap tailMap(K fromKey) {
         if (fromKey == null)
             throw new NullPointerException();
         return new ConcurrentSkipListSubMap(this, fromKey, null);
@@ -2318,7 +2318,7 @@ public class ConcurrentSkipListMap
      * 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.
@@ -2333,7 +2333,7 @@ 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.
@@ -2343,7 +2343,7 @@ public class ConcurrentSkipListMap
      */
     public K ceilingKey(K key) {
         Node n = findNear(key, GT|EQ);
-        return (n == null)? null : n.key;
+        return (n == null) ? null : n.key;
     }
 
     /**
@@ -2351,7 +2351,7 @@ public class ConcurrentSkipListMap
      * 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.
@@ -2366,7 +2366,7 @@ public class ConcurrentSkipListMap
     /**
      * 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.
@@ -2376,7 +2376,7 @@ public class ConcurrentSkipListMap
      */
     public K lowerKey(K key) {
         Node n = findNear(key, LT);
-        return (n == null)? null : n.key;
+        return (n == null) ? null : n.key;
     }
 
     /**
@@ -2384,7 +2384,7 @@ public class ConcurrentSkipListMap
      * 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.
@@ -2400,7 +2400,7 @@ public class ConcurrentSkipListMap
      * 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.
@@ -2410,7 +2410,7 @@ public class ConcurrentSkipListMap
      */
     public K floorKey(K key) {
         Node n = findNear(key, LT|EQ);
-        return (n == null)? null : n.key;
+        return (n == null) ? null : n.key;
     }
 
     /**
@@ -2418,7 +2418,7 @@ public class ConcurrentSkipListMap
      * 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.
@@ -2433,7 +2433,7 @@ 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.
@@ -2443,7 +2443,7 @@ public class ConcurrentSkipListMap
      */
     public K higherKey(K key) {
         Node n = findNear(key, GT);
-        return (n == null)? null : n.key;
+        return (n == null) ? null : n.key;
     }
 
     /**
@@ -2451,14 +2451,14 @@ public class ConcurrentSkipListMap
      * 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)
@@ -2471,14 +2471,14 @@ public class ConcurrentSkipListMap
      * 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 (;;) {
             Node n = findLast();
-            if (n == null) 
+            if (n == null)
                 return null;
             SnapshotEntry e = n.createSnapshot();
             if (e != null)
@@ -2491,7 +2491,7 @@ public class ConcurrentSkipListMap
      * 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.
      */
@@ -2504,7 +2504,7 @@ public class ConcurrentSkipListMap
      * 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.
      */
@@ -2517,27 +2517,27 @@ public class ConcurrentSkipListMap
 
     /**
      * Base of ten kinds of iterator classes:
-     *   ascending:  {map, submap} X {key, value, entry} 
-     *   descending: {map, submap} X {key, entry} 
+     *   ascending:  {map, submap} X {key, value, entry}
+     *   descending: {map, submap} X {key, entry}
      */
     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; 
+        public final boolean hasNext() {
+            return next != null;
         }
 
         /** initialize ascending iterator for entire range  */
         final void initAscending() {
             for (;;) {
-		next = findFirst();
+                next = findFirst();
                 if (next == null)
                     break;
                 nextValue = next.value;
@@ -2546,14 +2546,14 @@ public class ConcurrentSkipListMap
             }
         }
 
-        /** 
+        /**
          * 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.
          */
-        final void initAscending(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;
@@ -2571,7 +2571,7 @@ public class ConcurrentSkipListMap
             if ((last = next) == null)
                 throw new NoSuchElementException();
             for (;;) {
-		next = next.next;
+                next = next.next;
                 if (next == null)
                     break;
                 nextValue = next.value;
@@ -2587,7 +2587,7 @@ public class ConcurrentSkipListMap
             if ((last = next) == null)
                 throw new NoSuchElementException();
             for (;;) {
-		next = next.next;
+                next = next.next;
                 if (next == null)
                     break;
                 nextValue = next.value;
@@ -2604,7 +2604,7 @@ public class ConcurrentSkipListMap
         /** initialize descending iterator for entire range  */
         final void initDescending() {
             for (;;) {
-		next = findLast();
+                next = findLast();
                 if (next == null)
                     break;
                 nextValue = next.value;
@@ -2613,15 +2613,15 @@ public class ConcurrentSkipListMap
             }
         }
 
-        /** 
+        /**
          * 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) { 
+        final void initDescending(K least, K fence) {
             for (;;) {
-		next = findLower(fence);
+                next = findLower(fence);
                 if (next == null)
                     break;
                 nextValue = next.value;
@@ -2641,7 +2641,7 @@ public class ConcurrentSkipListMap
                 throw new NoSuchElementException();
             K k = last.key;
             for (;;) {
-		next = findNear(k, LT);
+                next = findNear(k, LT);
                 if (next == null)
                     break;
                 nextValue = next.value;
@@ -2658,7 +2658,7 @@ public class ConcurrentSkipListMap
                 throw new NoSuchElementException();
             K k = last.key;
             for (;;) {
-		next = findNear(k, LT);
+                next = findNear(k, LT);
                 if (next == null)
                     break;
                 nextValue = next.value;
@@ -2687,7 +2687,7 @@ public class ConcurrentSkipListMap
         ValueIterator() {
             initAscending();
         }
-        public V next() { 
+        public V next() {
             Object v = nextValue;
             ascend();
             return (V)v;
@@ -2698,7 +2698,7 @@ public class ConcurrentSkipListMap
         KeyIterator() {
             initAscending();
         }
-        public K next() { 
+        public K next() {
             Node n = next;
             ascend();
             return n.key;
@@ -2712,7 +2712,7 @@ public class ConcurrentSkipListMap
             this.fence = fence;
         }
 
-        public V next() { 
+        public V next() {
             Object v = nextValue;
             ascend(fence);
             return (V)v;
@@ -2726,7 +2726,7 @@ public class ConcurrentSkipListMap
             this.fence = fence;
         }
 
-        public K next() { 
+        public K next() {
             Node n = next;
             ascend(fence);
             return n.key;
@@ -2737,7 +2737,7 @@ public class ConcurrentSkipListMap
         DescendingKeyIterator() {
             initDescending();
         }
-        public K next() { 
+        public K next() {
             Node n = next;
             descend();
             return n.key;
@@ -2751,7 +2751,7 @@ public class ConcurrentSkipListMap
             this.least = least;
         }
 
-        public K next() { 
+        public K next() {
             Node n = next;
             descend(least);
             return n.key;
@@ -2767,7 +2767,7 @@ public class ConcurrentSkipListMap
         /** Cache of last value returned */
         Object lastValue;
 
-        EntryIter() { 
+        EntryIter() {
         }
 
         public K getKey() {
@@ -2781,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) {
@@ -2810,23 +2810,23 @@ public class ConcurrentSkipListMap
             // If not acting as entry, just use default.
             if (last == null)
                 return super.toString();
-	    return getKey() + "=" + getValue();
+            return getKey() + "=" + getValue();
         }
     }
 
-    final class EntryIterator extends EntryIter 
+    final class EntryIterator extends EntryIter
         implements Iterator> {
-        EntryIterator() { 
-            initAscending(); 
+        EntryIterator() {
+            initAscending();
         }
-        public Map.Entry next() { 
+        public Map.Entry next() {
             lastValue = nextValue;
             ascend();
             return this;
         }
     }
 
-    final class SubMapEntryIterator extends EntryIter 
+    final class SubMapEntryIterator extends EntryIter
         implements Iterator> {
         final K fence;
         SubMapEntryIterator(K least, K fence) {
@@ -2834,26 +2834,26 @@ public class ConcurrentSkipListMap
             this.fence = fence;
         }
 
-        public Map.Entry next() { 
+        public Map.Entry next() {
             lastValue = nextValue;
             ascend(fence);
             return this;
         }
     }
 
-    final class DescendingEntryIterator extends EntryIter 
+    final class DescendingEntryIterator extends EntryIter
         implements Iterator>  {
-        DescendingEntryIterator() { 
-            initDescending(); 
+        DescendingEntryIterator() {
+            initDescending();
         }
-        public Map.Entry next() { 
+        public Map.Entry next() {
             lastValue = nextValue;
             descend();
             return this;
         }
     }
 
-    final class DescendingSubMapEntryIterator extends EntryIter 
+    final class DescendingSubMapEntryIterator extends EntryIter
         implements Iterator>  {
         final K least;
         DescendingSubMapEntryIterator(K least, K fence) {
@@ -2861,7 +2861,7 @@ public class ConcurrentSkipListMap
             this.least = least;
         }
 
-        public Map.Entry next() { 
+        public Map.Entry next() {
             lastValue = nextValue;
             descend(least);
             return this;
@@ -2985,7 +2985,7 @@ public class ConcurrentSkipListMap
             if (!(o instanceof Map.Entry))
                 return false;
             Map.Entry e = (Map.Entry)o;
-            return ConcurrentSkipListMap.this.remove(e.getKey(), 
+            return ConcurrentSkipListMap.this.remove(e.getKey(),
                                                      e.getValue());
         }
         public boolean isEmpty() {
@@ -3000,13 +3000,13 @@ public class ConcurrentSkipListMap
 
         public Object[] toArray() {
             Collection> c = new ArrayList>();
-            for (Map.Entry e : this) 
+            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 (Map.Entry e : this) 
+            for (Map.Entry e : this)
                 c.add(new SnapshotEntry(e.getKey(), e.getValue()));
             return c.toArray(a);
         }
@@ -3036,9 +3036,9 @@ 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;
@@ -3047,16 +3047,16 @@ public class ConcurrentSkipListMap
         private transient Set> descendingEntrySetView;
 
         /**
-         * Creates a new submap. 
+         * 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
+         * @throws IllegalArgumentException if least and fence non-null
          *  and least greater than fence
          */
-        ConcurrentSkipListSubMap(ConcurrentSkipListMap map, 
+        ConcurrentSkipListSubMap(ConcurrentSkipListMap map,
                                  K least, K fence) {
-            if (least != null && 
-                fence != null && 
+            if (least != null &&
+                fence != null &&
                 map.compare(least, fence) > 0)
                 throw new IllegalArgumentException("inconsistent range");
             this.m = map;
@@ -3083,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));
         }
@@ -3128,7 +3128,7 @@ public class ConcurrentSkipListMap
 
         public V get(Object key) {
             K k = (K)key;
-            return ((!inHalfOpenRange(k)) ? null : m.get(k));
+            return (!inHalfOpenRange(k)) ? null : m.get(k);
         }
 
         public V put(K key, V value) {
@@ -3138,18 +3138,19 @@ public class ConcurrentSkipListMap
 
         public V remove(Object key) {
             K k = (K)key;
-            return (!inHalfOpenRange(k))? null : m.remove(k);
+            return (!inHalfOpenRange(k)) ? null : m.remove(k);
         }
 
         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;
             }
-            return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count;
+            return (count >= Integer.MAX_VALUE) ?
+                Integer.MAX_VALUE : (int)count;
         }
 
         public boolean isEmpty() {
@@ -3157,10 +3158,10 @@ public class ConcurrentSkipListMap
         }
 
         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))
@@ -3170,8 +3171,8 @@ public class ConcurrentSkipListMap
         }
 
         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);
@@ -3240,7 +3241,7 @@ public class ConcurrentSkipListMap
             return new ConcurrentSkipListSubMap(m, least, toKey);
         }
 
-        public  ConcurrentNavigableMap tailMap(K fromKey) {
+        public ConcurrentNavigableMap tailMap(K fromKey) {
             if (fromKey == null)
                 throw new NullPointerException();
             if (!inOpenRange(fromKey))
@@ -3280,7 +3281,7 @@ public class ConcurrentSkipListMap
                 m.getNear(key, m.LT|m.EQ, least, fence, true);
         }
 
-        
+
         public Map.Entry higherEntry(K key) {
             return (SnapshotEntry)
                 m.getNear(key, m.GT, least, fence, false);
@@ -3294,7 +3295,7 @@ public class ConcurrentSkipListMap
         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)
@@ -3436,13 +3437,13 @@ public class ConcurrentSkipListMap
             }
             public Object[] toArray() {
                 Collection> c = new ArrayList>();
-                for (Map.Entry e : this) 
+                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 (Map.Entry e : this) 
+                for (Map.Entry e : this)
                     c.add(new SnapshotEntry(e.getKey(), e.getValue()));
                 return c.toArray(a);
             }