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