40 import java.util.Collection; |
40 import java.util.Collection; |
41 import java.util.Deque; |
41 import java.util.Deque; |
42 import java.util.Iterator; |
42 import java.util.Iterator; |
43 import java.util.NoSuchElementException; |
43 import java.util.NoSuchElementException; |
44 import java.util.Queue; |
44 import java.util.Queue; |
|
45 import java.util.Spliterator; |
|
46 import java.util.Spliterators; |
|
47 import java.util.function.Consumer; |
45 |
48 |
46 /** |
49 /** |
47 * An unbounded concurrent {@linkplain Deque deque} based on linked nodes. |
50 * An unbounded concurrent {@linkplain Deque deque} based on linked nodes. |
48 * Concurrent insertion, removal, and access operations execute safely |
51 * Concurrent insertion, removal, and access operations execute safely |
49 * across multiple threads. |
52 * across multiple threads. |
1022 public boolean add(E e) { |
1025 public boolean add(E e) { |
1023 return offerLast(e); |
1026 return offerLast(e); |
1024 } |
1027 } |
1025 |
1028 |
1026 public E poll() { return pollFirst(); } |
1029 public E poll() { return pollFirst(); } |
|
1030 public E peek() { return peekFirst(); } |
|
1031 |
|
1032 /** |
|
1033 * @throws NoSuchElementException {@inheritDoc} |
|
1034 */ |
1027 public E remove() { return removeFirst(); } |
1035 public E remove() { return removeFirst(); } |
1028 public E peek() { return peekFirst(); } |
1036 |
|
1037 /** |
|
1038 * @throws NoSuchElementException {@inheritDoc} |
|
1039 */ |
|
1040 public E pop() { return removeFirst(); } |
|
1041 |
|
1042 /** |
|
1043 * @throws NoSuchElementException {@inheritDoc} |
|
1044 */ |
1029 public E element() { return getFirst(); } |
1045 public E element() { return getFirst(); } |
|
1046 |
|
1047 /** |
|
1048 * @throws NullPointerException {@inheritDoc} |
|
1049 */ |
1030 public void push(E e) { addFirst(e); } |
1050 public void push(E e) { addFirst(e); } |
1031 public E pop() { return removeFirst(); } |
|
1032 |
1051 |
1033 /** |
1052 /** |
1034 * Removes the first element {@code e} such that |
1053 * Removes the first element {@code e} such that |
1035 * {@code o.equals(e)}, if such an element exists in this deque. |
1054 * {@code o.equals(e)}, if such an element exists in this deque. |
1036 * If the deque does not contain the element, it is unchanged. |
1055 * If the deque does not contain the element, it is unchanged. |
1383 private class DescendingItr extends AbstractItr { |
1402 private class DescendingItr extends AbstractItr { |
1384 Node<E> startNode() { return last(); } |
1403 Node<E> startNode() { return last(); } |
1385 Node<E> nextNode(Node<E> p) { return pred(p); } |
1404 Node<E> nextNode(Node<E> p) { return pred(p); } |
1386 } |
1405 } |
1387 |
1406 |
|
1407 /** A customized variant of Spliterators.IteratorSpliterator */ |
|
1408 static final class CLDSpliterator<E> implements Spliterator<E> { |
|
1409 static final int MAX_BATCH = 1 << 25; // max batch array size; |
|
1410 final ConcurrentLinkedDeque<E> queue; |
|
1411 Node<E> current; // current node; null until initialized |
|
1412 int batch; // batch size for splits |
|
1413 boolean exhausted; // true when no more nodes |
|
1414 CLDSpliterator(ConcurrentLinkedDeque<E> queue) { |
|
1415 this.queue = queue; |
|
1416 } |
|
1417 |
|
1418 public Spliterator<E> trySplit() { |
|
1419 Node<E> p; |
|
1420 final ConcurrentLinkedDeque<E> q = this.queue; |
|
1421 int b = batch; |
|
1422 int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1; |
|
1423 if (!exhausted && |
|
1424 ((p = current) != null || (p = q.first()) != null)) { |
|
1425 if (p.item == null && p == (p = p.next)) |
|
1426 current = p = q.first(); |
|
1427 if (p != null && p.next != null) { |
|
1428 Object[] a = new Object[n]; |
|
1429 int i = 0; |
|
1430 do { |
|
1431 if ((a[i] = p.item) != null) |
|
1432 ++i; |
|
1433 if (p == (p = p.next)) |
|
1434 p = q.first(); |
|
1435 } while (p != null && i < n); |
|
1436 if ((current = p) == null) |
|
1437 exhausted = true; |
|
1438 if (i > 0) { |
|
1439 batch = i; |
|
1440 return Spliterators.spliterator |
|
1441 (a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL | |
|
1442 Spliterator.CONCURRENT); |
|
1443 } |
|
1444 } |
|
1445 } |
|
1446 return null; |
|
1447 } |
|
1448 |
|
1449 public void forEachRemaining(Consumer<? super E> action) { |
|
1450 Node<E> p; |
|
1451 if (action == null) throw new NullPointerException(); |
|
1452 final ConcurrentLinkedDeque<E> q = this.queue; |
|
1453 if (!exhausted && |
|
1454 ((p = current) != null || (p = q.first()) != null)) { |
|
1455 exhausted = true; |
|
1456 do { |
|
1457 E e = p.item; |
|
1458 if (p == (p = p.next)) |
|
1459 p = q.first(); |
|
1460 if (e != null) |
|
1461 action.accept(e); |
|
1462 } while (p != null); |
|
1463 } |
|
1464 } |
|
1465 |
|
1466 public boolean tryAdvance(Consumer<? super E> action) { |
|
1467 Node<E> p; |
|
1468 if (action == null) throw new NullPointerException(); |
|
1469 final ConcurrentLinkedDeque<E> q = this.queue; |
|
1470 if (!exhausted && |
|
1471 ((p = current) != null || (p = q.first()) != null)) { |
|
1472 E e; |
|
1473 do { |
|
1474 e = p.item; |
|
1475 if (p == (p = p.next)) |
|
1476 p = q.first(); |
|
1477 } while (e == null && p != null); |
|
1478 if ((current = p) == null) |
|
1479 exhausted = true; |
|
1480 if (e != null) { |
|
1481 action.accept(e); |
|
1482 return true; |
|
1483 } |
|
1484 } |
|
1485 return false; |
|
1486 } |
|
1487 |
|
1488 public long estimateSize() { return Long.MAX_VALUE; } |
|
1489 |
|
1490 public int characteristics() { |
|
1491 return Spliterator.ORDERED | Spliterator.NONNULL | |
|
1492 Spliterator.CONCURRENT; |
|
1493 } |
|
1494 } |
|
1495 |
|
1496 public Spliterator<E> spliterator() { |
|
1497 return new CLDSpliterator<E>(this); |
|
1498 } |
|
1499 |
1388 /** |
1500 /** |
1389 * Saves this deque to a stream (that is, serializes it). |
1501 * Saves this deque to a stream (that is, serializes it). |
1390 * |
1502 * |
1391 * @serialData All of the elements (each an {@code E}) in |
1503 * @serialData All of the elements (each an {@code E}) in |
1392 * the proper order, followed by a null |
1504 * the proper order, followed by a null |