hazard_pointer

---

1. Single Element Stack

class Stack {
  hazard_pointer<int> ptr;

public:
  void push(int value) {
    int* old;
    while (!(old = ptr.get())) {}
    ptr.put(new int(value), old);
  }

  int pop() {
    int* old;
    int* res;
    while (!(old = ptr.get())) {}
    while (!(res = ptr.get_and_clear(old))) {}
    return *res;
  }

  bool empty() {
    return ptr.get() == nullptr;
  }
};

2. Lock-Free Queue

template <typename T>
class Queue {
  hazard_pointer<T> head, tail;

public:
  void enqueue(T value) {
    T* old_tail;
    while (!(old_tail = tail.get())) {}
    tail.put(new T(value), old_tail);
    if (head.get() == nullptr) head.put(tail.get(), nullptr);
  }

  T dequeue() {
    T* old_head;
    T* old_head_next;
    while (!(old_head = head.get())) {}
    while (!(old_head_next = head.get_and_clear(old_head))) {}
    if (tail.get() == old_head) tail.put(old_head_next, nullptr);
    return *old_head;
  }

  bool empty() {
    return head.get() == nullptr;
  }
};

3. Lock-Free Linked List

template <typename T>
class Node {
public:
  hazard_pointer<T> next;
  T data;

  Node(T data, Node<T>* next) : data(data), next(next) {}
};

class List {
  hazard_pointer<Node<T>> head;

public:
  void push_front(T data) {
    Node<T>* new_node = new Node<T>(data, head.get());
    head.put(new_node, nullptr);
  }

  Node<T>* pop_front() {
    Node<T>* old_head;
    Node<T>* old_head_next;
    while (!(old_head = head.get())) {}
    while (!(old_head_next = head.get_and_clear(old_head))) {}
    return old_head;
  }

  bool empty() {
    return head.get() == nullptr;
  }
};

4. Lock-Free Reference Counting

class RefCounted {
  std::atomic<int> count;
  hazard_pointer<RefCounted> next;

public:
  RefCounted() : count(0) {}

  int increment() {
    return count.fetch_add(1);
  }

  int decrement() {
    return count.fetch_sub(1);
  }

  bool release() {
    while (count == 1) {
      int old;
      while (!(old = next.get())) {}
      if (count.compare_exchange_strong(1, 0)) {
        next.put(nullptr, old);
        return true;
      }
    }
    return false;
  }

  bool add_next(RefCounted* next_ptr) {
    int old;
    while (!(old = next.get())) {}
    return next.put(next_ptr, old);
  }
};

5. Lock-Free Thread Local Storage

template <typename T>
class TLS {
  thread_local T value;

  std::atomic<hazard_pointer<T>> slot;

public:
  TLS() {
    slot.store(hazard_pointer<T>(nullptr));
  }

  T get() {
    return value;
  }

  void set(T new_value) {
    T* old_value;
    while (!(old_value = slot.load()->get())) {}
    value = new_value;
    slot.store(hazard_pointer<T>(value, old_value));
  }

  void reset() {
    T* old_value;
    while (!(old_value = slot.load()->get())) {}
    value = nullptr;
    slot.store(hazard_pointer<T>(nullptr, old_value));
  }
};

6. Lock-Free Concurrent Map

template <typename K, typename V>
class ConcurrentMap {
  std::unordered_map<K, V> map;
  std::atomic<hazard_pointer<std::unordered_map<K, V>>> new_map;

public:
  V get(K key) {
    return map[key];
  }

  void put(K key, V value) {
    std::unordered_map<K, V>* old_map;
    while (!(old_map = new_map.load()->get())) {}
    map[key] = value;
    new_map.store(hazard_pointer<std::unordered_map<K, V>>(&map, old_map));
  }

  void remove(K key) {
    std::unordered_map<K, V>* old_map;
    while (!(old_map = new_map.load()->get())) {}
    map.erase(key);
    new_map.store(hazard_pointer<std::unordered_map<K, V>>(&map, old_map));
  }
};

7. Lock-Free Skip List

template <typename T>
class Node {
  hazard_pointer<Node<T>> next[level];
  T data;

  Node(T data, int level) : data(data) {
    for (int i = 0; i < level; i++)
      next[i] = hazard_pointer<Node<T>>(nullptr);
  }
};

template <typename T>
class SkipList {
  std::atomic<hazard_pointer<Node<T>>> head;
  int max_level;

public:
  SkipList(int max_level) : max_level(max_level) {}

  void insert(T data) {
    Node<T>* new_node = new Node<T>(data, max_level);

    for (int i = max_level - 1; i >= 0; i--) {
      Node<T>* pred = head.get();
      while (pred->next[i].get() != nullptr && pred->next[i].get()->data < data)
        pred = pred->next[i].get();
      new_node->next[i].put(pred->next[i].get(), nullptr);
      pred->next[i].put(new_node, pred->next[i].get());
    }
  }

  bool remove(T data) {
    bool found = false;
    for (int i = max_level - 1; i >= 0; i--) {
      Node<T>* pred = head.get();
      while (pred->next[i].get() != nullptr && pred->next[i].get()->data < data)
        pred = pred->next[i].get();
      if (pred->next[i].get() == nullptr || pred->next[i].get()->data > data)
        continue;
      pred->next[i].put(pred->next[i].get()->next[i].get(), pred->next[i].get());
      found = true;
    }
    return found;
  }

  bool exists(T data) {
    Node<T>* pred = head.get();
    for (int i = max_level - 1; i >= 0; i--) {
      while (pred->next[i].get() != nullptr && pred->next[i].get()->data < data)
        pred = pred->next[i].get();
      if (pred->next[i].get() == nullptr || pred->next[i].get()->data > data)
        return false;
      pred = pred->next[i].get();
    }
    return true;
  }
};

8. Lock-Free Binary Search Tree

template <typename T>
class Node {
  hazard_pointer<Node<T>> left, right;
  T data;

  Node(T data) : data(data) {}
};

template <typename T>
class BST {
  std::atomic<hazard_pointer<Node<T>>> root;

public:
  void insert(T data) {
    Node<T>* new_node = new Node<T>(data);

    Node<T>* pred = root.get();
    while (true) {
      if (pred->data == data)
        return;
      if (pred->data < data) {
        if (pred->right.get() == nullptr) {
          pred->right.put(new_node, nullptr);
          return;
        }
        pred = pred->right.get();
      } else {
        if (pred->left.get() == nullptr) {
          pred->left.put(new_node, nullptr);
          return;
        }
        pred = pred->left.get();
      }
    }
  }

  bool remove(T data) {
    bool found = false;
    Node<T>* pred = root.get();
    while (true) {
      if (pred->data == data) {
        found = true;
        break;
      }
      if (pred->data < data) {
        if (pred->right.get() == nullptr)
          break;
        pred = pred->right.get();
      } else {
        if (pred->left.get() == nullptr)
          break;
        pred = pred->left.get();
      }
    }

    if (found) {
      // Replace pred with its successor
      if (pred->right.get() != nullptr) {
        Node<T>* succ = pred->right.get();
        while (succ->left.get() != nullptr)
          succ = succ->left.get();
        pred->data = succ->data;
        pred->right.put(succ->right.get(), succ->right.get());
      } else if (pred->left.get() != nullptr) {
        Node<T>* succ = pred->left.get();
        while (succ->right.get() != nullptr)
          succ = succ->right.get();
        pred->data = succ->data;
        pred->left.put(succ->left.get(), succ->left.get());
      } else {
        if (pred == root.get())
          root.put(nullptr, pred);
        else if (pred == pred->left.get())
          pred->left.put(nullptr, pred);
        else if (pred == pred->right.get())
          pred->right.put(nullptr, pred);
      }
    }

    return found;
  }

  bool exists(T data) {
    Node<T>* pred = root.get();
    while (true) {
      if (pred->data == data)
        return true;
      if (pred->data < data) {
        if (pred->right.get() == nullptr)
          break;
        pred = pred->right.get();
      } else {
        if (pred->left.get() == nullptr)
          break;
        pred = pred->left.get();
      }
    }
    return