src/share/classes/java/util/concurrent/LinkedBlockingDeque.java
Print this page
*** 124,137 ****
* - this Node, meaning the successor is head
* - null, meaning there is no successor
*/
Node<E> next;
! Node(E x, Node<E> p, Node<E> n) {
item = x;
- prev = p;
- next = n;
}
}
/**
* Pointer to first node.
--- 124,135 ----
* - 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.
*** 197,207 ****
lock.lock(); // Never contended, but necessary for visibility
try {
for (E e : c) {
if (e == null)
throw new NullPointerException();
! if (!linkLast(e))
throw new IllegalStateException("Deque full");
}
} finally {
lock.unlock();
}
--- 195,205 ----
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();
}
*** 209,250 ****
// Basic linking and unlinking operations, called only while holding lock
/**
! * Links e as first element, or returns false if full.
*/
! private boolean linkFirst(E e) {
// assert lock.isHeldByCurrentThread();
if (count >= capacity)
return false;
Node<E> f = first;
! Node<E> x = new Node<E>(e, null, f);
! first = x;
if (last == null)
! last = x;
else
! f.prev = x;
++count;
notEmpty.signal();
return true;
}
/**
! * Links e as last element, or returns false if full.
*/
! private boolean linkLast(E e) {
// assert lock.isHeldByCurrentThread();
if (count >= capacity)
return false;
Node<E> l = last;
! Node<E> x = new Node<E>(e, l, null);
! last = x;
if (first == null)
! first = x;
else
! l.next = x;
++count;
notEmpty.signal();
return true;
}
--- 207,248 ----
// 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;
}
*** 337,350 ****
/**
* @throws NullPointerException {@inheritDoc}
*/
public boolean offerFirst(E e) {
if (e == null) throw new NullPointerException();
final ReentrantLock lock = this.lock;
lock.lock();
try {
! return linkFirst(e);
} finally {
lock.unlock();
}
}
--- 335,349 ----
/**
* @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();
}
}
*** 351,364 ****
/**
* @throws NullPointerException {@inheritDoc}
*/
public boolean offerLast(E e) {
if (e == null) throw new NullPointerException();
final ReentrantLock lock = this.lock;
lock.lock();
try {
! return linkLast(e);
} finally {
lock.unlock();
}
}
--- 350,364 ----
/**
* @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();
}
}
*** 366,379 ****
* @throws NullPointerException {@inheritDoc}
* @throws InterruptedException {@inheritDoc}
*/
public void putFirst(E e) throws InterruptedException {
if (e == null) throw new NullPointerException();
final ReentrantLock lock = this.lock;
lock.lock();
try {
! while (!linkFirst(e))
notFull.await();
} finally {
lock.unlock();
}
}
--- 366,380 ----
* @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();
}
}
*** 382,395 ****
* @throws NullPointerException {@inheritDoc}
* @throws InterruptedException {@inheritDoc}
*/
public void putLast(E e) throws InterruptedException {
if (e == null) throw new NullPointerException();
final ReentrantLock lock = this.lock;
lock.lock();
try {
! while (!linkLast(e))
notFull.await();
} finally {
lock.unlock();
}
}
--- 383,397 ----
* @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();
}
}
*** 399,413 ****
* @throws InterruptedException {@inheritDoc}
*/
public boolean offerFirst(E e, long timeout, TimeUnit unit)
throws InterruptedException {
if (e == null) throw new NullPointerException();
long nanos = unit.toNanos(timeout);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
! while (!linkFirst(e)) {
if (nanos <= 0)
return false;
nanos = notFull.awaitNanos(nanos);
}
return true;
--- 401,416 ----
* @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;
*** 421,435 ****
* @throws InterruptedException {@inheritDoc}
*/
public boolean offerLast(E e, long timeout, TimeUnit unit)
throws InterruptedException {
if (e == null) throw new NullPointerException();
long nanos = unit.toNanos(timeout);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
! while (!linkLast(e)) {
if (nanos <= 0)
return false;
nanos = notFull.awaitNanos(nanos);
}
return true;
--- 424,439 ----
* @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;
*** 953,963 ****
public String toString() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
! return super.toString();
} finally {
lock.unlock();
}
}
--- 957,980 ----
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();
}
}
*** 1052,1078 ****
lock.unlock();
}
}
/**
* Advances next.
*/
void advance() {
final ReentrantLock lock = LinkedBlockingDeque.this.lock;
lock.lock();
try {
// assert next != null;
! Node<E> s = nextNode(next);
! if (s == next) {
! next = firstNode();
! } else {
! // Skip over removed nodes.
! // May be necessary if multiple interior Nodes are removed.
! while (s != null && s.item == null)
! s = nextNode(s);
! next = s;
! }
nextItem = (next == null) ? null : next.item;
} finally {
lock.unlock();
}
}
--- 1069,1106 ----
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();
}
}