loulett

lock free stack

May 26th, 2016
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.79 KB | None | 0 0
  1. #include <thread>
  2. #include <vector>
  3. #include <iostream>
  4. #include <numeric>
  5. #include <atomic>
  6. #include <exception>
  7.  
  8. template <typename T>
  9. class lockFreeStack {
  10. private:
  11.     struct Node {
  12.         std::shared_ptr<T> data;
  13.         Node* next;
  14.         Node(T const& data_) :
  15.             data(std::make_shared<T>(data_))
  16.         {}
  17.     };
  18.  
  19.     std::atomic<Node*> head;
  20.  
  21. public:
  22.  
  23.     lockFreeStack() :
  24.         head(nullptr)
  25.     {}
  26.  
  27.     void Push(T const& data) {
  28.         Node* const new_node = new Node(data);
  29.         new_node->next = head.load();
  30.         while (!head.compare_exchange_weak(new_node->next, new_node));
  31.     }
  32.  
  33.     std::shared_ptr<T> Pop() {
  34.         Node* old_head = head.load();
  35.         while (old_head && !head.compare_exchange_weak(old_head, old_head->next));
  36.         return old_head ? old_head->data : std::shared_ptr<T>();
  37.     }
  38.  
  39.     std::shared_ptr<T> WaitAndPop() {
  40.         while (true) {
  41.             Node* old_head = head.load();
  42.             while (old_head && !head.compare_exchange_weak(old_head, old_head->next));
  43.             if (old_head)
  44.                 return old_head->data;
  45.         }
  46.     }
  47.  
  48.     std::shared_ptr<T> Top() {
  49.         if (head.load()) {
  50.             return head.load()->data;
  51.         }
  52.         else
  53.             throw std::exception("Stack is empty");
  54.     }
  55.  
  56. };
  57.  
  58. void job1(lockFreeStack<int>& stack, int i) {
  59.     stack.Push(i);
  60. }
  61.  
  62. void job2(lockFreeStack<int>& stack) {
  63.     stack.Pop();
  64. }
  65.  
  66. void job3(lockFreeStack<int>& stack, int i) {
  67.     stack.Push(i);
  68.     stack.Pop();
  69. }
  70.  
  71. int main() {
  72.     lockFreeStack<int> stack;
  73.     std::vector<std::thread> threads;
  74.  
  75.     stack.Push(0);
  76.     stack.Top();
  77.     stack.WaitAndPop();
  78.  
  79.     //Test1
  80.  
  81. /*  for (int i = 0; i < std::thread::hardware_concurrency(); i++) {
  82.         threads.push_back(std::thread(job1, std::ref(stack), i));
  83.     }
  84.     for (int i = 0; i < std::thread::hardware_concurrency(); i++) {
  85.         threads[i].join();
  86.     }
  87.     while (stack.Pop()) {}
  88.  
  89.     //Test2a
  90.     threads.clear();
  91.  
  92.     for (int i = 0; i < 2; i++) {
  93.         stack.Push(i);
  94.     }
  95.     for (int i = 2; i < std::thread::hardware_concurrency(); i++) {
  96.         if (i % 2 == 0)
  97.             threads.push_back(std::thread(job1, std::ref(stack), i));
  98.         else
  99.             threads.push_back(std::thread(job2, std::ref(stack)));
  100.     }
  101.     for (int i = 2; i < std::thread::hardware_concurrency(); i++) {
  102.         threads[i - 2].join();
  103.     }
  104.     while (stack.Pop()) {}
  105.  
  106.     //Test2b
  107.     threads.clear();
  108.  
  109.     for (int i = 0; i < std::thread::hardware_concurrency(); i++) {
  110.         if (i % 2 == 0)
  111.             threads.push_back(std::thread(job1, std::ref(stack), i));
  112.         else
  113.             threads.push_back(std::thread(job2, std::ref(stack)));
  114.     }
  115.     for (int i = 0; i < std::thread::hardware_concurrency(); i++) {
  116.         threads[i].join();
  117.     }
  118.     while (stack.Pop()) {}
  119.  
  120.     //Test3
  121.     threads.clear();
  122.  
  123.     for (int i = 0; i < std::thread::hardware_concurrency(); i++) {
  124.         threads.push_back(std::thread(job3, std::ref(stack), i));
  125.     }
  126.     for (int i = 0; i < std::thread::hardware_concurrency(); i++) {
  127.         threads[i].join();
  128.     }
  129.     while (stack.Pop()) {}*/
  130.  
  131.     return 0;
  132. }
Add Comment
Please, Sign In to add comment