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