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;
52 template <
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;
142 template <
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);
369 template <
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_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 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
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
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 ...
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