Last active
July 19, 2017 08:45
-
-
Save rdbuf/ddcfdec2ff24028df473e825e75c660b to your computer and use it in GitHub Desktop.
Simple concurrent linked lists
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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