1 /* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3 * 4 * This code is free software; you can redistribute it and/or modify it 5 * under the terms of the GNU General Public License version 2 only, as 6 * published by the Free Software Foundation. Oracle designates this 7 * particular file as subject to the "Classpath" exception as provided 8 * by Oracle in the LICENSE file that accompanied this code. 9 * 10 * This code is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 13 * version 2 for more details (a copy is included in the LICENSE file that 14 * accompanied this code). 15 * 16 * You should have received a copy of the GNU General Public License version 17 * 2 along with this work; if not, write to the Free Software Foundation, 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 19 * 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21 * or visit www.oracle.com if you need additional information or have any 22 * questions. 23 */ 24 25 /* 26 * This file is available under and governed by the GNU General Public 27 * License version 2 only, as published by the Free Software Foundation. 28 * However, the following notice accompanied the original version of this 29 * file: 30 * 31 * Written by Doug Lea with assistance from members of JCP JSR-166 32 * Expert Group and released to the public domain, as explained at 33 * http://creativecommons.org/publicdomain/zero/1.0/ 34 */ 35 36 package java.util.concurrent; 37 import java.io.Serializable; 38 import java.util.AbstractCollection; 39 import java.util.AbstractMap; 40 import java.util.AbstractSet; 41 import java.util.ArrayList; 42 import java.util.Collection; 43 import java.util.Collections; 44 import java.util.Comparator; 45 import java.util.Iterator; 46 import java.util.List; 47 import java.util.Map; 48 import java.util.NavigableMap; 49 import java.util.NavigableSet; 50 import java.util.NoSuchElementException; 51 import java.util.Set; 52 import java.util.SortedMap; 53 import java.util.SortedSet; 54 import java.util.Spliterator; 55 import java.util.concurrent.ConcurrentMap; 56 import java.util.concurrent.ConcurrentNavigableMap; 57 import java.util.function.BiFunction; 58 import java.util.function.Consumer; 59 import java.util.function.BiConsumer; 60 import java.util.function.Function; 61 import 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}/../technotes/guides/collections/index.html"> 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 */ 117 public 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 private 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> keySet; 381 /** Lazily initialized entry set */ 382 private transient EntrySet<K,V> entrySet; 383 /** Lazily initialized values collection */ 384 private transient Values<V> values; 385 /** Lazily initialized descending key set */ 386 private transient ConcurrentNavigableMap<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 UNSAFE.compareAndSwapObject(this, headOffset, 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 UNSAFE.compareAndSwapObject(this, valueOffset, cmp, val); 450 } 451 452 /** 453 * compareAndSet next field 454 */ 455 boolean casNext(Node<K,V> cmp, Node<K,V> val) { 456 return UNSAFE.compareAndSwapObject(this, nextOffset, 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 // UNSAFE mechanics 538 539 private static final sun.misc.Unsafe UNSAFE; 540 private static final long valueOffset; 541 private static final long nextOffset; 542 543 static { 544 try { 545 UNSAFE = sun.misc.Unsafe.getUnsafe(); 546 Class<?> k = Node.class; 547 valueOffset = UNSAFE.objectFieldOffset 548 (k.getDeclaredField("value")); 549 nextOffset = UNSAFE.objectFieldOffset 550 (k.getDeclaredField("next")); 551 } catch (Exception e) { 552 throw new Error(e); 553 } 554 } 555 } 556 557 /* ---------------- Indexing -------------- */ 558 559 /** 560 * Index nodes represent the levels of the skip list. Note that 561 * even though both Nodes and Indexes have forward-pointing 562 * fields, they have different types and are handled in different 563 * ways, that can't nicely be captured by placing field in a 564 * shared abstract class. 565 */ 566 static class Index<K,V> { 567 final Node<K,V> node; 568 final Index<K,V> down; 569 volatile Index<K,V> right; 570 571 /** 572 * Creates index node with given values. 573 */ 574 Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) { 575 this.node = node; 576 this.down = down; 577 this.right = right; 578 } 579 580 /** 581 * compareAndSet right field 582 */ 583 final boolean casRight(Index<K,V> cmp, Index<K,V> val) { 584 return UNSAFE.compareAndSwapObject(this, rightOffset, cmp, val); 585 } 586 587 /** 588 * Returns true if the node this indexes has been deleted. 589 * @return true if indexed node is known to be deleted 590 */ 591 final boolean indexesDeletedNode() { 592 return node.value == null; 593 } 594 595 /** 596 * Tries to CAS newSucc as successor. To minimize races with 597 * unlink that may lose this index node, if the node being 598 * indexed is known to be deleted, it doesn't try to link in. 599 * @param succ the expected current successor 600 * @param newSucc the new successor 601 * @return true if successful 602 */ 603 final boolean link(Index<K,V> succ, Index<K,V> newSucc) { 604 Node<K,V> n = node; 605 newSucc.right = succ; 606 return n.value != null && casRight(succ, newSucc); 607 } 608 609 /** 610 * Tries to CAS right field to skip over apparent successor 611 * succ. Fails (forcing a retraversal by caller) if this node 612 * is known to be deleted. 613 * @param succ the expected current successor 614 * @return true if successful 615 */ 616 final boolean unlink(Index<K,V> succ) { 617 return node.value != null && casRight(succ, succ.right); 618 } 619 620 // Unsafe mechanics 621 private static final sun.misc.Unsafe UNSAFE; 622 private static final long rightOffset; 623 static { 624 try { 625 UNSAFE = sun.misc.Unsafe.getUnsafe(); 626 Class<?> k = Index.class; 627 rightOffset = UNSAFE.objectFieldOffset 628 (k.getDeclaredField("right")); 629 } catch (Exception e) { 630 throw new Error(e); 631 } 632 } 633 } 634 635 /* ---------------- Head nodes -------------- */ 636 637 /** 638 * Nodes heading each level keep track of their level. 639 */ 640 static final class HeadIndex<K,V> extends Index<K,V> { 641 final int level; 642 HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) { 643 super(node, down, right); 644 this.level = level; 645 } 646 } 647 648 /* ---------------- Comparison utilities -------------- */ 649 650 /** 651 * Compares using comparator or natural ordering if null. 652 * Called only by methods that have performed required type checks. 653 */ 654 @SuppressWarnings({"unchecked", "rawtypes"}) 655 static final int cpr(Comparator c, Object x, Object y) { 656 return (c != null) ? c.compare(x, y) : ((Comparable)x).compareTo(y); 657 } 658 659 /* ---------------- Traversal -------------- */ 660 661 /** 662 * Returns a base-level node with key strictly less than given key, 663 * or the base-level header if there is no such node. Also 664 * unlinks indexes to deleted nodes found along the way. Callers 665 * rely on this side-effect of clearing indices to deleted nodes. 666 * @param key the key 667 * @return a predecessor of key 668 */ 669 private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) { 670 if (key == null) 671 throw new NullPointerException(); // don't postpone errors 672 for (;;) { 673 for (Index<K,V> q = head, r = q.right, d;;) { 674 if (r != null) { 675 Node<K,V> n = r.node; 676 K k = n.key; 677 if (n.value == null) { 678 if (!q.unlink(r)) 679 break; // restart 680 r = q.right; // reread r 681 continue; 682 } 683 if (cpr(cmp, key, k) > 0) { 684 q = r; 685 r = r.right; 686 continue; 687 } 688 } 689 if ((d = q.down) == null) 690 return q.node; 691 q = d; 692 r = d.right; 693 } 694 } 695 } 696 697 /** 698 * Returns node holding key or null if no such, clearing out any 699 * deleted nodes seen along the way. Repeatedly traverses at 700 * base-level looking for key starting at predecessor returned 701 * from findPredecessor, processing base-level deletions as 702 * encountered. Some callers rely on this side-effect of clearing 703 * deleted nodes. 704 * 705 * Restarts occur, at traversal step centered on node n, if: 706 * 707 * (1) After reading n's next field, n is no longer assumed 708 * predecessor b's current successor, which means that 709 * we don't have a consistent 3-node snapshot and so cannot 710 * unlink any subsequent deleted nodes encountered. 711 * 712 * (2) n's value field is null, indicating n is deleted, in 713 * which case we help out an ongoing structural deletion 714 * before retrying. Even though there are cases where such 715 * unlinking doesn't require restart, they aren't sorted out 716 * here because doing so would not usually outweigh cost of 717 * restarting. 718 * 719 * (3) n is a marker or n's predecessor's value field is null, 720 * indicating (among other possibilities) that 721 * findPredecessor returned a deleted node. We can't unlink 722 * the node because we don't know its predecessor, so rely 723 * on another call to findPredecessor to notice and return 724 * some earlier predecessor, which it will do. This check is 725 * only strictly needed at beginning of loop, (and the 726 * b.value check isn't strictly needed at all) but is done 727 * each iteration to help avoid contention with other 728 * threads by callers that will fail to be able to change 729 * links, and so will retry anyway. 730 * 731 * The traversal loops in doPut, doRemove, and findNear all 732 * include the same three kinds of checks. And specialized 733 * versions appear in findFirst, and findLast and their 734 * variants. They can't easily share code because each uses the 735 * reads of fields held in locals occurring in the orders they 736 * were performed. 737 * 738 * @param key the key 739 * @return node holding key, or null if no such 740 */ 741 private Node<K,V> findNode(Object key) { 742 if (key == null) 743 throw new NullPointerException(); // don't postpone errors 744 Comparator<? super K> cmp = comparator; 745 outer: for (;;) { 746 for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) { 747 Object v; int c; 748 if (n == null) 749 break outer; 750 Node<K,V> f = n.next; 751 if (n != b.next) // inconsistent read 752 break; 753 if ((v = n.value) == null) { // n is deleted 754 n.helpDelete(b, f); 755 break; 756 } 757 if (b.value == null || v == n) // b is deleted 758 break; 759 if ((c = cpr(cmp, key, n.key)) == 0) 760 return n; 761 if (c < 0) 762 break outer; 763 b = n; 764 n = f; 765 } 766 } 767 return null; 768 } 769 770 /** 771 * Gets value for key. Almost the same as findNode, but returns 772 * the found value (to avoid retries during re-reads) 773 * 774 * @param key the key 775 * @return the value, or null if absent 776 */ 777 private V doGet(Object key) { 778 if (key == null) 779 throw new NullPointerException(); 780 Comparator<? super K> cmp = comparator; 781 outer: for (;;) { 782 for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) { 783 Object v; int c; 784 if (n == null) 785 break outer; 786 Node<K,V> f = n.next; 787 if (n != b.next) // inconsistent read 788 break; 789 if ((v = n.value) == null) { // n is deleted 790 n.helpDelete(b, f); 791 break; 792 } 793 if (b.value == null || v == n) // b is deleted 794 break; 795 if ((c = cpr(cmp, key, n.key)) == 0) { 796 @SuppressWarnings("unchecked") V vv = (V)v; 797 return vv; 798 } 799 if (c < 0) 800 break outer; 801 b = n; 802 n = f; 803 } 804 } 805 return null; 806 } 807 808 /* ---------------- Insertion -------------- */ 809 810 /** 811 * Main insertion method. Adds element if not present, or 812 * replaces value if present and onlyIfAbsent is false. 813 * @param key the key 814 * @param value the value that must be associated with key 815 * @param onlyIfAbsent if should not insert if already present 816 * @return the old value, or null if newly inserted 817 */ 818 private V doPut(K key, V value, boolean onlyIfAbsent) { 819 Node<K,V> z; // added node 820 if (key == null) 821 throw new NullPointerException(); 822 Comparator<? super K> cmp = comparator; 823 outer: for (;;) { 824 for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) { 825 if (n != null) { 826 Object v; int c; 827 Node<K,V> f = n.next; 828 if (n != b.next) // inconsistent read 829 break; 830 if ((v = n.value) == null) { // n is deleted 831 n.helpDelete(b, f); 832 break; 833 } 834 if (b.value == null || v == n) // b is deleted 835 break; 836 if ((c = cpr(cmp, key, n.key)) > 0) { 837 b = n; 838 n = f; 839 continue; 840 } 841 if (c == 0) { 842 if (onlyIfAbsent || n.casValue(v, value)) { 843 @SuppressWarnings("unchecked") V vv = (V)v; 844 return vv; 845 } 846 break; // restart if lost race to replace value 847 } 848 // else c < 0; fall through 849 } 850 851 z = new Node<K,V>(key, value, n); 852 if (!b.casNext(n, z)) 853 break; // restart if lost race to append to b 854 break outer; 855 } 856 } 857 858 int rnd = ThreadLocalRandom.nextSecondarySeed(); 859 if ((rnd & 0x80000001) == 0) { // test highest and lowest bits 860 int level = 1, max; 861 while (((rnd >>>= 1) & 1) != 0) 862 ++level; 863 Index<K,V> idx = null; 864 HeadIndex<K,V> h = head; 865 if (level <= (max = h.level)) { 866 for (int i = 1; i <= level; ++i) 867 idx = new Index<K,V>(z, idx, null); 868 } 869 else { // try to grow by one level 870 level = max + 1; // hold in array and later pick the one to use 871 @SuppressWarnings("unchecked")Index<K,V>[] idxs = 872 (Index<K,V>[])new Index<?,?>[level+1]; 873 for (int i = 1; i <= level; ++i) 874 idxs[i] = idx = new Index<K,V>(z, idx, null); 875 for (;;) { 876 h = head; 877 int oldLevel = h.level; 878 if (level <= oldLevel) // lost race to add level 879 break; 880 HeadIndex<K,V> newh = h; 881 Node<K,V> oldbase = h.node; 882 for (int j = oldLevel+1; j <= level; ++j) 883 newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j); 884 if (casHead(h, newh)) { 885 h = newh; 886 idx = idxs[level = oldLevel]; 887 break; 888 } 889 } 890 } 891 // find insertion points and splice in 892 splice: for (int insertionLevel = level;;) { 893 int j = h.level; 894 for (Index<K,V> q = h, r = q.right, t = idx;;) { 895 if (q == null || t == null) 896 break splice; 897 if (r != null) { 898 Node<K,V> n = r.node; 899 // compare before deletion check avoids needing recheck 900 int c = cpr(cmp, key, n.key); 901 if (n.value == null) { 902 if (!q.unlink(r)) 903 break; 904 r = q.right; 905 continue; 906 } 907 if (c > 0) { 908 q = r; 909 r = r.right; 910 continue; 911 } 912 } 913 914 if (j == insertionLevel) { 915 if (!q.link(r, t)) 916 break; // restart 917 if (t.node.value == null) { 918 findNode(key); 919 break splice; 920 } 921 if (--insertionLevel == 0) 922 break splice; 923 } 924 925 if (--j >= insertionLevel && j < level) 926 t = t.down; 927 q = q.down; 928 r = q.right; 929 } 930 } 931 } 932 return null; 933 } 934 935 /* ---------------- Deletion -------------- */ 936 937 /** 938 * Main deletion method. Locates node, nulls value, appends a 939 * deletion marker, unlinks predecessor, removes associated index 940 * nodes, and possibly reduces head index level. 941 * 942 * Index nodes are cleared out simply by calling findPredecessor. 943 * which unlinks indexes to deleted nodes found along path to key, 944 * which will include the indexes to this node. This is done 945 * unconditionally. We can't check beforehand whether there are 946 * index nodes because it might be the case that some or all 947 * indexes hadn't been inserted yet for this node during initial 948 * search for it, and we'd like to ensure lack of garbage 949 * retention, so must call to be sure. 950 * 951 * @param key the key 952 * @param value if non-null, the value that must be 953 * associated with key 954 * @return the node, or null if not found 955 */ 956 final V doRemove(Object key, Object value) { 957 if (key == null) 958 throw new NullPointerException(); 959 Comparator<? super K> cmp = comparator; 960 outer: for (;;) { 961 for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) { 962 Object v; int c; 963 if (n == null) 964 break outer; 965 Node<K,V> f = n.next; 966 if (n != b.next) // inconsistent read 967 break; 968 if ((v = n.value) == null) { // n is deleted 969 n.helpDelete(b, f); 970 break; 971 } 972 if (b.value == null || v == n) // b is deleted 973 break; 974 if ((c = cpr(cmp, key, n.key)) < 0) 975 break outer; 976 if (c > 0) { 977 b = n; 978 n = f; 979 continue; 980 } 981 if (value != null && !value.equals(v)) 982 break outer; 983 if (!n.casValue(v, null)) 984 break; 985 if (!n.appendMarker(f) || !b.casNext(n, f)) 986 findNode(key); // retry via findNode 987 else { 988 findPredecessor(key, cmp); // clean index 989 if (head.right == null) 990 tryReduceLevel(); 991 } 992 @SuppressWarnings("unchecked") V vv = (V)v; 993 return vv; 994 } 995 } 996 return null; 997 } 998 999 /** 1000 * Possibly reduce head level if it has no nodes. This method can 1001 * (rarely) make mistakes, in which case levels can disappear even 1002 * though they are about to contain index nodes. This impacts 1003 * performance, not correctness. To minimize mistakes as well as 1004 * to reduce hysteresis, the level is reduced by one only if the 1005 * topmost three levels look empty. Also, if the removed level 1006 * looks non-empty after CAS, we try to change it back quick 1007 * before anyone notices our mistake! (This trick works pretty 1008 * well because this method will practically never make mistakes 1009 * unless current thread stalls immediately before first CAS, in 1010 * which case it is very unlikely to stall again immediately 1011 * afterwards, so will recover.) 1012 * 1013 * We put up with all this rather than just let levels grow 1014 * because otherwise, even a small map that has undergone a large 1015 * number of insertions and removals will have a lot of levels, 1016 * slowing down access more than would an occasional unwanted 1017 * reduction. 1018 */ 1019 private void tryReduceLevel() { 1020 HeadIndex<K,V> h = head; 1021 HeadIndex<K,V> d; 1022 HeadIndex<K,V> e; 1023 if (h.level > 3 && 1024 (d = (HeadIndex<K,V>)h.down) != null && 1025 (e = (HeadIndex<K,V>)d.down) != null && 1026 e.right == null && 1027 d.right == null && 1028 h.right == null && 1029 casHead(h, d) && // try to set 1030 h.right != null) // recheck 1031 casHead(d, h); // try to backout 1032 } 1033 1034 /* ---------------- Finding and removing first element -------------- */ 1035 1036 /** 1037 * Specialized variant of findNode to get first valid node. 1038 * @return first node or null if empty 1039 */ 1040 final Node<K,V> findFirst() { 1041 for (Node<K,V> b, n;;) { 1042 if ((n = (b = head.node).next) == null) 1043 return null; 1044 if (n.value != null) 1045 return n; 1046 n.helpDelete(b, n.next); 1047 } 1048 } 1049 1050 /** 1051 * Removes first entry; returns its snapshot. 1052 * @return null if empty, else snapshot of first entry 1053 */ 1054 private Map.Entry<K,V> doRemoveFirstEntry() { 1055 for (Node<K,V> b, n;;) { 1056 if ((n = (b = head.node).next) == null) 1057 return null; 1058 Node<K,V> f = n.next; 1059 if (n != b.next) 1060 continue; 1061 Object v = n.value; 1062 if (v == null) { 1063 n.helpDelete(b, f); 1064 continue; 1065 } 1066 if (!n.casValue(v, null)) 1067 continue; 1068 if (!n.appendMarker(f) || !b.casNext(n, f)) 1069 findFirst(); // retry 1070 clearIndexToFirst(); 1071 @SuppressWarnings("unchecked") V vv = (V)v; 1072 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, vv); 1073 } 1074 } 1075 1076 /** 1077 * Clears out index nodes associated with deleted first entry. 1078 */ 1079 private void clearIndexToFirst() { 1080 for (;;) { 1081 for (Index<K,V> q = head;;) { 1082 Index<K,V> r = q.right; 1083 if (r != null && r.indexesDeletedNode() && !q.unlink(r)) 1084 break; 1085 if ((q = q.down) == null) { 1086 if (head.right == null) 1087 tryReduceLevel(); 1088 return; 1089 } 1090 } 1091 } 1092 } 1093 1094 /** 1095 * Removes last entry; returns its snapshot. 1096 * Specialized variant of doRemove. 1097 * @return null if empty, else snapshot of last entry 1098 */ 1099 private Map.Entry<K,V> doRemoveLastEntry() { 1100 for (;;) { 1101 Node<K,V> b = findPredecessorOfLast(); 1102 Node<K,V> n = b.next; 1103 if (n == null) { 1104 if (b.isBaseHeader()) // empty 1105 return null; 1106 else 1107 continue; // all b's successors are deleted; retry 1108 } 1109 for (;;) { 1110 Node<K,V> f = n.next; 1111 if (n != b.next) // inconsistent read 1112 break; 1113 Object v = n.value; 1114 if (v == null) { // n is deleted 1115 n.helpDelete(b, f); 1116 break; 1117 } 1118 if (b.value == null || v == n) // b is deleted 1119 break; 1120 if (f != null) { 1121 b = n; 1122 n = f; 1123 continue; 1124 } 1125 if (!n.casValue(v, null)) 1126 break; 1127 K key = n.key; 1128 if (!n.appendMarker(f) || !b.casNext(n, f)) 1129 findNode(key); // retry via findNode 1130 else { // clean index 1131 findPredecessor(key, comparator); 1132 if (head.right == null) 1133 tryReduceLevel(); 1134 } 1135 @SuppressWarnings("unchecked") V vv = (V)v; 1136 return new AbstractMap.SimpleImmutableEntry<K,V>(key, vv); 1137 } 1138 } 1139 } 1140 1141 /* ---------------- Finding and removing last element -------------- */ 1142 1143 /** 1144 * Specialized version of find to get last valid node. 1145 * @return last node or null if empty 1146 */ 1147 final Node<K,V> findLast() { 1148 /* 1149 * findPredecessor can't be used to traverse index level 1150 * because this doesn't use comparisons. So traversals of 1151 * both levels are folded together. 1152 */ 1153 Index<K,V> q = head; 1154 for (;;) { 1155 Index<K,V> d, r; 1156 if ((r = q.right) != null) { 1157 if (r.indexesDeletedNode()) { 1158 q.unlink(r); 1159 q = head; // restart 1160 } 1161 else 1162 q = r; 1163 } else if ((d = q.down) != null) { 1164 q = d; 1165 } else { 1166 for (Node<K,V> b = q.node, n = b.next;;) { 1167 if (n == null) 1168 return b.isBaseHeader() ? null : b; 1169 Node<K,V> f = n.next; // inconsistent read 1170 if (n != b.next) 1171 break; 1172 Object v = n.value; 1173 if (v == null) { // n is deleted 1174 n.helpDelete(b, f); 1175 break; 1176 } 1177 if (b.value == null || v == n) // b is deleted 1178 break; 1179 b = n; 1180 n = f; 1181 } 1182 q = head; // restart 1183 } 1184 } 1185 } 1186 1187 /** 1188 * Specialized variant of findPredecessor to get predecessor of last 1189 * valid node. Needed when removing the last entry. It is possible 1190 * that all successors of returned node will have been deleted upon 1191 * return, in which case this method can be retried. 1192 * @return likely predecessor of last node 1193 */ 1194 private Node<K,V> findPredecessorOfLast() { 1195 for (;;) { 1196 for (Index<K,V> q = head;;) { 1197 Index<K,V> d, r; 1198 if ((r = q.right) != null) { 1199 if (r.indexesDeletedNode()) { 1200 q.unlink(r); 1201 break; // must restart 1202 } 1203 // proceed as far across as possible without overshooting 1204 if (r.node.next != null) { 1205 q = r; 1206 continue; 1207 } 1208 } 1209 if ((d = q.down) != null) 1210 q = d; 1211 else 1212 return q.node; 1213 } 1214 } 1215 } 1216 1217 /* ---------------- Relational operations -------------- */ 1218 1219 // Control values OR'ed as arguments to findNear 1220 1221 private static final int EQ = 1; 1222 private static final int LT = 2; 1223 private static final int GT = 0; // Actually checked as !LT 1224 1225 /** 1226 * Utility for ceiling, floor, lower, higher methods. 1227 * @param key the key 1228 * @param rel the relation -- OR'ed combination of EQ, LT, GT 1229 * @return nearest node fitting relation, or null if no such 1230 */ 1231 final Node<K,V> findNear(K key, int rel, Comparator<? super K> cmp) { 1232 if (key == null) 1233 throw new NullPointerException(); 1234 for (;;) { 1235 for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) { 1236 Object v; 1237 if (n == null) 1238 return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b; 1239 Node<K,V> f = n.next; 1240 if (n != b.next) // inconsistent read 1241 break; 1242 if ((v = n.value) == null) { // n is deleted 1243 n.helpDelete(b, f); 1244 break; 1245 } 1246 if (b.value == null || v == n) // b is deleted 1247 break; 1248 int c = cpr(cmp, key, n.key); 1249 if ((c == 0 && (rel & EQ) != 0) || 1250 (c < 0 && (rel & LT) == 0)) 1251 return n; 1252 if ( c <= 0 && (rel & LT) != 0) 1253 return b.isBaseHeader() ? null : b; 1254 b = n; 1255 n = f; 1256 } 1257 } 1258 } 1259 1260 /** 1261 * Returns SimpleImmutableEntry for results of findNear. 1262 * @param key the key 1263 * @param rel the relation -- OR'ed combination of EQ, LT, GT 1264 * @return Entry fitting relation, or null if no such 1265 */ 1266 final AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) { 1267 Comparator<? super K> cmp = comparator; 1268 for (;;) { 1269 Node<K,V> n = findNear(key, rel, cmp); 1270 if (n == null) 1271 return null; 1272 AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot(); 1273 if (e != null) 1274 return e; 1275 } 1276 } 1277 1278 /* ---------------- Constructors -------------- */ 1279 1280 /** 1281 * Constructs a new, empty map, sorted according to the 1282 * {@linkplain Comparable natural ordering} of the keys. 1283 */ 1284 public ConcurrentSkipListMap() { 1285 this.comparator = null; 1286 initialize(); 1287 } 1288 1289 /** 1290 * Constructs a new, empty map, sorted according to the specified 1291 * comparator. 1292 * 1293 * @param comparator the comparator that will be used to order this map. 1294 * If {@code null}, the {@linkplain Comparable natural 1295 * ordering} of the keys will be used. 1296 */ 1297 public ConcurrentSkipListMap(Comparator<? super K> comparator) { 1298 this.comparator = comparator; 1299 initialize(); 1300 } 1301 1302 /** 1303 * Constructs a new map containing the same mappings as the given map, 1304 * sorted according to the {@linkplain Comparable natural ordering} of 1305 * the keys. 1306 * 1307 * @param m the map whose mappings are to be placed in this map 1308 * @throws ClassCastException if the keys in {@code m} are not 1309 * {@link Comparable}, or are not mutually comparable 1310 * @throws NullPointerException if the specified map or any of its keys 1311 * or values are null 1312 */ 1313 public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) { 1314 this.comparator = null; 1315 initialize(); 1316 putAll(m); 1317 } 1318 1319 /** 1320 * Constructs a new map containing the same mappings and using the 1321 * same ordering as the specified sorted map. 1322 * 1323 * @param m the sorted map whose mappings are to be placed in this 1324 * map, and whose comparator is to be used to sort this map 1325 * @throws NullPointerException if the specified sorted map or any of 1326 * its keys or values are null 1327 */ 1328 public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) { 1329 this.comparator = m.comparator(); 1330 initialize(); 1331 buildFromSorted(m); 1332 } 1333 1334 /** 1335 * Returns a shallow copy of this {@code ConcurrentSkipListMap} 1336 * instance. (The keys and values themselves are not cloned.) 1337 * 1338 * @return a shallow copy of this map 1339 */ 1340 public ConcurrentSkipListMap<K,V> clone() { 1341 try { 1342 @SuppressWarnings("unchecked") 1343 ConcurrentSkipListMap<K,V> clone = 1344 (ConcurrentSkipListMap<K,V>) super.clone(); 1345 clone.initialize(); 1346 clone.buildFromSorted(this); 1347 return clone; 1348 } catch (CloneNotSupportedException e) { 1349 throw new InternalError(); 1350 } 1351 } 1352 1353 /** 1354 * Streamlined bulk insertion to initialize from elements of 1355 * given sorted map. Call only from constructor or clone 1356 * method. 1357 */ 1358 private void buildFromSorted(SortedMap<K, ? extends V> map) { 1359 if (map == null) 1360 throw new NullPointerException(); 1361 1362 HeadIndex<K,V> h = head; 1363 Node<K,V> basepred = h.node; 1364 1365 // Track the current rightmost node at each level. Uses an 1366 // ArrayList to avoid committing to initial or maximum level. 1367 ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>(); 1368 1369 // initialize 1370 for (int i = 0; i <= h.level; ++i) 1371 preds.add(null); 1372 Index<K,V> q = h; 1373 for (int i = h.level; i > 0; --i) { 1374 preds.set(i, q); 1375 q = q.down; 1376 } 1377 1378 Iterator<? extends Map.Entry<? extends K, ? extends V>> it = 1379 map.entrySet().iterator(); 1380 while (it.hasNext()) { 1381 Map.Entry<? extends K, ? extends V> e = it.next(); 1382 int rnd = ThreadLocalRandom.current().nextInt(); 1383 int j = 0; 1384 if ((rnd & 0x80000001) == 0) { 1385 do { 1386 ++j; 1387 } while (((rnd >>>= 1) & 1) != 0); 1388 if (j > h.level) j = h.level + 1; 1389 } 1390 K k = e.getKey(); 1391 V v = e.getValue(); 1392 if (k == null || v == null) 1393 throw new NullPointerException(); 1394 Node<K,V> z = new Node<K,V>(k, v, null); 1395 basepred.next = z; 1396 basepred = z; 1397 if (j > 0) { 1398 Index<K,V> idx = null; 1399 for (int i = 1; i <= j; ++i) { 1400 idx = new Index<K,V>(z, idx, null); 1401 if (i > h.level) 1402 h = new HeadIndex<K,V>(h.node, h, idx, i); 1403 1404 if (i < preds.size()) { 1405 preds.get(i).right = idx; 1406 preds.set(i, idx); 1407 } else 1408 preds.add(idx); 1409 } 1410 } 1411 } 1412 head = h; 1413 } 1414 1415 /* ---------------- Serialization -------------- */ 1416 1417 /** 1418 * Saves this map to a stream (that is, serializes it). 1419 * 1420 * @param s the stream 1421 * @throws java.io.IOException if an I/O error occurs 1422 * @serialData The key (Object) and value (Object) for each 1423 * key-value mapping represented by the map, followed by 1424 * {@code null}. The key-value mappings are emitted in key-order 1425 * (as determined by the Comparator, or by the keys' natural 1426 * ordering if no Comparator). 1427 */ 1428 private void writeObject(java.io.ObjectOutputStream s) 1429 throws java.io.IOException { 1430 // Write out the Comparator and any hidden stuff 1431 s.defaultWriteObject(); 1432 1433 // Write out keys and values (alternating) 1434 for (Node<K,V> n = findFirst(); n != null; n = n.next) { 1435 V v = n.getValidValue(); 1436 if (v != null) { 1437 s.writeObject(n.key); 1438 s.writeObject(v); 1439 } 1440 } 1441 s.writeObject(null); 1442 } 1443 1444 /** 1445 * Reconstitutes this map from a stream (that is, deserializes it). 1446 * @param s the stream 1447 * @throws ClassNotFoundException if the class of a serialized object 1448 * could not be found 1449 * @throws java.io.IOException if an I/O error occurs 1450 */ 1451 @SuppressWarnings("unchecked") 1452 private void readObject(final java.io.ObjectInputStream s) 1453 throws java.io.IOException, ClassNotFoundException { 1454 // Read in the Comparator and any hidden stuff 1455 s.defaultReadObject(); 1456 // Reset transients 1457 initialize(); 1458 1459 /* 1460 * This is nearly identical to buildFromSorted, but is 1461 * distinct because readObject calls can't be nicely adapted 1462 * as the kind of iterator needed by buildFromSorted. (They 1463 * can be, but doing so requires type cheats and/or creation 1464 * of adaptor classes.) It is simpler to just adapt the code. 1465 */ 1466 1467 HeadIndex<K,V> h = head; 1468 Node<K,V> basepred = h.node; 1469 ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>(); 1470 for (int i = 0; i <= h.level; ++i) 1471 preds.add(null); 1472 Index<K,V> q = h; 1473 for (int i = h.level; i > 0; --i) { 1474 preds.set(i, q); 1475 q = q.down; 1476 } 1477 1478 for (;;) { 1479 Object k = s.readObject(); 1480 if (k == null) 1481 break; 1482 Object v = s.readObject(); 1483 if (v == null) 1484 throw new NullPointerException(); 1485 K key = (K) k; 1486 V val = (V) v; 1487 int rnd = ThreadLocalRandom.current().nextInt(); 1488 int j = 0; 1489 if ((rnd & 0x80000001) == 0) { 1490 do { 1491 ++j; 1492 } while (((rnd >>>= 1) & 1) != 0); 1493 if (j > h.level) j = h.level + 1; 1494 } 1495 Node<K,V> z = new Node<K,V>(key, val, null); 1496 basepred.next = z; 1497 basepred = z; 1498 if (j > 0) { 1499 Index<K,V> idx = null; 1500 for (int i = 1; i <= j; ++i) { 1501 idx = new Index<K,V>(z, idx, null); 1502 if (i > h.level) 1503 h = new HeadIndex<K,V>(h.node, h, idx, i); 1504 1505 if (i < preds.size()) { 1506 preds.get(i).right = idx; 1507 preds.set(i, idx); 1508 } else 1509 preds.add(idx); 1510 } 1511 } 1512 } 1513 head = h; 1514 } 1515 1516 /* ------ Map API methods ------ */ 1517 1518 /** 1519 * Returns {@code true} if this map contains a mapping for the specified 1520 * key. 1521 * 1522 * @param key key whose presence in this map is to be tested 1523 * @return {@code true} if this map contains a mapping for the specified key 1524 * @throws ClassCastException if the specified key cannot be compared 1525 * with the keys currently in the map 1526 * @throws NullPointerException if the specified key is null 1527 */ 1528 public boolean containsKey(Object key) { 1529 return doGet(key) != null; 1530 } 1531 1532 /** 1533 * Returns the value to which the specified key is mapped, 1534 * or {@code null} if this map contains no mapping for the key. 1535 * 1536 * <p>More formally, if this map contains a mapping from a key 1537 * {@code k} to a value {@code v} such that {@code key} compares 1538 * equal to {@code k} according to the map's ordering, then this 1539 * method returns {@code v}; otherwise it returns {@code null}. 1540 * (There can be at most one such mapping.) 1541 * 1542 * @throws ClassCastException if the specified key cannot be compared 1543 * with the keys currently in the map 1544 * @throws NullPointerException if the specified key is null 1545 */ 1546 public V get(Object key) { 1547 return doGet(key); 1548 } 1549 1550 /** 1551 * Returns the value to which the specified key is mapped, 1552 * or the given defaultValue if this map contains no mapping for the key. 1553 * 1554 * @param key the key 1555 * @param defaultValue the value to return if this map contains 1556 * no mapping for the given key 1557 * @return the mapping for the key, if present; else the defaultValue 1558 * @throws NullPointerException if the specified key is null 1559 * @since 1.8 1560 */ 1561 public V getOrDefault(Object key, V defaultValue) { 1562 V v; 1563 return (v = doGet(key)) == null ? defaultValue : v; 1564 } 1565 1566 /** 1567 * Associates the specified value with the specified key in this map. 1568 * If the map previously contained a mapping for the key, the old 1569 * value is replaced. 1570 * 1571 * @param key key with which the specified value is to be associated 1572 * @param value value to be associated with the specified key 1573 * @return the previous value associated with the specified key, or 1574 * {@code null} if there was no mapping for the key 1575 * @throws ClassCastException if the specified key cannot be compared 1576 * with the keys currently in the map 1577 * @throws NullPointerException if the specified key or value is null 1578 */ 1579 public V put(K key, V value) { 1580 if (value == null) 1581 throw new NullPointerException(); 1582 return doPut(key, value, false); 1583 } 1584 1585 /** 1586 * Removes the mapping for the specified key from this map if present. 1587 * 1588 * @param key key for which mapping should be removed 1589 * @return the previous value associated with the specified key, or 1590 * {@code null} if there was no mapping for the key 1591 * @throws ClassCastException if the specified key cannot be compared 1592 * with the keys currently in the map 1593 * @throws NullPointerException if the specified key is null 1594 */ 1595 public V remove(Object key) { 1596 return doRemove(key, null); 1597 } 1598 1599 /** 1600 * Returns {@code true} if this map maps one or more keys to the 1601 * specified value. This operation requires time linear in the 1602 * map size. Additionally, it is possible for the map to change 1603 * during execution of this method, in which case the returned 1604 * result may be inaccurate. 1605 * 1606 * @param value value whose presence in this map is to be tested 1607 * @return {@code true} if a mapping to {@code value} exists; 1608 * {@code false} otherwise 1609 * @throws NullPointerException if the specified value is null 1610 */ 1611 public boolean containsValue(Object value) { 1612 if (value == null) 1613 throw new NullPointerException(); 1614 for (Node<K,V> n = findFirst(); n != null; n = n.next) { 1615 V v = n.getValidValue(); 1616 if (v != null && value.equals(v)) 1617 return true; 1618 } 1619 return false; 1620 } 1621 1622 /** 1623 * Returns the number of key-value mappings in this map. If this map 1624 * contains more than {@code Integer.MAX_VALUE} elements, it 1625 * returns {@code Integer.MAX_VALUE}. 1626 * 1627 * <p>Beware that, unlike in most collections, this method is 1628 * <em>NOT</em> a constant-time operation. Because of the 1629 * asynchronous nature of these maps, determining the current 1630 * number of elements requires traversing them all to count them. 1631 * Additionally, it is possible for the size to change during 1632 * execution of this method, in which case the returned result 1633 * will be inaccurate. Thus, this method is typically not very 1634 * useful in concurrent applications. 1635 * 1636 * @return the number of elements in this map 1637 */ 1638 public int size() { 1639 long count = 0; 1640 for (Node<K,V> n = findFirst(); n != null; n = n.next) { 1641 if (n.getValidValue() != null) 1642 ++count; 1643 } 1644 return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) count; 1645 } 1646 1647 /** 1648 * Returns {@code true} if this map contains no key-value mappings. 1649 * @return {@code true} if this map contains no key-value mappings 1650 */ 1651 public boolean isEmpty() { 1652 return findFirst() == null; 1653 } 1654 1655 /** 1656 * Removes all of the mappings from this map. 1657 */ 1658 public void clear() { 1659 initialize(); 1660 } 1661 1662 /** 1663 * If the specified key is not already associated with a value, 1664 * attempts to compute its value using the given mapping function 1665 * and enters it into this map unless {@code null}. The function 1666 * is <em>NOT</em> guaranteed to be applied once atomically only 1667 * if the value is not present. 1668 * 1669 * @param key key with which the specified value is to be associated 1670 * @param mappingFunction the function to compute a value 1671 * @return the current (existing or computed) value associated with 1672 * the specified key, or null if the computed value is null 1673 * @throws NullPointerException if the specified key is null 1674 * or the mappingFunction is null 1675 * @since 1.8 1676 */ 1677 public V computeIfAbsent(K key, 1678 Function<? super K, ? extends V> mappingFunction) { 1679 if (key == null || mappingFunction == null) 1680 throw new NullPointerException(); 1681 V v, p, r; 1682 if ((v = doGet(key)) == null && 1683 (r = mappingFunction.apply(key)) != null) 1684 v = (p = doPut(key, r, true)) == null ? r : p; 1685 return v; 1686 } 1687 1688 /** 1689 * If the value for the specified key is present, attempts to 1690 * compute a new mapping given the key and its current mapped 1691 * value. The function is <em>NOT</em> guaranteed to be applied 1692 * once atomically. 1693 * 1694 * @param key key with which a value may be associated 1695 * @param remappingFunction the function to compute a value 1696 * @return the new value associated with the specified key, or null if none 1697 * @throws NullPointerException if the specified key is null 1698 * or the remappingFunction is null 1699 * @since 1.8 1700 */ 1701 public V computeIfPresent(K key, 1702 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1703 if (key == null || remappingFunction == null) 1704 throw new NullPointerException(); 1705 Node<K,V> n; Object v; 1706 while ((n = findNode(key)) != null) { 1707 if ((v = n.value) != null) { 1708 @SuppressWarnings("unchecked") V vv = (V) v; 1709 V r = remappingFunction.apply(key, vv); 1710 if (r != null) { 1711 if (n.casValue(vv, r)) 1712 return r; 1713 } 1714 else if (doRemove(key, vv) != null) 1715 break; 1716 } 1717 } 1718 return null; 1719 } 1720 1721 /** 1722 * Attempts to compute a mapping for the specified key and its 1723 * current mapped value (or {@code null} if there is no current 1724 * mapping). The function is <em>NOT</em> guaranteed to be applied 1725 * once atomically. 1726 * 1727 * @param key key with which the specified value is to be associated 1728 * @param remappingFunction the function to compute a value 1729 * @return the new value associated with the specified key, or null if none 1730 * @throws NullPointerException if the specified key is null 1731 * or the remappingFunction is null 1732 * @since 1.8 1733 */ 1734 public V compute(K key, 1735 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1736 if (key == null || remappingFunction == null) 1737 throw new NullPointerException(); 1738 for (;;) { 1739 Node<K,V> n; Object v; V r; 1740 if ((n = findNode(key)) == null) { 1741 if ((r = remappingFunction.apply(key, null)) == null) 1742 break; 1743 if (doPut(key, r, true) == null) 1744 return r; 1745 } 1746 else if ((v = n.value) != null) { 1747 @SuppressWarnings("unchecked") V vv = (V) v; 1748 if ((r = remappingFunction.apply(key, vv)) != null) { 1749 if (n.casValue(vv, r)) 1750 return r; 1751 } 1752 else if (doRemove(key, vv) != null) 1753 break; 1754 } 1755 } 1756 return null; 1757 } 1758 1759 /** 1760 * If the specified key is not already associated with a value, 1761 * associates it with the given value. Otherwise, replaces the 1762 * value with the results of the given remapping function, or 1763 * removes if {@code null}. The function is <em>NOT</em> 1764 * guaranteed to be applied once atomically. 1765 * 1766 * @param key key with which the specified value is to be associated 1767 * @param value the value to use if absent 1768 * @param remappingFunction the function to recompute a value if present 1769 * @return the new value associated with the specified key, or null if none 1770 * @throws NullPointerException if the specified key or value is null 1771 * or the remappingFunction is null 1772 * @since 1.8 1773 */ 1774 public V merge(K key, V value, 1775 BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 1776 if (key == null || value == null || remappingFunction == null) 1777 throw new NullPointerException(); 1778 for (;;) { 1779 Node<K,V> n; Object v; V r; 1780 if ((n = findNode(key)) == null) { 1781 if (doPut(key, value, true) == null) 1782 return value; 1783 } 1784 else if ((v = n.value) != null) { 1785 @SuppressWarnings("unchecked") V vv = (V) v; 1786 if ((r = remappingFunction.apply(vv, value)) != null) { 1787 if (n.casValue(vv, r)) 1788 return r; 1789 } 1790 else if (doRemove(key, vv) != null) 1791 return null; 1792 } 1793 } 1794 } 1795 1796 /* ---------------- View methods -------------- */ 1797 1798 /* 1799 * Note: Lazy initialization works for views because view classes 1800 * are stateless/immutable so it doesn't matter wrt correctness if 1801 * more than one is created (which will only rarely happen). Even 1802 * so, the following idiom conservatively ensures that the method 1803 * returns the one it created if it does so, not one created by 1804 * another racing thread. 1805 */ 1806 1807 /** 1808 * Returns a {@link NavigableSet} view of the keys contained in this map. 1809 * 1810 * <p>The set's iterator returns the keys in ascending order. 1811 * The set's spliterator additionally reports {@link Spliterator#CONCURRENT}, 1812 * {@link Spliterator#NONNULL}, {@link Spliterator#SORTED} and 1813 * {@link Spliterator#ORDERED}, with an encounter order that is ascending 1814 * key order. The spliterator's comparator (see 1815 * {@link java.util.Spliterator#getComparator()}) is {@code null} if 1816 * the map's comparator (see {@link #comparator()}) is {@code null}. 1817 * Otherwise, the spliterator's comparator is the same as or imposes the 1818 * same total ordering as the map's comparator. 1819 * 1820 * <p>The set is backed by the map, so changes to the map are 1821 * reflected in the set, and vice-versa. The set supports element 1822 * removal, which removes the corresponding mapping from the map, 1823 * via the {@code Iterator.remove}, {@code Set.remove}, 1824 * {@code removeAll}, {@code retainAll}, and {@code clear} 1825 * operations. It does not support the {@code add} or {@code addAll} 1826 * operations. 1827 * 1828 * <p>The view's iterators and spliterators are 1829 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1830 * 1831 * <p>This method is equivalent to method {@code navigableKeySet}. 1832 * 1833 * @return a navigable set view of the keys in this map 1834 */ 1835 public NavigableSet<K> keySet() { 1836 KeySet<K> ks = keySet; 1837 return (ks != null) ? ks : (keySet = new KeySet<K>(this)); 1838 } 1839 1840 public NavigableSet<K> navigableKeySet() { 1841 KeySet<K> ks = keySet; 1842 return (ks != null) ? ks : (keySet = new KeySet<K>(this)); 1843 } 1844 1845 /** 1846 * Returns a {@link Collection} view of the values contained in this map. 1847 * <p>The collection's iterator returns the values in ascending order 1848 * of the corresponding keys. The collections's spliterator additionally 1849 * reports {@link Spliterator#CONCURRENT}, {@link Spliterator#NONNULL} and 1850 * {@link Spliterator#ORDERED}, with an encounter order that is ascending 1851 * order of the corresponding keys. 1852 * 1853 * <p>The collection is backed by the map, so changes to the map are 1854 * reflected in the collection, and vice-versa. The collection 1855 * supports element removal, which removes the corresponding 1856 * mapping from the map, via the {@code Iterator.remove}, 1857 * {@code Collection.remove}, {@code removeAll}, 1858 * {@code retainAll} and {@code clear} operations. It does not 1859 * support the {@code add} or {@code addAll} operations. 1860 * 1861 * <p>The view's iterators and spliterators are 1862 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1863 */ 1864 public Collection<V> values() { 1865 Values<V> vs = values; 1866 return (vs != null) ? vs : (values = new Values<V>(this)); 1867 } 1868 1869 /** 1870 * Returns a {@link Set} view of the mappings contained in this map. 1871 * 1872 * <p>The set's iterator returns the entries in ascending key order. The 1873 * set's spliterator additionally reports {@link Spliterator#CONCURRENT}, 1874 * {@link Spliterator#NONNULL}, {@link Spliterator#SORTED} and 1875 * {@link Spliterator#ORDERED}, with an encounter order that is ascending 1876 * key order. 1877 * 1878 * <p>The set is backed by the map, so changes to the map are 1879 * reflected in the set, and vice-versa. The set supports element 1880 * removal, which removes the corresponding mapping from the map, 1881 * via the {@code Iterator.remove}, {@code Set.remove}, 1882 * {@code removeAll}, {@code retainAll} and {@code clear} 1883 * operations. It does not support the {@code add} or 1884 * {@code addAll} operations. 1885 * 1886 * <p>The view's iterators and spliterators are 1887 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1888 * 1889 * <p>The {@code Map.Entry} elements traversed by the {@code iterator} 1890 * or {@code spliterator} do <em>not</em> support the {@code setValue} 1891 * operation. 1892 * 1893 * @return a set view of the mappings contained in this map, 1894 * sorted in ascending key order 1895 */ 1896 public Set<Map.Entry<K,V>> entrySet() { 1897 EntrySet<K,V> es = entrySet; 1898 return (es != null) ? es : (entrySet = new EntrySet<K,V>(this)); 1899 } 1900 1901 public ConcurrentNavigableMap<K,V> descendingMap() { 1902 ConcurrentNavigableMap<K,V> dm = descendingMap; 1903 return (dm != null) ? dm : (descendingMap = new SubMap<K,V> 1904 (this, null, false, null, false, true)); 1905 } 1906 1907 public NavigableSet<K> descendingKeySet() { 1908 return descendingMap().navigableKeySet(); 1909 } 1910 1911 /* ---------------- AbstractMap Overrides -------------- */ 1912 1913 /** 1914 * Compares the specified object with this map for equality. 1915 * Returns {@code true} if the given object is also a map and the 1916 * two maps represent the same mappings. More formally, two maps 1917 * {@code m1} and {@code m2} represent the same mappings if 1918 * {@code m1.entrySet().equals(m2.entrySet())}. This 1919 * operation may return misleading results if either map is 1920 * concurrently modified during execution of this method. 1921 * 1922 * @param o object to be compared for equality with this map 1923 * @return {@code true} if the specified object is equal to this map 1924 */ 1925 public boolean equals(Object o) { 1926 if (o == this) 1927 return true; 1928 if (!(o instanceof Map)) 1929 return false; 1930 Map<?,?> m = (Map<?,?>) o; 1931 try { 1932 for (Map.Entry<K,V> e : this.entrySet()) 1933 if (! e.getValue().equals(m.get(e.getKey()))) 1934 return false; 1935 for (Map.Entry<?,?> e : m.entrySet()) { 1936 Object k = e.getKey(); 1937 Object v = e.getValue(); 1938 if (k == null || v == null || !v.equals(get(k))) 1939 return false; 1940 } 1941 return true; 1942 } catch (ClassCastException unused) { 1943 return false; 1944 } catch (NullPointerException unused) { 1945 return false; 1946 } 1947 } 1948 1949 /* ------ ConcurrentMap API methods ------ */ 1950 1951 /** 1952 * {@inheritDoc} 1953 * 1954 * @return the previous value associated with the specified key, 1955 * or {@code null} if there was no mapping for the key 1956 * @throws ClassCastException if the specified key cannot be compared 1957 * with the keys currently in the map 1958 * @throws NullPointerException if the specified key or value is null 1959 */ 1960 public V putIfAbsent(K key, V value) { 1961 if (value == null) 1962 throw new NullPointerException(); 1963 return doPut(key, value, true); 1964 } 1965 1966 /** 1967 * {@inheritDoc} 1968 * 1969 * @throws ClassCastException if the specified key cannot be compared 1970 * with the keys currently in the map 1971 * @throws NullPointerException if the specified key is null 1972 */ 1973 public boolean remove(Object key, Object value) { 1974 if (key == null) 1975 throw new NullPointerException(); 1976 return value != null && doRemove(key, value) != null; 1977 } 1978 1979 /** 1980 * {@inheritDoc} 1981 * 1982 * @throws ClassCastException if the specified key cannot be compared 1983 * with the keys currently in the map 1984 * @throws NullPointerException if any of the arguments are null 1985 */ 1986 public boolean replace(K key, V oldValue, V newValue) { 1987 if (key == null || oldValue == null || newValue == null) 1988 throw new NullPointerException(); 1989 for (;;) { 1990 Node<K,V> n; Object v; 1991 if ((n = findNode(key)) == null) 1992 return false; 1993 if ((v = n.value) != null) { 1994 if (!oldValue.equals(v)) 1995 return false; 1996 if (n.casValue(v, newValue)) 1997 return true; 1998 } 1999 } 2000 } 2001 2002 /** 2003 * {@inheritDoc} 2004 * 2005 * @return the previous value associated with the specified key, 2006 * or {@code null} if there was no mapping for the key 2007 * @throws ClassCastException if the specified key cannot be compared 2008 * with the keys currently in the map 2009 * @throws NullPointerException if the specified key or value is null 2010 */ 2011 public V replace(K key, V value) { 2012 if (key == null || value == null) 2013 throw new NullPointerException(); 2014 for (;;) { 2015 Node<K,V> n; Object v; 2016 if ((n = findNode(key)) == null) 2017 return null; 2018 if ((v = n.value) != null && n.casValue(v, value)) { 2019 @SuppressWarnings("unchecked") V vv = (V)v; 2020 return vv; 2021 } 2022 } 2023 } 2024 2025 /* ------ SortedMap API methods ------ */ 2026 2027 public Comparator<? super K> comparator() { 2028 return comparator; 2029 } 2030 2031 /** 2032 * @throws NoSuchElementException {@inheritDoc} 2033 */ 2034 public K firstKey() { 2035 Node<K,V> n = findFirst(); 2036 if (n == null) 2037 throw new NoSuchElementException(); 2038 return n.key; 2039 } 2040 2041 /** 2042 * @throws NoSuchElementException {@inheritDoc} 2043 */ 2044 public K lastKey() { 2045 Node<K,V> n = findLast(); 2046 if (n == null) 2047 throw new NoSuchElementException(); 2048 return n.key; 2049 } 2050 2051 /** 2052 * @throws ClassCastException {@inheritDoc} 2053 * @throws NullPointerException if {@code fromKey} or {@code toKey} is null 2054 * @throws IllegalArgumentException {@inheritDoc} 2055 */ 2056 public ConcurrentNavigableMap<K,V> subMap(K fromKey, 2057 boolean fromInclusive, 2058 K toKey, 2059 boolean toInclusive) { 2060 if (fromKey == null || toKey == null) 2061 throw new NullPointerException(); 2062 return new SubMap<K,V> 2063 (this, fromKey, fromInclusive, toKey, toInclusive, false); 2064 } 2065 2066 /** 2067 * @throws ClassCastException {@inheritDoc} 2068 * @throws NullPointerException if {@code toKey} is null 2069 * @throws IllegalArgumentException {@inheritDoc} 2070 */ 2071 public ConcurrentNavigableMap<K,V> headMap(K toKey, 2072 boolean inclusive) { 2073 if (toKey == null) 2074 throw new NullPointerException(); 2075 return new SubMap<K,V> 2076 (this, null, false, toKey, inclusive, false); 2077 } 2078 2079 /** 2080 * @throws ClassCastException {@inheritDoc} 2081 * @throws NullPointerException if {@code fromKey} is null 2082 * @throws IllegalArgumentException {@inheritDoc} 2083 */ 2084 public ConcurrentNavigableMap<K,V> tailMap(K fromKey, 2085 boolean inclusive) { 2086 if (fromKey == null) 2087 throw new NullPointerException(); 2088 return new SubMap<K,V> 2089 (this, fromKey, inclusive, null, false, false); 2090 } 2091 2092 /** 2093 * @throws ClassCastException {@inheritDoc} 2094 * @throws NullPointerException if {@code fromKey} or {@code toKey} is null 2095 * @throws IllegalArgumentException {@inheritDoc} 2096 */ 2097 public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) { 2098 return subMap(fromKey, true, toKey, false); 2099 } 2100 2101 /** 2102 * @throws ClassCastException {@inheritDoc} 2103 * @throws NullPointerException if {@code toKey} is null 2104 * @throws IllegalArgumentException {@inheritDoc} 2105 */ 2106 public ConcurrentNavigableMap<K,V> headMap(K toKey) { 2107 return headMap(toKey, false); 2108 } 2109 2110 /** 2111 * @throws ClassCastException {@inheritDoc} 2112 * @throws NullPointerException if {@code fromKey} is null 2113 * @throws IllegalArgumentException {@inheritDoc} 2114 */ 2115 public ConcurrentNavigableMap<K,V> tailMap(K fromKey) { 2116 return tailMap(fromKey, true); 2117 } 2118 2119 /* ---------------- Relational operations -------------- */ 2120 2121 /** 2122 * Returns a key-value mapping associated with the greatest key 2123 * strictly less than the given key, or {@code null} if there is 2124 * no such key. The returned entry does <em>not</em> support the 2125 * {@code Entry.setValue} method. 2126 * 2127 * @throws ClassCastException {@inheritDoc} 2128 * @throws NullPointerException if the specified key is null 2129 */ 2130 public Map.Entry<K,V> lowerEntry(K key) { 2131 return getNear(key, LT); 2132 } 2133 2134 /** 2135 * @throws ClassCastException {@inheritDoc} 2136 * @throws NullPointerException if the specified key is null 2137 */ 2138 public K lowerKey(K key) { 2139 Node<K,V> n = findNear(key, LT, comparator); 2140 return (n == null) ? null : n.key; 2141 } 2142 2143 /** 2144 * Returns a key-value mapping associated with the greatest key 2145 * less than or equal to the given key, or {@code null} if there 2146 * is no such key. The returned entry does <em>not</em> support 2147 * the {@code Entry.setValue} method. 2148 * 2149 * @param key the key 2150 * @throws ClassCastException {@inheritDoc} 2151 * @throws NullPointerException if the specified key is null 2152 */ 2153 public Map.Entry<K,V> floorEntry(K key) { 2154 return getNear(key, LT|EQ); 2155 } 2156 2157 /** 2158 * @param key the key 2159 * @throws ClassCastException {@inheritDoc} 2160 * @throws NullPointerException if the specified key is null 2161 */ 2162 public K floorKey(K key) { 2163 Node<K,V> n = findNear(key, LT|EQ, comparator); 2164 return (n == null) ? null : n.key; 2165 } 2166 2167 /** 2168 * Returns a key-value mapping associated with the least key 2169 * greater than or equal to the given key, or {@code null} if 2170 * there is no such entry. The returned entry does <em>not</em> 2171 * support the {@code Entry.setValue} method. 2172 * 2173 * @throws ClassCastException {@inheritDoc} 2174 * @throws NullPointerException if the specified key is null 2175 */ 2176 public Map.Entry<K,V> ceilingEntry(K key) { 2177 return getNear(key, GT|EQ); 2178 } 2179 2180 /** 2181 * @throws ClassCastException {@inheritDoc} 2182 * @throws NullPointerException if the specified key is null 2183 */ 2184 public K ceilingKey(K key) { 2185 Node<K,V> n = findNear(key, GT|EQ, comparator); 2186 return (n == null) ? null : n.key; 2187 } 2188 2189 /** 2190 * Returns a key-value mapping associated with the least key 2191 * strictly greater than the given key, or {@code null} if there 2192 * is no such key. The returned entry does <em>not</em> support 2193 * the {@code Entry.setValue} method. 2194 * 2195 * @param key the key 2196 * @throws ClassCastException {@inheritDoc} 2197 * @throws NullPointerException if the specified key is null 2198 */ 2199 public Map.Entry<K,V> higherEntry(K key) { 2200 return getNear(key, GT); 2201 } 2202 2203 /** 2204 * @param key the key 2205 * @throws ClassCastException {@inheritDoc} 2206 * @throws NullPointerException if the specified key is null 2207 */ 2208 public K higherKey(K key) { 2209 Node<K,V> n = findNear(key, GT, comparator); 2210 return (n == null) ? null : n.key; 2211 } 2212 2213 /** 2214 * Returns a key-value mapping associated with the least 2215 * key in this map, or {@code null} if the map is empty. 2216 * The returned entry does <em>not</em> support 2217 * the {@code Entry.setValue} method. 2218 */ 2219 public Map.Entry<K,V> firstEntry() { 2220 for (;;) { 2221 Node<K,V> n = findFirst(); 2222 if (n == null) 2223 return null; 2224 AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot(); 2225 if (e != null) 2226 return e; 2227 } 2228 } 2229 2230 /** 2231 * Returns a key-value mapping associated with the greatest 2232 * key in this map, or {@code null} if the map is empty. 2233 * The returned entry does <em>not</em> support 2234 * the {@code Entry.setValue} method. 2235 */ 2236 public Map.Entry<K,V> lastEntry() { 2237 for (;;) { 2238 Node<K,V> n = findLast(); 2239 if (n == null) 2240 return null; 2241 AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot(); 2242 if (e != null) 2243 return e; 2244 } 2245 } 2246 2247 /** 2248 * Removes and returns a key-value mapping associated with 2249 * the least key in this map, or {@code null} if the map is empty. 2250 * The returned entry does <em>not</em> support 2251 * the {@code Entry.setValue} method. 2252 */ 2253 public Map.Entry<K,V> pollFirstEntry() { 2254 return doRemoveFirstEntry(); 2255 } 2256 2257 /** 2258 * Removes and returns a key-value mapping associated with 2259 * the greatest key in this map, or {@code null} if the map is empty. 2260 * The returned entry does <em>not</em> support 2261 * the {@code Entry.setValue} method. 2262 */ 2263 public Map.Entry<K,V> pollLastEntry() { 2264 return doRemoveLastEntry(); 2265 } 2266 2267 2268 /* ---------------- Iterators -------------- */ 2269 2270 /** 2271 * Base of iterator classes: 2272 */ 2273 abstract class Iter<T> implements Iterator<T> { 2274 /** the last node returned by next() */ 2275 Node<K,V> lastReturned; 2276 /** the next node to return from next(); */ 2277 Node<K,V> next; 2278 /** Cache of next value field to maintain weak consistency */ 2279 V nextValue; 2280 2281 /** Initializes ascending iterator for entire range. */ 2282 Iter() { 2283 while ((next = findFirst()) != null) { 2284 Object x = next.value; 2285 if (x != null && x != next) { 2286 @SuppressWarnings("unchecked") V vv = (V)x; 2287 nextValue = vv; 2288 break; 2289 } 2290 } 2291 } 2292 2293 public final boolean hasNext() { 2294 return next != null; 2295 } 2296 2297 /** Advances next to higher entry. */ 2298 final void advance() { 2299 if (next == null) 2300 throw new NoSuchElementException(); 2301 lastReturned = next; 2302 while ((next = next.next) != null) { 2303 Object x = next.value; 2304 if (x != null && x != next) { 2305 @SuppressWarnings("unchecked") V vv = (V)x; 2306 nextValue = vv; 2307 break; 2308 } 2309 } 2310 } 2311 2312 public void remove() { 2313 Node<K,V> l = lastReturned; 2314 if (l == null) 2315 throw new IllegalStateException(); 2316 // It would not be worth all of the overhead to directly 2317 // unlink from here. Using remove is fast enough. 2318 ConcurrentSkipListMap.this.remove(l.key); 2319 lastReturned = null; 2320 } 2321 2322 } 2323 2324 final class ValueIterator extends Iter<V> { 2325 public V next() { 2326 V v = nextValue; 2327 advance(); 2328 return v; 2329 } 2330 } 2331 2332 final class KeyIterator extends Iter<K> { 2333 public K next() { 2334 Node<K,V> n = next; 2335 advance(); 2336 return n.key; 2337 } 2338 } 2339 2340 final class EntryIterator extends Iter<Map.Entry<K,V>> { 2341 public Map.Entry<K,V> next() { 2342 Node<K,V> n = next; 2343 V v = nextValue; 2344 advance(); 2345 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v); 2346 } 2347 } 2348 2349 // Factory methods for iterators needed by ConcurrentSkipListSet etc 2350 2351 Iterator<K> keyIterator() { 2352 return new KeyIterator(); 2353 } 2354 2355 Iterator<V> valueIterator() { 2356 return new ValueIterator(); 2357 } 2358 2359 Iterator<Map.Entry<K,V>> entryIterator() { 2360 return new EntryIterator(); 2361 } 2362 2363 /* ---------------- View Classes -------------- */ 2364 2365 /* 2366 * View classes are static, delegating to a ConcurrentNavigableMap 2367 * to allow use by SubMaps, which outweighs the ugliness of 2368 * needing type-tests for Iterator methods. 2369 */ 2370 2371 static final <E> List<E> toList(Collection<E> c) { 2372 // Using size() here would be a pessimization. 2373 ArrayList<E> list = new ArrayList<E>(); 2374 for (E e : c) 2375 list.add(e); 2376 return list; 2377 } 2378 2379 static final class KeySet<E> 2380 extends AbstractSet<E> implements NavigableSet<E> { 2381 final ConcurrentNavigableMap<E,?> m; 2382 KeySet(ConcurrentNavigableMap<E,?> map) { m = map; } 2383 public int size() { return m.size(); } 2384 public boolean isEmpty() { return m.isEmpty(); } 2385 public boolean contains(Object o) { return m.containsKey(o); } 2386 public boolean remove(Object o) { return m.remove(o) != null; } 2387 public void clear() { m.clear(); } 2388 public E lower(E e) { return m.lowerKey(e); } 2389 public E floor(E e) { return m.floorKey(e); } 2390 public E ceiling(E e) { return m.ceilingKey(e); } 2391 public E higher(E e) { return m.higherKey(e); } 2392 public Comparator<? super E> comparator() { return m.comparator(); } 2393 public E first() { return m.firstKey(); } 2394 public E last() { return m.lastKey(); } 2395 public E pollFirst() { 2396 Map.Entry<E,?> e = m.pollFirstEntry(); 2397 return (e == null) ? null : e.getKey(); 2398 } 2399 public E pollLast() { 2400 Map.Entry<E,?> e = m.pollLastEntry(); 2401 return (e == null) ? null : e.getKey(); 2402 } 2403 @SuppressWarnings("unchecked") 2404 public Iterator<E> iterator() { 2405 if (m instanceof ConcurrentSkipListMap) 2406 return ((ConcurrentSkipListMap<E,Object>)m).keyIterator(); 2407 else 2408 return ((ConcurrentSkipListMap.SubMap<E,Object>)m).keyIterator(); 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<E> descendingIterator() { 2427 return descendingSet().iterator(); 2428 } 2429 public NavigableSet<E> subSet(E fromElement, 2430 boolean fromInclusive, 2431 E toElement, 2432 boolean toInclusive) { 2433 return new KeySet<E>(m.subMap(fromElement, fromInclusive, 2434 toElement, toInclusive)); 2435 } 2436 public NavigableSet<E> headSet(E toElement, boolean inclusive) { 2437 return new KeySet<E>(m.headMap(toElement, inclusive)); 2438 } 2439 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { 2440 return new KeySet<E>(m.tailMap(fromElement, inclusive)); 2441 } 2442 public NavigableSet<E> subSet(E fromElement, E toElement) { 2443 return subSet(fromElement, true, toElement, false); 2444 } 2445 public NavigableSet<E> headSet(E toElement) { 2446 return headSet(toElement, false); 2447 } 2448 public NavigableSet<E> tailSet(E fromElement) { 2449 return tailSet(fromElement, true); 2450 } 2451 public NavigableSet<E> descendingSet() { 2452 return new KeySet<E>(m.descendingMap()); 2453 } 2454 @SuppressWarnings("unchecked") 2455 public Spliterator<E> spliterator() { 2456 if (m instanceof ConcurrentSkipListMap) 2457 return ((ConcurrentSkipListMap<E,?>)m).keySpliterator(); 2458 else 2459 return (Spliterator<E>)((SubMap<E,?>)m).keyIterator(); 2460 } 2461 } 2462 2463 static final class Values<E> extends AbstractCollection<E> { 2464 final ConcurrentNavigableMap<?, E> m; 2465 Values(ConcurrentNavigableMap<?, E> map) { 2466 m = map; 2467 } 2468 @SuppressWarnings("unchecked") 2469 public Iterator<E> iterator() { 2470 if (m instanceof ConcurrentSkipListMap) 2471 return ((ConcurrentSkipListMap<?,E>)m).valueIterator(); 2472 else 2473 return ((SubMap<?,E>)m).valueIterator(); 2474 } 2475 public boolean isEmpty() { 2476 return m.isEmpty(); 2477 } 2478 public int size() { 2479 return m.size(); 2480 } 2481 public boolean contains(Object o) { 2482 return m.containsValue(o); 2483 } 2484 public void clear() { 2485 m.clear(); 2486 } 2487 public Object[] toArray() { return toList(this).toArray(); } 2488 public <T> T[] toArray(T[] a) { return toList(this).toArray(a); } 2489 @SuppressWarnings("unchecked") 2490 public Spliterator<E> spliterator() { 2491 if (m instanceof ConcurrentSkipListMap) 2492 return ((ConcurrentSkipListMap<?,E>)m).valueSpliterator(); 2493 else 2494 return (Spliterator<E>)((SubMap<?,E>)m).valueIterator(); 2495 } 2496 public boolean removeIf(Predicate<? super E> filter) { 2497 if (filter == null) throw new NullPointerException(); 2498 if (m instanceof ConcurrentSkipListMap) 2499 return ((ConcurrentSkipListMap<?,E>)m).removeValueIf(filter); 2500 // else use iterator 2501 @SuppressWarnings("unchecked") Iterator<Map.Entry<Object,E>> it = 2502 ((SubMap<Object,E>)m).entryIterator(); 2503 boolean removed = false; 2504 while (it.hasNext()) { 2505 Map.Entry<Object,E> e = it.next(); 2506 E v = e.getValue(); 2507 if (filter.test(v) && m.remove(e.getKey(), v)) 2508 removed = true; 2509 } 2510 return removed; 2511 } 2512 } 2513 2514 static final class EntrySet<K1,V1> extends AbstractSet<Map.Entry<K1,V1>> { 2515 final ConcurrentNavigableMap<K1, V1> m; 2516 EntrySet(ConcurrentNavigableMap<K1, V1> map) { 2517 m = map; 2518 } 2519 @SuppressWarnings("unchecked") 2520 public Iterator<Map.Entry<K1,V1>> iterator() { 2521 if (m instanceof ConcurrentSkipListMap) 2522 return ((ConcurrentSkipListMap<K1,V1>)m).entryIterator(); 2523 else 2524 return ((SubMap<K1,V1>)m).entryIterator(); 2525 } 2526 2527 public boolean contains(Object o) { 2528 if (!(o instanceof Map.Entry)) 2529 return false; 2530 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 2531 V1 v = m.get(e.getKey()); 2532 return v != null && v.equals(e.getValue()); 2533 } 2534 public boolean remove(Object o) { 2535 if (!(o instanceof Map.Entry)) 2536 return false; 2537 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 2538 return m.remove(e.getKey(), 2539 e.getValue()); 2540 } 2541 public boolean isEmpty() { 2542 return m.isEmpty(); 2543 } 2544 public int size() { 2545 return m.size(); 2546 } 2547 public void clear() { 2548 m.clear(); 2549 } 2550 public boolean equals(Object o) { 2551 if (o == this) 2552 return true; 2553 if (!(o instanceof Set)) 2554 return false; 2555 Collection<?> c = (Collection<?>) o; 2556 try { 2557 return containsAll(c) && c.containsAll(this); 2558 } catch (ClassCastException unused) { 2559 return false; 2560 } catch (NullPointerException unused) { 2561 return false; 2562 } 2563 } 2564 public Object[] toArray() { return toList(this).toArray(); } 2565 public <T> T[] toArray(T[] a) { return toList(this).toArray(a); } 2566 @SuppressWarnings("unchecked") 2567 public Spliterator<Map.Entry<K1,V1>> spliterator() { 2568 if (m instanceof ConcurrentSkipListMap) 2569 return ((ConcurrentSkipListMap<K1,V1>)m).entrySpliterator(); 2570 else 2571 return (Spliterator<Map.Entry<K1,V1>>) 2572 ((SubMap<K1,V1>)m).entryIterator(); 2573 } 2574 public boolean removeIf(Predicate<? super Entry<K1, V1>> filter) { 2575 if (filter == null) throw new NullPointerException(); 2576 if (m instanceof ConcurrentSkipListMap) 2577 return ((ConcurrentSkipListMap<K1,V1>)m).removeEntryIf(filter); 2578 // else use iterator 2579 Iterator<Map.Entry<K1,V1>> it = ((SubMap<K1,V1>)m).entryIterator(); 2580 boolean removed = false; 2581 while (it.hasNext()) { 2582 Map.Entry<K1,V1> e = it.next(); 2583 if (filter.test(e) && m.remove(e.getKey(), e.getValue())) 2584 removed = true; 2585 } 2586 return removed; 2587 } 2588 } 2589 2590 /** 2591 * Submaps returned by {@link ConcurrentSkipListMap} submap operations 2592 * represent a subrange of mappings of their underlying 2593 * maps. Instances of this class support all methods of their 2594 * underlying maps, differing in that mappings outside their range are 2595 * ignored, and attempts to add mappings outside their ranges result 2596 * in {@link IllegalArgumentException}. Instances of this class are 2597 * constructed only using the {@code subMap}, {@code headMap}, and 2598 * {@code tailMap} methods of their underlying maps. 2599 * 2600 * @serial include 2601 */ 2602 static final class SubMap<K,V> extends AbstractMap<K,V> 2603 implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable { 2604 private static final long serialVersionUID = -7647078645895051609L; 2605 2606 /** Underlying map */ 2607 private final ConcurrentSkipListMap<K,V> m; 2608 /** lower bound key, or null if from start */ 2609 private final K lo; 2610 /** upper bound key, or null if to end */ 2611 private final K hi; 2612 /** inclusion flag for lo */ 2613 private final boolean loInclusive; 2614 /** inclusion flag for hi */ 2615 private final boolean hiInclusive; 2616 /** direction */ 2617 private final boolean isDescending; 2618 2619 // Lazily initialized view holders 2620 private transient KeySet<K> keySetView; 2621 private transient Set<Map.Entry<K,V>> entrySetView; 2622 private transient Collection<V> valuesView; 2623 2624 /** 2625 * Creates a new submap, initializing all fields. 2626 */ 2627 SubMap(ConcurrentSkipListMap<K,V> map, 2628 K fromKey, boolean fromInclusive, 2629 K toKey, boolean toInclusive, 2630 boolean isDescending) { 2631 Comparator<? super K> cmp = map.comparator; 2632 if (fromKey != null && toKey != null && 2633 cpr(cmp, fromKey, toKey) > 0) 2634 throw new IllegalArgumentException("inconsistent range"); 2635 this.m = map; 2636 this.lo = fromKey; 2637 this.hi = toKey; 2638 this.loInclusive = fromInclusive; 2639 this.hiInclusive = toInclusive; 2640 this.isDescending = isDescending; 2641 } 2642 2643 /* ---------------- Utilities -------------- */ 2644 2645 boolean tooLow(Object key, Comparator<? super K> cmp) { 2646 int c; 2647 return (lo != null && ((c = cpr(cmp, key, lo)) < 0 || 2648 (c == 0 && !loInclusive))); 2649 } 2650 2651 boolean tooHigh(Object key, Comparator<? super K> cmp) { 2652 int c; 2653 return (hi != null && ((c = cpr(cmp, key, hi)) > 0 || 2654 (c == 0 && !hiInclusive))); 2655 } 2656 2657 boolean inBounds(Object key, Comparator<? super K> cmp) { 2658 return !tooLow(key, cmp) && !tooHigh(key, cmp); 2659 } 2660 2661 void checkKeyBounds(K key, Comparator<? super K> cmp) { 2662 if (key == null) 2663 throw new NullPointerException(); 2664 if (!inBounds(key, cmp)) 2665 throw new IllegalArgumentException("key out of range"); 2666 } 2667 2668 /** 2669 * Returns true if node key is less than upper bound of range. 2670 */ 2671 boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n, 2672 Comparator<? super K> cmp) { 2673 if (n == null) 2674 return false; 2675 if (hi == null) 2676 return true; 2677 K k = n.key; 2678 if (k == null) // pass by markers and headers 2679 return true; 2680 int c = cpr(cmp, k, hi); 2681 if (c > 0 || (c == 0 && !hiInclusive)) 2682 return false; 2683 return true; 2684 } 2685 2686 /** 2687 * Returns lowest node. This node might not be in range, so 2688 * most usages need to check bounds. 2689 */ 2690 ConcurrentSkipListMap.Node<K,V> loNode(Comparator<? super K> cmp) { 2691 if (lo == null) 2692 return m.findFirst(); 2693 else if (loInclusive) 2694 return m.findNear(lo, GT|EQ, cmp); 2695 else 2696 return m.findNear(lo, GT, cmp); 2697 } 2698 2699 /** 2700 * Returns highest node. This node might not be in range, so 2701 * most usages need to check bounds. 2702 */ 2703 ConcurrentSkipListMap.Node<K,V> hiNode(Comparator<? super K> cmp) { 2704 if (hi == null) 2705 return m.findLast(); 2706 else if (hiInclusive) 2707 return m.findNear(hi, LT|EQ, cmp); 2708 else 2709 return m.findNear(hi, LT, cmp); 2710 } 2711 2712 /** 2713 * Returns lowest absolute key (ignoring directionality). 2714 */ 2715 K lowestKey() { 2716 Comparator<? super K> cmp = m.comparator; 2717 ConcurrentSkipListMap.Node<K,V> n = loNode(cmp); 2718 if (isBeforeEnd(n, cmp)) 2719 return n.key; 2720 else 2721 throw new NoSuchElementException(); 2722 } 2723 2724 /** 2725 * Returns highest absolute key (ignoring directionality). 2726 */ 2727 K highestKey() { 2728 Comparator<? super K> cmp = m.comparator; 2729 ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp); 2730 if (n != null) { 2731 K last = n.key; 2732 if (inBounds(last, cmp)) 2733 return last; 2734 } 2735 throw new NoSuchElementException(); 2736 } 2737 2738 Map.Entry<K,V> lowestEntry() { 2739 Comparator<? super K> cmp = m.comparator; 2740 for (;;) { 2741 ConcurrentSkipListMap.Node<K,V> n = loNode(cmp); 2742 if (!isBeforeEnd(n, cmp)) 2743 return null; 2744 Map.Entry<K,V> e = n.createSnapshot(); 2745 if (e != null) 2746 return e; 2747 } 2748 } 2749 2750 Map.Entry<K,V> highestEntry() { 2751 Comparator<? super K> cmp = m.comparator; 2752 for (;;) { 2753 ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp); 2754 if (n == null || !inBounds(n.key, cmp)) 2755 return null; 2756 Map.Entry<K,V> e = n.createSnapshot(); 2757 if (e != null) 2758 return e; 2759 } 2760 } 2761 2762 Map.Entry<K,V> removeLowest() { 2763 Comparator<? super K> cmp = m.comparator; 2764 for (;;) { 2765 Node<K,V> n = loNode(cmp); 2766 if (n == null) 2767 return null; 2768 K k = n.key; 2769 if (!inBounds(k, cmp)) 2770 return null; 2771 V v = m.doRemove(k, null); 2772 if (v != null) 2773 return new AbstractMap.SimpleImmutableEntry<K,V>(k, v); 2774 } 2775 } 2776 2777 Map.Entry<K,V> removeHighest() { 2778 Comparator<? super K> cmp = m.comparator; 2779 for (;;) { 2780 Node<K,V> n = hiNode(cmp); 2781 if (n == null) 2782 return null; 2783 K k = n.key; 2784 if (!inBounds(k, cmp)) 2785 return null; 2786 V v = m.doRemove(k, null); 2787 if (v != null) 2788 return new AbstractMap.SimpleImmutableEntry<K,V>(k, v); 2789 } 2790 } 2791 2792 /** 2793 * Submap version of ConcurrentSkipListMap.getNearEntry 2794 */ 2795 Map.Entry<K,V> getNearEntry(K key, int rel) { 2796 Comparator<? super K> cmp = m.comparator; 2797 if (isDescending) { // adjust relation for direction 2798 if ((rel & LT) == 0) 2799 rel |= LT; 2800 else 2801 rel &= ~LT; 2802 } 2803 if (tooLow(key, cmp)) 2804 return ((rel & LT) != 0) ? null : lowestEntry(); 2805 if (tooHigh(key, cmp)) 2806 return ((rel & LT) != 0) ? highestEntry() : null; 2807 for (;;) { 2808 Node<K,V> n = m.findNear(key, rel, cmp); 2809 if (n == null || !inBounds(n.key, cmp)) 2810 return null; 2811 K k = n.key; 2812 V v = n.getValidValue(); 2813 if (v != null) 2814 return new AbstractMap.SimpleImmutableEntry<K,V>(k, v); 2815 } 2816 } 2817 2818 // Almost the same as getNearEntry, except for keys 2819 K getNearKey(K key, int rel) { 2820 Comparator<? super K> cmp = m.comparator; 2821 if (isDescending) { // adjust relation for direction 2822 if ((rel & LT) == 0) 2823 rel |= LT; 2824 else 2825 rel &= ~LT; 2826 } 2827 if (tooLow(key, cmp)) { 2828 if ((rel & LT) == 0) { 2829 ConcurrentSkipListMap.Node<K,V> n = loNode(cmp); 2830 if (isBeforeEnd(n, cmp)) 2831 return n.key; 2832 } 2833 return null; 2834 } 2835 if (tooHigh(key, cmp)) { 2836 if ((rel & LT) != 0) { 2837 ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp); 2838 if (n != null) { 2839 K last = n.key; 2840 if (inBounds(last, cmp)) 2841 return last; 2842 } 2843 } 2844 return null; 2845 } 2846 for (;;) { 2847 Node<K,V> n = m.findNear(key, rel, cmp); 2848 if (n == null || !inBounds(n.key, cmp)) 2849 return null; 2850 K k = n.key; 2851 V v = n.getValidValue(); 2852 if (v != null) 2853 return k; 2854 } 2855 } 2856 2857 /* ---------------- Map API methods -------------- */ 2858 2859 public boolean containsKey(Object key) { 2860 if (key == null) throw new NullPointerException(); 2861 return inBounds(key, m.comparator) && m.containsKey(key); 2862 } 2863 2864 public V get(Object key) { 2865 if (key == null) throw new NullPointerException(); 2866 return (!inBounds(key, m.comparator)) ? null : m.get(key); 2867 } 2868 2869 public V put(K key, V value) { 2870 checkKeyBounds(key, m.comparator); 2871 return m.put(key, value); 2872 } 2873 2874 public V remove(Object key) { 2875 return (!inBounds(key, m.comparator)) ? null : m.remove(key); 2876 } 2877 2878 public int size() { 2879 Comparator<? super K> cmp = m.comparator; 2880 long count = 0; 2881 for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp); 2882 isBeforeEnd(n, cmp); 2883 n = n.next) { 2884 if (n.getValidValue() != null) 2885 ++count; 2886 } 2887 return count >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)count; 2888 } 2889 2890 public boolean isEmpty() { 2891 Comparator<? super K> cmp = m.comparator; 2892 return !isBeforeEnd(loNode(cmp), cmp); 2893 } 2894 2895 public boolean containsValue(Object value) { 2896 if (value == null) 2897 throw new NullPointerException(); 2898 Comparator<? super K> cmp = m.comparator; 2899 for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp); 2900 isBeforeEnd(n, cmp); 2901 n = n.next) { 2902 V v = n.getValidValue(); 2903 if (v != null && value.equals(v)) 2904 return true; 2905 } 2906 return false; 2907 } 2908 2909 public void clear() { 2910 Comparator<? super K> cmp = m.comparator; 2911 for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp); 2912 isBeforeEnd(n, cmp); 2913 n = n.next) { 2914 if (n.getValidValue() != null) 2915 m.remove(n.key); 2916 } 2917 } 2918 2919 /* ---------------- ConcurrentMap API methods -------------- */ 2920 2921 public V putIfAbsent(K key, V value) { 2922 checkKeyBounds(key, m.comparator); 2923 return m.putIfAbsent(key, value); 2924 } 2925 2926 public boolean remove(Object key, Object value) { 2927 return inBounds(key, m.comparator) && m.remove(key, value); 2928 } 2929 2930 public boolean replace(K key, V oldValue, V newValue) { 2931 checkKeyBounds(key, m.comparator); 2932 return m.replace(key, oldValue, newValue); 2933 } 2934 2935 public V replace(K key, V value) { 2936 checkKeyBounds(key, m.comparator); 2937 return m.replace(key, value); 2938 } 2939 2940 /* ---------------- SortedMap API methods -------------- */ 2941 2942 public Comparator<? super K> comparator() { 2943 Comparator<? super K> cmp = m.comparator(); 2944 if (isDescending) 2945 return Collections.reverseOrder(cmp); 2946 else 2947 return cmp; 2948 } 2949 2950 /** 2951 * Utility to create submaps, where given bounds override 2952 * unbounded(null) ones and/or are checked against bounded ones. 2953 */ 2954 SubMap<K,V> newSubMap(K fromKey, boolean fromInclusive, 2955 K toKey, boolean toInclusive) { 2956 Comparator<? super K> cmp = m.comparator; 2957 if (isDescending) { // flip senses 2958 K tk = fromKey; 2959 fromKey = toKey; 2960 toKey = tk; 2961 boolean ti = fromInclusive; 2962 fromInclusive = toInclusive; 2963 toInclusive = ti; 2964 } 2965 if (lo != null) { 2966 if (fromKey == null) { 2967 fromKey = lo; 2968 fromInclusive = loInclusive; 2969 } 2970 else { 2971 int c = cpr(cmp, fromKey, lo); 2972 if (c < 0 || (c == 0 && !loInclusive && fromInclusive)) 2973 throw new IllegalArgumentException("key out of range"); 2974 } 2975 } 2976 if (hi != null) { 2977 if (toKey == null) { 2978 toKey = hi; 2979 toInclusive = hiInclusive; 2980 } 2981 else { 2982 int c = cpr(cmp, toKey, hi); 2983 if (c > 0 || (c == 0 && !hiInclusive && toInclusive)) 2984 throw new IllegalArgumentException("key out of range"); 2985 } 2986 } 2987 return new SubMap<K,V>(m, fromKey, fromInclusive, 2988 toKey, toInclusive, isDescending); 2989 } 2990 2991 public SubMap<K,V> subMap(K fromKey, boolean fromInclusive, 2992 K toKey, boolean toInclusive) { 2993 if (fromKey == null || toKey == null) 2994 throw new NullPointerException(); 2995 return newSubMap(fromKey, fromInclusive, toKey, toInclusive); 2996 } 2997 2998 public SubMap<K,V> headMap(K toKey, boolean inclusive) { 2999 if (toKey == null) 3000 throw new NullPointerException(); 3001 return newSubMap(null, false, toKey, inclusive); 3002 } 3003 3004 public SubMap<K,V> tailMap(K fromKey, boolean inclusive) { 3005 if (fromKey == null) 3006 throw new NullPointerException(); 3007 return newSubMap(fromKey, inclusive, null, false); 3008 } 3009 3010 public SubMap<K,V> subMap(K fromKey, K toKey) { 3011 return subMap(fromKey, true, toKey, false); 3012 } 3013 3014 public SubMap<K,V> headMap(K toKey) { 3015 return headMap(toKey, false); 3016 } 3017 3018 public SubMap<K,V> tailMap(K fromKey) { 3019 return tailMap(fromKey, true); 3020 } 3021 3022 public SubMap<K,V> descendingMap() { 3023 return new SubMap<K,V>(m, lo, loInclusive, 3024 hi, hiInclusive, !isDescending); 3025 } 3026 3027 /* ---------------- Relational methods -------------- */ 3028 3029 public Map.Entry<K,V> ceilingEntry(K key) { 3030 return getNearEntry(key, GT|EQ); 3031 } 3032 3033 public K ceilingKey(K key) { 3034 return getNearKey(key, GT|EQ); 3035 } 3036 3037 public Map.Entry<K,V> lowerEntry(K key) { 3038 return getNearEntry(key, LT); 3039 } 3040 3041 public K lowerKey(K key) { 3042 return getNearKey(key, LT); 3043 } 3044 3045 public Map.Entry<K,V> floorEntry(K key) { 3046 return getNearEntry(key, LT|EQ); 3047 } 3048 3049 public K floorKey(K key) { 3050 return getNearKey(key, LT|EQ); 3051 } 3052 3053 public Map.Entry<K,V> higherEntry(K key) { 3054 return getNearEntry(key, GT); 3055 } 3056 3057 public K higherKey(K key) { 3058 return getNearKey(key, GT); 3059 } 3060 3061 public K firstKey() { 3062 return isDescending ? highestKey() : lowestKey(); 3063 } 3064 3065 public K lastKey() { 3066 return isDescending ? lowestKey() : highestKey(); 3067 } 3068 3069 public Map.Entry<K,V> firstEntry() { 3070 return isDescending ? highestEntry() : lowestEntry(); 3071 } 3072 3073 public Map.Entry<K,V> lastEntry() { 3074 return isDescending ? lowestEntry() : highestEntry(); 3075 } 3076 3077 public Map.Entry<K,V> pollFirstEntry() { 3078 return isDescending ? removeHighest() : removeLowest(); 3079 } 3080 3081 public Map.Entry<K,V> pollLastEntry() { 3082 return isDescending ? removeLowest() : removeHighest(); 3083 } 3084 3085 /* ---------------- Submap Views -------------- */ 3086 3087 public NavigableSet<K> keySet() { 3088 KeySet<K> ks = keySetView; 3089 return (ks != null) ? ks : (keySetView = new KeySet<K>(this)); 3090 } 3091 3092 public NavigableSet<K> navigableKeySet() { 3093 KeySet<K> ks = keySetView; 3094 return (ks != null) ? ks : (keySetView = new KeySet<K>(this)); 3095 } 3096 3097 public Collection<V> values() { 3098 Collection<V> vs = valuesView; 3099 return (vs != null) ? vs : (valuesView = new Values<V>(this)); 3100 } 3101 3102 public Set<Map.Entry<K,V>> entrySet() { 3103 Set<Map.Entry<K,V>> es = entrySetView; 3104 return (es != null) ? es : (entrySetView = new EntrySet<K,V>(this)); 3105 } 3106 3107 public NavigableSet<K> descendingKeySet() { 3108 return descendingMap().navigableKeySet(); 3109 } 3110 3111 Iterator<K> keyIterator() { 3112 return new SubMapKeyIterator(); 3113 } 3114 3115 Iterator<V> valueIterator() { 3116 return new SubMapValueIterator(); 3117 } 3118 3119 Iterator<Map.Entry<K,V>> entryIterator() { 3120 return new SubMapEntryIterator(); 3121 } 3122 3123 /** 3124 * Variant of main Iter class to traverse through submaps. 3125 * Also serves as back-up Spliterator for views 3126 */ 3127 abstract class SubMapIter<T> implements Iterator<T>, Spliterator<T> { 3128 /** the last node returned by next() */ 3129 Node<K,V> lastReturned; 3130 /** the next node to return from next(); */ 3131 Node<K,V> next; 3132 /** Cache of next value field to maintain weak consistency */ 3133 V nextValue; 3134 3135 SubMapIter() { 3136 Comparator<? super K> cmp = m.comparator; 3137 for (;;) { 3138 next = isDescending ? hiNode(cmp) : loNode(cmp); 3139 if (next == null) 3140 break; 3141 Object x = next.value; 3142 if (x != null && x != next) { 3143 if (! inBounds(next.key, cmp)) 3144 next = null; 3145 else { 3146 @SuppressWarnings("unchecked") V vv = (V)x; 3147 nextValue = vv; 3148 } 3149 break; 3150 } 3151 } 3152 } 3153 3154 public final boolean hasNext() { 3155 return next != null; 3156 } 3157 3158 final void advance() { 3159 if (next == null) 3160 throw new NoSuchElementException(); 3161 lastReturned = next; 3162 if (isDescending) 3163 descend(); 3164 else 3165 ascend(); 3166 } 3167 3168 private void ascend() { 3169 Comparator<? super K> cmp = m.comparator; 3170 for (;;) { 3171 next = next.next; 3172 if (next == null) 3173 break; 3174 Object x = next.value; 3175 if (x != null && x != next) { 3176 if (tooHigh(next.key, cmp)) 3177 next = null; 3178 else { 3179 @SuppressWarnings("unchecked") V vv = (V)x; 3180 nextValue = vv; 3181 } 3182 break; 3183 } 3184 } 3185 } 3186 3187 private void descend() { 3188 Comparator<? super K> cmp = m.comparator; 3189 for (;;) { 3190 next = m.findNear(lastReturned.key, LT, cmp); 3191 if (next == null) 3192 break; 3193 Object x = next.value; 3194 if (x != null && x != next) { 3195 if (tooLow(next.key, cmp)) 3196 next = null; 3197 else { 3198 @SuppressWarnings("unchecked") V vv = (V)x; 3199 nextValue = vv; 3200 } 3201 break; 3202 } 3203 } 3204 } 3205 3206 public void remove() { 3207 Node<K,V> l = lastReturned; 3208 if (l == null) 3209 throw new IllegalStateException(); 3210 m.remove(l.key); 3211 lastReturned = null; 3212 } 3213 3214 public Spliterator<T> trySplit() { 3215 return null; 3216 } 3217 3218 public boolean tryAdvance(Consumer<? super T> action) { 3219 if (hasNext()) { 3220 action.accept(next()); 3221 return true; 3222 } 3223 return false; 3224 } 3225 3226 public void forEachRemaining(Consumer<? super T> action) { 3227 while (hasNext()) 3228 action.accept(next()); 3229 } 3230 3231 public long estimateSize() { 3232 return Long.MAX_VALUE; 3233 } 3234 3235 } 3236 3237 final class SubMapValueIterator extends SubMapIter<V> { 3238 public V next() { 3239 V v = nextValue; 3240 advance(); 3241 return v; 3242 } 3243 public int characteristics() { 3244 return 0; 3245 } 3246 } 3247 3248 final class SubMapKeyIterator extends SubMapIter<K> { 3249 public K next() { 3250 Node<K,V> n = next; 3251 advance(); 3252 return n.key; 3253 } 3254 public int characteristics() { 3255 return Spliterator.DISTINCT | Spliterator.ORDERED | 3256 Spliterator.SORTED; 3257 } 3258 public final Comparator<? super K> getComparator() { 3259 return SubMap.this.comparator(); 3260 } 3261 } 3262 3263 final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> { 3264 public Map.Entry<K,V> next() { 3265 Node<K,V> n = next; 3266 V v = nextValue; 3267 advance(); 3268 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v); 3269 } 3270 public int characteristics() { 3271 return Spliterator.DISTINCT; 3272 } 3273 } 3274 } 3275 3276 // default Map method overrides 3277 3278 public void forEach(BiConsumer<? super K, ? super V> action) { 3279 if (action == null) throw new NullPointerException(); 3280 V v; 3281 for (Node<K,V> n = findFirst(); n != null; n = n.next) { 3282 if ((v = n.getValidValue()) != null) 3283 action.accept(n.key, v); 3284 } 3285 } 3286 3287 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 3288 if (function == null) throw new NullPointerException(); 3289 V v; 3290 for (Node<K,V> n = findFirst(); n != null; n = n.next) { 3291 while ((v = n.getValidValue()) != null) { 3292 V r = function.apply(n.key, v); 3293 if (r == null) throw new NullPointerException(); 3294 if (n.casValue(v, r)) 3295 break; 3296 } 3297 } 3298 } 3299 3300 /** 3301 * Helper method for EntrySet.removeIf 3302 */ 3303 boolean removeEntryIf(Predicate<? super Entry<K, V>> function) { 3304 if (function == null) throw new NullPointerException(); 3305 boolean removed = false; 3306 for (Node<K,V> n = findFirst(); n != null; n = n.next) { 3307 V v; 3308 if ((v = n.getValidValue()) != null) { 3309 K k = n.key; 3310 Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v); 3311 if (function.test(e) && remove(k, v)) 3312 removed = true; 3313 } 3314 } 3315 return removed; 3316 } 3317 3318 /** 3319 * Helper method for Values.removeIf 3320 */ 3321 boolean removeValueIf(Predicate<? super V> function) { 3322 if (function == null) throw new NullPointerException(); 3323 boolean removed = false; 3324 for (Node<K,V> n = findFirst(); n != null; n = n.next) { 3325 V v; 3326 if ((v = n.getValidValue()) != null) { 3327 K k = n.key; 3328 if (function.test(v) && remove(k, v)) 3329 removed = true; 3330 } 3331 } 3332 return removed; 3333 } 3334 3335 /** 3336 * Base class providing common structure for Spliterators. 3337 * (Although not all that much common functionality; as usual for 3338 * view classes, details annoyingly vary in key, value, and entry 3339 * subclasses in ways that are not worth abstracting out for 3340 * internal classes.) 3341 * 3342 * The basic split strategy is to recursively descend from top 3343 * level, row by row, descending to next row when either split 3344 * off, or the end of row is encountered. Control of the number of 3345 * splits relies on some statistical estimation: The expected 3346 * remaining number of elements of a skip list when advancing 3347 * either across or down decreases by about 25%. To make this 3348 * observation useful, we need to know initial size, which we 3349 * don't. But we can just use Integer.MAX_VALUE so that we 3350 * don't prematurely zero out while splitting. 3351 */ 3352 abstract static class CSLMSpliterator<K,V> { 3353 final Comparator<? super K> comparator; 3354 final K fence; // exclusive upper bound for keys, or null if to end 3355 Index<K,V> row; // the level to split out 3356 Node<K,V> current; // current traversal node; initialize at origin 3357 int est; // pseudo-size estimate 3358 CSLMSpliterator(Comparator<? super K> comparator, Index<K,V> row, 3359 Node<K,V> origin, K fence, int est) { 3360 this.comparator = comparator; this.row = row; 3361 this.current = origin; this.fence = fence; this.est = est; 3362 } 3363 3364 public final long estimateSize() { return (long)est; } 3365 } 3366 3367 static final class KeySpliterator<K,V> extends CSLMSpliterator<K,V> 3368 implements Spliterator<K> { 3369 KeySpliterator(Comparator<? super K> comparator, Index<K,V> row, 3370 Node<K,V> origin, K fence, int est) { 3371 super(comparator, row, origin, fence, est); 3372 } 3373 3374 public Spliterator<K> trySplit() { 3375 Node<K,V> e; K ek; 3376 Comparator<? super K> cmp = comparator; 3377 K f = fence; 3378 if ((e = current) != null && (ek = e.key) != null) { 3379 for (Index<K,V> q = row; q != null; q = row = q.down) { 3380 Index<K,V> s; Node<K,V> b, n; K sk; 3381 if ((s = q.right) != null && (b = s.node) != null && 3382 (n = b.next) != null && n.value != null && 3383 (sk = n.key) != null && cpr(cmp, sk, ek) > 0 && 3384 (f == null || cpr(cmp, sk, f) < 0)) { 3385 current = n; 3386 Index<K,V> r = q.down; 3387 row = (s.right != null) ? s : s.down; 3388 est -= est >>> 2; 3389 return new KeySpliterator<K,V>(cmp, r, e, sk, est); 3390 } 3391 } 3392 } 3393 return null; 3394 } 3395 3396 public void forEachRemaining(Consumer<? super K> action) { 3397 if (action == null) throw new NullPointerException(); 3398 Comparator<? super K> cmp = comparator; 3399 K f = fence; 3400 Node<K,V> e = current; 3401 current = null; 3402 for (; e != null; e = e.next) { 3403 K k; Object v; 3404 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) 3405 break; 3406 if ((v = e.value) != null && v != e) 3407 action.accept(k); 3408 } 3409 } 3410 3411 public boolean tryAdvance(Consumer<? super K> action) { 3412 if (action == null) throw new NullPointerException(); 3413 Comparator<? super K> cmp = comparator; 3414 K f = fence; 3415 Node<K,V> e = current; 3416 for (; e != null; e = e.next) { 3417 K k; Object v; 3418 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) { 3419 e = null; 3420 break; 3421 } 3422 if ((v = e.value) != null && v != e) { 3423 current = e.next; 3424 action.accept(k); 3425 return true; 3426 } 3427 } 3428 current = e; 3429 return false; 3430 } 3431 3432 public int characteristics() { 3433 return Spliterator.DISTINCT | Spliterator.SORTED | 3434 Spliterator.ORDERED | Spliterator.CONCURRENT | 3435 Spliterator.NONNULL; 3436 } 3437 3438 public final Comparator<? super K> getComparator() { 3439 return comparator; 3440 } 3441 } 3442 // factory method for KeySpliterator 3443 final KeySpliterator<K,V> keySpliterator() { 3444 Comparator<? super K> cmp = comparator; 3445 for (;;) { // ensure h corresponds to origin p 3446 HeadIndex<K,V> h; Node<K,V> p; 3447 Node<K,V> b = (h = head).node; 3448 if ((p = b.next) == null || p.value != null) 3449 return new KeySpliterator<K,V>(cmp, h, p, null, (p == null) ? 3450 0 : Integer.MAX_VALUE); 3451 p.helpDelete(b, p.next); 3452 } 3453 } 3454 3455 static final class ValueSpliterator<K,V> extends CSLMSpliterator<K,V> 3456 implements Spliterator<V> { 3457 ValueSpliterator(Comparator<? super K> comparator, Index<K,V> row, 3458 Node<K,V> origin, K fence, int est) { 3459 super(comparator, row, origin, fence, est); 3460 } 3461 3462 public Spliterator<V> trySplit() { 3463 Node<K,V> e; K ek; 3464 Comparator<? super K> cmp = comparator; 3465 K f = fence; 3466 if ((e = current) != null && (ek = e.key) != null) { 3467 for (Index<K,V> q = row; q != null; q = row = q.down) { 3468 Index<K,V> s; Node<K,V> b, n; K sk; 3469 if ((s = q.right) != null && (b = s.node) != null && 3470 (n = b.next) != null && n.value != null && 3471 (sk = n.key) != null && cpr(cmp, sk, ek) > 0 && 3472 (f == null || cpr(cmp, sk, f) < 0)) { 3473 current = n; 3474 Index<K,V> r = q.down; 3475 row = (s.right != null) ? s : s.down; 3476 est -= est >>> 2; 3477 return new ValueSpliterator<K,V>(cmp, r, e, sk, est); 3478 } 3479 } 3480 } 3481 return null; 3482 } 3483 3484 public void forEachRemaining(Consumer<? super V> action) { 3485 if (action == null) throw new NullPointerException(); 3486 Comparator<? super K> cmp = comparator; 3487 K f = fence; 3488 Node<K,V> e = current; 3489 current = null; 3490 for (; e != null; e = e.next) { 3491 K k; Object v; 3492 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) 3493 break; 3494 if ((v = e.value) != null && v != e) { 3495 @SuppressWarnings("unchecked") V vv = (V)v; 3496 action.accept(vv); 3497 } 3498 } 3499 } 3500 3501 public boolean tryAdvance(Consumer<? super V> action) { 3502 if (action == null) throw new NullPointerException(); 3503 Comparator<? super K> cmp = comparator; 3504 K f = fence; 3505 Node<K,V> e = current; 3506 for (; e != null; e = e.next) { 3507 K k; Object v; 3508 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) { 3509 e = null; 3510 break; 3511 } 3512 if ((v = e.value) != null && v != e) { 3513 current = e.next; 3514 @SuppressWarnings("unchecked") V vv = (V)v; 3515 action.accept(vv); 3516 return true; 3517 } 3518 } 3519 current = e; 3520 return false; 3521 } 3522 3523 public int characteristics() { 3524 return Spliterator.CONCURRENT | Spliterator.ORDERED | 3525 Spliterator.NONNULL; 3526 } 3527 } 3528 3529 // Almost the same as keySpliterator() 3530 final ValueSpliterator<K,V> valueSpliterator() { 3531 Comparator<? super K> cmp = comparator; 3532 for (;;) { 3533 HeadIndex<K,V> h; Node<K,V> p; 3534 Node<K,V> b = (h = head).node; 3535 if ((p = b.next) == null || p.value != null) 3536 return new ValueSpliterator<K,V>(cmp, h, p, null, (p == null) ? 3537 0 : Integer.MAX_VALUE); 3538 p.helpDelete(b, p.next); 3539 } 3540 } 3541 3542 static final class EntrySpliterator<K,V> extends CSLMSpliterator<K,V> 3543 implements Spliterator<Map.Entry<K,V>> { 3544 EntrySpliterator(Comparator<? super K> comparator, Index<K,V> row, 3545 Node<K,V> origin, K fence, int est) { 3546 super(comparator, row, origin, fence, est); 3547 } 3548 3549 public Spliterator<Map.Entry<K,V>> trySplit() { 3550 Node<K,V> e; K ek; 3551 Comparator<? super K> cmp = comparator; 3552 K f = fence; 3553 if ((e = current) != null && (ek = e.key) != null) { 3554 for (Index<K,V> q = row; q != null; q = row = q.down) { 3555 Index<K,V> s; Node<K,V> b, n; K sk; 3556 if ((s = q.right) != null && (b = s.node) != null && 3557 (n = b.next) != null && n.value != null && 3558 (sk = n.key) != null && cpr(cmp, sk, ek) > 0 && 3559 (f == null || cpr(cmp, sk, f) < 0)) { 3560 current = n; 3561 Index<K,V> r = q.down; 3562 row = (s.right != null) ? s : s.down; 3563 est -= est >>> 2; 3564 return new EntrySpliterator<K,V>(cmp, r, e, sk, est); 3565 } 3566 } 3567 } 3568 return null; 3569 } 3570 3571 public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) { 3572 if (action == null) throw new NullPointerException(); 3573 Comparator<? super K> cmp = comparator; 3574 K f = fence; 3575 Node<K,V> e = current; 3576 current = null; 3577 for (; e != null; e = e.next) { 3578 K k; Object v; 3579 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) 3580 break; 3581 if ((v = e.value) != null && v != e) { 3582 @SuppressWarnings("unchecked") V vv = (V)v; 3583 action.accept 3584 (new AbstractMap.SimpleImmutableEntry<K,V>(k, vv)); 3585 } 3586 } 3587 } 3588 3589 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) { 3590 if (action == null) throw new NullPointerException(); 3591 Comparator<? super K> cmp = comparator; 3592 K f = fence; 3593 Node<K,V> e = current; 3594 for (; e != null; e = e.next) { 3595 K k; Object v; 3596 if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) { 3597 e = null; 3598 break; 3599 } 3600 if ((v = e.value) != null && v != e) { 3601 current = e.next; 3602 @SuppressWarnings("unchecked") V vv = (V)v; 3603 action.accept 3604 (new AbstractMap.SimpleImmutableEntry<K,V>(k, vv)); 3605 return true; 3606 } 3607 } 3608 current = e; 3609 return false; 3610 } 3611 3612 public int characteristics() { 3613 return Spliterator.DISTINCT | Spliterator.SORTED | 3614 Spliterator.ORDERED | Spliterator.CONCURRENT | 3615 Spliterator.NONNULL; 3616 } 3617 3618 public final Comparator<Map.Entry<K,V>> getComparator() { 3619 // Adapt or create a key-based comparator 3620 if (comparator != null) { 3621 return Map.Entry.comparingByKey(comparator); 3622 } 3623 else { 3624 return (Comparator<Map.Entry<K,V>> & Serializable) (e1, e2) -> { 3625 @SuppressWarnings("unchecked") 3626 Comparable<? super K> k1 = (Comparable<? super K>) e1.getKey(); 3627 return k1.compareTo(e2.getKey()); 3628 }; 3629 } 3630 } 3631 } 3632 3633 // Almost the same as keySpliterator() 3634 final EntrySpliterator<K,V> entrySpliterator() { 3635 Comparator<? super K> cmp = comparator; 3636 for (;;) { // almost same as key version 3637 HeadIndex<K,V> h; Node<K,V> p; 3638 Node<K,V> b = (h = head).node; 3639 if ((p = b.next) == null || p.value != null) 3640 return new EntrySpliterator<K,V>(cmp, h, p, null, (p == null) ? 3641 0 : Integer.MAX_VALUE); 3642 p.helpDelete(b, p.next); 3643 } 3644 } 3645 3646 // Unsafe mechanics 3647 private static final sun.misc.Unsafe UNSAFE; 3648 private static final long headOffset; 3649 private static final long SECONDARY; 3650 static { 3651 try { 3652 UNSAFE = sun.misc.Unsafe.getUnsafe(); 3653 Class<?> k = ConcurrentSkipListMap.class; 3654 headOffset = UNSAFE.objectFieldOffset 3655 (k.getDeclaredField("head")); 3656 Class<?> tk = Thread.class; 3657 SECONDARY = UNSAFE.objectFieldOffset 3658 (tk.getDeclaredField("threadLocalRandomSecondarySeed")); 3659 3660 } catch (Exception e) { 3661 throw new Error(e); 3662 } 3663 } 3664 }