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