vyukov_hash_map.hpp

//
// Copyright (c) 2018-2020 Manuel Pöter.
// Licensed under the MIT License. See LICENSE file in the project root for full license information.
//
 
#ifndef XENIUM_VYUKOV_HASH_MAP_HPP
#define XENIUM_VYUKOV_HASH_MAP_HPP
 
#include <xenium/acquire_guard.hpp>
#include <xenium/backoff.hpp>
#include <xenium/hash.hpp>
#include <xenium/parameter.hpp>
#include <xenium/policy.hpp>
#include <xenium/utils.hpp>
 
#include <atomic>
#include <cstdint>
 
namespace xenium {
 
namespace policy {
  template <class T>
  struct value_reclaimer;
} // namespace policy
 
namespace impl {
  template <class Key, class Value, class ValueReclaimer, class Reclaimer, bool TrivialKey, bool TrivialValue>
  struct vyukov_hash_map_traits;
} // namespace impl
 
template <class T, class Reclaimer>
struct managed_ptr;
 
namespace detail {
  template <class T>
  struct vyukov_supported_type {
    static constexpr bool value = std::is_trivial<T>::value && (sizeof(T) == 4 || sizeof(T) == 8);
  };
  template <class T, class Reclaimer>
  struct vyukov_supported_type<managed_ptr<T, Reclaimer>> {
    static_assert(std::is_base_of<typename Reclaimer::template enable_concurrent_ptr<T>, T>::value,
                  "The type T specified in managed_ptr must derive from Reclaimer::enable_concurrent_ptr");
    static constexpr bool value = true;
  };
} // namespace detail
 
template <class Key, class Value, class... Policies>
struct vyukov_hash_map {
  using reclaimer = parameter::type_param_t<policy::reclaimer, parameter::nil, Policies...>;
  using value_reclaimer = parameter::type_param_t<policy::value_reclaimer, parameter::nil, Policies...>;
  using hash = parameter::type_param_t<policy::hash, xenium::hash<Key>, Policies...>;
  using backoff = parameter::type_param_t<policy::backoff, no_backoff, Policies...>;
 
  template <class... NewPolicies>
  using with = vyukov_hash_map<Key, Value, NewPolicies..., Policies...>;
 
  static_assert(parameter::is_set<reclaimer>::value, "reclaimer policy must be specified");
 
private:
  using traits = typename impl::vyukov_hash_map_traits<Key,
                                                       Value,
                                                       value_reclaimer,
                                                       reclaimer,
                                                       detail::vyukov_supported_type<Key>::value,
                                                       detail::vyukov_supported_type<Value>::value>;
 
public:
  explicit vyukov_hash_map(std::size_t initial_capacity = 128);
  ~vyukov_hash_map();
 
  class iterator;
  using accessor = typename traits::accessor;
 
  using key_type = typename traits::key_type;
  using value_type = typename traits::value_type;
 
  bool emplace(key_type key, value_type value);
 
  template <class... Args>
  std::pair<accessor, bool> get_or_emplace(key_type key, Args&&... args);
 
  template <class Factory>
  std::pair<accessor, bool> get_or_emplace_lazy(key_type key, Factory&& factory);
 
  bool extract(const key_type& key, accessor& accessor);
 
  bool erase(const key_type& key);
 
  void erase(iterator& pos);
 
  bool try_get_value(const key_type& key, accessor& result) const;
 
  // TODO - implement contains
  // bool contains(const key_type& key) const;
 
  iterator find(const key_type& key);
 
  iterator begin();
 
  iterator end() { return iterator(); }
 
private:
  struct unlocker;
 
  struct bucket_state;
  struct bucket;
  struct extension_item;
  struct extension_bucket;
  struct block;
  using block_ptr = typename reclaimer::template concurrent_ptr<block, 0>;
  using guarded_block = typename block_ptr::guard_ptr;
 
  static constexpr std::uint32_t bucket_to_extension_ratio = 128;
  static constexpr std::uint32_t bucket_item_count = 3;
  static constexpr std::uint32_t extension_item_count = 10;
 
  static constexpr std::size_t item_counter_bits = utils::find_last_bit_set(bucket_item_count);
  static constexpr std::size_t lock_bit = 2 * item_counter_bits + 1;
  static constexpr std::size_t version_shift = lock_bit;
 
  static constexpr std::uint32_t lock = 1u << (lock_bit - 1);
  static constexpr std::size_t version_inc = static_cast<std::size_t>(1) << lock_bit;
 
  static constexpr std::uint32_t item_count_mask = (1u << item_counter_bits) - 1;
  static constexpr std::uint32_t delete_item_mask = item_count_mask << item_counter_bits;
 
  static constexpr std::align_val_t cacheline_size{64};
 
  block_ptr data_block;
  std::atomic<int> resize_lock;
 
  block* allocate_block(std::uint32_t bucket_count);
 
  bucket& lock_bucket(hash_t hash, guarded_block& block, bucket_state& state);
  void grow(bucket& bucket, bucket_state state);
  void do_grow();
 
  template <bool AcquireAccessor, class Factory, class Callback>
  bool do_get_or_emplace(Key&& key, Factory&& factory, Callback&& callback);
 
  bool do_extract(const key_type& key, accessor& result);
 
  static extension_item* allocate_extension_item(block* b, hash_t hash);
  static void free_extension_item(extension_item* item);
};
 
template <class Key, class Value, class... Policies>
class vyukov_hash_map<Key, Value, Policies...>::iterator {
public:
  using iterator_category = std::forward_iterator_tag;
  using difference_type = std::ptrdiff_t;
  using value_type = typename traits::iterator_value_type;
  using reference = typename traits::iterator_reference;
  using pointer = value_type*;
 
  iterator() = default;
  ~iterator();
 
  iterator(iterator&&);
  iterator& operator=(iterator&&);
 
  iterator(const iterator&) = delete;
  iterator& operator=(const iterator&) = delete;
 
  bool operator==(const iterator& r) const;
  bool operator!=(const iterator& r) const;
  iterator& operator++();
 
  reference operator*();
  pointer operator->();
 
  void reset();
 
private:
  guarded_block block{};
  bucket* current_bucket{};
  bucket_state current_bucket_state{};
  std::uint32_t index{};
  extension_item* extension{};
  std::atomic<extension_item*>* prev{};
  friend struct vyukov_hash_map;
 
  void move_to_next_bucket();
  Value* erase_current();
};
 
} // namespace xenium
 
#define XENIUM_VYUKOV_HASH_MAP_IMPL
#include <xenium/impl/vyukov_hash_map.hpp>
#include <xenium/impl/vyukov_hash_map_traits.hpp>
#undef XENIUM_VYUKOV_HASH_MAP_IMPL
 
#endif