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