并发容器之lockfree（二）无锁堆栈

堆栈在数据结构中，只有一个方向延伸。

package com.xjx.jdktest.concurrent.container;

import java.util.concurrent.atomic.AtomicReference;

class LockFreeStack<V> {

    private AtomicReference<Node<V>> top = new AtomicReference<>();

    public LockFreeStack() {
    }

    public void push(V o) {
        Node<V> nextValue = new Node<V>(o, null);
        Node<V> oldValue = null;
        do {
            oldValue = top.get();
            nextValue.setNext(oldValue); //新节点存入旧节点
        } while (!top.compareAndSet(oldValue, nextValue));

    }

    public V pop() {
        Node<V> oldValue = null;
        Node<V> nextValue = null;
        do {
            oldValue = top.get();
            if (oldValue == null) {
                continue;//oldValue为空则栈内是空的
            }
            nextValue = oldValue.getNext();
            //while中oldValue == null 是指在空栈的情况下重试
        } while (oldValue == null || !top.compareAndSet(oldValue, nextValue));
        return oldValue.getValue();
    }

    class Node<T> {
        private T value;
        private Node<T> next;
        public Node(T value, Node<T> next) {
            super();
            this.value = value;
            this.next = next;
        }
        public T getValue() {
            return value;
        }
        public void setValue(T value) {
            this.value = value;
        }
        public Node<T> getNext() {
            return next;
        }
        public void setNext(Node<T> next) {
            this.next = next;
        }
    }
}

现在我们假设栈内容是：
top==>5==>10==> 2 .然后ThreadA 调用pop方法，执行到这一句nextValue = oldValue.getNext();
然后ThreadA 用完时间片，失去CPU的控制权，ThreadB 抢夺CPU控制权。pop5,push 24,push 16,push 8
top==>8===>16===>24===>10==> 2.那假如8的对象的地址和THreadA 中的5相同。那么，当ThreadA 执行
top.compareAndSet(oldValue, nextValue)),这个时候top跳过16和24，执行指向10。
实际上这种情况在gc环境下不会发生，在我们用CAS比较A1和A2这两个引用时，暗含着的事实是——这两个引用存在，所以它们所引用的对象都是GC root可达的。那么在A1引用的对象还未被GC时，一个新new的对象是不可能和A1的对象有相同的地址的。所以A1 != A2。