xenium
Loading...
Searching...
No Matches
left_right.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#ifndef XENIUM_LEFT_RIGHT_HPP
7#define XENIUM_LEFT_RIGHT_HPP
8
9#include <atomic>
10#include <cassert>
11#include <mutex>
12#include <thread>
13
14#ifdef _MSC_VER
15#pragma warning(push)
16#pragma warning(disable: 4324) // structure was padded due to alignment specifier
17#endif
18
19namespace xenium {
20
37template<typename T>
38struct left_right {
46 left_right(T source) :
47 left(source),
48 right(std::move(source))
49 {}
50
59 left_right(T left, T right) :
60 left(std::move(left)),
61 right(std::move(right))
62 {}
63
67 left_right() = default;
68
82 template<typename Func>
83 auto read(Func&& func) const {
84 read_guard guard(*this);
85 // (1) - this seq-cst-load enforces a total order with the seq-cst-store (2, 3)
86 const T& inst = lr_indicator.load(std::memory_order_seq_cst) == READ_LEFT ? left : right;
87 return func(inst);
88 }
89
99 template<typename Func>
100 void update(Func&& func) {
101 std::lock_guard<std::mutex> lock(writer_mutex);
102 assert(lr_indicator.load() == version_index.load());
103 if (lr_indicator.load(std::memory_order_relaxed) == READ_LEFT) {
104 func(right);
105 // (2) - this seq-cst-store enforces a total order with the seq-cst-load (1)
106 lr_indicator.store(READ_RIGHT, std::memory_order_seq_cst);
107 toggle_version_and_wait();
108 func(left);
109 } else {
110 func(left);
111 // (3) - this seq-cst-store enforces a total order with the seq-cst-load (1)
112 lr_indicator.store(READ_LEFT, std::memory_order_seq_cst);
113 toggle_version_and_wait();
114 func(right);
115 }
116 }
117private:
118 struct alignas(64) read_indicator {
119 void arrive(void) {
120 // (4) - this seq-cst-fetch-add enforces a total order with the seq-cst-load (6)
121 counter.fetch_add(1, std::memory_order_seq_cst);
122 }
123 void depart(void) {
124 // (5) - this release-fetch-sub synchronizes-with the seq-cst-load (6)
125 counter.fetch_sub(1, std::memory_order_release);
126 // Note: even though this method is only called by reader threads that (usually)
127 // do not change the underlying data structure, we still have to use release
128 // order here to ensure that the read operations is properly ordered before a
129 // subsequent update operation.
130 }
131 bool empty(void) {
132 // (6) - this seq-cst-load enforces a total order with the seq-cst-fetch-add (4)
133 // and synchronizes-with the release-fetch-add (5)
134 return counter.load(std::memory_order_seq_cst) == 0;
135 }
136 private:
137 std::atomic<uint64_t> counter{0};
138 };
139
140 struct read_guard {
141 read_guard(const left_right& inst) :
142 indicator(inst.get_read_indicator(inst.version_index.load(std::memory_order_relaxed)))
143 {
144 indicator.arrive();
145 }
146 ~read_guard() { indicator.depart(); }
147 private:
148 read_indicator& indicator;
149 };
150 friend struct read_guard;
151
152 void toggle_version_and_wait(void) {
153 const int current_version = version_index.load(std::memory_order_relaxed);
154 const int current_idx = current_version & 0x1;
155 const int next_idx = (current_version + 1) & 0x1;
156
157 wait_for_readers(next_idx);
158 version_index.store(next_idx, std::memory_order_relaxed);
159 wait_for_readers(current_idx);
160 }
161
162 void wait_for_readers(int idx) {
163 auto& indicator = get_read_indicator(idx);
164 while (!indicator.empty())
165 std::this_thread::yield();
166 }
167
168 read_indicator& get_read_indicator(int idx) const {
169 assert(idx == 0 || idx == 1);
170 if (idx == 0)
171 return read_indicator1;
172 return read_indicator2;
173 }
174
175 static constexpr int READ_LEFT = 0;
176 static constexpr int READ_RIGHT = 1;
177
178 // TODO: make mutex type configurable via policy
179 std::mutex writer_mutex;
180 std::atomic<int> version_index{0} ;
181 std::atomic<int> lr_indicator { READ_LEFT };
182
183 mutable read_indicator read_indicator1;
184 T left;
185
186 mutable read_indicator read_indicator2;
187 T right;
188};
189}
190
191#ifdef _MSC_VER
192#pragma warning(pop)
193#endif
194
195#endif
Generic implementation of the LeftRight algorithm proposed by Ramalhete and Correia [RC15].
Definition left_right.hpp:38
left_right(T source)
Initialize the two underlying T instances with the specified source.
Definition left_right.hpp:46
auto read(Func &&func) const
Performs a read operation on the active instance using the specified functor.
Definition left_right.hpp:83
void update(Func &&func)
Performs an update operation on both underlying instances using the specified functor.
Definition left_right.hpp:100
left_right()=default
Default constructs both underlying instances.
left_right(T left, T right)
Initializes the two underlying instances withe the specified sources.
Definition left_right.hpp:59