RobinHoodImpl.h#
Fully qualified name: carb/container/RobinHoodImpl.h
File members: carb/container/RobinHoodImpl.h
// SPDX-FileCopyrightText: Copyright (c) 2022-2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
// SPDX-License-Identifier: LicenseRef-NvidiaProprietary
//
// NVIDIA CORPORATION, its affiliates and licensors retain all intellectual
// property and proprietary rights in and to this material, related
// documentation and any modifications thereto. Any use, reproduction,
// disclosure or distribution of this material and related documentation
// without an express license agreement from NVIDIA CORPORATION or
// its affiliates is strictly prohibited.
#pragma once
#include "../Defines.h"
#include "../MinMax.h"
#include <algorithm>
#include <iterator>
#include "detail/ContainerHelpers.h"
#include "../cpp/Bit.h"
#include "../detail/ExceptionProlog.h"
namespace carb::container
{
constexpr size_t kDefaultLoadFactor = 80;
namespace detail
{
template <typename It>
using ValueFromIt_t = std::remove_const_t<typename std::iterator_traits<It>::value_type>;
template <typename It>
using KeyFromIt_t = typename std::remove_const_t<std::tuple_element_t<0, ValueFromIt_t<It>>>;
template <typename It>
using MappedFromIt_t = typename std::tuple_element_t<1, ValueFromIt_t<It>>;
template <typename It>
using AllocFromIt_t = typename std::allocator<std::pair<std::add_const_t<KeyFromIt_t<It>>, MappedFromIt_t<It>>>;
template <typename Key, typename T, typename Hash, typename KeyEqual, typename Allocator, size_t LoadFactorMax100>
struct RobinHoodMapTraits
{
using value_type = std::pair<const Key, T>;
using key_type = Key;
using allocator_type = Allocator;
using AllocBaseType = AllocBase<Allocator>;
using HashCompareType = HashCompare<Key, Hash, KeyEqual>;
static constexpr size_t LoadFactor = LoadFactorMax100;
static constexpr const key_type& get_key(const value_type& value)
{
return value.first;
}
};
template <typename Key, typename Hash, typename KeyEqual, typename Allocator, size_t LoadFactorMax100>
struct RobinHoodSetTraits
{
using value_type = const Key;
using key_type = Key;
using allocator_type = Allocator;
using AllocBaseType = AllocBase<Allocator>;
using HashCompareType = HashCompare<Key, Hash, KeyEqual>;
static constexpr size_t LoadFactor = LoadFactorMax100;
static constexpr const key_type& get_key(const value_type& value)
{
return value;
}
};
template <typename Traits>
class CARB_VIZ RobinHood
{
using AllocatorTraitsType = typename std::allocator_traits<typename Traits::allocator_type>;
using TraitsType = Traits;
using HashCompareType = typename Traits::HashCompareType;
using AllocBaseType = typename Traits::AllocBaseType;
public:
#ifndef DOXYGEN_BUILD
using key_type = typename Traits::key_type;
using value_type = typename Traits::value_type;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using hasher = typename HashCompareType::hasher;
using key_equal = typename HashCompareType::key_equal;
using reference = value_type&;
using const_reference = const value_type&;
using pointer = typename AllocatorTraitsType::pointer;
using const_pointer = typename AllocatorTraitsType::const_pointer;
using allocator_type = typename Traits::allocator_type;
static constexpr size_t LoadFactor = Traits::LoadFactor;
static_assert(LoadFactor >= 10 && LoadFactor <= 100, "Load factor must be in range [10, 100]");
// clang-format off
class iter_base
{
public:
constexpr iter_base() noexcept = default;
bool operator == (const iter_base& other) const noexcept { CARB_ASSERT(owner == other.owner); return where == other.where; }
bool operator != (const iter_base& other) const noexcept { CARB_ASSERT(owner == other.owner); return where != other.where; }
protected:
constexpr iter_base(const RobinHood* owner_, value_type* where_) noexcept : owner(owner_), where(where_) {}
CARB_VIZ const RobinHood* owner{ nullptr };
CARB_VIZ value_type* where{ nullptr };
};
class CARB_VIZ const_find_iterator : public iter_base
{
using Base = iter_base;
public:
using iterator_category = std::forward_iterator_tag;
using value_type = RobinHood::value_type;
using difference_type = ptrdiff_t;
using pointer = const value_type*;
using reference = const value_type&;
constexpr const_find_iterator() noexcept = default;
reference operator * () const noexcept { CARB_ASSERT(this->where); return *this->where; }
pointer operator -> () const noexcept { CARB_ASSERT(this->where); return this->where; }
const_find_iterator& operator ++ () noexcept { CARB_ASSERT(this->where); incr(); return *this; }
const_find_iterator operator ++ (int) noexcept { const_find_iterator i{ *this }; incr(); return i; }
protected:
friend class RobinHood;
constexpr const_find_iterator(const RobinHood* owner_, value_type* where_) noexcept : Base{ owner_, where_ } {}
void incr() { CARB_ASSERT(this->owner && this->where); this->where = this->owner->_findnext(this->where); }
};
class find_iterator : public const_find_iterator
{
using Base = const_find_iterator;
public:
using iterator_category = std::forward_iterator_tag;
using value_type = RobinHood::value_type;
using difference_type = ptrdiff_t;
using pointer = value_type*;
using reference = value_type&;
constexpr find_iterator() noexcept = default;
reference operator * () const noexcept { CARB_ASSERT(this->where); return *this->where; }
pointer operator -> () const noexcept { CARB_ASSERT(this->where); return this->where; }
find_iterator& operator ++ () noexcept { CARB_ASSERT(this->where); this->incr(); return *this; }
find_iterator operator ++ (int) noexcept { CARB_ASSERT(this->where); find_iterator i{ *this }; this->incr(); return i; }
protected:
friend class RobinHood;
constexpr find_iterator(const RobinHood* owner_, value_type* where_) noexcept : Base(owner_, where_) {}
};
class CARB_VIZ const_iterator : public iter_base
{
using Base = iter_base;
public:
using iterator_category = std::forward_iterator_tag;
using value_type = RobinHood::value_type;
using difference_type = ptrdiff_t;
using pointer = const value_type*;
using reference = const value_type&;
constexpr const_iterator() noexcept = default;
reference operator * () const noexcept { CARB_ASSERT(this->where); return *this->where; }
pointer operator -> () const noexcept { CARB_ASSERT(this->where); return this->where; }
const_iterator& operator ++ () noexcept { CARB_ASSERT(this->where); incr(); return *this; }
const_iterator operator ++ (int) noexcept { const_iterator i{ *this }; incr(); return i; }
protected:
friend class RobinHood;
constexpr const_iterator(const RobinHood* owner_, value_type* where_) noexcept : Base{ owner_, where_ } {}
void incr() { CARB_ASSERT(this->owner && this->where); this->where = this->owner->_next(this->where); }
};
class iterator : public const_iterator
{
using Base = const_iterator;
public:
using iterator_category = std::forward_iterator_tag;
using value_type = RobinHood::value_type;
using difference_type = ptrdiff_t;
using pointer = value_type*;
using reference = value_type&;
constexpr iterator() noexcept = default;
reference operator * () const noexcept { CARB_ASSERT(this->where); return *this->where; }
pointer operator -> () const noexcept { CARB_ASSERT(this->where); return this->where; }
iterator& operator ++ () noexcept { CARB_ASSERT(this->where); this->incr(); return *this; }
iterator operator ++ (int) noexcept { CARB_ASSERT(this->where); iterator i{ *this }; this->incr(); return i; }
protected:
friend class RobinHood;
constexpr iterator(const RobinHood* owner_, value_type* where_) noexcept : Base(owner_, where_) {}
};
// clang-format on
constexpr RobinHood() noexcept = default;
RobinHood(const RobinHood& other)
: RobinHood(other, AllocatorTraitsType::select_on_container_copy_construction(other.get_allocator()))
{
}
explicit RobinHood(size_type reserved, const hasher& h, const key_equal& ke, const allocator_type& al)
: m_data(h, ke, al)
{
reserve(reserved);
}
explicit RobinHood(const allocator_type& al) : m_data(hasher(), key_equal(), al)
{
}
RobinHood(const RobinHood& other, const allocator_type& alloc) : m_data(other.m_data, alloc)
{
TableAllocatorType table_alloc(m_data.get_allocator());
// This effectively rebuilds `other` as *this, but it sizes *this as compactly as possible (whereas `other` may
// have a high capacity():size() ratio).
reserve(other.size());
for (auto& entry : other)
{
auto result = internal_insert_multi(Traits::get_key(entry));
TableAllocatorTraitsType::construct(table_alloc, result, entry); // copy
}
}
RobinHood(RobinHood&& other) : m_data(std::move(other.m_data))
{
}
RobinHood(RobinHood&& other, const allocator_type& alloc) : m_data(std::move(other.m_data), alloc)
{
using is_always_equal = typename AllocatorTraitsType::is_always_equal;
moveConstructWithAlloc(std::move(other), alloc, is_always_equal{});
}
~RobinHood()
{
if (m_data.m_table)
{
TableAllocatorType table_alloc(m_data.get_allocator());
HashesAllocatorType hash_alloc(m_data.get_allocator());
if (!empty())
{
if constexpr (!std::is_trivially_destructible_v<value_type>)
{
for (size_t i = 0; i != m_data.m_tableSize; ++i)
{
if (isHashValid(m_data.m_hashes[i]))
TableAllocatorTraitsType::destroy(table_alloc, m_data.m_table + i);
}
}
}
HashesAllocatorTraitsType::deallocate(
hash_alloc, std::exchange(m_data.m_hashes, nullptr), m_data.m_tableSize);
TableAllocatorTraitsType::deallocate(table_alloc, std::exchange(m_data.m_table, nullptr), m_data.m_tableSize);
m_data.m_size = m_data.m_tableSize = 0;
}
}
RobinHood& operator=(const RobinHood& other)
{
if (this != &other)
{
using propagate = typename AllocatorTraitsType::propagate_on_container_copy_assignment;
if constexpr (propagate::value)
{
m_data.get_allocator() = other.m_data.get_allocator();
}
copyAssign(other);
}
return *this;
}
RobinHood& operator=(RobinHood&& other)
{
if (this != &other)
{
using propagate = typename AllocatorTraitsType::propagate_on_container_move_assignment;
using is_always_equal = typename AllocatorTraitsType::is_always_equal;
moveAssign(std::move(other), std::disjunction<propagate, is_always_equal>{});
}
return *this;
}
#endif
const_iterator cbegin() const
{
if (CARB_UNLIKELY(empty()))
return cend();
auto const end = m_data.m_hashes + m_data.m_tableSize;
for (auto e = m_data.m_hashes; e != end; ++e)
if (isHashValid(*e))
return { this, m_data.m_table + (e - m_data.m_hashes) };
// Should never get here since we checked empty()
CARB_UNREACHABLE();
}
iterator begin()
{
if (CARB_UNLIKELY(empty()))
return end();
auto const kEnd = m_data.m_hashes + m_data.m_tableSize;
for (auto e = m_data.m_hashes; e != kEnd; ++e)
if (isHashValid(*e))
return { this, m_data.m_table + (e - m_data.m_hashes) };
// Should never get here since we checked empty()
CARB_UNREACHABLE();
}
const_iterator begin() const
{
return cbegin();
}
const_iterator cend() const
{
return { this, nullptr };
}
iterator end()
{
return { this, nullptr };
}
const_iterator end() const
{
return cend();
}
bool empty() const noexcept
{
return !m_data.m_size;
}
size_t size() const noexcept
{
return m_data.m_size;
}
constexpr size_t max_size() const noexcept
{
return size_t(-1) & ~kDeletedBit;
}
size_t capacity() const noexcept
{
// Handle case where Windows.h may have defined 'max'
#pragma push_macro("max")
#undef max
if (CARB_LIKELY(m_data.m_tableSize <= (std::numeric_limits<size_t>::max() / 100)))
return (m_data.m_tableSize * LoadFactor) / 100;
#pragma pop_macro("max")
// In the unlikely event of a huge table, switch operations to not overflow
return (m_data.m_tableSize / 100) * LoadFactor;
}
void clear()
{
if (!empty())
{
TableAllocatorType table_alloc(m_data.get_allocator());
size_t* const end = m_data.m_hashes + m_data.m_tableSize;
for (size_t* e = m_data.m_hashes; e != end; ++e)
{
if constexpr (!std::is_trivially_destructible_v<value_type>)
{
if (isHashValid(*e))
TableAllocatorTraitsType::destroy(table_alloc, m_data.m_table + (e - m_data.m_hashes));
}
*e = kEmpty;
}
m_data.m_size = 0;
}
}
void swap(RobinHood& other)
{
if (this != &other)
{
using propagate = typename AllocatorTraitsType::propagate_on_container_swap;
using is_always_equal = typename AllocatorTraitsType::is_always_equal;
internalSwap(other, std::disjunction<propagate, is_always_equal>{});
}
}
iterator erase(const_iterator pos)
{
CARB_ASSERT(pos.owner == this);
assertContained(pos.where);
internal_erase(pos.where);
return iterator{ this, _next(pos.where) };
}
iterator erase(const_iterator first, const_iterator last)
{
while (first != last)
first = erase(first);
return { this, first.where };
}
find_iterator erase(const_find_iterator pos)
{
CARB_ASSERT(pos.owner == this);
assertContained(pos.where);
find_iterator next{ this, _findnext(pos.where) };
internal_erase(pos.where);
return next;
}
find_iterator erase(const_find_iterator first, const_find_iterator last)
{
while (first != last)
first = erase(first);
return { this, first.where };
}
#ifndef DOXYGEN_BUILD
protected:
template <typename T>
constexpr static bool IsTransparent_v = dependent_bool<SupportsTransparent<key_type, hasher, key_equal>, T>::value;
public:
#endif
find_iterator find(const key_type& key)
{
return { this, internal_find(key) };
}
const_find_iterator find(const key_type& key) const
{
return { this, internal_find(key) };
}
template <typename K, typename = std::enable_if_t<IsTransparent_v<K>>>
find_iterator find(const K& key)
{
return { this, internal_find(key) };
}
template <typename K, typename = std::enable_if_t<IsTransparent_v<K>>>
const_find_iterator find(const K& key) const
{
return { this, internal_find(key) };
}
bool contains(const key_type& key) const
{
return !!internal_find(key);
}
template <typename K, typename = std::enable_if_t<IsTransparent_v<K>>>
bool contains(const K& key) const
{
return !!internal_find(key);
}
std::pair<find_iterator, find_iterator> equal_range(const key_type& key)
{
auto vt = this->internal_find(key);
find_iterator fend{ this, nullptr };
return vt ? std::make_pair(find_iterator{ this, vt }, fend) : std::make_pair(fend, fend);
}
std::pair<const_find_iterator, const_find_iterator> equal_range(const key_type& key) const
{
auto vt = this->internal_find(key);
const_find_iterator fend{ this, nullptr };
return vt ? std::make_pair(const_find_iterator{ this, vt }, fend) : std::make_pair(fend, fend);
}
template <typename K, typename = std::enable_if_t<IsTransparent_v<K>>>
std::pair<find_iterator, find_iterator> equal_range(const K& key)
{
auto vt = this->internal_find(key);
find_iterator fend{ this, nullptr };
return vt ? std::make_pair(find_iterator{ this, vt }, fend) : std::make_pair(fend, fend);
}
template <typename K, typename = std::enable_if_t<IsTransparent_v<K>>>
std::pair<const_find_iterator, const_find_iterator> equal_range(const K& key) const
{
auto vt = this->internal_find(key);
const_find_iterator fend{ this, nullptr };
return vt ? std::make_pair(const_find_iterator{ this, vt }, fend) : std::make_pair(fend, fend);
}
void reserve(size_t n)
{
if (n > capacity())
{
rehash(n);
}
}
void rehash(size_t n)
{
if (n < m_data.m_size)
n = m_data.m_size;
HashesAllocatorType hash_alloc(m_data.get_allocator());
TableAllocatorType table_alloc(m_data.get_allocator());
if (n == 0)
{
if (m_data.m_tableSize)
{
TableAllocatorTraitsType::deallocate(table_alloc, m_data.m_table, m_data.m_tableSize);
HashesAllocatorTraitsType::deallocate(hash_alloc, m_data.m_hashes, m_data.m_tableSize);
m_data.m_table = nullptr;
m_data.m_hashes = nullptr;
m_data.m_tableSize = 0;
}
return;
}
size_t const oldsize = m_data.m_tableSize;
ncvalue_type* const oldtable = m_data.m_table;
size_t* const oldhashes = m_data.m_hashes;
size_t* const oldend = oldhashes + m_data.m_tableSize;
size_t minsize = (n * 100 + (LoadFactor - 1)) / LoadFactor; // ceiling (round up)
constexpr static auto kMinSize_ = kMinSize; // CC-1110
size_t newsize = ::carb_max(kMinSize_, cpp::bit_ceil(minsize)); // must be a power of 2
// May throw, so allocate before any changes have been made
ncvalue_type* newtable = nullptr;
size_t* newhashes = nullptr;
CARBLOCAL_TRY_BEGIN
{
newtable = TableAllocatorTraitsType::allocate(table_alloc, newsize);
newhashes = HashesAllocatorTraitsType::allocate(hash_alloc, newsize);
}
CARBLOCAL_CATCH_ALL
{
if (newhashes)
HashesAllocatorTraitsType::deallocate(hash_alloc, newhashes, newsize);
if (newtable)
TableAllocatorTraitsType::deallocate(table_alloc, newtable, newsize);
}
m_data.m_table = std::exchange(newtable, nullptr);
m_data.m_hashes = newhashes;
m_data.m_tableSize = newsize;
CARB_ASSERT(capacity() >= m_data.m_size);
// Initialize
std::fill(newhashes, newhashes + newsize, kEmpty);
for (size_t* e = oldhashes; e != oldend; ++e)
if (isHashValid(*e))
{
auto& old = oldtable[e - oldhashes];
auto result = internal_insert_multi2(*e, Traits::get_key(old));
// TODO: Handle any exception during move
TableAllocatorTraitsType::construct(table_alloc, result, std::move(old));
TableAllocatorTraitsType::destroy(table_alloc, std::addressof(old));
}
HashesAllocatorTraitsType::deallocate(hash_alloc, oldhashes, oldsize);
TableAllocatorTraitsType::deallocate(table_alloc, oldtable, oldsize);
}
hasher hash_function() const
{
return m_data.hash_function();
}
key_equal key_eq() const
{
return m_data.key_eq();
}
allocator_type get_allocator() const noexcept
{
return m_data.get_allocator();
}
#ifndef DOXYGEN_BUILD
protected:
constexpr static size_t kDeletedBit = size_t(1) << (8 * sizeof(size_t) - 1);
constexpr static size_t kEmpty = size_t(-1) & ~kDeletedBit;
constexpr static size_t kMinSize = 8; // Minimum hash table size
static_assert(cpp::has_single_bit(kMinSize), "Must be power of 2");
using ncvalue_type = typename std::remove_const_t<value_type>;
using HashesAllocatorType = typename AllocatorTraitsType::template rebind_alloc<size_t>;
using HashesAllocatorTraitsType = typename std::allocator_traits<HashesAllocatorType>;
using TableAllocatorType = typename AllocatorTraitsType::template rebind_alloc<ncvalue_type>;
using TableAllocatorTraitsType = typename std::allocator_traits<TableAllocatorType>;
static constexpr bool isEmpty(size_t h) noexcept
{
return h == kEmpty;
}
static constexpr bool isDeleted(size_t h) noexcept
{
return !!(h & kDeletedBit);
}
static constexpr bool isHashValid(size_t h) noexcept
{
return !(isDeleted(h) || isEmpty(h));
}
struct Data : public HashCompareType, public AllocBaseType
{
Data() = default;
Data(hasher hash, key_equal eq, allocator_type alloc)
: HashCompareType(std::move(hash), std::move(eq)), AllocBaseType(std::move(alloc))
{
}
Data(const Data&) = default;
Data& operator=(const Data&) = default;
Data(Data&& other) : HashCompareType(std::move(other)), AllocBaseType(std::move(other))
{
m_table = std::exchange(other.m_table, nullptr);
m_hashes = std::exchange(other.m_hashes, nullptr);
m_size = std::exchange(other.m_size, 0);
m_tableSize = std::exchange(other.m_tableSize, 0);
}
Data& operator=(Data&& other)
{
std::swap<HashCompareType>(*this, other);
std::swap<AllocBaseType>(*this, other);
std::swap(m_table, other.m_table);
std::swap(m_hashes, other.m_hashes);
std::swap(m_size, other.m_size);
std::swap(m_tableSize, other.m_tableSize);
return *this;
}
Data(const Data& other, allocator_type alloc) : HashCompareType(other), AllocBaseType(std::move(alloc))
{
}
Data(Data&& other, allocator_type alloc) : HashCompareType(std::move(other)), AllocBaseType(std::move(alloc))
{
}
allocator_type& get_allocator() noexcept
{
return this->a();
}
const allocator_type& get_allocator() const noexcept
{
return this->a();
}
CARB_VIZ ncvalue_type* m_table{ nullptr };
CARB_VIZ size_t* m_hashes{ nullptr };
CARB_VIZ size_t m_size{ 0 };
CARB_VIZ size_t m_tableSize{ 0 };
};
HashCompareType& hct() noexcept
{
return m_data;
}
const HashCompareType& hct() const noexcept
{
return m_data;
}
template <typename K, typename = std::enable_if_t<IsTransparent_v<K>>>
size_t hash(const K& key) const noexcept
{
size_t h = size_t(hct()(key)) & ~kDeletedBit;
return h ^ (h == kEmpty);
}
size_t hash(const key_type& key) const noexcept
{
size_t h = size_t(hct()(key)) & ~kDeletedBit;
return h ^ (h == kEmpty);
}
void assertContained([[maybe_unused]] const value_type* v) const
{
CARB_ASSERT(v >= m_data.m_table && v < (m_data.m_table + m_data.m_tableSize));
}
const size_t* _end() const noexcept
{
return m_data.m_hashes + m_data.m_tableSize;
}
value_type* _next(value_type* prev) const
{
assertContained(prev);
const size_t* e = m_data.m_hashes + (prev - m_data.m_table) + 1;
for (; e != _end(); ++e)
if (isHashValid(*e))
return m_data.m_table + (e - m_data.m_hashes);
return nullptr;
}
template <typename K>
value_type* _findnext(value_type* prev, const K& key) const
{
assertContained(prev);
size_t const h = m_data.m_hashes[(prev - m_data.m_table)];
CARB_ASSERT(isHashValid(h));
size_t const kMask = (m_data.m_tableSize - 1);
size_t const start = (h & kMask); // starting index of the search. If we get back to this point, we're done.
size_t index = ((prev - m_data.m_table) + 1) & kMask;
size_t dist = (index - start) & kMask;
for (; index != start; index = (index + 1) & kMask, ++dist)
{
size_t* e = m_data.m_hashes + index;
if (isEmpty(*e))
{
return nullptr;
}
if (*e == h && hct()(Traits::get_key(m_data.m_table[index]), key))
{
return m_data.m_table + index;
}
size_t entryDist = (index - *e) & kMask;
if (dist > entryDist)
{
return nullptr;
}
}
return nullptr;
}
value_type* _findnext(value_type* prev) const
{
assertContained(prev);
return _findnext(prev, Traits::get_key(*prev));
}
template <typename... Args>
void construct(ncvalue_type* p, Args&&... args)
{
TableAllocatorType alloc(m_data.get_allocator());
TableAllocatorTraitsType::construct(alloc, p, std::forward<Args>(args)...);
}
constexpr iterator make_iter(value_type* where) const noexcept
{
return iterator{ this, where };
}
std::pair<iterator, bool> insert_unique(const value_type& value)
{
auto [p, inserted] = internal_insert(Traits::get_key(value));
if (inserted)
construct(p, value);
return std::make_pair(iterator{ this, p }, inserted);
}
std::pair<iterator, bool> insert_unique(value_type&& value)
{
auto [p, inserted] = internal_insert(Traits::get_key(value));
if (inserted)
construct(p, std::move(value));
return std::make_pair(iterator{ this, p }, inserted);
}
template <typename K>
std::pair<iterator, bool> insert_unique(K&& value)
{
const K& ref = value;
auto [p, inserted] = internal_insert(ref);
if (inserted)
construct(p, std::forward<K>(value));
return std::make_pair(iterator{ this, p }, inserted);
}
iterator insert_multi(const value_type& value)
{
auto p = internal_insert_multi(Traits::get_key(value));
construct(p, value);
return { this, p };
}
iterator insert_multi(value_type&& value)
{
auto p = internal_insert_multi(Traits::get_key(value));
construct(p, std::move(value));
return { this, p };
}
ncvalue_type* internal_insert_multi(const key_type& key)
{
if (((m_data.m_size) + 1) >= capacity())
{
reserve(m_data.m_size + 1);
}
CARB_ASSERT(m_data.m_size < m_data.m_tableSize);
size_t h = hash(key);
++m_data.m_size;
return internal_insert_multi2(h, key);
}
ncvalue_type* internal_insert_multi2(size_t h, const key_type& key)
{
TableAllocatorType table_alloc(m_data.get_allocator());
size_t const kMask = (m_data.m_tableSize - 1);
size_t index = h & kMask;
size_t last = (index - 1) & kMask;
size_t dist = 0; // distance from desired slot
size_t* e;
for (;;)
{
e = m_data.m_hashes + index;
if (isEmpty(*e))
{
*e = h;
return m_data.m_table + index;
}
// Compute the distance of the existing item or deleted entry
size_t const existingDist = (index - *e) & kMask;
if (isDeleted(*e))
{
// The evicted item can only go into a deleted slot only if it's "fair": our distance-from-desired must
// be same or worse than the existing deleted item.
if (dist >= existingDist)
{
// We can take a deleted entry that meets or exceeds our desired distance
*e = h;
return m_data.m_table + (e - m_data.m_hashes);
}
}
else if (dist > existingDist)
{
// Our distance from desired now exceeds the current entry, so we'll take it and evict whatever was
// previously there. Proceed to the next phase to find a spot for the evicted entry.
dist = existingDist;
break;
}
if (CARB_UNLIKELY(index == last))
{
// We reached the end without finding a valid spot, but there are deleted entries in the table. So
// rebuild to remove all of the deleted entries and recursively call.
rebuild();
return internal_insert_multi2(h, key);
}
index = (index + 1) & kMask;
++dist;
}
// At this point, we have to evict an existing item in order to insert at a fair position. The slot that will
// contain our new entry is pointed at by `orig`. Our caller will be responsible for initializing the value_type
ncvalue_type* const orig = m_data.m_table + (e - m_data.m_hashes);
std::swap(*e, h);
ncvalue_type value(std::move(*orig));
TableAllocatorTraitsType::destroy(table_alloc, orig); // caller will need to reconstruct
// We are now taking the perspective of the evicted item. `h` is already the hash value for the evicted item, so
// recompute `last`. `dist` is already the distance from desired for the evicted item as well.
last = (h - 1) & kMask;
// Start with the following index as it is the first candidate for the evicted item.
index = (index + 1) & kMask;
++dist;
for (;;)
{
e = m_data.m_hashes + index;
if (isEmpty(*e))
{
// Found an empty slot that the evicted item can move into.
*e = h;
TableAllocatorTraitsType::construct(table_alloc, m_data.m_table + index, std::move(value));
return orig;
}
size_t existingDist = (index - *e) & kMask;
if (isDeleted(*e))
{
// The evicted item can only go into a deleted slot only if it's "fair": our distance-from-desired must
// be same or worse than the existing deleted item.
if (dist >= existingDist)
{
*e = h;
TableAllocatorTraitsType::construct(table_alloc, m_data.m_table + index, std::move(value));
return orig;
}
}
else if (dist > existingDist)
{
// For an existing item, we can swap it out with the previously evicted item if it is worse off than the
// item at this location. It becomes the new evicted item and we continue traversal until we find a
// suitable location for it.
std::swap(*e, h);
swapValue(value, m_data.m_table[e - m_data.m_hashes], table_alloc);
dist = existingDist;
last = (h - 1) & kMask;
}
if (index == last)
{
// We're in a bad state. There are too many deleted items and we've walked the entire list trying to
// find a location. Do a rebuild to remove all the deleted entries and re-hash everything then call
// recursively.
std::swap(m_data.m_hashes[orig - m_data.m_table], h);
// Reconstruct the item at orig since it was previously deleted.
TableAllocatorTraitsType::construct(table_alloc, orig, std::move(value));
CARB_ASSERT(h == hash(key));
rebuild();
return internal_insert_multi2(h, key);
}
index = (index + 1) & kMask;
++dist;
}
}
template <typename K>
std::pair<ncvalue_type*, bool> internal_insert(const K& key)
{
if ((m_data.m_size + 1) >= capacity())
{
reserve(m_data.m_size + 1);
}
CARB_ASSERT(m_data.m_size < m_data.m_tableSize);
size_t h = hash(key);
auto result = internal_insert2(h, key);
m_data.m_size += result.second;
return result;
}
template <typename K>
std::pair<ncvalue_type*, bool> internal_insert2(size_t h, const K& key)
{
TableAllocatorType table_alloc(m_data.get_allocator());
size_t const kMask = (m_data.m_tableSize - 1);
size_t index = h & kMask;
size_t last = (index - 1) & kMask;
size_t dist = 0; // distance from desired slot
size_t* firstDeletedSlot = nullptr;
size_t* e;
for (;;)
{
e = m_data.m_hashes + index;
if (isEmpty(*e))
{
*e = h;
return std::make_pair(m_data.m_table + index, true);
}
if (*e == h && hct()(Traits::get_key(m_data.m_table[index]), key))
{
return std::make_pair(m_data.m_table + index, false);
}
// Compute the distance of the existing item or deleted entry
size_t const existingDist = (index - *e) & kMask;
if (dist > existingDist)
{
// Our distance from desired now exceeds the current entry, so we'll take it. If it's deleted, we can
// merely take it, but if something already exists there, we need to move it down the line.
if (!firstDeletedSlot && isDeleted(*e))
{
firstDeletedSlot = e;
}
if (firstDeletedSlot)
{
// If we found a deleted slot, we can go into it
*firstDeletedSlot = h;
return std::make_pair(m_data.m_table + (firstDeletedSlot - m_data.m_hashes), true);
}
if (CARB_UNLIKELY(index == last))
{
// We reached the end without finding a valid spot, but there are deleted entries in the table. So
// rebuild to remove all of the deleted entries and recursively call.
rebuild();
return internal_insert2(h, key);
}
// We break out and proceed to find a new location for the existing entry
dist = existingDist;
break;
}
else if (!firstDeletedSlot && dist == existingDist && isDeleted(*e))
{
firstDeletedSlot = e;
}
if (CARB_UNLIKELY(index == last))
{
// We reached the end without finding a valid spot. Rebuild to remove all deleted entries and call
// recursively.
rebuild();
return internal_insert2(h, key);
}
index = (index + 1) & kMask;
++dist;
}
// At this point, we guarantee that we need to insert and we had to evict an existing item. The slot that will
// contain our new entry is pointed at by `orig`. Our caller will be responsible for initializing the value_type
ncvalue_type* const orig = m_data.m_table + (e - m_data.m_hashes);
std::swap(*e, h);
ncvalue_type value(std::move(*orig));
TableAllocatorTraitsType::destroy(table_alloc, orig); // caller will need to reconstruct.
// We are now taking the perspective of the evicted item. `h` is already the hash value for the evicted item, so
// recompute `last`. `dist` is already the distance from desired for the evicted item as well.
last = (h - 1) & kMask;
// Start with the following index as it is the first candidate for the evicted item.
index = (index + 1) & kMask;
++dist;
for (;;)
{
e = m_data.m_hashes + index;
if (isEmpty(*e))
{
// Found an empty slot that the evicted item can move into.
*e = h;
TableAllocatorTraitsType::construct(table_alloc, m_data.m_table + index, std::move(value));
return std::make_pair(orig, true);
}
size_t existingDist = (index - *e) & kMask;
if (isDeleted(*e))
{
// The evicted item can only go into a deleted slot only if it's "fair": our distance-from-desired must
// be same or worse than the existing deleted item.
if (dist >= existingDist)
{
*e = h;
TableAllocatorTraitsType::construct(table_alloc, m_data.m_table + index, std::move(value));
return std::make_pair(orig, true);
}
}
else if (dist > existingDist)
{
// For an existing item, we can swap it out with the previously evicted item if it is worse off than the
// item at this location. It becomes the new evicted item and we continue traversal until we find a
// suitable location for it.
std::swap(*e, h);
swapValue(value, m_data.m_table[e - m_data.m_hashes], table_alloc);
dist = existingDist;
last = (h - 1) & kMask;
}
if (index == last)
{
// We're in a bad state. There are too many deleted items and we've walked the entire list trying to
// find a location. Do a rebuild to remove all the deleted entries and re-hash everything then call
// recursively.
std::swap(m_data.m_hashes[orig - m_data.m_table], h);
// Reconstruct the item at orig since it was previously deleted.
TableAllocatorTraitsType::construct(table_alloc, orig, std::move(value));
CARB_ASSERT(h == hash(key));
rebuild();
return internal_insert2(h, key);
}
index = (index + 1) & kMask;
++dist;
}
}
template <typename K>
size_t internal_count_multi(const K& key) const
{
size_t count = 0;
for (auto vt = internal_find(key); vt; vt = _findnext(vt, key))
++count;
return count;
}
void internal_erase(value_type* value)
{
TableAllocatorType table_alloc(m_data.get_allocator());
--m_data.m_size;
TableAllocatorTraitsType::destroy(table_alloc, value);
size_t index = value - m_data.m_table;
size_t* h = m_data.m_hashes + index;
// Set the deleted bit, but we retain most bits in the hash so that distance checks work properly.
*h |= kDeletedBit;
// If our next entry is kEmpty, then we can walk backwards and set everything to kEmpty. This will keep the
// table a bit cleaner of deleted entries.
size_t const kMask = m_data.m_tableSize - 1;
if (isEmpty(m_data.m_hashes[(index + 1) & kMask]))
{
do
{
*h = kEmpty;
index = (index - 1) & kMask;
h = m_data.m_hashes + index;
} while (isDeleted(*h));
}
}
template <class K>
value_type* internal_find(const K& key) const
{
if (CARB_UNLIKELY(empty()))
return nullptr;
size_t const h = hash(key);
size_t const kMask = size_t(m_data.m_tableSize - 1);
size_t index = h & kMask;
size_t dist = 0;
for (;;)
{
size_t* e = m_data.m_hashes + index;
if (isEmpty(*e))
return nullptr;
if (*e == h && hct()(Traits::get_key(m_data.m_table[index]), key))
{
return m_data.m_table + index;
}
size_t entryDist = (index - *e) & kMask;
if (dist > entryDist)
return nullptr;
// We do not need to check against the last entry here because distance keeps increasing. Eventually it will
// be larger than the number of items in the map.
++dist;
index = (index + 1) & kMask;
}
}
static void swapValue(ncvalue_type& v1, ncvalue_type& v2, TableAllocatorType& alloc) noexcept
{
// Cannot use std::swap because key is const, so work around it with move-construct/destruction
ncvalue_type temp{ std::move(v1) };
TableAllocatorTraitsType::destroy(alloc, std::addressof(v1));
TableAllocatorTraitsType::construct(alloc, std::addressof(v1), std::move(v2));
TableAllocatorTraitsType::destroy(alloc, std::addressof(v2));
TableAllocatorTraitsType::construct(alloc, std::addressof(v2), std::move(temp));
}
// Similar to rehash except that it keeps the same table size
void rebuild()
{
HashesAllocatorType hash_alloc(m_data.get_allocator());
TableAllocatorType table_alloc(m_data.get_allocator());
size_t const size = m_data.m_tableSize;
ncvalue_type* const oldtable = m_data.m_table;
size_t* const oldhashes = m_data.m_hashes;
size_t* const oldend = oldhashes + size;
// May throw, so allocate before making any changes.
ncvalue_type* newtable = nullptr;
size_t* newhashes = nullptr;
CARBLOCAL_TRY_BEGIN
{
newtable = TableAllocatorTraitsType::allocate(table_alloc, size);
newhashes = HashesAllocatorTraitsType::allocate(hash_alloc, size);
}
CARBLOCAL_CATCH_ALL
{
if (newhashes)
HashesAllocatorTraitsType::deallocate(hash_alloc, newhashes, size);
if (newtable)
TableAllocatorTraitsType::deallocate(table_alloc, newtable, size);
};
m_data.m_table = std::exchange(newtable, nullptr);
m_data.m_hashes = newhashes;
std::fill(newhashes, newhashes + size, kEmpty);
CARB_LIKELY_IF(m_data.m_size != 0)
{
for (size_t* e = oldhashes; e != oldend; ++e)
{
if (isHashValid(*e))
{
auto& old = oldtable[e - oldhashes];
auto result = internal_insert_multi2(*e, Traits::get_key(old));
// TODO: Handle exception during move
TableAllocatorTraitsType::construct(table_alloc, result, std::move(old));
TableAllocatorTraitsType::destroy(table_alloc, std::addressof(old));
}
}
}
HashesAllocatorTraitsType::deallocate(hash_alloc, oldhashes, size);
TableAllocatorTraitsType::deallocate(table_alloc, oldtable, size);
}
#endif
private:
void internalSwap(RobinHood& other, std::true_type)
{
std::swap(m_data, other.m_data);
}
void internalSwap(RobinHood& other, std::false_type)
{
CARB_FATAL_UNLESS(
m_data.get_allocator() == other.get_allocator(), "Undefined behavior to swap if allocators are not equal");
std::swap(m_data, other.m_data);
}
void copyAssign(const RobinHood& other)
{
TableAllocatorType alloc(m_data.get_allocator());
clear();
reserve(other.size());
for (auto& entry : other)
{
auto result = internal_insert_multi(Traits::get_key(entry));
TableAllocatorTraitsType::construct(alloc, result, entry); // copy
}
}
void moveConstructWithAlloc(RobinHood&& other, const allocator_type&, std::true_type)
{
std::swap(m_data.m_table, other.m_data.m_table);
std::swap(m_data.m_hashes, other.m_data.m_hashes);
std::swap(m_data.m_size, other.m_data.m_size);
std::swap(m_data.m_tableSize, other.m_data.m_tableSize);
}
void moveConstructWithAlloc(RobinHood&& other, const allocator_type& alloc, std::false_type)
{
if (other.m_data.get_allocator() == alloc)
{
// Allocators are equal => can move
moveConstructWithAlloc(std::move(other), alloc, std::true_type{});
}
else
{
TableAllocatorType al(m_data.get_allocator());
// Allocators not equal => must re-create
CARBLOCAL_TRY_BEGIN
{
reserve(other.size());
for (auto& entry : other)
{
auto result = internal_insert_multi(Traits::get_key(entry));
TableAllocatorTraitsType::construct(al, result, std::move(entry)); // move
}
}
CARBLOCAL_CATCH_ALL
{
clear();
}
}
}
void moveAssign(RobinHood&& other, std::true_type)
{
std::swap(m_data, other.m_data);
}
void moveAssign(RobinHood&& other, std::false_type)
{
if (m_data.get_allocator() == other.m_data.get_allocator())
{
// Allocators are equal => can swap
std::swap(m_data, other.m_data);
}
else
{
TableAllocatorType alloc(m_data.get_allocator());
// Allocators not equal => must re-create
CARBLOCAL_TRY_BEGIN
{
clear();
reserve(other.size());
for (auto& entry : other)
{
auto result = internal_insert_multi(Traits::get_key(entry));
TableAllocatorTraitsType::construct(alloc, result, std::move(entry)); // move
}
}
CARBLOCAL_CATCH_ALL
{
clear();
}
}
}
CARB_VIZ Data m_data;
};
template <typename Traits>
void swap(RobinHood<Traits>& lhs, RobinHood<Traits>& rhs)
{
lhs.swap(rhs);
}
template <typename Traits1, typename Traits2>
bool operator==(const RobinHood<Traits1>& lhs, const RobinHood<Traits2>& rhs)
{
if (&lhs == &rhs)
return true;
if (lhs.size() != rhs.size())
return false;
return std::is_permutation(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}
template <typename Traits1, typename Traits2>
bool operator!=(const RobinHood<Traits1>& lhs, const RobinHood<Traits2>& rhs)
{
return !(lhs == rhs);
}
} // namespace detail
} // namespace carb::container
#include "../detail/ExceptionEpilog.h"