--- jsr166/src/jsr166y/LinkedTransferQueue.java 2009/01/12 17:16:18 1.12 +++ jsr166/src/jsr166y/LinkedTransferQueue.java 2009/03/30 04:32:23 1.16 @@ -116,9 +116,14 @@ public class LinkedTransferQueue exte nextUpdater = AtomicReferenceFieldUpdater.newUpdater (QNode.class, QNode.class, "next"); - boolean casNext(QNode cmp, QNode val) { + final boolean casNext(QNode cmp, QNode val) { return nextUpdater.compareAndSet(this, cmp, val); } + + final void clearNext() { + nextUpdater.lazySet(this, this); + } + } /** @@ -151,7 +156,7 @@ public class LinkedTransferQueue exte */ private boolean advanceHead(QNode h, QNode nh) { if (h == head.get() && head.compareAndSet(h, nh)) { - h.next = h; // forget old next + h.clearNext(); // forget old next return true; } return false; @@ -344,6 +349,10 @@ public class LinkedTransferQueue exte if (w != Thread.currentThread()) LockSupport.unpark(w); } + + if (pred == null) + return; + /* * At any given time, exactly one node on list cannot be * deleted -- the last inserted node. To accommodate this, if @@ -442,6 +451,12 @@ public class LinkedTransferQueue exte return true; } + public boolean add(E e) { + if (e == null) throw new NullPointerException(); + xfer(e, NOWAIT, 0); + return true; + } + public void transfer(E e) throws InterruptedException { if (e == null) throw new NullPointerException(); if (xfer(e, WAIT, 0) == null) { @@ -538,6 +553,7 @@ public class LinkedTransferQueue exte return h; } } + reclean(); } } @@ -554,56 +570,68 @@ public class LinkedTransferQueue exte * if subsequently removed. */ class Itr implements Iterator { - QNode nextNode; // Next node to return next - QNode currentNode; // last returned node, for remove() - QNode prevNode; // predecessor of last returned node + QNode next; // node to return next + QNode pnext; // predecessor of next + QNode snext; // successor of next + QNode curr; // last returned node, for remove() + QNode pcurr; // predecessor of curr, for remove() E nextItem; // Cache of next item, once commited to in next Itr() { - nextNode = traversalHead(); - advance(); + findNext(); } - E advance() { - prevNode = currentNode; - currentNode = nextNode; - E x = nextItem; - - QNode p = nextNode.next; + /** + * Ensure next points to next valid node, or null if none. + */ + void findNext() { for (;;) { - if (p == null || !p.isData) { - nextNode = null; - nextItem = null; - return x; + QNode pred = pnext; + QNode q = next; + if (pred == null || pred == q) { + pred = traversalHead(); + q = pred.next; + } + if (q == null || !q.isData) { + next = null; + return; + } + Object x = q.get(); + QNode s = q.next; + if (x != null && q != x && q != s) { + nextItem = (E)x; + snext = s; + pnext = pred; + next = q; + return; } - Object item = p.get(); - if (item != p && item != null) { - nextNode = p; - nextItem = (E)item; - return x; - } - prevNode = p; - p = p.next; + pnext = q; + next = s; } } public boolean hasNext() { - return nextNode != null; + return next != null; } public E next() { - if (nextNode == null) throw new NoSuchElementException(); - return advance(); + if (next == null) throw new NoSuchElementException(); + pcurr = pnext; + curr = next; + pnext = next; + next = snext; + E x = nextItem; + findNext(); + return x; } public void remove() { - QNode p = currentNode; - QNode prev = prevNode; - if (prev == null || p == null) + QNode p = curr; + if (p == null) throw new IllegalStateException(); Object x = p.get(); if (x != null && x != p && p.compareAndSet(x, p)) - clean(prev, p); + clean(pcurr, p); } } @@ -692,6 +720,28 @@ public class LinkedTransferQueue exte return Integer.MAX_VALUE; } + public boolean remove(Object o) { + if (o == null) + return false; + for (;;) { + QNode pred = traversalHead(); + for (;;) { + QNode q = pred.next; + if (q == null || !q.isData) + return false; + if (q == pred) // restart + break; + Object x = q.get(); + if (x != null && x != q && o.equals(x) && + q.compareAndSet(x, q)) { + clean(pred, q); + return true; + } + pred = q; + } + } + } + /** * Save the state to a stream (that is, serialize it). * @@ -702,8 +752,8 @@ public class LinkedTransferQueue exte private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { s.defaultWriteObject(); - for (Iterator it = iterator(); it.hasNext(); ) - s.writeObject(it.next()); + for (E e : this) + s.writeObject(e); // Use trailing null as sentinel s.writeObject(null); } @@ -739,26 +789,46 @@ public class LinkedTransferQueue exte } // Temporary Unsafe mechanics for preliminary release + private static Unsafe getUnsafe() throws Throwable { + try { + return Unsafe.getUnsafe(); + } catch (SecurityException se) { + try { + return java.security.AccessController.doPrivileged + (new java.security.PrivilegedExceptionAction() { + public Unsafe run() throws Exception { + return getUnsafePrivileged(); + }}); + } catch (java.security.PrivilegedActionException e) { + throw e.getCause(); + } + } + } + + private static Unsafe getUnsafePrivileged() + throws NoSuchFieldException, IllegalAccessException { + Field f = Unsafe.class.getDeclaredField("theUnsafe"); + f.setAccessible(true); + return (Unsafe) f.get(null); + } + + private static long fieldOffset(String fieldName) + throws NoSuchFieldException { + return _unsafe.objectFieldOffset + (LinkedTransferQueue.class.getDeclaredField(fieldName)); + } + private static final Unsafe _unsafe; private static final long headOffset; private static final long tailOffset; private static final long cleanMeOffset; static { try { - if (LinkedTransferQueue.class.getClassLoader() != null) { - Field f = Unsafe.class.getDeclaredField("theUnsafe"); - f.setAccessible(true); - _unsafe = (Unsafe)f.get(null); - } - else - _unsafe = Unsafe.getUnsafe(); - headOffset = _unsafe.objectFieldOffset - (LinkedTransferQueue.class.getDeclaredField("head")); - tailOffset = _unsafe.objectFieldOffset - (LinkedTransferQueue.class.getDeclaredField("tail")); - cleanMeOffset = _unsafe.objectFieldOffset - (LinkedTransferQueue.class.getDeclaredField("cleanMe")); - } catch (Exception e) { + _unsafe = getUnsafe(); + headOffset = fieldOffset("head"); + tailOffset = fieldOffset("tail"); + cleanMeOffset = fieldOffset("cleanMe"); + } catch (Throwable e) { throw new RuntimeException("Could not initialize intrinsics", e); } }