820 return true;
821 return false;
822 } finally {
823 lock.unlock();
824 }
825 }
826
827 /**
828 * Appends all of the elements in the specified collection to the end of
829 * this deque, in the order that they are returned by the specified
830 * collection's iterator. Attempts to {@code addAll} of a deque to
831 * itself result in {@code IllegalArgumentException}.
832 *
833 * @param c the elements to be inserted into this deque
834 * @return {@code true} if this deque changed as a result of the call
835 * @throws NullPointerException if the specified collection or any
836 * of its elements are null
837 * @throws IllegalArgumentException if the collection is this deque
838 * @throws IllegalStateException if this deque is full
839 * @see #add(Object)
840 */
841 public boolean addAll(Collection<? extends E> c) {
842 if (c == this)
843 // As historically specified in AbstractQueue#addAll
844 throw new IllegalArgumentException();
845
846 // Copy c into a private chain of Nodes
847 Node<E> beg = null, end = null;
848 int n = 0;
849 for (E e : c) {
850 Objects.requireNonNull(e);
851 n++;
852 Node<E> newNode = new Node<E>(e);
853 if (beg == null)
854 beg = end = newNode;
855 else {
856 end.next = newNode;
857 newNode.prev = end;
858 end = newNode;
859 }
1268 *
1269 * <p>The returned spliterator is
1270 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1271 *
1272 * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT},
1273 * {@link Spliterator#ORDERED}, and {@link Spliterator#NONNULL}.
1274 *
1275 * @implNote
1276 * The {@code Spliterator} implements {@code trySplit} to permit limited
1277 * parallelism.
1278 *
1279 * @return a {@code Spliterator} over the elements in this deque
1280 * @since 1.8
1281 */
1282 public Spliterator<E> spliterator() {
1283 return new LBDSpliterator();
1284 }
1285
1286 /**
1287 * @throws NullPointerException {@inheritDoc}
1288 */
1289 public void forEach(Consumer<? super E> action) {
1290 Objects.requireNonNull(action);
1291 forEachFrom(action, null);
1292 }
1293
1294 /**
1295 * Runs action on each element found during a traversal starting at p.
1296 * If p is null, traversal starts at head.
1297 */
1298 void forEachFrom(Consumer<? super E> action, Node<E> p) {
1299 // Extract batches of elements while holding the lock; then
1300 // run the action on the elements while not
1301 final ReentrantLock lock = this.lock;
1302 final int batchSize = 64; // max number of elements per batch
1303 Object[] es = null; // container for batch of elements
1304 int n, len = 0;
1305 do {
1306 lock.lock();
1307 try {
1310 for (Node<E> q = p; q != null; q = succ(q))
1311 if (q.item != null && ++len == batchSize)
1312 break;
1313 es = new Object[len];
1314 }
1315 for (n = 0; p != null && n < len; p = succ(p))
1316 if ((es[n] = p.item) != null)
1317 n++;
1318 } finally {
1319 lock.unlock();
1320 }
1321 for (int i = 0; i < n; i++) {
1322 @SuppressWarnings("unchecked") E e = (E) es[i];
1323 action.accept(e);
1324 }
1325 } while (n > 0 && p != null);
1326 }
1327
1328 /**
1329 * @throws NullPointerException {@inheritDoc}
1330 */
1331 public boolean removeIf(Predicate<? super E> filter) {
1332 Objects.requireNonNull(filter);
1333 return bulkRemove(filter);
1334 }
1335
1336 /**
1337 * @throws NullPointerException {@inheritDoc}
1338 */
1339 public boolean removeAll(Collection<?> c) {
1340 Objects.requireNonNull(c);
1341 return bulkRemove(e -> c.contains(e));
1342 }
1343
1344 /**
1345 * @throws NullPointerException {@inheritDoc}
1346 */
1347 public boolean retainAll(Collection<?> c) {
1348 Objects.requireNonNull(c);
1349 return bulkRemove(e -> !c.contains(e));
1350 }
1351
1352 /** Implementation of bulk remove methods. */
1353 @SuppressWarnings("unchecked")
1354 private boolean bulkRemove(Predicate<? super E> filter) {
1355 boolean removed = false;
1356 Node<E> p = null;
1357 final ReentrantLock lock = this.lock;
1358 Node<E>[] nodes = null;
1359 int n, len = 0;
1360 do {
1361 // 1. Extract batch of up to 64 elements while holding the lock.
1362 long deathRow = 0; // "bitset" of size 64
1363 lock.lock();
1364 try {
1365 if (nodes == null) {
|
820 return true;
821 return false;
822 } finally {
823 lock.unlock();
824 }
825 }
826
827 /**
828 * Appends all of the elements in the specified collection to the end of
829 * this deque, in the order that they are returned by the specified
830 * collection's iterator. Attempts to {@code addAll} of a deque to
831 * itself result in {@code IllegalArgumentException}.
832 *
833 * @param c the elements to be inserted into this deque
834 * @return {@code true} if this deque changed as a result of the call
835 * @throws NullPointerException if the specified collection or any
836 * of its elements are null
837 * @throws IllegalArgumentException if the collection is this deque
838 * @throws IllegalStateException if this deque is full
839 * @see #add(Object)
840 * @since 9
841 */
842 public boolean addAll(Collection<? extends E> c) {
843 if (c == this)
844 // As historically specified in AbstractQueue#addAll
845 throw new IllegalArgumentException();
846
847 // Copy c into a private chain of Nodes
848 Node<E> beg = null, end = null;
849 int n = 0;
850 for (E e : c) {
851 Objects.requireNonNull(e);
852 n++;
853 Node<E> newNode = new Node<E>(e);
854 if (beg == null)
855 beg = end = newNode;
856 else {
857 end.next = newNode;
858 newNode.prev = end;
859 end = newNode;
860 }
1269 *
1270 * <p>The returned spliterator is
1271 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1272 *
1273 * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT},
1274 * {@link Spliterator#ORDERED}, and {@link Spliterator#NONNULL}.
1275 *
1276 * @implNote
1277 * The {@code Spliterator} implements {@code trySplit} to permit limited
1278 * parallelism.
1279 *
1280 * @return a {@code Spliterator} over the elements in this deque
1281 * @since 1.8
1282 */
1283 public Spliterator<E> spliterator() {
1284 return new LBDSpliterator();
1285 }
1286
1287 /**
1288 * @throws NullPointerException {@inheritDoc}
1289 * @since 9
1290 */
1291 public void forEach(Consumer<? super E> action) {
1292 Objects.requireNonNull(action);
1293 forEachFrom(action, null);
1294 }
1295
1296 /**
1297 * Runs action on each element found during a traversal starting at p.
1298 * If p is null, traversal starts at head.
1299 */
1300 void forEachFrom(Consumer<? super E> action, Node<E> p) {
1301 // Extract batches of elements while holding the lock; then
1302 // run the action on the elements while not
1303 final ReentrantLock lock = this.lock;
1304 final int batchSize = 64; // max number of elements per batch
1305 Object[] es = null; // container for batch of elements
1306 int n, len = 0;
1307 do {
1308 lock.lock();
1309 try {
1312 for (Node<E> q = p; q != null; q = succ(q))
1313 if (q.item != null && ++len == batchSize)
1314 break;
1315 es = new Object[len];
1316 }
1317 for (n = 0; p != null && n < len; p = succ(p))
1318 if ((es[n] = p.item) != null)
1319 n++;
1320 } finally {
1321 lock.unlock();
1322 }
1323 for (int i = 0; i < n; i++) {
1324 @SuppressWarnings("unchecked") E e = (E) es[i];
1325 action.accept(e);
1326 }
1327 } while (n > 0 && p != null);
1328 }
1329
1330 /**
1331 * @throws NullPointerException {@inheritDoc}
1332 * @since 9
1333 */
1334 public boolean removeIf(Predicate<? super E> filter) {
1335 Objects.requireNonNull(filter);
1336 return bulkRemove(filter);
1337 }
1338
1339 /**
1340 * @throws NullPointerException {@inheritDoc}
1341 * @since 9
1342 */
1343 public boolean removeAll(Collection<?> c) {
1344 Objects.requireNonNull(c);
1345 return bulkRemove(e -> c.contains(e));
1346 }
1347
1348 /**
1349 * @throws NullPointerException {@inheritDoc}
1350 * @since 9
1351 */
1352 public boolean retainAll(Collection<?> c) {
1353 Objects.requireNonNull(c);
1354 return bulkRemove(e -> !c.contains(e));
1355 }
1356
1357 /** Implementation of bulk remove methods. */
1358 @SuppressWarnings("unchecked")
1359 private boolean bulkRemove(Predicate<? super E> filter) {
1360 boolean removed = false;
1361 Node<E> p = null;
1362 final ReentrantLock lock = this.lock;
1363 Node<E>[] nodes = null;
1364 int n, len = 0;
1365 do {
1366 // 1. Extract batch of up to 64 elements while holding the lock.
1367 long deathRow = 0; // "bitset" of size 64
1368 lock.lock();
1369 try {
1370 if (nodes == null) {
|