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