线程安全的搜索和添加

Question

我需要能够做到以下几点：

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

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

是否有不同的方式来实现上述而不做双列表搜索（也许是某种seq_lock）？

Answer 1

将链接列表转换为排序后的链接列表。当它添加一个新节点的时候，你可以再次检查，看看另一个作者是否在添加一个等价节点的同时通过检查两个节点来获取锁定，而不是搜索整个列表。由于您需要确定新节点的排序顺序，因此您将在每个节点插入上花费更多时间，但无需搜索整个列表即可节省时间。总的来说，你可能会节省很多时间。