6 #ifndef XENIUM_HARRIS_MICHAEL_LIST_BASED_SET_HPP
7 #define XENIUM_HARRIS_MICHAEL_LIST_BASED_SET_HPP
9 #include <xenium/acquire_guard.hpp>
10 #include <xenium/backoff.hpp>
11 #include <xenium/parameter.hpp>
12 #include <xenium/policy.hpp>
38 template <
class Key,
class... Policies>
42 using value_type = Key;
43 using reclaimer = parameter::type_param_t<
policy::reclaimer, parameter::nil, Policies...>;
45 using compare = parameter::type_param_t<policy::compare, std::less<Key>, Policies...>;
47 template <
class... NewPolicies>
50 static_assert(parameter::is_set<reclaimer>::value,
"reclaimer policy must be specified");
71 template <
class... Args>
90 template <
class... Args>
103 bool erase(
const Key& key);
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;
161 concurrent_ptr* prev;
166 bool find(
const Key& key, find_info& info, backoff& backoff);
184 template <
class Key,
class... Policies>
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&;
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; }
232 info.cur.acquire(*start, std::memory_order_acquire);
236 explicit iterator(harris_michael_list_based_set& list, find_info&& info) :
238 info(std::move(info))
241 harris_michael_list_based_set* list;
245 template <
class Key,
class... Policies>
246 struct harris_michael_list_based_set<Key, Policies...>::node : reclaimer::template enable_concurrent_ptr<node, 1>
250 template<
class... Args >
251 node(Args&&... args) : key(std::forward<Args>(args)...), next() {}
254 template <
class Key,
class... Policies>
257 assert(info.cur.get() !=
nullptr);
258 auto next = info.cur->next.load(std::memory_order_relaxed);
261 if (next.mark() == 0 && tmp_guard.acquire_if_equal(info.cur->next, next, std::memory_order_acquire))
263 info.prev = &info.cur->next;
264 info.save = std::move(info.cur);
265 info.cur = std::move(tmp_guard);
271 auto key = info.cur->key;
273 list->
find(key, info, backoff);
275 assert(info.prev == &list->head ||
276 info.cur.get() ==
nullptr ||
277 (info.save.get() !=
nullptr && &info.save->next == info.prev));
281 template <
class Key,
class... Policies>
289 template <
class Key,
class... Policies>
294 auto p = head.load(std::memory_order_acquire);
298 auto next = p->next.load(std::memory_order_acquire);
304 template <
class Key,
class... Policies>
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;
312 info.save = start_guard;
313 info.next = info.prev->load(std::memory_order_relaxed);
314 if (info.next.mark() != 0) {
324 if (!info.cur.acquire_if_equal(*info.prev, info.next, std::memory_order_acquire))
330 info.next = info.cur->next.load(std::memory_order_relaxed);
331 if (info.next.mark() != 0)
336 info.next = info.cur->next.load(std::memory_order_acquire).get();
339 marked_ptr expected = info.cur.get();
343 if (!info.prev->compare_exchange_weak(expected, info.next,
344 std::memory_order_release,
345 std::memory_order_relaxed))
354 if (info.prev->load(std::memory_order_relaxed) != info.cur.get())
357 const Key& ckey = info.cur->key;
359 if (compare(ckey, key) ==
false)
360 return compare(key, ckey) ==
false;
362 info.prev = &info.cur->next;
363 std::swap(info.save, info.cur);
368 template <
class Key,
class... Policies>
371 find_info info{&head};
373 return find(key, info, backoff);
376 template <
class Key,
class... Policies>
379 find_info info{&head};
381 if (find(key, info, backoff))
382 return iterator(*
this, std::move(info));
386 template <
class Key,
class... Policies>
387 template <
class... Args>
390 auto result = emplace_or_get(std::forward<Args>(args)...);
391 return result.second;
394 template <
class Key,
class... Policies>
395 template <
class... Args>
398 node* n =
new node(std::forward<Args>(args)...);
399 find_info info{&head};
403 if (find(n->key, info, backoff))
406 return {iterator(*
this, std::move(info)),
false};
410 marked_ptr expected = info.cur.get();
411 n->next.store(expected, std::memory_order_relaxed);
412 guard_ptr new_guard(n);
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};
428 template <
class Key,
class... Policies>
432 find_info info{&head};
436 if (!find(key, info, backoff))
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))
450 assert(info.next.mark() == 0);
451 assert(info.cur.mark() == 0);
454 marked_ptr expected = info.cur;
458 if (info.prev->compare_exchange_weak(expected, info.next,
459 std::memory_order_release,
460 std::memory_order_relaxed))
464 find(key, info, backoff);
469 template <
class Key,
class... Policies>
474 auto next = pos.info.cur->next.load(std::memory_order_acquire);
475 while (next.mark() == 0)
479 if (pos.info.cur->next.compare_exchange_weak(next,
480 marked_ptr(next.get(), 1),
481 std::memory_order_acquire))
487 guard_ptr next_guard(next.get());
488 assert(pos.info.cur.mark() == 0);
491 marked_ptr expected = pos.info.cur;
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);
502 Key key = pos.info.cur->key;
505 find(key, pos.info, backoff);
511 template <
class Key,
class... Policies>
517 template <
class Key,
class... Policies>
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