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
xenium::vyukov_hash_map::iterator
A ForwardIterator to safely iterate vyukov_hash_map.
Definition: vyukov_hash_map.hpp:370
xenium::vyukov_hash_map::emplace
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
xenium::vyukov_hash_map::find
iterator find(const key_type &key)
Finds an element with key equivalent to key.
Definition: vyukov_hash_map.hpp:748
xenium::vyukov_hash_map
A concurrent hash-map that uses fine-grained locking.
Definition: vyukov_hash_map.hpp:143
xenium::policy::backoff
Policy to configure the backoff strategy.
Definition: policy.hpp:39
xenium::vyukov_hash_map::end
iterator end()
Returns an iterator to the element following the last element of the container.
Definition: vyukov_hash_map.hpp:305
xenium::policy::value_reclaimer
Policy to configure the reclaimer used for internally alloced nodes in vyukov_hash_map.
Definition: vyukov_hash_map.hpp:31
xenium::vyukov_hash_map::get_or_emplace_lazy
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 ...
xenium::vyukov_hash_map::extract
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
xenium::vyukov_hash_map::erase
bool erase(const key_type &key)
Removes the element with the key equivalent to key (if one exists).
Definition: vyukov_hash_map.hpp:302
xenium::managed_ptr
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
xenium::vyukov_hash_map::get_or_emplace
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 ...
xenium::policy::reclaimer
Policy to configure the reclamation scheme to be used.
Definition: policy.hpp:25
xenium::no_backoff
Dummy backoff strategy that does nothing.
Definition: backoff.hpp:17
xenium::vyukov_hash_map::try_get_value
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
xenium::vyukov_hash_map::begin
iterator begin()
Returns an iterator to the first element of the container.
Definition: vyukov_hash_map.hpp:777