/**
 * 当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其他线程都将失败。
 * 然而，失败的线程并不会被挂起，而是被告知在这次竞争中失败，并可以再次尝试。
 * 由于一个线程在竞争CAS时不会阻塞，因此它可以决定是否重新尝试，或者执行一些恢复操作，也或者不执行任何操作。
 */
public class SimulatedCAS {
    private int value;

    public synchronized int get(){
        return value;
    }

    public synchronized int compareAndSwap(int expectedValue,int newValue){
        int oldValue = value;
        if(oldValue == expectedValue){
            value = newValue;
        }
        return oldValue;
    }

    public synchronized boolean compareAndSet(int expectedValue,int newValue){
        return (expectedValue == compareAndSwap(expectedValue,newValue));
    }
}

/**
 * 通常，反复重试是一种合理的策略，但在一些竞争很激烈的情况下，更好的方式是在重试之前首先等待一段时间或者回退，从而避免造成活锁问题。
 *
 * 虽然java语言的锁定语句比较简洁，但JVM和操作在管理锁时需要完成的工作却并不简单。
 * 在实现锁定时需要遍历JVM中一条非常复杂的代码路径，并可能导致操作系统级的锁定、线程挂起以及上下文却换等动作。
 * 在最好的情况下，在锁定时至少需要一次CAS，因此虽然在使用锁时没有用到CAS，但实际上也无法节约任何执行开销。
 * 另外，在程序内部执行CAS不需要执行JVM代码、系统调用或线程调度操作。
 * 在应用级上看起来越长的代码路径，如果加上JVM和操作系统中的代码调用，那么事实上却变得更短。
 * CAS的主要缺点是，它要求调用者处理竞争问题，而在锁中能自动处理竞争问题
 */
public class CasCounter {
    private SimulatedCAS value;

    public int getValue(){
        return value.get();
    }

    public int increment(){
        int v;
        do{
            v = value.get();
        }while(v != value.compareAndSwap(v, v + 1));
        return v + 1;
    }
}

/**
 * 栈是由Node元素构成的一个链表，根节点为栈顶yop，每个元素中都包含了一个值以及指向下一个元素的链接。
 * push方法创建一个新的节点，该节点的next域指向当前的栈顶，然后使用CAS把这个新节点放入栈顶。
 *
 * @param <E>
 */
public class ConcurrentStack<E> {

    AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();

    public void push(E item){
        Node<E> newHead = new Node<E>(item);
        Node<E> oldHead;
        do{
            oldHead = top.get();
            newHead.next = oldHead;
        }while(!top.compareAndSet(oldHead, newHead));
    }

    public E pop(){
        Node<E> newHead;
        Node<E> oldHead;
        do{
            oldHead = top.get();
            if(oldHead == null){
                return null;
            }
            newHead = oldHead.next;
        }while(!top.compareAndSet(oldHead, newHead));
        return oldHead.item;
    }

    private static class Node<E>{
        public final E item;
        public Node<E> next;

        public Node(E item){
            this.item = item;
        }
    }
}

/**
 * 实现的关键点在于：
 * 当队列处于稳定状态时，未节点的next域将为空，如果队列处于中间状态，那么tail.next将为非空。
 * 因此，任何线程都能够通过检查tail.next来获取队列当前的状态。而且，当队列处于中间状态时，可以通过将尾节点向前移动一个节点，
 * 从而结束其他线程正在执行的插入元素操作，并使得队列恢复为稳定状态。
 *
 * @param <E>
 */
public class LinkedQueue<E> {

    private static class Node<E>{
        final E item;
        final AtomicReference<Node<E>> next;

        public Node(E item,Node<E> next){
            this.item = item;
            this.next = new AtomicReference<Node<E>>(next);
        }

        private final Node<E> dummy = new Node<E>(null,null);
        private final AtomicReference<Node<E>> head = new AtomicReference<Node<E>>(dummy);
        private final AtomicReference<Node<E>> tail = new AtomicReference<Node<E>>(dummy);

        private boolean put(E item){
            Node<E> newNode = new Node<E>(item,null);
            while(true){
                Node<E> curTail = tail.get();
                Node<E> tailNext = curTail.next.get();
                if(curTail == tail.get()){
                    if(tailNext != null){
                        //队列处于中间状态，推进尾节点
                        tail.compareAndSet(curTail, tailNext);
                    }else{
                        //处于稳定状态。尝试插入新节点
                        if(curTail.next.compareAndSet(null, newNode)){
                            //插入成功，尝试推进尾节点，这一步如果未来得及完成，可由别的线程帮忙
                            tail.compareAndSet(curTail, newNode);
                            return true;
                        }
                    }
                }
            }
        }
    }
}