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>
85 template <
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];
339 template <
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);
453 template <
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)) {}
465 template <
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);
482 template <
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);
547 template <
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);
557 template <
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));
569 template <
class Key,
class Value,
class... Policies>
570 template <
class... Args>
573 auto result = emplace_or_get(std::forward<Args>(args)...);
574 return result.second;
577 template <
class Key,
class Value,
class... Policies>
578 template <
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)...));
589 template <
class Key,
class Value,
class... Policies>
590 template <
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());
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>
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};
641 template <
class Key,
class Value,
class... Policies>
642 template <
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};
679 template <
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);
718 template <
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();
764 template <
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));
771 template <
class Key,
class Value,
class... Policies>
777 template <
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
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