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
18namespace xenium {
19
20namespace policy {
25 template <std::size_t Value>
26 struct buckets;
27
36 template <class T>
38
48 template <bool Value>
50}
51
85template <class Key, class Value, class... Policies>
87{
88public:
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
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
255private:
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
339template <class Key, class Value, class... Policies>
340class harris_michael_hash_map<Key, Value, Policies...>::iterator {
341public:
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
403private:
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
453template <class Key, class Value, class... Policies>
454class harris_michael_hash_map<Key, Value, Policies...>::accessor {
455public:
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(); }
459private:
460 accessor(guard_ptr&& guard): guard(std::move(guard)) {}
461 guard_ptr guard;
463};
464
465template <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
482template <class Key, class Value, class... Policies>
483bool 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.
490retry:
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
547template <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
557template <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
569template <class Key, class Value, class... Policies>
570template <class... Args>
572{
573 auto result = emplace_or_get(std::forward<Args>(args)...);
574 return result.second;
575}
576
577template <class Key, class Value, class... Policies>
578template <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
589template <class Key, class Value, class... Policies>
590template <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
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>
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
641template <class Key, class Value, class... Policies>
642template <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
679template <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
718template <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
764template <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
771template <class Key, class Value, class... Policies>
773{
774 return iterator(this, 0);
775}
776
777template <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
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