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