Hash table to hash key-value pairs in memory. More...

#include <WasmAlgo.hpp>

Inheritance diagram for m::wasm::HashTable:

Collaboration diagram for m::wasm::HashTable:

Data Structures
struct	the_entry
	Helper struct as proxy to access a hash table entry. More...

struct	the_reference
	Helper struct as proxy to access a single value (inclusive NULL bit) of a hash table entry. More...

struct	the_reference< NChar, IsConst >

Public Types
using	index_t = std::size_t

using	offset_t = int32_t

using	size_t = uint32_t

using	value_t = PrimitiveExpr< typename T::type >

template<sql_type T>
using	reference_t = the_reference< T, false >

template<sql_type T>
using	const_reference_t = the_reference< T, true >

using	entry_t = the_entry< false >

using	const_entry_t = the_entry< true >

using	callback_t = std::function< void(const_entry_t)>

using	hint_t = std::optional< Ptr< void > >

Public Member Functions
template<sql_type T, bool IsConst> requires (not std::same_as<T, NChar>)
	and (T::num_simd_lanes==1) struct the_reference< T

	the_reference (Ptr< value_t > value)

	the_reference (Ptr< value_t > value, Ptr< void > null_bitmap, uint8_t null_bit_offset)

void	discard ()
	‍Discards `this`.

the_reference	clone () const
	‍Returns a deep copy of `this`.

void	operator= (T _value)
	‍Assigns `this` to `_value`.

void	set_value (value_t value)
	‍Assigns the value of `this` to `value` w/o updating the NULL bit.

void	set_null_bit (Boolx1 is_null)
	‍Assigns the NULL bit of `this` to `is_null`. Does not update/modify the value of `this`.

void	set_null ()
	‍Sets `this` to NULL. Does not modify the value of `this`.

void	set_not_null ()
	‍Sets `this` to NOT NULL. Does not modify the value of `this`.

Boolx1	operator== (T _value)
	‍Compares `this` with `_value`.

	operator T ()
	‍Loads the value of `this`.

	HashTable ()=delete

	HashTable (const Schema &schema, std::vector< index_t > key_indices)
	Creates a hash table with schema `schema` and keys at `key_indices`.

	HashTable (const HashTable &)=delete

	HashTable (HashTable &&)=default

virtual	~HashTable ()

const Schema &	schema () const

virtual void	setup ()=0
	Performs the setup of the hash table.

virtual void	teardown ()=0
	Performs the teardown of the hash table.

virtual void	set_high_watermark (double percentage)=0
	Sets the high watermark, i.e.

virtual void	clear ()=0
	Clears the hash table.

virtual Ptr< void >	compute_bucket (std::vector< SQL_t > key) const =0
	Computes the bucket for key `key`.

virtual entry_t	emplace (std::vector< SQL_t > key)=0
	Inserts an entry into the hash table with key `key` regardless whether it already exists, i.e.

virtual std::pair< entry_t, Boolx1 >	try_emplace (std::vector< SQL_t > key)=0
	If no entry with key `key` already exists, inserts one into the hash table, i.e.

virtual std::pair< entry_t, Boolx1 >	find (std::vector< SQL_t > key, hint_t bucket_hint=hint_t())=0
	Tries to find an entry with key `key` in the hash table.

std::pair< const_entry_t, Boolx1 >	find (std::vector< SQL_t > key, hint_t bucket_hint=hint_t()) const
	Tries to find an entry with key `key` in the hash table.

virtual void	for_each (callback_t Pipeline) const =0
	Calls `Pipeline` for each entry contained in the hash table.

virtual void	for_each_in_equal_range (std::vector< SQL_t > key, callback_t Pipeline, bool predicated=false, hint_t bucket_hint=hint_t()) const =0
	Calls `Pipeline` for each entry with key `key` in the hash table, where the key comparison is performed predicated iff `predicated` is set.

virtual entry_t	dummy_entry ()=0
	Returns a handle to a newly created dummy entry which may be used to write the values for this entry.

Data Fields
	IsConst

Protected Member Functions
std::pair< size_t, size_t >	set_byte_offsets (std::vector< offset_t > &offsets_in_bytes, const std::vector< const Type * > &types, offset_t initial_offset_in_bytes=0, offset_t initial_max_alignment_in_bytes=1)
	Sets the byte offsets of an entry containing values of types `types` in `offsets_in_bytes` with the starting offset at `initial_offset_in_bytes` and an initial alignment requirement of `initial_max_alignment_in_bytes`.

Static Protected Member Functions
static std::vector< SQL_t >	clone (const std::vector< SQL_t > &values)
	‍Copies the vector of `SQL_t`s `values`.

Protected Attributes
std::reference_wrapper< const Schema >	schema_
	schema of hash table

std::vector< index_t >	key_indices_
	keys of hash table

std::vector< index_t >	value_indices_
	values of hash table

Private Member Functions
	the_reference (Ptr< value_t > value, std::optional< Ptr< U8x1 > > is_null_byte, std::optional< U8x1 > is_null_mask)

	the_reference (Ptr< value_t > value, Ptr< U8x1 > is_null_byte, U8x1 is_null_mask)

Private Attributes
Ptr< value_t >	value_

std::optional< Ptr< U8x1 > >	is_null_byte_

std::optional< U8x1 >	is_null_mask_

Friends
struct	the_entry< true >

the_reference	Select (Boolx1 cond, the_reference tru, the_reference fals)
	‍Selects either the reference `tru` or `fals` depending on the value of `cond`.

Detailed Description

Hash table to hash key-value pairs in memory.

Definition at line 55 of file WasmAlgo.hpp.

Member Typedef Documentation

◆ callback_t

using m::wasm::HashTable::callback_t = std::function<void(const_entry_t)>

Definition at line 486 of file WasmAlgo.hpp.

◆ const_entry_t

using m::wasm::HashTable::const_entry_t = the_entry<true>

Definition at line 484 of file WasmAlgo.hpp.

◆ const_reference_t

template<sql_type T>

using m::wasm::HashTable::const_reference_t = the_reference<T, true>

Definition at line 364 of file WasmAlgo.hpp.

◆ entry_t

using m::wasm::HashTable::entry_t = the_entry<false>

Definition at line 483 of file WasmAlgo.hpp.

◆ hint_t

using m::wasm::HashTable::hint_t = std::optional<Ptr<void> >

Definition at line 487 of file WasmAlgo.hpp.

◆ index_t

using m::wasm::HashTable::index_t = std::size_t

Definition at line 57 of file WasmAlgo.hpp.

◆ offset_t

using m::wasm::HashTable::offset_t = int32_t

Definition at line 58 of file WasmAlgo.hpp.

◆ reference_t

template<sql_type T>

using m::wasm::HashTable::reference_t = the_reference<T, false>

Definition at line 362 of file WasmAlgo.hpp.

◆ size_t

using m::wasm::HashTable::size_t = uint32_t

Definition at line 59 of file WasmAlgo.hpp.

◆ value_t

using m::wasm::HashTable::value_t = PrimitiveExpr<typename T::type>

Definition at line 75 of file WasmAlgo.hpp.

Constructor & Destructor Documentation

◆ HashTable() [1/4]

m::wasm::HashTable::HashTable ( )

delete

◆ HashTable() [2/4]

m::wasm::HashTable::HashTable	(	const Schema &	schema,
		std::vector< index_t >	key_indices
	)

inline

Creates a hash table with schema schema and keys at key_indices.

Definition at line 512 of file WasmAlgo.hpp.

References m::contains(), key_indices_, M_insist, m::Schema::num_entries(), schema(), and value_indices_.

◆ HashTable() [3/4]

m::wasm::HashTable::HashTable ( const HashTable & )

delete

◆ HashTable() [4/4]

m::wasm::HashTable::HashTable ( HashTable && )

default

◆ ~HashTable()

virtual m::wasm::HashTable::~HashTable ( )

inlinevirtual

Definition at line 529 of file WasmAlgo.hpp.

Member Function Documentation

◆ and()

template<sql_type T, bool IsConst>
requires (not std::same_as<T, NChar>)

m::wasm::HashTable::and ( T::num_simd_lanes = = 1 )

◆ clear()

virtual void m::wasm::HashTable::clear ( )

pure virtual

Clears the hash table.

Implemented in m::wasm::ChainedHashTable< IsGlobal >, and m::wasm::OpenAddressingHashTableBase.

◆ clone() [1/2]

the_reference m::wasm::HashTable::clone ( ) const

inline

‍Returns a deep copy of this.

Definition at line 113 of file WasmAlgo.hpp.

References is_null_byte_, is_null_mask_, and value_.

◆ clone() [2/2]

static std::vector< SQL_t > m::wasm::HashTable::clone ( const std::vector< SQL_t > & values )

inlinestaticprotected

‍Copies the vector of SQL_ts values.

Definition at line 491 of file WasmAlgo.hpp.

References M_unreachable, and m::wasm::value.

◆ compute_bucket()

virtual Ptr< void > m::wasm::HashTable::compute_bucket ( std::vector< SQL_t > key ) const

pure virtual

Computes the bucket for key key.

Often used as hint for find() and for_each_in_equal_range().

Implemented in m::wasm::ChainedHashTable< IsGlobal >, and m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >.

◆ discard()

void m::wasm::HashTable::discard ( )

inline

‍Discards this.

Definition at line 105 of file WasmAlgo.hpp.

References is_null_byte_, is_null_mask_, and value_.

Referenced by m::wasm::HashTable::the_entry< IsConst >::~the_entry().

◆ dummy_entry()

virtual entry_t m::wasm::HashTable::dummy_entry ( )

pure virtual

Returns a handle to a newly created dummy entry which may be used to write the values for this entry.

Note that even if the hash table is globally visible, this entry can only be used locally, i.e. within the function it is created in.

Implemented in m::wasm::ChainedHashTable< IsGlobal >, and m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >.

◆ emplace()

virtual entry_t m::wasm::HashTable::emplace ( std::vector< SQL_t > key )

pure virtual

Inserts an entry into the hash table with key key regardless whether it already exists, i.e.

duplicates are allowed. Returns a handle to the newly inserted entry which may be used to write the values for this entry. Rehashing of the hash table may be performed. Predication is supported, i.e. an entry is always inserted but can only be found later iff the predication predicate is fulfilled.

Implemented in m::wasm::ChainedHashTable< IsGlobal >, and m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >.

◆ find() [1/2]

std::pair< const_entry_t, Boolx1 > m::wasm::HashTable::find	(	std::vector< SQL_t >	key,
		hint_t	bucket_hint = `hint_t()`
	)		const

inline

Tries to find an entry with key key in the hash table.

Uses bucket_hint as hint to the bucket address. Returns a pair of a handle to the found entry which may be used to only read the values of this entry (if none is found this handle points to an arbitrary entry and should be ignored) and a boolean flag to indicate whether an element with the specified key was found. Predication is supported, i.e. if the predication predicate is not fulfilled, no entry will be found.

Definition at line 573 of file WasmAlgo.hpp.

References find().

◆ find() [2/2]

virtual std::pair< entry_t, Boolx1 > m::wasm::HashTable::find	(	std::vector< SQL_t >	key,
		hint_t	bucket_hint = `hint_t()`
	)

pure virtual

Tries to find an entry with key key in the hash table.

Uses bucket_hint as hint to the bucket address. Returns a pair of a handle to the found entry which may be used to both read and write the values of this entry (if none is found this handle points to an arbitrary entry and should be ignored) and a boolean flag to indicate whether an element with the specified key was found. Predication is supported, i.e. if the predication predicate is not fulfilled, no entry will be found.

Implemented in m::wasm::ChainedHashTable< IsGlobal >, and m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >.

Referenced by find().

◆ for_each()

virtual void m::wasm::HashTable::for_each ( callback_t Pipeline ) const

pure virtual

Calls Pipeline for each entry contained in the hash table.

At each call the argument is a handle to the respective entry which may be used to read both the keys and the values of this entry.

Implemented in m::wasm::ChainedHashTable< IsGlobal >, and m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >.

◆ for_each_in_equal_range()

virtual void m::wasm::HashTable::for_each_in_equal_range	(	std::vector< SQL_t >	key,
		callback_t	Pipeline,
		bool	predicated = `false`,
		hint_t	bucket_hint = `hint_t()`
	)		const

pure virtual

Calls Pipeline for each entry with key key in the hash table, where the key comparison is performed predicated iff predicated is set.

Uses bucket_hint as hint to the bucket address. At each call the argument is a handle to the respective entry which may be used to read both the keys and the values of this entry. Predication is supported, i.e. if the predication predicate is not fulfilled, the range of entries with an equal key will be empty.

Implemented in m::wasm::ChainedHashTable< IsGlobal >, and m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >.

◆ operator T()

m::wasm::HashTable::operator T ( )

inline

‍Loads the value of this.

Definition at line 175 of file WasmAlgo.hpp.

References is_null_byte_, is_null_mask_, m::T(), and value_.

◆ operator=()

void m::wasm::HashTable::operator= ( T _value )

inline

‍Assigns this to _value.

Definition at line 121 of file WasmAlgo.hpp.

References m::wasm::is_null(), is_null_byte_, is_null_mask_, M_insist, m::setbit(), m::wasm::value, and value_.

◆ operator==()

Boolx1 m::wasm::HashTable::operator== ( T _value )

inline

‍Compares this with _value.

Definition at line 163 of file WasmAlgo.hpp.

References m::wasm::and, m::wasm::is_null(), is_null_byte_, is_null_mask_, m::wasm::value, and value_.

◆ schema()

const Schema & m::wasm::HashTable::schema ( ) const

inline

Definition at line 531 of file WasmAlgo.hpp.

References schema_.

Referenced by HashTable().

◆ set_byte_offsets()

std::pair< HashTable::size_t, HashTable::size_t > HashTable::set_byte_offsets	(	std::vector< offset_t > &	offsets_in_bytes,
		const std::vector< const Type * > &	types,
		HashTable::offset_t	initial_offset_in_bytes = `0`,
		HashTable::offset_t	initial_max_alignment_in_bytes = `1`
	)

protected

Sets the byte offsets of an entry containing values of types types in offsets_in_bytes with the starting offset at initial_offset_in_bytes and an initial alignment requirement of initial_max_alignment_in_bytes.

To minimize padding, the values are sorted by their alignment requirement. Returns the byte size of an entry and its alignments requirement in bytes.

Definition at line 438 of file WasmAlgo.cpp.

References m::wasm::indices.

Referenced by m::wasm::ChainedHashTable< IsGlobal >::ChainedHashTable(), and m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::OpenAddressingHashTable().

◆ set_high_watermark()

virtual void m::wasm::HashTable::set_high_watermark ( double percentage )

pure virtual

Sets the high watermark, i.e.

the fraction of occupied entries before growing the hash table is required, to percentage.

Implemented in m::wasm::ChainedHashTable< IsGlobal >, and m::wasm::OpenAddressingHashTableBase.

◆ set_not_null()

void m::wasm::HashTable::set_not_null ( )

inline

‍Sets this to NOT NULL. Does not modify the value of this.

Definition at line 155 of file WasmAlgo.hpp.

References is_null_byte_, is_null_mask_, M_insist, and value_.

◆ set_null()

void m::wasm::HashTable::set_null ( )

inline

‍Sets this to NULL. Does not modify the value of this.

Definition at line 148 of file WasmAlgo.hpp.

References is_null_byte_, is_null_mask_, M_insist, and value_.

◆ set_null_bit()

void m::wasm::HashTable::set_null_bit ( Boolx1 is_null )

inline

‍Assigns the NULL bit of this to is_null. Does not update/modify the value of this.

Definition at line 141 of file WasmAlgo.hpp.

References m::wasm::is_null(), is_null_byte_, is_null_mask_, M_insist, m::setbit(), and value_.

◆ set_value()

void m::wasm::HashTable::set_value ( value_t value )

inline

‍Assigns the value of this to value w/o updating the NULL bit.

Definition at line 132 of file WasmAlgo.hpp.

References is_null_byte_, is_null_mask_, m::wasm::value, and value_.

◆ setup()

virtual void m::wasm::HashTable::setup ( )

pure virtual

Performs the setup of the hash table.

Must be called before any call to a setup method, i.e. setting the high watermark, or an access method, i.e. clearing, insertion, lookup, or dummy entry creation.

Implemented in m::wasm::ChainedHashTable< IsGlobal >, and m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >.

◆ teardown()

virtual void m::wasm::HashTable::teardown ( )

pure virtual

Performs the teardown of the hash table.

Must be called after all calls to a setup method, i.e. setting the high watermark, or an access method, i.e. clearing, insertion, lookup, or dummy entry creation.

Implemented in m::wasm::ChainedHashTable< IsGlobal >, and m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >.

◆ the_reference() [1/4]

m::wasm::HashTable::the_reference ( Ptr< value_t > value )

inlineexplicit

Definition at line 97 of file WasmAlgo.hpp.

◆ the_reference() [2/4]

m::wasm::HashTable::the_reference	(	Ptr< value_t >	value,
		Ptr< U8x1 >	is_null_byte,
		U8x1	is_null_mask
	)

inlineexplicitprivate

Definition at line 90 of file WasmAlgo.hpp.

◆ the_reference() [3/4]

m::wasm::HashTable::the_reference	(	Ptr< value_t >	value,
		Ptr< void >	null_bitmap,
		uint8_t	null_bit_offset
	)

inlineexplicit

Definition at line 98 of file WasmAlgo.hpp.

◆ the_reference() [4/4]

m::wasm::HashTable::the_reference	(	Ptr< value_t >	value,
		std::optional< Ptr< U8x1 > >	is_null_byte,
		std::optional< U8x1 >	is_null_mask
	)

inlineexplicitprivate

Definition at line 82 of file WasmAlgo.hpp.

References is_null_byte_, is_null_mask_, and M_insist.

◆ try_emplace()

virtual std::pair< entry_t, Boolx1 > m::wasm::HashTable::try_emplace ( std::vector< SQL_t > key )

pure virtual

If no entry with key key already exists, inserts one into the hash table, i.e.

no duplicates are inserted. Returns a pair of a handle to the entry with the given key which may be used to write the values for this entry and a boolean flag to indicate whether an insertion was performed. Rehashing of the hash table may be performed. Predication is supported, i.e. an entry is always inserted but can only be found later iff the predication predicate is fulfilled.

Implemented in m::wasm::ChainedHashTable< IsGlobal >, and m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >.

Friends And Related Function Documentation

◆ Select

the_reference Select	(	Boolx1	cond,
		the_reference	tru,
		the_reference	fals
	)

friend

‍Selects either the reference tru or fals depending on the value of cond.

Definition at line 183 of file WasmAlgo.hpp.

Referenced by m::wasm::HashTable::the_reference< NChar, IsConst >::operator NChar(), and m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::update_high_watermark().

◆ the_entry< true >

friend struct the_entry< true >

friend

Definition at line 70 of file WasmAlgo.hpp.

Referenced by m::wasm::HashTable::the_entry< IsConst >::operator the_entry< true >().

Field Documentation

◆ is_null_byte_

std::optional<Ptr<U8x1> > m::wasm::HashTable::is_null_byte_

private

Definition at line 79 of file WasmAlgo.hpp.

◆ is_null_mask_

std::optional<U8x1> m::wasm::HashTable::is_null_mask_

private

Definition at line 80 of file WasmAlgo.hpp.

◆ IsConst

m::wasm::HashTable::IsConst

Initial value:

{

friend struct the_entry<false>

Definition at line 70 of file WasmAlgo.hpp.

◆ key_indices_

std::vector<index_t> m::wasm::HashTable::key_indices_

protected

keys of hash table

Definition at line 505 of file WasmAlgo.hpp.

Referenced by m::wasm::OpenAddressingHashTableBase::hash_to_bucket(), HashTable(), and m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::OpenAddressingHashTable().

◆ schema_

std::reference_wrapper<const Schema> m::wasm::HashTable::schema_

protected

schema of hash table

Definition at line 504 of file WasmAlgo.hpp.

Referenced by m::wasm::ChainedHashTable< IsGlobal >::ChainedHashTable(), m::wasm::OpenAddressingHashTableBase::hash_to_bucket(), m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::OpenAddressingHashTable(), and schema().

◆ value_

Ptr<value_t> m::wasm::HashTable::value_

private

Definition at line 78 of file WasmAlgo.hpp.

Referenced by clone(), discard(), operator T(), operator=(), operator==(), set_not_null(), set_null(), set_null_bit(), and set_value().

◆ value_indices_

std::vector<index_t> m::wasm::HashTable::value_indices_

protected

values of hash table

Definition at line 506 of file WasmAlgo.hpp.

Referenced by HashTable(), and m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::OpenAddressingHashTable().

The documentation for this struct was generated from the following files:

src/backend/WasmAlgo.hpp
src/backend/WasmAlgo.cpp

Data Structures

Public Types

Public Member Functions

Data Fields

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ callback_t

◆ const_entry_t

◆ const_reference_t

◆ entry_t

◆ hint_t

◆ index_t

◆ offset_t

◆ reference_t

◆ size_t

◆ value_t

Constructor & Destructor Documentation

◆ HashTable() [1/4]

◆ HashTable() [2/4]

◆ HashTable() [3/4]

◆ HashTable() [4/4]

◆ ~HashTable()

Member Function Documentation

◆ and()

◆ clear()

◆ clone() [1/2]

◆ clone() [2/2]

◆ compute_bucket()

◆ discard()

◆ dummy_entry()

◆ emplace()

◆ find() [1/2]

◆ find() [2/2]

◆ for_each()

◆ for_each_in_equal_range()

◆ operator T()

◆ operator=()

◆ operator==()

◆ schema()

◆ set_byte_offsets()

◆ set_high_watermark()

◆ set_not_null()

◆ set_null()

◆ set_null_bit()

◆ set_value()

◆ setup()

◆ teardown()

◆ the_reference() [1/4]

◆ the_reference() [2/4]

◆ the_reference() [3/4]

◆ the_reference() [4/4]

◆ try_emplace()

Friends And Related Function Documentation

◆ Select

◆ the_entry< true >

Field Documentation

◆ is_null_byte_

◆ is_null_mask_

◆ IsConst

◆ key_indices_

◆ schema_

◆ value_

◆ value_indices_