# if defined(__SIZEOF_INT128__)

__uint128_t r = *a;

r *= *b;

*a = static_cast<uint64_t>(r);

*b = static_cast<uint64_t>(r >> 64U);

# elif defined(_MSC_VER) && defined(_M_X64)

*a = _umul128(*a, *b, b);

# else

uint64_t ha = *a >> 32U;

uint64_t hb = *b >> 32U;

uint64_t la = static_cast<uint32_t>(*a);

uint64_t lb = static_cast<uint32_t>(*b);

uint64_t hi{};

uint64_t lo{};

uint64_t rh = ha * hb;

uint64_t rm0 = ha * lb;

uint64_t rm1 = hb * la;

uint64_t rl = la * lb;

uint64_t t = rl + (rm0 << 32U);

auto c = static_cast<uint64_t>(t < rl);

lo = t + (rm1 << 32U);

c += static_cast<uint64_t>(lo < t);

hi = rh + (rm0 >> 32U) + (rm1 >> 32U) + c;

*a = lo;

*b = hi;

# endif

uint64_t v{};

std::memcpy(&v, p, 8U);

return v;

uint32_t v{};

std::memcpy(&v, p, 4);

return v;

static constexpr auto secret = std::array{UINT64_C(0xa0761d6478bd642f),

UINT64_C(0xe7037ed1a0b428db),

UINT64_C(0x8ebc6af09c88c6e3),

UINT64_C(0x589965cc75374cc3)};

auto const* p = static_cast<uint8_t const*>(key);

uint64_t seed = secret[0];

uint64_t a{};

uint64_t b{};

if (ANKERL_UNORDERED_DENSE_LIKELY(len <= 16)) {

if (ANKERL_UNORDERED_DENSE_LIKELY(len >= 4)) {

a = (r4(p) << 32U) | r4(p + ((len >> 3U) << 2U));

b = (r4(p + len - 4) << 32U) | r4(p + len - 4 - ((len >> 3U) << 2U));

} else if (ANKERL_UNORDERED_DENSE_LIKELY(len > 0)) {

a = r3(p, len);

b = 0;

} else {

a = 0;

b = 0;

}

} else {

size_t i = len;

if (ANKERL_UNORDERED_DENSE_UNLIKELY(i > 48)) {

uint64_t see1 = seed;

uint64_t see2 = seed;

do {

seed = mix(r8(p) ^ secret[1], r8(p + 8) ^ seed);

see1 = mix(r8(p + 16) ^ secret[2], r8(p + 24) ^ see1);

see2 = mix(r8(p + 32) ^ secret[3], r8(p + 40) ^ see2);

p += 48;

i -= 48;

} while (ANKERL_UNORDERED_DENSE_LIKELY(i > 48));

seed ^= see1 ^ see2;

}

while (ANKERL_UNORDERED_DENSE_UNLIKELY(i > 16)) {

seed = mix(r8(p) ^ secret[1], r8(p + 8) ^ seed);

i -= 16;

p += 16;

}

a = r8(p + i - 16);

b = r8(p + i - 8);

}

return mix(secret[1] ^ len, mix(a ^ secret[1], b ^ seed));

// Converts the value into 64bit. If it is an integral type, just cast it. Mixing is doing the rest.

// If it isn't an integral we need to hash it.

template <typename Arg>

[[nodiscard]] constexpr static auto to64(Arg const& arg) -> uint64_t {

if constexpr (std::is_integral_v<Arg> || std::is_enum_v<Arg>) {

return static_cast<uint64_t>(arg);

} else {

return hash<Arg>{}(arg);

}

}

[[nodiscard]] static auto mix64(uint64_t state, uint64_t v) -> uint64_t {

return detail::wyhash::mix(state + v, uint64_t{0x9ddfea08eb382d69});

}

// Creates a buffer that holds all the data from each element of the tuple. If possible we memcpy the data directly. If

// not, we hash the object and use this for the array. Size of the array is known at compile time, and memcpy is optimized

// away, so filling the buffer is highly efficient. Finally, call wyhash with this buffer.

template <typename T, std::size_t... Idx>

[[nodiscard]] static auto calc_hash(T const& t, std::index_sequence<Idx...>) noexcept -> uint64_t {

auto h = uint64_t{};

((h = mix64(h, to64(std::get<Idx>(t)))), ...);

return h;

}

static constexpr uint32_t dist_inc = 1U << 8U; // skip 1 byte fingerprint

static constexpr uint32_t fingerprint_mask = dist_inc - 1; // mask for 1 byte of fingerprint

uint32_t m_dist_and_fingerprint; // upper 3 byte: distance to original bucket. lower byte: fingerprint from hash

uint32_t m_value_idx; // index into the m_values vector.

static constexpr uint32_t dist_inc = 1U << 8U; // skip 1 byte fingerprint

static constexpr uint32_t fingerprint_mask = dist_inc - 1; // mask for 1 byte of fingerprint

uint32_t m_dist_and_fingerprint; // upper 3 byte: distance to original bucket. lower byte: fingerprint from hash

size_t m_value_idx; // index into the m_values vector.

template <bool IsConst>

class iter_t;

using allocator_type = Allocator;

using pointer = typename std::allocator_traits<allocator_type>::pointer;

using const_pointer = typename std::allocator_traits<allocator_type>::const_pointer;

using difference_type = typename std::allocator_traits<allocator_type>::difference_type;

using value_type = T;

using size_type = std::size_t;

using reference = T&;

using const_reference = T const&;

using iterator = iter_t<false>;

using const_iterator = iter_t<true>;

using vec_alloc = typename std::allocator_traits<Allocator>::template rebind_alloc<pointer>;

std::vector<pointer, vec_alloc> m_blocks{};

size_t m_size{};

// Calculates the maximum number for x in (s << x) <= max_val

static constexpr auto num_bits_closest(size_t max_val, size_t s) -> size_t {

auto f = size_t{0};

while (s << (f + 1) <= max_val) {

++f;

}

return f;

}

using self_t = segmented_vector<T, Allocator, MaxSegmentSizeBytes>;

static constexpr auto num_bits = num_bits_closest(MaxSegmentSizeBytes, sizeof(T));

static constexpr auto num_elements_in_block = 1U << num_bits;

static constexpr auto mask = num_elements_in_block - 1U;

/**

template <bool IsConst>

class iter_t {

using ptr_t = typename std::conditional_t<IsConst, segmented_vector::const_pointer const*, segmented_vector::pointer*>;

ptr_t m_data{};

size_t m_idx{};

template <bool B>

friend class iter_t;

public:

using difference_type = segmented_vector::difference_type;

using value_type = T;

using reference = typename std::conditional_t<IsConst, value_type const&, value_type&>;

using pointer = typename std::conditional_t<IsConst, segmented_vector::const_pointer, segmented_vector::pointer>;

using iterator_category = std::forward_iterator_tag;

iter_t() noexcept = default;

template <bool OtherIsConst, typename = typename std::enable_if<IsConst && !OtherIsConst>::type>

// NOLINTNEXTLINE(google-explicit-constructor,hicpp-explicit-conversions)

constexpr iter_t(iter_t<OtherIsConst> const& other) noexcept

: m_data(other.m_data)

, m_idx(other.m_idx) {}

constexpr iter_t(ptr_t data, size_t idx) noexcept

: m_data(data)

, m_idx(idx) {}

template <bool OtherIsConst, typename = typename std::enable_if<IsConst && !OtherIsConst>::type>

constexpr auto operator=(iter_t<OtherIsConst> const& other) noexcept -> iter_t& {

m_data = other.m_data;

m_idx = other.m_idx;

return *this;

}

constexpr auto operator++() noexcept -> iter_t& {

++m_idx;

return *this;

}

constexpr auto operator+(difference_type diff) noexcept -> iter_t {

return {m_data, static_cast<size_t>(static_cast<difference_type>(m_idx) + diff)};

}

template <bool OtherIsConst>

constexpr auto operator-(iter_t<OtherIsConst> const& other) noexcept -> difference_type {

return static_cast<difference_type>(m_idx) - static_cast<difference_type>(other.m_idx);

}

constexpr auto operator*() const noexcept -> reference {

return m_data[m_idx >> num_bits][m_idx & mask];

}

constexpr auto operator->() const noexcept -> pointer {

return &m_data[m_idx >> num_bits][m_idx & mask];

}

template <bool O>

constexpr auto operator==(iter_t<O> const& o) const noexcept -> bool {

return m_idx == o.m_idx;

}

template <bool O>

constexpr auto operator!=(iter_t<O> const& o) const noexcept -> bool {

return !(*this == o);

}

};

// slow path: need to allocate a new segment every once in a while

void increase_capacity() {

auto ba = Allocator(m_blocks.get_allocator());

pointer block = std::allocator_traits<Allocator>::allocate(ba, num_elements_in_block);

m_blocks.push_back(block);

}

// Moves everything from other

void append_everything_from(segmented_vector&& other) {

reserve(size() + other.size());

for (auto&& o : other) {

emplace_back(std::move(o));

}

}

// Copies everything from other

void append_everything_from(segmented_vector const& other) {

reserve(size() + other.size());

for (auto const& o : other) {

emplace_back(o);

}

}

void dealloc() {

auto ba = Allocator(m_blocks.get_allocator());

for (auto ptr : m_blocks) {

std::allocator_traits<Allocator>::deallocate(ba, ptr, num_elements_in_block);

}

}

[[nodiscard]] static constexpr auto calc_num_blocks_for_capacity(size_t capacity) {

return (capacity + num_elements_in_block - 1U) / num_elements_in_block;

}

segmented_vector() = default;

// NOLINTNEXTLINE(google-explicit-constructor,hicpp-explicit-conversions)

segmented_vector(Allocator alloc)

: m_blocks(vec_alloc(alloc)) {}

segmented_vector(segmented_vector&& other, Allocator alloc)

: segmented_vector(alloc) {

*this = std::move(other);

}

segmented_vector(segmented_vector const& other, Allocator alloc)

: m_blocks(vec_alloc(alloc)) {

append_everything_from(other);

}

segmented_vector(segmented_vector&& other) noexcept

: segmented_vector(std::move(other), get_allocator()) {}

segmented_vector(segmented_vector const& other) {

append_everything_from(other);

}

auto operator=(segmented_vector const& other) -> segmented_vector& {

if (this == &other) {

return *this;

}

clear();

append_everything_from(other);

return *this;

}

auto operator=(segmented_vector&& other) noexcept -> segmented_vector& {

clear();

dealloc();

if (other.get_allocator() == get_allocator()) {

m_blocks = std::move(other.m_blocks);

m_size = std::exchange(other.m_size, {});

} else {

// make sure to construct with other's allocator!

m_blocks = std::vector<pointer, vec_alloc>(vec_alloc(other.get_allocator()));

append_everything_from(std::move(other));

}

return *this;

}

~segmented_vector() {

clear();

dealloc();

}

[[nodiscard]] constexpr auto size() const -> size_t {

return m_size;

}

[[nodiscard]] constexpr auto capacity() const -> size_t {

return m_blocks.size() * num_elements_in_block;

}

// Indexing is highly performance critical

[[nodiscard]] constexpr auto operator[](size_t i) const noexcept -> T const& {

return m_blocks[i >> num_bits][i & mask];

}

[[nodiscard]] constexpr auto operator[](size_t i) noexcept -> T& {

return m_blocks[i >> num_bits][i & mask];

}

[[nodiscard]] constexpr auto begin() -> iterator {

return {m_blocks.data(), 0U};

}

[[nodiscard]] constexpr auto begin() const -> const_iterator {

return {m_blocks.data(), 0U};

}

[[nodiscard]] constexpr auto cbegin() const -> const_iterator {

return {m_blocks.data(), 0U};

}

[[nodiscard]] constexpr auto end() -> iterator {

return {m_blocks.data(), m_size};

}

[[nodiscard]] constexpr auto end() const -> const_iterator {

return {m_blocks.data(), m_size};

}

[[nodiscard]] constexpr auto cend() const -> const_iterator {

return {m_blocks.data(), m_size};

}

[[nodiscard]] constexpr auto back() -> reference {

return operator[](m_size - 1);

}

[[nodiscard]] constexpr auto back() const -> const_reference {

return operator[](m_size - 1);

}

void pop_back() {

back().~T();

--m_size;

}

[[nodiscard]] auto empty() const {

return 0 == m_size;

}

void reserve(size_t new_capacity) {

m_blocks.reserve(calc_num_blocks_for_capacity(new_capacity));

while (new_capacity > capacity()) {

increase_capacity();

}

}

[[nodiscard]] auto get_allocator() const -> allocator_type {

return allocator_type{m_blocks.get_allocator()};

}

template <class... Args>

auto emplace_back(Args&&... args) -> reference {

if (m_size == capacity()) {

increase_capacity();

}

auto* ptr = static_cast<void*>(&operator[](m_size));

auto& ref = *new (ptr) T(std::forward<Args>(args)...);

++m_size;

return ref;

}

void clear() {

if constexpr (!std::is_trivially_destructible_v<T>) {

for (size_t i = 0, s = size(); i < s; ++i) {

operator[](i).~T();

}

}

m_size = 0;

}

void shrink_to_fit() {

auto ba = Allocator(m_blocks.get_allocator());

auto num_blocks_required = calc_num_blocks_for_capacity(m_size);

while (m_blocks.size() > num_blocks_required) {

std::allocator_traits<Allocator>::deallocate(ba, m_blocks.back(), num_elements_in_block);

m_blocks.pop_back();

}

m_blocks.shrink_to_fit();

}

using underlying_value_type = typename std::conditional_t<is_map_v<T>, std::pair<Key, T>, Key>;

using underlying_container_type = std::conditional_t<IsSegmented,

segmented_vector<underlying_value_type, AllocatorOrContainer>,

std::vector<underlying_value_type, AllocatorOrContainer>>;

using value_container_type = std::

conditional_t<is_detected_v<detect_iterator, AllocatorOrContainer>, AllocatorOrContainer, underlying_container_type>;

using bucket_alloc =

typename std::allocator_traits<typename value_container_type::allocator_type>::template rebind_alloc<Bucket>;

using bucket_alloc_traits = std::allocator_traits<bucket_alloc>;

static constexpr uint8_t initial_shifts = 64 - 2; // 2^(64-m_shift) number of buckets

static constexpr float default_max_load_factor = 0.8F;

using key_type = Key;

using value_type = typename value_container_type::value_type;

using size_type = typename value_container_type::size_type;

using difference_type = typename value_container_type::difference_type;

using hasher = Hash;

using key_equal = KeyEqual;

using allocator_type = typename value_container_type::allocator_type;

using reference = typename value_container_type::reference;

using const_reference = typename value_container_type::const_reference;

using pointer = typename value_container_type::pointer;

using const_pointer = typename value_container_type::const_pointer;

using const_iterator = typename value_container_type::const_iterator;

using iterator = std::conditional_t<is_map_v<T>, typename value_container_type::iterator, const_iterator>;

using bucket_type = Bucket;

using value_idx_type = decltype(Bucket::m_value_idx);

using dist_and_fingerprint_type = decltype(Bucket::m_dist_and_fingerprint);

static_assert(std::is_trivially_destructible_v<Bucket>, "assert there's no need to call destructor / std::destroy");

static_assert(std::is_trivially_copyable_v<Bucket>, "assert we can just memset / memcpy");

value_container_type m_values{}; // Contains all the key-value pairs in one densely stored container. No holes.

using bucket_pointer = typename std::allocator_traits<bucket_alloc>::pointer;

bucket_pointer m_buckets{};

size_t m_num_buckets = 0;

size_t m_max_bucket_capacity = 0;

float m_max_load_factor = default_max_load_factor;

Hash m_hash{};

KeyEqual m_equal{};

uint8_t m_shifts = initial_shifts;

[[nodiscard]] auto next(value_idx_type bucket_idx) const -> value_idx_type {

return ANKERL_UNORDERED_DENSE_UNLIKELY(bucket_idx + 1U == m_num_buckets)

? 0

: static_cast<value_idx_type>(bucket_idx + 1U);

}

// Helper to access bucket through pointer types

[[nodiscard]] static constexpr auto at(bucket_pointer bucket_ptr, size_t offset) -> Bucket& {

return *(bucket_ptr + static_cast<typename std::allocator_traits<bucket_alloc>::difference_type>(offset));

}

// use the dist_inc and dist_dec functions so that uint16_t types work without warning

[[nodiscard]] static constexpr auto dist_inc(dist_and_fingerprint_type x) -> dist_and_fingerprint_type {

return static_cast<dist_and_fingerprint_type>(x + Bucket::dist_inc);

}

[[nodiscard]] static constexpr auto dist_dec(dist_and_fingerprint_type x) -> dist_and_fingerprint_type {

return static_cast<dist_and_fingerprint_type>(x - Bucket::dist_inc);

}

// The goal of mixed_hash is to always produce a high quality 64bit hash.

template <typename K>

[[nodiscard]] constexpr auto mixed_hash(K const& key) const -> uint64_t {

if constexpr (is_detected_v<detect_avalanching, Hash>) {

// we know that the hash is good because is_avalanching.

if constexpr (sizeof(decltype(m_hash(key))) < sizeof(uint64_t)) {

// 32bit hash and is_avalanching => multiply with a constant to avalanche bits upwards

return m_hash(key) * UINT64_C(0x9ddfea08eb382d69);

} else {

// 64bit and is_avalanching => only use the hash itself.

return m_hash(key);

}

} else {

// not is_avalanching => apply wyhash

return wyhash::hash(m_hash(key));

}

}

[[nodiscard]] constexpr auto dist_and_fingerprint_from_hash(uint64_t hash) const -> dist_and_fingerprint_type {

return Bucket::dist_inc | (static_cast<dist_and_fingerprint_type>(hash) & Bucket::fingerprint_mask);

}

[[nodiscard]] constexpr auto bucket_idx_from_hash(uint64_t hash) const -> value_idx_type {

return static_cast<value_idx_type>(hash >> m_shifts);

}

[[nodiscard]] static constexpr auto get_key(value_type const& vt) -> key_type const& {

if constexpr (is_map_v<T>) {

return vt.first;

} else {

return vt;

}

}

template <typename K>

[[nodiscard]] auto next_while_less(K const& key) const -> Bucket {

auto hash = mixed_hash(key);

auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);

auto bucket_idx = bucket_idx_from_hash(hash);

while (dist_and_fingerprint < at(m_buckets, bucket_idx).m_dist_and_fingerprint) {

dist_and_fingerprint = dist_inc(dist_and_fingerprint);

bucket_idx = next(bucket_idx);

}

return {dist_and_fingerprint, bucket_idx};

}

void place_and_shift_up(Bucket bucket, value_idx_type place) {

while (0 != at(m_buckets, place).m_dist_and_fingerprint) {

bucket = std::exchange(at(m_buckets, place), bucket);

bucket.m_dist_and_fingerprint = dist_inc(bucket.m_dist_and_fingerprint);

place = next(place);

}

at(m_buckets, place) = bucket;

}

[[nodiscard]] static constexpr auto calc_num_buckets(uint8_t shifts) -> size_t {

return (std::min)(max_bucket_count(), size_t{1} << (64U - shifts));

}

[[nodiscard]] constexpr auto calc_shifts_for_size(size_t s) const -> uint8_t {

auto shifts = initial_shifts;

while (shifts > 0 && static_cast<size_t>(static_cast<float>(calc_num_buckets(shifts)) * max_load_factor()) < s) {

--shifts;

}

return shifts;

}

// assumes m_values has data, m_buckets=m_buckets_end=nullptr, m_shifts is INITIAL_SHIFTS

void copy_buckets(table const& other) {

// assumes m_values has already the correct data copied over.

if (empty()) {

// when empty, at least allocate an initial buckets and clear them.

allocate_buckets_from_shift();

clear_buckets();

} else {

m_shifts = other.m_shifts;

allocate_buckets_from_shift();

std::memcpy(m_buckets, other.m_buckets, sizeof(Bucket) * bucket_count());

}

}

/**

[[nodiscard]] auto is_full() const -> bool {

return size() > m_max_bucket_capacity;

}

void deallocate_buckets() {

auto ba = bucket_alloc(m_values.get_allocator());

if (nullptr != m_buckets) {

bucket_alloc_traits::deallocate(ba, m_buckets, bucket_count());

m_buckets = nullptr;

}

m_num_buckets = 0;

m_max_bucket_capacity = 0;

}

void allocate_buckets_from_shift() {

auto ba = bucket_alloc(m_values.get_allocator());

m_num_buckets = calc_num_buckets(m_shifts);

m_buckets = bucket_alloc_traits::allocate(ba, m_num_buckets);

if (m_num_buckets == max_bucket_count()) {

// reached the maximum, make sure we can use each bucket

m_max_bucket_capacity = max_bucket_count();

} else {

m_max_bucket_capacity = static_cast<value_idx_type>(static_cast<float>(m_num_buckets) * max_load_factor());

}

}

void clear_buckets() {

if (m_buckets != nullptr) {

std::memset(&*m_buckets, 0, sizeof(Bucket) * bucket_count());

}

}

void clear_and_fill_buckets_from_values() {

clear_buckets();

for (value_idx_type value_idx = 0, end_idx = static_cast<value_idx_type>(m_values.size()); value_idx < end_idx;

++value_idx) {

auto const& key = get_key(m_values[value_idx]);

auto [dist_and_fingerprint, bucket] = next_while_less(key);

// we know for certain that key has not yet been inserted, so no need to check it.

place_and_shift_up({dist_and_fingerprint, value_idx}, bucket);

}

}

void increase_size() {