1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation. Sun designates this
7 * particular file as subject to the "Classpath" exception as provided
8 * by Sun in the LICENSE file that accompanied this code.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
21 * CA 95054 USA or visit www.sun.com if you need additional information or
22 * have any questions.
23 */
24
25 /*
26 * This file is available under and governed by the GNU General Public
27 * License version 2 only, as published by the Free Software Foundation.
28 * However, the following notice accompanied the original version of this
29 * file:
30 *
31 * Written by Doug Lea with assistance from members of JCP JSR-166
32 * Expert Group and released to the public domain, as explained at
33 * http://creativecommons.org/licenses/publicdomain
34 */
35
36 package java.util.concurrent;
37 import java.util;
38 import java.util.concurrent.atomic;
39
40 /**
41 * A scalable concurrent {@link ConcurrentNavigableMap} implementation.
42 * The map is sorted according to the {@linkplain Comparable natural
43 * ordering} of its keys, or by a {@link Comparator} provided at map
44 * creation time, depending on which constructor is used.
45 *
46 * <p>This class implements a concurrent variant of <a
47 * href="http://www.cs.umd.edu/~pugh/">SkipLists</a> providing
48 * expected average <i>log(n)</i> time cost for the
49 * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and
50 * <tt>remove</tt> operations and their variants. Insertion, removal,
51 * update, and access operations safely execute concurrently by
52 * multiple threads. Iterators are <i>weakly consistent</i>, returning
53 * elements reflecting the state of the map at some point at or since
54 * the creation of the iterator. They do <em>not</em> throw {@link
55 * ConcurrentModificationException}, and may proceed concurrently with
56 * other operations. Ascending key ordered views and their iterators
57 * are faster than descending ones.
58 *
59 * <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
60 * and its views represent snapshots of mappings at the time they were
61 * produced. They do <em>not</em> support the <tt>Entry.setValue</tt>
62 * method. (Note however that it is possible to change mappings in the
63 * associated map using <tt>put</tt>, <tt>putIfAbsent</tt>, or
64 * <tt>replace</tt>, depending on exactly which effect you need.)
65 *
66 * <p>Beware that, unlike in most collections, the <tt>size</tt>
67 * method is <em>not</em> a constant-time operation. Because of the
68 * asynchronous nature of these maps, determining the current number
69 * of elements requires a traversal of the elements. Additionally,
70 * the bulk operations <tt>putAll</tt>, <tt>equals</tt>, and
71 * <tt>clear</tt> are <em>not</em> guaranteed to be performed
72 * atomically. For example, an iterator operating concurrently with a
73 * <tt>putAll</tt> operation might view only some of the added
74 * elements.
75 *
76 * <p>This class and its views and iterators implement all of the
77 * <em>optional</em> methods of the {@link Map} and {@link Iterator}
78 * interfaces. Like most other concurrent collections, this class does
79 * <em>not</em> permit the use of <tt>null</tt> keys or values because some
80 * null return values cannot be reliably distinguished from the absence of
81 * elements.
82 *
83 * <p>This class is a member of the
84 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
85 * Java Collections Framework</a>.
86 *
87 * @author Doug Lea
88 * @param <K> the type of keys maintained by this map
89 * @param <V> the type of mapped values
90 * @since 1.6
91 */
92 public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
93 implements ConcurrentNavigableMap<K,V>,
94 Cloneable,
95 java.io.Serializable {
96 /*
97 * This class implements a tree-like two-dimensionally linked skip
98 * list in which the index levels are represented in separate
99 * nodes from the base nodes holding data. There are two reasons
100 * for taking this approach instead of the usual array-based
101 * structure: 1) Array based implementations seem to encounter
102 * more complexity and overhead 2) We can use cheaper algorithms
103 * for the heavily-traversed index lists than can be used for the
104 * base lists. Here's a picture of some of the basics for a
105 * possible list with 2 levels of index:
106 *
107 * Head nodes Index nodes
108 * +-+ right +-+ +-+
109 * |2|---------------->| |--------------------->| |->null
110 * +-+ +-+ +-+
111 * | down | |
112 * v v v
113 * +-+ +-+ +-+ +-+ +-+ +-+
114 * |1|----------->| |->| |------>| |----------->| |------>| |->null
115 * +-+ +-+ +-+ +-+ +-+ +-+
116 * v | | | | |
117 * Nodes next v v v v v
118 * +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
119 * | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
120 * +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
121 *
122 * The base lists use a variant of the HM linked ordered set
123 * algorithm. See Tim Harris, "A pragmatic implementation of
124 * non-blocking linked lists"
125 * http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged
126 * Michael "High Performance Dynamic Lock-Free Hash Tables and
127 * List-Based Sets"
128 * http://www.research.ibm.com/people/m/michael/pubs.htm. The
129 * basic idea in these lists is to mark the "next" pointers of
130 * deleted nodes when deleting to avoid conflicts with concurrent
131 * insertions, and when traversing to keep track of triples
132 * (predecessor, node, successor) in order to detect when and how
133 * to unlink these deleted nodes.
134 *
135 * Rather than using mark-bits to mark list deletions (which can
136 * be slow and space-intensive using AtomicMarkedReference), nodes
137 * use direct CAS'able next pointers. On deletion, instead of
138 * marking a pointer, they splice in another node that can be
139 * thought of as standing for a marked pointer (indicating this by
140 * using otherwise impossible field values). Using plain nodes
141 * acts roughly like "boxed" implementations of marked pointers,
142 * but uses new nodes only when nodes are deleted, not for every
143 * link. This requires less space and supports faster
144 * traversal. Even if marked references were better supported by
145 * JVMs, traversal using this technique might still be faster
146 * because any search need only read ahead one more node than
147 * otherwise required (to check for trailing marker) rather than
148 * unmasking mark bits or whatever on each read.
149 *
150 * This approach maintains the essential property needed in the HM
151 * algorithm of changing the next-pointer of a deleted node so
152 * that any other CAS of it will fail, but implements the idea by
153 * changing the pointer to point to a different node, not by
154 * marking it. While it would be possible to further squeeze
155 * space by defining marker nodes not to have key/value fields, it
156 * isn't worth the extra type-testing overhead. The deletion
157 * markers are rarely encountered during traversal and are
158 * normally quickly garbage collected. (Note that this technique
159 * would not work well in systems without garbage collection.)
160 *
161 * In addition to using deletion markers, the lists also use
162 * nullness of value fields to indicate deletion, in a style
163 * similar to typical lazy-deletion schemes. If a node's value is
164 * null, then it is considered logically deleted and ignored even
165 * though it is still reachable. This maintains proper control of
166 * concurrent replace vs delete operations -- an attempted replace
167 * must fail if a delete beat it by nulling field, and a delete
168 * must return the last non-null value held in the field. (Note:
169 * Null, rather than some special marker, is used for value fields
170 * here because it just so happens to mesh with the Map API
171 * requirement that method get returns null if there is no
172 * mapping, which allows nodes to remain concurrently readable
173 * even when deleted. Using any other marker value here would be
174 * messy at best.)
175 *
176 * Here's the sequence of events for a deletion of node n with
177 * predecessor b and successor f, initially:
178 *
179 * +------+ +------+ +------+
180 * ... | b |------>| n |----->| f | ...
181 * +------+ +------+ +------+
182 *
183 * 1. CAS n's value field from non-null to null.
184 * From this point on, no public operations encountering
185 * the node consider this mapping to exist. However, other
186 * ongoing insertions and deletions might still modify
187 * n's next pointer.
188 *
189 * 2. CAS n's next pointer to point to a new marker node.
190 * From this point on, no other nodes can be appended to n.
191 * which avoids deletion errors in CAS-based linked lists.
192 *
193 * +------+ +------+ +------+ +------+
194 * ... | b |------>| n |----->|marker|------>| f | ...
195 * +------+ +------+ +------+ +------+
196 *
197 * 3. CAS b's next pointer over both n and its marker.
198 * From this point on, no new traversals will encounter n,
199 * and it can eventually be GCed.
200 * +------+ +------+
201 * ... | b |----------------------------------->| f | ...
202 * +------+ +------+
203 *
204 * A failure at step 1 leads to simple retry due to a lost race
205 * with another operation. Steps 2-3 can fail because some other
206 * thread noticed during a traversal a node with null value and
207 * helped out by marking and/or unlinking. This helping-out
208 * ensures that no thread can become stuck waiting for progress of
209 * the deleting thread. The use of marker nodes slightly
210 * complicates helping-out code because traversals must track
211 * consistent reads of up to four nodes (b, n, marker, f), not
212 * just (b, n, f), although the next field of a marker is
213 * immutable, and once a next field is CAS'ed to point to a
214 * marker, it never again changes, so this requires less care.
215 *
216 * Skip lists add indexing to this scheme, so that the base-level
217 * traversals start close to the locations being found, inserted
218 * or deleted -- usually base level traversals only traverse a few
219 * nodes. This doesn't change the basic algorithm except for the
220 * need to make sure base traversals start at predecessors (here,
221 * b) that are not (structurally) deleted, otherwise retrying
222 * after processing the deletion.
223 *
224 * Index levels are maintained as lists with volatile next fields,
225 * using CAS to link and unlink. Races are allowed in index-list
226 * operations that can (rarely) fail to link in a new index node
227 * or delete one. (We can't do this of course for data nodes.)
228 * However, even when this happens, the index lists remain sorted,
229 * so correctly serve as indices. This can impact performance,
230 * but since skip lists are probabilistic anyway, the net result
231 * is that under contention, the effective "p" value may be lower
232 * than its nominal value. And race windows are kept small enough
233 * that in practice these failures are rare, even under a lot of
234 * contention.
235 *
236 * The fact that retries (for both base and index lists) are
237 * relatively cheap due to indexing allows some minor
238 * simplifications of retry logic. Traversal restarts are
239 * performed after most "helping-out" CASes. This isn't always
240 * strictly necessary, but the implicit backoffs tend to help
241 * reduce other downstream failed CAS's enough to outweigh restart
242 * cost. This worsens the worst case, but seems to improve even
243 * highly contended cases.
244 *
245 * Unlike most skip-list implementations, index insertion and
246 * deletion here require a separate traversal pass occuring after
247 * the base-level action, to add or remove index nodes. This adds
248 * to single-threaded overhead, but improves contended
249 * multithreaded performance by narrowing interference windows,
250 * and allows deletion to ensure that all index nodes will be made
251 * unreachable upon return from a public remove operation, thus
252 * avoiding unwanted garbage retention. This is more important
253 * here than in some other data structures because we cannot null
254 * out node fields referencing user keys since they might still be
255 * read by other ongoing traversals.
256 *
257 * Indexing uses skip list parameters that maintain good search
258 * performance while using sparser-than-usual indices: The
259 * hardwired parameters k=1, p=0.5 (see method randomLevel) mean
260 * that about one-quarter of the nodes have indices. Of those that
261 * do, half have one level, a quarter have two, and so on (see
262 * Pugh's Skip List Cookbook, sec 3.4). The expected total space
263 * requirement for a map is slightly less than for the current
264 * implementation of java.util.TreeMap.
265 *
266 * Changing the level of the index (i.e, the height of the
267 * tree-like structure) also uses CAS. The head index has initial
268 * level/height of one. Creation of an index with height greater
269 * than the current level adds a level to the head index by
270 * CAS'ing on a new top-most head. To maintain good performance
271 * after a lot of removals, deletion methods heuristically try to
272 * reduce the height if the topmost levels appear to be empty.
273 * This may encounter races in which it possible (but rare) to
274 * reduce and "lose" a level just as it is about to contain an
275 * index (that will then never be encountered). This does no
276 * structural harm, and in practice appears to be a better option
277 * than allowing unrestrained growth of levels.
278 *
279 * The code for all this is more verbose than you'd like. Most
280 * operations entail locating an element (or position to insert an
281 * element). The code to do this can't be nicely factored out
282 * because subsequent uses require a snapshot of predecessor
283 * and/or successor and/or value fields which can't be returned
284 * all at once, at least not without creating yet another object
285 * to hold them -- creating such little objects is an especially
286 * bad idea for basic internal search operations because it adds
287 * to GC overhead. (This is one of the few times I've wished Java
288 * had macros.) Instead, some traversal code is interleaved within
289 * insertion and removal operations. The control logic to handle
290 * all the retry conditions is sometimes twisty. Most search is
291 * broken into 2 parts. findPredecessor() searches index nodes
292 * only, returning a base-level predecessor of the key. findNode()
293 * finishes out the base-level search. Even with this factoring,
294 * there is a fair amount of near-duplication of code to handle
295 * variants.
296 *
297 * For explanation of algorithms sharing at least a couple of
298 * features with this one, see Mikhail Fomitchev's thesis
299 * (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
300 * (http://www.cl.cam.ac.uk/users/kaf24/), and Hakan Sundell's
301 * thesis (http://www.cs.chalmers.se/~phs/).
302 *
303 * Given the use of tree-like index nodes, you might wonder why
304 * this doesn't use some kind of search tree instead, which would
305 * support somewhat faster search operations. The reason is that
306 * there are no known efficient lock-free insertion and deletion
307 * algorithms for search trees. The immutability of the "down"
308 * links of index nodes (as opposed to mutable "left" fields in
309 * true trees) makes this tractable using only CAS operations.
310 *
311 * Notation guide for local variables
312 * Node: b, n, f for predecessor, node, successor
313 * Index: q, r, d for index node, right, down.
314 * t for another index node
315 * Head: h
316 * Levels: j
317 * Keys: k, key
318 * Values: v, value
319 * Comparisons: c
320 */
321
322 private static final long serialVersionUID = -8627078645895051609L;
323
324 /**
325 * Generates the initial random seed for the cheaper per-instance
326 * random number generators used in randomLevel.
327 */
328 private static final Random seedGenerator = new Random();
329
330 /**
331 * Special value used to identify base-level header
332 */
333 private static final Object BASE_HEADER = new Object();
334
335 /**
336 * The topmost head index of the skiplist.
337 */
338 private transient volatile HeadIndex<K,V> head;
339
340 /**
341 * The comparator used to maintain order in this map, or null
342 * if using natural ordering.
343 * @serial
344 */
345 private final Comparator<? super K> comparator;
346
347 /**
348 * Seed for simple random number generator. Not volatile since it
349 * doesn't matter too much if different threads don't see updates.
350 */
351 private transient int randomSeed;
352
353 /** Lazily initialized key set */
354 private transient KeySet keySet;
355 /** Lazily initialized entry set */
356 private transient EntrySet entrySet;
357 /** Lazily initialized values collection */
358 private transient Values values;
359 /** Lazily initialized descending key set */
360 private transient ConcurrentNavigableMap<K,V> descendingMap;
361
362 /**
363 * Initializes or resets state. Needed by constructors, clone,
364 * clear, readObject. and ConcurrentSkipListSet.clone.
365 * (Note that comparator must be separately initialized.)
366 */
367 final void initialize() {
368 keySet = null;
369 entrySet = null;
370 values = null;
371 descendingMap = null;
372 randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
373 head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
374 null, null, 1);
375 }
376
377 /** Updater for casHead */
378 private static final
379 AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex>
380 headUpdater = AtomicReferenceFieldUpdater.newUpdater
381 (ConcurrentSkipListMap.class, HeadIndex.class, "head");
382
383 /**
384 * compareAndSet head node
385 */
386 private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {
387 return headUpdater.compareAndSet(this, cmp, val);
388 }
389
390 /* ---------------- Nodes -------------- */
391
392 /**
393 * Nodes hold keys and values, and are singly linked in sorted
394 * order, possibly with some intervening marker nodes. The list is
395 * headed by a dummy node accessible as head.node. The value field
396 * is declared only as Object because it takes special non-V
397 * values for marker and header nodes.
398 */
399 static final class Node<K,V> {
400 final K key;
401 volatile Object value;
402 volatile Node<K,V> next;
403
404 /**
405 * Creates a new regular node.
406 */
407 Node(K key, Object value, Node<K,V> next) {
408 this.key = key;
409 this.value = value;
410 this.next = next;
411 }
412
413 /**
414 * Creates a new marker node. A marker is distinguished by
415 * having its value field point to itself. Marker nodes also
416 * have null keys, a fact that is exploited in a few places,
417 * but this doesn't distinguish markers from the base-level
418 * header node (head.node), which also has a null key.
419 */
420 Node(Node<K,V> next) {
421 this.key = null;
422 this.value = this;
423 this.next = next;
424 }
425
426 /** Updater for casNext */
427 static final AtomicReferenceFieldUpdater<Node, Node>
428 nextUpdater = AtomicReferenceFieldUpdater.newUpdater
429 (Node.class, Node.class, "next");
430
431 /** Updater for casValue */
432 static final AtomicReferenceFieldUpdater<Node, Object>
433 valueUpdater = AtomicReferenceFieldUpdater.newUpdater
434 (Node.class, Object.class, "value");
435
436 /**
437 * compareAndSet value field
438 */
439 boolean casValue(Object cmp, Object val) {
440 return valueUpdater.compareAndSet(this, cmp, val);
441 }
442
443 /**
444 * compareAndSet next field
445 */
446 boolean casNext(Node<K,V> cmp, Node<K,V> val) {
447 return nextUpdater.compareAndSet(this, cmp, val);
448 }
449
450 /**
451 * Returns true if this node is a marker. This method isn't
452 * actually called in any current code checking for markers
453 * because callers will have already read value field and need
454 * to use that read (not another done here) and so directly
455 * test if value points to node.
456 * @param n a possibly null reference to a node
457 * @return true if this node is a marker node
458 */
459 boolean isMarker() {
460 return value == this;
461 }
462
463 /**
464 * Returns true if this node is the header of base-level list.
465 * @return true if this node is header node
466 */
467 boolean isBaseHeader() {
468 return value == BASE_HEADER;
469 }
470
471 /**
472 * Tries to append a deletion marker to this node.
473 * @param f the assumed current successor of this node
474 * @return true if successful
475 */
476 boolean appendMarker(Node<K,V> f) {
477 return casNext(f, new Node<K,V>(f));
478 }
479
480 /**
481 * Helps out a deletion by appending marker or unlinking from
482 * predecessor. This is called during traversals when value
483 * field seen to be null.
484 * @param b predecessor
485 * @param f successor
486 */
487 void helpDelete(Node<K,V> b, Node<K,V> f) {
488 /*
489 * Rechecking links and then doing only one of the
490 * help-out stages per call tends to minimize CAS
491 * interference among helping threads.
492 */
493 if (f == next && this == b.next) {
494 if (f == null || f.value != f) // not already marked
495 appendMarker(f);
496 else
497 b.casNext(this, f.next);
498 }
499 }
500
501 /**
502 * Returns value if this node contains a valid key-value pair,
503 * else null.
504 * @return this node's value if it isn't a marker or header or
505 * is deleted, else null.
506 */
507 V getValidValue() {
508 Object v = value;
509 if (v == this || v == BASE_HEADER)
510 return null;
511 return (V)v;
512 }
513
514 /**
515 * Creates and returns a new SimpleImmutableEntry holding current
516 * mapping if this node holds a valid value, else null.
517 * @return new entry or null
518 */
519 AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {
520 V v = getValidValue();
521 if (v == null)
522 return null;
523 return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);
524 }
525 }
526
527 /* ---------------- Indexing -------------- */
528
529 /**
530 * Index nodes represent the levels of the skip list. Note that
531 * even though both Nodes and Indexes have forward-pointing
532 * fields, they have different types and are handled in different
533 * ways, that can't nicely be captured by placing field in a
534 * shared abstract class.
535 */
536 static class Index<K,V> {
537 final Node<K,V> node;
538 final Index<K,V> down;
539 volatile Index<K,V> right;
540
541 /**
542 * Creates index node with given values.
543 */
544 Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
545 this.node = node;
546 this.down = down;
547 this.right = right;
548 }
549
550 /** Updater for casRight */
551 static final AtomicReferenceFieldUpdater<Index, Index>
552 rightUpdater = AtomicReferenceFieldUpdater.newUpdater
553 (Index.class, Index.class, "right");
554
555 /**
556 * compareAndSet right field
557 */
558 final boolean casRight(Index<K,V> cmp, Index<K,V> val) {
559 return rightUpdater.compareAndSet(this, cmp, val);
560 }
561
562 /**
563 * Returns true if the node this indexes has been deleted.
564 * @return true if indexed node is known to be deleted
565 */
566 final boolean indexesDeletedNode() {
567 return node.value == null;
568 }
569
570 /**
571 * Tries to CAS newSucc as successor. To minimize races with
572 * unlink that may lose this index node, if the node being
573 * indexed is known to be deleted, it doesn't try to link in.
574 * @param succ the expected current successor
575 * @param newSucc the new successor
576 * @return true if successful
577 */
578 final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
579 Node<K,V> n = node;
580 newSucc.right = succ;
581 return n.value != null && casRight(succ, newSucc);
582 }
583
584 /**
585 * Tries to CAS right field to skip over apparent successor
586 * succ. Fails (forcing a retraversal by caller) if this node
587 * is known to be deleted.
588 * @param succ the expected current successor
589 * @return true if successful
590 */
591 final boolean unlink(Index<K,V> succ) {
592 return !indexesDeletedNode() && casRight(succ, succ.right);
593 }
594 }
595
596 /* ---------------- Head nodes -------------- */
597
598 /**
599 * Nodes heading each level keep track of their level.
600 */
601 static final class HeadIndex<K,V> extends Index<K,V> {
602 final int level;
603 HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
604 super(node, down, right);
605 this.level = level;
606 }
607 }
608
609 /* ---------------- Comparison utilities -------------- */
610
611 /**
612 * Represents a key with a comparator as a Comparable.
613 *
614 * Because most sorted collections seem to use natural ordering on
615 * Comparables (Strings, Integers, etc), most internal methods are
616 * geared to use them. This is generally faster than checking
617 * per-comparison whether to use comparator or comparable because
618 * it doesn't require a (Comparable) cast for each comparison.
619 * (Optimizers can only sometimes remove such redundant checks
620 * themselves.) When Comparators are used,
621 * ComparableUsingComparators are created so that they act in the
622 * same way as natural orderings. This penalizes use of
623 * Comparators vs Comparables, which seems like the right
624 * tradeoff.
625 */
626 static final class ComparableUsingComparator<K> implements Comparable<K> {
627 final K actualKey;
628 final Comparator<? super K> cmp;
629 ComparableUsingComparator(K key, Comparator<? super K> cmp) {
630 this.actualKey = key;
631 this.cmp = cmp;
632 }
633 public int compareTo(K k2) {
634 return cmp.compare(actualKey, k2);
635 }
636 }
637
638 /**
639 * If using comparator, return a ComparableUsingComparator, else
640 * cast key as Comparable, which may cause ClassCastException,
641 * which is propagated back to caller.
642 */
643 private Comparable<? super K> comparable(Object key) throws ClassCastException {
644 if (key == null)
645 throw new NullPointerException();
646 if (comparator != null)
647 return new ComparableUsingComparator<K>((K)key, comparator);
648 else
649 return (Comparable<? super K>)key;
650 }
651
652 /**
653 * Compares using comparator or natural ordering. Used when the
654 * ComparableUsingComparator approach doesn't apply.
655 */
656 int compare(K k1, K k2) throws ClassCastException {
657 Comparator<? super K> cmp = comparator;
658 if (cmp != null)
659 return cmp.compare(k1, k2);
660 else
661 return ((Comparable<? super K>)k1).compareTo(k2);
662 }
663
664 /**
665 * Returns true if given key greater than or equal to least and
666 * strictly less than fence, bypassing either test if least or
667 * fence are null. Needed mainly in submap operations.
668 */
669 boolean inHalfOpenRange(K key, K least, K fence) {
670 if (key == null)
671 throw new NullPointerException();
672 return ((least == null || compare(key, least) >= 0) &&
673 (fence == null || compare(key, fence) < 0));
674 }
675
676 /**
677 * Returns true if given key greater than or equal to least and less
678 * or equal to fence. Needed mainly in submap operations.
679 */
680 boolean inOpenRange(K key, K least, K fence) {
681 if (key == null)
682 throw new NullPointerException();
683 return ((least == null || compare(key, least) >= 0) &&
684 (fence == null || compare(key, fence) <= 0));
685 }
686
687 /* ---------------- Traversal -------------- */
688
689 /**
690 * Returns a base-level node with key strictly less than given key,
691 * or the base-level header if there is no such node. Also
692 * unlinks indexes to deleted nodes found along the way. Callers
693 * rely on this side-effect of clearing indices to deleted nodes.
694 * @param key the key
695 * @return a predecessor of key
696 */
697 private Node<K,V> findPredecessor(Comparable<? super K> key) {
698 if (key == null)
699 throw new NullPointerException(); // don't postpone errors
700 for (;;) {
701 Index<K,V> q = head;
702 Index<K,V> r = q.right;
703 for (;;) {
704 if (r != null) {
705 Node<K,V> n = r.node;
706 K k = n.key;
707 if (n.value == null) {
708 if (!q.unlink(r))
709 break; // restart
710 r = q.right; // reread r
711 continue;
712 }
713 if (key.compareTo(k) > 0) {
714 q = r;
715 r = r.right;
716 continue;
717 }
718 }
719 Index<K,V> d = q.down;
720 if (d != null) {
721 q = d;
722 r = d.right;
723 } else
724 return q.node;
725 }
726 }
727 }
728
729 /**
730 * Returns node holding key or null if no such, clearing out any
731 * deleted nodes seen along the way. Repeatedly traverses at
732 * base-level looking for key starting at predecessor returned
733 * from findPredecessor, processing base-level deletions as
734 * encountered. Some callers rely on this side-effect of clearing
735 * deleted nodes.
736 *
737 * Restarts occur, at traversal step centered on node n, if:
738 *
739 * (1) After reading n's next field, n is no longer assumed
740 * predecessor b's current successor, which means that
741 * we don't have a consistent 3-node snapshot and so cannot
742 * unlink any subsequent deleted nodes encountered.
743 *
744 * (2) n's value field is null, indicating n is deleted, in
745 * which case we help out an ongoing structural deletion
746 * before retrying. Even though there are cases where such
747 * unlinking doesn't require restart, they aren't sorted out
748 * here because doing so would not usually outweigh cost of
749 * restarting.
750 *
751 * (3) n is a marker or n's predecessor's value field is null,
752 * indicating (among other possibilities) that
753 * findPredecessor returned a deleted node. We can't unlink
754 * the node because we don't know its predecessor, so rely
755 * on another call to findPredecessor to notice and return
756 * some earlier predecessor, which it will do. This check is
757 * only strictly needed at beginning of loop, (and the
758 * b.value check isn't strictly needed at all) but is done
759 * each iteration to help avoid contention with other
760 * threads by callers that will fail to be able to change
761 * links, and so will retry anyway.
762 *
763 * The traversal loops in doPut, doRemove, and findNear all
764 * include the same three kinds of checks. And specialized
765 * versions appear in findFirst, and findLast and their
766 * variants. They can't easily share code because each uses the
767 * reads of fields held in locals occurring in the orders they
768 * were performed.
769 *
770 * @param key the key
771 * @return node holding key, or null if no such
772 */
773 private Node<K,V> findNode(Comparable<? super K> key) {
774 for (;;) {
775 Node<K,V> b = findPredecessor(key);
776 Node<K,V> n = b.next;
777 for (;;) {
778 if (n == null)
779 return null;
780 Node<K,V> f = n.next;
781 if (n != b.next) // inconsistent read
782 break;
783 Object v = n.value;
784 if (v == null) { // n is deleted
785 n.helpDelete(b, f);
786 break;
787 }
788 if (v == n || b.value == null) // b is deleted
789 break;
790 int c = key.compareTo(n.key);
791 if (c == 0)
792 return n;
793 if (c < 0)
794 return null;
795 b = n;
796 n = f;
797 }
798 }
799 }
800
801 /**
802 * Specialized variant of findNode to perform Map.get. Does a weak
803 * traversal, not bothering to fix any deleted index nodes,
804 * returning early if it happens to see key in index, and passing
805 * over any deleted base nodes, falling back to getUsingFindNode
806 * only if it would otherwise return value from an ongoing
807 * deletion. Also uses "bound" to eliminate need for some
808 * comparisons (see Pugh Cookbook). Also folds uses of null checks
809 * and node-skipping because markers have null keys.
810 * @param okey the key
811 * @return the value, or null if absent
812 */
813 private V doGet(Object okey) {
814 Comparable<? super K> key = comparable(okey);
815 Node<K,V> bound = null;
816 Index<K,V> q = head;
817 Index<K,V> r = q.right;
818 Node<K,V> n;
819 K k;
820 int c;
821 for (;;) {
822 Index<K,V> d;
823 // Traverse rights
824 if (r != null && (n = r.node) != bound && (k = n.key) != null) {
825 if ((c = key.compareTo(k)) > 0) {
826 q = r;
827 r = r.right;
828 continue;
829 } else if (c == 0) {
830 Object v = n.value;
831 return (v != null)? (V)v : getUsingFindNode(key);
832 } else
833 bound = n;
834 }
835
836 // Traverse down
837 if ((d = q.down) != null) {
838 q = d;
839 r = d.right;
840 } else
841 break;
842 }
843
844 // Traverse nexts
845 for (n = q.node.next; n != null; n = n.next) {
846 if ((k = n.key) != null) {
847 if ((c = key.compareTo(k)) == 0) {
848 Object v = n.value;
849 return (v != null)? (V)v : getUsingFindNode(key);
850 } else if (c < 0)
851 break;
852 }
853 }
854 return null;
855 }
856
857 /**
858 * Performs map.get via findNode. Used as a backup if doGet
859 * encounters an in-progress deletion.
860 * @param key the key
861 * @return the value, or null if absent
862 */
863 private V getUsingFindNode(Comparable<? super K> key) {
864 /*
865 * Loop needed here and elsewhere in case value field goes
866 * null just as it is about to be returned, in which case we
867 * lost a race with a deletion, so must retry.
868 */
869 for (;;) {
870 Node<K,V> n = findNode(key);
871 if (n == null)
872 return null;
873 Object v = n.value;
874 if (v != null)
875 return (V)v;
876 }
877 }
878
879 /* ---------------- Insertion -------------- */
880
881 /**
882 * Main insertion method. Adds element if not present, or
883 * replaces value if present and onlyIfAbsent is false.
884 * @param kkey the key
885 * @param value the value that must be associated with key
886 * @param onlyIfAbsent if should not insert if already present
887 * @return the old value, or null if newly inserted
888 */
889 private V doPut(K kkey, V value, boolean onlyIfAbsent) {
890 Comparable<? super K> key = comparable(kkey);
891 for (;;) {
892 Node<K,V> b = findPredecessor(key);
893 Node<K,V> n = b.next;
894 for (;;) {
895 if (n != null) {
896 Node<K,V> f = n.next;
897 if (n != b.next) // inconsistent read
898 break;;
899 Object v = n.value;
900 if (v == null) { // n is deleted
901 n.helpDelete(b, f);
902 break;
903 }
904 if (v == n || b.value == null) // b is deleted
905 break;
906 int c = key.compareTo(n.key);
907 if (c > 0) {
908 b = n;
909 n = f;
910 continue;
911 }
912 if (c == 0) {
913 if (onlyIfAbsent || n.casValue(v, value))
914 return (V)v;
915 else
916 break; // restart if lost race to replace value
917 }
918 // else c < 0; fall through
919 }
920
921 Node<K,V> z = new Node<K,V>(kkey, value, n);
922 if (!b.casNext(n, z))
923 break; // restart if lost race to append to b
924 int level = randomLevel();
925 if (level > 0)
926 insertIndex(z, level);
927 return null;
928 }
929 }
930 }
931
932 /**
933 * Returns a random level for inserting a new node.
934 * Hardwired to k=1, p=0.5, max 31 (see above and
935 * Pugh's "Skip List Cookbook", sec 3.4).
936 *
937 * This uses the simplest of the generators described in George
938 * Marsaglia's "Xorshift RNGs" paper. This is not a high-quality
939 * generator but is acceptable here.
940 */
941 private int randomLevel() {
942 int x = randomSeed;
943 x ^= x << 13;
944 x ^= x >>> 17;
945 randomSeed = x ^= x << 5;
946 if ((x & 0x8001) != 0) // test highest and lowest bits
947 return 0;
948 int level = 1;
949 while (((x >>>= 1) & 1) != 0) ++level;
950 return level;
951 }
952
953 /**
954 * Creates and adds index nodes for the given node.
955 * @param z the node
956 * @param level the level of the index
957 */
958 private void insertIndex(Node<K,V> z, int level) {
959 HeadIndex<K,V> h = head;
960 int max = h.level;
961
962 if (level <= max) {
963 Index<K,V> idx = null;
964 for (int i = 1; i <= level; ++i)
965 idx = new Index<K,V>(z, idx, null);
966 addIndex(idx, h, level);
967
968 } else { // Add a new level
969 /*
970 * To reduce interference by other threads checking for
971 * empty levels in tryReduceLevel, new levels are added
972 * with initialized right pointers. Which in turn requires
973 * keeping levels in an array to access them while
974 * creating new head index nodes from the opposite
975 * direction.
976 */
977 level = max + 1;
978 Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1];
979 Index<K,V> idx = null;
980 for (int i = 1; i <= level; ++i)
981 idxs[i] = idx = new Index<K,V>(z, idx, null);
982
983 HeadIndex<K,V> oldh;
984 int k;
985 for (;;) {
986 oldh = head;
987 int oldLevel = oldh.level;
988 if (level <= oldLevel) { // lost race to add level
989 k = level;
990 break;
991 }
992 HeadIndex<K,V> newh = oldh;
993 Node<K,V> oldbase = oldh.node;
994 for (int j = oldLevel+1; j <= level; ++j)
995 newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
996 if (casHead(oldh, newh)) {
997 k = oldLevel;
998 break;
999 }
1000 }
1001 addIndex(idxs[k], oldh, k);
1002 }
1003 }
1004
1005 /**
1006 * Adds given index nodes from given level down to 1.
1007 * @param idx the topmost index node being inserted
1008 * @param h the value of head to use to insert. This must be
1009 * snapshotted by callers to provide correct insertion level
1010 * @param indexLevel the level of the index
1011 */
1012 private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) {
1013 // Track next level to insert in case of retries
1014 int insertionLevel = indexLevel;
1015 Comparable<? super K> key = comparable(idx.node.key);
1016 if (key == null) throw new NullPointerException();
1017
1018 // Similar to findPredecessor, but adding index nodes along
1019 // path to key.
1020 for (;;) {
1021 int j = h.level;
1022 Index<K,V> q = h;
1023 Index<K,V> r = q.right;
1024 Index<K,V> t = idx;
1025 for (;;) {
1026 if (r != null) {
1027 Node<K,V> n = r.node;
1028 // compare before deletion check avoids needing recheck
1029 int c = key.compareTo(n.key);
1030 if (n.value == null) {
1031 if (!q.unlink(r))
1032 break;
1033 r = q.right;
1034 continue;
1035 }
1036 if (c > 0) {
1037 q = r;
1038 r = r.right;
1039 continue;
1040 }
1041 }
1042
1043 if (j == insertionLevel) {
1044 // Don't insert index if node already deleted
1045 if (t.indexesDeletedNode()) {
1046 findNode(key); // cleans up
1047 return;
1048 }
1049 if (!q.link(r, t))
1050 break; // restart
1051 if (--insertionLevel == 0) {
1052 // need final deletion check before return
1053 if (t.indexesDeletedNode())
1054 findNode(key);
1055 return;
1056 }
1057 }
1058
1059 if (--j >= insertionLevel && j < indexLevel)
1060 t = t.down;
1061 q = q.down;
1062 r = q.right;
1063 }
1064 }
1065 }
1066
1067 /* ---------------- Deletion -------------- */
1068
1069 /**
1070 * Main deletion method. Locates node, nulls value, appends a
1071 * deletion marker, unlinks predecessor, removes associated index
1072 * nodes, and possibly reduces head index level.
1073 *
1074 * Index nodes are cleared out simply by calling findPredecessor.
1075 * which unlinks indexes to deleted nodes found along path to key,
1076 * which will include the indexes to this node. This is done
1077 * unconditionally. We can't check beforehand whether there are
1078 * index nodes because it might be the case that some or all
1079 * indexes hadn't been inserted yet for this node during initial
1080 * search for it, and we'd like to ensure lack of garbage
1081 * retention, so must call to be sure.
1082 *
1083 * @param okey the key
1084 * @param value if non-null, the value that must be
1085 * associated with key
1086 * @return the node, or null if not found
1087 */
1088 final V doRemove(Object okey, Object value) {
1089 Comparable<? super K> key = comparable(okey);
1090 for (;;) {
1091 Node<K,V> b = findPredecessor(key);
1092 Node<K,V> n = b.next;
1093 for (;;) {
1094 if (n == null)
1095 return null;
1096 Node<K,V> f = n.next;
1097 if (n != b.next) // inconsistent read
1098 break;
1099 Object v = n.value;
1100 if (v == null) { // n is deleted
1101 n.helpDelete(b, f);
1102 break;
1103 }
1104 if (v == n || b.value == null) // b is deleted
1105 break;
1106 int c = key.compareTo(n.key);
1107 if (c < 0)
1108 return null;
1109 if (c > 0) {
1110 b = n;
1111 n = f;
1112 continue;
1113 }
1114 if (value != null && !value.equals(v))
1115 return null;
1116 if (!n.casValue(v, null))
1117 break;
1118 if (!n.appendMarker(f) || !b.casNext(n, f))
1119 findNode(key); // Retry via findNode
1120 else {
1121 findPredecessor(key); // Clean index
1122 if (head.right == null)
1123 tryReduceLevel();
1124 }
1125 return (V)v;
1126 }
1127 }
1128 }
1129
1130 /**
1131 * Possibly reduce head level if it has no nodes. This method can
1132 * (rarely) make mistakes, in which case levels can disappear even
1133 * though they are about to contain index nodes. This impacts
1134 * performance, not correctness. To minimize mistakes as well as
1135 * to reduce hysteresis, the level is reduced by one only if the
1136 * topmost three levels look empty. Also, if the removed level
1137 * looks non-empty after CAS, we try to change it back quick
1138 * before anyone notices our mistake! (This trick works pretty
1139 * well because this method will practically never make mistakes
1140 * unless current thread stalls immediately before first CAS, in
1141 * which case it is very unlikely to stall again immediately
1142 * afterwards, so will recover.)
1143 *
1144 * We put up with all this rather than just let levels grow
1145 * because otherwise, even a small map that has undergone a large
1146 * number of insertions and removals will have a lot of levels,
1147 * slowing down access more than would an occasional unwanted
1148 * reduction.
1149 */
1150 private void tryReduceLevel() {
1151 HeadIndex<K,V> h = head;
1152 HeadIndex<K,V> d;
1153 HeadIndex<K,V> e;
1154 if (h.level > 3 &&
1155 (d = (HeadIndex<K,V>)h.down) != null &&
1156 (e = (HeadIndex<K,V>)d.down) != null &&
1157 e.right == null &&
1158 d.right == null &&
1159 h.right == null &&
1160 casHead(h, d) && // try to set
1161 h.right != null) // recheck
1162 casHead(d, h); // try to backout
1163 }
1164
1165 /* ---------------- Finding and removing first element -------------- */
1166
1167 /**
1168 * Specialized variant of findNode to get first valid node.
1169 * @return first node or null if empty
1170 */
1171 Node<K,V> findFirst() {
1172 for (;;) {
1173 Node<K,V> b = head.node;
1174 Node<K,V> n = b.next;
1175 if (n == null)
1176 return null;
1177 if (n.value != null)
1178 return n;
1179 n.helpDelete(b, n.next);
1180 }
1181 }
1182
1183 /**
1184 * Removes first entry; returns its snapshot.
1185 * @return null if empty, else snapshot of first entry
1186 */
1187 Map.Entry<K,V> doRemoveFirstEntry() {
1188 for (;;) {
1189 Node<K,V> b = head.node;
1190 Node<K,V> n = b.next;
1191 if (n == null)
1192 return null;
1193 Node<K,V> f = n.next;
1194 if (n != b.next)
1195 continue;
1196 Object v = n.value;
1197 if (v == null) {
1198 n.helpDelete(b, f);
1199 continue;
1200 }
1201 if (!n.casValue(v, null))
1202 continue;
1203 if (!n.appendMarker(f) || !b.casNext(n, f))
1204 findFirst(); // retry
1205 clearIndexToFirst();
1206 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, (V)v);
1207 }
1208 }
1209
1210 /**
1211 * Clears out index nodes associated with deleted first entry.
1212 */
1213 private void clearIndexToFirst() {
1214 for (;;) {
1215 Index<K,V> q = head;
1216 for (;;) {
1217 Index<K,V> r = q.right;
1218 if (r != null && r.indexesDeletedNode() && !q.unlink(r))
1219 break;
1220 if ((q = q.down) == null) {
1221 if (head.right == null)
1222 tryReduceLevel();
1223 return;
1224 }
1225 }
1226 }
1227 }
1228
1229
1230 /* ---------------- Finding and removing last element -------------- */
1231
1232 /**
1233 * Specialized version of find to get last valid node.
1234 * @return last node or null if empty
1235 */
1236 Node<K,V> findLast() {
1237 /*
1238 * findPredecessor can't be used to traverse index level
1239 * because this doesn't use comparisons. So traversals of
1240 * both levels are folded together.
1241 */
1242 Index<K,V> q = head;
1243 for (;;) {
1244 Index<K,V> d, r;
1245 if ((r = q.right) != null) {
1246 if (r.indexesDeletedNode()) {
1247 q.unlink(r);
1248 q = head; // restart
1249 }
1250 else
1251 q = r;
1252 } else if ((d = q.down) != null) {
1253 q = d;
1254 } else {
1255 Node<K,V> b = q.node;
1256 Node<K,V> n = b.next;
1257 for (;;) {
1258 if (n == null)
1259 return (b.isBaseHeader())? null : b;
1260 Node<K,V> f = n.next; // inconsistent read
1261 if (n != b.next)
1262 break;
1263 Object v = n.value;
1264 if (v == null) { // n is deleted
1265 n.helpDelete(b, f);
1266 break;
1267 }
1268 if (v == n || b.value == null) // b is deleted
1269 break;
1270 b = n;
1271 n = f;
1272 }
1273 q = head; // restart
1274 }
1275 }
1276 }
1277
1278 /**
1279 * Specialized variant of findPredecessor to get predecessor of last
1280 * valid node. Needed when removing the last entry. It is possible
1281 * that all successors of returned node will have been deleted upon
1282 * return, in which case this method can be retried.
1283 * @return likely predecessor of last node
1284 */
1285 private Node<K,V> findPredecessorOfLast() {
1286 for (;;) {
1287 Index<K,V> q = head;
1288 for (;;) {
1289 Index<K,V> d, r;
1290 if ((r = q.right) != null) {
1291 if (r.indexesDeletedNode()) {
1292 q.unlink(r);
1293 break; // must restart
1294 }
1295 // proceed as far across as possible without overshooting
1296 if (r.node.next != null) {
1297 q = r;
1298 continue;
1299 }
1300 }
1301 if ((d = q.down) != null)
1302 q = d;
1303 else
1304 return q.node;
1305 }
1306 }
1307 }
1308
1309 /**
1310 * Removes last entry; returns its snapshot.
1311 * Specialized variant of doRemove.
1312 * @return null if empty, else snapshot of last entry
1313 */
1314 Map.Entry<K,V> doRemoveLastEntry() {
1315 for (;;) {
1316 Node<K,V> b = findPredecessorOfLast();
1317 Node<K,V> n = b.next;
1318 if (n == null) {
1319 if (b.isBaseHeader()) // empty
1320 return null;
1321 else
1322 continue; // all b's successors are deleted; retry
1323 }
1324 for (;;) {
1325 Node<K,V> f = n.next;
1326 if (n != b.next) // inconsistent read
1327 break;
1328 Object v = n.value;
1329 if (v == null) { // n is deleted
1330 n.helpDelete(b, f);
1331 break;
1332 }
1333 if (v == n || b.value == null) // b is deleted
1334 break;
1335 if (f != null) {
1336 b = n;
1337 n = f;
1338 continue;
1339 }
1340 if (!n.casValue(v, null))
1341 break;
1342 K key = n.key;
1343 Comparable<? super K> ck = comparable(key);
1344 if (!n.appendMarker(f) || !b.casNext(n, f))
1345 findNode(ck); // Retry via findNode
1346 else {
1347 findPredecessor(ck); // Clean index
1348 if (head.right == null)
1349 tryReduceLevel();
1350 }
1351 return new AbstractMap.SimpleImmutableEntry<K,V>(key, (V)v);
1352 }
1353 }
1354 }
1355
1356 /* ---------------- Relational operations -------------- */
1357
1358 // Control values OR'ed as arguments to findNear
1359
1360 private static final int EQ = 1;
1361 private static final int LT = 2;
1362 private static final int GT = 0; // Actually checked as !LT
1363
1364 /**
1365 * Utility for ceiling, floor, lower, higher methods.
1366 * @param kkey the key
1367 * @param rel the relation -- OR'ed combination of EQ, LT, GT
1368 * @return nearest node fitting relation, or null if no such
1369 */
1370 Node<K,V> findNear(K kkey, int rel) {
1371 Comparable<? super K> key = comparable(kkey);
1372 for (;;) {
1373 Node<K,V> b = findPredecessor(key);
1374 Node<K,V> n = b.next;
1375 for (;;) {
1376 if (n == null)
1377 return ((rel & LT) == 0 || b.isBaseHeader())? null : b;
1378 Node<K,V> f = n.next;
1379 if (n != b.next) // inconsistent read
1380 break;
1381 Object v = n.value;
1382 if (v == null) { // n is deleted
1383 n.helpDelete(b, f);
1384 break;
1385 }
1386 if (v == n || b.value == null) // b is deleted
1387 break;
1388 int c = key.compareTo(n.key);
1389 if ((c == 0 && (rel & EQ) != 0) ||
1390 (c < 0 && (rel & LT) == 0))
1391 return n;
1392 if ( c <= 0 && (rel & LT) != 0)
1393 return (b.isBaseHeader())? null : b;
1394 b = n;
1395 n = f;
1396 }
1397 }
1398 }
1399
1400 /**
1401 * Returns SimpleImmutableEntry for results of findNear.
1402 * @param key the key
1403 * @param rel the relation -- OR'ed combination of EQ, LT, GT
1404 * @return Entry fitting relation, or null if no such
1405 */
1406 AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) {
1407 for (;;) {
1408 Node<K,V> n = findNear(key, rel);
1409 if (n == null)
1410 return null;
1411 AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
1412 if (e != null)
1413 return e;
1414 }
1415 }
1416
1417
1418 /* ---------------- Constructors -------------- */
1419
1420 /**
1421 * Constructs a new, empty map, sorted according to the
1422 * {@linkplain Comparable natural ordering} of the keys.
1423 */
1424 public ConcurrentSkipListMap() {
1425 this.comparator = null;
1426 initialize();
1427 }
1428
1429 /**
1430 * Constructs a new, empty map, sorted according to the specified
1431 * comparator.
1432 *
1433 * @param comparator the comparator that will be used to order this map.
1434 * If <tt>null</tt>, the {@linkplain Comparable natural
1435 * ordering} of the keys will be used.
1436 */
1437 public ConcurrentSkipListMap(Comparator<? super K> comparator) {
1438 this.comparator = comparator;
1439 initialize();
1440 }
1441
1442 /**
1443 * Constructs a new map containing the same mappings as the given map,
1444 * sorted according to the {@linkplain Comparable natural ordering} of
1445 * the keys.
1446 *
1447 * @param m the map whose mappings are to be placed in this map
1448 * @throws ClassCastException if the keys in <tt>m</tt> are not
1449 * {@link Comparable}, or are not mutually comparable
1450 * @throws NullPointerException if the specified map or any of its keys
1451 * or values are null
1452 */
1453 public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
1454 this.comparator = null;
1455 initialize();
1456 putAll(m);
1457 }
1458
1459 /**
1460 * Constructs a new map containing the same mappings and using the
1461 * same ordering as the specified sorted map.
1462 *
1463 * @param m the sorted map whose mappings are to be placed in this
1464 * map, and whose comparator is to be used to sort this map
1465 * @throws NullPointerException if the specified sorted map or any of
1466 * its keys or values are null
1467 */
1468 public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
1469 this.comparator = m.comparator();
1470 initialize();
1471 buildFromSorted(m);
1472 }
1473
1474 /**
1475 * Returns a shallow copy of this <tt>ConcurrentSkipListMap</tt>
1476 * instance. (The keys and values themselves are not cloned.)
1477 *
1478 * @return a shallow copy of this map
1479 */
1480 public ConcurrentSkipListMap<K,V> clone() {
1481 ConcurrentSkipListMap<K,V> clone = null;
1482 try {
1483 clone = (ConcurrentSkipListMap<K,V>) super.clone();
1484 } catch (CloneNotSupportedException e) {
1485 throw new InternalError();
1486 }
1487
1488 clone.initialize();
1489 clone.buildFromSorted(this);
1490 return clone;
1491 }
1492
1493 /**
1494 * Streamlined bulk insertion to initialize from elements of
1495 * given sorted map. Call only from constructor or clone
1496 * method.
1497 */
1498 private void buildFromSorted(SortedMap<K, ? extends V> map) {
1499 if (map == null)
1500 throw new NullPointerException();
1501
1502 HeadIndex<K,V> h = head;
1503 Node<K,V> basepred = h.node;
1504
1505 // Track the current rightmost node at each level. Uses an
1506 // ArrayList to avoid committing to initial or maximum level.
1507 ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1508
1509 // initialize
1510 for (int i = 0; i <= h.level; ++i)
1511 preds.add(null);
1512 Index<K,V> q = h;
1513 for (int i = h.level; i > 0; --i) {
1514 preds.set(i, q);
1515 q = q.down;
1516 }
1517
1518 Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
1519 map.entrySet().iterator();
1520 while (it.hasNext()) {
1521 Map.Entry<? extends K, ? extends V> e = it.next();
1522 int j = randomLevel();
1523 if (j > h.level) j = h.level + 1;
1524 K k = e.getKey();
1525 V v = e.getValue();
1526 if (k == null || v == null)
1527 throw new NullPointerException();
1528 Node<K,V> z = new Node<K,V>(k, v, null);
1529 basepred.next = z;
1530 basepred = z;
1531 if (j > 0) {
1532 Index<K,V> idx = null;
1533 for (int i = 1; i <= j; ++i) {
1534 idx = new Index<K,V>(z, idx, null);
1535 if (i > h.level)
1536 h = new HeadIndex<K,V>(h.node, h, idx, i);
1537
1538 if (i < preds.size()) {
1539 preds.get(i).right = idx;
1540 preds.set(i, idx);
1541 } else
1542 preds.add(idx);
1543 }
1544 }
1545 }
1546 head = h;
1547 }
1548
1549 /* ---------------- Serialization -------------- */
1550
1551 /**
1552 * Save the state of this map to a stream.
1553 *
1554 * @serialData The key (Object) and value (Object) for each
1555 * key-value mapping represented by the map, followed by
1556 * <tt>null</tt>. The key-value mappings are emitted in key-order
1557 * (as determined by the Comparator, or by the keys' natural
1558 * ordering if no Comparator).
1559 */
1560 private void writeObject(java.io.ObjectOutputStream s)
1561 throws java.io.IOException {
1562 // Write out the Comparator and any hidden stuff
1563 s.defaultWriteObject();
1564
1565 // Write out keys and values (alternating)
1566 for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1567 V v = n.getValidValue();
1568 if (v != null) {
1569 s.writeObject(n.key);
1570 s.writeObject(v);
1571 }
1572 }
1573 s.writeObject(null);
1574 }
1575
1576 /**
1577 * Reconstitute the map from a stream.
1578 */
1579 private void readObject(final java.io.ObjectInputStream s)
1580 throws java.io.IOException, ClassNotFoundException {
1581 // Read in the Comparator and any hidden stuff
1582 s.defaultReadObject();
1583 // Reset transients
1584 initialize();
1585
1586 /*
1587 * This is nearly identical to buildFromSorted, but is
1588 * distinct because readObject calls can't be nicely adapted
1589 * as the kind of iterator needed by buildFromSorted. (They
1590 * can be, but doing so requires type cheats and/or creation
1591 * of adaptor classes.) It is simpler to just adapt the code.
1592 */
1593
1594 HeadIndex<K,V> h = head;
1595 Node<K,V> basepred = h.node;
1596 ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1597 for (int i = 0; i <= h.level; ++i)
1598 preds.add(null);
1599 Index<K,V> q = h;
1600 for (int i = h.level; i > 0; --i) {
1601 preds.set(i, q);
1602 q = q.down;
1603 }
1604
1605 for (;;) {
1606 Object k = s.readObject();
1607 if (k == null)
1608 break;
1609 Object v = s.readObject();
1610 if (v == null)
1611 throw new NullPointerException();
1612 K key = (K) k;
1613 V val = (V) v;
1614 int j = randomLevel();
1615 if (j > h.level) j = h.level + 1;
1616 Node<K,V> z = new Node<K,V>(key, val, null);
1617 basepred.next = z;
1618 basepred = z;
1619 if (j > 0) {
1620 Index<K,V> idx = null;
1621 for (int i = 1; i <= j; ++i) {
1622 idx = new Index<K,V>(z, idx, null);
1623 if (i > h.level)
1624 h = new HeadIndex<K,V>(h.node, h, idx, i);
1625
1626 if (i < preds.size()) {
1627 preds.get(i).right = idx;
1628 preds.set(i, idx);
1629 } else
1630 preds.add(idx);
1631 }
1632 }
1633 }
1634 head = h;
1635 }
1636
1637 /* ------ Map API methods ------ */
1638
1639 /**
1640 * Returns <tt>true</tt> if this map contains a mapping for the specified
1641 * key.
1642 *
1643 * @param key key whose presence in this map is to be tested
1644 * @return <tt>true</tt> if this map contains a mapping for the specified key
1645 * @throws ClassCastException if the specified key cannot be compared
1646 * with the keys currently in the map
1647 * @throws NullPointerException if the specified key is null
1648 */
1649 public boolean containsKey(Object key) {
1650 return doGet(key) != null;
1651 }
1652
1653 /**
1654 * Returns the value to which the specified key is mapped,
1655 * or {@code null} if this map contains no mapping for the key.
1656 *
1657 * <p>More formally, if this map contains a mapping from a key
1658 * {@code k} to a value {@code v} such that {@code key} compares
1659 * equal to {@code k} according to the map's ordering, then this
1660 * method returns {@code v}; otherwise it returns {@code null}.
1661 * (There can be at most one such mapping.)
1662 *
1663 * @throws ClassCastException if the specified key cannot be compared
1664 * with the keys currently in the map
1665 * @throws NullPointerException if the specified key is null
1666 */
1667 public V get(Object key) {
1668 return doGet(key);
1669 }
1670
1671 /**
1672 * Associates the specified value with the specified key in this map.
1673 * If the map previously contained a mapping for the key, the old
1674 * value is replaced.
1675 *
1676 * @param key key with which the specified value is to be associated
1677 * @param value value to be associated with the specified key
1678 * @return the previous value associated with the specified key, or
1679 * <tt>null</tt> if there was no mapping for the key
1680 * @throws ClassCastException if the specified key cannot be compared
1681 * with the keys currently in the map
1682 * @throws NullPointerException if the specified key or value is null
1683 */
1684 public V put(K key, V value) {
1685 if (value == null)
1686 throw new NullPointerException();
1687 return doPut(key, value, false);
1688 }
1689
1690 /**
1691 * Removes the mapping for the specified key from this map if present.
1692 *
1693 * @param key key for which mapping should be removed
1694 * @return the previous value associated with the specified key, or
1695 * <tt>null</tt> if there was no mapping for the key
1696 * @throws ClassCastException if the specified key cannot be compared
1697 * with the keys currently in the map
1698 * @throws NullPointerException if the specified key is null
1699 */
1700 public V remove(Object key) {
1701 return doRemove(key, null);
1702 }
1703
1704 /**
1705 * Returns <tt>true</tt> if this map maps one or more keys to the
1706 * specified value. This operation requires time linear in the
1707 * map size.
1708 *
1709 * @param value value whose presence in this map is to be tested
1710 * @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
1711 * <tt>false</tt> otherwise
1712 * @throws NullPointerException if the specified value is null
1713 */
1714 public boolean containsValue(Object value) {
1715 if (value == null)
1716 throw new NullPointerException();
1717 for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1718 V v = n.getValidValue();
1719 if (v != null && value.equals(v))
1720 return true;
1721 }
1722 return false;
1723 }
1724
1725 /**
1726 * Returns the number of key-value mappings in this map. If this map
1727 * contains more than <tt>Integer.MAX_VALUE</tt> elements, it
1728 * returns <tt>Integer.MAX_VALUE</tt>.
1729 *
1730 * <p>Beware that, unlike in most collections, this method is
1731 * <em>NOT</em> a constant-time operation. Because of the
1732 * asynchronous nature of these maps, determining the current
1733 * number of elements requires traversing them all to count them.
1734 * Additionally, it is possible for the size to change during
1735 * execution of this method, in which case the returned result
1736 * will be inaccurate. Thus, this method is typically not very
1737 * useful in concurrent applications.
1738 *
1739 * @return the number of elements in this map
1740 */
1741 public int size() {
1742 long count = 0;
1743 for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1744 if (n.getValidValue() != null)
1745 ++count;
1746 }
1747 return (count >= Integer.MAX_VALUE)? Integer.MAX_VALUE : (int)count;
1748 }
1749
1750 /**
1751 * Returns <tt>true</tt> if this map contains no key-value mappings.
1752 * @return <tt>true</tt> if this map contains no key-value mappings
1753 */
1754 public boolean isEmpty() {
1755 return findFirst() == null;
1756 }
1757
1758 /**
1759 * Removes all of the mappings from this map.
1760 */
1761 public void clear() {
1762 initialize();
1763 }
1764
1765 /* ---------------- View methods -------------- */
1766
1767 /*
1768 * Note: Lazy initialization works for views because view classes
1769 * are stateless/immutable so it doesn't matter wrt correctness if
1770 * more than one is created (which will only rarely happen). Even
1771 * so, the following idiom conservatively ensures that the method
1772 * returns the one it created if it does so, not one created by
1773 * another racing thread.
1774 */
1775
1776 /**
1777 * Returns a {@link NavigableSet} view of the keys contained in this map.
1778 * The set's iterator returns the keys in ascending order.
1779 * The set is backed by the map, so changes to the map are
1780 * reflected in the set, and vice-versa. The set supports element
1781 * removal, which removes the corresponding mapping from the map,
1782 * via the {@code Iterator.remove}, {@code Set.remove},
1783 * {@code removeAll}, {@code retainAll}, and {@code clear}
1784 * operations. It does not support the {@code add} or {@code addAll}
1785 * operations.
1786 *
1787 * <p>The view's {@code iterator} is a "weakly consistent" iterator
1788 * that will never throw {@link ConcurrentModificationException},
1789 * and guarantees to traverse elements as they existed upon
1790 * construction of the iterator, and may (but is not guaranteed to)
1791 * reflect any modifications subsequent to construction.
1792 *
1793 * <p>This method is equivalent to method {@code navigableKeySet}.
1794 *
1795 * @return a navigable set view of the keys in this map
1796 */
1797 public NavigableSet<K> keySet() {
1798 KeySet ks = keySet;
1799 return (ks != null) ? ks : (keySet = new KeySet(this));
1800 }
1801
1802 public NavigableSet<K> navigableKeySet() {
1803 KeySet ks = keySet;
1804 return (ks != null) ? ks : (keySet = new KeySet(this));
1805 }
1806
1807 /**
1808 * Returns a {@link Collection} view of the values contained in this map.
1809 * The collection's iterator returns the values in ascending order
1810 * of the corresponding keys.
1811 * The collection is backed by the map, so changes to the map are
1812 * reflected in the collection, and vice-versa. The collection
1813 * supports element removal, which removes the corresponding
1814 * mapping from the map, via the <tt>Iterator.remove</tt>,
1815 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1816 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
1817 * support the <tt>add</tt> or <tt>addAll</tt> operations.
1818 *
1819 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1820 * that will never throw {@link ConcurrentModificationException},
1821 * and guarantees to traverse elements as they existed upon
1822 * construction of the iterator, and may (but is not guaranteed to)
1823 * reflect any modifications subsequent to construction.
1824 */
1825 public Collection<V> values() {
1826 Values vs = values;
1827 return (vs != null) ? vs : (values = new Values(this));
1828 }
1829
1830 /**
1831 * Returns a {@link Set} view of the mappings contained in this map.
1832 * The set's iterator returns the entries in ascending key order.
1833 * The set is backed by the map, so changes to the map are
1834 * reflected in the set, and vice-versa. The set supports element
1835 * removal, which removes the corresponding mapping from the map,
1836 * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1837 * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1838 * operations. It does not support the <tt>add</tt> or
1839 * <tt>addAll</tt> operations.
1840 *
1841 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1842 * that will never throw {@link ConcurrentModificationException},
1843 * and guarantees to traverse elements as they existed upon
1844 * construction of the iterator, and may (but is not guaranteed to)
1845 * reflect any modifications subsequent to construction.
1846 *
1847 * <p>The <tt>Map.Entry</tt> elements returned by
1848 * <tt>iterator.next()</tt> do <em>not</em> support the
1849 * <tt>setValue</tt> operation.
1850 *
1851 * @return a set view of the mappings contained in this map,
1852 * sorted in ascending key order
1853 */
1854 public Set<Map.Entry<K,V>> entrySet() {
1855 EntrySet es = entrySet;
1856 return (es != null) ? es : (entrySet = new EntrySet(this));
1857 }
1858
1859 public ConcurrentNavigableMap<K,V> descendingMap() {
1860 ConcurrentNavigableMap<K,V> dm = descendingMap;
1861 return (dm != null) ? dm : (descendingMap = new SubMap<K,V>
1862 (this, null, false, null, false, true));
1863 }
1864
1865 public NavigableSet<K> descendingKeySet() {
1866 return descendingMap().navigableKeySet();
1867 }
1868
1869 /* ---------------- AbstractMap Overrides -------------- */
1870
1871 /**
1872 * Compares the specified object with this map for equality.
1873 * Returns <tt>true</tt> if the given object is also a map and the
1874 * two maps represent the same mappings. More formally, two maps
1875 * <tt>m1</tt> and <tt>m2</tt> represent the same mappings if
1876 * <tt>m1.entrySet().equals(m2.entrySet())</tt>. This
1877 * operation may return misleading results if either map is
1878 * concurrently modified during execution of this method.
1879 *
1880 * @param o object to be compared for equality with this map
1881 * @return <tt>true</tt> if the specified object is equal to this map
1882 */
1883 public boolean equals(Object o) {
1884 if (o == this)
1885 return true;
1886 if (!(o instanceof Map))
1887 return false;
1888 Map<?,?> m = (Map<?,?>) o;
1889 try {
1890 for (Map.Entry<K,V> e : this.entrySet())
1891 if (! e.getValue().equals(m.get(e.getKey())))
1892 return false;
1893 for (Map.Entry<?,?> e : m.entrySet()) {
1894 Object k = e.getKey();
1895 Object v = e.getValue();
1896 if (k == null || v == null || !v.equals(get(k)))
1897 return false;
1898 }
1899 return true;
1900 } catch (ClassCastException unused) {
1901 return false;
1902 } catch (NullPointerException unused) {
1903 return false;
1904 }
1905 }
1906
1907 /* ------ ConcurrentMap API methods ------ */
1908
1909 /**
1910 * {@inheritDoc}
1911 *
1912 * @return the previous value associated with the specified key,
1913 * or <tt>null</tt> if there was no mapping for the key
1914 * @throws ClassCastException if the specified key cannot be compared
1915 * with the keys currently in the map
1916 * @throws NullPointerException if the specified key or value is null
1917 */
1918 public V putIfAbsent(K key, V value) {
1919 if (value == null)
1920 throw new NullPointerException();
1921 return doPut(key, value, true);
1922 }
1923
1924 /**
1925 * {@inheritDoc}
1926 *
1927 * @throws ClassCastException if the specified key cannot be compared
1928 * with the keys currently in the map
1929 * @throws NullPointerException if the specified key is null
1930 */
1931 public boolean remove(Object key, Object value) {
1932 if (key == null)
1933 throw new NullPointerException();
1934 if (value == null)
1935 return false;
1936 return doRemove(key, value) != null;
1937 }
1938
1939 /**
1940 * {@inheritDoc}
1941 *
1942 * @throws ClassCastException if the specified key cannot be compared
1943 * with the keys currently in the map
1944 * @throws NullPointerException if any of the arguments are null
1945 */
1946 public boolean replace(K key, V oldValue, V newValue) {
1947 if (oldValue == null || newValue == null)
1948 throw new NullPointerException();
1949 Comparable<? super K> k = comparable(key);
1950 for (;;) {
1951 Node<K,V> n = findNode(k);
1952 if (n == null)
1953 return false;
1954 Object v = n.value;
1955 if (v != null) {
1956 if (!oldValue.equals(v))
1957 return false;
1958 if (n.casValue(v, newValue))
1959 return true;
1960 }
1961 }
1962 }
1963
1964 /**
1965 * {@inheritDoc}
1966 *
1967 * @return the previous value associated with the specified key,
1968 * or <tt>null</tt> if there was no mapping for the key
1969 * @throws ClassCastException if the specified key cannot be compared
1970 * with the keys currently in the map
1971 * @throws NullPointerException if the specified key or value is null
1972 */
1973 public V replace(K key, V value) {
1974 if (value == null)
1975 throw new NullPointerException();
1976 Comparable<? super K> k = comparable(key);
1977 for (;;) {
1978 Node<K,V> n = findNode(k);
1979 if (n == null)
1980 return null;
1981 Object v = n.value;
1982 if (v != null && n.casValue(v, value))
1983 return (V)v;
1984 }
1985 }
1986
1987 /* ------ SortedMap API methods ------ */
1988
1989 public Comparator<? super K> comparator() {
1990 return comparator;
1991 }
1992
1993 /**
1994 * @throws NoSuchElementException {@inheritDoc}
1995 */
1996 public K firstKey() {
1997 Node<K,V> n = findFirst();
1998 if (n == null)
1999 throw new NoSuchElementException();
2000 return n.key;
2001 }
2002
2003 /**
2004 * @throws NoSuchElementException {@inheritDoc}
2005 */
2006 public K lastKey() {
2007 Node<K,V> n = findLast();
2008 if (n == null)
2009 throw new NoSuchElementException();
2010 return n.key;
2011 }
2012
2013 /**
2014 * @throws ClassCastException {@inheritDoc}
2015 * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
2016 * @throws IllegalArgumentException {@inheritDoc}
2017 */
2018 public ConcurrentNavigableMap<K,V> subMap(K fromKey,
2019 boolean fromInclusive,
2020 K toKey,
2021 boolean toInclusive) {
2022 if (fromKey == null || toKey == null)
2023 throw new NullPointerException();
2024 return new SubMap<K,V>
2025 (this, fromKey, fromInclusive, toKey, toInclusive, false);
2026 }
2027
2028 /**
2029 * @throws ClassCastException {@inheritDoc}
2030 * @throws NullPointerException if {@code toKey} is null
2031 * @throws IllegalArgumentException {@inheritDoc}
2032 */
2033 public ConcurrentNavigableMap<K,V> headMap(K toKey,
2034 boolean inclusive) {
2035 if (toKey == null)
2036 throw new NullPointerException();
2037 return new SubMap<K,V>
2038 (this, null, false, toKey, inclusive, false);
2039 }
2040
2041 /**
2042 * @throws ClassCastException {@inheritDoc}
2043 * @throws NullPointerException if {@code fromKey} is null
2044 * @throws IllegalArgumentException {@inheritDoc}
2045 */
2046 public ConcurrentNavigableMap<K,V> tailMap(K fromKey,
2047 boolean inclusive) {
2048 if (fromKey == null)
2049 throw new NullPointerException();
2050 return new SubMap<K,V>
2051 (this, fromKey, inclusive, null, false, false);
2052 }
2053
2054 /**
2055 * @throws ClassCastException {@inheritDoc}
2056 * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
2057 * @throws IllegalArgumentException {@inheritDoc}
2058 */
2059 public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
2060 return subMap(fromKey, true, toKey, false);
2061 }
2062
2063 /**
2064 * @throws ClassCastException {@inheritDoc}
2065 * @throws NullPointerException if {@code toKey} is null
2066 * @throws IllegalArgumentException {@inheritDoc}
2067 */
2068 public ConcurrentNavigableMap<K,V> headMap(K toKey) {
2069 return headMap(toKey, false);
2070 }
2071
2072 /**
2073 * @throws ClassCastException {@inheritDoc}
2074 * @throws NullPointerException if {@code fromKey} is null
2075 * @throws IllegalArgumentException {@inheritDoc}
2076 */
2077 public ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
2078 return tailMap(fromKey, true);
2079 }
2080
2081 /* ---------------- Relational operations -------------- */
2082
2083 /**
2084 * Returns a key-value mapping associated with the greatest key
2085 * strictly less than the given key, or <tt>null</tt> if there is
2086 * no such key. The returned entry does <em>not</em> support the
2087 * <tt>Entry.setValue</tt> method.
2088 *
2089 * @throws ClassCastException {@inheritDoc}
2090 * @throws NullPointerException if the specified key is null
2091 */
2092 public Map.Entry<K,V> lowerEntry(K key) {
2093 return getNear(key, LT);
2094 }
2095
2096 /**
2097 * @throws ClassCastException {@inheritDoc}
2098 * @throws NullPointerException if the specified key is null
2099 */
2100 public K lowerKey(K key) {
2101 Node<K,V> n = findNear(key, LT);
2102 return (n == null)? null : n.key;
2103 }
2104
2105 /**
2106 * Returns a key-value mapping associated with the greatest key
2107 * less than or equal to the given key, or <tt>null</tt> if there
2108 * is no such key. The returned entry does <em>not</em> support
2109 * the <tt>Entry.setValue</tt> method.
2110 *
2111 * @param key the key
2112 * @throws ClassCastException {@inheritDoc}
2113 * @throws NullPointerException if the specified key is null
2114 */
2115 public Map.Entry<K,V> floorEntry(K key) {
2116 return getNear(key, LT|EQ);
2117 }
2118
2119 /**
2120 * @param key the key
2121 * @throws ClassCastException {@inheritDoc}
2122 * @throws NullPointerException if the specified key is null
2123 */
2124 public K floorKey(K key) {
2125 Node<K,V> n = findNear(key, LT|EQ);
2126 return (n == null)? null : n.key;
2127 }
2128
2129 /**
2130 * Returns a key-value mapping associated with the least key
2131 * greater than or equal to the given key, or <tt>null</tt> if
2132 * there is no such entry. The returned entry does <em>not</em>
2133 * support the <tt>Entry.setValue</tt> method.
2134 *
2135 * @throws ClassCastException {@inheritDoc}
2136 * @throws NullPointerException if the specified key is null
2137 */
2138 public Map.Entry<K,V> ceilingEntry(K key) {
2139 return getNear(key, GT|EQ);
2140 }
2141
2142 /**
2143 * @throws ClassCastException {@inheritDoc}
2144 * @throws NullPointerException if the specified key is null
2145 */
2146 public K ceilingKey(K key) {
2147 Node<K,V> n = findNear(key, GT|EQ);
2148 return (n == null)? null : n.key;
2149 }
2150
2151 /**
2152 * Returns a key-value mapping associated with the least key
2153 * strictly greater than the given key, or <tt>null</tt> if there
2154 * is no such key. The returned entry does <em>not</em> support
2155 * the <tt>Entry.setValue</tt> method.
2156 *
2157 * @param key the key
2158 * @throws ClassCastException {@inheritDoc}
2159 * @throws NullPointerException if the specified key is null
2160 */
2161 public Map.Entry<K,V> higherEntry(K key) {
2162 return getNear(key, GT);
2163 }
2164
2165 /**
2166 * @param key the key
2167 * @throws ClassCastException {@inheritDoc}
2168 * @throws NullPointerException if the specified key is null
2169 */
2170 public K higherKey(K key) {
2171 Node<K,V> n = findNear(key, GT);
2172 return (n == null)? null : n.key;
2173 }
2174
2175 /**
2176 * Returns a key-value mapping associated with the least
2177 * key in this map, or <tt>null</tt> if the map is empty.
2178 * The returned entry does <em>not</em> support
2179 * the <tt>Entry.setValue</tt> method.
2180 */
2181 public Map.Entry<K,V> firstEntry() {
2182 for (;;) {
2183 Node<K,V> n = findFirst();
2184 if (n == null)
2185 return null;
2186 AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
2187 if (e != null)
2188 return e;
2189 }
2190 }
2191
2192 /**
2193 * Returns a key-value mapping associated with the greatest
2194 * key in this map, or <tt>null</tt> if the map is empty.
2195 * The returned entry does <em>not</em> support
2196 * the <tt>Entry.setValue</tt> method.
2197 */
2198 public Map.Entry<K,V> lastEntry() {
2199 for (;;) {
2200 Node<K,V> n = findLast();
2201 if (n == null)
2202 return null;
2203 AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
2204 if (e != null)
2205 return e;
2206 }
2207 }
2208
2209 /**
2210 * Removes and returns a key-value mapping associated with
2211 * the least key in this map, or <tt>null</tt> if the map is empty.
2212 * The returned entry does <em>not</em> support
2213 * the <tt>Entry.setValue</tt> method.
2214 */
2215 public Map.Entry<K,V> pollFirstEntry() {
2216 return doRemoveFirstEntry();
2217 }
2218
2219 /**
2220 * Removes and returns a key-value mapping associated with
2221 * the greatest key in this map, or <tt>null</tt> if the map is empty.
2222 * The returned entry does <em>not</em> support
2223 * the <tt>Entry.setValue</tt> method.
2224 */
2225 public Map.Entry<K,V> pollLastEntry() {
2226 return doRemoveLastEntry();
2227 }
2228
2229
2230 /* ---------------- Iterators -------------- */
2231
2232 /**
2233 * Base of iterator classes:
2234 */
2235 abstract class Iter<T> implements Iterator<T> {
2236 /** the last node returned by next() */
2237 Node<K,V> lastReturned;
2238 /** the next node to return from next(); */
2239 Node<K,V> next;
2240 /** Cache of next value field to maintain weak consistency */
2241 V nextValue;
2242
2243 /** Initializes ascending iterator for entire range. */
2244 Iter() {
2245 for (;;) {
2246 next = findFirst();
2247 if (next == null)
2248 break;
2249 Object x = next.value;
2250 if (x != null && x != next) {
2251 nextValue = (V) x;
2252 break;
2253 }
2254 }
2255 }
2256
2257 public final boolean hasNext() {
2258 return next != null;
2259 }
2260
2261 /** Advances next to higher entry. */
2262 final void advance() {
2263 if (next == null)
2264 throw new NoSuchElementException();
2265 lastReturned = next;
2266 for (;;) {
2267 next = next.next;
2268 if (next == null)
2269 break;
2270 Object x = next.value;
2271 if (x != null && x != next) {
2272 nextValue = (V) x;
2273 break;
2274 }
2275 }
2276 }
2277
2278 public void remove() {
2279 Node<K,V> l = lastReturned;
2280 if (l == null)
2281 throw new IllegalStateException();
2282 // It would not be worth all of the overhead to directly
2283 // unlink from here. Using remove is fast enough.
2284 ConcurrentSkipListMap.this.remove(l.key);
2285 lastReturned = null;
2286 }
2287
2288 }
2289
2290 final class ValueIterator extends Iter<V> {
2291 public V next() {
2292 V v = nextValue;
2293 advance();
2294 return v;
2295 }
2296 }
2297
2298 final class KeyIterator extends Iter<K> {
2299 public K next() {
2300 Node<K,V> n = next;
2301 advance();
2302 return n.key;
2303 }
2304 }
2305
2306 final class EntryIterator extends Iter<Map.Entry<K,V>> {
2307 public Map.Entry<K,V> next() {
2308 Node<K,V> n = next;
2309 V v = nextValue;
2310 advance();
2311 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
2312 }
2313 }
2314
2315 // Factory methods for iterators needed by ConcurrentSkipListSet etc
2316
2317 Iterator<K> keyIterator() {
2318 return new KeyIterator();
2319 }
2320
2321 Iterator<V> valueIterator() {
2322 return new ValueIterator();
2323 }
2324
2325 Iterator<Map.Entry<K,V>> entryIterator() {
2326 return new EntryIterator();
2327 }
2328
2329 /* ---------------- View Classes -------------- */
2330
2331 /*
2332 * View classes are static, delegating to a ConcurrentNavigableMap
2333 * to allow use by SubMaps, which outweighs the ugliness of
2334 * needing type-tests for Iterator methods.
2335 */
2336
2337 static final <E> List<E> toList(Collection<E> c) {
2338 // Using size() here would be a pessimization.
2339 List<E> list = new ArrayList<E>();
2340 for (E e : c)
2341 list.add(e);
2342 return list;
2343 }
2344
2345 static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
2346 private final ConcurrentNavigableMap<E,Object> m;
2347 KeySet(ConcurrentNavigableMap<E,Object> map) { m = map; }
2348 public int size() { return m.size(); }
2349 public boolean isEmpty() { return m.isEmpty(); }
2350 public boolean contains(Object o) { return m.containsKey(o); }
2351 public boolean remove(Object o) { return m.remove(o) != null; }
2352 public void clear() { m.clear(); }
2353 public E lower(E e) { return m.lowerKey(e); }
2354 public E floor(E e) { return m.floorKey(e); }
2355 public E ceiling(E e) { return m.ceilingKey(e); }
2356 public E higher(E e) { return m.higherKey(e); }
2357 public Comparator<? super E> comparator() { return m.comparator(); }
2358 public E first() { return m.firstKey(); }
2359 public E last() { return m.lastKey(); }
2360 public E pollFirst() {
2361 Map.Entry<E,Object> e = m.pollFirstEntry();
2362 return e == null? null : e.getKey();
2363 }
2364 public E pollLast() {
2365 Map.Entry<E,Object> e = m.pollLastEntry();
2366 return e == null? null : e.getKey();
2367 
Save This Page