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;
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);
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();
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 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