src/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java

Print this page

        

*** 36,46 **** package java.util.concurrent; import java.util.AbstractCollection; import java.util.ArrayList; import java.util.Collection; - import java.util.ConcurrentModificationException; import java.util.Deque; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Queue; --- 36,45 ----
*** 210,220 **** * are occasionally broken. * * The actual representation we use is that p.next == p means to * goto the first node (which in turn is reached by following prev * pointers from head), and p.next == null && p.prev == p means ! * that the iteration is at an end and that p is a (final static) * dummy node, NEXT_TERMINATOR, and not the last active node. * Finishing the iteration when encountering such a TERMINATOR is * good enough for read-only traversals, so such traversals can use * p.next == null as the termination condition. When we need to * find the last (active) node, for enqueueing a new node, we need --- 209,219 ---- * are occasionally broken. * * The actual representation we use is that p.next == p means to * goto the first node (which in turn is reached by following prev * pointers from head), and p.next == null && p.prev == p means ! * that the iteration is at an end and that p is a (static final) * dummy node, NEXT_TERMINATOR, and not the last active node. * Finishing the iteration when encountering such a TERMINATOR is * good enough for read-only traversals, so such traversals can use * p.next == null as the termination condition. When we need to * find the last (active) node, for enqueueing a new node, we need
*** 269,279 **** * - tail.item may or may not be null * - tail may not be reachable from the first or last node, or from head */ private transient volatile Node<E> tail; ! private final static Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR; static { PREV_TERMINATOR = new Node<Object>(null); PREV_TERMINATOR.next = PREV_TERMINATOR; NEXT_TERMINATOR = new Node<Object>(null); --- 268,278 ---- * - tail.item may or may not be null * - tail may not be reachable from the first or last node, or from head */ private transient volatile Node<E> tail; ! private static final Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR; static { PREV_TERMINATOR = new Node<Object>(null); PREV_TERMINATOR.next = PREV_TERMINATOR; NEXT_TERMINATOR = new Node<Object>(null);
*** 399,409 **** // Lost CAS race to another thread; re-read next } } } ! private final static int HOPS = 2; /** * Unlinks non-null node x. */ void unlink(Node<E> x) { --- 398,408 ---- // Lost CAS race to another thread; re-read next } } } ! private static final int HOPS = 2; /** * Unlinks non-null node x. */ void unlink(Node<E> x) {
*** 868,913 **** tail = t; } /** * Inserts the specified element at the front of this deque. * ! * @throws NullPointerException {@inheritDoc} */ public void addFirst(E e) { linkFirst(e); } /** * Inserts the specified element at the end of this deque. * * <p>This method is equivalent to {@link #add}. * ! * @throws NullPointerException {@inheritDoc} */ public void addLast(E e) { linkLast(e); } /** * Inserts the specified element at the front of this deque. * ! * @return {@code true} always ! * @throws NullPointerException {@inheritDoc} */ public boolean offerFirst(E e) { linkFirst(e); return true; } /** * Inserts the specified element at the end of this deque. * * <p>This method is equivalent to {@link #add}. * ! * @return {@code true} always ! * @throws NullPointerException {@inheritDoc} */ public boolean offerLast(E e) { linkLast(e); return true; } --- 867,918 ---- tail = t; } /** * Inserts the specified element at the front of this deque. + * As the deque is unbounded, this method will never throw + * {@link IllegalStateException}. * ! * @throws NullPointerException if the specified element is null */ public void addFirst(E e) { linkFirst(e); } /** * Inserts the specified element at the end of this deque. + * As the deque is unbounded, this method will never throw + * {@link IllegalStateException}. * * <p>This method is equivalent to {@link #add}. * ! * @throws NullPointerException if the specified element is null */ public void addLast(E e) { linkLast(e); } /** * Inserts the specified element at the front of this deque. + * As the deque is unbounded, this method will never return {@code false}. * ! * @return {@code true} (as specified by {@link Deque#offerFirst}) ! * @throws NullPointerException if the specified element is null */ public boolean offerFirst(E e) { linkFirst(e); return true; } /** * Inserts the specified element at the end of this deque. + * As the deque is unbounded, this method will never return {@code false}. * * <p>This method is equivalent to {@link #add}. * ! * @return {@code true} (as specified by {@link Deque#offerLast}) ! * @throws NullPointerException if the specified element is null */ public boolean offerLast(E e) { linkLast(e); return true; }
*** 982,991 **** --- 987,997 ---- // *** Queue and stack methods *** /** * Inserts the specified element at the tail of this deque. + * As the deque is unbounded, this method will never return {@code false}. * * @return {@code true} (as specified by {@link Queue#offer}) * @throws NullPointerException if the specified element is null */ public boolean offer(E e) {
*** 992,1001 **** --- 998,1009 ---- return offerLast(e); } /** * Inserts the specified element at the tail of this deque. + * As the deque is unbounded, this method will never throw + * {@link IllegalStateException} or return {@code false}. * * @return {@code true} (as specified by {@link Collection#add}) * @throws NullPointerException if the specified element is null */ public boolean add(E e) {
*** 1014,1024 **** * {@code o.equals(e)}, if such an element exists in this deque. * If the deque does not contain the element, it is unchanged. * * @param o element to be removed from this deque, if present * @return {@code true} if the deque contained the specified element ! * @throws NullPointerException if the specified element is {@code null} */ public boolean removeFirstOccurrence(Object o) { checkNotNull(o); for (Node<E> p = first(); p != null; p = succ(p)) { E item = p.item; --- 1022,1032 ---- * {@code o.equals(e)}, if such an element exists in this deque. * If the deque does not contain the element, it is unchanged. * * @param o element to be removed from this deque, if present * @return {@code true} if the deque contained the specified element ! * @throws NullPointerException if the specified element is null */ public boolean removeFirstOccurrence(Object o) { checkNotNull(o); for (Node<E> p = first(); p != null; p = succ(p)) { E item = p.item;
*** 1035,1045 **** * {@code o.equals(e)}, if such an element exists in this deque. * If the deque does not contain the element, it is unchanged. * * @param o element to be removed from this deque, if present * @return {@code true} if the deque contained the specified element ! * @throws NullPointerException if the specified element is {@code null} */ public boolean removeLastOccurrence(Object o) { checkNotNull(o); for (Node<E> p = last(); p != null; p = pred(p)) { E item = p.item; --- 1043,1053 ---- * {@code o.equals(e)}, if such an element exists in this deque. * If the deque does not contain the element, it is unchanged. * * @param o element to be removed from this deque, if present * @return {@code true} if the deque contained the specified element ! * @throws NullPointerException if the specified element is null */ public boolean removeLastOccurrence(Object o) { checkNotNull(o); for (Node<E> p = last(); p != null; p = pred(p)) { E item = p.item;
*** 1108,1118 **** * {@code o.equals(e)}, if such an element exists in this deque. * If the deque does not contain the element, it is unchanged. * * @param o element to be removed from this deque, if present * @return {@code true} if the deque contained the specified element ! * @throws NullPointerException if the specified element is {@code null} */ public boolean remove(Object o) { return removeFirstOccurrence(o); } --- 1116,1126 ---- * {@code o.equals(e)}, if such an element exists in this deque. * If the deque does not contain the element, it is unchanged. * * @param o element to be removed from this deque, if present * @return {@code true} if the deque contained the specified element ! * @throws NullPointerException if the specified element is null */ public boolean remove(Object o) { return removeFirstOccurrence(o); }
*** 1163,1173 **** else { // p is last node beginningOfTheEnd.lazySetPrev(p); // CAS piggyback if (p.casNext(null, beginningOfTheEnd)) { // Successful CAS is the linearization point ! // for all elements to be added to this queue. if (!casTail(t, last)) { // Try a little harder to update tail, // since we may be adding many elements. t = tail; if (last.next == null) --- 1171,1181 ---- else { // p is last node beginningOfTheEnd.lazySetPrev(p); // CAS piggyback if (p.casNext(null, beginningOfTheEnd)) { // Successful CAS is the linearization point ! // for all elements to be added to this deque. if (!casTail(t, last)) { // Try a little harder to update tail, // since we may be adding many elements. t = tail; if (last.next == null)
*** 1249,1264 **** /** * Returns an iterator over the elements in this deque 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 * 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. * * @return an iterator over the elements in this deque in proper sequence */ public Iterator<E> iterator() { return new Itr(); --- 1257,1272 ---- /** * Returns an iterator over the elements in this deque in proper sequence. * The elements will be returned in order from first (head) to last (tail). * ! * <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. * * @return an iterator over the elements in this deque in proper sequence */ public Iterator<E> iterator() { return new Itr();
*** 1267,1282 **** /** * Returns an iterator over the elements in this deque in reverse * sequential order. The elements will be returned in order from * last (tail) to first (head). * ! * <p>The returned {@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. * * @return an iterator over the elements in this deque in reverse order */ public Iterator<E> descendingIterator() { return new DescendingItr(); --- 1275,1290 ---- /** * Returns an iterator over the elements in this deque in reverse * sequential order. The elements will be returned in order from * last (tail) to first (head). * ! * <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. * * @return an iterator over the elements in this deque in reverse order */ public Iterator<E> descendingIterator() { return new DescendingItr();