線程安全的搜索和添加

Question

我需要能夠做到以下幾點：

1. 搜索鏈接的列表。
2. 添加一個新的節點到列表中以防萬一找不到。
3. 線程安全並使用rwlock，因爲它主要讀取列表。

我遇到的問題是，當我從read_lock升級到write_lock時，我需要再次搜索列表，以確保其他線程沒有在write_lock上等待，而我正在執行列表搜索， read_lock。

是否有不同的方式來實現上述而不做雙列表搜索（也許是某種seq_lock）？

Answer 1

將鏈接列表轉換爲排序後的鏈接列表。當它添加一個新節點的時候，你可以再次檢查，看看另一個作者是否在添加一個等價節點的同時通過檢查兩個節點來獲取鎖定，而不是搜索整個列表。由於您需要確定新節點的排序順序，因此您將在每個節點插入上花費更多時間，但無需搜索整個列表即可節省時間。總的來說，你可能會節省很多時間。