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