jaroslav@1890: /* jaroslav@1890: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. jaroslav@1890: * jaroslav@1890: * This code is free software; you can redistribute it and/or modify it jaroslav@1890: * under the terms of the GNU General Public License version 2 only, as jaroslav@1890: * published by the Free Software Foundation. Oracle designates this jaroslav@1890: * particular file as subject to the "Classpath" exception as provided jaroslav@1890: * by Oracle in the LICENSE file that accompanied this code. jaroslav@1890: * jaroslav@1890: * This code is distributed in the hope that it will be useful, but WITHOUT jaroslav@1890: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or jaroslav@1890: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License jaroslav@1890: * version 2 for more details (a copy is included in the LICENSE file that jaroslav@1890: * accompanied this code). jaroslav@1890: * jaroslav@1890: * You should have received a copy of the GNU General Public License version jaroslav@1890: * 2 along with this work; if not, write to the Free Software Foundation, jaroslav@1890: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. jaroslav@1890: * jaroslav@1890: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA jaroslav@1890: * or visit www.oracle.com if you need additional information or have any jaroslav@1890: * questions. jaroslav@1890: */ jaroslav@1890: jaroslav@1890: /* jaroslav@1890: * This file is available under and governed by the GNU General Public jaroslav@1890: * License version 2 only, as published by the Free Software Foundation. jaroslav@1890: * However, the following notice accompanied the original version of this jaroslav@1890: * file: jaroslav@1890: * jaroslav@1890: * Written by Doug Lea with assistance from members of JCP JSR-166 jaroslav@1890: * Expert Group and released to the public domain, as explained at jaroslav@1890: * http://creativecommons.org/publicdomain/zero/1.0/ jaroslav@1890: */ jaroslav@1890: jaroslav@1890: package java.util.concurrent; jaroslav@1890: import java.util.*; jaroslav@1890: import java.util.concurrent.atomic.*; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * A scalable concurrent {@link ConcurrentNavigableMap} implementation. jaroslav@1890: * The map is sorted according to the {@linkplain Comparable natural jaroslav@1890: * ordering} of its keys, or by a {@link Comparator} provided at map jaroslav@1890: * creation time, depending on which constructor is used. jaroslav@1890: * jaroslav@1890: *

This class implements a concurrent variant of SkipLists jaroslav@1890: * providing expected average log(n) time cost for the jaroslav@1890: * containsKey, get, put and jaroslav@1890: * remove operations and their variants. Insertion, removal, jaroslav@1890: * update, and access operations safely execute concurrently by jaroslav@1890: * multiple threads. Iterators are weakly consistent, returning jaroslav@1890: * elements reflecting the state of the map at some point at or since jaroslav@1890: * the creation of the iterator. They do not throw {@link jaroslav@1890: * ConcurrentModificationException}, and may proceed concurrently with jaroslav@1890: * other operations. Ascending key ordered views and their iterators jaroslav@1890: * are faster than descending ones. jaroslav@1890: * jaroslav@1890: *

All Map.Entry pairs returned by methods in this class jaroslav@1890: * and its views represent snapshots of mappings at the time they were jaroslav@1890: * produced. They do not support the Entry.setValue jaroslav@1890: * method. (Note however that it is possible to change mappings in the jaroslav@1890: * associated map using put, putIfAbsent, or jaroslav@1890: * replace, depending on exactly which effect you need.) jaroslav@1890: * jaroslav@1890: *

Beware that, unlike in most collections, the size jaroslav@1890: * method is not a constant-time operation. Because of the jaroslav@1890: * asynchronous nature of these maps, determining the current number jaroslav@1890: * of elements requires a traversal of the elements, and so may report jaroslav@1890: * inaccurate results if this collection is modified during traversal. jaroslav@1890: * Additionally, the bulk operations putAll, equals, jaroslav@1890: * toArray, containsValue, and clear are jaroslav@1890: * not guaranteed to be performed atomically. For example, an jaroslav@1890: * iterator operating concurrently with a putAll operation jaroslav@1890: * might view only some of the added elements. jaroslav@1890: * jaroslav@1890: *

This class and its views and iterators implement all of the jaroslav@1890: * optional methods of the {@link Map} and {@link Iterator} jaroslav@1890: * interfaces. Like most other concurrent collections, this class does jaroslav@1890: * not permit the use of null keys or values because some jaroslav@1890: * null return values cannot be reliably distinguished from the absence of jaroslav@1890: * elements. jaroslav@1890: * jaroslav@1890: *

This class is a member of the jaroslav@1890: * jaroslav@1890: * Java Collections Framework. jaroslav@1890: * jaroslav@1890: * @author Doug Lea jaroslav@1890: * @param the type of keys maintained by this map jaroslav@1890: * @param the type of mapped values jaroslav@1890: * @since 1.6 jaroslav@1890: */ jaroslav@1890: public class ConcurrentSkipListMap extends AbstractMap jaroslav@1890: implements ConcurrentNavigableMap, jaroslav@1890: Cloneable, jaroslav@1890: java.io.Serializable { jaroslav@1890: /* jaroslav@1890: * This class implements a tree-like two-dimensionally linked skip jaroslav@1890: * list in which the index levels are represented in separate jaroslav@1890: * nodes from the base nodes holding data. There are two reasons jaroslav@1890: * for taking this approach instead of the usual array-based jaroslav@1890: * structure: 1) Array based implementations seem to encounter jaroslav@1890: * more complexity and overhead 2) We can use cheaper algorithms jaroslav@1890: * for the heavily-traversed index lists than can be used for the jaroslav@1890: * base lists. Here's a picture of some of the basics for a jaroslav@1890: * possible list with 2 levels of index: jaroslav@1890: * jaroslav@1890: * Head nodes Index nodes jaroslav@1890: * +-+ right +-+ +-+ jaroslav@1890: * |2|---------------->| |--------------------->| |->null jaroslav@1890: * +-+ +-+ +-+ jaroslav@1890: * | down | | jaroslav@1890: * v v v jaroslav@1890: * +-+ +-+ +-+ +-+ +-+ +-+ jaroslav@1890: * |1|----------->| |->| |------>| |----------->| |------>| |->null jaroslav@1890: * +-+ +-+ +-+ +-+ +-+ +-+ jaroslav@1890: * v | | | | | jaroslav@1890: * Nodes next v v v v v jaroslav@1890: * +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ jaroslav@1890: * | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null jaroslav@1890: * +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ jaroslav@1890: * jaroslav@1890: * The base lists use a variant of the HM linked ordered set jaroslav@1890: * algorithm. See Tim Harris, "A pragmatic implementation of jaroslav@1890: * non-blocking linked lists" jaroslav@1890: * http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged jaroslav@1890: * Michael "High Performance Dynamic Lock-Free Hash Tables and jaroslav@1890: * List-Based Sets" jaroslav@1890: * http://www.research.ibm.com/people/m/michael/pubs.htm. The jaroslav@1890: * basic idea in these lists is to mark the "next" pointers of jaroslav@1890: * deleted nodes when deleting to avoid conflicts with concurrent jaroslav@1890: * insertions, and when traversing to keep track of triples jaroslav@1890: * (predecessor, node, successor) in order to detect when and how jaroslav@1890: * to unlink these deleted nodes. jaroslav@1890: * jaroslav@1890: * Rather than using mark-bits to mark list deletions (which can jaroslav@1890: * be slow and space-intensive using AtomicMarkedReference), nodes jaroslav@1890: * use direct CAS'able next pointers. On deletion, instead of jaroslav@1890: * marking a pointer, they splice in another node that can be jaroslav@1890: * thought of as standing for a marked pointer (indicating this by jaroslav@1890: * using otherwise impossible field values). Using plain nodes jaroslav@1890: * acts roughly like "boxed" implementations of marked pointers, jaroslav@1890: * but uses new nodes only when nodes are deleted, not for every jaroslav@1890: * link. This requires less space and supports faster jaroslav@1890: * traversal. Even if marked references were better supported by jaroslav@1890: * JVMs, traversal using this technique might still be faster jaroslav@1890: * because any search need only read ahead one more node than jaroslav@1890: * otherwise required (to check for trailing marker) rather than jaroslav@1890: * unmasking mark bits or whatever on each read. jaroslav@1890: * jaroslav@1890: * This approach maintains the essential property needed in the HM jaroslav@1890: * algorithm of changing the next-pointer of a deleted node so jaroslav@1890: * that any other CAS of it will fail, but implements the idea by jaroslav@1890: * changing the pointer to point to a different node, not by jaroslav@1890: * marking it. While it would be possible to further squeeze jaroslav@1890: * space by defining marker nodes not to have key/value fields, it jaroslav@1890: * isn't worth the extra type-testing overhead. The deletion jaroslav@1890: * markers are rarely encountered during traversal and are jaroslav@1890: * normally quickly garbage collected. (Note that this technique jaroslav@1890: * would not work well in systems without garbage collection.) jaroslav@1890: * jaroslav@1890: * In addition to using deletion markers, the lists also use jaroslav@1890: * nullness of value fields to indicate deletion, in a style jaroslav@1890: * similar to typical lazy-deletion schemes. If a node's value is jaroslav@1890: * null, then it is considered logically deleted and ignored even jaroslav@1890: * though it is still reachable. This maintains proper control of jaroslav@1890: * concurrent replace vs delete operations -- an attempted replace jaroslav@1890: * must fail if a delete beat it by nulling field, and a delete jaroslav@1890: * must return the last non-null value held in the field. (Note: jaroslav@1890: * Null, rather than some special marker, is used for value fields jaroslav@1890: * here because it just so happens to mesh with the Map API jaroslav@1890: * requirement that method get returns null if there is no jaroslav@1890: * mapping, which allows nodes to remain concurrently readable jaroslav@1890: * even when deleted. Using any other marker value here would be jaroslav@1890: * messy at best.) jaroslav@1890: * jaroslav@1890: * Here's the sequence of events for a deletion of node n with jaroslav@1890: * predecessor b and successor f, initially: jaroslav@1890: * jaroslav@1890: * +------+ +------+ +------+ jaroslav@1890: * ... | b |------>| n |----->| f | ... jaroslav@1890: * +------+ +------+ +------+ jaroslav@1890: * jaroslav@1890: * 1. CAS n's value field from non-null to null. jaroslav@1890: * From this point on, no public operations encountering jaroslav@1890: * the node consider this mapping to exist. However, other jaroslav@1890: * ongoing insertions and deletions might still modify jaroslav@1890: * n's next pointer. jaroslav@1890: * jaroslav@1890: * 2. CAS n's next pointer to point to a new marker node. jaroslav@1890: * From this point on, no other nodes can be appended to n. jaroslav@1890: * which avoids deletion errors in CAS-based linked lists. jaroslav@1890: * jaroslav@1890: * +------+ +------+ +------+ +------+ jaroslav@1890: * ... | b |------>| n |----->|marker|------>| f | ... jaroslav@1890: * +------+ +------+ +------+ +------+ jaroslav@1890: * jaroslav@1890: * 3. CAS b's next pointer over both n and its marker. jaroslav@1890: * From this point on, no new traversals will encounter n, jaroslav@1890: * and it can eventually be GCed. jaroslav@1890: * +------+ +------+ jaroslav@1890: * ... | b |----------------------------------->| f | ... jaroslav@1890: * +------+ +------+ jaroslav@1890: * jaroslav@1890: * A failure at step 1 leads to simple retry due to a lost race jaroslav@1890: * with another operation. Steps 2-3 can fail because some other jaroslav@1890: * thread noticed during a traversal a node with null value and jaroslav@1890: * helped out by marking and/or unlinking. This helping-out jaroslav@1890: * ensures that no thread can become stuck waiting for progress of jaroslav@1890: * the deleting thread. The use of marker nodes slightly jaroslav@1890: * complicates helping-out code because traversals must track jaroslav@1890: * consistent reads of up to four nodes (b, n, marker, f), not jaroslav@1890: * just (b, n, f), although the next field of a marker is jaroslav@1890: * immutable, and once a next field is CAS'ed to point to a jaroslav@1890: * marker, it never again changes, so this requires less care. jaroslav@1890: * jaroslav@1890: * Skip lists add indexing to this scheme, so that the base-level jaroslav@1890: * traversals start close to the locations being found, inserted jaroslav@1890: * or deleted -- usually base level traversals only traverse a few jaroslav@1890: * nodes. This doesn't change the basic algorithm except for the jaroslav@1890: * need to make sure base traversals start at predecessors (here, jaroslav@1890: * b) that are not (structurally) deleted, otherwise retrying jaroslav@1890: * after processing the deletion. jaroslav@1890: * jaroslav@1890: * Index levels are maintained as lists with volatile next fields, jaroslav@1890: * using CAS to link and unlink. Races are allowed in index-list jaroslav@1890: * operations that can (rarely) fail to link in a new index node jaroslav@1890: * or delete one. (We can't do this of course for data nodes.) jaroslav@1890: * However, even when this happens, the index lists remain sorted, jaroslav@1890: * so correctly serve as indices. This can impact performance, jaroslav@1890: * but since skip lists are probabilistic anyway, the net result jaroslav@1890: * is that under contention, the effective "p" value may be lower jaroslav@1890: * than its nominal value. And race windows are kept small enough jaroslav@1890: * that in practice these failures are rare, even under a lot of jaroslav@1890: * contention. jaroslav@1890: * jaroslav@1890: * The fact that retries (for both base and index lists) are jaroslav@1890: * relatively cheap due to indexing allows some minor jaroslav@1890: * simplifications of retry logic. Traversal restarts are jaroslav@1890: * performed after most "helping-out" CASes. This isn't always jaroslav@1890: * strictly necessary, but the implicit backoffs tend to help jaroslav@1890: * reduce other downstream failed CAS's enough to outweigh restart jaroslav@1890: * cost. This worsens the worst case, but seems to improve even jaroslav@1890: * highly contended cases. jaroslav@1890: * jaroslav@1890: * Unlike most skip-list implementations, index insertion and jaroslav@1890: * deletion here require a separate traversal pass occuring after jaroslav@1890: * the base-level action, to add or remove index nodes. This adds jaroslav@1890: * to single-threaded overhead, but improves contended jaroslav@1890: * multithreaded performance by narrowing interference windows, jaroslav@1890: * and allows deletion to ensure that all index nodes will be made jaroslav@1890: * unreachable upon return from a public remove operation, thus jaroslav@1890: * avoiding unwanted garbage retention. This is more important jaroslav@1890: * here than in some other data structures because we cannot null jaroslav@1890: * out node fields referencing user keys since they might still be jaroslav@1890: * read by other ongoing traversals. jaroslav@1890: * jaroslav@1890: * Indexing uses skip list parameters that maintain good search jaroslav@1890: * performance while using sparser-than-usual indices: The jaroslav@1890: * hardwired parameters k=1, p=0.5 (see method randomLevel) mean jaroslav@1890: * that about one-quarter of the nodes have indices. Of those that jaroslav@1890: * do, half have one level, a quarter have two, and so on (see jaroslav@1890: * Pugh's Skip List Cookbook, sec 3.4). The expected total space jaroslav@1890: * requirement for a map is slightly less than for the current jaroslav@1890: * implementation of java.util.TreeMap. jaroslav@1890: * jaroslav@1890: * Changing the level of the index (i.e, the height of the jaroslav@1890: * tree-like structure) also uses CAS. The head index has initial jaroslav@1890: * level/height of one. Creation of an index with height greater jaroslav@1890: * than the current level adds a level to the head index by jaroslav@1890: * CAS'ing on a new top-most head. To maintain good performance jaroslav@1890: * after a lot of removals, deletion methods heuristically try to jaroslav@1890: * reduce the height if the topmost levels appear to be empty. jaroslav@1890: * This may encounter races in which it possible (but rare) to jaroslav@1890: * reduce and "lose" a level just as it is about to contain an jaroslav@1890: * index (that will then never be encountered). This does no jaroslav@1890: * structural harm, and in practice appears to be a better option jaroslav@1890: * than allowing unrestrained growth of levels. jaroslav@1890: * jaroslav@1890: * The code for all this is more verbose than you'd like. Most jaroslav@1890: * operations entail locating an element (or position to insert an jaroslav@1890: * element). The code to do this can't be nicely factored out jaroslav@1890: * because subsequent uses require a snapshot of predecessor jaroslav@1890: * and/or successor and/or value fields which can't be returned jaroslav@1890: * all at once, at least not without creating yet another object jaroslav@1890: * to hold them -- creating such little objects is an especially jaroslav@1890: * bad idea for basic internal search operations because it adds jaroslav@1890: * to GC overhead. (This is one of the few times I've wished Java jaroslav@1890: * had macros.) Instead, some traversal code is interleaved within jaroslav@1890: * insertion and removal operations. The control logic to handle jaroslav@1890: * all the retry conditions is sometimes twisty. Most search is jaroslav@1890: * broken into 2 parts. findPredecessor() searches index nodes jaroslav@1890: * only, returning a base-level predecessor of the key. findNode() jaroslav@1890: * finishes out the base-level search. Even with this factoring, jaroslav@1890: * there is a fair amount of near-duplication of code to handle jaroslav@1890: * variants. jaroslav@1890: * jaroslav@1890: * For explanation of algorithms sharing at least a couple of jaroslav@1890: * features with this one, see Mikhail Fomitchev's thesis jaroslav@1890: * (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis jaroslav@1890: * (http://www.cl.cam.ac.uk/users/kaf24/), and Hakan Sundell's jaroslav@1890: * thesis (http://www.cs.chalmers.se/~phs/). jaroslav@1890: * jaroslav@1890: * Given the use of tree-like index nodes, you might wonder why jaroslav@1890: * this doesn't use some kind of search tree instead, which would jaroslav@1890: * support somewhat faster search operations. The reason is that jaroslav@1890: * there are no known efficient lock-free insertion and deletion jaroslav@1890: * algorithms for search trees. The immutability of the "down" jaroslav@1890: * links of index nodes (as opposed to mutable "left" fields in jaroslav@1890: * true trees) makes this tractable using only CAS operations. jaroslav@1890: * jaroslav@1890: * Notation guide for local variables jaroslav@1890: * Node: b, n, f for predecessor, node, successor jaroslav@1890: * Index: q, r, d for index node, right, down. jaroslav@1890: * t for another index node jaroslav@1890: * Head: h jaroslav@1890: * Levels: j jaroslav@1890: * Keys: k, key jaroslav@1890: * Values: v, value jaroslav@1890: * Comparisons: c jaroslav@1890: */ jaroslav@1890: jaroslav@1890: private static final long serialVersionUID = -8627078645895051609L; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Generates the initial random seed for the cheaper per-instance jaroslav@1890: * random number generators used in randomLevel. jaroslav@1890: */ jaroslav@1890: private static final Random seedGenerator = new Random(); jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Special value used to identify base-level header jaroslav@1890: */ jaroslav@1890: private static final Object BASE_HEADER = new Object(); jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * The topmost head index of the skiplist. jaroslav@1890: */ jaroslav@1890: private transient volatile HeadIndex head; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * The comparator used to maintain order in this map, or null jaroslav@1890: * if using natural ordering. jaroslav@1890: * @serial jaroslav@1890: */ jaroslav@1890: private final Comparator comparator; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Seed for simple random number generator. Not volatile since it jaroslav@1890: * doesn't matter too much if different threads don't see updates. jaroslav@1890: */ jaroslav@1890: private transient int randomSeed; jaroslav@1890: jaroslav@1890: /** Lazily initialized key set */ jaroslav@1890: private transient KeySet keySet; jaroslav@1890: /** Lazily initialized entry set */ jaroslav@1890: private transient EntrySet entrySet; jaroslav@1890: /** Lazily initialized values collection */ jaroslav@1890: private transient Values values; jaroslav@1890: /** Lazily initialized descending key set */ jaroslav@1890: private transient ConcurrentNavigableMap descendingMap; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Initializes or resets state. Needed by constructors, clone, jaroslav@1890: * clear, readObject. and ConcurrentSkipListSet.clone. jaroslav@1890: * (Note that comparator must be separately initialized.) jaroslav@1890: */ jaroslav@1890: final void initialize() { jaroslav@1890: keySet = null; jaroslav@1890: entrySet = null; jaroslav@1890: values = null; jaroslav@1890: descendingMap = null; jaroslav@1890: randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero jaroslav@1890: head = new HeadIndex(new Node(null, BASE_HEADER, null), jaroslav@1890: null, null, 1); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * compareAndSet head node jaroslav@1890: */ jaroslav@1890: private boolean casHead(HeadIndex cmp, HeadIndex val) { jaroslav@1890: return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- Nodes -------------- */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Nodes hold keys and values, and are singly linked in sorted jaroslav@1890: * order, possibly with some intervening marker nodes. The list is jaroslav@1890: * headed by a dummy node accessible as head.node. The value field jaroslav@1890: * is declared only as Object because it takes special non-V jaroslav@1890: * values for marker and header nodes. jaroslav@1890: */ jaroslav@1890: static final class Node { jaroslav@1890: final K key; jaroslav@1890: volatile Object value; jaroslav@1890: volatile Node next; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Creates a new regular node. jaroslav@1890: */ jaroslav@1890: Node(K key, Object value, Node next) { jaroslav@1890: this.key = key; jaroslav@1890: this.value = value; jaroslav@1890: this.next = next; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Creates a new marker node. A marker is distinguished by jaroslav@1890: * having its value field point to itself. Marker nodes also jaroslav@1890: * have null keys, a fact that is exploited in a few places, jaroslav@1890: * but this doesn't distinguish markers from the base-level jaroslav@1890: * header node (head.node), which also has a null key. jaroslav@1890: */ jaroslav@1890: Node(Node next) { jaroslav@1890: this.key = null; jaroslav@1890: this.value = this; jaroslav@1890: this.next = next; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * compareAndSet value field jaroslav@1890: */ jaroslav@1890: boolean casValue(Object cmp, Object val) { jaroslav@1890: return UNSAFE.compareAndSwapObject(this, valueOffset, cmp, val); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * compareAndSet next field jaroslav@1890: */ jaroslav@1890: boolean casNext(Node cmp, Node val) { jaroslav@1890: return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns true if this node is a marker. This method isn't jaroslav@1890: * actually called in any current code checking for markers jaroslav@1890: * because callers will have already read value field and need jaroslav@1890: * to use that read (not another done here) and so directly jaroslav@1890: * test if value points to node. jaroslav@1890: * @param n a possibly null reference to a node jaroslav@1890: * @return true if this node is a marker node jaroslav@1890: */ jaroslav@1890: boolean isMarker() { jaroslav@1890: return value == this; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns true if this node is the header of base-level list. jaroslav@1890: * @return true if this node is header node jaroslav@1890: */ jaroslav@1890: boolean isBaseHeader() { jaroslav@1890: return value == BASE_HEADER; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Tries to append a deletion marker to this node. jaroslav@1890: * @param f the assumed current successor of this node jaroslav@1890: * @return true if successful jaroslav@1890: */ jaroslav@1890: boolean appendMarker(Node f) { jaroslav@1890: return casNext(f, new Node(f)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Helps out a deletion by appending marker or unlinking from jaroslav@1890: * predecessor. This is called during traversals when value jaroslav@1890: * field seen to be null. jaroslav@1890: * @param b predecessor jaroslav@1890: * @param f successor jaroslav@1890: */ jaroslav@1890: void helpDelete(Node b, Node f) { jaroslav@1890: /* jaroslav@1890: * Rechecking links and then doing only one of the jaroslav@1890: * help-out stages per call tends to minimize CAS jaroslav@1890: * interference among helping threads. jaroslav@1890: */ jaroslav@1890: if (f == next && this == b.next) { jaroslav@1890: if (f == null || f.value != f) // not already marked jaroslav@1890: appendMarker(f); jaroslav@1890: else jaroslav@1890: b.casNext(this, f.next); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns value if this node contains a valid key-value pair, jaroslav@1890: * else null. jaroslav@1890: * @return this node's value if it isn't a marker or header or jaroslav@1890: * is deleted, else null. jaroslav@1890: */ jaroslav@1890: V getValidValue() { jaroslav@1890: Object v = value; jaroslav@1890: if (v == this || v == BASE_HEADER) jaroslav@1890: return null; jaroslav@1890: return (V)v; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Creates and returns a new SimpleImmutableEntry holding current jaroslav@1890: * mapping if this node holds a valid value, else null. jaroslav@1890: * @return new entry or null jaroslav@1890: */ jaroslav@1890: AbstractMap.SimpleImmutableEntry createSnapshot() { jaroslav@1890: V v = getValidValue(); jaroslav@1890: if (v == null) jaroslav@1890: return null; jaroslav@1890: return new AbstractMap.SimpleImmutableEntry(key, v); jaroslav@1890: } jaroslav@1890: jaroslav@1890: // UNSAFE mechanics jaroslav@1890: jaroslav@1890: private static final sun.misc.Unsafe UNSAFE; jaroslav@1890: private static final long valueOffset; jaroslav@1890: private static final long nextOffset; jaroslav@1890: jaroslav@1890: static { jaroslav@1890: try { jaroslav@1890: UNSAFE = sun.misc.Unsafe.getUnsafe(); jaroslav@1890: Class k = Node.class; jaroslav@1890: valueOffset = UNSAFE.objectFieldOffset jaroslav@1890: (k.getDeclaredField("value")); jaroslav@1890: nextOffset = UNSAFE.objectFieldOffset jaroslav@1890: (k.getDeclaredField("next")); jaroslav@1890: } catch (Exception e) { jaroslav@1890: throw new Error(e); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- Indexing -------------- */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Index nodes represent the levels of the skip list. Note that jaroslav@1890: * even though both Nodes and Indexes have forward-pointing jaroslav@1890: * fields, they have different types and are handled in different jaroslav@1890: * ways, that can't nicely be captured by placing field in a jaroslav@1890: * shared abstract class. jaroslav@1890: */ jaroslav@1890: static class Index { jaroslav@1890: final Node node; jaroslav@1890: final Index down; jaroslav@1890: volatile Index right; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Creates index node with given values. jaroslav@1890: */ jaroslav@1890: Index(Node node, Index down, Index right) { jaroslav@1890: this.node = node; jaroslav@1890: this.down = down; jaroslav@1890: this.right = right; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * compareAndSet right field jaroslav@1890: */ jaroslav@1890: final boolean casRight(Index cmp, Index val) { jaroslav@1890: return UNSAFE.compareAndSwapObject(this, rightOffset, cmp, val); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns true if the node this indexes has been deleted. jaroslav@1890: * @return true if indexed node is known to be deleted jaroslav@1890: */ jaroslav@1890: final boolean indexesDeletedNode() { jaroslav@1890: return node.value == null; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Tries to CAS newSucc as successor. To minimize races with jaroslav@1890: * unlink that may lose this index node, if the node being jaroslav@1890: * indexed is known to be deleted, it doesn't try to link in. jaroslav@1890: * @param succ the expected current successor jaroslav@1890: * @param newSucc the new successor jaroslav@1890: * @return true if successful jaroslav@1890: */ jaroslav@1890: final boolean link(Index succ, Index newSucc) { jaroslav@1890: Node n = node; jaroslav@1890: newSucc.right = succ; jaroslav@1890: return n.value != null && casRight(succ, newSucc); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Tries to CAS right field to skip over apparent successor jaroslav@1890: * succ. Fails (forcing a retraversal by caller) if this node jaroslav@1890: * is known to be deleted. jaroslav@1890: * @param succ the expected current successor jaroslav@1890: * @return true if successful jaroslav@1890: */ jaroslav@1890: final boolean unlink(Index succ) { jaroslav@1890: return !indexesDeletedNode() && casRight(succ, succ.right); jaroslav@1890: } jaroslav@1890: jaroslav@1890: // Unsafe mechanics jaroslav@1890: private static final sun.misc.Unsafe UNSAFE; jaroslav@1890: private static final long rightOffset; jaroslav@1890: static { jaroslav@1890: try { jaroslav@1890: UNSAFE = sun.misc.Unsafe.getUnsafe(); jaroslav@1890: Class k = Index.class; jaroslav@1890: rightOffset = UNSAFE.objectFieldOffset jaroslav@1890: (k.getDeclaredField("right")); jaroslav@1890: } catch (Exception e) { jaroslav@1890: throw new Error(e); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- Head nodes -------------- */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Nodes heading each level keep track of their level. jaroslav@1890: */ jaroslav@1890: static final class HeadIndex extends Index { jaroslav@1890: final int level; jaroslav@1890: HeadIndex(Node node, Index down, Index right, int level) { jaroslav@1890: super(node, down, right); jaroslav@1890: this.level = level; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- Comparison utilities -------------- */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Represents a key with a comparator as a Comparable. jaroslav@1890: * jaroslav@1890: * Because most sorted collections seem to use natural ordering on jaroslav@1890: * Comparables (Strings, Integers, etc), most internal methods are jaroslav@1890: * geared to use them. This is generally faster than checking jaroslav@1890: * per-comparison whether to use comparator or comparable because jaroslav@1890: * it doesn't require a (Comparable) cast for each comparison. jaroslav@1890: * (Optimizers can only sometimes remove such redundant checks jaroslav@1890: * themselves.) When Comparators are used, jaroslav@1890: * ComparableUsingComparators are created so that they act in the jaroslav@1890: * same way as natural orderings. This penalizes use of jaroslav@1890: * Comparators vs Comparables, which seems like the right jaroslav@1890: * tradeoff. jaroslav@1890: */ jaroslav@1890: static final class ComparableUsingComparator implements Comparable { jaroslav@1890: final K actualKey; jaroslav@1890: final Comparator cmp; jaroslav@1890: ComparableUsingComparator(K key, Comparator cmp) { jaroslav@1890: this.actualKey = key; jaroslav@1890: this.cmp = cmp; jaroslav@1890: } jaroslav@1890: public int compareTo(K k2) { jaroslav@1890: return cmp.compare(actualKey, k2); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * If using comparator, return a ComparableUsingComparator, else jaroslav@1890: * cast key as Comparable, which may cause ClassCastException, jaroslav@1890: * which is propagated back to caller. jaroslav@1890: */ jaroslav@1890: private Comparable comparable(Object key) jaroslav@1890: throws ClassCastException { jaroslav@1890: if (key == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: if (comparator != null) jaroslav@1890: return new ComparableUsingComparator((K)key, comparator); jaroslav@1890: else jaroslav@1890: return (Comparable)key; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Compares using comparator or natural ordering. Used when the jaroslav@1890: * ComparableUsingComparator approach doesn't apply. jaroslav@1890: */ jaroslav@1890: int compare(K k1, K k2) throws ClassCastException { jaroslav@1890: Comparator cmp = comparator; jaroslav@1890: if (cmp != null) jaroslav@1890: return cmp.compare(k1, k2); jaroslav@1890: else jaroslav@1890: return ((Comparable)k1).compareTo(k2); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns true if given key greater than or equal to least and jaroslav@1890: * strictly less than fence, bypassing either test if least or jaroslav@1890: * fence are null. Needed mainly in submap operations. jaroslav@1890: */ jaroslav@1890: boolean inHalfOpenRange(K key, K least, K fence) { jaroslav@1890: if (key == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: return ((least == null || compare(key, least) >= 0) && jaroslav@1890: (fence == null || compare(key, fence) < 0)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns true if given key greater than or equal to least and less jaroslav@1890: * or equal to fence. Needed mainly in submap operations. jaroslav@1890: */ jaroslav@1890: boolean inOpenRange(K key, K least, K fence) { jaroslav@1890: if (key == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: return ((least == null || compare(key, least) >= 0) && jaroslav@1890: (fence == null || compare(key, fence) <= 0)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- Traversal -------------- */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns a base-level node with key strictly less than given key, jaroslav@1890: * or the base-level header if there is no such node. Also jaroslav@1890: * unlinks indexes to deleted nodes found along the way. Callers jaroslav@1890: * rely on this side-effect of clearing indices to deleted nodes. jaroslav@1890: * @param key the key jaroslav@1890: * @return a predecessor of key jaroslav@1890: */ jaroslav@1890: private Node findPredecessor(Comparable key) { jaroslav@1890: if (key == null) jaroslav@1890: throw new NullPointerException(); // don't postpone errors jaroslav@1890: for (;;) { jaroslav@1890: Index q = head; jaroslav@1890: Index r = q.right; jaroslav@1890: for (;;) { jaroslav@1890: if (r != null) { jaroslav@1890: Node n = r.node; jaroslav@1890: K k = n.key; jaroslav@1890: if (n.value == null) { jaroslav@1890: if (!q.unlink(r)) jaroslav@1890: break; // restart jaroslav@1890: r = q.right; // reread r jaroslav@1890: continue; jaroslav@1890: } jaroslav@1890: if (key.compareTo(k) > 0) { jaroslav@1890: q = r; jaroslav@1890: r = r.right; jaroslav@1890: continue; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: Index d = q.down; jaroslav@1890: if (d != null) { jaroslav@1890: q = d; jaroslav@1890: r = d.right; jaroslav@1890: } else jaroslav@1890: return q.node; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns node holding key or null if no such, clearing out any jaroslav@1890: * deleted nodes seen along the way. Repeatedly traverses at jaroslav@1890: * base-level looking for key starting at predecessor returned jaroslav@1890: * from findPredecessor, processing base-level deletions as jaroslav@1890: * encountered. Some callers rely on this side-effect of clearing jaroslav@1890: * deleted nodes. jaroslav@1890: * jaroslav@1890: * Restarts occur, at traversal step centered on node n, if: jaroslav@1890: * jaroslav@1890: * (1) After reading n's next field, n is no longer assumed jaroslav@1890: * predecessor b's current successor, which means that jaroslav@1890: * we don't have a consistent 3-node snapshot and so cannot jaroslav@1890: * unlink any subsequent deleted nodes encountered. jaroslav@1890: * jaroslav@1890: * (2) n's value field is null, indicating n is deleted, in jaroslav@1890: * which case we help out an ongoing structural deletion jaroslav@1890: * before retrying. Even though there are cases where such jaroslav@1890: * unlinking doesn't require restart, they aren't sorted out jaroslav@1890: * here because doing so would not usually outweigh cost of jaroslav@1890: * restarting. jaroslav@1890: * jaroslav@1890: * (3) n is a marker or n's predecessor's value field is null, jaroslav@1890: * indicating (among other possibilities) that jaroslav@1890: * findPredecessor returned a deleted node. We can't unlink jaroslav@1890: * the node because we don't know its predecessor, so rely jaroslav@1890: * on another call to findPredecessor to notice and return jaroslav@1890: * some earlier predecessor, which it will do. This check is jaroslav@1890: * only strictly needed at beginning of loop, (and the jaroslav@1890: * b.value check isn't strictly needed at all) but is done jaroslav@1890: * each iteration to help avoid contention with other jaroslav@1890: * threads by callers that will fail to be able to change jaroslav@1890: * links, and so will retry anyway. jaroslav@1890: * jaroslav@1890: * The traversal loops in doPut, doRemove, and findNear all jaroslav@1890: * include the same three kinds of checks. And specialized jaroslav@1890: * versions appear in findFirst, and findLast and their jaroslav@1890: * variants. They can't easily share code because each uses the jaroslav@1890: * reads of fields held in locals occurring in the orders they jaroslav@1890: * were performed. jaroslav@1890: * jaroslav@1890: * @param key the key jaroslav@1890: * @return node holding key, or null if no such jaroslav@1890: */ jaroslav@1890: private Node findNode(Comparable key) { jaroslav@1890: for (;;) { jaroslav@1890: Node b = findPredecessor(key); jaroslav@1890: Node n = b.next; jaroslav@1890: for (;;) { jaroslav@1890: if (n == null) jaroslav@1890: return null; jaroslav@1890: Node f = n.next; jaroslav@1890: if (n != b.next) // inconsistent read jaroslav@1890: break; jaroslav@1890: Object v = n.value; jaroslav@1890: if (v == null) { // n is deleted jaroslav@1890: n.helpDelete(b, f); jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: if (v == n || b.value == null) // b is deleted jaroslav@1890: break; jaroslav@1890: int c = key.compareTo(n.key); jaroslav@1890: if (c == 0) jaroslav@1890: return n; jaroslav@1890: if (c < 0) jaroslav@1890: return null; jaroslav@1890: b = n; jaroslav@1890: n = f; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Gets value for key using findNode. jaroslav@1890: * @param okey the key jaroslav@1890: * @return the value, or null if absent jaroslav@1890: */ jaroslav@1890: private V doGet(Object okey) { jaroslav@1890: Comparable key = comparable(okey); jaroslav@1890: /* jaroslav@1890: * Loop needed here and elsewhere in case value field goes jaroslav@1890: * null just as it is about to be returned, in which case we jaroslav@1890: * lost a race with a deletion, so must retry. jaroslav@1890: */ jaroslav@1890: for (;;) { jaroslav@1890: Node n = findNode(key); jaroslav@1890: if (n == null) jaroslav@1890: return null; jaroslav@1890: Object v = n.value; jaroslav@1890: if (v != null) jaroslav@1890: return (V)v; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- Insertion -------------- */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Main insertion method. Adds element if not present, or jaroslav@1890: * replaces value if present and onlyIfAbsent is false. jaroslav@1890: * @param kkey the key jaroslav@1890: * @param value the value that must be associated with key jaroslav@1890: * @param onlyIfAbsent if should not insert if already present jaroslav@1890: * @return the old value, or null if newly inserted jaroslav@1890: */ jaroslav@1890: private V doPut(K kkey, V value, boolean onlyIfAbsent) { jaroslav@1890: Comparable key = comparable(kkey); jaroslav@1890: for (;;) { jaroslav@1890: Node b = findPredecessor(key); jaroslav@1890: Node n = b.next; jaroslav@1890: for (;;) { jaroslav@1890: if (n != null) { jaroslav@1890: Node f = n.next; jaroslav@1890: if (n != b.next) // inconsistent read jaroslav@1890: break; jaroslav@1890: Object v = n.value; jaroslav@1890: if (v == null) { // n is deleted jaroslav@1890: n.helpDelete(b, f); jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: if (v == n || b.value == null) // b is deleted jaroslav@1890: break; jaroslav@1890: int c = key.compareTo(n.key); jaroslav@1890: if (c > 0) { jaroslav@1890: b = n; jaroslav@1890: n = f; jaroslav@1890: continue; jaroslav@1890: } jaroslav@1890: if (c == 0) { jaroslav@1890: if (onlyIfAbsent || n.casValue(v, value)) jaroslav@1890: return (V)v; jaroslav@1890: else jaroslav@1890: break; // restart if lost race to replace value jaroslav@1890: } jaroslav@1890: // else c < 0; fall through jaroslav@1890: } jaroslav@1890: jaroslav@1890: Node z = new Node(kkey, value, n); jaroslav@1890: if (!b.casNext(n, z)) jaroslav@1890: break; // restart if lost race to append to b jaroslav@1890: int level = randomLevel(); jaroslav@1890: if (level > 0) jaroslav@1890: insertIndex(z, level); jaroslav@1890: return null; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns a random level for inserting a new node. jaroslav@1890: * Hardwired to k=1, p=0.5, max 31 (see above and jaroslav@1890: * Pugh's "Skip List Cookbook", sec 3.4). jaroslav@1890: * jaroslav@1890: * This uses the simplest of the generators described in George jaroslav@1890: * Marsaglia's "Xorshift RNGs" paper. This is not a high-quality jaroslav@1890: * generator but is acceptable here. jaroslav@1890: */ jaroslav@1890: private int randomLevel() { jaroslav@1890: int x = randomSeed; jaroslav@1890: x ^= x << 13; jaroslav@1890: x ^= x >>> 17; jaroslav@1890: randomSeed = x ^= x << 5; jaroslav@1890: if ((x & 0x80000001) != 0) // test highest and lowest bits jaroslav@1890: return 0; jaroslav@1890: int level = 1; jaroslav@1890: while (((x >>>= 1) & 1) != 0) ++level; jaroslav@1890: return level; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Creates and adds index nodes for the given node. jaroslav@1890: * @param z the node jaroslav@1890: * @param level the level of the index jaroslav@1890: */ jaroslav@1890: private void insertIndex(Node z, int level) { jaroslav@1890: HeadIndex h = head; jaroslav@1890: int max = h.level; jaroslav@1890: jaroslav@1890: if (level <= max) { jaroslav@1890: Index idx = null; jaroslav@1890: for (int i = 1; i <= level; ++i) jaroslav@1890: idx = new Index(z, idx, null); jaroslav@1890: addIndex(idx, h, level); jaroslav@1890: jaroslav@1890: } else { // Add a new level jaroslav@1890: /* jaroslav@1890: * To reduce interference by other threads checking for jaroslav@1890: * empty levels in tryReduceLevel, new levels are added jaroslav@1890: * with initialized right pointers. Which in turn requires jaroslav@1890: * keeping levels in an array to access them while jaroslav@1890: * creating new head index nodes from the opposite jaroslav@1890: * direction. jaroslav@1890: */ jaroslav@1890: level = max + 1; jaroslav@1890: Index[] idxs = (Index[])new Index[level+1]; jaroslav@1890: Index idx = null; jaroslav@1890: for (int i = 1; i <= level; ++i) jaroslav@1890: idxs[i] = idx = new Index(z, idx, null); jaroslav@1890: jaroslav@1890: HeadIndex oldh; jaroslav@1890: int k; jaroslav@1890: for (;;) { jaroslav@1890: oldh = head; jaroslav@1890: int oldLevel = oldh.level; jaroslav@1890: if (level <= oldLevel) { // lost race to add level jaroslav@1890: k = level; jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: HeadIndex newh = oldh; jaroslav@1890: Node oldbase = oldh.node; jaroslav@1890: for (int j = oldLevel+1; j <= level; ++j) jaroslav@1890: newh = new HeadIndex(oldbase, newh, idxs[j], j); jaroslav@1890: if (casHead(oldh, newh)) { jaroslav@1890: k = oldLevel; jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: addIndex(idxs[k], oldh, k); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Adds given index nodes from given level down to 1. jaroslav@1890: * @param idx the topmost index node being inserted jaroslav@1890: * @param h the value of head to use to insert. This must be jaroslav@1890: * snapshotted by callers to provide correct insertion level jaroslav@1890: * @param indexLevel the level of the index jaroslav@1890: */ jaroslav@1890: private void addIndex(Index idx, HeadIndex h, int indexLevel) { jaroslav@1890: // Track next level to insert in case of retries jaroslav@1890: int insertionLevel = indexLevel; jaroslav@1890: Comparable key = comparable(idx.node.key); jaroslav@1890: if (key == null) throw new NullPointerException(); jaroslav@1890: jaroslav@1890: // Similar to findPredecessor, but adding index nodes along jaroslav@1890: // path to key. jaroslav@1890: for (;;) { jaroslav@1890: int j = h.level; jaroslav@1890: Index q = h; jaroslav@1890: Index r = q.right; jaroslav@1890: Index t = idx; jaroslav@1890: for (;;) { jaroslav@1890: if (r != null) { jaroslav@1890: Node n = r.node; jaroslav@1890: // compare before deletion check avoids needing recheck jaroslav@1890: int c = key.compareTo(n.key); jaroslav@1890: if (n.value == null) { jaroslav@1890: if (!q.unlink(r)) jaroslav@1890: break; jaroslav@1890: r = q.right; jaroslav@1890: continue; jaroslav@1890: } jaroslav@1890: if (c > 0) { jaroslav@1890: q = r; jaroslav@1890: r = r.right; jaroslav@1890: continue; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: if (j == insertionLevel) { jaroslav@1890: // Don't insert index if node already deleted jaroslav@1890: if (t.indexesDeletedNode()) { jaroslav@1890: findNode(key); // cleans up jaroslav@1890: return; jaroslav@1890: } jaroslav@1890: if (!q.link(r, t)) jaroslav@1890: break; // restart jaroslav@1890: if (--insertionLevel == 0) { jaroslav@1890: // need final deletion check before return jaroslav@1890: if (t.indexesDeletedNode()) jaroslav@1890: findNode(key); jaroslav@1890: return; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: if (--j >= insertionLevel && j < indexLevel) jaroslav@1890: t = t.down; jaroslav@1890: q = q.down; jaroslav@1890: r = q.right; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- Deletion -------------- */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Main deletion method. Locates node, nulls value, appends a jaroslav@1890: * deletion marker, unlinks predecessor, removes associated index jaroslav@1890: * nodes, and possibly reduces head index level. jaroslav@1890: * jaroslav@1890: * Index nodes are cleared out simply by calling findPredecessor. jaroslav@1890: * which unlinks indexes to deleted nodes found along path to key, jaroslav@1890: * which will include the indexes to this node. This is done jaroslav@1890: * unconditionally. We can't check beforehand whether there are jaroslav@1890: * index nodes because it might be the case that some or all jaroslav@1890: * indexes hadn't been inserted yet for this node during initial jaroslav@1890: * search for it, and we'd like to ensure lack of garbage jaroslav@1890: * retention, so must call to be sure. jaroslav@1890: * jaroslav@1890: * @param okey the key jaroslav@1890: * @param value if non-null, the value that must be jaroslav@1890: * associated with key jaroslav@1890: * @return the node, or null if not found jaroslav@1890: */ jaroslav@1890: final V doRemove(Object okey, Object value) { jaroslav@1890: Comparable key = comparable(okey); jaroslav@1890: for (;;) { jaroslav@1890: Node b = findPredecessor(key); jaroslav@1890: Node n = b.next; jaroslav@1890: for (;;) { jaroslav@1890: if (n == null) jaroslav@1890: return null; jaroslav@1890: Node f = n.next; jaroslav@1890: if (n != b.next) // inconsistent read jaroslav@1890: break; jaroslav@1890: Object v = n.value; jaroslav@1890: if (v == null) { // n is deleted jaroslav@1890: n.helpDelete(b, f); jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: if (v == n || b.value == null) // b is deleted jaroslav@1890: break; jaroslav@1890: int c = key.compareTo(n.key); jaroslav@1890: if (c < 0) jaroslav@1890: return null; jaroslav@1890: if (c > 0) { jaroslav@1890: b = n; jaroslav@1890: n = f; jaroslav@1890: continue; jaroslav@1890: } jaroslav@1890: if (value != null && !value.equals(v)) jaroslav@1890: return null; jaroslav@1890: if (!n.casValue(v, null)) jaroslav@1890: break; jaroslav@1890: if (!n.appendMarker(f) || !b.casNext(n, f)) jaroslav@1890: findNode(key); // Retry via findNode jaroslav@1890: else { jaroslav@1890: findPredecessor(key); // Clean index jaroslav@1890: if (head.right == null) jaroslav@1890: tryReduceLevel(); jaroslav@1890: } jaroslav@1890: return (V)v; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Possibly reduce head level if it has no nodes. This method can jaroslav@1890: * (rarely) make mistakes, in which case levels can disappear even jaroslav@1890: * though they are about to contain index nodes. This impacts jaroslav@1890: * performance, not correctness. To minimize mistakes as well as jaroslav@1890: * to reduce hysteresis, the level is reduced by one only if the jaroslav@1890: * topmost three levels look empty. Also, if the removed level jaroslav@1890: * looks non-empty after CAS, we try to change it back quick jaroslav@1890: * before anyone notices our mistake! (This trick works pretty jaroslav@1890: * well because this method will practically never make mistakes jaroslav@1890: * unless current thread stalls immediately before first CAS, in jaroslav@1890: * which case it is very unlikely to stall again immediately jaroslav@1890: * afterwards, so will recover.) jaroslav@1890: * jaroslav@1890: * We put up with all this rather than just let levels grow jaroslav@1890: * because otherwise, even a small map that has undergone a large jaroslav@1890: * number of insertions and removals will have a lot of levels, jaroslav@1890: * slowing down access more than would an occasional unwanted jaroslav@1890: * reduction. jaroslav@1890: */ jaroslav@1890: private void tryReduceLevel() { jaroslav@1890: HeadIndex h = head; jaroslav@1890: HeadIndex d; jaroslav@1890: HeadIndex e; jaroslav@1890: if (h.level > 3 && jaroslav@1890: (d = (HeadIndex)h.down) != null && jaroslav@1890: (e = (HeadIndex)d.down) != null && jaroslav@1890: e.right == null && jaroslav@1890: d.right == null && jaroslav@1890: h.right == null && jaroslav@1890: casHead(h, d) && // try to set jaroslav@1890: h.right != null) // recheck jaroslav@1890: casHead(d, h); // try to backout jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- Finding and removing first element -------------- */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Specialized variant of findNode to get first valid node. jaroslav@1890: * @return first node or null if empty jaroslav@1890: */ jaroslav@1890: Node findFirst() { jaroslav@1890: for (;;) { jaroslav@1890: Node b = head.node; jaroslav@1890: Node n = b.next; jaroslav@1890: if (n == null) jaroslav@1890: return null; jaroslav@1890: if (n.value != null) jaroslav@1890: return n; jaroslav@1890: n.helpDelete(b, n.next); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Removes first entry; returns its snapshot. jaroslav@1890: * @return null if empty, else snapshot of first entry jaroslav@1890: */ jaroslav@1890: Map.Entry doRemoveFirstEntry() { jaroslav@1890: for (;;) { jaroslav@1890: Node b = head.node; jaroslav@1890: Node n = b.next; jaroslav@1890: if (n == null) jaroslav@1890: return null; jaroslav@1890: Node f = n.next; jaroslav@1890: if (n != b.next) jaroslav@1890: continue; jaroslav@1890: Object v = n.value; jaroslav@1890: if (v == null) { jaroslav@1890: n.helpDelete(b, f); jaroslav@1890: continue; jaroslav@1890: } jaroslav@1890: if (!n.casValue(v, null)) jaroslav@1890: continue; jaroslav@1890: if (!n.appendMarker(f) || !b.casNext(n, f)) jaroslav@1890: findFirst(); // retry jaroslav@1890: clearIndexToFirst(); jaroslav@1890: return new AbstractMap.SimpleImmutableEntry(n.key, (V)v); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Clears out index nodes associated with deleted first entry. jaroslav@1890: */ jaroslav@1890: private void clearIndexToFirst() { jaroslav@1890: for (;;) { jaroslav@1890: Index q = head; jaroslav@1890: for (;;) { jaroslav@1890: Index r = q.right; jaroslav@1890: if (r != null && r.indexesDeletedNode() && !q.unlink(r)) jaroslav@1890: break; jaroslav@1890: if ((q = q.down) == null) { jaroslav@1890: if (head.right == null) jaroslav@1890: tryReduceLevel(); jaroslav@1890: return; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: jaroslav@1890: /* ---------------- Finding and removing last element -------------- */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Specialized version of find to get last valid node. jaroslav@1890: * @return last node or null if empty jaroslav@1890: */ jaroslav@1890: Node findLast() { jaroslav@1890: /* jaroslav@1890: * findPredecessor can't be used to traverse index level jaroslav@1890: * because this doesn't use comparisons. So traversals of jaroslav@1890: * both levels are folded together. jaroslav@1890: */ jaroslav@1890: Index q = head; jaroslav@1890: for (;;) { jaroslav@1890: Index d, r; jaroslav@1890: if ((r = q.right) != null) { jaroslav@1890: if (r.indexesDeletedNode()) { jaroslav@1890: q.unlink(r); jaroslav@1890: q = head; // restart jaroslav@1890: } jaroslav@1890: else jaroslav@1890: q = r; jaroslav@1890: } else if ((d = q.down) != null) { jaroslav@1890: q = d; jaroslav@1890: } else { jaroslav@1890: Node b = q.node; jaroslav@1890: Node n = b.next; jaroslav@1890: for (;;) { jaroslav@1890: if (n == null) jaroslav@1890: return b.isBaseHeader() ? null : b; jaroslav@1890: Node f = n.next; // inconsistent read jaroslav@1890: if (n != b.next) jaroslav@1890: break; jaroslav@1890: Object v = n.value; jaroslav@1890: if (v == null) { // n is deleted jaroslav@1890: n.helpDelete(b, f); jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: if (v == n || b.value == null) // b is deleted jaroslav@1890: break; jaroslav@1890: b = n; jaroslav@1890: n = f; jaroslav@1890: } jaroslav@1890: q = head; // restart jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Specialized variant of findPredecessor to get predecessor of last jaroslav@1890: * valid node. Needed when removing the last entry. It is possible jaroslav@1890: * that all successors of returned node will have been deleted upon jaroslav@1890: * return, in which case this method can be retried. jaroslav@1890: * @return likely predecessor of last node jaroslav@1890: */ jaroslav@1890: private Node findPredecessorOfLast() { jaroslav@1890: for (;;) { jaroslav@1890: Index q = head; jaroslav@1890: for (;;) { jaroslav@1890: Index d, r; jaroslav@1890: if ((r = q.right) != null) { jaroslav@1890: if (r.indexesDeletedNode()) { jaroslav@1890: q.unlink(r); jaroslav@1890: break; // must restart jaroslav@1890: } jaroslav@1890: // proceed as far across as possible without overshooting jaroslav@1890: if (r.node.next != null) { jaroslav@1890: q = r; jaroslav@1890: continue; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: if ((d = q.down) != null) jaroslav@1890: q = d; jaroslav@1890: else jaroslav@1890: return q.node; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Removes last entry; returns its snapshot. jaroslav@1890: * Specialized variant of doRemove. jaroslav@1890: * @return null if empty, else snapshot of last entry jaroslav@1890: */ jaroslav@1890: Map.Entry doRemoveLastEntry() { jaroslav@1890: for (;;) { jaroslav@1890: Node b = findPredecessorOfLast(); jaroslav@1890: Node n = b.next; jaroslav@1890: if (n == null) { jaroslav@1890: if (b.isBaseHeader()) // empty jaroslav@1890: return null; jaroslav@1890: else jaroslav@1890: continue; // all b's successors are deleted; retry jaroslav@1890: } jaroslav@1890: for (;;) { jaroslav@1890: Node f = n.next; jaroslav@1890: if (n != b.next) // inconsistent read jaroslav@1890: break; jaroslav@1890: Object v = n.value; jaroslav@1890: if (v == null) { // n is deleted jaroslav@1890: n.helpDelete(b, f); jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: if (v == n || b.value == null) // b is deleted jaroslav@1890: break; jaroslav@1890: if (f != null) { jaroslav@1890: b = n; jaroslav@1890: n = f; jaroslav@1890: continue; jaroslav@1890: } jaroslav@1890: if (!n.casValue(v, null)) jaroslav@1890: break; jaroslav@1890: K key = n.key; jaroslav@1890: Comparable ck = comparable(key); jaroslav@1890: if (!n.appendMarker(f) || !b.casNext(n, f)) jaroslav@1890: findNode(ck); // Retry via findNode jaroslav@1890: else { jaroslav@1890: findPredecessor(ck); // Clean index jaroslav@1890: if (head.right == null) jaroslav@1890: tryReduceLevel(); jaroslav@1890: } jaroslav@1890: return new AbstractMap.SimpleImmutableEntry(key, (V)v); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- Relational operations -------------- */ jaroslav@1890: jaroslav@1890: // Control values OR'ed as arguments to findNear jaroslav@1890: jaroslav@1890: private static final int EQ = 1; jaroslav@1890: private static final int LT = 2; jaroslav@1890: private static final int GT = 0; // Actually checked as !LT jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Utility for ceiling, floor, lower, higher methods. jaroslav@1890: * @param kkey the key jaroslav@1890: * @param rel the relation -- OR'ed combination of EQ, LT, GT jaroslav@1890: * @return nearest node fitting relation, or null if no such jaroslav@1890: */ jaroslav@1890: Node findNear(K kkey, int rel) { jaroslav@1890: Comparable key = comparable(kkey); jaroslav@1890: for (;;) { jaroslav@1890: Node b = findPredecessor(key); jaroslav@1890: Node n = b.next; jaroslav@1890: for (;;) { jaroslav@1890: if (n == null) jaroslav@1890: return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b; jaroslav@1890: Node f = n.next; jaroslav@1890: if (n != b.next) // inconsistent read jaroslav@1890: break; jaroslav@1890: Object v = n.value; jaroslav@1890: if (v == null) { // n is deleted jaroslav@1890: n.helpDelete(b, f); jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: if (v == n || b.value == null) // b is deleted jaroslav@1890: break; jaroslav@1890: int c = key.compareTo(n.key); jaroslav@1890: if ((c == 0 && (rel & EQ) != 0) || jaroslav@1890: (c < 0 && (rel & LT) == 0)) jaroslav@1890: return n; jaroslav@1890: if ( c <= 0 && (rel & LT) != 0) jaroslav@1890: return b.isBaseHeader() ? null : b; jaroslav@1890: b = n; jaroslav@1890: n = f; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns SimpleImmutableEntry for results of findNear. jaroslav@1890: * @param key the key jaroslav@1890: * @param rel the relation -- OR'ed combination of EQ, LT, GT jaroslav@1890: * @return Entry fitting relation, or null if no such jaroslav@1890: */ jaroslav@1890: AbstractMap.SimpleImmutableEntry getNear(K key, int rel) { jaroslav@1890: for (;;) { jaroslav@1890: Node n = findNear(key, rel); jaroslav@1890: if (n == null) jaroslav@1890: return null; jaroslav@1890: AbstractMap.SimpleImmutableEntry e = n.createSnapshot(); jaroslav@1890: if (e != null) jaroslav@1890: return e; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: jaroslav@1890: /* ---------------- Constructors -------------- */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Constructs a new, empty map, sorted according to the jaroslav@1890: * {@linkplain Comparable natural ordering} of the keys. jaroslav@1890: */ jaroslav@1890: public ConcurrentSkipListMap() { jaroslav@1890: this.comparator = null; jaroslav@1890: initialize(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Constructs a new, empty map, sorted according to the specified jaroslav@1890: * comparator. jaroslav@1890: * jaroslav@1890: * @param comparator the comparator that will be used to order this map. jaroslav@1890: * If null, the {@linkplain Comparable natural jaroslav@1890: * ordering} of the keys will be used. jaroslav@1890: */ jaroslav@1890: public ConcurrentSkipListMap(Comparator comparator) { jaroslav@1890: this.comparator = comparator; jaroslav@1890: initialize(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Constructs a new map containing the same mappings as the given map, jaroslav@1890: * sorted according to the {@linkplain Comparable natural ordering} of jaroslav@1890: * the keys. jaroslav@1890: * jaroslav@1890: * @param m the map whose mappings are to be placed in this map jaroslav@1890: * @throws ClassCastException if the keys in m are not jaroslav@1890: * {@link Comparable}, or are not mutually comparable jaroslav@1890: * @throws NullPointerException if the specified map or any of its keys jaroslav@1890: * or values are null jaroslav@1890: */ jaroslav@1890: public ConcurrentSkipListMap(Map m) { jaroslav@1890: this.comparator = null; jaroslav@1890: initialize(); jaroslav@1890: putAll(m); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Constructs a new map containing the same mappings and using the jaroslav@1890: * same ordering as the specified sorted map. jaroslav@1890: * jaroslav@1890: * @param m the sorted map whose mappings are to be placed in this jaroslav@1890: * map, and whose comparator is to be used to sort this map jaroslav@1890: * @throws NullPointerException if the specified sorted map or any of jaroslav@1890: * its keys or values are null jaroslav@1890: */ jaroslav@1890: public ConcurrentSkipListMap(SortedMap m) { jaroslav@1890: this.comparator = m.comparator(); jaroslav@1890: initialize(); jaroslav@1890: buildFromSorted(m); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns a shallow copy of this ConcurrentSkipListMap jaroslav@1890: * instance. (The keys and values themselves are not cloned.) jaroslav@1890: * jaroslav@1890: * @return a shallow copy of this map jaroslav@1890: */ jaroslav@1890: public ConcurrentSkipListMap clone() { jaroslav@1890: ConcurrentSkipListMap clone = null; jaroslav@1890: try { jaroslav@1890: clone = (ConcurrentSkipListMap) super.clone(); jaroslav@1890: } catch (CloneNotSupportedException e) { jaroslav@1890: throw new InternalError(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: clone.initialize(); jaroslav@1890: clone.buildFromSorted(this); jaroslav@1890: return clone; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Streamlined bulk insertion to initialize from elements of jaroslav@1890: * given sorted map. Call only from constructor or clone jaroslav@1890: * method. jaroslav@1890: */ jaroslav@1890: private void buildFromSorted(SortedMap map) { jaroslav@1890: if (map == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: jaroslav@1890: HeadIndex h = head; jaroslav@1890: Node basepred = h.node; jaroslav@1890: jaroslav@1890: // Track the current rightmost node at each level. Uses an jaroslav@1890: // ArrayList to avoid committing to initial or maximum level. jaroslav@1890: ArrayList> preds = new ArrayList>(); jaroslav@1890: jaroslav@1890: // initialize jaroslav@1890: for (int i = 0; i <= h.level; ++i) jaroslav@1890: preds.add(null); jaroslav@1890: Index q = h; jaroslav@1890: for (int i = h.level; i > 0; --i) { jaroslav@1890: preds.set(i, q); jaroslav@1890: q = q.down; jaroslav@1890: } jaroslav@1890: jaroslav@1890: Iterator> it = jaroslav@1890: map.entrySet().iterator(); jaroslav@1890: while (it.hasNext()) { jaroslav@1890: Map.Entry e = it.next(); jaroslav@1890: int j = randomLevel(); jaroslav@1890: if (j > h.level) j = h.level + 1; jaroslav@1890: K k = e.getKey(); jaroslav@1890: V v = e.getValue(); jaroslav@1890: if (k == null || v == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: Node z = new Node(k, v, null); jaroslav@1890: basepred.next = z; jaroslav@1890: basepred = z; jaroslav@1890: if (j > 0) { jaroslav@1890: Index idx = null; jaroslav@1890: for (int i = 1; i <= j; ++i) { jaroslav@1890: idx = new Index(z, idx, null); jaroslav@1890: if (i > h.level) jaroslav@1890: h = new HeadIndex(h.node, h, idx, i); jaroslav@1890: jaroslav@1890: if (i < preds.size()) { jaroslav@1890: preds.get(i).right = idx; jaroslav@1890: preds.set(i, idx); jaroslav@1890: } else jaroslav@1890: preds.add(idx); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: head = h; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- Serialization -------------- */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Save the state of this map to a stream. jaroslav@1890: * jaroslav@1890: * @serialData The key (Object) and value (Object) for each jaroslav@1890: * key-value mapping represented by the map, followed by jaroslav@1890: * null. The key-value mappings are emitted in key-order jaroslav@1890: * (as determined by the Comparator, or by the keys' natural jaroslav@1890: * ordering if no Comparator). jaroslav@1890: */ jaroslav@1890: private void writeObject(java.io.ObjectOutputStream s) jaroslav@1890: throws java.io.IOException { jaroslav@1890: // Write out the Comparator and any hidden stuff jaroslav@1890: s.defaultWriteObject(); jaroslav@1890: jaroslav@1890: // Write out keys and values (alternating) jaroslav@1890: for (Node n = findFirst(); n != null; n = n.next) { jaroslav@1890: V v = n.getValidValue(); jaroslav@1890: if (v != null) { jaroslav@1890: s.writeObject(n.key); jaroslav@1890: s.writeObject(v); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: s.writeObject(null); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Reconstitute the map from a stream. jaroslav@1890: */ jaroslav@1890: private void readObject(final java.io.ObjectInputStream s) jaroslav@1890: throws java.io.IOException, ClassNotFoundException { jaroslav@1890: // Read in the Comparator and any hidden stuff jaroslav@1890: s.defaultReadObject(); jaroslav@1890: // Reset transients jaroslav@1890: initialize(); jaroslav@1890: jaroslav@1890: /* jaroslav@1890: * This is nearly identical to buildFromSorted, but is jaroslav@1890: * distinct because readObject calls can't be nicely adapted jaroslav@1890: * as the kind of iterator needed by buildFromSorted. (They jaroslav@1890: * can be, but doing so requires type cheats and/or creation jaroslav@1890: * of adaptor classes.) It is simpler to just adapt the code. jaroslav@1890: */ jaroslav@1890: jaroslav@1890: HeadIndex h = head; jaroslav@1890: Node basepred = h.node; jaroslav@1890: ArrayList> preds = new ArrayList>(); jaroslav@1890: for (int i = 0; i <= h.level; ++i) jaroslav@1890: preds.add(null); jaroslav@1890: Index q = h; jaroslav@1890: for (int i = h.level; i > 0; --i) { jaroslav@1890: preds.set(i, q); jaroslav@1890: q = q.down; jaroslav@1890: } jaroslav@1890: jaroslav@1890: for (;;) { jaroslav@1890: Object k = s.readObject(); jaroslav@1890: if (k == null) jaroslav@1890: break; jaroslav@1890: Object v = s.readObject(); jaroslav@1890: if (v == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: K key = (K) k; jaroslav@1890: V val = (V) v; jaroslav@1890: int j = randomLevel(); jaroslav@1890: if (j > h.level) j = h.level + 1; jaroslav@1890: Node z = new Node(key, val, null); jaroslav@1890: basepred.next = z; jaroslav@1890: basepred = z; jaroslav@1890: if (j > 0) { jaroslav@1890: Index idx = null; jaroslav@1890: for (int i = 1; i <= j; ++i) { jaroslav@1890: idx = new Index(z, idx, null); jaroslav@1890: if (i > h.level) jaroslav@1890: h = new HeadIndex(h.node, h, idx, i); jaroslav@1890: jaroslav@1890: if (i < preds.size()) { jaroslav@1890: preds.get(i).right = idx; jaroslav@1890: preds.set(i, idx); jaroslav@1890: } else jaroslav@1890: preds.add(idx); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: head = h; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ------ Map API methods ------ */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns true if this map contains a mapping for the specified jaroslav@1890: * key. jaroslav@1890: * jaroslav@1890: * @param key key whose presence in this map is to be tested jaroslav@1890: * @return true if this map contains a mapping for the specified key jaroslav@1890: * @throws ClassCastException if the specified key cannot be compared jaroslav@1890: * with the keys currently in the map jaroslav@1890: * @throws NullPointerException if the specified key is null jaroslav@1890: */ jaroslav@1890: public boolean containsKey(Object key) { jaroslav@1890: return doGet(key) != null; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns the value to which the specified key is mapped, jaroslav@1890: * or {@code null} if this map contains no mapping for the key. jaroslav@1890: * jaroslav@1890: *

More formally, if this map contains a mapping from a key jaroslav@1890: * {@code k} to a value {@code v} such that {@code key} compares jaroslav@1890: * equal to {@code k} according to the map's ordering, then this jaroslav@1890: * method returns {@code v}; otherwise it returns {@code null}. jaroslav@1890: * (There can be at most one such mapping.) jaroslav@1890: * jaroslav@1890: * @throws ClassCastException if the specified key cannot be compared jaroslav@1890: * with the keys currently in the map jaroslav@1890: * @throws NullPointerException if the specified key is null jaroslav@1890: */ jaroslav@1890: public V get(Object key) { jaroslav@1890: return doGet(key); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Associates the specified value with the specified key in this map. jaroslav@1890: * If the map previously contained a mapping for the key, the old jaroslav@1890: * value is replaced. jaroslav@1890: * jaroslav@1890: * @param key key with which the specified value is to be associated jaroslav@1890: * @param value value to be associated with the specified key jaroslav@1890: * @return the previous value associated with the specified key, or jaroslav@1890: * null if there was no mapping for the key jaroslav@1890: * @throws ClassCastException if the specified key cannot be compared jaroslav@1890: * with the keys currently in the map jaroslav@1890: * @throws NullPointerException if the specified key or value is null jaroslav@1890: */ jaroslav@1890: public V put(K key, V value) { jaroslav@1890: if (value == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: return doPut(key, value, false); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Removes the mapping for the specified key from this map if present. jaroslav@1890: * jaroslav@1890: * @param key key for which mapping should be removed jaroslav@1890: * @return the previous value associated with the specified key, or jaroslav@1890: * null if there was no mapping for the key jaroslav@1890: * @throws ClassCastException if the specified key cannot be compared jaroslav@1890: * with the keys currently in the map jaroslav@1890: * @throws NullPointerException if the specified key is null jaroslav@1890: */ jaroslav@1890: public V remove(Object key) { jaroslav@1890: return doRemove(key, null); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns true if this map maps one or more keys to the jaroslav@1890: * specified value. This operation requires time linear in the jaroslav@1890: * map size. Additionally, it is possible for the map to change jaroslav@1890: * during execution of this method, in which case the returned jaroslav@1890: * result may be inaccurate. jaroslav@1890: * jaroslav@1890: * @param value value whose presence in this map is to be tested jaroslav@1890: * @return true if a mapping to value exists; jaroslav@1890: * false otherwise jaroslav@1890: * @throws NullPointerException if the specified value is null jaroslav@1890: */ jaroslav@1890: public boolean containsValue(Object value) { jaroslav@1890: if (value == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: for (Node n = findFirst(); n != null; n = n.next) { jaroslav@1890: V v = n.getValidValue(); jaroslav@1890: if (v != null && value.equals(v)) jaroslav@1890: return true; jaroslav@1890: } jaroslav@1890: return false; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns the number of key-value mappings in this map. If this map jaroslav@1890: * contains more than Integer.MAX_VALUE elements, it jaroslav@1890: * returns Integer.MAX_VALUE. jaroslav@1890: * jaroslav@1890: *

Beware that, unlike in most collections, this method is jaroslav@1890: * NOT a constant-time operation. Because of the jaroslav@1890: * asynchronous nature of these maps, determining the current jaroslav@1890: * number of elements requires traversing them all to count them. jaroslav@1890: * Additionally, it is possible for the size to change during jaroslav@1890: * execution of this method, in which case the returned result jaroslav@1890: * will be inaccurate. Thus, this method is typically not very jaroslav@1890: * useful in concurrent applications. jaroslav@1890: * jaroslav@1890: * @return the number of elements in this map jaroslav@1890: */ jaroslav@1890: public int size() { jaroslav@1890: long count = 0; jaroslav@1890: for (Node n = findFirst(); n != null; n = n.next) { jaroslav@1890: if (n.getValidValue() != null) jaroslav@1890: ++count; jaroslav@1890: } jaroslav@1890: return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) count; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns true if this map contains no key-value mappings. jaroslav@1890: * @return true if this map contains no key-value mappings jaroslav@1890: */ jaroslav@1890: public boolean isEmpty() { jaroslav@1890: return findFirst() == null; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Removes all of the mappings from this map. jaroslav@1890: */ jaroslav@1890: public void clear() { jaroslav@1890: initialize(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- View methods -------------- */ jaroslav@1890: jaroslav@1890: /* jaroslav@1890: * Note: Lazy initialization works for views because view classes jaroslav@1890: * are stateless/immutable so it doesn't matter wrt correctness if jaroslav@1890: * more than one is created (which will only rarely happen). Even jaroslav@1890: * so, the following idiom conservatively ensures that the method jaroslav@1890: * returns the one it created if it does so, not one created by jaroslav@1890: * another racing thread. jaroslav@1890: */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns a {@link NavigableSet} view of the keys contained in this map. jaroslav@1890: * The set's iterator returns the keys in ascending order. jaroslav@1890: * The set is backed by the map, so changes to the map are jaroslav@1890: * reflected in the set, and vice-versa. The set supports element jaroslav@1890: * removal, which removes the corresponding mapping from the map, jaroslav@1890: * via the {@code Iterator.remove}, {@code Set.remove}, jaroslav@1890: * {@code removeAll}, {@code retainAll}, and {@code clear} jaroslav@1890: * operations. It does not support the {@code add} or {@code addAll} jaroslav@1890: * operations. jaroslav@1890: * jaroslav@1890: *

The view's {@code iterator} is a "weakly consistent" iterator jaroslav@1890: * that will never throw {@link ConcurrentModificationException}, jaroslav@1890: * and guarantees to traverse elements as they existed upon jaroslav@1890: * construction of the iterator, and may (but is not guaranteed to) jaroslav@1890: * reflect any modifications subsequent to construction. jaroslav@1890: * jaroslav@1890: *

This method is equivalent to method {@code navigableKeySet}. jaroslav@1890: * jaroslav@1890: * @return a navigable set view of the keys in this map jaroslav@1890: */ jaroslav@1890: public NavigableSet keySet() { jaroslav@1890: KeySet ks = keySet; jaroslav@1890: return (ks != null) ? ks : (keySet = new KeySet(this)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public NavigableSet navigableKeySet() { jaroslav@1890: KeySet ks = keySet; jaroslav@1890: return (ks != null) ? ks : (keySet = new KeySet(this)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns a {@link Collection} view of the values contained in this map. jaroslav@1890: * The collection's iterator returns the values in ascending order jaroslav@1890: * of the corresponding keys. jaroslav@1890: * The collection is backed by the map, so changes to the map are jaroslav@1890: * reflected in the collection, and vice-versa. The collection jaroslav@1890: * supports element removal, which removes the corresponding jaroslav@1890: * mapping from the map, via the Iterator.remove, jaroslav@1890: * Collection.remove, removeAll, jaroslav@1890: * retainAll and clear operations. It does not jaroslav@1890: * support the add or addAll operations. jaroslav@1890: * jaroslav@1890: *

The view's iterator is a "weakly consistent" iterator jaroslav@1890: * that will never throw {@link ConcurrentModificationException}, jaroslav@1890: * and guarantees to traverse elements as they existed upon jaroslav@1890: * construction of the iterator, and may (but is not guaranteed to) jaroslav@1890: * reflect any modifications subsequent to construction. jaroslav@1890: */ jaroslav@1890: public Collection values() { jaroslav@1890: Values vs = values; jaroslav@1890: return (vs != null) ? vs : (values = new Values(this)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns a {@link Set} view of the mappings contained in this map. jaroslav@1890: * The set's iterator returns the entries in ascending key order. jaroslav@1890: * The set is backed by the map, so changes to the map are jaroslav@1890: * reflected in the set, and vice-versa. The set supports element jaroslav@1890: * removal, which removes the corresponding mapping from the map, jaroslav@1890: * via the Iterator.remove, Set.remove, jaroslav@1890: * removeAll, retainAll and clear jaroslav@1890: * operations. It does not support the add or jaroslav@1890: * addAll operations. jaroslav@1890: * jaroslav@1890: *

The view's iterator is a "weakly consistent" iterator jaroslav@1890: * that will never throw {@link ConcurrentModificationException}, jaroslav@1890: * and guarantees to traverse elements as they existed upon jaroslav@1890: * construction of the iterator, and may (but is not guaranteed to) jaroslav@1890: * reflect any modifications subsequent to construction. jaroslav@1890: * jaroslav@1890: *

The Map.Entry elements returned by jaroslav@1890: * iterator.next() do not support the jaroslav@1890: * setValue operation. jaroslav@1890: * jaroslav@1890: * @return a set view of the mappings contained in this map, jaroslav@1890: * sorted in ascending key order jaroslav@1890: */ jaroslav@1890: public Set> entrySet() { jaroslav@1890: EntrySet es = entrySet; jaroslav@1890: return (es != null) ? es : (entrySet = new EntrySet(this)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public ConcurrentNavigableMap descendingMap() { jaroslav@1890: ConcurrentNavigableMap dm = descendingMap; jaroslav@1890: return (dm != null) ? dm : (descendingMap = new SubMap jaroslav@1890: (this, null, false, null, false, true)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public NavigableSet descendingKeySet() { jaroslav@1890: return descendingMap().navigableKeySet(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- AbstractMap Overrides -------------- */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Compares the specified object with this map for equality. jaroslav@1890: * Returns true if the given object is also a map and the jaroslav@1890: * two maps represent the same mappings. More formally, two maps jaroslav@1890: * m1 and m2 represent the same mappings if jaroslav@1890: * m1.entrySet().equals(m2.entrySet()). This jaroslav@1890: * operation may return misleading results if either map is jaroslav@1890: * concurrently modified during execution of this method. jaroslav@1890: * jaroslav@1890: * @param o object to be compared for equality with this map jaroslav@1890: * @return true if the specified object is equal to this map jaroslav@1890: */ jaroslav@1890: public boolean equals(Object o) { jaroslav@1890: if (o == this) jaroslav@1890: return true; jaroslav@1890: if (!(o instanceof Map)) jaroslav@1890: return false; jaroslav@1890: Map m = (Map) o; jaroslav@1890: try { jaroslav@1890: for (Map.Entry e : this.entrySet()) jaroslav@1890: if (! e.getValue().equals(m.get(e.getKey()))) jaroslav@1890: return false; jaroslav@1890: for (Map.Entry e : m.entrySet()) { jaroslav@1890: Object k = e.getKey(); jaroslav@1890: Object v = e.getValue(); jaroslav@1890: if (k == null || v == null || !v.equals(get(k))) jaroslav@1890: return false; jaroslav@1890: } jaroslav@1890: return true; jaroslav@1890: } catch (ClassCastException unused) { jaroslav@1890: return false; jaroslav@1890: } catch (NullPointerException unused) { jaroslav@1890: return false; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ------ ConcurrentMap API methods ------ */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * {@inheritDoc} jaroslav@1890: * jaroslav@1890: * @return the previous value associated with the specified key, jaroslav@1890: * or null if there was no mapping for the key jaroslav@1890: * @throws ClassCastException if the specified key cannot be compared jaroslav@1890: * with the keys currently in the map jaroslav@1890: * @throws NullPointerException if the specified key or value is null jaroslav@1890: */ jaroslav@1890: public V putIfAbsent(K key, V value) { jaroslav@1890: if (value == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: return doPut(key, value, true); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * {@inheritDoc} jaroslav@1890: * jaroslav@1890: * @throws ClassCastException if the specified key cannot be compared jaroslav@1890: * with the keys currently in the map jaroslav@1890: * @throws NullPointerException if the specified key is null jaroslav@1890: */ jaroslav@1890: public boolean remove(Object key, Object value) { jaroslav@1890: if (key == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: if (value == null) jaroslav@1890: return false; jaroslav@1890: return doRemove(key, value) != null; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * {@inheritDoc} jaroslav@1890: * jaroslav@1890: * @throws ClassCastException if the specified key cannot be compared jaroslav@1890: * with the keys currently in the map jaroslav@1890: * @throws NullPointerException if any of the arguments are null jaroslav@1890: */ jaroslav@1890: public boolean replace(K key, V oldValue, V newValue) { jaroslav@1890: if (oldValue == null || newValue == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: Comparable k = comparable(key); jaroslav@1890: for (;;) { jaroslav@1890: Node n = findNode(k); jaroslav@1890: if (n == null) jaroslav@1890: return false; jaroslav@1890: Object v = n.value; jaroslav@1890: if (v != null) { jaroslav@1890: if (!oldValue.equals(v)) jaroslav@1890: return false; jaroslav@1890: if (n.casValue(v, newValue)) jaroslav@1890: return true; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * {@inheritDoc} jaroslav@1890: * jaroslav@1890: * @return the previous value associated with the specified key, jaroslav@1890: * or null if there was no mapping for the key jaroslav@1890: * @throws ClassCastException if the specified key cannot be compared jaroslav@1890: * with the keys currently in the map jaroslav@1890: * @throws NullPointerException if the specified key or value is null jaroslav@1890: */ jaroslav@1890: public V replace(K key, V value) { jaroslav@1890: if (value == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: Comparable k = comparable(key); jaroslav@1890: for (;;) { jaroslav@1890: Node n = findNode(k); jaroslav@1890: if (n == null) jaroslav@1890: return null; jaroslav@1890: Object v = n.value; jaroslav@1890: if (v != null && n.casValue(v, value)) jaroslav@1890: return (V)v; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ------ SortedMap API methods ------ */ jaroslav@1890: jaroslav@1890: public Comparator comparator() { jaroslav@1890: return comparator; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * @throws NoSuchElementException {@inheritDoc} jaroslav@1890: */ jaroslav@1890: public K firstKey() { jaroslav@1890: Node n = findFirst(); jaroslav@1890: if (n == null) jaroslav@1890: throw new NoSuchElementException(); jaroslav@1890: return n.key; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * @throws NoSuchElementException {@inheritDoc} jaroslav@1890: */ jaroslav@1890: public K lastKey() { jaroslav@1890: Node n = findLast(); jaroslav@1890: if (n == null) jaroslav@1890: throw new NoSuchElementException(); jaroslav@1890: return n.key; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * @throws ClassCastException {@inheritDoc} jaroslav@1890: * @throws NullPointerException if {@code fromKey} or {@code toKey} is null jaroslav@1890: * @throws IllegalArgumentException {@inheritDoc} jaroslav@1890: */ jaroslav@1890: public ConcurrentNavigableMap subMap(K fromKey, jaroslav@1890: boolean fromInclusive, jaroslav@1890: K toKey, jaroslav@1890: boolean toInclusive) { jaroslav@1890: if (fromKey == null || toKey == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: return new SubMap jaroslav@1890: (this, fromKey, fromInclusive, toKey, toInclusive, false); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * @throws ClassCastException {@inheritDoc} jaroslav@1890: * @throws NullPointerException if {@code toKey} is null jaroslav@1890: * @throws IllegalArgumentException {@inheritDoc} jaroslav@1890: */ jaroslav@1890: public ConcurrentNavigableMap headMap(K toKey, jaroslav@1890: boolean inclusive) { jaroslav@1890: if (toKey == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: return new SubMap jaroslav@1890: (this, null, false, toKey, inclusive, false); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * @throws ClassCastException {@inheritDoc} jaroslav@1890: * @throws NullPointerException if {@code fromKey} is null jaroslav@1890: * @throws IllegalArgumentException {@inheritDoc} jaroslav@1890: */ jaroslav@1890: public ConcurrentNavigableMap tailMap(K fromKey, jaroslav@1890: boolean inclusive) { jaroslav@1890: if (fromKey == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: return new SubMap jaroslav@1890: (this, fromKey, inclusive, null, false, false); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * @throws ClassCastException {@inheritDoc} jaroslav@1890: * @throws NullPointerException if {@code fromKey} or {@code toKey} is null jaroslav@1890: * @throws IllegalArgumentException {@inheritDoc} jaroslav@1890: */ jaroslav@1890: public ConcurrentNavigableMap subMap(K fromKey, K toKey) { jaroslav@1890: return subMap(fromKey, true, toKey, false); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * @throws ClassCastException {@inheritDoc} jaroslav@1890: * @throws NullPointerException if {@code toKey} is null jaroslav@1890: * @throws IllegalArgumentException {@inheritDoc} jaroslav@1890: */ jaroslav@1890: public ConcurrentNavigableMap headMap(K toKey) { jaroslav@1890: return headMap(toKey, false); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * @throws ClassCastException {@inheritDoc} jaroslav@1890: * @throws NullPointerException if {@code fromKey} is null jaroslav@1890: * @throws IllegalArgumentException {@inheritDoc} jaroslav@1890: */ jaroslav@1890: public ConcurrentNavigableMap tailMap(K fromKey) { jaroslav@1890: return tailMap(fromKey, true); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- Relational operations -------------- */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns a key-value mapping associated with the greatest key jaroslav@1890: * strictly less than the given key, or null if there is jaroslav@1890: * no such key. The returned entry does not support the jaroslav@1890: * Entry.setValue method. jaroslav@1890: * jaroslav@1890: * @throws ClassCastException {@inheritDoc} jaroslav@1890: * @throws NullPointerException if the specified key is null jaroslav@1890: */ jaroslav@1890: public Map.Entry lowerEntry(K key) { jaroslav@1890: return getNear(key, LT); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * @throws ClassCastException {@inheritDoc} jaroslav@1890: * @throws NullPointerException if the specified key is null jaroslav@1890: */ jaroslav@1890: public K lowerKey(K key) { jaroslav@1890: Node n = findNear(key, LT); jaroslav@1890: return (n == null) ? null : n.key; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns a key-value mapping associated with the greatest key jaroslav@1890: * less than or equal to the given key, or null if there jaroslav@1890: * is no such key. The returned entry does not support jaroslav@1890: * the Entry.setValue method. jaroslav@1890: * jaroslav@1890: * @param key the key jaroslav@1890: * @throws ClassCastException {@inheritDoc} jaroslav@1890: * @throws NullPointerException if the specified key is null jaroslav@1890: */ jaroslav@1890: public Map.Entry floorEntry(K key) { jaroslav@1890: return getNear(key, LT|EQ); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * @param key the key jaroslav@1890: * @throws ClassCastException {@inheritDoc} jaroslav@1890: * @throws NullPointerException if the specified key is null jaroslav@1890: */ jaroslav@1890: public K floorKey(K key) { jaroslav@1890: Node n = findNear(key, LT|EQ); jaroslav@1890: return (n == null) ? null : n.key; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns a key-value mapping associated with the least key jaroslav@1890: * greater than or equal to the given key, or null if jaroslav@1890: * there is no such entry. The returned entry does not jaroslav@1890: * support the Entry.setValue method. jaroslav@1890: * jaroslav@1890: * @throws ClassCastException {@inheritDoc} jaroslav@1890: * @throws NullPointerException if the specified key is null jaroslav@1890: */ jaroslav@1890: public Map.Entry ceilingEntry(K key) { jaroslav@1890: return getNear(key, GT|EQ); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * @throws ClassCastException {@inheritDoc} jaroslav@1890: * @throws NullPointerException if the specified key is null jaroslav@1890: */ jaroslav@1890: public K ceilingKey(K key) { jaroslav@1890: Node n = findNear(key, GT|EQ); jaroslav@1890: return (n == null) ? null : n.key; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns a key-value mapping associated with the least key jaroslav@1890: * strictly greater than the given key, or null if there jaroslav@1890: * is no such key. The returned entry does not support jaroslav@1890: * the Entry.setValue method. jaroslav@1890: * jaroslav@1890: * @param key the key jaroslav@1890: * @throws ClassCastException {@inheritDoc} jaroslav@1890: * @throws NullPointerException if the specified key is null jaroslav@1890: */ jaroslav@1890: public Map.Entry higherEntry(K key) { jaroslav@1890: return getNear(key, GT); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * @param key the key jaroslav@1890: * @throws ClassCastException {@inheritDoc} jaroslav@1890: * @throws NullPointerException if the specified key is null jaroslav@1890: */ jaroslav@1890: public K higherKey(K key) { jaroslav@1890: Node n = findNear(key, GT); jaroslav@1890: return (n == null) ? null : n.key; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns a key-value mapping associated with the least jaroslav@1890: * key in this map, or null if the map is empty. jaroslav@1890: * The returned entry does not support jaroslav@1890: * the Entry.setValue method. jaroslav@1890: */ jaroslav@1890: public Map.Entry firstEntry() { jaroslav@1890: for (;;) { jaroslav@1890: Node n = findFirst(); jaroslav@1890: if (n == null) jaroslav@1890: return null; jaroslav@1890: AbstractMap.SimpleImmutableEntry e = n.createSnapshot(); jaroslav@1890: if (e != null) jaroslav@1890: return e; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns a key-value mapping associated with the greatest jaroslav@1890: * key in this map, or null if the map is empty. jaroslav@1890: * The returned entry does not support jaroslav@1890: * the Entry.setValue method. jaroslav@1890: */ jaroslav@1890: public Map.Entry lastEntry() { jaroslav@1890: for (;;) { jaroslav@1890: Node n = findLast(); jaroslav@1890: if (n == null) jaroslav@1890: return null; jaroslav@1890: AbstractMap.SimpleImmutableEntry e = n.createSnapshot(); jaroslav@1890: if (e != null) jaroslav@1890: return e; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Removes and returns a key-value mapping associated with jaroslav@1890: * the least key in this map, or null if the map is empty. jaroslav@1890: * The returned entry does not support jaroslav@1890: * the Entry.setValue method. jaroslav@1890: */ jaroslav@1890: public Map.Entry pollFirstEntry() { jaroslav@1890: return doRemoveFirstEntry(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Removes and returns a key-value mapping associated with jaroslav@1890: * the greatest key in this map, or null if the map is empty. jaroslav@1890: * The returned entry does not support jaroslav@1890: * the Entry.setValue method. jaroslav@1890: */ jaroslav@1890: public Map.Entry pollLastEntry() { jaroslav@1890: return doRemoveLastEntry(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: jaroslav@1890: /* ---------------- Iterators -------------- */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Base of iterator classes: jaroslav@1890: */ jaroslav@1890: abstract class Iter implements Iterator { jaroslav@1890: /** the last node returned by next() */ jaroslav@1890: Node lastReturned; jaroslav@1890: /** the next node to return from next(); */ jaroslav@1890: Node next; jaroslav@1890: /** Cache of next value field to maintain weak consistency */ jaroslav@1890: V nextValue; jaroslav@1890: jaroslav@1890: /** Initializes ascending iterator for entire range. */ jaroslav@1890: Iter() { jaroslav@1890: for (;;) { jaroslav@1890: next = findFirst(); jaroslav@1890: if (next == null) jaroslav@1890: break; jaroslav@1890: Object x = next.value; jaroslav@1890: if (x != null && x != next) { jaroslav@1890: nextValue = (V) x; jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: public final boolean hasNext() { jaroslav@1890: return next != null; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** Advances next to higher entry. */ jaroslav@1890: final void advance() { jaroslav@1890: if (next == null) jaroslav@1890: throw new NoSuchElementException(); jaroslav@1890: lastReturned = next; jaroslav@1890: for (;;) { jaroslav@1890: next = next.next; jaroslav@1890: if (next == null) jaroslav@1890: break; jaroslav@1890: Object x = next.value; jaroslav@1890: if (x != null && x != next) { jaroslav@1890: nextValue = (V) x; jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: public void remove() { jaroslav@1890: Node l = lastReturned; jaroslav@1890: if (l == null) jaroslav@1890: throw new IllegalStateException(); jaroslav@1890: // It would not be worth all of the overhead to directly jaroslav@1890: // unlink from here. Using remove is fast enough. jaroslav@1890: ConcurrentSkipListMap.this.remove(l.key); jaroslav@1890: lastReturned = null; jaroslav@1890: } jaroslav@1890: jaroslav@1890: } jaroslav@1890: jaroslav@1890: final class ValueIterator extends Iter { jaroslav@1890: public V next() { jaroslav@1890: V v = nextValue; jaroslav@1890: advance(); jaroslav@1890: return v; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: final class KeyIterator extends Iter { jaroslav@1890: public K next() { jaroslav@1890: Node n = next; jaroslav@1890: advance(); jaroslav@1890: return n.key; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: final class EntryIterator extends Iter> { jaroslav@1890: public Map.Entry next() { jaroslav@1890: Node n = next; jaroslav@1890: V v = nextValue; jaroslav@1890: advance(); jaroslav@1890: return new AbstractMap.SimpleImmutableEntry(n.key, v); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: // Factory methods for iterators needed by ConcurrentSkipListSet etc jaroslav@1890: jaroslav@1890: Iterator keyIterator() { jaroslav@1890: return new KeyIterator(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: Iterator valueIterator() { jaroslav@1890: return new ValueIterator(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: Iterator> entryIterator() { jaroslav@1890: return new EntryIterator(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- View Classes -------------- */ jaroslav@1890: jaroslav@1890: /* jaroslav@1890: * View classes are static, delegating to a ConcurrentNavigableMap jaroslav@1890: * to allow use by SubMaps, which outweighs the ugliness of jaroslav@1890: * needing type-tests for Iterator methods. jaroslav@1890: */ jaroslav@1890: jaroslav@1890: static final List toList(Collection c) { jaroslav@1890: // Using size() here would be a pessimization. jaroslav@1890: List list = new ArrayList(); jaroslav@1890: for (E e : c) jaroslav@1890: list.add(e); jaroslav@1890: return list; jaroslav@1890: } jaroslav@1890: jaroslav@1890: static final class KeySet jaroslav@1890: extends AbstractSet implements NavigableSet { jaroslav@1890: private final ConcurrentNavigableMap m; jaroslav@1890: KeySet(ConcurrentNavigableMap map) { m = map; } jaroslav@1890: public int size() { return m.size(); } jaroslav@1890: public boolean isEmpty() { return m.isEmpty(); } jaroslav@1890: public boolean contains(Object o) { return m.containsKey(o); } jaroslav@1890: public boolean remove(Object o) { return m.remove(o) != null; } jaroslav@1890: public void clear() { m.clear(); } jaroslav@1890: public E lower(E e) { return m.lowerKey(e); } jaroslav@1890: public E floor(E e) { return m.floorKey(e); } jaroslav@1890: public E ceiling(E e) { return m.ceilingKey(e); } jaroslav@1890: public E higher(E e) { return m.higherKey(e); } jaroslav@1890: public Comparator comparator() { return m.comparator(); } jaroslav@1890: public E first() { return m.firstKey(); } jaroslav@1890: public E last() { return m.lastKey(); } jaroslav@1890: public E pollFirst() { jaroslav@1890: Map.Entry e = m.pollFirstEntry(); jaroslav@1890: return (e == null) ? null : e.getKey(); jaroslav@1890: } jaroslav@1890: public E pollLast() { jaroslav@1890: Map.Entry e = m.pollLastEntry(); jaroslav@1890: return (e == null) ? null : e.getKey(); jaroslav@1890: } jaroslav@1890: public Iterator iterator() { jaroslav@1890: if (m instanceof ConcurrentSkipListMap) jaroslav@1890: return ((ConcurrentSkipListMap)m).keyIterator(); jaroslav@1890: else jaroslav@1890: return ((ConcurrentSkipListMap.SubMap)m).keyIterator(); jaroslav@1890: } jaroslav@1890: public boolean equals(Object o) { jaroslav@1890: if (o == this) jaroslav@1890: return true; jaroslav@1890: if (!(o instanceof Set)) jaroslav@1890: return false; jaroslav@1890: Collection c = (Collection) o; jaroslav@1890: try { jaroslav@1890: return containsAll(c) && c.containsAll(this); jaroslav@1890: } catch (ClassCastException unused) { jaroslav@1890: return false; jaroslav@1890: } catch (NullPointerException unused) { jaroslav@1890: return false; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: public Object[] toArray() { return toList(this).toArray(); } jaroslav@1890: public T[] toArray(T[] a) { return toList(this).toArray(a); } jaroslav@1890: public Iterator descendingIterator() { jaroslav@1890: return descendingSet().iterator(); jaroslav@1890: } jaroslav@1890: public NavigableSet subSet(E fromElement, jaroslav@1890: boolean fromInclusive, jaroslav@1890: E toElement, jaroslav@1890: boolean toInclusive) { jaroslav@1890: return new KeySet(m.subMap(fromElement, fromInclusive, jaroslav@1890: toElement, toInclusive)); jaroslav@1890: } jaroslav@1890: public NavigableSet headSet(E toElement, boolean inclusive) { jaroslav@1890: return new KeySet(m.headMap(toElement, inclusive)); jaroslav@1890: } jaroslav@1890: public NavigableSet tailSet(E fromElement, boolean inclusive) { jaroslav@1890: return new KeySet(m.tailMap(fromElement, inclusive)); jaroslav@1890: } jaroslav@1890: public NavigableSet subSet(E fromElement, E toElement) { jaroslav@1890: return subSet(fromElement, true, toElement, false); jaroslav@1890: } jaroslav@1890: public NavigableSet headSet(E toElement) { jaroslav@1890: return headSet(toElement, false); jaroslav@1890: } jaroslav@1890: public NavigableSet tailSet(E fromElement) { jaroslav@1890: return tailSet(fromElement, true); jaroslav@1890: } jaroslav@1890: public NavigableSet descendingSet() { jaroslav@1890: return new KeySet(m.descendingMap()); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: static final class Values extends AbstractCollection { jaroslav@1890: private final ConcurrentNavigableMap m; jaroslav@1890: Values(ConcurrentNavigableMap map) { jaroslav@1890: m = map; jaroslav@1890: } jaroslav@1890: public Iterator iterator() { jaroslav@1890: if (m instanceof ConcurrentSkipListMap) jaroslav@1890: return ((ConcurrentSkipListMap)m).valueIterator(); jaroslav@1890: else jaroslav@1890: return ((SubMap)m).valueIterator(); jaroslav@1890: } jaroslav@1890: public boolean isEmpty() { jaroslav@1890: return m.isEmpty(); jaroslav@1890: } jaroslav@1890: public int size() { jaroslav@1890: return m.size(); jaroslav@1890: } jaroslav@1890: public boolean contains(Object o) { jaroslav@1890: return m.containsValue(o); jaroslav@1890: } jaroslav@1890: public void clear() { jaroslav@1890: m.clear(); jaroslav@1890: } jaroslav@1890: public Object[] toArray() { return toList(this).toArray(); } jaroslav@1890: public T[] toArray(T[] a) { return toList(this).toArray(a); } jaroslav@1890: } jaroslav@1890: jaroslav@1890: static final class EntrySet extends AbstractSet> { jaroslav@1890: private final ConcurrentNavigableMap m; jaroslav@1890: EntrySet(ConcurrentNavigableMap map) { jaroslav@1890: m = map; jaroslav@1890: } jaroslav@1890: jaroslav@1890: public Iterator> iterator() { jaroslav@1890: if (m instanceof ConcurrentSkipListMap) jaroslav@1890: return ((ConcurrentSkipListMap)m).entryIterator(); jaroslav@1890: else jaroslav@1890: return ((SubMap)m).entryIterator(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public boolean contains(Object o) { jaroslav@1890: if (!(o instanceof Map.Entry)) jaroslav@1890: return false; jaroslav@1890: Map.Entry e = (Map.Entry)o; jaroslav@1890: V1 v = m.get(e.getKey()); jaroslav@1890: return v != null && v.equals(e.getValue()); jaroslav@1890: } jaroslav@1890: public boolean remove(Object o) { jaroslav@1890: if (!(o instanceof Map.Entry)) jaroslav@1890: return false; jaroslav@1890: Map.Entry e = (Map.Entry)o; jaroslav@1890: return m.remove(e.getKey(), jaroslav@1890: e.getValue()); jaroslav@1890: } jaroslav@1890: public boolean isEmpty() { jaroslav@1890: return m.isEmpty(); jaroslav@1890: } jaroslav@1890: public int size() { jaroslav@1890: return m.size(); jaroslav@1890: } jaroslav@1890: public void clear() { jaroslav@1890: m.clear(); jaroslav@1890: } jaroslav@1890: public boolean equals(Object o) { jaroslav@1890: if (o == this) jaroslav@1890: return true; jaroslav@1890: if (!(o instanceof Set)) jaroslav@1890: return false; jaroslav@1890: Collection c = (Collection) o; jaroslav@1890: try { jaroslav@1890: return containsAll(c) && c.containsAll(this); jaroslav@1890: } catch (ClassCastException unused) { jaroslav@1890: return false; jaroslav@1890: } catch (NullPointerException unused) { jaroslav@1890: return false; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: public Object[] toArray() { return toList(this).toArray(); } jaroslav@1890: public T[] toArray(T[] a) { return toList(this).toArray(a); } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Submaps returned by {@link ConcurrentSkipListMap} submap operations jaroslav@1890: * represent a subrange of mappings of their underlying jaroslav@1890: * maps. Instances of this class support all methods of their jaroslav@1890: * underlying maps, differing in that mappings outside their range are jaroslav@1890: * ignored, and attempts to add mappings outside their ranges result jaroslav@1890: * in {@link IllegalArgumentException}. Instances of this class are jaroslav@1890: * constructed only using the subMap, headMap, and jaroslav@1890: * tailMap methods of their underlying maps. jaroslav@1890: * jaroslav@1890: * @serial include jaroslav@1890: */ jaroslav@1890: static final class SubMap extends AbstractMap jaroslav@1890: implements ConcurrentNavigableMap, Cloneable, jaroslav@1890: java.io.Serializable { jaroslav@1890: private static final long serialVersionUID = -7647078645895051609L; jaroslav@1890: jaroslav@1890: /** Underlying map */ jaroslav@1890: private final ConcurrentSkipListMap m; jaroslav@1890: /** lower bound key, or null if from start */ jaroslav@1890: private final K lo; jaroslav@1890: /** upper bound key, or null if to end */ jaroslav@1890: private final K hi; jaroslav@1890: /** inclusion flag for lo */ jaroslav@1890: private final boolean loInclusive; jaroslav@1890: /** inclusion flag for hi */ jaroslav@1890: private final boolean hiInclusive; jaroslav@1890: /** direction */ jaroslav@1890: private final boolean isDescending; jaroslav@1890: jaroslav@1890: // Lazily initialized view holders jaroslav@1890: private transient KeySet keySetView; jaroslav@1890: private transient Set> entrySetView; jaroslav@1890: private transient Collection valuesView; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Creates a new submap, initializing all fields jaroslav@1890: */ jaroslav@1890: SubMap(ConcurrentSkipListMap map, jaroslav@1890: K fromKey, boolean fromInclusive, jaroslav@1890: K toKey, boolean toInclusive, jaroslav@1890: boolean isDescending) { jaroslav@1890: if (fromKey != null && toKey != null && jaroslav@1890: map.compare(fromKey, toKey) > 0) jaroslav@1890: throw new IllegalArgumentException("inconsistent range"); jaroslav@1890: this.m = map; jaroslav@1890: this.lo = fromKey; jaroslav@1890: this.hi = toKey; jaroslav@1890: this.loInclusive = fromInclusive; jaroslav@1890: this.hiInclusive = toInclusive; jaroslav@1890: this.isDescending = isDescending; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- Utilities -------------- */ jaroslav@1890: jaroslav@1890: private boolean tooLow(K key) { jaroslav@1890: if (lo != null) { jaroslav@1890: int c = m.compare(key, lo); jaroslav@1890: if (c < 0 || (c == 0 && !loInclusive)) jaroslav@1890: return true; jaroslav@1890: } jaroslav@1890: return false; jaroslav@1890: } jaroslav@1890: jaroslav@1890: private boolean tooHigh(K key) { jaroslav@1890: if (hi != null) { jaroslav@1890: int c = m.compare(key, hi); jaroslav@1890: if (c > 0 || (c == 0 && !hiInclusive)) jaroslav@1890: return true; jaroslav@1890: } jaroslav@1890: return false; jaroslav@1890: } jaroslav@1890: jaroslav@1890: private boolean inBounds(K key) { jaroslav@1890: return !tooLow(key) && !tooHigh(key); jaroslav@1890: } jaroslav@1890: jaroslav@1890: private void checkKeyBounds(K key) throws IllegalArgumentException { jaroslav@1890: if (key == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: if (!inBounds(key)) jaroslav@1890: throw new IllegalArgumentException("key out of range"); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns true if node key is less than upper bound of range jaroslav@1890: */ jaroslav@1890: private boolean isBeforeEnd(ConcurrentSkipListMap.Node n) { jaroslav@1890: if (n == null) jaroslav@1890: return false; jaroslav@1890: if (hi == null) jaroslav@1890: return true; jaroslav@1890: K k = n.key; jaroslav@1890: if (k == null) // pass by markers and headers jaroslav@1890: return true; jaroslav@1890: int c = m.compare(k, hi); jaroslav@1890: if (c > 0 || (c == 0 && !hiInclusive)) jaroslav@1890: return false; jaroslav@1890: return true; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns lowest node. This node might not be in range, so jaroslav@1890: * most usages need to check bounds jaroslav@1890: */ jaroslav@1890: private ConcurrentSkipListMap.Node loNode() { jaroslav@1890: if (lo == null) jaroslav@1890: return m.findFirst(); jaroslav@1890: else if (loInclusive) jaroslav@1890: return m.findNear(lo, m.GT|m.EQ); jaroslav@1890: else jaroslav@1890: return m.findNear(lo, m.GT); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns highest node. This node might not be in range, so jaroslav@1890: * most usages need to check bounds jaroslav@1890: */ jaroslav@1890: private ConcurrentSkipListMap.Node hiNode() { jaroslav@1890: if (hi == null) jaroslav@1890: return m.findLast(); jaroslav@1890: else if (hiInclusive) jaroslav@1890: return m.findNear(hi, m.LT|m.EQ); jaroslav@1890: else jaroslav@1890: return m.findNear(hi, m.LT); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns lowest absolute key (ignoring directonality) jaroslav@1890: */ jaroslav@1890: private K lowestKey() { jaroslav@1890: ConcurrentSkipListMap.Node n = loNode(); jaroslav@1890: if (isBeforeEnd(n)) jaroslav@1890: return n.key; jaroslav@1890: else jaroslav@1890: throw new NoSuchElementException(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns highest absolute key (ignoring directonality) jaroslav@1890: */ jaroslav@1890: private K highestKey() { jaroslav@1890: ConcurrentSkipListMap.Node n = hiNode(); jaroslav@1890: if (n != null) { jaroslav@1890: K last = n.key; jaroslav@1890: if (inBounds(last)) jaroslav@1890: return last; jaroslav@1890: } jaroslav@1890: throw new NoSuchElementException(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: private Map.Entry lowestEntry() { jaroslav@1890: for (;;) { jaroslav@1890: ConcurrentSkipListMap.Node n = loNode(); jaroslav@1890: if (!isBeforeEnd(n)) jaroslav@1890: return null; jaroslav@1890: Map.Entry e = n.createSnapshot(); jaroslav@1890: if (e != null) jaroslav@1890: return e; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: private Map.Entry highestEntry() { jaroslav@1890: for (;;) { jaroslav@1890: ConcurrentSkipListMap.Node n = hiNode(); jaroslav@1890: if (n == null || !inBounds(n.key)) jaroslav@1890: return null; jaroslav@1890: Map.Entry e = n.createSnapshot(); jaroslav@1890: if (e != null) jaroslav@1890: return e; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: private Map.Entry removeLowest() { jaroslav@1890: for (;;) { jaroslav@1890: Node n = loNode(); jaroslav@1890: if (n == null) jaroslav@1890: return null; jaroslav@1890: K k = n.key; jaroslav@1890: if (!inBounds(k)) jaroslav@1890: return null; jaroslav@1890: V v = m.doRemove(k, null); jaroslav@1890: if (v != null) jaroslav@1890: return new AbstractMap.SimpleImmutableEntry(k, v); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: private Map.Entry removeHighest() { jaroslav@1890: for (;;) { jaroslav@1890: Node n = hiNode(); jaroslav@1890: if (n == null) jaroslav@1890: return null; jaroslav@1890: K k = n.key; jaroslav@1890: if (!inBounds(k)) jaroslav@1890: return null; jaroslav@1890: V v = m.doRemove(k, null); jaroslav@1890: if (v != null) jaroslav@1890: return new AbstractMap.SimpleImmutableEntry(k, v); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Submap version of ConcurrentSkipListMap.getNearEntry jaroslav@1890: */ jaroslav@1890: private Map.Entry getNearEntry(K key, int rel) { jaroslav@1890: if (isDescending) { // adjust relation for direction jaroslav@1890: if ((rel & m.LT) == 0) jaroslav@1890: rel |= m.LT; jaroslav@1890: else jaroslav@1890: rel &= ~m.LT; jaroslav@1890: } jaroslav@1890: if (tooLow(key)) jaroslav@1890: return ((rel & m.LT) != 0) ? null : lowestEntry(); jaroslav@1890: if (tooHigh(key)) jaroslav@1890: return ((rel & m.LT) != 0) ? highestEntry() : null; jaroslav@1890: for (;;) { jaroslav@1890: Node n = m.findNear(key, rel); jaroslav@1890: if (n == null || !inBounds(n.key)) jaroslav@1890: return null; jaroslav@1890: K k = n.key; jaroslav@1890: V v = n.getValidValue(); jaroslav@1890: if (v != null) jaroslav@1890: return new AbstractMap.SimpleImmutableEntry(k, v); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: // Almost the same as getNearEntry, except for keys jaroslav@1890: private K getNearKey(K key, int rel) { jaroslav@1890: if (isDescending) { // adjust relation for direction jaroslav@1890: if ((rel & m.LT) == 0) jaroslav@1890: rel |= m.LT; jaroslav@1890: else jaroslav@1890: rel &= ~m.LT; jaroslav@1890: } jaroslav@1890: if (tooLow(key)) { jaroslav@1890: if ((rel & m.LT) == 0) { jaroslav@1890: ConcurrentSkipListMap.Node n = loNode(); jaroslav@1890: if (isBeforeEnd(n)) jaroslav@1890: return n.key; jaroslav@1890: } jaroslav@1890: return null; jaroslav@1890: } jaroslav@1890: if (tooHigh(key)) { jaroslav@1890: if ((rel & m.LT) != 0) { jaroslav@1890: ConcurrentSkipListMap.Node n = hiNode(); jaroslav@1890: if (n != null) { jaroslav@1890: K last = n.key; jaroslav@1890: if (inBounds(last)) jaroslav@1890: return last; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: return null; jaroslav@1890: } jaroslav@1890: for (;;) { jaroslav@1890: Node n = m.findNear(key, rel); jaroslav@1890: if (n == null || !inBounds(n.key)) jaroslav@1890: return null; jaroslav@1890: K k = n.key; jaroslav@1890: V v = n.getValidValue(); jaroslav@1890: if (v != null) jaroslav@1890: return k; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- Map API methods -------------- */ jaroslav@1890: jaroslav@1890: public boolean containsKey(Object key) { jaroslav@1890: if (key == null) throw new NullPointerException(); jaroslav@1890: K k = (K)key; jaroslav@1890: return inBounds(k) && m.containsKey(k); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public V get(Object key) { jaroslav@1890: if (key == null) throw new NullPointerException(); jaroslav@1890: K k = (K)key; jaroslav@1890: return ((!inBounds(k)) ? null : m.get(k)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public V put(K key, V value) { jaroslav@1890: checkKeyBounds(key); jaroslav@1890: return m.put(key, value); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public V remove(Object key) { jaroslav@1890: K k = (K)key; jaroslav@1890: return (!inBounds(k)) ? null : m.remove(k); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public int size() { jaroslav@1890: long count = 0; jaroslav@1890: for (ConcurrentSkipListMap.Node n = loNode(); jaroslav@1890: isBeforeEnd(n); jaroslav@1890: n = n.next) { jaroslav@1890: if (n.getValidValue() != null) jaroslav@1890: ++count; jaroslav@1890: } jaroslav@1890: return count >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)count; jaroslav@1890: } jaroslav@1890: jaroslav@1890: public boolean isEmpty() { jaroslav@1890: return !isBeforeEnd(loNode()); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public boolean containsValue(Object value) { jaroslav@1890: if (value == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: for (ConcurrentSkipListMap.Node n = loNode(); jaroslav@1890: isBeforeEnd(n); jaroslav@1890: n = n.next) { jaroslav@1890: V v = n.getValidValue(); jaroslav@1890: if (v != null && value.equals(v)) jaroslav@1890: return true; jaroslav@1890: } jaroslav@1890: return false; jaroslav@1890: } jaroslav@1890: jaroslav@1890: public void clear() { jaroslav@1890: for (ConcurrentSkipListMap.Node n = loNode(); jaroslav@1890: isBeforeEnd(n); jaroslav@1890: n = n.next) { jaroslav@1890: if (n.getValidValue() != null) jaroslav@1890: m.remove(n.key); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- ConcurrentMap API methods -------------- */ jaroslav@1890: jaroslav@1890: public V putIfAbsent(K key, V value) { jaroslav@1890: checkKeyBounds(key); jaroslav@1890: return m.putIfAbsent(key, value); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public boolean remove(Object key, Object value) { jaroslav@1890: K k = (K)key; jaroslav@1890: return inBounds(k) && m.remove(k, value); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public boolean replace(K key, V oldValue, V newValue) { jaroslav@1890: checkKeyBounds(key); jaroslav@1890: return m.replace(key, oldValue, newValue); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public V replace(K key, V value) { jaroslav@1890: checkKeyBounds(key); jaroslav@1890: return m.replace(key, value); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- SortedMap API methods -------------- */ jaroslav@1890: jaroslav@1890: public Comparator comparator() { jaroslav@1890: Comparator cmp = m.comparator(); jaroslav@1890: if (isDescending) jaroslav@1890: return Collections.reverseOrder(cmp); jaroslav@1890: else jaroslav@1890: return cmp; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Utility to create submaps, where given bounds override jaroslav@1890: * unbounded(null) ones and/or are checked against bounded ones. jaroslav@1890: */ jaroslav@1890: private SubMap newSubMap(K fromKey, jaroslav@1890: boolean fromInclusive, jaroslav@1890: K toKey, jaroslav@1890: boolean toInclusive) { jaroslav@1890: if (isDescending) { // flip senses jaroslav@1890: K tk = fromKey; jaroslav@1890: fromKey = toKey; jaroslav@1890: toKey = tk; jaroslav@1890: boolean ti = fromInclusive; jaroslav@1890: fromInclusive = toInclusive; jaroslav@1890: toInclusive = ti; jaroslav@1890: } jaroslav@1890: if (lo != null) { jaroslav@1890: if (fromKey == null) { jaroslav@1890: fromKey = lo; jaroslav@1890: fromInclusive = loInclusive; jaroslav@1890: } jaroslav@1890: else { jaroslav@1890: int c = m.compare(fromKey, lo); jaroslav@1890: if (c < 0 || (c == 0 && !loInclusive && fromInclusive)) jaroslav@1890: throw new IllegalArgumentException("key out of range"); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: if (hi != null) { jaroslav@1890: if (toKey == null) { jaroslav@1890: toKey = hi; jaroslav@1890: toInclusive = hiInclusive; jaroslav@1890: } jaroslav@1890: else { jaroslav@1890: int c = m.compare(toKey, hi); jaroslav@1890: if (c > 0 || (c == 0 && !hiInclusive && toInclusive)) jaroslav@1890: throw new IllegalArgumentException("key out of range"); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: return new SubMap(m, fromKey, fromInclusive, jaroslav@1890: toKey, toInclusive, isDescending); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public SubMap subMap(K fromKey, jaroslav@1890: boolean fromInclusive, jaroslav@1890: K toKey, jaroslav@1890: boolean toInclusive) { jaroslav@1890: if (fromKey == null || toKey == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: return newSubMap(fromKey, fromInclusive, toKey, toInclusive); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public SubMap headMap(K toKey, jaroslav@1890: boolean inclusive) { jaroslav@1890: if (toKey == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: return newSubMap(null, false, toKey, inclusive); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public SubMap tailMap(K fromKey, jaroslav@1890: boolean inclusive) { jaroslav@1890: if (fromKey == null) jaroslav@1890: throw new NullPointerException(); jaroslav@1890: return newSubMap(fromKey, inclusive, null, false); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public SubMap subMap(K fromKey, K toKey) { jaroslav@1890: return subMap(fromKey, true, toKey, false); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public SubMap headMap(K toKey) { jaroslav@1890: return headMap(toKey, false); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public SubMap tailMap(K fromKey) { jaroslav@1890: return tailMap(fromKey, true); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public SubMap descendingMap() { jaroslav@1890: return new SubMap(m, lo, loInclusive, jaroslav@1890: hi, hiInclusive, !isDescending); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- Relational methods -------------- */ jaroslav@1890: jaroslav@1890: public Map.Entry ceilingEntry(K key) { jaroslav@1890: return getNearEntry(key, (m.GT|m.EQ)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public K ceilingKey(K key) { jaroslav@1890: return getNearKey(key, (m.GT|m.EQ)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public Map.Entry lowerEntry(K key) { jaroslav@1890: return getNearEntry(key, (m.LT)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public K lowerKey(K key) { jaroslav@1890: return getNearKey(key, (m.LT)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public Map.Entry floorEntry(K key) { jaroslav@1890: return getNearEntry(key, (m.LT|m.EQ)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public K floorKey(K key) { jaroslav@1890: return getNearKey(key, (m.LT|m.EQ)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public Map.Entry higherEntry(K key) { jaroslav@1890: return getNearEntry(key, (m.GT)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public K higherKey(K key) { jaroslav@1890: return getNearKey(key, (m.GT)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public K firstKey() { jaroslav@1890: return isDescending ? highestKey() : lowestKey(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public K lastKey() { jaroslav@1890: return isDescending ? lowestKey() : highestKey(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public Map.Entry firstEntry() { jaroslav@1890: return isDescending ? highestEntry() : lowestEntry(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public Map.Entry lastEntry() { jaroslav@1890: return isDescending ? lowestEntry() : highestEntry(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public Map.Entry pollFirstEntry() { jaroslav@1890: return isDescending ? removeHighest() : removeLowest(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public Map.Entry pollLastEntry() { jaroslav@1890: return isDescending ? removeLowest() : removeHighest(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* ---------------- Submap Views -------------- */ jaroslav@1890: jaroslav@1890: public NavigableSet keySet() { jaroslav@1890: KeySet ks = keySetView; jaroslav@1890: return (ks != null) ? ks : (keySetView = new KeySet(this)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public NavigableSet navigableKeySet() { jaroslav@1890: KeySet ks = keySetView; jaroslav@1890: return (ks != null) ? ks : (keySetView = new KeySet(this)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public Collection values() { jaroslav@1890: Collection vs = valuesView; jaroslav@1890: return (vs != null) ? vs : (valuesView = new Values(this)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public Set> entrySet() { jaroslav@1890: Set> es = entrySetView; jaroslav@1890: return (es != null) ? es : (entrySetView = new EntrySet(this)); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public NavigableSet descendingKeySet() { jaroslav@1890: return descendingMap().navigableKeySet(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: Iterator keyIterator() { jaroslav@1890: return new SubMapKeyIterator(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: Iterator valueIterator() { jaroslav@1890: return new SubMapValueIterator(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: Iterator> entryIterator() { jaroslav@1890: return new SubMapEntryIterator(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Variant of main Iter class to traverse through submaps. jaroslav@1890: */ jaroslav@1890: abstract class SubMapIter implements Iterator { jaroslav@1890: /** the last node returned by next() */ jaroslav@1890: Node lastReturned; jaroslav@1890: /** the next node to return from next(); */ jaroslav@1890: Node next; jaroslav@1890: /** Cache of next value field to maintain weak consistency */ jaroslav@1890: V nextValue; jaroslav@1890: jaroslav@1890: SubMapIter() { jaroslav@1890: for (;;) { jaroslav@1890: next = isDescending ? hiNode() : loNode(); jaroslav@1890: if (next == null) jaroslav@1890: break; jaroslav@1890: Object x = next.value; jaroslav@1890: if (x != null && x != next) { jaroslav@1890: if (! inBounds(next.key)) jaroslav@1890: next = null; jaroslav@1890: else jaroslav@1890: nextValue = (V) x; jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: public final boolean hasNext() { jaroslav@1890: return next != null; jaroslav@1890: } jaroslav@1890: jaroslav@1890: final void advance() { jaroslav@1890: if (next == null) jaroslav@1890: throw new NoSuchElementException(); jaroslav@1890: lastReturned = next; jaroslav@1890: if (isDescending) jaroslav@1890: descend(); jaroslav@1890: else jaroslav@1890: ascend(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: private void ascend() { jaroslav@1890: for (;;) { jaroslav@1890: next = next.next; jaroslav@1890: if (next == null) jaroslav@1890: break; jaroslav@1890: Object x = next.value; jaroslav@1890: if (x != null && x != next) { jaroslav@1890: if (tooHigh(next.key)) jaroslav@1890: next = null; jaroslav@1890: else jaroslav@1890: nextValue = (V) x; jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: private void descend() { jaroslav@1890: for (;;) { jaroslav@1890: next = m.findNear(lastReturned.key, LT); jaroslav@1890: if (next == null) jaroslav@1890: break; jaroslav@1890: Object x = next.value; jaroslav@1890: if (x != null && x != next) { jaroslav@1890: if (tooLow(next.key)) jaroslav@1890: next = null; jaroslav@1890: else jaroslav@1890: nextValue = (V) x; jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: public void remove() { jaroslav@1890: Node l = lastReturned; jaroslav@1890: if (l == null) jaroslav@1890: throw new IllegalStateException(); jaroslav@1890: m.remove(l.key); jaroslav@1890: lastReturned = null; jaroslav@1890: } jaroslav@1890: jaroslav@1890: } jaroslav@1890: jaroslav@1890: final class SubMapValueIterator extends SubMapIter { jaroslav@1890: public V next() { jaroslav@1890: V v = nextValue; jaroslav@1890: advance(); jaroslav@1890: return v; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: final class SubMapKeyIterator extends SubMapIter { jaroslav@1890: public K next() { jaroslav@1890: Node n = next; jaroslav@1890: advance(); jaroslav@1890: return n.key; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: final class SubMapEntryIterator extends SubMapIter> { jaroslav@1890: public Map.Entry next() { jaroslav@1890: Node n = next; jaroslav@1890: V v = nextValue; jaroslav@1890: advance(); jaroslav@1890: return new AbstractMap.SimpleImmutableEntry(n.key, v); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: // Unsafe mechanics jaroslav@1890: private static final sun.misc.Unsafe UNSAFE; jaroslav@1890: private static final long headOffset; jaroslav@1890: static { jaroslav@1890: try { jaroslav@1890: UNSAFE = sun.misc.Unsafe.getUnsafe(); jaroslav@1890: Class k = ConcurrentSkipListMap.class; jaroslav@1890: headOffset = UNSAFE.objectFieldOffset jaroslav@1890: (k.getDeclaredField("head")); jaroslav@1890: } catch (Exception e) { jaroslav@1890: throw new Error(e); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: }