diff options
Diffstat (limited to 'external/jsr166/java/util/concurrent/ConcurrentSkipListMap.java')
| -rw-r--r-- | external/jsr166/java/util/concurrent/ConcurrentSkipListMap.java | 3114 |
1 files changed, 0 insertions, 3114 deletions
diff --git a/external/jsr166/java/util/concurrent/ConcurrentSkipListMap.java b/external/jsr166/java/util/concurrent/ConcurrentSkipListMap.java deleted file mode 100644 index 52cd17a52..000000000 --- a/external/jsr166/java/util/concurrent/ConcurrentSkipListMap.java +++ /dev/null @@ -1,3114 +0,0 @@ -/* - * 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); - } - } - } -} |