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