ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/jsr166y/LinkedTransferQueue.java
(Generate patch)

Comparing jsr166/src/jsr166y/LinkedTransferQueue.java (file contents):
Revision 1.82 by jsr166, Mon Nov 29 20:58:06 2010 UTC vs.
Revision 1.93 by jsr166, Wed Oct 29 20:23:14 2014 UTC

# Line 1 | Line 1
1   /*
2   * Written by Doug Lea with assistance from members of JCP JSR-166
3   * Expert Group and released to the public domain, as explained at
4 < * http://creativecommons.org/licenses/publicdomain
4 > * http://creativecommons.org/publicdomain/zero/1.0/
5   */
6  
7   package jsr166y;
8  
9   import java.util.AbstractQueue;
10   import java.util.Collection;
11 – import java.util.ConcurrentModificationException;
11   import java.util.Iterator;
12   import java.util.NoSuchElementException;
13   import java.util.Queue;
# Line 23 | Line 22 | import java.util.concurrent.locks.LockSu
22   * producer.  The <em>tail</em> of the queue is that element that has
23   * been on the queue the shortest time for some producer.
24   *
25 < * <p>Beware that, unlike in most collections, the {@code size}
26 < * method is <em>NOT</em> a constant-time operation. Because of the
25 > * <p>Beware that, unlike in most collections, the {@code size} method
26 > * is <em>NOT</em> a constant-time operation. Because of the
27   * asynchronous nature of these queues, determining the current number
28 < * of elements requires a traversal of the elements.
28 > * of elements requires a traversal of the elements, and so may report
29 > * inaccurate results if this collection is modified during traversal.
30 > * Additionally, the bulk operations {@code addAll},
31 > * {@code removeAll}, {@code retainAll}, {@code containsAll},
32 > * {@code equals}, and {@code toArray} are <em>not</em> guaranteed
33 > * to be performed atomically. For example, an iterator operating
34 > * concurrently with an {@code addAll} operation might view only some
35 > * of the added elements.
36   *
37   * <p>This class and its iterator implement all of the
38   * <em>optional</em> methods of the {@link Collection} and {@link
# Line 70 | Line 76 | public class LinkedTransferQueue<E> exte
76       *
77       * A FIFO dual queue may be implemented using a variation of the
78       * Michael & Scott (M&S) lock-free queue algorithm
79 <     * (http://www.cs.rochester.edu/u/scott/papers/1996_PODC_queues.pdf).
79 >     * (http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf).
80       * It maintains two pointer fields, "head", pointing to a
81       * (matched) node that in turn points to the first actual
82       * (unmatched) queue node (or null if empty); and "tail" that
# Line 295 | Line 301 | public class LinkedTransferQueue<E> exte
301       *    of less-contended queues.  During spins threads check their
302       *    interrupt status and generate a thread-local random number
303       *    to decide to occasionally perform a Thread.yield. While
304 <     *    yield has underdefined specs, we assume that might it help,
305 <     *    and will not hurt in limiting impact of spinning on busy
304 >     *    yield has underdefined specs, we assume that it might help,
305 >     *    and will not hurt, in limiting impact of spinning on busy
306       *    systems.  We also use smaller (1/2) spins for nodes that are
307       *    not known to be front but whose predecessors have not
308       *    blocked -- these "chained" spins avoid artifacts of
# Line 497 | Line 503 | public class LinkedTransferQueue<E> exte
503              return false;
504          }
505  
500 –        // Unsafe mechanics
501 –        private static final sun.misc.Unsafe UNSAFE = getUnsafe();
502 –        private static final long nextOffset =
503 –            objectFieldOffset(UNSAFE, "next", Node.class);
504 –        private static final long itemOffset =
505 –            objectFieldOffset(UNSAFE, "item", Node.class);
506 –        private static final long waiterOffset =
507 –            objectFieldOffset(UNSAFE, "waiter", Node.class);
508 –
506          private static final long serialVersionUID = -3375979862319811754L;
507 +
508 +        // Unsafe mechanics
509 +        private static final sun.misc.Unsafe UNSAFE;
510 +        private static final long itemOffset;
511 +        private static final long nextOffset;
512 +        private static final long waiterOffset;
513 +        static {
514 +            try {
515 +                UNSAFE = getUnsafe();
516 +                Class<?> k = Node.class;
517 +                itemOffset = UNSAFE.objectFieldOffset
518 +                    (k.getDeclaredField("item"));
519 +                nextOffset = UNSAFE.objectFieldOffset
520 +                    (k.getDeclaredField("next"));
521 +                waiterOffset = UNSAFE.objectFieldOffset
522 +                    (k.getDeclaredField("waiter"));
523 +            } catch (Exception e) {
524 +                throw new Error(e);
525 +            }
526 +        }
527      }
528  
529      /** head of the queue; null until first enqueue */
# Line 581 | Line 598 | public class LinkedTransferQueue<E> exte
598                                  break;        // unless slack < 2
599                          }
600                          LockSupport.unpark(p.waiter);
601 <                        return this.<E>cast(item);
601 >                        return LinkedTransferQueue.<E>cast(item);
602                      }
603                  }
604                  Node n = p.next;
# Line 659 | Line 676 | public class LinkedTransferQueue<E> exte
676              if (item != e) {                  // matched
677                  // assert item != s;
678                  s.forgetContents();           // avoid garbage
679 <                return this.<E>cast(item);
679 >                return LinkedTransferQueue.<E>cast(item);
680              }
681              if ((w.isInterrupted() || (timed && nanos <= 0)) &&
682                      s.casItem(e, s)) {        // cancel
# Line 740 | Line 757 | public class LinkedTransferQueue<E> exte
757              Object item = p.item;
758              if (p.isData) {
759                  if (item != null && item != p)
760 <                    return this.<E>cast(item);
760 >                    return LinkedTransferQueue.<E>cast(item);
761              }
762              else if (item == null)
763                  return null;
# Line 806 | Line 823 | public class LinkedTransferQueue<E> exte
823              }
824  
825              this.lastRet = prev;
826 +
827              for (Node p = prev, s, n;;) {
828                  s = (p == null) ? head : p.next;
829                  if (s == null)
# Line 998 | Line 1016 | public class LinkedTransferQueue<E> exte
1016       * return {@code false}.
1017       *
1018       * @return {@code true} (as specified by
1019 <     *  {@link BlockingQueue#offer(Object,long,TimeUnit) BlockingQueue.offer})
1019 >     *  {@link java.util.concurrent.BlockingQueue#offer(Object,long,TimeUnit)
1020 >     *  BlockingQueue.offer})
1021       * @throws NullPointerException if the specified element is null
1022       */
1023      public boolean offer(E e, long timeout, TimeUnit unit) {
# Line 1115 | Line 1134 | public class LinkedTransferQueue<E> exte
1134          if (c == this)
1135              throw new IllegalArgumentException();
1136          int n = 0;
1137 <        E e;
1119 <        while ( (e = poll()) != null) {
1137 >        for (E e; (e = poll()) != null;) {
1138              c.add(e);
1139              ++n;
1140          }
# Line 1133 | Line 1151 | public class LinkedTransferQueue<E> exte
1151          if (c == this)
1152              throw new IllegalArgumentException();
1153          int n = 0;
1154 <        E e;
1137 <        while (n < maxElements && (e = poll()) != null) {
1154 >        for (E e; n < maxElements && (e = poll()) != null;) {
1155              c.add(e);
1156              ++n;
1157          }
# Line 1142 | Line 1159 | public class LinkedTransferQueue<E> exte
1159      }
1160  
1161      /**
1162 <     * Returns an iterator over the elements in this queue in proper
1163 <     * sequence, from head to tail.
1162 >     * Returns an iterator over the elements in this queue in proper sequence.
1163 >     * The elements will be returned in order from first (head) to last (tail).
1164       *
1165       * <p>The returned iterator is a "weakly consistent" iterator that
1166 <     * will never throw
1167 <     * {@link ConcurrentModificationException ConcurrentModificationException},
1168 <     * and guarantees to traverse elements as they existed upon
1169 <     * construction of the iterator, and may (but is not guaranteed
1170 <     * to) reflect any modifications subsequent to construction.
1166 >     * will never throw {@link java.util.ConcurrentModificationException
1167 >     * ConcurrentModificationException}, and guarantees to traverse
1168 >     * elements as they existed upon construction of the iterator, and
1169 >     * may (but is not guaranteed to) reflect any modifications
1170 >     * subsequent to construction.
1171       *
1172       * @return an iterator over the elements in this queue in proper sequence
1173       */
# Line 1241 | Line 1258 | public class LinkedTransferQueue<E> exte
1258       * {@code LinkedTransferQueue} is not capacity constrained.
1259       *
1260       * @return {@code Integer.MAX_VALUE} (as specified by
1261 <     *         {@link BlockingQueue#remainingCapacity()})
1261 >     *         {@link java.util.concurrent.BlockingQueue#remainingCapacity()
1262 >     *         BlockingQueue.remainingCapacity})
1263       */
1264      public int remainingCapacity() {
1265          return Integer.MAX_VALUE;
# Line 1273 | Line 1291 | public class LinkedTransferQueue<E> exte
1291          throws java.io.IOException, ClassNotFoundException {
1292          s.defaultReadObject();
1293          for (;;) {
1294 <            @SuppressWarnings("unchecked") E item = (E) s.readObject();
1294 >            @SuppressWarnings("unchecked")
1295 >            E item = (E) s.readObject();
1296              if (item == null)
1297                  break;
1298              else
# Line 1283 | Line 1302 | public class LinkedTransferQueue<E> exte
1302  
1303      // Unsafe mechanics
1304  
1305 <    private static final sun.misc.Unsafe UNSAFE = getUnsafe();
1306 <    private static final long headOffset =
1307 <        objectFieldOffset(UNSAFE, "head", LinkedTransferQueue.class);
1308 <    private static final long tailOffset =
1309 <        objectFieldOffset(UNSAFE, "tail", LinkedTransferQueue.class);
1291 <    private static final long sweepVotesOffset =
1292 <        objectFieldOffset(UNSAFE, "sweepVotes", LinkedTransferQueue.class);
1293 <
1294 <    static long objectFieldOffset(sun.misc.Unsafe UNSAFE,
1295 <                                  String field, Class<?> klazz) {
1305 >    private static final sun.misc.Unsafe UNSAFE;
1306 >    private static final long headOffset;
1307 >    private static final long tailOffset;
1308 >    private static final long sweepVotesOffset;
1309 >    static {
1310          try {
1311 <            return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field));
1312 <        } catch (NoSuchFieldException e) {
1313 <            // Convert Exception to corresponding Error
1314 <            NoSuchFieldError error = new NoSuchFieldError(field);
1315 <            error.initCause(e);
1316 <            throw error;
1311 >            UNSAFE = getUnsafe();
1312 >            Class<?> k = LinkedTransferQueue.class;
1313 >            headOffset = UNSAFE.objectFieldOffset
1314 >                (k.getDeclaredField("head"));
1315 >            tailOffset = UNSAFE.objectFieldOffset
1316 >                (k.getDeclaredField("tail"));
1317 >            sweepVotesOffset = UNSAFE.objectFieldOffset
1318 >                (k.getDeclaredField("sweepVotes"));
1319 >        } catch (Exception e) {
1320 >            throw new Error(e);
1321          }
1322      }
1323  
# Line 1313 | Line 1331 | public class LinkedTransferQueue<E> exte
1331      static sun.misc.Unsafe getUnsafe() {
1332          try {
1333              return sun.misc.Unsafe.getUnsafe();
1334 <        } catch (SecurityException se) {
1335 <            try {
1336 <                return java.security.AccessController.doPrivileged
1337 <                    (new java.security
1338 <                     .PrivilegedExceptionAction<sun.misc.Unsafe>() {
1339 <                        public sun.misc.Unsafe run() throws Exception {
1340 <                            java.lang.reflect.Field f = sun.misc
1341 <                                .Unsafe.class.getDeclaredField("theUnsafe");
1342 <                            f.setAccessible(true);
1343 <                            return (sun.misc.Unsafe) f.get(null);
1344 <                        }});
1345 <            } catch (java.security.PrivilegedActionException e) {
1346 <                throw new RuntimeException("Could not initialize intrinsics",
1347 <                                           e.getCause());
1348 <            }
1334 >        } catch (SecurityException tryReflectionInstead) {}
1335 >        try {
1336 >            return java.security.AccessController.doPrivileged
1337 >            (new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
1338 >                public sun.misc.Unsafe run() throws Exception {
1339 >                    Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
1340 >                    for (java.lang.reflect.Field f : k.getDeclaredFields()) {
1341 >                        f.setAccessible(true);
1342 >                        Object x = f.get(null);
1343 >                        if (k.isInstance(x))
1344 >                            return k.cast(x);
1345 >                    }
1346 >                    throw new NoSuchFieldError("the Unsafe");
1347 >                }});
1348 >        } catch (java.security.PrivilegedActionException e) {
1349 >            throw new RuntimeException("Could not initialize intrinsics",
1350 >                                       e.getCause());
1351          }
1352      }
1333 –
1353   }

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines