I'm trying to implement a concurrent linked list in C++ for multiple std::threads to operate on. The lock should not block the whole list, just single nodes. However, my debugging patience is reaching its limit with an error that occurs. Concurrent reads and inserts work fine, but once multiple threads also remove nodes, I am getting data races and mutex errors like the following:
Mutex M93731171587876416 is already destroyed.
Am I missing anything? The implementation of the remove function looks like below. Note that it is a sorted list.
#include <mutex>
template<typename T>
struct node {
T value;
node<T>* next;
std::mutex node_lock;
};
template<typename T>
class concurrent_list {
node<T>* first = nullptr;
public:
concurrent_list() = default;
concurrent_list(const concurrent_list<T>& other) = default;
concurrent_list(concurrent_list<T>&& other) = default;
concurrent_list<T>& operator=(const concurrent_list<T>& other) = default;
concurrent_list<T>& operator=(concurrent_list<T>&& other) = default;
~concurrent_list() {
while(first != nullptr) {
remove(first->value);
}
}
void remove(T v) {
/* first find position */
node<T>* pred = nullptr;
node<T>* current = first;
node<T>* succ = nullptr;
if (current != nullptr) {
current->node_lock.lock();
}
while (current != nullptr && current->value < v) {
/* search for node to remove */
if (pred != nullptr) {
pred->node_lock.unlock();
}
pred = current;
current = current->next;
if (current != nullptr) {
current->node_lock.lock();
}
}
if (current == nullptr || current->value != v) {
/* v not found */
if (pred != nullptr) {
pred->node_lock.unlock();
}
if (current != nullptr) {
current->node_lock.unlock();
}
return;
}
/* remove current */
succ = current->next;
if(succ != nullptr) {
succ->node_lock.lock();
}
if (pred == nullptr) {
first = current->next;
} else {
pred->next = current->next;
}
if (current != nullptr) {
current->node_lock.unlock();
}
delete current;
if (pred != nullptr) {
pred->node_lock.unlock();
}
if (succ != nullptr) {
succ->node_lock.unlock();
}
}
}
EDIT: I've tried current.unlock() before deleting the target node, but it did not seem to make a difference.