xenium
harris_michael_list_based_set.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_HARRIS_MICHAEL_LIST_BASED_SET_HPP
7#define XENIUM_HARRIS_MICHAEL_LIST_BASED_SET_HPP
8
9#include <xenium/acquire_guard.hpp>
10#include <xenium/backoff.hpp>
11#include <xenium/parameter.hpp>
12#include <xenium/policy.hpp>
13
14#include <functional>
15
16namespace xenium {
38template <class Key, class... Policies>
40{
41public:
42 using value_type = Key;
43 using reclaimer = parameter::type_param_t<policy::reclaimer, parameter::nil, Policies...>;
44 using backoff = parameter::type_param_t<policy::backoff, no_backoff, Policies...>;
45 using compare = parameter::type_param_t<policy::compare, std::less<Key>, Policies...>;
46
47 template <class... NewPolicies>
48 using with = harris_michael_list_based_set<Key, NewPolicies..., Policies...>;
49
50 static_assert(parameter::is_set<reclaimer>::value, "reclaimer policy must be specified");
51
54
55 class iterator;
56
71 template <class... Args>
72 bool emplace(Args&&... args);
73
90 template <class... Args>
91 std::pair<iterator, bool> emplace_or_get(Args&&... args);
92
103 bool erase(const Key& key);
104
116
126 iterator find(const Key& key);
127
136 bool contains(const Key& key);
137
142 iterator begin();
143
150 iterator end();
151
152private:
153 struct node;
154
155 using concurrent_ptr = typename reclaimer::template concurrent_ptr<node, 1>;
156 using marked_ptr = typename concurrent_ptr::marked_ptr;
157 using guard_ptr = typename concurrent_ptr::guard_ptr;
158
159 struct find_info
160 {
161 concurrent_ptr* prev;
162 marked_ptr next{};
163 guard_ptr cur{};
164 guard_ptr save{};
165 };
166 bool find(const Key& key, find_info& info, backoff& backoff);
167
168 concurrent_ptr head;
169};
170
184template <class Key, class... Policies>
185class harris_michael_list_based_set<Key, Policies...>::iterator {
186public:
187 using iterator_category = std::forward_iterator_tag;
188 using value_type = Key;
189 using difference_type = std::ptrdiff_t;
190 using pointer = const Key*;
191 using reference = const Key&;
192
193 iterator(iterator&&) = default;
194 iterator(const iterator&) = default;
195
196 iterator& operator=(iterator&&) = default;
197 iterator& operator=(const iterator&) = default;
198
207 iterator& operator++();
208 iterator operator++(int);
209
210 bool operator==(const iterator& other) const { return info.cur.get() == other.info.cur.get(); }
211 bool operator!=(const iterator& other) const { return !(*this == other); }
212 reference operator*() const noexcept { return info.cur->key; }
213 pointer operator->() const noexcept { return &info.cur->key; }
214
220 void reset() {
221 info.cur.reset();
222 info.save.reset();
223 }
224private:
226
227 explicit iterator(harris_michael_list_based_set& list, concurrent_ptr* start) : list(&list)
228 {
229 info.prev = start;
230 if (start) {
231 // (2) - this acquire-load synchronizes-with the release-CAS (7, 8, 10, 13)
232 info.cur.acquire(*start, std::memory_order_acquire);
233 }
234 }
235
236 explicit iterator(harris_michael_list_based_set& list, find_info&& info) :
237 list(&list),
238 info(std::move(info))
239 {}
240
241 harris_michael_list_based_set* list;
242 find_info info;
243};
244
245template <class Key, class... Policies>
246struct harris_michael_list_based_set<Key, Policies...>::node : reclaimer::template enable_concurrent_ptr<node, 1>
247{
248 const Key key;
249 concurrent_ptr next;
250 template< class... Args >
251 node(Args&&... args) : key(std::forward<Args>(args)...), next() {}
252};
253
254template <class Key, class... Policies>
256{
257 assert(info.cur.get() != nullptr);
258 auto next = info.cur->next.load(std::memory_order_relaxed);
259 guard_ptr tmp_guard;
260 // (1) - this acquire-load synchronizes-with the release-CAS (7, 8, 10, 13)
261 if (next.mark() == 0 && tmp_guard.acquire_if_equal(info.cur->next, next, std::memory_order_acquire))
262 {
263 info.prev = &info.cur->next;
264 info.save = std::move(info.cur);
265 info.cur = std::move(tmp_guard);
266 }
267 else
268 {
269 // cur is marked for removal
270 // -> use find to remove it and get to the next node with a compare(key, cur->key) == false
271 auto key = info.cur->key;
272 backoff backoff;
273 list->find(key, info, backoff);
274 }
275 assert(info.prev == &list->head ||
276 info.cur.get() == nullptr ||
277 (info.save.get() != nullptr && &info.save->next == info.prev));
278 return *this;
279}
280
281template <class Key, class... Policies>
283{
284 iterator retval = *this;
285 ++(*this);
286 return retval;
287}
288
289template <class Key, class... Policies>
291{
292 // delete all remaining nodes
293 // (3) - this acquire-load synchronizes-with the release-CAS (7, 8, 10, 13)
294 auto p = head.load(std::memory_order_acquire);
295 while (p)
296 {
297 // (4) - this acquire-load synchronizes-with the release-CAS (7, 8, 10, 13)
298 auto next = p->next.load(std::memory_order_acquire);
299 delete p.get();
300 p = next;
301 }
302}
303
304template <class Key, class... Policies>
305bool harris_michael_list_based_set<Key, Policies...>::find(const Key& key, find_info& info, backoff& backoff)
306{
307 assert((info.save == nullptr && info.prev == &head) || &info.save->next == info.prev);
308 concurrent_ptr* start = info.prev;
309 guard_ptr start_guard = info.save; // we have to keep a guard_ptr to prevent start's node from getting reclaimed.
310retry:
311 info.prev = start;
312 info.save = start_guard;
313 info.next = info.prev->load(std::memory_order_relaxed);
314 if (info.next.mark() != 0) {
315 // our start node is marked for removal -> we have to restart from head
316 start = &head;
317 start_guard.reset();
318 goto retry;
319 }
320
321 for (;;)
322 {
323 // (5) - this acquire-load synchronizes-with the release-CAS (7, 8, 10, 13)
324 if (!info.cur.acquire_if_equal(*info.prev, info.next, std::memory_order_acquire))
325 goto retry;
326
327 if (!info.cur)
328 return false;
329
330 info.next = info.cur->next.load(std::memory_order_relaxed);
331 if (info.next.mark() != 0)
332 {
333 // Node *cur is marked for deletion -> update the link and retire the element
334
335 // (6) - this acquire-load synchronizes-with the release-CAS (7, 8, 10, 13)
336 info.next = info.cur->next.load(std::memory_order_acquire).get();
337
338 // Try to splice out node
339 marked_ptr expected = info.cur.get();
340 // (7) - this release-CAS synchronizes with the acquire-load (1, 2, 3, 4, 5, 6, 11)
341 // and the require-CAS (9, 12)
342 // it is the head of a potential release sequence containing (9, 12)
343 if (!info.prev->compare_exchange_weak(expected, info.next,
344 std::memory_order_release,
345 std::memory_order_relaxed))
346 {
347 backoff();
348 goto retry;
349 }
350 info.cur.reclaim();
351 }
352 else
353 {
354 if (info.prev->load(std::memory_order_relaxed) != info.cur.get())
355 goto retry; // cur might be cut from list.
356
357 const Key& ckey = info.cur->key;
358 compare compare;
359 if (compare(ckey, key) == false)
360 return compare(key, ckey) == false;
361
362 info.prev = &info.cur->next;
363 std::swap(info.save, info.cur);
364 }
365 }
366}
367
368template <class Key, class... Policies>
370{
371 find_info info{&head};
372 backoff backoff;
373 return find(key, info, backoff);
374}
375
376template <class Key, class... Policies>
378{
379 find_info info{&head};
380 backoff backoff;
381 if (find(key, info, backoff))
382 return iterator(*this, std::move(info));
383 return end();
384}
385
386template <class Key, class... Policies>
387template <class... Args>
389{
390 auto result = emplace_or_get(std::forward<Args>(args)...);
391 return result.second;
392}
393
394template <class Key, class... Policies>
395template <class... Args>
396auto harris_michael_list_based_set<Key, Policies...>::emplace_or_get(Args&&... args) -> std::pair<iterator, bool>
397{
398 node* n = new node(std::forward<Args>(args)...);
399 find_info info{&head};
400 backoff backoff;
401 for (;;)
402 {
403 if (find(n->key, info, backoff))
404 {
405 delete n;
406 return {iterator(*this, std::move(info)), false};
407 }
408
409 // Try to install new node
410 marked_ptr expected = info.cur.get();
411 n->next.store(expected, std::memory_order_relaxed);
412 guard_ptr new_guard(n);
413
414 // (8) - this release-CAS synchronizes with the acquire-load (1, 2, 3, 4, 5, 6, 11)
415 // and the acquire-CAS (9, 12)
416 // it is the head of a potential release sequence containing (9, 12)
417 if (info.prev->compare_exchange_weak(expected, n,
418 std::memory_order_release,
419 std::memory_order_relaxed)) {
420 info.cur = std::move(new_guard);
421 return {iterator(*this, std::move(info)), true};
422 }
423
424 backoff();
425 }
426}
427
428template <class Key, class... Policies>
430{
431 backoff backoff;
432 find_info info{&head};
433 // Find node in list with matching key and mark it for reclamation.
434 for (;;)
435 {
436 if (!find(key, info, backoff))
437 return false; // No such node in the list
438
439 // (9) - this acquire-CAS synchronizes with the release-CAS (7, 8, 10, 13)
440 // and is part of a release sequence headed by those operations
441 if (info.cur->next.compare_exchange_weak(info.next,
442 marked_ptr(info.next.get(), 1),
443 std::memory_order_acquire,
444 std::memory_order_relaxed))
445 break;
446
447 backoff();
448 }
449
450 assert(info.next.mark() == 0);
451 assert(info.cur.mark() == 0);
452
453 // Try to splice out node
454 marked_ptr expected = info.cur;
455 // (10) - this release-CAS synchronizes with the acquire-load (1, 2, 3, 4, 5, 6, 11)
456 // and the acquire-CAS (9, 12)
457 // it is the head of a potential release sequence containing (9, 12)
458 if (info.prev->compare_exchange_weak(expected, info.next,
459 std::memory_order_release,
460 std::memory_order_relaxed))
461 info.cur.reclaim();
462 else
463 // Another thread interfered -> rewalk the list to ensure reclamation of marked node before returning.
464 find(key, info, backoff);
465
466 return true;
467}
468
469template <class Key, class... Policies>
471{
472 backoff backoff;
473 // (11) - this acquire-load synchronizes-with the release-CAS (7, 8, 10, 13)
474 auto next = pos.info.cur->next.load(std::memory_order_acquire);
475 while (next.mark() == 0)
476 {
477 // (12) - this acquire-CAS synchronizes-with the release-CAS (7, 8, 10, 13)
478 // and is part of a release sequence headed by those operations
479 if (pos.info.cur->next.compare_exchange_weak(next,
480 marked_ptr(next.get(), 1),
481 std::memory_order_acquire))
482 break;
483
484 backoff();
485 }
486
487 guard_ptr next_guard(next.get());
488 assert(pos.info.cur.mark() == 0);
489
490 // Try to splice out node
491 marked_ptr expected = pos.info.cur;
492 // (13) - this release-CAS synchronizes with the acquire-load (1, 2, 3, 4, 5, 6, 11)
493 // and the acquire-CAS (9, 12)
494 // it is the head of a potential release sequence containing (9, 12)
495 if (pos.info.prev->compare_exchange_weak(expected, next_guard,
496 std::memory_order_release,
497 std::memory_order_relaxed)) {
498 pos.info.cur.reclaim();
499 pos.info.cur = std::move(next_guard);
500 } else {
501 next_guard.reset();
502 Key key = pos.info.cur->key;
503
504 // Another thread interfered -> rewalk the list to ensure reclamation of marked node before returning.
505 find(key, pos.info, backoff);
506 }
507
508 return pos;
509}
510
511template <class Key, class... Policies>
513{
514 return iterator(*this, &head);
515}
516
517template <class Key, class... Policies>
519{
520 return iterator(*this, nullptr);
521}
522}
523
524#endif
A ForwardIterator to safely iterate the list.
Definition: harris_michael_list_based_set.hpp:185
iterator & operator++()
Moves the iterator to the next element. In the absence of conflicting operations, this operation has ...
Definition: harris_michael_list_based_set.hpp:255
void reset()
Resets the iterator; this is equivalent to assigning to end() it. This operation can be handy in situ...
Definition: harris_michael_list_based_set.hpp:220
A lock-free container that contains a sorted set of unique objects of type Key.
Definition: harris_michael_list_based_set.hpp:40
iterator find(const Key &key)
Finds an element with key equivalent to key.
Definition: harris_michael_list_based_set.hpp:377
iterator begin()
Returns an iterator to the first element of the container.
Definition: harris_michael_list_based_set.hpp:512
bool emplace(Args &&... args)
Inserts a new element into the container if the container doesn't already contain an element with an ...
Definition: harris_michael_list_based_set.hpp:388
iterator end()
Returns an iterator to the element following the last element of the container.
Definition: harris_michael_list_based_set.hpp:518
bool contains(const Key &key)
Checks if there is an element with key equivalent to key in the container.
Definition: harris_michael_list_based_set.hpp:369
bool erase(const Key &key)
Removes the element with the key equivalent to key (if one exists).
Definition: harris_michael_list_based_set.hpp:429
std::pair< iterator, bool > emplace_or_get(Args &&... args)
Inserts a new element into the container if the container doesn't already contain an element with an ...
Dummy backoff strategy that does nothing.
Definition: backoff.hpp:17
Policy to configure the backoff strategy.
Definition: policy.hpp:39
Policy to configure the reclamation scheme to be used.
Definition: policy.hpp:25