--- jsr166/src/jsr166x/ConcurrentSkipListMap.java 2009/08/01 22:12:59 1.7 +++ jsr166/src/jsr166x/ConcurrentSkipListMap.java 2009/11/16 04:16:42 1.8 @@ -4,7 +4,7 @@ * http://creativecommons.org/licenses/publicdomain */ -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; @@ -331,7 +331,7 @@ public class ConcurrentSkipListMap */ 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"); @@ -466,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. */ @@ -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,7 +581,7 @@ 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; @@ -606,7 +606,7 @@ public class ConcurrentSkipListMap } /** - * Returns the value corresponding to this entry. + * Returns the value corresponding to this entry. * * @return the value corresponding to this entry. */ @@ -688,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; } @@ -713,7 +713,7 @@ public class ConcurrentSkipListMap * 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)); @@ -724,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)); @@ -738,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 (;;) { @@ -757,7 +757,7 @@ public class ConcurrentSkipListMap continue; } } - if ((d = q.down) != null) + if ((d = q.down) != null) q = d; else return q.node; @@ -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) { @@ -869,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) { @@ -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; } @@ -979,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; @@ -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; @@ -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. + * 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 */ 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) @@ -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. + * Remove 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,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,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,15 +1357,15 @@ 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); @@ -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. + * Remove last entry; return key or null if empty. */ K pollLastKey() { return (K)doRemoveLast(true); @@ -1431,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 @@ -1512,7 +1512,7 @@ public class ConcurrentSkipListMap return null; K k = n.key; V v = n.getValidValue(); - if (v != null) + if (v != null) 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()) { @@ -1692,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). @@ -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. @@ -1849,9 +1849,9 @@ public class ConcurrentSkipListMap * @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 (Node n = findFirst(); n != null; n = n.next) { V v = n.getValidValue(); @@ -2062,7 +2062,7 @@ public class ConcurrentSkipListMap return false; Map t = (Map) o; try { - return (containsAllMappings(this, t) && + return (containsAllMappings(this, t) && containsAllMappings(t, this)); } catch(ClassCastException 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,7 +2093,7 @@ 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);
@@ -2102,14 +2102,14 @@ public class ConcurrentSkipListMap
      * @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);
     }
@@ -2117,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;
@@ -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();
@@ -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.
@@ -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.
@@ -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.
@@ -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.
@@ -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,8 +2517,8 @@ 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() */
@@ -2530,8 +2530,8 @@ public class ConcurrentSkipListMap
 
         Iter() {}
 
-        public final boolean hasNext() { 
-            return next != null; 
+        public final boolean hasNext() {
+            return next != null;
         }
 
         /** initialize ascending iterator for entire range  */
@@ -2546,12 +2546,12 @@ 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);
                 if (next == null)
@@ -2613,13 +2613,13 @@ 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);
                 if (next == null)
@@ -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() {
@@ -2814,19 +2814,19 @@ public class ConcurrentSkipListMap
         }
     }
 
-    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
          *  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));
         }
@@ -3143,8 +3143,8 @@ public class ConcurrentSkipListMap
 
         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;
@@ -3157,10 +3157,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 +3170,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);
@@ -3280,7 +3280,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 +3294,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 +3436,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);
             }