FM / util

/usr/local/lib64/python3.6/site-packages/torch/include/c10/util/

/usr/local/lib64/python3.6/site-packages/torch/include/c10/util

Name	Size	Mode	Actions
accumulate.h	4205	0644	edit dl rm
AlignOf.h	4835	0644	edit dl rm
Array.h	11354	0644	edit dl rm
ArrayRef.h	9058	0644	edit dl rm
Backtrace.h	364	0644	edit dl rm
BFloat16-inl.h	9222	0644	edit dl rm
BFloat16-math.h	5217	0644	edit dl rm
BFloat16.h	2372	0644	edit dl rm
Bitset.h	3414	0644	edit dl rm
C++17.h	13329	0644	edit dl rm
complex.h	17542	0644	edit dl rm
complex_math.h	10902	0644	edit dl rm
complex_utils.h	958	0644	edit dl rm
ConstexprCrc.h	6633	0644	edit dl rm
copysign.h	866	0644	edit dl rm
DeadlockDetection.h	1920	0644	edit dl rm
Deprecated.h	3579	0644	edit dl rm
either.h	6423	0644	edit dl rm
env.h	835	0644	edit dl rm
Exception.h	24723	0644	edit dl rm
ExclusivelyOwned.h	4759	0644	edit dl rm
Flags.h	10056	0644	edit dl rm
flat_hash_map.h	61655	0644	edit dl rm
FunctionRef.h	2301	0644	edit dl rm
Half-inl.h	8674	0644	edit dl rm
Half.h	18965	0644	edit dl rm
hash.h	5084	0644	edit dl rm
IdWrapper.h	2348	0644	edit dl rm
intrusive_ptr.h	35563	0644	edit dl rm
in_place.h	350	0644	edit dl rm
irange.h	2679	0644	edit dl rm
LeftRight.h	6016	0644	edit dl rm
llvmMathExtras.h	29168	0644	edit dl rm
Logging.h	11256	0644	edit dl rm
logging_is_google_glog.h	2031	0644	edit dl rm
logging_is_not_google_glog.h	8271	0644	edit dl rm
MathConstants.h	858	0644	edit dl rm
math_compat.h	7296	0644	edit dl rm
MaybeOwned.h	6689	0644	edit dl rm
Metaprogramming.h	15288	0644	edit dl rm
numa.h	696	0644	edit dl rm
Optional.h	35592	0644	edit dl rm
order_preserving_flat_hash_map.h	65482	0644	edit dl rm
overloaded.h	709	0644	edit dl rm
python_stub.h	56	0644	edit dl rm
qint8.h	472	0644	edit dl rm
qint32.h	319	0644	edit dl rm
quint4x2.h	366	0644	edit dl rm
quint8.h	320	0644	edit dl rm
Registry.h	12242	0644	edit dl rm
reverse_iterator.h	8796	0644	edit dl rm
ScopeExit.h	1345	0644	edit dl rm
signal_handler.h	3154	0644	edit dl rm
SmallBuffer.h	1243	0644	edit dl rm
SmallVector.h	34456	0644	edit dl rm
sparse_bitset.h	26511	0644	edit dl rm
StringUtil.h	4538	0644	edit dl rm
string_utils.h	3989	0644	edit dl rm
string_view.h	20189	0644	edit dl rm
tempfile.h	6029	0644	edit dl rm
ThreadLocal.h	3883	0644	edit dl rm
ThreadLocalDebugInfo.h	2603	0644	edit dl rm
thread_name.h	148	0644	edit dl rm
Type.h	607	0644	edit dl rm
TypeCast.h	6972	0644	edit dl rm
typeid.h	18793	0644	edit dl rm
TypeIndex.h	5251	0644	edit dl rm
TypeList.h	16901	0644	edit dl rm
TypeTraits.h	5368	0644	edit dl rm
Unicode.h	295	0644	edit dl rm
UniqueVoidPtr.h	4117	0644	edit dl rm
Unroll.h	667	0644	edit dl rm
variant.h	95182	0644	edit dl rm
win32-headers.h	858	0644	edit dl rm

Edit: /usr/local/lib64/python3.6/site-packages/torch/include/c10/util/order_preserving_flat_hash_map.h (65482B)

// Taken from
// https://github.com/skarupke/flat_hash_map/blob/2c4687431f978f02a3780e24b8b701d22aa32d9c/flat_hash_map.hpp
// with fixes applied:
// - https://github.com/skarupke/flat_hash_map/pull/25
// - https://github.com/skarupke/flat_hash_map/pull/26
// - replace size_t with uint64_t to fix it for 32bit
// - add "GCC diagnostic" pragma to ignore -Wshadow
// - make sherwood_v3_table::convertible_to_iterator public because GCC5 seems
// to have issues with it otherwise
// - fix compiler warnings in operator templated_iterator<const value_type>

//          Copyright Malte Skarupke 2017.
// Distributed under the Boost Software License, Version 1.0.
//    (See http://www.boost.org/LICENSE_1_0.txt)

// Modified to maintain insertion and deletion order through a doubly-linked
// list

#pragma once

#include <c10/util/C++17.h>
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <iterator>
#include <type_traits>
#include <utility>

#ifndef _MSC_VER
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wshadow"
#endif

#ifdef _MSC_VER
#define SKA_NOINLINE(...) __declspec(noinline) __VA_ARGS__
#else
#define SKA_NOINLINE(...) __VA_ARGS__ __attribute__((noinline))
#endif

namespace ska_ordered {

struct prime_number_hash_policy;
struct power_of_two_hash_policy;
struct fibonacci_hash_policy;

namespace detailv3 {
template <typename Result, typename Functor>
struct functor_storage : Functor {
  functor_storage() = default;
  functor_storage(const Functor& functor) : Functor(functor) {}
  template <typename... Args>
  Result operator()(Args&&... args) {
    return static_cast<Functor&>(*this)(std::forward<Args>(args)...);
  }
  template <typename... Args>
  Result operator()(Args&&... args) const {
    return static_cast<const Functor&>(*this)(std::forward<Args>(args)...);
  }
};
template <typename Result, typename... Args>
struct functor_storage<Result, Result (*)(Args...)> {
  typedef Result (*function_ptr)(Args...);
  function_ptr function;
  functor_storage(function_ptr function) : function(function) {}
  Result operator()(Args... args) const {
    return function(std::forward<Args>(args)...);
  }
  operator function_ptr&() {
    return function;
  }
  operator const function_ptr&() {
    return function;
  }
};
template <typename key_type, typename value_type, typename hasher>
struct KeyOrValueHasher : functor_storage<uint64_t, hasher> {
  typedef functor_storage<uint64_t, hasher> hasher_storage;
  KeyOrValueHasher() = default;
  KeyOrValueHasher(const hasher& hash) : hasher_storage(hash) {}
  uint64_t operator()(const key_type& key) {
    return static_cast<hasher_storage&>(*this)(key);
  }
  uint64_t operator()(const key_type& key) const {
    return static_cast<const hasher_storage&>(*this)(key);
  }
  uint64_t operator()(const value_type& value) {
    return static_cast<hasher_storage&>(*this)(value.first);
  }
  uint64_t operator()(const value_type& value) const {
    return static_cast<const hasher_storage&>(*this)(value.first);
  }
  template <typename F, typename S>
  uint64_t operator()(const std::pair<F, S>& value) {
    return static_cast<hasher_storage&>(*this)(value.first);
  }
  template <typename F, typename S>
  uint64_t operator()(const std::pair<F, S>& value) const {
    return static_cast<const hasher_storage&>(*this)(value.first);
  }
};
template <typename key_type, typename value_type, typename key_equal>
struct KeyOrValueEquality : functor_storage<bool, key_equal> {
  typedef functor_storage<bool, key_equal> equality_storage;
  KeyOrValueEquality() = default;
  KeyOrValueEquality(const key_equal& equality) : equality_storage(equality) {}
  bool operator()(const key_type& lhs, const key_type& rhs) {
    return static_cast<equality_storage&>(*this)(lhs, rhs);
  }
  bool operator()(const key_type& lhs, const value_type& rhs) {
    return static_cast<equality_storage&>(*this)(lhs, rhs.first);
  }
  bool operator()(const value_type& lhs, const key_type& rhs) {
    return static_cast<equality_storage&>(*this)(lhs.first, rhs);
  }
  bool operator()(const value_type& lhs, const value_type& rhs) {
    return static_cast<equality_storage&>(*this)(lhs.first, rhs.first);
  }
  template <typename F, typename S>
  bool operator()(const key_type& lhs, const std::pair<F, S>& rhs) {
    return static_cast<equality_storage&>(*this)(lhs, rhs.first);
  }
  template <typename F, typename S>
  bool operator()(const std::pair<F, S>& lhs, const key_type& rhs) {
    return static_cast<equality_storage&>(*this)(lhs.first, rhs);
  }
  template <typename F, typename S>
  bool operator()(const value_type& lhs, const std::pair<F, S>& rhs) {
    return static_cast<equality_storage&>(*this)(lhs.first, rhs.first);
  }
  template <typename F, typename S>
  bool operator()(const std::pair<F, S>& lhs, const value_type& rhs) {
    return static_cast<equality_storage&>(*this)(lhs.first, rhs.first);
  }
  template <typename FL, typename SL, typename FR, typename SR>
  bool operator()(const std::pair<FL, SL>& lhs, const std::pair<FR, SR>& rhs) {
    return static_cast<equality_storage&>(*this)(lhs.first, rhs.first);
  }
};
static constexpr int8_t min_lookups = 4;
template <typename T>
struct sherwood_v3_entry {
  sherwood_v3_entry() {}
  sherwood_v3_entry(int8_t distance_from_desired)
      : distance_from_desired(distance_from_desired) {}
  ~sherwood_v3_entry() {}

bool has_value() const {
    return distance_from_desired >= 0;
  }
  bool is_empty() const {
    return distance_from_desired < 0;
  }
  bool is_at_desired_position() const {
    return distance_from_desired <= 0;
  }
  template <typename... Args>
  void emplace(int8_t distance, Args&&... args) {
    new (std::addressof(value)) T(std::forward<Args>(args)...);
    distance_from_desired = distance;
  }

void destroy_value() {
    value.~T();
    distance_from_desired = -1;
  }

sherwood_v3_entry<T>* prev = nullptr;
  sherwood_v3_entry<T>* next = nullptr;
  int8_t distance_from_desired = -1;
  static constexpr int8_t special_end_value = 0;
  union {
    T value;
  };
};

inline int8_t log2(uint64_t value) {
  static constexpr int8_t table[64] = {
      63, 0,  58, 1,  59, 47, 53, 2,  60, 39, 48, 27, 54, 33, 42, 3,
      61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4,
      62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21,
      56, 45, 25, 31, 35, 16, 9,  12, 44, 24, 15, 8,  23, 7,  6,  5};
  value |= value >> 1;
  value |= value >> 2;
  value |= value >> 4;
  value |= value >> 8;
  value |= value >> 16;
  value |= value >> 32;
  return table[((value - (value >> 1)) * 0x07EDD5E59A4E28C2) >> 58];
}

template <typename T, bool>
struct AssignIfTrue {
  void operator()(T& lhs, const T& rhs) {
    lhs = rhs;
  }
  void operator()(T& lhs, T&& rhs) {
    lhs = std::move(rhs);
  }
};
template <typename T>
struct AssignIfTrue<T, false> {
  void operator()(T&, const T&) {}
  void operator()(T&, T&&) {}
};

inline uint64_t next_power_of_two(uint64_t i) {
  --i;
  i |= i >> 1;
  i |= i >> 2;
  i |= i >> 4;
  i |= i >> 8;
  i |= i >> 16;
  i |= i >> 32;
  ++i;
  return i;
}

// Implementation taken from http://en.cppreference.com/w/cpp/types/void_t
// (it takes CWG1558 into account and also works for older compilers)
template <typename... Ts>
struct make_void {
  typedef void type;
};
template <typename... Ts>
using void_t = typename make_void<Ts...>::type;

template <typename T, typename = void>
struct HashPolicySelector {
  typedef fibonacci_hash_policy type;
};
template <typename T>
struct HashPolicySelector<T, void_t<typename T::hash_policy>> {
  typedef typename T::hash_policy type;
};

template <
    typename T,
    typename FindKey,
    typename ArgumentHash,
    typename Hasher,
    typename ArgumentEqual,
    typename Equal,
    typename ArgumentAlloc,
    typename EntryAlloc>
class sherwood_v3_table : private EntryAlloc, private Hasher, private Equal {
  using Entry = detailv3::sherwood_v3_entry<T>;
  using AllocatorTraits = std::allocator_traits<EntryAlloc>;
  using EntryPointer = typename AllocatorTraits::pointer;

public:
  struct convertible_to_iterator;

using value_type = T;
  using size_type = uint64_t;
  using difference_type = std::ptrdiff_t;
  using hasher = ArgumentHash;
  using key_equal = ArgumentEqual;
  using allocator_type = EntryAlloc;
  using reference = value_type&;
  using const_reference = const value_type&;
  using pointer = value_type*;
  using const_pointer = const value_type*;

sherwood_v3_table() {}
  explicit sherwood_v3_table(
      size_type bucket_count,
      const ArgumentHash& hash = ArgumentHash(),
      const ArgumentEqual& equal = ArgumentEqual(),
      const ArgumentAlloc& alloc = ArgumentAlloc())
      : EntryAlloc(alloc), Hasher(hash), Equal(equal) {
    rehash(bucket_count);
  }
  sherwood_v3_table(size_type bucket_count, const ArgumentAlloc& alloc)
      : sherwood_v3_table(
            bucket_count,
            ArgumentHash(),
            ArgumentEqual(),
            alloc) {}
  sherwood_v3_table(
      size_type bucket_count,
      const ArgumentHash& hash,
      const ArgumentAlloc& alloc)
      : sherwood_v3_table(bucket_count, hash, ArgumentEqual(), alloc) {}
  explicit sherwood_v3_table(const ArgumentAlloc& alloc) : EntryAlloc(alloc) {}
  template <typename It>
  sherwood_v3_table(
      It first,
      It last,
      size_type bucket_count = 0,
      const ArgumentHash& hash = ArgumentHash(),
      const ArgumentEqual& equal = ArgumentEqual(),
      const ArgumentAlloc& alloc = ArgumentAlloc())
      : sherwood_v3_table(bucket_count, hash, equal, alloc) {
    insert(first, last);
  }
  template <typename It>
  sherwood_v3_table(
      It first,
      It last,
      size_type bucket_count,
      const ArgumentAlloc& alloc)
      : sherwood_v3_table(
            first,
            last,
            bucket_count,
            ArgumentHash(),
            ArgumentEqual(),
            alloc) {}
  template <typename It>
  sherwood_v3_table(
      It first,
      It last,
      size_type bucket_count,
      const ArgumentHash& hash,
      const ArgumentAlloc& alloc)
      : sherwood_v3_table(
            first,
            last,
            bucket_count,
            hash,
            ArgumentEqual(),
            alloc) {}
  sherwood_v3_table(
      std::initializer_list<T> il,
      size_type bucket_count = 0,
      const ArgumentHash& hash = ArgumentHash(),
      const ArgumentEqual& equal = ArgumentEqual(),
      const ArgumentAlloc& alloc = ArgumentAlloc())
      : sherwood_v3_table(bucket_count, hash, equal, alloc) {
    if (bucket_count == 0)
      rehash(il.size());
    insert(il.begin(), il.end());
  }
  sherwood_v3_table(
      std::initializer_list<T> il,
      size_type bucket_count,
      const ArgumentAlloc& alloc)
      : sherwood_v3_table(
            il,
            bucket_count,
            ArgumentHash(),
            ArgumentEqual(),
            alloc) {}
  sherwood_v3_table(
      std::initializer_list<T> il,
      size_type bucket_count,
      const ArgumentHash& hash,
      const ArgumentAlloc& alloc)
      : sherwood_v3_table(il, bucket_count, hash, ArgumentEqual(), alloc) {}
  sherwood_v3_table(const sherwood_v3_table& other)
      : sherwood_v3_table(
            other,
            AllocatorTraits::select_on_container_copy_construction(
                other.get_allocator())) {}
  sherwood_v3_table(const sherwood_v3_table& other, const ArgumentAlloc& alloc)
      : EntryAlloc(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, max_lookups);
      throw;
    }
  }
  sherwood_v3_table(sherwood_v3_table&& other) noexcept
      : EntryAlloc(std::move(other)),
        Hasher(std::move(other)),
        Equal(std::move(other)) {
    swap_pointers(other);
  }
  sherwood_v3_table(
      sherwood_v3_table&& other,
      const ArgumentAlloc& alloc) noexcept
      : EntryAlloc(alloc), Hasher(std::move(other)), Equal(std::move(other)) {
    swap_pointers(other);
  }
  sherwood_v3_table& operator=(const sherwood_v3_table& other) {
    if (this == std::addressof(other))
      return *this;

clear();
    if (AllocatorTraits::propagate_on_container_copy_assignment::value) {
      if (static_cast<EntryAlloc&>(*this) !=
          static_cast<const EntryAlloc&>(other)) {
        reset_to_empty_state();
      }
      AssignIfTrue<
          EntryAlloc,
          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_v3_table& operator=(sherwood_v3_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<
          EntryAlloc,
          AllocatorTraits::propagate_on_container_move_assignment::value>()(
          *this, std::move(other));
      swap_pointers(other);
    } else if (
        static_cast<EntryAlloc&>(*this) == static_cast<EntryAlloc&>(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_v3_table() {
    clear();
    deallocate_data(entries, num_slots_minus_one, max_lookups);
  }

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 {
    templated_iterator() = default;
    templated_iterator(EntryPointer current) : current(current) {}
    EntryPointer current = EntryPointer();

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.current == rhs.current;
    }
    friend bool operator!=(
        const templated_iterator& lhs,
        const templated_iterator& rhs) {
      return !(lhs == rhs);
    }

templated_iterator& operator++() {
      current = current->next;
      return *this;
    }
    templated_iterator operator++(int) {
      templated_iterator copy(*this);
      ++*this;
      return copy;
    }

ValueType& operator*() const {
      return current->value;
    }
    ValueType* operator->() const {
      return std::addressof(current->value);
    }

// the template automatically disables the operator when value_type is
    // already const, because that would cause a lot of compiler warnings
    // otherwise.
    template <
        class target_type = const value_type,
        class = typename std::enable_if<
            std::is_same<target_type, const value_type>::value &&
            !std::is_same<target_type, value_type>::value>::type>
    operator templated_iterator<target_type>() const {
      return {current};
    }
  };
  using iterator = templated_iterator<value_type>;
  using const_iterator = templated_iterator<const value_type>;

iterator begin() {
    return sentinel->next;
  }
  const_iterator begin() const {
    return sentinel->next;
  }
  const_iterator cbegin() const {
    return begin();
  }
  iterator end() {
    return sentinel;
  }
  const_iterator end() const {
    return sentinel;
  }
  const_iterator cend() const {
    return end();
  }

iterator find(const FindKey& key) {
    uint64_t index =
        hash_policy.index_for_hash(hash_object(key), num_slots_minus_one);
    EntryPointer it = entries + ptrdiff_t(index);
    for (int8_t distance = 0; it->distance_from_desired >= distance;
         ++distance, ++it) {
      if (compares_equal(key, it->value))
        return {it};
    }
    return end();
  }
  const_iterator find(const FindKey& key) const {
    return const_cast<sherwood_v3_table*>(this)->find(key);
  }
  uint64_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>
  std::pair<iterator, bool> emplace(Key&& key, Args&&... args) {
    uint64_t index =
        hash_policy.index_for_hash(hash_object(key), num_slots_minus_one);
    EntryPointer current_entry = entries + ptrdiff_t(index);
    int8_t distance_from_desired = 0;
    for (; current_entry->distance_from_desired >= distance_from_desired;
         ++current_entry, ++distance_from_desired) {
      // insertion of an existing key does not change ordering
      if (compares_equal(key, current_entry->value))
        return {{current_entry}, false};
    }
    return emplace_new_key(
        distance_from_desired,
        current_entry,
        std::forward<Key>(key),
        std::forward<Args>(args)...);
  }

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(uint64_t num_buckets) {
    num_buckets = std::max(
        num_buckets,
        static_cast<uint64_t>(
            std::ceil(num_elements / static_cast<double>(_max_load_factor))));
    if (num_buckets == 0) {
      reset_to_empty_state();
      return;
    }
    auto new_prime_index = hash_policy.next_size_over(num_buckets);
    if (num_buckets == bucket_count())
      return;
    int8_t new_max_lookups = compute_max_lookups(num_buckets);
    EntryPointer new_buckets(
        AllocatorTraits::allocate(*this, num_buckets + new_max_lookups));
    EntryPointer special_end_item =
        new_buckets + static_cast<ptrdiff_t>(num_buckets + new_max_lookups - 1);
    for (EntryPointer it = new_buckets; it != special_end_item; ++it)
      it->distance_from_desired = -1;
    special_end_item->distance_from_desired = Entry::special_end_value;
    std::swap(entries, new_buckets);
    std::swap(num_slots_minus_one, num_buckets);
    --num_slots_minus_one;
    hash_policy.commit(new_prime_index);
    int8_t old_max_lookups = max_lookups;
    max_lookups = new_max_lookups;
    num_elements = 0;

auto start = sentinel->next;
    // point sentinel to itself;
    reset_list();
    // reinsert list
    for (EntryPointer it = start; it != sentinel;) {
      auto next = it->next;
      emplace(std::move(it->value));
      it->destroy_value();
      it = next;
    }

deallocate_data(new_buckets, num_buckets, old_max_lookups);
  }

void reserve(uint64_t num_elements) {
    uint64_t required_buckets = num_buckets_for_reserve(num_elements);
    if (required_buckets > bucket_count())
      rehash(required_buckets);
  }

void replace_linked_list_position(
      EntryPointer to_be_replaced,
      EntryPointer new_node) {
    remove_from_list(new_node);
    insert_after(new_node, to_be_replaced->prev);
    remove_from_list(to_be_replaced);
  }

// 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) {
    EntryPointer current = to_erase.current;
    remove_from_list(current);
    current->destroy_value();
    --num_elements;

for (EntryPointer next = current + ptrdiff_t(1);
         !next->is_at_desired_position();
         ++current, ++next) {
      // if an entry is being removed, and there are other entries with the
      // same hash, the other entries get moved to their desired position by
      // reinserting.
      current->emplace(next->distance_from_desired - 1, std::move(next->value));
      replace_linked_list_position(next, current);
      next->destroy_value();
    }
    return {to_erase.current};
  }

iterator erase(const_iterator begin_it, const_iterator end_it) {
    // whenever an entry is removed and there are other entries with the same
    // hash, the other entries must get moved to their desired position.
    // any reference to a moved entry is invalidated.
    // here, we iterate through the range, and make sure that we update
    // the pointer to our next entry in the list or the end of the iterator
    // when it is invalidated.

auto curr_iter = begin_it.current;
    auto next_iter = curr_iter->next;
    auto end_iter = end_it.current;

while (curr_iter != end_iter) {
      remove_from_list(curr_iter);
      curr_iter->destroy_value();
      --num_elements;

for (EntryPointer next_hash_slot = curr_iter + ptrdiff_t(1);
           !next_hash_slot->is_at_desired_position();
           ++curr_iter, ++next_hash_slot) {
        curr_iter->emplace(
            next_hash_slot->distance_from_desired - 1,
            std::move(next_hash_slot->value));
        replace_linked_list_position(next_hash_slot, curr_iter);
        next_hash_slot->destroy_value();

// we are invalidating next_iter or end_iter
        if (next_hash_slot == end_iter) {
          end_iter = curr_iter;
        } else if (next_hash_slot == next_iter) {
          next_iter = curr_iter;
        }
      }
      curr_iter = next_iter;
      next_iter = curr_iter->next;
    }

return {end_iter};
  }

uint64_t erase(const FindKey& key) {
    auto found = find(key);
    if (found == end())
      return 0;
    else {
      erase(found);
      return 1;
    }
  }

void clear() {
    for (EntryPointer it = entries,
                      end = it +
             static_cast<ptrdiff_t>(num_slots_minus_one + max_lookups);
         it != end;
         ++it) {
      if (it->has_value())
        it->destroy_value();
    }
    reset_list();
    num_elements = 0;
  }

void shrink_to_fit() {
    rehash_for_other_container(*this);
  }

void swap(sherwood_v3_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<EntryAlloc&>(*this), static_cast<EntryAlloc&>(other));
  }

uint64_t size() const {
    return num_elements;
  }
  uint64_t max_size() const {
    return (AllocatorTraits::max_size(*this)) / sizeof(Entry);
  }
  uint64_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) - min_lookups) / sizeof(Entry);
  }
  uint64_t bucket(const FindKey& key) const {
    return hash_policy.index_for_hash(hash_object(key), num_slots_minus_one);
  }
  float load_factor() const {
    uint64_t buckets = bucket_count();
    if (buckets)
      return static_cast<float>(num_elements) / bucket_count();
    else
      return 0;
  }
  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:
  EntryPointer entries = empty_default_table();
  uint64_t num_slots_minus_one = 0;
  typename HashPolicySelector<ArgumentHash>::type hash_policy;
  int8_t max_lookups = detailv3::min_lookups - 1;
  float _max_load_factor = 0.5f;
  uint64_t num_elements = 0;
  std::unique_ptr<sherwood_v3_entry<T>> sentinel_val;

// head of doubly linked list
  EntryPointer sentinel = initSentinel();

EntryPointer initSentinel() {
    // needs to be a pointer so that hash map can be used with forward declared
    // types
    sentinel_val = std::make_unique<sherwood_v3_entry<T>>();
    sentinel = sentinel_val.get();
    reset_list();
    return sentinel;
  }

EntryPointer empty_default_table() {
    EntryPointer result =
        AllocatorTraits::allocate(*this, detailv3::min_lookups);
    EntryPointer special_end_item =
        result + static_cast<ptrdiff_t>(detailv3::min_lookups - 1);
    for (EntryPointer it = result; it != special_end_item; ++it)
      it->distance_from_desired = -1;
    special_end_item->distance_from_desired = Entry::special_end_value;
    return result;
  }

static int8_t compute_max_lookups(uint64_t num_buckets) {
    int8_t desired = detailv3::log2(num_buckets);
    return std::max(detailv3::min_lookups, desired);
  }

uint64_t num_buckets_for_reserve(uint64_t num_elements) const {
    return static_cast<uint64_t>(std::ceil(
        num_elements / std::min(0.5, static_cast<double>(_max_load_factor))));
  }
  void rehash_for_other_container(const sherwood_v3_table& other) {
    rehash(
        std::min(num_buckets_for_reserve(other.size()), other.bucket_count()));
  }

void swap_pointers(sherwood_v3_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_lookups, other.max_lookups);
    swap(_max_load_factor, other._max_load_factor);
    swap(sentinel, other.sentinel);
    swap(sentinel_val, other.sentinel_val);
  }

void reset_list() {
    sentinel->next = sentinel;
    sentinel->prev = sentinel;
  }

void remove_from_list(EntryPointer elem) {
    elem->prev->next = elem->next;
    elem->next->prev = elem->prev;
  }

void insert_after(EntryPointer new_elem, EntryPointer prev) {
    auto next = prev->next;

prev->next = new_elem;
    new_elem->prev = prev;

new_elem->next = next;
    next->prev = new_elem;
  }

void swap_adjacent_nodes(EntryPointer before, EntryPointer after) {
    // sentinel stays consant, so before->prev cannot equal after
    auto before_prev = before->prev;
    auto after_next = after->next;

before_prev->next = after;
    after->prev = before_prev;

after_next->prev = before;
    before->next = after_next;

before->prev = after;
    after->next = before;
  }

void swap_positions(EntryPointer p1, EntryPointer p2) {
    if (p1 == p2) {
      return;
    }
    if (p1->next == p2) {
      return swap_adjacent_nodes(p1, p2);
    } else if (p2->next == p1) {
      return swap_adjacent_nodes(p2, p1);
    }

auto p1_prev = p1->prev;
    auto p1_next = p1->next;

auto p2_prev = p2->prev;
    auto p2_next = p2->next;

p1_prev->next = p2;
    p2->prev = p1_prev;

p1_next->prev = p2;
    p2->next = p1_next;

p2_prev->next = p1;
    p1->prev = p2_prev;

p2_next->prev = p1;
    p1->next = p2_next;
  }

void append_to_list(EntryPointer new_tail) {
    insert_after(new_tail, sentinel->prev);
  }

template <typename Key, typename... Args>
  SKA_NOINLINE(std::pair<iterator, bool>)
  emplace_new_key(
      int8_t distance_from_desired,
      EntryPointer current_entry,
      Key&& key,
      Args&&... args) {
    using std::swap;
    if (num_slots_minus_one == 0 || distance_from_desired == max_lookups ||
        num_elements + 1 >
            (num_slots_minus_one + 1) * static_cast<double>(_max_load_factor)) {
      grow();
      return emplace(std::forward<Key>(key), std::forward<Args>(args)...);
    } else if (current_entry->is_empty()) {
      current_entry->emplace(
          distance_from_desired,
          std::forward<Key>(key),
          std::forward<Args>(args)...);
      ++num_elements;
      append_to_list(current_entry);
      return {{current_entry}, true};
    }
    value_type to_insert(std::forward<Key>(key), std::forward<Args>(args)...);
    swap(distance_from_desired, current_entry->distance_from_desired);
    // We maintain the invariant that:
    // - result.current_entry contains the new value we're inserting
    //   and is in the LinkedList position of to_insert
    // - to_insert contains the value that reprseents the position of
    //   result.current_entry
    swap(to_insert, current_entry->value);
    iterator result = {current_entry};
    for (++distance_from_desired, ++current_entry;; ++current_entry) {
      if (current_entry->is_empty()) {
        current_entry->emplace(distance_from_desired, std::move(to_insert));
        append_to_list(current_entry);
        // now we can swap back the displaced value to its correct position,
        // putting the new value we're inserting to the front of the list
        swap_positions(current_entry, result.current);
        ++num_elements;
        return {result, true};
      } else if (current_entry->distance_from_desired < distance_from_desired) {
        swap(distance_from_desired, current_entry->distance_from_desired);
        swap(to_insert, current_entry->value);
        // to maintain our invariants we need to swap positions
        // of result.current & current_entry:
        swap_positions(result.current, current_entry);
        ++distance_from_desired;
      } else {
        ++distance_from_desired;
        if (distance_from_desired == max_lookups) {
          // the displaced element gets put back into its correct position
          // we grow the hash table, and then try again to reinsert the new
          // element
          swap(to_insert, result.current->value);
          grow();
          return emplace(std::move(to_insert));
        }
      }
    }
  }

void grow() {
    rehash(std::max(uint64_t(4), 2 * bucket_count()));
  }

void deallocate_data(
      EntryPointer begin,
      uint64_t num_slots_minus_one,
      int8_t max_lookups) {
    AllocatorTraits::deallocate(
        *this, begin, num_slots_minus_one + max_lookups + 1);
  }

void reset_to_empty_state() {
    deallocate_data(entries, num_slots_minus_one, max_lookups);
    entries = empty_default_table();
    num_slots_minus_one = 0;
    hash_policy.reset();
    max_lookups = detailv3::min_lookups - 1;
  }

template <typename U>
  uint64_t hash_object(const U& key) {
    return static_cast<Hasher&>(*this)(key);
  }
  template <typename U>
  uint64_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);
  }

public:
  struct convertible_to_iterator {
    EntryPointer it;

operator iterator() {
      if (it->has_value())
        return {it};
      else
        return ++iterator{it};
    }
    operator const_iterator() {
      if (it->has_value())
        return {it};
      else
        return ++const_iterator{it};
    }
  };
};
} // namespace detailv3

struct prime_number_hash_policy {
  static uint64_t mod0(uint64_t) {
    return 0llu;
  }
  static uint64_t mod2(uint64_t hash) {
    return hash % 2llu;
  }
  static uint64_t mod3(uint64_t hash) {
    return hash % 3llu;
  }
  static uint64_t mod5(uint64_t hash) {
    return hash % 5llu;
  }
  static uint64_t mod7(uint64_t hash) {
    return hash % 7llu;
  }
  static uint64_t mod11(uint64_t hash) {
    return hash % 11llu;
  }
  static uint64_t mod13(uint64_t hash) {
    return hash % 13llu;
  }
  static uint64_t mod17(uint64_t hash) {
    return hash % 17llu;
  }
  static uint64_t mod23(uint64_t hash) {
    return hash % 23llu;
  }
  static uint64_t mod29(uint64_t hash) {
    return hash % 29llu;
  }
  static uint64_t mod37(uint64_t hash) {
    return hash % 37llu;
  }
  static uint64_t mod47(uint64_t hash) {
    return hash % 47llu;
  }
  static uint64_t mod59(uint64_t hash) {
    return hash % 59llu;
  }
  static uint64_t mod73(uint64_t hash) {
    return hash % 73llu;
  }
  static uint64_t mod97(uint64_t hash) {
    return hash % 97llu;
  }
  static uint64_t mod127(uint64_t hash) {
    return hash % 127llu;
  }
  static uint64_t mod151(uint64_t hash) {
    return hash % 151llu;
  }
  static uint64_t mod197(uint64_t hash) {
    return hash % 197llu;
  }
  static uint64_t mod251(uint64_t hash) {
    return hash % 251llu;
  }
  static uint64_t mod313(uint64_t hash) {
    return hash % 313llu;
  }
  static uint64_t mod397(uint64_t hash) {
    return hash % 397llu;
  }
  static uint64_t mod499(uint64_t hash) {
    return hash % 499llu;
  }
  static uint64_t mod631(uint64_t hash) {
    return hash % 631llu;
  }
  static uint64_t mod797(uint64_t hash) {
    return hash % 797llu;
  }
  static uint64_t mod1009(uint64_t hash) {
    return hash % 1009llu;
  }
  static uint64_t mod1259(uint64_t hash) {
    return hash % 1259llu;
  }
  static uint64_t mod1597(uint64_t hash) {
    return hash % 1597llu;
  }
  static uint64_t mod2011(uint64_t hash) {
    return hash % 2011llu;
  }
  static uint64_t mod2539(uint64_t hash) {
    return hash % 2539llu;
  }
  static uint64_t mod3203(uint64_t hash) {
    return hash % 3203llu;
  }
  static uint64_t mod4027(uint64_t hash) {
    return hash % 4027llu;
  }
  static uint64_t mod5087(uint64_t hash) {
    return hash % 5087llu;
  }
  static uint64_t mod6421(uint64_t hash) {
    return hash % 6421llu;
  }
  static uint64_t mod8089(uint64_t hash) {
    return hash % 8089llu;
  }
  static uint64_t mod10193(uint64_t hash) {
    return hash % 10193llu;
  }
  static uint64_t mod12853(uint64_t hash) {
    return hash % 12853llu;
  }
  static uint64_t mod16193(uint64_t hash) {
    return hash % 16193llu;
  }
  static uint64_t mod20399(uint64_t hash) {
    return hash % 20399llu;
  }
  static uint64_t mod25717(uint64_t hash) {
    return hash % 25717llu;
  }
  static uint64_t mod32401(uint64_t hash) {
    return hash % 32401llu;
  }
  static uint64_t mod40823(uint64_t hash) {
    return hash % 40823llu;
  }
  static uint64_t mod51437(uint64_t hash) {
    return hash % 51437llu;
  }
  static uint64_t mod64811(uint64_t hash) {
    return hash % 64811llu;
  }
  static uint64_t mod81649(uint64_t hash) {
    return hash % 81649llu;
  }
  static uint64_t mod102877(uint64_t hash) {
    return hash % 102877llu;
  }
  static uint64_t mod129607(uint64_t hash) {
    return hash % 129607llu;
  }
  static uint64_t mod163307(uint64_t hash) {
    return hash % 163307llu;
  }
  static uint64_t mod205759(uint64_t hash) {
    return hash % 205759llu;
  }
  static uint64_t mod259229(uint64_t hash) {
    return hash % 259229llu;
  }
  static uint64_t mod326617(uint64_t hash) {
    return hash % 326617llu;
  }
  static uint64_t mod411527(uint64_t hash) {
    return hash % 411527llu;
  }
  static uint64_t mod518509(uint64_t hash) {
    return hash % 518509llu;
  }
  static uint64_t mod653267(uint64_t hash) {
    return hash % 653267llu;
  }
  static uint64_t mod823117(uint64_t hash) {
    return hash % 823117llu;
  }
  static uint64_t mod1037059(uint64_t hash) {
    return hash % 1037059llu;
  }
  static uint64_t mod1306601(uint64_t hash) {
    return hash % 1306601llu;
  }
  static uint64_t mod1646237(uint64_t hash) {
    return hash % 1646237llu;
  }
  static uint64_t mod2074129(uint64_t hash) {
    return hash % 2074129llu;
  }
  static uint64_t mod2613229(uint64_t hash) {
    return hash % 2613229llu;
  }
  static uint64_t mod3292489(uint64_t hash) {
    return hash % 3292489llu;
  }
  static uint64_t mod4148279(uint64_t hash) {
    return hash % 4148279llu;
  }
  static uint64_t mod5226491(uint64_t hash) {
    return hash % 5226491llu;
  }
  static uint64_t mod6584983(uint64_t hash) {
    return hash % 6584983llu;
  }
  static uint64_t mod8296553(uint64_t hash) {
    return hash % 8296553llu;
  }
  static uint64_t mod10453007(uint64_t hash) {
    return hash % 10453007llu;
  }
  static uint64_t mod13169977(uint64_t hash) {
    return hash % 13169977llu;
  }
  static uint64_t mod16593127(uint64_t hash) {
    return hash % 16593127llu;
  }
  static uint64_t mod20906033(uint64_t hash) {
    return hash % 20906033llu;
  }
  static uint64_t mod26339969(uint64_t hash) {
    return hash % 26339969llu;
  }
  static uint64_t mod33186281(uint64_t hash) {
    return hash % 33186281llu;
  }
  static uint64_t mod41812097(uint64_t hash) {
    return hash % 41812097llu;
  }
  static uint64_t mod52679969(uint64_t hash) {
    return hash % 52679969llu;
  }
  static uint64_t mod66372617(uint64_t hash) {
    return hash % 66372617llu;
  }
  static uint64_t mod83624237(uint64_t hash) {
    return hash % 83624237llu;
  }
  static uint64_t mod105359939(uint64_t hash) {
    return hash % 105359939llu;
  }
  static uint64_t mod132745199(uint64_t hash) {
    return hash % 132745199llu;
  }
  static uint64_t mod167248483(uint64_t hash) {
    return hash % 167248483llu;
  }
  static uint64_t mod210719881(uint64_t hash) {
    return hash % 210719881llu;
  }
  static uint64_t mod265490441(uint64_t hash) {
    return hash % 265490441llu;
  }
  static uint64_t mod334496971(uint64_t hash) {
    return hash % 334496971llu;
  }
  static uint64_t mod421439783(uint64_t hash) {
    return hash % 421439783llu;
  }
  static uint64_t mod530980861(uint64_t hash) {
    return hash % 530980861llu;
  }
  static uint64_t mod668993977(uint64_t hash) {
    return hash % 668993977llu;
  }
  static uint64_t mod842879579(uint64_t hash) {
    return hash % 842879579llu;
  }
  static uint64_t mod1061961721(uint64_t hash) {
    return hash % 1061961721llu;
  }
  static uint64_t mod1337987929(uint64_t hash) {
    return hash % 1337987929llu;
  }
  static uint64_t mod1685759167(uint64_t hash) {
    return hash % 1685759167llu;
  }
  static uint64_t mod2123923447(uint64_t hash) {
    return hash % 2123923447llu;
  }
  static uint64_t mod2675975881(uint64_t hash) {
    return hash % 2675975881llu;
  }
  static uint64_t mod3371518343(uint64_t hash) {
    return hash % 3371518343llu;
  }
  static uint64_t mod4247846927(uint64_t hash) {
    return hash % 4247846927llu;
  }
  static uint64_t mod5351951779(uint64_t hash) {
    return hash % 5351951779llu;
  }
  static uint64_t mod6743036717(uint64_t hash) {
    return hash % 6743036717llu;
  }
  static uint64_t mod8495693897(uint64_t hash) {
    return hash % 8495693897llu;
  }
  static uint64_t mod10703903591(uint64_t hash) {
    return hash % 10703903591llu;
  }
  static uint64_t mod13486073473(uint64_t hash) {
    return hash % 13486073473llu;
  }
  static uint64_t mod16991387857(uint64_t hash) {
    return hash % 16991387857llu;
  }
  static uint64_t mod21407807219(uint64_t hash) {
    return hash % 21407807219llu;
  }
  static uint64_t mod26972146961(uint64_t hash) {
    return hash % 26972146961llu;
  }
  static uint64_t mod33982775741(uint64_t hash) {
    return hash % 33982775741llu;
  }
  static uint64_t mod42815614441(uint64_t hash) {
    return hash % 42815614441llu;
  }
  static uint64_t mod53944293929(uint64_t hash) {
    return hash % 53944293929llu;
  }
  static uint64_t mod67965551447(uint64_t hash) {
    return hash % 67965551447llu;
  }
  static uint64_t mod85631228929(uint64_t hash) {
    return hash % 85631228929llu;
  }
  static uint64_t mod107888587883(uint64_t hash) {
    return hash % 107888587883llu;
  }
  static uint64_t mod135931102921(uint64_t hash) {
    return hash % 135931102921llu;
  }
  static uint64_t mod171262457903(uint64_t hash) {
    return hash % 171262457903llu;
  }
  static uint64_t mod215777175787(uint64_t hash) {
    return hash % 215777175787llu;
  }
  static uint64_t mod271862205833(uint64_t hash) {
    return hash % 271862205833llu;
  }
  static uint64_t mod342524915839(uint64_t hash) {
    return hash % 342524915839llu;
  }
  static uint64_t mod431554351609(uint64_t hash) {
    return hash % 431554351609llu;
  }
  static uint64_t mod543724411781(uint64_t hash) {
    return hash % 543724411781llu;
  }
  static uint64_t mod685049831731(uint64_t hash) {
    return hash % 685049831731llu;
  }
  static uint64_t mod863108703229(uint64_t hash) {
    return hash % 863108703229llu;
  }
  static uint64_t mod1087448823553(uint64_t hash) {
    return hash % 1087448823553llu;
  }
  static uint64_t mod1370099663459(uint64_t hash) {
    return hash % 1370099663459llu;
  }
  static uint64_t mod1726217406467(uint64_t hash) {
    return hash % 1726217406467llu;
  }
  static uint64_t mod2174897647073(uint64_t hash) {
    return hash % 2174897647073llu;
  }
  static uint64_t mod2740199326961(uint64_t hash) {
    return hash % 2740199326961llu;
  }
  static uint64_t mod3452434812973(uint64_t hash) {
    return hash % 3452434812973llu;
  }
  static uint64_t mod4349795294267(uint64_t hash) {
    return hash % 4349795294267llu;
  }
  static uint64_t mod5480398654009(uint64_t hash) {
    return hash % 5480398654009llu;
  }
  static uint64_t mod6904869625999(uint64_t hash) {
    return hash % 6904869625999llu;
  }
  static uint64_t mod8699590588571(uint64_t hash) {
    return hash % 8699590588571llu;
  }
  static uint64_t mod10960797308051(uint64_t hash) {
    return hash % 10960797308051llu;
  }
  static uint64_t mod13809739252051(uint64_t hash) {
    return hash % 13809739252051llu;
  }
  static uint64_t mod17399181177241(uint64_t hash) {
    return hash % 17399181177241llu;
  }
  static uint64_t mod21921594616111(uint64_t hash) {
    return hash % 21921594616111llu;
  }
  static uint64_t mod27619478504183(uint64_t hash) {
    return hash % 27619478504183llu;
  }
  static uint64_t mod34798362354533(uint64_t hash) {
    return hash % 34798362354533llu;
  }
  static uint64_t mod43843189232363(uint64_t hash) {
    return hash % 43843189232363llu;
  }
  static uint64_t mod55238957008387(uint64_t hash) {
    return hash % 55238957008387llu;
  }
  static uint64_t mod69596724709081(uint64_t hash) {
    return hash % 69596724709081llu;
  }
  static uint64_t mod87686378464759(uint64_t hash) {
    return hash % 87686378464759llu;
  }
  static uint64_t mod110477914016779(uint64_t hash) {
    return hash % 110477914016779llu;
  }
  static uint64_t mod139193449418173(uint64_t hash) {
    return hash % 139193449418173llu;
  }
  static uint64_t mod175372756929481(uint64_t hash) {
    return hash % 175372756929481llu;
  }
  static uint64_t mod220955828033581(uint64_t hash) {
    return hash % 220955828033581llu;
  }
  static uint64_t mod278386898836457(uint64_t hash) {
    return hash % 278386898836457llu;
  }
  static uint64_t mod350745513859007(uint64_t hash) {
    return hash % 350745513859007llu;
  }
  static uint64_t mod441911656067171(uint64_t hash) {
    return hash % 441911656067171llu;
  }
  static uint64_t mod556773797672909(uint64_t hash) {
    return hash % 556773797672909llu;
  }
  static uint64_t mod701491027718027(uint64_t hash) {
    return hash % 701491027718027llu;
  }
  static uint64_t mod883823312134381(uint64_t hash) {
    return hash % 883823312134381llu;
  }
  static uint64_t mod1113547595345903(uint64_t hash) {
    return hash % 1113547595345903llu;
  }
  static uint64_t mod1402982055436147(uint64_t hash) {
    return hash % 1402982055436147llu;
  }
  static uint64_t mod1767646624268779(uint64_t hash) {
    return hash % 1767646624268779llu;
  }
  static uint64_t mod2227095190691797(uint64_t hash) {
    return hash % 2227095190691797llu;
  }
  static uint64_t mod2805964110872297(uint64_t hash) {
    return hash % 2805964110872297llu;
  }
  static uint64_t mod3535293248537579(uint64_t hash) {
    return hash % 3535293248537579llu;
  }
  static uint64_t mod4454190381383713(uint64_t hash) {
    return hash % 4454190381383713llu;
  }
  static uint64_t mod5611928221744609(uint64_t hash) {
    return hash % 5611928221744609llu;
  }
  static uint64_t mod7070586497075177(uint64_t hash) {
    return hash % 7070586497075177llu;
  }
  static uint64_t mod8908380762767489(uint64_t hash) {
    return hash % 8908380762767489llu;
  }
  static uint64_t mod11223856443489329(uint64_t hash) {
    return hash % 11223856443489329llu;
  }
  static uint64_t mod14141172994150357(uint64_t hash) {
    return hash % 14141172994150357llu;
  }
  static uint64_t mod17816761525534927(uint64_t hash) {
    return hash % 17816761525534927llu;
  }
  static uint64_t mod22447712886978529(uint64_t hash) {
    return hash % 22447712886978529llu;
  }
  static uint64_t mod28282345988300791(uint64_t hash) {
    return hash % 28282345988300791llu;
  }
  static uint64_t mod35633523051069991(uint64_t hash) {
    return hash % 35633523051069991llu;
  }
  static uint64_t mod44895425773957261(uint64_t hash) {
    return hash % 44895425773957261llu;
  }
  static uint64_t mod56564691976601587(uint64_t hash) {
    return hash % 56564691976601587llu;
  }
  static uint64_t mod71267046102139967(uint64_t hash) {
    return hash % 71267046102139967llu;
  }
  static uint64_t mod89790851547914507(uint64_t hash) {
    return hash % 89790851547914507llu;
  }
  static uint64_t mod113129383953203213(uint64_t hash) {
    return hash % 113129383953203213llu;
  }
  static uint64_t mod142534092204280003(uint64_t hash) {
    return hash % 142534092204280003llu;
  }
  static uint64_t mod179581703095829107(uint64_t hash) {
    return hash % 179581703095829107llu;
  }
  static uint64_t mod226258767906406483(uint64_t hash) {
    return hash % 226258767906406483llu;
  }
  static uint64_t mod285068184408560057(uint64_t hash) {
    return hash % 285068184408560057llu;
  }
  static uint64_t mod359163406191658253(uint64_t hash) {
    return hash % 359163406191658253llu;
  }
  static uint64_t mod452517535812813007(uint64_t hash) {
    return hash % 452517535812813007llu;
  }
  static uint64_t mod570136368817120201(uint64_t hash) {
    return hash % 570136368817120201llu;
  }
  static uint64_t mod718326812383316683(uint64_t hash) {
    return hash % 718326812383316683llu;
  }
  static uint64_t mod905035071625626043(uint64_t hash) {
    return hash % 905035071625626043llu;
  }
  static uint64_t mod1140272737634240411(uint64_t hash) {
    return hash % 1140272737634240411llu;
  }
  static uint64_t mod1436653624766633509(uint64_t hash) {
    return hash % 1436653624766633509llu;
  }
  static uint64_t mod1810070143251252131(uint64_t hash) {
    return hash % 1810070143251252131llu;
  }
  static uint64_t mod2280545475268481167(uint64_t hash) {
    return hash % 2280545475268481167llu;
  }
  static uint64_t mod2873307249533267101(uint64_t hash) {
    return hash % 2873307249533267101llu;
  }
  static uint64_t mod3620140286502504283(uint64_t hash) {
    return hash % 3620140286502504283llu;
  }
  static uint64_t mod4561090950536962147(uint64_t hash) {
    return hash % 4561090950536962147llu;
  }
  static uint64_t mod5746614499066534157(uint64_t hash) {
    return hash % 5746614499066534157llu;
  }
  static uint64_t mod7240280573005008577(uint64_t hash) {
    return hash % 7240280573005008577llu;
  }
  static uint64_t mod9122181901073924329(uint64_t hash) {
    return hash % 9122181901073924329llu;
  }
  static uint64_t mod11493228998133068689(uint64_t hash) {
    return hash % 11493228998133068689llu;
  }
  static uint64_t mod14480561146010017169(uint64_t hash) {
    return hash % 14480561146010017169llu;
  }
  static uint64_t mod18446744073709551557(uint64_t hash) {
    return hash % 18446744073709551557llu;
  }

using mod_function = uint64_t (*)(uint64_t);

mod_function next_size_over(uint64_t& size) const {
    // prime numbers generated by the following method:
    // 1. start with a prime p = 2
    // 2. go to wolfram alpha and get p = NextPrime(2 * p)
    // 3. repeat 2. until you overflow 64 bits
    // you now have large gaps which you would hit if somebody called reserve()
    // with an unlucky number.
    // 4. to fill the gaps for every prime p go to wolfram alpha and get
    // ClosestPrime(p * 2^(1/3)) and ClosestPrime(p * 2^(2/3)) and put those in
    // the gaps
    // 5. get PrevPrime(2^64) and put it at the end
    static constexpr const uint64_t prime_list[] = {
        2llu,
        3llu,
        5llu,
        7llu,
        11llu,
        13llu,
        17llu,
        23llu,
        29llu,
        37llu,
        47llu,
        59llu,
        73llu,
        97llu,
        127llu,
        151llu,
        197llu,
        251llu,
        313llu,
        397llu,
        499llu,
        631llu,
        797llu,
        1009llu,
        1259llu,
        1597llu,
        2011llu,
        2539llu,
        3203llu,
        4027llu,
        5087llu,
        6421llu,
        8089llu,
        10193llu,
        12853llu,
        16193llu,
        20399llu,
        25717llu,
        32401llu,
        40823llu,
        51437llu,
        64811llu,
        81649llu,
        102877llu,
        129607llu,
        163307llu,
        205759llu,
        259229llu,
        326617llu,
        411527llu,
        518509llu,
        653267llu,
        823117llu,
        1037059llu,
        1306601llu,
        1646237llu,
        2074129llu,
        2613229llu,
        3292489llu,
        4148279llu,
        5226491llu,
        6584983llu,
        8296553llu,
        10453007llu,
        13169977llu,
        16593127llu,
        20906033llu,
        26339969llu,
        33186281llu,
        41812097llu,
        52679969llu,
        66372617llu,
        83624237llu,
        105359939llu,
        132745199llu,
        167248483llu,
        210719881llu,
        265490441llu,
        334496971llu,
        421439783llu,
        530980861llu,
        668993977llu,
        842879579llu,
        1061961721llu,
        1337987929llu,
        1685759167llu,
        2123923447llu,
        2675975881llu,
        3371518343llu,
        4247846927llu,
        5351951779llu,
        6743036717llu,
        8495693897llu,
        10703903591llu,
        13486073473llu,
        16991387857llu,
        21407807219llu,
        26972146961llu,
        33982775741llu,
        42815614441llu,
        53944293929llu,
        67965551447llu,
        85631228929llu,
        107888587883llu,
        135931102921llu,
        171262457903llu,
        215777175787llu,
        271862205833llu,
        342524915839llu,
        431554351609llu,
        543724411781llu,
        685049831731llu,
        863108703229llu,
        1087448823553llu,
        1370099663459llu,
        1726217406467llu,
        2174897647073llu,
        2740199326961llu,
        3452434812973llu,
        4349795294267llu,
        5480398654009llu,
        6904869625999llu,
        8699590588571llu,
        10960797308051llu,
        13809739252051llu,
        17399181177241llu,
        21921594616111llu,
        27619478504183llu,
        34798362354533llu,
        43843189232363llu,
        55238957008387llu,
        69596724709081llu,
        87686378464759llu,
        110477914016779llu,
        139193449418173llu,
        175372756929481llu,
        220955828033581llu,
        278386898836457llu,
        350745513859007llu,
        441911656067171llu,
        556773797672909llu,
        701491027718027llu,
        883823312134381llu,
        1113547595345903llu,
        1402982055436147llu,
        1767646624268779llu,
        2227095190691797llu,
        2805964110872297llu,
        3535293248537579llu,
        4454190381383713llu,
        5611928221744609llu,
        7070586497075177llu,
        8908380762767489llu,
        11223856443489329llu,
        14141172994150357llu,
        17816761525534927llu,
        22447712886978529llu,
        28282345988300791llu,
        35633523051069991llu,
        44895425773957261llu,
        56564691976601587llu,
        71267046102139967llu,
        89790851547914507llu,
        113129383953203213llu,
        142534092204280003llu,
        179581703095829107llu,
        226258767906406483llu,
        285068184408560057llu,
        359163406191658253llu,
        452517535812813007llu,
        570136368817120201llu,
        718326812383316683llu,
        905035071625626043llu,
        1140272737634240411llu,
        1436653624766633509llu,
        1810070143251252131llu,
        2280545475268481167llu,
        2873307249533267101llu,
        3620140286502504283llu,
        4561090950536962147llu,
        5746614499066534157llu,
        7240280573005008577llu,
        9122181901073924329llu,
        11493228998133068689llu,
        14480561146010017169llu,
        18446744073709551557llu};
    static constexpr uint64_t (*const mod_functions[])(uint64_t) = {
        &mod0,
        &mod2,
        &mod3,
        &mod5,
        &mod7,
        &mod11,
        &mod13,
        &mod17,
        &mod23,
        &mod29,
        &mod37,
        &mod47,
        &mod59,
        &mod73,
        &mod97,
        &mod127,
        &mod151,
        &mod197,
        &mod251,
        &mod313,
        &mod397,
        &mod499,
        &mod631,
        &mod797,
        &mod1009,
        &mod1259,
        &mod1597,
        &mod2011,
        &mod2539,
        &mod3203,
        &mod4027,
        &mod5087,
        &mod6421,
        &mod8089,
        &mod10193,
        &mod12853,
        &mod16193,
        &mod20399,
        &mod25717,
        &mod32401,
        &mod40823,
        &mod51437,
        &mod64811,
        &mod81649,
        &mod102877,
        &mod129607,
        &mod163307,
        &mod205759,
        &mod259229,
        &mod326617,
        &mod411527,
        &mod518509,
        &mod653267,
        &mod823117,
        &mod1037059,
        &mod1306601,
        &mod1646237,
        &mod2074129,
        &mod2613229,
        &mod3292489,
        &mod4148279,
        &mod5226491,
        &mod6584983,
        &mod8296553,
        &mod10453007,
        &mod13169977,
        &mod16593127,
        &mod20906033,
        &mod26339969,
        &mod33186281,
        &mod41812097,
        &mod52679969,
        &mod66372617,
        &mod83624237,
        &mod105359939,
        &mod132745199,
        &mod167248483,
        &mod210719881,
        &mod265490441,
        &mod334496971,
        &mod421439783,
        &mod530980861,
        &mod668993977,
        &mod842879579,
        &mod1061961721,
        &mod1337987929,
        &mod1685759167,
        &mod2123923447,
        &mod2675975881,
        &mod3371518343,
        &mod4247846927,
        &mod5351951779,
        &mod6743036717,
        &mod8495693897,
        &mod10703903591,
        &mod13486073473,
        &mod16991387857,
        &mod21407807219,
        &mod26972146961,
        &mod33982775741,
        &mod42815614441,
        &mod53944293929,
        &mod67965551447,
        &mod85631228929,
        &mod107888587883,
        &mod135931102921,
        &mod171262457903,
        &mod215777175787,
        &mod271862205833,
        &mod342524915839,
        &mod431554351609,
        &mod543724411781,
        &mod685049831731,
        &mod863108703229,
        &mod1087448823553,
        &mod1370099663459,
        &mod1726217406467,
        &mod2174897647073,
        &mod2740199326961,
        &mod3452434812973,
        &mod4349795294267,
        &mod5480398654009,
        &mod6904869625999,
        &mod8699590588571,
        &mod10960797308051,
        &mod13809739252051,
        &mod17399181177241,
        &mod21921594616111,
        &mod27619478504183,
        &mod34798362354533,
        &mod43843189232363,
        &mod55238957008387,
        &mod69596724709081,
        &mod87686378464759,
        &mod110477914016779,
        &mod139193449418173,
        &mod175372756929481,
        &mod220955828033581,
        &mod278386898836457,
        &mod350745513859007,
        &mod441911656067171,
        &mod556773797672909,
        &mod701491027718027,
        &mod883823312134381,
        &mod1113547595345903,
        &mod1402982055436147,
        &mod1767646624268779,
        &mod2227095190691797,
        &mod2805964110872297,
        &mod3535293248537579,
        &mod4454190381383713,
        &mod5611928221744609,
        &mod7070586497075177,
        &mod8908380762767489,
        &mod11223856443489329,
        &mod14141172994150357,
        &mod17816761525534927,
        &mod22447712886978529,
        &mod28282345988300791,
        &mod35633523051069991,
        &mod44895425773957261,
        &mod56564691976601587,
        &mod71267046102139967,
        &mod89790851547914507,
        &mod113129383953203213,
        &mod142534092204280003,
        &mod179581703095829107,
        &mod226258767906406483,
        &mod285068184408560057,
        &mod359163406191658253,
        &mod452517535812813007,
        &mod570136368817120201,
        &mod718326812383316683,
        &mod905035071625626043,
        &mod1140272737634240411,
        &mod1436653624766633509,
        &mod1810070143251252131,
        &mod2280545475268481167,
        &mod2873307249533267101,
        &mod3620140286502504283,
        &mod4561090950536962147,
        &mod5746614499066534157,
        &mod7240280573005008577,
        &mod9122181901073924329,
        &mod11493228998133068689,
        &mod14480561146010017169,
        &mod18446744073709551557};
    const uint64_t* found = std::lower_bound(
        std::begin(prime_list), std::end(prime_list) - 1, size);
    size = *found;
    return mod_functions[1 + found - prime_list];
  }
  void commit(mod_function new_mod_function) {
    current_mod_function = new_mod_function;
  }
  void reset() {
    current_mod_function = &mod0;
  }

uint64_t index_for_hash(uint64_t hash, uint64_t /*num_slots_minus_one*/)
      const {
    return current_mod_function(hash);
  }
  uint64_t keep_in_range(uint64_t index, uint64_t num_slots_minus_one) const {
    return index > num_slots_minus_one ? current_mod_function(index) : index;
  }

private:
  mod_function current_mod_function = &mod0;
};

struct power_of_two_hash_policy {
  uint64_t index_for_hash(uint64_t hash, uint64_t num_slots_minus_one) const {
    return hash & num_slots_minus_one;
  }
  uint64_t keep_in_range(uint64_t index, uint64_t num_slots_minus_one) const {
    return index_for_hash(index, num_slots_minus_one);
  }
  int8_t next_size_over(uint64_t& size) const {
    size = detailv3::next_power_of_two(size);
    return 0;
  }
  void commit(int8_t) {}
  void reset() {}
};

struct fibonacci_hash_policy {
  uint64_t index_for_hash(uint64_t hash, uint64_t /*num_slots_minus_one*/)
      const {
    return (11400714819323198485ull * hash) >> shift;
  }
  uint64_t keep_in_range(uint64_t index, uint64_t num_slots_minus_one) const {
    return index & num_slots_minus_one;
  }

int8_t next_size_over(uint64_t& size) const {
    size = std::max(uint64_t(2), detailv3::next_power_of_two(size));
    return 64 - detailv3::log2(size);
  }
  void commit(int8_t shift) {
    this->shift = shift;
  }
  void reset() {
    shift = 63;
  }

private:
  int8_t shift = 63;
};

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 order_preserving_flat_hash_map
    : public detailv3::sherwood_v3_table<
          std::pair<K, V>,
          K,
          H,
          detailv3::KeyOrValueHasher<K, std::pair<K, V>, H>,
          E,
          detailv3::KeyOrValueEquality<K, std::pair<K, V>, E>,
          A,
          typename std::allocator_traits<A>::template rebind_alloc<
              detailv3::sherwood_v3_entry<std::pair<K, V>>>> {
  using Table = detailv3::sherwood_v3_table<
      std::pair<K, V>,
      K,
      H,
      detailv3::KeyOrValueHasher<K, std::pair<K, V>, H>,
      E,
      detailv3::KeyOrValueEquality<K, std::pair<K, V>, E>,
      A,
      typename std::allocator_traits<A>::template rebind_alloc<
          detailv3::sherwood_v3_entry<std::pair<K, V>>>>;

public:
  using key_type = K;
  using mapped_type = V;

using Table::Table;
  order_preserving_flat_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;
  }

friend bool operator==(
      const order_preserving_flat_hash_map& lhs,
      const order_preserving_flat_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 order_preserving_flat_hash_map& lhs,
      const order_preserving_flat_hash_map& rhs) {
    return !(lhs == rhs);
  }

private:
  struct convertible_to_value {
    operator V() const {
      return V();
    }
  };
};

template <
    typename T,
    typename H = std::hash<T>,
    typename E = std::equal_to<T>,
    typename A = std::allocator<T>>
class flat_hash_set
    : public detailv3::sherwood_v3_table<
          T,
          T,
          H,
          detailv3::functor_storage<uint64_t, H>,
          E,
          detailv3::functor_storage<bool, E>,
          A,
          typename std::allocator_traits<A>::template rebind_alloc<
              detailv3::sherwood_v3_entry<T>>> {
  using Table = detailv3::sherwood_v3_table<
      T,
      T,
      H,
      detailv3::functor_storage<uint64_t, H>,
      E,
      detailv3::functor_storage<bool, E>,
      A,
      typename std::allocator_traits<A>::template rebind_alloc<
          detailv3::sherwood_v3_entry<T>>>;

public:
  using key_type = T;

using Table::Table;
  flat_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 flat_hash_set& lhs, const flat_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 flat_hash_set& lhs, const flat_hash_set& rhs) {
    return !(lhs == rhs);
  }
};

template <typename T>
struct power_of_two_std_hash : std::hash<T> {
  typedef ska_ordered::power_of_two_hash_policy hash_policy;
};

} // namespace ska_ordered

#ifndef _MSC_VER
#pragma GCC diagnostic pop
#endif

cmd: