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