Congratulations — I think this is the first concurrency-related code I've reviewed on CodeReview in which I have not managed to find any concurrency-related bugs! It looks like a solid implementation of "hand-over-hand" traversal. (Now that I've said that, I bet someone else will find a bug. :))
First, a few stylistic nitpicks:
using namespace std;
Never! Just write std::vector<std::thread>
if that's what you mean. The small space savings isn't worth dealing with all the people like me who'll tell you over and over not to write using namespace std;
at global scope. :)
const int N = 10;
Make this constexpr int N = 10;
and you won't need to capture a copy of it in your lambda.
for (int i = 0; i < n; i++) {
threads[i].join();
}
Prefer to write this with a ranged for loop:
for (auto&& thread : threads) {
thread.join();
}
struct Node {
int val;
Node *next;
mutex m;
Node(int val_, Node *next_ = nullptr) : val(val_), next(next_) {}
};
Defaulted function arguments are the devil. And, completely independently, so are implicit conversions! I would prefer to write this as:
struct Node {
int val;
Node *next = nullptr;
mutex m;
explicit Node(int val_) : val(val_) {}
explicit Node(int val_, Node *next_) : val(val_), next(next_) {}
};
or even
struct Node {
int val;
Node *next;
mutex m;
explicit Node(int val_) : Node(val_, nullptr) {}
explicit Node(int val_, Node *next_) : val(val_), next(next_) {}
};
Okay, now for the serious stuff.
void erase(int pos);
This is a really weird API for a linked list. For one thing, even for a non-concurrent linked list, you're turning "erase a node" into an O(n) operation. More importantly for a concurrent linked list, I can't see how this operation is useful at all! Suppose some thread says "please erase the 42nd element." How does it even know what the 42nd element is, given that any other thread could modify the list at any time?
Your use of raw new
and delete
looks safe to me, but it would be a lot easier to verify its safety if you just didn't use raw new
and delete
! Consider this trivial rewrite of insert
:
void insert(int val, int pos) {
auto new_node = std::make_unique<Node>(val);
Node *prev = head_;
unique_lock<mutex> prev_lk(prev->m);
Node *node = prev->next;
unique_lock<mutex> node_lk(node->m);
for (int i = 0; i < pos && node != tail_; i++) {
prev = node;
node = node->next;
prev_lk.swap(node_lk);
node_lk = unique_lock<mutex>(node->m);
}
new_node->next = node;
prev->next = new_node.release();
}
Only two lines changed, but now it's obvious that we never leak memory...
...except in the destructor of LockBasedLinkedList
, which (being defaulted) just leaks every node remaining in the list! Was that intentional, or an oversight?
Also consider the behavior of
LockBasedLinkedList a;
auto b = a;
This certainly doesn't do what you want. What do you want it to do? If the answer is "I want it not to compile," then you should =delete
your copy operations:
LockBasedLinkedList(const LockBasedLinkedList&) = delete;
LockBasedLinkedList& operator=(const LockBasedLinkedList&) = delete;
In get
:
if (node == tail_) {
return 0;
}
How would your user distinguish the 0
that means "no such node" from the 0
that means "this node exists and has value 0
"? I would strongly recommend designing your API so that this distinction is obvious to the user. For example:
std::optional<int> get(int);
How to return unique_lock in a function...?
I think this is related to your get
API, yeah? That is, maybe you want something like
LockedNodePointer get(int);
class LockedNodePointer {
public:
LockedNodePointer(std::nullptr_t) : ptr_(nullptr) {}
Node& operator*() const { return *ptr_; }
Node& operator->() const { return ptr_; }
private:
friend class LockBasedLinkedList;
using Lock = std::unique_lock<std::mutex>;
explicit LockedNodePointer(Lock lk, Node *ptr) : lk_(lk), ptr_(ptr) {}
Lock lk_;
Node *ptr_;
};
This is an even cleaner way to distinguish "node with value 0
" from "no such node."
It would also be interesting to consider: do you need a version of your get
member function that is const
-qualified? (Getting an element doesn't really modify the list, right?)
Do you need two overloads of get
— one const
and one non-const
?