di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self > Class Template Reference

Node based (closed addressing) hash table. More...

#include <di/container/hash/node/node_hash_table.h>

Inheritance diagram for di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >:

Public Member Functions
	NodeHashTable ()=default
	NodeHashTable (NodeHashTable const &)=delete
auto	operator= (NodeHashTable const &) -> NodeHashTable &=delete
constexpr	NodeHashTable (Eq eq, Hasher hasher={})
constexpr	NodeHashTable (NodeHashTable &&other)
constexpr auto	operator= (NodeHashTable &&other) -> NodeHashTable &
constexpr	~NodeHashTable ()
constexpr auto	size () const -> usize
constexpr auto	empty () const -> bool
constexpr auto	bucket_count () const -> usize
constexpr auto	begin () -> Iterator
constexpr auto	begin () const -> ConstIterator
constexpr auto	end () -> Iterator
constexpr auto	end () const -> ConstIterator
constexpr auto	unconst_iterator (ConstIterator it) -> Iterator
constexpr auto	insert_node (Node &node)
constexpr auto	insert_node (ConstIterator, Node &node)
constexpr auto	erase_impl (ConstIterator it) -> Iterator
template<typename U> requires (concepts::Predicate<Eq&, Key const&, U const&> && concepts::HashSame<Key, U>)
constexpr auto	equal_range_impl (U &&needle) const
template<typename U> requires (concepts::Predicate<Eq&, Key const&, U const&> && concepts::HashSame<Key, U>)
constexpr auto	find_impl (U &&needle) const -> ConstIterator
constexpr auto	reserve (usize new_capacity) -> decltype(util::declval< Buckets & >().reserve_from_nothing(new_capacity))
constexpr void	merge_impl (NodeHashTable &&other)

Protected Types
using	Node = HashNode<Tag>
using	Iterator = HashNodeIterator<Value, Tag>
using	ConstIterator = container::ConstIteratorImpl<Iterator>
using	ConcreteNode = decltype(Tag::node_type(in_place_type<Value>))
using	Key = meta::Type<detail::NodeHashTableKey<Value, is_map>>

Protected Member Functions
constexpr auto	down_cast_self () -> decltype(auto)
constexpr auto	node_value (Node &node) const -> Value &
constexpr auto	node_value (Node const &node) const -> Value const &
constexpr void	merge_impl_without_rehashing (NodeHashTable &&other)
constexpr auto	insert_node_without_rehashing (Node &node, bool call_insertion_hook=true)
template<typename U>
constexpr auto	hash (U const &value) const -> u64
constexpr auto	hash (Value const &value) const -> u64
template<typename T, typename U>
constexpr auto	equal (T const &a, U const &b) const -> bool
template<typename T>
constexpr auto	equal (T const &a, Value const &b) const -> bool
template<typename T>
constexpr auto	equal (Value const &a, T const &b) const -> bool
constexpr auto	equal (Value const &a, Value const &b) const -> bool

Protected Attributes
Buckets	m_buckets {}
usize	m_size { 0 }
Eq	m_eq {}
Hasher	m_hasher {}

Static Protected Attributes
static constexpr bool	allow_rehashing_in_insert = false

Friends
template<typename, typename, concepts::Hasher, typename, typename, typename, bool, bool, typename>
class	NodeHashTable

Detailed Description

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>
class di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >

Node based (closed addressing) hash table.

This is fairly straightforward implementation of a hash table. It uses a vector of buckets, where each bucket is a singlely-linked list of nodes.

Member Typedef Documentation

ConcreteNode

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

using di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::ConcreteNode = decltype(Tag::node_type(in_place_type<Value>))

protected

ConstIterator

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

using di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::ConstIterator = container::ConstIteratorImpl<Iterator>

protected

Iterator

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

using di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::Iterator = HashNodeIterator<Value, Tag>

protected

Key

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

using di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::Key = meta::Type<detail::NodeHashTableKey<Value, is_map>>

protected

Node

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

using di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::Node = HashNode<Tag>

protected

Constructor & Destructor Documentation

NodeHashTable() [1/4]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::NodeHashTable ( )

default

NodeHashTable() [2/4]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::NodeHashTable ( NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self > const & )

delete

NodeHashTable() [3/4]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::NodeHashTable ( Eq eq, Hasher hasher = {} )

inlineexplicitconstexpr

NodeHashTable() [4/4]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::NodeHashTable ( NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self > && other )

inlineconstexpr

~NodeHashTable()

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::~NodeHashTable ( )

inlineconstexpr

Member Function Documentation

begin() [1/2]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::begin ( ) ->Iterator

inlineconstexpr

begin() [2/2]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::begin ( ) const->ConstIterator

inlineconstexpr

bucket_count()

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::bucket_count ( ) const->usize

inlineconstexpr

down_cast_self()

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::down_cast_self ( ) ->decltype(auto)

inlineconstexprprotected

empty()

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::empty ( ) const->bool

inlineconstexpr

end() [1/2]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::end ( ) ->Iterator

inlineconstexpr

end() [2/2]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::end ( ) const->ConstIterator

inlineconstexpr

equal() [1/4]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

template<typename T, typename U>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::equal ( T const & a, U const & b ) const->bool

inlineconstexprprotected

equal() [2/4]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

template<typename T>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::equal ( T const & a, Value const & b ) const->bool

inlineconstexprprotected

equal() [3/4]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

template<typename T>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::equal ( Value const & a, T const & b ) const->bool

inlineconstexprprotected

equal() [4/4]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::equal ( Value const & a, Value const & b ) const->bool

inlineconstexprprotected

equal_range_impl()

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

template<typename U>
requires (concepts::Predicate<Eq&, Key const&, U const&> && concepts::HashSame<Key, U>)

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::equal_range_impl ( U && needle ) const

inlineconstexpr

erase_impl()

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::erase_impl ( ConstIterator it ) ->Iterator

inlineconstexpr

find_impl()

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

template<typename U>
requires (concepts::Predicate<Eq&, Key const&, U const&> && concepts::HashSame<Key, U>)

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::find_impl ( U && needle ) const->ConstIterator

inlineconstexpr

hash() [1/2]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

template<typename U>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::hash ( U const & value ) const->u64

inlineconstexprprotected

hash() [2/2]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::hash ( Value const & value ) const->u64

inlineconstexprprotected

insert_node() [1/2]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::insert_node ( ConstIterator , Node & node )

inlineconstexpr

insert_node() [2/2]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::insert_node ( Node & node )

inlineconstexpr

insert_node_without_rehashing()

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::insert_node_without_rehashing ( Node & node, bool call_insertion_hook = true )

inlineconstexprprotected

merge_impl()

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

void di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::merge_impl ( NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self > && other )

inlineconstexpr

merge_impl_without_rehashing()

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

void di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::merge_impl_without_rehashing ( NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self > && other )

inlineconstexprprotected

node_value() [1/2]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::node_value ( Node & node ) const->Value &

inlineconstexprprotected

node_value() [2/2]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::node_value ( Node const & node ) const->Valueconst &

inlineconstexprprotected

operator=() [1/2]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::operator= ( NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self > && other ) ->NodeHashTable &

inlineconstexpr

operator=() [2/2]

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::operator= ( NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self > const & ) ->NodeHashTable &=delete

delete

reserve()

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::reserve ( usize new_capacity ) ->decltype(util::declval< Buckets & >().reserve_from_nothing(new_capacity))

inlineconstexpr

size()

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::size ( ) const->usize

inlineconstexpr

unconst_iterator()

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

auto di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::unconst_iterator ( ConstIterator it ) ->Iterator

inlineconstexpr

Friends And Related Symbol Documentation

NodeHashTable

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

template<typename, typename, concepts::Hasher, typename, typename, typename, bool, bool, typename>

friend class NodeHashTable

friend

Member Data Documentation

allow_rehashing_in_insert

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

bool di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::allow_rehashing_in_insert = false

staticconstexprprotected

m_buckets

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

Buckets di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::m_buckets {}

protected

m_eq

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

Eq di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::m_eq {}

protected

m_hasher

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

Hasher di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::m_hasher {}

protected

m_size

template<typename Value, typename Eq, concepts::Hasher Hasher, typename Buckets, typename Tag, typename Interface, bool is_multi, bool is_map, typename Self = Void>

usize di::container::NodeHashTable< Value, Eq, Hasher, Buckets, Tag, Interface, is_multi, is_map, Self >::m_size { 0 }

protected

---

The documentation for this class was generated from the following file:

• di/container/hash/node/node_hash_table.h