xenium
retire_list.hpp
1 //
2 // Copyright (c) 2018-2020 Manuel Pöter.
3 // Licensed under the MIT License. See LICENSE file in the project root for full license information.
4 //
5 
6 #pragma once
7 
8 #include <xenium/detail/port.hpp>
9 #include <xenium/reclamation/detail/deletable_object.hpp>
10 
11 namespace xenium { namespace reclamation { namespace detail {
12  template <class Node = deletable_object>
13  struct retired_nodes
14  {
15  Node* first;
16  Node* last;
17  };
18 
19  template <class Node = deletable_object>
20  struct retire_list
21  {
22  retire_list()
23  {
24  nodes.first = nullptr;
25  nodes.last = nullptr;
26  }
27 
28  ~retire_list() { assert(nodes.first == nullptr); }
29 
30  void push(Node* node)
31  {
32  node->next = nodes.first;
33  nodes.first = node;
34  if (nodes.last == nullptr)
35  nodes.last = node;
36  }
37 
38  retired_nodes<Node> steal()
39  {
40  auto result = nodes;
41  nodes.first = nullptr;
42  nodes.last = nullptr;
43  return result;
44  };
45 
46  bool empty() const { return nodes.first == nullptr; }
47  private:
48  retired_nodes<Node> nodes;
49  };
50 
51  template <class Node = deletable_object>
52  struct counting_retire_list
53  {
54  void push(Node* node)
55  {
56  list.push(node);
57  ++counter;
58  }
59 
60  retired_nodes<Node> steal()
61  {
62  counter = 0;
63  return list.steal();
64  };
65 
66  bool empty() const { return list.empty(); }
67  std::size_t size() const { return counter; }
68  private:
69  retire_list<Node> list;
70  std::size_t counter;
71  };
72 
73  template <class Node = deletable_object>
74  struct orphan_list
75  {
76  void add(retired_nodes<Node> nodes)
77  {
78  assert(nodes.first != nullptr);
79  auto h = head.load(std::memory_order_relaxed);
80  do {
81  nodes.last->next = h;
82  // (1) - this releas-CAS synchronizes-with the acquire-exchange (2)
83  } while (!head.compare_exchange_weak(h, nodes.first,
84  std::memory_order_release,
85  std::memory_order_relaxed));
86  }
87 
88  XENIUM_FORCEINLINE Node* adopt()
89  {
90  if (head.load(std::memory_order_relaxed) == nullptr)
91  return nullptr;
92 
93  // (2) - this acquire-exchange synchronizes-with the release-CAS (1)
94  return head.exchange(nullptr, std::memory_order_acquire);
95  };
96  private:
97  std::atomic<Node*> head;
98  };
99 }}}