From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- .../util/concurrent/ConcurrentLinkedQueue.java | 480 +++++++++++++++++++++ 1 file changed, 480 insertions(+) create mode 100644 libjava/classpath/external/jsr166/java/util/concurrent/ConcurrentLinkedQueue.java (limited to 'libjava/classpath/external/jsr166/java/util/concurrent/ConcurrentLinkedQueue.java') diff --git a/libjava/classpath/external/jsr166/java/util/concurrent/ConcurrentLinkedQueue.java b/libjava/classpath/external/jsr166/java/util/concurrent/ConcurrentLinkedQueue.java new file mode 100644 index 000000000..000f4a4c9 --- /dev/null +++ b/libjava/classpath/external/jsr166/java/util/concurrent/ConcurrentLinkedQueue.java @@ -0,0 +1,480 @@ +/* + * Written by Doug Lea with assistance from members of JCP JSR-166 + * Expert Group and released to the public domain, as explained at + * http://creativecommons.org/licenses/publicdomain + */ + +package java.util.concurrent; +import java.util.*; +import java.util.concurrent.atomic.*; + + +/** + * An unbounded thread-safe {@linkplain Queue queue} based on linked nodes. + * This queue orders elements FIFO (first-in-first-out). + * The head of the queue is that element that has been on the + * queue the longest time. + * The tail of the queue is that element that has been on the + * queue the shortest time. New elements + * are inserted at the tail of the queue, and the queue retrieval + * operations obtain elements at the head of the queue. + * A ConcurrentLinkedQueue is an appropriate choice when + * many threads will share access to a common collection. + * This queue does not permit null elements. + * + *

This implementation employs an efficient "wait-free" + * algorithm based on one described in Simple, + * Fast, and Practical Non-Blocking and Blocking Concurrent Queue + * Algorithms by Maged M. Michael and Michael L. Scott. + * + *

Beware that, unlike in most collections, the size method + * is NOT a constant-time operation. Because of the + * asynchronous nature of these queues, determining the current number + * of elements requires a traversal of the elements. + * + *

This class and its iterator implement all of the + * optional methods of the {@link Collection} and {@link + * Iterator} interfaces. + * + *

Memory consistency effects: As with other concurrent + * collections, actions in a thread prior to placing an object into a + * {@code ConcurrentLinkedQueue} + * happen-before + * actions subsequent to the access or removal of that element from + * the {@code ConcurrentLinkedQueue} in another thread. + * + *

This class is a member of the + * + * Java Collections Framework. + * + * @since 1.5 + * @author Doug Lea + * @param the type of elements held in this collection + * + */ +public class ConcurrentLinkedQueue extends AbstractQueue + implements Queue, java.io.Serializable { + private static final long serialVersionUID = 196745693267521676L; + + /* + * This is a straight adaptation of Michael & Scott algorithm. + * For explanation, read the paper. The only (minor) algorithmic + * difference is that this version supports lazy deletion of + * internal nodes (method remove(Object)) -- remove CAS'es item + * fields to null. The normal queue operations unlink but then + * pass over nodes with null item fields. Similarly, iteration + * methods ignore those with nulls. + * + * Also note that like most non-blocking algorithms in this + * package, this implementation relies on the fact that in garbage + * collected systems, there is no possibility of ABA problems due + * to recycled nodes, so there is no need to use "counted + * pointers" or related techniques seen in versions used in + * non-GC'ed settings. + */ + + private static class Node { + private volatile E item; + private volatile Node next; + + private static final + AtomicReferenceFieldUpdater + nextUpdater = + AtomicReferenceFieldUpdater.newUpdater + (Node.class, Node.class, "next"); + private static final + AtomicReferenceFieldUpdater + itemUpdater = + AtomicReferenceFieldUpdater.newUpdater + (Node.class, Object.class, "item"); + + Node(E x) { item = x; } + + Node(E x, Node n) { item = x; next = n; } + + E getItem() { + return item; + } + + boolean casItem(E cmp, E val) { + return itemUpdater.compareAndSet(this, cmp, val); + } + + void setItem(E val) { + itemUpdater.set(this, val); + } + + Node getNext() { + return next; + } + + boolean casNext(Node cmp, Node val) { + return nextUpdater.compareAndSet(this, cmp, val); + } + + void setNext(Node val) { + nextUpdater.set(this, val); + } + + } + + private static final + AtomicReferenceFieldUpdater + tailUpdater = + AtomicReferenceFieldUpdater.newUpdater + (ConcurrentLinkedQueue.class, Node.class, "tail"); + private static final + AtomicReferenceFieldUpdater + headUpdater = + AtomicReferenceFieldUpdater.newUpdater + (ConcurrentLinkedQueue.class, Node.class, "head"); + + private boolean casTail(Node cmp, Node val) { + return tailUpdater.compareAndSet(this, cmp, val); + } + + private boolean casHead(Node cmp, Node val) { + return headUpdater.compareAndSet(this, cmp, val); + } + + + /** + * Pointer to header node, initialized to a dummy node. The first + * actual node is at head.getNext(). + */ + private transient volatile Node head = new Node(null, null); + + /** Pointer to last node on list **/ + private transient volatile Node tail = head; + + + /** + * Creates a ConcurrentLinkedQueue that is initially empty. + */ + public ConcurrentLinkedQueue() {} + + /** + * Creates a ConcurrentLinkedQueue + * initially containing the elements of the given collection, + * added in traversal order of the collection's iterator. + * @param c the collection of elements to initially contain + * @throws NullPointerException if the specified collection or any + * of its elements are null + */ + public ConcurrentLinkedQueue(Collection c) { + for (Iterator it = c.iterator(); it.hasNext();) + add(it.next()); + } + + // Have to override just to update the javadoc + + /** + * Inserts the specified element at the tail of this queue. + * + * @return true (as specified by {@link Collection#add}) + * @throws NullPointerException if the specified element is null + */ + public boolean add(E e) { + return offer(e); + } + + /** + * Inserts the specified element at the tail of this queue. + * + * @return true (as specified by {@link Queue#offer}) + * @throws NullPointerException if the specified element is null + */ + public boolean offer(E e) { + if (e == null) throw new NullPointerException(); + Node n = new Node(e, null); + for (;;) { + Node t = tail; + Node s = t.getNext(); + if (t == tail) { + if (s == null) { + if (t.casNext(s, n)) { + casTail(t, n); + return true; + } + } else { + casTail(t, s); + } + } + } + } + + public E poll() { + for (;;) { + Node h = head; + Node t = tail; + Node first = h.getNext(); + if (h == head) { + if (h == t) { + if (first == null) + return null; + else + casTail(t, first); + } else if (casHead(h, first)) { + E item = first.getItem(); + if (item != null) { + first.setItem(null); + return item; + } + // else skip over deleted item, continue loop, + } + } + } + } + + public E peek() { // same as poll except don't remove item + for (;;) { + Node h = head; + Node t = tail; + Node first = h.getNext(); + if (h == head) { + if (h == t) { + if (first == null) + return null; + else + casTail(t, first); + } else { + E item = first.getItem(); + if (item != null) + return item; + else // remove deleted node and continue + casHead(h, first); + } + } + } + } + + /** + * Returns the first actual (non-header) node on list. This is yet + * another variant of poll/peek; here returning out the first + * node, not element (so we cannot collapse with peek() without + * introducing race.) + */ + Node first() { + for (;;) { + Node h = head; + Node t = tail; + Node first = h.getNext(); + if (h == head) { + if (h == t) { + if (first == null) + return null; + else + casTail(t, first); + } else { + if (first.getItem() != null) + return first; + else // remove deleted node and continue + casHead(h, first); + } + } + } + } + + + /** + * Returns true if this queue contains no elements. + * + * @return true if this queue contains no elements + */ + public boolean isEmpty() { + return first() == null; + } + + /** + * Returns the number of elements in this queue. If this queue + * contains more than Integer.MAX_VALUE elements, returns + * Integer.MAX_VALUE. + * + *

Beware that, unlike in most collections, this method is + * NOT a constant-time operation. Because of the + * asynchronous nature of these queues, determining the current + * number of elements requires an O(n) traversal. + * + * @return the number of elements in this queue + */ + public int size() { + int count = 0; + for (Node p = first(); p != null; p = p.getNext()) { + if (p.getItem() != null) { + // Collections.size() spec says to max out + if (++count == Integer.MAX_VALUE) + break; + } + } + return count; + } + + /** + * Returns true if this queue contains the specified element. + * More formally, returns true if and only if this queue contains + * at least one element e such that o.equals(e). + * + * @param o object to be checked for containment in this queue + * @return true if this queue contains the specified element + */ + public boolean contains(Object o) { + if (o == null) return false; + for (Node p = first(); p != null; p = p.getNext()) { + E item = p.getItem(); + if (item != null && + o.equals(item)) + return true; + } + return false; + } + + /** + * Removes a single instance of the specified element from this queue, + * if it is present. More formally, removes an element e such + * that o.equals(e), if this queue contains one or more such + * elements. + * Returns true if this queue contained the specified element + * (or equivalently, if this queue changed as a result of the call). + * + * @param o element to be removed from this queue, if present + * @return true if this queue changed as a result of the call + */ + public boolean remove(Object o) { + if (o == null) return false; + for (Node p = first(); p != null; p = p.getNext()) { + E item = p.getItem(); + if (item != null && + o.equals(item) && + p.casItem(item, null)) + return true; + } + return false; + } + + /** + * Returns an iterator over the elements in this queue in proper sequence. + * The returned iterator is a "weakly consistent" iterator that + * will never throw {@link 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 queue in proper sequence + */ + public Iterator iterator() { + return new Itr(); + } + + private class Itr implements Iterator { + /** + * Next node to return item for. + */ + private Node nextNode; + + /** + * nextItem holds on to item fields because once we claim + * that an element exists in hasNext(), we must return it in + * the following next() call even if it was in the process of + * being removed when hasNext() was called. + */ + private E nextItem; + + /** + * Node of the last returned item, to support remove. + */ + private Node lastRet; + + Itr() { + advance(); + } + + /** + * Moves to next valid node and returns item to return for + * next(), or null if no such. + */ + private E advance() { + lastRet = nextNode; + E x = nextItem; + + Node p = (nextNode == null)? first() : nextNode.getNext(); + for (;;) { + if (p == null) { + nextNode = null; + nextItem = null; + return x; + } + E item = p.getItem(); + if (item != null) { + nextNode = p; + nextItem = item; + return x; + } else // skip over nulls + p = p.getNext(); + } + } + + public boolean hasNext() { + return nextNode != null; + } + + public E next() { + if (nextNode == null) throw new NoSuchElementException(); + return advance(); + } + + public void remove() { + Node l = lastRet; + if (l == null) throw new IllegalStateException(); + // rely on a future traversal to relink. + l.setItem(null); + lastRet = null; + } + } + + /** + * Save the state to a stream (that is, serialize it). + * + * @serialData All of the elements (each an E) in + * the proper order, followed by a null + * @param s the stream + */ + private void writeObject(java.io.ObjectOutputStream s) + throws java.io.IOException { + + // Write out any hidden stuff + s.defaultWriteObject(); + + // Write out all elements in the proper order. + for (Node p = first(); p != null; p = p.getNext()) { + Object item = p.getItem(); + if (item != null) + s.writeObject(item); + } + + // Use trailing null as sentinel + s.writeObject(null); + } + + /** + * Reconstitute the Queue instance from a stream (that is, + * deserialize it). + * @param s the stream + */ + private void readObject(java.io.ObjectInputStream s) + throws java.io.IOException, ClassNotFoundException { + // Read in capacity, and any hidden stuff + s.defaultReadObject(); + head = new Node(null, null); + tail = head; + // Read in all elements and place in queue + for (;;) { + E item = (E)s.readObject(); + if (item == null) + break; + else + offer(item); + } + } + +} -- cgit v1.2.3