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. Oracle designates this 7 * particular file as subject to the "Classpath" exception as provided 8 * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21 * or visit www.oracle.com if you need additional information or have any 22 * 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/publicdomain/zero/1.0/ 34 */ 35 36 package java.util.concurrent; 37 38 import java.io.Serializable; 39 import java.util.AbstractCollection; 40 import java.util.AbstractMap; 41 import java.util.AbstractSet; 42 import java.util.ArrayList; 43 import java.util.Collection; 44 import java.util.Collections; 45 import java.util.Comparator; 46 import java.util.Iterator; 47 import java.util.List; 48 import java.util.Map; 49 import java.util.NavigableMap; 50 import java.util.NavigableSet; 51 import java.util.NoSuchElementException; 52 import java.util.Set; 53 import java.util.SortedMap; 54 import java.util.Spliterator; 55 import java.util.function.BiConsumer; 56 import java.util.function.BiFunction; 57 import java.util.function.Consumer; 58 import java.util.function.Function; 59 import java.util.function.Predicate; 60 61 // BEGIN android-note 62 // removed link to collections framework docs 63 // END android-note 64 65 /** 66 * A scalable concurrent {@link ConcurrentNavigableMap} implementation. 67 * The map is sorted according to the {@linkplain Comparable natural 68 * ordering} of its keys, or by a {@link Comparator} provided at map 69 * creation time, depending on which constructor is used. 70 * 71 * <p>This class implements a concurrent variant of <a 72 * href="http://en.wikipedia.org/wiki/Skip_list" target="_top">SkipLists</a> 73 * providing expected average <i>log(n)</i> time cost for the 74 * {@code containsKey}, {@code get}, {@code put} and 75 * {@code remove} operations and their variants. Insertion, removal, 76 * update, and access operations safely execute concurrently by 77 * multiple threads. 78 * 79 * <p>Iterators and spliterators are 80 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 81 * 82 * <p>Ascending key ordered views and their iterators are faster than 83 * descending ones. 84 * 85 * <p>All {@code Map.Entry} pairs returned by methods in this class 86 * and its views represent snapshots of mappings at the time they were 87 * produced. They do <em>not</em> support the {@code Entry.setValue} 88 * method. (Note however that it is possible to change mappings in the 89 * associated map using {@code put}, {@code putIfAbsent}, or 90 * {@code replace}, depending on exactly which effect you need.) 91 * 92 * <p>Beware that, unlike in most collections, the {@code size} 93 * method is <em>not</em> a constant-time operation. Because of the 94 * asynchronous nature of these maps, determining the current number 95 * of elements requires a traversal of the elements, and so may report 96 * inaccurate results if this collection is modified during traversal. 97 * Additionally, the bulk operations {@code putAll}, {@code equals}, 98 * {@code toArray}, {@code containsValue}, and {@code clear} are 99 * <em>not</em> guaranteed to be performed atomically. For example, an 100 * iterator operating concurrently with a {@code putAll} operation 101 * might view only some of the added elements. 102 * 103 * <p>This class and its views and iterators implement all of the 104 * <em>optional</em> methods of the {@link Map} and {@link Iterator} 105 * interfaces. Like most other concurrent collections, this class does 106 * <em>not</em> permit the use of {@code null} keys or values because some 107 * null return values cannot be reliably distinguished from the absence of 108 * elements. 109 * 110 * @author Doug Lea 111 * @param <K> the type of keys maintained by this map 112 * @param <V> the type of mapped values 113 * @since 1.6 114 */ 115 public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V> 116 implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable { 117 /* 118 * This class implements a tree-like two-dimensionally linked skip 119 * list in which the index levels are represented in separate 120 * nodes from the base nodes holding data. There are two reasons 121 * for taking this approach instead of the usual array-based 122 * structure: 1) Array based implementations seem to encounter 123 * more complexity and overhead 2) We can use cheaper algorithms 124 * for the heavily-traversed index lists than can be used for the 125 * base lists. Here's a picture of some of the basics for a 126 * possible list with 2 levels of index: 127 * 128 * Head nodes Index nodes 129 * +-+ right +-+ +-+ 130 * |2|---------------->| |--------------------->| |->null 131 * +-+ +-+ +-+ 132 * | down | | 133 * v v v 134 * +-+ +-+ +-+ +-+ +-+ +-+ 135 * |1|----------->| |->| |------>| |----------->| |------>| |->null 136 * +-+ +-+ +-+ +-+ +-+ +-+ 137 * v | | | | | 138 * Nodes next v v v v v 139 * +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ 140 * | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null 141 * +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ 142 * 143 * The base lists use a variant of the HM linked ordered set 144 * algorithm. See Tim Harris, "A pragmatic implementation of 145 * non-blocking linked lists" 146 * http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged 147 * Michael "High Performance Dynamic Lock-Free Hash Tables and 148 * List-Based Sets" 149 * http://www.research.ibm.com/people/m/michael/pubs.htm. The 150 * basic idea in these lists is to mark the "next" pointers of 151 * deleted nodes when deleting to avoid conflicts with concurrent 152 * insertions, and when traversing to keep track of triples 153 * (predecessor, node, successor) in order to detect when and how 154 * to unlink these deleted nodes. 155 * 156 * Rather than using mark-bits to mark list deletions (which can 157 * be slow and space-intensive using AtomicMarkedReference), nodes 158 * use direct CAS'able next pointers. On deletion, instead of 159 * marking a pointer, they splice in another node that can be 160 * thought of as standing for a marked pointer (indicating this by 161 * using otherwise impossible field values). Using plain nodes 162 * acts roughly like "boxed" implementations of marked pointers, 163 * but uses new nodes only when nodes are deleted, not for every 164 * link. This requires less space and supports faster 165 * traversal. Even if marked references were better supported by 166 * JVMs, traversal using this technique might still be faster 167 * because any search need only read ahead one more node than 168 * otherwise required (to check for trailing marker) rather than 169 * unmasking mark bits or whatever on each read. 170 * 171 * This approach maintains the essential property needed in the HM 172 * algorithm of changing the next-pointer of a deleted node so 173 * that any other CAS of it will fail, but implements the idea by 174 * changing the pointer to point to a different node, not by 175 * marking it. While it would be possible to further squeeze 176 * space by defining marker nodes not to have key/value fields, it 177 * isn't worth the extra type-testing overhead. The deletion 178 * markers are rarely encountered during traversal and are 179 * normally quickly garbage collected. (Note that this technique 180 * would not work well in systems without garbage collection.) 181 * 182 * In addition to using deletion markers, the lists also use 183 * nullness of value fields to indicate deletion, in a style 184 * similar to typical lazy-deletion schemes. If a node's value is 185 * null, then it is considered logically deleted and ignored even 186 * though it is still reachable. This maintains proper control of 187 * concurrent replace vs delete operations -- an attempted replace 188 * must fail if a delete beat it by nulling field, and a delete 189 * must return the last non-null value held in the field. (Note: 190 * Null, rather than some special marker, is used for value fields 191 * here because it just so happens to mesh with the Map API 192 * requirement that method get returns null if there is no 193 * mapping, which allows nodes to remain concurrently readable 194 * even when deleted. Using any other marker value here would be 195 * messy at best.) 196 * 197 * Here's the sequence of events for a deletion of node n with 198 * predecessor b and successor f, initially: 199 * 200 * +------+ +------+ +------+ 201 * ... | b |------>| n |----->| f | ... 202 * +------+ +------+ +------+ 203 * 204 * 1. CAS n's value field from non-null to null. 205 * From this point on, no public operations encountering 206 * the node consider this mapping to exist. However, other 207 * ongoing insertions and deletions might still modify 208 * n's next pointer. 209 * 210 * 2. CAS n's next pointer to point to a new marker node. 211 * From this point on, no other nodes can be appended to n. 212 * which avoids deletion errors in CAS-based linked lists. 213 * 214 * +------+ +------+ +------+ +------+ 215 * ... | b |------>| n |----->|marker|------>| f | ... 216 * +------+ +------+ +------+ +------+ 217 * 218 * 3. CAS b's next pointer over both n and its marker. 219 * From this point on, no new traversals will encounter n, 220 * and it can eventually be GCed. 221 * +------+ +------+ 222 * ... | b |----------------------------------->| f | ... 223 * +------+ +------+ 224 * 225 * A failure at step 1 leads to simple retry due to a lost race 226 * with another operation. Steps 2-3 can fail because some other 227 * thread noticed during a traversal a node with null value and 228 * helped out by marking and/or unlinking. This helping-out 229 * ensures that no thread can become stuck waiting for progress of 230 * the deleting thread. The use of marker nodes slightly 231 * complicates helping-out code because traversals must track 232 * consistent reads of up to four nodes (b, n, marker, f), not 233 * just (b, n, f), although the next field of a marker is 234 * immutable, and once a next field is CAS'ed to point to a 235 * marker, it never again changes, so this requires less care. 236 * 237 * Skip lists add indexing to this scheme, so that the base-level 238 * traversals start close to the locations being found, inserted 239 * or deleted -- usually base level traversals only traverse a few 240 * nodes. This doesn't change the basic algorithm except for the 241 * need to make sure base traversals start at predecessors (here, 242 * b) that are not (structurally) deleted, otherwise retrying 243 * after processing the deletion. 244 * 245 * Index levels are maintained as lists with volatile next fields, 246 * using CAS to link and unlink. Races are allowed in index-list 247 * operations that can (rarely) fail to link in a new index node 248 * or delete one. (We can't do this of course for data nodes.) 249 * However, even when this happens, the index lists remain sorted, 250 * so correctly serve as indices. This can impact performance, 251 * but since skip lists are probabilistic anyway, the net result 252 * is that under contention, the effective "p" value may be lower 253 * than its nominal value. And race windows are kept small enough 254 * that in practice these failures are rare, even under a lot of 255 * contention. 256 * 257 * The fact that retries (for both base and index lists) are 258 * relatively cheap due to indexing allows some minor 259 * simplifications of retry logic. Traversal restarts are 260 * performed after most "helping-out" CASes. This isn't always 261 * strictly necessary, but the implicit backoffs tend to help 262 * reduce other downstream failed CAS's enough to outweigh restart 263 * cost. This worsens the worst case, but seems to improve even 264 * highly contended cases. 265 * 266 * Unlike most skip-list implementations, index insertion and 267 * deletion here require a separate traversal pass occurring after 268 * the base-level action, to add or remove index nodes. This adds 269 * to single-threaded overhead, but improves contended 270 * multithreaded performance by narrowing interference windows, 271 * and allows deletion to ensure that all index nodes will be made 272 * unreachable upon return from a public remove operation, thus 273 * avoiding unwanted garbage retention. This is more important 274 * here than in some other data structures because we cannot null 275 * out node fields referencing user keys since they might still be 276 * read by other ongoing traversals. 277 * 278 * Indexing uses skip list parameters that maintain good search 279 * performance while using sparser-than-usual indices: The 280 * hardwired parameters k=1, p=0.5 (see method doPut) mean 281 * that about one-quarter of the nodes have indices. Of those that 282 * do, half have one level, a quarter have two, and so on (see 283 * Pugh's Skip List Cookbook, sec 3.4). The expected total space 284 * requirement for a map is slightly less than for the current 285 * implementation of java.util.TreeMap. 286 * 287 * Changing the level of the index (i.e, the height of the 288 * tree-like structure) also uses CAS. The head index has initial 289 * level/height of one. Creation of an index with height greater 290 * than the current level adds a level to the head index by 291 * CAS'ing on a new top-most head. To maintain good performance 292 * after a lot of removals, deletion methods heuristically try to 293 * reduce the height if the topmost levels appear to be empty. 294 * This may encounter races in which it possible (but rare) to 295 * reduce and "lose" a level just as it is about to contain an 296 * index (that will then never be encountered). This does no 297 * structural harm, and in practice appears to be a better option 298 * than allowing unrestrained growth of levels. 299 * 300 * The code for all this is more verbose than you'd like. Most 301 * operations entail locating an element (or position to insert an 302 * element). The code to do this can't be nicely factored out 303 * because subsequent uses require a snapshot of predecessor 304 * and/or successor and/or value fields which can't be returned 305 * all at once, at least not without creating yet another object 306 * to hold them -- creating such little objects is an especially 307 * bad idea for basic internal search operations because it adds 308 * to GC overhead. (This is one of the few times I've wished Java 309 * had macros.) Instead, some traversal code is interleaved within 310 * insertion and removal operations. The control logic to handle 311 * all the retry conditions is sometimes twisty. Most search is 312 * broken into 2 parts. findPredecessor() searches index nodes 313 * only, returning a base-level predecessor of the key. findNode() 314 * finishes out the base-level search. Even with this factoring, 315 * there is a fair amount of near-duplication of code to handle 316 * variants. 317 * 318 * To produce random values without interference across threads, 319 * we use within-JDK thread local random support (via the 320 * "secondary seed", to avoid interference with user-level 321 * ThreadLocalRandom.) 322 * 323 * A previous version of this class wrapped non-comparable keys 324 * with their comparators to emulate Comparables when using 325 * comparators vs Comparables. However, JVMs now appear to better 326 * handle infusing comparator-vs-comparable choice into search 327 * loops. Static method cpr(comparator, x, y) is used for all 328 * comparisons, which works well as long as the comparator 329 * argument is set up outside of loops (thus sometimes passed as 330 * an argument to internal methods) to avoid field re-reads. 331 * 332 * For explanation of algorithms sharing at least a couple of 333 * features with this one, see Mikhail Fomitchev's thesis 334 * (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis 335 * (http://www.cl.cam.ac.uk/users/kaf24/), and Hakan Sundell's 336 * thesis (http://www.cs.chalmers.se/~phs/). 337 * 338 * Given the use of tree-like index nodes, you might wonder why 339 * this doesn't use some kind of search tree instead, which would 340 * support somewhat faster search operations. The reason is that 341 * there are no known efficient lock-free insertion and deletion 342 * algorithms for search trees. The immutability of the "down" 343 * links of index nodes (as opposed to mutable "left" fields in 344 * true trees) makes this tractable using only CAS operations. 345 * 346 * Notation guide for local variables 347 * Node: b, n, f for predecessor, node, successor 348 * Index: q, r, d for index node, right, down. 349 * t for another index node 350 * Head: h 351 * Levels: j 352 * Keys: k, key 353 * Values: v, value 354 * Comparisons: c 355 */ 356 357 private static final long serialVersionUID = -8627078645895051609L; 358 359 /** 360 * Special value used to identify base-level header. 361 */ 362 static final Object BASE_HEADER = new Object(); 363 364 /** 365 * The topmost head index of the skiplist. 366 */ 367 private transient volatile HeadIndex<K,V> head; 368 369 /** 370 * The comparator used to maintain order in this map, or null if 371 * using natural ordering. (Non-private to simplify access in 372 * nested classes.) 373 * @serial 374 */ 375 final Comparator<? super K> comparator; 376 377 /** Lazily initialized key set */ 378 private transient KeySet<K,V> keySet; 379 /** Lazily initialized entry set */ 380 private transient EntrySet<K,V> entrySet; 381 /** Lazily initialized values collection */ 382 private transient Values<K,V> values; 383 /** Lazily initialized descending key set */ 384 private transient ConcurrentNavigableMap<K,V> descendingMap; 385 386 /** 387 * Initializes or resets state. Needed by constructors, clone, 388 * clear, readObject. and ConcurrentSkipListSet.clone. 389 * (Note that comparator must be separately initialized.) 390 */ initialize()391 private void initialize() { 392 keySet = null; 393 entrySet = null; 394 values = null; 395 descendingMap = null; 396 head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null), 397 null, null, 1); 398 } 399 400 /** 401 * compareAndSet head node. 402 */ casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val)403 private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) { 404 return U.compareAndSwapObject(this, HEAD, cmp, val); 405 } 406 407 /* ---------------- Nodes -------------- */ 408 409 /** 410 * Nodes hold keys and values, and are singly linked in sorted 411 * order, possibly with some intervening marker nodes. The list is 412 * headed by a dummy node accessible as head.node. The value field 413 * is declared only as Object because it takes special non-V 414 * values for marker and header nodes. 415 */ 416 static final class Node<K,V> { 417 final K key; 418 volatile Object value; 419 volatile Node<K,V> next; 420 421 /** 422 * Creates a new regular node. 423 */ Node(K key, Object value, Node<K,V> next)424 Node(K key, Object value, Node<K,V> next) { 425 this.key = key; 426 this.value = value; 427 this.next = next; 428 } 429 430 /** 431 * Creates a new marker node. A marker is distinguished by 432 * having its value field point to itself. Marker nodes also 433 * have null keys, a fact that is exploited in a few places, 434 * but this doesn't distinguish markers from the base-level 435 * header node (head.node), which also has a null key. 436 */ Node(Node<K,V> next)437 Node(Node<K,V> next) { 438 this.key = null; 439 this.value = this; 440 this.next = next; 441 } 442 443 /** 444 * compareAndSet value field. 445 */ casValue(Object cmp, Object val)446 boolean casValue(Object cmp, Object val) { 447 return U.compareAndSwapObject(this, VALUE, cmp, val); 448 } 449 450 /** 451 * compareAndSet next field. 452 */ casNext(Node<K,V> cmp, Node<K,V> val)453 boolean casNext(Node<K,V> cmp, Node<K,V> val) { 454 return U.compareAndSwapObject(this, NEXT, cmp, val); 455 } 456 457 /** 458 * Returns true if this node is a marker. This method isn't 459 * actually called in any current code checking for markers 460 * because callers will have already read value field and need 461 * to use that read (not another done here) and so directly 462 * test if value points to node. 463 * 464 * @return true if this node is a marker node 465 */ isMarker()466 boolean isMarker() { 467 return value == this; 468 } 469 470 /** 471 * Returns true if this node is the header of base-level list. 472 * @return true if this node is header node 473 */ isBaseHeader()474 boolean isBaseHeader() { 475 return value == BASE_HEADER; 476 } 477 478 /** 479 * Tries to append a deletion marker to this node. 480 * @param f the assumed current successor of this node 481 * @return true if successful 482 */ appendMarker(Node<K,V> f)483 boolean appendMarker(Node<K,V> f) { 484 return casNext(f, new Node<K,V>(f)); 485 } 486 487 /** 488 * Helps out a deletion by appending marker or unlinking from 489 * predecessor. This is called during traversals when value 490 * field seen to be null. 491 * @param b predecessor 492 * @param f successor 493 */ helpDelete(Node<K,V> b, Node<K,V> f)494 void helpDelete(Node<K,V> b, Node<K,V> f) { 495 /* 496 * Rechecking links and then doing only one of the 497 * help-out stages per call tends to minimize CAS 498 * interference among helping threads. 499 */ 500 if (f == next && this == b.next) { 501 if (f == null || f.value != f) // not already marked 502 casNext(f, new Node<K,V>(f)); 503 else 504 b.casNext(this, f.next); 505 } 506 } 507 508 /** 509 * Returns value if this node contains a valid key-value pair, 510 * else null. 511 * @return this node's value if it isn't a marker or header or 512 * is deleted, else null 513 */ getValidValue()514 V getValidValue() { 515 Object v = value; 516 if (v == this || v == BASE_HEADER) 517 return null; 518 @SuppressWarnings("unchecked") V vv = (V)v; 519 return vv; 520 } 521 522 /** 523 * Creates and returns a new SimpleImmutableEntry holding current 524 * mapping if this node holds a valid value, else null. 525 * @return new entry or null 526 */ createSnapshot()527 AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() { 528 Object v = value; 529 if (v == null || v == this || v == BASE_HEADER) 530 return null; 531 @SuppressWarnings("unchecked") V vv = (V)v; 532 return new AbstractMap.SimpleImmutableEntry<K,V>(key, vv); 533 } 534 535 // Unsafe mechanics 536 537 private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 538 private static final long VALUE; 539 private static final long NEXT; 540 541 static { 542 try { 543 VALUE = U.objectFieldOffset 544 (Node.class.getDeclaredField("value")); 545 NEXT = U.objectFieldOffset 546 (Node.class.getDeclaredField("next")); 547 } catch (ReflectiveOperationException e) { 548 throw new Error(e); 549 } 550 } 551 } 552 553 /* ---------------- Indexing -------------- */ 554 555 /** 556 * Index nodes represent the levels of the skip list. Note that 557 * even though both Nodes and Indexes have forward-pointing 558 * fields, they have different types and are handled in different 559 * ways, that can't nicely be captured by placing field in a 560 * shared abstract class. 561 */ 562 static class Index<K,V> { 563 final Node<K,V> node; 564 final Index<K,V> down; 565 volatile Index<K,V> right; 566 567 /** 568 * Creates index node with given values. 569 */ Index(Node<K,V> node, Index<K,V> down, Index<K,V> right)570 Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) { 571 this.node = node; 572 this.down = down; 573 this.right = right; 574 } 575 576 /** 577 * compareAndSet right field. 578 */ casRight(Index<K,V> cmp, Index<K,V> val)579 final boolean casRight(Index<K,V> cmp, Index<K,V> val) { 580 return U.compareAndSwapObject(this, RIGHT, cmp, val); 581 } 582 583 /** 584 * Returns true if the node this indexes has been deleted. 585 * @return true if indexed node is known to be deleted 586 */ indexesDeletedNode()587 final boolean indexesDeletedNode() { 588 return node.value == null; 589 } 590 591 /** 592 * Tries to CAS newSucc as successor. To minimize races with 593 * unlink that may lose this index node, if the node being 594 * indexed is known to be deleted, it doesn't try to link in. 595 * @param succ the expected current successor 596 * @param newSucc the new successor 597 * @return true if successful 598 */ link(Index<K,V> succ, Index<K,V> newSucc)599 final boolean link(Index<K,V> succ, Index<K,V> newSucc) { 600 Node<K,V> n = node; 601 newSucc.right = succ; 602 return n.value != null && casRight(succ, newSucc); 603 } 604 605 /** 606 * Tries to CAS right field to skip over apparent successor 607 * succ. Fails (forcing a retraversal by caller) if this node 608 * is known to be deleted. 609 * @param succ the expected current successor 610 * @return true if successful 611 */ unlink(Index<K,V> succ)612 final boolean unlink(Index<K,V> succ) { 613 return node.value != null && casRight(succ, succ.right); 614 } 615 616 // Unsafe mechanics 617 private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 618 private static final long RIGHT; 619 static { 620 try { 621 RIGHT = U.objectFieldOffset 622 (Index.class.getDeclaredField("right")); 623 } catch (ReflectiveOperationException e) { 624 throw new Error(e); 625 } 626 } 627 } 628 629 /* ---------------- Head nodes -------------- */ 630 631 /** 632 * Nodes heading each level keep track of their level. 633 */ 634 static final class HeadIndex<K,V> extends Index<K,V> { 635 final int level; HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level)636 HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) { 637 super(node, down, right); 638 this.level = level; 639 } 640 } 641 642 /* ---------------- Comparison utilities -------------- */ 643 644 /** 645 * Compares using comparator or natural ordering if null. 646 * Called only by methods that have performed required type checks. 647 */ 648 @SuppressWarnings({"unchecked", "rawtypes"}) cpr(Comparator c, Object x, Object y)649 static final int cpr(Comparator c, Object x, Object y) { 650 return (c != null) ? c.compare(x, y) : ((Comparable)x).compareTo(y); 651 } 652 653 /* ---------------- Traversal -------------- */ 654 655 /** 656 * Returns a base-level node with key strictly less than given key, 657 * or the base-level header if there is no such node. Also 658 * unlinks indexes to deleted nodes found along the way. Callers 659 * rely on this side-effect of clearing indices to deleted nodes. 660 * @param key the key 661 * @return a predecessor of key 662 */ findPredecessor(Object key, Comparator<? super K> cmp)663 private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) { 664 if (key == null) 665 throw new NullPointerException(); // don't postpone errors 666 for (;;) { 667 for (Index<K,V> q = head, r = q.right, d;;) { 668 if (r != null) { 669 Node<K,V> n = r.node; 670 K k = n.key; 671 if (n.value == null) { 672 if (!q.unlink(r)) 673 break; // restart 674 r = q.right; // reread r 675 continue; 676 } 677 if (cpr(cmp, key, k) > 0) { 678 q = r; 679 r = r.right; 680 continue; 681 } 682 } 683 if ((d = q.down) == null) 684 return q.node; 685 q = d; 686 r = d.right; 687 } 688 } 689 } 690 691 /** 692 * Returns node holding key or null if no such, clearing out any 693 * deleted nodes seen along the way. Repeatedly traverses at 694 * base-level looking for key starting at predecessor returned 695 * from findPredecessor, processing base-level deletions as 696 * encountered. Some callers rely on this side-effect of clearing 697 * deleted nodes. 698 * 699 * Restarts occur, at traversal step centered on node n, if: 700 * 701 * (1) After reading n's next field, n is no longer assumed 702 * predecessor b's current successor, which means that 703 * we don't have a consistent 3-node snapshot and so cannot 704 * unlink any subsequent deleted nodes encountered. 705 * 706 * (2) n's value field is null, indicating n is deleted, in 707 * which case we help out an ongoing structural deletion 708 * before retrying. Even though there are cases where such 709 * unlinking doesn't require restart, they aren't sorted out 710 * here because doing so would not usually outweigh cost of 711 * restarting. 712 * 713 * (3) n is a marker or n's predecessor's value field is null, 714 * indicating (among other possibilities) that 715 * findPredecessor returned a deleted node. We can't unlink 716 * the node because we don't know its predecessor, so rely 717 * on another call to findPredecessor to notice and return 718 * some earlier predecessor, which it will do. This check is 719 * only strictly needed at beginning of loop, (and the 720 * b.value check isn't strictly needed at all) but is done 721 * each iteration to help avoid contention with other 722 * threads by callers that will fail to be able to change 723 * links, and so will retry anyway. 724 * 725 * The traversal loops in doPut, doRemove, and findNear all 726 * include the same three kinds of checks. And specialized 727 * versions appear in findFirst, and findLast and their variants. 728 * They can't easily share code because each uses the reads of 729 * fields held in locals occurring in the orders they were 730 * performed. 731 * 732 * @param key the key 733 * @return node holding key, or null if no such 734 */ findNode(Object key)735 private Node<K,V> findNode(Object key) { 736 if (key == null) 737 throw new NullPointerException(); // don't postpone errors 738 Comparator<? super K> cmp = comparator; 739 outer: for (;;) { 740 for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) { 741 Object v; int c; 742 if (n == null) 743 break outer; 744 Node<K,V> f = n.next; 745 if (n != b.next) // inconsistent read 746 break; 747 if ((v = n.value) == null) { // n is deleted 748 n.helpDelete(b, f); 749 break; 750 } 751 if (b.value == null || v == n) // b is deleted 752 break; 753 if ((c = cpr(cmp, key, n.key)) == 0) 754 return n; 755 if (c < 0) 756 break outer; 757 b = n; 758 n = f; 759 } 760 } 761 return null; 762 } 763 764 /** 765 * Gets value for key. Almost the same as findNode, but returns 766 * the found value (to avoid retries during re-reads) 767 * 768 * @param key the key 769 * @return the value, or null if absent 770 */ doGet(Object key)771 private V doGet(Object key) { 772 if (key == null) 773 throw new NullPointerException(); 774 Comparator<? super K> cmp = comparator; 775 outer: for (;;) { 776 for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) { 777 Object v; int c; 778 if (n == null) 779 break outer; 780 Node<K,V> f = n.next; 781 if (n != b.next) // inconsistent read 782 break; 783 if ((v = n.value) == null) { // n is deleted 784 n.helpDelete(b, f); 785 break; 786 } 787 if (b.value == null || v == n) // b is deleted 788 break; 789 if ((c = cpr(cmp, key, n.key)) == 0) { 790 @SuppressWarnings("unchecked") V vv = (V)v; 791 return vv; 792 } 793 if (c < 0) 794 break outer; 795 b = n; 796 n = f; 797 } 798 } 799 return null; 800 } 801 802 /* ---------------- Insertion -------------- */ 803 804 /** 805 * Main insertion method. Adds element if not present, or 806 * replaces value if present and onlyIfAbsent is false. 807 * @param key the key 808 * @param value the value that must be associated with key 809 * @param onlyIfAbsent if should not insert if already present 810 * @return the old value, or null if newly inserted 811 */ doPut(K key, V value, boolean onlyIfAbsent)812 private V doPut(K key, V value, boolean onlyIfAbsent) { 813 Node<K,V> z; // added node 814 if (key == null) 815 throw new NullPointerException(); 816 Comparator<? super K> cmp = comparator; 817 outer: for (;;) { 818 for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) { 819 if (n != null) { 820 Object v; int c; 821 Node<K,V> f = n.next; 822 if (n != b.next) // inconsistent read 823 break; 824 if ((v = n.value) == null) { // n is deleted 825 n.helpDelete(b, f); 826 break; 827 } 828 if (b.value == null || v == n) // b is deleted 829 break; 830 if ((c = cpr(cmp, key, n.key)) > 0) { 831 b = n; 832 n = f; 833 continue; 834 } 835 if (c == 0) { 836 if (onlyIfAbsent || n.casValue(v, value)) { 837 @SuppressWarnings("unchecked") V vv = (V)v; 838 return vv; 839 } 840 break; // restart if lost race to replace value 841 } 842 // else c < 0; fall through 843 } 844 845 z = new Node<K,V>(key, value, n); 846 if (!b.casNext(n, z)) 847 break; // restart if lost race to append to b 848 break outer; 849 } 850 } 851 852 int rnd = ThreadLocalRandom.nextSecondarySeed(); 853 if ((rnd & 0x80000001) == 0) { // test highest and lowest bits 854 int level = 1, max; 855 while (((rnd >>>= 1) & 1) != 0) 856 ++level; 857 Index<K,V> idx = null; 858 HeadIndex<K,V> h = head; 859 if (level <= (max = h.level)) { 860 for (int i = 1; i <= level; ++i) 861 idx = new Index<K,V>(z, idx, null); 862 } 863 else { // try to grow by one level 864 level = max + 1; // hold in array and later pick the one to use 865 @SuppressWarnings("unchecked")Index<K,V>[] idxs = 866 (Index<K,V>[])new Index<?,?>[level+1]; 867 for (int i = 1; i <= level; ++i) 868 idxs[i] = idx = new Index<K,V>(z, idx, null); 869 for (;;) { 870 h = head; 871 int oldLevel = h.level; 872 if (level <= oldLevel) // lost race to add level 873 break; 874 HeadIndex<K,V> newh = h; 875 Node<K,V> oldbase = h.node; 876 for (int j = oldLevel+1; j <= level; ++j) 877 newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j); 878 if (casHead(h, newh)) { 879 h = newh; 880 idx = idxs[level = oldLevel]; 881 break; 882 } 883 } 884 } 885 // find insertion points and splice in 886 splice: for (int insertionLevel = level;;) { 887 int j = h.level; 888 for (Index<K,V> q = h, r = q.right, t = idx;;) { 889 if (q == null || t == null) 890 break splice; 891 if (r != null) { 892 Node<K,V> n = r.node; 893 // compare before deletion check avoids needing recheck 894 int c = cpr(cmp, key, n.key); 895 if (n.value == null) { 896 if (!q.unlink(r)) 897 break; 898 r = q.right; 899 continue; 900 } 901 if (c > 0) { 902 q = r; 903 r = r.right; 904 continue; 905 } 906 } 907 908 if (j == insertionLevel) { 909 if (!q.link(r, t)) 910 break; // restart 911 if (t.node.value == null) { 912 findNode(key); 913 break splice; 914 } 915 if (--insertionLevel == 0) 916 break splice; 917 } 918 919 if (--j >= insertionLevel && j < level) 920 t = t.down; 921 q = q.down; 922 r = q.right; 923 } 924 } 925 } 926 return null; 927 } 928 929 /* ---------------- Deletion -------------- */ 930 931 /** 932 * Main deletion method. Locates node, nulls value, appends a 933 * deletion marker, unlinks predecessor, removes associated index 934 * nodes, and possibly reduces head index level. 935 * 936 * Index nodes are cleared out simply by calling findPredecessor. 937 * which unlinks indexes to deleted nodes found along path to key, 938 * which will include the indexes to this node. This is done 939 * unconditionally. We can't check beforehand whether there are 940 * index nodes because it might be the case that some or all 941 * indexes hadn't been inserted yet for this node during initial 942 * search for it, and we'd like to ensure lack of garbage 943 * retention, so must call to be sure. 944 * 945 * @param key the key 946 * @param value if non-null, the value that must be 947 * associated with key 948 * @return the node, or null if not found 949 */ doRemove(Object key, Object value)950 final V doRemove(Object key, Object value) { 951 if (key == null) 952 throw new NullPointerException(); 953 Comparator<? super K> cmp = comparator; 954 outer: for (;;) { 955 for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) { 956 Object v; int c; 957 if (n == null) 958 break outer; 959 Node<K,V> f = n.next; 960 if (n != b.next) // inconsistent read 961 break; 962 if ((v = n.value) == null) { // n is deleted 963 n.helpDelete(b, f); 964 break; 965 } 966 if (b.value == null || v == n) // b is deleted 967 break; 968 if ((c = cpr(cmp, key, n.key)) < 0) 969 break outer; 970 if (c > 0) { 971 b = n; 972 n = f; 973 continue; 974 } 975 if (value != null && !value.equals(v)) 976 break outer; 977 if (!n.casValue(v, null)) 978 break; 979 if (!n.appendMarker(f) || !b.casNext(n, f)) 980 findNode(key); // retry via findNode 981 else { 982 findPredecessor(key, cmp); // clean index 983 if (head.right == null) 984 tryReduceLevel(); 985 } 986 @SuppressWarnings("unchecked") V vv = (V)v; 987 return vv; 988 } 989 } 990 return null; 991 } 992 993 /** 994 * Possibly reduce head level if it has no nodes. This method can 995 * (rarely) make mistakes, in which case levels can disappear even 996 * though they are about to contain index nodes. This impacts 997 * performance, not correctness. To minimize mistakes as well as 998 * to reduce hysteresis, the level is reduced by one only if the 999 * topmost three levels look empty. Also, if the removed level 1000 * looks non-empty after CAS, we try to change it back quick 1001 * before anyone notices our mistake! (This trick works pretty 1002 * well because this method will practically never make mistakes 1003 * unless current thread stalls immediately before first CAS, in 1004 * which case it is very unlikely to stall again immediately 1005 * afterwards, so will recover.) 1006 * 1007 * We put up with all this rather than just let levels grow 1008 * because otherwise, even a small map that has undergone a large 1009 * number of insertions and removals will have a lot of levels, 1010 * slowing down access more than would an occasional unwanted 1011 * reduction. 1012 */ tryReduceLevel()1013 private void tryReduceLevel() { 1014 HeadIndex<K,V> h = head; 1015 HeadIndex<K,V> d; 1016 HeadIndex<K,V> e; 1017 if (h.level > 3 && 1018 (d = (HeadIndex<K,V>)h.down) != null && 1019 (e = (HeadIndex<K,V>)d.down) != null && 1020 e.right == null && 1021 d.right == null && 1022 h.right == null && 1023 casHead(h, d) && // try to set 1024 h.right != null) // recheck 1025 casHead(d, h); // try to backout 1026 } 1027 1028 /* ---------------- Finding and removing first element -------------- */ 1029 1030 /** 1031 * Specialized variant of findNode to get first valid node. 1032 * @return first node or null if empty 1033 */ findFirst()1034 final Node<K,V> findFirst() { 1035 for (Node<K,V> b, n;;) { 1036 if ((n = (b = head.node).next) == null) 1037 return null; 1038 if (n.value != null) 1039 return n; 1040 n.helpDelete(b, n.next); 1041 } 1042 } 1043 1044 /** 1045 * Removes first entry; returns its snapshot. 1046 * @return null if empty, else snapshot of first entry 1047 */ doRemoveFirstEntry()1048 private Map.Entry<K,V> doRemoveFirstEntry() { 1049 for (Node<K,V> b, n;;) { 1050 if ((n = (b = head.node).next) == null) 1051 return null; 1052 Node<K,V> f = n.next; 1053 if (n != b.next) 1054 continue; 1055 Object v = n.value; 1056 if (v == null) { 1057 n.helpDelete(b, f); 1058 continue; 1059 } 1060 if (!n.casValue(v, null)) 1061 continue; 1062 if (!n.appendMarker(f) || !b.casNext(n, f)) 1063 findFirst(); // retry 1064 clearIndexToFirst(); 1065 @SuppressWarnings("unchecked") V vv = (V)v; 1066 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, vv); 1067 } 1068 } 1069 1070 /** 1071 * Clears out index nodes associated with deleted first entry. 1072 */ clearIndexToFirst()1073 private void clearIndexToFirst() { 1074 for (;;) { 1075 for (Index<K,V> q = head;;) { 1076 Index<K,V> r = q.right; 1077 if (r != null && r.indexesDeletedNode() && !q.unlink(r)) 1078 break; 1079 if ((q = q.down) == null) { 1080 if (head.right == null) 1081 tryReduceLevel(); 1082 return; 1083 } 1084 } 1085 } 1086 } 1087 1088 /** 1089 * Removes last entry; returns its snapshot. 1090 * Specialized variant of doRemove. 1091 * @return null if empty, else snapshot of last entry 1092 */ doRemoveLastEntry()1093 private Map.Entry<K,V> doRemoveLastEntry() { 1094 for (;;) { 1095 Node<K,V> b = findPredecessorOfLast(); 1096 Node<K,V> n = b.next; 1097 if (n == null) { 1098 if (b.isBaseHeader()) // empty 1099 return null; 1100 else 1101 continue; // all b's successors are deleted; retry 1102 } 1103 for (;;) { 1104 Node<K,V> f = n.next; 1105 if (n != b.next) // inconsistent read 1106 break; 1107 Object v = n.value; 1108 if (v == null) { // n is deleted 1109 n.helpDelete(b, f); 1110 break; 1111 } 1112 if (b.value == null || v == n) // b is deleted 1113 break; 1114 if (f != null) { 1115 b = n; 1116 n = f; 1117 continue; 1118 } 1119 if (!n.casValue(v, null)) 1120 break; 1121 K key = n.key; 1122 if (!n.appendMarker(f) || !b.casNext(n, f)) 1123 findNode(key); // retry via findNode 1124 else { // clean index 1125 findPredecessor(key, comparator); 1126 if (head.right == null) 1127 tryReduceLevel(); 1128 } 1129 @SuppressWarnings("unchecked") V vv = (V)v; 1130 return new AbstractMap.SimpleImmutableEntry<K,V>(key, vv); 1131 } 1132 } 1133 } 1134 1135 /* ---------------- Finding and removing last element -------------- */ 1136 1137 /** 1138 * Specialized version of find to get last valid node. 1139 * @return last node or null if empty 1140 */ findLast()1141 final Node<K,V> findLast() { 1142 /* 1143 * findPredecessor can't be used to traverse index level 1144 * because this doesn't use comparisons. So traversals of 1145 * both levels are folded together. 1146 */ 1147 Index<K,V> q = head; 1148 for (;;) { 1149 Index<K,V> d, r; 1150 if ((r = q.right) != null) { 1151 if (r.indexesDeletedNode()) { 1152 q.unlink(r); 1153 q = head; // restart 1154 } 1155 else 1156 q = r; 1157 } else if ((d = q.down) != null) { 1158 q = d; 1159 } else { 1160 for (Node<K,V> b = q.node, n = b.next;;) { 1161 if (n == null) 1162 return b.isBaseHeader() ? null : b; 1163 Node<K,V> f = n.next; // inconsistent read 1164 if (n != b.next) 1165 break; 1166 Object v = n.value; 1167 if (v == null) { // n is deleted 1168 n.helpDelete(b, f); 1169 break; 1170 } 1171 if (b.value == null || v == n) // b is deleted 1172 break; 1173 b = n; 1174 n = f; 1175 } 1176 q = head; // restart 1177 } 1178 } 1179 } 1180 1181 /** 1182 * Specialized variant of findPredecessor to get predecessor of last 1183 * valid node. Needed when removing the last entry. It is possible 1184 * that all successors of returned node will have been deleted upon 1185 * return, in which case this method can be retried. 1186 * @return likely predecessor of last node 1187 */ findPredecessorOfLast()1188 private Node<K,V> findPredecessorOfLast() { 1189 for (;;) { 1190 for (Index<K,V> q = head;;) { 1191 Index<K,V> d, r; 1192 if ((r = q.right) != null) { 1193 if (r.indexesDeletedNode()) { 1194 q.unlink(r); 1195 break; // must restart 1196 } 1197 // proceed as far across as possible without overshooting 1198 if (r.node.next != null) { 1199 q = r; 1200 continue; 1201 } 1202 } 1203 if ((d = q.down) != null) 1204 q = d; 1205 else 1206 return q.node; 1207 } 1208 } 1209 } 1210 1211 /* ---------------- Relational operations -------------- */ 1212 1213 // Control values OR'ed as arguments to findNear 1214 1215 private static final int EQ = 1; 1216 private static final int LT = 2; 1217 private static final int GT = 0; // Actually checked as !LT 1218 1219 /** 1220 * Utility for ceiling, floor, lower, higher methods. 1221 * @param key the key 1222 * @param rel the relation -- OR'ed combination of EQ, LT, GT 1223 * @return nearest node fitting relation, or null if no such 1224 */ findNear(K key, int rel, Comparator<? super K> cmp)1225 final Node<K,V> findNear(K key, int rel, Comparator<? super K> cmp) { 1226 if (key == null) 1227 throw new NullPointerException(); 1228 for (;;) { 1229 for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) { 1230 Object v; 1231 if (n == null) 1232 return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b; 1233 Node<K,V> f = n.next; 1234 if (n != b.next) // inconsistent read 1235 break; 1236 if ((v = n.value) == null) { // n is deleted 1237 n.helpDelete(b, f); 1238 break; 1239 } 1240 if (b.value == null || v == n) // b is deleted 1241 break; 1242 int c = cpr(cmp, key, n.key); 1243 if ((c == 0 && (rel & EQ) != 0) || 1244 (c < 0 && (rel & LT) == 0)) 1245 return n; 1246 if ( c <= 0 && (rel & LT) != 0) 1247 return b.isBaseHeader() ? null : b; 1248 b = n; 1249 n = f; 1250 } 1251 } 1252 } 1253 1254 /** 1255 * Returns SimpleImmutableEntry for results of findNear. 1256 * @param key the key 1257 * @param rel the relation -- OR'ed combination of EQ, LT, GT 1258 * @return Entry fitting relation, or null if no such 1259 */ getNear(K key, int rel)1260 final AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) { 1261 Comparator<? super K> cmp = comparator; 1262 for (;;) { 1263 Node<K,V> n = findNear(key, rel, cmp); 1264 if (n == null) 1265 return null; 1266 AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot(); 1267 if (e != null) 1268 return e; 1269 } 1270 } 1271 1272 /* ---------------- Constructors -------------- */ 1273 1274 /** 1275 * Constructs a new, empty map, sorted according to the 1276 * {@linkplain Comparable natural ordering} of the keys. 1277 */ ConcurrentSkipListMap()1278 public ConcurrentSkipListMap() { 1279 this.comparator = null; 1280 initialize(); 1281 } 1282 1283 /** 1284 * Constructs a new, empty map, sorted according to the specified 1285 * comparator. 1286 * 1287 * @param comparator the comparator that will be used to order this map. 1288 * If {@code null}, the {@linkplain Comparable natural 1289 * ordering} of the keys will be used. 1290 */ ConcurrentSkipListMap(Comparator<? super K> comparator)1291 public ConcurrentSkipListMap(Comparator<? super K> comparator) { 1292 this.comparator = comparator; 1293 initialize(); 1294 } 1295 1296 /** 1297 * Constructs a new map containing the same mappings as the given map, 1298 * sorted according to the {@linkplain Comparable natural ordering} of 1299 * the keys. 1300 * 1301 * @param m the map whose mappings are to be placed in this map 1302 * @throws ClassCastException if the keys in {@code m} are not 1303 * {@link Comparable}, or are not mutually comparable 1304 * @throws NullPointerException if the specified map or any of its keys 1305 * or values are null 1306 */ ConcurrentSkipListMap(Map<? extends K, ? extends V> m)1307 public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) { 1308 this.comparator = null; 1309 initialize(); 1310 putAll(m); 1311 } 1312 1313 /** 1314 * Constructs a new map containing the same mappings and using the 1315 * same ordering as the specified sorted map. 1316 * 1317 * @param m the sorted map whose mappings are to be placed in this 1318 * map, and whose comparator is to be used to sort this map 1319 * @throws NullPointerException if the specified sorted map or any of 1320 * its keys or values are null 1321 */ ConcurrentSkipListMap(SortedMap<K, ? extends V> m)1322 public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) { 1323 this.comparator = m.comparator(); 1324 initialize(); 1325 buildFromSorted(m); 1326 } 1327 1328 /** 1329 * Returns a shallow copy of this {@code ConcurrentSkipListMap} 1330 * instance. (The keys and values themselves are not cloned.) 1331 * 1332 * @return a shallow copy of this map 1333 */ clone()1334 public ConcurrentSkipListMap<K,V> clone() { 1335 try { 1336 @SuppressWarnings("unchecked") 1337 ConcurrentSkipListMap<K,V> clone = 1338 (ConcurrentSkipListMap<K,V>) super.clone(); 1339 clone.initialize(); 1340 clone.buildFromSorted(this); 1341 return clone; 1342 } catch (CloneNotSupportedException e) { 1343 throw new InternalError(); 1344 } 1345 } 1346 1347 /** 1348 * Streamlined bulk insertion to initialize from elements of 1349 * given sorted map. Call only from constructor or clone 1350 * method. 1351 */ buildFromSorted(SortedMap<K, ? extends V> map)1352 private void buildFromSorted(SortedMap<K, ? extends V> map) { 1353 if (map == null) 1354 throw new NullPointerException(); 1355 1356 HeadIndex<K,V> h = head; 1357 Node<K,V> basepred = h.node; 1358 1359 // Track the current rightmost node at each level. Uses an 1360 // ArrayList to avoid committing to initial or maximum level. 1361 ArrayList<Index<K,V>> preds = new ArrayList<>(); 1362 1363 // initialize 1364 for (int i = 0; i <= h.level; ++i) 1365 preds.add(null); 1366 Index<K,V> q = h; 1367 for (int i = h.level; i > 0; --i) { 1368 preds.set(i, q); 1369 q = q.down; 1370 } 1371 1372 Iterator<? extends Map.Entry<? extends K, ? extends V>> it = 1373 map.entrySet().iterator(); 1374 while (it.hasNext()) { 1375 Map.Entry<? extends K, ? extends V> e = it.next(); 1376 int rnd = ThreadLocalRandom.current().nextInt(); 1377 int j = 0; 1378 if ((rnd & 0x80000001) == 0) { 1379 do { 1380 ++j; 1381 } while (((rnd >>>= 1) & 1) != 0); 1382 if (j > h.level) j = h.level + 1; 1383 } 1384 K k = e.getKey(); 1385 V v = e.getValue(); 1386 if (k == null || v == null) 1387 throw new NullPointerException(); 1388 Node<K,V> z = new Node<K,V>(k, v, null); 1389 basepred.next = z; 1390 basepred = z; 1391 if (j > 0) { 1392 Index<K,V> idx = null; 1393 for (int i = 1; i <= j; ++i) { 1394 idx = new Index<K,V>(z, idx, null); 1395 if (i > h.level) 1396 h = new HeadIndex<K,V>(h.node, h, idx, i); 1397 1398 if (i < preds.size()) { 1399 preds.get(i).right = idx; 1400 preds.set(i, idx); 1401 } else 1402 preds.add(idx); 1403 } 1404 } 1405 } 1406 head = h; 1407 } 1408 1409 /* ---------------- Serialization -------------- */ 1410 1411 /** 1412 * Saves this map to a stream (that is, serializes it). 1413 * 1414 * @param s the stream 1415 * @throws java.io.IOException if an I/O error occurs 1416 * @serialData The key (Object) and value (Object) for each 1417 * key-value mapping represented by the map, followed by 1418 * {@code null}. The key-value mappings are emitted in key-order 1419 * (as determined by the Comparator, or by the keys' natural 1420 * ordering if no Comparator). 1421 */ writeObject(java.io.ObjectOutputStream s)1422 private void writeObject(java.io.ObjectOutputStream s) 1423 throws java.io.IOException { 1424 // Write out the Comparator and any hidden stuff 1425 s.defaultWriteObject(); 1426 1427 // Write out keys and values (alternating) 1428 for (Node<K,V> n = findFirst(); n != null; n = n.next) { 1429 V v = n.getValidValue(); 1430 if (v != null) { 1431 s.writeObject(n.key); 1432 s.writeObject(v); 1433 } 1434 } 1435 s.writeObject(null); 1436 } 1437 1438 /** 1439 * Reconstitutes this map from a stream (that is, deserializes it). 1440 * @param s the stream 1441 * @throws ClassNotFoundException if the class of a serialized object 1442 * could not be found 1443 * @throws java.io.IOException if an I/O error occurs 1444 */ 1445 @SuppressWarnings("unchecked") readObject(final java.io.ObjectInputStream s)1446 private void readObject(final java.io.ObjectInputStream s) 1447 throws java.io.IOException, ClassNotFoundException { 1448 // Read in the Comparator and any hidden stuff 1449 s.defaultReadObject(); 1450 // Reset transients 1451 initialize(); 1452 1453 /* 1454 * This is nearly identical to buildFromSorted, but is 1455 * distinct because readObject calls can't be nicely adapted 1456 * as the kind of iterator needed by buildFromSorted. (They 1457 * can be, but doing so requires type cheats and/or creation 1458 * of adapter classes.) It is simpler to just adapt the code. 1459 */ 1460 1461 HeadIndex<K,V> h = head; 1462 Node<K,V> basepred = h.node; 1463 ArrayList<Index<K,V>> preds = new ArrayList<>(); 1464 for (int i = 0; i <= h.level; ++i) 1465 preds.add(null); 1466 Index<K,V> q = h; 1467 for (int i = h.level; i > 0; --i) { 1468 preds.set(i, q); 1469 q = q.down; 1470 } 1471 1472 for (;;) { 1473 Object k = s.readObject(); 1474 if (k == null) 1475 break; 1476 Object v = s.readObject(); 1477 if (v == null) 1478 throw new NullPointerException(); 1479 K key = (K) k; 1480 V val = (V) v; 1481 int rnd = ThreadLocalRandom.current().nextInt(); 1482 int j = 0; 1483 if ((rnd & 0x80000001) == 0) { 1484 do { 1485 ++j; 1486 } while (((rnd >>>= 1) & 1) != 0); 1487 if (j > h.level) j = h.level + 1; 1488 } 1489 Node<K,V> z = new Node<K,V>(key, val, null); 1490 basepred.next = z; 1491 basepred = z; 1492 if (j > 0) { 1493 Index<K,V> idx = null; 1494 for (int i = 1; i <= j; ++i) { 1495 idx = new Index<K,V>(z, idx, null); 1496 if (i > h.level) 1497 h = new HeadIndex<K,V>(h.node, h, idx, i); 1498 1499 if (i < preds.size()) { 1500 preds.get(i).right = idx; 1501 preds.set(i, idx); 1502 } else 1503 preds.add(idx); 1504 } 1505 } 1506 } 1507 head = h; 1508 } 1509 1510 /* ------ Map API methods ------ */ 1511 1512 /** 1513 * Returns {@code true} if this map contains a mapping for the specified 1514 * key. 1515 * 1516 * @param key key whose presence in this map is to be tested 1517 * @return {@code true} if this map contains a mapping for the specified key 1518 * @throws ClassCastException if the specified key cannot be compared 1519 * with the keys currently in the map 1520 * @throws NullPointerException if the specified key is null 1521 */ containsKey(Object key)1522 public boolean containsKey(Object key) { 1523 return doGet(key) != null; 1524 } 1525 1526 /** 1527 * Returns the value to which the specified key is mapped, 1528 * or {@code null} if this map contains no mapping for the key. 1529 * 1530 * <p>More formally, if this map contains a mapping from a key 1531 * {@code k} to a value {@code v} such that {@code key} compares 1532 * equal to {@code k} according to the map's ordering, then this 1533 * method returns {@code v}; otherwise it returns {@code null}. 1534 * (There can be at most one such mapping.) 1535 * 1536 * @throws ClassCastException if the specified key cannot be compared 1537 * with the keys currently in the map 1538 * @throws NullPointerException if the specified key is null 1539 */ get(Object key)1540 public V get(Object key) { 1541 return doGet(key); 1542 } 1543 1544 /** 1545 * Returns the value to which the specified key is mapped, 1546 * or the given defaultValue if this map contains no mapping for the key. 1547 * 1548 * @param key the key 1549 * @param defaultValue the value to return if this map contains 1550 * no mapping for the given key 1551 * @return the mapping for the key, if present; else the defaultValue 1552 * @throws NullPointerException if the specified key is null 1553 * @since 1.8 1554 */ getOrDefault(Object key, V defaultValue)1555 public V getOrDefault(Object key, V defaultValue) { 1556 V v; 1557 return (v = doGet(key)) == null ? defaultValue : v; 1558 } 1559 1560 /** 1561 * Associates the specified value with the specified key in this map. 1562 * If the map previously contained a mapping for the key, the old 1563 * value is replaced. 1564 * 1565 * @param key key with which the specified value is to be associated 1566 * @param value value to be associated with the specified key 1567 * @return the previous value associated with the specified key, or 1568 * {@code null} if there was no mapping for the key 1569 * @throws ClassCastException if the specified key cannot be compared 1570 * with the keys currently in the map 1571 * @throws NullPointerException if the specified key or value is null 1572 */ put(K key, V value)1573 public V put(K key, V value) { 1574 if (value == null) 1575 throw new NullPointerException(); 1576 return doPut(key, value, false); 1577 } 1578 1579 /** 1580 * Removes the mapping for the specified key from this map if present. 1581 * 1582 * @param key key for which mapping should be removed 1583 * @return the previous value associated with the specified key, or 1584 * {@code null} if there was no mapping for the key 1585 * @throws ClassCastException if the specified key cannot be compared 1586 * with the keys currently in the map 1587 * @throws NullPointerException if the specified key is null 1588 */ remove(Object key)1589 public V remove(Object key) { 1590 return doRemove(key, null); 1591 } 1592 1593 /** 1594 * Returns {@code true} if this map maps one or more keys to the 1595 * specified value. This operation requires time linear in the 1596 * map size. Additionally, it is possible for the map to change 1597 * during execution of this method, in which case the returned 1598 * result may be inaccurate. 1599 * 1600 * @param value value whose presence in this map is to be tested 1601 * @return {@code true} if a mapping to {@code value} exists; 1602 * {@code false} otherwise 1603 * @throws NullPointerException if the specified value is null 1604 */ containsValue(Object value)1605 public boolean containsValue(Object value) { 1606 if (value == null) 1607 throw new NullPointerException(); 1608 for (Node<K,V> n = findFirst(); n != null; n = n.next) { 1609 V v = n.getValidValue(); 1610 if (v != null && value.equals(v)) 1611 return true; 1612 } 1613 return false; 1614 } 1615 1616 /** 1617 * Returns the number of key-value mappings in this map. If this map 1618 * contains more than {@code Integer.MAX_VALUE} elements, it 1619 * returns {@code Integer.MAX_VALUE}. 1620 * 1621 * <p>Beware that, unlike in most collections, this method is 1622 * <em>NOT</em> a constant-time operation. Because of the 1623 * asynchronous nature of these maps, determining the current 1624 * number of elements requires traversing them all to count them. 1625 * Additionally, it is possible for the size to change during 1626 * execution of this method, in which case the returned result 1627 * will be inaccurate. Thus, this method is typically not very 1628 * useful in concurrent applications. 1629 * 1630 * @return the number of elements in this map 1631 */ size()1632 public int size() { 1633 long count = 0; 1634 for (Node<K,V> n = findFirst(); n != null; n = n.next) { 1635 if (n.getValidValue() != null) 1636 ++count; 1637 } 1638 return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) count; 1639 } 1640 1641 /** 1642 * Returns {@code true} if this map contains no key-value mappings. 1643 * @return {@code true} if this map contains no key-value mappings 1644 */ isEmpty()1645 public boolean isEmpty() { 1646 return findFirst() == null; 1647 } 1648 1649 /** 1650 * Removes all of the mappings from this map. 1651 */ clear()1652 public void clear() { 1653 initialize(); 1654 } 1655 1656 /** 1657 * If the specified key is not already associated with a value, 1658 * attempts to compute its value using the given mapping function 1659 * and enters it into this map unless {@code null}. The function 1660 * is <em>NOT</em> guaranteed to be applied once atomically only 1661 * if the value is not present. 1662 * 1663 * @param key key with which the specified value is to be associated 1664 * @param mappingFunction the function to compute a value 1665 * @return the current (existing or computed) value associated with 1666 * the specified key, or null if the computed value is null 1667 * @throws NullPointerException if the specified key is null 1668 * or the mappingFunction is null 1669 * @since 1.8 1670 */ computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)1671 public V computeIfAbsent(K key, 1672 Function<? super K, ? extends V> mappingFunction) { 1673 if (key == null || mappingFunction == null) 1674 throw new NullPointerException(); 1675 V v, p, r; 1676 if ((v = doGet(key)) == null && 1677 (r = mappingFunction.apply(key)) != null) 1678 v = (p = doPut(key, r, true)) == null ? r : p; 1679 return v; 1680 } 1681 1682 /** 1683 * If the value for the specified key is present, attempts to 1684 * compute a new mapping given the key and its current mapped 1685 * value. The function is <em>NOT</em> guaranteed to be applied 1686 * once atomically. 1687 * 1688 * @param key key with which a value may be associated 1689 * @param remappingFunction the function to compute a value 1690 * @return the new value associated with the specified key, or null if none 1691 * @throws NullPointerException if the specified key is null 1692 * or the remappingFunction is null 1693 * @since 1.8 1694 */ computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)1695 public V computeIfPresent(K key, 1696 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1697 if (key == null || remappingFunction == null) 1698 throw new NullPointerException(); 1699 Node<K,V> n; Object v; 1700 while ((n = findNode(key)) != null) { 1701 if ((v = n.value) != null) { 1702 @SuppressWarnings("unchecked") V vv = (V) v; 1703 V r = remappingFunction.apply(key, vv); 1704 if (r != null) { 1705 if (n.casValue(vv, r)) 1706 return r; 1707 } 1708 else if (doRemove(key, vv) != null) 1709 break; 1710 } 1711 } 1712 return null; 1713 } 1714 1715 /** 1716 * Attempts to compute a mapping for the specified key and its 1717 * current mapped value (or {@code null} if there is no current 1718 * mapping). The function is <em>NOT</em> guaranteed to be applied 1719 * once atomically. 1720 * 1721 * @param key key with which the specified value is to be associated 1722 * @param remappingFunction the function to compute a value 1723 * @return the new value associated with the specified key, or null if none 1724 * @throws NullPointerException if the specified key is null 1725 * or the remappingFunction is null 1726 * @since 1.8 1727 */ compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)1728 public V compute(K key, 1729 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1730 if (key == null || remappingFunction == null) 1731 throw new NullPointerException(); 1732 for (;;) { 1733 Node<K,V> n; Object v; V r; 1734 if ((n = findNode(key)) == null) { 1735 if ((r = remappingFunction.apply(key, null)) == null) 1736 break; 1737 if (doPut(key, r, true) == null) 1738 return r; 1739 } 1740 else if ((v = n.value) != null) { 1741 @SuppressWarnings("unchecked") V vv = (V) v; 1742 if ((r = remappingFunction.apply(key, vv)) != null) { 1743 if (n.casValue(vv, r)) 1744 return r; 1745 } 1746 else if (doRemove(key, vv) != null) 1747 break; 1748 } 1749 } 1750 return null; 1751 } 1752 1753 /** 1754 * If the specified key is not already associated with a value, 1755 * associates it with the given value. Otherwise, replaces the 1756 * value with the results of the given remapping function, or 1757 * removes if {@code null}. The function is <em>NOT</em> 1758 * guaranteed to be applied once atomically. 1759 * 1760 * @param key key with which the specified value is to be associated 1761 * @param value the value to use if absent 1762 * @param remappingFunction the function to recompute a value if present 1763 * @return the new value associated with the specified key, or null if none 1764 * @throws NullPointerException if the specified key or value is null 1765 * or the remappingFunction is null 1766 * @since 1.8 1767 */ merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)1768 public V merge(K key, V value, 1769 BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 1770 if (key == null || value == null || remappingFunction == null) 1771 throw new NullPointerException(); 1772 for (;;) { 1773 Node<K,V> n; Object v; V r; 1774 if ((n = findNode(key)) == null) { 1775 if (doPut(key, value, true) == null) 1776 return value; 1777 } 1778 else if ((v = n.value) != null) { 1779 @SuppressWarnings("unchecked") V vv = (V) v; 1780 if ((r = remappingFunction.apply(vv, value)) != null) { 1781 if (n.casValue(vv, r)) 1782 return r; 1783 } 1784 else if (doRemove(key, vv) != null) 1785 return null; 1786 } 1787 } 1788 } 1789 1790 /* ---------------- View methods -------------- */ 1791 1792 /* 1793 * Note: Lazy initialization works for views because view classes 1794 * are stateless/immutable so it doesn't matter wrt correctness if 1795 * more than one is created (which will only rarely happen). Even 1796 * so, the following idiom conservatively ensures that the method 1797 * returns the one it created if it does so, not one created by 1798 * another racing thread. 1799 */ 1800 1801 /** 1802 * Returns a {@link NavigableSet} view of the keys contained in this map. 1803 * 1804 * <p>The set's iterator returns the keys in ascending order. 1805 * The set's spliterator additionally reports {@link Spliterator#CONCURRENT}, 1806 * {@link Spliterator#NONNULL}, {@link Spliterator#SORTED} and 1807 * {@link Spliterator#ORDERED}, with an encounter order that is ascending 1808 * key order. The spliterator's comparator (see 1809 * {@link java.util.Spliterator#getComparator()}) is {@code null} if 1810 * the map's comparator (see {@link #comparator()}) is {@code null}. 1811 * Otherwise, the spliterator's comparator is the same as or imposes the 1812 * same total ordering as the map's comparator. 1813 * 1814 * <p>The set is backed by the map, so changes to the map are 1815 * reflected in the set, and vice-versa. The set supports element 1816 * removal, which removes the corresponding mapping from the map, 1817 * via the {@code Iterator.remove}, {@code Set.remove}, 1818 * {@code removeAll}, {@code retainAll}, and {@code clear} 1819 * operations. It does not support the {@code add} or {@code addAll} 1820 * operations. 1821 * 1822 * <p>The view's iterators and spliterators are 1823 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1824 * 1825 * <p>This method is equivalent to method {@code navigableKeySet}. 1826 * 1827 * @return a navigable set view of the keys in this map 1828 */ keySet()1829 public NavigableSet<K> keySet() { 1830 KeySet<K,V> ks = keySet; 1831 return (ks != null) ? ks : (keySet = new KeySet<>(this)); 1832 } 1833 navigableKeySet()1834 public NavigableSet<K> navigableKeySet() { 1835 KeySet<K,V> ks = keySet; 1836 return (ks != null) ? ks : (keySet = new KeySet<>(this)); 1837 } 1838 1839 /** 1840 * Returns a {@link Collection} view of the values contained in this map. 1841 * <p>The collection's iterator returns the values in ascending order 1842 * of the corresponding keys. The collections's spliterator additionally 1843 * reports {@link Spliterator#CONCURRENT}, {@link Spliterator#NONNULL} and 1844 * {@link Spliterator#ORDERED}, with an encounter order that is ascending 1845 * order of the corresponding keys. 1846 * 1847 * <p>The collection is backed by the map, so changes to the map are 1848 * reflected in the collection, and vice-versa. The collection 1849 * supports element removal, which removes the corresponding 1850 * mapping from the map, via the {@code Iterator.remove}, 1851 * {@code Collection.remove}, {@code removeAll}, 1852 * {@code retainAll} and {@code clear} operations. It does not 1853 * support the {@code add} or {@code addAll} operations. 1854 * 1855 * <p>The view's iterators and spliterators are 1856 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1857 */ values()1858 public Collection<V> values() { 1859 Values<K,V> vs = values; 1860 return (vs != null) ? vs : (values = new Values<>(this)); 1861 } 1862 1863 /** 1864 * Returns a {@link Set} view of the mappings contained in this map. 1865 * 1866 * <p>The set's iterator returns the entries in ascending key order. The 1867 * set's spliterator additionally reports {@link Spliterator#CONCURRENT}, 1868 * {@link Spliterator#NONNULL}, {@link Spliterator#SORTED} and 1869 * {@link Spliterator#ORDERED}, with an encounter order that is ascending 1870 * key order. 1871 * 1872 * <p>The set is backed by the map, so changes to the map are 1873 * reflected in the set, and vice-versa. The set supports element 1874 * removal, which removes the corresponding mapping from the map, 1875 * via the {@code Iterator.remove}, {@code Set.remove}, 1876 * {@code removeAll}, {@code retainAll} and {@code clear} 1877 * operations. It does not support the {@code add} or 1878 * {@code addAll} operations. 1879 * 1880 * <p>The view's iterators and spliterators are 1881 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1882 * 1883 * <p>The {@code Map.Entry} elements traversed by the {@code iterator} 1884 * or {@code spliterator} do <em>not</em> support the {@code setValue} 1885 * operation. 1886 * 1887 * @return a set view of the mappings contained in this map, 1888 * sorted in ascending key order 1889 */ entrySet()1890 public Set<Map.Entry<K,V>> entrySet() { 1891 EntrySet<K,V> es = entrySet; 1892 return (es != null) ? es : (entrySet = new EntrySet<K,V>(this)); 1893 } 1894 descendingMap()1895 public ConcurrentNavigableMap<K,V> descendingMap() { 1896 ConcurrentNavigableMap<K,V> dm = descendingMap; 1897 return (dm != null) ? dm : (descendingMap = new SubMap<K,V> 1898 (this, null, false, null, false, true)); 1899 } 1900 descendingKeySet()1901 public NavigableSet<K> descendingKeySet() { 1902 return descendingMap().navigableKeySet(); 1903 } 1904 1905 /* ---------------- AbstractMap Overrides -------------- */ 1906 1907 /** 1908 * Compares the specified object with this map for equality. 1909 * Returns {@code true} if the given object is also a map and the 1910 * two maps represent the same mappings. More formally, two maps 1911 * {@code m1} and {@code m2} represent the same mappings if 1912 * {@code m1.entrySet().equals(m2.entrySet())}. This 1913 * operation may return misleading results if either map is 1914 * concurrently modified during execution of this method. 1915 * 1916 * @param o object to be compared for equality with this map 1917 * @return {@code true} if the specified object is equal to this map 1918 */ equals(Object o)1919 public boolean equals(Object o) { 1920 if (o == this) 1921 return true; 1922 if (!(o instanceof Map)) 1923 return false; 1924 Map<?,?> m = (Map<?,?>) o; 1925 try { 1926 for (Map.Entry<K,V> e : this.entrySet()) 1927 if (! e.getValue().equals(m.get(e.getKey()))) 1928 return false; 1929 for (Map.Entry<?,?> e : m.entrySet()) { 1930 Object k = e.getKey(); 1931 Object v = e.getValue(); 1932 if (k == null || v == null || !v.equals(get(k))) 1933 return false; 1934 } 1935 return true; 1936 } catch (ClassCastException unused) { 1937 return false; 1938 } catch (NullPointerException unused) { 1939 return false; 1940 } 1941 } 1942 1943 /* ------ ConcurrentMap API methods ------ */ 1944 1945 /** 1946 * {@inheritDoc} 1947 * 1948 * @return the previous value associated with the specified key, 1949 * or {@code null} if there was no mapping for the key 1950 * @throws ClassCastException if the specified key cannot be compared 1951 * with the keys currently in the map 1952 * @throws NullPointerException if the specified key or value is null 1953 */ putIfAbsent(K key, V value)1954 public V putIfAbsent(K key, V value) { 1955 if (value == null) 1956 throw new NullPointerException(); 1957 return doPut(key, value, true); 1958 } 1959 1960 /** 1961 * {@inheritDoc} 1962 * 1963 * @throws ClassCastException if the specified key cannot be compared 1964 * with the keys currently in the map 1965 * @throws NullPointerException if the specified key is null 1966 */ remove(Object key, Object value)1967 public boolean remove(Object key, Object value) { 1968 if (key == null) 1969 throw new NullPointerException(); 1970 return value != null && doRemove(key, value) != null; 1971 } 1972 1973 /** 1974 * {@inheritDoc} 1975 * 1976 * @throws ClassCastException if the specified key cannot be compared 1977 * with the keys currently in the map 1978 * @throws NullPointerException if any of the arguments are null 1979 */ replace(K key, V oldValue, V newValue)1980 public boolean replace(K key, V oldValue, V newValue) { 1981 if (key == null || oldValue == null || newValue == null) 1982 throw new NullPointerException(); 1983 for (;;) { 1984 Node<K,V> n; Object v; 1985 if ((n = findNode(key)) == null) 1986 return false; 1987 if ((v = n.value) != null) { 1988 if (!oldValue.equals(v)) 1989 return false; 1990 if (n.casValue(v, newValue)) 1991 return true; 1992 } 1993 } 1994 } 1995 1996 /** 1997 * {@inheritDoc} 1998 * 1999 * @return the previous value associated with the specified key, 2000 * or {@code null} if there was no mapping for the key 2001 * @throws ClassCastException if the specified key cannot be compared 2002 * with the keys currently in the map 2003 * @throws NullPointerException if the specified key or value is null 2004 */ replace(K key, V value)2005 public V replace(K key, V value) { 2006 if (key == null || value == null) 2007 throw new NullPointerException(); 2008 for (;;) { 2009 Node<K,V> n; Object v; 2010 if ((n = findNode(key)) == null) 2011 return null; 2012 if ((v = n.value) != null && n.casValue(v, value)) { 2013 @SuppressWarnings("unchecked") V vv = (V)v; 2014 return vv; 2015 } 2016 } 2017 } 2018 2019 /* ------ SortedMap API methods ------ */ 2020 comparator()2021 public Comparator<? super K> comparator() { 2022 return comparator; 2023 } 2024 2025 /** 2026 * @throws NoSuchElementException {@inheritDoc} 2027 */ firstKey()2028 public K firstKey() { 2029 Node<K,V> n = findFirst(); 2030 if (n == null) 2031 throw new NoSuchElementException(); 2032 return n.key; 2033 } 2034 2035 /** 2036 * @throws NoSuchElementException {@inheritDoc} 2037 */ lastKey()2038 public K lastKey() { 2039 Node<K,V> n = findLast(); 2040 if (n == null) 2041 throw new NoSuchElementException(); 2042 return n.key; 2043 } 2044 2045 /** 2046 * @throws ClassCastException {@inheritDoc} 2047 * @throws NullPointerException if {@code fromKey} or {@code toKey} is null 2048 * @throws IllegalArgumentException {@inheritDoc} 2049 */ subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)2050 public ConcurrentNavigableMap<K,V> subMap(K fromKey, 2051 boolean fromInclusive, 2052 K toKey, 2053 boolean toInclusive) { 2054 if (fromKey == null || toKey == null) 2055 throw new NullPointerException(); 2056 return new SubMap<K,V> 2057 (this, fromKey, fromInclusive, toKey, toInclusive, false); 2058 } 2059 2060 /** 2061 * @throws ClassCastException {@inheritDoc} 2062 * @throws NullPointerException if {@code toKey} is null 2063 * @throws IllegalArgumentException {@inheritDoc} 2064 */ headMap(K toKey, boolean inclusive)2065 public ConcurrentNavigableMap<K,V> headMap(K toKey, 2066 boolean inclusive) { 2067 if (toKey == null) 2068 throw new NullPointerException(); 2069 return new SubMap<K,V> 2070 (this, null, false, toKey, inclusive, false); 2071 } 2072 2073 /** 2074 * @throws ClassCastException {@inheritDoc} 2075 * @throws NullPointerException if {@code fromKey} is null 2076 * @throws IllegalArgumentException {@inheritDoc} 2077 */ tailMap(K fromKey, boolean inclusive)2078 public ConcurrentNavigableMap<K,V> tailMap(K fromKey, 2079 boolean inclusive) { 2080 if (fromKey == null) 2081 throw new NullPointerException(); 2082 return new SubMap<K,V> 2083 (this, fromKey, inclusive, null, false, false); 2084 } 2085 2086 /** 2087 * @throws ClassCastException {@inheritDoc} 2088 * @throws NullPointerException if {@code fromKey} or {@code toKey} is null 2089 * @throws IllegalArgumentException {@inheritDoc} 2090 */ subMap(K fromKey, K toKey)2091 public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) { 2092 return subMap(fromKey, true, toKey, false); 2093 } 2094 2095 /** 2096 * @throws ClassCastException {@inheritDoc} 2097 * @throws NullPointerException if {@code toKey} is null 2098 * @throws IllegalArgumentException {@inheritDoc} 2099 */ headMap(K toKey)2100 public ConcurrentNavigableMap<K,V> headMap(K toKey) { 2101 return headMap(toKey, false); 2102 } 2103 2104 /** 2105 * @throws ClassCastException {@inheritDoc} 2106 * @throws NullPointerException if {@code fromKey} is null 2107 * @throws IllegalArgumentException {@inheritDoc} 2108 */ tailMap(K fromKey)2109 public ConcurrentNavigableMap<K,V> tailMap(K fromKey) { 2110 return tailMap(fromKey, true); 2111 } 2112 2113 /* ---------------- Relational operations -------------- */ 2114 2115 /** 2116 * Returns a key-value mapping associated with the greatest key 2117 * strictly less than the given key, or {@code null} if there is 2118 * no such key. The returned entry does <em>not</em> support the 2119 * {@code Entry.setValue} method. 2120 * 2121 * @throws ClassCastException {@inheritDoc} 2122 * @throws NullPointerException if the specified key is null 2123 */ lowerEntry(K key)2124 public Map.Entry<K,V> lowerEntry(K key) { 2125 return getNear(key, LT); 2126 } 2127 2128 /** 2129 * @throws ClassCastException {@inheritDoc} 2130 * @throws NullPointerException if the specified key is null 2131 */ lowerKey(K key)2132 public K lowerKey(K key) { 2133 Node<K,V> n = findNear(key, LT, comparator); 2134 return (n == null) ? null : n.key; 2135 } 2136 2137 /** 2138 * Returns a key-value mapping associated with the greatest key 2139 * less than or equal to the given key, or {@code null} if there 2140 * is no such key. The returned entry does <em>not</em> support 2141 * the {@code Entry.setValue} method. 2142 * 2143 * @param key the key 2144 * @throws ClassCastException {@inheritDoc} 2145 * @throws NullPointerException if the specified key is null 2146 */ floorEntry(K key)2147 public Map.Entry<K,V> floorEntry(K key) { 2148 return getNear(key, LT|EQ); 2149 } 2150 2151 /** 2152 * @param key the key 2153 * @throws ClassCastException {@inheritDoc} 2154 * @throws NullPointerException if the specified key is null 2155 */ floorKey(K key)2156 public K floorKey(K key) { 2157 Node<K,V> n = findNear(key, LT|EQ, comparator); 2158 return (n == null) ? null : n.key; 2159 } 2160 2161 /** 2162 * Returns a key-value mapping associated with the least key 2163 * greater than or equal to the given key, or {@code null} if 2164 * there is no such entry. The returned entry does <em>not</em> 2165 * support the {@code Entry.setValue} method. 2166 * 2167 * @throws ClassCastException {@inheritDoc} 2168 * @throws NullPointerException if the specified key is null 2169 */ ceilingEntry(K key)2170 public Map.Entry<K,V> ceilingEntry(K key) { 2171 return getNear(key, GT|EQ); 2172 } 2173 2174 /** 2175 * @throws ClassCastException {@inheritDoc} 2176 * @throws NullPointerException if the specified key is null 2177 */ ceilingKey(K key)2178 public K ceilingKey(K key) { 2179 Node<K,V> n = findNear(key, GT|EQ, comparator); 2180 return (n == null) ? null : n.key; 2181 } 2182 2183 /** 2184 * Returns a key-value mapping associated with the least key 2185 * strictly greater than the given key, or {@code null} if there 2186 * is no such key. The returned entry does <em>not</em> support 2187 * the {@code Entry.setValue} method. 2188 * 2189 * @param key the key 2190 * @throws ClassCastException {@inheritDoc} 2191 * @throws NullPointerException if the specified key is null 2192 */ higherEntry(K key)2193 public Map.Entry<K,V> higherEntry(K key) { 2194 return getNear(key, GT); 2195 } 2196 2197 /** 2198 * @param key the key 2199 * @throws ClassCastException {@inheritDoc} 2200 * @throws NullPointerException if the specified key is null 2201 */ higherKey(K key)2202 public K higherKey(K key) { 2203 Node<K,V> n = findNear(key, GT, comparator); 2204 return (n == null) ? null : n.key; 2205 } 2206 2207 /** 2208 * Returns a key-value mapping associated with the least 2209 * key in this map, or {@code null} if the map is empty. 2210 * The returned entry does <em>not</em> support 2211 * the {@code Entry.setValue} method. 2212 */ firstEntry()2213 public Map.Entry<K,V> firstEntry() { 2214 for (;;) { 2215 Node<K,V> n = findFirst(); 2216 if (n == null) 2217 return null; 2218 AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot(); 2219 if (e != null) 2220 return e; 2221 } 2222 } 2223 2224 /** 2225 * Returns a key-value mapping associated with the greatest 2226 * key in this map, or {@code null} if the map is empty. 2227 * The returned entry does <em>not</em> support 2228 * the {@code Entry.setValue} method. 2229 */ lastEntry()2230 public Map.Entry<K,V> lastEntry() { 2231 for (;;) { 2232 Node<K,V> n = findLast(); 2233 if (n == null) 2234 return null; 2235 AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot(); 2236 if (e != null) 2237 return e; 2238 } 2239 } 2240 2241 /** 2242 * Removes and returns a key-value mapping associated with 2243 * the least key in this map, or {@code null} if the map is empty. 2244 * The returned entry does <em>not</em> support 2245 * the {@code Entry.setValue} method. 2246 */ pollFirstEntry()2247 public Map.Entry<K,V> pollFirstEntry() { 2248 return doRemoveFirstEntry(); 2249 } 2250 2251 /** 2252 * Removes and returns a key-value mapping associated with 2253 * the greatest key in this map, or {@code null} if the map is empty. 2254 * The returned entry does <em>not</em> support 2255 * the {@code Entry.setValue} method. 2256 */ pollLastEntry()2257 public Map.Entry<K,V> pollLastEntry() { 2258 return doRemoveLastEntry(); 2259 } 2260 2261 2262 /* ---------------- Iterators -------------- */ 2263 2264 /** 2265 * Base of iterator classes: 2266 */ 2267 abstract class Iter<T> implements Iterator<T> { 2268 /** the last node returned by next() */ 2269 Node<K,V> lastReturned; 2270 /** the next node to return from next(); */ 2271 Node<K,V> next; 2272 /** Cache of next value field to maintain weak consistency */ 2273 V nextValue; 2274 2275 /** Initializes ascending iterator for entire range. */ Iter()2276 Iter() { 2277 while ((next = findFirst()) != null) { 2278 Object x = next.value; 2279 if (x != null && x != next) { 2280 @SuppressWarnings("unchecked") V vv = (V)x; 2281 nextValue = vv; 2282 break; 2283 } 2284 } 2285 } 2286 hasNext()2287 public final boolean hasNext() { 2288 return next != null; 2289 } 2290 2291 /** Advances next to higher entry. */ advance()2292 final void advance() { 2293 if (next == null) 2294 throw new NoSuchElementException(); 2295 lastReturned = next; 2296 while ((next = next.next) != null) { 2297 Object x = next.value; 2298 if (x != null && x != next) { 2299 @SuppressWarnings("unchecked") V vv = (V)x; 2300 nextValue = vv; 2301 break; 2302 } 2303 } 2304 } 2305 remove()2306 public void remove() { 2307 Node<K,V> l = lastReturned; 2308 if (l == null) 2309 throw new IllegalStateException(); 2310 // It would not be worth all of the overhead to directly 2311 // unlink from here. Using remove is fast enough. 2312 ConcurrentSkipListMap.this.remove(l.key); 2313 lastReturned = null; 2314 } 2315 2316 } 2317 2318 final class ValueIterator extends Iter<V> { next()2319 public V next() { 2320 V v = nextValue; 2321 advance(); 2322 return v; 2323 } 2324 } 2325 2326 final class KeyIterator extends Iter<K> { next()2327 public K next() { 2328 Node<K,V> n = next; 2329 advance(); 2330 return n.key; 2331 } 2332 } 2333 2334 final class EntryIterator extends Iter<Map.Entry<K,V>> { next()2335 public Map.Entry<K,V> next() { 2336 Node<K,V> n = next; 2337 V v = nextValue; 2338 advance(); 2339 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v); 2340 } 2341 } 2342 2343 /* ---------------- View Classes -------------- */ 2344 2345 /* 2346 * View classes are static, delegating to a ConcurrentNavigableMap 2347 * to allow use by SubMaps, which outweighs the ugliness of 2348 * needing type-tests for Iterator methods. 2349 */ 2350 toList(Collection<E> c)2351 static final <E> List<E> toList(Collection<E> c) { 2352 // Using size() here would be a pessimization. 2353 ArrayList<E> list = new ArrayList<E>(); 2354 for (E e : c) 2355 list.add(e); 2356 return list; 2357 } 2358 2359 static final class KeySet<K,V> 2360 extends AbstractSet<K> implements NavigableSet<K> { 2361 final ConcurrentNavigableMap<K,V> m; KeySet(ConcurrentNavigableMap<K,V> map)2362 KeySet(ConcurrentNavigableMap<K,V> map) { m = map; } size()2363 public int size() { return m.size(); } isEmpty()2364 public boolean isEmpty() { return m.isEmpty(); } contains(Object o)2365 public boolean contains(Object o) { return m.containsKey(o); } remove(Object o)2366 public boolean remove(Object o) { return m.remove(o) != null; } clear()2367 public void clear() { m.clear(); } lower(K e)2368 public K lower(K e) { return m.lowerKey(e); } floor(K e)2369 public K floor(K e) { return m.floorKey(e); } ceiling(K e)2370 public K ceiling(K e) { return m.ceilingKey(e); } higher(K e)2371 public K higher(K e) { return m.higherKey(e); } comparator()2372 public Comparator<? super K> comparator() { return m.comparator(); } first()2373 public K first() { return m.firstKey(); } last()2374 public K last() { return m.lastKey(); } pollFirst()2375 public K pollFirst() { 2376 Map.Entry<K,V> e = m.pollFirstEntry(); 2377 return (e == null) ? null : e.getKey(); 2378 } pollLast()2379 public K pollLast() { 2380 Map.Entry<K,V> e = m.pollLastEntry(); 2381 return (e == null) ? null : e.getKey(); 2382 } iterator()2383 public Iterator<K> iterator() { 2384 return (m instanceof ConcurrentSkipListMap) 2385 ? ((ConcurrentSkipListMap<K,V>)m).new KeyIterator() 2386 : ((SubMap<K,V>)m).new SubMapKeyIterator(); 2387 } equals(Object o)2388 public boolean equals(Object o) { 2389 if (o == this) 2390 return true; 2391 if (!(o instanceof Set)) 2392 return false; 2393 Collection<?> c = (Collection<?>) o; 2394 try { 2395 return containsAll(c) && c.containsAll(this); 2396 } catch (ClassCastException unused) { 2397 return false; 2398 } catch (NullPointerException unused) { 2399 return false; 2400 } 2401 } toArray()2402 public Object[] toArray() { return toList(this).toArray(); } toArray(T[] a)2403 public <T> T[] toArray(T[] a) { return toList(this).toArray(a); } descendingIterator()2404 public Iterator<K> descendingIterator() { 2405 return descendingSet().iterator(); 2406 } subSet(K fromElement, boolean fromInclusive, K toElement, boolean toInclusive)2407 public NavigableSet<K> subSet(K fromElement, 2408 boolean fromInclusive, 2409 K toElement, 2410 boolean toInclusive) { 2411 return new KeySet<>(m.subMap(fromElement, fromInclusive, 2412 toElement, toInclusive)); 2413 } headSet(K toElement, boolean inclusive)2414 public NavigableSet<K> headSet(K toElement, boolean inclusive) { 2415 return new KeySet<>(m.headMap(toElement, inclusive)); 2416 } tailSet(K fromElement, boolean inclusive)2417 public NavigableSet<K> tailSet(K fromElement, boolean inclusive) { 2418 return new KeySet<>(m.tailMap(fromElement, inclusive)); 2419 } subSet(K fromElement, K toElement)2420 public NavigableSet<K> subSet(K fromElement, K toElement) { 2421 return subSet(fromElement, true, toElement, false); 2422 } headSet(K toElement)2423 public NavigableSet<K> headSet(K toElement) { 2424 return headSet(toElement, false); 2425 } tailSet(K fromElement)2426 public NavigableSet<K> tailSet(K fromElement) { 2427 return tailSet(fromElement, true); 2428 } descendingSet()2429 public NavigableSet<K> descendingSet() { 2430 return new KeySet<>(m.descendingMap()); 2431 } 2432 spliterator()2433 public Spliterator<K> spliterator() { 2434 return (m instanceof ConcurrentSkipListMap) 2435 ? ((ConcurrentSkipListMap<K,V>)m).keySpliterator() 2436 : ((SubMap<K,V>)m).new SubMapKeyIterator(); 2437 } 2438 } 2439 2440 static final class Values<K,V> extends AbstractCollection<V> { 2441 final ConcurrentNavigableMap<K,V> m; Values(ConcurrentNavigableMap<K,V> map)2442 Values(ConcurrentNavigableMap<K,V> map) { 2443 m = map; 2444 } iterator()2445 public Iterator<V> iterator() { 2446 return (m instanceof ConcurrentSkipListMap) 2447 ? ((ConcurrentSkipListMap<K,V>)m).new ValueIterator() 2448 : ((SubMap<K,V>)m).new SubMapValueIterator(); 2449 } size()2450 public int size() { return m.size(); } isEmpty()2451 public boolean isEmpty() { return m.isEmpty(); } contains(Object o)2452 public boolean contains(Object o) { return m.containsValue(o); } clear()2453 public void clear() { m.clear(); } toArray()2454 public Object[] toArray() { return toList(this).toArray(); } toArray(T[] a)2455 public <T> T[] toArray(T[] a) { return toList(this).toArray(a); } 2456 spliterator()2457 public Spliterator<V> spliterator() { 2458 return (m instanceof ConcurrentSkipListMap) 2459 ? ((ConcurrentSkipListMap<K,V>)m).valueSpliterator() 2460 : ((SubMap<K,V>)m).new SubMapValueIterator(); 2461 } 2462 removeIf(Predicate<? super V> filter)2463 public boolean removeIf(Predicate<? super V> filter) { 2464 if (filter == null) throw new NullPointerException(); 2465 if (m instanceof ConcurrentSkipListMap) 2466 return ((ConcurrentSkipListMap<K,V>)m).removeValueIf(filter); 2467 // else use iterator 2468 Iterator<Map.Entry<K,V>> it = 2469 ((SubMap<K,V>)m).new SubMapEntryIterator(); 2470 boolean removed = false; 2471 while (it.hasNext()) { 2472 Map.Entry<K,V> e = it.next(); 2473 V v = e.getValue(); 2474 if (filter.test(v) && m.remove(e.getKey(), v)) 2475 removed = true; 2476 } 2477 return removed; 2478 } 2479 } 2480 2481 static final class EntrySet<K,V> extends AbstractSet<Map.Entry<K,V>> { 2482 final ConcurrentNavigableMap<K,V> m; EntrySet(ConcurrentNavigableMap<K,V> map)2483 EntrySet(ConcurrentNavigableMap<K,V> map) { 2484 m = map; 2485 } iterator()2486 public Iterator<Map.Entry<K,V>> iterator() { 2487 return (m instanceof ConcurrentSkipListMap) 2488 ? ((ConcurrentSkipListMap<K,V>)m).new EntryIterator() 2489 : ((SubMap<K,V>)m).new SubMapEntryIterator(); 2490 } 2491 contains(Object o)2492 public boolean contains(Object o) { 2493 if (!(o instanceof Map.Entry)) 2494 return false; 2495 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 2496 V v = m.get(e.getKey()); 2497 return v != null && v.equals(e.getValue()); 2498 } remove(Object o)2499 public boolean remove(Object o) { 2500 if (!(o instanceof Map.Entry)) 2501 return false; 2502 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 2503 return m.remove(e.getKey(), 2504 e.getValue()); 2505 } isEmpty()2506 public boolean isEmpty() { 2507 return m.isEmpty(); 2508 } size()2509 public int size() { 2510 return m.size(); 2511 } clear()2512 public void clear() { 2513 m.clear(); 2514 } equals(Object o)2515 public boolean equals(Object o) { 2516 if (o == this) 2517 return true; 2518 if (!(o instanceof Set)) 2519 return false; 2520 Collection<?> c = (Collection<?>) o; 2521 try { 2522 return containsAll(c) && c.containsAll(this); 2523 } catch (ClassCastException unused) { 2524 return false; 2525 } catch (NullPointerException unused) { 2526 return false; 2527 } 2528 } toArray()2529 public Object[] toArray() { return toList(this).toArray(); } toArray(T[] a)2530 public <T> T[] toArray(T[] a) { return toList(this).toArray(a); } 2531 spliterator()2532 public Spliterator<Map.Entry<K,V>> spliterator() { 2533 return (m instanceof ConcurrentSkipListMap) 2534 ? ((ConcurrentSkipListMap<K,V>)m).entrySpliterator() 2535 : ((SubMap<K,V>)m).new SubMapEntryIterator(); 2536 } removeIf(Predicate<? super Entry<K,V>> filter)2537 public boolean removeIf(Predicate<? super Entry<K,V>> filter) { 2538 if (filter == null) throw new NullPointerException(); 2539 if (m instanceof ConcurrentSkipListMap) 2540 return ((ConcurrentSkipListMap<K,V>)m).removeEntryIf(filter); 2541 // else use iterator 2542 Iterator<Map.Entry<K,V>> it = 2543 ((SubMap<K,V>)m).new SubMapEntryIterator(); 2544 boolean removed = false; 2545 while (it.hasNext()) { 2546 Map.Entry<K,V> e = it.next(); 2547 if (filter.test(e) && m.remove(e.getKey(), e.getValue())) 2548 removed = true; 2549 } 2550 return removed; 2551 } 2552 } 2553 2554 /** 2555 * Submaps returned by {@link ConcurrentSkipListMap} submap operations 2556 * represent a subrange of mappings of their underlying maps. 2557 * Instances of this class support all methods of their underlying 2558 * maps, differing in that mappings outside their range are ignored, 2559 * and attempts to add mappings outside their ranges result in {@link 2560 * IllegalArgumentException}. Instances of this class are constructed 2561 * only using the {@code subMap}, {@code headMap}, and {@code tailMap} 2562 * methods of their underlying maps. 2563 * 2564 * @serial include 2565 */ 2566 static final class SubMap<K,V> extends AbstractMap<K,V> 2567 implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable { 2568 private static final long serialVersionUID = -7647078645895051609L; 2569 2570 /** Underlying map */ 2571 final ConcurrentSkipListMap<K,V> m; 2572 /** lower bound key, or null if from start */ 2573 private final K lo; 2574 /** upper bound key, or null if to end */ 2575 private final K hi; 2576 /** inclusion flag for lo */ 2577 private final boolean loInclusive; 2578 /** inclusion flag for hi */ 2579 private final boolean hiInclusive; 2580 /** direction */ 2581 final boolean isDescending; 2582 2583 // Lazily initialized view holders 2584 private transient KeySet<K,V> keySetView; 2585 private transient Set<Map.Entry<K,V>> entrySetView; 2586 private transient Collection<V> valuesView; 2587 2588 /** 2589 * Creates a new submap, initializing all fields. 2590 */ SubMap(ConcurrentSkipListMap<K,V> map, K fromKey, boolean fromInclusive, K toKey, boolean toInclusive, boolean isDescending)2591 SubMap(ConcurrentSkipListMap<K,V> map, 2592 K fromKey, boolean fromInclusive, 2593 K toKey, boolean toInclusive, 2594 boolean isDescending) { 2595 Comparator<? super K> cmp = map.comparator; 2596 if (fromKey != null && toKey != null && 2597 cpr(cmp, fromKey, toKey) > 0) 2598 throw new IllegalArgumentException("inconsistent range"); 2599 this.m = map; 2600 this.lo = fromKey; 2601 this.hi = toKey; 2602 this.loInclusive = fromInclusive; 2603 this.hiInclusive = toInclusive; 2604 this.isDescending = isDescending; 2605 } 2606 2607 /* ---------------- Utilities -------------- */ 2608 tooLow(Object key, Comparator<? super K> cmp)2609 boolean tooLow(Object key, Comparator<? super K> cmp) { 2610 int c; 2611 return (lo != null && ((c = cpr(cmp, key, lo)) < 0 || 2612 (c == 0 && !loInclusive))); 2613 } 2614 tooHigh(Object key, Comparator<? super K> cmp)2615 boolean tooHigh(Object key, Comparator<? super K> cmp) { 2616 int c; 2617 return (hi != null && ((c = cpr(cmp, key, hi)) > 0 || 2618 (c == 0 && !hiInclusive))); 2619 } 2620 inBounds(Object key, Comparator<? super K> cmp)2621 boolean inBounds(Object key, Comparator<? super K> cmp) { 2622 return !tooLow(key, cmp) && !tooHigh(key, cmp); 2623 } 2624 checkKeyBounds(K key, Comparator<? super K> cmp)2625 void checkKeyBounds(K key, Comparator<? super K> cmp) { 2626 if (key == null) 2627 throw new NullPointerException(); 2628 if (!inBounds(key, cmp)) 2629 throw new IllegalArgumentException("key out of range"); 2630 } 2631 2632 /** 2633 * Returns true if node key is less than upper bound of range. 2634 */ isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n, Comparator<? super K> cmp)2635 boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n, 2636 Comparator<? super K> cmp) { 2637 if (n == null) 2638 return false; 2639 if (hi == null) 2640 return true; 2641 K k = n.key; 2642 if (k == null) // pass by markers and headers 2643 return true; 2644 int c = cpr(cmp, k, hi); 2645 if (c > 0 || (c == 0 && !hiInclusive)) 2646 return false; 2647 return true; 2648 } 2649 2650 /** 2651 * Returns lowest node. This node might not be in range, so 2652 * most usages need to check bounds. 2653 */ loNode(Comparator<? super K> cmp)2654 ConcurrentSkipListMap.Node<K,V> loNode(Comparator<? super K> cmp) { 2655 if (lo == null) 2656 return m.findFirst(); 2657 else if (loInclusive) 2658 return m.findNear(lo, GT|EQ, cmp); 2659 else 2660 return m.findNear(lo, GT, cmp); 2661 } 2662 2663 /** 2664 * Returns highest node. This node might not be in range, so 2665 * most usages need to check bounds. 2666 */ hiNode(Comparator<? super K> cmp)2667 ConcurrentSkipListMap.Node<K,V> hiNode(Comparator<? super K> cmp) { 2668 if (hi == null) 2669 return m.findLast(); 2670 else if (hiInclusive) 2671 return m.findNear(hi, LT|EQ, cmp); 2672 else 2673 return m.findNear(hi, LT, cmp); 2674 } 2675 2676 /** 2677 * Returns lowest absolute key (ignoring directionality). 2678 */ lowestKey()2679 K lowestKey() { 2680 Comparator<? super K> cmp = m.comparator; 2681 ConcurrentSkipListMap.Node<K,V> n = loNode(cmp); 2682 if (isBeforeEnd(n, cmp)) 2683 return n.key; 2684 else 2685 throw new NoSuchElementException(); 2686 } 2687 2688 /** 2689 * Returns highest absolute key (ignoring directionality). 2690 */ highestKey()2691 K highestKey() { 2692 Comparator<? super K> cmp = m.comparator; 2693 ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp); 2694 if (n != null) { 2695 K last = n.key; 2696 if (inBounds(last, cmp)) 2697 return last; 2698 } 2699 throw new NoSuchElementException(); 2700 } 2701 lowestEntry()2702 Map.Entry<K,V> lowestEntry() { 2703 Comparator<? super K> cmp = m.comparator; 2704 for (;;) { 2705 ConcurrentSkipListMap.Node<K,V> n = loNode(cmp); 2706 if (!isBeforeEnd(n, cmp)) 2707 return null; 2708 Map.Entry<K,V> e = n.createSnapshot(); 2709 if (e != null) 2710 return e; 2711 } 2712 } 2713 highestEntry()2714 Map.Entry<K,V> highestEntry() { 2715 Comparator<? super K> cmp = m.comparator; 2716 for (;;) { 2717 ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp); 2718 if (n == null || !inBounds(n.key, cmp)) 2719 return null; 2720 Map.Entry<K,V> e = n.createSnapshot(); 2721 if (e != null) 2722 return e; 2723 } 2724 } 2725 removeLowest()2726 Map.Entry<K,V> removeLowest() { 2727 Comparator<? super K> cmp = m.comparator; 2728 for (;;) { 2729 Node<K,V> n = loNode(cmp); 2730 if (n == null) 2731 return null; 2732 K k = n.key; 2733 if (!inBounds(k, cmp)) 2734 return null; 2735 V v = m.doRemove(k, null); 2736 if (v != null) 2737 return new AbstractMap.SimpleImmutableEntry<K,V>(k, v); 2738 } 2739 } 2740 removeHighest()2741 Map.Entry<K,V> removeHighest() { 2742 Comparator<? super K> cmp = m.comparator; 2743 for (;;) { 2744 Node<K,V> n = hiNode(cmp); 2745 if (n == null) 2746 return null; 2747 K k = n.key; 2748 if (!inBounds(k, cmp)) 2749 return null; 2750 V v = m.doRemove(k, null); 2751 if (v != null) 2752 return new AbstractMap.SimpleImmutableEntry<K,V>(k, v); 2753 } 2754 } 2755 2756 /** 2757 * Submap version of ConcurrentSkipListMap.getNearEntry. 2758 */ getNearEntry(K key, int rel)2759 Map.Entry<K,V> getNearEntry(K key, int rel) { 2760 Comparator<? super K> cmp = m.comparator; 2761 if (isDescending) { // adjust relation for direction 2762 if ((rel & LT) == 0) 2763 rel |= LT; 2764 else 2765 rel &= ~LT; 2766 } 2767 if (tooLow(key, cmp)) 2768 return ((rel & LT) != 0) ? null : lowestEntry(); 2769 if (tooHigh(key, cmp)) 2770 return ((rel & LT) != 0) ? highestEntry() : null; 2771 for (;;) { 2772 Node<K,V> n = m.findNear(key, rel, cmp); 2773 if (n == null || !inBounds(n.key, cmp)) 2774 return null; 2775 K k = n.key; 2776 V v = n.getValidValue(); 2777 if (v != null) 2778 return new AbstractMap.SimpleImmutableEntry<K,V>(k, v); 2779 } 2780 } 2781 2782 // Almost the same as getNearEntry, except for keys getNearKey(K key, int rel)2783 K getNearKey(K key, int rel) { 2784 Comparator<? super K> cmp = m.comparator; 2785 if (isDescending) { // adjust relation for direction 2786 if ((rel & LT) == 0) 2787 rel |= LT; 2788 else 2789 rel &= ~LT; 2790 } 2791 if (tooLow(key, cmp)) { 2792 if ((rel & LT) == 0) { 2793 ConcurrentSkipListMap.Node<K,V> n = loNode(cmp); 2794 if (isBeforeEnd(n, cmp)) 2795 return n.key; 2796 } 2797 return null; 2798 } 2799 if (tooHigh(key, cmp)) { 2800 if ((rel & LT) != 0) { 2801 ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp); 2802 if (n != null) { 2803 K last = n.key; 2804 if (inBounds(last, cmp)) 2805 return last; 2806 } 2807 } 2808 return null; 2809 } 2810 for (;;) { 2811 Node<K,V> n = m.findNear(key, rel, cmp); 2812 if (n == null || !inBounds(n.key, cmp)) 2813 return null; 2814 K k = n.key; 2815 V v = n.getValidValue(); 2816 if (v != null) 2817 return k; 2818 } 2819 } 2820 2821 /* ---------------- Map API methods -------------- */ 2822 containsKey(Object key)2823 public boolean containsKey(Object key) { 2824 if (key == null) throw new NullPointerException(); 2825 return inBounds(key, m.comparator) && m.containsKey(key); 2826 } 2827 get(Object key)2828 public V get(Object key) { 2829 if (key == null) throw new NullPointerException(); 2830 return (!inBounds(key, m.comparator)) ? null : m.get(key); 2831 } 2832 put(K key, V value)2833 public V put(K key, V value) { 2834 checkKeyBounds(key, m.comparator); 2835 return m.put(key, value); 2836 } 2837 remove(Object key)2838 public V remove(Object key) { 2839 return (!inBounds(key, m.comparator)) ? null : m.remove(key); 2840 } 2841 size()2842 public int size() { 2843 Comparator<? super K> cmp = m.comparator; 2844 long count = 0; 2845 for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp); 2846 isBeforeEnd(n, cmp); 2847 n = n.next) { 2848 if (n.getValidValue() != null) 2849 ++count; 2850 } 2851 return count >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)count; 2852 } 2853 isEmpty()2854 public boolean isEmpty() { 2855 Comparator<? super K> cmp = m.comparator; 2856 return !isBeforeEnd(loNode(cmp), cmp); 2857 } 2858 containsValue(Object value)2859 public boolean containsValue(Object value) { 2860 if (value == null) 2861 throw new NullPointerException(); 2862 Comparator<? super K> cmp = m.comparator; 2863 for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp); 2864 isBeforeEnd(n, cmp); 2865 n = n.next) { 2866 V v = n.getValidValue(); 2867 if (v != null && value.equals(v)) 2868 return true; 2869 } 2870 return false; 2871 } 2872 clear()2873 public void clear() { 2874 Comparator<? super K> cmp = m.comparator; 2875 for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp); 2876 isBeforeEnd(n, cmp); 2877 n = n.next) { 2878 if (n.getValidValue() != null) 2879 m.remove(n.key); 2880 } 2881 } 2882 2883 /* ---------------- ConcurrentMap API methods -------------- */ 2884 putIfAbsent(K key, V value)2885 public V putIfAbsent(K key, V value) { 2886 checkKeyBounds(key, m.comparator); 2887 return m.putIfAbsent(key, value); 2888 } 2889 remove(Object key, Object value)2890 public boolean remove(Object key, Object value) { 2891 return inBounds(key, m.comparator) && m.remove(key, value); 2892 } 2893 replace(K key, V oldValue, V newValue)2894 public boolean replace(K key, V oldValue, V newValue) { 2895 checkKeyBounds(key, m.comparator); 2896 return m.replace(key, oldValue, newValue); 2897 } 2898 replace(K key, V value)2899 public V replace(K key, V value) { 2900 checkKeyBounds(key, m.comparator); 2901 return m.replace(key, value); 2902 } 2903 2904 /* ---------------- SortedMap API methods -------------- */ 2905 comparator()2906 public Comparator<? super K> comparator() { 2907 Comparator<? super K> cmp = m.comparator(); 2908 if (isDescending) 2909 return Collections.reverseOrder(cmp); 2910 else 2911 return cmp; 2912 } 2913 2914 /** 2915 * Utility to create submaps, where given bounds override 2916 * unbounded(null) ones and/or are checked against bounded ones. 2917 */ newSubMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)2918 SubMap<K,V> newSubMap(K fromKey, boolean fromInclusive, 2919 K toKey, boolean toInclusive) { 2920 Comparator<? super K> cmp = m.comparator; 2921 if (isDescending) { // flip senses 2922 K tk = fromKey; 2923 fromKey = toKey; 2924 toKey = tk; 2925 boolean ti = fromInclusive; 2926 fromInclusive = toInclusive; 2927 toInclusive = ti; 2928 } 2929 if (lo != null) { 2930 if (fromKey == null) { 2931 fromKey = lo; 2932 fromInclusive = loInclusive; 2933 } 2934 else { 2935 int c = cpr(cmp, fromKey, lo); 2936 if (c < 0 || (c == 0 && !loInclusive && fromInclusive)) 2937 throw new IllegalArgumentException("key out of range"); 2938 } 2939 } 2940 if (hi != null) { 2941 if (toKey == null) { 2942 toKey = hi; 2943 toInclusive = hiInclusive; 2944 } 2945 else { 2946 int c = cpr(cmp, toKey, hi); 2947 if (c > 0 || (c == 0 && !hiInclusive && toInclusive)) 2948 throw new IllegalArgumentException("key out of range"); 2949 } 2950 } 2951 return new SubMap<K,V>(m, fromKey, fromInclusive, 2952 toKey, toInclusive, isDescending); 2953 } 2954 subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)2955 public SubMap<K,V> subMap(K fromKey, boolean fromInclusive, 2956 K toKey, boolean toInclusive) { 2957 if (fromKey == null || toKey == null) 2958 throw new NullPointerException(); 2959 return newSubMap(fromKey, fromInclusive, toKey, toInclusive); 2960 } 2961 headMap(K toKey, boolean inclusive)2962 public SubMap<K,V> headMap(K toKey, boolean inclusive) { 2963 if (toKey == null) 2964 throw new NullPointerException(); 2965 return newSubMap(null, false, toKey, inclusive); 2966 } 2967 tailMap(K fromKey, boolean inclusive)2968 public SubMap<K,V> tailMap(K fromKey, boolean inclusive) { 2969 if (fromKey == null) 2970 throw new NullPointerException(); 2971 return newSubMap(fromKey, inclusive, null, false); 2972 } 2973 subMap(K fromKey, K toKey)2974 public SubMap<K,V> subMap(K fromKey, K toKey) { 2975 return subMap(fromKey, true, toKey, false); 2976 } 2977 headMap(K toKey)2978 public SubMap<K,V> headMap(K toKey) { 2979 return headMap(toKey, false); 2980 } 2981 tailMap(K fromKey)2982 public SubMap<K,V> tailMap(K fromKey) { 2983 return tailMap(fromKey, true); 2984 } 2985 descendingMap()2986 public SubMap<K,V> descendingMap() { 2987 return new SubMap<K,V>(m, lo, loInclusive, 2988 hi, hiInclusive, !isDescending); 2989 } 2990 2991 /* ---------------- Relational methods -------------- */ 2992 ceilingEntry(K key)2993 public Map.Entry<K,V> ceilingEntry(K key) { 2994 return getNearEntry(key, GT|EQ); 2995 } 2996 ceilingKey(K key)2997 public K ceilingKey(K key) { 2998 return getNearKey(key, GT|EQ); 2999 } 3000 lowerEntry(K key)3001 public Map.Entry<K,V> lowerEntry(K key) { 3002 return getNearEntry(key, LT); 3003 } 3004 lowerKey(K key)3005 public K lowerKey(K key) { 3006 return getNearKey(key, LT); 3007 } 3008 floorEntry(K key)3009 public Map.Entry<K,V> floorEntry(K key) { 3010 return getNearEntry(key, LT|EQ); 3011 } 3012 floorKey(K key)3013 public K floorKey(K key) { 3014 return getNearKey(key, LT|EQ); 3015 } 3016 higherEntry(K key)3017 public Map.Entry<K,V> higherEntry(K key) { 3018 return getNearEntry(key, GT); 3019 } 3020 higherKey(K key)3021 public K higherKey(K key) { 3022 return getNearKey(key, GT); 3023 } 3024 firstKey()3025 public K firstKey() { 3026 return isDescending ? highestKey() : lowestKey(); 3027 } 3028 lastKey()3029 public K lastKey() { 3030 return isDescending ? lowestKey() : highestKey(); 3031 } 3032 firstEntry()3033 public Map.Entry<K,V> firstEntry() { 3034 return isDescending ? highestEntry() : lowestEntry(); 3035 } 3036 lastEntry()3037 public Map.Entry<K,V> lastEntry() { 3038 return isDescending ? lowestEntry() : highestEntry(); 3039 } 3040 pollFirstEntry()3041 public Map.Entry<K,V> pollFirstEntry() { 3042 return isDescending ? removeHighest() : removeLowest(); 3043 } 3044 pollLastEntry()3045 public Map.Entry<K,V> pollLastEntry() { 3046 return isDescending ? removeLowest() : removeHighest(); 3047 } 3048 3049 /* ---------------- Submap Views -------------- */ 3050 keySet()3051 public NavigableSet<K> keySet() { 3052 KeySet<K,V> ks = keySetView; 3053 return (ks != null) ? ks : (keySetView = new KeySet<>(this)); 3054 } 3055 navigableKeySet()3056 public NavigableSet<K> navigableKeySet() { 3057 KeySet<K,V> ks = keySetView; 3058 return (ks != null) ? ks : (keySetView = new KeySet<>(this)); 3059 } 3060 values()3061 public Collection<V> values() { 3062 Collection<V> vs = valuesView; 3063 return (vs != null) ? vs : (valuesView = new Values<>(this)); 3064 } 3065 entrySet()3066 public Set<Map.Entry<K,V>> entrySet() { 3067 Set<Map.Entry<K,V>> es = entrySetView; 3068 return (es != null) ? es : (entrySetView = new EntrySet<K,V>(this)); 3069 } 3070 descendingKeySet()3071 public NavigableSet<K> descendingKeySet() { 3072 return descendingMap().navigableKeySet(); 3073 } 3074 3075 /** 3076 * Variant of main Iter class to traverse through submaps. 3077 * Also serves as back-up Spliterator for views. 3078 */ 3079 abstract class SubMapIter<T> implements Iterator<T>, Spliterator<T> { 3080 /** the last node returned by next() */ 3081 Node<K,V> lastReturned; 3082 /** the next node to return from next(); */ 3083 Node<K,V> next; 3084 /** Cache of next value field to maintain weak consistency */ 3085 V nextValue; 3086 SubMapIter()3087 SubMapIter() { 3088 Comparator<? super K> cmp = m.comparator; 3089 for (;;) { 3090 next = isDescending ? hiNode(cmp) : loNode(cmp); 3091 if (next == null) 3092 break; 3093 Object x = next.value; 3094 if (x != null && x != next) { 3095 if (! inBounds(next.key, cmp)) 3096 next = null; 3097 else { 3098 @SuppressWarnings("unchecked") V vv = (V)x; 3099 nextValue = vv; 3100 } 3101 break; 3102 } 3103 } 3104 } 3105 hasNext()3106 public final boolean hasNext() { 3107 return next != null; 3108 } 3109 advance()3110 final void advance() { 3111 if (next == null) 3112 throw new NoSuchElementException(); 3113 lastReturned = next; 3114 if (isDescending) 3115 descend(); 3116 else 3117 ascend(); 3118 } 3119 ascend()3120 private void ascend() { 3121 Comparator<? super K> cmp = m.comparator; 3122 for (;;) { 3123 next = next.next; 3124 if (next == null) 3125 break; 3126 Object x = next.value; 3127 if (x != null && x != next) { 3128 if (tooHigh(next.key, cmp)) 3129 next = null; 3130 else { 3131 @SuppressWarnings("unchecked") V vv = (V)x; 3132 nextValue = vv; 3133 } 3134 break; 3135 } 3136 } 3137 } 3138 descend()3139 private void descend() { 3140 Comparator<? super K> cmp = m.comparator; 3141 for (;;) { 3142 next = m.findNear(lastReturned.key, LT, cmp); 3143 if (next == null) 3144 break; 3145 Object x = next.value; 3146 if (x != null && x != next) { 3147 if (tooLow(next.key, cmp)) 3148 next = null; 3149 else { 3150 @SuppressWarnings("unchecked") V vv = (V)x; 3151 nextValue = vv; 3152 } 3153 break; 3154 } 3155 } 3156 } 3157 remove()3158 public void remove() { 3159 Node<K,V> l = lastReturned; 3160 if (l == null) 3161 throw new IllegalStateException(); 3162 m.remove(l.key); 3163 lastReturned = null; 3164 } 3165 trySplit()3166 public Spliterator<T> trySplit() { 3167 return null; 3168 } 3169 tryAdvance(Consumer<? super T> action)3170 public boolean tryAdvance(Consumer<? super T> action) { 3171 if (hasNext()) { 3172 action.accept(next()); 3173 return true; 3174 } 3175 return false; 3176 } 3177 forEachRemaining(Consumer<? super T> action)3178 public void forEachRemaining(Consumer<? super T> action) { 3179 while (hasNext()) 3180 action.accept(next()); 3181 } 3182 estimateSize()3183 public long estimateSize() { 3184 return Long.MAX_VALUE; 3185 } 3186 3187 } 3188 3189 final class SubMapValueIterator extends SubMapIter<V> { next()3190 public V next() { 3191 V v = nextValue; 3192 advance(); 3193 return v; 3194 } characteristics()3195 public int characteristics() { 3196 return 0; 3197 } 3198 } 3199 3200 final class SubMapKeyIterator extends SubMapIter<K> { next()3201 public K next() { 3202 Node<K,V> n = next; 3203 advance(); 3204 return n.key; 3205 } characteristics()3206 public int characteristics() { 3207 return Spliterator.DISTINCT | Spliterator.ORDERED | 3208 Spliterator.SORTED; 3209 } getComparator()3210 public final Comparator<? super K> getComparator() { 3211 return SubMap.this.comparator(); 3212 } 3213 } 3214 3215 final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> { next()3216 public Map.Entry<K,V> next() { 3217 Node<K,V> n = next; 3218 V v = nextValue; 3219 advance(); 3220 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v); 3221 } characteristics()3222 public int characteristics() { 3223 return Spliterator.DISTINCT; 3224 } 3225 } 3226 } 3227 3228 // default Map method overrides 3229 forEach(BiConsumer<? super K, ? super V> action)3230 public void forEach(BiConsumer<? super K, ? super V> action) { 3231 if (action == null) throw new NullPointerException(); 3232 V v; 3233 for (Node<K,V> n = findFirst(); n != null; n = n.next) { 3234 if ((v = n.getValidValue()) != null) 3235 action.accept(n.key, v); 3236 } 3237 } 3238 replaceAll(BiFunction<? super K, ? super V, ? extends V> function)3239 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 3240 if (function == null) throw new NullPointerException(); 3241 V v; 3242 for (Node<K,V> n = findFirst(); n != null; n = n.next) { 3243 while ((v = n.getValidValue()) != null) { 3244 V r = function.apply(n.key, v); 3245 if (r == null) throw new NullPointerException(); 3246 if (n.casValue(v, r)) 3247 break; 3248 } 3249 } 3250 } 3251 3252 /** 3253 * Helper method for EntrySet.removeIf. 3254 */ removeEntryIf(Predicate<? super Entry<K,V>> function)3255 boolean removeEntryIf(Predicate<? super Entry<K,V>> function) { 3256 if (function == null) throw new NullPointerException(); 3257 boolean removed = false; 3258 for (Node<K,V> n = findFirst(); n != null; n = n.next) { 3259 V v; 3260 if ((v = n.getValidValue()) != null) { 3261 K k = n.key; 3262 Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v); 3263 if (function.test(e) && remove(k, v)) 3264 removed = true; 3265 } 3266 } 3267 return removed; 3268 } 3269 3270 /** 3271 * Helper method for Values.removeIf. 3272 */ removeValueIf(Predicate<? super V> function)3273 boolean removeValueIf(Predicate<? super V> function) { 3274 if (function == null) throw new NullPointerException(); 3275 boolean removed = false; 3276 for (Node<K,V> n = findFirst(); n != null; n = n.next) { 3277 V v; 3278 if ((v = n.getValidValue()) != null) { 3279 K k = n.key; 3280 if (function.test(v) && remove(k, v)) 3281 removed = true; 3282 } 3283 } 3284 return removed; 3285 } 3286 3287 /** 3288 * Base class providing common structure for Spliterators. 3289 * (Although not all that much common functionality; as usual for 3290 * view classes, details annoyingly vary in key, value, and entry 3291 * subclasses in ways that are not worth abstracting out for 3292 * internal classes.) 3293 * 3294 * The basic split strategy is to recursively descend from top 3295 * level, row by row, descending to next row when either split 3296 * off, or the end of row is encountered. Control of the number of 3297 * splits relies on some statistical estimation: The expected 3298 * remaining number of elements of a skip list when advancing 3299 * either across or down decreases by about 25%. To make this 3300 * observation useful, we need to know initial size, which we 3301 * don't. But we can just use Integer.MAX_VALUE so that we 3302 * don't prematurely zero out while splitting. 3303 */ 3304 abstract static class CSLMSpliterator<K,V> { 3305 final Comparator<? super K> comparator; 3306 final K fence; // exclusive upper bound for keys, or null if to end 3307 Index<K,V> row; // the level to split out 3308 Node<K,V> current; // current traversal node; initialize at origin 3309 int est; // pseudo-size estimate CSLMSpliterator(Comparator<? super K> comparator, Index<K,V> row, Node<K,V> origin, K fence, int est)3310 CSLMSpliterator(Comparator<? super K> comparator, Index<K,V> row, 3311 Node<K,V> origin, K fence, int est) { 3312 this.comparator = comparator; this.row = row; 3313 this.current = origin; this.fence = fence; this.est = est; 3314 } 3315 estimateSize()3316 public final long estimateSize() { return (long)est; } 3317 } 3318 3319 static final class KeySpliterator<K,V> extends CSLMSpliterator<K,V> 3320 implements Spliterator<K> { KeySpliterator(Comparator<? super K> comparator, Index<K,V> row, Node<K,V> origin, K fence, int est)3321 KeySpliterator(Comparator<? super K> comparator, Index<K,V> row, 3322 Node<K,V> origin, K fence, int est) { 3323 super(comparator, row, origin, fence, est); 3324 } 3325 trySplit()3326 public KeySpliterator<K,V> trySplit() { 3327 Node<K,V> e; K ek; 3328 Comparator<? super K> cmp = comparator; 3329 K f = fence; 3330 if ((e = current) != null && (ek = e.key) != null) { 3331 for (Index<K,V> q = row; q != null; q = row = q.down) { 3332 Index<K,V> s; Node<K,V> b, n; K sk; 3333 if ((s = q.right) != null && (b = s.node) != null && 3334 (n = b.next) != null && n.value != null && 3335 (sk = n.key) != null && cpr(cmp, sk, ek) > 0 && 3336 (f == null || cpr(cmp, sk, f) < 0)) { 3337 current = n; 3338 Index<K,V> r = q.down; 3339 row = (s.right != null) ? s : s.down; 3340 est -= est >>> 2; 3341 return new KeySpliterator<K,V>(cmp, r, e, sk, est); 3342 } 3343 } 3344 } 3345 return null; 3346 } 3347 forEachRemaining(Consumer<? super K> action)3348 public void forEachRemaining(Consumer<? super K> action) { 3349 if (action == null) throw new NullPointerException(); 3350 Comparator<? super K> cmp = comparator; 3351 K f = fence; 3352 Node<K,V> e = current; 3353 current = null; 3354 for (; e != null; e = e.next) { 3355 K k; Object v; 3356 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) 3357 break; 3358 if ((v = e.value) != null && v != e) 3359 action.accept(k); 3360 } 3361 } 3362 tryAdvance(Consumer<? super K> action)3363 public boolean tryAdvance(Consumer<? super K> action) { 3364 if (action == null) throw new NullPointerException(); 3365 Comparator<? super K> cmp = comparator; 3366 K f = fence; 3367 Node<K,V> e = current; 3368 for (; e != null; e = e.next) { 3369 K k; Object v; 3370 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) { 3371 e = null; 3372 break; 3373 } 3374 if ((v = e.value) != null && v != e) { 3375 current = e.next; 3376 action.accept(k); 3377 return true; 3378 } 3379 } 3380 current = e; 3381 return false; 3382 } 3383 characteristics()3384 public int characteristics() { 3385 return Spliterator.DISTINCT | Spliterator.SORTED | 3386 Spliterator.ORDERED | Spliterator.CONCURRENT | 3387 Spliterator.NONNULL; 3388 } 3389 getComparator()3390 public final Comparator<? super K> getComparator() { 3391 return comparator; 3392 } 3393 } 3394 // factory method for KeySpliterator keySpliterator()3395 final KeySpliterator<K,V> keySpliterator() { 3396 Comparator<? super K> cmp = comparator; 3397 for (;;) { // ensure h corresponds to origin p 3398 HeadIndex<K,V> h; Node<K,V> p; 3399 Node<K,V> b = (h = head).node; 3400 if ((p = b.next) == null || p.value != null) 3401 return new KeySpliterator<K,V>(cmp, h, p, null, (p == null) ? 3402 0 : Integer.MAX_VALUE); 3403 p.helpDelete(b, p.next); 3404 } 3405 } 3406 3407 static final class ValueSpliterator<K,V> extends CSLMSpliterator<K,V> 3408 implements Spliterator<V> { ValueSpliterator(Comparator<? super K> comparator, Index<K,V> row, Node<K,V> origin, K fence, int est)3409 ValueSpliterator(Comparator<? super K> comparator, Index<K,V> row, 3410 Node<K,V> origin, K fence, int est) { 3411 super(comparator, row, origin, fence, est); 3412 } 3413 trySplit()3414 public ValueSpliterator<K,V> trySplit() { 3415 Node<K,V> e; K ek; 3416 Comparator<? super K> cmp = comparator; 3417 K f = fence; 3418 if ((e = current) != null && (ek = e.key) != null) { 3419 for (Index<K,V> q = row; q != null; q = row = q.down) { 3420 Index<K,V> s; Node<K,V> b, n; K sk; 3421 if ((s = q.right) != null && (b = s.node) != null && 3422 (n = b.next) != null && n.value != null && 3423 (sk = n.key) != null && cpr(cmp, sk, ek) > 0 && 3424 (f == null || cpr(cmp, sk, f) < 0)) { 3425 current = n; 3426 Index<K,V> r = q.down; 3427 row = (s.right != null) ? s : s.down; 3428 est -= est >>> 2; 3429 return new ValueSpliterator<K,V>(cmp, r, e, sk, est); 3430 } 3431 } 3432 } 3433 return null; 3434 } 3435 forEachRemaining(Consumer<? super V> action)3436 public void forEachRemaining(Consumer<? super V> action) { 3437 if (action == null) throw new NullPointerException(); 3438 Comparator<? super K> cmp = comparator; 3439 K f = fence; 3440 Node<K,V> e = current; 3441 current = null; 3442 for (; e != null; e = e.next) { 3443 K k; Object v; 3444 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) 3445 break; 3446 if ((v = e.value) != null && v != e) { 3447 @SuppressWarnings("unchecked") V vv = (V)v; 3448 action.accept(vv); 3449 } 3450 } 3451 } 3452 tryAdvance(Consumer<? super V> action)3453 public boolean tryAdvance(Consumer<? super V> action) { 3454 if (action == null) throw new NullPointerException(); 3455 Comparator<? super K> cmp = comparator; 3456 K f = fence; 3457 Node<K,V> e = current; 3458 for (; e != null; e = e.next) { 3459 K k; Object v; 3460 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) { 3461 e = null; 3462 break; 3463 } 3464 if ((v = e.value) != null && v != e) { 3465 current = e.next; 3466 @SuppressWarnings("unchecked") V vv = (V)v; 3467 action.accept(vv); 3468 return true; 3469 } 3470 } 3471 current = e; 3472 return false; 3473 } 3474 characteristics()3475 public int characteristics() { 3476 return Spliterator.CONCURRENT | Spliterator.ORDERED | 3477 Spliterator.NONNULL; 3478 } 3479 } 3480 3481 // Almost the same as keySpliterator() valueSpliterator()3482 final ValueSpliterator<K,V> valueSpliterator() { 3483 Comparator<? super K> cmp = comparator; 3484 for (;;) { 3485 HeadIndex<K,V> h; Node<K,V> p; 3486 Node<K,V> b = (h = head).node; 3487 if ((p = b.next) == null || p.value != null) 3488 return new ValueSpliterator<K,V>(cmp, h, p, null, (p == null) ? 3489 0 : Integer.MAX_VALUE); 3490 p.helpDelete(b, p.next); 3491 } 3492 } 3493 3494 static final class EntrySpliterator<K,V> extends CSLMSpliterator<K,V> 3495 implements Spliterator<Map.Entry<K,V>> { EntrySpliterator(Comparator<? super K> comparator, Index<K,V> row, Node<K,V> origin, K fence, int est)3496 EntrySpliterator(Comparator<? super K> comparator, Index<K,V> row, 3497 Node<K,V> origin, K fence, int est) { 3498 super(comparator, row, origin, fence, est); 3499 } 3500 trySplit()3501 public EntrySpliterator<K,V> trySplit() { 3502 Node<K,V> e; K ek; 3503 Comparator<? super K> cmp = comparator; 3504 K f = fence; 3505 if ((e = current) != null && (ek = e.key) != null) { 3506 for (Index<K,V> q = row; q != null; q = row = q.down) { 3507 Index<K,V> s; Node<K,V> b, n; K sk; 3508 if ((s = q.right) != null && (b = s.node) != null && 3509 (n = b.next) != null && n.value != null && 3510 (sk = n.key) != null && cpr(cmp, sk, ek) > 0 && 3511 (f == null || cpr(cmp, sk, f) < 0)) { 3512 current = n; 3513 Index<K,V> r = q.down; 3514 row = (s.right != null) ? s : s.down; 3515 est -= est >>> 2; 3516 return new EntrySpliterator<K,V>(cmp, r, e, sk, est); 3517 } 3518 } 3519 } 3520 return null; 3521 } 3522 forEachRemaining(Consumer<? super Map.Entry<K,V>> action)3523 public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) { 3524 if (action == null) throw new NullPointerException(); 3525 Comparator<? super K> cmp = comparator; 3526 K f = fence; 3527 Node<K,V> e = current; 3528 current = null; 3529 for (; e != null; e = e.next) { 3530 K k; Object v; 3531 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) 3532 break; 3533 if ((v = e.value) != null && v != e) { 3534 @SuppressWarnings("unchecked") V vv = (V)v; 3535 action.accept 3536 (new AbstractMap.SimpleImmutableEntry<K,V>(k, vv)); 3537 } 3538 } 3539 } 3540 tryAdvance(Consumer<? super Map.Entry<K,V>> action)3541 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) { 3542 if (action == null) throw new NullPointerException(); 3543 Comparator<? super K> cmp = comparator; 3544 K f = fence; 3545 Node<K,V> e = current; 3546 for (; e != null; e = e.next) { 3547 K k; Object v; 3548 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) { 3549 e = null; 3550 break; 3551 } 3552 if ((v = e.value) != null && v != e) { 3553 current = e.next; 3554 @SuppressWarnings("unchecked") V vv = (V)v; 3555 action.accept 3556 (new AbstractMap.SimpleImmutableEntry<K,V>(k, vv)); 3557 return true; 3558 } 3559 } 3560 current = e; 3561 return false; 3562 } 3563 characteristics()3564 public int characteristics() { 3565 return Spliterator.DISTINCT | Spliterator.SORTED | 3566 Spliterator.ORDERED | Spliterator.CONCURRENT | 3567 Spliterator.NONNULL; 3568 } 3569 getComparator()3570 public final Comparator<Map.Entry<K,V>> getComparator() { 3571 // Adapt or create a key-based comparator 3572 if (comparator != null) { 3573 return Map.Entry.comparingByKey(comparator); 3574 } 3575 else { 3576 return (Comparator<Map.Entry<K,V>> & Serializable) (e1, e2) -> { 3577 @SuppressWarnings("unchecked") 3578 Comparable<? super K> k1 = (Comparable<? super K>) e1.getKey(); 3579 return k1.compareTo(e2.getKey()); 3580 }; 3581 } 3582 } 3583 } 3584 3585 // Almost the same as keySpliterator() entrySpliterator()3586 final EntrySpliterator<K,V> entrySpliterator() { 3587 Comparator<? super K> cmp = comparator; 3588 for (;;) { // almost same as key version 3589 HeadIndex<K,V> h; Node<K,V> p; 3590 Node<K,V> b = (h = head).node; 3591 if ((p = b.next) == null || p.value != null) 3592 return new EntrySpliterator<K,V>(cmp, h, p, null, (p == null) ? 3593 0 : Integer.MAX_VALUE); 3594 p.helpDelete(b, p.next); 3595 } 3596 } 3597 3598 // Unsafe mechanics 3599 private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 3600 private static final long HEAD; 3601 static { 3602 try { 3603 HEAD = U.objectFieldOffset 3604 (ConcurrentSkipListMap.class.getDeclaredField("head")); 3605 } catch (ReflectiveOperationException e) { 3606 throw new Error(e); 3607 } 3608 } 3609 } 3610