text: //          Copyright Malte Skarupke 2017.
  // Distributed under the Boost Software License, Version 1.0.
  //    (See http://www.boost.org/LICENSE_1_0.txt)
  
  #pragma once
  
  #if _WIN32 || _WIN64
    #if _WIN64
      #define ENV64BIT
    #else
      #define ENV32BIT
    #endif
  #endif
  
   // Check GCC
  #if __GNUC__
    #if __x86_64__ || __ppc64__
      #define ENV64BIT
    #else
      #define ENV32BIT
    #endif
  #endif
  
  
  #include <cstdint>
  #include <cstddef>
  #include <cmath>
  #include <algorithm>
  #include <iterator>
  #include <utility>
  #include <type_traits>
  #include "flat_hash_map.hpp"
  #include <vector>
  #include <array>
  
  namespace ska
  {
  
  namespace detailv8
  {
  using ska::detailv3::functor_storage;
  using ska::detailv3::KeyOrValueHasher;
  using ska::detailv3::KeyOrValueEquality;
  using ska::detailv3::AssignIfTrue;
  using ska::detailv3::HashPolicySelector;
  
  template<typename = void>
  struct sherwood_v8_constants
  {
      static constexpr int8_t magic_for_empty = int8_t(0b11111111);
      static constexpr int8_t magic_for_reserved = int8_t(0b11111110);
      static constexpr int8_t bits_for_direct_hit = int8_t(0b10000000);
      static constexpr int8_t magic_for_direct_hit = int8_t(0b00000000);
      static constexpr int8_t magic_for_list_entry = int8_t(0b10000000);
  
      static constexpr int8_t bits_for_distance = int8_t(0b01111111);
      inline static int distance_from_metadata(int8_t metadata)
      {
          return metadata & bits_for_distance;
      }
  
      static constexpr int num_jump_distances =
  #ifdef ENV64BIT
          126
  #else // if 32 bits
          100
  #endif
          ;
  
      // jump distances chosen like this:
      // 1. pick the first 16 integers to promote staying in the same block
      // 2. add the next 66 triangular numbers to get even jumps when
      // the hash table is a power of two
      // 3. add 44 more triangular numbers at a much steeper growth rate
      // to get a sequence that allows large jumps so that a table
      // with 10000 sequential numbers doesn't endlessly re-allocate
      static constexpr size_t jump_distances[num_jump_distances]
      {
          0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
  
          21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231,
          253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630,
          666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176,
          1225, 1275, 1326, 1378, 1431, 1485, 1540, 1596, 1653, 1711, 1770, 1830,
          1891, 1953, 2016, 2080, 2145, 2211, 2278, 2346, 2415, 2485, 2556,
  
          3741, 8385, 18915, 42486, 95703, 215496, 485605, 1091503, 2456436,
          5529475, 12437578, 27986421, 62972253, 141700195, 318819126, 717314626,
  
          1614000520, 3631437253,
   #ifdef ENV64BIT
          8170829695, 18384318876, 41364501751,
  
          93070021080, 209407709220, 471167588430, 1060127437995, 2385287281530,
          5366895564381, 12075513791265, 27169907873235, 61132301007778,
          137547673121001, 309482258302503, 696335090510256, 1566753939653640,
          3525196427195653, 7931691866727775, 17846306747368716,
          40154190394120111, 90346928493040500, 203280588949935750,
          457381324898247375, 1029107980662394500, 2315492957028380766,
          5209859150892887590,
      };
  };
  template<typename T>
  constexpr int8_t sherwood_v8_constants<T>::magic_for_empty;
  template<typename T>
  constexpr int8_t sherwood_v8_constants<T>::magic_for_reserved;
  template<typename T>
  constexpr int8_t sherwood_v8_constants<T>::bits_for_direct_hit;
  template<typename T>
  constexpr int8_t sherwood_v8_constants<T>::magic_for_direct_hit;
  template<typename T>
  constexpr int8_t sherwood_v8_constants<T>::magic_for_list_entry;
  
  template<typename T>
  constexpr int8_t sherwood_v8_constants<T>::bits_for_distance;
  
  template<typename T>
  constexpr int sherwood_v8_constants<T>::num_jump_distances;
  template<typename T>
  constexpr size_t sherwood_v8_constants<T>::jump_distances[num_jump_distances];
  
  template<typename T, uint8_t BlockSize>
  struct sherwood_v8_block
  {
      sherwood_v8_block()
      {
      }
      ~sherwood_v8_block()
      {
      }
      int8_t control_bytes[BlockSize];
      union
      {
          T data[BlockSize];
      };
  
      static sherwood_v8_block * empty_block()
      {
          static std::array<int8_t, BlockSize> empty_bytes = []
          {
              std::array<int8_t, BlockSize> result;
              result.fill(sherwood_v8_constants<>::magic_for_empty);
              return result;
          }();
          return reinterpret_cast<sherwood_v8_block *>(&empty_bytes);
      }
  
      int first_empty_index() const
      {
          for (int i = 0; i < BlockSize; ++i)
          {
              if (control_bytes[i] == sherwood_v8_constants<>::magic_for_empty)
                  return i;
          }
          return -1;
      }
  
      void fill_control_bytes(int8_t value)
      {
          std::fill(std::begin(control_bytes), std::end(control_bytes), value);
      }
  };
  
  template<typename T, typename FindKey, typename ArgumentHash, typename Hasher, typename ArgumentEqual, typename Equal, typename ArgumentAlloc, typename ByteAlloc, uint8_t BlockSize>
  class sherwood_v8_table : private ByteAlloc, private Hasher, private Equal
  {
      using AllocatorTraits = std::allocator_traits<ByteAlloc>;
      using BlockType = sherwood_v8_block<T, BlockSize>;
      using BlockPointer = BlockType *;
      using BytePointer = typename AllocatorTraits::pointer;
      struct convertible_to_iterator;
      using Constants = sherwood_v8_constants<>;
  
  public:
  
      using value_type = T;
      using size_type = size_t;
      using difference_type = std::ptrdiff_t;
      using hasher = ArgumentHash;
      using key_equal = ArgumentEqual;
      using allocator_type = ByteAlloc;
      using reference = value_type &;
      using const_reference = const value_type &;
      using pointer = value_type *;
      using const_pointer = const value_type *;
  
      sherwood_v8_table()
      {
      }
      explicit sherwood_v8_table(size_type bucket_count, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc())
          : ByteAlloc(alloc), Hasher(hash), Equal(equal)
      {
          if (bucket_count)
              rehash(bucket_count);
      }
      sherwood_v8_table(size_type bucket_count, const ArgumentAlloc & alloc)
          : sherwood_v8_table(bucket_count, ArgumentHash(), ArgumentEqual(), alloc)
      {
      }
      sherwood_v8_table(size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc)
          : sherwood_v8_table(bucket_count, hash, ArgumentEqual(), alloc)
      {
      }
      explicit sherwood_v8_table(const ArgumentAlloc & alloc)
          : ByteAlloc(alloc)
      {
      }
      template<typename It>
      sherwood_v8_table(It first, It last, size_type bucket_count = 0, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc())
          : sherwood_v8_table(bucket_count, hash, equal, alloc)
      {
          insert(first, last);
      }
      template<typename It>
      sherwood_v8_table(It first, It last, size_type bucket_count, const ArgumentAlloc & alloc)
          : sherwood_v8_table(first, last, bucket_count, ArgumentHash(), ArgumentEqual(), alloc)
      {
      }
      template<typename It>
      sherwood_v8_table(It first, It last, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc)
          : sherwood_v8_table(first, last, bucket_count, hash, ArgumentEqual(), alloc)
      {
      }
      sherwood_v8_table(std::initializer_list<T> il, size_type bucket_count = 0, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc())
          : sherwood_v8_table(bucket_count, hash, equal, alloc)
      {
          if (bucket_count == 0)
              rehash(il.size());
          insert(il.begin(), il.end());
      }
      sherwood_v8_table(std::initializer_list<T> il, size_type bucket_count, const ArgumentAlloc & alloc)
          : sherwood_v8_table(il, bucket_count, ArgumentHash(), ArgumentEqual(), alloc)
      {
      }
      sherwood_v8_table(std::initializer_list<T> il, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc)
          : sherwood_v8_table(il, bucket_count, hash, ArgumentEqual(), alloc)
      {
      }
      sherwood_v8_table(const sherwood_v8_table & other)
          : sherwood_v8_table(other, AllocatorTraits::select_on_container_copy_construction(other.get_allocator()))
      {
      }
      sherwood_v8_table(const sherwood_v8_table & other, const ArgumentAlloc & alloc)
          : ByteAlloc(alloc), Hasher(other), Equal(other), _max_load_factor(other._max_load_factor)
      {
          rehash_for_other_container(other);
          try
          {
              insert(other.begin(), other.end());
          }
          catch(...)
          {
              clear();
              deallocate_data(entries, num_slots_minus_one);
              throw;
          }
      }
      sherwood_v8_table(sherwood_v8_table && other) noexcept
          : ByteAlloc(std::move(other)), Hasher(std::move(other)), Equal(std::move(other))
          , _max_load_factor(other._max_load_factor)
      {
          swap_pointers(other);
      }
      sherwood_v8_table(sherwood_v8_table && other, const ArgumentAlloc & alloc) noexcept
          : ByteAlloc(alloc), Hasher(std::move(other)), Equal(std::move(other))
          , _max_load_factor(other._max_load_factor)
      {
          swap_pointers(other);
      }
      sherwood_v8_table & operator=(const sherwood_v8_table & other)
      {
          if (this == std::addressof(other))
              return *this;
  
          clear();
          if (AllocatorTraits::propagate_on_container_copy_assignment::value)
          {
              if (static_cast<ByteAlloc &>(*this) != static_cast<const ByteAlloc &>(other))
              {
                  reset_to_empty_state();
              }
              AssignIfTrue<ByteAlloc, AllocatorTraits::propagate_on_container_copy_assignment::value>()(*this, other);
          }
          _max_load_factor = other._max_load_factor;
          static_cast<Hasher &>(*this) = other;
          static_cast<Equal &>(*this) = other;
          rehash_for_other_container(other);
          insert(other.begin(), other.end());
          return *this;
      }
      sherwood_v8_table & operator=(sherwood_v8_table && other) noexcept
      {
          if (this == std::addressof(other))
              return *this;
          else if (AllocatorTraits::propagate_on_container_move_assignment::value)
          {
              clear();
              reset_to_empty_state();
              AssignIfTrue<ByteAlloc, AllocatorTraits::propagate_on_container_move_assignment::value>()(*this, std::move(other));
              swap_pointers(other);
          }
          else if (static_cast<ByteAlloc &>(*this) == static_cast<ByteAlloc &>(other))
          {
              swap_pointers(other);
          }
          else
          {
              clear();
              _max_load_factor = other._max_load_factor;
              rehash_for_other_container(other);
              for (T & elem : other)
                  emplace(std::move(elem));
              other.clear();
          }
          static_cast<Hasher &>(*this) = std::move(other);
          static_cast<Equal &>(*this) = std::move(other);
          return *this;
      }
      ~sherwood_v8_table()
      {
          clear();
          deallocate_data(entries, num_slots_minus_one);
      }
  
      const allocator_type & get_allocator() const
      {
          return static_cast<const allocator_type &>(*this);
      }
      const ArgumentEqual & key_eq() const
      {
          return static_cast<const ArgumentEqual &>(*this);
      }
      const ArgumentHash & hash_function() const
      {
          return static_cast<const ArgumentHash &>(*this);
      }
  
      template<typename ValueType>
      struct templated_iterator
      {
      private:
          friend class sherwood_v8_table;
          BlockPointer current = BlockPointer();
          size_t index = 0;
  
      public:
          templated_iterator()
          {
          }
          templated_iterator(BlockPointer entries, size_t index)
              : current(entries)
              , index(index)
          {
          }
  
          using iterator_category = std::forward_iterator_tag;
          using value_type = ValueType;
          using difference_type = ptrdiff_t;
          using pointer = ValueType *;
          using reference = ValueType &;
  
          friend bool operator==(const templated_iterator & lhs, const templated_iterator & rhs)
          {
              return lhs.index == rhs.index;
          }
          friend bool operator!=(const templated_iterator & lhs, const templated_iterator & rhs)
          {
              return !(lhs == rhs);
          }
  
          templated_iterator & operator++()
          {
              do
              {
                  if (index % BlockSize == 0)
                      --current;
                  if (index-- == 0)
                      break;
              }
              while(current->control_bytes[index % BlockSize] == Constants::magic_for_empty);
              return *this;
          }
          templated_iterator operator++(int)
          {
              templated_iterator copy(*this);
              ++*this;
              return copy;
          }
  
          ValueType & operator*() const
          {
              return current->data[index % BlockSize];
          }
          ValueType * operator->() const
          {
              return current->data + index % BlockSize;
          }
  
          operator templated_iterator<const value_type>() const
          {
              return { current, index };
          }
      };
      using iterator = templated_iterator<value_type>;
      using const_iterator = templated_iterator<const value_type>;
  
      iterator begin()
      {
          size_t num_slots = num_slots_minus_one ? num_slots_minus_one + 1 : 0;
          return ++iterator{ entries + num_slots / BlockSize, num_slots };
      }
      const_iterator begin() const
      {
          size_t num_slots = num_slots_minus_one ? num_slots_minus_one + 1 : 0;
          return ++iterator{ entries + num_slots / BlockSize, num_slots };
      }
      const_iterator cbegin() const
      {
          return begin();
      }
      iterator end()
      {
          return { entries - 1, std::numeric_limits<size_t>::max() };
      }
      const_iterator end() const
      {
          return { entries - 1, std::numeric_limits<size_t>::max() };
      }
      const_iterator cend() const
      {
          return end();
      }
  
      inline iterator find(const FindKey & key)
      {
          size_t index = hash_object(key);
          size_t num_slots_minus_one = this->num_slots_minus_one;
          BlockPointer entries = this->entries;
          index = hash_policy.index_for_hash(index, num_slots_minus_one);
          bool first = true;
          for (;;)
          {
              size_t block_index = index / BlockSize;
              int index_in_block = index % BlockSize;
              BlockPointer block = entries + block_index;
              int8_t metadata = block->control_bytes[index_in_block];
              if (first)
              {
                  if ((metadata & Constants::bits_for_direct_hit) != Constants::magic_for_direct_hit)
                      return end();
                  first = false;
              }
              if (compares_equal(key, block->data[index_in_block]))
                  return { block, index };
              int8_t to_next_index = metadata & Constants::bits_for_distance;
              if (to_next_index == 0)
                  return end();
              index += Constants::jump_distances[to_next_index];
              index = hash_policy.keep_in_range(index, num_slots_minus_one);
          }
      }
      inline const_iterator find(const FindKey & key) const
      {
          return const_cast<sherwood_v8_table *>(this)->find(key);
      }
      size_t count(const FindKey & key) const
      {
          return find(key) == end() ? 0 : 1;
      }
      std::pair<iterator, iterator> equal_range(const FindKey & key)
      {
          iterator found = find(key);
          if (found == end())
              return { found, found };
          else
              return { found, std::next(found) };
      }
      std::pair<const_iterator, const_iterator> equal_range(const FindKey & key) const
      {
          const_iterator found = find(key);
          if (found == end())
              return { found, found };
          else
              return { found, std::next(found) };
      }
  
  
      template<typename Key, typename... Args>
      inline std::pair<iterator, bool> emplace(Key && key, Args &&... args)
      {
          size_t index = hash_object(key);
          size_t num_slots_minus_one = this->num_slots_minus_one;
          BlockPointer entries = this->entries;
          index = hash_policy.index_for_hash(index, num_slots_minus_one);
          bool first = true;
          for (;;)
          {
              size_t block_index = index / BlockSize;
              int index_in_block = index % BlockSize;
              BlockPointer block = entries + block_index;
              int8_t metadata = block->control_bytes[index_in_block];
              if (first)
              {
                  if ((metadata & Constants::bits_for_direct_hit) != Constants::magic_for_direct_hit)
                      return emplace_direct_hit({ index, block }, std::forward<Key>(key), std::forward<Args>(args)...);
                  first = false;
              }
              if (compares_equal(key, block->data[index_in_block]))
                  return { { block, index }, false };
              int8_t to_next_index = metadata & Constants::bits_for_distance;
              if (to_next_index == 0)
                  return emplace_new_key({ index, block }, std::forward<Key>(key), std::forward<Args>(args)...);
              index += Constants::jump_distances[to_next_index];
              index = hash_policy.keep_in_range(index, num_slots_minus_one);
          }
      }
  
      std::pair<iterator, bool> insert(const value_type & value)
      {
          return emplace(value);
      }
      std::pair<iterator, bool> insert(value_type && value)
      {
          return emplace(std::move(value));
      }
      template<typename... Args>
      iterator emplace_hint(const_iterator, Args &&... args)
      {
          return emplace(std::forward<Args>(args)...).first;
      }
      iterator insert(const_iterator, const value_type & value)
      {
          return emplace(value).first;
      }
      iterator insert(const_iterator, value_type && value)
      {
          return emplace(std::move(value)).first;
      }
  
      template<typename It>
      void insert(It begin, It end)
      {
          for (; begin != end; ++begin)
          {
              emplace(*begin);
          }
      }
      void insert(std::initializer_list<value_type> il)
      {
          insert(il.begin(), il.end());
      }
  
      void rehash(size_t num_items)
      {
          num_items = std::max(num_items, static_cast<size_t>(std::ceil(num_elements / static_cast<double>(_max_load_factor))));
          if (num_items == 0)
          {
              reset_to_empty_state();
              return;
          }
          auto new_prime_index = hash_policy.next_size_over(num_items);
          if (num_items == num_slots_minus_one + 1)
              return;
          size_t num_blocks = num_items / BlockSize;
          if (num_items % BlockSize)
              ++num_blocks;
          size_t memory_requirement = calculate_memory_requirement(num_blocks);
          unsigned char * new_memory = &*AllocatorTraits::allocate(*this, memory_requirement);
  
          BlockPointer new_buckets = reinterpret_cast<BlockPointer>(new_memory);
  
          BlockPointer special_end_item = new_buckets + num_blocks;
          for (BlockPointer it = new_buckets; it <= special_end_item; ++it)
              it->fill_control_bytes(Constants::magic_for_empty);
          using std::swap;
          swap(entries, new_buckets);
          swap(num_slots_minus_one, num_items);
          --num_slots_minus_one;
          hash_policy.commit(new_prime_index);
          num_elements = 0;
          if (num_items)
              ++num_items;
          size_t old_num_blocks = num_items / BlockSize;
          if (num_items % BlockSize)
              ++old_num_blocks;
          for (BlockPointer it = new_buckets, end = new_buckets + old_num_blocks; it != end; ++it)
          {
              for (int i = 0; i < BlockSize; ++i)
              {
                  int8_t metadata = it->control_bytes[i];
                  if (metadata != Constants::magic_for_empty && metadata != Constants::magic_for_reserved)
                  {
                      emplace(std::move(it->data[i]));
                      AllocatorTraits::destroy(*this, it->data + i);
                  }
              }
          }
          deallocate_data(new_buckets, num_items - 1);
      }
  
      void reserve(size_t num_elements)
      {
          size_t required_buckets = num_buckets_for_reserve(num_elements);
          if (required_buckets > bucket_count())
              rehash(required_buckets);
      }
  
      // the return value is a type that can be converted to an iterator
      // the reason for doing this is that it's not free to find the
      // iterator pointing at the next element. if you care about the
      // next iterator, turn the return value into an iterator
      convertible_to_iterator erase(const_iterator to_erase)
      {
          LinkedListIt current = { to_erase.index, to_erase.current };
          if (current.has_next())
          {
              LinkedListIt previous = current;
              LinkedListIt next = current.next(*this);
              while (next.has_next())
              {
                  previous = next;
                  next = next.next(*this);
              }
              AllocatorTraits::destroy(*this, std::addressof(*current));
              AllocatorTraits::construct(*this, std::addressof(*current), std::move(*next));
              AllocatorTraits::destroy(*this, std::addressof(*next));
              next.set_metadata(Constants::magic_for_empty);
              previous.clear_next();
          }
          else
          {
              if (!current.is_direct_hit())
                  find_parent_block(current).clear_next();
              AllocatorTraits::destroy(*this, std::addressof(*current));
              current.set_metadata(Constants::magic_for_empty);
          }
          --num_elements;
          return { to_erase.current, to_erase.index };
      }
  
      iterator erase(const_iterator begin_it, const_iterator end_it)
      {
          if (begin_it == end_it)
              return { begin_it.current, begin_it.index };
          if (std::next(begin_it) == end_it)
              return erase(begin_it);
          if (begin_it == begin() && end_it == end())
          {
              clear();
              return { end_it.current, end_it.index };
          }
          std::vector<std::pair<int, LinkedListIt>> depth_in_chain;
          for (const_iterator it = begin_it; it != end_it; ++it)
          {
              LinkedListIt list_it(it.index, it.current);
              if (list_it.is_direct_hit())
                  depth_in_chain.emplace_back(0, list_it);
              else
              {
                  LinkedListIt root = find_direct_hit(list_it);
                  int distance = 1;
                  for (;;)
                  {
                      LinkedListIt next = root.next(*this);
                      if (next == list_it)
                          break;
                      ++distance;
                      root = next;
                  }
                  depth_in_chain.emplace_back(distance, list_it);
              }
          }
          std::sort(depth_in_chain.begin(), depth_in_chain.end(), [](const auto & a, const auto & b) { return a.first < b.first; });
          for (auto it = depth_in_chain.rbegin(), end = depth_in_chain.rend(); it != end; ++it)
          {
              erase(it->second.it());
          }
  
          if (begin_it.current->control_bytes[begin_it.index % BlockSize] == Constants::magic_for_empty)
              return ++iterator{ begin_it.current, begin_it.index };
          else
              return { begin_it.current, begin_it.index };
      }
  
      size_t erase(const FindKey & key)
      {
          auto found = find(key);
          if (found == end())
              return 0;
          else
          {
              erase(found);
              return 1;
          }
      }
  
      void clear()
      {
          if (!num_slots_minus_one)
              return;
          size_t num_slots = num_slots_minus_one + 1;
          size_t num_blocks = num_slots / BlockSize;
          if (num_slots % BlockSize)
              ++num_blocks;
          for (BlockPointer it = entries, end = it + num_blocks; it != end; ++it)
          {
              for (int i = 0; i < BlockSize; ++i)
              {
                  if (it->control_bytes[i] != Constants::magic_for_empty)
                  {
                      AllocatorTraits::destroy(*this, std::addressof(it->data[i]));
                      it->control_bytes[i] = Constants::magic_for_empty;
                  }
              }
          }
          num_elements = 0;
      }
  
      void shrink_to_fit()
      {
          rehash_for_other_container(*this);
      }
  
      void swap(sherwood_v8_table & other)
      {
          using std::swap;
          swap_pointers(other);
          swap(static_cast<ArgumentHash &>(*this), static_cast<ArgumentHash &>(other));
          swap(static_cast<ArgumentEqual &>(*this), static_cast<ArgumentEqual &>(other));
          if (AllocatorTraits::propagate_on_container_swap::value)
              swap(static_cast<ByteAlloc &>(*this), static_cast<ByteAlloc &>(other));
      }
  
      size_t size() const
      {
          return num_elements;
      }
      size_t max_size() const
      {
          return (AllocatorTraits::max_size(*this)) / sizeof(T);
      }
      size_t bucket_count() const
      {
          return num_slots_minus_one ? num_slots_minus_one + 1 : 0;
      }
      size_type max_bucket_count() const
      {
          return (AllocatorTraits::max_size(*this)) / sizeof(T);
      }
      size_t bucket(const FindKey & key) const
      {
          return hash_policy.index_for_hash(hash_object(key), num_slots_minus_one);
      }
      float load_factor() const
      {
          return static_cast<double>(num_elements) / (num_slots_minus_one + 1);
      }
      void max_load_factor(float value)
      {
          _max_load_factor = value;
      }
      float max_load_factor() const
      {
          return _max_load_factor;
      }
  
      bool empty() const
      {
          return num_elements == 0;
      }
  
  private:
      BlockPointer entries = BlockType::empty_block();
      size_t num_slots_minus_one = 0;
      typename HashPolicySelector<ArgumentHash>::type hash_policy;
      float _max_load_factor = 0.9375f;
      size_t num_elements = 0;
  
      size_t num_buckets_for_reserve(size_t num_elements) const
      {
          return static_cast<size_t>(std::ceil(num_elements / static_cast<double>(_max_load_factor)));
      }
      void rehash_for_other_container(const sherwood_v8_table & other)
      {
          rehash(std::min(num_buckets_for_reserve(other.size()), other.bucket_count()));
      }
      bool is_full() const
      {
          if (!num_slots_minus_one)
              return true;
          else
              return num_elements + 1 > (num_slots_minus_one + 1) * static_cast<double>(_max_load_factor);
      }
  
      void swap_pointers(sherwood_v8_table & other)
      {
          using std::swap;
          swap(hash_policy, other.hash_policy);
          swap(entries, other.entries);
          swap(num_slots_minus_one, other.num_slots_minus_one);
          swap(num_elements, other.num_elements);
          swap(_max_load_factor, other._max_load_factor);
      }
  
      struct LinkedListIt
      {
          size_t index = 0;
          BlockPointer block = nullptr;
  
          LinkedListIt()
          {
          }
          LinkedListIt(size_t index, BlockPointer block)
              : index(index), block(block)
          {
          }
  
          iterator it() const
          {
              return { block, index };
          }
          int index_in_block() const
          {
              return index % BlockSize;
          }
          bool is_direct_hit() const
          {
              return (metadata() & Constants::bits_for_direct_hit) == Constants::magic_for_direct_hit;
          }
          bool is_empty() const
          {
              return metadata() == Constants::magic_for_empty;
          }
          bool has_next() const
          {
              return jump_index() != 0;
          }
          int8_t jump_index() const
          {
              return Constants::distance_from_metadata(metadata());
          }
          int8_t metadata() const
          {
              return block->control_bytes[index_in_block()];
          }
          void set_metadata(int8_t metadata)
          {
              block->control_bytes[index_in_block()] = metadata;
          }
  
          LinkedListIt next(sherwood_v8_table & table) const
          {
              int8_t distance = jump_index();
              size_t next_index = table.hash_policy.keep_in_range(index + Constants::jump_distances[distance], table.num_slots_minus_one);
              return { next_index, table.entries + next_index / BlockSize };
          }
          void set_next(int8_t jump_index)
          {
              int8_t & metadata = block->control_bytes[index_in_block()];
              metadata = (metadata & ~Constants::bits_for_distance) | jump_index;
          }
          void clear_next()
          {
              set_next(0);
          }
  
          value_type & operator*() const
          {
              return block->data[index_in_block()];
          }
          bool operator!() const
          {
              return !block;
          }
          explicit operator bool() const
          {
              return block != nullptr;
          }
          bool operator==(const LinkedListIt & other) const
          {
              return index == other.index;
          }
          bool operator!=(const LinkedListIt & other) const
          {
              return !(*this == other);
          }
      };
  
      template<typename... Args>
      SKA_NOINLINE(std::pair<iterator, bool>) emplace_direct_hit(LinkedListIt block, Args &&... args)
      {
          using std::swap;
          if (is_full())
          {
              grow();
              return emplace(std::forward<Args>(args)...);
          }
          if (block.metadata() == Constants::magic_for_empty)
          {
              AllocatorTraits::construct(*this, std::addressof(*block), std::forward<Args>(args)...);
              block.set_metadata(Constants::magic_for_direct_hit);
              ++num_elements;
              return { block.it(), true };
          }
          else
          {
              LinkedListIt parent_block = find_parent_block(block);
              std::pair<int8_t, LinkedListIt> free_block = find_free_index(parent_block);
              if (!free_block.first)
              {
                  grow();
                  return emplace(std::forward<Args>(args)...);
              }
              value_type new_value(std::forward<Args>(args)...);
              for (LinkedListIt it = block;;)
              {
                  AllocatorTraits::construct(*this, std::addressof(*free_block.second), std::move(*it));
                  AllocatorTraits::destroy(*this, std::addressof(*it));
                  parent_block.set_next(free_block.first);
                  free_block.second.set_metadata(Constants::magic_for_list_entry);
                  if (!it.has_next())
                  {
                      it.set_metadata(Constants::magic_for_empty);
                      break;
                  }
                  LinkedListIt next = it.next(*this);
                  it.set_metadata(Constants::magic_for_empty);
                  block.set_metadata(Constants::magic_for_reserved);
                  it = next;
                  parent_block = free_block.second;
                  free_block = find_free_index(free_block.second);
                  if (!free_block.first)
                  {
                      grow();
                      return emplace(std::move(new_value));
                  }
              }
              AllocatorTraits::construct(*this, std::addressof(*block), std::move(new_value));
              block.set_metadata(Constants::magic_for_direct_hit);
              ++num_elements;
              return { block.it(), true };
          }
      }
  
      template<typename... Args>
      SKA_NOINLINE(std::pair<iterator, bool>) emplace_new_key(LinkedListIt parent, Args &&... args)
      {
          if (is_full())
          {
              grow();
              return emplace(std::forward<Args>(args)...);
          }
          std::pair<int8_t, LinkedListIt> free_block = find_free_index(parent);
          if (!free_block.first)
          {
              grow();
              return emplace(std::forward<Args>(args)...);
          }
          AllocatorTraits::construct(*this, std::addressof(*free_block.second), std::forward<Args>(args)...);
          free_block.second.set_metadata(Constants::magic_for_list_entry);
          parent.set_next(free_block.first);
          ++num_elements;
          return { free_block.second.it(), true };
      }
  
      LinkedListIt find_direct_hit(LinkedListIt child) const
      {
          size_t to_move_hash = hash_object(*child);
          size_t to_move_index = hash_policy.index_for_hash(to_move_hash, num_slots_minus_one);
          return { to_move_index, entries + to_move_index / BlockSize };
      }
      LinkedListIt find_parent_block(LinkedListIt child)
      {
          LinkedListIt parent_block = find_direct_hit(child);
          for (;;)
          {
              LinkedListIt next = parent_block.next(*this);
              if (next == child)
                  return parent_block;
              parent_block = next;
          }
      }
  
      std::pair<int8_t, LinkedListIt> find_free_index(LinkedListIt parent) const
      {
          for (int8_t jump_index = 1; jump_index < Constants::num_jump_distances; ++jump_index)
          {
              size_t index = hash_policy.keep_in_range(parent.index + Constants::jump_distances[jump_index], num_slots_minus_one);
              BlockPointer block = entries + index / BlockSize;
              if (block->control_bytes[index % BlockSize] == Constants::magic_for_empty)
                  return { jump_index, { index, block } };
          }
          return { 0, {} };
      }
  
      void grow()
      {
          rehash(std::max(size_t(10), 2 * bucket_count()));
      }
  
      size_t calculate_memory_requirement(size_t num_blocks)
      {
          size_t memory_required = sizeof(BlockType) * num_blocks;
          memory_required += BlockSize; // for metadata of past-the-end pointer
          return memory_required;
      }
  
      void deallocate_data(BlockPointer begin, size_t num_slots_minus_one)
      {
          if (begin == BlockType::empty_block())
              return;
  
          ++num_slots_minus_one;
          size_t num_blocks = num_slots_minus_one / BlockSize;
          if (num_slots_minus_one % BlockSize)
              ++num_blocks;
          size_t memory = calculate_memory_requirement(num_blocks);
          unsigned char * as_byte_pointer = reinterpret_cast<unsigned char *>(begin);
          AllocatorTraits::deallocate(*this, typename AllocatorTraits::pointer(as_byte_pointer), memory);
      }
  
      void reset_to_empty_state()
      {
          deallocate_data(entries, num_slots_minus_one);
          entries = BlockType::empty_block();
          num_slots_minus_one = 0;
          hash_policy.reset();
      }
  
      template<typename U>
      size_t hash_object(const U & key)
      {
          return static_cast<Hasher &>(*this)(key);
      }
      template<typename U>
      size_t hash_object(const U & key) const
      {
          return static_cast<const Hasher &>(*this)(key);
      }
      template<typename L, typename R>
      bool compares_equal(const L & lhs, const R & rhs)
      {
          return static_cast<Equal &>(*this)(lhs, rhs);
      }
  
      struct convertible_to_iterator
      {
          BlockPointer it;
          size_t index;
  
          operator iterator()
          {
              if (it->control_bytes[index % BlockSize] == Constants::magic_for_empty)
                  return ++iterator{it, index};
              else
                  return { it, index };
          }
          operator const_iterator()
          {
              if (it->control_bytes[index % BlockSize] == Constants::magic_for_empty)
                  return ++iterator{it, index};
              else
                  return { it, index };
          }
      };
  };
  template<typename T, typename Enable = void>
  struct AlignmentOr8Bytes
  {
      static constexpr size_t value = 8;
  };
  template<typename T>
  struct AlignmentOr8Bytes<T, typename std::enable_if<alignof(T) >= 1>::type>
  {
      static constexpr size_t value = alignof(T);
  };
  template<typename... Args>
  struct CalculateBytellBlockSize;
  template<typename First, typename... More>
  struct CalculateBytellBlockSize<First, More...>
  {
      static constexpr size_t this_value = AlignmentOr8Bytes<First>::value;
      static constexpr size_t base_value = CalculateBytellBlockSize<More...>::value;
      static constexpr size_t value = this_value > base_value ? this_value : base_value;
  };
  template<>
  struct CalculateBytellBlockSize<>
  {
      static constexpr size_t value = 8;
  };
  }
  
  template<typename K, typename V, typename H = std::hash<K>, typename E = std::equal_to<K>, typename A = std::allocator<std::pair<K, V> > >
  class bytell_hash_map
          : public detailv8::sherwood_v8_table
          <
              std::pair<K, V>,
              K,
              H,
              detailv8::KeyOrValueHasher<K, std::pair<K, V>, H>,
              E,
              detailv8::KeyOrValueEquality<K, std::pair<K, V>, E>,
              A,
              typename std::allocator_traits<A>::template rebind_alloc<unsigned char>,
              detailv8::CalculateBytellBlockSize<K, V>::value
          >
  {
      using Table = detailv8::sherwood_v8_table
      <
          std::pair<K, V>,
          K,
          H,
          detailv8::KeyOrValueHasher<K, std::pair<K, V>, H>,
          E,
          detailv8::KeyOrValueEquality<K, std::pair<K, V>, E>,
          A,
          typename std::allocator_traits<A>::template rebind_alloc<unsigned char>,
          detailv8::CalculateBytellBlockSize<K, V>::value
      >;
  public:
  
      using key_type = K;
      using mapped_type = V;
  
      using Table::Table;
      bytell_hash_map()
      {
      }
  
      inline V & operator[](const K & key)
      {
          return emplace(key, convertible_to_value()).first->second;
      }
      inline V & operator[](K && key)
      {
          return emplace(std::move(key), convertible_to_value()).first->second;
      }
      V & at(const K & key)
      {
          auto found = this->find(key);
          if (found == this->end())
              throw std::out_of_range("Argument passed to at() was not in the map.");
          return found->second;
      }
      const V & at(const K & key) const
      {
          auto found = this->find(key);
          if (found == this->end())
              throw std::out_of_range("Argument passed to at() was not in the map.");
          return found->second;
      }
  
      using Table::emplace;
      std::pair<typename Table::iterator, bool> emplace()
      {
          return emplace(key_type(), convertible_to_value());
      }
      template<typename M>
      std::pair<typename Table::iterator, bool> insert_or_assign(const key_type & key, M && m)
      {
          auto emplace_result = emplace(key, std::forward<M>(m));
          if (!emplace_result.second)
              emplace_result.first->second = std::forward<M>(m);
          return emplace_result;
      }
      template<typename M>
      std::pair<typename Table::iterator, bool> insert_or_assign(key_type && key, M && m)
      {
          auto emplace_result = emplace(std::move(key), std::forward<M>(m));
          if (!emplace_result.second)
              emplace_result.first->second = std::forward<M>(m);
          return emplace_result;
      }
      template<typename M>
      typename Table::iterator insert_or_assign(typename Table::const_iterator, const key_type & key, M && m)
      {
          return insert_or_assign(key, std::forward<M>(m)).first;
      }
      template<typename M>
      typename Table::iterator insert_or_assign(typename Table::const_iterator, key_type && key, M && m)
      {
          return insert_or_assign(std::move(key), std::forward<M>(m)).first;
      }
          template<typename... Args>
      std::pair<typename Table::iterator, bool> try_emplace(const key_type & key, Args&&... args)
      {
          return this->try_emplace_impl(key, std::forward<Args>(args)...);
      }
  
      template<typename... Args>
      std::pair<typename Table::iterator, bool> try_emplace(key_type && key, Args&&... args)
      {
          return try_emplace_impl(std::forward<key_type>(key), std::forward<Args>(args)...);
      }
  
      template<typename... Args >
      typename Table::iterator try_emplace(typename Table::const_iterator, const key_type & key, Args&&... args)
      {
          return try_emplace(key, std::forward<Args>(args)...).first;
      }
      template<typename... Args>
      typename Table::iterator try_emplace(typename Table::const_iterator, key_type && key, Args&&... args)
      {
          return try_emplace(std::forward<key_type>(key), std::forward<Args>(args)...).first;
      }
  
      friend bool operator==(const bytell_hash_map & lhs, const bytell_hash_map & rhs)
      {
          if (lhs.size() != rhs.size())
              return false;
          for (const typename Table::value_type & value : lhs)
          {
              auto found = rhs.find(value.first);
              if (found == rhs.end())
                  return false;
              else if (value.second != found->second)
                  return false;
          }
          return true;
      }
      friend bool operator!=(const bytell_hash_map & lhs, const bytell_hash_map & rhs)
      {
          return !(lhs == rhs);
      }
  
  private:
      struct convertible_to_value
      {
          operator V() const
          {
              return V();
          }
      };
      template <typename KeyType = key_type, class... Args>
      std::pair<typename Table::iterator, bool> try_emplace_impl(KeyType&& key, Args&&... args) {
          auto res = this->find(key);
          if (res == this->end())
              return this->emplace(std::forward<KeyType>(key), std::forward<Args>(args)...);
          return { { res }, false };
      }
  };
  
  template<typename T, typename H = std::hash<T>, typename E = std::equal_to<T>, typename A = std::allocator<T> >
  class bytell_hash_set
          : public detailv8::sherwood_v8_table
          <
              T,
              T,
              H,
              detailv8::functor_storage<size_t, H>,
              E,
              detailv8::functor_storage<bool, E>,
              A,
              typename std::allocator_traits<A>::template rebind_alloc<unsigned char>,
              detailv8::CalculateBytellBlockSize<T>::value
          >
  {
      using Table = detailv8::sherwood_v8_table
      <
          T,
          T,
          H,
          detailv8::functor_storage<size_t, H>,
          E,
          detailv8::functor_storage<bool, E>,
          A,
          typename std::allocator_traits<A>::template rebind_alloc<unsigned char>,
          detailv8::CalculateBytellBlockSize<T>::value
      >;
  public:
  
      using key_type = T;
  
      using Table::Table;
      bytell_hash_set()
      {
      }
  
      template<typename... Args>
      std::pair<typename Table::iterator, bool> emplace(Args &&... args)
      {
          return Table::emplace(T(std::forward<Args>(args)...));
      }
      std::pair<typename Table::iterator, bool> emplace(const key_type & arg)
      {
          return Table::emplace(arg);
      }
      std::pair<typename Table::iterator, bool> emplace(key_type & arg)
      {
          return Table::emplace(arg);
      }
      std::pair<typename Table::iterator, bool> emplace(const key_type && arg)
      {
          return Table::emplace(std::move(arg));
      }
      std::pair<typename Table::iterator, bool> emplace(key_type && arg)
      {
          return Table::emplace(std::move(arg));
      }
  
      friend bool operator==(const bytell_hash_set & lhs, const bytell_hash_set & rhs)
      {
          if (lhs.size() != rhs.size())
              return false;
          for (const T & value : lhs)
          {
              if (rhs.find(value) == rhs.end())
                  return false;
          }
          return true;
      }
      friend bool operator!=(const bytell_hash_set & lhs, const bytell_hash_set & rhs)
      {
          return !(lhs == rhs);
      }
  };
  
  } // end namespace ska