读ConcurrentLinkedQueue_JAVA_编程开发_程序员俱乐部

class="java" name="code">
//这是一个无阻塞的队列没有加任何锁全部利用CAS机制实现。效率极高。
//先看构造函数
public ConcurrentLinkedQueue() {
        head = tail = new Node<E>(null);
    }

public ConcurrentLinkedQueue(Collection<? extends E> c) {
        Node<E> h = null, t = null;
        for (E e : c) {
	    //元素不可以为null
            checkNotNull(e);
            Node<E> newNode = new Node<E>(e);
	    //如果头节点为空
            if (h == null)
                h = t = newNode;
            else {
	        //设为下一个节点
                t.lazySetNext(newNode);
                t = newNode;
            }
        }
        if (h == null)
            h = t = new Node<E>(null);
        head = h;
        tail = t;
    }

//添加元素
public boolean add(E e) {
        return offer(e);
    }

 public boolean offer(E e) {
        checkNotNull(e);
        final Node<E> newNode = new Node<E>(e);

        for (Node<E> t = tail, p = t;;) {
            Node<E> q = p.next;
	    //当前p是尾节点
            if (q == null) {
		//利用cas设置值
                if (p.casNext(null, newNode)) {
                    //这意味着一个线程已经设置了tail.next。相当于每两次更新下tail
                    if (p != t) 
		        //将newNode设置为尾节点
                        casTail(t, newNode);  // Failure is OK.
                    return true;
                }
                // Lost CAS race to another thread; re-read next
            }
	    //在poll的时候设置了哨兵,正好遇到哨兵了。
            else if (p == q)
               
                p = (t != (t = tail)) ? t : head;
            else
                // Check for tail updates after two hops.
		//寻找尾节点。这里有一个优化假如tail已经被修改直接定位到tail作为最后一个节点。
                p = (p != t && t != (t = tail)) ? t : q;
        }
    }


//获取并移除一个节点
public E poll() {
        restartFromHead:
        for (;;) {
            for (Node<E> h = head, p = h, q;;) {
                E item = p.item;
                 //如果item有值并且将item设置为null成功
                if (item != null && p.casItem(item, null)) {
                    //这和offer思路一样
                    if (p != h) 
                        updateHead(h, ((q = p.next) != null) ? q : p);
                    return item;
                }
		//没有了
                else if ((q = p.next) == null) {
                    updateHead(h, p);
                    return null;
                }
		//遇到哨兵节点了重新循环
                else if (p == q)
                    continue restartFromHead;
                else
                    p = q;
            }
        }
    }

//只获取但是不移除
public E peek() {
        restartFromHead:
        for (;;) {
            for (Node<E> h = head, p = h, q;;) {
                E item = p.item;
                if (item != null || (q = p.next) == null) {
		    //设置p为头结点,也就是过滤p前面的空节点。
                    updateHead(h, p);
                    return item;
                }
                else if (p == q)
                    continue restartFromHead;
                else
                    p = q;
            }
        }
    }

//判断队列是否为空
public boolean isEmpty() {
        return first() == null;
    }

//找到第一个不为null的节点。并且设置为头节点。
Node<E> first() {
        restartFromHead:
        for (;;) {
            for (Node<E> h = head, p = h, q;;) {
                boolean hasItem = (p.item != null);
                if (hasItem || (q = p.next) == null) {
                    updateHead(h, p);
                    return hasItem ? p : null;
                }
                else if (p == q)
                    continue restartFromHead;
                else
                    p = q;
            }
        }
    }

//获取元素个数
public int size() {
        int count = 0;
        for (Node<E> p = first(); p != null; p = succ(p))
            if (p.item != null)
                // Collection.size() spec says to max out
                if (++count == Integer.MAX_VALUE)
                    break;
        return count;
    }


final Node<E> succ(Node<E> p) {
        Node<E> next = p.next;
        return (p == next) ? head : next;
    }

//包含某个元素和size的实现差不多
public boolean contains(Object o) {
        if (o == null) return false;
        for (Node<E> p = first(); p != null; p = succ(p)) {
            E item = p.item;
            if (item != null && o.equals(item))
                return true;
        }
        return false;
    }

//移除一个元素
public boolean remove(Object o) {
        if (o == null) return false;
        Node<E> pred = null;
        for (Node<E> p = first(); p != null; p = succ(p)) {
            E item = p.item;
            if (item != null &&
                o.equals(item) &&
                p.casItem(item, null)) {
                Node<E> next = succ(p);
                if (pred != null && next != null)
                    pred.casNext(p, next);
                return true;
            }
            pred = p;
        }
        return false;
    }

//新增全部
 public boolean addAll(Collection<? extends E> c) {
        if (c == this)
            throw new IllegalArgumentException();

        // Copy c into a private chain of Nodes
	//将c变为链表结构
        Node<E> beginningOfTheEnd = null, last = null;
        for (E e : c) {
            checkNotNull(e);
            Node<E> newNode = new Node<E>(e);
            if (beginningOfTheEnd == null)
                beginningOfTheEnd = last = newNode;
            else {
                last.lazySetNext(newNode);
                last = newNode;
            }
        }
        if (beginningOfTheEnd == null)
            return false;

        // Atomically append the chain at the tail of this collection
        for (Node<E> t = tail, p = t;;) {
            Node<E> q = p.next;
	    //如果当前p正好是队尾
            if (q == null) {
                // p is last node
		//CAS设置值
                if (p.casNext(null, beginningOfTheEnd)) {
                    //可能队尾已经被其他线程设置过了
                    if (!casTail(t, last)) {
                        //再次尝试
                        t = tail;
                        if (last.next == null)
                            casTail(t, last);
                    }
                    return true;
                }
                
            }
            else if (p == q)
              
                p = (t != (t = tail)) ? t : head;
            else
               
                p = (p != t && t != (t = tail)) ? t : q;
        }
    }

  public Object[] toArray() {
        
        ArrayList<E> al = new ArrayList<E>();
        for (Node<E> p = first(); p != null; p = succ(p)) {
            E item = p.item;
            if (item != null)
                al.add(item);
        }
        return al.toArray();
    }

//这个实现和其他集合的实现不太一样。我个人觉得是因为计算size有开销。所以这样写提升效率。
 public <T> T[] toArray(T[] a) {
       
        int k = 0;
        Node<E> p;
        for (p = first(); p != null && k < a.length; p = succ(p)) {
            E item = p.item;
            if (item != null)
                a[k++] = (T)item;
        }
	//如果a的length>队列的length
        if (p == null) {
            if (k < a.length)
                a[k] = null;
            return a;
        }

        //如果a的length<队列的length
        ArrayList<E> al = new ArrayList<E>();
        for (Node<E> q = first(); q != null; q = succ(q)) {
            E item = q.item;
            if (item != null)
                al.add(item);
        }
        return al.toArray(a);
    }

//迭代器
private class Itr implements Iterator<E> {
       
        private Node<E> nextNode;

        private E nextItem;

        private Node<E> lastRet;

        Itr() {
            advance();
        }

       
        private E advance() {
            lastRet = nextNode;
            E x = nextItem;

            Node<E> pred, p;
            if (nextNode == null) {
                p = first();
                pred = null;
            } else {
                pred = nextNode;
                p = succ(nextNode);
            }

            for (;;) {
                if (p == null) {
                    nextNode = null;
                    nextItem = null;
                    return x;
                }
                E item = p.item;
                if (item != null) {
                    nextNode = p;
                    nextItem = item;
                    return x;
                } else {
                    // skip over nulls
                    Node<E> next = succ(p);
                    if (pred != null && next != null)
                        pred.casNext(p, next);
                    p = next;
                }
            }
        }

        public boolean hasNext() {
            return nextNode != null;
        }

        public E next() {
            if (nextNode == null) throw new NoSuchElementException();
            return advance();
        }

        public void remove() {
            Node<E> l = lastRet;
            if (l == null) throw new IllegalStateException();
            
            l.item = null;
            lastRet = null;
        }
    }