#include <WasmAlgo.hpp>

Inheritance diagram for m::wasm::ChainedHashTable< IsGlobal >:

Collaboration diagram for m::wasm::ChainedHashTable< IsGlobal >:

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
	ChainedHashTable (const Schema &schema, std::vector< HashTable::index_t > key_indices, uint32_t initial_capacity)
	Creates a chained hash table with schema `schema`, keys at `key_indices`, and an initial capacity for `initial_capacity` buckets, i.e.

	ChainedHashTable (ChainedHashTable &&)=default

	~ChainedHashTable ()

void	setup () override
	Performs the setup of all local variables of the hash table (by reading them from the global backups iff.

void	teardown () override
	Performs the teardown of all local variables of the hash table (by storing them into the global backups iff.

void	set_high_watermark (double percentage) override
	Sets the high watermark, i.e.

void	clear () override
	Clears the hash table.

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

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

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

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

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

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

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

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	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`.

const Schema &	schema () const

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.

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 Types
template<typename T >
using	var_t = std::conditional_t< IsGlobal, Global< T >, Var< T > >
	‍variable type dependent on whether the hash table should be globally usable

Private Member Functions
Ptr< void >	begin () const
	Returns the address of the first bucket, i.e.

Ptr< void >	end () const
	Returns the address of the past-the-end bucket.

U32x1	mask () const
	Returns the mask of the hash table, i.e.

U32x1	capacity () const
	Returns the capacity of the hash table.

U32x1	size_in_bytes () const
	Returns the overall size in bytes of the actual hash table, i.e.

void	update_high_watermark ()
	Updates internal high watermark variables according to the currently set high watermark percentage.

void	create_predication_dummy ()
	Creates dummy entry for predication.

Ptr< void >	hash_to_bucket (std::vector< SQL_t > key) const
	Returns the bucket address for the key `key` by hashing it.

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

Boolx1	equal_key (Ptr< void > entry, std::vector< SQL_t > key) const
	Compares the key of the entry at address `entry` with `key` and returns `true` iff they are equal.

void	insert_key (Ptr< void > entry, std::vector< SQL_t > key)
	Inserts the key `key` into the entry at address `entry`.

entry_t	value_entry (Ptr< void > entry) const
	Returns a handle for the entry at address `entry` which may be used to write the values of the corresponding entry.

const_entry_t	entry (Ptr< void > entry) const
	Returns a handle for the entry at address `entry` which may be used to read both the keys and the values of the corresponding entry.

void	rehash ()
	Performs rehashing, i.e.

	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
HashTable::size_t	entry_size_in_bytes_
	entry size in bytes

HashTable::size_t	entry_max_alignment_in_bytes_
	alignment requirement in bytes of a single entry

std::vector< HashTable::offset_t >	entry_offsets_in_bytes_
	entry offsets, i.e.

HashTable::offset_t	null_bitmap_offset_in_bytes_
	‍offset of NULL bitmap; only specified if at least one entry is nullable

HashTable::offset_t	ptr_offset_in_bytes_
	offset of pointer to next entry in linked collision list

std::optional< Var< Ptr< void > > >	address_
	base address of hash table

std::optional< Var< U32x1 > >	mask_
	‍mask of hash table, i.e. number of buckets / collision lists minus 1; always a power of 2 minus 1

std::optional< Var< U32x1 > >	num_entries_
	number of occupied entries of hash table

double	high_watermark_percentage_ = 1.0
	fraction of occupied entries before growing the hash table is required

std::optional< Var< U32x1 > >	high_watermark_absolute_
	‍maximum number of entries before growing the hash table is required

chained_hash_table_storage< IsGlobal >	storage_
	‍if `IsGlobal`, contains backups for address, capacity, number of entries, and absolute high watermark

std::optional< FunctionProxy< void(void)> >	rehash_
	‍function to perform rehashing; only possible for global hash tables since variables have to be updated

std::vector< std::pair< Ptr< void >, U32x1 > >	dummy_allocations_
	address-size pairs of dummy entry allocations

std::optional< var_t< Ptr< void > > >	predication_dummy_
	dummy bucket used for predication

Ptr< value_t >	value_

std::optional< Ptr< U8x1 > >	is_null_byte_

std::optional< U8x1 >	is_null_mask_

Detailed Description

template<bool IsGlobal>
struct m::wasm::ChainedHashTable< IsGlobal >

Definition at line 625 of file WasmAlgo.hpp.

Member Typedef Documentation

◆ callback_t

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

inherited

Definition at line 486 of file WasmAlgo.hpp.

◆ const_entry_t

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

inherited

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>

inherited

Definition at line 364 of file WasmAlgo.hpp.

◆ entry_t

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

inherited

Definition at line 483 of file WasmAlgo.hpp.

◆ hint_t

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

inherited

Definition at line 487 of file WasmAlgo.hpp.

◆ index_t

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

inherited

Definition at line 57 of file WasmAlgo.hpp.

◆ offset_t

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

inherited

Definition at line 58 of file WasmAlgo.hpp.

◆ reference_t

template<sql_type T>

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

inherited

Definition at line 362 of file WasmAlgo.hpp.

◆ size_t

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

inherited

Definition at line 59 of file WasmAlgo.hpp.

◆ value_t

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

inherited

Definition at line 75 of file WasmAlgo.hpp.

◆ var_t

template<bool IsGlobal>

template<typename T >

using m::wasm::ChainedHashTable< IsGlobal >::var_t = std::conditional_t<IsGlobal, Global<T>, Var<T> >

private

‍variable type dependent on whether the hash table should be globally usable

Definition at line 630 of file WasmAlgo.hpp.

Constructor & Destructor Documentation

◆ ChainedHashTable() [1/2]

template<bool IsGlobal>

ChainedHashTable::ChainedHashTable	(	const Schema &	schema,
		std::vector< HashTable::index_t >	key_indices,
		uint32_t	initial_capacity
	)

Creates a chained hash table with schema schema, keys at key_indices, and an initial capacity for initial_capacity buckets, i.e.

collision lists. Emits code to allocate a fresh hash table. The hash table is globally visible iff

Template Parameters

IsGlobal.

Definition at line 476 of file WasmAlgo.cpp.

◆ ChainedHashTable() [2/2]

template<bool IsGlobal>

m::wasm::ChainedHashTable< IsGlobal >::ChainedHashTable ( ChainedHashTable< IsGlobal > && )

default

◆ ~ChainedHashTable()

template<bool IsGlobal>

ChainedHashTable::~ChainedHashTable

Definition at line 528 of file WasmAlgo.cpp.

References m::wasm::Module::Allocator, m::wasm::and, m::wasm::make_signed(), Wasm_insist, and WHILE.

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 )

inherited

◆ begin()

template<bool IsGlobal>

Ptr< void > m::wasm::ChainedHashTable< IsGlobal >::begin ( ) const

inlineprivate

Returns the address of the first bucket, i.e.

the pointer to the first collision list.

Definition at line 665 of file WasmAlgo.hpp.

References m::wasm::ChainedHashTable< IsGlobal >::address_, and M_insist.

Referenced by m::wasm::ChainedHashTable< IsGlobal >::end().

◆ capacity()

template<bool IsGlobal>

U32x1 m::wasm::ChainedHashTable< IsGlobal >::capacity ( ) const

inlineprivate

Returns the capacity of the hash table.

Definition at line 672 of file WasmAlgo.hpp.

References m::wasm::ChainedHashTable< IsGlobal >::mask().

Referenced by m::wasm::ChainedHashTable< IsGlobal >::size_in_bytes(), and m::wasm::ChainedHashTable< IsGlobal >::update_high_watermark().

◆ clear()

template<bool IsGlobal>

void ChainedHashTable::clear ( )

overridevirtual

Clears the hash table.

Implements m::wasm::HashTable.

Definition at line 674 of file WasmAlgo.cpp.

References m::wasm::Module::Allocator, m::wasm::and, m::wasm::U, Wasm_insist, and WHILE.

◆ clone() [1/2]

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

inlineinherited

‍Returns a deep copy of this.

Definition at line 113 of file WasmAlgo.hpp.

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

◆ clone() [2/2]

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

inlinestaticprotectedinherited

‍Copies the vector of SQL_ts values.

Definition at line 491 of file WasmAlgo.hpp.

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

◆ compute_bucket()

template<bool IsGlobal>

Ptr< void > ChainedHashTable::compute_bucket ( std::vector< SQL_t > key ) const

overridevirtual

Computes the bucket for key key.

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

Implements m::wasm::HashTable.

Definition at line 717 of file WasmAlgo.cpp.

References m::wasm::CodeGenContext::Get(), M_insist, m::wasm::num_simd_lanes, and m::wasm::Select().

◆ create_predication_dummy()

template<bool IsGlobal>

void m::wasm::ChainedHashTable< IsGlobal >::create_predication_dummy ( )

inlineprivate

Creates dummy entry for predication.

Definition at line 709 of file WasmAlgo.hpp.

References m::wasm::Module::Allocator, M_insist, m::wasm::ChainedHashTable< IsGlobal >::predication_dummy_, and m::wasm::U.

◆ discard()

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

inlineinherited

‍Discards this.

Definition at line 105 of file WasmAlgo.hpp.

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

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

◆ dummy_entry()

template<bool IsGlobal>

HashTable::entry_t ChainedHashTable::dummy_entry ( )

overridevirtual

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.

Implements m::wasm::HashTable.

Definition at line 931 of file WasmAlgo.cpp.

References m::wasm::Module::Allocator, and M_CONSTEXPR_COND.

◆ emplace()

template<bool IsGlobal>

HashTable::entry_t ChainedHashTable::emplace ( std::vector< SQL_t > key )

overridevirtual

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.

Implements m::wasm::HashTable.

Definition at line 739 of file WasmAlgo.cpp.

References IF, and M_insist.

◆ emplace_without_rehashing()

template<bool IsGlobal>

HashTable::entry_t ChainedHashTable::emplace_without_rehashing ( std::vector< SQL_t > key )

private

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. No rehashing of the hash table must be performed, i.e. the hash table must have at least one free entry slot.

Definition at line 754 of file WasmAlgo.cpp.

References m::wasm::Module::Allocator, m::wasm::clone(), m::wasm::CodeGenContext::Get(), M_insist, m::wasm::num_simd_lanes, m::wasm::Select(), and Wasm_insist.

◆ end()

template<bool IsGlobal>

Ptr< void > m::wasm::ChainedHashTable< IsGlobal >::end ( ) const

inlineprivate

Returns the address of the past-the-end bucket.

Definition at line 667 of file WasmAlgo.hpp.

References m::wasm::ChainedHashTable< IsGlobal >::begin(), and m::wasm::ChainedHashTable< IsGlobal >::size_in_bytes().

◆ entry()

template<bool IsGlobal>

HashTable::const_entry_t ChainedHashTable::entry ( Ptr< void > entry ) const

private

Returns a handle for the entry at address entry which may be used to read both the keys and the values of the corresponding entry.

Definition at line 1138 of file WasmAlgo.cpp.

References m::wasm::HashTable::the_entry< IsConst >::add(), m::wasm::and, m::wasm::HashTable::the_entry< IsConst >::get(), M_unreachable, m::wasm::n, m::T(), and m::visit().

◆ equal_key()

template<bool IsGlobal>

Boolx1 ChainedHashTable::equal_key	(	Ptr< void >	entry,
		std::vector< SQL_t >	key
	)		const

private

Compares the key of the entry at address entry with key and returns true iff they are equal.

Definition at line 945 of file WasmAlgo.cpp.

References m::wasm::and, M_insist, M_unreachable, m::wasm::n, m::wasm::res, m::T(), and m::visit().

◆ find() [1/2]

template<bool IsGlobal>

std::pair< HashTable::entry_t, Boolx1 > ChainedHashTable::find	(	std::vector< SQL_t >	key,
		hint_t	bucket_hint
	)

overridevirtual

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.

Implements m::wasm::HashTable.

Definition at line 873 of file WasmAlgo.cpp.

References m::wasm::BREAK(), m::wasm::clone(), and WHILE.

◆ find() [2/2]

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

inlineinherited

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 m::wasm::HashTable::find().

◆ for_each()

template<bool IsGlobal>

void ChainedHashTable::for_each ( callback_t Pipeline ) const

overridevirtual

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.

Implements m::wasm::HashTable.

Definition at line 893 of file WasmAlgo.cpp.

References m::wasm::and, Wasm_insist, and WHILE.

◆ for_each_in_equal_range()

template<bool IsGlobal>

void ChainedHashTable::for_each_in_equal_range	(	std::vector< SQL_t >	key,
		callback_t	Pipeline,
		bool	predicated,
		hint_t	bucket_hint
	)		const

overridevirtual

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.

Implements m::wasm::HashTable.

Definition at line 909 of file WasmAlgo.cpp.

References m::wasm::Environment::add_predicate(), m::wasm::clone(), m::wasm::CodeGenContext::env(), m::wasm::CodeGenContext::Get(), IF, and WHILE.

◆ hash_to_bucket()

template<bool IsGlobal>

Ptr< void > ChainedHashTable::hash_to_bucket ( std::vector< SQL_t > key ) const

private

Returns the bucket address for the key key by hashing it.

Definition at line 693 of file WasmAlgo.cpp.

References m::wasm::and, m::wasm::hash(), M_insist, m::wasm::make_signed(), m::wasm::murmur3_64a_hash(), and Wasm_insist.

◆ insert_key()

template<bool IsGlobal>

void ChainedHashTable::insert_key	(	Ptr< void >	entry,
		std::vector< SQL_t >	key
	)

private

Inserts the key key into the entry at address entry.

Definition at line 1010 of file WasmAlgo.cpp.

References m::wasm::discard(), insert(), M_insist, M_unreachable, m::wasm::n, m::T(), and m::visit().

◆ mask()

template<bool IsGlobal>

U32x1 m::wasm::ChainedHashTable< IsGlobal >::mask ( ) const

inlineprivate

Returns the mask of the hash table, i.e.

capacity - 1U, which can be used to mask a hash value into the range of the hash table.

Definition at line 670 of file WasmAlgo.hpp.

References M_insist, and m::wasm::ChainedHashTable< IsGlobal >::mask_.

Referenced by m::wasm::ChainedHashTable< IsGlobal >::capacity().

◆ operator T()

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

inlineinherited

‍Loads the value of this.

Definition at line 175 of file WasmAlgo.hpp.

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

◆ operator==()

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

inlineinherited

‍Compares this with _value.

Definition at line 163 of file WasmAlgo.hpp.

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

◆ rehash()

template<bool IsGlobal>

void ChainedHashTable::rehash

private

Performs rehashing, i.e.

resizes the hash table to the double of its capacity (by internally creating a new one) while asserting that all entries are still correctly contained in the resized hash table (by rehashing and reinserting but not reallocating them into the newly created hash table).

Definition at line 1205 of file WasmAlgo.cpp.

References m::wasm::Module::Allocator, m::wasm::and, FUNCTION, m::wasm::CodeGenContext::Get(), M_insist, M_unreachable, m::wasm::make_unsigned(), m::wasm::CodeGenContext::scoped_environment(), Throw, Wasm_insist, and WHILE.

◆ schema()

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

inlineinherited

Definition at line 531 of file WasmAlgo.hpp.

References m::wasm::HashTable::schema_.

Referenced by m::wasm::HashTable::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`
	)

protectedinherited

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()

template<bool IsGlobal>

void m::wasm::ChainedHashTable< IsGlobal >::set_high_watermark ( double percentage )

inlineoverridevirtual

Sets the high watermark, i.e.

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

Implements m::wasm::HashTable.

Definition at line 688 of file WasmAlgo.hpp.

References m::wasm::ChainedHashTable< IsGlobal >::high_watermark_percentage_, and m::wasm::ChainedHashTable< IsGlobal >::update_high_watermark().

◆ set_not_null()

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

inlineinherited

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

Definition at line 155 of file WasmAlgo.hpp.

References m::wasm::HashTable::is_null_byte_, m::wasm::HashTable::is_null_mask_, M_insist, and m::wasm::HashTable::value_.

◆ set_null()

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

inlineinherited

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

Definition at line 148 of file WasmAlgo.hpp.

References m::wasm::HashTable::is_null_byte_, m::wasm::HashTable::is_null_mask_, M_insist, and m::wasm::HashTable::value_.

◆ set_null_bit()

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

inlineinherited

‍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(), m::wasm::HashTable::is_null_byte_, m::wasm::HashTable::is_null_mask_, M_insist, m::setbit(), and m::wasm::HashTable::value_.

◆ set_value()

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

inlineinherited

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

Definition at line 132 of file WasmAlgo.hpp.

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

◆ setup()

template<bool IsGlobal>

void ChainedHashTable::setup

overridevirtual

Performs the setup of all local variables of the hash table (by reading them from the global backups iff.

Template Parameters

IsGlobal). 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.

Implements m::wasm::HashTable.

Definition at line 569 of file WasmAlgo.cpp.

References m::wasm::Module::Allocator, ELSE, IF, and M_insist.

◆ size_in_bytes()

template<bool IsGlobal>

U32x1 m::wasm::ChainedHashTable< IsGlobal >::size_in_bytes ( ) const

inlineprivate

Returns the overall size in bytes of the actual hash table, i.e.

without collision list entries.

Definition at line 674 of file WasmAlgo.hpp.

References m::wasm::ChainedHashTable< IsGlobal >::capacity().

Referenced by m::wasm::ChainedHashTable< IsGlobal >::end().

◆ teardown()

template<bool IsGlobal>

void ChainedHashTable::teardown

overridevirtual

Performs the teardown of all local variables of the hash table (by storing them into the global backups iff.

Template Parameters

IsGlobal). 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.

Implements m::wasm::HashTable.

Definition at line 615 of file WasmAlgo.cpp.

References m::wasm::Module::Allocator, m::wasm::and, M_insist, Wasm_insist, and WHILE.

◆ the_reference() [1/4]

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

inlineexplicitinherited

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
	)

inlineexplicitprivateinherited

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
	)

inlineexplicitinherited

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
	)

inlineexplicitprivateinherited

Definition at line 82 of file WasmAlgo.hpp.

References m::wasm::HashTable::is_null_byte_, m::wasm::HashTable::is_null_mask_, and M_insist.

◆ try_emplace()

template<bool IsGlobal>

std::pair< HashTable::entry_t, Boolx1 > ChainedHashTable::try_emplace ( std::vector< SQL_t > key )

overridevirtual

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.

Implements m::wasm::HashTable.

Definition at line 796 of file WasmAlgo.cpp.

References m::wasm::Module::Allocator, BLOCK, m::wasm::BREAK(), m::wasm::clone(), m::wasm::CONTINUE(), ELSE, m::wasm::CodeGenContext::Get(), m::wasm::GOTO(), IF, LOOP, M_insist, m::wasm::num_simd_lanes, m::wasm::Select(), m::wasm::U, and Wasm_insist.

◆ update_high_watermark()

template<bool IsGlobal>

void m::wasm::ChainedHashTable< IsGlobal >::update_high_watermark ( )

inlineprivate

Updates internal high watermark variables according to the currently set high watermark percentage.

Definition at line 699 of file WasmAlgo.hpp.

References m::wasm::ChainedHashTable< IsGlobal >::capacity(), m::wasm::ChainedHashTable< IsGlobal >::high_watermark_absolute_, m::wasm::ChainedHashTable< IsGlobal >::high_watermark_percentage_, M_insist, and Wasm_insist.

Referenced by m::wasm::ChainedHashTable< IsGlobal >::set_high_watermark().

◆ value_entry()

template<bool IsGlobal>

HashTable::entry_t ChainedHashTable::value_entry ( Ptr< void > entry ) const

private

Returns a handle for the entry at address entry which may be used to write the values of the corresponding entry.

Definition at line 1075 of file WasmAlgo.cpp.

References m::wasm::HashTable::the_entry< IsConst >::add(), m::wasm::HashTable::the_entry< IsConst >::get(), M_unreachable, m::wasm::n, m::T(), and m::visit().

Field Documentation

◆ address_

template<bool IsGlobal>

std::optional<Var<Ptr<void> > > m::wasm::ChainedHashTable< IsGlobal >::address_

private

base address of hash table

Definition at line 639 of file WasmAlgo.hpp.

Referenced by m::wasm::ChainedHashTable< IsGlobal >::begin().

◆ dummy_allocations_

template<bool IsGlobal>

std::vector<std::pair<Ptr<void>, U32x1> > m::wasm::ChainedHashTable< IsGlobal >::dummy_allocations_

private

address-size pairs of dummy entry allocations

Definition at line 650 of file WasmAlgo.hpp.

◆ entry_max_alignment_in_bytes_

template<bool IsGlobal>

HashTable::size_t m::wasm::ChainedHashTable< IsGlobal >::entry_max_alignment_in_bytes_

private

alignment requirement in bytes of a single entry

Definition at line 633 of file WasmAlgo.hpp.

Referenced by m::wasm::ChainedHashTable< IsGlobal >::ChainedHashTable().

◆ entry_offsets_in_bytes_

template<bool IsGlobal>

std::vector<HashTable::offset_t> m::wasm::ChainedHashTable< IsGlobal >::entry_offsets_in_bytes_

private

entry offsets, i.e.

offsets of keys and values

Definition at line 634 of file WasmAlgo.hpp.

Referenced by m::wasm::ChainedHashTable< IsGlobal >::ChainedHashTable().

◆ entry_size_in_bytes_

template<bool IsGlobal>

HashTable::size_t m::wasm::ChainedHashTable< IsGlobal >::entry_size_in_bytes_

private

entry size in bytes

Definition at line 632 of file WasmAlgo.hpp.

Referenced by m::wasm::ChainedHashTable< IsGlobal >::ChainedHashTable().

◆ high_watermark_absolute_

template<bool IsGlobal>

std::optional<Var<U32x1> > m::wasm::ChainedHashTable< IsGlobal >::high_watermark_absolute_

private

‍maximum number of entries before growing the hash table is required

Definition at line 645 of file WasmAlgo.hpp.

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

◆ high_watermark_percentage_

template<bool IsGlobal>

double m::wasm::ChainedHashTable< IsGlobal >::high_watermark_percentage_ = 1.0

private

fraction of occupied entries before growing the hash table is required

Definition at line 643 of file WasmAlgo.hpp.

Referenced by m::wasm::ChainedHashTable< IsGlobal >::set_high_watermark(), and m::wasm::ChainedHashTable< IsGlobal >::update_high_watermark().

◆ is_null_byte_

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

privateinherited

Definition at line 79 of file WasmAlgo.hpp.

◆ is_null_mask_

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

privateinherited

Definition at line 80 of file WasmAlgo.hpp.

◆ IsConst

m::wasm::HashTable::IsConst

inherited

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_

protectedinherited

keys of hash table

Definition at line 505 of file WasmAlgo.hpp.

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

◆ mask_

template<bool IsGlobal>

std::optional<Var<U32x1> > m::wasm::ChainedHashTable< IsGlobal >::mask_

private

‍mask of hash table, i.e. number of buckets / collision lists minus 1; always a power of 2 minus 1

Definition at line 641 of file WasmAlgo.hpp.

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

◆ null_bitmap_offset_in_bytes_

template<bool IsGlobal>

HashTable::offset_t m::wasm::ChainedHashTable< IsGlobal >::null_bitmap_offset_in_bytes_

private

‍offset of NULL bitmap; only specified if at least one entry is nullable

Definition at line 636 of file WasmAlgo.hpp.

Referenced by m::wasm::ChainedHashTable< IsGlobal >::ChainedHashTable().

◆ num_entries_

template<bool IsGlobal>

std::optional<Var<U32x1> > m::wasm::ChainedHashTable< IsGlobal >::num_entries_

private

number of occupied entries of hash table

Definition at line 642 of file WasmAlgo.hpp.

◆ predication_dummy_

template<bool IsGlobal>

std::optional<var_t<Ptr<void> > > m::wasm::ChainedHashTable< IsGlobal >::predication_dummy_

private

dummy bucket used for predication

Definition at line 651 of file WasmAlgo.hpp.

Referenced by m::wasm::ChainedHashTable< IsGlobal >::create_predication_dummy().

◆ ptr_offset_in_bytes_

template<bool IsGlobal>

HashTable::offset_t m::wasm::ChainedHashTable< IsGlobal >::ptr_offset_in_bytes_

private

offset of pointer to next entry in linked collision list

Definition at line 637 of file WasmAlgo.hpp.

Referenced by m::wasm::ChainedHashTable< IsGlobal >::ChainedHashTable().

◆ rehash_

template<bool IsGlobal>

std::optional<FunctionProxy<void(void)> > m::wasm::ChainedHashTable< IsGlobal >::rehash_

private

‍function to perform rehashing; only possible for global hash tables since variables have to be updated

Definition at line 649 of file WasmAlgo.hpp.

◆ schema_

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

protectedinherited

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 m::wasm::HashTable::schema().

◆ storage_

template<bool IsGlobal>

chained_hash_table_storage<IsGlobal> m::wasm::ChainedHashTable< IsGlobal >::storage_

private

‍if IsGlobal, contains backups for address, capacity, number of entries, and absolute high watermark

Definition at line 647 of file WasmAlgo.hpp.

Referenced by m::wasm::ChainedHashTable< IsGlobal >::ChainedHashTable().

◆ value_

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

privateinherited

Definition at line 78 of file WasmAlgo.hpp.

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

◆ value_indices_

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

protectedinherited

values of hash table

Definition at line 506 of file WasmAlgo.hpp.

Referenced by m::wasm::HashTable::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

Public Types

Public Member Functions

Data Fields

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Private Types

Private Member Functions

Private Attributes

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

◆ var_t

Constructor & Destructor Documentation

◆ ChainedHashTable() [1/2]

◆ ChainedHashTable() [2/2]

◆ ~ChainedHashTable()

Member Function Documentation

◆ and()

◆ begin()

◆ capacity()

◆ clear()

◆ clone() [1/2]

◆ clone() [2/2]

◆ compute_bucket()

◆ create_predication_dummy()

◆ discard()

◆ dummy_entry()

◆ emplace()

◆ emplace_without_rehashing()

◆ end()

◆ entry()

◆ equal_key()

◆ find() [1/2]

◆ find() [2/2]

◆ for_each()

◆ for_each_in_equal_range()

◆ hash_to_bucket()

◆ insert_key()

◆ mask()

◆ operator T()

◆ operator==()

◆ rehash()

◆ schema()

◆ set_byte_offsets()

◆ set_high_watermark()

◆ set_not_null()

◆ set_null()

◆ set_null_bit()

◆ set_value()

◆ setup()

◆ size_in_bytes()

◆ teardown()

◆ the_reference() [1/4]

◆ the_reference() [2/4]

◆ the_reference() [3/4]

◆ the_reference() [4/4]

◆ try_emplace()

◆ update_high_watermark()

◆ value_entry()

Field Documentation

◆ address_

◆ dummy_allocations_

◆ entry_max_alignment_in_bytes_

◆ entry_offsets_in_bytes_

◆ entry_size_in_bytes_

◆ high_watermark_absolute_

◆ high_watermark_percentage_

◆ is_null_byte_

◆ is_null_mask_

◆ IsConst