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 
16 namespace xenium {
38 template <class Key, class... Policies>
40 {
41 public:
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 
115  iterator erase(iterator pos);
116 
126  iterator find(const Key& key);
127 
136  bool contains(const Key& key);
137 
142  iterator begin();
143 
150  iterator end();
151 
152 private:
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 
184 template <class Key, class... Policies>
185 class harris_michael_list_based_set<Key, Policies...>::iterator {
186 public:
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  }
224 private:
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 
245 template <class Key, class... Policies>
246 struct 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 
254 template <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 
281 template <class Key, class... Policies>
283 {
284  iterator retval = *this;
285  ++(*this);
286  return retval;
287 }
288 
289 template <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 
304 template <class Key, class... Policies>
305 bool 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.
310 retry:
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 
368 template <class Key, class... Policies>
370 {
371  find_info info{&head};
372  backoff backoff;
373  return find(key, info, backoff);
374 }
375 
376 template <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 
386 template <class Key, class... Policies>
387 template <class... Args>
389 {
390  auto result = emplace_or_get(std::forward<Args>(args)...);
391  return result.second;
392 }
393 
394 template <class Key, class... Policies>
395 template <class... Args>
396 auto 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 
428 template <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 
469 template <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 
511 template <class Key, class... Policies>
513 {
514  return iterator(*this, &head);
515 }
516 
517 template <class Key, class... Policies>
519 {
520  return iterator(*this, nullptr);
521 }
522 }
523 
524 #endif
xenium::policy::backoff
Policy to configure the backoff strategy.
Definition: policy.hpp:39
xenium::harris_michael_list_based_set::find
iterator find(const Key &key)
Finds an element with key equivalent to key.
Definition: harris_michael_list_based_set.hpp:377
xenium::harris_michael_list_based_set::emplace_or_get
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 ...
xenium::harris_michael_list_based_set::erase
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
xenium::harris_michael_list_based_set::contains
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
xenium::harris_michael_list_based_set::iterator::reset
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
xenium::harris_michael_list_based_set::emplace
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
xenium::harris_michael_list_based_set::end
iterator end()
Returns an iterator to the element following the last element of the container.
Definition: harris_michael_list_based_set.hpp:518
xenium::harris_michael_list_based_set
A lock-free container that contains a sorted set of unique objects of type Key.
Definition: harris_michael_list_based_set.hpp:40
xenium::policy::reclaimer
Policy to configure the reclamation scheme to be used.
Definition: policy.hpp:25
xenium::no_backoff
Dummy backoff strategy that does nothing.
Definition: backoff.hpp:17
xenium::harris_michael_list_based_set::iterator
A ForwardIterator to safely iterate the list.
Definition: harris_michael_list_based_set.hpp:185
xenium::harris_michael_list_based_set::iterator::operator++
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
xenium::harris_michael_list_based_set::begin
iterator begin()
Returns an iterator to the first element of the container.
Definition: harris_michael_list_based_set.hpp:512