无锁的线程安全栈

template <typename T>
class LockFreeStack {
 private:
  struct Node;
  struct CountNodePtr {
    int external_count;
    Node* ptr;
  };
  struct Node {
    std::shared_ptr<T> data;
    std::atomic<int> internal_count;
    CountNodePtr next;

    Node(const T& value)
        : data(std::make_shared<T>(value)), internal_count(0) {}
  };
  std::atomic<CountNodePtr> head;
};

class LockFreeStack {
private:
  struct Node {
    std::shared_ptr<T> data;
    Node* next;
  };
  std::atomic<Node*> head;

public:
  std::shared_ptr<T> pop() {
    Node* old_head = head.load(); // 1
    while(old_head && !head.compare_exchange_weak(old_head, old_head->next)); // 2
    std::shared_ptr<T> res = old_head ? old_head->data : std::make_shared<T>();
    delete old_head;
    return res;
  }
};

void push(const T& value) {
  // 1. 创建结点，并计数
  CountNodePtr new_node;
  new_node.ptr = new Node(value);
  new_node.external_count = 1;

  // 2. 将新结点的next指向head
  new_node.ptr->next = head;

  // 3. 确保新结点的next指向的是最新的head
  // 并将新节点设为head
  while(!head.compare_exchange_weak(new_node.ptr->next, new_node));
}

void IncreaseHeadCount(CountNodePtr& old_counter) {
  // new_counter只是个临时量
  counted_node_ptr new_counter;
  do {
    new_counter = old_counter;
    ++new_counter.external_count;
    // 如果head没变，head的外部计数加一
    // 如果head改变，old_counter拷贝head，然后head的外部计数加一
  } while(!head.compare_exchange_strong(old_counter, new_counter));
  old_counter.external_count = new_counter.external_count;
}

std::shared_ptr<T> pop() {
  CountNodePtr old_head = head.load();
  while (1) {
    // 获取头节点以及其外部计数
    IncreaseHeadCount(old_head);
    node* old_head_ptr = old_head.ptr;
    if (!old_head_ptr) return std::shared_ptr<T>();

    // 某个线程(线程a)进入后，其他线程就无法获取到当前结点了
    // 其他线程就两种情况:
    // 1. 刚进入pop，还没有IncreaseHeadCount()，那就与当前节点无关了，加载的是另外的结点
    // 2. 经过了这个IncreaseHeadCount()，引用的是与线程a相同的结点，此时只能结束对当前结点的引用
    // 内部计数减一，即执行else if的内容
    if (head.compare_exchange_strong(old_head, old_head_ptr->next)) {

      std::shared_ptr<T> res;
      res.swap(old_head_ptr->data);

      // head不再引用该结点，因此减一
      // 当前的old_head也将要超出作用域，再次减一
      // 该代码好像有些误导，需要看下面的部分才能明白此处的含义
      const int count_increase = old_head.external_count - 2;

      // 当前线程退出引用后，计数的第一阶段结束
      // 此时外部计数为external_count，而内部计数为internal_count - 2
      // 判断总计数 = external_count + (internal_count - 2)是否为0
      // 即判断internal_count == -(external_count - 2)
      // 此处解释了上面count_increase的定义，以及下面的if判断

      // 计数进入第二阶段，将外部计数加入到内部计数
      // internal_count = (internal_count - 2) + external_count
      // 也就是internal_count.fetch_add(external_count - 2)
      if (old_head_ptr->internal_count.fetch_add(count_increase) ==
          -count_increase) {
        delete old_head_ptr;
      }
      return res;
    } else if (old_head_ptr->internal_count.fetch_sub(1) == 1) {
      // internal_count.fetch_sub(-1)很好理解，其他线程退出对当前结点的引用，详情见if(CAS)处的注释
      // 对于internal_count == 1的判断
      // 一般来说internal_count肯定为0或者负数，即线程退出结点的引用而递减
      // 当internal_count为正数时，表示当前节点的计数由内部计数来表达(计数的第二阶段)
      // internal_count为1，表示只有当前线程持有该节点，因此退出引用，删除节点
      delete old_head_ptr;
    }
  }
}