c - 中断安全设置扫描

Question

我需要一个数据结构来满足这些有点不寻常的(AFAIK)要求:

1. 支持的操作有 Insert(set, item)、Delete(set, item) 和 ForAll(set, operation)
2. 插入和删除是很少见的操作。一组通常只包含一个项目。
3. 在 C 中的实现必须是可行的；特别是，不会为您收集垃圾。
4. ForAll 必须安全地从异步信号处理程序执行，其调用可能会中断 Insert 或 Delete。

当然，最后一个要求是 killer 锏。我有一个玩具实现，它围绕全局链表抛出一个全局锁，但如果信号处理程序中断关键部分，它就会死锁。

(我知道在信号处理程序中执行任何代码的所有问题；为了这个问题的目的，让我们关注如何使 ForAll 崩溃和死锁安全，当它可能有中断插入或删除。)

Answer 1

如果集合通常很小，这样在 Insert 和 Delete 方法中线性搜索列表就足够快了，那么您可以使用使用比较和交换的无锁链表实现。搜索给出了一些解释和例子。

http://www.google.com/search?q=lock+free+linked+list

列表的所有更新都是作为原子操作(比较和交换)完成的，因此中断不会导致问题。