Treiber Stack 无锁并发栈

这里介绍一种无锁并发栈 ——Treiber Stack

abstract.png

基本原理

Treiber Stack 是一种 Lock-Free 无锁的并发栈，由 R. Kent Treiber 于 1986 年提出。其底层原理是借助于 CAS、自旋实现的。Java 的 ForkJoinPool、FutureTask、CompletableFuture 等均应用了 Treiber Stack

入栈、出栈的过程也很简单：

• 入栈过程：先把入栈元素的 next 指针指向当前最新的的栈顶元素，然后利用 CAS 操作保证修改栈顶指针为 入栈元素 时，没有其他线程进行修改操作。当然，如果栈顶元素发生了修改，则会进行重试
• 出栈过程：先获取当前最新的栈顶元素，将其作为准备出栈的元素。然后利用 CAS 操作保证修改栈顶指针为 其 next 指针指向的元素 时，没有其他线程进行修改操作。当然，如果栈顶元素发生了修改，则会进行重试

Java 实现

import lombok.Data;
import java.util.concurrent.atomic.AtomicReference;

public class TreiberStack<E> {
    /**
     * 栈顶指针
     */
    private final AtomicReference<Node<E>> stackTop = new AtomicReference<>();

    /**
     * 入栈
     * @param val
     */
    public void push(E val) {
        Node<E> newHeadNode = new Node<>(val);
        Node<E> oldHeadNode;
        do{
            oldHeadNode = stackTop.get();
            newHeadNode.setNext( oldHeadNode );
        }while ( !stackTop.compareAndSet(oldHeadNode, newHeadNode) );
    }

    /**
     * 出栈
     * @return
     */
    public E pop() {
        Node<E> newHeadNode;
        Node<E> oldHeadNode;

        do{
            oldHeadNode = stackTop.get();
            if( oldHeadNode==null ) {
                return null;
            }
            newHeadNode = oldHeadNode.getNext();
        } while ( !stackTop.compareAndSet(oldHeadNode, newHeadNode));
        return oldHeadNode.getVal();
    }

    public int size() {
        if( stackTop.get()==null )  {
            return 0;
        }

        int size = 0;
        Node<E> current = stackTop.get();
        while( current!=null ) {
            size++;
            current = current.getNext();
        }
        return size;
    }

    public boolean isEmpty() {
        return size()==0;
    }

    @Data
    public static class Node<E> {
        private E val;

        private Node<E> next;

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