LinkedBlockingDeque.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.apache.commons.pool2.impl;

  19. import java.io.IOException;
  20. import java.io.ObjectInputStream;
  21. import java.io.Serializable;
  22. import java.time.Duration;
  23. import java.util.AbstractQueue;
  24. import java.util.Collection;
  25. import java.util.Deque;
  26. import java.util.Iterator;
  27. import java.util.NoSuchElementException;
  28. import java.util.Objects;
  29. import java.util.concurrent.TimeUnit;
  30. import java.util.concurrent.locks.Condition;

  32. /**
  33.  * An optionally-bounded {@linkplain java.util.concurrent.BlockingDeque blocking
  34.  * deque} based on linked nodes.
  35.  *
  36.  * <p> The optional capacity bound constructor argument serves as a
  37.  * way to prevent excessive expansion. The capacity, if unspecified,
  38.  * is equal to {@link Integer#MAX_VALUE}.  Linked nodes are
  39.  * dynamically created upon each insertion unless this would bring the
  40.  * deque above capacity.
  41.  * </p>
  42.  *
  43.  * <p>Most operations run in constant time (ignoring time spent
  44.  * blocking).  Exceptions include {@link #remove(Object) remove},
  45.  * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link
  46.  * #removeLastOccurrence removeLastOccurrence}, {@link #contains
  47.  * contains}, {@link #iterator iterator.remove()}, and the bulk
  48.  * operations, all of which run in linear time.
  49.  * </p>
  50.  *
  51.  * <p>This class and its iterator implement all of the
  52.  * <em>optional</em> methods of the {@link Collection} and {@link
  53.  * Iterator} interfaces.
  54.  * </p>
  55.  *
  56.  * <p>This class is a member of the
  57.  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  58.  * Java Collections Framework</a>.
  59.  * </p>
  60.  *
  61.  * @param <E> the type of elements held in this collection
  62.  *
  63.  * Note: This was copied from Apache Harmony and modified to suit the needs of
  64.  *       Commons Pool.
  65.  *
  66.  * @since 2.0
  67.  */
  68. final class LinkedBlockingDeque<E> extends AbstractQueue<E>
  69.         implements Deque<E>, Serializable {

  71.     /*
  72.      * Implemented as a simple doubly-linked list protected by a
  73.      * single lock and using conditions to manage blocking.
  74.      *
  75.      * To implement weakly consistent iterators, it appears we need to
  76.      * keep all Nodes GC-reachable from a predecessor dequeued Node.
  77.      * That would cause two problems:
  78.      * - allow a rogue Iterator to cause unbounded memory retention
  79.      * - cause cross-generational linking of old Nodes to new Nodes if
  80.      *   a Node was tenured while live, which generational GCs have a
  81.      *   hard time dealing with, causing repeated major collections.
  82.      * However, only non-deleted Nodes need to be reachable from
  83.      * dequeued Nodes, and reachability does not necessarily have to
  84.      * be of the kind understood by the GC.  We use the trick of
  85.      * linking a Node that has just been dequeued to itself.  Such a
  86.      * self-link implicitly means to jump to "first" (for next links)
  87.      * or "last" (for prev links).
  88.      */

  90.     /*
  91.      * We have "diamond" multiple interface/abstract class inheritance
  92.      * here, and that introduces ambiguities. Often we want the
  93.      * BlockingDeque javadoc combined with the AbstractQueue
  94.      * implementation, so a lot of method specs are duplicated here.
  95.      */

  97.     /**
  98.      * Base class for Iterators for LinkedBlockingDeque
  99.      */
  100.     private abstract class AbstractItr implements Iterator<E> {
  101.         /**
  102.          * The next node to return in next()
  103.          */
  104.          Node<E> next;

  106.         /**
  107.          * nextItem holds on to item fields because once we claim that
  108.          * an element exists in hasNext(), we must return item read
  109.          * under lock (in advance()) even if it was in the process of
  110.          * being removed when hasNext() was called.
  111.          */
  112.         E nextItem;

  114.         /**
  115.          * Node returned by most recent call to next. Needed by remove.
  116.          * Reset to null if this element is deleted by a call to remove.
  117.          */
  118.         private Node<E> lastRet;

  120.         /**
  121.          * Constructs a new iterator. Sets the initial position.
  122.          */
  123.         AbstractItr() {
  124.             // set to initial position
  125.             lock.lock();
  126.             try {
  127.                 next = firstNode();
  128.                 nextItem = next == null ? null : next.item;
  129.             } finally {
  130.                 lock.unlock();
  131.             }
  132.         }

  134.         /**
  135.          * Advances next.
  136.          */
  137.         void advance() {
  138.             lock.lock();
  139.             try {
  140.                 // assert next != null;
  141.                 next = succ(next);
  142.                 nextItem = next == null ? null : next.item;
  143.             } finally {
  144.                 lock.unlock();
  145.             }
  146.         }

  148.         /**
  149.          * Obtain the first node to be returned by the iterator.
  150.          *
  151.          * @return first node
  152.          */
  153.         abstract Node<E> firstNode();

  155.         @Override
  156.         public boolean hasNext() {
  157.             return next != null;
  158.         }

  160.         @Override
  161.         public E next() {
  162.             if (next == null) {
  163.                 throw new NoSuchElementException();
  164.             }
  165.             lastRet = next;
  166.             final E x = nextItem;
  167.             advance();
  168.             return x;
  169.         }

  171.         /**
  172.          * For a given node, obtain the next node to be returned by the
  173.          * iterator.
  174.          *
  175.          * @param n given node
  176.          * @return next node
  177.          */
  178.         abstract Node<E> nextNode(Node<E> n);

  180.         @Override
  181.         public void remove() {
  182.             final Node<E> n = lastRet;
  183.             if (n == null) {
  184.                 throw new IllegalStateException();
  185.             }
  186.             lastRet = null;
  187.             lock.lock();
  188.             try {
  189.                 if (n.item != null) {
  190.                     unlink(n);
  191.                 }
  192.             } finally {
  193.                 lock.unlock();
  194.             }
  195.         }

  197.         /**
  198.          * Returns the successor node of the given non-null, but
  199.          * possibly previously deleted, node.
  200.          *
  201.          * @param n node whose successor is sought
  202.          * @return successor node
  203.          */
  204.         private Node<E> succ(Node<E> n) {
  205.             // Chains of deleted nodes ending in null or self-links
  206.             // are possible if multiple interior nodes are removed.
  207.             for (;;) {
  208.                 final Node<E> s = nextNode(n);
  209.                 if (s == null) {
  210.                     return null;
  211.                 }
  212.                 if (s.item != null) {
  213.                     return s;
  214.                 }
  215.                 if (s == n) {
  216.                     return firstNode();
  217.                 }
  218.                 n = s;
  219.             }
  220.         }
  221.     }

  223.     /** Descending iterator */
  224.     private final class DescendingItr extends AbstractItr {
  225.         @Override
  226.         Node<E> firstNode() { return last; }
  227.         @Override
  228.         Node<E> nextNode(final Node<E> n) { return n.prev; }
  229.     }

  231.     /** Forward iterator */
  232.     private final class Itr extends AbstractItr {
  233.         @Override
  234.         Node<E> firstNode() { return first; }
  235.         @Override
  236.         Node<E> nextNode(final Node<E> n) { return n.next; }
  237.         }

  239.     /**
  240.      * Doubly-linked list node class.
  241.      *
  242.      * @param <E> node item type
  243.      */
  244.     private static final class Node<E> {
  245.         /**
  246.          * The item, or null if this node has been removed.
  247.          */
  248.         E item;

  250.         /**
  251.          * One of:
  252.          * - the real predecessor Node
  253.          * - this Node, meaning the predecessor is tail
  254.          * - null, meaning there is no predecessor
  255.          */
  256.         Node<E> prev;

  258.         /**
  259.          * One of:
  260.          * - the real successor Node
  261.          * - this Node, meaning the successor is head
  262.          * - null, meaning there is no successor
  263.          */
  264.         Node<E> next;

  266.         /**
  267.          * Constructs a new list node.
  268.          *
  269.          * @param x The list item
  270.          * @param p Previous item
  271.          * @param n Next item
  272.          */
  273.         Node(final E x, final Node<E> p, final Node<E> n) {
  274.             item = x;
  275.             prev = p;
  276.             next = n;
  277.         }
  278.     }

  280.     private static final long serialVersionUID = -387911632671998426L;

  282.     /**
  283.      * Pointer to first node.
  284.      * Invariant: (first == null && last == null) ||
  285.      *            (first.prev == null && first.item != null)
  286.      */
  287.     private transient Node<E> first; // @GuardedBy("lock")

  289.     /**
  290.      * Pointer to last node.
  291.      * Invariant: (first == null && last == null) ||
  292.      *            (last.next == null && last.item != null)
  293.      */
  294.     private transient Node<E> last; // @GuardedBy("lock")

  296.     /** Number of items in the deque */
  297.     private transient int count; // @GuardedBy("lock")

  299.     /** Maximum number of items in the deque */
  300.     private final int capacity;

  302.     /** Main lock guarding all access */
  303.     private final InterruptibleReentrantLock lock;

  305.     /** Condition for waiting takes */
  306.     private final Condition notEmpty;

  308.     /** Condition for waiting puts */
  309.     private final Condition notFull;

  311.     /**
  312.      * Creates a {@code LinkedBlockingDeque} with a capacity of
  313.      * {@link Integer#MAX_VALUE}.
  314.      */
  315.     public LinkedBlockingDeque() {
  316.         this(Integer.MAX_VALUE);
  317.     }

  319.     /**
  320.      * Creates a {@code LinkedBlockingDeque} with a capacity of
  321.      * {@link Integer#MAX_VALUE} and the given fairness policy.
  322.      * @param fairness true means threads waiting on the deque should be served
  323.      * as if waiting in a FIFO request queue
  324.      */
  325.     public LinkedBlockingDeque(final boolean fairness) {
  326.         this(Integer.MAX_VALUE, fairness);
  327.     }

  329.     // Basic linking and unlinking operations, called only while holding lock

  331.     /**
  332.      * Creates a {@code LinkedBlockingDeque} with a capacity of
  333.      * {@link Integer#MAX_VALUE}, initially containing the elements of
  334.      * the given collection, added in traversal order of the
  335.      * collection's iterator.
  336.      *
  337.      * @param c the collection of elements to initially contain
  338.      * @throws NullPointerException if the specified collection or any
  339.      *         of its elements are null
  340.      */
  341.     public LinkedBlockingDeque(final Collection<? extends E> c) {
  342.         this(Integer.MAX_VALUE);
  343.         lock.lock(); // Never contended, but necessary for visibility
  344.         try {
  345.             for (final E e : c) {
  346.                 Objects.requireNonNull(e);
  347.                 if (!linkLast(e)) {
  348.                     throw new IllegalStateException("Deque full");
  349.                 }
  350.             }
  351.         } finally {
  352.             lock.unlock();
  353.         }
  354.     }

  356.     /**
  357.      * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity.
  358.      *
  359.      * @param capacity the capacity of this deque
  360.      * @throws IllegalArgumentException if {@code capacity} is less than 1
  361.      */
  362.     public LinkedBlockingDeque(final int capacity) {
  363.         this(capacity, false);
  364.     }

  366.     /**
  367.      * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity
  368.      * and fairness policy.
  369.      *
  370.      * @param capacity the capacity of this deque
  371.      * @param fairness true means threads waiting on the deque should be served
  372.      * as if waiting in a FIFO request queue
  373.      * @throws IllegalArgumentException if {@code capacity} is less than 1
  374.      */
  375.     public LinkedBlockingDeque(final int capacity, final boolean fairness) {
  376.         if (capacity <= 0) {
  377.             throw new IllegalArgumentException();
  378.         }
  379.         this.capacity = capacity;
  380.         lock = new InterruptibleReentrantLock(fairness);
  381.         notEmpty = lock.newCondition();
  382.         notFull = lock.newCondition();
  383.     }

  385.     /**
  386.      * {@inheritDoc}
  387.      */
  388.     @Override
  389.     public boolean add(final E e) {
  390.         addLast(e);
  391.         return true;
  392.     }

  394.     /**
  395.      * {@inheritDoc}
  396.      */
  397.     @Override
  398.     public void addFirst(final E e) {
  399.         if (!offerFirst(e)) {
  400.             throw new IllegalStateException("Deque full");
  401.         }
  402.     }

  404.     // BlockingDeque methods

  406.     /**
  407.      * {@inheritDoc}
  408.      */
  409.     @Override
  410.     public void addLast(final E e) {
  411.         if (!offerLast(e)) {
  412.             throw new IllegalStateException("Deque full");
  413.         }
  414.     }

  416.     /**
  417.      * Atomically removes all of the elements from this deque.
  418.      * The deque will be empty after this call returns.
  419.      */
  420.     @Override
  421.     public void clear() {
  422.         lock.lock();
  423.         try {
  424.             for (Node<E> f = first; f != null;) {
  425.                 f.item = null;
  426.                 final Node<E> n = f.next;
  427.                 f.prev = null;
  428.                 f.next = null;
  429.                 f = n;
  430.             }
  431.             first = last = null;
  432.             count = 0;
  433.             notFull.signalAll();
  434.         } finally {
  435.             lock.unlock();
  436.         }
  437.     }

  439.     /**
  440.      * Returns {@code true} if this deque contains the specified element.
  441.      * More formally, returns {@code true} if and only if this deque contains
  442.      * at least one element {@code e} such that {@code o.equals(e)}.
  443.      *
  444.      * @param o object to be checked for containment in this deque
  445.      * @return {@code true} if this deque contains the specified element
  446.      */
  447.     @Override
  448.     public boolean contains(final Object o) {
  449.         if (o == null) {
  450.             return false;
  451.         }
  452.         lock.lock();
  453.         try {
  454.             for (Node<E> p = first; p != null; p = p.next) {
  455.                 if (o.equals(p.item)) {
  456.                     return true;
  457.                 }
  458.             }
  459.             return false;
  460.         } finally {
  461.             lock.unlock();
  462.         }
  463.     }

  465.     /**
  466.      * {@inheritDoc}
  467.      */
  468.     @Override
  469.     public Iterator<E> descendingIterator() {
  470.         return new DescendingItr();
  471.     }

  473.     /**
  474.      * Drains the queue to the specified collection.
  475.      *
  476.      * @param c The collection to add the elements to
  477.      * @return number of elements added to the collection
  478.      * @throws UnsupportedOperationException if the add operation is not
  479.      *         supported by the specified collection
  480.      * @throws ClassCastException if the class of the elements held by this
  481.      *         collection prevents them from being added to the specified
  482.      *         collection
  483.      * @throws NullPointerException if c is null
  484.      * @throws IllegalArgumentException if c is this instance
  485.      */
  486.     public int drainTo(final Collection<? super E> c) {
  487.         return drainTo(c, Integer.MAX_VALUE);
  488.     }

  490.     /**
  491.      * Drains no more than the specified number of elements from the queue to the
  492.      * specified collection.
  493.      *
  494.      * @param collection collection to add the elements to
  495.      * @param maxElements maximum number of elements to remove from the queue
  496.      * @return number of elements added to the collection
  497.      * @throws UnsupportedOperationException if the add operation is not
  498.      *         supported by the specified collection
  499.      * @throws ClassCastException if the class of the elements held by this
  500.      *         collection prevents them from being added to the specified
  501.      *         collection
  502.      * @throws NullPointerException if c is null
  503.      * @throws IllegalArgumentException if c is this instance
  504.      */
  505.     public int drainTo(final Collection<? super E> collection, final int maxElements) {
  506.         Objects.requireNonNull(collection, "collection");
  507.         if (collection == this) {
  508.             throw new IllegalArgumentException();
  509.         }
  510.         lock.lock();
  511.         try {
  512.             final int n = Math.min(maxElements, count);
  513.             for (int i = 0; i < n; i++) {
  514.                 collection.add(first.item); // In this order, in case add() throws.
  515.                 unlinkFirst();
  516.             }
  517.             return n;
  518.         } finally {
  519.             lock.unlock();
  520.         }
  521.     }

  523.     /**
  524.      * Retrieves, but does not remove, the head of the queue represented by
  525.      * this deque.  This method differs from {@link #peek peek} only in that
  526.      * it throws an exception if this deque is empty.
  527.      *
  528.      * <p>This method is equivalent to {@link #getFirst() getFirst}.
  529.      *
  530.      * @return the head of the queue represented by this deque
  531.      * @throws NoSuchElementException if this deque is empty
  532.      */
  533.     @Override
  534.     public E element() {
  535.         return getFirst();
  536.     }

  538.     /**
  539.      * {@inheritDoc}
  540.      */
  541.     @Override
  542.     public E getFirst() {
  543.         final E x = peekFirst();
  544.         if (x == null) {
  545.             throw new NoSuchElementException();
  546.         }
  547.         return x;
  548.     }

  550.     /**
  551.      * {@inheritDoc}
  552.      */
  553.     @Override
  554.     public E getLast() {
  555.         final E x = peekLast();
  556.         if (x == null) {
  557.             throw new NoSuchElementException();
  558.         }
  559.         return x;
  560.     }

  562.     /**
  563.      * Gets the length of the queue of threads waiting to take instances from this deque. See disclaimer on accuracy
  564.      * in {@link java.util.concurrent.locks.ReentrantLock#getWaitQueueLength(Condition)}.
  565.      *
  566.      * @return number of threads waiting on this deque's notEmpty condition.
  567.      */
  568.     public int getTakeQueueLength() {
  569.         lock.lock();
  570.         try {
  571.            return lock.getWaitQueueLength(notEmpty);
  572.         } finally {
  573.             lock.unlock();
  574.         }
  575.     }

  577.     /**
  578.      * Returns true if there are threads waiting to take instances from this deque. See disclaimer on accuracy in
  579.      * {@link java.util.concurrent.locks.ReentrantLock#hasWaiters(Condition)}.
  580.      *
  581.      * @return true if there is at least one thread waiting on this deque's notEmpty condition.
  582.      */
  583.     public boolean hasTakeWaiters() {
  584.         lock.lock();
  585.         try {
  586.             return lock.hasWaiters(notEmpty);
  587.         } finally {
  588.             lock.unlock();
  589.         }
  590.     }

  592.     /**
  593.      * Interrupts the threads currently waiting to take an object from the pool. See disclaimer on accuracy in
  594.      * {@link java.util.concurrent.locks.ReentrantLock#getWaitingThreads(Condition)}.
  595.      */
  596.     public void interuptTakeWaiters() {
  597.         lock.lock();
  598.         try {
  599.             lock.interruptWaiters(notEmpty);
  600.         } finally {
  601.             lock.unlock();
  602.         }
  603.     }

  605.     /**
  606.      * Returns an iterator over the elements in this deque in proper sequence.
  607.      * The elements will be returned in order from first (head) to last (tail).
  608.      * The returned {@code Iterator} is a "weakly consistent" iterator that
  609.      * will never throw {@link java.util.ConcurrentModificationException
  610.      * ConcurrentModificationException},
  611.      * and guarantees to traverse elements as they existed upon
  612.      * construction of the iterator, and may (but is not guaranteed to)
  613.      * reflect any modifications subsequent to construction.
  614.      *
  615.      * @return an iterator over the elements in this deque in proper sequence
  616.      */
  617.     @Override
  618.     public Iterator<E> iterator() {
  619.         return new Itr();
  620.     }

  622.     /**
  623.      * Links provided element as first element, or returns false if full.
  624.      *
  625.      * @param e The element to link as the first element.
  626.      * @return {@code true} if successful, otherwise {@code false}
  627.      */
  628.     private boolean linkFirst(final E e) {
  629.         // assert lock.isHeldByCurrentThread();
  630.         if (count >= capacity) {
  631.             return false;
  632.         }
  633.         final Node<E> f = first;
  634.         final Node<E> x = new Node<>(e, null, f);
  635.         first = x;
  636.         if (last == null) {
  637.             last = x;
  638.         } else {
  639.             f.prev = x;
  640.         }
  641.         ++count;
  642.         notEmpty.signal();
  643.         return true;
  644.     }

  646.     /**
  647.      * Links provided element as last element, or returns false if full.
  648.      *
  649.      * @param e The element to link as the last element.
  650.      * @return {@code true} if successful, otherwise {@code false}
  651.      */
  652.     private boolean linkLast(final E e) {
  653.         // assert lock.isHeldByCurrentThread();
  654.         if (count >= capacity) {
  655.             return false;
  656.         }
  657.         final Node<E> l = last;
  658.         final Node<E> x = new Node<>(e, l, null);
  659.         last = x;
  660.         if (first == null) {
  661.             first = x;
  662.         } else {
  663.             l.next = x;
  664.         }
  665.         ++count;
  666.         notEmpty.signal();
  667.         return true;
  668.     }

  670.     /**
  671.      * {@inheritDoc}
  672.      */
  673.     @Override
  674.     public boolean offer(final E e) {
  675.         return offerLast(e);
  676.     }

  678.     /**
  679.      * Links the provided element as the last in the queue, waiting up to the
  680.      * specified time to do so if the queue is full.
  681.      * <p>
  682.      * This method is equivalent to {@link #offerLast(Object, long, TimeUnit)}
  683.      *
  684.      * @param e         element to link
  685.      * @param timeout   length of time to wait
  686.      * @return {@code true} if successful, otherwise {@code false}
  687.      * @throws NullPointerException if e is null
  688.      * @throws InterruptedException if the thread is interrupted whilst waiting
  689.      *         for space
  690.      */
  691.     boolean offer(final E e, final Duration timeout) throws InterruptedException {
  692.         return offerLast(e, timeout);
  693.     }

  695.     /**
  696.      * Links the provided element as the last in the queue, waiting up to the
  697.      * specified time to do so if the queue is full.
  698.      * <p>
  699.      * This method is equivalent to {@link #offerLast(Object, long, TimeUnit)}
  700.      *
  701.      * @param e         element to link
  702.      * @param timeout   length of time to wait
  703.      * @param unit      units that timeout is expressed in
  704.      * @return {@code true} if successful, otherwise {@code false}
  705.      * @throws NullPointerException if e is null
  706.      * @throws InterruptedException if the thread is interrupted whilst waiting
  707.      *         for space
  708.      */
  709.     public boolean offer(final E e, final long timeout, final TimeUnit unit) throws InterruptedException {
  710.         return offerLast(e, timeout, unit);
  711.     }

  713.     /**
  714.      * {@inheritDoc}
  715.      */
  716.     @Override
  717.     public boolean offerFirst(final E e) {
  718.         Objects.requireNonNull(e, "e");
  719.         lock.lock();
  720.         try {
  721.             return linkFirst(e);
  722.         } finally {
  723.             lock.unlock();
  724.         }
  725.     }

  727.     /**
  728.      * Links the provided element as the first in the queue, waiting up to the
  729.      * specified time to do so if the queue is full.
  730.      *
  731.      * @param e         element to link
  732.      * @param timeout   length of time to wait
  733.      * @return {@code true} if successful, otherwise {@code false}
  734.      * @throws NullPointerException if e is null
  735.      * @throws InterruptedException if the thread is interrupted whilst waiting
  736.      *         for space
  737.      */
  738.     public boolean offerFirst(final E e, final Duration timeout) throws InterruptedException {
  739.         Objects.requireNonNull(e, "e");
  740.         long nanos = timeout.toNanos();
  741.         lock.lockInterruptibly();
  742.         try {
  743.             while (!linkFirst(e)) {
  744.                 if (nanos <= 0) {
  745.                     return false;
  746.                 }
  747.                 nanos = notFull.awaitNanos(nanos);
  748.             }
  749.             return true;
  750.         } finally {
  751.             lock.unlock();
  752.         }
  753.     }

  755.     /**
  756.      * Links the provided element as the first in the queue, waiting up to the
  757.      * specified time to do so if the queue is full.
  758.      *
  759.      * @param e         element to link
  760.      * @param timeout   length of time to wait
  761.      * @param unit      units that timeout is expressed in
  762.      * @return {@code true} if successful, otherwise {@code false}
  763.      * @throws NullPointerException if e is null
  764.      * @throws InterruptedException if the thread is interrupted whilst waiting
  765.      *         for space
  766.      */
  767.     public boolean offerFirst(final E e, final long timeout, final TimeUnit unit) throws InterruptedException {
  768.         return offerFirst(e, PoolImplUtils.toDuration(timeout, unit));
  769.     }

  771.     /**
  772.      * {@inheritDoc}
  773.      */
  774.     @Override
  775.     public boolean offerLast(final E e) {
  776.         Objects.requireNonNull(e, "e");
  777.         lock.lock();
  778.         try {
  779.             return linkLast(e);
  780.         } finally {
  781.             lock.unlock();
  782.         }
  783.     }

  785.     /**
  786.      * Links the provided element as the last in the queue, waiting up to the
  787.      * specified time to do so if the queue is full.
  788.      *
  789.      * @param e         element to link
  790.      * @param timeout   length of time to wait
  791.      * @return {@code true} if successful, otherwise {@code false}
  792.      * @throws NullPointerException if e is null
  793.      * @throws InterruptedException if the thread is interrupted whist waiting
  794.      *         for space
  795.      */
  796.     boolean offerLast(final E e, final Duration timeout) throws InterruptedException {
  797.         Objects.requireNonNull(e, "e");
  798.         long nanos = timeout.toNanos();
  799.         lock.lockInterruptibly();
  800.         try {
  801.             while (!linkLast(e)) {
  802.                 if (nanos <= 0) {
  803.                     return false;
  804.                 }
  805.                 nanos = notFull.awaitNanos(nanos);
  806.             }
  807.             return true;
  808.         } finally {
  809.             lock.unlock();
  810.         }
  811.     }

  813.     /**
  814.      * Links the provided element as the last in the queue, waiting up to the
  815.      * specified time to do so if the queue is full.
  816.      *
  817.      * @param e         element to link
  818.      * @param timeout   length of time to wait
  819.      * @param unit      units that timeout is expressed in
  820.      * @return {@code true} if successful, otherwise {@code false}
  821.      * @throws NullPointerException if e is null
  822.      * @throws InterruptedException if the thread is interrupted whist waiting
  823.      *         for space
  824.      */
  825.     public boolean offerLast(final E e, final long timeout, final TimeUnit unit) throws InterruptedException {
  826.         return offerLast(e, PoolImplUtils.toDuration(timeout, unit));
  827.     }

  829.     @Override
  830.     public E peek() {
  831.         return peekFirst();
  832.     }

  834.     // BlockingQueue methods

  836.     @Override
  837.     public E peekFirst() {
  838.         lock.lock();
  839.         try {
  840.             return first == null ? null : first.item;
  841.         } finally {
  842.             lock.unlock();
  843.         }
  844.     }

  846.     @Override
  847.     public E peekLast() {
  848.         lock.lock();
  849.         try {
  850.             return last == null ? null : last.item;
  851.         } finally {
  852.             lock.unlock();
  853.         }
  854.     }

  856.     @Override
  857.     public E poll() {
  858.         return pollFirst();
  859.     }

  861.     /**
  862.      * Unlinks the first element in the queue, waiting up to the specified time
  863.      * to do so if the queue is empty.
  864.      *
  865.      * <p>This method is equivalent to {@link #pollFirst(long, TimeUnit)}.
  866.      *
  867.      * @param timeout   length of time to wait
  868.      * @return the unlinked element
  869.      * @throws InterruptedException if the current thread is interrupted
  870.      */
  871.     E poll(final Duration timeout) throws InterruptedException {
  872.         return pollFirst(timeout);
  873.     }

  875.     /**
  876.      * Unlinks the first element in the queue, waiting up to the specified time
  877.      * to do so if the queue is empty.
  878.      *
  879.      * <p>This method is equivalent to {@link #pollFirst(long, TimeUnit)}.
  880.      *
  881.      * @param timeout   length of time to wait
  882.      * @param unit      units that timeout is expressed in
  883.      * @return the unlinked element
  884.      * @throws InterruptedException if the current thread is interrupted
  885.      */
  886.     public E poll(final long timeout, final TimeUnit unit) throws InterruptedException {
  887.         return pollFirst(timeout, unit);
  888.     }

  890.     @Override
  891.     public E pollFirst() {
  892.         lock.lock();
  893.         try {
  894.             return unlinkFirst();
  895.         } finally {
  896.             lock.unlock();
  897.         }
  898.     }

  900.     /**
  901.      * Unlinks the first element in the queue, waiting up to the specified time
  902.      * to do so if the queue is empty.
  903.      *
  904.      * @param timeout   length of time to wait
  905.      * @return the unlinked element
  906.      * @throws InterruptedException if the current thread is interrupted
  907.      */
  908.     E pollFirst(final Duration timeout) throws InterruptedException {
  909.         long nanos = timeout.toNanos();
  910.         lock.lockInterruptibly();
  911.         try {
  912.             E x;
  913.             while ((x = unlinkFirst()) == null) {
  914.                 if (nanos <= 0) {
  915.                     return null;
  916.                 }
  917.                 nanos = notEmpty.awaitNanos(nanos);
  918.             }
  919.             return x;
  920.         } finally {
  921.             lock.unlock();
  922.         }
  923.     }

  925.     /**
  926.      * Unlinks the first element in the queue, waiting up to the specified time
  927.      * to do so if the queue is empty.
  928.      *
  929.      * @param timeout   length of time to wait
  930.      * @param unit      units that timeout is expressed in
  931.      * @return the unlinked element
  932.      * @throws InterruptedException if the current thread is interrupted
  933.      */
  934.     public E pollFirst(final long timeout, final TimeUnit unit) throws InterruptedException {
  935.         return pollFirst(PoolImplUtils.toDuration(timeout, unit));
  936.     }

  938.     @Override
  939.     public E pollLast() {
  940.         lock.lock();
  941.         try {
  942.             return unlinkLast();
  943.         } finally {
  944.             lock.unlock();
  945.         }
  946.     }

  948.     /**
  949.      * Unlinks the last element in the queue, waiting up to the specified time
  950.      * to do so if the queue is empty.
  951.      *
  952.      * @param timeout   length of time to wait
  953.      * @return the unlinked element
  954.      * @throws InterruptedException if the current thread is interrupted
  955.      */
  956.     public E pollLast(final Duration timeout)
  957.         throws InterruptedException {
  958.         long nanos = timeout.toNanos();
  959.         lock.lockInterruptibly();
  960.         try {
  961.             E x;
  962.             while ((x = unlinkLast()) == null) {
  963.                 if (nanos <= 0) {
  964.                     return null;
  965.                 }
  966.                 nanos = notEmpty.awaitNanos(nanos);
  967.             }
  968.             return x;
  969.         } finally {
  970.             lock.unlock();
  971.         }
  972.     }

  974.     /**
  975.      * Unlinks the last element in the queue, waiting up to the specified time
  976.      * to do so if the queue is empty.
  977.      *
  978.      * @param timeout   length of time to wait
  979.      * @param unit      units that timeout is expressed in
  980.      * @return the unlinked element
  981.      * @throws InterruptedException if the current thread is interrupted
  982.      */
  983.     public E pollLast(final long timeout, final TimeUnit unit)
  984.         throws InterruptedException {
  985.         return pollLast(PoolImplUtils.toDuration(timeout, unit));
  986.     }

  988.     /**
  989.      * {@inheritDoc}
  990.      */
  991.     @Override
  992.     public E pop() {
  993.         return removeFirst();
  994.     }

  996.     /**
  997.      * {@inheritDoc}
  998.      */
  999.     @Override
  1000.     public void push(final E e) {
  1001.         addFirst(e);
  1002.     }

  1004.     /**
  1005.      * Links the provided element as the last in the queue, waiting until there
  1006.      * is space to do so if the queue is full.
  1007.      *
  1008.      * <p>
  1009.      * This method is equivalent to {@link #putLast(Object)}.
  1010.      * </p>
  1011.      *
  1012.      * @param e element to link
  1013.      * @throws NullPointerException if e is null
  1014.      * @throws InterruptedException if the thread is interrupted whilst waiting
  1015.      *         for space
  1016.      */
  1017.     public void put(final E e) throws InterruptedException {
  1018.         putLast(e);
  1019.     }

  1021.     /**
  1022.      * Links the provided element as the first in the queue, waiting until there
  1023.      * is space to do so if the queue is full.
  1024.      *
  1025.      * @param e element to link
  1026.      * @throws NullPointerException if e is null
  1027.      * @throws InterruptedException if the thread is interrupted whilst waiting
  1028.      *         for space
  1029.      */
  1030.     public void putFirst(final E e) throws InterruptedException {
  1031.         Objects.requireNonNull(e, "e");
  1032.         lock.lock();
  1033.         try {
  1034.             while (!linkFirst(e)) {
  1035.                 notFull.await();
  1036.             }
  1037.         } finally {
  1038.             lock.unlock();
  1039.         }
  1040.     }

  1042.     /**
  1043.      * Links the provided element as the last in the queue, waiting until there
  1044.      * is space to do so if the queue is full.
  1045.      *
  1046.      * @param e element to link
  1047.      * @throws NullPointerException if e is null
  1048.      * @throws InterruptedException if the thread is interrupted whilst waiting
  1049.      *         for space
  1050.      */
  1051.     public void putLast(final E e) throws InterruptedException {
  1052.         Objects.requireNonNull(e, "e");
  1053.         lock.lock();
  1054.         try {
  1055.             while (!linkLast(e)) {
  1056.                 notFull.await();
  1057.             }
  1058.         } finally {
  1059.             lock.unlock();
  1060.         }
  1061.     }

  1063.     // Stack methods

  1065.     /**
  1066.      * Reconstitutes this deque from a stream (that is,
  1067.      * deserialize it).
  1068.      * @param s the stream
  1069.      */
  1070.     private void readObject(final ObjectInputStream s)
  1071.         throws IOException, ClassNotFoundException {
  1072.         s.defaultReadObject();
  1073.         count = 0;
  1074.         first = null;
  1075.         last = null;
  1076.         // Read in all elements and place in queue
  1077.         for (;;) {
  1078.             @SuppressWarnings("unchecked")
  1079.             final E item = (E)s.readObject();
  1080.             if (item == null) {
  1081.                 break;
  1082.             }
  1083.             add(item);
  1084.         }
  1085.     }

  1087.     /**
  1088.      * Returns the number of additional elements that this deque can ideally
  1089.      * (in the absence of memory or resource constraints) accept without
  1090.      * blocking. This is always equal to the initial capacity of this deque
  1091.      * less the current {@code size} of this deque.
  1092.      *
  1093.      * <p>
  1094.      * Note that you <em>cannot</em> always tell if an attempt to insert
  1095.      * an element will succeed by inspecting {@code remainingCapacity}
  1096.      * because it may be the case that another thread is about to
  1097.      * insert or remove an element.
  1098.      * </p>
  1099.      *
  1100.      * @return The number of additional elements the queue is able to accept
  1101.      */
  1102.     public int remainingCapacity() {
  1103.         lock.lock();
  1104.         try {
  1105.             return capacity - count;
  1106.         } finally {
  1107.             lock.unlock();
  1108.         }
  1109.     }

  1111.     // Collection methods

  1113.     /**
  1114.      * Retrieves and removes the head of the queue represented by this deque.
  1115.      * This method differs from {@link #poll poll} only in that it throws an
  1116.      * exception if this deque is empty.
  1117.      *
  1118.      * <p>
  1119.      * This method is equivalent to {@link #removeFirst() removeFirst}.
  1120.      * </p>
  1121.      *
  1122.      * @return the head of the queue represented by this deque
  1123.      * @throws NoSuchElementException if this deque is empty
  1124.      */
  1125.     @Override
  1126.     public E remove() {
  1127.         return removeFirst();
  1128.     }

  1130.     /**
  1131.      * Removes the first occurrence of the specified element from this deque.
  1132.      * If the deque does not contain the element, it is unchanged.
  1133.      * More formally, removes the first element {@code e} such that
  1134.      * {@code o.equals(e)} (if such an element exists).
  1135.      * Returns {@code true} if this deque contained the specified element
  1136.      * (or equivalently, if this deque changed as a result of the call).
  1137.      *
  1138.      * <p>
  1139.      * This method is equivalent to
  1140.      * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}.
  1141.      * </p>
  1142.      *
  1143.      * @param o element to be removed from this deque, if present
  1144.      * @return {@code true} if this deque changed as a result of the call
  1145.      */
  1146.     @Override
  1147.     public boolean remove(final Object o) {
  1148.         return removeFirstOccurrence(o);
  1149.     }

  1151.     /**
  1152.      * {@inheritDoc}
  1153.      */
  1154.     @Override
  1155.     public E removeFirst() {
  1156.         final E x = pollFirst();
  1157.         if (x == null) {
  1158.             throw new NoSuchElementException();
  1159.         }
  1160.         return x;
  1161.     }

  1163.     /*
  1164.      * TODO: Add support for more efficient bulk operations.
  1165.      *
  1166.      * We don't want to acquire the lock for every iteration, but we
  1167.      * also want other threads a chance to interact with the
  1168.      * collection, especially when count is close to capacity.
  1169.      */

  1171. //     /**
  1172. //      * Adds all of the elements in the specified collection to this
  1173. //      * queue.  Attempts to addAll of a queue to itself result in
  1174. //      * {@code IllegalArgumentException}. Further, the behavior of
  1175. //      * this operation is undefined if the specified collection is
  1176. //      * modified while the operation is in progress.
  1177. //      *
  1178. //      * @param c collection containing elements to be added to this queue
  1179. //      * @return {@code true} if this queue changed as a result of the call
  1180. //      * @throws ClassCastException
  1181. //      * @throws NullPointerException
  1182. //      * @throws IllegalArgumentException
  1183. //      * @throws IllegalStateException
  1184. //      * @see #add(Object)
  1185. //      */
  1186. //     public boolean addAll(Collection<? extends E> c) {
  1187. //         if (c == null)
  1188. //             throw new NullPointerException();
  1189. //         if (c == this)
  1190. //             throw new IllegalArgumentException();
  1191. //         final ReentrantLock lock = this.lock;
  1192. //         lock.lock();
  1193. //         try {
  1194. //             boolean modified = false;
  1195. //             for (E e : c)
  1196. //                 if (linkLast(e))
  1197. //                     modified = true;
  1198. //             return modified;
  1199. //         } finally {
  1200. //             lock.unlock();
  1201. //         }
  1202. //     }

  1204.     @Override
  1205.     public boolean removeFirstOccurrence(final Object o) {
  1206.         if (o == null) {
  1207.             return false;
  1208.         }
  1209.         lock.lock();
  1210.         try {
  1211.             for (Node<E> p = first; p != null; p = p.next) {
  1212.                 if (o.equals(p.item)) {
  1213.                     unlink(p);
  1214.                     return true;
  1215.                 }
  1216.             }
  1217.             return false;
  1218.         } finally {
  1219.             lock.unlock();
  1220.         }
  1221.     }

  1223.     /**
  1224.      * {@inheritDoc}
  1225.      */
  1226.     @Override
  1227.     public E removeLast() {
  1228.         final E x = pollLast();
  1229.         if (x == null) {
  1230.             throw new NoSuchElementException();
  1231.         }
  1232.         return x;
  1233.     }

  1235.     @Override
  1236.     public boolean removeLastOccurrence(final Object o) {
  1237.         if (o == null) {
  1238.             return false;
  1239.         }
  1240.         lock.lock();
  1241.         try {
  1242.             for (Node<E> p = last; p != null; p = p.prev) {
  1243.                 if (o.equals(p.item)) {
  1244.                     unlink(p);
  1245.                     return true;
  1246.                 }
  1247.             }
  1248.             return false;
  1249.         } finally {
  1250.             lock.unlock();
  1251.         }
  1252.     }

  1254.     /**
  1255.      * Returns the number of elements in this deque.
  1256.      *
  1257.      * @return the number of elements in this deque
  1258.      */
  1259.     @Override
  1260.     public int size() {
  1261.         lock.lock();
  1262.         try {
  1263.             return count;
  1264.         } finally {
  1265.             lock.unlock();
  1266.         }
  1267.     }

  1269.     /**
  1270.      * Unlinks the first element in the queue, waiting until there is an element
  1271.      * to unlink if the queue is empty.
  1272.      *
  1273.      * <p>
  1274.      * This method is equivalent to {@link #takeFirst()}.
  1275.      * </p>
  1276.      *
  1277.      * @return the unlinked element
  1278.      * @throws InterruptedException if the current thread is interrupted
  1279.      */
  1280.     public E take() throws InterruptedException {
  1281.         return takeFirst();
  1282.     }

  1284.     /**
  1285.      * Unlinks the first element in the queue, waiting until there is an element
  1286.      * to unlink if the queue is empty.
  1287.      *
  1288.      * @return the unlinked element
  1289.      * @throws InterruptedException if the current thread is interrupted
  1290.      */
  1291.     public E takeFirst() throws InterruptedException {
  1292.         lock.lock();
  1293.         try {
  1294.             E x;
  1295.             while ((x = unlinkFirst()) == null) {
  1296.                 notEmpty.await();
  1297.             }
  1298.             return x;
  1299.         } finally {
  1300.             lock.unlock();
  1301.         }
  1302.     }

  1304.     /**
  1305.      * Unlinks the last element in the queue, waiting until there is an element
  1306.      * to unlink if the queue is empty.
  1307.      *
  1308.      * @return the unlinked element
  1309.      * @throws InterruptedException if the current thread is interrupted
  1310.      */
  1311.     public E takeLast() throws InterruptedException {
  1312.         lock.lock();
  1313.         try {
  1314.             E x;
  1315.             while ((x = unlinkLast()) == null) {
  1316.                 notEmpty.await();
  1317.             }
  1318.             return x;
  1319.         } finally {
  1320.             lock.unlock();
  1321.         }
  1322.     }

  1324.     /**
  1325.      * Returns an array containing all of the elements in this deque, in
  1326.      * proper sequence (from first to last element).
  1327.      *
  1328.      * <p>
  1329.      * The returned array will be "safe" in that no references to it are
  1330.      * maintained by this deque.  (In other words, this method must allocate
  1331.      * a new array).  The caller is thus free to modify the returned array.
  1332.      * </p>
  1333.      * <p>
  1334.      * This method acts as bridge between array-based and collection-based
  1335.      * APIs.
  1336.      * </p>
  1337.      *
  1338.      * @return an array containing all of the elements in this deque
  1339.      */
  1340.     @Override
  1341.     public Object[] toArray() {
  1342.         lock.lock();
  1343.         try {
  1344.             final Object[] a = new Object[count];
  1345.             int k = 0;
  1346.             for (Node<E> p = first; p != null; p = p.next) {
  1347.                 a[k++] = p.item;
  1348.             }
  1349.             return a;
  1350.         } finally {
  1351.             lock.unlock();
  1352.         }
  1353.     }

  1355.     /**
  1356.      * {@inheritDoc}
  1357.      */
  1358.     @SuppressWarnings("unchecked")
  1359.     @Override
  1360.     public <T> T[] toArray(T[] a) {
  1361.         lock.lock();
  1362.         try {
  1363.             if (a.length < count) {
  1364.                 a = (T[])java.lang.reflect.Array.newInstance
  1365.                     (a.getClass().getComponentType(), count);
  1366.             }
  1367.             int k = 0;
  1368.             for (Node<E> p = first; p != null; p = p.next) {
  1369.                 a[k++] = (T)p.item;
  1370.             }
  1371.             if (a.length > k) {
  1372.                 a[k] = null;
  1373.             }
  1374.             return a;
  1375.         } finally {
  1376.             lock.unlock();
  1377.         }
  1378.     }

  1380.     @Override
  1381.     public String toString() {
  1382.         lock.lock();
  1383.         try {
  1384.             return super.toString();
  1385.         } finally {
  1386.             lock.unlock();
  1387.         }
  1388.     }

  1390.     /**
  1391.      * Unlinks the provided node.
  1392.      *
  1393.      * @param x The node to unlink
  1394.      */
  1395.     private void unlink(final Node<E> x) {
  1396.         // assert lock.isHeldByCurrentThread();
  1397.         final Node<E> p = x.prev;
  1398.         final Node<E> n = x.next;
  1399.         if (p == null) {
  1400.             unlinkFirst();
  1401.         } else if (n == null) {
  1402.             unlinkLast();
  1403.         } else {
  1404.             p.next = n;
  1405.             n.prev = p;
  1406.             x.item = null;
  1407.             // Don't mess with x's links.  They may still be in use by
  1408.             // an iterator.
  1409.         --count;
  1410.             notFull.signal();
  1411.         }
  1412.     }

  1414.     // Monitoring methods

  1416.     /**
  1417.      * Removes and returns the first element, or null if empty.
  1418.      *
  1419.      * @return The first element or {@code null} if empty
  1420.      */
  1421.     private E unlinkFirst() {
  1422.         // assert lock.isHeldByCurrentThread();
  1423.         final Node<E> f = first;
  1424.         if (f == null) {
  1425.             return null;
  1426.         }
  1427.         final Node<E> n = f.next;
  1428.         final E item = f.item;
  1429.         f.item = null;
  1430.         f.next = f; // help GC
  1431.         first = n;
  1432.         if (n == null) {
  1433.             last = null;
  1434.         } else {
  1435.             n.prev = null;
  1436.         }
  1437.         --count;
  1438.         notFull.signal();
  1439.         return item;
  1440.     }

  1442.     /**
  1443.      * Removes and returns the last element, or null if empty.
  1444.      *
  1445.      * @return The first element or {@code null} if empty
  1446.      */
  1447.     private E unlinkLast() {
  1448.         // assert lock.isHeldByCurrentThread();
  1449.         final Node<E> l = last;
  1450.         if (l == null) {
  1451.             return null;
  1452.         }
  1453.         final Node<E> p = l.prev;
  1454.         final E item = l.item;
  1455.         l.item = null;
  1456.         l.prev = l; // help GC
  1457.         last = p;
  1458.         if (p == null) {
  1459.             first = null;
  1460.         } else {
  1461.             p.next = null;
  1462.         }
  1463.         --count;
  1464.         notFull.signal();
  1465.         return item;
  1466.     }

  1468.     /**
  1469.      * Saves the state of this deque to a stream (that is, serialize it).
  1470.      *
  1471.      * @serialData The capacity (int), followed by elements (each an
  1472.      * {@code Object}) in the proper order, followed by a null
  1473.      * @param s the stream
  1474.      * @throws  IOException if I/O errors occur while writing to the underlying {@code OutputStream}
  1475.      */
  1476.     private void writeObject(final java.io.ObjectOutputStream s) throws IOException {
  1477.         lock.lock();
  1478.         try {
  1479.             // Write out capacity and any hidden stuff
  1480.             s.defaultWriteObject();
  1481.             // Write out all elements in the proper order.
  1482.             for (Node<E> p = first; p != null; p = p.next) {
  1483.                 s.writeObject(p.item);
  1484.             }
  1485.             // Use trailing null as sentinel
  1486.             s.writeObject(null);
  1487.         } finally {
  1488.             lock.unlock();
  1489.         }
  1490.     }
  1491. }
Created with JaCoCo 0.8.12.202403310830