Follow-up to this question: after reading the comments, I decided to redesign my linked list to have a cursor that only contains one node and implement the interface similar to the one of forward_list in STL. The interface is fairly clear in my opinion but I also added extra comments where I found appropriate. There are some TODO that I added that I want to fix and haven't been able to find a solution to. Also looking for general design/style comments.
#include <iostream>
#include <thread>
#include <mutex>
#include <memory>
#include <optional>
#include <vector>
// Singly linked list that contains a shared pointer to its head and a mutex
// that has to be acquired to change the head.
class LockBasedLinkedList {
public:
// A node contains a value and a shared pointer to the next node. The
// reason for shared_ptr is because a cursor (iterator) contains a weak_ptr
// to a node. To read or write to a field of a node, a mutex has to be
// acquired.
struct Node {
int val;
std::shared_ptr<Node> next;
std::mutex m;
explicit Node(int val_, const std::shared_ptr<Node> &next_)
: val(val_), next(next_) {}
};
// A cursor (iterator) contains a weak pointer to a node that is
// materialized every time the node is accessed. Because the interface of
// the list allows insertion and deletion AFTER the node in the cursor, to
// insert at the beginning, there must be a special BEFORE_BEGIN cursor.
struct Cursor {
enum class NodeType {BEFORE_BEGIN, NORMAL, END};
NodeType type;
std::weak_ptr<Node> node_weak;
explicit Cursor(NodeType type_, const std::shared_ptr<Node> &node)
: type(type_), node_weak(node) {}
};
explicit LockBasedLinkedList();
~LockBasedLinkedList();
Cursor before_begin(); // not const for consistency with begin()
Cursor begin(); // TODO: think about how to make it const
Cursor end(); // not const for consistency with begin()
bool empty(); // TODO: think about how to make it const
bool try_insert_after(const Cursor &c, int val);
bool try_erase_after(const Cursor &c);
std::optional<int> get(const Cursor &c);
bool cursor_try_next(Cursor &c);
private:
std::shared_ptr<Node> head;
std::mutex m;
};
LockBasedLinkedList::LockBasedLinkedList() : head(nullptr) {}
LockBasedLinkedList::~LockBasedLinkedList() {
// TODO: free nodes to avoid stack overflow
}
LockBasedLinkedList::Cursor LockBasedLinkedList::before_begin() {
return Cursor(Cursor::NodeType::BEFORE_BEGIN, nullptr);
}
LockBasedLinkedList::Cursor LockBasedLinkedList::begin() {
// Lock the list because some other thread might be modifying the head.
std::lock_guard<std::mutex> guard(m);
return Cursor(Cursor::NodeType::NORMAL, head);
}
LockBasedLinkedList::Cursor LockBasedLinkedList::end() {
return Cursor(Cursor::NodeType::END, nullptr);
}
bool LockBasedLinkedList::empty() {
// Lock the list because some other thread might be modifying the head.
std::lock_guard<std::mutex> guard(m);
return head == nullptr;
}
// If the cursor points to the end (one past the last node) then return false.
// If the cursor points to the node before the first one, lock the list because
// the head will change. Otherwise, materialize the node in the cursor and
// acquire its lock to modify it.
bool LockBasedLinkedList::try_insert_after(const Cursor &c, int val) {
if (c.type == Cursor::NodeType::END) {
return false;
}
if (c.type == Cursor::NodeType::BEFORE_BEGIN) {
std::lock_guard<std::mutex> guard(m);
auto node = std::make_shared<Node>(val, head);
head = node;
return true;
}
auto node = c.node_weak.lock();
if (node == nullptr) {
return false; // the node was erased
}
std::lock_guard<std::mutex> guard(node->m);
auto new_node = std::make_shared<Node>(val, node->next);
node->next = new_node;
// TODO: rethink how to change the cursor (do I want to do that?)
return true;
}
// If the cursor points to the end (one past the last node) then return false.
// If the cursor points to the node before the first one, lock the list because
// the head will change, acquire the lock of the first node and set the head to
// the node after. Otherwise, materialize the node in the cursor, acquire its
// lock, acquire the lock of the next node and set the next field to the node
// after the next one.
bool LockBasedLinkedList::try_erase_after(const Cursor &c) {
if (c.type == Cursor::NodeType::END) {
return false;
}
if (c.type == Cursor::NodeType::BEFORE_BEGIN) {
std::lock_guard<std::mutex> guard(m);
if (head == nullptr) {
return false; // the list is empty
}
std::lock_guard<std::mutex> guard_head(head->m);
head = head->next;
return true;
}
auto node = c.node_weak.lock();
if (node == nullptr) {
return false; // the node was erased
}
std::lock_guard<std::mutex> guard(node->m);
if (node->next == nullptr) {
return false; // this is the last node
}
std::lock_guard<std::mutex> guard_next(node->next->m);
node->next = node->next->next;
// TODO: rethink how to change the cursor (do I want to do that?)
return true;
}
std::optional<int> LockBasedLinkedList::get(const Cursor &c) {
if (c.type == Cursor::NodeType::BEFORE_BEGIN
|| c.type == Cursor::NodeType::END) {
return {};
}
auto node = c.node_weak.lock();
if (node == nullptr) {
return {}; // the node was erased
}
std::lock_guard<std::mutex> guard(node->m);
return node->val;
}
bool LockBasedLinkedList::cursor_try_next(Cursor &c) {
if (c.type == Cursor::NodeType::END) {
return false;
}
if (c.type == Cursor::NodeType::BEFORE_BEGIN) {
std::lock_guard<std::mutex> guard(m);
// TODO: maybe get rid of NodeType::END
if (head == nullptr) {
c = Cursor(Cursor::NodeType::END, nullptr);
} else {
c = Cursor(Cursor::NodeType::NORMAL, head);
}
return true;
}
auto node = c.node_weak.lock();
if (node == nullptr) {
return false; // the node was erased
}
std::lock_guard<std::mutex> guard(node->m);
if (node->next == nullptr) {
c = Cursor(Cursor::NodeType::END, nullptr);
} else {
c = Cursor(Cursor::NodeType::NORMAL, node->next);
}
return true;
}
void testNThread(int n) {
constexpr int N = 100;
std::vector<std::thread> threads(n);
LockBasedLinkedList lst;
for (int i = 0; i < n; i++) {
threads[i] = std::thread([i, &lst]() {
for (int j = 0; j < N; j++) {
while (!lst.try_insert_after(lst.before_begin(), i)) {
std::cout << "urgh insert\n";
}
}
});
}
for (auto &&t : threads) {
t.join();
}
for (int i = 0; i < N * n; i++) {
auto valopt = lst.get(lst.begin());
while (!valopt) {
valopt = lst.get(lst.begin());
}
int val = valopt.value();
while (!lst.try_erase_after(lst.before_begin())) {
std::cout << "urgh erase\n";
}
std::cout << val << " ";
}
std::cout << "\n";
}
int main(int argc, char **argv) {
int n = 10;
if (argc >= 2) {
n = atoi(argv[1]);
}
testNThread(n);
}
