Iros
 
Loading...
Searching...
No Matches
Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes | Static Protected Attributes | Friends | List of all members
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 >:
[legend]

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 -> Value const&
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: