Print this page
Split |
Close |
Expand all |
Collapse all |
--- old/src/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java
+++ new/src/share/classes/java/util/concurrent/ConcurrentLinkedDeque.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 *
↓ open down ↓ |
30 lines elided |
↑ open up ↑ |
31 31 * Written by Doug Lea and Martin Buchholz with assistance from members of
32 32 * JCP JSR-166 Expert Group and released to the public domain, as explained
33 33 * at http://creativecommons.org/licenses/publicdomain
34 34 */
35 35
36 36 package java.util.concurrent;
37 37
38 38 import java.util.AbstractCollection;
39 39 import java.util.ArrayList;
40 40 import java.util.Collection;
41 -import java.util.ConcurrentModificationException;
42 41 import java.util.Deque;
43 42 import java.util.Iterator;
44 43 import java.util.NoSuchElementException;
45 44 import java.util.Queue;
46 45
47 46 /**
48 47 * An unbounded concurrent {@linkplain Deque deque} based on linked nodes.
49 48 * Concurrent insertion, removal, and access operations execute safely
50 49 * across multiple threads.
51 50 * A {@code ConcurrentLinkedDeque} is an appropriate choice when
52 51 * many threads will share access to a common collection.
53 52 * Like most other concurrent collection implementations, this class
54 53 * does not permit the use of {@code null} elements.
55 54 *
56 55 * <p>Iterators are <i>weakly consistent</i>, returning elements
57 56 * reflecting the state of the deque at some point at or since the
58 57 * creation of the iterator. They do <em>not</em> throw {@link
59 58 * java.util.ConcurrentModificationException
60 59 * ConcurrentModificationException}, and may proceed concurrently with
61 60 * other operations.
62 61 *
63 62 * <p>Beware that, unlike in most collections, the {@code size}
64 63 * method is <em>NOT</em> a constant-time operation. Because of the
65 64 * asynchronous nature of these deques, determining the current number
66 65 * of elements requires a traversal of the elements.
67 66 *
68 67 * <p>This class and its iterator implement all of the <em>optional</em>
69 68 * methods of the {@link Deque} and {@link Iterator} interfaces.
70 69 *
71 70 * <p>Memory consistency effects: As with other concurrent collections,
72 71 * actions in a thread prior to placing an object into a
73 72 * {@code ConcurrentLinkedDeque}
74 73 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
75 74 * actions subsequent to the access or removal of that element from
76 75 * the {@code ConcurrentLinkedDeque} in another thread.
77 76 *
78 77 * <p>This class is a member of the
79 78 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
80 79 * Java Collections Framework</a>.
81 80 *
82 81 * @since 1.7
83 82 * @author Doug Lea
84 83 * @author Martin Buchholz
85 84 * @param <E> the type of elements held in this collection
86 85 */
87 86
88 87 public class ConcurrentLinkedDeque<E>
89 88 extends AbstractCollection<E>
90 89 implements Deque<E>, java.io.Serializable {
91 90
92 91 /*
93 92 * This is an implementation of a concurrent lock-free deque
94 93 * supporting interior removes but not interior insertions, as
95 94 * required to support the entire Deque interface.
96 95 *
97 96 * We extend the techniques developed for ConcurrentLinkedQueue and
98 97 * LinkedTransferQueue (see the internal docs for those classes).
99 98 * Understanding the ConcurrentLinkedQueue implementation is a
100 99 * prerequisite for understanding the implementation of this class.
101 100 *
102 101 * The data structure is a symmetrical doubly-linked "GC-robust"
103 102 * linked list of nodes. We minimize the number of volatile writes
104 103 * using two techniques: advancing multiple hops with a single CAS
105 104 * and mixing volatile and non-volatile writes of the same memory
106 105 * locations.
107 106 *
108 107 * A node contains the expected E ("item") and links to predecessor
109 108 * ("prev") and successor ("next") nodes:
110 109 *
111 110 * class Node<E> { volatile Node<E> prev, next; volatile E item; }
112 111 *
113 112 * A node p is considered "live" if it contains a non-null item
114 113 * (p.item != null). When an item is CASed to null, the item is
115 114 * atomically logically deleted from the collection.
116 115 *
117 116 * At any time, there is precisely one "first" node with a null
118 117 * prev reference that terminates any chain of prev references
119 118 * starting at a live node. Similarly there is precisely one
120 119 * "last" node terminating any chain of next references starting at
121 120 * a live node. The "first" and "last" nodes may or may not be live.
122 121 * The "first" and "last" nodes are always mutually reachable.
123 122 *
124 123 * A new element is added atomically by CASing the null prev or
125 124 * next reference in the first or last node to a fresh node
126 125 * containing the element. The element's node atomically becomes
127 126 * "live" at that point.
128 127 *
129 128 * A node is considered "active" if it is a live node, or the
130 129 * first or last node. Active nodes cannot be unlinked.
131 130 *
132 131 * A "self-link" is a next or prev reference that is the same node:
133 132 * p.prev == p or p.next == p
134 133 * Self-links are used in the node unlinking process. Active nodes
135 134 * never have self-links.
136 135 *
137 136 * A node p is active if and only if:
138 137 *
139 138 * p.item != null ||
140 139 * (p.prev == null && p.next != p) ||
141 140 * (p.next == null && p.prev != p)
142 141 *
143 142 * The deque object has two node references, "head" and "tail".
144 143 * The head and tail are only approximations to the first and last
145 144 * nodes of the deque. The first node can always be found by
146 145 * following prev pointers from head; likewise for tail. However,
147 146 * it is permissible for head and tail to be referring to deleted
148 147 * nodes that have been unlinked and so may not be reachable from
149 148 * any live node.
150 149 *
151 150 * There are 3 stages of node deletion;
152 151 * "logical deletion", "unlinking", and "gc-unlinking".
153 152 *
154 153 * 1. "logical deletion" by CASing item to null atomically removes
155 154 * the element from the collection, and makes the containing node
156 155 * eligible for unlinking.
157 156 *
158 157 * 2. "unlinking" makes a deleted node unreachable from active
159 158 * nodes, and thus eventually reclaimable by GC. Unlinked nodes
160 159 * may remain reachable indefinitely from an iterator.
161 160 *
162 161 * Physical node unlinking is merely an optimization (albeit a
163 162 * critical one), and so can be performed at our convenience. At
164 163 * any time, the set of live nodes maintained by prev and next
165 164 * links are identical, that is, the live nodes found via next
166 165 * links from the first node is equal to the elements found via
167 166 * prev links from the last node. However, this is not true for
168 167 * nodes that have already been logically deleted - such nodes may
169 168 * be reachable in one direction only.
170 169 *
171 170 * 3. "gc-unlinking" takes unlinking further by making active
172 171 * nodes unreachable from deleted nodes, making it easier for the
173 172 * GC to reclaim future deleted nodes. This step makes the data
174 173 * structure "gc-robust", as first described in detail by Boehm
175 174 * (http://portal.acm.org/citation.cfm?doid=503272.503282).
176 175 *
177 176 * GC-unlinked nodes may remain reachable indefinitely from an
178 177 * iterator, but unlike unlinked nodes, are never reachable from
179 178 * head or tail.
180 179 *
181 180 * Making the data structure GC-robust will eliminate the risk of
182 181 * unbounded memory retention with conservative GCs and is likely
183 182 * to improve performance with generational GCs.
184 183 *
185 184 * When a node is dequeued at either end, e.g. via poll(), we would
186 185 * like to break any references from the node to active nodes. We
187 186 * develop further the use of self-links that was very effective in
188 187 * other concurrent collection classes. The idea is to replace
189 188 * prev and next pointers with special values that are interpreted
190 189 * to mean off-the-list-at-one-end. These are approximations, but
191 190 * good enough to preserve the properties we want in our
192 191 * traversals, e.g. we guarantee that a traversal will never visit
193 192 * the same element twice, but we don't guarantee whether a
194 193 * traversal that runs out of elements will be able to see more
195 194 * elements later after enqueues at that end. Doing gc-unlinking
196 195 * safely is particularly tricky, since any node can be in use
197 196 * indefinitely (for example by an iterator). We must ensure that
198 197 * the nodes pointed at by head/tail never get gc-unlinked, since
199 198 * head/tail are needed to get "back on track" by other nodes that
200 199 * are gc-unlinked. gc-unlinking accounts for much of the
201 200 * implementation complexity.
202 201 *
203 202 * Since neither unlinking nor gc-unlinking are necessary for
204 203 * correctness, there are many implementation choices regarding
↓ open down ↓ |
153 lines elided |
↑ open up ↑ |
205 204 * frequency (eagerness) of these operations. Since volatile
206 205 * reads are likely to be much cheaper than CASes, saving CASes by
207 206 * unlinking multiple adjacent nodes at a time may be a win.
208 207 * gc-unlinking can be performed rarely and still be effective,
209 208 * since it is most important that long chains of deleted nodes
210 209 * are occasionally broken.
211 210 *
212 211 * The actual representation we use is that p.next == p means to
213 212 * goto the first node (which in turn is reached by following prev
214 213 * pointers from head), and p.next == null && p.prev == p means
215 - * that the iteration is at an end and that p is a (final static)
214 + * that the iteration is at an end and that p is a (static final)
216 215 * dummy node, NEXT_TERMINATOR, and not the last active node.
217 216 * Finishing the iteration when encountering such a TERMINATOR is
218 217 * good enough for read-only traversals, so such traversals can use
219 218 * p.next == null as the termination condition. When we need to
220 219 * find the last (active) node, for enqueueing a new node, we need
221 220 * to check whether we have reached a TERMINATOR node; if so,
222 221 * restart traversal from tail.
223 222 *
224 223 * The implementation is completely directionally symmetrical,
225 224 * except that most public methods that iterate through the list
226 225 * follow next pointers ("forward" direction).
227 226 *
228 227 * We believe (without full proof) that all single-element deque
229 228 * operations (e.g., addFirst, peekLast, pollLast) are linearizable
230 229 * (see Herlihy and Shavit's book). However, some combinations of
231 230 * operations are known not to be linearizable. In particular,
232 231 * when an addFirst(A) is racing with pollFirst() removing B, it is
233 232 * possible for an observer iterating over the elements to observe
234 233 * A B C and subsequently observe A C, even though no interior
235 234 * removes are ever performed. Nevertheless, iterators behave
236 235 * reasonably, providing the "weakly consistent" guarantees.
237 236 *
238 237 * Empirically, microbenchmarks suggest that this class adds about
239 238 * 40% overhead relative to ConcurrentLinkedQueue, which feels as
240 239 * good as we can hope for.
241 240 */
242 241
243 242 private static final long serialVersionUID = 876323262645176354L;
244 243
245 244 /**
246 245 * A node from which the first node on list (that is, the unique node p
247 246 * with p.prev == null && p.next != p) can be reached in O(1) time.
248 247 * Invariants:
249 248 * - the first node is always O(1) reachable from head via prev links
250 249 * - all live nodes are reachable from the first node via succ()
251 250 * - head != null
252 251 * - (tmp = head).next != tmp || tmp != head
253 252 * - head is never gc-unlinked (but may be unlinked)
254 253 * Non-invariants:
255 254 * - head.item may or may not be null
256 255 * - head may not be reachable from the first or last node, or from tail
257 256 */
258 257 private transient volatile Node<E> head;
259 258
260 259 /**
261 260 * A node from which the last node on list (that is, the unique node p
262 261 * with p.next == null && p.prev != p) can be reached in O(1) time.
263 262 * Invariants:
↓ open down ↓ |
38 lines elided |
↑ open up ↑ |
264 263 * - the last node is always O(1) reachable from tail via next links
265 264 * - all live nodes are reachable from the last node via pred()
266 265 * - tail != null
267 266 * - tail is never gc-unlinked (but may be unlinked)
268 267 * Non-invariants:
269 268 * - tail.item may or may not be null
270 269 * - tail may not be reachable from the first or last node, or from head
271 270 */
272 271 private transient volatile Node<E> tail;
273 272
274 - private final static Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR;
273 + private static final Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR;
275 274
276 275 static {
277 276 PREV_TERMINATOR = new Node<Object>(null);
278 277 PREV_TERMINATOR.next = PREV_TERMINATOR;
279 278 NEXT_TERMINATOR = new Node<Object>(null);
280 279 NEXT_TERMINATOR.prev = NEXT_TERMINATOR;
281 280 }
282 281
283 282 @SuppressWarnings("unchecked")
284 283 Node<E> prevTerminator() {
285 284 return (Node<E>) PREV_TERMINATOR;
286 285 }
287 286
288 287 @SuppressWarnings("unchecked")
289 288 Node<E> nextTerminator() {
290 289 return (Node<E>) NEXT_TERMINATOR;
291 290 }
292 291
293 292 static final class Node<E> {
294 293 volatile Node<E> prev;
295 294 volatile E item;
296 295 volatile Node<E> next;
297 296
298 297 /**
299 298 * Constructs a new node. Uses relaxed write because item can
300 299 * only be seen after publication via casNext or casPrev.
301 300 */
302 301 Node(E item) {
303 302 UNSAFE.putObject(this, itemOffset, item);
304 303 }
305 304
306 305 boolean casItem(E cmp, E val) {
307 306 return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
308 307 }
309 308
310 309 void lazySetNext(Node<E> val) {
311 310 UNSAFE.putOrderedObject(this, nextOffset, val);
312 311 }
313 312
314 313 boolean casNext(Node<E> cmp, Node<E> val) {
315 314 return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
316 315 }
317 316
318 317 void lazySetPrev(Node<E> val) {
319 318 UNSAFE.putOrderedObject(this, prevOffset, val);
320 319 }
321 320
322 321 boolean casPrev(Node<E> cmp, Node<E> val) {
323 322 return UNSAFE.compareAndSwapObject(this, prevOffset, cmp, val);
324 323 }
325 324
326 325 // Unsafe mechanics
327 326
328 327 private static final sun.misc.Unsafe UNSAFE =
329 328 sun.misc.Unsafe.getUnsafe();
330 329 private static final long prevOffset =
331 330 objectFieldOffset(UNSAFE, "prev", Node.class);
332 331 private static final long itemOffset =
333 332 objectFieldOffset(UNSAFE, "item", Node.class);
334 333 private static final long nextOffset =
335 334 objectFieldOffset(UNSAFE, "next", Node.class);
336 335 }
337 336
338 337 /**
339 338 * Links e as first element.
340 339 */
341 340 private void linkFirst(E e) {
342 341 checkNotNull(e);
343 342 final Node<E> newNode = new Node<E>(e);
344 343
345 344 restartFromHead:
346 345 for (;;)
347 346 for (Node<E> h = head, p = h, q;;) {
348 347 if ((q = p.prev) != null &&
349 348 (q = (p = q).prev) != null)
350 349 // Check for head updates every other hop.
351 350 // If p == q, we are sure to follow head instead.
352 351 p = (h != (h = head)) ? h : q;
353 352 else if (p.next == p) // PREV_TERMINATOR
354 353 continue restartFromHead;
355 354 else {
356 355 // p is first node
357 356 newNode.lazySetNext(p); // CAS piggyback
358 357 if (p.casPrev(null, newNode)) {
359 358 // Successful CAS is the linearization point
360 359 // for e to become an element of this deque,
361 360 // and for newNode to become "live".
362 361 if (p != h) // hop two nodes at a time
363 362 casHead(h, newNode); // Failure is OK.
364 363 return;
365 364 }
366 365 // Lost CAS race to another thread; re-read prev
367 366 }
368 367 }
369 368 }
370 369
371 370 /**
372 371 * Links e as last element.
373 372 */
374 373 private void linkLast(E e) {
375 374 checkNotNull(e);
376 375 final Node<E> newNode = new Node<E>(e);
377 376
378 377 restartFromTail:
379 378 for (;;)
380 379 for (Node<E> t = tail, p = t, q;;) {
381 380 if ((q = p.next) != null &&
382 381 (q = (p = q).next) != null)
383 382 // Check for tail updates every other hop.
384 383 // If p == q, we are sure to follow tail instead.
385 384 p = (t != (t = tail)) ? t : q;
386 385 else if (p.prev == p) // NEXT_TERMINATOR
387 386 continue restartFromTail;
388 387 else {
389 388 // p is last node
390 389 newNode.lazySetPrev(p); // CAS piggyback
391 390 if (p.casNext(null, newNode)) {
392 391 // Successful CAS is the linearization point
393 392 // for e to become an element of this deque,
↓ open down ↓ |
109 lines elided |
↑ open up ↑ |
394 393 // and for newNode to become "live".
395 394 if (p != t) // hop two nodes at a time
396 395 casTail(t, newNode); // Failure is OK.
397 396 return;
398 397 }
399 398 // Lost CAS race to another thread; re-read next
400 399 }
401 400 }
402 401 }
403 402
404 - private final static int HOPS = 2;
403 + private static final int HOPS = 2;
405 404
406 405 /**
407 406 * Unlinks non-null node x.
408 407 */
409 408 void unlink(Node<E> x) {
410 409 // assert x != null;
411 410 // assert x.item == null;
412 411 // assert x != PREV_TERMINATOR;
413 412 // assert x != NEXT_TERMINATOR;
414 413
415 414 final Node<E> prev = x.prev;
416 415 final Node<E> next = x.next;
417 416 if (prev == null) {
418 417 unlinkFirst(x, next);
419 418 } else if (next == null) {
420 419 unlinkLast(x, prev);
421 420 } else {
422 421 // Unlink interior node.
423 422 //
424 423 // This is the common case, since a series of polls at the
425 424 // same end will be "interior" removes, except perhaps for
426 425 // the first one, since end nodes cannot be unlinked.
427 426 //
428 427 // At any time, all active nodes are mutually reachable by
429 428 // following a sequence of either next or prev pointers.
430 429 //
431 430 // Our strategy is to find the unique active predecessor
432 431 // and successor of x. Try to fix up their links so that
433 432 // they point to each other, leaving x unreachable from
434 433 // active nodes. If successful, and if x has no live
435 434 // predecessor/successor, we additionally try to gc-unlink,
436 435 // leaving active nodes unreachable from x, by rechecking
437 436 // that the status of predecessor and successor are
438 437 // unchanged and ensuring that x is not reachable from
439 438 // tail/head, before setting x's prev/next links to their
440 439 // logical approximate replacements, self/TERMINATOR.
441 440 Node<E> activePred, activeSucc;
442 441 boolean isFirst, isLast;
443 442 int hops = 1;
444 443
445 444 // Find active predecessor
446 445 for (Node<E> p = prev; ; ++hops) {
447 446 if (p.item != null) {
448 447 activePred = p;
449 448 isFirst = false;
450 449 break;
451 450 }
452 451 Node<E> q = p.prev;
453 452 if (q == null) {
454 453 if (p.next == p)
455 454 return;
456 455 activePred = p;
457 456 isFirst = true;
458 457 break;
459 458 }
460 459 else if (p == q)
461 460 return;
462 461 else
463 462 p = q;
464 463 }
465 464
466 465 // Find active successor
467 466 for (Node<E> p = next; ; ++hops) {
468 467 if (p.item != null) {
469 468 activeSucc = p;
470 469 isLast = false;
471 470 break;
472 471 }
473 472 Node<E> q = p.next;
474 473 if (q == null) {
475 474 if (p.prev == p)
476 475 return;
477 476 activeSucc = p;
478 477 isLast = true;
479 478 break;
480 479 }
481 480 else if (p == q)
482 481 return;
483 482 else
484 483 p = q;
485 484 }
486 485
487 486 // TODO: better HOP heuristics
488 487 if (hops < HOPS
489 488 // always squeeze out interior deleted nodes
490 489 && (isFirst | isLast))
491 490 return;
492 491
493 492 // Squeeze out deleted nodes between activePred and
494 493 // activeSucc, including x.
495 494 skipDeletedSuccessors(activePred);
496 495 skipDeletedPredecessors(activeSucc);
497 496
498 497 // Try to gc-unlink, if possible
499 498 if ((isFirst | isLast) &&
500 499
501 500 // Recheck expected state of predecessor and successor
502 501 (activePred.next == activeSucc) &&
503 502 (activeSucc.prev == activePred) &&
504 503 (isFirst ? activePred.prev == null : activePred.item != null) &&
505 504 (isLast ? activeSucc.next == null : activeSucc.item != null)) {
506 505
507 506 updateHead(); // Ensure x is not reachable from head
508 507 updateTail(); // Ensure x is not reachable from tail
509 508
510 509 // Finally, actually gc-unlink
511 510 x.lazySetPrev(isFirst ? prevTerminator() : x);
512 511 x.lazySetNext(isLast ? nextTerminator() : x);
513 512 }
514 513 }
515 514 }
516 515
517 516 /**
518 517 * Unlinks non-null first node.
519 518 */
520 519 private void unlinkFirst(Node<E> first, Node<E> next) {
521 520 // assert first != null;
522 521 // assert next != null;
523 522 // assert first.item == null;
524 523 for (Node<E> o = null, p = next, q;;) {
525 524 if (p.item != null || (q = p.next) == null) {
526 525 if (o != null && p.prev != p && first.casNext(next, p)) {
527 526 skipDeletedPredecessors(p);
528 527 if (first.prev == null &&
529 528 (p.next == null || p.item != null) &&
530 529 p.prev == first) {
531 530
532 531 updateHead(); // Ensure o is not reachable from head
533 532 updateTail(); // Ensure o is not reachable from tail
534 533
535 534 // Finally, actually gc-unlink
536 535 o.lazySetNext(o);
537 536 o.lazySetPrev(prevTerminator());
538 537 }
539 538 }
540 539 return;
541 540 }
542 541 else if (p == q)
543 542 return;
544 543 else {
545 544 o = p;
546 545 p = q;
547 546 }
548 547 }
549 548 }
550 549
551 550 /**
552 551 * Unlinks non-null last node.
553 552 */
554 553 private void unlinkLast(Node<E> last, Node<E> prev) {
555 554 // assert last != null;
556 555 // assert prev != null;
557 556 // assert last.item == null;
558 557 for (Node<E> o = null, p = prev, q;;) {
559 558 if (p.item != null || (q = p.prev) == null) {
560 559 if (o != null && p.next != p && last.casPrev(prev, p)) {
561 560 skipDeletedSuccessors(p);
562 561 if (last.next == null &&
563 562 (p.prev == null || p.item != null) &&
564 563 p.next == last) {
565 564
566 565 updateHead(); // Ensure o is not reachable from head
567 566 updateTail(); // Ensure o is not reachable from tail
568 567
569 568 // Finally, actually gc-unlink
570 569 o.lazySetPrev(o);
571 570 o.lazySetNext(nextTerminator());
572 571 }
573 572 }
574 573 return;
575 574 }
576 575 else if (p == q)
577 576 return;
578 577 else {
579 578 o = p;
580 579 p = q;
581 580 }
582 581 }
583 582 }
584 583
585 584 /**
586 585 * Guarantees that any node which was unlinked before a call to
587 586 * this method will be unreachable from head after it returns.
588 587 * Does not guarantee to eliminate slack, only that head will
589 588 * point to a node that was active while this method was running.
590 589 */
591 590 private final void updateHead() {
592 591 // Either head already points to an active node, or we keep
593 592 // trying to cas it to the first node until it does.
594 593 Node<E> h, p, q;
595 594 restartFromHead:
596 595 while ((h = head).item == null && (p = h.prev) != null) {
597 596 for (;;) {
598 597 if ((q = p.prev) == null ||
599 598 (q = (p = q).prev) == null) {
600 599 // It is possible that p is PREV_TERMINATOR,
601 600 // but if so, the CAS is guaranteed to fail.
602 601 if (casHead(h, p))
603 602 return;
604 603 else
605 604 continue restartFromHead;
606 605 }
607 606 else if (h != head)
608 607 continue restartFromHead;
609 608 else
610 609 p = q;
611 610 }
612 611 }
613 612 }
614 613
615 614 /**
616 615 * Guarantees that any node which was unlinked before a call to
617 616 * this method will be unreachable from tail after it returns.
618 617 * Does not guarantee to eliminate slack, only that tail will
619 618 * point to a node that was active while this method was running.
620 619 */
621 620 private final void updateTail() {
622 621 // Either tail already points to an active node, or we keep
623 622 // trying to cas it to the last node until it does.
624 623 Node<E> t, p, q;
625 624 restartFromTail:
626 625 while ((t = tail).item == null && (p = t.next) != null) {
627 626 for (;;) {
628 627 if ((q = p.next) == null ||
629 628 (q = (p = q).next) == null) {
630 629 // It is possible that p is NEXT_TERMINATOR,
631 630 // but if so, the CAS is guaranteed to fail.
632 631 if (casTail(t, p))
633 632 return;
634 633 else
635 634 continue restartFromTail;
636 635 }
637 636 else if (t != tail)
638 637 continue restartFromTail;
639 638 else
640 639 p = q;
641 640 }
642 641 }
643 642 }
644 643
645 644 private void skipDeletedPredecessors(Node<E> x) {
646 645 whileActive:
647 646 do {
648 647 Node<E> prev = x.prev;
649 648 // assert prev != null;
650 649 // assert x != NEXT_TERMINATOR;
651 650 // assert x != PREV_TERMINATOR;
652 651 Node<E> p = prev;
653 652 findActive:
654 653 for (;;) {
655 654 if (p.item != null)
656 655 break findActive;
657 656 Node<E> q = p.prev;
658 657 if (q == null) {
659 658 if (p.next == p)
660 659 continue whileActive;
661 660 break findActive;
662 661 }
663 662 else if (p == q)
664 663 continue whileActive;
665 664 else
666 665 p = q;
667 666 }
668 667
669 668 // found active CAS target
670 669 if (prev == p || x.casPrev(prev, p))
671 670 return;
672 671
673 672 } while (x.item != null || x.next == null);
674 673 }
675 674
676 675 private void skipDeletedSuccessors(Node<E> x) {
677 676 whileActive:
678 677 do {
679 678 Node<E> next = x.next;
680 679 // assert next != null;
681 680 // assert x != NEXT_TERMINATOR;
682 681 // assert x != PREV_TERMINATOR;
683 682 Node<E> p = next;
684 683 findActive:
685 684 for (;;) {
686 685 if (p.item != null)
687 686 break findActive;
688 687 Node<E> q = p.next;
689 688 if (q == null) {
690 689 if (p.prev == p)
691 690 continue whileActive;
692 691 break findActive;
693 692 }
694 693 else if (p == q)
695 694 continue whileActive;
696 695 else
697 696 p = q;
698 697 }
699 698
700 699 // found active CAS target
701 700 if (next == p || x.casNext(next, p))
702 701 return;
703 702
704 703 } while (x.item != null || x.prev == null);
705 704 }
706 705
707 706 /**
708 707 * Returns the successor of p, or the first node if p.next has been
709 708 * linked to self, which will only be true if traversing with a
710 709 * stale pointer that is now off the list.
711 710 */
712 711 final Node<E> succ(Node<E> p) {
713 712 // TODO: should we skip deleted nodes here?
714 713 Node<E> q = p.next;
715 714 return (p == q) ? first() : q;
716 715 }
717 716
718 717 /**
719 718 * Returns the predecessor of p, or the last node if p.prev has been
720 719 * linked to self, which will only be true if traversing with a
721 720 * stale pointer that is now off the list.
722 721 */
723 722 final Node<E> pred(Node<E> p) {
724 723 Node<E> q = p.prev;
725 724 return (p == q) ? last() : q;
726 725 }
727 726
728 727 /**
729 728 * Returns the first node, the unique node p for which:
730 729 * p.prev == null && p.next != p
731 730 * The returned node may or may not be logically deleted.
732 731 * Guarantees that head is set to the returned node.
733 732 */
734 733 Node<E> first() {
735 734 restartFromHead:
736 735 for (;;)
737 736 for (Node<E> h = head, p = h, q;;) {
738 737 if ((q = p.prev) != null &&
739 738 (q = (p = q).prev) != null)
740 739 // Check for head updates every other hop.
741 740 // If p == q, we are sure to follow head instead.
742 741 p = (h != (h = head)) ? h : q;
743 742 else if (p == h
744 743 // It is possible that p is PREV_TERMINATOR,
745 744 // but if so, the CAS is guaranteed to fail.
746 745 || casHead(h, p))
747 746 return p;
748 747 else
749 748 continue restartFromHead;
750 749 }
751 750 }
752 751
753 752 /**
754 753 * Returns the last node, the unique node p for which:
755 754 * p.next == null && p.prev != p
756 755 * The returned node may or may not be logically deleted.
757 756 * Guarantees that tail is set to the returned node.
758 757 */
759 758 Node<E> last() {
760 759 restartFromTail:
761 760 for (;;)
762 761 for (Node<E> t = tail, p = t, q;;) {
763 762 if ((q = p.next) != null &&
764 763 (q = (p = q).next) != null)
765 764 // Check for tail updates every other hop.
766 765 // If p == q, we are sure to follow tail instead.
767 766 p = (t != (t = tail)) ? t : q;
768 767 else if (p == t
769 768 // It is possible that p is NEXT_TERMINATOR,
770 769 // but if so, the CAS is guaranteed to fail.
771 770 || casTail(t, p))
772 771 return p;
773 772 else
774 773 continue restartFromTail;
775 774 }
776 775 }
777 776
778 777 // Minor convenience utilities
779 778
780 779 /**
781 780 * Throws NullPointerException if argument is null.
782 781 *
783 782 * @param v the element
784 783 */
785 784 private static void checkNotNull(Object v) {
786 785 if (v == null)
787 786 throw new NullPointerException();
788 787 }
789 788
790 789 /**
791 790 * Returns element unless it is null, in which case throws
792 791 * NoSuchElementException.
793 792 *
794 793 * @param v the element
795 794 * @return the element
796 795 */
797 796 private E screenNullResult(E v) {
798 797 if (v == null)
799 798 throw new NoSuchElementException();
800 799 return v;
801 800 }
802 801
803 802 /**
804 803 * Creates an array list and fills it with elements of this list.
805 804 * Used by toArray.
806 805 *
807 806 * @return the arrayList
808 807 */
809 808 private ArrayList<E> toArrayList() {
810 809 ArrayList<E> list = new ArrayList<E>();
811 810 for (Node<E> p = first(); p != null; p = succ(p)) {
812 811 E item = p.item;
813 812 if (item != null)
814 813 list.add(item);
815 814 }
816 815 return list;
817 816 }
818 817
819 818 /**
820 819 * Constructs an empty deque.
821 820 */
822 821 public ConcurrentLinkedDeque() {
823 822 head = tail = new Node<E>(null);
824 823 }
825 824
826 825 /**
827 826 * Constructs a deque initially containing the elements of
828 827 * the given collection, added in traversal order of the
829 828 * collection's iterator.
830 829 *
831 830 * @param c the collection of elements to initially contain
832 831 * @throws NullPointerException if the specified collection or any
833 832 * of its elements are null
834 833 */
835 834 public ConcurrentLinkedDeque(Collection<? extends E> c) {
836 835 // Copy c into a private chain of Nodes
837 836 Node<E> h = null, t = null;
838 837 for (E e : c) {
839 838 checkNotNull(e);
840 839 Node<E> newNode = new Node<E>(e);
841 840 if (h == null)
842 841 h = t = newNode;
843 842 else {
844 843 t.lazySetNext(newNode);
845 844 newNode.lazySetPrev(t);
846 845 t = newNode;
847 846 }
848 847 }
849 848 initHeadTail(h, t);
850 849 }
851 850
852 851 /**
853 852 * Initializes head and tail, ensuring invariants hold.
854 853 */
855 854 private void initHeadTail(Node<E> h, Node<E> t) {
856 855 if (h == t) {
857 856 if (h == null)
858 857 h = t = new Node<E>(null);
859 858 else {
860 859 // Avoid edge case of a single Node with non-null item.
861 860 Node<E> newNode = new Node<E>(null);
862 861 t.lazySetNext(newNode);
↓ open down ↓ |
448 lines elided |
↑ open up ↑ |
863 862 newNode.lazySetPrev(t);
864 863 t = newNode;
865 864 }
866 865 }
867 866 head = h;
868 867 tail = t;
869 868 }
870 869
871 870 /**
872 871 * Inserts the specified element at the front of this deque.
872 + * As the deque is unbounded, this method will never throw
873 + * {@link IllegalStateException}.
873 874 *
874 - * @throws NullPointerException {@inheritDoc}
875 + * @throws NullPointerException if the specified element is null
875 876 */
876 877 public void addFirst(E e) {
877 878 linkFirst(e);
878 879 }
879 880
880 881 /**
881 882 * Inserts the specified element at the end of this deque.
883 + * As the deque is unbounded, this method will never throw
884 + * {@link IllegalStateException}.
882 885 *
883 886 * <p>This method is equivalent to {@link #add}.
884 887 *
885 - * @throws NullPointerException {@inheritDoc}
888 + * @throws NullPointerException if the specified element is null
886 889 */
887 890 public void addLast(E e) {
888 891 linkLast(e);
889 892 }
890 893
891 894 /**
892 895 * Inserts the specified element at the front of this deque.
896 + * As the deque is unbounded, this method will never return {@code false}.
893 897 *
894 - * @return {@code true} always
895 - * @throws NullPointerException {@inheritDoc}
898 + * @return {@code true} (as specified by {@link Deque#offerFirst})
899 + * @throws NullPointerException if the specified element is null
896 900 */
897 901 public boolean offerFirst(E e) {
898 902 linkFirst(e);
899 903 return true;
900 904 }
901 905
902 906 /**
903 907 * Inserts the specified element at the end of this deque.
908 + * As the deque is unbounded, this method will never return {@code false}.
904 909 *
905 910 * <p>This method is equivalent to {@link #add}.
906 911 *
907 - * @return {@code true} always
908 - * @throws NullPointerException {@inheritDoc}
912 + * @return {@code true} (as specified by {@link Deque#offerLast})
913 + * @throws NullPointerException if the specified element is null
909 914 */
910 915 public boolean offerLast(E e) {
911 916 linkLast(e);
912 917 return true;
913 918 }
914 919
915 920 public E peekFirst() {
916 921 for (Node<E> p = first(); p != null; p = succ(p)) {
917 922 E item = p.item;
918 923 if (item != null)
919 924 return item;
920 925 }
921 926 return null;
922 927 }
923 928
924 929 public E peekLast() {
925 930 for (Node<E> p = last(); p != null; p = pred(p)) {
926 931 E item = p.item;
927 932 if (item != null)
928 933 return item;
929 934 }
930 935 return null;
931 936 }
932 937
↓ open down ↓ |
14 lines elided |
↑ open up ↑ |
933 938 /**
934 939 * @throws NoSuchElementException {@inheritDoc}
935 940 */
936 941 public E getFirst() {
937 942 return screenNullResult(peekFirst());
938 943 }
939 944
940 945 /**
941 946 * @throws NoSuchElementException {@inheritDoc}
942 947 */
943 - public E getLast() {
948 + public E getLast() {
944 949 return screenNullResult(peekLast());
945 950 }
946 951
947 952 public E pollFirst() {
948 953 for (Node<E> p = first(); p != null; p = succ(p)) {
949 954 E item = p.item;
950 955 if (item != null && p.casItem(item, null)) {
951 956 unlink(p);
952 957 return item;
953 958 }
954 959 }
955 960 return null;
956 961 }
957 962
958 963 public E pollLast() {
959 964 for (Node<E> p = last(); p != null; p = pred(p)) {
960 965 E item = p.item;
961 966 if (item != null && p.casItem(item, null)) {
962 967 unlink(p);
963 968 return item;
964 969 }
965 970 }
966 971 return null;
967 972 }
968 973
969 974 /**
970 975 * @throws NoSuchElementException {@inheritDoc}
971 976 */
972 977 public E removeFirst() {
973 978 return screenNullResult(pollFirst());
974 979 }
975 980
976 981 /**
↓ open down ↓ |
23 lines elided |
↑ open up ↑ |
977 982 * @throws NoSuchElementException {@inheritDoc}
978 983 */
979 984 public E removeLast() {
980 985 return screenNullResult(pollLast());
981 986 }
982 987
983 988 // *** Queue and stack methods ***
984 989
985 990 /**
986 991 * Inserts the specified element at the tail of this deque.
992 + * As the deque is unbounded, this method will never return {@code false}.
987 993 *
988 994 * @return {@code true} (as specified by {@link Queue#offer})
989 995 * @throws NullPointerException if the specified element is null
990 996 */
991 997 public boolean offer(E e) {
992 998 return offerLast(e);
993 999 }
994 1000
995 1001 /**
996 1002 * Inserts the specified element at the tail of this deque.
1003 + * As the deque is unbounded, this method will never throw
1004 + * {@link IllegalStateException} or return {@code false}.
997 1005 *
998 1006 * @return {@code true} (as specified by {@link Collection#add})
999 1007 * @throws NullPointerException if the specified element is null
1000 1008 */
1001 1009 public boolean add(E e) {
1002 1010 return offerLast(e);
1003 1011 }
1004 1012
1005 1013 public E poll() { return pollFirst(); }
1006 1014 public E remove() { return removeFirst(); }
1007 1015 public E peek() { return peekFirst(); }
1008 1016 public E element() { return getFirst(); }
↓ open down ↓ |
2 lines elided |
↑ open up ↑ |
1009 1017 public void push(E e) { addFirst(e); }
1010 1018 public E pop() { return removeFirst(); }
1011 1019
1012 1020 /**
1013 1021 * Removes the first element {@code e} such that
1014 1022 * {@code o.equals(e)}, if such an element exists in this deque.
1015 1023 * If the deque does not contain the element, it is unchanged.
1016 1024 *
1017 1025 * @param o element to be removed from this deque, if present
1018 1026 * @return {@code true} if the deque contained the specified element
1019 - * @throws NullPointerException if the specified element is {@code null}
1027 + * @throws NullPointerException if the specified element is null
1020 1028 */
1021 1029 public boolean removeFirstOccurrence(Object o) {
1022 1030 checkNotNull(o);
1023 1031 for (Node<E> p = first(); p != null; p = succ(p)) {
1024 1032 E item = p.item;
1025 1033 if (item != null && o.equals(item) && p.casItem(item, null)) {
1026 1034 unlink(p);
1027 1035 return true;
1028 1036 }
1029 1037 }
1030 1038 return false;
1031 1039 }
1032 1040
1033 1041 /**
1034 1042 * Removes the last element {@code e} such that
1035 1043 * {@code o.equals(e)}, if such an element exists in this deque.
1036 1044 * If the deque does not contain the element, it is unchanged.
1037 1045 *
1038 1046 * @param o element to be removed from this deque, if present
1039 1047 * @return {@code true} if the deque contained the specified element
1040 - * @throws NullPointerException if the specified element is {@code null}
1048 + * @throws NullPointerException if the specified element is null
1041 1049 */
1042 1050 public boolean removeLastOccurrence(Object o) {
1043 1051 checkNotNull(o);
1044 1052 for (Node<E> p = last(); p != null; p = pred(p)) {
1045 1053 E item = p.item;
1046 1054 if (item != null && o.equals(item) && p.casItem(item, null)) {
1047 1055 unlink(p);
1048 1056 return true;
1049 1057 }
1050 1058 }
1051 1059 return false;
1052 1060 }
1053 1061
1054 1062 /**
1055 1063 * Returns {@code true} if this deque contains at least one
1056 1064 * element {@code e} such that {@code o.equals(e)}.
1057 1065 *
1058 1066 * @param o element whose presence in this deque is to be tested
1059 1067 * @return {@code true} if this deque contains the specified element
1060 1068 */
1061 1069 public boolean contains(Object o) {
1062 1070 if (o == null) return false;
1063 1071 for (Node<E> p = first(); p != null; p = succ(p)) {
1064 1072 E item = p.item;
1065 1073 if (item != null && o.equals(item))
1066 1074 return true;
1067 1075 }
1068 1076 return false;
1069 1077 }
1070 1078
1071 1079 /**
1072 1080 * Returns {@code true} if this collection contains no elements.
1073 1081 *
1074 1082 * @return {@code true} if this collection contains no elements
1075 1083 */
1076 1084 public boolean isEmpty() {
1077 1085 return peekFirst() == null;
1078 1086 }
1079 1087
1080 1088 /**
1081 1089 * Returns the number of elements in this deque. If this deque
1082 1090 * contains more than {@code Integer.MAX_VALUE} elements, it
1083 1091 * returns {@code Integer.MAX_VALUE}.
1084 1092 *
1085 1093 * <p>Beware that, unlike in most collections, this method is
1086 1094 * <em>NOT</em> a constant-time operation. Because of the
1087 1095 * asynchronous nature of these deques, determining the current
1088 1096 * number of elements requires traversing them all to count them.
1089 1097 * Additionally, it is possible for the size to change during
1090 1098 * execution of this method, in which case the returned result
1091 1099 * will be inaccurate. Thus, this method is typically not very
1092 1100 * useful in concurrent applications.
1093 1101 *
1094 1102 * @return the number of elements in this deque
1095 1103 */
1096 1104 public int size() {
1097 1105 int count = 0;
1098 1106 for (Node<E> p = first(); p != null; p = succ(p))
1099 1107 if (p.item != null)
1100 1108 // Collection.size() spec says to max out
1101 1109 if (++count == Integer.MAX_VALUE)
1102 1110 break;
↓ open down ↓ |
52 lines elided |
↑ open up ↑ |
1103 1111 return count;
1104 1112 }
1105 1113
1106 1114 /**
1107 1115 * Removes the first element {@code e} such that
1108 1116 * {@code o.equals(e)}, if such an element exists in this deque.
1109 1117 * If the deque does not contain the element, it is unchanged.
1110 1118 *
1111 1119 * @param o element to be removed from this deque, if present
1112 1120 * @return {@code true} if the deque contained the specified element
1113 - * @throws NullPointerException if the specified element is {@code null}
1121 + * @throws NullPointerException if the specified element is null
1114 1122 */
1115 1123 public boolean remove(Object o) {
1116 1124 return removeFirstOccurrence(o);
1117 1125 }
1118 1126
1119 1127 /**
1120 1128 * Appends all of the elements in the specified collection to the end of
1121 1129 * this deque, in the order that they are returned by the specified
1122 1130 * collection's iterator. Attempts to {@code addAll} of a deque to
1123 1131 * itself result in {@code IllegalArgumentException}.
1124 1132 *
1125 1133 * @param c the elements to be inserted into this deque
1126 1134 * @return {@code true} if this deque changed as a result of the call
1127 1135 * @throws NullPointerException if the specified collection or any
1128 1136 * of its elements are null
1129 1137 * @throws IllegalArgumentException if the collection is this deque
1130 1138 */
1131 1139 public boolean addAll(Collection<? extends E> c) {
1132 1140 if (c == this)
1133 1141 // As historically specified in AbstractQueue#addAll
1134 1142 throw new IllegalArgumentException();
1135 1143
1136 1144 // Copy c into a private chain of Nodes
1137 1145 Node<E> beginningOfTheEnd = null, last = null;
1138 1146 for (E e : c) {
1139 1147 checkNotNull(e);
1140 1148 Node<E> newNode = new Node<E>(e);
1141 1149 if (beginningOfTheEnd == null)
1142 1150 beginningOfTheEnd = last = newNode;
1143 1151 else {
1144 1152 last.lazySetNext(newNode);
1145 1153 newNode.lazySetPrev(last);
1146 1154 last = newNode;
1147 1155 }
1148 1156 }
1149 1157 if (beginningOfTheEnd == null)
1150 1158 return false;
1151 1159
1152 1160 // Atomically append the chain at the tail of this collection
1153 1161 restartFromTail:
1154 1162 for (;;)
1155 1163 for (Node<E> t = tail, p = t, q;;) {
1156 1164 if ((q = p.next) != null &&
1157 1165 (q = (p = q).next) != null)
↓ open down ↓ |
34 lines elided |
↑ open up ↑ |
1158 1166 // Check for tail updates every other hop.
1159 1167 // If p == q, we are sure to follow tail instead.
1160 1168 p = (t != (t = tail)) ? t : q;
1161 1169 else if (p.prev == p) // NEXT_TERMINATOR
1162 1170 continue restartFromTail;
1163 1171 else {
1164 1172 // p is last node
1165 1173 beginningOfTheEnd.lazySetPrev(p); // CAS piggyback
1166 1174 if (p.casNext(null, beginningOfTheEnd)) {
1167 1175 // Successful CAS is the linearization point
1168 - // for all elements to be added to this queue.
1176 + // for all elements to be added to this deque.
1169 1177 if (!casTail(t, last)) {
1170 1178 // Try a little harder to update tail,
1171 1179 // since we may be adding many elements.
1172 1180 t = tail;
1173 1181 if (last.next == null)
1174 1182 casTail(t, last);
1175 1183 }
1176 1184 return true;
1177 1185 }
1178 1186 // Lost CAS race to another thread; re-read next
1179 1187 }
1180 1188 }
1181 1189 }
1182 1190
1183 1191 /**
1184 1192 * Removes all of the elements from this deque.
1185 1193 */
1186 1194 public void clear() {
1187 1195 while (pollFirst() != null)
1188 1196 ;
1189 1197 }
1190 1198
1191 1199 /**
1192 1200 * Returns an array containing all of the elements in this deque, in
1193 1201 * proper sequence (from first to last element).
1194 1202 *
1195 1203 * <p>The returned array will be "safe" in that no references to it are
1196 1204 * maintained by this deque. (In other words, this method must allocate
1197 1205 * a new array). The caller is thus free to modify the returned array.
1198 1206 *
1199 1207 * <p>This method acts as bridge between array-based and collection-based
1200 1208 * APIs.
1201 1209 *
1202 1210 * @return an array containing all of the elements in this deque
1203 1211 */
1204 1212 public Object[] toArray() {
1205 1213 return toArrayList().toArray();
1206 1214 }
1207 1215
1208 1216 /**
1209 1217 * Returns an array containing all of the elements in this deque,
1210 1218 * in proper sequence (from first to last element); the runtime
1211 1219 * type of the returned array is that of the specified array. If
1212 1220 * the deque fits in the specified array, it is returned therein.
1213 1221 * Otherwise, a new array is allocated with the runtime type of
1214 1222 * the specified array and the size of this deque.
1215 1223 *
1216 1224 * <p>If this deque fits in the specified array with room to spare
1217 1225 * (i.e., the array has more elements than this deque), the element in
1218 1226 * the array immediately following the end of the deque is set to
1219 1227 * {@code null}.
1220 1228 *
1221 1229 * <p>Like the {@link #toArray()} method, this method acts as
1222 1230 * bridge between array-based and collection-based APIs. Further,
1223 1231 * this method allows precise control over the runtime type of the
1224 1232 * output array, and may, under certain circumstances, be used to
1225 1233 * save allocation costs.
1226 1234 *
1227 1235 * <p>Suppose {@code x} is a deque known to contain only strings.
1228 1236 * The following code can be used to dump the deque into a newly
1229 1237 * allocated array of {@code String}:
1230 1238 *
1231 1239 * <pre>
1232 1240 * String[] y = x.toArray(new String[0]);</pre>
1233 1241 *
1234 1242 * Note that {@code toArray(new Object[0])} is identical in function to
1235 1243 * {@code toArray()}.
1236 1244 *
1237 1245 * @param a the array into which the elements of the deque are to
1238 1246 * be stored, if it is big enough; otherwise, a new array of the
1239 1247 * same runtime type is allocated for this purpose
1240 1248 * @return an array containing all of the elements in this deque
1241 1249 * @throws ArrayStoreException if the runtime type of the specified array
1242 1250 * is not a supertype of the runtime type of every element in
1243 1251 * this deque
↓ open down ↓ |
65 lines elided |
↑ open up ↑ |
1244 1252 * @throws NullPointerException if the specified array is null
1245 1253 */
1246 1254 public <T> T[] toArray(T[] a) {
1247 1255 return toArrayList().toArray(a);
1248 1256 }
1249 1257
1250 1258 /**
1251 1259 * Returns an iterator over the elements in this deque in proper sequence.
1252 1260 * The elements will be returned in order from first (head) to last (tail).
1253 1261 *
1254 - * <p>The returned {@code Iterator} is a "weakly consistent" iterator that
1262 + * <p>The returned iterator is a "weakly consistent" iterator that
1255 1263 * will never throw {@link java.util.ConcurrentModificationException
1256 - * ConcurrentModificationException},
1257 - * and guarantees to traverse elements as they existed upon
1258 - * construction of the iterator, and may (but is not guaranteed to)
1259 - * reflect any modifications subsequent to construction.
1264 + * ConcurrentModificationException}, and guarantees to traverse
1265 + * elements as they existed upon construction of the iterator, and
1266 + * may (but is not guaranteed to) reflect any modifications
1267 + * subsequent to construction.
1260 1268 *
1261 1269 * @return an iterator over the elements in this deque in proper sequence
1262 1270 */
1263 1271 public Iterator<E> iterator() {
1264 1272 return new Itr();
1265 1273 }
1266 1274
1267 1275 /**
1268 1276 * Returns an iterator over the elements in this deque in reverse
1269 1277 * sequential order. The elements will be returned in order from
1270 1278 * last (tail) to first (head).
1271 1279 *
1272 - * <p>The returned {@code Iterator} is a "weakly consistent" iterator that
1280 + * <p>The returned iterator is a "weakly consistent" iterator that
1273 1281 * will never throw {@link java.util.ConcurrentModificationException
1274 - * ConcurrentModificationException},
1275 - * and guarantees to traverse elements as they existed upon
1276 - * construction of the iterator, and may (but is not guaranteed to)
1277 - * reflect any modifications subsequent to construction.
1282 + * ConcurrentModificationException}, and guarantees to traverse
1283 + * elements as they existed upon construction of the iterator, and
1284 + * may (but is not guaranteed to) reflect any modifications
1285 + * subsequent to construction.
1278 1286 *
1279 1287 * @return an iterator over the elements in this deque in reverse order
1280 1288 */
1281 1289 public Iterator<E> descendingIterator() {
1282 1290 return new DescendingItr();
1283 1291 }
1284 1292
1285 1293 private abstract class AbstractItr implements Iterator<E> {
1286 1294 /**
1287 1295 * Next node to return item for.
1288 1296 */
1289 1297 private Node<E> nextNode;
1290 1298
1291 1299 /**
1292 1300 * nextItem holds on to item fields because once we claim
1293 1301 * that an element exists in hasNext(), we must return it in
1294 1302 * the following next() call even if it was in the process of
1295 1303 * being removed when hasNext() was called.
1296 1304 */
1297 1305 private E nextItem;
1298 1306
1299 1307 /**
1300 1308 * Node returned by most recent call to next. Needed by remove.
1301 1309 * Reset to null if this element is deleted by a call to remove.
1302 1310 */
1303 1311 private Node<E> lastRet;
1304 1312
1305 1313 abstract Node<E> startNode();
1306 1314 abstract Node<E> nextNode(Node<E> p);
1307 1315
1308 1316 AbstractItr() {
1309 1317 advance();
1310 1318 }
1311 1319
1312 1320 /**
1313 1321 * Sets nextNode and nextItem to next valid node, or to null
1314 1322 * if no such.
1315 1323 */
1316 1324 private void advance() {
1317 1325 lastRet = nextNode;
1318 1326
1319 1327 Node<E> p = (nextNode == null) ? startNode() : nextNode(nextNode);
1320 1328 for (;; p = nextNode(p)) {
1321 1329 if (p == null) {
1322 1330 // p might be active end or TERMINATOR node; both are OK
1323 1331 nextNode = null;
1324 1332 nextItem = null;
1325 1333 break;
1326 1334 }
1327 1335 E item = p.item;
1328 1336 if (item != null) {
1329 1337 nextNode = p;
1330 1338 nextItem = item;
1331 1339 break;
1332 1340 }
1333 1341 }
1334 1342 }
1335 1343
1336 1344 public boolean hasNext() {
1337 1345 return nextItem != null;
1338 1346 }
1339 1347
1340 1348 public E next() {
1341 1349 E item = nextItem;
1342 1350 if (item == null) throw new NoSuchElementException();
1343 1351 advance();
1344 1352 return item;
1345 1353 }
1346 1354
1347 1355 public void remove() {
1348 1356 Node<E> l = lastRet;
1349 1357 if (l == null) throw new IllegalStateException();
1350 1358 l.item = null;
1351 1359 unlink(l);
1352 1360 lastRet = null;
1353 1361 }
1354 1362 }
1355 1363
1356 1364 /** Forward iterator */
1357 1365 private class Itr extends AbstractItr {
1358 1366 Node<E> startNode() { return first(); }
1359 1367 Node<E> nextNode(Node<E> p) { return succ(p); }
1360 1368 }
1361 1369
1362 1370 /** Descending iterator */
1363 1371 private class DescendingItr extends AbstractItr {
1364 1372 Node<E> startNode() { return last(); }
1365 1373 Node<E> nextNode(Node<E> p) { return pred(p); }
1366 1374 }
1367 1375
1368 1376 /**
1369 1377 * Saves the state to a stream (that is, serializes it).
1370 1378 *
1371 1379 * @serialData All of the elements (each an {@code E}) in
1372 1380 * the proper order, followed by a null
1373 1381 * @param s the stream
1374 1382 */
1375 1383 private void writeObject(java.io.ObjectOutputStream s)
1376 1384 throws java.io.IOException {
1377 1385
1378 1386 // Write out any hidden stuff
1379 1387 s.defaultWriteObject();
1380 1388
1381 1389 // Write out all elements in the proper order.
1382 1390 for (Node<E> p = first(); p != null; p = succ(p)) {
1383 1391 E item = p.item;
1384 1392 if (item != null)
1385 1393 s.writeObject(item);
1386 1394 }
1387 1395
1388 1396 // Use trailing null as sentinel
1389 1397 s.writeObject(null);
1390 1398 }
1391 1399
1392 1400 /**
1393 1401 * Reconstitutes the instance from a stream (that is, deserializes it).
1394 1402 * @param s the stream
1395 1403 */
1396 1404 private void readObject(java.io.ObjectInputStream s)
1397 1405 throws java.io.IOException, ClassNotFoundException {
1398 1406 s.defaultReadObject();
1399 1407
1400 1408 // Read in elements until trailing null sentinel found
1401 1409 Node<E> h = null, t = null;
1402 1410 Object item;
1403 1411 while ((item = s.readObject()) != null) {
1404 1412 @SuppressWarnings("unchecked")
1405 1413 Node<E> newNode = new Node<E>((E) item);
1406 1414 if (h == null)
1407 1415 h = t = newNode;
1408 1416 else {
1409 1417 t.lazySetNext(newNode);
1410 1418 newNode.lazySetPrev(t);
1411 1419 t = newNode;
1412 1420 }
1413 1421 }
1414 1422 initHeadTail(h, t);
1415 1423 }
1416 1424
1417 1425 // Unsafe mechanics
1418 1426
1419 1427 private static final sun.misc.Unsafe UNSAFE =
1420 1428 sun.misc.Unsafe.getUnsafe();
1421 1429 private static final long headOffset =
1422 1430 objectFieldOffset(UNSAFE, "head", ConcurrentLinkedDeque.class);
1423 1431 private static final long tailOffset =
1424 1432 objectFieldOffset(UNSAFE, "tail", ConcurrentLinkedDeque.class);
1425 1433
1426 1434 private boolean casHead(Node<E> cmp, Node<E> val) {
1427 1435 return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
1428 1436 }
1429 1437
1430 1438 private boolean casTail(Node<E> cmp, Node<E> val) {
1431 1439 return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val);
1432 1440 }
1433 1441
1434 1442 static long objectFieldOffset(sun.misc.Unsafe UNSAFE,
1435 1443 String field, Class<?> klazz) {
1436 1444 try {
1437 1445 return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field));
1438 1446 } catch (NoSuchFieldException e) {
1439 1447 // Convert Exception to corresponding Error
1440 1448 NoSuchFieldError error = new NoSuchFieldError(field);
1441 1449 error.initCause(e);
1442 1450 throw error;
1443 1451 }
1444 1452 }
1445 1453 }
↓ open down ↓ |
158 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX