diff options
Diffstat (limited to 'gcc-4.4.3/libjava/classpath/external/jsr166/java/util/concurrent/ConcurrentSkipListMap.java')
| -rw-r--r-- | gcc-4.4.3/libjava/classpath/external/jsr166/java/util/concurrent/ConcurrentSkipListMap.java | 3114 |
1 files changed, 3114 insertions, 0 deletions
diff --git a/gcc-4.4.3/libjava/classpath/external/jsr166/java/util/concurrent/ConcurrentSkipListMap.java b/gcc-4.4.3/libjava/classpath/external/jsr166/java/util/concurrent/ConcurrentSkipListMap.java new file mode 100644 index 000000000..bbb00a0f0 --- /dev/null +++ b/gcc-4.4.3/libjava/classpath/external/jsr166/java/util/concurrent/ConcurrentSkipListMap.java @@ -0,0 +1,3114 @@ +/* + * Written by Doug Lea with assistance from members of JCP JSR-166 + * Expert Group and released to the public domain, as explained at + * http://creativecommons.org/licenses/publicdomain + */ + +package java.util.concurrent; +import java.util.*; +import java.util.concurrent.atomic.*; + +/** + * A scalable concurrent {@link ConcurrentNavigableMap} implementation. + * The map is sorted according to the {@linkplain Comparable natural + * ordering} of its keys, or by a {@link Comparator} provided at map + * creation time, depending on which constructor is used. + * + * <p>This class implements a concurrent variant of <a + * href="http://www.cs.umd.edu/~pugh/">SkipLists</a> providing + * expected average <i>log(n)</i> time cost for the + * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and + * <tt>remove</tt> operations and their variants. Insertion, removal, + * update, and access operations safely execute concurrently by + * multiple threads. Iterators are <i>weakly consistent</i>, returning + * elements reflecting the state of the map at some point at or since + * the creation of the iterator. They do <em>not</em> throw {@link + * ConcurrentModificationException}, and may proceed concurrently with + * other operations. Ascending key ordered views and their iterators + * are faster than descending ones. + * + * <p>All <tt>Map.Entry</tt> pairs returned by methods in this class + * and its views represent snapshots of mappings at the time they were + * produced. They do <em>not</em> support the <tt>Entry.setValue</tt> + * method. (Note however that it is possible to change mappings in the + * associated map using <tt>put</tt>, <tt>putIfAbsent</tt>, or + * <tt>replace</tt>, depending on exactly which effect you need.) + * + * <p>Beware that, unlike in most collections, the <tt>size</tt> + * method is <em>not</em> a constant-time operation. Because of the + * asynchronous nature of these maps, determining the current number + * of elements requires a traversal of the elements. Additionally, + * the bulk operations <tt>putAll</tt>, <tt>equals</tt>, and + * <tt>clear</tt> are <em>not</em> guaranteed to be performed + * atomically. For example, an iterator operating concurrently with a + * <tt>putAll</tt> operation might view only some of the added + * elements. + * + * <p>This class and its views and iterators implement all of the + * <em>optional</em> methods of the {@link Map} and {@link Iterator} + * interfaces. Like most other concurrent collections, this class does + * <em>not</em> permit the use of <tt>null</tt> keys or values because some + * null return values cannot be reliably distinguished from the absence of + * elements. + * + * <p>This class is a member of the + * <a href="{@docRoot}/../technotes/guides/collections/index.html"> + * Java Collections Framework</a>. + * + * @author Doug Lea + * @param <K> the type of keys maintained by this map + * @param <V> the type of mapped values + * @since 1.6 + */ +public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V> + implements ConcurrentNavigableMap<K,V>, + Cloneable, + java.io.Serializable { + /* + * This class implements a tree-like two-dimensionally linked skip + * list in which the index levels are represented in separate + * nodes from the base nodes holding data. There are two reasons + * for taking this approach instead of the usual array-based + * structure: 1) Array based implementations seem to encounter + * more complexity and overhead 2) We can use cheaper algorithms + * for the heavily-traversed index lists than can be used for the + * base lists. Here's a picture of some of the basics for a + * possible list with 2 levels of index: + * + * Head nodes Index nodes + * +-+ 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 + * 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 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. + * + * Rather than using mark-bits to mark list deletions (which can + * be slow and space-intensive using AtomicMarkedReference), nodes + * use direct CAS'able next pointers. On deletion, instead of + * marking a pointer, they splice in another node that can be + * thought of as standing for a marked pointer (indicating this by + * using otherwise impossible field values). Using plain nodes + * acts roughly like "boxed" implementations of marked pointers, + * but uses new nodes only when nodes are deleted, not for every + * link. This requires less space and supports faster + * traversal. Even if marked references were better supported by + * JVMs, traversal using this technique might still be faster + * because any search need only read ahead one more node than + * otherwise required (to check for trailing marker) rather than + * unmasking mark bits or whatever on each read. + * + * This approach maintains the essential property needed in the HM + * algorithm of changing the next-pointer of a deleted node so + * that any other CAS of it will fail, but implements the idea by + * changing the pointer to point to a different node, not by + * marking it. While it would be possible to further squeeze + * space by defining marker nodes not to have key/value fields, it + * isn't worth the extra type-testing overhead. The deletion + * markers are rarely encountered during traversal and are + * normally quickly garbage collected. (Note that this technique + * would not work well in systems without garbage collection.) + * + * In addition to using deletion markers, the lists also use + * nullness of value fields to indicate deletion, in a style + * similar to typical lazy-deletion schemes. If a node's value is + * null, then it is considered logically deleted and ignored even + * though it is still reachable. This maintains proper control of + * concurrent replace vs delete operations -- an attempted replace + * must fail if a delete beat it by nulling field, and a delete + * must return the last non-null value held in the field. (Note: + * Null, rather than some special marker, is used for value fields + * here because it just so happens to mesh with the Map API + * requirement that method get returns null if there is no + * mapping, which allows nodes to remain concurrently readable + * even when deleted. Using any other marker value here would be + * messy at best.) + * + * 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 + * the node consider this mapping to exist. However, other + * ongoing insertions and deletions might still modify + * n's next pointer. + * + * 2. CAS n's next pointer to point to a new marker node. + * From this point on, no other nodes can be appended to n. + * which avoids deletion errors in CAS-based linked lists. + * + * +------+ +------+ +------+ +------+ + * ... | 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 + * helped out by marking and/or unlinking. This helping-out + * ensures that no thread can become stuck waiting for progress of + * the deleting thread. The use of marker nodes slightly + * complicates helping-out code because traversals must track + * consistent reads of up to four nodes (b, n, marker, f), not + * just (b, n, f), although the next field of a marker is + * immutable, and once a next field is CAS'ed to point to a + * marker, it never again changes, so this requires less care. + * + * Skip lists add indexing to this scheme, so that the base-level + * traversals start close to the locations being found, inserted + * or deleted -- usually base level traversals only traverse a few + * 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. + * + * Index levels are maintained as lists with volatile next fields, + * using CAS to link and unlink. Races are allowed in index-list + * operations that can (rarely) fail to link in a new index node + * or delete one. (We can't do this of course for data nodes.) + * However, even when this happens, the index lists remain sorted, + * so correctly serve as indices. This can impact performance, + * but since skip lists are probabilistic anyway, the net result + * is that under contention, the effective "p" value may be lower + * than its nominal value. And race windows are kept small enough + * that in practice these failures are rare, even under a lot of + * contention. + * + * The fact that retries (for both base and index lists) are + * relatively cheap due to indexing allows some minor + * simplifications of retry logic. Traversal restarts are + * performed after most "helping-out" CASes. This isn't always + * strictly necessary, but the implicit backoffs tend to help + * reduce other downstream failed CAS's enough to outweigh restart + * cost. This worsens the worst case, but seems to improve even + * highly contended cases. + * + * Unlike most skip-list implementations, index insertion and + * deletion here require a separate traversal pass occuring after + * the base-level action, to add or remove index nodes. This adds + * to single-threaded overhead, but improves contended + * multithreaded performance by narrowing interference windows, + * and allows deletion to ensure that all index nodes will be made + * unreachable upon return from a public remove operation, thus + * avoiding unwanted garbage retention. This is more important + * here than in some other data structures because we cannot null + * out node fields referencing user keys since they might still be + * read by other ongoing traversals. + * + * Indexing uses skip list parameters that maintain good search + * performance while using sparser-than-usual indices: The + * hardwired parameters k=1, p=0.5 (see method randomLevel) mean + * that about one-quarter of the nodes have indices. Of those that + * do, half have one level, a quarter have two, and so on (see + * Pugh's Skip List Cookbook, sec 3.4). The expected total space + * requirement for a map is slightly less than for the current + * implementation of java.util.TreeMap. + * + * Changing the level of the index (i.e, the height of the + * tree-like structure) also uses CAS. The head index has initial + * level/height of one. Creation of an index with height greater + * than the current level adds a level to the head index by + * CAS'ing on a new top-most head. To maintain good performance + * after a lot of removals, deletion methods heuristically try to + * reduce the height if the topmost levels appear to be empty. + * This may encounter races in which it possible (but rare) to + * reduce and "lose" a level just as it is about to contain an + * index (that will then never be encountered). This does no + * structural harm, and in practice appears to be a better option + * than allowing unrestrained growth of levels. + * + * The code for all this is more verbose than you'd like. Most + * operations entail locating an element (or position to insert an + * element). The code to do this can't be nicely factored out + * because subsequent uses require a snapshot of predecessor + * and/or successor and/or value fields which can't be returned + * all at once, at least not without creating yet another object + * to hold them -- creating such little objects is an especially + * bad idea for basic internal search operations because it adds + * to GC overhead. (This is one of the few times I've wished Java + * had macros.) Instead, some traversal code is interleaved within + * insertion and removal operations. The control logic to handle + * all the retry conditions is sometimes twisty. Most search is + * broken into 2 parts. findPredecessor() searches index nodes + * only, returning a base-level predecessor of the key. findNode() + * finishes out the base-level search. Even with this factoring, + * there is a fair amount of near-duplication of code to handle + * variants. + * + * 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 Hakan Sundell's + * thesis (http://www.cs.chalmers.se/~phs/). + * + * Given the use of tree-like index nodes, you might wonder why + * this doesn't use some kind of search tree instead, which would + * support somewhat faster search operations. The reason is that + * there are no known efficient lock-free insertion and deletion + * algorithms for search trees. The immutability of the "down" + * links of index nodes (as opposed to mutable "left" fields in + * true trees) makes this tractable using only CAS operations. + * + * Notation guide for local variables + * Node: b, n, f for predecessor, node, successor + * Index: q, r, d for index node, right, down. + * t for another index node + * Head: h + * Levels: j + * Keys: k, key + * Values: v, value + * Comparisons: c + */ + + private static final long serialVersionUID = -8627078645895051609L; + + /** + * Generates the initial random seed for the cheaper per-instance + * random number generators used in randomLevel. + */ + private static final Random seedGenerator = new Random(); + + /** + * Special value used to identify base-level header + */ + private static final Object BASE_HEADER = new Object(); + + /** + * The topmost head index of the skiplist. + */ + private transient volatile HeadIndex<K,V> head; + + /** + * The comparator used to maintain order in this map, or null + * if using natural ordering. + * @serial + */ + private final Comparator<? super K> comparator; + + /** + * Seed for simple random number generator. Not volatile since it + * doesn't matter too much if different threads don't see updates. + */ + private transient int randomSeed; + + /** Lazily initialized key set */ + private transient KeySet keySet; + /** Lazily initialized entry set */ + private transient EntrySet entrySet; + /** Lazily initialized values collection */ + private transient Values values; + /** Lazily initialized descending key set */ + private transient ConcurrentNavigableMap<K,V> descendingMap; + + /** + * Initializes or resets state. Needed by constructors, clone, + * clear, readObject. and ConcurrentSkipListSet.clone. + * (Note that comparator must be separately initialized.) + */ + final void initialize() { + keySet = null; + entrySet = null; + values = null; + descendingMap = null; + randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero + head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null), + null, null, 1); + } + + /** Updater for casHead */ + private static final + AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex> + headUpdater = AtomicReferenceFieldUpdater.newUpdater + (ConcurrentSkipListMap.class, HeadIndex.class, "head"); + + /** + * compareAndSet head node + */ + private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) { + return headUpdater.compareAndSet(this, cmp, val); + } + + /* ---------------- Nodes -------------- */ + + /** + * Nodes hold keys and values, and are singly linked in sorted + * order, possibly with some intervening marker nodes. The list is + * headed by a dummy node accessible as head.node. The value field + * is declared only as Object because it takes special non-V + * values for marker and header nodes. + */ + static final class Node<K,V> { + final K key; + volatile Object value; + volatile Node<K,V> next; + + /** + * Creates a new regular node. + */ + Node(K key, Object value, Node<K,V> next) { + this.key = key; + this.value = value; + this.next = next; + } + + /** + * Creates a new marker node. A marker is distinguished by + * having its value field point to itself. Marker nodes also + * have null keys, a fact that is exploited in a few places, + * but this doesn't distinguish markers from the base-level + * header node (head.node), which also has a null key. + */ + Node(Node<K,V> next) { + this.key = null; + this.value = this; + this.next = next; + } + + /** Updater for casNext */ + static final AtomicReferenceFieldUpdater<Node, Node> + nextUpdater = AtomicReferenceFieldUpdater.newUpdater + (Node.class, Node.class, "next"); + + /** Updater for casValue */ + static final AtomicReferenceFieldUpdater<Node, Object> + valueUpdater = AtomicReferenceFieldUpdater.newUpdater + (Node.class, Object.class, "value"); + + /** + * compareAndSet value field + */ + boolean casValue(Object cmp, Object val) { + return valueUpdater.compareAndSet(this, cmp, val); + } + + /** + * compareAndSet next field + */ + boolean casNext(Node<K,V> cmp, Node<K,V> val) { + return nextUpdater.compareAndSet(this, cmp, val); + } + + /** + * Returns true if this node is a marker. This method isn't + * actually called in any current code checking for markers + * because callers will have already read value field and need + * to use that read (not another done here) and so directly + * test if value points to node. + * @param n a possibly null reference to a node + * @return true if this node is a marker node + */ + boolean isMarker() { + return value == this; + } + + /** + * Returns true if this node is the header of base-level list. + * @return true if this node is header node + */ + boolean isBaseHeader() { + return value == BASE_HEADER; + } + + /** + * Tries to append a deletion marker to this node. + * @param f the assumed current successor of this node + * @return true if successful + */ + boolean appendMarker(Node<K,V> f) { + return casNext(f, new Node<K,V>(f)); + } + + /** + * Helps out a deletion by appending marker or unlinking from + * predecessor. This is called during traversals when value + * field seen to be null. + * @param b predecessor + * @param f successor + */ + void helpDelete(Node<K,V> b, Node<K,V> f) { + /* + * Rechecking links and then doing only one of the + * help-out stages per call tends to minimize CAS + * interference among helping threads. + */ + if (f == next && this == b.next) { + if (f == null || f.value != f) // not already marked + appendMarker(f); + else + b.casNext(this, f.next); + } + } + + /** + * Returns value if this node contains a valid key-value pair, + * else null. + * @return this node's value if it isn't a marker or header or + * is deleted, else null. + */ + V getValidValue() { + Object v = value; + if (v == this || v == BASE_HEADER) + return null; + return (V)v; + } + + /** + * Creates and returns a new SimpleImmutableEntry holding current + * mapping if this node holds a valid value, else null. + * @return new entry or null + */ + AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() { + V v = getValidValue(); + if (v == null) + return null; + return new AbstractMap.SimpleImmutableEntry<K,V>(key, v); + } + } + + /* ---------------- Indexing -------------- */ + + /** + * Index nodes represent the levels of the skip list. Note that + * even though both Nodes and Indexes have forward-pointing + * fields, they have different types and are handled in different + * ways, that can't nicely be captured by placing field in a + * shared abstract class. + */ + static class Index<K,V> { + final Node<K,V> node; + final Index<K,V> down; + volatile Index<K,V> right; + + /** + * Creates index node with given values. + */ + Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) { + this.node = node; + this.down = down; + this.right = right; + } + + /** Updater for casRight */ + static final AtomicReferenceFieldUpdater<Index, Index> + rightUpdater = AtomicReferenceFieldUpdater.newUpdater + (Index.class, Index.class, "right"); + + /** + * compareAndSet right field + */ + final boolean casRight(Index<K,V> cmp, Index<K,V> val) { + return rightUpdater.compareAndSet(this, cmp, val); + } + + /** + * Returns true if the node this indexes has been deleted. + * @return true if indexed node is known to be deleted + */ + final boolean indexesDeletedNode() { + return node.value == null; + } + + /** + * Tries to CAS newSucc as successor. To minimize races with + * unlink that may lose this index node, if the node being + * indexed is known to be deleted, it doesn't try to link in. + * @param succ the expected current successor + * @param newSucc the new successor + * @return true if successful + */ + final boolean link(Index<K,V> succ, Index<K,V> newSucc) { + Node<K,V> n = node; + newSucc.right = succ; + return n.value != null && casRight(succ, newSucc); + } + + /** + * Tries to CAS right field to skip over apparent successor + * succ. Fails (forcing a retraversal by caller) if this node + * is known to be deleted. + * @param succ the expected current successor + * @return true if successful + */ + final boolean unlink(Index<K,V> succ) { + return !indexesDeletedNode() && casRight(succ, succ.right); + } + } + + /* ---------------- Head nodes -------------- */ + + /** + * Nodes heading each level keep track of their level. + */ + static final class HeadIndex<K,V> extends Index<K,V> { + final int level; + HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) { + super(node, down, right); + this.level = level; + } + } + + /* ---------------- Comparison utilities -------------- */ + + /** + * Represents a key with a comparator as a Comparable. + * + * Because most sorted collections seem to use natural ordering on + * Comparables (Strings, Integers, etc), most internal methods are + * geared to use them. This is generally faster than checking + * per-comparison whether to use comparator or comparable because + * it doesn't require a (Comparable) cast for each comparison. + * (Optimizers can only sometimes remove such redundant checks + * themselves.) When Comparators are used, + * ComparableUsingComparators are created so that they act in the + * same way as natural orderings. This penalizes use of + * Comparators vs Comparables, which seems like the right + * tradeoff. + */ + static final class ComparableUsingComparator<K> implements Comparable<K> { + final K actualKey; + final Comparator<? super K> cmp; + ComparableUsingComparator(K key, Comparator<? super K> cmp) { + this.actualKey = key; + this.cmp = cmp; + } + public int compareTo(K k2) { + return cmp.compare(actualKey, k2); + } + } + + /** + * If using comparator, return a ComparableUsingComparator, else + * cast key as Comparable, which may cause ClassCastException, + * which is propagated back to caller. + */ + private Comparable<? super K> comparable(Object key) throws ClassCastException { + if (key == null) + throw new NullPointerException(); + if (comparator != null) + return new ComparableUsingComparator<K>((K)key, comparator); + else + return (Comparable<? super K>)key; + } + + /** + * Compares using comparator or natural ordering. Used when the + * ComparableUsingComparator approach doesn't apply. + */ + int compare(K k1, K k2) throws ClassCastException { + Comparator<? super K> cmp = comparator; + if (cmp != null) + return cmp.compare(k1, k2); + else + return ((Comparable<? super K>)k1).compareTo(k2); + } + + /** + * Returns true if given key greater than or equal to least and + * strictly less than fence, bypassing either test if least or + * fence are null. Needed mainly in submap operations. + */ + boolean inHalfOpenRange(K key, K least, K fence) { + if (key == null) + throw new NullPointerException(); + return ((least == null || compare(key, least) >= 0) && + (fence == null || compare(key, fence) < 0)); + } + + /** + * Returns true if given key greater than or equal to least and less + * or equal to fence. Needed mainly in submap operations. + */ + boolean inOpenRange(K key, K least, K fence) { + if (key == null) + throw new NullPointerException(); + return ((least == null || compare(key, least) >= 0) && + (fence == null || compare(key, fence) <= 0)); + } + + /* ---------------- Traversal -------------- */ + + /** + * Returns a base-level node with key strictly less than given key, + * or the base-level header if there is no such node. Also + * unlinks indexes to deleted nodes found along the way. Callers + * rely on this side-effect of clearing indices to deleted nodes. + * @param key the key + * @return a predecessor of key + */ + private Node<K,V> findPredecessor(Comparable<? super K> key) { + if (key == null) + throw new NullPointerException(); // don't postpone errors + for (;;) { + Index<K,V> q = head; + Index<K,V> r = q.right; + for (;;) { + if (r != null) { + Node<K,V> n = r.node; + K k = n.key; + if (n.value == null) { + if (!q.unlink(r)) + break; // restart + r = q.right; // reread r + continue; + } + if (key.compareTo(k) > 0) { + q = r; + r = r.right; + continue; + } + } + Index<K,V> d = q.down; + if (d != null) { + q = d; + r = d.right; + } else + return q.node; + } + } + } + + /** + * Returns node holding key or null if no such, clearing out any + * deleted nodes seen along the way. Repeatedly traverses at + * base-level looking for key starting at predecessor returned + * from findPredecessor, processing base-level deletions as + * encountered. Some callers rely on this side-effect of clearing + * deleted nodes. + * + * Restarts occur, at traversal step centered on node n, if: + * + * (1) After reading n's next field, n is no longer assumed + * predecessor b's current successor, which means that + * we don't have a consistent 3-node snapshot and so cannot + * unlink any subsequent deleted nodes encountered. + * + * (2) n's value field is null, indicating n is deleted, in + * which case we help out an ongoing structural deletion + * before retrying. Even though there are cases where such + * unlinking doesn't require restart, they aren't sorted out + * 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, + * 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 + * on another call to findPredecessor to notice and return + * some earlier predecessor, which it will do. This check is + * only strictly needed at beginning of loop, (and the + * b.value check isn't strictly needed at all) but is done + * each iteration to help avoid contention with other + * threads by callers that will fail to be able to change + * links, and so will retry anyway. + * + * The traversal loops in doPut, doRemove, and findNear all + * include the same three kinds of checks. And specialized + * versions appear in findFirst, and findLast and their + * variants. 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 + */ + private Node<K,V> findNode(Comparable<? super K> key) { + for (;;) { + Node<K,V> b = findPredecessor(key); + Node<K,V> n = b.next; + for (;;) { + if (n == null) + return null; + Node<K,V> f = n.next; + if (n != b.next) // inconsistent read + break; + Object v = n.value; + if (v == null) { // n is deleted + n.helpDelete(b, f); + break; + } + if (v == n || b.value == null) // b is deleted + break; + int c = key.compareTo(n.key); + if (c == 0) + return n; + if (c < 0) + return null; + b = n; + n = f; + } + } + } + + /** + * 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 + * only if it would otherwise return value from an ongoing + * deletion. Also uses "bound" to eliminate need for some + * comparisons (see Pugh Cookbook). Also folds uses of null checks + * and node-skipping because markers have null keys. + * @param okey the key + * @return the value, or null if absent + */ + private V doGet(Object okey) { + Comparable<? super K> key = comparable(okey); + Node<K,V> bound = null; + Index<K,V> q = head; + Index<K,V> r = q.right; + Node<K,V> n; + K k; + int c; + for (;;) { + Index<K,V> d; + // Traverse rights + if (r != null && (n = r.node) != bound && (k = n.key) != null) { + if ((c = key.compareTo(k)) > 0) { + q = r; + r = r.right; + continue; + } else if (c == 0) { + Object v = n.value; + return (v != null)? (V)v : getUsingFindNode(key); + } else + bound = n; + } + + // Traverse down + if ((d = q.down) != null) { + q = d; + r = d.right; + } else + break; + } + + // Traverse nexts + for (n = q.node.next; n != null; n = n.next) { + if ((k = n.key) != null) { + if ((c = key.compareTo(k)) == 0) { + Object v = n.value; + return (v != null)? (V)v : getUsingFindNode(key); + } else if (c < 0) + break; + } + } + return null; + } + + /** + * Performs map.get via findNode. Used as a backup if doGet + * encounters an in-progress deletion. + * @param key the key + * @return the value, or null if absent + */ + private V getUsingFindNode(Comparable<? super K> key) { + /* + * 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<K,V> n = findNode(key); + if (n == null) + return null; + Object v = n.value; + if (v != null) + return (V)v; + } + } + + /* ---------------- Insertion -------------- */ + + /** + * Main insertion method. Adds element if not present, or + * replaces value if present and onlyIfAbsent is false. + * @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 + */ + private V doPut(K kkey, V value, boolean onlyIfAbsent) { + Comparable<? super K> key = comparable(kkey); + for (;;) { + Node<K,V> b = findPredecessor(key); + Node<K,V> n = b.next; + for (;;) { + if (n != null) { + Node<K,V> f = n.next; + if (n != b.next) // inconsistent read + break; + Object v = n.value; + if (v == null) { // n is deleted + n.helpDelete(b, f); + break; + } + if (v == n || b.value == null) // b is deleted + break; + int c = key.compareTo(n.key); + if (c > 0) { + b = n; + n = f; + continue; + } + if (c == 0) { + if (onlyIfAbsent || n.casValue(v, value)) + return (V)v; + else + break; // restart if lost race to replace value + } + // else c < 0; fall through + } + + Node<K,V> z = new Node<K,V>(kkey, value, n); + if (!b.casNext(n, z)) + break; // restart if lost race to append to b + int level = randomLevel(); + if (level > 0) + insertIndex(z, level); + return null; + } + } + } + + /** + * Returns a random level for inserting a new node. + * Hardwired to k=1, p=0.5, max 31 (see above and + * Pugh's "Skip List Cookbook", sec 3.4). + * + * This uses the simplest of the generators described in George + * Marsaglia's "Xorshift RNGs" paper. This is not a high-quality + * generator but is acceptable here. + */ + private int randomLevel() { + int x = randomSeed; + x ^= x << 13; + x ^= x >>> 17; + randomSeed = x ^= x << 5; + if ((x & 0x8001) != 0) // test highest and lowest bits + return 0; + int level = 1; + while (((x >>>= 1) & 1) != 0) ++level; + return level; + } + + /** + * Creates and adds index nodes for the given node. + * @param z the node + * @param level the level of the index + */ + private void insertIndex(Node<K,V> z, int level) { + HeadIndex<K,V> h = head; + int max = h.level; + + if (level <= max) { + Index<K,V> idx = null; + for (int i = 1; i <= level; ++i) + idx = new Index<K,V>(z, idx, null); + addIndex(idx, h, level); + + } else { // Add a new level + /* + * To reduce interference by other threads checking for + * empty levels in tryReduceLevel, new levels are added + * with initialized right pointers. Which in turn requires + * keeping levels in an array to access them while + * creating new head index nodes from the opposite + * direction. + */ + level = max + 1; + Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1]; + Index<K,V> idx = null; + for (int i = 1; i <= level; ++i) + idxs[i] = idx = new Index<K,V>(z, idx, null); + + HeadIndex<K,V> oldh; + int k; + for (;;) { + oldh = head; + int oldLevel = oldh.level; + if (level <= oldLevel) { // lost race to add level + k = level; + break; + } + HeadIndex<K,V> newh = oldh; + Node<K,V> oldbase = oldh.node; + for (int j = oldLevel+1; j <= level; ++j) + newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j); + if (casHead(oldh, newh)) { + k = oldLevel; + break; + } + } + addIndex(idxs[k], oldh, k); + } + } + + /** + * Adds given index nodes from given level down to 1. + * @param idx the topmost index node being inserted + * @param h the value of head to use to insert. This must be + * snapshotted by callers to provide correct insertion level + * @param indexLevel the level of the index + */ + private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) { + // Track next level to insert in case of retries + int insertionLevel = indexLevel; + Comparable<? super K> key = comparable(idx.node.key); + if (key == null) throw new NullPointerException(); + + // Similar to findPredecessor, but adding index nodes along + // path to key. + for (;;) { + int j = h.level; + Index<K,V> q = h; + Index<K,V> r = q.right; + Index<K,V> t = idx; + for (;;) { + if (r != null) { + Node<K,V> n = r.node; + // compare before deletion check avoids needing recheck + int c = key.compareTo(n.key); + if (n.value == null) { + if (!q.unlink(r)) + break; + r = q.right; + continue; + } + if (c > 0) { + q = r; + r = r.right; + continue; + } + } + + if (j == insertionLevel) { + // Don't insert index if node already deleted + if (t.indexesDeletedNode()) { + findNode(key); // cleans up + return; + } + if (!q.link(r, t)) + break; // restart + if (--insertionLevel == 0) { + // need final deletion check before return + if (t.indexesDeletedNode()) + findNode(key); + return; + } + } + + if (--j >= insertionLevel && j < indexLevel) + t = t.down; + q = q.down; + r = q.right; + } + } + } + + /* ---------------- Deletion -------------- */ + + /** + * Main deletion method. Locates node, nulls value, appends a + * deletion marker, unlinks predecessor, removes associated index + * nodes, and possibly reduces head index level. + * + * Index nodes are cleared out simply by calling findPredecessor. + * which unlinks indexes to deleted nodes found along path to key, + * which will include the indexes to this node. This is done + * unconditionally. We can't check beforehand whether there are + * index nodes because it might be the case that some or all + * indexes hadn't been inserted yet for this node during initial + * search for it, and we'd like to ensure lack of garbage + * retention, so must call to be sure. + * + * @param okey the key + * @param value if non-null, the value that must be + * associated with key + * @return the node, or null if not found + */ + final V doRemove(Object okey, Object value) { + Comparable<? super K> key = comparable(okey); + for (;;) { + Node<K,V> b = findPredecessor(key); + Node<K,V> n = b.next; + for (;;) { + if (n == null) + return null; + Node<K,V> f = n.next; + if (n != b.next) // inconsistent read + break; + Object v = n.value; + if (v == null) { // n is deleted + n.helpDelete(b, f); + break; + } + if (v == n || b.value == null) // b is deleted + break; + int c = key.compareTo(n.key); + if (c < 0) + return null; + if (c > 0) { + b = n; + n = f; + continue; + } + if (value != null && !value.equals(v)) + return null; + if (!n.casValue(v, null)) + break; + if (!n.appendMarker(f) || !b.casNext(n, f)) + findNode(key); // Retry via findNode + else { + findPredecessor(key); // Clean index + if (head.right == null) + tryReduceLevel(); + } + return (V)v; + } + } + } + + /** + * 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 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 + * well because this method will practically never make mistakes + * unless current thread stalls immediately before first CAS, in + * which case it is very unlikely to stall again immediately + * afterwards, so will recover.) + * + * We put up with all this rather than just let levels grow + * because otherwise, even a small map that has undergone a large + * number of insertions and removals will have a lot of levels, + * slowing down access more than would an occasional unwanted + * reduction. + */ + private void tryReduceLevel() { + HeadIndex<K,V> h = head; + HeadIndex<K,V> d; + HeadIndex<K,V> e; + if (h.level > 3 && + (d = (HeadIndex<K,V>)h.down) != null && + (e = (HeadIndex<K,V>)d.down) != null && + e.right == null && + d.right == null && + h.right == null && + casHead(h, d) && // try to set + h.right != null) // recheck + casHead(d, h); // try to backout + } + + /* ---------------- Finding and removing first element -------------- */ + + /** + * Specialized variant of findNode to get first valid node. + * @return first node or null if empty + */ + Node<K,V> findFirst() { + for (;;) { + Node<K,V> b = head.node; + Node<K,V> n = b.next; + if (n == null) + return null; + if (n.value != null) + return n; + n.helpDelete(b, n.next); + } + } + + /** + * Removes first entry; returns its snapshot. + * @return null if empty, else snapshot of first entry + */ + Map.Entry<K,V> doRemoveFirstEntry() { + for (;;) { + Node<K,V> b = head.node; + Node<K,V> n = b.next; + if (n == null) + return null; + Node<K,V> 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 AbstractMap.SimpleImmutableEntry<K,V>(n.key, (V)v); + } + } + + /** + * Clears out index nodes associated with deleted first entry. + */ + private void clearIndexToFirst() { + for (;;) { + Index<K,V> q = head; + for (;;) { + Index<K,V> r = q.right; + if (r != null && r.indexesDeletedNode() && !q.unlink(r)) + break; + if ((q = q.down) == null) { + if (head.right == null) + tryReduceLevel(); + return; + } + } + } + } + + + /* ---------------- Finding and removing last element -------------- */ + + /** + * Specialized version of find to get last valid node. + * @return last node or null if empty + */ + Node<K,V> findLast() { + /* + * findPredecessor can't be used to traverse index level + * because this doesn't use comparisons. So traversals of + * both levels are folded together. + */ + Index<K,V> q = head; + for (;;) { + Index<K,V> d, r; + if ((r = q.right) != null) { + if (r.indexesDeletedNode()) { + q.unlink(r); + q = head; // restart + } + else + q = r; + } else if ((d = q.down) != null) { + q = d; + } else { + Node<K,V> b = q.node; + Node<K,V> n = b.next; + for (;;) { + if (n == null) + return (b.isBaseHeader())? null : b; + Node<K,V> f = n.next; // inconsistent read + if (n != b.next) + break; + Object v = n.value; + if (v == null) { // n is deleted + n.helpDelete(b, f); + break; + } + if (v == n || b.value == null) // b is deleted + break; + b = n; + n = f; + } + q = head; // restart + } + } + } + + /** + * Specialized variant of findPredecessor to get predecessor of last + * valid node. Needed when removing the last entry. It is possible + * that all successors of returned node will have been deleted upon + * return, in which case this method can be retried. + * @return likely predecessor of last node + */ + private Node<K,V> findPredecessorOfLast() { + for (;;) { + Index<K,V> q = head; + for (;;) { + Index<K,V> 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; + } + } + } + + /** + * Removes last entry; returns its snapshot. + * Specialized variant of doRemove. + * @return null if empty, else snapshot of last entry + */ + Map.Entry<K,V> doRemoveLastEntry() { + for (;;) { + Node<K,V> b = findPredecessorOfLast(); + Node<K,V> n = b.next; + if (n == null) { + if (b.isBaseHeader()) // empty + return null; + else + continue; // all b's successors are deleted; retry + } + for (;;) { + Node<K,V> f = n.next; + if (n != b.next) // inconsistent read + break; + Object v = n.value; + if (v == null) { // n is deleted + n.helpDelete(b, f); + break; + } + if (v == n || b.value == null) // b is deleted + break; + if (f != null) { + b = n; + n = f; + continue; + } + if (!n.casValue(v, null)) + break; + K key = n.key; + Comparable<? super K> ck = comparable(key); + if (!n.appendMarker(f) || !b.casNext(n, f)) + findNode(ck); // Retry via findNode + else { + findPredecessor(ck); // Clean index + if (head.right == null) + tryReduceLevel(); + } + return new AbstractMap.SimpleImmutableEntry<K,V>(key, (V)v); + } + } + } + + /* ---------------- Relational operations -------------- */ + + // Control values OR'ed as arguments to findNear + + private static final int EQ = 1; + private static final int LT = 2; + private static final int GT = 0; // Actually checked as !LT + + /** + * Utility for ceiling, floor, lower, higher methods. + * @param kkey the key + * @param rel the relation -- OR'ed combination of EQ, LT, GT + * @return nearest node fitting relation, or null if no such + */ + Node<K,V> findNear(K kkey, int rel) { + Comparable<? super K> key = comparable(kkey); + for (;;) { + Node<K,V> b = findPredecessor(key); + Node<K,V> n = b.next; + for (;;) { + if (n == null) + return ((rel & LT) == 0 || b.isBaseHeader())? null : b; + Node<K,V> f = n.next; + if (n != b.next) // inconsistent read + break; + Object v = n.value; + if (v == null) { // n is deleted + n.helpDelete(b, f); + break; + } + if (v == n || b.value == null) // b is deleted + break; + int c = key.compareTo(n.key); + if ((c == 0 && (rel & EQ) != 0) || + (c < 0 && (rel & LT) == 0)) + return n; + if ( c <= 0 && (rel & LT) != 0) + return (b.isBaseHeader())? null : b; + b = n; + n = f; + } + } + } + + /** + * Returns SimpleImmutableEntry for results of findNear. + * @param key the key + * @param rel the relation -- OR'ed combination of EQ, LT, GT + * @return Entry fitting relation, or null if no such + */ + AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) { + for (;;) { + Node<K,V> n = findNear(key, rel); + if (n == null) + return null; + AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot(); + if (e != null) + return e; + } + } + + + /* ---------------- Constructors -------------- */ + + /** + * Constructs a new, empty map, sorted according to the + * {@linkplain Comparable natural ordering} of the keys. + */ + public ConcurrentSkipListMap() { + this.comparator = null; + initialize(); + } + + /** + * Constructs a new, empty map, sorted according to the specified + * comparator. + * + * @param comparator the comparator that will be used to order this map. + * If <tt>null</tt>, the {@linkplain Comparable natural + * ordering} of the keys will be used. + */ + public ConcurrentSkipListMap(Comparator<? super K> comparator) { + this.comparator = comparator; + initialize(); + } + + /** + * Constructs a new map containing the same mappings as the given map, + * sorted according to the {@linkplain Comparable natural ordering} of + * the keys. + * + * @param m the map whose mappings are to be placed in this map + * @throws ClassCastException if the keys in <tt>m</tt> are not + * {@link Comparable}, or are not mutually comparable + * @throws NullPointerException if the specified map or any of its keys + * or values are null + */ + public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) { + this.comparator = null; + initialize(); + putAll(m); + } + + /** + * Constructs a new map containing the same mappings and using the + * same ordering as the specified sorted map. + * + * @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 or any of + * its keys or values are null + */ + public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) { + this.comparator = m.comparator(); + initialize(); + buildFromSorted(m); + } + + /** + * Returns a shallow copy of this <tt>ConcurrentSkipListMap</tt> + * instance. (The keys and values themselves are not cloned.) + * + * @return a shallow copy of this map + */ + public ConcurrentSkipListMap<K,V> clone() { + ConcurrentSkipListMap<K,V> clone = null; + try { + clone = (ConcurrentSkipListMap<K,V>) super.clone(); + } catch (CloneNotSupportedException e) { + throw new InternalError(); + } + + clone.initialize(); + clone.buildFromSorted(this); + return clone; + } + + /** + * Streamlined bulk insertion to initialize from elements of + * given sorted map. Call only from constructor or clone + * method. + */ + private void buildFromSorted(SortedMap<K, ? extends V> map) { + if (map == null) + throw new NullPointerException(); + + HeadIndex<K,V> h = head; + Node<K,V> basepred = h.node; + + // Track the current rightmost node at each level. Uses an + // ArrayList to avoid committing to initial or maximum level. + ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>(); + + // initialize + for (int i = 0; i <= h.level; ++i) + preds.add(null); + Index<K,V> q = h; + for (int i = h.level; i > 0; --i) { + preds.set(i, q); + q = q.down; + } + + Iterator<? extends Map.Entry<? extends K, ? extends V>> it = + map.entrySet().iterator(); + while (it.hasNext()) { + Map.Entry<? extends K, ? extends V> e = it.next(); + int j = randomLevel(); + if (j > h.level) j = h.level + 1; + K k = e.getKey(); + V v = e.getValue(); + if (k == null || v == null) + throw new NullPointerException(); + Node<K,V> z = new Node<K,V>(k, v, null); + basepred.next = z; + basepred = z; + if (j > 0) { + Index<K,V> idx = null; + for (int i = 1; i <= j; ++i) { + idx = new Index<K,V>(z, idx, null); + if (i > h.level) + h = new HeadIndex<K,V>(h.node, h, idx, i); + + if (i < preds.size()) { + preds.get(i).right = idx; + preds.set(i, idx); + } else + preds.add(idx); + } + } + } + head = h; + } + + /* ---------------- Serialization -------------- */ + + /** + * Save the state of this map to a stream. + * + * @serialData The key (Object) and value (Object) for each + * key-value mapping represented by the map, followed by + * <tt>null</tt>. The key-value mappings are emitted in key-order + * (as determined by the Comparator, or by the keys' natural + * ordering if no Comparator). + */ + private void writeObject(java.io.ObjectOutputStream s) + throws java.io.IOException { + // Write out the Comparator and any hidden stuff + s.defaultWriteObject(); + + // Write out keys and values (alternating) + for (Node<K,V> n = findFirst(); n != null; n = n.next) { + V v = n.getValidValue(); + if (v != null) { + s.writeObject(n.key); + s.writeObject(v); + } + } + s.writeObject(null); + } + + /** + * Reconstitute the map from a stream. + */ + private void readObject(final java.io.ObjectInputStream s) + throws java.io.IOException, ClassNotFoundException { + // Read in the Comparator and any hidden stuff + s.defaultReadObject(); + // 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 + * can be, but doing so requires type cheats and/or creation + * of adaptor classes.) It is simpler to just adapt the code. + */ + + HeadIndex<K,V> h = head; + Node<K,V> basepred = h.node; + ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>(); + for (int i = 0; i <= h.level; ++i) + preds.add(null); + Index<K,V> q = h; + for (int i = h.level; i > 0; --i) { + preds.set(i, q); + q = q.down; + } + + for (;;) { + Object k = s.readObject(); + if (k == null) + break; + Object v = s.readObject(); + if (v == null) + throw new NullPointerException(); + K key = (K) k; + V val = (V) v; + int j = randomLevel(); + if (j > h.level) j = h.level + 1; + Node<K,V> z = new Node<K,V>(key, val, null); + basepred.next = z; + basepred = z; + if (j > 0) { + Index<K,V> idx = null; + for (int i = 1; i <= j; ++i) { + idx = new Index<K,V>(z, idx, null); + if (i > h.level) + h = new HeadIndex<K,V>(h.node, h, idx, i); + + if (i < preds.size()) { + preds.get(i).right = idx; + preds.set(i, idx); + } else + preds.add(idx); + } + } + } + head = h; + } + + /* ------ Map API methods ------ */ + + /** + * Returns <tt>true</tt> if this map contains a mapping for the specified + * key. + * + * @param key key whose presence in this map is to be tested + * @return <tt>true</tt> if this map contains a mapping for the specified key + * @throws ClassCastException if the specified key cannot be compared + * with the keys currently in the map + * @throws NullPointerException if the specified key is null + */ + public boolean containsKey(Object key) { + return doGet(key) != null; + } + + /** + * Returns the value to which the specified key is mapped, + * or {@code null} if this map contains no mapping for the key. + * + * <p>More formally, if this map contains a mapping from a key + * {@code k} to a value {@code v} such that {@code key} compares + * equal to {@code k} according to the map's ordering, then this + * method returns {@code v}; otherwise it returns {@code null}. + * (There can be at most one such mapping.) + * + * @throws ClassCastException if the specified key cannot be compared + * with the keys currently in the map + * @throws NullPointerException if the specified key is null + */ + public V get(Object key) { + return doGet(key); + } + + /** + * Associates the specified value with the specified key in this map. + * If the map previously contained a mapping for the 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 the previous value associated with the specified key, or + * <tt>null</tt> if there was no mapping for the key + * @throws ClassCastException if the specified key cannot be compared + * with the keys currently in the map + * @throws NullPointerException if the specified key or value is null + */ + public V put(K key, V value) { + if (value == null) + throw new NullPointerException(); + return doPut(key, value, false); + } + + /** + * Removes the mapping for the specified key from this map if present. + * + * @param key key for which mapping should be removed + * @return the previous value associated with the specified key, or + * <tt>null</tt> if there was no mapping for the key + * @throws ClassCastException if the specified key cannot be compared + * with the keys currently in the map + * @throws NullPointerException if the specified key is null + */ + public V remove(Object key) { + return doRemove(key, null); + } + + /** + * Returns <tt>true</tt> 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 <tt>true</tt> if a mapping to <tt>value</tt> exists; + * <tt>false</tt> otherwise + * @throws NullPointerException if the specified value is null + */ + public boolean containsValue(Object value) { + if (value == null) + throw new NullPointerException(); + for (Node<K,V> n = findFirst(); n != null; n = n.next) { + V v = n.getValidValue(); + if (v != null && value.equals(v)) + return true; + } + return false; + } + + /** + * Returns the number of key-value mappings in this map. If this map + * contains more than <tt>Integer.MAX_VALUE</tt> elements, it + * returns <tt>Integer.MAX_VALUE</tt>. + * + * <p>Beware that, unlike in most collections, this method is + * <em>NOT</em> 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 (Node<K,V> n = findFirst(); n != null; n = n.next) { + if (n.getValidValue() != null) + ++count; + } + return (count >= Integer.MAX_VALUE)? Integer.MAX_VALUE : (int)count; + } + + /** + * Returns <tt>true</tt> if this map contains no key-value mappings. + * @return <tt>true</tt> if this map contains no key-value mappings + */ + public boolean isEmpty() { + return findFirst() == null; + } + + /** + * Removes all of the mappings from this map. + */ + public void clear() { + initialize(); + } + + /* ---------------- View methods -------------- */ + + /* + * Note: Lazy initialization works for 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. + */ + + /** + * Returns a {@link NavigableSet} view of the keys contained in this map. + * The set's iterator returns the keys in ascending 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 the map, + * via the {@code Iterator.remove}, {@code Set.remove}, + * {@code removeAll}, {@code retainAll}, and {@code clear} + * operations. It does not support the {@code add} or {@code addAll} + * operations. + * + * <p>The view's {@code iterator} is a "weakly consistent" iterator + * that will never throw {@link 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. + * + * <p>This method is equivalent to method {@code navigableKeySet}. + * + * @return a navigable set view of the keys in this map + */ + public NavigableSet<K> keySet() { + KeySet ks = keySet; + return (ks != null) ? ks : (keySet = new KeySet(this)); + } + + public NavigableSet<K> navigableKeySet() { + KeySet ks = keySet; + return (ks != null) ? ks : (keySet = new KeySet(this)); + } + + /** + * Returns a {@link Collection} view of the values contained in this map. + * The collection's iterator returns the values in ascending order + * of the corresponding keys. + * 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 <tt>Iterator.remove</tt>, + * <tt>Collection.remove</tt>, <tt>removeAll</tt>, + * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not + * support the <tt>add</tt> or <tt>addAll</tt> operations. + * + * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator + * that will never throw {@link 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. + */ + public Collection<V> values() { + Values vs = values; + return (vs != null) ? vs : (values = new Values(this)); + } + + /** + * Returns a {@link Set} view of the mappings contained in this map. + * The set's iterator returns the entries in ascending key 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 the map, + * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, + * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt> + * operations. It does not support the <tt>add</tt> or + * <tt>addAll</tt> operations. + * + * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator + * that will never throw {@link 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. + * + * <p>The <tt>Map.Entry</tt> elements returned by + * <tt>iterator.next()</tt> do <em>not</em> support the + * <tt>setValue</tt> operation. + * + * @return a set view of the mappings contained in this map, + * sorted in ascending key order + */ + public Set<Map.Entry<K,V>> entrySet() { + EntrySet es = entrySet; + return (es != null) ? es : (entrySet = new EntrySet(this)); + } + + public ConcurrentNavigableMap<K,V> descendingMap() { + ConcurrentNavigableMap<K,V> dm = descendingMap; + return (dm != null) ? dm : (descendingMap = new SubMap<K,V> + (this, null, false, null, false, true)); + } + + public NavigableSet<K> descendingKeySet() { + return descendingMap().navigableKeySet(); + } + + /* ---------------- AbstractMap Overrides -------------- */ + + /** + * Compares the specified object with this map for equality. + * Returns <tt>true</tt> if the given object is also a map and the + * two maps represent the same mappings. More formally, two maps + * <tt>m1</tt> and <tt>m2</tt> represent the same mappings if + * <tt>m1.entrySet().equals(m2.entrySet())</tt>. 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 <tt>true</tt> 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<?,?> m = (Map<?,?>) o; + try { + for (Map.Entry<K,V> e : this.entrySet()) + if (! e.getValue().equals(m.get(e.getKey()))) + return false; + for (Map.Entry<?,?> e : m.entrySet()) { + Object k = e.getKey(); + Object v = e.getValue(); + if (k == null || v == null || !v.equals(get(k))) + return false; + } + return true; + } catch (ClassCastException unused) { + return false; + } catch (NullPointerException unused) { + return false; + } + } + + /* ------ ConcurrentMap API methods ------ */ + + /** + * {@inheritDoc} + * + * @return the previous value associated with the specified key, + * or <tt>null</tt> if there was no mapping for the key + * @throws ClassCastException if the specified key cannot be compared + * with the keys currently in the map + * @throws NullPointerException if the specified key or value is null + */ + public V putIfAbsent(K key, V value) { + if (value == null) + throw new NullPointerException(); + return doPut(key, value, true); + } + + /** + * {@inheritDoc} + * + * @throws ClassCastException if the specified key cannot be compared + * with the keys currently in the map + * @throws NullPointerException if the specified key is null + */ + public boolean remove(Object key, Object value) { + if (key == null) + throw new NullPointerException(); + if (value == null) + return false; + return doRemove(key, value) != null; + } + + /** + * {@inheritDoc} + * + * @throws ClassCastException if the specified key cannot be compared + * with the keys currently in the map + * @throws NullPointerException if any of the arguments are null + */ + public boolean replace(K key, V oldValue, V newValue) { + if (oldValue == null || newValue == null) + throw new NullPointerException(); + Comparable<? super K> k = comparable(key); + for (;;) { + Node<K,V> n = findNode(k); + if (n == null) + return false; + Object v = n.value; + if (v != null) { + if (!oldValue.equals(v)) + return false; + if (n.casValue(v, newValue)) + return true; + } + } + } + + /** + * {@inheritDoc} + * + * @return the previous value associated with the specified key, + * or <tt>null</tt> if there was no mapping for the key + * @throws ClassCastException if the specified key cannot be compared + * with the keys currently in the map + * @throws NullPointerException if the specified key or value is null + */ + public V replace(K key, V value) { + if (value == null) + throw new NullPointerException(); + Comparable<? super K> k = comparable(key); + for (;;) { + Node<K,V> n = findNode(k); + if (n == null) + return null; + Object v = n.value; + if (v != null && n.casValue(v, value)) + return (V)v; + } + } + + /* ------ SortedMap API methods ------ */ + + public Comparator<? super K> comparator() { + return comparator; + } + + /** + * @throws NoSuchElementException {@inheritDoc} + */ + public K firstKey() { + Node<K,V> n = findFirst(); + if (n == null) + throw new NoSuchElementException(); + return n.key; + } + + /** + * @throws NoSuchElementException {@inheritDoc} + */ + public K lastKey() { + Node<K,V> n = findLast(); + if (n == null) + throw new NoSuchElementException(); + return n.key; + } + + /** + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if {@code fromKey} or {@code toKey} is null + * @throws IllegalArgumentException {@inheritDoc} + */ + public ConcurrentNavigableMap<K,V> subMap(K fromKey, + boolean fromInclusive, + K toKey, + boolean toInclusive) { + if (fromKey == null || toKey == null) + throw new NullPointerException(); + return new SubMap<K,V> + (this, fromKey, fromInclusive, toKey, toInclusive, false); + } + + /** + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if {@code toKey} is null + * @throws IllegalArgumentException {@inheritDoc} + */ + public ConcurrentNavigableMap<K,V> headMap(K toKey, + boolean inclusive) { + if (toKey == null) + throw new NullPointerException(); + return new SubMap<K,V> + (this, null, false, toKey, inclusive, false); + } + + /** + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if {@code fromKey} is null + * @throws IllegalArgumentException {@inheritDoc} + */ + public ConcurrentNavigableMap<K,V> tailMap(K fromKey, + boolean inclusive) { + if (fromKey == null) + throw new NullPointerException(); + return new SubMap<K,V> + (this, fromKey, inclusive, null, false, false); + } + + /** + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if {@code fromKey} or {@code toKey} is null + * @throws IllegalArgumentException {@inheritDoc} + */ + public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) { + return subMap(fromKey, true, toKey, false); + } + + /** + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if {@code toKey} is null + * @throws IllegalArgumentException {@inheritDoc} + */ + public ConcurrentNavigableMap<K,V> headMap(K toKey) { + return headMap(toKey, false); + } + + /** + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if {@code fromKey} is null + * @throws IllegalArgumentException {@inheritDoc} + */ + public ConcurrentNavigableMap<K,V> tailMap(K fromKey) { + return tailMap(fromKey, true); + } + + /* ---------------- Relational operations -------------- */ + + /** + * Returns a key-value mapping associated with the greatest key + * strictly less than the given key, or <tt>null</tt> if there is + * no such key. The returned entry does <em>not</em> support the + * <tt>Entry.setValue</tt> method. + * + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if the specified key is null + */ + public Map.Entry<K,V> lowerEntry(K key) { + return getNear(key, LT); + } + + /** + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if the specified key is null + */ + public K lowerKey(K key) { + Node<K,V> 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 <tt>null</tt> if there + * is no such key. The returned entry does <em>not</em> support + * the <tt>Entry.setValue</tt> method. + * + * @param key the key + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if the specified key is null + */ + public Map.Entry<K,V> floorEntry(K key) { + return getNear(key, LT|EQ); + } + + /** + * @param key the key + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if the specified key is null + */ + public K floorKey(K key) { + Node<K,V> n = findNear(key, LT|EQ); + return (n == null)? null : n.key; + } + + /** + * Returns a key-value mapping associated with the least key + * greater than or equal to the given key, or <tt>null</tt> if + * there is no such entry. The returned entry does <em>not</em> + * support the <tt>Entry.setValue</tt> method. + * + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if the specified key is null + */ + public Map.Entry<K,V> ceilingEntry(K key) { + return getNear(key, GT|EQ); + } + + /** + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if the specified key is null + */ + public K ceilingKey(K key) { + Node<K,V> n = findNear(key, GT|EQ); + return (n == null)? null : n.key; + } + + /** + * Returns a key-value mapping associated with the least key + * strictly greater than the given key, or <tt>null</tt> if there + * is no such key. The returned entry does <em>not</em> support + * the <tt>Entry.setValue</tt> method. + * + * @param key the key + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if the specified key is null + */ + public Map.Entry<K,V> higherEntry(K key) { + return getNear(key, GT); + } + + /** + * @param key the key + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if the specified key is null + */ + public K higherKey(K key) { + Node<K,V> n = findNear(key, GT); + return (n == null)? null : n.key; + } + + /** + * Returns a key-value mapping associated with the least + * key in this map, or <tt>null</tt> if the map is empty. + * The returned entry does <em>not</em> support + * the <tt>Entry.setValue</tt> method. + */ + public Map.Entry<K,V> firstEntry() { + for (;;) { + Node<K,V> n = findFirst(); + if (n == null) + return null; + AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot(); + if (e != null) + return e; + } + } + + /** + * Returns a key-value mapping associated with the greatest + * key in this map, or <tt>null</tt> if the map is empty. + * The returned entry does <em>not</em> support + * the <tt>Entry.setValue</tt> method. + */ + public Map.Entry<K,V> lastEntry() { + for (;;) { + Node<K,V> n = findLast(); + if (n == null) + return null; + AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot(); + if (e != null) + return e; + } + } + + /** + * Removes and returns a key-value mapping associated with + * the least key in this map, or <tt>null</tt> if the map is empty. + * The returned entry does <em>not</em> support + * the <tt>Entry.setValue</tt> method. + */ + public Map.Entry<K,V> pollFirstEntry() { + return doRemoveFirstEntry(); + } + + /** + * Removes and returns a key-value mapping associated with + * the greatest key in this map, or <tt>null</tt> if the map is empty. + * The returned entry does <em>not</em> support + * the <tt>Entry.setValue</tt> method. + */ + public Map.Entry<K,V> pollLastEntry() { + return doRemoveLastEntry(); + } + + + /* ---------------- Iterators -------------- */ + + /** + * Base of iterator classes: + */ + abstract class Iter<T> implements Iterator<T> { + /** the last node returned by next() */ + Node<K,V> lastReturned; + /** the next node to return from next(); */ + Node<K,V> next; + /** Cache of next value field to maintain weak consistency */ + V nextValue; + + /** Initializes ascending iterator for entire range. */ + Iter() { + for (;;) { + next = findFirst(); + if (next == null) + break; + Object x = next.value; + if (x != null && x != next) { + nextValue = (V) x; + break; + } + } + } + + public final boolean hasNext() { + return next != null; + } + + /** Advances next to higher entry. */ + final void advance() { + if ((lastReturned = next) == null) + throw new NoSuchElementException(); + for (;;) { + next = next.next; + if (next == null) + break; + Object x = next.value; + if (x != null && x != next) { + nextValue = (V) x; + break; + } + } + } + + public void remove() { + Node<K,V> l = lastReturned; + if (l == null) + throw new IllegalStateException(); + // It would not be worth all of the overhead to directly + // unlink from here. Using remove is fast enough. + ConcurrentSkipListMap.this.remove(l.key); + lastReturned = null; + } + + } + + final class ValueIterator extends Iter<V> { + public V next() { + V v = nextValue; + advance(); + return v; + } + } + + final class KeyIterator extends Iter<K> { + public K next() { + Node<K,V> n = next; + advance(); + return n.key; + } + } + + final class EntryIterator extends Iter<Map.Entry<K,V>> { + public Map.Entry<K,V> next() { + Node<K,V> n = next; + V v = nextValue; + advance(); + return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v); + } + } + + // Factory methods for iterators needed by ConcurrentSkipListSet etc + + Iterator<K> keyIterator() { + return new KeyIterator(); + } + + Iterator<V> valueIterator() { + return new ValueIterator(); + } + + Iterator<Map.Entry<K,V>> entryIterator() { + return new EntryIterator(); + } + + /* ---------------- View Classes -------------- */ + + /* + * View classes are static, delegating to a ConcurrentNavigableMap + * to allow use by SubMaps, which outweighs the ugliness of + * needing type-tests for Iterator methods. + */ + + static final <E> List<E> toList(Collection<E> c) { + // Using size() here would be a pessimization. + List<E> list = new ArrayList<E>(); + for (E e : c) + list.add(e); + return list; + } + + static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> { + private final ConcurrentNavigableMap<E,Object> m; + KeySet(ConcurrentNavigableMap<E,Object> map) { m = map; } + public int size() { return m.size(); } + public boolean isEmpty() { return m.isEmpty(); } + public boolean contains(Object o) { return m.containsKey(o); } + public boolean remove(Object o) { return m.remove(o) != null; } + public void clear() { m.clear(); } + public E lower(E e) { return m.lowerKey(e); } + public E floor(E e) { return m.floorKey(e); } + public E ceiling(E e) { return m.ceilingKey(e); } + public E higher(E e) { return m.higherKey(e); } + public Comparator<? super E> comparator() { return m.comparator(); } + public E first() { return m.firstKey(); } + public E last() { return m.lastKey(); } + public E pollFirst() { + Map.Entry<E,Object> e = m.pollFirstEntry(); + return e == null? null : e.getKey(); + } + public E pollLast() { + Map.Entry<E,Object> e = m.pollLastEntry(); + return e == null? null : e.getKey(); + } + public Iterator<E> iterator() { + if (m instanceof ConcurrentSkipListMap) + return ((ConcurrentSkipListMap<E,Object>)m).keyIterator(); + else + return ((ConcurrentSkipListMap.SubMap<E,Object>)m).keyIterator(); + } + public boolean equals(Object o) { + if (o == this) + return true; + if (!(o instanceof Set)) + return false; + Collection<?> c = (Collection<?>) o; + try { + return containsAll(c) && c.containsAll(this); + } catch (ClassCastException unused) { + return false; + } catch (NullPointerException unused) { + return false; + } + } + public Object[] toArray() { return toList(this).toArray(); } + public <T> T[] toArray(T[] a) { return toList(this).toArray(a); } + public Iterator<E> descendingIterator() { + return descendingSet().iterator(); + } + public NavigableSet<E> subSet(E fromElement, + boolean fromInclusive, + E toElement, + boolean toInclusive) { + return new ConcurrentSkipListSet<E> + (m.subMap(fromElement, fromInclusive, + toElement, toInclusive)); + } + public NavigableSet<E> headSet(E toElement, boolean inclusive) { + return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive)); + } + public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { + return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive)); + } + public NavigableSet<E> subSet(E fromElement, E toElement) { + return subSet(fromElement, true, toElement, false); + } + public NavigableSet<E> headSet(E toElement) { + return headSet(toElement, false); + } + public NavigableSet<E> tailSet(E fromElement) { + return tailSet(fromElement, true); + } + public NavigableSet<E> descendingSet() { + return new ConcurrentSkipListSet(m.descendingMap()); + } + } + + static final class Values<E> extends AbstractCollection<E> { + private final ConcurrentNavigableMap<Object, E> m; + Values(ConcurrentNavigableMap<Object, E> map) { + m = map; + } + public Iterator<E> iterator() { + if (m instanceof ConcurrentSkipListMap) + return ((ConcurrentSkipListMap<Object,E>)m).valueIterator(); + else + return ((SubMap<Object,E>)m).valueIterator(); + } + public boolean isEmpty() { + return m.isEmpty(); + } + public int size() { + return m.size(); + } + public boolean contains(Object o) { + return m.containsValue(o); + } + public void clear() { + m.clear(); + } + public Object[] toArray() { return toList(this).toArray(); } + public <T> T[] toArray(T[] a) { return toList(this).toArray(a); } + } + + static final class EntrySet<K1,V1> extends AbstractSet<Map.Entry<K1,V1>> { + private final ConcurrentNavigableMap<K1, V1> m; + EntrySet(ConcurrentNavigableMap<K1, V1> map) { + m = map; + } + + public Iterator<Map.Entry<K1,V1>> iterator() { + if (m instanceof ConcurrentSkipListMap) + return ((ConcurrentSkipListMap<K1,V1>)m).entryIterator(); + else + return ((SubMap<K1,V1>)m).entryIterator(); + } + + public boolean contains(Object o) { + if (!(o instanceof Map.Entry)) + return false; + Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o; + V1 v = m.get(e.getKey()); + return v != null && v.equals(e.getValue()); + } + public boolean remove(Object o) { + if (!(o instanceof Map.Entry)) + return false; + Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o; + return m.remove(e.getKey(), + e.getValue()); + } + public boolean isEmpty() { + return m.isEmpty(); + } + public int size() { + return m.size(); + } + public void clear() { + m.clear(); + } + public boolean equals(Object o) { + if (o == this) + return true; + if (!(o instanceof Set)) + return false; + Collection<?> c = (Collection<?>) o; + try { + return containsAll(c) && c.containsAll(this); + } catch (ClassCastException unused) { + return false; + } catch (NullPointerException unused) { + return false; + } + } + public Object[] toArray() { return toList(this).toArray(); } + public <T> T[] toArray(T[] a) { return toList(this).toArray(a); } + } + + /** + * Submaps returned by {@link ConcurrentSkipListMap} submap operations + * represent a subrange of mappings of their underlying + * maps. Instances of this class support all methods of their + * underlying maps, differing in that mappings outside their range are + * ignored, and attempts to add mappings outside their ranges result + * in {@link IllegalArgumentException}. Instances of this class are + * constructed only using the <tt>subMap</tt>, <tt>headMap</tt>, and + * <tt>tailMap</tt> methods of their underlying maps. + * + * @serial include + */ + static final class SubMap<K,V> extends AbstractMap<K,V> + implements ConcurrentNavigableMap<K,V>, Cloneable, + java.io.Serializable { + private static final long serialVersionUID = -7647078645895051609L; + + /** Underlying map */ + private final ConcurrentSkipListMap<K,V> m; + /** lower bound key, or null if from start */ + private final K lo; + /** upper bound key, or null if to end */ + private final K hi; + /** inclusion flag for lo */ + private final boolean loInclusive; + /** inclusion flag for hi */ + private final boolean hiInclusive; + /** direction */ + private final boolean isDescending; + + // Lazily initialized view holders + private transient KeySet<K> keySetView; + private transient Set<Map.Entry<K,V>> entrySetView; + private transient Collection<V> valuesView; + + /** + * Creates a new submap, initializing all fields + */ + SubMap(ConcurrentSkipListMap<K,V> map, + K fromKey, boolean fromInclusive, + K toKey, boolean toInclusive, + boolean isDescending) { + if (fromKey != null && toKey != null && + map.compare(fromKey, toKey) > 0) + throw new IllegalArgumentException("inconsistent range"); + this.m = map; + this.lo = fromKey; + this.hi = toKey; + this.loInclusive = fromInclusive; + this.hiInclusive = toInclusive; + this.isDescending = isDescending; + } + + /* ---------------- Utilities -------------- */ + + private boolean tooLow(K key) { + if (lo != null) { + int c = m.compare(key, lo); + if (c < 0 || (c == 0 && !loInclusive)) + return true; + } + return false; + } + + private boolean tooHigh(K key) { + if (hi != null) { + int c = m.compare(key, hi); + if (c > 0 || (c == 0 && !hiInclusive)) + return true; + } + return false; + } + + private boolean inBounds(K key) { + return !tooLow(key) && !tooHigh(key); + } + + private void checkKeyBounds(K key) throws IllegalArgumentException { + if (key == null) + throw new NullPointerException(); + if (!inBounds(key)) + throw new IllegalArgumentException("key out of range"); + } + + /** + * Returns true if node key is less than upper bound of range + */ + private boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) { + if (n == null) + return false; + if (hi == null) + return true; + K k = n.key; + if (k == null) // pass by markers and headers + return true; + int c = m.compare(k, hi); + if (c > 0 || (c == 0 && !hiInclusive)) + return false; + return true; + } + + /** + * Returns lowest node. This node might not be in range, so + * most usages need to check bounds + */ + private ConcurrentSkipListMap.Node<K,V> loNode() { + if (lo == null) + return m.findFirst(); + else if (loInclusive) + return m.findNear(lo, m.GT|m.EQ); + else + return m.findNear(lo, m.GT); + } + + /** + * Returns highest node. This node might not be in range, so + * most usages need to check bounds + */ + private ConcurrentSkipListMap.Node<K,V> hiNode() { + if (hi == null) + return m.findLast(); + else if (hiInclusive) + return m.findNear(hi, m.LT|m.EQ); + else + return m.findNear(hi, m.LT); + } + + /** + * Returns lowest absolute key (ignoring directonality) + */ + private K lowestKey() { + ConcurrentSkipListMap.Node<K,V> n = loNode(); + if (isBeforeEnd(n)) + return n.key; + else + throw new NoSuchElementException(); + } + + /** + * Returns highest absolute key (ignoring directonality) + */ + private K highestKey() { + ConcurrentSkipListMap.Node<K,V> n = hiNode(); + if (n != null) { + K last = n.key; + if (inBounds(last)) + return last; + } + throw new NoSuchElementException(); + } + + private Map.Entry<K,V> lowestEntry() { + for (;;) { + ConcurrentSkipListMap.Node<K,V> n = loNode(); + if (!isBeforeEnd(n)) + return null; + Map.Entry<K,V> e = n.createSnapshot(); + if (e != null) + return e; + } + } + + private Map.Entry<K,V> highestEntry() { + for (;;) { + ConcurrentSkipListMap.Node<K,V> n = hiNode(); + if (n == null || !inBounds(n.key)) + return null; + Map.Entry<K,V> e = n.createSnapshot(); + if (e != null) + return e; + } + } + + private Map.Entry<K,V> removeLowest() { + for (;;) { + Node<K,V> n = loNode(); + if (n == null) + return null; + K k = n.key; + if (!inBounds(k)) + return null; + V v = m.doRemove(k, null); + if (v != null) + return new AbstractMap.SimpleImmutableEntry<K,V>(k, v); + } + } + + private Map.Entry<K,V> removeHighest() { + for (;;) { + Node<K,V> n = hiNode(); + if (n == null) + return null; + K k = n.key; + if (!inBounds(k)) + return null; + V v = m.doRemove(k, null); + if (v != null) + return new AbstractMap.SimpleImmutableEntry<K,V>(k, v); + } + } + + /** + * Submap version of ConcurrentSkipListMap.getNearEntry + */ + private Map.Entry<K,V> getNearEntry(K key, int rel) { + if (isDescending) { // adjust relation for direction + if ((rel & m.LT) == 0) + rel |= m.LT; + else + rel &= ~m.LT; + } + if (tooLow(key)) + return ((rel & m.LT) != 0)? null : lowestEntry(); + if (tooHigh(key)) + return ((rel & m.LT) != 0)? highestEntry() : null; + for (;;) { + Node<K,V> n = m.findNear(key, rel); + if (n == null || !inBounds(n.key)) + return null; + K k = n.key; + V v = n.getValidValue(); + if (v != null) + return new AbstractMap.SimpleImmutableEntry<K,V>(k, v); + } + } + + // Almost the same as getNearEntry, except for keys + private K getNearKey(K key, int rel) { + if (isDescending) { // adjust relation for direction + if ((rel & m.LT) == 0) + rel |= m.LT; + else + rel &= ~m.LT; + } + if (tooLow(key)) { + if ((rel & m.LT) == 0) { + ConcurrentSkipListMap.Node<K,V> n = loNode(); + if (isBeforeEnd(n)) + return n.key; + } + return null; + } + if (tooHigh(key)) { + if ((rel & m.LT) != 0) { + ConcurrentSkipListMap.Node<K,V> n = hiNode(); + if (n != null) { + K last = n.key; + if (inBounds(last)) + return last; + } + } + return null; + } + for (;;) { + Node<K,V> n = m.findNear(key, rel); + if (n == null || !inBounds(n.key)) + return null; + K k = n.key; + V v = n.getValidValue(); + if (v != null) + return k; + } + } + + /* ---------------- Map API methods -------------- */ + + public boolean containsKey(Object key) { + if (key == null) throw new NullPointerException(); + K k = (K)key; + return inBounds(k) && m.containsKey(k); + } + + public V get(Object key) { + if (key == null) throw new NullPointerException(); + K k = (K)key; + return ((!inBounds(k)) ? null : m.get(k)); + } + + public V put(K key, V value) { + checkKeyBounds(key); + return m.put(key, value); + } + + public V remove(Object key) { + K k = (K)key; + return (!inBounds(k))? null : m.remove(k); + } + + public int size() { + long count = 0; + for (ConcurrentSkipListMap.Node<K,V> n = loNode(); + isBeforeEnd(n); + n = n.next) { + if (n.getValidValue() != null) + ++count; + } + return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count; + } + + public boolean isEmpty() { + return !isBeforeEnd(loNode()); + } + + public boolean containsValue(Object value) { + if (value == null) + throw new NullPointerException(); + for (ConcurrentSkipListMap.Node<K,V> n = loNode(); + isBeforeEnd(n); + n = n.next) { + V v = n.getValidValue(); + if (v != null && value.equals(v)) + return true; + } + return false; + } + + public void clear() { + for (ConcurrentSkipListMap.Node<K,V> n = loNode(); + isBeforeEnd(n); + n = n.next) { + if (n.getValidValue() != null) + m.remove(n.key); + } + } + + /* ---------------- ConcurrentMap API methods -------------- */ + + public V putIfAbsent(K key, V value) { + checkKeyBounds(key); + return m.putIfAbsent(key, value); + } + + public boolean remove(Object key, Object value) { + K k = (K)key; + return inBounds(k) && m.remove(k, value); + } + + public boolean replace(K key, V oldValue, V newValue) { + checkKeyBounds(key); + return m.replace(key, oldValue, newValue); + } + + public V replace(K key, V value) { + checkKeyBounds(key); + return m.replace(key, value); + } + + /* ---------------- SortedMap API methods -------------- */ + + public Comparator<? super K> comparator() { + Comparator<? super K> cmp = m.comparator(); + if (isDescending) + return Collections.reverseOrder(cmp); + else + return cmp; + } + + /** + * Utility to create submaps, where given bounds override + * unbounded(null) ones and/or are checked against bounded ones. + */ + private SubMap<K,V> newSubMap(K fromKey, + boolean fromInclusive, + K toKey, + boolean toInclusive) { + if (isDescending) { // flip senses + K tk = fromKey; + fromKey = toKey; + toKey = tk; + boolean ti = fromInclusive; + fromInclusive = toInclusive; + toInclusive = ti; + } + if (lo != null) { + if (fromKey == null) { + fromKey = lo; + fromInclusive = loInclusive; + } + else { + int c = m.compare(fromKey, lo); + if (c < 0 || (c == 0 && !loInclusive && fromInclusive)) + throw new IllegalArgumentException("key out of range"); + } + } + if (hi != null) { + if (toKey == null) { + toKey = hi; + toInclusive = hiInclusive; + } + else { + int c = m.compare(toKey, hi); + if (c > 0 || (c == 0 && !hiInclusive && toInclusive)) + throw new IllegalArgumentException("key out of range"); + } + } + return new SubMap<K,V>(m, fromKey, fromInclusive, + toKey, toInclusive, isDescending); + } + + public SubMap<K,V> subMap(K fromKey, + boolean fromInclusive, + K toKey, + boolean toInclusive) { + if (fromKey == null || toKey == null) + throw new NullPointerException(); + return newSubMap(fromKey, fromInclusive, toKey, toInclusive); + } + + public SubMap<K,V> headMap(K toKey, + boolean inclusive) { + if (toKey == null) + throw new NullPointerException(); + return newSubMap(null, false, toKey, inclusive); + } + + public SubMap<K,V> tailMap(K fromKey, + boolean inclusive) { + if (fromKey == null) + throw new NullPointerException(); + return newSubMap(fromKey, inclusive, null, false); + } + + public SubMap<K,V> subMap(K fromKey, K toKey) { + return subMap(fromKey, true, toKey, false); + } + + public SubMap<K,V> headMap(K toKey) { + return headMap(toKey, false); + } + + public SubMap<K,V> tailMap(K fromKey) { + return tailMap(fromKey, true); + } + + public SubMap<K,V> descendingMap() { + return new SubMap<K,V>(m, lo, loInclusive, + hi, hiInclusive, !isDescending); + } + + /* ---------------- Relational methods -------------- */ + + public Map.Entry<K,V> ceilingEntry(K key) { + return getNearEntry(key, (m.GT|m.EQ)); + } + + public K ceilingKey(K key) { + return getNearKey(key, (m.GT|m.EQ)); + } + + public Map.Entry<K,V> lowerEntry(K key) { + return getNearEntry(key, (m.LT)); + } + + public K lowerKey(K key) { + return getNearKey(key, (m.LT)); + } + + public Map.Entry<K,V> floorEntry(K key) { + return getNearEntry(key, (m.LT|m.EQ)); + } + + public K floorKey(K key) { + return getNearKey(key, (m.LT|m.EQ)); + } + + public Map.Entry<K,V> higherEntry(K key) { + return getNearEntry(key, (m.GT)); + } + + public K higherKey(K key) { + return getNearKey(key, (m.GT)); + } + + public K firstKey() { + return isDescending? highestKey() : lowestKey(); + } + + public K lastKey() { + return isDescending? lowestKey() : highestKey(); + } + + public Map.Entry<K,V> firstEntry() { + return isDescending? highestEntry() : lowestEntry(); + } + + public Map.Entry<K,V> lastEntry() { + return isDescending? lowestEntry() : highestEntry(); + } + + public Map.Entry<K,V> pollFirstEntry() { + return isDescending? removeHighest() : removeLowest(); + } + + public Map.Entry<K,V> pollLastEntry() { + return isDescending? removeLowest() : removeHighest(); + } + + /* ---------------- Submap Views -------------- */ + + public NavigableSet<K> keySet() { + KeySet<K> ks = keySetView; + return (ks != null) ? ks : (keySetView = new KeySet(this)); + } + + public NavigableSet<K> navigableKeySet() { + KeySet<K> ks = keySetView; + return (ks != null) ? ks : (keySetView = new KeySet(this)); + } + + public Collection<V> values() { + Collection<V> vs = valuesView; + return (vs != null) ? vs : (valuesView = new Values(this)); + } + + public Set<Map.Entry<K,V>> entrySet() { + Set<Map.Entry<K,V>> es = entrySetView; + return (es != null) ? es : (entrySetView = new EntrySet(this)); + } + + public NavigableSet<K> descendingKeySet() { + return descendingMap().navigableKeySet(); + } + + Iterator<K> keyIterator() { + return new SubMapKeyIterator(); + } + + Iterator<V> valueIterator() { + return new SubMapValueIterator(); + } + + Iterator<Map.Entry<K,V>> entryIterator() { + return new SubMapEntryIterator(); + } + + /** + * Variant of main Iter class to traverse through submaps. + */ + abstract class SubMapIter<T> implements Iterator<T> { + /** the last node returned by next() */ + Node<K,V> lastReturned; + /** the next node to return from next(); */ + Node<K,V> next; + /** Cache of next value field to maintain weak consistency */ + V nextValue; + + SubMapIter() { + for (;;) { + next = isDescending ? hiNode() : loNode(); + if (next == null) + break; + Object x = next.value; + if (x != null && x != next) { + if (! inBounds(next.key)) + next = null; + else + nextValue = (V) x; + break; + } + } + } + + public final boolean hasNext() { + return next != null; + } + + final void advance() { + if ((lastReturned = next) == null) + throw new NoSuchElementException(); + if (isDescending) + descend(); + else + ascend(); + } + + private void ascend() { + for (;;) { + next = next.next; + if (next == null) + break; + Object x = next.value; + if (x != null && x != next) { + if (tooHigh(next.key)) + next = null; + else + nextValue = (V) x; + break; + } + } + } + + private void descend() { + for (;;) { + next = m.findNear(lastReturned.key, LT); + if (next == null) + break; + Object x = next.value; + if (x != null && x != next) { + if (tooLow(next.key)) + next = null; + else + nextValue = (V) x; + break; + } + } + } + + public void remove() { + Node<K,V> l = lastReturned; + if (l == null) + throw new IllegalStateException(); + m.remove(l.key); + lastReturned = null; + } + + } + + final class SubMapValueIterator extends SubMapIter<V> { + public V next() { + V v = nextValue; + advance(); + return v; + } + } + + final class SubMapKeyIterator extends SubMapIter<K> { + public K next() { + Node<K,V> n = next; + advance(); + return n.key; + } + } + + final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> { + public Map.Entry<K,V> next() { + Node<K,V> n = next; + V v = nextValue; + advance(); + return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v); + } + } + } +} |