xenium
harris_michael_hash_map.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_HASH_MAP_HPP
7 #define XENIUM_HARRIS_MICHAEL_HASH_MAP_HPP
8 
9 #include <xenium/acquire_guard.hpp>
10 #include <xenium/backoff.hpp>
11 #include <xenium/hash.hpp>
12 #include <xenium/parameter.hpp>
13 #include <xenium/policy.hpp>
14 #include <xenium/utils.hpp>
15 
16 #include <atomic>
17 
18 namespace xenium {
19 
20 namespace policy {
25  template <std::size_t Value>
26  struct buckets;
27 
36  template <class T>
37  struct map_to_bucket;
38 
48  template <bool Value>
49  struct memoize_hash;
50 }
51 
85 template <class Key, class Value, class... Policies>
87 {
88 public:
89  using value_type = std::pair<const Key, Value>;
90  using reclaimer = parameter::type_param_t<policy::reclaimer, parameter::nil, Policies...>;
91  using hash = parameter::type_param_t<policy::hash, xenium::hash<Key>, Policies...>;
92  using map_to_bucket = parameter::type_param_t<policy::map_to_bucket, utils::modulo<std::size_t>, Policies...>;
93  using backoff = parameter::type_param_t<policy::backoff, no_backoff, Policies...>;
94  static constexpr std::size_t num_buckets = parameter::value_param_t<std::size_t, policy::buckets, 512, Policies...>::value;
95  static constexpr bool memoize_hash =
96  parameter::value_param_t<bool, policy::memoize_hash, !std::is_scalar<Key>::value, Policies...>::value;
97 
98  template <class... NewPolicies>
99  using with = harris_michael_hash_map<Key, Value, NewPolicies..., Policies...>;
100 
101  static_assert(parameter::is_set<reclaimer>::value, "reclaimer policy must be specified");
102 
103  class iterator;
104  class accessor;
105 
106  harris_michael_hash_map() = default;
108 
123  template <class... Args>
124  bool emplace(Args&&... args);
125 
142  template <class... Args>
143  std::pair<iterator, bool> emplace_or_get(Args&&... args);
144 
162  template <class... Args>
163  std::pair<iterator, bool> get_or_emplace(Key key, Args&&... args);
164 
184  template <class Factory>
185  std::pair<iterator, bool> get_or_emplace_lazy(Key key, Factory factory);
186 
197  bool erase(const Key& key);
198 
209  iterator erase(iterator pos);
210 
220  iterator find(const Key& key);
221 
230  bool contains(const Key& key);
231 
239  accessor operator[](const Key& key);
240 
245  iterator begin();
246 
253  iterator end();
254 
255 private:
256  struct node;
257  using hash_t = std::size_t;
258  using concurrent_ptr = typename reclaimer::template concurrent_ptr<node, 1>;
259  using marked_ptr = typename concurrent_ptr::marked_ptr;
260  using guard_ptr = typename concurrent_ptr::guard_ptr;
261 
262  template <typename Factory>
263  std::pair<iterator, bool> do_get_or_emplace_lazy(Key key, Factory node_factory);
264 
265  struct construct_without_hash {};
266 
267  struct data_without_hash
268  {
269  value_type value;
270  template <class... Args>
271  data_without_hash(hash_t /*hash*/, Args&&... args) :
272  value(std::forward<Args>(args)...)
273  {}
274  template <class... Args>
275  data_without_hash(construct_without_hash, Args&&... args) :
276  value(std::forward<Args>(args)...)
277  {}
278  hash_t get_hash() const { return hash{}(value.first); }
279  bool greater_or_equal(hash_t /*h*/, const Key& key) const { return value.first >= key; }
280  };
281 
282  struct data_with_hash
283  {
284  hash_t hash;
285  value_type value;
286  template <class... Args>
287  data_with_hash(hash_t hash, Args&&... args) :
288  hash(hash), value(std::forward<Args>(args)...)
289  {}
290  template <class... Args>
291  data_with_hash(construct_without_hash, Args&&... args) :
292  value(std::forward<Args>(args)...)
293  {
294  hash = harris_michael_hash_map::hash{}(value.first);
295  }
296  hash_t get_hash() const { return hash; }
297  bool greater_or_equal(hash_t h, const Key& key) const { return hash >= h && value.first >= key; }
298  };
299 
300  using data_t = std::conditional_t<memoize_hash, data_with_hash, data_without_hash>;
301 
302 
303  struct node : reclaimer::template enable_concurrent_ptr<node, 1>
304  {
305  data_t data;
306  concurrent_ptr next;
307  template <class... Args>
308  node(Args&&... args) :
309  data(std::forward<Args>(args)...), next()
310  {}
311  };
312 
313  struct find_info
314  {
315  concurrent_ptr* prev;
316  marked_ptr next{};
317  guard_ptr cur{};
318  guard_ptr save{};
319  };
320 
321  bool find(hash_t hash, const Key& key, std::size_t bucket, find_info& info, backoff& backoff);
322 
323  concurrent_ptr buckets[num_buckets];
324 };
325 
339 template <class Key, class Value, class... Policies>
340 class harris_michael_hash_map<Key, Value, Policies...>::iterator {
341 public:
342  using iterator_category = std::forward_iterator_tag;
343  using value_type = harris_michael_hash_map::value_type;
344  using difference_type = std::ptrdiff_t;
345  using pointer = value_type*;
346  using reference = value_type&;
347 
348  iterator(iterator&&) = default;
349  iterator(const iterator&) = default;
350 
351  iterator& operator=(iterator&&) = default;
352  iterator& operator=(const iterator&) = default;
353 
354  iterator& operator++()
355  {
356  assert(info.cur.get() != nullptr);
357  auto next = info.cur->next.load(std::memory_order_relaxed);
358  guard_ptr tmp_guard;
359  // (1) - this acquire-load synchronizes-with the release-CAS (8, 9, 10, 12, 15)
360  if (next.mark() == 0 && tmp_guard.acquire_if_equal(info.cur->next, next, std::memory_order_acquire))
361  {
362  info.prev = &info.cur->next;
363  info.save = std::move(info.cur);
364  info.cur = std::move(tmp_guard);
365  }
366  else
367  {
368  // cur is marked for removal
369  // -> use find to remove it and get to the next node with a key >= cur->key
370  // Note: we have to copy key here!
371  Key key = info.cur->data.value.first;
372  hash_t h = info.cur->data.get_hash();
373  backoff backoff;
374  map->find(h, key, bucket, info, backoff);
375  }
376  assert(info.prev == &map->buckets[bucket] ||
377  info.cur.get() == nullptr ||
378  (info.save.get() != nullptr && &info.save->next == info.prev));
379 
380  if (!info.cur)
381  move_to_next_bucket();
382 
383  return *this;
384  }
385  iterator operator++(int)
386  {
387  iterator retval = *this;
388  ++(*this);
389  return retval;
390  }
391  bool operator==(const iterator& other) const { return info.cur.get() == other.info.cur.get(); }
392  bool operator!=(const iterator& other) const { return !(*this == other); }
393  reference operator*() const noexcept { return info.cur->data.value; }
394  pointer operator->() const noexcept { return &info.cur->data.value; }
395 
396  void reset() {
397  bucket = num_buckets;
398  info.prev = nullptr;
399  info.cur.reset();
400  info.save.reset();
401  }
402 
403 private:
405 
406  explicit iterator(harris_michael_hash_map* map) :
407  map(map),
408  bucket(num_buckets)
409  {}
410 
411  explicit iterator(harris_michael_hash_map* map, std::size_t bucket) :
412  map(map),
413  bucket(bucket)
414  {
415  info.prev = &map->buckets[bucket];
416  // (2) - this acquire-load synchronizes-with the release-CAS (8, 9, 10, 12, 15)
417  info.cur.acquire(*info.prev, std::memory_order_acquire);
418 
419  if (!info.cur)
420  move_to_next_bucket();
421  }
422 
423  explicit iterator(harris_michael_hash_map* map, std::size_t bucket, find_info&& info) :
424  map(map),
425  bucket(bucket),
426  info(std::move(info))
427  {}
428 
429  void move_to_next_bucket() {
430  info.save.reset();
431  while (!info.cur && bucket < num_buckets - 1) {
432  ++bucket;
433  info.prev = &map->buckets[bucket];
434  // (3) - this acquire-load synchronizes-with the release-CAS (8, 9, 10, 12, 15)
435  info.cur.acquire(*info.prev, std::memory_order_acquire);
436  }
437  }
438 
440  std::size_t bucket;
441  find_info info;
442 };
443 
453 template <class Key, class Value, class... Policies>
454 class harris_michael_hash_map<Key, Value, Policies...>::accessor {
455 public:
456  Value* operator->() const noexcept { return &guard->data.value.second; }
457  Value& operator*() const noexcept { return guard->data.value.second; }
458  void reset() { guard.reset(); }
459 private:
460  accessor(guard_ptr&& guard): guard(std::move(guard)) {}
461  guard_ptr guard;
463 };
464 
465 template <class Key, class Value, class... Policies>
467 {
468  for (std::size_t i = 0; i < num_buckets; ++i)
469  {
470  // (4) - this acquire-load synchronizes-with the release-CAS (8, 9, 10, 12, 15)
471  auto p = buckets[i].load(std::memory_order_acquire);
472  while (p)
473  {
474  // (5) - this acquire-load synchronizes-with the release-CAS (8, 9, 10, 12, 15)
475  auto next = p->next.load(std::memory_order_acquire);
476  delete p.get();
477  p = next;
478  }
479  }
480 }
481 
482 template <class Key, class Value, class... Policies>
483 bool harris_michael_hash_map<Key, Value, Policies...>::find(hash_t hash, const Key& key, std::size_t bucket,
484  find_info& info, backoff& backoff)
485 {
486  auto& head = buckets[bucket];
487  assert((info.save == nullptr && info.prev == &head) || &info.save->next == info.prev);
488  concurrent_ptr* start = info.prev;
489  guard_ptr start_guard = info.save; // we have to keep a guard_ptr to prevent start's node from getting reclaimed.
490 retry:
491  info.prev = start;
492  info.save = start_guard;
493  info.next = info.prev->load(std::memory_order_relaxed);
494  if (info.next.mark() != 0) {
495  // our start node is marked for removal -> we have to restart from head
496  start = &head;
497  start_guard.reset();
498  goto retry;
499  }
500 
501  for (;;)
502  {
503  // (6) - this acquire-load synchronizes-with the release-CAS (8, 9, 10, 12, 15)
504  if (!info.cur.acquire_if_equal(*info.prev, info.next, std::memory_order_acquire))
505  goto retry;
506 
507  if (!info.cur)
508  return false;
509 
510  info.next = info.cur->next.load(std::memory_order_relaxed);
511  if (info.next.mark() != 0)
512  {
513  // Node *cur is marked for deletion -> update the link and retire the element
514 
515  // (7) - this acquire-load synchronizes-with the release-CAS (8, 9, 10, 12, 15)
516  info.next = info.cur->next.load(std::memory_order_acquire).get();
517 
518  // Try to splice out node
519  marked_ptr expected = info.cur.get();
520  // (8) - this release-CAS synchronizes with the acquire-load (1, 2, 3, 4, 5, 6, 7, 13)
521  // and the acquire-CAS (11, 14)
522  // it is the head of a potential release sequence containing (11, 14)
523  if (!info.prev->compare_exchange_weak(expected, info.next,
524  std::memory_order_release,
525  std::memory_order_relaxed))
526  {
527  backoff();
528  goto retry;
529  }
530  info.cur.reclaim();
531  }
532  else
533  {
534  if (info.prev->load(std::memory_order_relaxed) != info.cur.get())
535  goto retry; // cur might be cut from the hash_map.
536 
537  const auto& data = info.cur->data;
538  if (data.greater_or_equal(hash, key))
539  return data.value.first == key;
540 
541  info.prev = &info.cur->next;
542  std::swap(info.save, info.cur);
543  }
544  }
545 }
546 
547 template <class Key, class Value, class... Policies>
549 {
550  auto h = hash{}(key);
551  auto bucket = map_to_bucket{}(h, num_buckets);
552  find_info info{&buckets[bucket]};
553  backoff backoff;
554  return find(h, key, bucket, info, backoff);
555 }
556 
557 template <class Key, class Value, class... Policies>
559 {
560  auto h = hash{}(key);
561  auto bucket = map_to_bucket{}(h, num_buckets);
562  find_info info{&buckets[bucket]};
563  backoff backoff;
564  if (find(h, key, bucket, info, backoff))
565  return iterator(this, bucket, std::move(info));
566  return end();
567 }
568 
569 template <class Key, class Value, class... Policies>
570 template <class... Args>
572 {
573  auto result = emplace_or_get(std::forward<Args>(args)...);
574  return result.second;
575 }
576 
577 template <class Key, class Value, class... Policies>
578 template <class... Args>
580 -> std::pair<iterator, bool>
581 {
582  return do_get_or_emplace_lazy(std::move(key), [&args...](hash_t hash, Key key) {
583  return new node(hash, std::piecewise_construct,
584  std::forward_as_tuple(std::move(key)),
585  std::forward_as_tuple(std::forward<Args>(args)...));
586  });
587 }
588 
589 template <class Key, class Value, class... Policies>
590 template <typename Factory>
592  -> std::pair<iterator, bool>
593 {
594  return do_get_or_emplace_lazy(std::move(key), [&value_factory](hash_t hash, Key key) {
595  return new node(hash, std::move(key), value_factory());
596  });
597 }
598 
599 template <class Key, class Value, class... Policies>
600 template <typename Factory>
601 auto harris_michael_hash_map<Key, Value, Policies...>::do_get_or_emplace_lazy(Key key, Factory node_factory)
602  -> std::pair<iterator, bool>
603 {
604  node* n = nullptr;
605  auto h = hash{}(key);
606  auto bucket = map_to_bucket{}(h, num_buckets);
607 
608  const Key* pkey = &key;
609  find_info info{&buckets[bucket]};
610  backoff backoff;
611  for (;;)
612  {
613  if (find(h, *pkey, bucket, info, backoff))
614  {
615  delete n;
616  return {iterator(this, bucket, std::move(info)), false};
617  }
618  if (n == nullptr) {
619  n = node_factory(h, std::move(key));
620  pkey = &n->data.value.first;
621  }
622 
623  // Try to install new node
624  marked_ptr cur = info.cur.get();
625  info.cur.reset();
626  info.cur = guard_ptr(n);
627  n->next.store(cur, std::memory_order_relaxed);
628 
629  // (9) - this release-CAS synchronizes with the acquire-load (1, 2, 3, 4, 5, 6, 7, 13)
630  // and the acquire-CAS (11, 14)
631  // it is the head of a potential release sequence containing (11, 14)
632  if (info.prev->compare_exchange_weak(cur, n,
633  std::memory_order_release,
634  std::memory_order_relaxed))
635  return {iterator(this, bucket, std::move(info)), true};
636 
637  backoff();
638  }
639 }
640 
641 template <class Key, class Value, class... Policies>
642 template <class... Args>
644  -> std::pair<iterator, bool>
645 {
646  node* n = new node(construct_without_hash{}, std::forward<Args>(args)...);
647 
648  auto h = n->data.get_hash();
649  auto bucket = map_to_bucket{}(h, num_buckets);
650 
651  find_info info{&buckets[bucket]};
652  backoff backoff;
653  for (;;)
654  {
655  if (find(h, n->data.value.first, bucket, info, backoff))
656  {
657  delete n;
658  return {iterator(this, bucket, std::move(info)), false};
659  }
660  // Try to install new node
661  marked_ptr expected = info.cur.get();
662  n->next.store(expected, std::memory_order_relaxed);
663  guard_ptr new_guard(n);
664 
665  // (10) - this release-CAS synchronizes with the acquire-load (1, 2, 3, 4, 5, 6, 7, 13)
666  // and the acquire-CAS (11, 14)
667  // it is the head of a potential release sequence containing (11, 14)
668  if (info.prev->compare_exchange_weak(expected, n,
669  std::memory_order_release,
670  std::memory_order_relaxed)) {
671  info.cur = std::move(new_guard);
672  return {iterator(this, bucket, std::move(info)), true};
673  }
674 
675  backoff();
676  }
677 }
678 
679 template <class Key, class Value, class... Policies>
681 {
682  auto h = hash{}(key);
683  auto bucket = map_to_bucket{}(h, num_buckets);
684  backoff backoff;
685  find_info info{&buckets[bucket]};
686  // Find node in hash_map with matching key and mark it for erasure.
687  do
688  {
689  if (!find(h, key, bucket, info, backoff))
690  return false; // No such node in the hash_map
691  // (11) - this acquire-CAS synchronizes with the release-CAS (8, 9, 10, 12, 15)
692  // and is part of a release sequence headed by those operations
693  } while (!info.cur->next.compare_exchange_weak(info.next,
694  marked_ptr(info.next.get(), 1),
695  std::memory_order_acquire,
696  std::memory_order_relaxed));
697 
698  assert(info.next.mark() == 0);
699  assert(info.cur.mark() == 0);
700 
701  // Try to splice out node
702  marked_ptr expected = info.cur;
703  // (12) - this release-CAS synchronizes with the acquire-load (1, 2, 3, 4, 5, 6, 7, 13)
704  // and the acquire-CAS (11, 14)
705  // it is the head of a potential release sequence containing (11, 14)
706  if (info.prev->compare_exchange_weak(expected, info.next.get(),
707  std::memory_order_release,
708  std::memory_order_relaxed))
709  info.cur.reclaim();
710  else
711  // Another thread interfered -> rewalk the bucket's list to ensure
712  // reclamation of marked node before returning.
713  find(h, key, bucket, info, backoff);
714 
715  return true;
716 }
717 
718 template <class Key, class Value, class... Policies>
720 {
721  backoff backoff;
722  // (13) - this acquire-load synchronizes-with the release-CAS (8, 9, 10, 12, 15)
723  auto next = pos.info.cur->next.load(std::memory_order_acquire);
724  while (next.mark() == 0)
725  {
726  // (14) - this acquire-CAS synchronizes with the release-CAS (8, 9, 10, 12, 15)
727  // and is part of a release sequence headed by those operations
728  if (pos.info.cur->next.compare_exchange_weak(next,
729  marked_ptr(next.get(), 1),
730  std::memory_order_acquire))
731  break;
732 
733  backoff();
734  }
735 
736  guard_ptr next_guard(next.get());
737  assert(pos.info.cur.mark() == 0);
738 
739  // Try to splice out node
740  marked_ptr expected = pos.info.cur;
741  // (15) - this release-CAS synchronizes with the acquire-load (1, 2, 3, 4, 5, 6, 7, 13)
742  // and the acquire-CAS (11, 14)
743  // it is the head of a potential release sequence containing (11, 14)
744  if (pos.info.prev->compare_exchange_weak(expected, next_guard,
745  std::memory_order_release,
746  std::memory_order_relaxed)) {
747  pos.info.cur.reclaim();
748  pos.info.cur = std::move(next_guard);
749  } else {
750  next_guard.reset();
751  Key key = pos.info.cur->data.value.first;
752  hash_t h = pos.info.cur->data.get_hash();
753 
754  // Another thread interfered -> rewalk the list to ensure reclamation of marked node before returning.
755  find(h, key, pos.bucket, pos.info, backoff);
756  }
757 
758  if (!pos.info.cur)
759  pos.move_to_next_bucket();
760 
761  return pos;
762 }
763 
764 template <class Key, class Value, class... Policies>
766 {
767  auto result = get_or_emplace_lazy(key, []() { return Value{}; });
768  return accessor(std::move(result.first.info.cur));
769 }
770 
771 template <class Key, class Value, class... Policies>
773 {
774  return iterator(this, 0);
775 }
776 
777 template <class Key, class Value, class... Policies>
779 {
780  return iterator(this);
781 }
782 }
783 
784 #endif
An accessor to safely access the value of an element.
Definition: harris_michael_hash_map.hpp:454
A ForwardIterator to safely iterate the hash-map.
Definition: harris_michael_hash_map.hpp:340
A generic lock-free hash-map.
Definition: harris_michael_hash_map.hpp:87
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 ...
std::pair< iterator, bool > get_or_emplace(Key key, Args &&... args)
Inserts a new element into the container if the container doesn't already contain an element with an ...
iterator end()
Returns an iterator to the element following the last element of the container.
Definition: harris_michael_hash_map.hpp:778
bool erase(const Key &key)
Removes the element with the key equivalent to key (if one exists).
Definition: harris_michael_hash_map.hpp:680
bool contains(const Key &key)
Checks if there is an element with key equivalent to key in the container.
Definition: harris_michael_hash_map.hpp:548
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_hash_map.hpp:571
accessor operator[](const Key &key)
The accessor
Definition: harris_michael_hash_map.hpp:765
std::pair< iterator, bool > get_or_emplace_lazy(Key key, Factory factory)
Inserts a new element into the container if the container doesn't already contain an element with an ...
iterator find(const Key &key)
Finds an element with key equivalent to key.
Definition: harris_michael_hash_map.hpp:558
iterator begin()
Returns an iterator to the first element of the container.
Definition: harris_michael_hash_map.hpp:772
Slim wrapper around std::hash with specialization for pointer types.
Definition: hash.hpp:25
Dummy backoff strategy that does nothing.
Definition: backoff.hpp:17
Policy to configure the backoff strategy.
Definition: policy.hpp:39
Policy to configure the number of buckets in harris_michael_hash_map.
Definition: harris_michael_hash_map.hpp:26
Policy to configure the function that maps the hash value to a bucket in harris_michael_hash_map.
Definition: harris_michael_hash_map.hpp:37
Policy to configure whether the hash value should be stored and used during lookup operations in harr...
Definition: harris_michael_hash_map.hpp:49
Policy to configure the reclamation scheme to be used.
Definition: policy.hpp:25