1:
6:
7: package ;
8: import ;
9: import ;
10:
11:
40: public class LinkedBlockingDeque<E>
41: extends AbstractQueue<E>
42: implements BlockingDeque<E>, java.io.Serializable {
43:
44:
48:
49:
55:
56: private static final long serialVersionUID = -387911632671998426L;
57:
58:
59: static final class Node<E> {
60: E item;
61: Node<E> prev;
62: Node<E> next;
63: Node(E x, Node<E> p, Node<E> n) {
64: item = x;
65: prev = p;
66: next = n;
67: }
68: }
69:
70:
71: private transient Node<E> first;
72:
73: private transient Node<E> last;
74:
75: private transient int count;
76:
77: private final int capacity;
78:
79: private final ReentrantLock lock = new ReentrantLock();
80:
81: private final Condition notEmpty = lock.newCondition();
82:
83: private final Condition notFull = lock.newCondition();
84:
85:
89: public LinkedBlockingDeque() {
90: this(Integer.MAX_VALUE);
91: }
92:
93:
99: public LinkedBlockingDeque(int capacity) {
100: if (capacity <= 0) throw new IllegalArgumentException();
101: this.capacity = capacity;
102: }
103:
104:
114: public LinkedBlockingDeque(Collection<? extends E> c) {
115: this(Integer.MAX_VALUE);
116: for (E e : c)
117: add(e);
118: }
119:
120:
121:
122:
123:
126: private boolean linkFirst(E e) {
127: if (count >= capacity)
128: return false;
129: ++count;
130: Node<E> f = first;
131: Node<E> x = new Node<E>(e, null, f);
132: first = x;
133: if (last == null)
134: last = x;
135: else
136: f.prev = x;
137: notEmpty.signal();
138: return true;
139: }
140:
141:
144: private boolean linkLast(E e) {
145: if (count >= capacity)
146: return false;
147: ++count;
148: Node<E> l = last;
149: Node<E> x = new Node<E>(e, l, null);
150: last = x;
151: if (first == null)
152: first = x;
153: else
154: l.next = x;
155: notEmpty.signal();
156: return true;
157: }
158:
159:
162: private E unlinkFirst() {
163: Node<E> f = first;
164: if (f == null)
165: return null;
166: Node<E> n = f.next;
167: first = n;
168: if (n == null)
169: last = null;
170: else
171: n.prev = null;
172: --count;
173: notFull.signal();
174: return f.item;
175: }
176:
177:
180: private E unlinkLast() {
181: Node<E> l = last;
182: if (l == null)
183: return null;
184: Node<E> p = l.prev;
185: last = p;
186: if (p == null)
187: first = null;
188: else
189: p.next = null;
190: --count;
191: notFull.signal();
192: return l.item;
193: }
194:
195:
198: private void unlink(Node<E> x) {
199: Node<E> p = x.prev;
200: Node<E> n = x.next;
201: if (p == null) {
202: if (n == null)
203: first = last = null;
204: else {
205: n.prev = null;
206: first = n;
207: }
208: } else if (n == null) {
209: p.next = null;
210: last = p;
211: } else {
212: p.next = n;
213: n.prev = p;
214: }
215: --count;
216: notFull.signalAll();
217: }
218:
219:
220:
221:
225: public void addFirst(E e) {
226: if (!offerFirst(e))
227: throw new IllegalStateException("Deque full");
228: }
229:
230:
234: public void addLast(E e) {
235: if (!offerLast(e))
236: throw new IllegalStateException("Deque full");
237: }
238:
239:
242: public boolean offerFirst(E e) {
243: if (e == null) throw new NullPointerException();
244: lock.lock();
245: try {
246: return linkFirst(e);
247: } finally {
248: lock.unlock();
249: }
250: }
251:
252:
255: public boolean offerLast(E e) {
256: if (e == null) throw new NullPointerException();
257: lock.lock();
258: try {
259: return linkLast(e);
260: } finally {
261: lock.unlock();
262: }
263: }
264:
265:
269: public void putFirst(E e) throws InterruptedException {
270: if (e == null) throw new NullPointerException();
271: lock.lock();
272: try {
273: while (!linkFirst(e))
274: notFull.await();
275: } finally {
276: lock.unlock();
277: }
278: }
279:
280:
284: public void putLast(E e) throws InterruptedException {
285: if (e == null) throw new NullPointerException();
286: lock.lock();
287: try {
288: while (!linkLast(e))
289: notFull.await();
290: } finally {
291: lock.unlock();
292: }
293: }
294:
295:
299: public boolean offerFirst(E e, long timeout, TimeUnit unit)
300: throws InterruptedException {
301: if (e == null) throw new NullPointerException();
302: long nanos = unit.toNanos(timeout);
303: lock.lockInterruptibly();
304: try {
305: for (;;) {
306: if (linkFirst(e))
307: return true;
308: if (nanos <= 0)
309: return false;
310: nanos = notFull.awaitNanos(nanos);
311: }
312: } finally {
313: lock.unlock();
314: }
315: }
316:
317:
321: public boolean offerLast(E e, long timeout, TimeUnit unit)
322: throws InterruptedException {
323: if (e == null) throw new NullPointerException();
324: long nanos = unit.toNanos(timeout);
325: lock.lockInterruptibly();
326: try {
327: for (;;) {
328: if (linkLast(e))
329: return true;
330: if (nanos <= 0)
331: return false;
332: nanos = notFull.awaitNanos(nanos);
333: }
334: } finally {
335: lock.unlock();
336: }
337: }
338:
339:
342: public E removeFirst() {
343: E x = pollFirst();
344: if (x == null) throw new NoSuchElementException();
345: return x;
346: }
347:
348:
351: public E removeLast() {
352: E x = pollLast();
353: if (x == null) throw new NoSuchElementException();
354: return x;
355: }
356:
357: public E pollFirst() {
358: lock.lock();
359: try {
360: return unlinkFirst();
361: } finally {
362: lock.unlock();
363: }
364: }
365:
366: public E pollLast() {
367: lock.lock();
368: try {
369: return unlinkLast();
370: } finally {
371: lock.unlock();
372: }
373: }
374:
375: public E takeFirst() throws InterruptedException {
376: lock.lock();
377: try {
378: E x;
379: while ( (x = unlinkFirst()) == null)
380: notEmpty.await();
381: return x;
382: } finally {
383: lock.unlock();
384: }
385: }
386:
387: public E takeLast() throws InterruptedException {
388: lock.lock();
389: try {
390: E x;
391: while ( (x = unlinkLast()) == null)
392: notEmpty.await();
393: return x;
394: } finally {
395: lock.unlock();
396: }
397: }
398:
399: public E pollFirst(long timeout, TimeUnit unit)
400: throws InterruptedException {
401: long nanos = unit.toNanos(timeout);
402: lock.lockInterruptibly();
403: try {
404: for (;;) {
405: E x = unlinkFirst();
406: if (x != null)
407: return x;
408: if (nanos <= 0)
409: return null;
410: nanos = notEmpty.awaitNanos(nanos);
411: }
412: } finally {
413: lock.unlock();
414: }
415: }
416:
417: public E pollLast(long timeout, TimeUnit unit)
418: throws InterruptedException {
419: long nanos = unit.toNanos(timeout);
420: lock.lockInterruptibly();
421: try {
422: for (;;) {
423: E x = unlinkLast();
424: if (x != null)
425: return x;
426: if (nanos <= 0)
427: return null;
428: nanos = notEmpty.awaitNanos(nanos);
429: }
430: } finally {
431: lock.unlock();
432: }
433: }
434:
435:
438: public E getFirst() {
439: E x = peekFirst();
440: if (x == null) throw new NoSuchElementException();
441: return x;
442: }
443:
444:
447: public E getLast() {
448: E x = peekLast();
449: if (x == null) throw new NoSuchElementException();
450: return x;
451: }
452:
453: public E peekFirst() {
454: lock.lock();
455: try {
456: return (first == null) ? null : first.item;
457: } finally {
458: lock.unlock();
459: }
460: }
461:
462: public E peekLast() {
463: lock.lock();
464: try {
465: return (last == null) ? null : last.item;
466: } finally {
467: lock.unlock();
468: }
469: }
470:
471: public boolean removeFirstOccurrence(Object o) {
472: if (o == null) return false;
473: lock.lock();
474: try {
475: for (Node<E> p = first; p != null; p = p.next) {
476: if (o.equals(p.item)) {
477: unlink(p);
478: return true;
479: }
480: }
481: return false;
482: } finally {
483: lock.unlock();
484: }
485: }
486:
487: public boolean removeLastOccurrence(Object o) {
488: if (o == null) return false;
489: lock.lock();
490: try {
491: for (Node<E> p = last; p != null; p = p.prev) {
492: if (o.equals(p.item)) {
493: unlink(p);
494: return true;
495: }
496: }
497: return false;
498: } finally {
499: lock.unlock();
500: }
501: }
502:
503:
504:
505:
516: public boolean add(E e) {
517: addLast(e);
518: return true;
519: }
520:
521:
524: public boolean offer(E e) {
525: return offerLast(e);
526: }
527:
528:
532: public void put(E e) throws InterruptedException {
533: putLast(e);
534: }
535:
536:
540: public boolean offer(E e, long timeout, TimeUnit unit)
541: throws InterruptedException {
542: return offerLast(e, timeout, unit);
543: }
544:
545:
555: public E remove() {
556: return removeFirst();
557: }
558:
559: public E poll() {
560: return pollFirst();
561: }
562:
563: public E take() throws InterruptedException {
564: return takeFirst();
565: }
566:
567: public E poll(long timeout, TimeUnit unit) throws InterruptedException {
568: return pollFirst(timeout, unit);
569: }
570:
571:
581: public E element() {
582: return getFirst();
583: }
584:
585: public E peek() {
586: return peekFirst();
587: }
588:
589:
600: public int remainingCapacity() {
601: lock.lock();
602: try {
603: return capacity - count;
604: } finally {
605: lock.unlock();
606: }
607: }
608:
609:
615: public int drainTo(Collection<? super E> c) {
616: if (c == null)
617: throw new NullPointerException();
618: if (c == this)
619: throw new IllegalArgumentException();
620: lock.lock();
621: try {
622: for (Node<E> p = first; p != null; p = p.next)
623: c.add(p.item);
624: int n = count;
625: count = 0;
626: first = last = null;
627: notFull.signalAll();
628: return n;
629: } finally {
630: lock.unlock();
631: }
632: }
633:
634:
640: public int drainTo(Collection<? super E> c, int maxElements) {
641: if (c == null)
642: throw new NullPointerException();
643: if (c == this)
644: throw new IllegalArgumentException();
645: lock.lock();
646: try {
647: int n = 0;
648: while (n < maxElements && first != null) {
649: c.add(first.item);
650: first.prev = null;
651: first = first.next;
652: --count;
653: ++n;
654: }
655: if (first == null)
656: last = null;
657: notFull.signalAll();
658: return n;
659: } finally {
660: lock.unlock();
661: }
662: }
663:
664:
665:
666:
670: public void push(E e) {
671: addFirst(e);
672: }
673:
674:
677: public E pop() {
678: return removeFirst();
679: }
680:
681:
682:
683:
697: public boolean remove(Object o) {
698: return removeFirstOccurrence(o);
699: }
700:
701:
706: public int size() {
707: lock.lock();
708: try {
709: return count;
710: } finally {
711: lock.unlock();
712: }
713: }
714:
715:
723: public boolean contains(Object o) {
724: if (o == null) return false;
725: lock.lock();
726: try {
727: for (Node<E> p = first; p != null; p = p.next)
728: if (o.equals(p.item))
729: return true;
730: return false;
731: } finally {
732: lock.unlock();
733: }
734: }
735:
736:
740: boolean removeNode(Node<E> e) {
741: lock.lock();
742: try {
743: for (Node<E> p = first; p != null; p = p.next) {
744: if (p == e) {
745: unlink(p);
746: return true;
747: }
748: }
749: return false;
750: } finally {
751: lock.unlock();
752: }
753: }
754:
755:
768: public Object[] toArray() {
769: lock.lock();
770: try {
771: Object[] a = new Object[count];
772: int k = 0;
773: for (Node<E> p = first; p != null; p = p.next)
774: a[k++] = p.item;
775: return a;
776: } finally {
777: lock.unlock();
778: }
779: }
780:
781:
817: public <T> T[] toArray(T[] a) {
818: lock.lock();
819: try {
820: if (a.length < count)
821: a = (T[])java.lang.reflect.Array.newInstance(
822: a.getClass().getComponentType(),
823: count
824: );
825:
826: int k = 0;
827: for (Node<E> p = first; p != null; p = p.next)
828: a[k++] = (T)p.item;
829: if (a.length > k)
830: a[k] = null;
831: return a;
832: } finally {
833: lock.unlock();
834: }
835: }
836:
837: public String toString() {
838: lock.lock();
839: try {
840: return super.toString();
841: } finally {
842: lock.unlock();
843: }
844: }
845:
846:
850: public void clear() {
851: lock.lock();
852: try {
853: first = last = null;
854: count = 0;
855: notFull.signalAll();
856: } finally {
857: lock.unlock();
858: }
859: }
860:
861:
872: public Iterator<E> iterator() {
873: return new Itr();
874: }
875:
876:
886: public Iterator<E> descendingIterator() {
887: return new DescendingItr();
888: }
889:
890:
893: private abstract class AbstractItr implements Iterator<E> {
894:
897: Node<E> next;
898:
899:
905: E nextItem;
906:
907:
911: private Node<E> lastRet;
912:
913: AbstractItr() {
914: advance();
915: }
916:
917:
921: abstract void advance();
922:
923: public boolean hasNext() {
924: return next != null;
925: }
926:
927: public E next() {
928: if (next == null)
929: throw new NoSuchElementException();
930: lastRet = next;
931: E x = nextItem;
932: advance();
933: return x;
934: }
935:
936: public void remove() {
937: Node<E> n = lastRet;
938: if (n == null)
939: throw new IllegalStateException();
940: lastRet = null;
941:
942:
943:
944: removeNode(n);
945: }
946: }
947:
948:
949: private class Itr extends AbstractItr {
950: void advance() {
951: final ReentrantLock lock = LinkedBlockingDeque.this.lock;
952: lock.lock();
953: try {
954: next = (next == null)? first : next.next;
955: nextItem = (next == null)? null : next.item;
956: } finally {
957: lock.unlock();
958: }
959: }
960: }
961:
962:
965: private class DescendingItr extends AbstractItr {
966: void advance() {
967: final ReentrantLock lock = LinkedBlockingDeque.this.lock;
968: lock.lock();
969: try {
970: next = (next == null)? last : next.prev;
971: nextItem = (next == null)? null : next.item;
972: } finally {
973: lock.unlock();
974: }
975: }
976: }
977:
978:
985: private void writeObject(java.io.ObjectOutputStream s)
986: throws java.io.IOException {
987: lock.lock();
988: try {
989:
990: s.defaultWriteObject();
991:
992: for (Node<E> p = first; p != null; p = p.next)
993: s.writeObject(p.item);
994:
995: s.writeObject(null);
996: } finally {
997: lock.unlock();
998: }
999: }
1000:
1001:
1006: private void readObject(java.io.ObjectInputStream s)
1007: throws java.io.IOException, ClassNotFoundException {
1008: s.defaultReadObject();
1009: count = 0;
1010: first = null;
1011: last = null;
1012:
1013: for (;;) {
1014: E item = (E)s.readObject();
1015: if (item == null)
1016: break;
1017: add(item);
1018: }
1019: }
1020:
1021: }