遍历带有危险指针的列表

Question

我正在使用Hazard指针来实现C中的无锁链接列表.除了各种基本队列和堆栈之外,我找不到任何示例代码.问题是我需要遍历列表,所以我的问题是我是否可以在分配后更改危险指针的值.例如:

t?Top
while(true) {
    if t=null then
        return null
    *hp?t
    if Top!=t then
        continue
    ...
    t?(t?next) //after this instruction pointer t will be still protected?
}

Answer 1

最后我根据原始论文完成了我自己版本的危险指针（HP）的实现。我的问题的答案是否定的，它不再可以安全使用。原因是，HP 的工作方式是，当您将 t 声明为危险指针时，*hp正在保护t所指向的节点，因此当t移动到下一个节点时，HP 机制会继续保护前一个节点。我必须将新值重新分配给*hp，然后才能安全使用它。

\n\n

另外，在本文的示例中，它并不明确，但是当您使用完危险指针时，您必须释放它。这意味着，将*hp返回到其原始状态（NULL )。这样，如果另一个线程想要删除（退休）该节点，它将不会被视为正在使用。

\n\n

在上面的示例中，我必须在离开该方法之前释放*hp 。在循环内部，这是不必要的，因为我覆盖相同的 *hp 位置 (*hp \xe2\x86\x90 t)，因此前一个节点不再受保护。

\n