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
11namespace 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}}}