--- jsr166/src/jsr166x/ConcurrentSkipListMap.java 2004/09/06 17:01:54 1.2
+++ jsr166/src/jsr166x/ConcurrentSkipListMap.java 2004/12/21 17:27:44 1.5
@@ -27,9 +27,10 @@ import java.util.concurrent.atomic.*;
* elements reflecting the state of the map at some point at or since
* the creation of the iterator. They do not throw {@link
* ConcurrentModificationException}, and may proceed concurrently with
- * other operations.
+ * other operations. Ascending key ordered views and their iterators
+ * are faster than descending ones.
*
- * All Map.Entry pairs returned by methods in this class
+ *
All Map.Entry pairs returned by methods in this class
* and its views represent snapshots of mappings at the time they were
* produced. They do not support the Entry.setValue
* method. (Note however that it is possible to change mappings in the
@@ -39,7 +40,12 @@ import java.util.concurrent.atomic.*;
*
Beware that, unlike in most collections, the size
* method is not a constant-time operation. Because of the
* asynchronous nature of these maps, determining the current number
- * of elements requires a traversal of the elements.
+ * of elements requires a traversal of the elements. Additionally,
+ * the bulk operations putAll, equals, and
+ * clear are not guaranteed to be performed
+ * atomically. For example, an iterator operating concurrently with a
+ * putAll operation might view only some of the added
+ * elements.
*
*
This class and its views and iterators implement all of the
* optional methods of the {@link Map} and {@link Iterator}
@@ -68,7 +74,7 @@ public class ConcurrentSkipListMap
* possible list with 2 levels of index:
*
* Head nodes Index nodes
- * +-+ right +-+ +-+
+ * +-+ right +-+ +-+
* |2|---------------->| |--------------------->| |->null
* +-+ +-+ +-+
* | down | |
@@ -76,21 +82,22 @@ public class ConcurrentSkipListMap
* +-+ +-+ +-+ +-+ +-+ +-+
* |1|----------->| |->| |------>| |----------->| |------>| |->null
* +-+ +-+ +-+ +-+ +-+ +-+
- * | | | | | |
- * v Nodes v v v v v
+ * v | | | | |
+ * Nodes next v v v v v
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
*
* The base lists use a variant of the HM linked ordered set
- * algorithm (See Tim Harris, "A pragmatic implementation of
+ * algorithm. See Tim Harris, "A pragmatic implementation of
* non-blocking linked lists"
* http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged
* Michael "High Performance Dynamic Lock-Free Hash Tables and
* List-Based Sets"
- * http://www.research.ibm.com/people/m/michael/pubs.htm). The
- * basic idea in these lists is to mark pointers of deleted nodes
- * when deleting, and when traversing to keep track of triples
+ * http://www.research.ibm.com/people/m/michael/pubs.htm. The
+ * basic idea in these lists is to mark the "next" pointers of
+ * deleted nodes when deleting to avoid conflicts with concurrent
+ * insertions, and when traversing to keep track of triples
* (predecessor, node, successor) in order to detect when and how
* to unlink these deleted nodes.
*
@@ -259,8 +266,8 @@ public class ConcurrentSkipListMap
* For explanation of algorithms sharing at least a couple of
* features with this one, see Mikhail Fomitchev's thesis
* (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
- * (http://www.cl.cam.ac.uk/users/kaf24/), and papers by
- * Håkan Sundell (http://www.cs.chalmers.se/~phs/).
+ * (http://www.cl.cam.ac.uk/users/kaf24/), and Håkan Sundell's
+ * thesis (http://www.cs.chalmers.se/~phs/).
*
* Given the use of tree-like index nodes, you might wonder why
* this doesn't use some kind of search tree instead, which would
@@ -312,6 +319,10 @@ public class ConcurrentSkipListMap
private transient EntrySet entrySet;
/** Lazily initialized values collection */
private transient Values values;
+ /** Lazily initialized descending key set */
+ private transient DescendingKeySet descendingKeySet;
+ /** Lazily initialized descending entry set */
+ private transient DescendingEntrySet descendingEntrySet;
/**
* Initialize or reset state. Needed by constructors, clone,
@@ -322,6 +333,8 @@ public class ConcurrentSkipListMap
keySet = null;
entrySet = null;
values = null;
+ descendingEntrySet = null;
+ descendingKeySet = null;
randomSeed = (int) System.nanoTime();
head = new HeadIndex(new Node(null, BASE_HEADER, null),
null, null, 1);
@@ -386,7 +399,6 @@ public class ConcurrentSkipListMap
valueUpdater = AtomicReferenceFieldUpdater.newUpdater
(Node.class, Object.class, "value");
-
/**
* compareAndSet value field
*/
@@ -495,16 +507,7 @@ public class ConcurrentSkipListMap
volatile Index right;
/**
- * Creates index node with unknown right pointer
- */
- Index(Node node, Index down) {
- this.node = node;
- this.key = node.key;
- this.down = down;
- }
-
- /**
- * Creates index node with known right pointer
+ * Creates index node with given values
*/
Index(Node node, Index down, Index right) {
this.node = node;
@@ -566,8 +569,7 @@ public class ConcurrentSkipListMap
*/
static final class HeadIndex extends Index {
final int level;
- HeadIndex(Node node, Index down, Index right,
- int level) {
+ HeadIndex(Node node, Index down, Index right, int level) {
super(node, down, right);
this.level = level;
}
@@ -707,7 +709,8 @@ public class ConcurrentSkipListMap
/**
* Return true if given key greater than or equal to least and
- * strictly less than fence. Needed mainly in submap operations.
+ * strictly less than fence, bypassing either test if least or
+ * fence oare null. Needed mainly in submap operations.
*/
boolean inHalfOpenRange(K key, K least, K fence) {
if (key == null)
@@ -797,8 +800,8 @@ public class ConcurrentSkipListMap
* links, and so will retry anyway.
*
* The traversal loops in doPut, doRemove, and findNear all
- * include with the same three kinds of checks. And specialized
- * versions appear in doRemoveFirstEntry, findFirst, and
+ * include the same three kinds of checks. And specialized
+ * versions appear in doRemoveFirst, doRemoveLast, findFirst, and
* findLast. They can't easily share code because each uses the
* reads of fields held in locals occurring in the orders they
* were performed.
@@ -835,7 +838,7 @@ public class ConcurrentSkipListMap
}
/**
- * Specialized variant of findNode to perform map.get. Does a weak
+ * Specialized variant of findNode to perform Map.get. Does a weak
* traversal, not bothering to fix any deleted index nodes,
* returning early if it happens to see key in index, and passing
* over any deleted base nodes, falling back to getUsingFindNode
@@ -893,8 +896,11 @@ public class ConcurrentSkipListMap
* @return the value, or null if absent
*/
private V getUsingFindNode(Comparable key) {
- // Loop needed here and elsewhere to protect against value
- // field going null just as it is about to be returned.
+ /*
+ * Loop needed here and elsewhere in case value field goes
+ * null just as it is about to be returned, in which case we
+ * lost a race with a deletion, so must retry.
+ */
for (;;) {
Node n = findNode(key);
if (n == null)
@@ -992,7 +998,7 @@ public class ConcurrentSkipListMap
if (level <= max) {
Index idx = null;
for (int i = 1; i <= level; ++i)
- idx = new Index(z, idx);
+ idx = new Index(z, idx, null);
addIndex(idx, h, level);
} else { // Add a new level
@@ -1008,7 +1014,7 @@ public class ConcurrentSkipListMap
Index[] idxs = (Index[])new Index[level+1];
Index idx = null;
for (int i = 1; i <= level; ++i)
- idxs[i] = idx = new Index(z, idx);
+ idxs[i] = idx = new Index(z, idx, null);
HeadIndex oldh;
int k;
@@ -1098,7 +1104,7 @@ public class ConcurrentSkipListMap
* deletion marker, unlinks predecessor, removes associated index
* nodes, and possibly reduces head index level.
*
- * Index node are cleared out simply by calling findPredecessor.
+ * Index nodes are cleared out simply by calling findPredecessor.
* which unlinks indexes to deleted nodes found along path to key,
* which will include the indexes to this node. This is done
* unconditionally. We can't check beforehand whether there are
@@ -1158,8 +1164,8 @@ public class ConcurrentSkipListMap
* Possibly reduce head level if it has no nodes. This method can
* (rarely) make mistakes, in which case levels can disappear even
* though they are about to contain index nodes. This impacts
- * performance, not correctness. To minimize mistakes and also to
- * reduce hysteresis, the level is reduced by one only if the
+ * performance, not correctness. To minimize mistakes as well as
+ * to reduce hysteresis, the level is reduced by one only if the
* topmost three levels look empty. Also, if the removed level
* looks non-empty after CAS, we try to change it back quick
* before anyone notices our mistake! (This trick works pretty
@@ -1189,16 +1195,21 @@ public class ConcurrentSkipListMap
casHead(d, h); // try to backout
}
+ /**
+ * Version of remove with boolean return. Needed by view classes
+ */
+ boolean removep(Object key) {
+ return doRemove(key, null) != null;
+ }
- /* ---------------- Positional operations -------------- */
+ /* ---------------- Finding and removing first element -------------- */
/**
- * Specialized version of find to get first valid node
+ * Specialized variant of findNode to get first valid node
* @return first node or null if empty
*/
Node findFirst() {
for (;;) {
- // cheaper checks because we know head is never deleted
Node b = head.node;
Node n = b.next;
if (n == null)
@@ -1210,10 +1221,12 @@ public class ConcurrentSkipListMap
}
/**
- * Remove first entry; return its key or null if empty.
- * Used by ConcurrentSkipListSet
+ * Remove first entry; return either its key or a snapshot.
+ * @param keyOnly if true return key, else return SnapshotEntry
+ * (This is a little ugly, but avoids code duplication.)
+ * @return null if empty, first key if keyOnly true, else key,value entry
*/
- K removeFirstKey() {
+ Object doRemoveFirst(boolean keyOnly) {
for (;;) {
Node b = head.node;
Node n = b.next;
@@ -1232,43 +1245,14 @@ public class ConcurrentSkipListMap
if (!n.appendMarker(f) || !b.casNext(n, f))
findFirst(); // retry
clearIndexToFirst();
- return n.key;
- }
- }
-
- /**
- * Remove first entry; return SnapshotEntry or null if empty.
- */
- private SnapshotEntry doRemoveFirstEntry() {
- /*
- * This must be mostly duplicated from removeFirstKey because we
- * need to save the last value read before it is nulled out
- */
- for (;;) {
- Node b = head.node;
- Node n = b.next;
- if (n == null)
- return null;
- Node f = n.next;
- if (n != b.next)
- continue;
- Object v = n.value;
- if (v == null) {
- n.helpDelete(b, f);
- continue;
- }
- if (!n.casValue(v, null))
- continue;
- if (!n.appendMarker(f) || !b.casNext(n, f))
- findFirst(); // retry
- clearIndexToFirst();
- return new SnapshotEntry(n.key, (V)v);
+ K key = n.key;
+ return (keyOnly)? key : new SnapshotEntry(key, (V)v);
}
}
/**
* Clear out index nodes associated with deleted first entry.
- * Needed by removeFirstKey and removeFirstEntry
+ * Needed by doRemoveFirst
*/
private void clearIndexToFirst() {
for (;;) {
@@ -1286,6 +1270,15 @@ public class ConcurrentSkipListMap
}
}
+ /**
+ * Remove first entry; return key or null if empty.
+ */
+ K pollFirstKey() {
+ return (K)doRemoveFirst(true);
+ }
+
+ /* ---------------- Finding and removing last element -------------- */
+
/**
* Specialized version of find to get last valid node
* @return last node or null if empty
@@ -1332,19 +1325,23 @@ public class ConcurrentSkipListMap
}
}
+
/**
- * Temporary helper method for two-pass implementation of
- * removeLastEntry, mostly pasted from doRemove.
- * TODO: replace with one-pass implementation
+ * Specialized version of doRemove for last entry.
+ * @param keyOnly if true return key, else return SnapshotEntry
+ * @return null if empty, last key if keyOnly true, else key,value entry
*/
- private Object removeIfLast(K kkey) {
- Comparable key = comparable(kkey);
+ Object doRemoveLast(boolean keyOnly) {
for (;;) {
- Node b = findPredecessor(key);
+ Node b = findPredecessorOfLast();
Node n = b.next;
- for (;;) {
- if (n == null)
+ if (n == null) {
+ if (b.isBaseHeader()) // empty
return null;
+ else
+ continue; // all b's successors are deleted; retry
+ }
+ for (;;) {
Node f = n.next;
if (n != b.next) // inconsistent read
break;
@@ -1355,57 +1352,63 @@ public class ConcurrentSkipListMap
}
if (v == n || b.value == null) // b is deleted
break;
- int c = key.compareTo(n.key);
- if (c < 0)
- return null;
- if (c > 0) {
+ if (f != null) {
b = n;
n = f;
continue;
}
- if (f != null) // fail if n not last
- return null;
if (!n.casValue(v, null))
- return null;
+ break;
+ K key = n.key;
+ Comparable ck = comparable(key);
if (!n.appendMarker(f) || !b.casNext(n, f))
- findNode(key); // Retry via findNode
+ findNode(ck); // Retry via findNode
else {
- findPredecessor(key); // Clean index
+ findPredecessor(ck); // Clean index
if (head.right == null)
tryReduceLevel();
}
- return v;
+ return (keyOnly)? key : new SnapshotEntry(key, (V)v);
}
}
}
/**
- * Remove last entry; return SnapshotEntry or null if empty.
+ * Specialized variant of findPredecessor to get predecessor of
+ * last valid node. Needed by doRemoveLast. It is possible that
+ * all successors of returned node will have been deleted upon
+ * return, in which case this method can be retried.
+ * @return likely predecessor of last node.
*/
- private SnapshotEntry doRemoveLastEntry() {
+ private Node findPredecessorOfLast() {
for (;;) {
- Node l = findLast();
- if (l == null)
- return null;
- K k = l.key;
- Object v = removeIfLast(k);
- if (v != null)
- return new SnapshotEntry(k, (V)v);
+ Index q = head;
+ for (;;) {
+ Index d, r;
+ if ((r = q.right) != null) {
+ if (r.indexesDeletedNode()) {
+ q.unlink(r);
+ break; // must restart
+ }
+ // proceed as far across as possible without overshooting
+ if (r.node.next != null) {
+ q = r;
+ continue;
+ }
+ }
+ if ((d = q.down) != null)
+ q = d;
+ else
+ return q.node;
+ }
}
}
-
+
/**
* Remove last entry; return key or null if empty.
*/
- K removeLastKey() {
- for (;;) {
- Node l = findLast();
- if (l == null)
- return null;
- K k = l.key;
- if (removeIfLast(k) != null)
- return k;
- }
+ K pollLastKey() {
+ return (K)doRemoveLast(true);
}
/* ---------------- Relational operations -------------- */
@@ -1414,7 +1417,7 @@ public class ConcurrentSkipListMap
private static final int EQ = 1;
private static final int LT = 2;
- private static final int GT = 0;
+ private static final int GT = 0; // Actually checked as !LT
/**
* Utility for ceiling, floor, lower, higher methods.
@@ -1469,6 +1472,93 @@ public class ConcurrentSkipListMap
}
}
+ /**
+ * Return ceiling, or first node if key is null
+ */
+ Node findCeiling(K key) {
+ return (key == null)? findFirst() : findNear(key, GT|EQ);
+ }
+
+ /**
+ * Return lower node, or last node if key is null
+ */
+ Node findLower(K key) {
+ return (key == null)? findLast() : findNear(key, LT);
+ }
+
+ /**
+ * Return SnapshotEntry or key for results of findNear ofter screening
+ * to ensure result is in given range. Needed by submaps.
+ * @param kkey the key
+ * @param rel the relation -- OR'ed combination of EQ, LT, GT
+ * @param least minimum allowed key value
+ * @param fence key greater than maximum allowed key value
+ * @param keyOnly if true return key, else return SnapshotEntry
+ * @return Key or Entry fitting relation, or null if no such
+ */
+ Object getNear(K kkey, int rel, K least, K fence, boolean keyOnly) {
+ K key = kkey;
+ // Don't return keys less than least
+ if ((rel & LT) == 0) {
+ if (compare(key, least) < 0) {
+ key = least;
+ rel = rel | EQ;
+ }
+ }
+
+ for (;;) {
+ Node n = findNear(key, rel);
+ if (n == null || !inHalfOpenRange(n.key, least, fence))
+ return null;
+ K k = n.key;
+ V v = n.getValidValue();
+ if (v != null)
+ return keyOnly? k : new SnapshotEntry(k, v);
+ }
+ }
+
+ /**
+ * Find and remove least element of subrange.
+ * @param least minimum allowed key value
+ * @param fence key greater than maximum allowed key value
+ * @param keyOnly if true return key, else return SnapshotEntry
+ * @return least Key or Entry, or null if no such
+ */
+ Object removeFirstEntryOfSubrange(K least, K fence, boolean keyOnly) {
+ for (;;) {
+ Node n = findCeiling(least);
+ if (n == null)
+ return null;
+ K k = n.key;
+ if (fence != null && compare(k, fence) >= 0)
+ return null;
+ V v = doRemove(k, null);
+ if (v != null)
+ return (keyOnly)? k : new SnapshotEntry(k, v);
+ }
+ }
+
+ /**
+ * Find and remove greatest element of subrange.
+ * @param least minimum allowed key value
+ * @param fence key greater than maximum allowed key value
+ * @param keyOnly if true return key, else return SnapshotEntry
+ * @return least Key or Entry, or null if no such
+ */
+ Object removeLastEntryOfSubrange(K least, K fence, boolean keyOnly) {
+ for (;;) {
+ Node n = findLower(fence);
+ if (n == null)
+ return null;
+ K k = n.key;
+ if (least != null && compare(k, least) < 0)
+ return null;
+ V v = doRemove(k, null);
+ if (v != null)
+ return (keyOnly)? k : new SnapshotEntry(k, v);
+ }
+ }
+
/* ---------------- Constructors -------------- */
/**
@@ -1499,7 +1589,7 @@ public class ConcurrentSkipListMap
* @param m the map whose mappings are to be placed in this map.
* @throws ClassCastException if the keys in m are not Comparable, or
* are not mutually comparable.
- * @throws NullPointerException if the specified map is null.
+ * @throws NullPointerException if the specified map is null.
*/
public ConcurrentSkipListMap(Map m) {
this.comparator = null;
@@ -1510,9 +1600,10 @@ public class ConcurrentSkipListMap
/**
* Constructs a new map containing the same mappings as the given
* SortedMap, sorted according to the same ordering.
- * @param m the sorted map whose mappings are to be placed in this map,
- * and whose comparator is to be used to sort this map.
- * @throws NullPointerException if the specified sorted map is null.
+ * @param m the sorted map whose mappings are to be placed in this
+ * map, and whose comparator is to be used to sort this map.
+ * @throws NullPointerException if the specified sorted map is
+ * null.
*/
public ConcurrentSkipListMap(SortedMap m) {
this.comparator = m.comparator();
@@ -1580,7 +1671,7 @@ public class ConcurrentSkipListMap
if (j > 0) {
Index idx = null;
for (int i = 1; i <= j; ++i) {
- idx = new Index(z, idx);
+ idx = new Index(z, idx, null);
if (i > h.level)
h = new HeadIndex(h.node, h, idx, i);
@@ -1633,7 +1724,7 @@ public class ConcurrentSkipListMap
initialize();
/*
- * This is basically identical to buildFromSorted, but is
+ * This is nearly identical to buildFromSorted, but is
* distinct because readObject calls can't be nicely adapted
* as the kind of iterator needed by buildFromSorted. (They
* can be, but doing so requires type cheats and/or creation
@@ -1668,7 +1759,7 @@ public class ConcurrentSkipListMap
if (j > 0) {
Index idx = null;
for (int i = 1; i <= j; ++i) {
- idx = new Index(z, idx);
+ idx = new Index(z, idx, null);
if (i > h.level)
h = new HeadIndex(h.node, h, idx, i);
@@ -1841,6 +1932,37 @@ public class ConcurrentSkipListMap
}
/**
+ * Returns a set view of the keys contained in this map in
+ * descending order. The set is backed by the map, so changes to
+ * the map are reflected in the set, and vice-versa. The set
+ * supports element removal, which removes the corresponding
+ * mapping from this map, via the Iterator.remove,
+ * Set.remove, removeAll, retainAll,
+ * and clear operations. It does not support the
+ * add or addAll operations. The view's
+ * iterator is a "weakly consistent" iterator that will
+ * never throw {@link java.util.ConcurrentModificationException},
+ * and guarantees to traverse elements as they existed upon
+ * construction of the iterator, and may (but is not guaranteed
+ * to) reflect any modifications subsequent to construction.
+ *
+ * @return a set view of the keys contained in this map.
+ */
+ public Set descendingKeySet() {
+ /*
+ * Note: Lazy intialization works here and for other views
+ * because view classes are stateless/immutable so it doesn't
+ * matter wrt correctness if more than one is created (which
+ * will only rarely happen). Even so, the following idiom
+ * conservatively ensures that the method returns the one it
+ * created if it does so, not one created by another racing
+ * thread.
+ */
+ DescendingKeySet ks = descendingKeySet;
+ return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
+ }
+
+ /**
* Returns a collection view of the values contained in this map.
* The collection is backed by the map, so changes to the map are
* reflected in the collection, and vice-versa. The collection
@@ -1890,6 +2012,80 @@ public class ConcurrentSkipListMap
return (es != null) ? es : (entrySet = new EntrySet());
}
+ /**
+ * Returns a collection view of the mappings contained in this
+ * map, in descending order. Each element in the returned
+ * collection is a Map.Entry. The collection is backed
+ * by the map, so changes to the map are reflected in the
+ * collection, and vice-versa. The collection supports element
+ * removal, which removes the corresponding mapping from the map,
+ * via the Iterator.remove, Collection.remove,
+ * removeAll, retainAll, and clear
+ * operations. It does not support the add or
+ * addAll operations. The view's iterator is a
+ * "weakly consistent" iterator that will never throw {@link
+ * java.util.ConcurrentModificationException}, and guarantees to
+ * traverse elements as they existed upon construction of the
+ * iterator, and may (but is not guaranteed to) reflect any
+ * modifications subsequent to construction. The
+ * Map.Entry elements returned by
+ * iterator.next() do not support the
+ * setValue operation.
+ *
+ * @return a collection view of the mappings contained in this map.
+ */
+ public Set> descendingEntrySet() {
+ DescendingEntrySet es = descendingEntrySet;
+ return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
+ }
+
+ /* ---------------- AbstractMap Overrides -------------- */
+
+ /**
+ * Compares the specified object with this map for equality.
+ * Returns true if the given object is also a map and the
+ * two maps represent the same mappings. More formally, two maps
+ * t1 and t2 represent the same mappings if
+ * t1.keySet().equals(t2.keySet()) and for every key
+ * k in t1.keySet(), (t1.get(k)==null ?
+ * t2.get(k)==null : t1.get(k).equals(t2.get(k))) . This
+ * operation may return misleading results if either map is
+ * concurrently modified during execution of this method.
+ *
+ * @param o object to be compared for equality with this map.
+ * @return true if the specified object is equal to this map.
+ */
+ public boolean equals(Object o) {
+ if (o == this)
+ return true;
+ if (!(o instanceof Map))
+ return false;
+ Map t = (Map) o;
+ try {
+ return (containsAllMappings(this, t) &&
+ containsAllMappings(t, this));
+ } catch(ClassCastException unused) {
+ return false;
+ } catch(NullPointerException unused) {
+ return false;
+ }
+ }
+
+ /**
+ * Helper for equals -- check for containment, avoiding nulls.
+ */
+ static boolean containsAllMappings(Map a, Map b) {
+ Iterator> it = b.entrySet().iterator();
+ while (it.hasNext()) {
+ Entry e = it.next();
+ Object k = e.getKey();
+ Object v = e.getValue();
+ if (k == null || v == null || !v.equals(a.get(k)))
+ return false;
+ }
+ return true;
+ }
+
/* ------ ConcurrentMap API methods ------ */
/**
@@ -1902,7 +2098,7 @@ public class ConcurrentSkipListMap
* else
* return map.get(key);
*
- * Except that the action is performed atomically.
+ * except that the action is performed atomically.
* @param key key with which the specified value is to be associated.
* @param value value to be associated with the specified key.
* @return previous value associated with specified key, or null
@@ -2076,17 +2272,17 @@ public class ConcurrentSkipListMap
}
/**
- * Returns a view of the portion of this map whose keys are strictly less
- * than toKey. The returned sorted map is backed by this map, so
- * changes in the returned sorted map are reflected in this map, and
- * vice-versa.
+ * Returns a view of the portion of this map whose keys are
+ * strictly less than toKey. The returned sorted map is
+ * backed by this map, so changes in the returned sorted map are
+ * reflected in this map, and vice-versa.
* @param toKey high endpoint (exclusive) of the headMap.
- * @return a view of the portion of this map whose keys are strictly
- * less than toKey.
+ * @return a view of the portion of this map whose keys are
+ * strictly less than toKey.
*
* @throws ClassCastException if toKey is not compatible
- * with this map's comparator (or, if the map has no comparator,
- * if toKey does not implement Comparable).
+ * with this map's comparator (or, if the map has no comparator,
+ * if toKey does not implement Comparable).
* @throws NullPointerException if toKey is null.
*/
public ConcurrentNavigableMap headMap(K toKey) {
@@ -2101,11 +2297,12 @@ public class ConcurrentSkipListMap
* map is backed by this map, so changes in the returned sorted
* map are reflected in this map, and vice-versa.
* @param fromKey low endpoint (inclusive) of the tailMap.
- * @return a view of the portion of this map whose keys are greater
- * than or equal to fromKey.
- * @throws ClassCastException if fromKey is not compatible
- * with this map's comparator (or, if the map has no comparator,
- * if fromKey does not implement Comparable).
+ * @return a view of the portion of this map whose keys are
+ * greater than or equal to fromKey.
+ * @throws ClassCastException if fromKey is not
+ * compatible with this map's comparator (or, if the map has no
+ * comparator, if fromKey does not implement
+ * Comparable).
* @throws NullPointerException if fromKey is null.
*/
public ConcurrentNavigableMap tailMap(K fromKey) {
@@ -2118,15 +2315,15 @@ public class ConcurrentSkipListMap
/**
* Returns a key-value mapping associated with the least key
- * greater than or equal to the given key, or null if there is
- * no such entry. The returned entry does not support
- * the Entry.setValue method.
+ * greater than or equal to the given key, or null if
+ * there is no such entry. The returned entry does not
+ * support the Entry.setValue method.
*
* @param key the key.
- * @return an Entry associated with ceiling of given key, or null
- * if there is no such Entry.
- * @throws ClassCastException if key cannot be compared with the keys
- * currently in the map.
+ * @return an Entry associated with ceiling of given key, or
+ * null if there is no such Entry.
+ * @throws ClassCastException if key cannot be compared with the
+ * keys currently in the map.
* @throws NullPointerException if key is null.
*/
public Map.Entry ceilingEntry(K key) {
@@ -2134,14 +2331,30 @@ public class ConcurrentSkipListMap
}
/**
+ * Returns least key greater than or equal to the given key, or
+ * null if there is no such key.
+ *
+ * @param key the key.
+ * @return the ceiling key, or null
+ * if there is no such key.
+ * @throws ClassCastException if key cannot be compared with the keys
+ * currently in the map.
+ * @throws NullPointerException if key is null.
+ */
+ public K ceilingKey(K key) {
+ Node n = findNear(key, GT|EQ);
+ return (n == null)? null : n.key;
+ }
+
+ /**
* Returns a key-value mapping associated with the greatest
- * key strictly less than the given key, or null if there is no
+ * key strictly less than the given key, or null if there is no
* such entry. The returned entry does not support
* the Entry.setValue method.
*
* @param key the key.
* @return an Entry with greatest key less than the given
- * key, or null if there is no such Entry.
+ * key, or null if there is no such Entry.
* @throws ClassCastException if key cannot be compared with the keys
* currently in the map.
* @throws NullPointerException if key is null.
@@ -2151,13 +2364,29 @@ public class ConcurrentSkipListMap
}
/**
- * Returns a key-value mapping associated with the greatest
- * key less than or equal to the given key, or null if there is no
- * such entry. The returned entry does not support
+ * Returns the greatest key strictly less than the given key, or
+ * null if there is no such key.
+ *
+ * @param key the key.
+ * @return the greatest key less than the given
+ * key, or null if there is no such key.
+ * @throws ClassCastException if key cannot be compared with the keys
+ * currently in the map.
+ * @throws NullPointerException if key is null.
+ */
+ public K lowerKey(K key) {
+ Node n = findNear(key, LT);
+ return (n == null)? null : n.key;
+ }
+
+ /**
+ * Returns a key-value mapping associated with the greatest key
+ * less than or equal to the given key, or null if there
+ * is no such entry. The returned entry does not support
* the Entry.setValue method.
*
* @param key the key.
- * @return an Entry associated with floor of given key, or null
+ * @return an Entry associated with floor of given key, or null
* if there is no such Entry.
* @throws ClassCastException if key cannot be compared with the keys
* currently in the map.
@@ -2168,14 +2397,31 @@ public class ConcurrentSkipListMap
}
/**
- * Returns a key-value mapping associated with the least
- * key strictly greater than the given key, or null if there is no
- * such entry. The returned entry does not support
+ * Returns the greatest key
+ * less than or equal to the given key, or null if there
+ * is no such key.
+ *
+ * @param key the key.
+ * @return the floor of given key, or null if there is no
+ * such key.
+ * @throws ClassCastException if key cannot be compared with the keys
+ * currently in the map.
+ * @throws NullPointerException if key is null.
+ */
+ public K floorKey(K key) {
+ Node n = findNear(key, LT|EQ);
+ return (n == null)? null : n.key;
+ }
+
+ /**
+ * Returns a key-value mapping associated with the least key
+ * strictly greater than the given key, or null if there
+ * is no such entry. The returned entry does not support
* the Entry.setValue method.
*
* @param key the key.
* @return an Entry with least key greater than the given key, or
- * null if there is no such Entry.
+ * null if there is no such Entry.
* @throws ClassCastException if key cannot be compared with the keys
* currently in the map.
* @throws NullPointerException if key is null.
@@ -2185,12 +2431,28 @@ public class ConcurrentSkipListMap
}
/**
+ * Returns the least key strictly greater than the given key, or
+ * null if there is no such key.
+ *
+ * @param key the key.
+ * @return the least key greater than the given key, or
+ * null if there is no such key.
+ * @throws ClassCastException if key cannot be compared with the keys
+ * currently in the map.
+ * @throws NullPointerException if key is null.
+ */
+ public K higherKey(K key) {
+ Node n = findNear(key, GT);
+ return (n == null)? null : n.key;
+ }
+
+ /**
* Returns a key-value mapping associated with the least
- * key in this map, or null if the map is empty.
+ * key in this map, or null if the map is empty.
* The returned entry does not support
* the Entry.setValue method.
*
- * @return an Entry with least key, or null
+ * @return an Entry with least key, or null
* if the map is empty.
*/
public Map.Entry firstEntry() {
@@ -2206,11 +2468,11 @@ public class ConcurrentSkipListMap
/**
* Returns a key-value mapping associated with the greatest
- * key in this map, or null if the map is empty.
+ * key in this map, or null if the map is empty.
* The returned entry does not support
* the Entry.setValue method.
*
- * @return an Entry with greatest key, or null
+ * @return an Entry with greatest key, or null
* if the map is empty.
*/
public Map.Entry lastEntry() {
@@ -2226,37 +2488,39 @@ public class ConcurrentSkipListMap
/**
* Removes and returns a key-value mapping associated with
- * the least key in this map, or null if the map is empty.
+ * the least key in this map, or null if the map is empty.
* The returned entry does not support
* the Entry.setValue method.
*
- * @return the removed first entry of this map, or null
+ * @return the removed first entry of this map, or null
* if the map is empty.
*/
public Map.Entry pollFirstEntry() {
- return doRemoveFirstEntry();
+ return (SnapshotEntry)doRemoveFirst(false);
}
/**
* Removes and returns a key-value mapping associated with
- * the greatest key in this map, or null if the map is empty.
+ * the greatest key in this map, or null if the map is empty.
* The returned entry does not support
* the Entry.setValue method.
*
- * @return the removed last entry of this map, or null
+ * @return the removed last entry of this map, or null
* if the map is empty.
*/
public Map.Entry pollLastEntry() {
- return doRemoveLastEntry();
+ return (SnapshotEntry)doRemoveLast(false);
}
+
/* ---------------- Iterators -------------- */
/**
- * Base of iterator classes.
- * (Six kinds: {key, value, entry} X {map, submap})
+ * Base of ten kinds of iterator classes:
+ * ascending: {map, submap} X {key, value, entry}
+ * descending: {map, submap} X {key, entry}
*/
- abstract class ConcurrentSkipListMapIterator {
+ abstract class Iter {
/** the last node returned by next() */
Node last;
/** the next node to return from next(); */
@@ -2264,8 +2528,14 @@ public class ConcurrentSkipListMap
/** Cache of next value field to maintain weak consistency */
Object nextValue;
- /** Create normal iterator for entire range */
- ConcurrentSkipListMapIterator() {
+ Iter() {}
+
+ public final boolean hasNext() {
+ return next != null;
+ }
+
+ /** initialize ascending iterator for entire range */
+ final void initAscending() {
for (;;) {
next = findFirst();
if (next == null)
@@ -2277,11 +2547,11 @@ public class ConcurrentSkipListMap
}
/**
- * Create a submap iterator starting at given least key, or
- * first node if least is null, but not greater or equal to
- * fence, or end if fence is null.
+ * initialize ascending iterator starting at given least key,
+ * or first node if least is null, but not greater or
+ * equal to fence, or end if fence is null.
*/
- ConcurrentSkipListMapIterator(K least, K fence) {
+ final void initAscending(K least, K fence) {
for (;;) {
next = findCeiling(least);
if (next == null)
@@ -2296,12 +2566,8 @@ public class ConcurrentSkipListMap
}
}
}
-
- public final boolean hasNext() {
- return next != null;
- }
-
- final void advance() {
+ /** advance next to higher entry */
+ final void ascend() {
if ((last = next) == null)
throw new NoSuchElementException();
for (;;) {
@@ -2315,9 +2581,9 @@ public class ConcurrentSkipListMap
}
/**
- * Version of advance for submaps to stop at fence
+ * Version of ascend for submaps to stop at fence
*/
- final void advance(K fence) {
+ final void ascend(K fence) {
if ((last = next) == null)
throw new NoSuchElementException();
for (;;) {
@@ -2335,6 +2601,77 @@ public class ConcurrentSkipListMap
}
}
+ /** initialize descending iterator for entire range */
+ final void initDescending() {
+ for (;;) {
+ next = findLast();
+ if (next == null)
+ break;
+ nextValue = next.value;
+ if (nextValue != null && nextValue != next)
+ break;
+ }
+ }
+
+ /**
+ * initialize descending iterator starting at key less
+ * than or equal to given fence key, or
+ * last node if fence is null, but not less than
+ * least, or beginning if lest is null.
+ */
+ final void initDescending(K least, K fence) {
+ for (;;) {
+ next = findLower(fence);
+ if (next == null)
+ break;
+ nextValue = next.value;
+ if (nextValue != null && nextValue != next) {
+ if (least != null && compare(least, next.key) > 0) {
+ next = null;
+ nextValue = null;
+ }
+ break;
+ }
+ }
+ }
+
+ /** advance next to lower entry */
+ final void descend() {
+ if ((last = next) == null)
+ throw new NoSuchElementException();
+ K k = last.key;
+ for (;;) {
+ next = findNear(k, LT);
+ if (next == null)
+ break;
+ nextValue = next.value;
+ if (nextValue != null && nextValue != next)
+ break;
+ }
+ }
+
+ /**
+ * Version of descend for submaps to stop at least
+ */
+ final void descend(K least) {
+ if ((last = next) == null)
+ throw new NoSuchElementException();
+ K k = last.key;
+ for (;;) {
+ next = findNear(k, LT);
+ if (next == null)
+ break;
+ nextValue = next.value;
+ if (nextValue != null && nextValue != next) {
+ if (least != null && compare(least, next.key) > 0) {
+ next = null;
+ nextValue = null;
+ }
+ break;
+ }
+ }
+ }
+
public void remove() {
Node l = last;
if (l == null)
@@ -2343,22 +2680,80 @@ public class ConcurrentSkipListMap
// unlink from here. Using remove is fast enough.
ConcurrentSkipListMap.this.remove(l.key);
}
+
+ }
+
+ final class ValueIterator extends Iter implements Iterator {
+ ValueIterator() {
+ initAscending();
+ }
+ public V next() {
+ Object v = nextValue;
+ ascend();
+ return (V)v;
+ }
+ }
+
+ final class KeyIterator extends Iter implements Iterator {
+ KeyIterator() {
+ initAscending();
+ }
+ public K next() {
+ Node n = next;
+ ascend();
+ return n.key;
+ }
}
- final class ValueIterator extends ConcurrentSkipListMapIterator
- implements Iterator {
+ class SubMapValueIterator extends Iter implements Iterator {
+ final K fence;
+ SubMapValueIterator(K least, K fence) {
+ initAscending(least, fence);
+ this.fence = fence;
+ }
+
public V next() {
Object v = nextValue;
- advance();
+ ascend(fence);
return (V)v;
}
}
- final class KeyIterator extends ConcurrentSkipListMapIterator
- implements Iterator {
+ final class SubMapKeyIterator extends Iter implements Iterator {
+ final K fence;
+ SubMapKeyIterator(K least, K fence) {
+ initAscending(least, fence);
+ this.fence = fence;
+ }
+
+ public K next() {
+ Node n = next;
+ ascend(fence);
+ return n.key;
+ }
+ }
+
+ final class DescendingKeyIterator extends Iter implements Iterator {
+ DescendingKeyIterator() {
+ initDescending();
+ }
public K next() {
Node n = next;
- advance();
+ descend();
+ return n.key;
+ }
+ }
+
+ final class DescendingSubMapKeyIterator extends Iter implements Iterator {
+ final K least;
+ DescendingSubMapKeyIterator(K least, K fence) {
+ initDescending(least, fence);
+ this.least = least;
+ }
+
+ public K next() {
+ Node n = next;
+ descend(least);
return n.key;
}
}
@@ -2368,23 +2763,11 @@ public class ConcurrentSkipListMap
* elsewhere of using the iterator itself to represent entries,
* thus avoiding having to create entry objects in next().
*/
- class EntryIterator extends ConcurrentSkipListMapIterator
- implements Map.Entry, Iterator> {
+ abstract class EntryIter extends Iter implements Map.Entry {
/** Cache of last value returned */
Object lastValue;
- EntryIterator() {
- super();
- }
-
- EntryIterator(K least, K fence) {
- super(least, fence);
- }
-
- public Map.Entry next() {
- lastValue = nextValue;
- advance();
- return this;
+ EntryIter() {
}
public K getKey() {
@@ -2431,56 +2814,60 @@ public class ConcurrentSkipListMap
}
}
- /**
- * Submap iterators start at given starting point at beginning of
- * submap range, and advance until they are at end of range.
- */
- class SubMapEntryIterator extends EntryIterator {
+ final class EntryIterator extends EntryIter
+ implements Iterator> {
+ EntryIterator() {
+ initAscending();
+ }
+ public Map.Entry next() {
+ lastValue = nextValue;
+ ascend();
+ return this;
+ }
+ }
+
+ final class SubMapEntryIterator extends EntryIter
+ implements Iterator> {
final K fence;
SubMapEntryIterator(K least, K fence) {
- super(least, fence);
+ initAscending(least, fence);
this.fence = fence;
}
public Map.Entry next() {
lastValue = nextValue;
- advance(fence);
+ ascend(fence);
return this;
}
}
- class SubMapValueIterator extends ConcurrentSkipListMapIterator
- implements Iterator {
- final K fence;
- SubMapValueIterator(K least, K fence) {
- super(least, fence);
- this.fence = fence;
+ final class DescendingEntryIterator extends EntryIter
+ implements Iterator> {
+ DescendingEntryIterator() {
+ initDescending();
}
-
- public V next() {
- Object v = nextValue;
- advance(fence);
- return (V)v;
+ public Map.Entry next() {
+ lastValue = nextValue;
+ descend();
+ return this;
}
}
- class SubMapKeyIterator extends ConcurrentSkipListMapIterator
- implements Iterator {
- final K fence;
- SubMapKeyIterator(K least, K fence) {
- super(least, fence);
- this.fence = fence;
+ final class DescendingSubMapEntryIterator extends EntryIter
+ implements Iterator> {
+ final K least;
+ DescendingSubMapEntryIterator(K least, K fence) {
+ initDescending(least, fence);
+ this.least = least;
}
- public K next() {
- Node n = next;
- advance(fence);
- return n.key;
+ public Map.Entry next() {
+ lastValue = nextValue;
+ descend(least);
+ return this;
}
}
- /* ---------------- Utilities for views, sets, submaps -------------- */
-
// Factory methods for iterators needed by submaps and/or
// ConcurrentSkipListSet
@@ -2488,159 +2875,33 @@ public class ConcurrentSkipListMap
return new KeyIterator();
}
- SubMapEntryIterator subMapEntryIterator(K least, K fence) {
- return new SubMapEntryIterator(least, fence);
- }
-
- SubMapKeyIterator subMapKeyIterator(K least, K fence) {
- return new SubMapKeyIterator(least, fence);
- }
-
- SubMapValueIterator subMapValueIterator(K least, K fence) {
- return new SubMapValueIterator(least, fence);
- }
-
-
- /**
- * Version of remove with boolean return. Needed by
- * view classes and ConcurrentSkipListSet
- */
- boolean removep(Object key) {
- return doRemove(key, null) != null;
- }
-
- /**
- * Return SnapshotEntry for results of findNear ofter screening
- * to ensure result is in given range. Needed by submaps.
- * @param kkey the key
- * @param rel the relation -- OR'ed combination of EQ, LT, GT
- * @param least minimum allowed key value
- * @param fence key greater than maximum allowed key value
- * @return Entry fitting relation, or null if no such
- */
- SnapshotEntry getNear(K kkey, int rel, K least, K fence) {
- K key = kkey;
- // Don't return keys less than least
- if ((rel & LT) == 0) {
- if (compare(key, least) < 0) {
- key = least;
- rel = rel | EQ;
- }
- }
-
- for (;;) {
- Node n = findNear(key, rel);
- if (n == null || !inHalfOpenRange(n.key, least, fence))
- return null;
- SnapshotEntry e = n.createSnapshot();
- if (e != null)
- return e;
- }
- }
-
- // Methods expanding out relational operations for submaps
-
- /**
- * Return ceiling, or first node if key is null
- */
- Node findCeiling(K key) {
- return (key == null)? findFirst() : findNear(key, GT|EQ);
+ Iterator descendingKeyIterator() {
+ return new DescendingKeyIterator();
}
- /**
- * Return lower node, or last node if key is null
- */
- Node findLower(K key) {
- return (key == null)? findLast() : findNear(key, LT);
- }
-
- /**
- * Find and remove least element of subrange.
- */
- SnapshotEntry removeFirstEntryOfSubrange(K least, K fence) {
- for (;;) {
- Node n = findCeiling(least);
- if (n == null)
- return null;
- K k = n.key;
- if (fence != null && compare(k, fence) >= 0)
- return null;
- V v = doRemove(k, null);
- if (v != null)
- return new SnapshotEntry(k,v);
- }
- }
-
-
- /**
- * Find and remove greatest element of subrange.
- */
- SnapshotEntry removeLastEntryOfSubrange(K least, K fence) {
- for (;;) {
- Node n = findLower(fence);
- if (n == null)
- return null;
- K k = n.key;
- if (least != null && compare(k, least) < 0)
- return null;
- V v = doRemove(k, null);
- if (v != null)
- return new SnapshotEntry(k,v);
- }
- }
-
-
- SnapshotEntry getCeiling(K key, K least, K fence) {
- return getNear(key, GT|EQ, least, fence);
- }
-
- SnapshotEntry getLower(K key, K least, K fence) {
- return getNear(key, LT, least, fence);
- }
-
- SnapshotEntry getFloor(K key, K least, K fence) {
- return getNear(key, LT|EQ, least, fence);
- }
-
- SnapshotEntry getHigher(K key, K least, K fence) {
- return getNear(key, GT, least, fence);
- }
-
- // Key-returning relational methods for ConcurrentSkipListSet
-
- K ceilingKey(K key) {
- Node n = findNear(key, GT|EQ);
- return (n == null)? null : n.key;
- }
-
- K lowerKey(K key) {
- Node n = findNear(key, LT);
- return (n == null)? null : n.key;
+ SubMapEntryIterator subMapEntryIterator(K least, K fence) {
+ return new SubMapEntryIterator(least, fence);
}
- K floorKey(K key) {
- Node n = findNear(key, LT|EQ);
- return (n == null)? null : n.key;
+ DescendingSubMapEntryIterator descendingSubMapEntryIterator(K least, K fence) {
+ return new DescendingSubMapEntryIterator(least, fence);
}
- K higherKey(K key) {
- Node n = findNear(key, GT);
- return (n == null)? null : n.key;
+ SubMapKeyIterator subMapKeyIterator(K least, K fence) {
+ return new SubMapKeyIterator(least, fence);
}
- K lowestKey() {
- Node n = findFirst();
- return (n == null)? null : n.key;
+ DescendingSubMapKeyIterator descendingSubMapKeyIterator(K least, K fence) {
+ return new DescendingSubMapKeyIterator(least, fence);
}
- K highestKey() {
- Node n = findLast();
- return (n == null)? null : n.key;
+ SubMapValueIterator subMapValueIterator(K least, K fence) {
+ return new SubMapValueIterator(least, fence);
}
/* ---------------- Views -------------- */
- final class KeySet extends AbstractSet {
+ class KeySet extends AbstractSet {
public Iterator iterator() {
return new KeyIterator();
}
@@ -2673,6 +2934,11 @@ public class ConcurrentSkipListMap
}
}
+ class DescendingKeySet extends KeySet {
+ public Iterator iterator() {
+ return new DescendingKeyIterator();
+ }
+ }
final class Values extends AbstractCollection {
public Iterator iterator() {
@@ -2704,7 +2970,7 @@ public class ConcurrentSkipListMap
}
}
- final class EntrySet extends AbstractSet> {
+ class EntrySet extends AbstractSet> {
public Iterator> iterator() {
return new EntryIterator();
}
@@ -2719,7 +2985,8 @@ public class ConcurrentSkipListMap
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
- return ConcurrentSkipListMap.this.remove(e.getKey(), e.getValue());
+ return ConcurrentSkipListMap.this.remove(e.getKey(),
+ e.getValue());
}
public boolean isEmpty() {
return ConcurrentSkipListMap.this.isEmpty();
@@ -2733,24 +3000,24 @@ public class ConcurrentSkipListMap
public Object[] toArray() {
Collection> c = new ArrayList>();
- for (Node n = findFirst(); n != null; n = n.next) {
- Map.Entry e = n.createSnapshot();
- if (e != null)
- c.add(e);
- }
+ for (Map.Entry e : this)
+ c.add(new SnapshotEntry(e.getKey(), e.getValue()));
return c.toArray();
}
public T[] toArray(T[] a) {
Collection> c = new ArrayList>();
- for (Node n = findFirst(); n != null; n = n.next) {
- Map.Entry e = n.createSnapshot();
- if (e != null)
- c.add(e);
- }
+ for (Map.Entry e : this)
+ c.add(new SnapshotEntry(e.getKey(), e.getValue()));
return c.toArray(a);
}
}
+ class DescendingEntrySet extends EntrySet {
+ public Iterator> iterator() {
+ return new DescendingEntryIterator();
+ }
+ }
+
/**
* Submaps returned by {@link ConcurrentSkipListMap} submap operations
* represent a subrange of mappings of their underlying
@@ -2776,17 +3043,21 @@ public class ConcurrentSkipListMap
private transient Set keySetView;
private transient Set> entrySetView;
private transient Collection valuesView;
+ private transient Set descendingKeySetView;
+ private transient Set> descendingEntrySetView;
/**
* Creates a new submap.
- * @param least inclusive least value, or null if from start
- * @param fence exclusive upper bound or null if to end
+ * @param least inclusive least value, or null if from start
+ * @param fence exclusive upper bound or null if to end
* @throws IllegalArgumentException if least and fence nonnull
* and least greater than fence
*/
ConcurrentSkipListSubMap(ConcurrentSkipListMap map,
K least, K fence) {
- if (least != null && fence != null && map.compare(least, fence) > 0)
+ if (least != null &&
+ fence != null &&
+ map.compare(least, fence) > 0)
throw new IllegalArgumentException("inconsistent range");
this.m = map;
this.least = least;
@@ -2833,7 +3104,7 @@ public class ConcurrentSkipListMap
/**
* Returns least key. Needed by ConcurrentSkipListSet
- * @return least key or null if from start
+ * @return least key or null if from start
*/
K getLeast() {
return least;
@@ -2841,126 +3112,35 @@ public class ConcurrentSkipListMap
/**
* Returns fence key. Needed by ConcurrentSkipListSet
- * @return fence key or null of to end
+ * @return fence key or null of to end
*/
K getFence() {
return fence;
}
- /**
- * Non-exception throwing version of firstKey needed by
- * ConcurrentSkipListSubSet
- * @return first key, or null if empty
- */
- K lowestKey() {
- ConcurrentSkipListMap.Node n = firstNode();
- if (isBeforeEnd(n))
- return n.key;
- else
- return null;
- }
-
- /**
- * Non-exception throwing version of highestKey needed by
- * ConcurrentSkipListSubSet
- * @return last key, or null if empty
- */
- K highestKey() {
- ConcurrentSkipListMap.Node n = lastNode();
- if (isBeforeEnd(n))
- return n.key;
- else
- return null;
- }
/* ---------------- Map API methods -------------- */
- /**
- * Returns true if this map contains a mapping for
- * the specified key.
- * @param key key whose presence in this map is to be tested.
- * @return true if this map contains a mapping for
- * the specified key.
- * @throws ClassCastException if the key cannot be compared
- * with the keys currently in the map.
- * @throws NullPointerException if the key is null.
- */
public boolean containsKey(Object key) {
K k = (K)key;
return inHalfOpenRange(k) && m.containsKey(k);
}
- /**
- * Returns the value to which this map maps the specified key.
- * Returns null if the map contains no mapping for
- * this key.
- *
- * @param key key whose associated value is to be returned.
- * @return the value to which this map maps the specified key,
- * or null if the map contains no mapping for the
- * key.
- * @throws ClassCastException if the key cannot be compared
- * with the keys currently in the map.
- * @throws NullPointerException if the key is null.
- */
public V get(Object key) {
K k = (K)key;
return ((!inHalfOpenRange(k)) ? null : m.get(k));
}
- /**
- * Associates the specified value with the specified key in
- * this map. If the map previously contained a mapping for
- * this key, the old value is replaced.
- *
- * @param key key with which the specified value is to be associated.
- * @param value value to be associated with the specified key.
- *
- * @return previous value associated with specified key, or
- * null if there was no mapping for key.
- * @throws ClassCastException if the key cannot be compared
- * with the keys currently in the map.
- * @throws IllegalArgumentException if key outside range of
- * this submap.
- * @throws NullPointerException if the key or value are null.
- */
public V put(K key, V value) {
checkKey(key);
return m.put(key, value);
}
- /**
- * Removes the mapping for this key from this Map if present.
- *
- * @param key key for which mapping should be removed
- * @return previous value associated with specified key, or
- * null if there was no mapping for key.
- *
- * @throws ClassCastException if the key cannot be compared
- * with the keys currently in the map.
- * @throws NullPointerException if the key is null.
- */
public V remove(Object key) {
K k = (K)key;
return (!inHalfOpenRange(k))? null : m.remove(k);
}
- /**
- * Returns the number of elements in this map. If this map
- * contains more than Integer.MAX_VALUE elements, it
- * returns Integer.MAX_VALUE.
- *
- * Beware that, unlike in most collections, this method is
- * NOT a constant-time operation. Because of the
- * asynchronous nature of these maps, determining the current
- * number of elements requires traversing them all to count them.
- * Additionally, it is possible for the size to change during
- * execution of this method, in which case the returned result
- * will be inaccurate. Thus, this method is typically not very
- * useful in concurrent applications.
- *
- * @return the number of elements in this map.
- */
public int size() {
long count = 0;
for (ConcurrentSkipListMap.Node n = firstNode();
@@ -2972,24 +3152,10 @@ public class ConcurrentSkipListMap
return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count;
}
- /**
- * Returns true if this map contains no key-value mappings.
- * @return true if this map contains no key-value mappings.
- */
public boolean isEmpty() {
return !isBeforeEnd(firstNode());
}
- /**
- * Returns true if this map maps one or more keys to the
- * specified value. This operation requires time linear in the
- * Map size.
- *
- * @param value value whose presence in this Map is to be tested.
- * @return true if a mapping to value exists;
- * false otherwise.
- * @throws NullPointerException if the value is null.
- */
public boolean containsValue(Object value) {
if (value == null)
throw new NullPointerException();
@@ -3003,9 +3169,6 @@ public class ConcurrentSkipListMap
return false;
}
- /**
- * Removes all mappings from this map.
- */
public void clear() {
for (ConcurrentSkipListMap.Node n = firstNode();
isBeforeEnd(n);
@@ -3017,102 +3180,21 @@ public class ConcurrentSkipListMap
/* ---------------- ConcurrentMap API methods -------------- */
- /**
- * If the specified key is not already associated
- * with a value, associate it with the given value.
- * This is equivalent to
- *
- * if (!map.containsKey(key))
- * return map.put(key, value);
- * else
- * return map.get(key);
- *
- * Except that the action is performed atomically.
- * @param key key with which the specified value is to be associated.
- * @param value value to be associated with the specified key.
- * @return previous value associated with specified key, or
- * null if there was no mapping for key.
- *
- * @throws ClassCastException if the key cannot be compared
- * with the keys currently in the map.
- * @throws IllegalArgumentException if key outside range of
- * this submap.
- * @throws NullPointerException if the key or value are null.
- */
public V putIfAbsent(K key, V value) {
checkKey(key);
return m.putIfAbsent(key, value);
}
- /**
- * Remove entry for key only if currently mapped to given value.
- * Acts as
- *
- * if ((map.containsKey(key) && map.get(key).equals(value)) {
- * map.remove(key);
- * return true;
- * } else return false;
- *
- * except that the action is performed atomically.
- * @param key key with which the specified value is associated.
- * @param value value associated with the specified key.
- * @return true if the value was removed, false otherwise
- * @throws ClassCastException if the key cannot be compared
- * with the keys currently in the map.
- * @throws NullPointerException if the key or value are
- * null.
- */
public boolean remove(Object key, Object value) {
K k = (K)key;
return inHalfOpenRange(k) && m.remove(k, value);
}
- /**
- * Replace entry for key only if currently mapped to given value.
- * Acts as
- *
- * if ((map.containsKey(key) && map.get(key).equals(oldValue)) {
- * map.put(key, newValue);
- * return true;
- * } else return false;
- *
- * except that the action is performed atomically.
- * @param key key with which the specified value is associated.
- * @param oldValue value expected to be associated with the specified key.
- * @param newValue value to be associated with the specified key.
- * @return true if the value was replaced
- * @throws ClassCastException if the key cannot be compared
- * with the keys currently in the map.
- * @throws IllegalArgumentException if key outside range of
- * this submap.
- * @throws NullPointerException if key, oldValue or newValue
- * are null.
- */
public boolean replace(K key, V oldValue, V newValue) {
checkKey(key);
return m.replace(key, oldValue, newValue);
}
- /**
- * Replace entry for key only if currently mapped to some value.
- * Acts as
- *
- * if ((map.containsKey(key)) {
- * return map.put(key, value);
- * } else return null;
- *
- * except that the action is performed atomically.
- * @param key key with which the specified value is associated.
- * @param value value to be associated with the specified key.
- * @return previous value associated with specified key, or
- * null if there was no mapping for key.
- * @throws ClassCastException if the key cannot be compared
- * with the keys currently in the map.
- * @throws IllegalArgumentException if key outside range of
- * this submap.
- * @throws NullPointerException if the key or value are
- * null.
- */
public V replace(K key, V value) {
checkKey(key);
return m.replace(key, value);
@@ -3120,23 +3202,10 @@ public class ConcurrentSkipListMap
/* ---------------- SortedMap API methods -------------- */
- /**
- * Returns the comparator used to order this map, or null
- * if this map uses its keys' natural order.
- *
- * @return the comparator associated with this map, or
- * null if it uses its keys' natural sort method.
- */
public Comparator comparator() {
return m.comparator();
}
- /**
- * Returns the first (lowest) key currently in this map.
- *
- * @return the first (lowest) key currently in this map.
- * @throws NoSuchElementException Map is empty.
- */
public K firstKey() {
ConcurrentSkipListMap.Node n = firstNode();
if (isBeforeEnd(n))
@@ -3145,12 +3214,6 @@ public class ConcurrentSkipListMap
throw new NoSuchElementException();
}
- /**
- * Returns the last (highest) key currently in this map.
- *
- * @return the last (highest) key currently in this map.
- * @throws NoSuchElementException Map is empty.
- */
public K lastKey() {
ConcurrentSkipListMap.Node n = lastNode();
if (n != null) {
@@ -3161,32 +3224,6 @@ public class ConcurrentSkipListMap
throw new NoSuchElementException();
}
- /**
- * Returns a view of the portion of this map whose keys range
- * from fromKey, inclusive, to toKey,
- * exclusive. (If fromKey and toKey are
- * equal, the returned sorted map is empty.) The returned
- * sorted map is backed by this map, so changes in the
- * returned sorted map are reflected in this map, and
- * vice-versa.
-
- * @param fromKey low endpoint (inclusive) of the subMap.
- * @param toKey high endpoint (exclusive) of the subMap.
- *
- * @return a view of the portion of this map whose keys range
- * from fromKey, inclusive, to toKey,
- * exclusive.
- *
- * @throws ClassCastException if fromKey and
- * toKey cannot be compared to one another using this
- * map's comparator (or, if the map has no comparator, using
- * natural ordering).
- * @throws IllegalArgumentException if fromKey is
- * greater than toKey or either key is outside of
- * the range of this submap.
- * @throws NullPointerException if fromKey or
- * toKey is null.
- */
public ConcurrentNavigableMap subMap(K fromKey, K toKey) {
if (fromKey == null || toKey == null)
throw new NullPointerException();
@@ -3195,24 +3232,6 @@ public class ConcurrentSkipListMap
return new ConcurrentSkipListSubMap(m, fromKey, toKey);
}
- /**
- * Returns a view of the portion of this map whose keys are
- * strictly less than toKey. The returned sorted map
- * is backed by this map, so changes in the returned sorted
- * map are reflected in this map, and vice-versa.
- * @param toKey high endpoint (exclusive) of the headMap.
- * @return a view of the portion of this map whose keys are
- * strictly less than toKey.
- *
- * @throws ClassCastException if toKey is not
- * compatible with this map's comparator (or, if the map has
- * no comparator, if toKey does not implement
- * Comparable).
- * @throws IllegalArgumentException if toKey is
- * outside of the range of this submap.
- * @throws NullPointerException if toKey is
- * null.
- */
public ConcurrentNavigableMap headMap(K toKey) {
if (toKey == null)
throw new NullPointerException();
@@ -3221,23 +3240,6 @@ public class ConcurrentSkipListMap
return new ConcurrentSkipListSubMap(m, least, toKey);
}
- /**
- * Returns a view of the portion of this map whose keys are
- * greater than or equal to fromKey. The returned sorted
- * map is backed by this map, so changes in the returned sorted
- * map are reflected in this map, and vice-versa.
- * @param fromKey low endpoint (inclusive) of the tailMap.
- * @return a view of the portion of this map whose keys are
- * greater than or equal to fromKey.
- * @throws ClassCastException if fromKey is not
- * compatible with this map's comparator (or, if the map has
- * no comparator, if fromKey does not implement
- * Comparable).
- * @throws IllegalArgumentException if fromKey is
- * outside of the range of this submap.
- * @throws NullPointerException if fromKey is
- * null.
- */
public ConcurrentNavigableMap tailMap(K fromKey) {
if (fromKey == null)
throw new NullPointerException();
@@ -3248,83 +3250,47 @@ public class ConcurrentSkipListMap
/* ---------------- Relational methods -------------- */
- /**
- * Returns a key-value mapping associated with the least key
- * greater than or equal to the given key, or null if there is
- * no such entry. The returned entry does not support
- * the Entry.setValue method.
- *
- * @param key the key.
- * @return an Entry associated with ceiling of given key, or null
- * if there is no such Entry.
- * @throws ClassCastException if key cannot be compared with the keys
- * currently in the map.
- * @throws NullPointerException if key is null.
- */
public Map.Entry ceilingEntry(K key) {
- return m.getCeiling(key, least, fence);
+ return (SnapshotEntry)
+ m.getNear(key, m.GT|m.EQ, least, fence, false);
+ }
+
+ public K ceilingKey(K key) {
+ return (K)
+ m.getNear(key, m.GT|m.EQ, least, fence, true);
}
- /**
- * Returns a key-value mapping associated with the greatest
- * key strictly less than the given key, or null if there is no
- * such entry. The returned entry does not support
- * the Entry.setValue method.
- *
- * @param key the key.
- * @return an Entry with greatest key less than the given
- * key, or null if there is no such Entry.
- * @throws ClassCastException if key cannot be compared with the keys
- * currently in the map.
- * @throws NullPointerException if key is null.
- */
public Map.Entry lowerEntry(K key) {
- return m.getLower(key, least, fence);
+ return (SnapshotEntry)
+ m.getNear(key, m.LT, least, fence, false);
+ }
+
+ public K lowerKey(K key) {
+ return (K)
+ m.getNear(key, m.LT, least, fence, true);
}
- /**
- * Returns a key-value mapping associated with the greatest
- * key less than or equal to the given key, or null if there is no
- * such entry. The returned entry does not support
- * the Entry.setValue method.
- *
- * @param key the key.
- * @return an Entry associated with floor of given key, or null
- * if there is no such Entry.
- * @throws ClassCastException if key cannot be compared with the keys
- * currently in the map.
- * @throws NullPointerException if key is null.
- */
public Map.Entry floorEntry(K key) {
- return m.getFloor(key, least, fence);
+ return (SnapshotEntry)
+ m.getNear(key, m.LT|m.EQ, least, fence, false);
+ }
+
+ public K floorKey(K key) {
+ return (K)
+ m.getNear(key, m.LT|m.EQ, least, fence, true);
}
+
- /**
- * Returns a key-value mapping associated with the least
- * key strictly greater than the given key, or null if there is no
- * such entry. The returned entry does