Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <thread>
- #include <vector>
- #include <iostream>
- #include <numeric>
- #include <atomic>
- #include <exception>
- template <typename T>
- class lockFreeStack {
- private:
- struct Node {
- std::shared_ptr<T> data;
- Node* next;
- Node(T const& data_) :
- data(std::make_shared<T>(data_))
- {}
- };
- std::atomic<Node*> head;
- public:
- lockFreeStack() :
- head(nullptr)
- {}
- void Push(T const& data) {
- Node* const new_node = new Node(data);
- new_node->next = head.load();
- while (!head.compare_exchange_weak(new_node->next, new_node));
- }
- std::shared_ptr<T> Pop() {
- Node* old_head = head.load();
- while (old_head && !head.compare_exchange_weak(old_head, old_head->next));
- return old_head ? old_head->data : std::shared_ptr<T>();
- }
- std::shared_ptr<T> WaitAndPop() {
- while (true) {
- Node* old_head = head.load();
- while (old_head && !head.compare_exchange_weak(old_head, old_head->next));
- if (old_head)
- return old_head->data;
- }
- }
- std::shared_ptr<T> Top() {
- if (head.load()) {
- return head.load()->data;
- }
- else
- throw std::exception("Stack is empty");
- }
- };
- void job1(lockFreeStack<int>& stack, int i) {
- stack.Push(i);
- }
- void job2(lockFreeStack<int>& stack) {
- stack.Pop();
- }
- void job3(lockFreeStack<int>& stack, int i) {
- stack.Push(i);
- stack.Pop();
- }
- int main() {
- lockFreeStack<int> stack;
- std::vector<std::thread> threads;
- stack.Push(0);
- stack.Top();
- stack.WaitAndPop();
- //Test1
- /* for (int i = 0; i < std::thread::hardware_concurrency(); i++) {
- threads.push_back(std::thread(job1, std::ref(stack), i));
- }
- for (int i = 0; i < std::thread::hardware_concurrency(); i++) {
- threads[i].join();
- }
- while (stack.Pop()) {}
- //Test2a
- threads.clear();
- for (int i = 0; i < 2; i++) {
- stack.Push(i);
- }
- for (int i = 2; i < std::thread::hardware_concurrency(); i++) {
- if (i % 2 == 0)
- threads.push_back(std::thread(job1, std::ref(stack), i));
- else
- threads.push_back(std::thread(job2, std::ref(stack)));
- }
- for (int i = 2; i < std::thread::hardware_concurrency(); i++) {
- threads[i - 2].join();
- }
- while (stack.Pop()) {}
- //Test2b
- threads.clear();
- for (int i = 0; i < std::thread::hardware_concurrency(); i++) {
- if (i % 2 == 0)
- threads.push_back(std::thread(job1, std::ref(stack), i));
- else
- threads.push_back(std::thread(job2, std::ref(stack)));
- }
- for (int i = 0; i < std::thread::hardware_concurrency(); i++) {
- threads[i].join();
- }
- while (stack.Pop()) {}
- //Test3
- threads.clear();
- for (int i = 0; i < std::thread::hardware_concurrency(); i++) {
- threads.push_back(std::thread(job3, std::ref(stack), i));
- }
- for (int i = 0; i < std::thread::hardware_concurrency(); i++) {
- threads[i].join();
- }
- while (stack.Pop()) {}*/
- return 0;
- }
Add Comment
Please, Sign In to add comment