specification

• ordered（ascending）
• no duplicated key

features

• non-blocking
• linearizable
• compare-and-swap based

仅使用一个cas的缺陷

• insert

• delete

对于只有一个insert或者一个delete的情况，没有问题会出现。

• insert and delete

但是如果一个insert和一个delete同时进行，问题就会出现。删除30的时候，一个cas无法保证，也不能避免10和30之间的修改。

解决方法：用两个cas

基本思想

• stage 1 用一个cas mark将要被删除结点的next field（logically deleted）；

• stage 2 另一个cas来进行删除结点（physically deleted）。

stage 1结束以后，list的结构保持不变，mark以后的结点，避免了新节点insert到该结点的后面。

algorithm

marked and unmarked

A node is marked if and only if its next field is marked.

这句话是关键：论文中的mark，实际上是mark了要被删除结点的next指针，而不是要被删除的结点本身。 我觉得从另一个视角来看，mark的效果是，不允许改变要被删除结点的后继结点。这点从避免前文提到的问题的角度来说，也应该是正确的理解。

get_marked_reference和get_unmarked_reference是以copy的形式传入reference，mark或者unmark以后的并不是reference本身。

数据结构

1
2
3
4
5
6
7
8
9

struct Node {
  key_type key;
  node *next;
}

struct list {
  node *head;
  node *tail;
}

search

满足这么几个要求：

• left_node.key < search_key <= right_node.key
• left_node and right_node are unmarked
• right_node is immediate successor（直接后继） of left_node

有这么几个步骤：

• 找到left_node和right_node
• 检查是不是直接后继
  • 是，直接返回
• 移除left_node and right_node之间的一个或多个marked结点

insert

• 找到left_node和right_node
• cas插入

delete

如前文解决方法中描述的，分两个阶段：

• stage 1:
  • 找到left_node和right_node
  • logically delete
• stage 2:
  • physically delete
    • cas删除
    • 或者search中删除

find

• 找到left_node和right_node
• right_node == search_key

Reference

1. A Pragmatic Implementation of Non-Blocking Linked-lists, Timothy L. Harris.