1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| structure pointer_t {ptr: pointer to node_t, count: unsigned integer}
structure node_t {value: data type, next: pointer_t}
structure queue_t {Head: pointer_t, Tail: pointer_t}
initialize(Q: pointer to queue_t)
node = new_node() // 创建新的空闲节点
node->next.ptr = NULL // 将其变为LinkList的单节点
Q->Head.ptr = Q->Tail.ptr = node // 把Head，Trail节点都设置为这个节点
enqueue(Q: pointer to queue_t, value: data type)
E1: node = new_node() // 创建一个新空闲节点
E2: node->value = value // 拷贝入栈值到空闲节点
E3: node->next.ptr = NULL // 配置当前节点的下一节点为null
E4: loop // 循环不停尝试直到入队结束
E5: tail = Q->Tail // 获取 Tail.ptr 和 Tail.count
E6: next = tail.ptr->next // 读取next ptr和 count fields
E7: if tail == Q->Tail // tail和next是确定的吗
// Tail仍然指向最后一个节点吗
E8: if next.ptr == NULL
// 尝试把节点放到队列尾部
E9: if CAS(&tail.ptr->next, next, <node, next.count+1>)
E10: break // 入队成功，退出循环
E11: endif
E12: else // Tail由于并发没有指向下一个节点
// 尝试移动Tail到下一个节点
E13: CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
E14: endif
E15: endif
E16: endloop
// 入队结束. 尝试把Tail节点更新为当前新插入的节点
E17: CAS(&Q->Tail, tail, <node, tail.count+1>)
dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean
D1: loop // 持续尝试直到出队结束
D2: head = Q->Head // Read Head 读头节点
D3: tail = Q->Tail // Read Tail 读尾节点
D4: next = head.ptr->next // 读头节点的下一节点
D5: if head == Q->Head // 头节点和尾节点是否确定？
D6: if head.ptr == tail.ptr // 队空或尾部超过头部？
D7: if next.ptr == NULL // 队空？
D8: return FALSE // 队列为空，无法出队
D9: endif
// Tail如果确实落后，尝试更新Tail
D10: CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
D11: else // No need to deal with Tail
// 在CAS前读取值不然下一个出队操作可能释放下一个节点
D12: *pvalue = next.ptr->value
// 尝试交换Head节点到下一个节点
D13: if CAS(&Q->Head, head, <next.ptr, head.count+1>)
D14: break //出队成功，退出循环
D15: endif
D16: endif
D17: endif
D18: endloop
D19: free(head.ptr) //当前安全，可以释放原节点
D20: return TRUE // 队列非空，出队成功
|