8011427: java.util.concurrent collection Spliterator implementations
Reviewed-by: martin
Contributed-by: Doug Lea <dl@cs.oswego.edu>
--- a/jdk/src/share/classes/java/util/concurrent/ArrayBlockingQueue.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/ArrayBlockingQueue.java Wed Jul 03 11:58:09 2013 +0200
@@ -34,8 +34,15 @@
*/
package java.util.concurrent;
-import java.util.concurrent.locks.*;
-import java.util.*;
+import java.util.concurrent.locks.Condition;
+import java.util.concurrent.locks.ReentrantLock;
+import java.util.AbstractQueue;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.lang.ref.WeakReference;
+import java.util.Spliterators;
+import java.util.Spliterator;
/**
* A bounded {@linkplain BlockingQueue blocking queue} backed by an
@@ -102,19 +109,21 @@
/** Main lock guarding all access */
final ReentrantLock lock;
+
/** Condition for waiting takes */
private final Condition notEmpty;
+
/** Condition for waiting puts */
private final Condition notFull;
- // Internal helper methods
+ /**
+ * Shared state for currently active iterators, or null if there
+ * are known not to be any. Allows queue operations to update
+ * iterator state.
+ */
+ transient Itrs itrs = null;
- /**
- * Circularly increment i.
- */
- final int inc(int i) {
- return (++i == items.length) ? 0 : i;
- }
+ // Internal helper methods
/**
* Circularly decrement i.
@@ -123,11 +132,6 @@
return ((i == 0) ? items.length : i) - 1;
}
- @SuppressWarnings("unchecked")
- static <E> E cast(Object item) {
- return (E) item;
- }
-
/**
* Returns item at index i.
*/
@@ -150,10 +154,14 @@
* Inserts element at current put position, advances, and signals.
* Call only when holding lock.
*/
- private void insert(E x) {
+ private void enqueue(E x) {
+ // assert lock.getHoldCount() == 1;
+ // assert items[putIndex] == null;
+ final Object[] items = this.items;
items[putIndex] = x;
- putIndex = inc(putIndex);
- ++count;
+ if (++putIndex == items.length)
+ putIndex = 0;
+ count++;
notEmpty.signal();
}
@@ -161,43 +169,62 @@
* Extracts element at current take position, advances, and signals.
* Call only when holding lock.
*/
- private E extract() {
+ private E dequeue() {
+ // assert lock.getHoldCount() == 1;
+ // assert items[takeIndex] != null;
final Object[] items = this.items;
@SuppressWarnings("unchecked")
E x = (E) items[takeIndex];
items[takeIndex] = null;
- takeIndex = inc(takeIndex);
- --count;
+ if (++takeIndex == items.length)
+ takeIndex = 0;
+ count--;
+ if (itrs != null)
+ itrs.elementDequeued();
notFull.signal();
return x;
}
/**
- * Deletes item at position i.
- * Utility for remove and iterator.remove.
+ * Deletes item at array index removeIndex.
+ * Utility for remove(Object) and iterator.remove.
* Call only when holding lock.
*/
- void removeAt(int i) {
+ void removeAt(final int removeIndex) {
+ // assert lock.getHoldCount() == 1;
+ // assert items[removeIndex] != null;
+ // assert removeIndex >= 0 && removeIndex < items.length;
final Object[] items = this.items;
- // if removing front item, just advance
- if (i == takeIndex) {
+ if (removeIndex == takeIndex) {
+ // removing front item; just advance
items[takeIndex] = null;
- takeIndex = inc(takeIndex);
+ if (++takeIndex == items.length)
+ takeIndex = 0;
+ count--;
+ if (itrs != null)
+ itrs.elementDequeued();
} else {
+ // an "interior" remove
+
// slide over all others up through putIndex.
- for (;;) {
- int nexti = inc(i);
- if (nexti != putIndex) {
- items[i] = items[nexti];
- i = nexti;
+ final int putIndex = this.putIndex;
+ for (int i = removeIndex;;) {
+ int next = i + 1;
+ if (next == items.length)
+ next = 0;
+ if (next != putIndex) {
+ items[i] = items[next];
+ i = next;
} else {
items[i] = null;
- putIndex = i;
+ this.putIndex = i;
break;
}
}
+ count--;
+ if (itrs != null)
+ itrs.removedAt(removeIndex);
}
- --count;
notFull.signal();
}
@@ -302,7 +329,7 @@
if (count == items.length)
return false;
else {
- insert(e);
+ enqueue(e);
return true;
}
} finally {
@@ -324,7 +351,7 @@
try {
while (count == items.length)
notFull.await();
- insert(e);
+ enqueue(e);
} finally {
lock.unlock();
}
@@ -351,7 +378,7 @@
return false;
nanos = notFull.awaitNanos(nanos);
}
- insert(e);
+ enqueue(e);
return true;
} finally {
lock.unlock();
@@ -362,7 +389,7 @@
final ReentrantLock lock = this.lock;
lock.lock();
try {
- return (count == 0) ? null : extract();
+ return (count == 0) ? null : dequeue();
} finally {
lock.unlock();
}
@@ -374,7 +401,7 @@
try {
while (count == 0)
notEmpty.await();
- return extract();
+ return dequeue();
} finally {
lock.unlock();
}
@@ -390,7 +417,7 @@
return null;
nanos = notEmpty.awaitNanos(nanos);
}
- return extract();
+ return dequeue();
} finally {
lock.unlock();
}
@@ -400,7 +427,7 @@
final ReentrantLock lock = this.lock;
lock.lock();
try {
- return (count == 0) ? null : itemAt(takeIndex);
+ return itemAt(takeIndex); // null when queue is empty
} finally {
lock.unlock();
}
@@ -469,11 +496,17 @@
final ReentrantLock lock = this.lock;
lock.lock();
try {
- for (int i = takeIndex, k = count; k > 0; i = inc(i), k--) {
- if (o.equals(items[i])) {
- removeAt(i);
- return true;
- }
+ if (count > 0) {
+ final int putIndex = this.putIndex;
+ int i = takeIndex;
+ do {
+ if (o.equals(items[i])) {
+ removeAt(i);
+ return true;
+ }
+ if (++i == items.length)
+ i = 0;
+ } while (i != putIndex);
}
return false;
} finally {
@@ -495,9 +528,16 @@
final ReentrantLock lock = this.lock;
lock.lock();
try {
- for (int i = takeIndex, k = count; k > 0; i = inc(i), k--)
- if (o.equals(items[i]))
- return true;
+ if (count > 0) {
+ final int putIndex = this.putIndex;
+ int i = takeIndex;
+ do {
+ if (o.equals(items[i]))
+ return true;
+ if (++i == items.length)
+ i = 0;
+ } while (i != putIndex);
+ }
return false;
} finally {
lock.unlock();
@@ -518,18 +558,23 @@
* @return an array containing all of the elements in this queue
*/
public Object[] toArray() {
- final Object[] items = this.items;
+ Object[] a;
final ReentrantLock lock = this.lock;
lock.lock();
try {
final int count = this.count;
- Object[] a = new Object[count];
- for (int i = takeIndex, k = 0; k < count; i = inc(i), k++)
- a[k] = items[i];
- return a;
+ a = new Object[count];
+ int n = items.length - takeIndex;
+ if (count <= n)
+ System.arraycopy(items, takeIndex, a, 0, count);
+ else {
+ System.arraycopy(items, takeIndex, a, 0, n);
+ System.arraycopy(items, 0, a, n, count - n);
+ }
} finally {
lock.unlock();
}
+ return a;
}
/**
@@ -553,8 +598,7 @@
* The following code can be used to dump the queue into a newly
* allocated array of {@code String}:
*
- * <pre>
- * String[] y = x.toArray(new String[0]);</pre>
+ * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
*
* Note that {@code toArray(new Object[0])} is identical in function to
* {@code toArray()}.
@@ -579,14 +623,19 @@
if (len < count)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), count);
- for (int i = takeIndex, k = 0; k < count; i = inc(i), k++)
- a[k] = (T) items[i];
+ int n = items.length - takeIndex;
+ if (count <= n)
+ System.arraycopy(items, takeIndex, a, 0, count);
+ else {
+ System.arraycopy(items, takeIndex, a, 0, n);
+ System.arraycopy(items, 0, a, n, count - n);
+ }
if (len > count)
a[count] = null;
- return a;
} finally {
lock.unlock();
}
+ return a;
}
public String toString() {
@@ -597,14 +646,17 @@
if (k == 0)
return "[]";
+ final Object[] items = this.items;
StringBuilder sb = new StringBuilder();
sb.append('[');
- for (int i = takeIndex; ; i = inc(i)) {
+ for (int i = takeIndex; ; ) {
Object e = items[i];
sb.append(e == this ? "(this Collection)" : e);
if (--k == 0)
return sb.append(']').toString();
sb.append(',').append(' ');
+ if (++i == items.length)
+ i = 0;
}
} finally {
lock.unlock();
@@ -620,12 +672,22 @@
final ReentrantLock lock = this.lock;
lock.lock();
try {
- for (int i = takeIndex, k = count; k > 0; i = inc(i), k--)
- items[i] = null;
- count = 0;
- putIndex = 0;
- takeIndex = 0;
- notFull.signalAll();
+ int k = count;
+ if (k > 0) {
+ final int putIndex = this.putIndex;
+ int i = takeIndex;
+ do {
+ items[i] = null;
+ if (++i == items.length)
+ i = 0;
+ } while (i != putIndex);
+ takeIndex = putIndex;
+ count = 0;
+ if (itrs != null)
+ itrs.queueIsEmpty();
+ for (; k > 0 && lock.hasWaiters(notFull); k--)
+ notFull.signal();
+ }
} finally {
lock.unlock();
}
@@ -638,34 +700,7 @@
* @throws IllegalArgumentException {@inheritDoc}
*/
public int drainTo(Collection<? super E> c) {
- checkNotNull(c);
- if (c == this)
- throw new IllegalArgumentException();
- final Object[] items = this.items;
- final ReentrantLock lock = this.lock;
- lock.lock();
- try {
- int i = takeIndex;
- int n = 0;
- int max = count;
- while (n < max) {
- @SuppressWarnings("unchecked")
- E x = (E) items[i];
- c.add(x);
- items[i] = null;
- i = inc(i);
- ++n;
- }
- if (n > 0) {
- count = 0;
- putIndex = 0;
- takeIndex = 0;
- notFull.signalAll();
- }
- return n;
- } finally {
- lock.unlock();
- }
+ return drainTo(c, Integer.MAX_VALUE);
}
/**
@@ -684,23 +719,35 @@
final ReentrantLock lock = this.lock;
lock.lock();
try {
- int i = takeIndex;
- int n = 0;
- int max = (maxElements < count) ? maxElements : count;
- while (n < max) {
- @SuppressWarnings("unchecked")
- E x = (E) items[i];
- c.add(x);
- items[i] = null;
- i = inc(i);
- ++n;
+ int n = Math.min(maxElements, count);
+ int take = takeIndex;
+ int i = 0;
+ try {
+ while (i < n) {
+ @SuppressWarnings("unchecked")
+ E x = (E) items[take];
+ c.add(x);
+ items[take] = null;
+ if (++take == items.length)
+ take = 0;
+ i++;
+ }
+ return n;
+ } finally {
+ // Restore invariants even if c.add() threw
+ if (i > 0) {
+ count -= i;
+ takeIndex = take;
+ if (itrs != null) {
+ if (count == 0)
+ itrs.queueIsEmpty();
+ else if (i > take)
+ itrs.takeIndexWrapped();
+ }
+ for (; i > 0 && lock.hasWaiters(notFull); i--)
+ notFull.signal();
+ }
}
- if (n > 0) {
- count -= n;
- takeIndex = i;
- notFull.signalAll();
- }
- return n;
} finally {
lock.unlock();
}
@@ -710,12 +757,12 @@
* Returns an iterator over the elements in this queue in proper sequence.
* The elements will be returned in order from first (head) to last (tail).
*
- * <p>The returned {@code Iterator} is a "weakly consistent" iterator that
+ * <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.
+ * 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 queue in proper sequence
*/
@@ -724,88 +771,634 @@
}
/**
- * Iterator for ArrayBlockingQueue. To maintain weak consistency
- * with respect to puts and takes, we (1) read ahead one slot, so
- * as to not report hasNext true but then not have an element to
- * return -- however we later recheck this slot to use the most
- * current value; (2) ensure that each array slot is traversed at
- * most once (by tracking "remaining" elements); (3) skip over
- * null slots, which can occur if takes race ahead of iterators.
- * However, for circular array-based queues, we cannot rely on any
- * well established definition of what it means to be weakly
- * consistent with respect to interior removes since these may
- * require slot overwrites in the process of sliding elements to
- * cover gaps. So we settle for resiliency, operating on
- * established apparent nexts, which may miss some elements that
- * have moved between calls to next.
+ * Shared data between iterators and their queue, allowing queue
+ * modifications to update iterators when elements are removed.
+ *
+ * This adds a lot of complexity for the sake of correctly
+ * handling some uncommon operations, but the combination of
+ * circular-arrays and supporting interior removes (i.e., those
+ * not at head) would cause iterators to sometimes lose their
+ * places and/or (re)report elements they shouldn't. To avoid
+ * this, when a queue has one or more iterators, it keeps iterator
+ * state consistent by:
+ *
+ * (1) keeping track of the number of "cycles", that is, the
+ * number of times takeIndex has wrapped around to 0.
+ * (2) notifying all iterators via the callback removedAt whenever
+ * an interior element is removed (and thus other elements may
+ * be shifted).
+ *
+ * These suffice to eliminate iterator inconsistencies, but
+ * unfortunately add the secondary responsibility of maintaining
+ * the list of iterators. We track all active iterators in a
+ * simple linked list (accessed only when the queue's lock is
+ * held) of weak references to Itr. The list is cleaned up using
+ * 3 different mechanisms:
+ *
+ * (1) Whenever a new iterator is created, do some O(1) checking for
+ * stale list elements.
+ *
+ * (2) Whenever takeIndex wraps around to 0, check for iterators
+ * that have been unused for more than one wrap-around cycle.
+ *
+ * (3) Whenever the queue becomes empty, all iterators are notified
+ * and this entire data structure is discarded.
+ *
+ * So in addition to the removedAt callback that is necessary for
+ * correctness, iterators have the shutdown and takeIndexWrapped
+ * callbacks that help remove stale iterators from the list.
+ *
+ * Whenever a list element is examined, it is expunged if either
+ * the GC has determined that the iterator is discarded, or if the
+ * iterator reports that it is "detached" (does not need any
+ * further state updates). Overhead is maximal when takeIndex
+ * never advances, iterators are discarded before they are
+ * exhausted, and all removals are interior removes, in which case
+ * all stale iterators are discovered by the GC. But even in this
+ * case we don't increase the amortized complexity.
+ *
+ * Care must be taken to keep list sweeping methods from
+ * reentrantly invoking another such method, causing subtle
+ * corruption bugs.
+ */
+ class Itrs {
+
+ /**
+ * Node in a linked list of weak iterator references.
+ */
+ private class Node extends WeakReference<Itr> {
+ Node next;
+
+ Node(Itr iterator, Node next) {
+ super(iterator);
+ this.next = next;
+ }
+ }
+
+ /** Incremented whenever takeIndex wraps around to 0 */
+ int cycles = 0;
+
+ /** Linked list of weak iterator references */
+ private Node head;
+
+ /** Used to expunge stale iterators */
+ private Node sweeper = null;
+
+ private static final int SHORT_SWEEP_PROBES = 4;
+ private static final int LONG_SWEEP_PROBES = 16;
+
+ Itrs(Itr initial) {
+ register(initial);
+ }
+
+ /**
+ * Sweeps itrs, looking for and expunging stale iterators.
+ * If at least one was found, tries harder to find more.
+ * Called only from iterating thread.
+ *
+ * @param tryHarder whether to start in try-harder mode, because
+ * there is known to be at least one iterator to collect
+ */
+ void doSomeSweeping(boolean tryHarder) {
+ // assert lock.getHoldCount() == 1;
+ // assert head != null;
+ int probes = tryHarder ? LONG_SWEEP_PROBES : SHORT_SWEEP_PROBES;
+ Node o, p;
+ final Node sweeper = this.sweeper;
+ boolean passedGo; // to limit search to one full sweep
+
+ if (sweeper == null) {
+ o = null;
+ p = head;
+ passedGo = true;
+ } else {
+ o = sweeper;
+ p = o.next;
+ passedGo = false;
+ }
+
+ for (; probes > 0; probes--) {
+ if (p == null) {
+ if (passedGo)
+ break;
+ o = null;
+ p = head;
+ passedGo = true;
+ }
+ final Itr it = p.get();
+ final Node next = p.next;
+ if (it == null || it.isDetached()) {
+ // found a discarded/exhausted iterator
+ probes = LONG_SWEEP_PROBES; // "try harder"
+ // unlink p
+ p.clear();
+ p.next = null;
+ if (o == null) {
+ head = next;
+ if (next == null) {
+ // We've run out of iterators to track; retire
+ itrs = null;
+ return;
+ }
+ }
+ else
+ o.next = next;
+ } else {
+ o = p;
+ }
+ p = next;
+ }
+
+ this.sweeper = (p == null) ? null : o;
+ }
+
+ /**
+ * Adds a new iterator to the linked list of tracked iterators.
+ */
+ void register(Itr itr) {
+ // assert lock.getHoldCount() == 1;
+ head = new Node(itr, head);
+ }
+
+ /**
+ * Called whenever takeIndex wraps around to 0.
+ *
+ * Notifies all iterators, and expunges any that are now stale.
+ */
+ void takeIndexWrapped() {
+ // assert lock.getHoldCount() == 1;
+ cycles++;
+ for (Node o = null, p = head; p != null;) {
+ final Itr it = p.get();
+ final Node next = p.next;
+ if (it == null || it.takeIndexWrapped()) {
+ // unlink p
+ // assert it == null || it.isDetached();
+ p.clear();
+ p.next = null;
+ if (o == null)
+ head = next;
+ else
+ o.next = next;
+ } else {
+ o = p;
+ }
+ p = next;
+ }
+ if (head == null) // no more iterators to track
+ itrs = null;
+ }
+
+ /**
+ * Called whenever an interior remove (not at takeIndex) occured.
+ *
+ * Notifies all iterators, and expunges any that are now stale.
+ */
+ void removedAt(int removedIndex) {
+ for (Node o = null, p = head; p != null;) {
+ final Itr it = p.get();
+ final Node next = p.next;
+ if (it == null || it.removedAt(removedIndex)) {
+ // unlink p
+ // assert it == null || it.isDetached();
+ p.clear();
+ p.next = null;
+ if (o == null)
+ head = next;
+ else
+ o.next = next;
+ } else {
+ o = p;
+ }
+ p = next;
+ }
+ if (head == null) // no more iterators to track
+ itrs = null;
+ }
+
+ /**
+ * Called whenever the queue becomes empty.
+ *
+ * Notifies all active iterators that the queue is empty,
+ * clears all weak refs, and unlinks the itrs datastructure.
+ */
+ void queueIsEmpty() {
+ // assert lock.getHoldCount() == 1;
+ for (Node p = head; p != null; p = p.next) {
+ Itr it = p.get();
+ if (it != null) {
+ p.clear();
+ it.shutdown();
+ }
+ }
+ head = null;
+ itrs = null;
+ }
+
+ /**
+ * Called whenever an element has been dequeued (at takeIndex).
+ */
+ void elementDequeued() {
+ // assert lock.getHoldCount() == 1;
+ if (count == 0)
+ queueIsEmpty();
+ else if (takeIndex == 0)
+ takeIndexWrapped();
+ }
+ }
+
+ /**
+ * Iterator for ArrayBlockingQueue.
+ *
+ * To maintain weak consistency with respect to puts and takes, we
+ * read ahead one slot, so as to not report hasNext true but then
+ * not have an element to return.
+ *
+ * We switch into "detached" mode (allowing prompt unlinking from
+ * itrs without help from the GC) when all indices are negative, or
+ * when hasNext returns false for the first time. This allows the
+ * iterator to track concurrent updates completely accurately,
+ * except for the corner case of the user calling Iterator.remove()
+ * after hasNext() returned false. Even in this case, we ensure
+ * that we don't remove the wrong element by keeping track of the
+ * expected element to remove, in lastItem. Yes, we may fail to
+ * remove lastItem from the queue if it moved due to an interleaved
+ * interior remove while in detached mode.
*/
private class Itr implements Iterator<E> {
- private int remaining; // Number of elements yet to be returned
- private int nextIndex; // Index of element to be returned by next
- private E nextItem; // Element to be returned by next call to next
- private E lastItem; // Element returned by last call to next
- private int lastRet; // Index of last element returned, or -1 if none
+ /** Index to look for new nextItem; NONE at end */
+ private int cursor;
+
+ /** Element to be returned by next call to next(); null if none */
+ private E nextItem;
+
+ /** Index of nextItem; NONE if none, REMOVED if removed elsewhere */
+ private int nextIndex;
+
+ /** Last element returned; null if none or not detached. */
+ private E lastItem;
+
+ /** Index of lastItem, NONE if none, REMOVED if removed elsewhere */
+ private int lastRet;
+
+ /** Previous value of takeIndex, or DETACHED when detached */
+ private int prevTakeIndex;
+
+ /** Previous value of iters.cycles */
+ private int prevCycles;
+
+ /** Special index value indicating "not available" or "undefined" */
+ private static final int NONE = -1;
+
+ /**
+ * Special index value indicating "removed elsewhere", that is,
+ * removed by some operation other than a call to this.remove().
+ */
+ private static final int REMOVED = -2;
+
+ /** Special value for prevTakeIndex indicating "detached mode" */
+ private static final int DETACHED = -3;
Itr() {
+ // assert lock.getHoldCount() == 0;
+ lastRet = NONE;
final ReentrantLock lock = ArrayBlockingQueue.this.lock;
lock.lock();
try {
- lastRet = -1;
- if ((remaining = count) > 0)
+ if (count == 0) {
+ // assert itrs == null;
+ cursor = NONE;
+ nextIndex = NONE;
+ prevTakeIndex = DETACHED;
+ } else {
+ final int takeIndex = ArrayBlockingQueue.this.takeIndex;
+ prevTakeIndex = takeIndex;
nextItem = itemAt(nextIndex = takeIndex);
+ cursor = incCursor(takeIndex);
+ if (itrs == null) {
+ itrs = new Itrs(this);
+ } else {
+ itrs.register(this); // in this order
+ itrs.doSomeSweeping(false);
+ }
+ prevCycles = itrs.cycles;
+ // assert takeIndex >= 0;
+ // assert prevTakeIndex == takeIndex;
+ // assert nextIndex >= 0;
+ // assert nextItem != null;
+ }
} finally {
lock.unlock();
}
}
- public boolean hasNext() {
- return remaining > 0;
+ boolean isDetached() {
+ // assert lock.getHoldCount() == 1;
+ return prevTakeIndex < 0;
+ }
+
+ private int incCursor(int index) {
+ // assert lock.getHoldCount() == 1;
+ if (++index == items.length)
+ index = 0;
+ if (index == putIndex)
+ index = NONE;
+ return index;
+ }
+
+ /**
+ * Returns true if index is invalidated by the given number of
+ * dequeues, starting from prevTakeIndex.
+ */
+ private boolean invalidated(int index, int prevTakeIndex,
+ long dequeues, int length) {
+ if (index < 0)
+ return false;
+ int distance = index - prevTakeIndex;
+ if (distance < 0)
+ distance += length;
+ return dequeues > distance;
}
- public E next() {
+ /**
+ * Adjusts indices to incorporate all dequeues since the last
+ * operation on this iterator. Call only from iterating thread.
+ */
+ private void incorporateDequeues() {
+ // assert lock.getHoldCount() == 1;
+ // assert itrs != null;
+ // assert !isDetached();
+ // assert count > 0;
+
+ final int cycles = itrs.cycles;
+ final int takeIndex = ArrayBlockingQueue.this.takeIndex;
+ final int prevCycles = this.prevCycles;
+ final int prevTakeIndex = this.prevTakeIndex;
+
+ if (cycles != prevCycles || takeIndex != prevTakeIndex) {
+ final int len = items.length;
+ // how far takeIndex has advanced since the previous
+ // operation of this iterator
+ long dequeues = (cycles - prevCycles) * len
+ + (takeIndex - prevTakeIndex);
+
+ // Check indices for invalidation
+ if (invalidated(lastRet, prevTakeIndex, dequeues, len))
+ lastRet = REMOVED;
+ if (invalidated(nextIndex, prevTakeIndex, dequeues, len))
+ nextIndex = REMOVED;
+ if (invalidated(cursor, prevTakeIndex, dequeues, len))
+ cursor = takeIndex;
+
+ if (cursor < 0 && nextIndex < 0 && lastRet < 0)
+ detach();
+ else {
+ this.prevCycles = cycles;
+ this.prevTakeIndex = takeIndex;
+ }
+ }
+ }
+
+ /**
+ * Called when itrs should stop tracking this iterator, either
+ * because there are no more indices to update (cursor < 0 &&
+ * nextIndex < 0 && lastRet < 0) or as a special exception, when
+ * lastRet >= 0, because hasNext() is about to return false for the
+ * first time. Call only from iterating thread.
+ */
+ private void detach() {
+ // Switch to detached mode
+ // assert lock.getHoldCount() == 1;
+ // assert cursor == NONE;
+ // assert nextIndex < 0;
+ // assert lastRet < 0 || nextItem == null;
+ // assert lastRet < 0 ^ lastItem != null;
+ if (prevTakeIndex >= 0) {
+ // assert itrs != null;
+ prevTakeIndex = DETACHED;
+ // try to unlink from itrs (but not too hard)
+ itrs.doSomeSweeping(true);
+ }
+ }
+
+ /**
+ * For performance reasons, we would like not to acquire a lock in
+ * hasNext in the common case. To allow for this, we only access
+ * fields (i.e. nextItem) that are not modified by update operations
+ * triggered by queue modifications.
+ */
+ public boolean hasNext() {
+ // assert lock.getHoldCount() == 0;
+ if (nextItem != null)
+ return true;
+ noNext();
+ return false;
+ }
+
+ private void noNext() {
final ReentrantLock lock = ArrayBlockingQueue.this.lock;
lock.lock();
try {
- if (remaining <= 0)
- throw new NoSuchElementException();
- lastRet = nextIndex;
- E x = itemAt(nextIndex); // check for fresher value
- if (x == null) {
- x = nextItem; // we are forced to report old value
- lastItem = null; // but ensure remove fails
+ // assert cursor == NONE;
+ // assert nextIndex == NONE;
+ if (!isDetached()) {
+ // assert lastRet >= 0;
+ incorporateDequeues(); // might update lastRet
+ if (lastRet >= 0) {
+ lastItem = itemAt(lastRet);
+ // assert lastItem != null;
+ detach();
+ }
}
- else
- lastItem = x;
- while (--remaining > 0 && // skip over nulls
- (nextItem = itemAt(nextIndex = inc(nextIndex))) == null)
- ;
- return x;
+ // assert isDetached();
+ // assert lastRet < 0 ^ lastItem != null;
} finally {
lock.unlock();
}
}
- public void remove() {
+ public E next() {
+ // assert lock.getHoldCount() == 0;
+ final E x = nextItem;
+ if (x == null)
+ throw new NoSuchElementException();
final ReentrantLock lock = ArrayBlockingQueue.this.lock;
lock.lock();
try {
- int i = lastRet;
- if (i == -1)
- throw new IllegalStateException();
- lastRet = -1;
- E x = lastItem;
- lastItem = null;
- // only remove if item still at index
- if (x != null && x == items[i]) {
- boolean removingHead = (i == takeIndex);
- removeAt(i);
- if (!removingHead)
- nextIndex = dec(nextIndex);
+ if (!isDetached())
+ incorporateDequeues();
+ // assert nextIndex != NONE;
+ // assert lastItem == null;
+ lastRet = nextIndex;
+ final int cursor = this.cursor;
+ if (cursor >= 0) {
+ nextItem = itemAt(nextIndex = cursor);
+ // assert nextItem != null;
+ this.cursor = incCursor(cursor);
+ } else {
+ nextIndex = NONE;
+ nextItem = null;
}
} finally {
lock.unlock();
}
+ return x;
}
+
+ public void remove() {
+ // assert lock.getHoldCount() == 0;
+ final ReentrantLock lock = ArrayBlockingQueue.this.lock;
+ lock.lock();
+ try {
+ if (!isDetached())
+ incorporateDequeues(); // might update lastRet or detach
+ final int lastRet = this.lastRet;
+ this.lastRet = NONE;
+ if (lastRet >= 0) {
+ if (!isDetached())
+ removeAt(lastRet);
+ else {
+ final E lastItem = this.lastItem;
+ // assert lastItem != null;
+ this.lastItem = null;
+ if (itemAt(lastRet) == lastItem)
+ removeAt(lastRet);
+ }
+ } else if (lastRet == NONE)
+ throw new IllegalStateException();
+ // else lastRet == REMOVED and the last returned element was
+ // previously asynchronously removed via an operation other
+ // than this.remove(), so nothing to do.
+
+ if (cursor < 0 && nextIndex < 0)
+ detach();
+ } finally {
+ lock.unlock();
+ // assert lastRet == NONE;
+ // assert lastItem == null;
+ }
+ }
+
+ /**
+ * Called to notify the iterator that the queue is empty, or that it
+ * has fallen hopelessly behind, so that it should abandon any
+ * further iteration, except possibly to return one more element
+ * from next(), as promised by returning true from hasNext().
+ */
+ void shutdown() {
+ // assert lock.getHoldCount() == 1;
+ cursor = NONE;
+ if (nextIndex >= 0)
+ nextIndex = REMOVED;
+ if (lastRet >= 0) {
+ lastRet = REMOVED;
+ lastItem = null;
+ }
+ prevTakeIndex = DETACHED;
+ // Don't set nextItem to null because we must continue to be
+ // able to return it on next().
+ //
+ // Caller will unlink from itrs when convenient.
+ }
+
+ private int distance(int index, int prevTakeIndex, int length) {
+ int distance = index - prevTakeIndex;
+ if (distance < 0)
+ distance += length;
+ return distance;
+ }
+
+ /**
+ * Called whenever an interior remove (not at takeIndex) occured.
+ *
+ * @return true if this iterator should be unlinked from itrs
+ */
+ boolean removedAt(int removedIndex) {
+ // assert lock.getHoldCount() == 1;
+ if (isDetached())
+ return true;
+
+ final int cycles = itrs.cycles;
+ final int takeIndex = ArrayBlockingQueue.this.takeIndex;
+ final int prevCycles = this.prevCycles;
+ final int prevTakeIndex = this.prevTakeIndex;
+ final int len = items.length;
+ int cycleDiff = cycles - prevCycles;
+ if (removedIndex < takeIndex)
+ cycleDiff++;
+ final int removedDistance =
+ (cycleDiff * len) + (removedIndex - prevTakeIndex);
+ // assert removedDistance >= 0;
+ int cursor = this.cursor;
+ if (cursor >= 0) {
+ int x = distance(cursor, prevTakeIndex, len);
+ if (x == removedDistance) {
+ if (cursor == putIndex)
+ this.cursor = cursor = NONE;
+ }
+ else if (x > removedDistance) {
+ // assert cursor != prevTakeIndex;
+ this.cursor = cursor = dec(cursor);
+ }
+ }
+ int lastRet = this.lastRet;
+ if (lastRet >= 0) {
+ int x = distance(lastRet, prevTakeIndex, len);
+ if (x == removedDistance)
+ this.lastRet = lastRet = REMOVED;
+ else if (x > removedDistance)
+ this.lastRet = lastRet = dec(lastRet);
+ }
+ int nextIndex = this.nextIndex;
+ if (nextIndex >= 0) {
+ int x = distance(nextIndex, prevTakeIndex, len);
+ if (x == removedDistance)
+ this.nextIndex = nextIndex = REMOVED;
+ else if (x > removedDistance)
+ this.nextIndex = nextIndex = dec(nextIndex);
+ }
+ else if (cursor < 0 && nextIndex < 0 && lastRet < 0) {
+ this.prevTakeIndex = DETACHED;
+ return true;
+ }
+ return false;
+ }
+
+ /**
+ * Called whenever takeIndex wraps around to zero.
+ *
+ * @return true if this iterator should be unlinked from itrs
+ */
+ boolean takeIndexWrapped() {
+ // assert lock.getHoldCount() == 1;
+ if (isDetached())
+ return true;
+ if (itrs.cycles - prevCycles > 1) {
+ // All the elements that existed at the time of the last
+ // operation are gone, so abandon further iteration.
+ shutdown();
+ return true;
+ }
+ return false;
+ }
+
+// /** Uncomment for debugging. */
+// public String toString() {
+// return ("cursor=" + cursor + " " +
+// "nextIndex=" + nextIndex + " " +
+// "lastRet=" + lastRet + " " +
+// "nextItem=" + nextItem + " " +
+// "lastItem=" + lastItem + " " +
+// "prevCycles=" + prevCycles + " " +
+// "prevTakeIndex=" + prevTakeIndex + " " +
+// "size()=" + size() + " " +
+// "remainingCapacity()=" + remainingCapacity());
+// }
}
+ public Spliterator<E> spliterator() {
+ return Spliterators.spliterator
+ (this, Spliterator.ORDERED | Spliterator.NONNULL |
+ Spliterator.CONCURRENT);
+ }
}
--- a/jdk/src/share/classes/java/util/concurrent/BlockingDeque.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/BlockingDeque.java Wed Jul 03 11:58:09 2013 +0200
@@ -41,17 +41,18 @@
* for the deque to become non-empty when retrieving an element, and wait for
* space to become available in the deque when storing an element.
*
- * <p><tt>BlockingDeque</tt> methods come in four forms, with different ways
+ * <p>{@code BlockingDeque} methods come in four forms, with different ways
* of handling operations that cannot be satisfied immediately, but may be
* satisfied at some point in the future:
* one throws an exception, the second returns a special value (either
- * <tt>null</tt> or <tt>false</tt>, depending on the operation), the third
+ * {@code null} or {@code false}, depending on the operation), the third
* blocks the current thread indefinitely until the operation can succeed,
* and the fourth blocks for only a given maximum time limit before giving
* up. These methods are summarized in the following table:
*
* <p>
* <table BORDER CELLPADDING=3 CELLSPACING=1>
+ * <caption>Summary of BlockingDeque methods</caption>
* <tr>
* <td ALIGN=CENTER COLSPAN = 5> <b>First Element (Head)</b></td>
* </tr>
@@ -116,20 +117,21 @@
* </tr>
* </table>
*
- * <p>Like any {@link BlockingQueue}, a <tt>BlockingDeque</tt> is thread safe,
+ * <p>Like any {@link BlockingQueue}, a {@code BlockingDeque} is thread safe,
* does not permit null elements, and may (or may not) be
* capacity-constrained.
*
- * <p>A <tt>BlockingDeque</tt> implementation may be used directly as a FIFO
- * <tt>BlockingQueue</tt>. The methods inherited from the
- * <tt>BlockingQueue</tt> interface are precisely equivalent to
- * <tt>BlockingDeque</tt> methods as indicated in the following table:
+ * <p>A {@code BlockingDeque} implementation may be used directly as a FIFO
+ * {@code BlockingQueue}. The methods inherited from the
+ * {@code BlockingQueue} interface are precisely equivalent to
+ * {@code BlockingDeque} methods as indicated in the following table:
*
* <p>
* <table BORDER CELLPADDING=3 CELLSPACING=1>
+ * <caption>Comparison of BlockingQueue and BlockingDeque methods</caption>
* <tr>
- * <td ALIGN=CENTER> <b><tt>BlockingQueue</tt> Method</b></td>
- * <td ALIGN=CENTER> <b>Equivalent <tt>BlockingDeque</tt> Method</b></td>
+ * <td ALIGN=CENTER> <b>{@code BlockingQueue} Method</b></td>
+ * <td ALIGN=CENTER> <b>Equivalent {@code BlockingDeque} Method</b></td>
* </tr>
* <tr>
* <td ALIGN=CENTER COLSPAN = 2> <b>Insert</b></td>
@@ -208,7 +210,7 @@
/**
* Inserts the specified element at the front of this deque if it is
* possible to do so immediately without violating capacity restrictions,
- * throwing an <tt>IllegalStateException</tt> if no space is currently
+ * throwing an {@code IllegalStateException} if no space is currently
* available. When using a capacity-restricted deque, it is generally
* preferable to use {@link #offerFirst(Object) offerFirst}.
*
@@ -223,7 +225,7 @@
/**
* Inserts the specified element at the end of this deque if it is
* possible to do so immediately without violating capacity restrictions,
- * throwing an <tt>IllegalStateException</tt> if no space is currently
+ * throwing an {@code IllegalStateException} if no space is currently
* available. When using a capacity-restricted deque, it is generally
* preferable to use {@link #offerLast(Object) offerLast}.
*
@@ -238,7 +240,7 @@
/**
* Inserts the specified element at the front of this deque if it is
* possible to do so immediately without violating capacity restrictions,
- * returning <tt>true</tt> upon success and <tt>false</tt> if no space is
+ * returning {@code true} upon success and {@code false} if no space is
* currently available.
* When using a capacity-restricted deque, this method is generally
* preferable to the {@link #addFirst(Object) addFirst} method, which can
@@ -254,7 +256,7 @@
/**
* Inserts the specified element at the end of this deque if it is
* possible to do so immediately without violating capacity restrictions,
- * returning <tt>true</tt> upon success and <tt>false</tt> if no space is
+ * returning {@code true} upon success and {@code false} if no space is
* currently available.
* When using a capacity-restricted deque, this method is generally
* preferable to the {@link #addLast(Object) addLast} method, which can
@@ -302,10 +304,10 @@
*
* @param e the element to add
* @param timeout how long to wait before giving up, in units of
- * <tt>unit</tt>
- * @param unit a <tt>TimeUnit</tt> determining how to interpret the
- * <tt>timeout</tt> parameter
- * @return <tt>true</tt> if successful, or <tt>false</tt> if
+ * {@code unit}
+ * @param unit a {@code TimeUnit} determining how to interpret the
+ * {@code timeout} parameter
+ * @return {@code true} if successful, or {@code false} if
* the specified waiting time elapses before space is available
* @throws InterruptedException if interrupted while waiting
* @throws ClassCastException if the class of the specified element
@@ -324,10 +326,10 @@
*
* @param e the element to add
* @param timeout how long to wait before giving up, in units of
- * <tt>unit</tt>
- * @param unit a <tt>TimeUnit</tt> determining how to interpret the
- * <tt>timeout</tt> parameter
- * @return <tt>true</tt> if successful, or <tt>false</tt> if
+ * {@code unit}
+ * @param unit a {@code TimeUnit} determining how to interpret the
+ * {@code timeout} parameter
+ * @return {@code true} if successful, or {@code false} if
* the specified waiting time elapses before space is available
* @throws InterruptedException if interrupted while waiting
* @throws ClassCastException if the class of the specified element
@@ -363,10 +365,10 @@
* become available.
*
* @param timeout how long to wait before giving up, in units of
- * <tt>unit</tt>
- * @param unit a <tt>TimeUnit</tt> determining how to interpret the
- * <tt>timeout</tt> parameter
- * @return the head of this deque, or <tt>null</tt> if the specified
+ * {@code unit}
+ * @param unit a {@code TimeUnit} determining how to interpret the
+ * {@code timeout} parameter
+ * @return the head of this deque, or {@code null} if the specified
* waiting time elapses before an element is available
* @throws InterruptedException if interrupted while waiting
*/
@@ -379,10 +381,10 @@
* become available.
*
* @param timeout how long to wait before giving up, in units of
- * <tt>unit</tt>
- * @param unit a <tt>TimeUnit</tt> determining how to interpret the
- * <tt>timeout</tt> parameter
- * @return the tail of this deque, or <tt>null</tt> if the specified
+ * {@code unit}
+ * @param unit a {@code TimeUnit} determining how to interpret the
+ * {@code timeout} parameter
+ * @return the tail of this deque, or {@code null} if the specified
* waiting time elapses before an element is available
* @throws InterruptedException if interrupted while waiting
*/
@@ -392,13 +394,13 @@
/**
* 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 <tt>e</tt> such that
- * <tt>o.equals(e)</tt> (if such an element exists).
- * Returns <tt>true</tt> if this deque contained the specified element
+ * 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).
*
* @param o element to be removed from this deque, if present
- * @return <tt>true</tt> if an element was removed as a result of this call
+ * @return {@code true} if an element was removed as a result of this call
* @throws ClassCastException if the class of the specified element
* is incompatible with this deque
* (<a href="../Collection.html#optional-restrictions">optional</a>)
@@ -410,13 +412,13 @@
/**
* Removes the last occurrence of the specified element from this deque.
* If the deque does not contain the element, it is unchanged.
- * More formally, removes the last element <tt>e</tt> such that
- * <tt>o.equals(e)</tt> (if such an element exists).
- * Returns <tt>true</tt> if this deque contained the specified element
+ * More formally, removes the last 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).
*
* @param o element to be removed from this deque, if present
- * @return <tt>true</tt> if an element was removed as a result of this call
+ * @return {@code true} if an element was removed as a result of this call
* @throws ClassCastException if the class of the specified element
* is incompatible with this deque
* (<a href="../Collection.html#optional-restrictions">optional</a>)
@@ -431,8 +433,8 @@
* Inserts the specified element into the queue represented by this deque
* (in other words, at the tail of this deque) if it is possible to do so
* immediately without violating capacity restrictions, returning
- * <tt>true</tt> upon success and throwing an
- * <tt>IllegalStateException</tt> if no space is currently available.
+ * {@code true} upon success and throwing an
+ * {@code IllegalStateException} if no space is currently available.
* When using a capacity-restricted deque, it is generally preferable to
* use {@link #offer(Object) offer}.
*
@@ -452,7 +454,7 @@
* Inserts the specified element into the queue represented by this deque
* (in other words, at the tail of this deque) if it is possible to do so
* immediately without violating capacity restrictions, returning
- * <tt>true</tt> upon success and <tt>false</tt> if no space is currently
+ * {@code true} upon success and {@code false} if no space is currently
* available. When using a capacity-restricted deque, this method is
* generally preferable to the {@link #add} method, which can fail to
* insert an element only by throwing an exception.
@@ -494,8 +496,8 @@
* {@link #offerLast(Object,long,TimeUnit) offerLast}.
*
* @param e the element to add
- * @return <tt>true</tt> if the element was added to this deque, else
- * <tt>false</tt>
+ * @return {@code true} if the element was added to this deque, else
+ * {@code false}
* @throws InterruptedException {@inheritDoc}
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this deque
@@ -522,11 +524,11 @@
/**
* Retrieves and removes the head of the queue represented by this deque
* (in other words, the first element of this deque), or returns
- * <tt>null</tt> if this deque is empty.
+ * {@code null} if this deque is empty.
*
* <p>This method is equivalent to {@link #pollFirst()}.
*
- * @return the head of this deque, or <tt>null</tt> if this deque is empty
+ * @return the head of this deque, or {@code null} if this deque is empty
*/
E poll();
@@ -550,7 +552,7 @@
* <p>This method is equivalent to
* {@link #pollFirst(long,TimeUnit) pollFirst}.
*
- * @return the head of this deque, or <tt>null</tt> if the
+ * @return the head of this deque, or {@code null} if the
* specified waiting time elapses before an element is available
* @throws InterruptedException if interrupted while waiting
*/
@@ -573,27 +575,27 @@
/**
* Retrieves, but does not remove, the head of the queue represented by
* this deque (in other words, the first element of this deque), or
- * returns <tt>null</tt> if this deque is empty.
+ * returns {@code null} if this deque is empty.
*
* <p>This method is equivalent to {@link #peekFirst() peekFirst}.
*
- * @return the head of this deque, or <tt>null</tt> if this deque is empty
+ * @return the head of this deque, or {@code null} if this deque is empty
*/
E peek();
/**
* 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 <tt>e</tt> such that
- * <tt>o.equals(e)</tt> (if such an element exists).
- * Returns <tt>true</tt> if this deque contained the specified element
+ * 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 <tt>true</tt> if this deque changed as a result of the call
+ * @return {@code true} if this deque changed as a result of the call
* @throws ClassCastException if the class of the specified element
* is incompatible with this deque
* (<a href="../Collection.html#optional-restrictions">optional</a>)
@@ -603,12 +605,12 @@
boolean remove(Object o);
/**
- * Returns <tt>true</tt> if this deque contains the specified element.
- * More formally, returns <tt>true</tt> if and only if this deque contains
- * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
+ * 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 <tt>true</tt> if this deque contains the specified element
+ * @return {@code true} if this deque contains the specified element
* @throws ClassCastException if the class of the specified element
* is incompatible with this deque
* (<a href="../Collection.html#optional-restrictions">optional</a>)
@@ -635,9 +637,10 @@
// *** Stack methods ***
/**
- * Pushes an element onto the stack represented by this deque. In other
- * words, inserts the element at the front of this deque unless it would
- * violate capacity restrictions.
+ * Pushes an element onto the stack represented by this deque (in other
+ * words, at the head of this deque) if it is possible to do so
+ * immediately without violating capacity restrictions, throwing an
+ * {@code IllegalStateException} if no space is currently available.
*
* <p>This method is equivalent to {@link #addFirst(Object) addFirst}.
*
--- a/jdk/src/share/classes/java/util/concurrent/BlockingQueue.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/BlockingQueue.java Wed Jul 03 11:58:09 2013 +0200
@@ -44,17 +44,18 @@
* element, and wait for space to become available in the queue when
* storing an element.
*
- * <p><tt>BlockingQueue</tt> methods come in four forms, with different ways
+ * <p>{@code BlockingQueue} methods come in four forms, with different ways
* of handling operations that cannot be satisfied immediately, but may be
* satisfied at some point in the future:
* one throws an exception, the second returns a special value (either
- * <tt>null</tt> or <tt>false</tt>, depending on the operation), the third
+ * {@code null} or {@code false}, depending on the operation), the third
* blocks the current thread indefinitely until the operation can succeed,
* and the fourth blocks for only a given maximum time limit before giving
* up. These methods are summarized in the following table:
*
* <p>
* <table BORDER CELLPADDING=3 CELLSPACING=1>
+ * <caption>Summary of BlockingQueue methods</caption>
* <tr>
* <td></td>
* <td ALIGN=CENTER><em>Throws exception</em></td>
@@ -85,37 +86,37 @@
* </tr>
* </table>
*
- * <p>A <tt>BlockingQueue</tt> does not accept <tt>null</tt> elements.
- * Implementations throw <tt>NullPointerException</tt> on attempts
- * to <tt>add</tt>, <tt>put</tt> or <tt>offer</tt> a <tt>null</tt>. A
- * <tt>null</tt> is used as a sentinel value to indicate failure of
- * <tt>poll</tt> operations.
+ * <p>A {@code BlockingQueue} does not accept {@code null} elements.
+ * Implementations throw {@code NullPointerException} on attempts
+ * to {@code add}, {@code put} or {@code offer} a {@code null}. A
+ * {@code null} is used as a sentinel value to indicate failure of
+ * {@code poll} operations.
*
- * <p>A <tt>BlockingQueue</tt> may be capacity bounded. At any given
- * time it may have a <tt>remainingCapacity</tt> beyond which no
- * additional elements can be <tt>put</tt> without blocking.
- * A <tt>BlockingQueue</tt> without any intrinsic capacity constraints always
- * reports a remaining capacity of <tt>Integer.MAX_VALUE</tt>.
+ * <p>A {@code BlockingQueue} may be capacity bounded. At any given
+ * time it may have a {@code remainingCapacity} beyond which no
+ * additional elements can be {@code put} without blocking.
+ * A {@code BlockingQueue} without any intrinsic capacity constraints always
+ * reports a remaining capacity of {@code Integer.MAX_VALUE}.
*
- * <p> <tt>BlockingQueue</tt> implementations are designed to be used
+ * <p>{@code BlockingQueue} implementations are designed to be used
* primarily for producer-consumer queues, but additionally support
* the {@link java.util.Collection} interface. So, for example, it is
* possible to remove an arbitrary element from a queue using
- * <tt>remove(x)</tt>. However, such operations are in general
+ * {@code remove(x)}. However, such operations are in general
* <em>not</em> performed very efficiently, and are intended for only
* occasional use, such as when a queued message is cancelled.
*
- * <p> <tt>BlockingQueue</tt> implementations are thread-safe. All
+ * <p>{@code BlockingQueue} implementations are thread-safe. All
* queuing methods achieve their effects atomically using internal
* locks or other forms of concurrency control. However, the
- * <em>bulk</em> Collection operations <tt>addAll</tt>,
- * <tt>containsAll</tt>, <tt>retainAll</tt> and <tt>removeAll</tt> are
+ * <em>bulk</em> Collection operations {@code addAll},
+ * {@code containsAll}, {@code retainAll} and {@code removeAll} are
* <em>not</em> necessarily performed atomically unless specified
* otherwise in an implementation. So it is possible, for example, for
- * <tt>addAll(c)</tt> to fail (throwing an exception) after adding
- * only some of the elements in <tt>c</tt>.
+ * {@code addAll(c)} to fail (throwing an exception) after adding
+ * only some of the elements in {@code c}.
*
- * <p>A <tt>BlockingQueue</tt> does <em>not</em> intrinsically support
+ * <p>A {@code BlockingQueue} does <em>not</em> intrinsically support
* any kind of "close" or "shutdown" operation to
* indicate that no more items will be added. The needs and usage of
* such features tend to be implementation-dependent. For example, a
@@ -125,7 +126,7 @@
*
* <p>
* Usage example, based on a typical producer-consumer scenario.
- * Note that a <tt>BlockingQueue</tt> can safely be used with multiple
+ * Note that a {@code BlockingQueue} can safely be used with multiple
* producers and multiple consumers.
* <pre> {@code
* class Producer implements Runnable {
@@ -181,13 +182,13 @@
/**
* Inserts the specified element into this queue if it is possible to do
* so immediately without violating capacity restrictions, returning
- * <tt>true</tt> upon success and throwing an
- * <tt>IllegalStateException</tt> if no space is currently available.
+ * {@code true} upon success and throwing an
+ * {@code IllegalStateException} if no space is currently available.
* When using a capacity-restricted queue, it is generally preferable to
* use {@link #offer(Object) offer}.
*
* @param e the element to add
- * @return <tt>true</tt> (as specified by {@link Collection#add})
+ * @return {@code true} (as specified by {@link Collection#add})
* @throws IllegalStateException if the element cannot be added at this
* time due to capacity restrictions
* @throws ClassCastException if the class of the specified element
@@ -201,14 +202,14 @@
/**
* Inserts the specified element into this queue if it is possible to do
* so immediately without violating capacity restrictions, returning
- * <tt>true</tt> upon success and <tt>false</tt> if no space is currently
+ * {@code true} upon success and {@code false} if no space is currently
* available. When using a capacity-restricted queue, this method is
* generally preferable to {@link #add}, which can fail to insert an
* element only by throwing an exception.
*
* @param e the element to add
- * @return <tt>true</tt> if the element was added to this queue, else
- * <tt>false</tt>
+ * @return {@code true} if the element was added to this queue, else
+ * {@code false}
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this queue
* @throws NullPointerException if the specified element is null
@@ -237,10 +238,10 @@
*
* @param e the element to add
* @param timeout how long to wait before giving up, in units of
- * <tt>unit</tt>
- * @param unit a <tt>TimeUnit</tt> determining how to interpret the
- * <tt>timeout</tt> parameter
- * @return <tt>true</tt> if successful, or <tt>false</tt> if
+ * {@code unit}
+ * @param unit a {@code TimeUnit} determining how to interpret the
+ * {@code timeout} parameter
+ * @return {@code true} if successful, or {@code false} if
* the specified waiting time elapses before space is available
* @throws InterruptedException if interrupted while waiting
* @throws ClassCastException if the class of the specified element
@@ -266,10 +267,10 @@
* specified wait time if necessary for an element to become available.
*
* @param timeout how long to wait before giving up, in units of
- * <tt>unit</tt>
- * @param unit a <tt>TimeUnit</tt> determining how to interpret the
- * <tt>timeout</tt> parameter
- * @return the head of this queue, or <tt>null</tt> if the
+ * {@code unit}
+ * @param unit a {@code TimeUnit} determining how to interpret the
+ * {@code timeout} parameter
+ * @return the head of this queue, or {@code null} if the
* specified waiting time elapses before an element is available
* @throws InterruptedException if interrupted while waiting
*/
@@ -279,11 +280,11 @@
/**
* Returns the number of additional elements that this queue can ideally
* (in the absence of memory or resource constraints) accept without
- * blocking, or <tt>Integer.MAX_VALUE</tt> if there is no intrinsic
+ * blocking, or {@code Integer.MAX_VALUE} if there is no intrinsic
* limit.
*
* <p>Note that you <em>cannot</em> always tell if an attempt to insert
- * an element will succeed by inspecting <tt>remainingCapacity</tt>
+ * 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.
*
@@ -293,14 +294,14 @@
/**
* Removes a single instance of the specified element from this queue,
- * if it is present. More formally, removes an element <tt>e</tt> such
- * that <tt>o.equals(e)</tt>, if this queue contains one or more such
+ * 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 <tt>true</tt> if this queue contained the specified element
+ * 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 <tt>true</tt> if this queue changed as a result of the call
+ * @return {@code true} if this queue changed as a result of the call
* @throws ClassCastException if the class of the specified element
* is incompatible with this queue
* (<a href="../Collection.html#optional-restrictions">optional</a>)
@@ -310,12 +311,12 @@
boolean remove(Object o);
/**
- * Returns <tt>true</tt> if this queue contains the specified element.
- * More formally, returns <tt>true</tt> if and only if this queue contains
- * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
+ * 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 <tt>true</tt> if this queue contains the specified element
+ * @return {@code true} if this queue contains the specified element
* @throws ClassCastException if the class of the specified element
* is incompatible with this queue
* (<a href="../Collection.html#optional-restrictions">optional</a>)
@@ -329,10 +330,10 @@
* to the given collection. This operation may be more
* efficient than repeatedly polling this queue. A failure
* encountered while attempting to add elements to
- * collection <tt>c</tt> may result in elements being in neither,
+ * collection {@code c} may result in elements being in neither,
* either or both collections when the associated exception is
* thrown. Attempts to drain a queue to itself result in
- * <tt>IllegalArgumentException</tt>. Further, the behavior of
+ * {@code IllegalArgumentException}. Further, the behavior of
* this operation is undefined if the specified collection is
* modified while the operation is in progress.
*
@@ -353,10 +354,10 @@
* Removes at most the given number of available elements from
* this queue and adds them to the given collection. A failure
* encountered while attempting to add elements to
- * collection <tt>c</tt> may result in elements being in neither,
+ * collection {@code c} may result in elements being in neither,
* either or both collections when the associated exception is
* thrown. Attempts to drain a queue to itself result in
- * <tt>IllegalArgumentException</tt>. Further, the behavior of
+ * {@code IllegalArgumentException}. Further, the behavior of
* this operation is undefined if the specified collection is
* modified while the operation is in progress.
*
--- a/jdk/src/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java Wed Jul 03 11:58:09 2013 +0200
@@ -42,6 +42,9 @@
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Queue;
+import java.util.Spliterator;
+import java.util.Spliterators;
+import java.util.function.Consumer;
/**
* An unbounded concurrent {@linkplain Deque deque} based on linked nodes.
@@ -816,7 +819,7 @@
* Creates an array list and fills it with elements of this list.
* Used by toArray.
*
- * @return the arrayList
+ * @return the array list
*/
private ArrayList<E> toArrayList() {
ArrayList<E> list = new ArrayList<E>();
@@ -1024,11 +1027,27 @@
}
public E poll() { return pollFirst(); }
+ public E peek() { return peekFirst(); }
+
+ /**
+ * @throws NoSuchElementException {@inheritDoc}
+ */
public E remove() { return removeFirst(); }
- public E peek() { return peekFirst(); }
+
+ /**
+ * @throws NoSuchElementException {@inheritDoc}
+ */
+ public E pop() { return removeFirst(); }
+
+ /**
+ * @throws NoSuchElementException {@inheritDoc}
+ */
public E element() { return getFirst(); }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
public void push(E e) { addFirst(e); }
- public E pop() { return removeFirst(); }
/**
* Removes the first element {@code e} such that
@@ -1385,6 +1404,99 @@
Node<E> nextNode(Node<E> p) { return pred(p); }
}
+ /** A customized variant of Spliterators.IteratorSpliterator */
+ static final class CLDSpliterator<E> implements Spliterator<E> {
+ static final int MAX_BATCH = 1 << 25; // max batch array size;
+ final ConcurrentLinkedDeque<E> queue;
+ Node<E> current; // current node; null until initialized
+ int batch; // batch size for splits
+ boolean exhausted; // true when no more nodes
+ CLDSpliterator(ConcurrentLinkedDeque<E> queue) {
+ this.queue = queue;
+ }
+
+ public Spliterator<E> trySplit() {
+ Node<E> p;
+ final ConcurrentLinkedDeque<E> q = this.queue;
+ int b = batch;
+ int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
+ if (!exhausted &&
+ ((p = current) != null || (p = q.first()) != null)) {
+ if (p.item == null && p == (p = p.next))
+ current = p = q.first();
+ if (p != null && p.next != null) {
+ Object[] a = new Object[n];
+ int i = 0;
+ do {
+ if ((a[i] = p.item) != null)
+ ++i;
+ if (p == (p = p.next))
+ p = q.first();
+ } while (p != null && i < n);
+ if ((current = p) == null)
+ exhausted = true;
+ if (i > 0) {
+ batch = i;
+ return Spliterators.spliterator
+ (a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL |
+ Spliterator.CONCURRENT);
+ }
+ }
+ }
+ return null;
+ }
+
+ public void forEachRemaining(Consumer<? super E> action) {
+ Node<E> p;
+ if (action == null) throw new NullPointerException();
+ final ConcurrentLinkedDeque<E> q = this.queue;
+ if (!exhausted &&
+ ((p = current) != null || (p = q.first()) != null)) {
+ exhausted = true;
+ do {
+ E e = p.item;
+ if (p == (p = p.next))
+ p = q.first();
+ if (e != null)
+ action.accept(e);
+ } while (p != null);
+ }
+ }
+
+ public boolean tryAdvance(Consumer<? super E> action) {
+ Node<E> p;
+ if (action == null) throw new NullPointerException();
+ final ConcurrentLinkedDeque<E> q = this.queue;
+ if (!exhausted &&
+ ((p = current) != null || (p = q.first()) != null)) {
+ E e;
+ do {
+ e = p.item;
+ if (p == (p = p.next))
+ p = q.first();
+ } while (e == null && p != null);
+ if ((current = p) == null)
+ exhausted = true;
+ if (e != null) {
+ action.accept(e);
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public long estimateSize() { return Long.MAX_VALUE; }
+
+ public int characteristics() {
+ return Spliterator.ORDERED | Spliterator.NONNULL |
+ Spliterator.CONCURRENT;
+ }
+ }
+
+ public Spliterator<E> spliterator() {
+ return new CLDSpliterator<E>(this);
+ }
+
/**
* Saves this deque to a stream (that is, serializes it).
*
--- a/jdk/src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java Wed Jul 03 11:58:09 2013 +0200
@@ -41,6 +41,9 @@
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Queue;
+import java.util.Spliterator;
+import java.util.Spliterators;
+import java.util.function.Consumer;
/**
* An unbounded thread-safe {@linkplain Queue queue} based on linked nodes.
@@ -56,7 +59,7 @@
* Like most other concurrent collection implementations, this class
* does not permit the use of {@code null} elements.
*
- * <p>This implementation employs an efficient "wait-free"
+ * <p>This implementation employs an efficient <em>non-blocking</em>
* algorithm based on one described in <a
* href="http://www.cs.rochester.edu/u/michael/PODC96.html"> Simple,
* Fast, and Practical Non-Blocking and Blocking Concurrent Queue
@@ -295,7 +298,7 @@
}
/**
- * Try to CAS head to p. If successful, repoint old head to itself
+ * Tries to CAS head to p. If successful, repoint old head to itself
* as sentinel for succ(), below.
*/
final void updateHead(Node<E> h, Node<E> p) {
@@ -792,6 +795,96 @@
tail = t;
}
+ /** A customized variant of Spliterators.IteratorSpliterator */
+ static final class CLQSpliterator<E> implements Spliterator<E> {
+ static final int MAX_BATCH = 1 << 25; // max batch array size;
+ final ConcurrentLinkedQueue<E> queue;
+ Node<E> current; // current node; null until initialized
+ int batch; // batch size for splits
+ boolean exhausted; // true when no more nodes
+ CLQSpliterator(ConcurrentLinkedQueue<E> queue) {
+ this.queue = queue;
+ }
+
+ public Spliterator<E> trySplit() {
+ Node<E> p;
+ final ConcurrentLinkedQueue<E> q = this.queue;
+ int b = batch;
+ int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
+ if (!exhausted &&
+ ((p = current) != null || (p = q.first()) != null) &&
+ p.next != null) {
+ Object[] a = new Object[n];
+ int i = 0;
+ do {
+ if ((a[i] = p.item) != null)
+ ++i;
+ if (p == (p = p.next))
+ p = q.first();
+ } while (p != null && i < n);
+ if ((current = p) == null)
+ exhausted = true;
+ if (i > 0) {
+ batch = i;
+ return Spliterators.spliterator
+ (a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL |
+ Spliterator.CONCURRENT);
+ }
+ }
+ return null;
+ }
+
+ public void forEachRemaining(Consumer<? super E> action) {
+ Node<E> p;
+ if (action == null) throw new NullPointerException();
+ final ConcurrentLinkedQueue<E> q = this.queue;
+ if (!exhausted &&
+ ((p = current) != null || (p = q.first()) != null)) {
+ exhausted = true;
+ do {
+ E e = p.item;
+ if (p == (p = p.next))
+ p = q.first();
+ if (e != null)
+ action.accept(e);
+ } while (p != null);
+ }
+ }
+
+ public boolean tryAdvance(Consumer<? super E> action) {
+ Node<E> p;
+ if (action == null) throw new NullPointerException();
+ final ConcurrentLinkedQueue<E> q = this.queue;
+ if (!exhausted &&
+ ((p = current) != null || (p = q.first()) != null)) {
+ E e;
+ do {
+ e = p.item;
+ if (p == (p = p.next))
+ p = q.first();
+ } while (e == null && p != null);
+ if ((current = p) == null)
+ exhausted = true;
+ if (e != null) {
+ action.accept(e);
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public long estimateSize() { return Long.MAX_VALUE; }
+
+ public int characteristics() {
+ return Spliterator.ORDERED | Spliterator.NONNULL |
+ Spliterator.CONCURRENT;
+ }
+ }
+
+ public Spliterator<E> spliterator() {
+ return new CLQSpliterator<E>(this);
+ }
+
/**
* Throws NullPointerException if argument is null.
*
--- a/jdk/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java Wed Jul 03 11:58:09 2013 +0200
@@ -34,7 +34,25 @@
*/
package java.util.concurrent;
-import java.util.*;
+import java.util.AbstractCollection;
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NavigableSet;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.SortedMap;
+import java.util.Spliterator;
+import java.util.function.BiFunction;
+import java.util.function.Consumer;
+import java.util.function.BiConsumer;
+import java.util.function.Function;
/**
* A scalable concurrent {@link ConcurrentNavigableMap} implementation.
@@ -45,38 +63,38 @@
* <p>This class implements a concurrent variant of <a
* href="http://en.wikipedia.org/wiki/Skip_list" target="_top">SkipLists</a>
* providing expected average <i>log(n)</i> time cost for the
- * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and
- * <tt>remove</tt> operations and their variants. Insertion, removal,
+ * {@code containsKey}, {@code get}, {@code put} and
+ * {@code remove} operations and their variants. Insertion, removal,
* update, and access operations safely execute concurrently by
* multiple threads. Iterators are <i>weakly consistent</i>, returning
* elements reflecting the state of the map at some point at or since
* the creation of the iterator. They do <em>not</em> throw {@link
- * ConcurrentModificationException}, and may proceed concurrently with
- * other operations. Ascending key ordered views and their iterators
- * are faster than descending ones.
+ * java.util.ConcurrentModificationException ConcurrentModificationException},
+ * and may proceed concurrently with other operations. Ascending key ordered
+ * views and their iterators are faster than descending ones.
*
- * <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
+ * <p>All {@code Map.Entry} pairs returned by methods in this class
* and its views represent snapshots of mappings at the time they were
- * produced. They do <em>not</em> support the <tt>Entry.setValue</tt>
+ * produced. They do <em>not</em> support the {@code Entry.setValue}
* method. (Note however that it is possible to change mappings in the
- * associated map using <tt>put</tt>, <tt>putIfAbsent</tt>, or
- * <tt>replace</tt>, depending on exactly which effect you need.)
+ * associated map using {@code put}, {@code putIfAbsent}, or
+ * {@code replace}, depending on exactly which effect you need.)
*
- * <p>Beware that, unlike in most collections, the <tt>size</tt>
+ * <p>Beware that, unlike in most collections, the {@code size}
* method is <em>not</em> a constant-time operation. Because of the
* asynchronous nature of these maps, determining the current number
* of elements requires a traversal of the elements, and so may report
* inaccurate results if this collection is modified during traversal.
- * Additionally, the bulk operations <tt>putAll</tt>, <tt>equals</tt>,
- * <tt>toArray</tt>, <tt>containsValue</tt>, and <tt>clear</tt> are
+ * Additionally, the bulk operations {@code putAll}, {@code equals},
+ * {@code toArray}, {@code containsValue}, and {@code clear} are
* <em>not</em> guaranteed to be performed atomically. For example, an
- * iterator operating concurrently with a <tt>putAll</tt> operation
+ * iterator operating concurrently with a {@code putAll} operation
* might view only some of the added elements.
*
* <p>This class and its views and iterators implement all of the
* <em>optional</em> methods of the {@link Map} and {@link Iterator}
* interfaces. Like most other concurrent collections, this class does
- * <em>not</em> permit the use of <tt>null</tt> keys or values because some
+ * <em>not</em> permit the use of {@code null} keys or values because some
* null return values cannot be reliably distinguished from the absence of
* elements.
*
@@ -89,7 +107,6 @@
* @param <V> the type of mapped values
* @since 1.6
*/
-@SuppressWarnings("unchecked")
public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
implements ConcurrentNavigableMap<K,V>,
Cloneable,
@@ -257,7 +274,7 @@
*
* Indexing uses skip list parameters that maintain good search
* performance while using sparser-than-usual indices: The
- * hardwired parameters k=1, p=0.5 (see method randomLevel) mean
+ * hardwired parameters k=1, p=0.5 (see method doPut) mean
* that about one-quarter of the nodes have indices. Of those that
* do, half have one level, a quarter have two, and so on (see
* Pugh's Skip List Cookbook, sec 3.4). The expected total space
@@ -295,6 +312,20 @@
* there is a fair amount of near-duplication of code to handle
* variants.
*
+ * To produce random values without interference across threads,
+ * we use within-JDK thread local random support (via the
+ * "secondary seed", to avoid interference with user-level
+ * ThreadLocalRandom.)
+ *
+ * A previous version of this class wrapped non-comparable keys
+ * with their comparators to emulate Comparables when using
+ * comparators vs Comparables. However, JVMs now appear to better
+ * handle infusing comparator-vs-comparable choice into search
+ * loops. Static method cpr(comparator, x, y) is used for all
+ * comparisons, which works well as long as the comparator
+ * argument is set up outside of loops (thus sometimes passed as
+ * an argument to internal methods) to avoid field re-reads.
+ *
* For explanation of algorithms sharing at least a couple of
* features with this one, see Mikhail Fomitchev's thesis
* (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
@@ -323,12 +354,6 @@
private static final long serialVersionUID = -8627078645895051609L;
/**
- * Generates the initial random seed for the cheaper per-instance
- * random number generators used in randomLevel.
- */
- private static final Random seedGenerator = new Random();
-
- /**
* Special value used to identify base-level header
*/
private static final Object BASE_HEADER = new Object();
@@ -339,17 +364,12 @@
private transient volatile HeadIndex<K,V> head;
/**
- * The comparator used to maintain order in this map, or null
- * if using natural ordering.
+ * The comparator used to maintain order in this map, or null if
+ * using natural ordering. (Non-private to simplify access in
+ * nested classes.)
* @serial
*/
- private final Comparator<? super K> comparator;
-
- /**
- * Seed for simple random number generator. Not volatile since it
- * doesn't matter too much if different threads don't see updates.
- */
- private transient int randomSeed;
+ final Comparator<? super K> comparator;
/** Lazily initialized key set */
private transient KeySet<K> keySet;
@@ -365,12 +385,11 @@
* clear, readObject. and ConcurrentSkipListSet.clone.
* (Note that comparator must be separately initialized.)
*/
- final void initialize() {
+ private void initialize() {
keySet = null;
entrySet = null;
values = null;
descendingMap = null;
- randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
null, null, 1);
}
@@ -438,7 +457,7 @@
* because callers will have already read value field and need
* to use that read (not another done here) and so directly
* test if value points to node.
- * @param n a possibly null reference to a node
+ *
* @return true if this node is a marker node
*/
boolean isMarker() {
@@ -477,7 +496,7 @@
*/
if (f == next && this == b.next) {
if (f == null || f.value != f) // not already marked
- appendMarker(f);
+ casNext(f, new Node<K,V>(f));
else
b.casNext(this, f.next);
}
@@ -487,13 +506,14 @@
* Returns value if this node contains a valid key-value pair,
* else null.
* @return this node's value if it isn't a marker or header or
- * is deleted, else null.
+ * is deleted, else null
*/
V getValidValue() {
Object v = value;
if (v == this || v == BASE_HEADER)
return null;
- return (V)v;
+ @SuppressWarnings("unchecked") V vv = (V)v;
+ return vv;
}
/**
@@ -502,10 +522,11 @@
* @return new entry or null
*/
AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {
- V v = getValidValue();
- if (v == null)
+ Object v = value;
+ if (v == null || v == this || v == BASE_HEADER)
return null;
- return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);
+ @SuppressWarnings("unchecked") V vv = (V)v;
+ return new AbstractMap.SimpleImmutableEntry<K,V>(key, vv);
}
// UNSAFE mechanics
@@ -588,7 +609,7 @@
* @return true if successful
*/
final boolean unlink(Index<K,V> succ) {
- return !indexesDeletedNode() && casRight(succ, succ.right);
+ return node.value != null && casRight(succ, succ.right);
}
// Unsafe mechanics
@@ -622,80 +643,12 @@
/* ---------------- Comparison utilities -------------- */
/**
- * Represents a key with a comparator as a Comparable.
- *
- * Because most sorted collections seem to use natural ordering on
- * Comparables (Strings, Integers, etc), most internal methods are
- * geared to use them. This is generally faster than checking
- * per-comparison whether to use comparator or comparable because
- * it doesn't require a (Comparable) cast for each comparison.
- * (Optimizers can only sometimes remove such redundant checks
- * themselves.) When Comparators are used,
- * ComparableUsingComparators are created so that they act in the
- * same way as natural orderings. This penalizes use of
- * Comparators vs Comparables, which seems like the right
- * tradeoff.
- */
- static final class ComparableUsingComparator<K> implements Comparable<K> {
- final K actualKey;
- final Comparator<? super K> cmp;
- ComparableUsingComparator(K key, Comparator<? super K> cmp) {
- this.actualKey = key;
- this.cmp = cmp;
- }
- public int compareTo(K k2) {
- return cmp.compare(actualKey, k2);
- }
- }
-
- /**
- * If using comparator, return a ComparableUsingComparator, else
- * cast key as Comparable, which may cause ClassCastException,
- * which is propagated back to caller.
+ * Compares using comparator or natural ordering if null.
+ * Called only by methods that have performed required type checks.
*/
- private Comparable<? super K> comparable(Object key)
- throws ClassCastException {
- if (key == null)
- throw new NullPointerException();
- if (comparator != null)
- return new ComparableUsingComparator<K>((K)key, comparator);
- else
- return (Comparable<? super K>)key;
- }
-
- /**
- * Compares using comparator or natural ordering. Used when the
- * ComparableUsingComparator approach doesn't apply.
- */
- int compare(K k1, K k2) throws ClassCastException {
- Comparator<? super K> cmp = comparator;
- if (cmp != null)
- return cmp.compare(k1, k2);
- else
- return ((Comparable<? super K>)k1).compareTo(k2);
- }
-
- /**
- * Returns true if given key greater than or equal to least and
- * strictly less than fence, bypassing either test if least or
- * fence are null. Needed mainly in submap operations.
- */
- boolean inHalfOpenRange(K key, K least, K fence) {
- if (key == null)
- throw new NullPointerException();
- return ((least == null || compare(key, least) >= 0) &&
- (fence == null || compare(key, fence) < 0));
- }
-
- /**
- * Returns true if given key greater than or equal to least and less
- * or equal to fence. Needed mainly in submap operations.
- */
- boolean inOpenRange(K key, K least, K fence) {
- if (key == null)
- throw new NullPointerException();
- return ((least == null || compare(key, least) >= 0) &&
- (fence == null || compare(key, fence) <= 0));
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ static final int cpr(Comparator c, Object x, Object y) {
+ return (c != null) ? c.compare(x, y) : ((Comparable)x).compareTo(y);
}
/* ---------------- Traversal -------------- */
@@ -708,13 +661,11 @@
* @param key the key
* @return a predecessor of key
*/
- private Node<K,V> findPredecessor(Comparable<? super K> key) {
+ private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
if (key == null)
throw new NullPointerException(); // don't postpone errors
for (;;) {
- Index<K,V> q = head;
- Index<K,V> r = q.right;
- for (;;) {
+ for (Index<K,V> q = head, r = q.right, d;;) {
if (r != null) {
Node<K,V> n = r.node;
K k = n.key;
@@ -724,18 +675,16 @@
r = q.right; // reread r
continue;
}
- if (key.compareTo(k) > 0) {
+ if (cpr(cmp, key, k) > 0) {
q = r;
r = r.right;
continue;
}
}
- Index<K,V> d = q.down;
- if (d != null) {
- q = d;
- r = d.right;
- } else
+ if ((d = q.down) == null)
return q.node;
+ q = d;
+ r = d.right;
}
}
}
@@ -784,54 +733,71 @@
* @param key the key
* @return node holding key, or null if no such
*/
- private Node<K,V> findNode(Comparable<? super K> key) {
- for (;;) {
- Node<K,V> b = findPredecessor(key);
- Node<K,V> n = b.next;
- for (;;) {
+ private Node<K,V> findNode(Object key) {
+ if (key == null)
+ throw new NullPointerException(); // don't postpone errors
+ Comparator<? super K> cmp = comparator;
+ outer: for (;;) {
+ for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
+ Object v; int c;
if (n == null)
- return null;
+ break outer;
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read
break;
- Object v = n.value;
- if (v == null) { // n is deleted
+ if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
- if (v == n || b.value == null) // b is deleted
+ if (b.value == null || v == n) // b is deleted
break;
- int c = key.compareTo(n.key);
- if (c == 0)
+ if ((c = cpr(cmp, key, n.key)) == 0)
return n;
if (c < 0)
- return null;
+ break outer;
b = n;
n = f;
}
}
+ return null;
}
/**
- * Gets value for key using findNode.
- * @param okey the key
+ * Gets value for key. Almost the same as findNode, but returns
+ * the found value (to avoid retries during re-reads)
+ *
+ * @param key the key
* @return the value, or null if absent
*/
- private V doGet(Object okey) {
- Comparable<? super K> key = comparable(okey);
- /*
- * Loop needed here and elsewhere in case value field goes
- * null just as it is about to be returned, in which case we
- * lost a race with a deletion, so must retry.
- */
- for (;;) {
- Node<K,V> n = findNode(key);
- if (n == null)
- return null;
- Object v = n.value;
- if (v != null)
- return (V)v;
+ private V doGet(Object key) {
+ if (key == null)
+ throw new NullPointerException();
+ Comparator<? super K> cmp = comparator;
+ outer: for (;;) {
+ for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
+ Object v; int c;
+ if (n == null)
+ break outer;
+ Node<K,V> f = n.next;
+ if (n != b.next) // inconsistent read
+ break;
+ if ((v = n.value) == null) { // n is deleted
+ n.helpDelete(b, f);
+ break;
+ }
+ if (b.value == null || v == n) // b is deleted
+ break;
+ if ((c = cpr(cmp, key, n.key)) == 0) {
+ @SuppressWarnings("unchecked") V vv = (V)v;
+ return vv;
+ }
+ if (c < 0)
+ break outer;
+ b = n;
+ n = f;
+ }
}
+ return null;
}
/* ---------------- Insertion -------------- */
@@ -839,187 +805,126 @@
/**
* Main insertion method. Adds element if not present, or
* replaces value if present and onlyIfAbsent is false.
- * @param kkey the key
- * @param value the value that must be associated with key
+ * @param key the key
+ * @param value the value that must be associated with key
* @param onlyIfAbsent if should not insert if already present
* @return the old value, or null if newly inserted
*/
- private V doPut(K kkey, V value, boolean onlyIfAbsent) {
- Comparable<? super K> key = comparable(kkey);
- for (;;) {
- Node<K,V> b = findPredecessor(key);
- Node<K,V> n = b.next;
- for (;;) {
+ private V doPut(K key, V value, boolean onlyIfAbsent) {
+ Node<K,V> z; // added node
+ if (key == null)
+ throw new NullPointerException();
+ Comparator<? super K> cmp = comparator;
+ outer: for (;;) {
+ for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
if (n != null) {
+ Object v; int c;
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read
break;
- Object v = n.value;
- if (v == null) { // n is deleted
+ if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
- if (v == n || b.value == null) // b is deleted
+ if (b.value == null || v == n) // b is deleted
break;
- int c = key.compareTo(n.key);
- if (c > 0) {
+ if ((c = cpr(cmp, key, n.key)) > 0) {
b = n;
n = f;
continue;
}
if (c == 0) {
- if (onlyIfAbsent || n.casValue(v, value))
- return (V)v;
- else
- break; // restart if lost race to replace value
+ if (onlyIfAbsent || n.casValue(v, value)) {
+ @SuppressWarnings("unchecked") V vv = (V)v;
+ return vv;
+ }
+ break; // restart if lost race to replace value
}
// else c < 0; fall through
}
- Node<K,V> z = new Node<K,V>(kkey, value, n);
+ z = new Node<K,V>(key, value, n);
if (!b.casNext(n, z))
break; // restart if lost race to append to b
- int level = randomLevel();
- if (level > 0)
- insertIndex(z, level);
- return null;
+ break outer;
}
}
- }
- /**
- * Returns a random level for inserting a new node.
- * Hardwired to k=1, p=0.5, max 31 (see above and
- * Pugh's "Skip List Cookbook", sec 3.4).
- *
- * This uses the simplest of the generators described in George
- * Marsaglia's "Xorshift RNGs" paper. This is not a high-quality
- * generator but is acceptable here.
- */
- private int randomLevel() {
- int x = randomSeed;
- x ^= x << 13;
- x ^= x >>> 17;
- randomSeed = x ^= x << 5;
- if ((x & 0x80000001) != 0) // test highest and lowest bits
- return 0;
- int level = 1;
- while (((x >>>= 1) & 1) != 0) ++level;
- return level;
- }
-
- /**
- * Creates and adds index nodes for the given node.
- * @param z the node
- * @param level the level of the index
- */
- private void insertIndex(Node<K,V> z, int level) {
- HeadIndex<K,V> h = head;
- int max = h.level;
-
- if (level <= max) {
+ int rnd = ThreadLocalRandom.nextSecondarySeed();
+ if ((rnd & 0x80000001) == 0) { // test highest and lowest bits
+ int level = 1, max;
+ while (((rnd >>>= 1) & 1) != 0)
+ ++level;
Index<K,V> idx = null;
- for (int i = 1; i <= level; ++i)
- idx = new Index<K,V>(z, idx, null);
- addIndex(idx, h, level);
-
- } else { // Add a new level
- /*
- * To reduce interference by other threads checking for
- * empty levels in tryReduceLevel, new levels are added
- * with initialized right pointers. Which in turn requires
- * keeping levels in an array to access them while
- * creating new head index nodes from the opposite
- * direction.
- */
- level = max + 1;
- Index<K,V>[] idxs = (Index<K,V>[])new Index<?,?>[level+1];
- Index<K,V> idx = null;
- for (int i = 1; i <= level; ++i)
- idxs[i] = idx = new Index<K,V>(z, idx, null);
-
- HeadIndex<K,V> oldh;
- int k;
- for (;;) {
- oldh = head;
- int oldLevel = oldh.level;
- if (level <= oldLevel) { // lost race to add level
- k = level;
- break;
- }
- HeadIndex<K,V> newh = oldh;
- Node<K,V> oldbase = oldh.node;
- for (int j = oldLevel+1; j <= level; ++j)
- newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
- if (casHead(oldh, newh)) {
- k = oldLevel;
- break;
+ HeadIndex<K,V> h = head;
+ if (level <= (max = h.level)) {
+ for (int i = 1; i <= level; ++i)
+ idx = new Index<K,V>(z, idx, null);
+ }
+ else { // try to grow by one level
+ level = max + 1; // hold in array and later pick the one to use
+ @SuppressWarnings("unchecked")Index<K,V>[] idxs =
+ (Index<K,V>[])new Index<?,?>[level+1];
+ for (int i = 1; i <= level; ++i)
+ idxs[i] = idx = new Index<K,V>(z, idx, null);
+ for (;;) {
+ h = head;
+ int oldLevel = h.level;
+ if (level <= oldLevel) // lost race to add level
+ break;
+ HeadIndex<K,V> newh = h;
+ Node<K,V> oldbase = h.node;
+ for (int j = oldLevel+1; j <= level; ++j)
+ newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
+ if (casHead(h, newh)) {
+ h = newh;
+ idx = idxs[level = oldLevel];
+ break;
+ }
}
}
- addIndex(idxs[k], oldh, k);
- }
- }
-
- /**
- * Adds given index nodes from given level down to 1.
- * @param idx the topmost index node being inserted
- * @param h the value of head to use to insert. This must be
- * snapshotted by callers to provide correct insertion level
- * @param indexLevel the level of the index
- */
- private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) {
- // Track next level to insert in case of retries
- int insertionLevel = indexLevel;
- Comparable<? super K> key = comparable(idx.node.key);
- if (key == null) throw new NullPointerException();
+ // find insertion points and splice in
+ splice: for (int insertionLevel = level;;) {
+ int j = h.level;
+ for (Index<K,V> q = h, r = q.right, t = idx;;) {
+ if (q == null || t == null)
+ break splice;
+ if (r != null) {
+ Node<K,V> n = r.node;
+ // compare before deletion check avoids needing recheck
+ int c = cpr(cmp, key, n.key);
+ if (n.value == null) {
+ if (!q.unlink(r))
+ break;
+ r = q.right;
+ continue;
+ }
+ if (c > 0) {
+ q = r;
+ r = r.right;
+ continue;
+ }
+ }
- // Similar to findPredecessor, but adding index nodes along
- // path to key.
- for (;;) {
- int j = h.level;
- Index<K,V> q = h;
- Index<K,V> r = q.right;
- Index<K,V> t = idx;
- for (;;) {
- if (r != null) {
- Node<K,V> n = r.node;
- // compare before deletion check avoids needing recheck
- int c = key.compareTo(n.key);
- if (n.value == null) {
- if (!q.unlink(r))
- break;
- r = q.right;
- continue;
- }
- if (c > 0) {
- q = r;
- r = r.right;
- continue;
+ if (j == insertionLevel) {
+ if (!q.link(r, t))
+ break; // restart
+ if (t.node.value == null) {
+ findNode(key);
+ break splice;
+ }
+ if (--insertionLevel == 0)
+ break splice;
}
+
+ if (--j >= insertionLevel && j < level)
+ t = t.down;
+ q = q.down;
+ r = q.right;
}
-
- if (j == insertionLevel) {
- // Don't insert index if node already deleted
- if (t.indexesDeletedNode()) {
- findNode(key); // cleans up
- return;
- }
- if (!q.link(r, t))
- break; // restart
- if (--insertionLevel == 0) {
- // need final deletion check before return
- if (t.indexesDeletedNode())
- findNode(key);
- return;
- }
- }
-
- if (--j >= insertionLevel && j < indexLevel)
- t = t.down;
- q = q.down;
- r = q.right;
}
}
+ return null;
}
/* ---------------- Deletion -------------- */
@@ -1038,51 +943,52 @@
* search for it, and we'd like to ensure lack of garbage
* retention, so must call to be sure.
*
- * @param okey the key
+ * @param key the key
* @param value if non-null, the value that must be
* associated with key
* @return the node, or null if not found
*/
- final V doRemove(Object okey, Object value) {
- Comparable<? super K> key = comparable(okey);
- for (;;) {
- Node<K,V> b = findPredecessor(key);
- Node<K,V> n = b.next;
- for (;;) {
+ final V doRemove(Object key, Object value) {
+ if (key == null)
+ throw new NullPointerException();
+ Comparator<? super K> cmp = comparator;
+ outer: for (;;) {
+ for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
+ Object v; int c;
if (n == null)
- return null;
+ break outer;
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read
break;
- Object v = n.value;
- if (v == null) { // n is deleted
+ if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
- if (v == n || b.value == null) // b is deleted
+ if (b.value == null || v == n) // b is deleted
break;
- int c = key.compareTo(n.key);
- if (c < 0)
- return null;
+ if ((c = cpr(cmp, key, n.key)) < 0)
+ break outer;
if (c > 0) {
b = n;
n = f;
continue;
}
if (value != null && !value.equals(v))
- return null;
+ break outer;
if (!n.casValue(v, null))
break;
if (!n.appendMarker(f) || !b.casNext(n, f))
- findNode(key); // Retry via findNode
+ findNode(key); // retry via findNode
else {
- findPredecessor(key); // Clean index
+ findPredecessor(key, cmp); // clean index
if (head.right == null)
tryReduceLevel();
}
- return (V)v;
+ @SuppressWarnings("unchecked") V vv = (V)v;
+ return vv;
}
}
+ return null;
}
/**
@@ -1126,11 +1032,9 @@
* Specialized variant of findNode to get first valid node.
* @return first node or null if empty
*/
- Node<K,V> findFirst() {
- for (;;) {
- Node<K,V> b = head.node;
- Node<K,V> n = b.next;
- if (n == null)
+ final Node<K,V> findFirst() {
+ for (Node<K,V> b, n;;) {
+ if ((n = (b = head.node).next) == null)
return null;
if (n.value != null)
return n;
@@ -1142,11 +1046,9 @@
* Removes first entry; returns its snapshot.
* @return null if empty, else snapshot of first entry
*/
- Map.Entry<K,V> doRemoveFirstEntry() {
- for (;;) {
- Node<K,V> b = head.node;
- Node<K,V> n = b.next;
- if (n == null)
+ private Map.Entry<K,V> doRemoveFirstEntry() {
+ for (Node<K,V> b, n;;) {
+ if ((n = (b = head.node).next) == null)
return null;
Node<K,V> f = n.next;
if (n != b.next)
@@ -1161,7 +1063,8 @@
if (!n.appendMarker(f) || !b.casNext(n, f))
findFirst(); // retry
clearIndexToFirst();
- return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, (V)v);
+ @SuppressWarnings("unchecked") V vv = (V)v;
+ return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, vv);
}
}
@@ -1170,8 +1073,7 @@
*/
private void clearIndexToFirst() {
for (;;) {
- Index<K,V> q = head;
- for (;;) {
+ for (Index<K,V> q = head;;) {
Index<K,V> r = q.right;
if (r != null && r.indexesDeletedNode() && !q.unlink(r))
break;
@@ -1184,6 +1086,52 @@
}
}
+ /**
+ * Removes last entry; returns its snapshot.
+ * Specialized variant of doRemove.
+ * @return null if empty, else snapshot of last entry
+ */
+ private Map.Entry<K,V> doRemoveLastEntry() {
+ for (;;) {
+ Node<K,V> b = findPredecessorOfLast();
+ Node<K,V> n = b.next;
+ if (n == null) {
+ if (b.isBaseHeader()) // empty
+ return null;
+ else
+ continue; // all b's successors are deleted; retry
+ }
+ for (;;) {
+ Node<K,V> f = n.next;
+ if (n != b.next) // inconsistent read
+ break;
+ Object v = n.value;
+ if (v == null) { // n is deleted
+ n.helpDelete(b, f);
+ break;
+ }
+ if (b.value == null || v == n) // b is deleted
+ break;
+ if (f != null) {
+ b = n;
+ n = f;
+ continue;
+ }
+ if (!n.casValue(v, null))
+ break;
+ K key = n.key;
+ if (!n.appendMarker(f) || !b.casNext(n, f))
+ findNode(key); // retry via findNode
+ else { // clean index
+ findPredecessor(key, comparator);
+ if (head.right == null)
+ tryReduceLevel();
+ }
+ @SuppressWarnings("unchecked") V vv = (V)v;
+ return new AbstractMap.SimpleImmutableEntry<K,V>(key, vv);
+ }
+ }
+ }
/* ---------------- Finding and removing last element -------------- */
@@ -1191,7 +1139,7 @@
* Specialized version of find to get last valid node.
* @return last node or null if empty
*/
- Node<K,V> findLast() {
+ final Node<K,V> findLast() {
/*
* findPredecessor can't be used to traverse index level
* because this doesn't use comparisons. So traversals of
@@ -1210,9 +1158,7 @@
} else if ((d = q.down) != null) {
q = d;
} else {
- Node<K,V> b = q.node;
- Node<K,V> n = b.next;
- for (;;) {
+ for (Node<K,V> b = q.node, n = b.next;;) {
if (n == null)
return b.isBaseHeader() ? null : b;
Node<K,V> f = n.next; // inconsistent read
@@ -1223,7 +1169,7 @@
n.helpDelete(b, f);
break;
}
- if (v == n || b.value == null) // b is deleted
+ if (b.value == null || v == n) // b is deleted
break;
b = n;
n = f;
@@ -1242,8 +1188,7 @@
*/
private Node<K,V> findPredecessorOfLast() {
for (;;) {
- Index<K,V> q = head;
- for (;;) {
+ for (Index<K,V> q = head;;) {
Index<K,V> d, r;
if ((r = q.right) != null) {
if (r.indexesDeletedNode()) {
@@ -1264,53 +1209,6 @@
}
}
- /**
- * Removes last entry; returns its snapshot.
- * Specialized variant of doRemove.
- * @return null if empty, else snapshot of last entry
- */
- Map.Entry<K,V> doRemoveLastEntry() {
- for (;;) {
- Node<K,V> b = findPredecessorOfLast();
- Node<K,V> n = b.next;
- if (n == null) {
- if (b.isBaseHeader()) // empty
- return null;
- else
- continue; // all b's successors are deleted; retry
- }
- for (;;) {
- Node<K,V> f = n.next;
- if (n != b.next) // inconsistent read
- break;
- Object v = n.value;
- if (v == null) { // n is deleted
- n.helpDelete(b, f);
- break;
- }
- if (v == n || b.value == null) // b is deleted
- break;
- if (f != null) {
- b = n;
- n = f;
- continue;
- }
- if (!n.casValue(v, null))
- break;
- K key = n.key;
- Comparable<? super K> ck = comparable(key);
- if (!n.appendMarker(f) || !b.casNext(n, f))
- findNode(ck); // Retry via findNode
- else {
- findPredecessor(ck); // Clean index
- if (head.right == null)
- tryReduceLevel();
- }
- return new AbstractMap.SimpleImmutableEntry<K,V>(key, (V)v);
- }
- }
- }
-
/* ---------------- Relational operations -------------- */
// Control values OR'ed as arguments to findNear
@@ -1321,29 +1219,28 @@
/**
* Utility for ceiling, floor, lower, higher methods.
- * @param kkey the key
+ * @param key the key
* @param rel the relation -- OR'ed combination of EQ, LT, GT
* @return nearest node fitting relation, or null if no such
*/
- Node<K,V> findNear(K kkey, int rel) {
- Comparable<? super K> key = comparable(kkey);
+ final Node<K,V> findNear(K key, int rel, Comparator<? super K> cmp) {
+ if (key == null)
+ throw new NullPointerException();
for (;;) {
- Node<K,V> b = findPredecessor(key);
- Node<K,V> n = b.next;
- for (;;) {
+ for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
+ Object v;
if (n == null)
return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read
break;
- Object v = n.value;
- if (v == null) { // n is deleted
+ if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
- if (v == n || b.value == null) // b is deleted
+ if (b.value == null || v == n) // b is deleted
break;
- int c = key.compareTo(n.key);
+ int c = cpr(cmp, key, n.key);
if ((c == 0 && (rel & EQ) != 0) ||
(c < 0 && (rel & LT) == 0))
return n;
@@ -1361,9 +1258,10 @@
* @param rel the relation -- OR'ed combination of EQ, LT, GT
* @return Entry fitting relation, or null if no such
*/
- AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) {
+ final AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) {
+ Comparator<? super K> cmp = comparator;
for (;;) {
- Node<K,V> n = findNear(key, rel);
+ Node<K,V> n = findNear(key, rel, cmp);
if (n == null)
return null;
AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
@@ -1372,7 +1270,6 @@
}
}
-
/* ---------------- Constructors -------------- */
/**
@@ -1389,7 +1286,7 @@
* comparator.
*
* @param comparator the comparator that will be used to order this map.
- * If <tt>null</tt>, the {@linkplain Comparable natural
+ * If {@code null}, the {@linkplain Comparable natural
* ordering} of the keys will be used.
*/
public ConcurrentSkipListMap(Comparator<? super K> comparator) {
@@ -1403,7 +1300,7 @@
* the keys.
*
* @param m the map whose mappings are to be placed in this map
- * @throws ClassCastException if the keys in <tt>m</tt> are not
+ * @throws ClassCastException if the keys in {@code m} are not
* {@link Comparable}, or are not mutually comparable
* @throws NullPointerException if the specified map or any of its keys
* or values are null
@@ -1430,7 +1327,7 @@
}
/**
- * Returns a shallow copy of this <tt>ConcurrentSkipListMap</tt>
+ * Returns a shallow copy of this {@code ConcurrentSkipListMap}
* instance. (The keys and values themselves are not cloned.)
*
* @return a shallow copy of this map
@@ -1477,8 +1374,14 @@
map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<? extends K, ? extends V> e = it.next();
- int j = randomLevel();
- if (j > h.level) j = h.level + 1;
+ int rnd = ThreadLocalRandom.current().nextInt();
+ int j = 0;
+ if ((rnd & 0x80000001) == 0) {
+ do {
+ ++j;
+ } while (((rnd >>>= 1) & 1) != 0);
+ if (j > h.level) j = h.level + 1;
+ }
K k = e.getKey();
V v = e.getValue();
if (k == null || v == null)
@@ -1511,7 +1414,7 @@
*
* @serialData The key (Object) and value (Object) for each
* key-value mapping represented by the map, followed by
- * <tt>null</tt>. The key-value mappings are emitted in key-order
+ * {@code null}. The key-value mappings are emitted in key-order
* (as determined by the Comparator, or by the keys' natural
* ordering if no Comparator).
*/
@@ -1534,6 +1437,7 @@
/**
* Reconstitutes this map from a stream (that is, deserializes it).
*/
+ @SuppressWarnings("unchecked")
private void readObject(final java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in the Comparator and any hidden stuff
@@ -1569,8 +1473,14 @@
throw new NullPointerException();
K key = (K) k;
V val = (V) v;
- int j = randomLevel();
- if (j > h.level) j = h.level + 1;
+ int rnd = ThreadLocalRandom.current().nextInt();
+ int j = 0;
+ if ((rnd & 0x80000001) == 0) {
+ do {
+ ++j;
+ } while (((rnd >>>= 1) & 1) != 0);
+ if (j > h.level) j = h.level + 1;
+ }
Node<K,V> z = new Node<K,V>(key, val, null);
basepred.next = z;
basepred = z;
@@ -1595,11 +1505,11 @@
/* ------ Map API methods ------ */
/**
- * Returns <tt>true</tt> if this map contains a mapping for the specified
+ * Returns {@code true} if this map contains a mapping for the specified
* key.
*
* @param key key whose presence in this map is to be tested
- * @return <tt>true</tt> if this map contains a mapping for the specified key
+ * @return {@code true} if this map contains a mapping for the specified key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
@@ -1627,6 +1537,22 @@
}
/**
+ * Returns the value to which the specified key is mapped,
+ * or the given defaultValue if this map contains no mapping for the key.
+ *
+ * @param key the key
+ * @param defaultValue the value to return if this map contains
+ * no mapping for the given key
+ * @return the mapping for the key, if present; else the defaultValue
+ * @throws NullPointerException if the specified key is null
+ * @since 1.8
+ */
+ public V getOrDefault(Object key, V defaultValue) {
+ V v;
+ return (v = doGet(key)) == null ? defaultValue : v;
+ }
+
+ /**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
@@ -1634,7 +1560,7 @@
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with the specified key, or
- * <tt>null</tt> if there was no mapping for the key
+ * {@code null} if there was no mapping for the key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key or value is null
@@ -1650,7 +1576,7 @@
*
* @param key key for which mapping should be removed
* @return the previous value associated with the specified key, or
- * <tt>null</tt> if there was no mapping for the key
+ * {@code null} if there was no mapping for the key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
@@ -1660,15 +1586,15 @@
}
/**
- * Returns <tt>true</tt> if this map maps one or more keys to the
+ * Returns {@code true} if this map maps one or more keys to the
* specified value. This operation requires time linear in the
* map size. Additionally, it is possible for the map to change
* during execution of this method, in which case the returned
* result may be inaccurate.
*
* @param value value whose presence in this map is to be tested
- * @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
- * <tt>false</tt> otherwise
+ * @return {@code true} if a mapping to {@code value} exists;
+ * {@code false} otherwise
* @throws NullPointerException if the specified value is null
*/
public boolean containsValue(Object value) {
@@ -1684,8 +1610,8 @@
/**
* Returns the number of key-value mappings in this map. If this map
- * contains more than <tt>Integer.MAX_VALUE</tt> elements, it
- * returns <tt>Integer.MAX_VALUE</tt>.
+ * contains more than {@code Integer.MAX_VALUE} elements, it
+ * returns {@code Integer.MAX_VALUE}.
*
* <p>Beware that, unlike in most collections, this method is
* <em>NOT</em> a constant-time operation. Because of the
@@ -1708,8 +1634,8 @@
}
/**
- * Returns <tt>true</tt> if this map contains no key-value mappings.
- * @return <tt>true</tt> if this map contains no key-value mappings
+ * Returns {@code true} if this map contains no key-value mappings.
+ * @return {@code true} if this map contains no key-value mappings
*/
public boolean isEmpty() {
return findFirst() == null;
@@ -1722,6 +1648,140 @@
initialize();
}
+ /**
+ * If the specified key is not already associated with a value,
+ * attempts to compute its value using the given mapping function
+ * and enters it into this map unless {@code null}. The function
+ * is <em>NOT</em> guaranteed to be applied once atomically only
+ * if the value is not present.
+ *
+ * @param key key with which the specified value is to be associated
+ * @param mappingFunction the function to compute a value
+ * @return the current (existing or computed) value associated with
+ * the specified key, or null if the computed value is null
+ * @throws NullPointerException if the specified key is null
+ * or the mappingFunction is null
+ * @since 1.8
+ */
+ public V computeIfAbsent(K key,
+ Function<? super K, ? extends V> mappingFunction) {
+ if (key == null || mappingFunction == null)
+ throw new NullPointerException();
+ V v, p, r;
+ if ((v = doGet(key)) == null &&
+ (r = mappingFunction.apply(key)) != null)
+ v = (p = doPut(key, r, true)) == null ? r : p;
+ return v;
+ }
+
+ /**
+ * If the value for the specified key is present, attempts to
+ * compute a new mapping given the key and its current mapped
+ * value. The function is <em>NOT</em> guaranteed to be applied
+ * once atomically.
+ *
+ * @param key key with which a value may be associated
+ * @param remappingFunction the function to compute a value
+ * @return the new value associated with the specified key, or null if none
+ * @throws NullPointerException if the specified key is null
+ * or the remappingFunction is null
+ * @since 1.8
+ */
+ public V computeIfPresent(K key,
+ BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+ if (key == null || remappingFunction == null)
+ throw new NullPointerException();
+ Node<K,V> n; Object v;
+ while ((n = findNode(key)) != null) {
+ if ((v = n.value) != null) {
+ @SuppressWarnings("unchecked") V vv = (V) v;
+ V r = remappingFunction.apply(key, vv);
+ if (r != null) {
+ if (n.casValue(vv, r))
+ return r;
+ }
+ else if (doRemove(key, vv) != null)
+ break;
+ }
+ }
+ return null;
+ }
+
+ /**
+ * Attempts to compute a mapping for the specified key and its
+ * current mapped value (or {@code null} if there is no current
+ * mapping). The function is <em>NOT</em> guaranteed to be applied
+ * once atomically.
+ *
+ * @param key key with which the specified value is to be associated
+ * @param remappingFunction the function to compute a value
+ * @return the new value associated with the specified key, or null if none
+ * @throws NullPointerException if the specified key is null
+ * or the remappingFunction is null
+ * @since 1.8
+ */
+ public V compute(K key,
+ BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+ if (key == null || remappingFunction == null)
+ throw new NullPointerException();
+ for (;;) {
+ Node<K,V> n; Object v; V r;
+ if ((n = findNode(key)) == null) {
+ if ((r = remappingFunction.apply(key, null)) == null)
+ break;
+ if (doPut(key, r, true) == null)
+ return r;
+ }
+ else if ((v = n.value) != null) {
+ @SuppressWarnings("unchecked") V vv = (V) v;
+ if ((r = remappingFunction.apply(key, vv)) != null) {
+ if (n.casValue(vv, r))
+ return r;
+ }
+ else if (doRemove(key, vv) != null)
+ break;
+ }
+ }
+ return null;
+ }
+
+ /**
+ * If the specified key is not already associated with a value,
+ * associates it with the given value. Otherwise, replaces the
+ * value with the results of the given remapping function, or
+ * removes if {@code null}. The function is <em>NOT</em>
+ * guaranteed to be applied once atomically.
+ *
+ * @param key key with which the specified value is to be associated
+ * @param value the value to use if absent
+ * @param remappingFunction the function to recompute a value if present
+ * @return the new value associated with the specified key, or null if none
+ * @throws NullPointerException if the specified key or value is null
+ * or the remappingFunction is null
+ * @since 1.8
+ */
+ public V merge(K key, V value,
+ BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
+ if (key == null || value == null || remappingFunction == null)
+ throw new NullPointerException();
+ for (;;) {
+ Node<K,V> n; Object v; V r;
+ if ((n = findNode(key)) == null) {
+ if (doPut(key, value, true) == null)
+ return value;
+ }
+ else if ((v = n.value) != null) {
+ @SuppressWarnings("unchecked") V vv = (V) v;
+ if ((r = remappingFunction.apply(vv, value)) != null) {
+ if (n.casValue(vv, r))
+ return r;
+ }
+ else if (doRemove(key, vv) != null)
+ return null;
+ }
+ }
+ }
+
/* ---------------- View methods -------------- */
/*
@@ -1744,11 +1804,11 @@
* operations. It does not support the {@code add} or {@code addAll}
* operations.
*
- * <p>The view's {@code iterator} is a "weakly consistent" iterator
- * that will never throw {@link 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.
+ * <p>The view's {@code 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.
*
* <p>This method is equivalent to method {@code navigableKeySet}.
*
@@ -1771,16 +1831,16 @@
* The collection is backed by the map, so changes to the map are
* reflected in the collection, and vice-versa. The collection
* supports element removal, which removes the corresponding
- * mapping from the map, via the <tt>Iterator.remove</tt>,
- * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
- * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
- * support the <tt>add</tt> or <tt>addAll</tt> operations.
+ * mapping from the map, via the {@code Iterator.remove},
+ * {@code Collection.remove}, {@code removeAll},
+ * {@code retainAll} and {@code clear} operations. It does not
+ * support the {@code add} or {@code addAll} operations.
*
- * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
- * that will never throw {@link 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.
+ * <p>The view's {@code 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.
*/
public Collection<V> values() {
Values<V> vs = values;
@@ -1793,20 +1853,20 @@
* The set is backed by the map, so changes to the map are
* reflected in the set, and vice-versa. The set supports element
* removal, which removes the corresponding mapping from the map,
- * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
- * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
- * operations. It does not support the <tt>add</tt> or
- * <tt>addAll</tt> operations.
+ * via the {@code Iterator.remove}, {@code Set.remove},
+ * {@code removeAll}, {@code retainAll} and {@code clear}
+ * operations. It does not support the {@code add} or
+ * {@code addAll} operations.
*
- * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
- * that will never throw {@link 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.
+ * <p>The view's {@code 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.
*
- * <p>The <tt>Map.Entry</tt> elements returned by
- * <tt>iterator.next()</tt> do <em>not</em> support the
- * <tt>setValue</tt> operation.
+ * <p>The {@code Map.Entry} elements returned by
+ * {@code iterator.next()} do <em>not</em> support the
+ * {@code setValue} operation.
*
* @return a set view of the mappings contained in this map,
* sorted in ascending key order
@@ -1830,15 +1890,15 @@
/**
* Compares the specified object with this map for equality.
- * Returns <tt>true</tt> if the given object is also a map and the
+ * Returns {@code true} if the given object is also a map and the
* two maps represent the same mappings. More formally, two maps
- * <tt>m1</tt> and <tt>m2</tt> represent the same mappings if
- * <tt>m1.entrySet().equals(m2.entrySet())</tt>. This
+ * {@code m1} and {@code m2} represent the same mappings if
+ * {@code m1.entrySet().equals(m2.entrySet())}. This
* operation may return misleading results if either map is
* concurrently modified during execution of this method.
*
* @param o object to be compared for equality with this map
- * @return <tt>true</tt> if the specified object is equal to this map
+ * @return {@code true} if the specified object is equal to this map
*/
public boolean equals(Object o) {
if (o == this)
@@ -1870,7 +1930,7 @@
* {@inheritDoc}
*
* @return the previous value associated with the specified key,
- * or <tt>null</tt> if there was no mapping for the key
+ * or {@code null} if there was no mapping for the key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key or value is null
@@ -1891,9 +1951,7 @@
public boolean remove(Object key, Object value) {
if (key == null)
throw new NullPointerException();
- if (value == null)
- return false;
- return doRemove(key, value) != null;
+ return value != null && doRemove(key, value) != null;
}
/**
@@ -1904,15 +1962,13 @@
* @throws NullPointerException if any of the arguments are null
*/
public boolean replace(K key, V oldValue, V newValue) {
- if (oldValue == null || newValue == null)
+ if (key == null || oldValue == null || newValue == null)
throw new NullPointerException();
- Comparable<? super K> k = comparable(key);
for (;;) {
- Node<K,V> n = findNode(k);
- if (n == null)
+ Node<K,V> n; Object v;
+ if ((n = findNode(key)) == null)
return false;
- Object v = n.value;
- if (v != null) {
+ if ((v = n.value) != null) {
if (!oldValue.equals(v))
return false;
if (n.casValue(v, newValue))
@@ -1925,22 +1981,22 @@
* {@inheritDoc}
*
* @return the previous value associated with the specified key,
- * or <tt>null</tt> if there was no mapping for the key
+ * or {@code null} if there was no mapping for the key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key or value is null
*/
public V replace(K key, V value) {
- if (value == null)
+ if (key == null || value == null)
throw new NullPointerException();
- Comparable<? super K> k = comparable(key);
for (;;) {
- Node<K,V> n = findNode(k);
- if (n == null)
+ Node<K,V> n; Object v;
+ if ((n = findNode(key)) == null)
return null;
- Object v = n.value;
- if (v != null && n.casValue(v, value))
- return (V)v;
+ if ((v = n.value) != null && n.casValue(v, value)) {
+ @SuppressWarnings("unchecked") V vv = (V)v;
+ return vv;
+ }
}
}
@@ -2042,9 +2098,9 @@
/**
* Returns a key-value mapping associated with the greatest key
- * strictly less than the given key, or <tt>null</tt> if there is
+ * strictly less than the given key, or {@code null} if there is
* no such key. The returned entry does <em>not</em> support the
- * <tt>Entry.setValue</tt> method.
+ * {@code Entry.setValue} method.
*
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if the specified key is null
@@ -2058,15 +2114,15 @@
* @throws NullPointerException if the specified key is null
*/
public K lowerKey(K key) {
- Node<K,V> n = findNear(key, LT);
+ Node<K,V> n = findNear(key, LT, comparator);
return (n == null) ? null : n.key;
}
/**
* Returns a key-value mapping associated with the greatest key
- * less than or equal to the given key, or <tt>null</tt> if there
+ * less than or equal to the given key, or {@code null} if there
* is no such key. The returned entry does <em>not</em> support
- * the <tt>Entry.setValue</tt> method.
+ * the {@code Entry.setValue} method.
*
* @param key the key
* @throws ClassCastException {@inheritDoc}
@@ -2082,15 +2138,15 @@
* @throws NullPointerException if the specified key is null
*/
public K floorKey(K key) {
- Node<K,V> n = findNear(key, LT|EQ);
+ Node<K,V> n = findNear(key, LT|EQ, comparator);
return (n == null) ? null : n.key;
}
/**
* Returns a key-value mapping associated with the least key
- * greater than or equal to the given key, or <tt>null</tt> if
+ * greater than or equal to the given key, or {@code null} if
* there is no such entry. The returned entry does <em>not</em>
- * support the <tt>Entry.setValue</tt> method.
+ * support the {@code Entry.setValue} method.
*
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if the specified key is null
@@ -2104,15 +2160,15 @@
* @throws NullPointerException if the specified key is null
*/
public K ceilingKey(K key) {
- Node<K,V> n = findNear(key, GT|EQ);
+ Node<K,V> n = findNear(key, GT|EQ, comparator);
return (n == null) ? null : n.key;
}
/**
* Returns a key-value mapping associated with the least key
- * strictly greater than the given key, or <tt>null</tt> if there
+ * strictly greater than the given key, or {@code null} if there
* is no such key. The returned entry does <em>not</em> support
- * the <tt>Entry.setValue</tt> method.
+ * the {@code Entry.setValue} method.
*
* @param key the key
* @throws ClassCastException {@inheritDoc}
@@ -2128,15 +2184,15 @@
* @throws NullPointerException if the specified key is null
*/
public K higherKey(K key) {
- Node<K,V> n = findNear(key, GT);
+ Node<K,V> n = findNear(key, GT, comparator);
return (n == null) ? null : n.key;
}
/**
* Returns a key-value mapping associated with the least
- * key in this map, or <tt>null</tt> if the map is empty.
+ * key in this map, or {@code null} if the map is empty.
* The returned entry does <em>not</em> support
- * the <tt>Entry.setValue</tt> method.
+ * the {@code Entry.setValue} method.
*/
public Map.Entry<K,V> firstEntry() {
for (;;) {
@@ -2151,9 +2207,9 @@
/**
* Returns a key-value mapping associated with the greatest
- * key in this map, or <tt>null</tt> if the map is empty.
+ * key in this map, or {@code null} if the map is empty.
* The returned entry does <em>not</em> support
- * the <tt>Entry.setValue</tt> method.
+ * the {@code Entry.setValue} method.
*/
public Map.Entry<K,V> lastEntry() {
for (;;) {
@@ -2168,9 +2224,9 @@
/**
* Removes and returns a key-value mapping associated with
- * the least key in this map, or <tt>null</tt> if the map is empty.
+ * the least key in this map, or {@code null} if the map is empty.
* The returned entry does <em>not</em> support
- * the <tt>Entry.setValue</tt> method.
+ * the {@code Entry.setValue} method.
*/
public Map.Entry<K,V> pollFirstEntry() {
return doRemoveFirstEntry();
@@ -2178,9 +2234,9 @@
/**
* Removes and returns a key-value mapping associated with
- * the greatest key in this map, or <tt>null</tt> if the map is empty.
+ * the greatest key in this map, or {@code null} if the map is empty.
* The returned entry does <em>not</em> support
- * the <tt>Entry.setValue</tt> method.
+ * the {@code Entry.setValue} method.
*/
public Map.Entry<K,V> pollLastEntry() {
return doRemoveLastEntry();
@@ -2202,13 +2258,11 @@
/** Initializes ascending iterator for entire range. */
Iter() {
- for (;;) {
- next = findFirst();
- if (next == null)
- break;
+ while ((next = findFirst()) != null) {
Object x = next.value;
if (x != null && x != next) {
- nextValue = (V) x;
+ @SuppressWarnings("unchecked") V vv = (V)x;
+ nextValue = vv;
break;
}
}
@@ -2223,13 +2277,11 @@
if (next == null)
throw new NoSuchElementException();
lastReturned = next;
- for (;;) {
- next = next.next;
- if (next == null)
- break;
+ while ((next = next.next) != null) {
Object x = next.value;
if (x != null && x != next) {
- nextValue = (V) x;
+ @SuppressWarnings("unchecked") V vv = (V)x;
+ nextValue = vv;
break;
}
}
@@ -2296,7 +2348,7 @@
static final <E> List<E> toList(Collection<E> c) {
// Using size() here would be a pessimization.
- List<E> list = new ArrayList<E>();
+ ArrayList<E> list = new ArrayList<E>();
for (E e : c)
list.add(e);
return list;
@@ -2304,7 +2356,7 @@
static final class KeySet<E>
extends AbstractSet<E> implements NavigableSet<E> {
- private final ConcurrentNavigableMap<E,?> m;
+ final ConcurrentNavigableMap<E,?> m;
KeySet(ConcurrentNavigableMap<E,?> map) { m = map; }
public int size() { return m.size(); }
public boolean isEmpty() { return m.isEmpty(); }
@@ -2326,6 +2378,7 @@
Map.Entry<E,?> e = m.pollLastEntry();
return (e == null) ? null : e.getKey();
}
+ @SuppressWarnings("unchecked")
public Iterator<E> iterator() {
if (m instanceof ConcurrentSkipListMap)
return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();
@@ -2376,13 +2429,21 @@
public NavigableSet<E> descendingSet() {
return new KeySet<E>(m.descendingMap());
}
+ @SuppressWarnings("unchecked")
+ public Spliterator<E> spliterator() {
+ if (m instanceof ConcurrentSkipListMap)
+ return ((ConcurrentSkipListMap<E,?>)m).keySpliterator();
+ else
+ return (Spliterator<E>)((SubMap<E,?>)m).keyIterator();
+ }
}
static final class Values<E> extends AbstractCollection<E> {
- private final ConcurrentNavigableMap<?, E> m;
+ final ConcurrentNavigableMap<?, E> m;
Values(ConcurrentNavigableMap<?, E> map) {
m = map;
}
+ @SuppressWarnings("unchecked")
public Iterator<E> iterator() {
if (m instanceof ConcurrentSkipListMap)
return ((ConcurrentSkipListMap<?,E>)m).valueIterator();
@@ -2403,14 +2464,21 @@
}
public Object[] toArray() { return toList(this).toArray(); }
public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
+ @SuppressWarnings("unchecked")
+ public Spliterator<E> spliterator() {
+ if (m instanceof ConcurrentSkipListMap)
+ return ((ConcurrentSkipListMap<?,E>)m).valueSpliterator();
+ else
+ return (Spliterator<E>)((SubMap<?,E>)m).valueIterator();
+ }
}
static final class EntrySet<K1,V1> extends AbstractSet<Map.Entry<K1,V1>> {
- private final ConcurrentNavigableMap<K1, V1> m;
+ final ConcurrentNavigableMap<K1, V1> m;
EntrySet(ConcurrentNavigableMap<K1, V1> map) {
m = map;
}
-
+ @SuppressWarnings("unchecked")
public Iterator<Map.Entry<K1,V1>> iterator() {
if (m instanceof ConcurrentSkipListMap)
return ((ConcurrentSkipListMap<K1,V1>)m).entryIterator();
@@ -2457,6 +2525,14 @@
}
public Object[] toArray() { return toList(this).toArray(); }
public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
+ @SuppressWarnings("unchecked")
+ public Spliterator<Map.Entry<K1,V1>> spliterator() {
+ if (m instanceof ConcurrentSkipListMap)
+ return ((ConcurrentSkipListMap<K1,V1>)m).entrySpliterator();
+ else
+ return (Spliterator<Map.Entry<K1,V1>>)
+ ((SubMap<K1,V1>)m).entryIterator();
+ }
}
/**
@@ -2466,8 +2542,8 @@
* underlying maps, differing in that mappings outside their range are
* ignored, and attempts to add mappings outside their ranges result
* in {@link IllegalArgumentException}. Instances of this class are
- * constructed only using the <tt>subMap</tt>, <tt>headMap</tt>, and
- * <tt>tailMap</tt> methods of their underlying maps.
+ * constructed only using the {@code subMap}, {@code headMap}, and
+ * {@code tailMap} methods of their underlying maps.
*
* @serial include
*/
@@ -2495,14 +2571,15 @@
private transient Collection<V> valuesView;
/**
- * Creates a new submap, initializing all fields
+ * Creates a new submap, initializing all fields.
*/
SubMap(ConcurrentSkipListMap<K,V> map,
K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive,
boolean isDescending) {
+ Comparator<? super K> cmp = map.comparator;
if (fromKey != null && toKey != null &&
- map.compare(fromKey, toKey) > 0)
+ cpr(cmp, fromKey, toKey) > 0)
throw new IllegalArgumentException("inconsistent range");
this.m = map;
this.lo = fromKey;
@@ -2514,39 +2591,34 @@
/* ---------------- Utilities -------------- */
- private boolean tooLow(K key) {
- if (lo != null) {
- int c = m.compare(key, lo);
- if (c < 0 || (c == 0 && !loInclusive))
- return true;
- }
- return false;
+ boolean tooLow(Object key, Comparator<? super K> cmp) {
+ int c;
+ return (lo != null && ((c = cpr(cmp, key, lo)) < 0 ||
+ (c == 0 && !loInclusive)));
}
- private boolean tooHigh(K key) {
- if (hi != null) {
- int c = m.compare(key, hi);
- if (c > 0 || (c == 0 && !hiInclusive))
- return true;
- }
- return false;
+ boolean tooHigh(Object key, Comparator<? super K> cmp) {
+ int c;
+ return (hi != null && ((c = cpr(cmp, key, hi)) > 0 ||
+ (c == 0 && !hiInclusive)));
}
- private boolean inBounds(K key) {
- return !tooLow(key) && !tooHigh(key);
+ boolean inBounds(Object key, Comparator<? super K> cmp) {
+ return !tooLow(key, cmp) && !tooHigh(key, cmp);
}
- private void checkKeyBounds(K key) throws IllegalArgumentException {
+ void checkKeyBounds(K key, Comparator<? super K> cmp) {
if (key == null)
throw new NullPointerException();
- if (!inBounds(key))
+ if (!inBounds(key, cmp))
throw new IllegalArgumentException("key out of range");
}
/**
- * Returns true if node key is less than upper bound of range
+ * Returns true if node key is less than upper bound of range.
*/
- private boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) {
+ boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n,
+ Comparator<? super K> cmp) {
if (n == null)
return false;
if (hi == null)
@@ -2554,7 +2626,7 @@
K k = n.key;
if (k == null) // pass by markers and headers
return true;
- int c = m.compare(k, hi);
+ int c = cpr(cmp, k, hi);
if (c > 0 || (c == 0 && !hiInclusive))
return false;
return true;
@@ -2562,58 +2634,61 @@
/**
* Returns lowest node. This node might not be in range, so
- * most usages need to check bounds
+ * most usages need to check bounds.
*/
- private ConcurrentSkipListMap.Node<K,V> loNode() {
+ ConcurrentSkipListMap.Node<K,V> loNode(Comparator<? super K> cmp) {
if (lo == null)
return m.findFirst();
else if (loInclusive)
- return m.findNear(lo, GT|EQ);
+ return m.findNear(lo, GT|EQ, cmp);
else
- return m.findNear(lo, GT);
+ return m.findNear(lo, GT, cmp);
}
/**
* Returns highest node. This node might not be in range, so
- * most usages need to check bounds
+ * most usages need to check bounds.
*/
- private ConcurrentSkipListMap.Node<K,V> hiNode() {
+ ConcurrentSkipListMap.Node<K,V> hiNode(Comparator<? super K> cmp) {
if (hi == null)
return m.findLast();
else if (hiInclusive)
- return m.findNear(hi, LT|EQ);
+ return m.findNear(hi, LT|EQ, cmp);
else
- return m.findNear(hi, LT);
+ return m.findNear(hi, LT, cmp);
}
/**
- * Returns lowest absolute key (ignoring directonality)
+ * Returns lowest absolute key (ignoring directonality).
*/
- private K lowestKey() {
- ConcurrentSkipListMap.Node<K,V> n = loNode();
- if (isBeforeEnd(n))
+ K lowestKey() {
+ Comparator<? super K> cmp = m.comparator;
+ ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
+ if (isBeforeEnd(n, cmp))
return n.key;
else
throw new NoSuchElementException();
}
/**
- * Returns highest absolute key (ignoring directonality)
+ * Returns highest absolute key (ignoring directonality).
*/
- private K highestKey() {
- ConcurrentSkipListMap.Node<K,V> n = hiNode();
+ K highestKey() {
+ Comparator<? super K> cmp = m.comparator;
+ ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp);
if (n != null) {
K last = n.key;
- if (inBounds(last))
+ if (inBounds(last, cmp))
return last;
}
throw new NoSuchElementException();
}
- private Map.Entry<K,V> lowestEntry() {
+ Map.Entry<K,V> lowestEntry() {
+ Comparator<? super K> cmp = m.comparator;
for (;;) {
- ConcurrentSkipListMap.Node<K,V> n = loNode();
- if (!isBeforeEnd(n))
+ ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
+ if (!isBeforeEnd(n, cmp))
return null;
Map.Entry<K,V> e = n.createSnapshot();
if (e != null)
@@ -2621,10 +2696,11 @@
}
}
- private Map.Entry<K,V> highestEntry() {
+ Map.Entry<K,V> highestEntry() {
+ Comparator<? super K> cmp = m.comparator;
for (;;) {
- ConcurrentSkipListMap.Node<K,V> n = hiNode();
- if (n == null || !inBounds(n.key))
+ ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp);
+ if (n == null || !inBounds(n.key, cmp))
return null;
Map.Entry<K,V> e = n.createSnapshot();
if (e != null)
@@ -2632,13 +2708,14 @@
}
}
- private Map.Entry<K,V> removeLowest() {
+ Map.Entry<K,V> removeLowest() {
+ Comparator<? super K> cmp = m.comparator;
for (;;) {
- Node<K,V> n = loNode();
+ Node<K,V> n = loNode(cmp);
if (n == null)
return null;
K k = n.key;
- if (!inBounds(k))
+ if (!inBounds(k, cmp))
return null;
V v = m.doRemove(k, null);
if (v != null)
@@ -2646,13 +2723,14 @@
}
}
- private Map.Entry<K,V> removeHighest() {
+ Map.Entry<K,V> removeHighest() {
+ Comparator<? super K> cmp = m.comparator;
for (;;) {
- Node<K,V> n = hiNode();
+ Node<K,V> n = hiNode(cmp);
if (n == null)
return null;
K k = n.key;
- if (!inBounds(k))
+ if (!inBounds(k, cmp))
return null;
V v = m.doRemove(k, null);
if (v != null)
@@ -2663,20 +2741,21 @@
/**
* Submap version of ConcurrentSkipListMap.getNearEntry
*/
- private Map.Entry<K,V> getNearEntry(K key, int rel) {
+ Map.Entry<K,V> getNearEntry(K key, int rel) {
+ Comparator<? super K> cmp = m.comparator;
if (isDescending) { // adjust relation for direction
if ((rel & LT) == 0)
rel |= LT;
else
rel &= ~LT;
}
- if (tooLow(key))
+ if (tooLow(key, cmp))
return ((rel & LT) != 0) ? null : lowestEntry();
- if (tooHigh(key))
+ if (tooHigh(key, cmp))
return ((rel & LT) != 0) ? highestEntry() : null;
for (;;) {
- Node<K,V> n = m.findNear(key, rel);
- if (n == null || !inBounds(n.key))
+ Node<K,V> n = m.findNear(key, rel, cmp);
+ if (n == null || !inBounds(n.key, cmp))
return null;
K k = n.key;
V v = n.getValidValue();
@@ -2686,35 +2765,36 @@
}
// Almost the same as getNearEntry, except for keys
- private K getNearKey(K key, int rel) {
+ K getNearKey(K key, int rel) {
+ Comparator<? super K> cmp = m.comparator;
if (isDescending) { // adjust relation for direction
if ((rel & LT) == 0)
rel |= LT;
else
rel &= ~LT;
}
- if (tooLow(key)) {
+ if (tooLow(key, cmp)) {
if ((rel & LT) == 0) {
- ConcurrentSkipListMap.Node<K,V> n = loNode();
- if (isBeforeEnd(n))
+ ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
+ if (isBeforeEnd(n, cmp))
return n.key;
}
return null;
}
- if (tooHigh(key)) {
+ if (tooHigh(key, cmp)) {
if ((rel & LT) != 0) {
- ConcurrentSkipListMap.Node<K,V> n = hiNode();
+ ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp);
if (n != null) {
K last = n.key;
- if (inBounds(last))
+ if (inBounds(last, cmp))
return last;
}
}
return null;
}
for (;;) {
- Node<K,V> n = m.findNear(key, rel);
- if (n == null || !inBounds(n.key))
+ Node<K,V> n = m.findNear(key, rel, cmp);
+ if (n == null || !inBounds(n.key, cmp))
return null;
K k = n.key;
V v = n.getValidValue();
@@ -2727,30 +2807,28 @@
public boolean containsKey(Object key) {
if (key == null) throw new NullPointerException();
- K k = (K)key;
- return inBounds(k) && m.containsKey(k);
+ return inBounds(key, m.comparator) && m.containsKey(key);
}
public V get(Object key) {
if (key == null) throw new NullPointerException();
- K k = (K)key;
- return (!inBounds(k)) ? null : m.get(k);
+ return (!inBounds(key, m.comparator)) ? null : m.get(key);
}
public V put(K key, V value) {
- checkKeyBounds(key);
+ checkKeyBounds(key, m.comparator);
return m.put(key, value);
}
public V remove(Object key) {
- K k = (K)key;
- return (!inBounds(k)) ? null : m.remove(k);
+ return (!inBounds(key, m.comparator)) ? null : m.remove(key);
}
public int size() {
+ Comparator<? super K> cmp = m.comparator;
long count = 0;
- for (ConcurrentSkipListMap.Node<K,V> n = loNode();
- isBeforeEnd(n);
+ for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
+ isBeforeEnd(n, cmp);
n = n.next) {
if (n.getValidValue() != null)
++count;
@@ -2759,14 +2837,16 @@
}
public boolean isEmpty() {
- return !isBeforeEnd(loNode());
+ Comparator<? super K> cmp = m.comparator;
+ return !isBeforeEnd(loNode(cmp), cmp);
}
public boolean containsValue(Object value) {
if (value == null)
throw new NullPointerException();
- for (ConcurrentSkipListMap.Node<K,V> n = loNode();
- isBeforeEnd(n);
+ Comparator<? super K> cmp = m.comparator;
+ for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
+ isBeforeEnd(n, cmp);
n = n.next) {
V v = n.getValidValue();
if (v != null && value.equals(v))
@@ -2776,8 +2856,9 @@
}
public void clear() {
- for (ConcurrentSkipListMap.Node<K,V> n = loNode();
- isBeforeEnd(n);
+ Comparator<? super K> cmp = m.comparator;
+ for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
+ isBeforeEnd(n, cmp);
n = n.next) {
if (n.getValidValue() != null)
m.remove(n.key);
@@ -2787,22 +2868,21 @@
/* ---------------- ConcurrentMap API methods -------------- */
public V putIfAbsent(K key, V value) {
- checkKeyBounds(key);
+ checkKeyBounds(key, m.comparator);
return m.putIfAbsent(key, value);
}
public boolean remove(Object key, Object value) {
- K k = (K)key;
- return inBounds(k) && m.remove(k, value);
+ return inBounds(key, m.comparator) && m.remove(key, value);
}
public boolean replace(K key, V oldValue, V newValue) {
- checkKeyBounds(key);
+ checkKeyBounds(key, m.comparator);
return m.replace(key, oldValue, newValue);
}
public V replace(K key, V value) {
- checkKeyBounds(key);
+ checkKeyBounds(key, m.comparator);
return m.replace(key, value);
}
@@ -2820,10 +2900,9 @@
* Utility to create submaps, where given bounds override
* unbounded(null) ones and/or are checked against bounded ones.
*/
- private SubMap<K,V> newSubMap(K fromKey,
- boolean fromInclusive,
- K toKey,
- boolean toInclusive) {
+ SubMap<K,V> newSubMap(K fromKey, boolean fromInclusive,
+ K toKey, boolean toInclusive) {
+ Comparator<? super K> cmp = m.comparator;
if (isDescending) { // flip senses
K tk = fromKey;
fromKey = toKey;
@@ -2838,7 +2917,7 @@
fromInclusive = loInclusive;
}
else {
- int c = m.compare(fromKey, lo);
+ int c = cpr(cmp, fromKey, lo);
if (c < 0 || (c == 0 && !loInclusive && fromInclusive))
throw new IllegalArgumentException("key out of range");
}
@@ -2849,7 +2928,7 @@
toInclusive = hiInclusive;
}
else {
- int c = m.compare(toKey, hi);
+ int c = cpr(cmp, toKey, hi);
if (c > 0 || (c == 0 && !hiInclusive && toInclusive))
throw new IllegalArgumentException("key out of range");
}
@@ -2858,24 +2937,20 @@
toKey, toInclusive, isDescending);
}
- public SubMap<K,V> subMap(K fromKey,
- boolean fromInclusive,
- K toKey,
- boolean toInclusive) {
+ public SubMap<K,V> subMap(K fromKey, boolean fromInclusive,
+ K toKey, boolean toInclusive) {
if (fromKey == null || toKey == null)
throw new NullPointerException();
return newSubMap(fromKey, fromInclusive, toKey, toInclusive);
}
- public SubMap<K,V> headMap(K toKey,
- boolean inclusive) {
+ public SubMap<K,V> headMap(K toKey, boolean inclusive) {
if (toKey == null)
throw new NullPointerException();
return newSubMap(null, false, toKey, inclusive);
}
- public SubMap<K,V> tailMap(K fromKey,
- boolean inclusive) {
+ public SubMap<K,V> tailMap(K fromKey, boolean inclusive) {
if (fromKey == null)
throw new NullPointerException();
return newSubMap(fromKey, inclusive, null, false);
@@ -2996,8 +3071,9 @@
/**
* Variant of main Iter class to traverse through submaps.
+ * Also serves as back-up Spliterator for views
*/
- abstract class SubMapIter<T> implements Iterator<T> {
+ abstract class SubMapIter<T> implements Iterator<T>, Spliterator<T> {
/** the last node returned by next() */
Node<K,V> lastReturned;
/** the next node to return from next(); */
@@ -3006,16 +3082,19 @@
V nextValue;
SubMapIter() {
+ Comparator<? super K> cmp = m.comparator;
for (;;) {
- next = isDescending ? hiNode() : loNode();
+ next = isDescending ? hiNode(cmp) : loNode(cmp);
if (next == null)
break;
Object x = next.value;
if (x != null && x != next) {
- if (! inBounds(next.key))
+ if (! inBounds(next.key, cmp))
next = null;
- else
- nextValue = (V) x;
+ else {
+ @SuppressWarnings("unchecked") V vv = (V)x;
+ nextValue = vv;
+ }
break;
}
}
@@ -3036,32 +3115,38 @@
}
private void ascend() {
+ Comparator<? super K> cmp = m.comparator;
for (;;) {
next = next.next;
if (next == null)
break;
Object x = next.value;
if (x != null && x != next) {
- if (tooHigh(next.key))
+ if (tooHigh(next.key, cmp))
next = null;
- else
- nextValue = (V) x;
+ else {
+ @SuppressWarnings("unchecked") V vv = (V)x;
+ nextValue = vv;
+ }
break;
}
}
}
private void descend() {
+ Comparator<? super K> cmp = m.comparator;
for (;;) {
- next = m.findNear(lastReturned.key, LT);
+ next = m.findNear(lastReturned.key, LT, cmp);
if (next == null)
break;
Object x = next.value;
if (x != null && x != next) {
- if (tooLow(next.key))
+ if (tooLow(next.key, cmp))
next = null;
- else
- nextValue = (V) x;
+ else {
+ @SuppressWarnings("unchecked") V vv = (V)x;
+ nextValue = vv;
+ }
break;
}
}
@@ -3075,6 +3160,26 @@
lastReturned = null;
}
+ public Spliterator<T> trySplit() {
+ return null;
+ }
+
+ public boolean tryAdvance(Consumer<? super T> action) {
+ if (hasNext()) {
+ action.accept(next());
+ return true;
+ }
+ return false;
+ }
+
+ public void forEachRemaining(Consumer<? super T> action) {
+ while (hasNext())
+ action.accept(next());
+ }
+
+ public long estimateSize() {
+ return Long.MAX_VALUE;
+ }
}
final class SubMapValueIterator extends SubMapIter<V> {
@@ -3083,6 +3188,9 @@
advance();
return v;
}
+ public int characteristics() {
+ return 0;
+ }
}
final class SubMapKeyIterator extends SubMapIter<K> {
@@ -3091,6 +3199,13 @@
advance();
return n.key;
}
+ public int characteristics() {
+ return Spliterator.DISTINCT | Spliterator.ORDERED |
+ Spliterator.SORTED;
+ }
+ public final Comparator<? super K> getComparator() {
+ return SubMap.this.comparator();
+ }
}
final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> {
@@ -3100,18 +3215,351 @@
advance();
return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
}
+ public int characteristics() {
+ return Spliterator.DISTINCT;
+ }
+ }
+ }
+
+ // default Map method overrides
+
+ public void forEach(BiConsumer<? super K, ? super V> action) {
+ if (action == null) throw new NullPointerException();
+ V v;
+ for (Node<K,V> n = findFirst(); n != null; n = n.next) {
+ if ((v = n.getValidValue()) != null)
+ action.accept(n.key, v);
+ }
+ }
+
+ public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
+ if (function == null) throw new NullPointerException();
+ V v;
+ for (Node<K,V> n = findFirst(); n != null; n = n.next) {
+ while ((v = n.getValidValue()) != null) {
+ V r = function.apply(n.key, v);
+ if (r == null) throw new NullPointerException();
+ if (n.casValue(v, r))
+ break;
+ }
+ }
+ }
+
+ /**
+ * Base class providing common structure for Spliterators.
+ * (Although not all that much common functionality; as usual for
+ * view classes, details annoyingly vary in key, value, and entry
+ * subclasses in ways that are not worth abstracting out for
+ * internal classes.)
+ *
+ * The basic split strategy is to recursively descend from top
+ * level, row by row, descending to next row when either split
+ * off, or the end of row is encountered. Control of the number of
+ * splits relies on some statistical estimation: The expected
+ * remaining number of elements of a skip list when advancing
+ * either across or down decreases by about 25%. To make this
+ * observation useful, we need to know initial size, which we
+ * don't. But we can just use Integer.MAX_VALUE so that we
+ * don't prematurely zero out while splitting.
+ */
+ abstract static class CSLMSpliterator<K,V> {
+ final Comparator<? super K> comparator;
+ final K fence; // exclusive upper bound for keys, or null if to end
+ Index<K,V> row; // the level to split out
+ Node<K,V> current; // current traversal node; initialize at origin
+ int est; // pseudo-size estimate
+ CSLMSpliterator(Comparator<? super K> comparator, Index<K,V> row,
+ Node<K,V> origin, K fence, int est) {
+ this.comparator = comparator; this.row = row;
+ this.current = origin; this.fence = fence; this.est = est;
+ }
+
+ public final long estimateSize() { return (long)est; }
+ }
+
+ static final class KeySpliterator<K,V> extends CSLMSpliterator<K,V>
+ implements Spliterator<K> {
+ KeySpliterator(Comparator<? super K> comparator, Index<K,V> row,
+ Node<K,V> origin, K fence, int est) {
+ super(comparator, row, origin, fence, est);
+ }
+
+ public Spliterator<K> trySplit() {
+ Node<K,V> e; K ek;
+ Comparator<? super K> cmp = comparator;
+ K f = fence;
+ if ((e = current) != null && (ek = e.key) != null) {
+ for (Index<K,V> q = row; q != null; q = row = q.down) {
+ Index<K,V> s; Node<K,V> b, n; K sk;
+ if ((s = q.right) != null && (b = s.node) != null &&
+ (n = b.next) != null && n.value != null &&
+ (sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
+ (f == null || cpr(cmp, sk, f) < 0)) {
+ current = n;
+ Index<K,V> r = q.down;
+ row = (s.right != null) ? s : s.down;
+ est -= est >>> 2;
+ return new KeySpliterator<K,V>(cmp, r, e, sk, est);
+ }
+ }
+ }
+ return null;
+ }
+
+ public void forEachRemaining(Consumer<? super K> action) {
+ if (action == null) throw new NullPointerException();
+ Comparator<? super K> cmp = comparator;
+ K f = fence;
+ Node<K,V> e = current;
+ current = null;
+ for (; e != null; e = e.next) {
+ K k; Object v;
+ if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
+ break;
+ if ((v = e.value) != null && v != e)
+ action.accept(k);
+ }
+ }
+
+ public boolean tryAdvance(Consumer<? super K> action) {
+ if (action == null) throw new NullPointerException();
+ Comparator<? super K> cmp = comparator;
+ K f = fence;
+ Node<K,V> e = current;
+ for (; e != null; e = e.next) {
+ K k; Object v;
+ if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
+ e = null;
+ break;
+ }
+ if ((v = e.value) != null && v != e) {
+ current = e.next;
+ action.accept(k);
+ return true;
+ }
+ }
+ current = e;
+ return false;
+ }
+
+ public int characteristics() {
+ return Spliterator.DISTINCT | Spliterator.SORTED |
+ Spliterator.ORDERED | Spliterator.CONCURRENT |
+ Spliterator.NONNULL;
+ }
+
+ public final Comparator<? super K> getComparator() {
+ return comparator;
+ }
+ }
+ // factory method for KeySpliterator
+ final KeySpliterator<K,V> keySpliterator() {
+ Comparator<? super K> cmp = comparator;
+ for (;;) { // ensure h corresponds to origin p
+ HeadIndex<K,V> h; Node<K,V> p;
+ Node<K,V> b = (h = head).node;
+ if ((p = b.next) == null || p.value != null)
+ return new KeySpliterator<K,V>(cmp, h, p, null, (p == null) ?
+ 0 : Integer.MAX_VALUE);
+ p.helpDelete(b, p.next);
+ }
+ }
+
+ static final class ValueSpliterator<K,V> extends CSLMSpliterator<K,V>
+ implements Spliterator<V> {
+ ValueSpliterator(Comparator<? super K> comparator, Index<K,V> row,
+ Node<K,V> origin, K fence, int est) {
+ super(comparator, row, origin, fence, est);
+ }
+
+ public Spliterator<V> trySplit() {
+ Node<K,V> e; K ek;
+ Comparator<? super K> cmp = comparator;
+ K f = fence;
+ if ((e = current) != null && (ek = e.key) != null) {
+ for (Index<K,V> q = row; q != null; q = row = q.down) {
+ Index<K,V> s; Node<K,V> b, n; K sk;
+ if ((s = q.right) != null && (b = s.node) != null &&
+ (n = b.next) != null && n.value != null &&
+ (sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
+ (f == null || cpr(cmp, sk, f) < 0)) {
+ current = n;
+ Index<K,V> r = q.down;
+ row = (s.right != null) ? s : s.down;
+ est -= est >>> 2;
+ return new ValueSpliterator<K,V>(cmp, r, e, sk, est);
+ }
+ }
+ }
+ return null;
+ }
+
+ public void forEachRemaining(Consumer<? super V> action) {
+ if (action == null) throw new NullPointerException();
+ Comparator<? super K> cmp = comparator;
+ K f = fence;
+ Node<K,V> e = current;
+ current = null;
+ for (; e != null; e = e.next) {
+ K k; Object v;
+ if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
+ break;
+ if ((v = e.value) != null && v != e) {
+ @SuppressWarnings("unchecked") V vv = (V)v;
+ action.accept(vv);
+ }
+ }
+ }
+
+ public boolean tryAdvance(Consumer<? super V> action) {
+ if (action == null) throw new NullPointerException();
+ Comparator<? super K> cmp = comparator;
+ K f = fence;
+ Node<K,V> e = current;
+ for (; e != null; e = e.next) {
+ K k; Object v;
+ if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
+ e = null;
+ break;
+ }
+ if ((v = e.value) != null && v != e) {
+ current = e.next;
+ @SuppressWarnings("unchecked") V vv = (V)v;
+ action.accept(vv);
+ return true;
+ }
+ }
+ current = e;
+ return false;
+ }
+
+ public int characteristics() {
+ return Spliterator.CONCURRENT | Spliterator.NONNULL;
+ }
+ }
+
+ // Almost the same as keySpliterator()
+ final ValueSpliterator<K,V> valueSpliterator() {
+ Comparator<? super K> cmp = comparator;
+ for (;;) {
+ HeadIndex<K,V> h; Node<K,V> p;
+ Node<K,V> b = (h = head).node;
+ if ((p = b.next) == null || p.value != null)
+ return new ValueSpliterator<K,V>(cmp, h, p, null, (p == null) ?
+ 0 : Integer.MAX_VALUE);
+ p.helpDelete(b, p.next);
+ }
+ }
+
+ static final class EntrySpliterator<K,V> extends CSLMSpliterator<K,V>
+ implements Spliterator<Map.Entry<K,V>> {
+ EntrySpliterator(Comparator<? super K> comparator, Index<K,V> row,
+ Node<K,V> origin, K fence, int est) {
+ super(comparator, row, origin, fence, est);
+ }
+
+ public Spliterator<Map.Entry<K,V>> trySplit() {
+ Node<K,V> e; K ek;
+ Comparator<? super K> cmp = comparator;
+ K f = fence;
+ if ((e = current) != null && (ek = e.key) != null) {
+ for (Index<K,V> q = row; q != null; q = row = q.down) {
+ Index<K,V> s; Node<K,V> b, n; K sk;
+ if ((s = q.right) != null && (b = s.node) != null &&
+ (n = b.next) != null && n.value != null &&
+ (sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
+ (f == null || cpr(cmp, sk, f) < 0)) {
+ current = n;
+ Index<K,V> r = q.down;
+ row = (s.right != null) ? s : s.down;
+ est -= est >>> 2;
+ return new EntrySpliterator<K,V>(cmp, r, e, sk, est);
+ }
+ }
+ }
+ return null;
+ }
+
+ public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
+ if (action == null) throw new NullPointerException();
+ Comparator<? super K> cmp = comparator;
+ K f = fence;
+ Node<K,V> e = current;
+ current = null;
+ for (; e != null; e = e.next) {
+ K k; Object v;
+ if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
+ break;
+ if ((v = e.value) != null && v != e) {
+ @SuppressWarnings("unchecked") V vv = (V)v;
+ action.accept
+ (new AbstractMap.SimpleImmutableEntry<K,V>(k, vv));
+ }
+ }
+ }
+
+ public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
+ if (action == null) throw new NullPointerException();
+ Comparator<? super K> cmp = comparator;
+ K f = fence;
+ Node<K,V> e = current;
+ for (; e != null; e = e.next) {
+ K k; Object v;
+ if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
+ e = null;
+ break;
+ }
+ if ((v = e.value) != null && v != e) {
+ current = e.next;
+ @SuppressWarnings("unchecked") V vv = (V)v;
+ action.accept
+ (new AbstractMap.SimpleImmutableEntry<K,V>(k, vv));
+ return true;
+ }
+ }
+ current = e;
+ return false;
+ }
+
+ public int characteristics() {
+ return Spliterator.DISTINCT | Spliterator.SORTED |
+ Spliterator.ORDERED | Spliterator.CONCURRENT |
+ Spliterator.NONNULL;
+ }
+
+ public final Comparator<Map.Entry<K,V>> getComparator() {
+ return comparator == null ? null :
+ Map.Entry.comparingByKey(comparator);
+ }
+ }
+
+ // Almost the same as keySpliterator()
+ final EntrySpliterator<K,V> entrySpliterator() {
+ Comparator<? super K> cmp = comparator;
+ for (;;) { // almost same as key version
+ HeadIndex<K,V> h; Node<K,V> p;
+ Node<K,V> b = (h = head).node;
+ if ((p = b.next) == null || p.value != null)
+ return new EntrySpliterator<K,V>(cmp, h, p, null, (p == null) ?
+ 0 : Integer.MAX_VALUE);
+ p.helpDelete(b, p.next);
}
}
// Unsafe mechanics
private static final sun.misc.Unsafe UNSAFE;
private static final long headOffset;
+ private static final long SECONDARY;
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class<?> k = ConcurrentSkipListMap.class;
headOffset = UNSAFE.objectFieldOffset
(k.getDeclaredField("head"));
+ Class<?> tk = Thread.class;
+ SECONDARY = UNSAFE.objectFieldOffset
+ (tk.getDeclaredField("threadLocalRandomSecondarySeed"));
+
} catch (Exception e) {
throw new Error(e);
}
--- a/jdk/src/share/classes/java/util/concurrent/ConcurrentSkipListSet.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/ConcurrentSkipListSet.java Wed Jul 03 11:58:09 2013 +0200
@@ -34,7 +34,17 @@
*/
package java.util.concurrent;
-import java.util.*;
+import java.util.AbstractSet;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NavigableMap;
+import java.util.NavigableSet;
+import java.util.Set;
+import java.util.SortedSet;
+import java.util.Spliterator;
/**
* A scalable concurrent {@link NavigableSet} implementation based on
@@ -44,33 +54,33 @@
* on which constructor is used.
*
* <p>This implementation provides expected average <i>log(n)</i> time
- * cost for the <tt>contains</tt>, <tt>add</tt>, and <tt>remove</tt>
+ * cost for the {@code contains}, {@code add}, and {@code remove}
* operations and their variants. Insertion, removal, and access
* operations safely execute concurrently by multiple threads.
* Iterators are <i>weakly consistent</i>, returning elements
* reflecting the state of the set at some point at or since the
* creation of the iterator. They do <em>not</em> throw {@link
- * ConcurrentModificationException}, and may proceed concurrently with
- * other operations. Ascending ordered views and their iterators are
- * faster than descending ones.
+ * java.util.ConcurrentModificationException}, and may proceed
+ * concurrently with other operations. Ascending ordered views and
+ * their iterators are faster than descending ones.
*
- * <p>Beware that, unlike in most collections, the <tt>size</tt>
+ * <p>Beware that, unlike in most collections, the {@code size}
* method is <em>not</em> a constant-time operation. Because of the
* asynchronous nature of these sets, determining the current number
* of elements requires a traversal of the elements, and so may report
* inaccurate results if this collection is modified during traversal.
- * Additionally, the bulk operations <tt>addAll</tt>,
- * <tt>removeAll</tt>, <tt>retainAll</tt>, <tt>containsAll</tt>,
- * <tt>equals</tt>, and <tt>toArray</tt> are <em>not</em> guaranteed
+ * Additionally, the bulk operations {@code addAll},
+ * {@code removeAll}, {@code retainAll}, {@code containsAll},
+ * {@code equals}, and {@code toArray} are <em>not</em> guaranteed
* to be performed atomically. For example, an iterator operating
- * concurrently with an <tt>addAll</tt> operation might view only some
+ * concurrently with an {@code addAll} operation might view only some
* of the added elements.
*
* <p>This class and its iterators implement all of the
* <em>optional</em> methods of the {@link Set} and {@link Iterator}
* interfaces. Like most other concurrent collection implementations,
- * this class does not permit the use of <tt>null</tt> elements,
- * because <tt>null</tt> arguments and return values cannot be reliably
+ * this class does not permit the use of {@code null} elements,
+ * because {@code null} arguments and return values cannot be reliably
* distinguished from the absence of elements.
*
* <p>This class is a member of the
@@ -90,7 +100,7 @@
/**
* The underlying map. Uses Boolean.TRUE as value for each
* element. This field is declared final for the sake of thread
- * safety, which entails some ugliness in clone()
+ * safety, which entails some ugliness in clone().
*/
private final ConcurrentNavigableMap<E,Object> m;
@@ -107,7 +117,7 @@
* the specified comparator.
*
* @param comparator the comparator that will be used to order this set.
- * If <tt>null</tt>, the {@linkplain Comparable natural
+ * If {@code null}, the {@linkplain Comparable natural
* ordering} of the elements will be used.
*/
public ConcurrentSkipListSet(Comparator<? super E> comparator) {
@@ -120,7 +130,7 @@
* {@linkplain Comparable natural ordering}.
*
* @param c The elements that will comprise the new set
- * @throws ClassCastException if the elements in <tt>c</tt> are
+ * @throws ClassCastException if the elements in {@code c} are
* not {@link Comparable}, or are not mutually comparable
* @throws NullPointerException if the specified collection or any
* of its elements are null
@@ -151,7 +161,7 @@
}
/**
- * Returns a shallow copy of this <tt>ConcurrentSkipListSet</tt>
+ * Returns a shallow copy of this {@code ConcurrentSkipListSet}
* instance. (The elements themselves are not cloned.)
*
* @return a shallow copy of this set
@@ -172,8 +182,8 @@
/**
* Returns the number of elements in this set. If this set
- * contains more than <tt>Integer.MAX_VALUE</tt> elements, it
- * returns <tt>Integer.MAX_VALUE</tt>.
+ * contains more than {@code Integer.MAX_VALUE} elements, it
+ * returns {@code Integer.MAX_VALUE}.
*
* <p>Beware that, unlike in most collections, this method is
* <em>NOT</em> a constant-time operation. Because of the
@@ -191,20 +201,20 @@
}
/**
- * Returns <tt>true</tt> if this set contains no elements.
- * @return <tt>true</tt> if this set contains no elements
+ * Returns {@code true} if this set contains no elements.
+ * @return {@code true} if this set contains no elements
*/
public boolean isEmpty() {
return m.isEmpty();
}
/**
- * Returns <tt>true</tt> if this set contains the specified element.
- * More formally, returns <tt>true</tt> if and only if this set
- * contains an element <tt>e</tt> such that <tt>o.equals(e)</tt>.
+ * Returns {@code true} if this set contains the specified element.
+ * More formally, returns {@code true} if and only if this set
+ * contains an element {@code e} such that {@code o.equals(e)}.
*
* @param o object to be checked for containment in this set
- * @return <tt>true</tt> if this set contains the specified element
+ * @return {@code true} if this set contains the specified element
* @throws ClassCastException if the specified element cannot be
* compared with the elements currently in this set
* @throws NullPointerException if the specified element is null
@@ -215,15 +225,15 @@
/**
* Adds the specified element to this set if it is not already present.
- * More formally, adds the specified element <tt>e</tt> to this set if
- * the set contains no element <tt>e2</tt> such that <tt>e.equals(e2)</tt>.
+ * More formally, adds the specified element {@code e} to this set if
+ * the set contains no element {@code e2} such that {@code e.equals(e2)}.
* If this set already contains the element, the call leaves the set
- * unchanged and returns <tt>false</tt>.
+ * unchanged and returns {@code false}.
*
* @param e element to be added to this set
- * @return <tt>true</tt> if this set did not already contain the
+ * @return {@code true} if this set did not already contain the
* specified element
- * @throws ClassCastException if <tt>e</tt> cannot be compared
+ * @throws ClassCastException if {@code e} cannot be compared
* with the elements currently in this set
* @throws NullPointerException if the specified element is null
*/
@@ -233,15 +243,15 @@
/**
* Removes the specified element from this set if it is present.
- * More formally, removes an element <tt>e</tt> such that
- * <tt>o.equals(e)</tt>, if this set contains such an element.
- * Returns <tt>true</tt> if this set contained the element (or
+ * More formally, removes an element {@code e} such that
+ * {@code o.equals(e)}, if this set contains such an element.
+ * Returns {@code true} if this set contained the element (or
* equivalently, if this set changed as a result of the call).
* (This set will not contain the element once the call returns.)
*
* @param o object to be removed from this set, if present
- * @return <tt>true</tt> if this set contained the specified element
- * @throws ClassCastException if <tt>o</tt> cannot be compared
+ * @return {@code true} if this set contained the specified element
+ * @throws ClassCastException if {@code o} cannot be compared
* with the elements currently in this set
* @throws NullPointerException if the specified element is null
*/
@@ -279,7 +289,7 @@
/**
* Compares the specified object with this set for equality. Returns
- * <tt>true</tt> if the specified object is also a set, the two sets
+ * {@code true} if the specified object is also a set, the two sets
* have the same size, and every member of the specified set is
* contained in this set (or equivalently, every member of this set is
* contained in the specified set). This definition ensures that the
@@ -287,7 +297,7 @@
* set interface.
*
* @param o the object to be compared for equality with this set
- * @return <tt>true</tt> if the specified object is equal to this set
+ * @return {@code true} if the specified object is equal to this set
*/
public boolean equals(Object o) {
// Override AbstractSet version to avoid calling size()
@@ -312,7 +322,7 @@
* value is the <i>asymmetric set difference</i> of the two sets.
*
* @param c collection containing elements to be removed from this set
- * @return <tt>true</tt> if this set changed as a result of the call
+ * @return {@code true} if this set changed as a result of the call
* @throws ClassCastException if the types of one or more elements in this
* set are incompatible with the specified collection
* @throws NullPointerException if the specified collection or any
@@ -380,14 +390,14 @@
}
/**
- * @throws NoSuchElementException {@inheritDoc}
+ * @throws java.util.NoSuchElementException {@inheritDoc}
*/
public E first() {
return m.firstKey();
}
/**
- * @throws NoSuchElementException {@inheritDoc}
+ * @throws java.util.NoSuchElementException {@inheritDoc}
*/
public E last() {
return m.lastKey();
@@ -460,7 +470,7 @@
* reflected in the descending set, and vice-versa.
*
* <p>The returned set has an ordering equivalent to
- * <tt>{@link Collections#reverseOrder(Comparator) Collections.reverseOrder}(comparator())</tt>.
+ * {@link Collections#reverseOrder(Comparator) Collections.reverseOrder}{@code (comparator())}.
* The expression {@code s.descendingSet().descendingSet()} returns a
* view of {@code s} essentially equivalent to {@code s}.
*
@@ -470,6 +480,14 @@
return new ConcurrentSkipListSet<E>(m.descendingMap());
}
+ @SuppressWarnings("unchecked")
+ public Spliterator<E> spliterator() {
+ if (m instanceof ConcurrentSkipListMap)
+ return ((ConcurrentSkipListMap<E,?>)m).keySpliterator();
+ else
+ return (Spliterator<E>)((ConcurrentSkipListMap.SubMap<E,?>)m).keyIterator();
+ }
+
// Support for resetting map in clone
private void setMap(ConcurrentNavigableMap<E,Object> map) {
UNSAFE.putObjectVolatile(this, mapOffset, map);
--- a/jdk/src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java Wed Jul 03 11:58:09 2013 +0200
@@ -1,5 +1,4 @@
/*
- * Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -34,7 +33,19 @@
*/
package java.util.concurrent;
-import java.util.*;
+import java.util.AbstractList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.NoSuchElementException;
+import java.util.Objects;
+import java.util.RandomAccess;
+import java.util.Spliterator;
+import java.util.Spliterators;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.Consumer;
import java.util.function.Predicate;
@@ -42,10 +53,10 @@
/**
* A thread-safe variant of {@link java.util.ArrayList} in which all mutative
- * operations (<tt>add</tt>, <tt>set</tt>, and so on) are implemented by
+ * operations ({@code add}, {@code set}, and so on) are implemented by
* making a fresh copy of the underlying array.
*
- * <p> This is ordinarily too costly, but may be <em>more</em> efficient
+ * <p>This is ordinarily too costly, but may be <em>more</em> efficient
* than alternatives when traversal operations vastly outnumber
* mutations, and is useful when you cannot or don't want to
* synchronize traversals, yet need to preclude interference among
@@ -53,14 +64,14 @@
* reference to the state of the array at the point that the iterator
* was created. This array never changes during the lifetime of the
* iterator, so interference is impossible and the iterator is
- * guaranteed not to throw <tt>ConcurrentModificationException</tt>.
+ * guaranteed not to throw {@code ConcurrentModificationException}.
* The iterator will not reflect additions, removals, or changes to
* the list since the iterator was created. Element-changing
- * operations on iterators themselves (<tt>remove</tt>, <tt>set</tt>, and
- * <tt>add</tt>) are not supported. These methods throw
- * <tt>UnsupportedOperationException</tt>.
+ * operations on iterators themselves ({@code remove}, {@code set}, and
+ * {@code add}) are not supported. These methods throw
+ * {@code UnsupportedOperationException}.
*
- * <p>All elements are permitted, including <tt>null</tt>.
+ * <p>All elements are permitted, including {@code null}.
*
* <p>Memory consistency effects: As with other concurrent
* collections, actions in a thread prior to placing an object into a
@@ -82,10 +93,10 @@
private static final long serialVersionUID = 8673264195747942595L;
/** The lock protecting all mutators */
- transient final ReentrantLock lock = new ReentrantLock();
+ final transient ReentrantLock lock = new ReentrantLock();
/** The array, accessed only via getArray/setArray. */
- private volatile transient Object[] array;
+ private transient volatile Object[] array;
/**
* Gets the array. Non-private so as to also be accessible
@@ -118,10 +129,15 @@
* @throws NullPointerException if the specified collection is null
*/
public CopyOnWriteArrayList(Collection<? extends E> c) {
- Object[] elements = c.toArray();
- // c.toArray might (incorrectly) not return Object[] (see 6260652)
- if (elements.getClass() != Object[].class)
- elements = Arrays.copyOf(elements, elements.length, Object[].class);
+ Object[] elements;
+ if (c.getClass() == CopyOnWriteArrayList.class)
+ elements = ((CopyOnWriteArrayList<?>)c).getArray();
+ else {
+ elements = c.toArray();
+ // c.toArray might (incorrectly) not return Object[] (see 6260652)
+ if (elements.getClass() != Object[].class)
+ elements = Arrays.copyOf(elements, elements.length, Object[].class);
+ }
setArray(elements);
}
@@ -146,9 +162,9 @@
}
/**
- * Returns <tt>true</tt> if this list contains no elements.
+ * Returns {@code true} if this list contains no elements.
*
- * @return <tt>true</tt> if this list contains no elements
+ * @return {@code true} if this list contains no elements
*/
public boolean isEmpty() {
return size() == 0;
@@ -158,7 +174,7 @@
* Tests for equality, coping with nulls.
*/
private static boolean eq(Object o1, Object o2) {
- return (o1 == null ? o2 == null : o1.equals(o2));
+ return (o1 == null) ? o2 == null : o1.equals(o2);
}
/**
@@ -205,13 +221,13 @@
}
/**
- * Returns <tt>true</tt> if this list contains the specified element.
- * More formally, returns <tt>true</tt> if and only if this list contains
- * at least one element <tt>e</tt> such that
+ * Returns {@code true} if this list contains the specified element.
+ * More formally, returns {@code true} if and only if this list contains
+ * at least one element {@code e} such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
- * @return <tt>true</tt> if this list contains the specified element
+ * @return {@code true} if this list contains the specified element
*/
public boolean contains(Object o) {
Object[] elements = getArray();
@@ -228,17 +244,17 @@
/**
* Returns the index of the first occurrence of the specified element in
- * this list, searching forwards from <tt>index</tt>, or returns -1 if
+ * this list, searching forwards from {@code index}, or returns -1 if
* the element is not found.
- * More formally, returns the lowest index <tt>i</tt> such that
+ * More formally, returns the lowest index {@code i} such that
* <tt>(i >= index && (e==null ? get(i)==null : e.equals(get(i))))</tt>,
* or -1 if there is no such index.
*
* @param e element to search for
* @param index index to start searching from
* @return the index of the first occurrence of the element in
- * this list at position <tt>index</tt> or later in the list;
- * <tt>-1</tt> if the element is not found.
+ * this list at position {@code index} or later in the list;
+ * {@code -1} if the element is not found.
* @throws IndexOutOfBoundsException if the specified index is negative
*/
public int indexOf(E e, int index) {
@@ -256,16 +272,16 @@
/**
* Returns the index of the last occurrence of the specified element in
- * this list, searching backwards from <tt>index</tt>, or returns -1 if
+ * this list, searching backwards from {@code index}, or returns -1 if
* the element is not found.
- * More formally, returns the highest index <tt>i</tt> such that
+ * More formally, returns the highest index {@code i} such that
* <tt>(i <= index && (e==null ? get(i)==null : e.equals(get(i))))</tt>,
* or -1 if there is no such index.
*
* @param e element to search for
* @param index index to start searching backwards from
* @return the index of the last occurrence of the element at position
- * less than or equal to <tt>index</tt> in this list;
+ * less than or equal to {@code index} in this list;
* -1 if the element is not found.
* @throws IndexOutOfBoundsException if the specified index is greater
* than or equal to the current size of this list
@@ -323,7 +339,7 @@
* <p>If this list fits in the specified array with room to spare
* (i.e., the array has more elements than this list), the element in
* the array immediately following the end of the list is set to
- * <tt>null</tt>. (This is useful in determining the length of this
+ * {@code null}. (This is useful in determining the length of this
* list <i>only</i> if the caller knows that this list does not contain
* any null elements.)
*
@@ -332,14 +348,14 @@
* precise control over the runtime type of the output array, and may,
* under certain circumstances, be used to save allocation costs.
*
- * <p>Suppose <tt>x</tt> is a list known to contain only strings.
+ * <p>Suppose {@code x} is a list known to contain only strings.
* The following code can be used to dump the list into a newly
- * allocated array of <tt>String</tt>:
+ * allocated array of {@code String}:
*
* <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
*
- * Note that <tt>toArray(new Object[0])</tt> is identical in function to
- * <tt>toArray()</tt>.
+ * Note that {@code toArray(new Object[0])} is identical in function to
+ * {@code toArray()}.
*
* @param a the array into which the elements of the list are to
* be stored, if it is big enough; otherwise, a new array of the
@@ -412,7 +428,7 @@
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
- * @return <tt>true</tt> (as specified by {@link Collection#add})
+ * @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
final ReentrantLock lock = this.lock;
@@ -496,45 +512,54 @@
* Removes the first occurrence of the specified element from this list,
* if it is present. If this list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
- * <tt>i</tt> such that
+ * {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
- * (if such an element exists). Returns <tt>true</tt> if this list
+ * (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
- * @return <tt>true</tt> if this list contained the specified element
+ * @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
+ Object[] snapshot = getArray();
+ int index = indexOf(o, snapshot, 0, snapshot.length);
+ return (index < 0) ? false : remove(o, snapshot, index);
+ }
+
+ /**
+ * A version of remove(Object) using the strong hint that given
+ * recent snapshot contains o at the given index.
+ */
+ private boolean remove(Object o, Object[] snapshot, int index) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
- Object[] elements = getArray();
- int len = elements.length;
- if (len != 0) {
- // Copy while searching for element to remove
- // This wins in the normal case of element being present
- int newlen = len - 1;
- Object[] newElements = new Object[newlen];
-
- for (int i = 0; i < newlen; ++i) {
- if (eq(o, elements[i])) {
- // found one; copy remaining and exit
- for (int k = i + 1; k < len; ++k)
- newElements[k-1] = elements[k];
- setArray(newElements);
- return true;
- } else
- newElements[i] = elements[i];
+ Object[] current = getArray();
+ int len = current.length;
+ if (snapshot != current) findIndex: {
+ int prefix = Math.min(index, len);
+ for (int i = 0; i < prefix; i++) {
+ if (current[i] != snapshot[i] && eq(o, current[i])) {
+ index = i;
+ break findIndex;
+ }
}
-
- // special handling for last cell
- if (eq(o, elements[newlen])) {
- setArray(newElements);
- return true;
- }
+ if (index >= len)
+ return false;
+ if (current[index] == o)
+ break findIndex;
+ index = indexOf(o, current, index, len);
+ if (index < 0)
+ return false;
}
- return false;
+ Object[] newElements = new Object[len - 1];
+ System.arraycopy(current, 0, newElements, 0, index);
+ System.arraycopy(current, index + 1,
+ newElements, index,
+ len - index - 1);
+ setArray(newElements);
+ return true;
} finally {
lock.unlock();
}
@@ -542,10 +567,10 @@
/**
* Removes from this list all of the elements whose index is between
- * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
+ * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
* Shifts any succeeding elements to the left (reduces their index).
- * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
- * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
+ * This call shortens the list by {@code (toIndex - fromIndex)} elements.
+ * (If {@code toIndex==fromIndex}, this operation has no effect.)
*
* @param fromIndex index of first element to be removed
* @param toIndex index after last element to be removed
@@ -581,23 +606,34 @@
* Appends the element, if not present.
*
* @param e element to be added to this list, if absent
- * @return <tt>true</tt> if the element was added
+ * @return {@code true} if the element was added
*/
public boolean addIfAbsent(E e) {
+ Object[] snapshot = getArray();
+ return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
+ addIfAbsent(e, snapshot);
+ }
+
+ /**
+ * A version of addIfAbsent using the strong hint that given
+ * recent snapshot does not contain e.
+ */
+ private boolean addIfAbsent(E e, Object[] snapshot) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
- // Copy while checking if already present.
- // This wins in the most common case where it is not present
- Object[] elements = getArray();
- int len = elements.length;
- Object[] newElements = new Object[len + 1];
- for (int i = 0; i < len; ++i) {
- if (eq(e, elements[i]))
- return false; // exit, throwing away copy
- else
- newElements[i] = elements[i];
+ Object[] current = getArray();
+ int len = current.length;
+ if (snapshot != current) {
+ // Optimize for lost race to another addXXX operation
+ int common = Math.min(snapshot.length, len);
+ for (int i = 0; i < common; i++)
+ if (current[i] != snapshot[i] && eq(e, current[i]))
+ return false;
+ if (indexOf(e, current, common, len) >= 0)
+ return false;
}
+ Object[] newElements = Arrays.copyOf(current, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
@@ -607,11 +643,11 @@
}
/**
- * Returns <tt>true</tt> if this list contains all of the elements of the
+ * Returns {@code true} if this list contains all of the elements of the
* specified collection.
*
* @param c collection to be checked for containment in this list
- * @return <tt>true</tt> if this list contains all of the elements of the
+ * @return {@code true} if this list contains all of the elements of the
* specified collection
* @throws NullPointerException if the specified collection is null
* @see #contains(Object)
@@ -632,7 +668,7 @@
* in this class because of the need for an internal temporary array.
*
* @param c collection containing elements to be removed from this list
- * @return <tt>true</tt> if this list changed as a result of the call
+ * @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="../Collection.html#optional-restrictions">optional</a>)
@@ -675,7 +711,7 @@
* its elements that are not contained in the specified collection.
*
* @param c collection containing elements to be retained in this list
- * @return <tt>true</tt> if this list changed as a result of the call
+ * @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="../Collection.html#optional-restrictions">optional</a>)
@@ -727,22 +763,22 @@
Object[] cs = c.toArray();
if (cs.length == 0)
return 0;
- Object[] uniq = new Object[cs.length];
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
int added = 0;
- for (int i = 0; i < cs.length; ++i) { // scan for duplicates
+ // uniquify and compact elements in cs
+ for (int i = 0; i < cs.length; ++i) {
Object e = cs[i];
if (indexOf(e, elements, 0, len) < 0 &&
- indexOf(e, uniq, 0, added) < 0)
- uniq[added++] = e;
+ indexOf(e, cs, 0, added) < 0)
+ cs[added++] = e;
}
if (added > 0) {
Object[] newElements = Arrays.copyOf(elements, len + added);
- System.arraycopy(uniq, 0, newElements, len, added);
+ System.arraycopy(cs, 0, newElements, len, added);
setArray(newElements);
}
return added;
@@ -771,12 +807,13 @@
* collection's iterator.
*
* @param c collection containing elements to be added to this list
- * @return <tt>true</tt> if this list changed as a result of the call
+ * @return {@code true} if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
* @see #add(Object)
*/
public boolean addAll(Collection<? extends E> c) {
- Object[] cs = c.toArray();
+ Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ?
+ ((CopyOnWriteArrayList<?>)c).getArray() : c.toArray();
if (cs.length == 0)
return false;
final ReentrantLock lock = this.lock;
@@ -784,9 +821,13 @@
try {
Object[] elements = getArray();
int len = elements.length;
- Object[] newElements = Arrays.copyOf(elements, len + cs.length);
- System.arraycopy(cs, 0, newElements, len, cs.length);
- setArray(newElements);
+ if (len == 0 && cs.getClass() == Object[].class)
+ setArray(cs);
+ else {
+ Object[] newElements = Arrays.copyOf(elements, len + cs.length);
+ System.arraycopy(cs, 0, newElements, len, cs.length);
+ setArray(newElements);
+ }
return true;
} finally {
lock.unlock();
@@ -804,7 +845,7 @@
* @param index index at which to insert the first element
* from the specified collection
* @param c collection containing elements to be added to this list
- * @return <tt>true</tt> if this list changed as a result of the call
+ * @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
* @see #add(int,Object)
@@ -840,6 +881,74 @@
}
}
+ public void forEach(Consumer<? super E> action) {
+ if (action == null) throw new NullPointerException();
+ Object[] elements = getArray();
+ int len = elements.length;
+ for (int i = 0; i < len; ++i) {
+ @SuppressWarnings("unchecked") E e = (E) elements[i];
+ action.accept(e);
+ }
+ }
+
+ public boolean removeIf(Predicate<? super E> filter) {
+ if (filter == null) throw new NullPointerException();
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ Object[] elements = getArray();
+ int len = elements.length;
+ if (len != 0) {
+ int newlen = 0;
+ Object[] temp = new Object[len];
+ for (int i = 0; i < len; ++i) {
+ @SuppressWarnings("unchecked") E e = (E) elements[i];
+ if (!filter.test(e))
+ temp[newlen++] = e;
+ }
+ if (newlen != len) {
+ setArray(Arrays.copyOf(temp, newlen));
+ return true;
+ }
+ }
+ return false;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ public void replaceAll(UnaryOperator<E> operator) {
+ if (operator == null) throw new NullPointerException();
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ Object[] elements = getArray();
+ int len = elements.length;
+ Object[] newElements = Arrays.copyOf(elements, len);
+ for (int i = 0; i < len; ++i) {
+ @SuppressWarnings("unchecked") E e = (E) elements[i];
+ newElements[i] = operator.apply(e);
+ }
+ setArray(newElements);
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ public void sort(Comparator<? super E> c) {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ Object[] elements = getArray();
+ Object[] newElements = Arrays.copyOf(elements, elements.length);
+ @SuppressWarnings("unchecked") E[] es = (E[])newElements;
+ Arrays.sort(es, c);
+ setArray(newElements);
+ } finally {
+ lock.unlock();
+ }
+ }
+
/**
* Saves this list to a stream (that is, serializes it).
*
@@ -886,8 +995,8 @@
* Returns a string representation of this list. The string
* representation consists of the string representations of the list's
* elements in the order they are returned by its iterator, enclosed in
- * square brackets (<tt>"[]"</tt>). Adjacent elements are separated by
- * the characters <tt>", "</tt> (comma and space). Elements are
+ * square brackets ({@code "[]"}). Adjacent elements are separated by
+ * the characters {@code ", "} (comma and space). Elements are
* converted to strings as by {@link String#valueOf(Object)}.
*
* @return a string representation of this list
@@ -953,7 +1062,7 @@
* <p>The returned iterator provides a snapshot of the state of the list
* when the iterator was constructed. No synchronization is needed while
* traversing the iterator. The iterator does <em>NOT</em> support the
- * <tt>remove</tt> method.
+ * {@code remove} method.
*
* @return an iterator over the elements in this list in proper sequence
*/
@@ -967,7 +1076,7 @@
* <p>The returned iterator provides a snapshot of the state of the list
* when the iterator was constructed. No synchronization is needed while
* traversing the iterator. The iterator does <em>NOT</em> support the
- * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
+ * {@code remove}, {@code set} or {@code add} methods.
*/
public ListIterator<E> listIterator() {
return new COWIterator<E>(getArray(), 0);
@@ -979,7 +1088,7 @@
* <p>The returned iterator provides a snapshot of the state of the list
* when the iterator was constructed. No synchronization is needed while
* traversing the iterator. The iterator does <em>NOT</em> support the
- * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
+ * {@code remove}, {@code set} or {@code add} methods.
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
@@ -992,7 +1101,12 @@
return new COWIterator<E>(elements, index);
}
- private static class COWIterator<E> implements ListIterator<E> {
+ public Spliterator<E> spliterator() {
+ return Spliterators.spliterator
+ (getArray(), Spliterator.IMMUTABLE | Spliterator.ORDERED);
+ }
+
+ static final class COWIterator<E> implements ListIterator<E> {
/** Snapshot of the array */
private final Object[] snapshot;
/** Index of element to be returned by subsequent call to next. */
@@ -1035,7 +1149,7 @@
/**
* Not supported. Always throws UnsupportedOperationException.
- * @throws UnsupportedOperationException always; <tt>remove</tt>
+ * @throws UnsupportedOperationException always; {@code remove}
* is not supported by this iterator.
*/
public void remove() {
@@ -1044,7 +1158,7 @@
/**
* Not supported. Always throws UnsupportedOperationException.
- * @throws UnsupportedOperationException always; <tt>set</tt>
+ * @throws UnsupportedOperationException always; {@code set}
* is not supported by this iterator.
*/
public void set(E e) {
@@ -1053,7 +1167,7 @@
/**
* Not supported. Always throws UnsupportedOperationException.
- * @throws UnsupportedOperationException always; <tt>add</tt>
+ * @throws UnsupportedOperationException always; {@code add}
* is not supported by this iterator.
*/
public void add(E e) {
@@ -1061,12 +1175,13 @@
}
@Override
- @SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
- final int size = snapshot.length;
- for (int i=cursor; i < size; i++) {
- action.accept((E) snapshot[i]);
+ Object[] elements = snapshot;
+ final int size = elements.length;
+ for (int i = cursor; i < size; i++) {
+ @SuppressWarnings("unchecked") E e = (E) elements[i];
+ action.accept(e);
}
cursor = size;
}
@@ -1074,7 +1189,7 @@
/**
* Returns a view of the portion of this list between
- * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
+ * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
* The returned list is backed by this list, so changes in the
* returned list are reflected in this list.
*
@@ -1274,55 +1389,196 @@
}
}
- @Override
public void forEach(Consumer<? super E> action) {
- @SuppressWarnings("unchecked")
- final E[] elements = (E[]) l.getArray();
- checkForComodification();
- l.forEach(action, elements, offset, offset + size);
+ if (action == null) throw new NullPointerException();
+ int lo = offset;
+ int hi = offset + size;
+ Object[] a = expectedArray;
+ if (l.getArray() != a)
+ throw new ConcurrentModificationException();
+ if (lo < 0 || hi > a.length)
+ throw new IndexOutOfBoundsException();
+ for (int i = lo; i < hi; ++i) {
+ @SuppressWarnings("unchecked") E e = (E) a[i];
+ action.accept(e);
+ }
}
- @Override
+ public void replaceAll(UnaryOperator<E> operator) {
+ if (operator == null) throw new NullPointerException();
+ final ReentrantLock lock = l.lock;
+ lock.lock();
+ try {
+ int lo = offset;
+ int hi = offset + size;
+ Object[] elements = expectedArray;
+ if (l.getArray() != elements)
+ throw new ConcurrentModificationException();
+ int len = elements.length;
+ if (lo < 0 || hi > len)
+ throw new IndexOutOfBoundsException();
+ Object[] newElements = Arrays.copyOf(elements, len);
+ for (int i = lo; i < hi; ++i) {
+ @SuppressWarnings("unchecked") E e = (E) elements[i];
+ newElements[i] = operator.apply(e);
+ }
+ l.setArray(expectedArray = newElements);
+ } finally {
+ lock.unlock();
+ }
+ }
+
public void sort(Comparator<? super E> c) {
final ReentrantLock lock = l.lock;
lock.lock();
try {
- checkForComodification();
- l.sort(c, offset, offset + size);
- expectedArray = l.getArray();
+ int lo = offset;
+ int hi = offset + size;
+ Object[] elements = expectedArray;
+ if (l.getArray() != elements)
+ throw new ConcurrentModificationException();
+ int len = elements.length;
+ if (lo < 0 || hi > len)
+ throw new IndexOutOfBoundsException();
+ Object[] newElements = Arrays.copyOf(elements, len);
+ @SuppressWarnings("unchecked") E[] es = (E[])newElements;
+ Arrays.sort(es, lo, hi, c);
+ l.setArray(expectedArray = newElements);
} finally {
lock.unlock();
}
}
- @Override
- public boolean removeIf(Predicate<? super E> filter) {
- Objects.requireNonNull(filter);
+ public boolean removeAll(Collection<?> c) {
+ if (c == null) throw new NullPointerException();
+ boolean removed = false;
+ final ReentrantLock lock = l.lock;
+ lock.lock();
+ try {
+ int n = size;
+ if (n > 0) {
+ int lo = offset;
+ int hi = offset + n;
+ Object[] elements = expectedArray;
+ if (l.getArray() != elements)
+ throw new ConcurrentModificationException();
+ int len = elements.length;
+ if (lo < 0 || hi > len)
+ throw new IndexOutOfBoundsException();
+ int newSize = 0;
+ Object[] temp = new Object[n];
+ for (int i = lo; i < hi; ++i) {
+ Object element = elements[i];
+ if (!c.contains(element))
+ temp[newSize++] = element;
+ }
+ if (newSize != n) {
+ Object[] newElements = new Object[len - n + newSize];
+ System.arraycopy(elements, 0, newElements, 0, lo);
+ System.arraycopy(temp, 0, newElements, lo, newSize);
+ System.arraycopy(elements, hi, newElements,
+ lo + newSize, len - hi);
+ size = newSize;
+ removed = true;
+ l.setArray(expectedArray = newElements);
+ }
+ }
+ } finally {
+ lock.unlock();
+ }
+ return removed;
+ }
+
+ public boolean retainAll(Collection<?> c) {
+ if (c == null) throw new NullPointerException();
+ boolean removed = false;
final ReentrantLock lock = l.lock;
lock.lock();
try {
- checkForComodification();
- final int removeCount =
- l.removeIf(filter, offset, offset + size);
- expectedArray = l.getArray();
- size -= removeCount;
- return removeCount > 0;
+ int n = size;
+ if (n > 0) {
+ int lo = offset;
+ int hi = offset + n;
+ Object[] elements = expectedArray;
+ if (l.getArray() != elements)
+ throw new ConcurrentModificationException();
+ int len = elements.length;
+ if (lo < 0 || hi > len)
+ throw new IndexOutOfBoundsException();
+ int newSize = 0;
+ Object[] temp = new Object[n];
+ for (int i = lo; i < hi; ++i) {
+ Object element = elements[i];
+ if (c.contains(element))
+ temp[newSize++] = element;
+ }
+ if (newSize != n) {
+ Object[] newElements = new Object[len - n + newSize];
+ System.arraycopy(elements, 0, newElements, 0, lo);
+ System.arraycopy(temp, 0, newElements, lo, newSize);
+ System.arraycopy(elements, hi, newElements,
+ lo + newSize, len - hi);
+ size = newSize;
+ removed = true;
+ l.setArray(expectedArray = newElements);
+ }
+ }
} finally {
lock.unlock();
}
+ return removed;
}
- @Override
- public void replaceAll(UnaryOperator<E> operator) {
+ public boolean removeIf(Predicate<? super E> filter) {
+ if (filter == null) throw new NullPointerException();
+ boolean removed = false;
final ReentrantLock lock = l.lock;
lock.lock();
try {
- checkForComodification();
- l.replaceAll(operator, offset, offset + size);
- expectedArray = l.getArray();
+ int n = size;
+ if (n > 0) {
+ int lo = offset;
+ int hi = offset + n;
+ Object[] elements = expectedArray;
+ if (l.getArray() != elements)
+ throw new ConcurrentModificationException();
+ int len = elements.length;
+ if (lo < 0 || hi > len)
+ throw new IndexOutOfBoundsException();
+ int newSize = 0;
+ Object[] temp = new Object[n];
+ for (int i = lo; i < hi; ++i) {
+ @SuppressWarnings("unchecked") E e = (E) elements[i];
+ if (!filter.test(e))
+ temp[newSize++] = e;
+ }
+ if (newSize != n) {
+ Object[] newElements = new Object[len - n + newSize];
+ System.arraycopy(elements, 0, newElements, 0, lo);
+ System.arraycopy(temp, 0, newElements, lo, newSize);
+ System.arraycopy(elements, hi, newElements,
+ lo + newSize, len - hi);
+ size = newSize;
+ removed = true;
+ l.setArray(expectedArray = newElements);
+ }
+ }
} finally {
lock.unlock();
}
+ return removed;
+ }
+
+ public Spliterator<E> spliterator() {
+ int lo = offset;
+ int hi = offset + size;
+ Object[] a = expectedArray;
+ if (l.getArray() != a)
+ throw new ConcurrentModificationException();
+ if (lo < 0 || hi > a.length)
+ throw new IndexOutOfBoundsException();
+ return Spliterators.spliterator
+ (a, lo, hi, Spliterator.IMMUTABLE | Spliterator.ORDERED);
}
}
@@ -1380,11 +1636,12 @@
}
@Override
- @SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
- while (nextIndex() < size) {
- action.accept(it.next());
+ int s = size;
+ ListIterator<E> i = it;
+ while (nextIndex() < s) {
+ action.accept(i.next());
}
}
}
@@ -1405,139 +1662,4 @@
throw new Error(e);
}
}
-
- @Override
- @SuppressWarnings("unchecked")
- public void forEach(Consumer<? super E> action) {
- forEach(action, (E[]) getArray(), 0, size());
- }
-
- private void forEach(Consumer<? super E> action,
- final E[] elements,
- final int from, final int to) {
- Objects.requireNonNull(action);
- for (int i = from; i < to; i++) {
- action.accept(elements[i]);
- }
- }
-
- @Override
- public void sort(Comparator<? super E> c) {
- final ReentrantLock lock = this.lock;
- lock.lock();
- try {
- sort(c, 0, size());
- } finally {
- lock.unlock();
- }
- }
-
- // must be called with this.lock held
- @SuppressWarnings("unchecked")
- private void sort(Comparator<? super E> c, final int from, final int to) {
- final E[] elements = (E[]) getArray();
- final E[] newElements = Arrays.copyOf(elements, elements.length);
- // only elements [from, to) are sorted
- Arrays.sort(newElements, from, to, c);
- setArray(newElements);
- }
-
- @Override
- public boolean removeIf(Predicate<? super E> filter) {
- Objects.requireNonNull(filter);
- final ReentrantLock lock = this.lock;
- lock.lock();
- try {
- return removeIf(filter, 0, size()) > 0;
- } finally {
- lock.unlock();
- }
- }
-
- // must be called with this.lock held
- private int removeIf(Predicate<? super E> filter, final int from, final int to) {
- Objects.requireNonNull(filter);
- final ReentrantLock lock = this.lock;
- lock.lock();
- try {
- @SuppressWarnings("unchecked")
- final E[] elements = (E[]) getArray();
-
- // figure out which elements are to be removed
- // any exception thrown from the filter predicate at this stage
- // will leave the collection unmodified
- int removeCount = 0;
- final int range = to - from;
- final BitSet removeSet = new BitSet(range);
- for (int i = 0; i < range; i++) {
- final E element = elements[from + i];
- if (filter.test(element)) {
- // removeSet is zero-based to keep its size small
- removeSet.set(i);
- removeCount++;
- }
- }
-
- // copy surviving elements into a new array
- if (removeCount > 0) {
- final int newSize = elements.length - removeCount;
- final int newRange = newSize - from;
- @SuppressWarnings("unchecked")
- final E[] newElements = (E[]) new Object[newSize];
- // copy elements before [from, to) unmodified
- for (int i = 0; i < from; i++) {
- newElements[i] = elements[i];
- }
- // elements [from, to) are subject to removal
- int j = 0;
- for (int i = 0; (i < range) && (j < newRange); i++) {
- i = removeSet.nextClearBit(i);
- if (i >= range) {
- break;
- }
- newElements[from + (j++)] = elements[from + i];
- }
- // copy any remaining elements beyond [from, to)
- j += from;
- for (int i = to; (i < elements.length) && (j < newSize); i++) {
- newElements[j++] = elements[i];
- }
- setArray(newElements);
- }
-
- return removeCount;
- } finally {
- lock.unlock();
- }
- }
-
- @Override
- public void replaceAll(UnaryOperator<E> operator) {
- Objects.requireNonNull(operator);
- final ReentrantLock lock = this.lock;
- lock.lock();
- try {
- replaceAll(operator, 0, size());
- } finally {
- lock.unlock();
- }
- }
-
- // must be called with this.lock held
- @SuppressWarnings("unchecked")
- private void replaceAll(UnaryOperator<E> operator, final int from, final int to) {
- final E[] elements = (E[]) getArray();
- final E[] newElements = (E[]) new Object[elements.length];
- for (int i = 0; i < from; i++) {
- newElements[i] = elements[i];
- }
- // the operator is only applied to elements [from, to)
- for (int i = from; i < to; i++) {
- newElements[i] = operator.apply(elements[i]);
- }
- for (int i = to; i < elements.length; i++) {
- newElements[i] = elements[i];
- }
- setArray(newElements);
- }
}
--- a/jdk/src/share/classes/java/util/concurrent/CopyOnWriteArraySet.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/CopyOnWriteArraySet.java Wed Jul 03 11:58:09 2013 +0200
@@ -34,7 +34,14 @@
*/
package java.util.concurrent;
-import java.util.*;
+import java.util.Collection;
+import java.util.Set;
+import java.util.AbstractSet;
+import java.util.Iterator;
+import java.util.Spliterator;
+import java.util.Spliterators;
+import java.util.function.Predicate;
+import java.util.function.Consumer;
/**
* A {@link java.util.Set} that uses an internal {@link CopyOnWriteArrayList}
@@ -45,17 +52,17 @@
* vastly outnumber mutative operations, and you need
* to prevent interference among threads during traversal.
* <li>It is thread-safe.
- * <li>Mutative operations (<tt>add</tt>, <tt>set</tt>, <tt>remove</tt>, etc.)
+ * <li>Mutative operations ({@code add}, {@code set}, {@code remove}, etc.)
* are expensive since they usually entail copying the entire underlying
* array.
- * <li>Iterators do not support the mutative <tt>remove</tt> operation.
+ * <li>Iterators do not support the mutative {@code remove} operation.
* <li>Traversal via iterators is fast and cannot encounter
* interference from other threads. Iterators rely on
* unchanging snapshots of the array at the time the iterators were
* constructed.
* </ul>
*
- * <p> <b>Sample Usage.</b> The following code sketch uses a
+ * <p><b>Sample Usage.</b> The following code sketch uses a
* copy-on-write set to maintain a set of Handler objects that
* perform some action upon state updates.
*
@@ -73,7 +80,7 @@
* public void update() {
* changeState();
* for (Handler handler : handlers)
- * handler.handle();
+ * handler.handle();
* }
* }}</pre>
*
@@ -107,8 +114,15 @@
* @throws NullPointerException if the specified collection is null
*/
public CopyOnWriteArraySet(Collection<? extends E> c) {
- al = new CopyOnWriteArrayList<E>();
- al.addAllAbsent(c);
+ if (c.getClass() == CopyOnWriteArraySet.class) {
+ @SuppressWarnings("unchecked") CopyOnWriteArraySet<E> cc =
+ (CopyOnWriteArraySet<E>)c;
+ al = new CopyOnWriteArrayList<E>(cc.al);
+ }
+ else {
+ al = new CopyOnWriteArrayList<E>();
+ al.addAllAbsent(c);
+ }
}
/**
@@ -121,22 +135,22 @@
}
/**
- * Returns <tt>true</tt> if this set contains no elements.
+ * Returns {@code true} if this set contains no elements.
*
- * @return <tt>true</tt> if this set contains no elements
+ * @return {@code true} if this set contains no elements
*/
public boolean isEmpty() {
return al.isEmpty();
}
/**
- * Returns <tt>true</tt> if this set contains the specified element.
- * More formally, returns <tt>true</tt> if and only if this set
- * contains an element <tt>e</tt> such that
+ * Returns {@code true} if this set contains the specified element.
+ * More formally, returns {@code true} if and only if this set
+ * contains an element {@code e} such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this set is to be tested
- * @return <tt>true</tt> if this set contains the specified element
+ * @return {@code true} if this set contains the specified element
*/
public boolean contains(Object o) {
return al.contains(o);
@@ -172,7 +186,7 @@
* <p>If this set fits in the specified array with room to spare
* (i.e., the array has more elements than this set), the element in
* the array immediately following the end of the set is set to
- * <tt>null</tt>. (This is useful in determining the length of this
+ * {@code null}. (This is useful in determining the length of this
* set <i>only</i> if the caller knows that this set does not contain
* any null elements.)
*
@@ -185,14 +199,14 @@
* precise control over the runtime type of the output array, and may,
* under certain circumstances, be used to save allocation costs.
*
- * <p>Suppose <tt>x</tt> is a set known to contain only strings.
+ * <p>Suppose {@code x} is a set known to contain only strings.
* The following code can be used to dump the set into a newly allocated
- * array of <tt>String</tt>:
+ * array of {@code String}:
*
* <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
*
- * Note that <tt>toArray(new Object[0])</tt> is identical in function to
- * <tt>toArray()</tt>.
+ * Note that {@code toArray(new Object[0])} is identical in function to
+ * {@code toArray()}.
*
* @param a the array into which the elements of this set are to be
* stored, if it is big enough; otherwise, a new array of the same
@@ -217,15 +231,15 @@
/**
* Removes the specified element from this set if it is present.
- * More formally, removes an element <tt>e</tt> such that
+ * More formally, removes an element {@code e} such that
* <tt>(o==null ? e==null : o.equals(e))</tt>,
- * if this set contains such an element. Returns <tt>true</tt> if
+ * if this set contains such an element. Returns {@code true} if
* this set contained the element (or equivalently, if this set
* changed as a result of the call). (This set will not contain the
* element once the call returns.)
*
* @param o object to be removed from this set, if present
- * @return <tt>true</tt> if this set contained the specified element
+ * @return {@code true} if this set contained the specified element
*/
public boolean remove(Object o) {
return al.remove(o);
@@ -233,14 +247,14 @@
/**
* Adds the specified element to this set if it is not already present.
- * More formally, adds the specified element <tt>e</tt> to this set if
- * the set contains no element <tt>e2</tt> such that
+ * More formally, adds the specified element {@code e} to this set if
+ * the set contains no element {@code e2} such that
* <tt>(e==null ? e2==null : e.equals(e2))</tt>.
* If this set already contains the element, the call leaves the set
- * unchanged and returns <tt>false</tt>.
+ * unchanged and returns {@code false}.
*
* @param e element to be added to this set
- * @return <tt>true</tt> if this set did not already contain the specified
+ * @return {@code true} if this set did not already contain the specified
* element
*/
public boolean add(E e) {
@@ -248,12 +262,12 @@
}
/**
- * Returns <tt>true</tt> if this set contains all of the elements of the
+ * Returns {@code true} if this set contains all of the elements of the
* specified collection. If the specified collection is also a set, this
- * method returns <tt>true</tt> if it is a <i>subset</i> of this set.
+ * method returns {@code true} if it is a <i>subset</i> of this set.
*
* @param c collection to be checked for containment in this set
- * @return <tt>true</tt> if this set contains all of the elements of the
+ * @return {@code true} if this set contains all of the elements of the
* specified collection
* @throws NullPointerException if the specified collection is null
* @see #contains(Object)
@@ -265,13 +279,13 @@
/**
* Adds all of the elements in the specified collection to this set if
* they're not already present. If the specified collection is also a
- * set, the <tt>addAll</tt> operation effectively modifies this set so
+ * set, the {@code addAll} operation effectively modifies this set so
* that its value is the <i>union</i> of the two sets. 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 set
- * @return <tt>true</tt> if this set changed as a result of the call
+ * @return {@code true} if this set changed as a result of the call
* @throws NullPointerException if the specified collection is null
* @see #add(Object)
*/
@@ -286,7 +300,7 @@
* <i>asymmetric set difference</i> of the two sets.
*
* @param c collection containing elements to be removed from this set
- * @return <tt>true</tt> if this set changed as a result of the call
+ * @return {@code true} if this set changed as a result of the call
* @throws ClassCastException if the class of an element of this set
* is incompatible with the specified collection (optional)
* @throws NullPointerException if this set contains a null element and the
@@ -307,7 +321,7 @@
* two sets.
*
* @param c collection containing elements to be retained in this set
- * @return <tt>true</tt> if this set changed as a result of the call
+ * @return {@code true} if this set changed as a result of the call
* @throws ClassCastException if the class of an element of this set
* is incompatible with the specified collection (optional)
* @throws NullPointerException if this set contains a null element and the
@@ -326,7 +340,7 @@
* <p>The returned iterator provides a snapshot of the state of the set
* when the iterator was constructed. No synchronization is needed while
* traversing the iterator. The iterator does <em>NOT</em> support the
- * <tt>remove</tt> method.
+ * {@code remove} method.
*
* @return an iterator over the elements in this set
*/
@@ -338,7 +352,7 @@
* Compares the specified object with this set for equality.
* Returns {@code true} if the specified object is the same object
* as this object, or if it is also a {@link Set} and the elements
- * returned by an {@linkplain List#iterator() iterator} over the
+ * returned by an {@linkplain Set#iterator() iterator} over the
* specified set are the same as the elements returned by an
* iterator over this set. More formally, the two iterators are
* considered to return the same elements if they return the same
@@ -382,6 +396,19 @@
return k == len;
}
+ public boolean removeIf(Predicate<? super E> filter) {
+ return al.removeIf(filter);
+ }
+
+ public void forEach(Consumer<? super E> action) {
+ al.forEach(action);
+ }
+
+ public Spliterator<E> spliterator() {
+ return Spliterators.spliterator
+ (al.getArray(), Spliterator.IMMUTABLE | Spliterator.DISTINCT);
+ }
+
/**
* Tests for equality, coping with nulls.
*/
--- a/jdk/src/share/classes/java/util/concurrent/DelayQueue.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/DelayQueue.java Wed Jul 03 11:58:09 2013 +0200
@@ -33,28 +33,31 @@
* http://creativecommons.org/publicdomain/zero/1.0/
*/
-
package java.util.concurrent;
-import java.util.concurrent.locks.*;
+import static java.util.concurrent.TimeUnit.NANOSECONDS;
+import java.util.concurrent.locks.Condition;
+import java.util.concurrent.locks.ReentrantLock;
import java.util.*;
/**
* An unbounded {@linkplain BlockingQueue blocking queue} of
- * <tt>Delayed</tt> elements, in which an element can only be taken
+ * {@code Delayed} elements, in which an element can only be taken
* when its delay has expired. The <em>head</em> of the queue is that
- * <tt>Delayed</tt> element whose delay expired furthest in the
- * past. If no delay has expired there is no head and <tt>poll</tt>
- * will return <tt>null</tt>. Expiration occurs when an element's
- * <tt>getDelay(TimeUnit.NANOSECONDS)</tt> method returns a value less
+ * {@code Delayed} element whose delay expired furthest in the
+ * past. If no delay has expired there is no head and {@code poll}
+ * will return {@code null}. Expiration occurs when an element's
+ * {@code getDelay(TimeUnit.NANOSECONDS)} method returns a value less
* than or equal to zero. Even though unexpired elements cannot be
- * removed using <tt>take</tt> or <tt>poll</tt>, they are otherwise
- * treated as normal elements. For example, the <tt>size</tt> method
+ * removed using {@code take} or {@code poll}, they are otherwise
+ * treated as normal elements. For example, the {@code size} method
* returns the count of both expired and unexpired elements.
* This queue does not permit null elements.
*
* <p>This class and its iterator implement all of the
* <em>optional</em> methods of the {@link Collection} and {@link
- * Iterator} interfaces.
+ * Iterator} interfaces. The Iterator provided in method {@link
+ * #iterator()} is <em>not</em> guaranteed to traverse the elements of
+ * the DelayQueue in any particular order.
*
* <p>This class is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
@@ -64,11 +67,10 @@
* @author Doug Lea
* @param <E> the type of elements held in this collection
*/
-
public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
implements BlockingQueue<E> {
- private transient final ReentrantLock lock = new ReentrantLock();
+ private final transient ReentrantLock lock = new ReentrantLock();
private final PriorityQueue<E> q = new PriorityQueue<E>();
/**
@@ -97,12 +99,12 @@
private final Condition available = lock.newCondition();
/**
- * Creates a new <tt>DelayQueue</tt> that is initially empty.
+ * Creates a new {@code DelayQueue} that is initially empty.
*/
public DelayQueue() {}
/**
- * Creates a <tt>DelayQueue</tt> initially containing the elements of the
+ * Creates a {@code DelayQueue} initially containing the elements of the
* given collection of {@link Delayed} instances.
*
* @param c the collection of elements to initially contain
@@ -117,7 +119,7 @@
* Inserts the specified element into this delay queue.
*
* @param e the element to add
- * @return <tt>true</tt> (as specified by {@link Collection#add})
+ * @return {@code true} (as specified by {@link Collection#add})
* @throws NullPointerException if the specified element is null
*/
public boolean add(E e) {
@@ -128,7 +130,7 @@
* Inserts the specified element into this delay queue.
*
* @param e the element to add
- * @return <tt>true</tt>
+ * @return {@code true}
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E e) {
@@ -164,7 +166,7 @@
* @param e the element to add
* @param timeout This parameter is ignored as the method never blocks
* @param unit This parameter is ignored as the method never blocks
- * @return <tt>true</tt>
+ * @return {@code true}
* @throws NullPointerException {@inheritDoc}
*/
public boolean offer(E e, long timeout, TimeUnit unit) {
@@ -172,10 +174,10 @@
}
/**
- * Retrieves and removes the head of this queue, or returns <tt>null</tt>
+ * Retrieves and removes the head of this queue, or returns {@code null}
* if this queue has no elements with an expired delay.
*
- * @return the head of this queue, or <tt>null</tt> if this
+ * @return the head of this queue, or {@code null} if this
* queue has no elements with an expired delay
*/
public E poll() {
@@ -183,7 +185,7 @@
lock.lock();
try {
E first = q.peek();
- if (first == null || first.getDelay(TimeUnit.NANOSECONDS) > 0)
+ if (first == null || first.getDelay(NANOSECONDS) > 0)
return null;
else
return q.poll();
@@ -208,10 +210,11 @@
if (first == null)
available.await();
else {
- long delay = first.getDelay(TimeUnit.NANOSECONDS);
+ long delay = first.getDelay(NANOSECONDS);
if (delay <= 0)
return q.poll();
- else if (leader != null)
+ first = null; // don't retain ref while waiting
+ if (leader != null)
available.await();
else {
Thread thisThread = Thread.currentThread();
@@ -237,7 +240,7 @@
* until an element with an expired delay is available on this queue,
* or the specified wait time expires.
*
- * @return the head of this queue, or <tt>null</tt> if the
+ * @return the head of this queue, or {@code null} if the
* specified waiting time elapses before an element with
* an expired delay becomes available
* @throws InterruptedException {@inheritDoc}
@@ -255,11 +258,12 @@
else
nanos = available.awaitNanos(nanos);
} else {
- long delay = first.getDelay(TimeUnit.NANOSECONDS);
+ long delay = first.getDelay(NANOSECONDS);
if (delay <= 0)
return q.poll();
if (nanos <= 0)
return null;
+ first = null; // don't retain ref while waiting
if (nanos < delay || leader != null)
nanos = available.awaitNanos(nanos);
else {
@@ -284,13 +288,13 @@
/**
* Retrieves, but does not remove, the head of this queue, or
- * returns <tt>null</tt> if this queue is empty. Unlike
- * <tt>poll</tt>, if no expired elements are available in the queue,
+ * returns {@code null} if this queue is empty. Unlike
+ * {@code poll}, if no expired elements are available in the queue,
* this method returns the element that will expire next,
* if one exists.
*
- * @return the head of this queue, or <tt>null</tt> if this
- * queue is empty.
+ * @return the head of this queue, or {@code null} if this
+ * queue is empty
*/
public E peek() {
final ReentrantLock lock = this.lock;
@@ -313,6 +317,17 @@
}
/**
+ * Returns first element only if it is expired.
+ * Used only by drainTo. Call only when holding lock.
+ */
+ private E peekExpired() {
+ // assert lock.isHeldByCurrentThread();
+ E first = q.peek();
+ return (first == null || first.getDelay(NANOSECONDS) > 0) ?
+ null : first;
+ }
+
+ /**
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
@@ -327,11 +342,9 @@
lock.lock();
try {
int n = 0;
- for (;;) {
- E first = q.peek();
- if (first == null || first.getDelay(TimeUnit.NANOSECONDS) > 0)
- break;
- c.add(q.poll());
+ for (E e; (e = peekExpired()) != null;) {
+ c.add(e); // In this order, in case add() throws.
+ q.poll();
++n;
}
return n;
@@ -357,11 +370,9 @@
lock.lock();
try {
int n = 0;
- while (n < maxElements) {
- E first = q.peek();
- if (first == null || first.getDelay(TimeUnit.NANOSECONDS) > 0)
- break;
- c.add(q.poll());
+ for (E e; n < maxElements && (e = peekExpired()) != null;) {
+ c.add(e); // In this order, in case add() throws.
+ q.poll();
++n;
}
return n;
@@ -387,10 +398,10 @@
}
/**
- * Always returns <tt>Integer.MAX_VALUE</tt> because
- * a <tt>DelayQueue</tt> is not capacity constrained.
+ * Always returns {@code Integer.MAX_VALUE} because
+ * a {@code DelayQueue} is not capacity constrained.
*
- * @return <tt>Integer.MAX_VALUE</tt>
+ * @return {@code Integer.MAX_VALUE}
*/
public int remainingCapacity() {
return Integer.MAX_VALUE;
@@ -430,7 +441,7 @@
* <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
- * <tt>null</tt>.
+ * {@code null}.
*
* <p>Like the {@link #toArray()} method, this method acts as bridge between
* array-based and collection-based APIs. Further, this method allows
@@ -438,13 +449,12 @@
* under certain circumstances, be used to save allocation costs.
*
* <p>The following code can be used to dump a delay queue into a newly
- * allocated array of <tt>Delayed</tt>:
+ * allocated array of {@code Delayed}:
*
- * <pre>
- * Delayed[] a = q.toArray(new Delayed[0]);</pre>
+ * <pre> {@code Delayed[] a = q.toArray(new Delayed[0]);}</pre>
*
- * Note that <tt>toArray(new Object[0])</tt> is identical in function to
- * <tt>toArray()</tt>.
+ * Note that {@code toArray(new Object[0])} is identical in function to
+ * {@code toArray()}.
*
* @param a the array into which the elements of the queue are to
* be stored, if it is big enough; otherwise, a new array of the
@@ -480,6 +490,24 @@
}
/**
+ * Identity-based version for use in Itr.remove
+ */
+ void removeEQ(Object o) {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ for (Iterator<E> it = q.iterator(); it.hasNext(); ) {
+ if (o == it.next()) {
+ it.remove();
+ break;
+ }
+ }
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
* Returns an iterator over all the elements (both expired and
* unexpired) in this queue. The iterator does not return the
* elements in any particular order.
@@ -502,7 +530,7 @@
*/
private class Itr implements Iterator<E> {
final Object[] array; // Array of all elements
- int cursor; // index of next element to return;
+ int cursor; // index of next element to return
int lastRet; // index of last element, or -1 if no such
Itr(Object[] array) {
@@ -525,21 +553,8 @@
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
- Object x = array[lastRet];
+ removeEQ(array[lastRet]);
lastRet = -1;
- // Traverse underlying queue to find == element,
- // not just a .equals element.
- lock.lock();
- try {
- for (Iterator<E> it = q.iterator(); it.hasNext(); ) {
- if (it.next() == x) {
- it.remove();
- return;
- }
- }
- } finally {
- lock.unlock();
- }
}
}
--- a/jdk/src/share/classes/java/util/concurrent/Delayed.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/Delayed.java Wed Jul 03 11:58:09 2013 +0200
@@ -40,8 +40,8 @@
* acted upon after a given delay.
*
* <p>An implementation of this interface must define a
- * <tt>compareTo</tt> method that provides an ordering consistent with
- * its <tt>getDelay</tt> method.
+ * {@code compareTo} method that provides an ordering consistent with
+ * its {@code getDelay} method.
*
* @since 1.5
* @author Doug Lea
--- a/jdk/src/share/classes/java/util/concurrent/LinkedBlockingDeque.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/LinkedBlockingDeque.java Wed Jul 03 11:58:09 2013 +0200
@@ -41,12 +41,15 @@
import java.util.NoSuchElementException;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
+import java.util.Spliterator;
+import java.util.Spliterators;
+import java.util.function.Consumer;
/**
* An optionally-bounded {@linkplain BlockingDeque blocking deque} based on
* linked nodes.
*
- * <p> The optional capacity bound constructor argument serves as a
+ * <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
@@ -315,8 +318,8 @@
// BlockingDeque methods
/**
- * @throws IllegalStateException {@inheritDoc}
- * @throws NullPointerException {@inheritDoc}
+ * @throws IllegalStateException if this deque is full
+ * @throws NullPointerException {@inheritDoc}
*/
public void addFirst(E e) {
if (!offerFirst(e))
@@ -324,7 +327,7 @@
}
/**
- * @throws IllegalStateException {@inheritDoc}
+ * @throws IllegalStateException if this deque is full
* @throws NullPointerException {@inheritDoc}
*/
public void addLast(E e) {
@@ -623,8 +626,7 @@
*
* <p>This method is equivalent to {@link #addLast}.
*
- * @throws IllegalStateException if the element cannot be added at this
- * time due to capacity restrictions
+ * @throws IllegalStateException if this deque is full
* @throws NullPointerException if the specified element is null
*/
public boolean add(E e) {
@@ -761,8 +763,8 @@
// Stack methods
/**
- * @throws IllegalStateException {@inheritDoc}
- * @throws NullPointerException {@inheritDoc}
+ * @throws IllegalStateException if this deque is full
+ * @throws NullPointerException {@inheritDoc}
*/
public void push(E e) {
addFirst(e);
@@ -852,7 +854,7 @@
// * @throws ClassCastException {@inheritDoc}
// * @throws NullPointerException {@inheritDoc}
// * @throws IllegalArgumentException {@inheritDoc}
-// * @throws IllegalStateException {@inheritDoc}
+// * @throws IllegalStateException if this deque is full
// * @see #add(Object)
// */
// public boolean addAll(Collection<? extends E> c) {
@@ -1151,6 +1153,127 @@
Node<E> nextNode(Node<E> n) { return n.prev; }
}
+ /** A customized variant of Spliterators.IteratorSpliterator */
+ static final class LBDSpliterator<E> implements Spliterator<E> {
+ static final int MAX_BATCH = 1 << 25; // max batch array size;
+ final LinkedBlockingDeque<E> queue;
+ Node<E> current; // current node; null until initialized
+ int batch; // batch size for splits
+ boolean exhausted; // true when no more nodes
+ long est; // size estimate
+ LBDSpliterator(LinkedBlockingDeque<E> queue) {
+ this.queue = queue;
+ this.est = queue.size();
+ }
+
+ public long estimateSize() { return est; }
+
+ public Spliterator<E> trySplit() {
+ Node<E> h;
+ final LinkedBlockingDeque<E> q = this.queue;
+ int b = batch;
+ int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
+ if (!exhausted &&
+ ((h = current) != null || (h = q.first) != null) &&
+ h.next != null) {
+ Object[] a = new Object[n];
+ final ReentrantLock lock = q.lock;
+ int i = 0;
+ Node<E> p = current;
+ lock.lock();
+ try {
+ if (p != null || (p = q.first) != null) {
+ do {
+ if ((a[i] = p.item) != null)
+ ++i;
+ } while ((p = p.next) != null && i < n);
+ }
+ } finally {
+ lock.unlock();
+ }
+ if ((current = p) == null) {
+ est = 0L;
+ exhausted = true;
+ }
+ else if ((est -= i) < 0L)
+ est = 0L;
+ if (i > 0) {
+ batch = i;
+ return Spliterators.spliterator
+ (a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL |
+ Spliterator.CONCURRENT);
+ }
+ }
+ return null;
+ }
+
+ public void forEachRemaining(Consumer<? super E> action) {
+ if (action == null) throw new NullPointerException();
+ final LinkedBlockingDeque<E> q = this.queue;
+ final ReentrantLock lock = q.lock;
+ if (!exhausted) {
+ exhausted = true;
+ Node<E> p = current;
+ do {
+ E e = null;
+ lock.lock();
+ try {
+ if (p == null)
+ p = q.first;
+ while (p != null) {
+ e = p.item;
+ p = p.next;
+ if (e != null)
+ break;
+ }
+ } finally {
+ lock.unlock();
+ }
+ if (e != null)
+ action.accept(e);
+ } while (p != null);
+ }
+ }
+
+ public boolean tryAdvance(Consumer<? super E> action) {
+ if (action == null) throw new NullPointerException();
+ final LinkedBlockingDeque<E> q = this.queue;
+ final ReentrantLock lock = q.lock;
+ if (!exhausted) {
+ E e = null;
+ lock.lock();
+ try {
+ if (current == null)
+ current = q.first;
+ while (current != null) {
+ e = current.item;
+ current = current.next;
+ if (e != null)
+ break;
+ }
+ } finally {
+ lock.unlock();
+ }
+ if (current == null)
+ exhausted = true;
+ if (e != null) {
+ action.accept(e);
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return Spliterator.ORDERED | Spliterator.NONNULL |
+ Spliterator.CONCURRENT;
+ }
+ }
+
+ public Spliterator<E> spliterator() {
+ return new LBDSpliterator<E>(this);
+ }
+
/**
* Saves this deque to a stream (that is, serializes it).
*
--- a/jdk/src/share/classes/java/util/concurrent/LinkedBlockingQueue.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/LinkedBlockingQueue.java Wed Jul 03 11:58:09 2013 +0200
@@ -42,6 +42,9 @@
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
+import java.util.Spliterator;
+import java.util.Spliterators;
+import java.util.function.Consumer;
/**
* An optionally-bounded {@linkplain BlockingQueue blocking queue} based on
@@ -56,7 +59,7 @@
* 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
+ * <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
@@ -216,7 +219,7 @@
}
/**
- * Lock to prevent both puts and takes.
+ * Locks to prevent both puts and takes.
*/
void fullyLock() {
putLock.lock();
@@ -224,7 +227,7 @@
}
/**
- * Unlock to allow both puts and takes.
+ * Unlocks to allow both puts and takes.
*/
void fullyUnlock() {
takeLock.unlock();
@@ -362,7 +365,7 @@
* 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.
+ * the specified waiting time elapses before space is available
* @throws InterruptedException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
@@ -782,6 +785,7 @@
* item to hand out so that if hasNext() reports true, we will
* still have it to return even if lost race with a take etc.
*/
+
private Node<E> current;
private Node<E> lastRet;
private E currentElement;
@@ -855,6 +859,124 @@
}
}
+ /** A customized variant of Spliterators.IteratorSpliterator */
+ static final class LBQSpliterator<E> implements Spliterator<E> {
+ static final int MAX_BATCH = 1 << 25; // max batch array size;
+ final LinkedBlockingQueue<E> queue;
+ Node<E> current; // current node; null until initialized
+ int batch; // batch size for splits
+ boolean exhausted; // true when no more nodes
+ long est; // size estimate
+ LBQSpliterator(LinkedBlockingQueue<E> queue) {
+ this.queue = queue;
+ this.est = queue.size();
+ }
+
+ public long estimateSize() { return est; }
+
+ public Spliterator<E> trySplit() {
+ Node<E> h;
+ final LinkedBlockingQueue<E> q = this.queue;
+ int b = batch;
+ int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
+ if (!exhausted &&
+ ((h = current) != null || (h = q.head.next) != null) &&
+ h.next != null) {
+ Object[] a = new Object[n];
+ int i = 0;
+ Node<E> p = current;
+ q.fullyLock();
+ try {
+ if (p != null || (p = q.head.next) != null) {
+ do {
+ if ((a[i] = p.item) != null)
+ ++i;
+ } while ((p = p.next) != null && i < n);
+ }
+ } finally {
+ q.fullyUnlock();
+ }
+ if ((current = p) == null) {
+ est = 0L;
+ exhausted = true;
+ }
+ else if ((est -= i) < 0L)
+ est = 0L;
+ if (i > 0) {
+ batch = i;
+ return Spliterators.spliterator
+ (a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL |
+ Spliterator.CONCURRENT);
+ }
+ }
+ return null;
+ }
+
+ public void forEachRemaining(Consumer<? super E> action) {
+ if (action == null) throw new NullPointerException();
+ final LinkedBlockingQueue<E> q = this.queue;
+ if (!exhausted) {
+ exhausted = true;
+ Node<E> p = current;
+ do {
+ E e = null;
+ q.fullyLock();
+ try {
+ if (p == null)
+ p = q.head.next;
+ while (p != null) {
+ e = p.item;
+ p = p.next;
+ if (e != null)
+ break;
+ }
+ } finally {
+ q.fullyUnlock();
+ }
+ if (e != null)
+ action.accept(e);
+ } while (p != null);
+ }
+ }
+
+ public boolean tryAdvance(Consumer<? super E> action) {
+ if (action == null) throw new NullPointerException();
+ final LinkedBlockingQueue<E> q = this.queue;
+ if (!exhausted) {
+ E e = null;
+ q.fullyLock();
+ try {
+ if (current == null)
+ current = q.head.next;
+ while (current != null) {
+ e = current.item;
+ current = current.next;
+ if (e != null)
+ break;
+ }
+ } finally {
+ q.fullyUnlock();
+ }
+ if (current == null)
+ exhausted = true;
+ if (e != null) {
+ action.accept(e);
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return Spliterator.ORDERED | Spliterator.NONNULL |
+ Spliterator.CONCURRENT;
+ }
+ }
+
+ public Spliterator<E> spliterator() {
+ return new LBQSpliterator<E>(this);
+ }
+
/**
* Saves this queue to a stream (that is, serializes it).
*
--- a/jdk/src/share/classes/java/util/concurrent/LinkedTransferQueue.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/LinkedTransferQueue.java Wed Jul 03 11:58:09 2013 +0200
@@ -40,8 +40,10 @@
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Queue;
-import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.LockSupport;
+import java.util.Spliterator;
+import java.util.Spliterators;
+import java.util.function.Consumer;
/**
* An unbounded {@link TransferQueue} based on linked nodes.
@@ -777,6 +779,24 @@
}
/**
+ * Version of firstOfMode used by Spliterator
+ */
+ final Node firstDataNode() {
+ for (Node p = head; p != null;) {
+ Object item = p.item;
+ if (p.isData) {
+ if (item != null && item != p)
+ return p;
+ }
+ else if (item == null)
+ break;
+ if (p == (p = p.next))
+ p = head;
+ }
+ return null;
+ }
+
+ /**
* Returns the item in the first unmatched node with isData; or
* null if none. Used by peek.
*/
@@ -910,6 +930,98 @@
}
}
+ /** A customized variant of Spliterators.IteratorSpliterator */
+ static final class LTQSpliterator<E> implements Spliterator<E> {
+ static final int MAX_BATCH = 1 << 25; // max batch array size;
+ final LinkedTransferQueue<E> queue;
+ Node current; // current node; null until initialized
+ int batch; // batch size for splits
+ boolean exhausted; // true when no more nodes
+ LTQSpliterator(LinkedTransferQueue<E> queue) {
+ this.queue = queue;
+ }
+
+ public Spliterator<E> trySplit() {
+ Node p;
+ final LinkedTransferQueue<E> q = this.queue;
+ int b = batch;
+ int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
+ if (!exhausted &&
+ ((p = current) != null || (p = q.firstDataNode()) != null) &&
+ p.next != null) {
+ Object[] a = new Object[n];
+ int i = 0;
+ do {
+ if ((a[i] = p.item) != null)
+ ++i;
+ if (p == (p = p.next))
+ p = q.firstDataNode();
+ } while (p != null && i < n);
+ if ((current = p) == null)
+ exhausted = true;
+ if (i > 0) {
+ batch = i;
+ return Spliterators.spliterator
+ (a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL |
+ Spliterator.CONCURRENT);
+ }
+ }
+ return null;
+ }
+
+ @SuppressWarnings("unchecked")
+ public void forEachRemaining(Consumer<? super E> action) {
+ Node p;
+ if (action == null) throw new NullPointerException();
+ final LinkedTransferQueue<E> q = this.queue;
+ if (!exhausted &&
+ ((p = current) != null || (p = q.firstDataNode()) != null)) {
+ exhausted = true;
+ do {
+ Object e = p.item;
+ if (p == (p = p.next))
+ p = q.firstDataNode();
+ if (e != null)
+ action.accept((E)e);
+ } while (p != null);
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ public boolean tryAdvance(Consumer<? super E> action) {
+ Node p;
+ if (action == null) throw new NullPointerException();
+ final LinkedTransferQueue<E> q = this.queue;
+ if (!exhausted &&
+ ((p = current) != null || (p = q.firstDataNode()) != null)) {
+ Object e;
+ do {
+ e = p.item;
+ if (p == (p = p.next))
+ p = q.firstDataNode();
+ } while (e == null && p != null);
+ if ((current = p) == null)
+ exhausted = true;
+ if (e != null) {
+ action.accept((E)e);
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public long estimateSize() { return Long.MAX_VALUE; }
+
+ public int characteristics() {
+ return Spliterator.ORDERED | Spliterator.NONNULL |
+ Spliterator.CONCURRENT;
+ }
+ }
+
+ public Spliterator<E> spliterator() {
+ return new LTQSpliterator<E>(this);
+ }
+
/* -------------- Removal methods -------------- */
/**
--- a/jdk/src/share/classes/java/util/concurrent/PriorityBlockingQueue.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/PriorityBlockingQueue.java Wed Jul 03 11:58:09 2013 +0200
@@ -37,7 +37,17 @@
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
-import java.util.*;
+import java.util.AbstractQueue;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.PriorityQueue;
+import java.util.Queue;
+import java.util.SortedSet;
+import java.util.Spliterator;
+import java.util.function.Consumer;
/**
* An unbounded {@linkplain BlockingQueue blocking queue} that uses
@@ -342,7 +352,6 @@
* @param k the position to fill
* @param x the item to insert
* @param array the heap array
- * @param n heap size
*/
private static <T> void siftUpComparable(int k, T x, Object[] array) {
Comparable<? super T> key = (Comparable<? super T>) x;
@@ -936,6 +945,70 @@
}
}
+ // Similar to Collections.ArraySnapshotSpliterator but avoids
+ // commitment to toArray until needed
+ static final class PBQSpliterator<E> implements Spliterator<E> {
+ final PriorityBlockingQueue<E> queue;
+ Object[] array;
+ int index;
+ int fence;
+
+ PBQSpliterator(PriorityBlockingQueue<E> queue, Object[] array,
+ int index, int fence) {
+ this.queue = queue;
+ this.array = array;
+ this.index = index;
+ this.fence = fence;
+ }
+
+ final int getFence() {
+ int hi;
+ if ((hi = fence) < 0)
+ hi = fence = (array = queue.toArray()).length;
+ return hi;
+ }
+
+ public Spliterator<E> trySplit() {
+ int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+ return (lo >= mid) ? null :
+ new PBQSpliterator<E>(queue, array, lo, index = mid);
+ }
+
+ @SuppressWarnings("unchecked")
+ public void forEachRemaining(Consumer<? super E> action) {
+ Object[] a; int i, hi; // hoist accesses and checks from loop
+ if (action == null)
+ throw new NullPointerException();
+ if ((a = array) == null)
+ fence = (a = queue.toArray()).length;
+ if ((hi = fence) <= a.length &&
+ (i = index) >= 0 && i < (index = hi)) {
+ do { action.accept((E)a[i]); } while (++i < hi);
+ }
+ }
+
+ public boolean tryAdvance(Consumer<? super E> action) {
+ if (action == null)
+ throw new NullPointerException();
+ if (getFence() > index && index >= 0) {
+ @SuppressWarnings("unchecked") E e = (E) array[index++];
+ action.accept(e);
+ return true;
+ }
+ return false;
+ }
+
+ public long estimateSize() { return (long)(getFence() - index); }
+
+ public int characteristics() {
+ return Spliterator.NONNULL | Spliterator.SIZED | Spliterator.SUBSIZED;
+ }
+ }
+
+ public Spliterator<E> spliterator() {
+ return new PBQSpliterator<E>(this, null, 0, -1);
+ }
+
// Unsafe mechanics
private static final sun.misc.Unsafe UNSAFE;
private static final long allocationSpinLockOffset;
--- a/jdk/src/share/classes/java/util/concurrent/SynchronousQueue.java Tue Jul 02 15:58:09 2013 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/SynchronousQueue.java Wed Jul 03 11:58:09 2013 +0200
@@ -44,17 +44,17 @@
* operation must wait for a corresponding remove operation by another
* thread, and vice versa. A synchronous queue does not have any
* internal capacity, not even a capacity of one. You cannot
- * <tt>peek</tt> at a synchronous queue because an element is only
+ * {@code peek} at a synchronous queue because an element is only
* present when you try to remove it; you cannot insert an element
* (using any method) unless another thread is trying to remove it;
* you cannot iterate as there is nothing to iterate. The
* <em>head</em> of the queue is the element that the first queued
* inserting thread is trying to add to the queue; if there is no such
* queued thread then no element is available for removal and
- * <tt>poll()</tt> will return <tt>null</tt>. For purposes of other
- * <tt>Collection</tt> methods (for example <tt>contains</tt>), a
- * <tt>SynchronousQueue</tt> acts as an empty collection. This queue
- * does not permit <tt>null</tt> elements.
+ * {@code poll()} will return {@code null}. For purposes of other
+ * {@code Collection} methods (for example {@code contains}), a
+ * {@code SynchronousQueue} acts as an empty collection. This queue
+ * does not permit {@code null} elements.
*
* <p>Synchronous queues are similar to rendezvous channels used in
* CSP and Ada. They are well suited for handoff designs, in which an
@@ -62,10 +62,10 @@
* in another thread in order to hand it some information, event, or
* task.
*
- * <p> This class supports an optional fairness policy for ordering
+ * <p>This class supports an optional fairness policy for ordering
* waiting producer and consumer threads. By default, this ordering
* is not guaranteed. However, a queue constructed with fairness set
- * to <tt>true</tt> grants threads access in FIFO order.
+ * to {@code true} grants threads access in FIFO order.
*
* <p>This class and its iterator implement all of the
* <em>optional</em> methods of the {@link Collection} and {@link
@@ -599,7 +599,7 @@
/**
* Reference to a cancelled node that might not yet have been
* unlinked from queue because it was the last inserted node
- * when it cancelled.
+ * when it was cancelled.
*/
transient volatile QNode cleanMe;
@@ -847,14 +847,14 @@
private transient volatile Transferer<E> transferer;
/**
- * Creates a <tt>SynchronousQueue</tt> with nonfair access policy.
+ * Creates a {@code SynchronousQueue} with nonfair access policy.
*/
public SynchronousQueue() {
this(false);
}
/**
- * Creates a <tt>SynchronousQueue</tt> with the specified fairness policy.
+ * Creates a {@code SynchronousQueue} with the specified fairness policy.
*
* @param fair if true, waiting threads contend in FIFO order for
* access; otherwise the order is unspecified.
@@ -882,8 +882,8 @@
* Inserts the specified element into this queue, waiting if necessary
* up to the specified wait time for another thread to receive it.
*
- * @return <tt>true</tt> if successful, or <tt>false</tt> if the
- * specified waiting time elapses before a consumer appears.
+ * @return {@code true} if successful, or {@code false} if the
+ * specified waiting time elapses before a consumer appears
* @throws InterruptedException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
@@ -902,8 +902,8 @@
* waiting to receive it.
*
* @param e the element to add
- * @return <tt>true</tt> if the element was added to this queue, else
- * <tt>false</tt>
+ * @return {@code true} if the element was added to this queue, else
+ * {@code false}
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E e) {
@@ -931,8 +931,8 @@
* if necessary up to the specified wait time, for another thread
* to insert it.
*
- * @return the head of this queue, or <tt>null</tt> if the
- * specified waiting time elapses before an element is present.
+ * @return the head of this queue, or {@code null} if the
+ * specified waiting time elapses before an element is present
* @throws InterruptedException {@inheritDoc}
*/
public E poll(long timeout, TimeUnit unit) throws InterruptedException {
@@ -946,18 +946,18 @@
* Retrieves and removes the head of this queue, if another thread
* is currently making an element available.
*
- * @return the head of this queue, or <tt>null</tt> if no
- * element is available.
+ * @return the head of this queue, or {@code null} if no
+ * element is available
*/
public E poll() {
return transferer.transfer(null, true, 0);
}
/**
- * Always returns <tt>true</tt>.
- * A <tt>SynchronousQueue</tt> has no internal capacity.
+ * Always returns {@code true}.
+ * A {@code SynchronousQueue} has no internal capacity.
*
- * @return <tt>true</tt>
+ * @return {@code true}
*/
public boolean isEmpty() {
return true;
@@ -965,9 +965,9 @@
/**
* Always returns zero.
- * A <tt>SynchronousQueue</tt> has no internal capacity.
+ * A {@code SynchronousQueue} has no internal capacity.
*
- * @return zero.
+ * @return zero
*/
public int size() {
return 0;
@@ -975,9 +975,9 @@
/**
* Always returns zero.
- * A <tt>SynchronousQueue</tt> has no internal capacity.
+ * A {@code SynchronousQueue} has no internal capacity.
*
- * @return zero.
+ * @return zero
*/
public int remainingCapacity() {
return 0;
@@ -985,80 +985,80 @@
/**
* Does nothing.
- * A <tt>SynchronousQueue</tt> has no internal capacity.
+ * A {@code SynchronousQueue} has no internal capacity.
*/
public void clear() {
}
/**
- * Always returns <tt>false</tt>.
- * A <tt>SynchronousQueue</tt> has no internal capacity.
+ * Always returns {@code false}.
+ * A {@code SynchronousQueue} has no internal capacity.
*
* @param o the element
- * @return <tt>false</tt>
+ * @return {@code false}
*/
public boolean contains(Object o) {
return false;
}
/**
- * Always returns <tt>false</tt>.
- * A <tt>SynchronousQueue</tt> has no internal capacity.
+ * Always returns {@code false}.
+ * A {@code SynchronousQueue} has no internal capacity.
*
* @param o the element to remove
- * @return <tt>false</tt>
+ * @return {@code false}
*/
public boolean remove(Object o) {
return false;
}
/**
- * Returns <tt>false</tt> unless the given collection is empty.
- * A <tt>SynchronousQueue</tt> has no internal capacity.
+ * Returns {@code false} unless the given collection is empty.
+ * A {@code SynchronousQueue} has no internal capacity.
*
* @param c the collection
- * @return <tt>false</tt> unless given collection is empty
+ * @return {@code false} unless given collection is empty
*/
public boolean containsAll(Collection<?> c) {
return c.isEmpty();
}
/**
- * Always returns <tt>false</tt>.
- * A <tt>SynchronousQueue</tt> has no internal capacity.
+ * Always returns {@code false}.
+ * A {@code SynchronousQueue} has no internal capacity.
*
* @param c the collection
- * @return <tt>false</tt>
+ * @return {@code false}
*/
public boolean removeAll(Collection<?> c) {
return false;
}
/**
- * Always returns <tt>false</tt>.
- * A <tt>SynchronousQueue</tt> has no internal capacity.
+ * Always returns {@code false}.
+ * A {@code SynchronousQueue} has no internal capacity.
*
* @param c the collection
- * @return <tt>false</tt>
+ * @return {@code false}
*/
public boolean retainAll(Collection<?> c) {
return false;
}
/**
- * Always returns <tt>null</tt>.
- * A <tt>SynchronousQueue</tt> does not return elements
+ * Always returns {@code null}.
+ * A {@code SynchronousQueue} does not return elements
* unless actively waited on.
*
- * @return <tt>null</tt>
+ * @return {@code null}
*/
public E peek() {
return null;
}
/**
- * Returns an empty iterator in which <tt>hasNext</tt> always returns
- * <tt>false</tt>.
+ * Returns an empty iterator in which {@code hasNext} always returns
+ * {@code false}.
*
* @return an empty iterator
*/
@@ -1077,6 +1077,10 @@
public void remove() { throw new IllegalStateException(); }
}
+ public Spliterator<E> spliterator() {
+ return Spliterators.emptySpliterator();
+ }
+
/**
* Returns a zero-length array.
* @return a zero-length array
@@ -1086,7 +1090,7 @@
}
/**
- * Sets the zeroeth element of the specified array to <tt>null</tt>
+ * Sets the zeroeth element of the specified array to {@code null}
* (if the array has non-zero length) and returns it.
*
* @param a the array