SHARE
TWEET

Untitled

a guest May 19th, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma once
  2.  
  3. #include "thread_local.hpp"
  4.  
  5. #include <twist/stdlike/atomic.hpp>
  6.  
  7. #include <twist/support/compiler.hpp>
  8.  
  9. #include <functional>
  10.  
  11. namespace solutions {
  12.  
  13. // Michael-Scott lock-free queue
  14.  
  15. template <typename T>
  16. class LockFreeQueue {
  17.  private:
  18.   struct Node {
  19.     twist::atomic<Node*> next;
  20.     T item;
  21.  
  22.     Node(T my_item) {
  23.       item = my_item;
  24.       next.store(nullptr);
  25.     }
  26.  
  27.     ~Node() {
  28.       if (next.load()) {
  29.         delete next.load();
  30.       }
  31.     }
  32.   };
  33.  
  34.   ThreadLocal<std::vector<Node*> > hazard_pointers_;
  35.   ThreadLocal<std::vector<Node*> > delete_obj_;
  36.   twist::atomic<Node*> head_;
  37.   twist::atomic<Node*> tail_;
  38.   size_t hp_cnt_{0};
  39.  
  40.   void Delete_useless_ptrs() {
  41.     std::vector<Node*> new_delete_obj;
  42.     for (Node* ptr : (*delete_obj_)) {
  43.       for (auto &hp : hazard_pointers_) {
  44.         if (hp[0] == ptr || hp[1] == ptr) {
  45.           new_delete_obj.push_back(ptr);
  46.         }
  47.         else {
  48.           delete ptr;
  49.         }
  50.       }
  51.     }
  52.     (*delete_obj_) = new_delete_obj;
  53.   }
  54.  
  55.  public:
  56.   LockFreeQueue() {
  57.     Node* dummy = new Node(T());
  58.     head_.store(dummy);
  59.     tail_.store(dummy);
  60.  
  61.     for (auto& hp : hazard_pointers_) {
  62.       hp.resize(2, nullptr);
  63.     }
  64.   }
  65.  
  66.   ~LockFreeQueue() {
  67.     for (auto& hp : hazard_pointers_) {
  68.       delete hp[0];
  69.       delete hp[1];
  70.     }
  71.  
  72.     for (auto& delete_hp : delete_obj_) {
  73.       for (auto& ptr : delete_hp) {
  74.         delete ptr;
  75.       }
  76.     }
  77.  
  78.     Node* my_head = head_.load();
  79.     Node* my_tail = tail_.load();
  80.     head_.store(nullptr);
  81.     tail_.store(nullptr);
  82.  
  83.     if (my_head) {
  84.       delete my_head;
  85.     }
  86.   }
  87.  
  88.   void Enqueue(T item) {
  89.     if (!(*hazard_pointers_).size()) {
  90.       (*hazard_pointers_).resize(2, nullptr);
  91.     }
  92.  
  93.     Node* new_node = new Node(item);
  94.     Node* my_tail;
  95.  
  96.     for (;;) {
  97.       my_tail = tail_.load();
  98.       (*hazard_pointers_)[0] = my_tail;
  99.       if (my_tail != tail_.load()) {
  100.         continue;
  101.       }
  102.  
  103.       Node* next = my_tail->next;
  104.       if (next != nullptr) {
  105.         tail_.compare_exchange_weak(my_tail, next);
  106.         continue;
  107.       }
  108.  
  109.       Node* nothing = nullptr;
  110.       if (my_tail->next.compare_exchange_strong(nothing, new_node)) {
  111.         break;
  112.       }
  113.     }
  114.  
  115.     tail_.compare_exchange_strong(my_tail, new_node);
  116.     (*hazard_pointers_)[0] = nullptr;
  117.   }
  118.  
  119.   bool Dequeue(T& item) {
  120.     Node* my_head;
  121.  
  122.     for (;;) {
  123.       my_head = head_.load();
  124.       (*hazard_pointers_)[0] = my_head;
  125.       if (my_head != head_.load()) {
  126.         continue;
  127.       }
  128.  
  129.       Node* next = my_head->next.load();
  130.       (*hazard_pointers_)[1] = next;
  131.       if (head_ != head_.load()) {
  132.         continue;
  133.       }
  134.  
  135.       if (!next) {
  136.         (*hazard_pointers_)[0] = nullptr;
  137.         return false;
  138.       }
  139.  
  140.       Node* my_tail = tail_.load();
  141.       if (my_head == my_tail) {
  142.         tail_.compare_exchange_strong(my_tail, next);
  143.         continue;
  144.       }
  145.  
  146.       item = next->item;
  147.       if (head_.compare_exchange_strong(my_head, next)) {
  148.         break;
  149.       }
  150.     }
  151.  
  152.     (*hazard_pointers_)[0] = nullptr;
  153.     (*hazard_pointers_)[1] = nullptr;
  154.  
  155.     (*delete_obj_).push_back(my_head);
  156.  
  157.     size_t hp_cnt = 0;
  158.     for (auto& hp : hazard_pointers_) {
  159.       UNUSED(hp);
  160.       hp_cnt++;
  161.     }
  162.     hp_cnt *= 2;
  163.     if ((*delete_obj_).size() == 2 * hp_cnt_) {
  164.       Delete_useless_ptrs();
  165.     }
  166.  
  167.     return true;
  168.   }
  169. };
  170.  
  171. }  // namespace solutions
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top