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 
19 namespace xenium {
20 
21 namespace policy {
30  template <class T>
32 }
33 
34 namespace 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 
52 template <class T, class Reclaimer>
53 struct managed_ptr;
54 
55 namespace 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 
142 template <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 
154 private:
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 
158 public:
159  vyukov_hash_map(std::size_t initial_capacity = 128);
160  ~vyukov_hash_map();
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(); }
306 private:
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 
369 template <class Key, class Value, class... Policies>
370 class vyukov_hash_map<Key, Value, Policies...>::iterator {
371 public:
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 
381  iterator(iterator&&);
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();
400 private:
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_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