Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[4205] branches/QUADS_QUERY_BRANCH/bigdata/src
|
From: <tho...@us...> - 2011-02-17 12:56:23
|
Revision: 4205
http://bigdata.svn.sourceforge.net/bigdata/?rev=4205&view=rev
Author: thompsonbry
Date: 2011-02-17 12:56:14 +0000 (Thu, 17 Feb 2011)
Log Message:
-----------
Initial check in of the LinkedBlockingQueue, LinkedBlockingDeque and their test suites from the JSR 166 sources. The source files are in the public domain per the author's declaration, which is replicated below:
/*
* Written by Doug Lea with assistance from members of JCP JSR-166
* Expert Group and released to the public domain, as explained at
* http://creativecommons.org/licenses/publicdomain
*/
These files are being introduced so that we may address certain patterns, such as found in BlockingBuffer and ChunkedRunningQuery, where nested locks occur which lead to deadlock if we use a blocking operation on the queue and otherwise lead to unsatisfactory designs involving polling and retries on the queue.
The files as checked in have been modified solely to resolve dependencies and (in the case of the unit tests) to comment out some unused methods which depend on Java 1.7 features.
Modified Paths:
--------------
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/TestAll.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/util/concurrent/TestAll.java
Added Paths:
-----------
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/jsr166/
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/jsr166/LinkedBlockingDeque.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/jsr166/LinkedBlockingQueue.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/jsr166/package.html
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/jsr166/
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/jsr166/BlockingQueueTest.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/jsr166/JSR166TestCase.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/jsr166/LinkedBlockingDequeTest.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/jsr166/LinkedBlockingQueueTest.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/jsr166/TestAll.java
Added: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/jsr166/LinkedBlockingDeque.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/jsr166/LinkedBlockingDeque.java (rev 0)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/jsr166/LinkedBlockingDeque.java 2011-02-17 12:56:14 UTC (rev 4205)
@@ -0,0 +1,1171 @@
+/*
+ * Written by Doug Lea with assistance from members of JCP JSR-166
+ * Expert Group and released to the public domain, as explained at
+ * http://creativecommons.org/licenses/publicdomain
+ */
+
+package com.bigdata.jsr166;
+
+import java.util.AbstractQueue;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.BlockingDeque;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.locks.Condition;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on
+ * linked nodes.
+ *
+ * <p> The optional capacity bound constructor argument serves as a
+ * way to prevent excessive expansion. The capacity, if unspecified,
+ * is equal to {@link Integer#MAX_VALUE}. Linked nodes are
+ * dynamically created upon each insertion unless this would bring the
+ * deque above capacity.
+ *
+ * <p>Most operations run in constant time (ignoring time spent
+ * blocking). Exceptions include {@link #remove(Object) remove},
+ * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link
+ * #removeLastOccurrence removeLastOccurrence}, {@link #contains
+ * contains}, {@link #iterator iterator.remove()}, and the bulk
+ * operations, all of which run in linear time.
+ *
+ * <p>This class and its iterator implement all of the
+ * <em>optional</em> methods of the {@link Collection} and {@link
+ * Iterator} interfaces.
+ *
+ * <p>This class is a member of the
+ * <a href="{@docRoot}/../technotes/guides/collections/index.html">
+ * Java Collections Framework</a>.
+ *
+ * @since 1.6
+ * @author Doug Lea
+ * @param <E> the type of elements held in this collection
+ */
+public class LinkedBlockingDeque<E>
+ extends AbstractQueue<E>
+ implements BlockingDeque<E>, java.io.Serializable {
+
+ /*
+ * Implemented as a simple doubly-linked list protected by a
+ * single lock and using conditions to manage blocking.
+ *
+ * To implement weakly consistent iterators, it appears we need to
+ * keep all Nodes GC-reachable from a predecessor dequeued Node.
+ * That would cause two problems:
+ * - allow a rogue Iterator to cause unbounded memory retention
+ * - cause cross-generational linking of old Nodes to new Nodes if
+ * a Node was tenured while live, which generational GCs have a
+ * hard time dealing with, causing repeated major collections.
+ * However, only non-deleted Nodes need to be reachable from
+ * dequeued Nodes, and reachability does not necessarily have to
+ * be of the kind understood by the GC. We use the trick of
+ * linking a Node that has just been dequeued to itself. Such a
+ * self-link implicitly means to jump to "first" (for next links)
+ * or "last" (for prev links).
+ */
+
+ /*
+ * We have "diamond" multiple interface/abstract class inheritance
+ * here, and that introduces ambiguities. Often we want the
+ * BlockingDeque javadoc combined with the AbstractQueue
+ * implementation, so a lot of method specs are duplicated here.
+ */
+
+ private static final long serialVersionUID = -387911632671998426L;
+
+ /** Doubly-linked list node class */
+ static final class Node<E> {
+ /**
+ * The item, or null if this node has been removed.
+ */
+ E item;
+
+ /**
+ * One of:
+ * - the real predecessor Node
+ * - this Node, meaning the predecessor is tail
+ * - null, meaning there is no predecessor
+ */
+ Node<E> prev;
+
+ /**
+ * One of:
+ * - the real successor Node
+ * - this Node, meaning the successor is head
+ * - null, meaning there is no successor
+ */
+ Node<E> next;
+
+ Node(E x) {
+ item = x;
+ }
+ }
+
+ /**
+ * Pointer to first node.
+ * Invariant: (first == null && last == null) ||
+ * (first.prev == null && first.item != null)
+ */
+ transient Node<E> first;
+
+ /**
+ * Pointer to last node.
+ * Invariant: (first == null && last == null) ||
+ * (last.next == null && last.item != null)
+ */
+ transient Node<E> last;
+
+ /** Number of items in the deque */
+ private transient int count;
+
+ /** Maximum number of items in the deque */
+ private final int capacity;
+
+ /** Main lock guarding all access */
+ final ReentrantLock lock = new ReentrantLock();
+
+ /** Condition for waiting takes */
+ private final Condition notEmpty = lock.newCondition();
+
+ /** Condition for waiting puts */
+ private final Condition notFull = lock.newCondition();
+
+ /**
+ * Creates a {@code LinkedBlockingDeque} with a capacity of
+ * {@link Integer#MAX_VALUE}.
+ */
+ public LinkedBlockingDeque() {
+ this(Integer.MAX_VALUE);
+ }
+
+ /**
+ * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity.
+ *
+ * @param capacity the capacity of this deque
+ * @throws IllegalArgumentException if {@code capacity} is less than 1
+ */
+ public LinkedBlockingDeque(int capacity) {
+ if (capacity <= 0) throw new IllegalArgumentException();
+ this.capacity = capacity;
+ }
+
+ /**
+ * Creates a {@code LinkedBlockingDeque} with a capacity of
+ * {@link Integer#MAX_VALUE}, initially containing the elements of
+ * the given collection, added in traversal order of the
+ * collection's iterator.
+ *
+ * @param c the collection of elements to initially contain
+ * @throws NullPointerException if the specified collection or any
+ * of its elements are null
+ */
+ public LinkedBlockingDeque(Collection<? extends E> c) {
+ this(Integer.MAX_VALUE);
+ final ReentrantLock lock = this.lock;
+ lock.lock(); // Never contended, but necessary for visibility
+ try {
+ for (E e : c) {
+ if (e == null)
+ throw new NullPointerException();
+ if (!linkLast(new Node<E>(e)))
+ throw new IllegalStateException("Deque full");
+ }
+ } finally {
+ lock.unlock();
+ }
+ }
+
+
+ // Basic linking and unlinking operations, called only while holding lock
+
+ /**
+ * Links node as first element, or returns false if full.
+ */
+ private boolean linkFirst(Node<E> node) {
+ // assert lock.isHeldByCurrentThread();
+ if (count >= capacity)
+ return false;
+ Node<E> f = first;
+ node.next = f;
+ first = node;
+ if (last == null)
+ last = node;
+ else
+ f.prev = node;
+ ++count;
+ notEmpty.signal();
+ return true;
+ }
+
+ /**
+ * Links node as last element, or returns false if full.
+ */
+ private boolean linkLast(Node<E> node) {
+ // assert lock.isHeldByCurrentThread();
+ if (count >= capacity)
+ return false;
+ Node<E> l = last;
+ node.prev = l;
+ last = node;
+ if (first == null)
+ first = node;
+ else
+ l.next = node;
+ ++count;
+ notEmpty.signal();
+ return true;
+ }
+
+ /**
+ * Removes and returns first element, or null if empty.
+ */
+ private E unlinkFirst() {
+ // assert lock.isHeldByCurrentThread();
+ Node<E> f = first;
+ if (f == null)
+ return null;
+ Node<E> n = f.next;
+ E item = f.item;
+ f.item = null;
+ f.next = f; // help GC
+ first = n;
+ if (n == null)
+ last = null;
+ else
+ n.prev = null;
+ --count;
+ notFull.signal();
+ return item;
+ }
+
+ /**
+ * Removes and returns last element, or null if empty.
+ */
+ private E unlinkLast() {
+ // assert lock.isHeldByCurrentThread();
+ Node<E> l = last;
+ if (l == null)
+ return null;
+ Node<E> p = l.prev;
+ E item = l.item;
+ l.item = null;
+ l.prev = l; // help GC
+ last = p;
+ if (p == null)
+ first = null;
+ else
+ p.next = null;
+ --count;
+ notFull.signal();
+ return item;
+ }
+
+ /**
+ * Unlinks x.
+ */
+ void unlink(Node<E> x) {
+ // assert lock.isHeldByCurrentThread();
+ Node<E> p = x.prev;
+ Node<E> n = x.next;
+ if (p == null) {
+ unlinkFirst();
+ } else if (n == null) {
+ unlinkLast();
+ } else {
+ p.next = n;
+ n.prev = p;
+ x.item = null;
+ // Don't mess with x's links. They may still be in use by
+ // an iterator.
+ --count;
+ notFull.signal();
+ }
+ }
+
+ // BlockingDeque methods
+
+ /**
+ * @throws IllegalStateException {@inheritDoc}
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public void addFirst(E e) {
+ if (!offerFirst(e))
+ throw new IllegalStateException("Deque full");
+ }
+
+ /**
+ * @throws IllegalStateException {@inheritDoc}
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public void addLast(E e) {
+ if (!offerLast(e))
+ throw new IllegalStateException("Deque full");
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean offerFirst(E e) {
+ if (e == null) throw new NullPointerException();
+ Node<E> node = new Node<E>(e);
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ return linkFirst(node);
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean offerLast(E e) {
+ if (e == null) throw new NullPointerException();
+ Node<E> node = new Node<E>(e);
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ return linkLast(node);
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ * @throws InterruptedException {@inheritDoc}
+ */
+ public void putFirst(E e) throws InterruptedException {
+ if (e == null) throw new NullPointerException();
+ Node<E> node = new Node<E>(e);
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ while (!linkFirst(node))
+ notFull.await();
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ * @throws InterruptedException {@inheritDoc}
+ */
+ public void putLast(E e) throws InterruptedException {
+ if (e == null) throw new NullPointerException();
+ Node<E> node = new Node<E>(e);
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ while (!linkLast(node))
+ notFull.await();
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ * @throws InterruptedException {@inheritDoc}
+ */
+ public boolean offerFirst(E e, long timeout, TimeUnit unit)
+ throws InterruptedException {
+ if (e == null) throw new NullPointerException();
+ Node<E> node = new Node<E>(e);
+ long nanos = unit.toNanos(timeout);
+ final ReentrantLock lock = this.lock;
+ lock.lockInterruptibly();
+ try {
+ while (!linkFirst(node)) {
+ if (nanos <= 0)
+ return false;
+ nanos = notFull.awaitNanos(nanos);
+ }
+ return true;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ * @throws InterruptedException {@inheritDoc}
+ */
+ public boolean offerLast(E e, long timeout, TimeUnit unit)
+ throws InterruptedException {
+ if (e == null) throw new NullPointerException();
+ Node<E> node = new Node<E>(e);
+ long nanos = unit.toNanos(timeout);
+ final ReentrantLock lock = this.lock;
+ lock.lockInterruptibly();
+ try {
+ while (!linkLast(node)) {
+ if (nanos <= 0)
+ return false;
+ nanos = notFull.awaitNanos(nanos);
+ }
+ return true;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
+ * @throws NoSuchElementException {@inheritDoc}
+ */
+ public E removeFirst() {
+ E x = pollFirst();
+ if (x == null) throw new NoSuchElementException();
+ return x;
+ }
+
+ /**
+ * @throws NoSuchElementException {@inheritDoc}
+ */
+ public E removeLast() {
+ E x = pollLast();
+ if (x == null) throw new NoSuchElementException();
+ return x;
+ }
+
+ public E pollFirst() {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ return unlinkFirst();
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ public E pollLast() {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ return unlinkLast();
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ public E takeFirst() throws InterruptedException {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ E x;
+ while ( (x = unlinkFirst()) == null)
+ notEmpty.await();
+ return x;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ public E takeLast() throws InterruptedException {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ E x;
+ while ( (x = unlinkLast()) == null)
+ notEmpty.await();
+ return x;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ public E pollFirst(long timeout, TimeUnit unit)
+ throws InterruptedException {
+ long nanos = unit.toNanos(timeout);
+ final ReentrantLock lock = this.lock;
+ lock.lockInterruptibly();
+ try {
+ E x;
+ while ( (x = unlinkFirst()) == null) {
+ if (nanos <= 0)
+ return null;
+ nanos = notEmpty.awaitNanos(nanos);
+ }
+ return x;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ public E pollLast(long timeout, TimeUnit unit)
+ throws InterruptedException {
+ long nanos = unit.toNanos(timeout);
+ final ReentrantLock lock = this.lock;
+ lock.lockInterruptibly();
+ try {
+ E x;
+ while ( (x = unlinkLast()) == null) {
+ if (nanos <= 0)
+ return null;
+ nanos = notEmpty.awaitNanos(nanos);
+ }
+ return x;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
+ * @throws NoSuchElementException {@inheritDoc}
+ */
+ public E getFirst() {
+ E x = peekFirst();
+ if (x == null) throw new NoSuchElementException();
+ return x;
+ }
+
+ /**
+ * @throws NoSuchElementException {@inheritDoc}
+ */
+ public E getLast() {
+ E x = peekLast();
+ if (x == null) throw new NoSuchElementException();
+ return x;
+ }
+
+ public E peekFirst() {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ return (first == null) ? null : first.item;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ public E peekLast() {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ return (last == null) ? null : last.item;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ public boolean removeFirstOccurrence(Object o) {
+ if (o == null) return false;
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ for (Node<E> p = first; p != null; p = p.next) {
+ if (o.equals(p.item)) {
+ unlink(p);
+ return true;
+ }
+ }
+ return false;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ public boolean removeLastOccurrence(Object o) {
+ if (o == null) return false;
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ for (Node<E> p = last; p != null; p = p.prev) {
+ if (o.equals(p.item)) {
+ unlink(p);
+ return true;
+ }
+ }
+ return false;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ // BlockingQueue methods
+
+ /**
+ * Inserts the specified element at the end of this deque unless it would
+ * violate capacity restrictions. When using a capacity-restricted deque,
+ * it is generally preferable to use method {@link #offer(Object) offer}.
+ *
+ * <p>This method is equivalent to {@link #addLast}.
+ *
+ * @throws IllegalStateException if the element cannot be added at this
+ * time due to capacity restrictions
+ * @throws NullPointerException if the specified element is null
+ */
+ public boolean add(E e) {
+ addLast(e);
+ return true;
+ }
+
+ /**
+ * @throws NullPointerException if the specified element is null
+ */
+ public boolean offer(E e) {
+ return offerLast(e);
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ * @throws InterruptedException {@inheritDoc}
+ */
+ public void put(E e) throws InterruptedException {
+ putLast(e);
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ * @throws InterruptedException {@inheritDoc}
+ */
+ public boolean offer(E e, long timeout, TimeUnit unit)
+ throws InterruptedException {
+ return offerLast(e, timeout, unit);
+ }
+
+ /**
+ * Retrieves and removes the head of the queue represented by this deque.
+ * This method differs from {@link #poll poll} only in that it throws an
+ * exception if this deque is empty.
+ *
+ * <p>This method is equivalent to {@link #removeFirst() removeFirst}.
+ *
+ * @return the head of the queue represented by this deque
+ * @throws NoSuchElementException if this deque is empty
+ */
+ public E remove() {
+ return removeFirst();
+ }
+
+ public E poll() {
+ return pollFirst();
+ }
+
+ public E take() throws InterruptedException {
+ return takeFirst();
+ }
+
+ public E poll(long timeout, TimeUnit unit) throws InterruptedException {
+ return pollFirst(timeout, unit);
+ }
+
+ /**
+ * Retrieves, but does not remove, the head of the queue represented by
+ * this deque. This method differs from {@link #peek peek} only in that
+ * it throws an exception if this deque is empty.
+ *
+ * <p>This method is equivalent to {@link #getFirst() getFirst}.
+ *
+ * @return the head of the queue represented by this deque
+ * @throws NoSuchElementException if this deque is empty
+ */
+ public E element() {
+ return getFirst();
+ }
+
+ public E peek() {
+ return peekFirst();
+ }
+
+ /**
+ * Returns the number of additional elements that this deque can ideally
+ * (in the absence of memory or resource constraints) accept without
+ * blocking. This is always equal to the initial capacity of this deque
+ * less the current {@code size} of this deque.
+ *
+ * <p>Note that you <em>cannot</em> always tell if an attempt to insert
+ * an element will succeed by inspecting {@code remainingCapacity}
+ * because it may be the case that another thread is about to
+ * insert or remove an element.
+ */
+ public int remainingCapacity() {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ return capacity - count;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
+ * @throws UnsupportedOperationException {@inheritDoc}
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException {@inheritDoc}
+ * @throws IllegalArgumentException {@inheritDoc}
+ */
+ public int drainTo(Collection<? super E> c) {
+ return drainTo(c, Integer.MAX_VALUE);
+ }
+
+ /**
+ * @throws UnsupportedOperationException {@inheritDoc}
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException {@inheritDoc}
+ * @throws IllegalArgumentException {@inheritDoc}
+ */
+ public int drainTo(Collection<? super E> c, int maxElements) {
+ if (c == null)
+ throw new NullPointerException();
+ if (c == this)
+ throw new IllegalArgumentException();
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ int n = Math.min(maxElements, count);
+ for (int i = 0; i < n; i++) {
+ c.add(first.item); // In this order, in case add() throws.
+ unlinkFirst();
+ }
+ return n;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ // Stack methods
+
+ /**
+ * @throws IllegalStateException {@inheritDoc}
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public void push(E e) {
+ addFirst(e);
+ }
+
+ /**
+ * @throws NoSuchElementException {@inheritDoc}
+ */
+ public E pop() {
+ return removeFirst();
+ }
+
+ // Collection methods
+
+ /**
+ * Removes the first occurrence of the specified element from this deque.
+ * If the deque does not contain the element, it is unchanged.
+ * More formally, removes the first element {@code e} such that
+ * {@code o.equals(e)} (if such an element exists).
+ * Returns {@code true} if this deque contained the specified element
+ * (or equivalently, if this deque changed as a result of the call).
+ *
+ * <p>This method is equivalent to
+ * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}.
+ *
+ * @param o element to be removed from this deque, if present
+ * @return {@code true} if this deque changed as a result of the call
+ */
+ public boolean remove(Object o) {
+ return removeFirstOccurrence(o);
+ }
+
+ /**
+ * Returns the number of elements in this deque.
+ *
+ * @return the number of elements in this deque
+ */
+ public int size() {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ return count;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
+ * Returns {@code true} if this deque contains the specified element.
+ * More formally, returns {@code true} if and only if this deque contains
+ * at least one element {@code e} such that {@code o.equals(e)}.
+ *
+ * @param o object to be checked for containment in this deque
+ * @return {@code true} if this deque contains the specified element
+ */
+ public boolean contains(Object o) {
+ if (o == null) return false;
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ for (Node<E> p = first; p != null; p = p.next)
+ if (o.equals(p.item))
+ return true;
+ return false;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /*
+ * TODO: Add support for more efficient bulk operations.
+ *
+ * We don't want to acquire the lock for every iteration, but we
+ * also want other threads a chance to interact with the
+ * collection, especially when count is close to capacity.
+ */
+
+// /**
+// * Adds all of the elements in the specified collection to this
+// * queue. Attempts to addAll of a queue to itself result in
+// * {@code IllegalArgumentException}. Further, the behavior of
+// * this operation is undefined if the specified collection is
+// * modified while the operation is in progress.
+// *
+// * @param c collection containing elements to be added to this queue
+// * @return {@code true} if this queue changed as a result of the call
+// * @throws ClassCastException {@inheritDoc}
+// * @throws NullPointerException {@inheritDoc}
+// * @throws IllegalArgumentException {@inheritDoc}
+// * @throws IllegalStateException {@inheritDoc}
+// * @see #add(Object)
+// */
+// public boolean addAll(Collection<? extends E> c) {
+// if (c == null)
+// throw new NullPointerException();
+// if (c == this)
+// throw new IllegalArgumentException();
+// final ReentrantLock lock = this.lock;
+// lock.lock();
+// try {
+// boolean modified = false;
+// for (E e : c)
+// if (linkLast(e))
+// modified = true;
+// return modified;
+// } finally {
+// lock.unlock();
+// }
+// }
+
+ /**
+ * Returns an array containing all of the elements in this deque, in
+ * proper sequence (from first to last element).
+ *
+ * <p>The returned array will be "safe" in that no references to it are
+ * maintained by this deque. (In other words, this method must allocate
+ * a new array). The caller is thus free to modify the returned array.
+ *
+ * <p>This method acts as bridge between array-based and collection-based
+ * APIs.
+ *
+ * @return an array containing all of the elements in this deque
+ */
+ @SuppressWarnings("unchecked")
+ public Object[] toArray() {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ Object[] a = new Object[count];
+ int k = 0;
+ for (Node<E> p = first; p != null; p = p.next)
+ a[k++] = p.item;
+ return a;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
+ * Returns an array containing all of the elements in this deque, in
+ * proper sequence; the runtime type of the returned array is that of
+ * the specified array. If the deque fits in the specified array, it
+ * is returned therein. Otherwise, a new array is allocated with the
+ * runtime type of the specified array and the size of this deque.
+ *
+ * <p>If this deque fits in the specified array with room to spare
+ * (i.e., the array has more elements than this deque), the element in
+ * the array immediately following the end of the deque is set to
+ * {@code null}.
+ *
+ * <p>Like the {@link #toArray()} method, this method acts as bridge between
+ * array-based and collection-based APIs. Further, this method allows
+ * precise control over the runtime type of the output array, and may,
+ * under certain circumstances, be used to save allocation costs.
+ *
+ * <p>Suppose {@code x} is a deque known to contain only strings.
+ * The following code can be used to dump the deque into a newly
+ * allocated array of {@code String}:
+ *
+ * <pre>
+ * String[] y = x.toArray(new String[0]);</pre>
+ *
+ * Note that {@code toArray(new Object[0])} is identical in function to
+ * {@code toArray()}.
+ *
+ * @param a the array into which the elements of the deque are to
+ * be stored, if it is big enough; otherwise, a new array of the
+ * same runtime type is allocated for this purpose
+ * @return an array containing all of the elements in this deque
+ * @throws ArrayStoreException if the runtime type of the specified array
+ * is not a supertype of the runtime type of every element in
+ * this deque
+ * @throws NullPointerException if the specified array is null
+ */
+ @SuppressWarnings("unchecked")
+ public <T> T[] toArray(T[] a) {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ if (a.length < count)
+ a = (T[])java.lang.reflect.Array.newInstance
+ (a.getClass().getComponentType(), count);
+
+ int k = 0;
+ for (Node<E> p = first; p != null; p = p.next)
+ a[k++] = (T)p.item;
+ if (a.length > k)
+ a[k] = null;
+ return a;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ public String toString() {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ Node<E> p = first;
+ if (p == null)
+ return "[]";
+
+ StringBuilder sb = new StringBuilder();
+ sb.append('[');
+ for (;;) {
+ E e = p.item;
+ sb.append(e == this ? "(this Collection)" : e);
+ p = p.next;
+ if (p == null)
+ return sb.append(']').toString();
+ sb.append(',').append(' ');
+ }
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
+ * Atomically removes all of the elements from this deque.
+ * The deque will be empty after this call returns.
+ */
+ public void clear() {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ for (Node<E> f = first; f != null; ) {
+ f.item = null;
+ Node<E> n = f.next;
+ f.prev = null;
+ f.next = null;
+ f = n;
+ }
+ first = last = null;
+ count = 0;
+ notFull.signalAll();
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
+ * Returns an iterator over the elements in this deque in proper sequence.
+ * The elements will be returned in order from first (head) to last (tail).
+ *
+ * <p>The returned iterator is a "weakly consistent" iterator that
+ * will never throw {@link java.util.ConcurrentModificationException
+ * ConcurrentModificationException}, and guarantees to traverse
+ * elements as they existed upon construction of the iterator, and
+ * may (but is not guaranteed to) reflect any modifications
+ * subsequent to construction.
+ *
+ * @return an iterator over the elements in this deque in proper sequence
+ */
+ public Iterator<E> iterator() {
+ return new Itr();
+ }
+
+ /**
+ * Returns an iterator over the elements in this deque in reverse
+ * sequential order. The elements will be returned in order from
+ * last (tail) to first (head).
+ *
+ * <p>The returned iterator is a "weakly consistent" iterator that
+ * will never throw {@link java.util.ConcurrentModificationException
+ * ConcurrentModificationException}, and guarantees to traverse
+ * elements as they existed upon construction of the iterator, and
+ * may (but is not guaranteed to) reflect any modifications
+ * subsequent to construction.
+ *
+ * @return an iterator over the elements in this deque in reverse order
+ */
+ public Iterator<E> descendingIterator() {
+ return new DescendingItr();
+ }
+
+ /**
+ * Base class for Iterators for LinkedBlockingDeque
+ */
+ private abstract class AbstractItr implements Iterator<E> {
+ /**
+ * The next node to return in next()
+ */
+ Node<E> next;
+
+ /**
+ * nextItem holds on to item fields because once we claim that
+ * an element exists in hasNext(), we must return item read
+ * under lock (in advance()) even if it was in the process of
+ * being removed when hasNext() was called.
+ */
+ E nextItem;
+
+ /**
+ * Node returned by most recent call to next. Needed by remove.
+ * Reset to null if this element is deleted by a call to remove.
+ */
+ private Node<E> lastRet;
+
+ abstract Node<E> firstNode();
+ abstract Node<E> nextNode(Node<E> n);
+
+ AbstractItr() {
+ // set to initial position
+ final ReentrantLock lock = LinkedBlockingDeque.this.lock;
+ lock.lock();
+ try {
+ next = firstNode();
+ nextItem = (next == null) ? null : next.item;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
+ * Returns the successor node of the given non-null, but
+ * possibly previously deleted, node.
+ */
+ private Node<E> succ(Node<E> n) {
+ // Chains of deleted nodes ending in null or self-links
+ // are possible if multiple interior nodes are removed.
+ for (;;) {
+ Node<E> s = nextNode(n);
+ if (s == null)
+ return null;
+ else if (s.item != null)
+ return s;
+ else if (s == n)
+ return firstNode();
+ else
+ n = s;
+ }
+ }
+
+ /**
+ * Advances next.
+ */
+ void advance() {
+ final ReentrantLock lock = LinkedBlockingDeque.this.lock;
+ lock.lock();
+ try {
+ // assert next != null;
+ next = succ(next);
+ nextItem = (next == null) ? null : next.item;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ public boolean hasNext() {
+ return next != null;
+ }
+
+ public E next() {
+ if (next == null)
+ throw new NoSuchElementException();
+ lastRet = next;
+ E x = nextItem;
+ advance();
+ return x;
+ }
+
+ public void remove() {
+ Node<E> n = lastRet;
+ if (n == null)
+ throw new IllegalStateException();
+ lastRet = null;
+ final ReentrantLock lock = LinkedBlockingDeque.this.lock;
+ lock.lock();
+ try {
+ if (n.item != null)
+ unlink(n);
+ } finally {
+ lock.unlock();
+ }
+ }
+ }
+
+ /** Forward iterator */
+ private class Itr extends AbstractItr {
+ Node<E> firstNode() { return first; }
+ Node<E> nextNode(Node<E> n) { return n.next; }
+ }
+
+ /** Descending iterator */
+ private class DescendingItr extends AbstractItr {
+ Node<E> firstNode() { return last; }
+ Node<E> nextNode(Node<E> n) { return n.prev; }
+ }
+
+ /**
+ * Save the state of this deque to a stream (that is, serialize it).
+ *
+ * @serialData The capacity (int), followed by elements (each an
+ * {@code Object}) in the proper order, followed by a null
+ * @param s the stream
+ */
+ private void writeObject(java.io.ObjectOutputStream s)
+ throws java.io.IOException {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ // Write out capacity and any hidden stuff
+ s.defaultWriteObject();
+ // Write out all elements in the proper order.
+ for (Node<E> p = first; p != null; p = p.next)
+ s.writeObject(p.item);
+ // Use trailing null as sentinel
+ s.writeObject(null);
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
+ * Reconstitute this deque from a stream (that is,
+ * deserialize it).
+ * @param s the stream
+ */
+ private void readObject(java.io.ObjectInputStream s)
+ throws java.io.IOException, ClassNotFoundException {
+ s.defaultReadObject();
+ count = 0;
+ first = null;
+ last = null;
+ // Read in all elements and place in queue
+ for (;;) {
+ @SuppressWarnings("unchecked")
+ E item = (E)s.readObject();
+ if (item == null)
+ break;
+ add(item);
+ }
+ }
+
+}
Property changes on: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/jsr166/LinkedBlockingDeque.java
___________________________________________________________________
Added: svn:keywords
+ Id Date Revision Author HeadURL
Added: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/jsr166/LinkedBlockingQueue.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/jsr166/LinkedBlockingQueue.java (rev 0)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/jsr166/LinkedBlockingQueue.java 2011-02-17 12:56:14 UTC (rev 4205)
@@ -0,0 +1,883 @@
+/*
+ * Written by Doug Lea with assistance from members of JCP JSR-166
+ * Expert Group and released to the public domain, as explained at
+ * http://creativecommons.org/licenses/publicdomain
+ */
+
+package com.bigdata.jsr166;
+
+import java.util.AbstractQueue;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.BlockingQueue;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.locks.Condition;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * An optionally-bounded {@linkplain BlockingQueue blocking queue} based on
+ * linked nodes.
+ * This queue orders elements FIFO (first-in-first-out).
+ * The <em>head</em> of the queue is that element that has been on the
+ * queue the longest time.
+ * The <em>tail</em> of the queue is that element that has been on the
+ * queue the shortest time. New elements
+ * are inserted at the tail of the queue, and the queue retrieval
+ * operations obtain elements at the head of the queue.
+ * Linked queues typically have higher throughput than array-based queues but
+ * less predictable performance in most concurrent applications.
+ *
+ * <p> The optional capacity bound constructor argument serves as a
+ * way to prevent excessive queue expansion. The capacity, if unspecified,
+ * is equal to {@link Integer#MAX_VALUE}. Linked nodes are
+ * dynamically created upon each insertion unless this would bring the
+ * queue above capacity.
+ *
+ * <p>This class and its iterator implement all of the
+ * <em>optional</em> methods of the {@link Collection} and {@link
+ * Iterator} interfaces.
+ *
+ * <p>This class is a member of the
+ * <a href="{@docRoot}/../technotes/guides/collections/index.html">
+ * Java Collections Framework</a>.
+ *
+ * @since 1.5
+ * @author Doug Lea
+ * @param <E> the type of elements held in this collection
+ *
+ */
+public class LinkedBlockingQueue<E> extends AbstractQueue<E>
+ implements BlockingQueue<E>, java.io.Serializable {
+ private static final long serialVersionUID = -6903933977591709194L;
+
+ /*
+ * A variant of the "two lock queue" algorithm. The putLock gates
+ * entry to put (and offer), and has an associated condition for
+ * waiting puts. Similarly for the takeLock. The "count" field
+ * that they both rely on is maintained as an atomic to avoid
+ * needing to get both locks in most cases. Also, to minimize need
+ * for puts to get takeLock and vice-versa, cascading notifies are
+ * used. When a put notices that it has enabled at least one take,
+ * it signals taker. That taker in turn signals others if more
+ * items have been entered since the signal. And symmetrically for
+ * takes signalling puts. Operations such as remove(Object) and
+ * iterators acquire both locks.
+ *
+ * Visibility between writers and readers is provided as follows:
+ *
+ * Whenever an element is enqueued, the putLock is acquired and
+ * count updated. A subsequent reader guarantees visibility to the
+ * enqueued Node by either acquiring the putLock (via fullyLock)
+ * or by acquiring the takeLock, and then reading n = count.get();
+ * this gives visibility to the first n items.
+ *
+ * To implement weakly consistent iterators, it appears we need to
+ * keep all Nodes GC-reachable from a predecessor dequeued Node.
+ * That would cause two problems:
+ * - allow a rogue Iterator to cause unbounded memory retention
+ * - cause cross-generational linking of old Nodes to new Nodes if
+ * a Node was tenured while live, which generational GCs have a
+ * hard time dealing with, causing repeated major collections.
+ * However, only non-deleted Nodes need to be reachable from
+ * dequeued Nodes, and reachability does not necessarily have to
+ * be of the kind understood by the GC. We use the trick of
+ * linking a Node that has just been dequeued to itself. Such a
+ * self-link implicitly means to advance to head.next.
+ */
+
+ /**
+ * Linked list node class
+ */
+ static class Node<E> {
+ E item;
+
+ /**
+ * One of:
+ * - the real successor Node
+ * - this Node, meaning the successor is head.next
+ * - null, meaning there is no successor (this is the last node)
+ */
+ Node<E> next;
+
+ Node(E x) { item = x; }
+ }
+
+ /** The capacity bound, or Integer.MAX_VALUE if none */
+ private final int capacity;
+
+ /** Current number of elements */
+ private final AtomicInteger count = new AtomicInteger(0);
+
+ /**
+ * Head of linked list.
+ * Invariant: head.item == null
+ */
+ private transient Node<E> head;
+
+ /**
+ * Tail of linked list.
+ * Invariant: last.next == null
+ */
+ private transient Node<E> last;
+
+ /** Lock held by take, poll, etc */
+ private final ReentrantLock takeLock = new ReentrantLock();
+
+ /** Wait queue for waiting takes */
+ private final Condition notEmpty = takeLock.newCondition();
+
+ /** Lock held by put, offer, etc */
+ private final ReentrantLock putLock = new ReentrantLock();
+
+ /** Wait queue for waiting puts */
+ private final Condition notFull = putLock.newCondition();
+
+ /**
+ * Signals a waiting take. Called only from put/offer (which do not
+ * otherwise ordinarily lock takeLock.)
+ */
+ private void signalNotEmpty() {
+ final ReentrantLock takeLock = this.takeLock;
+ takeLock.lock();
+ try {
+ notEmpty.signal();
+ } finally {
+ takeLock.unlock();
+ }
+ }
+
+ /**
+ * Signals a waiting put. Called only from take/poll.
+ */
+ private void signalNotFull() {
+ final ReentrantLock putLock = this.putLock;
+ putLock.lock();
+ try {
+ notFull.signal();
+ } finally {
+ putLock.unlock();
+ }
+ }
+
+ /**
+ * Links node at end of queue.
+ *
+ * @param node the node
+ */
+ private void enqueue(Node<E> node) {
+ // assert putLock.isHeldByCurrentThread();
+ // assert last.next == null;
+ last = last.next = node;
+ }
+
+ /**
+ * Removes a node from head of queue.
+ *
+ * @return the node
+ */
+ private E dequeue() {
+ // assert takeLock.isHeldByCurrentThread();
+ // assert head.item == null;
+ Node<E> h = head;
+ Node<E> first = h.next;
+ h.next = h; // help GC
+ head = first;
+ E x = first.item;
+ first.item = null;
+ return x;
+ }
+
+ /**
+ * Lock to prevent both puts and takes.
+ */
+ void fullyLock() {
+ putLock.lock();
+ takeLock.lock();
+ }
+
+ /**
+ * Unlock to allow both puts and takes.
+ */
+ void fullyUnlock() {
+ takeLock.unlock();
+ putLock.unlock();
+ }
+
+// /**
+// * Tells whether both locks are held by current thread.
+// */
+// boolean isFullyLocked() {
+// return (putLock.isHeldByCurrentThread() &&
+// takeLock.isHeldByCurrentThread());
+// }
+
+ /**
+ * Creates a {@code LinkedBlockingQueue} with a capacity of
+ * {@link Integer#MAX_VALUE}.
+ */
+ public LinkedBlockingQueue() {
+ this(Integer.MAX_VALUE);
+ }
+
+ /**
+ * Creates a {@code LinkedBlockingQueue} with the given (fixed) capacity.
+ *
+ * @param capacity the capacity of this queue
+ * @throws IllegalArgumentException if {@code capacity} is not greater
+ * than zero
+ */
+ public LinkedBlockingQueue(int capacity) {
+ if (capacity <= 0) throw new IllegalArgumentException();
+ this.capacity = capacity;
+ last = head = new Node<E>(null);
+ }
+
+ /**
+ * Creates a {@code LinkedBlockingQueue} with a capacity of
+ * {@link Integer#MAX_VALUE}, initially containing the elements of the
+ * given collection,
+ * added in traversal order of the collection's iterator.
+ *
+ * @param c the collection of elements to initially contain
+ * @throws NullPointerException if the specified collection or any
+ * of its elements are null
+ */
+ public LinkedBlockingQueue(Collection<? extends E> c) {
+ this(Integer.MAX_VALUE);
+ final ReentrantLock putLock = this.putLock;
+ putLock.lock(); // Never contended, but necessary for visibility
+ try {
+ int n = 0;
+ for (E e : c) {
+ if (e == null)
+ throw new NullPointerException();
+ if (n == capacity)
+ throw new IllegalStateException("Queue full");
+ enqueue(new Node<E>(e));
+ ++n;
+ }
+ count.set(n);
+ } finally {
+ putLock.unlock();
+ }
+ }
+
+
+ // this doc comment is overridden to remove the reference to collections
+ // greater in size than Integer.MAX_VALUE
+ /**
+ * Returns the number of elements in this queue.
+ *
+ * @return the number of elements in this queue
+ */
+ public int size() {
+ return count.get();
+ }
+
+ // this doc comment is a modified copy of the inherited doc comment,
+ // without the reference to unlimited queues.
+ /**
+ * Returns the number of additional elements that this queue can ideally
+ * (in the absence of memory or resource constraints) accept without
+ * blocking. This is always equal to the initial capacity of this queue
+ * less the current {@code size} of this queue.
+ *
+ * <p>Note that you <em>cannot</em> always tell if an attempt to insert
+ * an element will succeed by inspecting {@code remainingCapacity}
+ * because it may be the case that another thread is about to
+ * insert or remove an element.
+ */
+ public int remainingCapacity() {
+ return capacity - count.get();
+ }
+
+ /**
+ * Inserts the specified element at the tail of this queue, waiting if
+ * necessary for space to become available.
+ *
+ * @throws InterruptedException {@inheritDoc}
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public void put(E e) throws InterruptedException {
+ if (e == null) throw new NullPointerException();
+ // Note: convention in all put/take/etc is to preset local var
+ // holding count negative to indicate failure unless set.
+ int c = -1;
+ Node<E> node = new Node(e);
+ final ReentrantLock putLock = this.putLock;
+ final AtomicInteger count = this.count;
+ putLock.lockInterruptibly();
+ try {
+ /*
+ * Note that count is used in wait guard even though it is
+ * not protected by lock. This works because count can
+ * only decrease at this point (all other puts are shut
+ * out by lock), and we (or some other waiting put) are
+ * signalled if it ever changes from capacity. Similarly
+ * for all other uses of count in other wait guards.
+ */
+ while (count.get() == capacity) {
+ notFull.await();
+ }
+ enqueue(node);
+ c = count.getAndIncrement();
+ if (c + 1 < capacity)
+ notFull.signal();
+ } finally {
+ putLock.unlock();
+ }
+ if (c == 0)
+ signalNotEmpty();
+ }
+
+ /**
+ * Inserts the specified element at the tail of this queue, waiting if
+ * necessary up to the specified wait time for space to become available.
+ *
+ * @return {@code true} if successful, or {@code false} if
+ * the specified waiting time elapses before space is available.
+ * @throws InterruptedException {@inheritDoc}
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean offer(E e, long timeout, TimeUnit unit)
+ throws InterruptedException {
+
+ if (e == null) throw new NullPointerException();
+ long nanos = unit.toNanos(timeout);
+ int c = -1;
+ final ReentrantLock putLock = this.putLock;
+ final AtomicInteger count = this.count;
+ putLock.lockInterruptibly();
+ try {
+ while (count.get() == capacity) {
+ if (nanos <= 0)
+ return false;
+ nanos = notFull.awaitNanos(nanos);
+ }
+ enqueue(new Node<E>(e));
+ c = count.getAndIncrement();
+ if (c + 1 < capacity)
+ notFull.signal();
+ } finally {
+ putLock.unlock();
+ }
+ if (c == 0)
+ signalNotEmpty();
+ return true;
+ }
+
+ /**
+ * Inserts the specified element at the tail of this queue if it is
+ * possible to do so immediately without exceeding the queue's capacity,
+ * returning {@code true} upon success and {@code false} if this queue
+ * is full.
+ * When using a capacity-restricted queue, this method is generally
+ * preferable to method {@link BlockingQueue#add add}, which can fail to
+ * insert an element only by throwing an exception.
+ *
+ * @throws NullPointerException if the specified element is null
+ */
+ public boolean offer(E e) {
+ if (e == null) throw new NullPointerException();
+ final AtomicInteger count = this.count;
+ if (count.get() == capacity)
+ return false;
+ int c = -1;
+ Node<E> node = new Node(e);
+ final ReentrantLock putLock = this.putLock;
+ putLock.lock();
+ try {
+ if (count.get() < capacity) {
+ enqueue(node);
+ c = count.getAndIncrement();
+ if (c + 1 < capacity)
+ notFull.signal();
+ }
+ } finally {
+ putLock.unlock();
+ }
+ if (c == 0)
+ signalNotEmpty();
+ return c >= 0;
+ }
+
+
+ public E take() throws InterruptedException {
+ E x;
+ int c = -1;
+ final AtomicInteger count = this.count;
+ final ReentrantLock takeLock = this.takeLock;
+ takeLock.lockInterruptibly();
+ try {
+ while (count.get() == 0) {
+ notEmpty.await();
+ }
+ x = dequeue();
+ c = count.getAndDecrement();
+ if (c > 1)
+ notEmpty.signal();
+ } finally {
+ takeLock.unlock();
+ }
+ if (c == capacity)
+ signalNotFull();
+ return x;
+ }
+
+ public E poll(long timeout, TimeUnit unit) throws InterruptedException {
+ E x = null;
+ int c = -1;
+ long nanos = unit.toNanos(timeout);
+ final AtomicInteger count = this.count;
+ final ReentrantLock takeLock = this.takeLock;
+ takeLock.lockInterruptibly();
+ try {
+ while (count.get() == 0) {
+ if (nanos <= 0)
+ return null;
+ nanos = notEmpty.awaitNanos(nanos);
+ }
+ x = dequeue();
+ c = count.getAndDecrement();
+ if (c > 1)
+ notEmpty.signal();
+ } finally {
+ takeLock.unlock();
+ }
+ if (c == capacity)
+ signalNotFull();
+ return x;
+ }
+
+ public E poll() {
+ final AtomicInteger count = this.count;
+ if (count.get() == 0)
+ return null;
+ E x = null;
+ int c = -1;
+ final ReentrantLock takeLock = this.takeLock;
+ takeLock.lock();
+ try {
+ if (count.get() > 0) {
+ x = dequeue();
+ c = count.getAndDecrement();
+ if (c > 1)
+ notEmpty.signal();
+ }
+ } finally {
+ takeLock.unlock();
+ }
+ if (c == capacity)
+ signalNotFull();
+ return x;
+ }
+
+ public E peek() {
+ if (count.get() == 0)
+ return null;
+ final ReentrantLock takeLock = this.takeLock;
+ takeLock.lock();
+ try {
+ Node<E> first = head.next;
+ if (first == null)
+ return null;
+ else
+ return first.item;
+ } finally {
+ takeLock.unlock();
+ }
+ }
+
+ /**
+ * Unlinks interior Node p with predecessor trail.
+ */
+ void unlink(Node<E> p, Node<E> trail) {
+ // assert isFullyLocked();
+ // p.next is not changed, to allow iterators that are
+ // traversing p to maintain their weak-consistency guarantee.
+ p.item = null;
+ trail.next = p.next;
+ if (last == p)
+ last = trail;
+ if (count.getAndDecrement() == capacity)
+ notFull.signal();
+ }
+
+ /**
+ * Removes a single instance of the specified element from this queue,
+ * if it is present. More formally, removes an element {@code e} such
+ * that {@code o.equals(e)}, if this queue contains one or more such
+ * elements.
+ * Returns {@code true} if this queue contained the specified element
+ * (or equivalently, if this queue changed as a result of the call).
+ *
+ * @param o element to be removed from this queue, if present
+ * @return {@code true} if this queue changed as a result of the call
+ */
+ public boolean remove(Object o) {
+ if (o == null) return false;
+ fullyLock();
+ try {
+ for (Node<E> trail = head, p = trail.next;
+ p != null;
+ trail = p, p = p.next) {
+ if (o.equals(p.item)) {
+ unlink(p, trail);
+ return true;
+ }
+ }
+ return false;
+ } finally {
+ fullyUnlock();
+ }
+ }
+
+ /**
+ * Returns {@code true} if this queue contains the specified element.
+ * More formally, returns {@code true} if and only if this queue contains
+ * at least one element {@code e} such that {@code o.equals(e)}.
+ *
+ * @param o object to be checked for containment in this queue
+ * @return {@code true} if this queue contains the specified element
+ */
+ public boolean contains(Object o) {
+ if (o == null) return false;
+ fullyLock();
+ try {
+ for (Node<E> p = head.next; p != null; p = p.next)
+ if (o.equals(p.item))
+ return true;
+ return false;
+ } finally {
+ fullyUnlock();
+ }
+ }
+
+ /**
+ * Returns an array containing all of the elements in this queue, in
+ * proper sequence.
+ *
+ * <p>The returned array will be "safe" in that no references to it are
+ * maintained by this queue. (In other words, this method must allocate
+ * a new array). The caller is thus free to modify the returned array.
+ *
+ * <p>This method acts as bridge between array-based and collection-based
+ * APIs.
+ *
+ * @return an array containing all of the elements in this queue
+ */
+ public Object[] toArray() {
+ fullyLock();
+ try {
+ int size = count.get();
+ Object[] a = new Object[size];
+ int k = 0;
+ for (Node<E> p = head.next; p != null; p = p.next)
+ a[k++] = p.item;
+ return a;
+ } finally {
+ fullyUnlock();
+ }
+ }
+
+ /**
+ * Returns an array containing all of the elements in this queue, in
+ * proper sequence; the runtime type of the returned array is that of
+ * the specified array. If the queue fits in the specified array, it
+ * is returned therein. Otherwise, a new array is allocated with the
+ * runtime type of the specified array and the size of this queue.
+ *
+ * <p>If this queue fits in the specified array with room to spare
+ * (i.e., the array has more elements than this queue), the element in
+ * the array immediately following the end of the queue is set to
+ * {@code null}.
+ *
+ * <p>Like the {@link #t...
[truncated message content] |
