Skip to content

Instantly share code, notes, and snippets.

@rdbuf
Last active July 19, 2017 08:45
Show Gist options
  • Save rdbuf/ddcfdec2ff24028df473e825e75c660b to your computer and use it in GitHub Desktop.
Save rdbuf/ddcfdec2ff24028df473e825e75c660b to your computer and use it in GitHub Desktop.
Simple concurrent linked lists
#include <array>
#include <future>
#include <iostream>
#include <list>
#include <mutex>
#include <vector>
namespace list {
template<class ElemT>
class list_base {
virtual bool add(ElemT&&) = 0;
virtual bool remove(const ElemT&) = 0;
protected:
struct Node {
Node() = default;
Node(ElemT&& value)
: value{value} {}
ElemT value;
std::shared_ptr<Node> next;
std::mutex mutex;
};
};
template<class ElemT>
class fine_grained : public list_base<ElemT> {
public:
bool add(ElemT&& value) override {
std::shared_ptr<Node> curr, temp;
for (curr = head_, curr->mutex.lock();
curr->next;
temp = curr, curr = curr->next, curr->mutex.lock(), temp->mutex.unlock())
;
curr->next = std::make_shared<Node>(std::move(value));
curr->mutex.unlock();
return true;
}
bool remove(const ElemT& value) override {
std::shared_ptr<Node> curr, next;
for (curr = head_, curr->mutex.lock(), next = head_->next;
next && (next->mutex.lock(), true);
curr->mutex.unlock(), curr = next, next = next->next) {
if (next->value == value) {
curr->next = next->next;
curr->mutex.unlock();
return true;
}
}
curr->mutex.unlock();
return false;
}
template<class T>
friend std::ostream& operator<<(std::ostream&, const fine_grained<T>&);
private:
using Node = typename list_base<ElemT>::Node;
std::shared_ptr<Node> head_ = std::make_shared<Node>();
};
template<class T>
std::ostream& operator<<(std::ostream& os, const fine_grained<T>& list) {
using Node = typename fine_grained<T>::Node;
std::shared_ptr<Node> curr, temp;
for (curr = list.head_, curr->mutex.lock(); curr->next; temp = curr,
curr = curr->next, curr->mutex.lock(), temp->mutex.unlock()) {
std::cout << curr->next->value << " ";
}
curr->mutex.unlock();
return os;
}
}
#include "linked-lists.hh"
int main() {
list::fine_grained<int> list;
std::array<std::future<bool>, 10> a = {
std::async(std::launch::async, &list::fine_grained<int>::add, &list, 2),
std::async(std::launch::async, &list::fine_grained<int>::remove, &list, 2),
std::async(std::launch::async, &list::fine_grained<int>::add, &list, 3),
std::async(std::launch::async, &list::fine_grained<int>::add, &list, 3),
std::async(std::launch::async, &list::fine_grained<int>::add, &list, 5),
std::async(std::launch::async, &list::fine_grained<int>::add, &list, 8),
std::async(std::launch::async, &list::fine_grained<int>::remove, &list, 3),
std::async(std::launch::async, &list::fine_grained<int>::remove, &list, 8),
std::async(std::launch::async, &list::fine_grained<int>::add, &list, 2),
std::async(std::launch::async, &list::fine_grained<int>::add, &list, 10)
};
for (auto& x : a) {
x.get();
}
std::cout << list << std::endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment