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
xenium::harris_michael_hash_map::get_or_emplace_lazy
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 ...
xenium::policy::backoff
Policy to configure the backoff strategy.
Definition: policy.hpp:39
xenium::harris_michael_hash_map::end
iterator end()
Returns an iterator to the element following the last element of the container.
Definition: harris_michael_hash_map.hpp:778
xenium::harris_michael_hash_map::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_hash_map::operator[]
accessor operator[](const Key &key)
The accessor
Definition: harris_michael_hash_map.hpp:765
xenium::harris_michael_hash_map::find
iterator find(const Key &key)
Finds an element with key equivalent to key.
Definition: harris_michael_hash_map.hpp:558
xenium::harris_michael_hash_map::begin
iterator begin()
Returns an iterator to the first element of the container.
Definition: harris_michael_hash_map.hpp:772
xenium::harris_michael_hash_map::accessor
An accessor to safely access the value of an element.
Definition: harris_michael_hash_map.hpp:454
xenium::hash
Slim wrapper around std::hash with specialization for pointer types.
Definition: hash.hpp:25
xenium::policy::buckets
Policy to configure the number of buckets in harris_michael_hash_map.
Definition: harris_michael_hash_map.hpp:26
xenium::harris_michael_hash_map::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_hash_map.hpp:571
xenium::policy::reclaimer
Policy to configure the reclamation scheme to be used.
Definition: policy.hpp:25
xenium::policy::memoize_hash
Policy to configure whether the hash value should be stored and used during lookup operations in harr...
Definition: harris_michael_hash_map.hpp:49
xenium::no_backoff
Dummy backoff strategy that does nothing.
Definition: backoff.hpp:17
xenium::harris_michael_hash_map::erase
bool erase(const Key &key)
Removes the element with the key equivalent to key (if one exists).
Definition: harris_michael_hash_map.hpp:680
xenium::harris_michael_hash_map::get_or_emplace
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 ...
xenium::harris_michael_hash_map::iterator
A ForwardIterator to safely iterate the hash-map.
Definition: harris_michael_hash_map.hpp:340
xenium::policy::map_to_bucket
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
xenium::harris_michael_hash_map
A generic lock-free hash-map.
Definition: harris_michael_hash_map.hpp:87
xenium::harris_michael_hash_map::contains
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