linux - 线程安全的搜索和添加

Question

我需要能够执行以下操作：

1. 搜索一个链表。
2. 将新节点添加到列表中，以防找不到。
3. 是线程安全的并使用 rwlock ，因为它主要读取列表。

我遇到的问题是，当我从 read_lock 提升到 write_lock 时，我需要再次搜索列表，以确保在执行持有 read_lock 的列表搜索时其他线程没有等待 write_lock。

是否有不同的方法可以在不进行双重列表搜索（可能是某种 seq_lock ）的情况下实现上述目标？

Answer 1

将链表转换为排序的链表。当需要添加新节点时，您可以通过仅检查两个节点而不是搜索整个列表来再次检查其他写入者是否在您获取锁时添加了等效节点。您将在每个节点插入上花费更多时间，因为您需要确定新节点的排序顺序，但您无需搜索整个列表即可节省时间。总的来说，您可能会节省很多时间。