Print this page


Split Close
Expand all
Collapse all
          --- old/src/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java
          +++ new/src/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java
↓ open down ↓ 30 lines elided ↑ open up ↑
  31   31   * Written by Doug Lea and Martin Buchholz with assistance from members of
  32   32   * JCP JSR-166 Expert Group and released to the public domain, as explained
  33   33   * at http://creativecommons.org/licenses/publicdomain
  34   34   */
  35   35  
  36   36  package java.util.concurrent;
  37   37  
  38   38  import java.util.AbstractCollection;
  39   39  import java.util.ArrayList;
  40   40  import java.util.Collection;
  41      -import java.util.ConcurrentModificationException;
  42   41  import java.util.Deque;
  43   42  import java.util.Iterator;
  44   43  import java.util.NoSuchElementException;
  45   44  import java.util.Queue;
  46   45  
  47   46  /**
  48   47   * An unbounded concurrent {@linkplain Deque deque} based on linked nodes.
  49   48   * Concurrent insertion, removal, and access operations execute safely
  50   49   * across multiple threads.
  51   50   * A {@code ConcurrentLinkedDeque} is an appropriate choice when
↓ open down ↓ 153 lines elided ↑ open up ↑
 205  204       * frequency (eagerness) of these operations.  Since volatile
 206  205       * reads are likely to be much cheaper than CASes, saving CASes by
 207  206       * unlinking multiple adjacent nodes at a time may be a win.
 208  207       * gc-unlinking can be performed rarely and still be effective,
 209  208       * since it is most important that long chains of deleted nodes
 210  209       * are occasionally broken.
 211  210       *
 212  211       * The actual representation we use is that p.next == p means to
 213  212       * goto the first node (which in turn is reached by following prev
 214  213       * pointers from head), and p.next == null && p.prev == p means
 215      -     * that the iteration is at an end and that p is a (final static)
      214 +     * that the iteration is at an end and that p is a (static final)
 216  215       * dummy node, NEXT_TERMINATOR, and not the last active node.
 217  216       * Finishing the iteration when encountering such a TERMINATOR is
 218  217       * good enough for read-only traversals, so such traversals can use
 219  218       * p.next == null as the termination condition.  When we need to
 220  219       * find the last (active) node, for enqueueing a new node, we need
 221  220       * to check whether we have reached a TERMINATOR node; if so,
 222  221       * restart traversal from tail.
 223  222       *
 224  223       * The implementation is completely directionally symmetrical,
 225  224       * except that most public methods that iterate through the list
↓ open down ↓ 38 lines elided ↑ open up ↑
 264  263       * - the last node is always O(1) reachable from tail via next links
 265  264       * - all live nodes are reachable from the last node via pred()
 266  265       * - tail != null
 267  266       * - tail is never gc-unlinked (but may be unlinked)
 268  267       * Non-invariants:
 269  268       * - tail.item may or may not be null
 270  269       * - tail may not be reachable from the first or last node, or from head
 271  270       */
 272  271      private transient volatile Node<E> tail;
 273  272  
 274      -    private final static Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR;
      273 +    private static final Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR;
 275  274  
 276  275      static {
 277  276          PREV_TERMINATOR = new Node<Object>(null);
 278  277          PREV_TERMINATOR.next = PREV_TERMINATOR;
 279  278          NEXT_TERMINATOR = new Node<Object>(null);
 280  279          NEXT_TERMINATOR.prev = NEXT_TERMINATOR;
 281  280      }
 282  281  
 283  282      @SuppressWarnings("unchecked")
 284  283      Node<E> prevTerminator() {
↓ open down ↓ 109 lines elided ↑ open up ↑
 394  393                          // and for newNode to become "live".
 395  394                          if (p != t) // hop two nodes at a time
 396  395                              casTail(t, newNode);  // Failure is OK.
 397  396                          return;
 398  397                      }
 399  398                      // Lost CAS race to another thread; re-read next
 400  399                  }
 401  400              }
 402  401      }
 403  402  
 404      -    private final static int HOPS = 2;
      403 +    private static final int HOPS = 2;
 405  404  
 406  405      /**
 407  406       * Unlinks non-null node x.
 408  407       */
 409  408      void unlink(Node<E> x) {
 410  409          // assert x != null;
 411  410          // assert x.item == null;
 412  411          // assert x != PREV_TERMINATOR;
 413  412          // assert x != NEXT_TERMINATOR;
 414  413  
↓ open down ↓ 448 lines elided ↑ open up ↑
 863  862                  newNode.lazySetPrev(t);
 864  863                  t = newNode;
 865  864              }
 866  865          }
 867  866          head = h;
 868  867          tail = t;
 869  868      }
 870  869  
 871  870      /**
 872  871       * Inserts the specified element at the front of this deque.
      872 +     * As the deque is unbounded, this method will never throw
      873 +     * {@link IllegalStateException}.
 873  874       *
 874      -     * @throws NullPointerException {@inheritDoc}
      875 +     * @throws NullPointerException if the specified element is null
 875  876       */
 876  877      public void addFirst(E e) {
 877  878          linkFirst(e);
 878  879      }
 879  880  
 880  881      /**
 881  882       * Inserts the specified element at the end of this deque.
      883 +     * As the deque is unbounded, this method will never throw
      884 +     * {@link IllegalStateException}.
 882  885       *
 883  886       * <p>This method is equivalent to {@link #add}.
 884  887       *
 885      -     * @throws NullPointerException {@inheritDoc}
      888 +     * @throws NullPointerException if the specified element is null
 886  889       */
 887  890      public void addLast(E e) {
 888  891          linkLast(e);
 889  892      }
 890  893  
 891  894      /**
 892  895       * Inserts the specified element at the front of this deque.
      896 +     * As the deque is unbounded, this method will never return {@code false}.
 893  897       *
 894      -     * @return {@code true} always
 895      -     * @throws NullPointerException {@inheritDoc}
      898 +     * @return {@code true} (as specified by {@link Deque#offerFirst})
      899 +     * @throws NullPointerException if the specified element is null
 896  900       */
 897  901      public boolean offerFirst(E e) {
 898  902          linkFirst(e);
 899  903          return true;
 900  904      }
 901  905  
 902  906      /**
 903  907       * Inserts the specified element at the end of this deque.
      908 +     * As the deque is unbounded, this method will never return {@code false}.
 904  909       *
 905  910       * <p>This method is equivalent to {@link #add}.
 906  911       *
 907      -     * @return {@code true} always
 908      -     * @throws NullPointerException {@inheritDoc}
      912 +     * @return {@code true} (as specified by {@link Deque#offerLast})
      913 +     * @throws NullPointerException if the specified element is null
 909  914       */
 910  915      public boolean offerLast(E e) {
 911  916          linkLast(e);
 912  917          return true;
 913  918      }
 914  919  
 915  920      public E peekFirst() {
 916  921          for (Node<E> p = first(); p != null; p = succ(p)) {
 917  922              E item = p.item;
 918  923              if (item != null)
↓ open down ↓ 14 lines elided ↑ open up ↑
 933  938      /**
 934  939       * @throws NoSuchElementException {@inheritDoc}
 935  940       */
 936  941      public E getFirst() {
 937  942          return screenNullResult(peekFirst());
 938  943      }
 939  944  
 940  945      /**
 941  946       * @throws NoSuchElementException {@inheritDoc}
 942  947       */
 943      -    public E getLast()  {
      948 +    public E getLast() {
 944  949          return screenNullResult(peekLast());
 945  950      }
 946  951  
 947  952      public E pollFirst() {
 948  953          for (Node<E> p = first(); p != null; p = succ(p)) {
 949  954              E item = p.item;
 950  955              if (item != null && p.casItem(item, null)) {
 951  956                  unlink(p);
 952  957                  return item;
 953  958              }
↓ open down ↓ 23 lines elided ↑ open up ↑
 977  982       * @throws NoSuchElementException {@inheritDoc}
 978  983       */
 979  984      public E removeLast() {
 980  985          return screenNullResult(pollLast());
 981  986      }
 982  987  
 983  988      // *** Queue and stack methods ***
 984  989  
 985  990      /**
 986  991       * Inserts the specified element at the tail of this deque.
      992 +     * As the deque is unbounded, this method will never return {@code false}.
 987  993       *
 988  994       * @return {@code true} (as specified by {@link Queue#offer})
 989  995       * @throws NullPointerException if the specified element is null
 990  996       */
 991  997      public boolean offer(E e) {
 992  998          return offerLast(e);
 993  999      }
 994 1000  
 995 1001      /**
 996 1002       * Inserts the specified element at the tail of this deque.
     1003 +     * As the deque is unbounded, this method will never throw
     1004 +     * {@link IllegalStateException} or return {@code false}.
 997 1005       *
 998 1006       * @return {@code true} (as specified by {@link Collection#add})
 999 1007       * @throws NullPointerException if the specified element is null
1000 1008       */
1001 1009      public boolean add(E e) {
1002 1010          return offerLast(e);
1003 1011      }
1004 1012  
1005 1013      public E poll()           { return pollFirst(); }
1006 1014      public E remove()         { return removeFirst(); }
↓ open down ↓ 2 lines elided ↑ open up ↑
1009 1017      public void push(E e)     { addFirst(e); }
1010 1018      public E pop()            { return removeFirst(); }
1011 1019  
1012 1020      /**
1013 1021       * Removes the first element {@code e} such that
1014 1022       * {@code o.equals(e)}, if such an element exists in this deque.
1015 1023       * If the deque does not contain the element, it is unchanged.
1016 1024       *
1017 1025       * @param o element to be removed from this deque, if present
1018 1026       * @return {@code true} if the deque contained the specified element
1019      -     * @throws NullPointerException if the specified element is {@code null}
     1027 +     * @throws NullPointerException if the specified element is null
1020 1028       */
1021 1029      public boolean removeFirstOccurrence(Object o) {
1022 1030          checkNotNull(o);
1023 1031          for (Node<E> p = first(); p != null; p = succ(p)) {
1024 1032              E item = p.item;
1025 1033              if (item != null && o.equals(item) && p.casItem(item, null)) {
1026 1034                  unlink(p);
1027 1035                  return true;
1028 1036              }
1029 1037          }
1030 1038          return false;
1031 1039      }
1032 1040  
1033 1041      /**
1034 1042       * Removes the last element {@code e} such that
1035 1043       * {@code o.equals(e)}, if such an element exists in this deque.
1036 1044       * If the deque does not contain the element, it is unchanged.
1037 1045       *
1038 1046       * @param o element to be removed from this deque, if present
1039 1047       * @return {@code true} if the deque contained the specified element
1040      -     * @throws NullPointerException if the specified element is {@code null}
     1048 +     * @throws NullPointerException if the specified element is null
1041 1049       */
1042 1050      public boolean removeLastOccurrence(Object o) {
1043 1051          checkNotNull(o);
1044 1052          for (Node<E> p = last(); p != null; p = pred(p)) {
1045 1053              E item = p.item;
1046 1054              if (item != null && o.equals(item) && p.casItem(item, null)) {
1047 1055                  unlink(p);
1048 1056                  return true;
1049 1057              }
1050 1058          }
↓ open down ↓ 52 lines elided ↑ open up ↑
1103 1111          return count;
1104 1112      }
1105 1113  
1106 1114      /**
1107 1115       * Removes the first element {@code e} such that
1108 1116       * {@code o.equals(e)}, if such an element exists in this deque.
1109 1117       * If the deque does not contain the element, it is unchanged.
1110 1118       *
1111 1119       * @param o element to be removed from this deque, if present
1112 1120       * @return {@code true} if the deque contained the specified element
1113      -     * @throws NullPointerException if the specified element is {@code null}
     1121 +     * @throws NullPointerException if the specified element is null
1114 1122       */
1115 1123      public boolean remove(Object o) {
1116 1124          return removeFirstOccurrence(o);
1117 1125      }
1118 1126  
1119 1127      /**
1120 1128       * Appends all of the elements in the specified collection to the end of
1121 1129       * this deque, in the order that they are returned by the specified
1122 1130       * collection's iterator.  Attempts to {@code addAll} of a deque to
1123 1131       * itself result in {@code IllegalArgumentException}.
↓ open down ↓ 34 lines elided ↑ open up ↑
1158 1166                      // Check for tail updates every other hop.
1159 1167                      // If p == q, we are sure to follow tail instead.
1160 1168                      p = (t != (t = tail)) ? t : q;
1161 1169                  else if (p.prev == p) // NEXT_TERMINATOR
1162 1170                      continue restartFromTail;
1163 1171                  else {
1164 1172                      // p is last node
1165 1173                      beginningOfTheEnd.lazySetPrev(p); // CAS piggyback
1166 1174                      if (p.casNext(null, beginningOfTheEnd)) {
1167 1175                          // Successful CAS is the linearization point
1168      -                        // for all elements to be added to this queue.
     1176 +                        // for all elements to be added to this deque.
1169 1177                          if (!casTail(t, last)) {
1170 1178                              // Try a little harder to update tail,
1171 1179                              // since we may be adding many elements.
1172 1180                              t = tail;
1173 1181                              if (last.next == null)
1174 1182                                  casTail(t, last);
1175 1183                          }
1176 1184                          return true;
1177 1185                      }
1178 1186                      // Lost CAS race to another thread; re-read next
↓ open down ↓ 65 lines elided ↑ open up ↑
1244 1252       * @throws NullPointerException if the specified array is null
1245 1253       */
1246 1254      public <T> T[] toArray(T[] a) {
1247 1255          return toArrayList().toArray(a);
1248 1256      }
1249 1257  
1250 1258      /**
1251 1259       * Returns an iterator over the elements in this deque in proper sequence.
1252 1260       * The elements will be returned in order from first (head) to last (tail).
1253 1261       *
1254      -     * <p>The returned {@code Iterator} is a "weakly consistent" iterator that
     1262 +     * <p>The returned iterator is a "weakly consistent" iterator that
1255 1263       * will never throw {@link java.util.ConcurrentModificationException
1256      -     * ConcurrentModificationException},
1257      -     * and guarantees to traverse elements as they existed upon
1258      -     * construction of the iterator, and may (but is not guaranteed to)
1259      -     * reflect any modifications subsequent to construction.
     1264 +     * ConcurrentModificationException}, and guarantees to traverse
     1265 +     * elements as they existed upon construction of the iterator, and
     1266 +     * may (but is not guaranteed to) reflect any modifications
     1267 +     * subsequent to construction.
1260 1268       *
1261 1269       * @return an iterator over the elements in this deque in proper sequence
1262 1270       */
1263 1271      public Iterator<E> iterator() {
1264 1272          return new Itr();
1265 1273      }
1266 1274  
1267 1275      /**
1268 1276       * Returns an iterator over the elements in this deque in reverse
1269 1277       * sequential order.  The elements will be returned in order from
1270 1278       * last (tail) to first (head).
1271 1279       *
1272      -     * <p>The returned {@code Iterator} is a "weakly consistent" iterator that
     1280 +     * <p>The returned iterator is a "weakly consistent" iterator that
1273 1281       * will never throw {@link java.util.ConcurrentModificationException
1274      -     * ConcurrentModificationException},
1275      -     * and guarantees to traverse elements as they existed upon
1276      -     * construction of the iterator, and may (but is not guaranteed to)
1277      -     * reflect any modifications subsequent to construction.
     1282 +     * ConcurrentModificationException}, and guarantees to traverse
     1283 +     * elements as they existed upon construction of the iterator, and
     1284 +     * may (but is not guaranteed to) reflect any modifications
     1285 +     * subsequent to construction.
1278 1286       *
1279 1287       * @return an iterator over the elements in this deque in reverse order
1280 1288       */
1281 1289      public Iterator<E> descendingIterator() {
1282 1290          return new DescendingItr();
1283 1291      }
1284 1292  
1285 1293      private abstract class AbstractItr implements Iterator<E> {
1286 1294          /**
1287 1295           * Next node to return item for.
↓ open down ↓ 158 lines elided ↑ open up ↑
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX