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