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/licenses/publicdomain |
4 |
> |
* http://creativecommons.org/publicdomain/zero/1.0/ |
5 |
|
*/ |
6 |
|
|
7 |
|
package jsr166x; |
14 |
|
* An optionally-bounded {@linkplain BlockingDeque blocking deque} based on |
15 |
|
* linked nodes. |
16 |
|
* |
17 |
< |
* <p> The optional capacity bound constructor argument serves as a |
17 |
> |
* <p>The optional capacity bound constructor argument serves as a |
18 |
|
* way to prevent excessive expansion. The capacity, if unspecified, |
19 |
|
* is equal to {@link Integer#MAX_VALUE}. Linked nodes are |
20 |
|
* dynamically created upon each insertion unless this would bring the |
39 |
|
*/ |
40 |
|
public class LinkedBlockingDeque<E> |
41 |
|
extends AbstractQueue<E> |
42 |
< |
implements BlockingDeque<E>, java.io.Serializable { |
42 |
> |
implements BlockingDeque<E>, java.io.Serializable { |
43 |
|
|
44 |
|
/* |
45 |
|
* Implemented as a simple doubly-linked list protected by a |
50 |
|
|
51 |
|
/** Doubly-linked list node class */ |
52 |
|
static final class Node<E> { |
53 |
< |
E item; |
53 |
> |
E item; |
54 |
|
Node<E> prev; |
55 |
|
Node<E> next; |
56 |
|
Node(E x, Node<E> p, Node<E> n) { |
76 |
|
private final Condition notFull = lock.newCondition(); |
77 |
|
|
78 |
|
/** |
79 |
< |
* Creates a <tt>LinkedBlockingDeque</tt> with a capacity of |
79 |
> |
* Creates a {@code LinkedBlockingDeque} with a capacity of |
80 |
|
* {@link Integer#MAX_VALUE}. |
81 |
|
*/ |
82 |
|
public LinkedBlockingDeque() { |
84 |
|
} |
85 |
|
|
86 |
|
/** |
87 |
< |
* Creates a <tt>LinkedBlockingDeque</tt> with the given (fixed) |
87 |
> |
* Creates a {@code LinkedBlockingDeque} with the given (fixed) |
88 |
|
* capacity. |
89 |
|
* @param capacity the capacity of this deque |
90 |
< |
* @throws IllegalArgumentException if <tt>capacity</tt> is less than 1 |
90 |
> |
* @throws IllegalArgumentException if {@code capacity} is less than 1 |
91 |
|
*/ |
92 |
|
public LinkedBlockingDeque(int capacity) { |
93 |
|
if (capacity <= 0) throw new IllegalArgumentException(); |
95 |
|
} |
96 |
|
|
97 |
|
/** |
98 |
< |
* Creates a <tt>LinkedBlockingDeque</tt> with a capacity of |
98 |
> |
* Creates a {@code LinkedBlockingDeque} with a capacity of |
99 |
|
* {@link Integer#MAX_VALUE}, initially containing the elements of the |
100 |
|
* given collection, |
101 |
|
* added in traversal order of the collection's iterator. |
102 |
|
* @param c the collection of elements to initially contain |
103 |
< |
* @throws NullPointerException if <tt>c</tt> or any element within it |
104 |
< |
* is <tt>null</tt> |
103 |
> |
* @throws NullPointerException if {@code c} or any element within it |
104 |
> |
* is {@code null} |
105 |
|
*/ |
106 |
|
public LinkedBlockingDeque(Collection<? extends E> c) { |
107 |
|
this(Integer.MAX_VALUE); |
149 |
|
} |
150 |
|
|
151 |
|
/** |
152 |
< |
* Remove and return first element, or null if empty |
152 |
> |
* Removes and returns first element, or null if empty. |
153 |
|
*/ |
154 |
|
private E unlinkFirst() { |
155 |
|
Node<E> f = first; |
157 |
|
return null; |
158 |
|
Node<E> n = f.next; |
159 |
|
first = n; |
160 |
< |
if (n == null) |
160 |
> |
if (n == null) |
161 |
|
last = null; |
162 |
< |
else |
162 |
> |
else |
163 |
|
n.prev = null; |
164 |
|
--count; |
165 |
|
notFull.signal(); |
167 |
|
} |
168 |
|
|
169 |
|
/** |
170 |
< |
* Remove and return last element, or null if empty |
170 |
> |
* Removes and returns last element, or null if empty. |
171 |
|
*/ |
172 |
|
private E unlinkLast() { |
173 |
|
Node<E> l = last; |
175 |
|
return null; |
176 |
|
Node<E> p = l.prev; |
177 |
|
last = p; |
178 |
< |
if (p == null) |
178 |
> |
if (p == null) |
179 |
|
first = null; |
180 |
< |
else |
180 |
> |
else |
181 |
|
p.next = null; |
182 |
|
--count; |
183 |
|
notFull.signal(); |
191 |
|
Node<E> p = x.prev; |
192 |
|
Node<E> n = x.next; |
193 |
|
if (p == null) { |
194 |
< |
if (n == null) |
194 |
> |
if (n == null) |
195 |
|
first = last = null; |
196 |
|
else { |
197 |
|
n.prev = null; |
230 |
|
} |
231 |
|
} |
232 |
|
|
233 |
< |
public void addFirst(E e) { |
233 |
> |
public void addFirst(E e) { |
234 |
|
if (!offerFirst(e)) |
235 |
|
throw new IllegalStateException("Deque full"); |
236 |
|
} |
237 |
|
|
238 |
< |
public void addLast(E e) { |
238 |
> |
public void addLast(E e) { |
239 |
|
if (!offerLast(e)) |
240 |
|
throw new IllegalStateException("Deque full"); |
241 |
|
} |
288 |
|
} |
289 |
|
} |
290 |
|
|
291 |
< |
public E firstElement() { |
291 |
> |
public E getFirst() { |
292 |
|
E x = peekFirst(); |
293 |
|
if (x == null) throw new NoSuchElementException(); |
294 |
|
return x; |
295 |
|
} |
296 |
|
|
297 |
< |
public E lastElement() { |
297 |
> |
public E getLast() { |
298 |
|
E x = peekLast(); |
299 |
|
if (x == null) throw new NoSuchElementException(); |
300 |
|
return x; |
365 |
|
lock.unlock(); |
366 |
|
} |
367 |
|
} |
368 |
< |
|
368 |
> |
|
369 |
|
public boolean offerLast(E o, long timeout, TimeUnit unit) |
370 |
|
throws InterruptedException { |
371 |
|
if (o == null) throw new NullPointerException(); |
384 |
|
} |
385 |
|
} |
386 |
|
|
387 |
< |
public E pollFirst(long timeout, TimeUnit unit) |
387 |
> |
public E pollFirst(long timeout, TimeUnit unit) |
388 |
|
throws InterruptedException { |
389 |
|
lock.lockInterruptibly(); |
390 |
|
try { |
402 |
|
} |
403 |
|
} |
404 |
|
|
405 |
< |
public E pollLast(long timeout, TimeUnit unit) |
405 |
> |
public E pollLast(long timeout, TimeUnit unit) |
406 |
|
throws InterruptedException { |
407 |
|
lock.lockInterruptibly(); |
408 |
|
try { |
429 |
|
public E remove() { return removeFirst(); } |
430 |
|
public E pop() { return removeFirst(); } |
431 |
|
public E peek() { return peekFirst(); } |
432 |
< |
public E element() { return firstElement(); } |
432 |
> |
public E element() { return getFirst(); } |
433 |
|
public boolean remove(Object o) { return removeFirstOccurrence(o); } |
434 |
|
|
435 |
|
// BlockingQueue methods |
436 |
|
|
437 |
< |
public void put(E o) throws InterruptedException { putLast(o); } |
438 |
< |
public E take() throws InterruptedException { return takeFirst(); } |
437 |
> |
public void put(E o) throws InterruptedException { putLast(o); } |
438 |
> |
public E take() throws InterruptedException { return takeFirst(); } |
439 |
|
public boolean offer(E o, long timeout, TimeUnit unit) |
440 |
|
throws InterruptedException { return offerLast(o, timeout, unit); } |
441 |
|
public E poll(long timeout, TimeUnit unit) |
444 |
|
/** |
445 |
|
* Returns the number of elements in this deque. |
446 |
|
* |
447 |
< |
* @return the number of elements in this deque. |
447 |
> |
* @return the number of elements in this deque |
448 |
|
*/ |
449 |
|
public int size() { |
450 |
|
lock.lock(); |
459 |
|
* Returns the number of elements that this deque can ideally (in |
460 |
|
* the absence of memory or resource constraints) accept without |
461 |
|
* blocking. This is always equal to the initial capacity of this deque |
462 |
< |
* less the current <tt>size</tt> of this deque. |
462 |
> |
* less the current {@code size} of this deque. |
463 |
|
* <p>Note that you <em>cannot</em> always tell if |
464 |
< |
* an attempt to <tt>add</tt> an element will succeed by |
465 |
< |
* inspecting <tt>remainingCapacity</tt> because it may be the |
466 |
< |
* case that a waiting consumer is ready to <tt>take</tt> an |
464 |
> |
* an attempt to {@code add} an element will succeed by |
465 |
> |
* inspecting {@code remainingCapacity} because it may be the |
466 |
> |
* case that a waiting consumer is ready to {@code take} an |
467 |
|
* element out of an otherwise full deque. |
468 |
|
*/ |
469 |
|
public int remainingCapacity() { |
479 |
|
if (o == null) return false; |
480 |
|
lock.lock(); |
481 |
|
try { |
482 |
< |
for (Node<E> p = first; p != null; p = p.next) |
482 |
> |
for (Node<E> p = first; p != null; p = p.next) |
483 |
|
if (o.equals(p.item)) |
484 |
|
return true; |
485 |
|
return false; |
524 |
|
* Variant of removeFirstOccurrence needed by iterator.remove. |
525 |
|
* Searches for the node, not its contents. |
526 |
|
*/ |
527 |
< |
boolean removeNode(Node<E> e) { |
527 |
> |
boolean removeNode(Node<E> e) { |
528 |
|
lock.lock(); |
529 |
|
try { |
530 |
|
for (Node<E> p = first; p != null; p = p.next) { |
544 |
|
try { |
545 |
|
Object[] a = new Object[count]; |
546 |
|
int k = 0; |
547 |
< |
for (Node<E> p = first; p != null; p = p.next) |
547 |
> |
for (Node<E> p = first; p != null; p = p.next) |
548 |
|
a[k++] = p.item; |
549 |
|
return a; |
550 |
|
} finally { |
562 |
|
); |
563 |
|
|
564 |
|
int k = 0; |
565 |
< |
for (Node<E> p = first; p != null; p = p.next) |
565 |
> |
for (Node<E> p = first; p != null; p = p.next) |
566 |
|
a[k++] = (T)p.item; |
567 |
|
if (a.length > k) |
568 |
|
a[k] = null; |
603 |
|
throw new IllegalArgumentException(); |
604 |
|
lock.lock(); |
605 |
|
try { |
606 |
< |
for (Node<E> p = first; p != null; p = p.next) |
606 |
> |
for (Node<E> p = first; p != null; p = p.next) |
607 |
|
c.add(p.item); |
608 |
|
int n = count; |
609 |
|
count = 0; |
641 |
|
|
642 |
|
/** |
643 |
|
* Returns an iterator over the elements in this deque in proper sequence. |
644 |
< |
* The returned <tt>Iterator</tt> is a "weakly consistent" iterator that |
644 |
> |
* The returned {@code Iterator} is a "weakly consistent" iterator that |
645 |
|
* will never throw {@link java.util.ConcurrentModificationException}, |
646 |
|
* and guarantees to traverse elements as they existed upon |
647 |
|
* construction of the iterator, and may (but is not guaranteed to) |
648 |
|
* reflect any modifications subsequent to construction. |
649 |
|
* |
650 |
< |
* @return an iterator over the elements in this deque in proper sequence. |
650 |
> |
* @return an iterator over the elements in this deque in proper sequence |
651 |
|
*/ |
652 |
|
public Iterator<E> iterator() { |
653 |
|
return new Itr(); |
664 |
|
* an element exists in hasNext(), we must return item read |
665 |
|
* under lock (in advance()) even if it was in the process of |
666 |
|
* being removed when hasNext() was called. |
667 |
< |
**/ |
667 |
> |
*/ |
668 |
|
private E nextItem; |
669 |
|
|
670 |
|
/** |
680 |
|
/** |
681 |
|
* Advance next, or if not yet initialized, set to first node. |
682 |
|
*/ |
683 |
< |
private void advance() { |
683 |
> |
private void advance() { |
684 |
|
final ReentrantLock lock = LinkedBlockingDeque.this.lock; |
685 |
|
lock.lock(); |
686 |
|
try { |
687 |
< |
next = (next == null)? first : next.next; |
688 |
< |
nextItem = (next == null)? null : next.item; |
687 |
> |
next = (next == null) ? first : next.next; |
688 |
> |
nextItem = (next == null) ? null : next.item; |
689 |
|
} finally { |
690 |
|
lock.unlock(); |
691 |
|
} |
717 |
|
} |
718 |
|
|
719 |
|
/** |
720 |
< |
* Save the state to a stream (that is, serialize it). |
720 |
> |
* Saves the state to a stream (that is, serializes it). |
721 |
|
* |
722 |
|
* @serialData The capacity (int), followed by elements (each an |
723 |
< |
* <tt>Object</tt>) in the proper order, followed by a null |
723 |
> |
* {@code Object}) in the proper order, followed by a null |
724 |
|
* @param s the stream |
725 |
|
*/ |
726 |
|
private void writeObject(java.io.ObjectOutputStream s) |
740 |
|
} |
741 |
|
|
742 |
|
/** |
743 |
< |
* Reconstitute this deque instance from a stream (that is, |
744 |
< |
* deserialize it). |
743 |
> |
* Reconstitutes this deque instance from a stream (that is, |
744 |
> |
* deserializes it). |
745 |
|
* @param s the stream |
746 |
|
*/ |
747 |
|
private void readObject(java.io.ObjectInputStream s) |
758 |
|
add(item); |
759 |
|
} |
760 |
|
} |
761 |
< |
|
761 |
> |
|
762 |
|
} |