1 |
/* |
2 |
* Written by Doug Lea with assistance from members of JCP JSR-166 |
3 |
* Expert Group and released to the public domain, as explained at |
4 |
* http://creativecommons.org/publicdomain/zero/1.0/ |
5 |
*/ |
6 |
|
7 |
package jsr166x; |
8 |
|
9 |
import java.util.AbstractCollection; |
10 |
import java.util.ArrayList; |
11 |
import java.util.Collection; |
12 |
import jsr166x.Deque; |
13 |
//import java.util.Deque; |
14 |
import java.util.Iterator; |
15 |
import java.util.ConcurrentModificationException; |
16 |
import java.util.NoSuchElementException; |
17 |
import java.util.concurrent.atomic.AtomicReference; |
18 |
|
19 |
/** |
20 |
* A concurrent linked-list implementation of a {@link Deque} |
21 |
* (double-ended queue). Concurrent insertion, removal, and access |
22 |
* operations execute safely across multiple threads. Iterators are |
23 |
* <i>weakly consistent</i>, returning elements reflecting the state |
24 |
* of the deque at some point at or since the creation of the |
25 |
* iterator. They do <em>not</em> throw {@link |
26 |
* ConcurrentModificationException}, and may proceed concurrently with |
27 |
* other operations. |
28 |
* |
29 |
* <p>This class and its iterators implement all of the |
30 |
* <em>optional</em> methods of the {@link Collection} and {@link |
31 |
* Iterator} interfaces. Like most other concurrent collection |
32 |
* implementations, this class does not permit the use of |
33 |
* {@code null} elements. because some null arguments and return |
34 |
* values cannot be reliably distinguished from the absence of |
35 |
* elements. Arbitrarily, the {@link Collection#remove} method is |
36 |
* mapped to {@code removeFirstOccurrence}, and {@link |
37 |
* Collection#add} is mapped to {@code addLast}. |
38 |
* |
39 |
* <p>Beware that, unlike in most collections, the {@code size} |
40 |
* method is <em>NOT</em> a constant-time operation. Because of the |
41 |
* asynchronous nature of these deques, determining the current number |
42 |
* of elements requires a traversal of the elements. |
43 |
* |
44 |
* <p>This class is {@code Serializable}, but relies on default |
45 |
* serialization mechanisms. Usually, it is a better idea for any |
46 |
* serializable class using a {@code ConcurrentLinkedDeque} to instead |
47 |
* serialize a snapshot of the elements obtained by method |
48 |
* {@code toArray}. |
49 |
* |
50 |
* @author Doug Lea |
51 |
* @param <E> the type of elements held in this collection |
52 |
*/ |
53 |
|
54 |
public class ConcurrentLinkedDeque<E> |
55 |
extends AbstractCollection<E> |
56 |
implements Deque<E>, java.io.Serializable { |
57 |
|
58 |
/* |
59 |
* This is an adaptation of an algorithm described in Paul |
60 |
* Martin's "A Practical Lock-Free Doubly-Linked List". Sun Labs |
61 |
* Tech report. The basic idea is to primarily rely on |
62 |
* next-pointers to ensure consistency. Prev-pointers are in part |
63 |
* optimistic, reconstructed using forward pointers as needed. |
64 |
* The main forward list uses a variant of HM-list algorithm |
65 |
* similar to the one used in ConcurrentSkipListMap class, but a |
66 |
* little simpler. It is also basically similar to the approach |
67 |
* in Edya Ladan-Mozes and Nir Shavit "An Optimistic Approach to |
68 |
* Lock-Free FIFO Queues" in DISC04. |
69 |
* |
70 |
* Quoting a summary in Paul Martin's tech report: |
71 |
* |
72 |
* All cleanups work to maintain these invariants: |
73 |
* (1) forward pointers are the ground truth. |
74 |
* (2) forward pointers to dead nodes can be improved by swinging them |
75 |
* further forward around the dead node. |
76 |
* (2.1) forward pointers are still correct when pointing to dead |
77 |
* nodes, and forward pointers from dead nodes are left |
78 |
* as they were when the node was deleted. |
79 |
* (2.2) multiple dead nodes may point forward to the same node. |
80 |
* (3) backward pointers were correct when they were installed |
81 |
* (3.1) backward pointers are correct when pointing to any |
82 |
* node which points forward to them, but since more than |
83 |
* one forward pointer may point to them, the live one is best. |
84 |
* (4) backward pointers that are out of date due to deletion |
85 |
* point to a deleted node, and need to point further back until |
86 |
* they point to the live node that points to their source. |
87 |
* (5) backward pointers that are out of date due to insertion |
88 |
* point too far backwards, so shortening their scope (by searching |
89 |
* forward) fixes them. |
90 |
* (6) backward pointers from a dead node cannot be "improved" since |
91 |
* there may be no live node pointing forward to their origin. |
92 |
* (However, it does no harm to try to improve them while |
93 |
* racing with a deletion.) |
94 |
* |
95 |
* |
96 |
* Notation guide for local variables |
97 |
* n, b, f : a node, its predecessor, and successor |
98 |
* s : some other successor |
99 |
*/ |
100 |
|
101 |
/** |
102 |
* Linked Nodes. As a minor efficiency hack, this class |
103 |
* opportunistically inherits from AtomicReference, with the |
104 |
* atomic ref used as the "next" link. |
105 |
* |
106 |
* Nodes are in doubly-linked lists. There are three |
107 |
* kinds of special nodes, distinguished by: |
108 |
* * The list header has a null prev link. |
109 |
* * The list trailer has a null next link. |
110 |
* * A deletion marker has a prev link pointing to itself. |
111 |
* All three kinds of special nodes have null element fields. |
112 |
* |
113 |
* Regular nodes have non-null element, next, and prev fields. To |
114 |
* avoid visible inconsistencies when deletions overlap element |
115 |
* replacement, replacements are done by replacing the node, not |
116 |
* just setting the element. |
117 |
* |
118 |
* Nodes can be traversed by read-only ConcurrentLinkedDeque class |
119 |
* operations just by following raw next pointers, so long as they |
120 |
* ignore any special nodes seen along the way. (This is automated |
121 |
* in method forward.) However, traversal using prev pointers is |
122 |
* not guaranteed to see all live nodes since a prev pointer of a |
123 |
* deleted node can become unrecoverably stale. |
124 |
*/ |
125 |
static final class Node<E> extends AtomicReference<Node<E>> { |
126 |
private volatile Node<E> prev; |
127 |
final E element; |
128 |
private static final long serialVersionUID = 876323262645176354L; |
129 |
|
130 |
/** Creates a node with given contents. */ |
131 |
Node(E element, Node<E> next, Node<E> prev) { |
132 |
super(next); |
133 |
this.prev = prev; |
134 |
this.element = element; |
135 |
} |
136 |
|
137 |
/** Creates a marker node with given successor. */ |
138 |
Node(Node<E> next) { |
139 |
super(next); |
140 |
this.prev = this; |
141 |
this.element = null; |
142 |
} |
143 |
|
144 |
/** |
145 |
* Gets next link (which is actually the value held |
146 |
* as atomic reference). |
147 |
*/ |
148 |
private Node<E> getNext() { |
149 |
return get(); |
150 |
} |
151 |
|
152 |
/** |
153 |
* Sets next link. |
154 |
* @param n the next node |
155 |
*/ |
156 |
void setNext(Node<E> n) { |
157 |
set(n); |
158 |
} |
159 |
|
160 |
/** |
161 |
* compareAndSet next link |
162 |
*/ |
163 |
private boolean casNext(Node<E> cmp, Node<E> val) { |
164 |
return compareAndSet(cmp, val); |
165 |
} |
166 |
|
167 |
/** |
168 |
* Gets prev link. |
169 |
*/ |
170 |
private Node<E> getPrev() { |
171 |
return prev; |
172 |
} |
173 |
|
174 |
/** |
175 |
* Sets prev link. |
176 |
* @param b the previous node |
177 |
*/ |
178 |
void setPrev(Node<E> b) { |
179 |
prev = b; |
180 |
} |
181 |
|
182 |
/** |
183 |
* Returns true if this is a header, trailer, or marker node. |
184 |
*/ |
185 |
boolean isSpecial() { |
186 |
return element == null; |
187 |
} |
188 |
|
189 |
/** |
190 |
* Returns true if this is a trailer node. |
191 |
*/ |
192 |
boolean isTrailer() { |
193 |
return getNext() == null; |
194 |
} |
195 |
|
196 |
/** |
197 |
* Returns true if this is a header node. |
198 |
*/ |
199 |
boolean isHeader() { |
200 |
return getPrev() == null; |
201 |
} |
202 |
|
203 |
/** |
204 |
* Returns true if this is a marker node. |
205 |
*/ |
206 |
boolean isMarker() { |
207 |
return getPrev() == this; |
208 |
} |
209 |
|
210 |
/** |
211 |
* Returns true if this node is followed by a marker node, |
212 |
* meaning that this node is deleted. |
213 |
* |
214 |
* @return true if this node is deleted |
215 |
*/ |
216 |
boolean isDeleted() { |
217 |
Node<E> f = getNext(); |
218 |
return f != null && f.isMarker(); |
219 |
} |
220 |
|
221 |
/** |
222 |
* Returns next node, ignoring deletion marker. |
223 |
*/ |
224 |
private Node<E> nextNonmarker() { |
225 |
Node<E> f = getNext(); |
226 |
return (f == null || !f.isMarker()) ? f : f.getNext(); |
227 |
} |
228 |
|
229 |
/** |
230 |
* Returns the next non-deleted node, swinging next pointer |
231 |
* around any encountered deleted nodes, and also patching up |
232 |
* successor's prev link to point back to this. Returns |
233 |
* null if this node is trailer so has no successor. |
234 |
* |
235 |
* @return successor, or null if no such |
236 |
*/ |
237 |
Node<E> successor() { |
238 |
Node<E> f = nextNonmarker(); |
239 |
for (;;) { |
240 |
if (f == null) |
241 |
return null; |
242 |
if (!f.isDeleted()) { |
243 |
if (f.getPrev() != this && !isDeleted()) |
244 |
f.setPrev(this); // relink f's prev |
245 |
return f; |
246 |
} |
247 |
Node<E> s = f.nextNonmarker(); |
248 |
if (f == getNext()) |
249 |
casNext(f, s); // unlink f |
250 |
f = s; |
251 |
} |
252 |
} |
253 |
|
254 |
/** |
255 |
* Returns the apparent predecessor of target by searching |
256 |
* forward for it, starting at this node, patching up pointers |
257 |
* while traversing. Used by predecessor(). |
258 |
* |
259 |
* @return target's predecessor, or null if not found |
260 |
*/ |
261 |
private Node<E> findPredecessorOf(Node<E> target) { |
262 |
Node<E> n = this; |
263 |
for (;;) { |
264 |
Node<E> f = n.successor(); |
265 |
if (f == target) |
266 |
return n; |
267 |
if (f == null) |
268 |
return null; |
269 |
n = f; |
270 |
} |
271 |
} |
272 |
|
273 |
/** |
274 |
* Returns the previous non-deleted node, patching up pointers |
275 |
* as needed. Returns null if this node is header so has no |
276 |
* successor. May also return null if this node is deleted, |
277 |
* so doesn't have a distinct predecessor. |
278 |
* |
279 |
* @return predecessor or null if not found |
280 |
*/ |
281 |
Node<E> predecessor() { |
282 |
Node<E> n = this; |
283 |
for (;;) { |
284 |
Node<E> b = n.getPrev(); |
285 |
if (b == null) |
286 |
return n.findPredecessorOf(this); |
287 |
Node<E> s = b.getNext(); |
288 |
if (s == this) |
289 |
return b; |
290 |
if (s == null || !s.isMarker()) { |
291 |
Node<E> p = b.findPredecessorOf(this); |
292 |
if (p != null) |
293 |
return p; |
294 |
} |
295 |
n = b; |
296 |
} |
297 |
} |
298 |
|
299 |
/** |
300 |
* Returns the next node containing a nondeleted user element. |
301 |
* Use for forward list traversal. |
302 |
* |
303 |
* @return successor, or null if no such |
304 |
*/ |
305 |
Node<E> forward() { |
306 |
Node<E> f = successor(); |
307 |
return (f == null || f.isSpecial()) ? null : f; |
308 |
} |
309 |
|
310 |
/** |
311 |
* Returns previous node containing a nondeleted user element, if |
312 |
* possible. Use for backward list traversal, but beware that |
313 |
* if this method is called from a deleted node, it might not |
314 |
* be able to determine a usable predecessor. |
315 |
* |
316 |
* @return predecessor, or null if no such could be found |
317 |
*/ |
318 |
Node<E> back() { |
319 |
Node<E> f = predecessor(); |
320 |
return (f == null || f.isSpecial()) ? null : f; |
321 |
} |
322 |
|
323 |
/** |
324 |
* Tries to insert a node holding element as successor, failing |
325 |
* if this node is deleted. |
326 |
* |
327 |
* @param element the element |
328 |
* @return the new node, or null on failure |
329 |
*/ |
330 |
Node<E> append(E element) { |
331 |
for (;;) { |
332 |
Node<E> f = getNext(); |
333 |
if (f == null || f.isMarker()) |
334 |
return null; |
335 |
Node<E> x = new Node<E>(element, f, this); |
336 |
if (casNext(f, x)) { |
337 |
f.setPrev(x); // optimistically link |
338 |
return x; |
339 |
} |
340 |
} |
341 |
} |
342 |
|
343 |
/** |
344 |
* Tries to insert a node holding element as predecessor, failing |
345 |
* if no live predecessor can be found to link to. |
346 |
* |
347 |
* @param element the element |
348 |
* @return the new node, or null on failure |
349 |
*/ |
350 |
Node<E> prepend(E element) { |
351 |
for (;;) { |
352 |
Node<E> b = predecessor(); |
353 |
if (b == null) |
354 |
return null; |
355 |
Node<E> x = new Node<E>(element, this, b); |
356 |
if (b.casNext(this, x)) { |
357 |
setPrev(x); // optimistically link |
358 |
return x; |
359 |
} |
360 |
} |
361 |
} |
362 |
|
363 |
/** |
364 |
* Tries to mark this node as deleted, failing if already |
365 |
* deleted or if this node is header or trailer. |
366 |
* |
367 |
* @return true if successful |
368 |
*/ |
369 |
boolean delete() { |
370 |
Node<E> b = getPrev(); |
371 |
Node<E> f = getNext(); |
372 |
if (b != null && f != null && !f.isMarker() && |
373 |
casNext(f, new Node<E>(f))) { |
374 |
if (b.casNext(this, f)) |
375 |
f.setPrev(b); |
376 |
return true; |
377 |
} |
378 |
return false; |
379 |
} |
380 |
|
381 |
/** |
382 |
* Tries to insert a node holding element to replace this node. |
383 |
* failing if already deleted. A currently unused proof of |
384 |
* concept that demonstrates atomic node content replacement. |
385 |
* |
386 |
* Although this implementation ensures that exactly one |
387 |
* version of this Node is alive at a given time, it fails to |
388 |
* maintain atomicity in the sense that iterators may |
389 |
* encounter both the old and new versions of the element. |
390 |
* |
391 |
* @param newElement the new element |
392 |
* @return the new node, or null on failure |
393 |
*/ |
394 |
Node<E> replace(E newElement) { |
395 |
for (;;) { |
396 |
Node<E> b = getPrev(); |
397 |
Node<E> f = getNext(); |
398 |
if (b == null || f == null || f.isMarker()) |
399 |
return null; |
400 |
Node<E> x = new Node<E>(newElement, f, b); |
401 |
if (casNext(f, new Node<E>(x))) { |
402 |
b.successor(); // to relink b |
403 |
x.successor(); // to relink f |
404 |
return x; |
405 |
} |
406 |
} |
407 |
} |
408 |
} |
409 |
|
410 |
// Minor convenience utilities |
411 |
|
412 |
/** |
413 |
* Returns true if given reference is non-null and isn't a header, |
414 |
* trailer, or marker. |
415 |
* |
416 |
* @param n (possibly null) node |
417 |
* @return true if n exists as a user node |
418 |
*/ |
419 |
private static boolean usable(Node<?> n) { |
420 |
return n != null && !n.isSpecial(); |
421 |
} |
422 |
|
423 |
/** |
424 |
* Throws NullPointerException if argument is null. |
425 |
* |
426 |
* @param v the element |
427 |
*/ |
428 |
private static void checkNotNull(Object v) { |
429 |
if (v == null) |
430 |
throw new NullPointerException(); |
431 |
} |
432 |
|
433 |
/** |
434 |
* Returns element unless it is null, in which case throws |
435 |
* NoSuchElementException. |
436 |
* |
437 |
* @param v the element |
438 |
* @return the element |
439 |
*/ |
440 |
private E screenNullResult(E v) { |
441 |
if (v == null) |
442 |
throw new NoSuchElementException(); |
443 |
return v; |
444 |
} |
445 |
|
446 |
/** |
447 |
* Creates an array list and fills it with elements of this list. |
448 |
* Used by toArray. |
449 |
* |
450 |
* @return the arrayList |
451 |
*/ |
452 |
private ArrayList<E> toArrayList() { |
453 |
ArrayList<E> c = new ArrayList<E>(); |
454 |
for (Node<E> n = header.forward(); n != null; n = n.forward()) |
455 |
c.add(n.element); |
456 |
return c; |
457 |
} |
458 |
|
459 |
// Fields and constructors |
460 |
|
461 |
private static final long serialVersionUID = 876323262645176354L; |
462 |
|
463 |
/** |
464 |
* List header. First usable node is at header.forward(). |
465 |
*/ |
466 |
private final Node<E> header; |
467 |
|
468 |
/** |
469 |
* List trailer. Last usable node is at trailer.back(). |
470 |
*/ |
471 |
private final Node<E> trailer; |
472 |
|
473 |
/** |
474 |
* Constructs an empty deque. |
475 |
*/ |
476 |
public ConcurrentLinkedDeque() { |
477 |
Node<E> h = new Node<E>(null, null, null); |
478 |
Node<E> t = new Node<E>(null, null, h); |
479 |
h.setNext(t); |
480 |
header = h; |
481 |
trailer = t; |
482 |
} |
483 |
|
484 |
/** |
485 |
* Constructs a deque initially containing the elements of |
486 |
* the given collection, added in traversal order of the |
487 |
* collection's iterator. |
488 |
* |
489 |
* @param c the collection of elements to initially contain |
490 |
* @throws NullPointerException if the specified collection or any |
491 |
* of its elements are null |
492 |
*/ |
493 |
public ConcurrentLinkedDeque(Collection<? extends E> c) { |
494 |
this(); |
495 |
addAll(c); |
496 |
} |
497 |
|
498 |
/** |
499 |
* Inserts the specified element at the front of this deque. |
500 |
* |
501 |
* @throws NullPointerException {@inheritDoc} |
502 |
*/ |
503 |
public void addFirst(E e) { |
504 |
checkNotNull(e); |
505 |
while (header.append(e) == null) |
506 |
; |
507 |
} |
508 |
|
509 |
/** |
510 |
* Inserts the specified element at the end of this deque. |
511 |
* This is identical in function to the {@code add} method. |
512 |
* |
513 |
* @throws NullPointerException {@inheritDoc} |
514 |
*/ |
515 |
public void addLast(E e) { |
516 |
checkNotNull(e); |
517 |
while (trailer.prepend(e) == null) |
518 |
; |
519 |
} |
520 |
|
521 |
/** |
522 |
* Inserts the specified element at the front of this deque. |
523 |
* |
524 |
* @return {@code true} always |
525 |
* @throws NullPointerException {@inheritDoc} |
526 |
*/ |
527 |
public boolean offerFirst(E e) { |
528 |
addFirst(e); |
529 |
return true; |
530 |
} |
531 |
|
532 |
/** |
533 |
* Inserts the specified element at the end of this deque. |
534 |
* |
535 |
* <p>This method is equivalent to {@link #add}. |
536 |
* |
537 |
* @return {@code true} always |
538 |
* @throws NullPointerException {@inheritDoc} |
539 |
*/ |
540 |
public boolean offerLast(E e) { |
541 |
addLast(e); |
542 |
return true; |
543 |
} |
544 |
|
545 |
public E peekFirst() { |
546 |
Node<E> n = header.successor(); |
547 |
return (n == null) ? null : n.element; |
548 |
} |
549 |
|
550 |
public E peekLast() { |
551 |
Node<E> n = trailer.predecessor(); |
552 |
return (n == null) ? null : n.element; |
553 |
} |
554 |
|
555 |
/** |
556 |
* @throws NoSuchElementException {@inheritDoc} |
557 |
*/ |
558 |
public E getFirst() { |
559 |
return screenNullResult(peekFirst()); |
560 |
} |
561 |
|
562 |
/** |
563 |
* @throws NoSuchElementException {@inheritDoc} |
564 |
*/ |
565 |
public E getLast() { |
566 |
return screenNullResult(peekLast()); |
567 |
} |
568 |
|
569 |
public E pollFirst() { |
570 |
for (;;) { |
571 |
Node<E> n = header.successor(); |
572 |
if (!usable(n)) |
573 |
return null; |
574 |
if (n.delete()) |
575 |
return n.element; |
576 |
} |
577 |
} |
578 |
|
579 |
public E pollLast() { |
580 |
for (;;) { |
581 |
Node<E> n = trailer.predecessor(); |
582 |
if (!usable(n)) |
583 |
return null; |
584 |
if (n.delete()) |
585 |
return n.element; |
586 |
} |
587 |
} |
588 |
|
589 |
/** |
590 |
* @throws NoSuchElementException {@inheritDoc} |
591 |
*/ |
592 |
public E removeFirst() { |
593 |
return screenNullResult(pollFirst()); |
594 |
} |
595 |
|
596 |
/** |
597 |
* @throws NoSuchElementException {@inheritDoc} |
598 |
*/ |
599 |
public E removeLast() { |
600 |
return screenNullResult(pollLast()); |
601 |
} |
602 |
|
603 |
// *** Queue and stack methods *** |
604 |
|
605 |
/** |
606 |
* Inserts the specified element at the tail of this queue. |
607 |
* |
608 |
* @return {@code true} (as specified by {@link Queue#offer}) |
609 |
* @throws NullPointerException if the specified element is null |
610 |
*/ |
611 |
public boolean offer(E e) { |
612 |
return offerLast(e); |
613 |
} |
614 |
|
615 |
/** |
616 |
* Inserts the specified element at the tail of this deque. |
617 |
* |
618 |
* @return {@code true} (as specified by {@link Collection#add}) |
619 |
* @throws NullPointerException if the specified element is null |
620 |
*/ |
621 |
public boolean add(E e) { |
622 |
return offerLast(e); |
623 |
} |
624 |
|
625 |
public E poll() { return pollFirst(); } |
626 |
public E remove() { return removeFirst(); } |
627 |
public E peek() { return peekFirst(); } |
628 |
public E element() { return getFirst(); } |
629 |
public void push(E e) { addFirst(e); } |
630 |
public E pop() { return removeFirst(); } |
631 |
|
632 |
/** |
633 |
* Removes the first element {@code e} such that |
634 |
* {@code o.equals(e)}, if such an element exists in this deque. |
635 |
* If the deque does not contain the element, it is unchanged. |
636 |
* |
637 |
* @param o element to be removed from this deque, if present |
638 |
* @return {@code true} if the deque contained the specified element |
639 |
* @throws NullPointerException if the specified element is {@code null} |
640 |
*/ |
641 |
public boolean removeFirstOccurrence(Object o) { |
642 |
checkNotNull(o); |
643 |
for (;;) { |
644 |
Node<E> n = header.forward(); |
645 |
for (;;) { |
646 |
if (n == null) |
647 |
return false; |
648 |
if (o.equals(n.element)) { |
649 |
if (n.delete()) |
650 |
return true; |
651 |
else |
652 |
break; // restart if interference |
653 |
} |
654 |
n = n.forward(); |
655 |
} |
656 |
} |
657 |
} |
658 |
|
659 |
/** |
660 |
* Removes the last element {@code e} such that |
661 |
* {@code o.equals(e)}, if such an element exists in this deque. |
662 |
* If the deque does not contain the element, it is unchanged. |
663 |
* |
664 |
* @param o element to be removed from this deque, if present |
665 |
* @return {@code true} if the deque contained the specified element |
666 |
* @throws NullPointerException if the specified element is {@code null} |
667 |
*/ |
668 |
public boolean removeLastOccurrence(Object o) { |
669 |
checkNotNull(o); |
670 |
for (;;) { |
671 |
Node<E> s = trailer; |
672 |
for (;;) { |
673 |
Node<E> n = s.back(); |
674 |
if (s.isDeleted() || (n != null && n.successor() != s)) |
675 |
break; // restart if pred link is suspect. |
676 |
if (n == null) |
677 |
return false; |
678 |
if (o.equals(n.element)) { |
679 |
if (n.delete()) |
680 |
return true; |
681 |
else |
682 |
break; // restart if interference |
683 |
} |
684 |
s = n; |
685 |
} |
686 |
} |
687 |
} |
688 |
|
689 |
/** |
690 |
* Returns {@code true} if this deque contains at least one |
691 |
* element {@code e} such that {@code o.equals(e)}. |
692 |
* |
693 |
* @param o element whose presence in this deque is to be tested |
694 |
* @return {@code true} if this deque contains the specified element |
695 |
*/ |
696 |
public boolean contains(Object o) { |
697 |
if (o == null) return false; |
698 |
for (Node<E> n = header.forward(); n != null; n = n.forward()) |
699 |
if (o.equals(n.element)) |
700 |
return true; |
701 |
return false; |
702 |
} |
703 |
|
704 |
/** |
705 |
* Returns {@code true} if this collection contains no elements. |
706 |
* |
707 |
* @return {@code true} if this collection contains no elements |
708 |
*/ |
709 |
public boolean isEmpty() { |
710 |
return !usable(header.successor()); |
711 |
} |
712 |
|
713 |
/** |
714 |
* Returns the number of elements in this deque. If this deque |
715 |
* contains more than {@code Integer.MAX_VALUE} elements, it |
716 |
* returns {@code Integer.MAX_VALUE}. |
717 |
* |
718 |
* <p>Beware that, unlike in most collections, this method is |
719 |
* <em>NOT</em> a constant-time operation. Because of the |
720 |
* asynchronous nature of these deques, determining the current |
721 |
* number of elements requires traversing them all to count them. |
722 |
* Additionally, it is possible for the size to change during |
723 |
* execution of this method, in which case the returned result |
724 |
* will be inaccurate. Thus, this method is typically not very |
725 |
* useful in concurrent applications. |
726 |
* |
727 |
* @return the number of elements in this deque |
728 |
*/ |
729 |
public int size() { |
730 |
long count = 0; |
731 |
for (Node<E> n = header.forward(); n != null; n = n.forward()) |
732 |
++count; |
733 |
return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) count; |
734 |
} |
735 |
|
736 |
/** |
737 |
* Removes the first element {@code e} such that |
738 |
* {@code o.equals(e)}, if such an element exists in this deque. |
739 |
* If the deque does not contain the element, it is unchanged. |
740 |
* |
741 |
* @param o element to be removed from this deque, if present |
742 |
* @return {@code true} if the deque contained the specified element |
743 |
* @throws NullPointerException if the specified element is {@code null} |
744 |
*/ |
745 |
public boolean remove(Object o) { |
746 |
return removeFirstOccurrence(o); |
747 |
} |
748 |
|
749 |
/** |
750 |
* Appends all of the elements in the specified collection to the end of |
751 |
* this deque, in the order that they are returned by the specified |
752 |
* collection's iterator. The behavior of this operation is undefined if |
753 |
* the specified collection is modified while the operation is in |
754 |
* progress. (This implies that the behavior of this call is undefined if |
755 |
* the specified Collection is this deque, and this deque is nonempty.) |
756 |
* |
757 |
* @param c the elements to be inserted into this deque |
758 |
* @return {@code true} if this deque changed as a result of the call |
759 |
* @throws NullPointerException if {@code c} or any element within it |
760 |
* is {@code null} |
761 |
*/ |
762 |
public boolean addAll(Collection<? extends E> c) { |
763 |
Iterator<? extends E> it = c.iterator(); |
764 |
if (!it.hasNext()) |
765 |
return false; |
766 |
do { |
767 |
addLast(it.next()); |
768 |
} while (it.hasNext()); |
769 |
return true; |
770 |
} |
771 |
|
772 |
/** |
773 |
* Removes all of the elements from this deque. |
774 |
*/ |
775 |
public void clear() { |
776 |
while (pollFirst() != null) |
777 |
; |
778 |
} |
779 |
|
780 |
/** |
781 |
* Returns an array containing all of the elements in this deque, in |
782 |
* proper sequence (from first to last element). |
783 |
* |
784 |
* <p>The returned array will be "safe" in that no references to it are |
785 |
* maintained by this deque. (In other words, this method must allocate |
786 |
* a new array). The caller is thus free to modify the returned array. |
787 |
* |
788 |
* <p>This method acts as bridge between array-based and collection-based |
789 |
* APIs. |
790 |
* |
791 |
* @return an array containing all of the elements in this deque |
792 |
*/ |
793 |
public Object[] toArray() { |
794 |
return toArrayList().toArray(); |
795 |
} |
796 |
|
797 |
/** |
798 |
* Returns an array containing all of the elements in this deque, |
799 |
* in proper sequence (from first to last element); the runtime |
800 |
* type of the returned array is that of the specified array. If |
801 |
* the deque fits in the specified array, it is returned therein. |
802 |
* Otherwise, a new array is allocated with the runtime type of |
803 |
* the specified array and the size of this deque. |
804 |
* |
805 |
* <p>If this deque fits in the specified array with room to spare |
806 |
* (i.e., the array has more elements than this deque), the element in |
807 |
* the array immediately following the end of the deque is set to |
808 |
* {@code null}. |
809 |
* |
810 |
* <p>Like the {@link #toArray()} method, this method acts as bridge between |
811 |
* array-based and collection-based APIs. Further, this method allows |
812 |
* precise control over the runtime type of the output array, and may, |
813 |
* under certain circumstances, be used to save allocation costs. |
814 |
* |
815 |
* <p>Suppose {@code x} is a deque known to contain only strings. |
816 |
* The following code can be used to dump the deque into a newly |
817 |
* allocated array of {@code String}: |
818 |
* |
819 |
* <pre> |
820 |
* String[] y = x.toArray(new String[0]);</pre> |
821 |
* |
822 |
* Note that {@code toArray(new Object[0])} is identical in function to |
823 |
* {@code toArray()}. |
824 |
* |
825 |
* @param a the array into which the elements of the deque are to |
826 |
* be stored, if it is big enough; otherwise, a new array of the |
827 |
* same runtime type is allocated for this purpose |
828 |
* @return an array containing all of the elements in this deque |
829 |
* @throws ArrayStoreException if the runtime type of the specified array |
830 |
* is not a supertype of the runtime type of every element in |
831 |
* this deque |
832 |
* @throws NullPointerException if the specified array is null |
833 |
*/ |
834 |
public <T> T[] toArray(T[] a) { |
835 |
return toArrayList().toArray(a); |
836 |
} |
837 |
|
838 |
/** |
839 |
* Returns an iterator over the elements in this deque in proper sequence. |
840 |
* The elements will be returned in order from first (head) to last (tail). |
841 |
* The returned {@code Iterator} is a "weakly consistent" iterator that |
842 |
* will never throw {@link java.util.ConcurrentModificationException |
843 |
* ConcurrentModificationException}, |
844 |
* and guarantees to traverse elements as they existed upon |
845 |
* construction of the iterator, and may (but is not guaranteed to) |
846 |
* reflect any modifications subsequent to construction. |
847 |
* |
848 |
* @return an iterator over the elements in this deque in proper sequence |
849 |
*/ |
850 |
public Iterator<E> iterator() { |
851 |
return new CLDIterator(); |
852 |
} |
853 |
|
854 |
final class CLDIterator implements Iterator<E> { |
855 |
Node<E> last; |
856 |
Node<E> next = header.forward(); |
857 |
|
858 |
public boolean hasNext() { |
859 |
return next != null; |
860 |
} |
861 |
|
862 |
public E next() { |
863 |
Node<E> l = last = next; |
864 |
if (l == null) |
865 |
throw new NoSuchElementException(); |
866 |
next = next.forward(); |
867 |
return l.element; |
868 |
} |
869 |
|
870 |
public void remove() { |
871 |
Node<E> l = last; |
872 |
if (l == null) |
873 |
throw new IllegalStateException(); |
874 |
while (!l.delete() && !l.isDeleted()) |
875 |
; |
876 |
} |
877 |
} |
878 |
|
879 |
/** |
880 |
* Not yet implemented. |
881 |
*/ |
882 |
public Iterator<E> descendingIterator() { |
883 |
throw new UnsupportedOperationException(); |
884 |
} |
885 |
} |