xenium
vyukov_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_VYUKOV_HASH_MAP_HPP
7#define XENIUM_VYUKOV_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#include <cstdint>
18
19namespace xenium {
20
21namespace policy {
30 template <class T>
32}
33
34namespace impl {
35 template <
36 class Key,
37 class Value,
38 class ValueReclaimer,
39 class Reclaimer,
40 bool TrivialKey,
41 bool TrivialValue>
42 struct vyukov_hash_map_traits;
43}
44
52template <class T, class Reclaimer>
54
55namespace detail {
56 template <class T>
57 struct vyukov_supported_type {
58 static constexpr bool value =
59 std::is_trivial<T>::value && (sizeof(T) == 4 || sizeof(T) == 8);
60 };
61 template <class T, class Reclaimer>
62 struct vyukov_supported_type<managed_ptr<T, Reclaimer>> {
63 static_assert(
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;
67 };
68}
69
142template <class Key, class Value, class... Policies>
144 using reclaimer = parameter::type_param_t<policy::reclaimer, parameter::nil, Policies...>;
145 using value_reclaimer = parameter::type_param_t<policy::value_reclaimer, parameter::nil, Policies...>;
146 using hash = parameter::type_param_t<policy::hash, xenium::hash<Key>, Policies...>;
147 using backoff = parameter::type_param_t<policy::backoff, no_backoff, Policies...>;
148
149 template <class... NewPolicies>
150 using with = vyukov_hash_map<Key, Value, NewPolicies..., Policies...>;
151
152 static_assert(parameter::is_set<reclaimer>::value, "reclaimer policy must be specified");
153
154private:
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>;
157
158public:
159 vyukov_hash_map(std::size_t initial_capacity = 128);
161
162 class iterator;
163 using accessor = typename traits::accessor;
164
165 using key_type = typename traits::key_type;
166 using value_type = typename traits::value_type;
167
181 bool emplace(key_type key, value_type value);
182
198 template <class... Args>
199 std::pair<accessor, bool> get_or_emplace(key_type key, Args&&... args);
200
219 template <class Factory>
220 std::pair<accessor, bool> get_or_emplace_lazy(key_type key, Factory&& factory);
221
234 bool extract(const key_type& key, accessor& accessor);
235
246 bool erase(const key_type& key);
247
258 void erase(iterator& pos);
259
272 bool try_get_value(const key_type& key, accessor& result) const;
273
274 // TODO - implement contains
275 //bool contains(const key_type& key) const;
276
286 iterator find(const key_type& key);
287
295 iterator begin();
296
305 iterator end() { return iterator(); }
306private:
307 struct unlocker;
308
309 struct bucket_state;
310 struct bucket;
311 struct extension_item;
312 struct extension_bucket;
313 struct block;
314 using block_ptr = typename reclaimer::template concurrent_ptr<block, 0>;
315 using guarded_block = typename block_ptr::guard_ptr;
316
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;
320
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;
324
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;
327
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;
330
331 static constexpr std::align_val_t cacheline_size{64};
332
333 block_ptr data_block;
334 std::atomic<int> resize_lock;
335
336 block* allocate_block(std::uint32_t bucket_count);
337
338 bucket& lock_bucket(hash_t hash, guarded_block& block, bucket_state& state);
339 void grow(bucket& bucket, bucket_state state);
340 void do_grow();
341
342 template <bool AcquireAccessor, class Factory, class Callback>
343 bool do_get_or_emplace(Key&& key, Factory&& factory, Callback&& callback);
344
345 bool do_extract(const key_type& key, accessor& value);
346
347 static extension_item* allocate_extension_item(block* b, hash_t hash);
348 static void free_extension_item(extension_item* item);
349};
350
369template <class Key, class Value, class... Policies>
370class vyukov_hash_map<Key, Value, Policies...>::iterator {
371public:
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*;
377
378 iterator();
379 ~iterator();
380
382 iterator& operator=(iterator&&);
383
384 iterator(const iterator&) = delete;
385 iterator& operator=(const iterator&) = delete;
386
387 bool operator==(const iterator& r) const;
388 bool operator!=(const iterator& r) const;
389 iterator& operator++();
390
391 reference operator*();
392 pointer operator->();
393
399 void reset();
400private:
401 guarded_block block;
402 bucket* current_bucket;
403 bucket_state current_bucket_state;
404 std::uint32_t index;
405 extension_item* extension;
406 std::atomic<extension_item*>* prev;
407 friend struct vyukov_hash_map;
408
409 void move_to_next_bucket();
410 Value* erase_current();
411};
412
413}
414
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
419
420#endif
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