6#ifndef XENIUM_VYUKOV_HASH_MAP_HPP
7#define XENIUM_VYUKOV_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>
42 struct vyukov_hash_map_traits;
52template <
class T,
class Reclaimer>
57 struct vyukov_supported_type {
58 static constexpr bool value =
59 std::is_trivial<T>::value && (
sizeof(T) == 4 ||
sizeof(T) == 8);
61 template <
class T,
class Reclaimer>
62 struct vyukov_supported_type<
managed_ptr<T, Reclaimer>> {
64 std::is_base_of<typename Reclaimer::template enable_concurrent_ptr<T>, T>::value,
65 "The type T specified in managed_ptr must derive from Reclaimer::enable_concurrent_ptr");
66 static constexpr bool value =
true;
142template <
class Key,
class Value,
class... Policies>
144 using reclaimer = parameter::type_param_t<
policy::reclaimer, parameter::nil, Policies...>;
146 using hash = parameter::type_param_t<policy::hash, xenium::hash<Key>, Policies...>;
149 template <
class... NewPolicies>
152 static_assert(parameter::is_set<reclaimer>::value,
"reclaimer policy must be specified");
155 using traits =
typename impl::vyukov_hash_map_traits<Key, Value, value_reclaimer, reclaimer,
156 detail::vyukov_supported_type<Key>::value, detail::vyukov_supported_type<Value>::value>;
163 using accessor =
typename traits::accessor;
165 using key_type =
typename traits::key_type;
166 using value_type =
typename traits::value_type;
181 bool emplace(key_type key, value_type value);
198 template <
class... Args>
219 template <
class Factory>
234 bool extract(
const key_type& key, accessor& accessor);
246 bool erase(
const key_type& key);
272 bool try_get_value(
const key_type& key, accessor& result)
const;
311 struct extension_item;
312 struct extension_bucket;
314 using block_ptr =
typename reclaimer::template concurrent_ptr<block, 0>;
315 using guarded_block =
typename block_ptr::guard_ptr;
317 static constexpr std::uint32_t bucket_to_extension_ratio = 128;
318 static constexpr std::uint32_t bucket_item_count = 3;
319 static constexpr std::uint32_t extension_item_count = 10;
321 static constexpr std::size_t item_counter_bits = utils::find_last_bit_set(bucket_item_count);
322 static constexpr std::size_t lock_bit = 2 * item_counter_bits + 1;
323 static constexpr std::size_t version_shift = lock_bit;
325 static constexpr std::uint32_t lock = 1u << (lock_bit - 1);
326 static constexpr std::size_t version_inc =
static_cast<std::size_t
>(1) << lock_bit;
328 static constexpr std::uint32_t item_count_mask = (1u << item_counter_bits) - 1;
329 static constexpr std::uint32_t delete_item_mask = item_count_mask << item_counter_bits;
331 static constexpr std::align_val_t cacheline_size{64};
333 block_ptr data_block;
334 std::atomic<int> resize_lock;
336 block* allocate_block(std::uint32_t bucket_count);
338 bucket& lock_bucket(hash_t hash, guarded_block& block, bucket_state& state);
339 void grow(bucket& bucket, bucket_state state);
342 template <
bool AcquireAccessor,
class Factory,
class Callback>
343 bool do_get_or_emplace(Key&& key, Factory&& factory, Callback&& callback);
345 bool do_extract(
const key_type& key, accessor& value);
347 static extension_item* allocate_extension_item(block* b, hash_t hash);
348 static void free_extension_item(extension_item* item);
369template <
class Key,
class Value,
class... Policies>
372 using iterator_category = std::forward_iterator_tag;
373 using difference_type = std::ptrdiff_t;
374 using value_type =
typename traits::iterator_value_type;
375 using reference =
typename traits::iterator_reference;
376 using pointer = value_type*;
387 bool operator==(
const iterator& r)
const;
388 bool operator!=(
const iterator& r)
const;
391 reference operator*();
392 pointer operator->();
402 bucket* current_bucket;
403 bucket_state current_bucket_state;
405 extension_item* extension;
406 std::atomic<extension_item*>* prev;
409 void move_to_next_bucket();
410 Value* erase_current();
415#define XENIUM_VYUKOV_HASH_MAP_IMPL
416#include <xenium/impl/vyukov_hash_map_traits.hpp>
417#include <xenium/impl/vyukov_hash_map.hpp>
418#undef XENIUM_VYUKOV_HASH_MAP_IMPL
A ForwardIterator to safely iterate vyukov_hash_map.
Definition: vyukov_hash_map.hpp:370
A helper struct to define that the lifetime of value objects of type T has to be managed by the speci...
Definition: vyukov_hash_map.hpp:53
Dummy backoff strategy that does nothing.
Definition: backoff.hpp:17
Policy to configure the backoff strategy.
Definition: policy.hpp:39
Policy to configure the reclamation scheme to be used.
Definition: policy.hpp:25
Policy to configure the reclaimer used for internally alloced nodes in vyukov_hash_map.
Definition: vyukov_hash_map.hpp:31
A concurrent hash-map that uses fine-grained locking.
Definition: vyukov_hash_map.hpp:143
std::pair< accessor, bool > get_or_emplace(key_type key, Args &&... args)
Inserts a new element into the container if the container doesn't already contain an element with an ...
bool try_get_value(const key_type &key, accessor &result) const
Provides an accessor to the value associated with the specified key, if such an element exists in the...
Definition: vyukov_hash_map.hpp:501
bool erase(const key_type &key)
Removes the element with the key equivalent to key (if one exists).
Definition: vyukov_hash_map.hpp:302
bool emplace(key_type key, value_type value)
Inserts a new element into the container if the container doesn't already contain an element with an ...
Definition: vyukov_hash_map.hpp:196
std::pair< accessor, bool > get_or_emplace_lazy(key_type key, Factory &&factory)
Inserts a new element into the container if the container doesn't already contain an element with an ...
bool extract(const key_type &key, accessor &accessor)
Removes the element with the key equivalent to key (if one exists), and provides an accessor to the r...
Definition: vyukov_hash_map.hpp:310
iterator begin()
Returns an iterator to the first element of the container.
Definition: vyukov_hash_map.hpp:777
iterator end()
Returns an iterator to the element following the last element of the container.
Definition: vyukov_hash_map.hpp:305
iterator find(const key_type &key)
Finds an element with key equivalent to key.
Definition: vyukov_hash_map.hpp:748