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 |
public class ConcurrentLinkedDeque<E> |
54 |
extends AbstractCollection<E> |
55 |
implements Deque<E>, java.io.Serializable { |
56 |
|
57 |
/* |
58 |
* This is an adaptation of an algorithm described in Paul |
59 |
* Martin's "A Practical Lock-Free Doubly-Linked List". Sun Labs |
60 |
* Tech report. The basic idea is to primarily rely on |
61 |
* next-pointers to ensure consistency. Prev-pointers are in part |
62 |
* optimistic, reconstructed using forward pointers as needed. |
63 |
* The main forward list uses a variant of HM-list algorithm |
64 |
* similar to the one used in ConcurrentSkipListMap class, but a |
65 |
* little simpler. It is also basically similar to the approach |
66 |
* in Edya Ladan-Mozes and Nir Shavit "An Optimistic Approach to |
67 |
* Lock-Free FIFO Queues" in DISC04. |
68 |
* |
69 |
* Quoting a summary in Paul Martin's tech report: |
70 |
* |
71 |
* All cleanups work to maintain these invariants: |
72 |
* (1) forward pointers are the ground truth. |
73 |
* (2) forward pointers to dead nodes can be improved by swinging them |
74 |
* further forward around the dead node. |
75 |
* (2.1) forward pointers are still correct when pointing to dead |
76 |
* nodes, and forward pointers from dead nodes are left |
77 |
* as they were when the node was deleted. |
78 |
* (2.2) multiple dead nodes may point forward to the same node. |
79 |
* (3) backward pointers were correct when they were installed |
80 |
* (3.1) backward pointers are correct when pointing to any |
81 |
* node which points forward to them, but since more than |
82 |
* one forward pointer may point to them, the live one is best. |
83 |
* (4) backward pointers that are out of date due to deletion |
84 |
* point to a deleted node, and need to point further back until |
85 |
* they point to the live node that points to their source. |
86 |
* (5) backward pointers that are out of date due to insertion |
87 |
* point too far backwards, so shortening their scope (by searching |
88 |
* forward) fixes them. |
89 |
* (6) backward pointers from a dead node cannot be "improved" since |
90 |
* there may be no live node pointing forward to their origin. |
91 |
* (However, it does no harm to try to improve them while |
92 |
* racing with a deletion.) |
93 |
* |
94 |
* |
95 |
* Notation guide for local variables |
96 |
* n, b, f : a node, its predecessor, and successor |
97 |
* s : some other successor |
98 |
*/ |
99 |
|
100 |
/** |
101 |
* Linked Nodes. As a minor efficiency hack, this class |
102 |
* opportunistically inherits from AtomicReference, with the |
103 |
* atomic ref used as the "next" link. |
104 |
* |
105 |
* Nodes are in doubly-linked lists. There are three |
106 |
* kinds of special nodes, distinguished by: |
107 |
* * The list header has a null prev link. |
108 |
* * The list trailer has a null next link. |
109 |
* * A deletion marker has a prev link pointing to itself. |
110 |
* All three kinds of special nodes have null element fields. |
111 |
* |
112 |
* Regular nodes have non-null element, next, and prev fields. To |
113 |
* avoid visible inconsistencies when deletions overlap element |
114 |
* replacement, replacements are done by replacing the node, not |
115 |
* just setting the element. |
116 |
* |
117 |
* Nodes can be traversed by read-only ConcurrentLinkedDeque class |
118 |
* operations just by following raw next pointers, so long as they |
119 |
* ignore any special nodes seen along the way. (This is automated |
120 |
* in method forward.) However, traversal using prev pointers is |
121 |
* not guaranteed to see all live nodes since a prev pointer of a |
122 |
* deleted node can become unrecoverably stale. |
123 |
*/ |
124 |
static final class Node<E> extends AtomicReference<Node<E>> { |
125 |
private volatile Node<E> prev; |
126 |
final E element; |
127 |
private static final long serialVersionUID = 876323262645176354L; |
128 |
|
129 |
/** Creates a node with given contents. */ |
130 |
Node(E element, Node<E> next, Node<E> prev) { |
131 |
super(next); |
132 |
this.prev = prev; |
133 |
this.element = element; |
134 |
} |
135 |
|
136 |
/** Creates a marker node with given successor. */ |
137 |
Node(Node<E> next) { |
138 |
super(next); |
139 |
this.prev = this; |
140 |
this.element = null; |
141 |
} |
142 |
|
143 |
/** |
144 |
* Gets next link (which is actually the value held |
145 |
* as atomic reference). |
146 |
*/ |
147 |
private Node<E> getNext() { |
148 |
return get(); |
149 |
} |
150 |
|
151 |
/** |
152 |
* Sets next link. |
153 |
* @param n the next node |
154 |
*/ |
155 |
void setNext(Node<E> n) { |
156 |
set(n); |
157 |
} |
158 |
|
159 |
/** |
160 |
* compareAndSet next link |
161 |
*/ |
162 |
private boolean casNext(Node<E> cmp, Node<E> val) { |
163 |
return compareAndSet(cmp, val); |
164 |
} |
165 |
|
166 |
/** |
167 |
* Gets prev link. |
168 |
*/ |
169 |
private Node<E> getPrev() { |
170 |
return prev; |
171 |
} |
172 |
|
173 |
/** |
174 |
* Sets prev link. |
175 |
* @param b the previous node |
176 |
*/ |
177 |
void setPrev(Node<E> b) { |
178 |
prev = b; |
179 |
} |
180 |
|
181 |
/** |
182 |
* Returns true if this is a header, trailer, or marker node. |
183 |
*/ |
184 |
boolean isSpecial() { |
185 |
return element == null; |
186 |
} |
187 |
|
188 |
/** |
189 |
* Returns true if this is a trailer node. |
190 |
*/ |
191 |
boolean isTrailer() { |
192 |
return getNext() == null; |
193 |
} |
194 |
|
195 |
/** |
196 |
* Returns true if this is a header node. |
197 |
*/ |
198 |
boolean isHeader() { |
199 |
return getPrev() == null; |
200 |
} |
201 |
|
202 |
/** |
203 |
* Returns true if this is a marker node. |
204 |
*/ |
205 |
boolean isMarker() { |
206 |
return getPrev() == this; |
207 |
} |
208 |
|
209 |
/** |
210 |
* Returns true if this node is followed by a marker node, |
211 |
* meaning that this node is deleted. |
212 |
* |
213 |
* @return true if this node is deleted |
214 |
*/ |
215 |
boolean isDeleted() { |
216 |
Node<E> f = getNext(); |
217 |
return f != null && f.isMarker(); |
218 |
} |
219 |
|
220 |
/** |
221 |
* Returns next node, ignoring deletion marker. |
222 |
*/ |
223 |
private Node<E> nextNonmarker() { |
224 |
Node<E> f = getNext(); |
225 |
return (f == null || !f.isMarker()) ? f : f.getNext(); |
226 |
} |
227 |
|
228 |
/** |
229 |
* Returns the next non-deleted node, swinging next pointer |
230 |
* around any encountered deleted nodes, and also patching up |
231 |
* successor's prev link to point back to this. Returns |
232 |
* null if this node is trailer so has no successor. |
233 |
* |
234 |
* @return successor, or null if no such |
235 |
*/ |
236 |
Node<E> successor() { |
237 |
Node<E> f = nextNonmarker(); |
238 |
for (;;) { |
239 |
if (f == null) |
240 |
return null; |
241 |
if (!f.isDeleted()) { |
242 |
if (f.getPrev() != this && !isDeleted()) |
243 |
f.setPrev(this); // relink f's prev |
244 |
return f; |
245 |
} |
246 |
Node<E> s = f.nextNonmarker(); |
247 |
if (f == getNext()) |
248 |
casNext(f, s); // unlink f |
249 |
f = s; |
250 |
} |
251 |
} |
252 |
|
253 |
/** |
254 |
* Returns the apparent predecessor of target by searching |
255 |
* forward for it, starting at this node, patching up pointers |
256 |
* while traversing. Used by predecessor(). |
257 |
* |
258 |
* @return target's predecessor, or null if not found |
259 |
*/ |
260 |
private Node<E> findPredecessorOf(Node<E> target) { |
261 |
Node<E> n = this; |
262 |
for (;;) { |
263 |
Node<E> f = n.successor(); |
264 |
if (f == target) |
265 |
return n; |
266 |
if (f == null) |
267 |
return null; |
268 |
n = f; |
269 |
} |
270 |
} |
271 |
|
272 |
/** |
273 |
* Returns the previous non-deleted node, patching up pointers |
274 |
* as needed. Returns null if this node is header so has no |
275 |
* successor. May also return null if this node is deleted, |
276 |
* so doesn't have a distinct predecessor. |
277 |
* |
278 |
* @return predecessor, or null if not found |
279 |
*/ |
280 |
Node<E> predecessor() { |
281 |
Node<E> n = this; |
282 |
for (;;) { |
283 |
Node<E> b = n.getPrev(); |
284 |
if (b == null) |
285 |
return n.findPredecessorOf(this); |
286 |
Node<E> s = b.getNext(); |
287 |
if (s == this) |
288 |
return b; |
289 |
if (s == null || !s.isMarker()) { |
290 |
Node<E> p = b.findPredecessorOf(this); |
291 |
if (p != null) |
292 |
return p; |
293 |
} |
294 |
n = b; |
295 |
} |
296 |
} |
297 |
|
298 |
/** |
299 |
* Returns the next node containing a nondeleted user element. |
300 |
* Use for forward list traversal. |
301 |
* |
302 |
* @return successor, or null if no such |
303 |
*/ |
304 |
Node<E> forward() { |
305 |
Node<E> f = successor(); |
306 |
return (f == null || f.isSpecial()) ? null : f; |
307 |
} |
308 |
|
309 |
/** |
310 |
* Returns previous node containing a nondeleted user element, if |
311 |
* possible. Use for backward list traversal, but beware that |
312 |
* if this method is called from a deleted node, it might not |
313 |
* be able to determine a usable predecessor. |
314 |
* |
315 |
* @return predecessor, or null if no such could be found |
316 |
*/ |
317 |
Node<E> back() { |
318 |
Node<E> f = predecessor(); |
319 |
return (f == null || f.isSpecial()) ? null : f; |
320 |
} |
321 |
|
322 |
/** |
323 |
* Tries to insert a node holding element as successor, failing |
324 |
* if this node is deleted. |
325 |
* |
326 |
* @param element the element |
327 |
* @return the new node, or null on failure |
328 |
*/ |
329 |
Node<E> append(E element) { |
330 |
for (;;) { |
331 |
Node<E> f = getNext(); |
332 |
if (f == null || f.isMarker()) |
333 |
return null; |
334 |
Node<E> x = new Node<E>(element, f, this); |
335 |
if (casNext(f, x)) { |
336 |
f.setPrev(x); // optimistically link |
337 |
return x; |
338 |
} |
339 |
} |
340 |
} |
341 |
|
342 |
/** |
343 |
* Tries to insert a node holding element as predecessor, failing |
344 |
* if no live predecessor can be found to link to. |
345 |
* |
346 |
* @param element the element |
347 |
* @return the new node, or null on failure |
348 |
*/ |
349 |
Node<E> prepend(E element) { |
350 |
for (;;) { |
351 |
Node<E> b = predecessor(); |
352 |
if (b == null) |
353 |
return null; |
354 |
Node<E> x = new Node<E>(element, this, b); |
355 |
if (b.casNext(this, x)) { |
356 |
setPrev(x); // optimistically link |
357 |
return x; |
358 |
} |
359 |
} |
360 |
} |
361 |
|
362 |
/** |
363 |
* Tries to mark this node as deleted, failing if already |
364 |
* deleted or if this node is header or trailer. |
365 |
* |
366 |
* @return true if successful |
367 |
*/ |
368 |
boolean delete() { |
369 |
Node<E> b = getPrev(); |
370 |
Node<E> f = getNext(); |
371 |
if (b != null && f != null && !f.isMarker() && |
372 |
casNext(f, new Node<E>(f))) { |
373 |
if (b.casNext(this, f)) |
374 |
f.setPrev(b); |
375 |
return true; |
376 |
} |
377 |
return false; |
378 |
} |
379 |
|
380 |
/** |
381 |
* Tries to insert a node holding element to replace this node. |
382 |
* failing if already deleted. A currently unused proof of |
383 |
* concept that demonstrates atomic node content replacement. |
384 |
* |
385 |
* Although this implementation ensures that exactly one |
386 |
* version of this Node is alive at a given time, it fails to |
387 |
* maintain atomicity in the sense that iterators may |
388 |
* encounter both the old and new versions of the element. |
389 |
* |
390 |
* @param newElement the new element |
391 |
* @return the new node, or null on failure |
392 |
*/ |
393 |
Node<E> replace(E newElement) { |
394 |
for (;;) { |
395 |
Node<E> b = getPrev(); |
396 |
Node<E> f = getNext(); |
397 |
if (b == null || f == null || f.isMarker()) |
398 |
return null; |
399 |
Node<E> x = new Node<E>(newElement, f, b); |
400 |
if (casNext(f, new Node<E>(x))) { |
401 |
b.successor(); // to relink b |
402 |
x.successor(); // to relink f |
403 |
return x; |
404 |
} |
405 |
} |
406 |
} |
407 |
} |
408 |
|
409 |
// Minor convenience utilities |
410 |
|
411 |
/** |
412 |
* Returns true if given reference is non-null and isn't a header, |
413 |
* trailer, or marker. |
414 |
* |
415 |
* @param n (possibly null) node |
416 |
* @return true if n exists as a user node |
417 |
*/ |
418 |
private static boolean usable(Node<?> n) { |
419 |
return n != null && !n.isSpecial(); |
420 |
} |
421 |
|
422 |
/** |
423 |
* Throws NullPointerException if argument is null. |
424 |
* |
425 |
* @param v the element |
426 |
*/ |
427 |
private static void checkNotNull(Object v) { |
428 |
if (v == null) |
429 |
throw new NullPointerException(); |
430 |
} |
431 |
|
432 |
/** |
433 |
* Returns element unless it is null, in which case throws |
434 |
* NoSuchElementException. |
435 |
* |
436 |
* @param v the element |
437 |
* @return the element |
438 |
*/ |
439 |
private E screenNullResult(E v) { |
440 |
if (v == null) |
441 |
throw new NoSuchElementException(); |
442 |
return v; |
443 |
} |
444 |
|
445 |
/** |
446 |
* Creates an array list and fills it with elements of this list. |
447 |
* Used by toArray. |
448 |
* |
449 |
* @return the array list |
450 |
*/ |
451 |
private ArrayList<E> toArrayList() { |
452 |
ArrayList<E> c = new ArrayList<E>(); |
453 |
for (Node<E> n = header.forward(); n != null; n = n.forward()) |
454 |
c.add(n.element); |
455 |
return c; |
456 |
} |
457 |
|
458 |
// Fields and constructors |
459 |
|
460 |
private static final long serialVersionUID = 876323262645176354L; |
461 |
|
462 |
/** |
463 |
* List header. First usable node is at header.forward(). |
464 |
*/ |
465 |
private final Node<E> header; |
466 |
|
467 |
/** |
468 |
* List trailer. Last usable node is at trailer.back(). |
469 |
*/ |
470 |
private final Node<E> trailer; |
471 |
|
472 |
/** |
473 |
* Constructs an empty deque. |
474 |
*/ |
475 |
public ConcurrentLinkedDeque() { |
476 |
Node<E> h = new Node<E>(null, null, null); |
477 |
Node<E> t = new Node<E>(null, null, h); |
478 |
h.setNext(t); |
479 |
header = h; |
480 |
trailer = t; |
481 |
} |
482 |
|
483 |
/** |
484 |
* Constructs a deque initially containing the elements of |
485 |
* the given collection, added in traversal order of the |
486 |
* collection's iterator. |
487 |
* |
488 |
* @param c the collection of elements to initially contain |
489 |
* @throws NullPointerException if the specified collection or any |
490 |
* of its elements are null |
491 |
*/ |
492 |
public ConcurrentLinkedDeque(Collection<? extends E> c) { |
493 |
this(); |
494 |
addAll(c); |
495 |
} |
496 |
|
497 |
/** |
498 |
* Inserts the specified element at the front of this deque. |
499 |
* |
500 |
* @throws NullPointerException {@inheritDoc} |
501 |
*/ |
502 |
public void addFirst(E e) { |
503 |
checkNotNull(e); |
504 |
while (header.append(e) == null) |
505 |
; |
506 |
} |
507 |
|
508 |
/** |
509 |
* Inserts the specified element at the end of this deque. |
510 |
* This is identical in function to the {@code add} method. |
511 |
* |
512 |
* @throws NullPointerException {@inheritDoc} |
513 |
*/ |
514 |
public void addLast(E e) { |
515 |
checkNotNull(e); |
516 |
while (trailer.prepend(e) == null) |
517 |
; |
518 |
} |
519 |
|
520 |
/** |
521 |
* Inserts the specified element at the front of this deque. |
522 |
* |
523 |
* @return {@code true} always |
524 |
* @throws NullPointerException {@inheritDoc} |
525 |
*/ |
526 |
public boolean offerFirst(E e) { |
527 |
addFirst(e); |
528 |
return true; |
529 |
} |
530 |
|
531 |
/** |
532 |
* Inserts the specified element at the end of this deque. |
533 |
* |
534 |
* <p>This method is equivalent to {@link #add}. |
535 |
* |
536 |
* @return {@code true} always |
537 |
* @throws NullPointerException {@inheritDoc} |
538 |
*/ |
539 |
public boolean offerLast(E e) { |
540 |
addLast(e); |
541 |
return true; |
542 |
} |
543 |
|
544 |
public E peekFirst() { |
545 |
Node<E> n = header.successor(); |
546 |
return (n == null) ? null : n.element; |
547 |
} |
548 |
|
549 |
public E peekLast() { |
550 |
Node<E> n = trailer.predecessor(); |
551 |
return (n == null) ? null : n.element; |
552 |
} |
553 |
|
554 |
/** |
555 |
* @throws NoSuchElementException {@inheritDoc} |
556 |
*/ |
557 |
public E getFirst() { |
558 |
return screenNullResult(peekFirst()); |
559 |
} |
560 |
|
561 |
/** |
562 |
* @throws NoSuchElementException {@inheritDoc} |
563 |
*/ |
564 |
public E getLast() { |
565 |
return screenNullResult(peekLast()); |
566 |
} |
567 |
|
568 |
public E pollFirst() { |
569 |
for (;;) { |
570 |
Node<E> n = header.successor(); |
571 |
if (!usable(n)) |
572 |
return null; |
573 |
if (n.delete()) |
574 |
return n.element; |
575 |
} |
576 |
} |
577 |
|
578 |
public E pollLast() { |
579 |
for (;;) { |
580 |
Node<E> n = trailer.predecessor(); |
581 |
if (!usable(n)) |
582 |
return null; |
583 |
if (n.delete()) |
584 |
return n.element; |
585 |
} |
586 |
} |
587 |
|
588 |
/** |
589 |
* @throws NoSuchElementException {@inheritDoc} |
590 |
*/ |
591 |
public E removeFirst() { |
592 |
return screenNullResult(pollFirst()); |
593 |
} |
594 |
|
595 |
/** |
596 |
* @throws NoSuchElementException {@inheritDoc} |
597 |
*/ |
598 |
public E removeLast() { |
599 |
return screenNullResult(pollLast()); |
600 |
} |
601 |
|
602 |
// *** Queue and stack methods *** |
603 |
|
604 |
/** |
605 |
* Inserts the specified element at the tail of this queue. |
606 |
* |
607 |
* @return {@code true} |
608 |
* (as specified by {@link java.util.Queue#offer 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 |
} |