6#ifndef XENIUM_HARRIS_MICHAEL_HASH_MAP_HPP
7#define XENIUM_HARRIS_MICHAEL_HASH_MAP_HPP
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>
25 template <std::
size_t Value>
85template <
class Key,
class Value,
class... Policies>
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...>;
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;
98 template <
class... NewPolicies>
101 static_assert(parameter::is_set<reclaimer>::value,
"reclaimer policy must be specified");
123 template <
class... Args>
142 template <
class... Args>
162 template <
class... Args>
184 template <
class Factory>
197 bool erase(
const Key& key);
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;
262 template <
typename Factory>
263 std::pair<iterator, bool> do_get_or_emplace_lazy(Key key, Factory node_factory);
265 struct construct_without_hash {};
267 struct data_without_hash
270 template <
class... Args>
271 data_without_hash(hash_t , Args&&... args) :
272 value(std::forward<Args>(args)...)
274 template <
class... Args>
275 data_without_hash(construct_without_hash, Args&&... args) :
276 value(std::forward<Args>(args)...)
278 hash_t get_hash()
const {
return hash{}(value.first); }
279 bool greater_or_equal(hash_t ,
const Key& key)
const {
return value.first >= key; }
282 struct data_with_hash
286 template <
class... Args>
287 data_with_hash(hash_t hash, Args&&... args) :
288 hash(hash), value(std::forward<Args>(args)...)
290 template <
class... Args>
291 data_with_hash(construct_without_hash, Args&&... args) :
292 value(std::forward<Args>(args)...)
294 hash = harris_michael_hash_map::hash{}(value.first);
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; }
300 using data_t = std::conditional_t<memoize_hash, data_with_hash, data_without_hash>;
303 struct node : reclaimer::template enable_concurrent_ptr<node, 1>
307 template <
class... Args>
308 node(Args&&... args) :
309 data(std::forward<Args>(args)...), next()
315 concurrent_ptr* prev;
321 bool find(hash_t hash,
const Key& key, std::size_t bucket, find_info& info, backoff& backoff);
323 concurrent_ptr buckets[num_buckets];
339template <
class Key,
class Value,
class... Policies>
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&;
356 assert(info.cur.get() !=
nullptr);
357 auto next = info.cur->next.load(std::memory_order_relaxed);
360 if (next.mark() == 0 && tmp_guard.acquire_if_equal(info.cur->next, next, std::memory_order_acquire))
362 info.prev = &info.cur->next;
363 info.save = std::move(info.cur);
364 info.cur = std::move(tmp_guard);
371 Key key = info.cur->data.value.first;
372 hash_t h = info.cur->data.get_hash();
374 map->find(h, key, bucket, info, backoff);
376 assert(info.prev == &map->buckets[bucket] ||
377 info.cur.get() ==
nullptr ||
378 (info.save.get() !=
nullptr && &info.save->next == info.prev));
381 move_to_next_bucket();
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; }
397 bucket = num_buckets;
415 info.prev = &map->buckets[bucket];
417 info.cur.acquire(*info.prev, std::memory_order_acquire);
420 move_to_next_bucket();
426 info(std::move(info))
429 void move_to_next_bucket() {
431 while (!info.cur && bucket < num_buckets - 1) {
433 info.prev = &map->buckets[bucket];
435 info.cur.acquire(*info.prev, std::memory_order_acquire);
453template <
class Key,
class Value,
class... Policies>
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(); }
460 accessor(guard_ptr&& guard): guard(std::move(guard)) {}
465template <
class Key,
class Value,
class... Policies>
468 for (std::size_t i = 0; i < num_buckets; ++i)
471 auto p = buckets[i].load(std::memory_order_acquire);
475 auto next = p->next.load(std::memory_order_acquire);
482template <
class Key,
class Value,
class... Policies>
484 find_info& info, backoff& backoff)
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;
492 info.save = start_guard;
493 info.next = info.prev->load(std::memory_order_relaxed);
494 if (info.next.mark() != 0) {
504 if (!info.cur.acquire_if_equal(*info.prev, info.next, std::memory_order_acquire))
510 info.next = info.cur->next.load(std::memory_order_relaxed);
511 if (info.next.mark() != 0)
516 info.next = info.cur->next.load(std::memory_order_acquire).get();
519 marked_ptr expected = info.cur.get();
523 if (!info.prev->compare_exchange_weak(expected, info.next,
524 std::memory_order_release,
525 std::memory_order_relaxed))
534 if (info.prev->load(std::memory_order_relaxed) != info.cur.get())
537 const auto& data = info.cur->data;
538 if (data.greater_or_equal(hash, key))
539 return data.value.first == key;
541 info.prev = &info.cur->next;
542 std::swap(info.save, info.cur);
547template <
class Key,
class Value,
class... Policies>
550 auto h = hash{}(key);
551 auto bucket = map_to_bucket{}(h, num_buckets);
552 find_info info{&buckets[bucket]};
554 return find(h, key, bucket, info, backoff);
557template <
class Key,
class Value,
class... Policies>
560 auto h = hash{}(key);
561 auto bucket = map_to_bucket{}(h, num_buckets);
562 find_info info{&buckets[bucket]};
564 if (find(h, key, bucket, info, backoff))
565 return iterator(
this, bucket, std::move(info));
569template <
class Key,
class Value,
class... Policies>
570template <
class... Args>
573 auto result = emplace_or_get(std::forward<Args>(args)...);
574 return result.second;
577template <
class Key,
class Value,
class... Policies>
578template <
class... Args>
580-> std::pair<iterator, bool>
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)...));
589template <
class Key,
class Value,
class... Policies>
590template <
typename Factory>
592 -> std::pair<iterator, bool>
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());
599template <
class Key,
class Value,
class... Policies>
600template <
typename Factory>
601auto harris_michael_hash_map<Key, Value, Policies...>::do_get_or_emplace_lazy(Key key, Factory node_factory)
602 -> std::pair<iterator, bool>
605 auto h = hash{}(key);
606 auto bucket = map_to_bucket{}(h, num_buckets);
608 const Key* pkey = &key;
609 find_info info{&buckets[bucket]};
613 if (find(h, *pkey, bucket, info, backoff))
616 return {iterator(
this, bucket, std::move(info)),
false};
619 n = node_factory(h, std::move(key));
620 pkey = &n->data.value.first;
624 marked_ptr cur = info.cur.get();
626 info.cur = guard_ptr(n);
627 n->next.store(cur, std::memory_order_relaxed);
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};
641template <
class Key,
class Value,
class... Policies>
642template <
class... Args>
644 -> std::pair<iterator, bool>
646 node* n =
new node(construct_without_hash{}, std::forward<Args>(args)...);
648 auto h = n->data.get_hash();
649 auto bucket = map_to_bucket{}(h, num_buckets);
651 find_info info{&buckets[bucket]};
655 if (find(h, n->data.value.first, bucket, info, backoff))
658 return {iterator(
this, bucket, std::move(info)),
false};
661 marked_ptr expected = info.cur.get();
662 n->next.store(expected, std::memory_order_relaxed);
663 guard_ptr new_guard(n);
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};
679template <
class Key,
class Value,
class... Policies>
682 auto h = hash{}(key);
683 auto bucket = map_to_bucket{}(h, num_buckets);
685 find_info info{&buckets[bucket]};
689 if (!find(h, key, bucket, info, backoff))
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));
698 assert(info.next.mark() == 0);
699 assert(info.cur.mark() == 0);
702 marked_ptr expected = info.cur;
706 if (info.prev->compare_exchange_weak(expected, info.next.get(),
707 std::memory_order_release,
708 std::memory_order_relaxed))
713 find(h, key, bucket, info, backoff);
718template <
class Key,
class Value,
class... Policies>
723 auto next = pos.info.cur->next.load(std::memory_order_acquire);
724 while (next.mark() == 0)
728 if (pos.info.cur->next.compare_exchange_weak(next,
729 marked_ptr(next.get(), 1),
730 std::memory_order_acquire))
736 guard_ptr next_guard(next.get());
737 assert(pos.info.cur.mark() == 0);
740 marked_ptr expected = pos.info.cur;
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);
751 Key key = pos.info.cur->data.value.first;
752 hash_t h = pos.info.cur->data.get_hash();
755 find(h, key, pos.bucket, pos.info, backoff);
759 pos.move_to_next_bucket();
764template <
class Key,
class Value,
class... Policies>
767 auto result = get_or_emplace_lazy(key, []() {
return Value{}; });
768 return accessor(std::move(result.first.info.cur));
771template <
class Key,
class Value,
class... Policies>
777template <
class Key,
class Value,
class... Policies>
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
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 > 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_lazy(Key key, Factory factory)
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 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