#include <WasmAlgo.hpp>

Inheritance diagram for m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >:

Collaboration diagram for m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >:

Public Types
using	ref_t = uint32_t
	4 bytes for reference counting

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
	OpenAddressingHashTable (const Schema &schema, std::vector< HashTable::index_t > key_indices, uint32_t initial_capacity)
	Creates an open addressing hash table with schema `schema`, keys at `key_indices`, and an initial capacity for `initial_capacity` entries.

	OpenAddressingHashTable (OpenAddressingHashTable &&)=default

	~OpenAddressingHashTable ()

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.

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.

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

U32x1	size_in_bytes () const
	Returns the overall size in bytes of the hash table.

HashTable::size_t	entry_size_in_bytes () const
	Returns the size in bytes of a single entry in the hash table.

template<typename T >
void	set_probing_strategy ()
	Sets the hash table's probing strategy to.

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

void	clear () override
	Clears the hash table.

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
const ProbingStrategy &	probing_strategy () const
	Returns the currently used probing strategy of the hash table.

Reference< ref_t >	reference_count (Ptr< void > entry) const
	Returns a `Reference` to the reference counter for the entry at address `entry`.

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

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::unique_ptr< ProbingStrategy >	probing_strategy_
	probing strategy to handle collisions

HashTable::offset_t	refs_offset_in_bytes_
	offset in bytes for reference counter

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

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

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 override
	Returns the address of the first entry.

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

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

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

void	create_predication_dummy ()
	Creates dummy entry for predication.

Ptr< void >	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 > slot, std::vector< SQL_t > key) const
	Compares the key of the slot at address `slot` with `key` and returns `true` iff they are equal.

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

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

const_entry_t	entry (Ptr< void > slot) const
	Returns a handle for the slot at address `slot` 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
open_addressing_hash_table_layout< ValueInPlace >	layout_
	layout of hash table

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

std::optional< Var< U32x1 > >	mask_
	mask of hash table; always a power of 2 minus 1, i.e. 0b0..01..1

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

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

open_addressing_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 entry 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, bool ValueInPlace>
struct m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >

Definition at line 899 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.

◆ ref_t

using m::wasm::OpenAddressingHashTableBase::ref_t = uint32_t

inherited

4 bytes for reference counting

Definition at line 771 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, bool ValueInPlace>

template<typename T >

using m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::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 904 of file WasmAlgo.hpp.

Constructor & Destructor Documentation

◆ OpenAddressingHashTable() [1/2]

template<bool IsGlobal, bool ValueInPlace>

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

Creates an open addressing hash table with schema schema, keys at key_indices, and an initial capacity for initial_capacity entries.

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

Template Parameters

IsGlobal	and the values are stores in-place iff
ValueInPlace.

Definition at line 1355 of file WasmAlgo.cpp.

References m::contains(), m::wasm::OpenAddressingHashTableBase::entry_max_alignment_in_bytes_, m::wasm::OpenAddressingHashTableBase::entry_size_in_bytes_, m::Type::Get_Bitmap(), m::Type::Get_Integer(), m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::high_watermark_absolute_, m::wasm::HashTable::key_indices_, m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::layout_, M_insist, m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::mask_, m::wasm::OpenAddressingHashTableBase::refs_offset_in_bytes_, m::wasm::HashTable::schema_, m::wasm::HashTable::set_byte_offsets(), m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::storage_, and m::wasm::HashTable::value_indices_.

◆ OpenAddressingHashTable() [2/2]

template<bool IsGlobal, bool ValueInPlace>

m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::OpenAddressingHashTable ( OpenAddressingHashTable< IsGlobal, ValueInPlace > && )

default

◆ ~OpenAddressingHashTable()

template<bool IsGlobal, bool ValueInPlace>

OpenAddressingHashTable::~OpenAddressingHashTable

Definition at line 1477 of file WasmAlgo.cpp.

References m::wasm::Module::Allocator, m::wasm::and, IF, 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, bool ValueInPlace>

Ptr< void > m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::begin ( ) const

inlineoverrideprivatevirtual

Returns the address of the first entry.

Implements m::wasm::OpenAddressingHashTableBase.

Definition at line 930 of file WasmAlgo.hpp.

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

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

◆ capacity()

U32x1 m::wasm::OpenAddressingHashTableBase::capacity ( ) const

inlineinherited

Returns the capacity of the hash table.

Definition at line 812 of file WasmAlgo.hpp.

References m::wasm::OpenAddressingHashTableBase::mask().

Referenced by m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::end(), m::wasm::OpenAddressingHashTableBase::size_in_bytes(), m::wasm::LinearProbing::skip_slots(), and m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::update_high_watermark().

◆ clear()

void OpenAddressingHashTableBase::clear ( )

overridevirtualinherited

Clears the hash table.

Implements m::wasm::HashTable.

Definition at line 1322 of file WasmAlgo.cpp.

References m::wasm::and, m::wasm::OpenAddressingHashTableBase::begin(), m::wasm::OpenAddressingHashTableBase::end(), m::wasm::OpenAddressingHashTableBase::entry_size_in_bytes_, m::wasm::OpenAddressingHashTableBase::reference_count(), 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, bool ValueInPlace>

Ptr< void > OpenAddressingHashTable::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 1595 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, bool ValueInPlace>

void m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::create_predication_dummy ( )

inlineprivate

Creates dummy entry for predication.

Definition at line 959 of file WasmAlgo.hpp.

References m::wasm::Module::Allocator, m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::dummy_allocations_, m::wasm::OpenAddressingHashTableBase::entry_max_alignment_in_bytes_, m::wasm::OpenAddressingHashTableBase::entry_size_in_bytes_, M_insist, m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::predication_dummy_, and m::wasm::OpenAddressingHashTableBase::reference_count().

◆ 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, bool ValueInPlace>

HashTable::entry_t OpenAddressingHashTable::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 1878 of file WasmAlgo.cpp.

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

◆ emplace()

template<bool IsGlobal, bool ValueInPlace>

HashTable::entry_t OpenAddressingHashTable::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 1617 of file WasmAlgo.cpp.

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

◆ emplace_without_rehashing()

template<bool IsGlobal, bool ValueInPlace>

Ptr< void > OpenAddressingHashTable::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 pointer to the newly inserted slot without allocating any space for possible out-of-place values. 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 1645 of file WasmAlgo.cpp.

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

◆ end()

template<bool IsGlobal, bool ValueInPlace>

Ptr< void > m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::end ( ) const

inlineoverrideprivatevirtual

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

Implements m::wasm::OpenAddressingHashTableBase.

Definition at line 931 of file WasmAlgo.hpp.

References m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::begin(), m::wasm::OpenAddressingHashTableBase::capacity(), m::wasm::OpenAddressingHashTableBase::entry_size_in_bytes_, and m::wasm::make_signed().

◆ entry()

template<bool IsGlobal, bool ValueInPlace>

HashTable::const_entry_t OpenAddressingHashTable::entry ( Ptr< void > slot ) const

private

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

< pointer to out-of-place values

Definition at line 2133 of file WasmAlgo.cpp.

References m::wasm::HashTable::the_entry< IsConst >::add(), m::wasm::and, m::wasm::NChar::clone(), m::contains(), M_CONSTEXPR_COND, M_insist, M_unreachable, m::wasm::n, m::T(), m::wasm::value, and m::visit().

◆ entry_size_in_bytes()

HashTable::size_t m::wasm::OpenAddressingHashTableBase::entry_size_in_bytes ( ) const

inlineinherited

Returns the size in bytes of a single entry in the hash table.

Definition at line 816 of file WasmAlgo.hpp.

References m::wasm::OpenAddressingHashTableBase::entry_size_in_bytes_.

Referenced by m::wasm::LinearProbing::advance_to_next_slot(), m::wasm::QuadraticProbing::advance_to_next_slot(), m::wasm::LinearProbing::skip_slots(), and m::wasm::QuadraticProbing::skip_slots().

◆ equal_key()

template<bool IsGlobal, bool ValueInPlace>

Boolx1 OpenAddressingHashTable::equal_key	(	Ptr< void >	slot,
		std::vector< SQL_t >	key
	)		const

private

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

Definition at line 1904 of file WasmAlgo.cpp.

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

◆ find() [1/2]

template<bool IsGlobal, bool ValueInPlace>

std::pair< HashTable::entry_t, Boolx1 > OpenAddressingHashTable::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 1794 of file WasmAlgo.cpp.

References m::wasm::and, m::wasm::BREAK(), m::wasm::clone(), M_insist, Wasm_insist, 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, bool ValueInPlace>

void OpenAddressingHashTable::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 1830 of file WasmAlgo.cpp.

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

◆ for_each_in_equal_range()

template<bool IsGlobal, bool ValueInPlace>

void OpenAddressingHashTable::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 1844 of file WasmAlgo.cpp.

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

◆ hash_to_bucket()

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

protectedinherited

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

Definition at line 1332 of file WasmAlgo.cpp.

References m::wasm::and, m::wasm::OpenAddressingHashTableBase::begin(), m::wasm::OpenAddressingHashTableBase::end(), m::wasm::OpenAddressingHashTableBase::entry_size_in_bytes_, m::wasm::hash(), m::wasm::HashTable::key_indices_, M_insist, m::wasm::make_signed(), m::wasm::OpenAddressingHashTableBase::mask(), m::wasm::murmur3_64a_hash(), m::wasm::HashTable::schema_, and Wasm_insist.

◆ insert_key()

template<bool IsGlobal, bool ValueInPlace>

void OpenAddressingHashTable::insert_key	(	Ptr< void >	slot,
		std::vector< SQL_t >	key
	)

private

Inserts the key key into the slot at address slot.

Definition at line 1981 of file WasmAlgo.cpp.

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

◆ mask()

template<bool IsGlobal, bool ValueInPlace>

U32x1 m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::mask ( ) const

inlineoverrideprivatevirtual

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.

Implements m::wasm::OpenAddressingHashTableBase.

Definition at line 932 of file WasmAlgo.hpp.

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

◆ 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_.

◆ probing_strategy()

const ProbingStrategy & m::wasm::OpenAddressingHashTableBase::probing_strategy ( ) const

inlineprotectedinherited

Returns the currently used probing strategy of the hash table.

Definition at line 823 of file WasmAlgo.hpp.

References M_insist, and m::wasm::OpenAddressingHashTableBase::probing_strategy_.

◆ reference_count()

Reference< ref_t > m::wasm::OpenAddressingHashTableBase::reference_count ( Ptr< void > entry ) const

inlineprotectedinherited

Returns a Reference to the reference counter for the entry at address entry.

Definition at line 826 of file WasmAlgo.hpp.

References m::wasm::OpenAddressingHashTableBase::refs_offset_in_bytes_.

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

◆ rehash()

template<bool IsGlobal, bool ValueInPlace>

void OpenAddressingHashTable::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 them into the newly created hash table).

Definition at line 2231 of file WasmAlgo.cpp.

References m::wasm::Module::Allocator, m::wasm::and, FUNCTION, m::wasm::CodeGenContext::Get(), IF, M_insist, M_unreachable, m::wasm::make_unsigned(), m::wasm::CodeGenContext::scoped_environment(), m::T(), Throw, m::wasm::U, 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()

void m::wasm::OpenAddressingHashTableBase::set_high_watermark ( double percentage )

inlineoverridevirtualinherited

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 831 of file WasmAlgo.hpp.

References m::wasm::OpenAddressingHashTableBase::high_watermark_percentage_, and m::wasm::OpenAddressingHashTableBase::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_probing_strategy()

template<typename T >

void m::wasm::OpenAddressingHashTableBase::set_probing_strategy ( )

inlineinherited

Sets the hash table's probing strategy to.

Template Parameters

T.

Definition at line 820 of file WasmAlgo.hpp.

References m::wasm::OpenAddressingHashTableBase::probing_strategy_.

◆ 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, bool ValueInPlace>

void OpenAddressingHashTable::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 1504 of file WasmAlgo.cpp.

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

◆ size_in_bytes()

U32x1 m::wasm::OpenAddressingHashTableBase::size_in_bytes ( ) const

inlineinherited

Returns the overall size in bytes of the hash table.

Definition at line 814 of file WasmAlgo.hpp.

References m::wasm::OpenAddressingHashTableBase::capacity(), and m::wasm::OpenAddressingHashTableBase::entry_size_in_bytes_.

Referenced by m::wasm::QuadraticProbing::advance_to_next_slot(), m::wasm::LinearProbing::skip_slots(), and m::wasm::QuadraticProbing::skip_slots().

◆ teardown()

template<bool IsGlobal, bool ValueInPlace>

void OpenAddressingHashTable::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 1550 of file WasmAlgo.cpp.

References m::wasm::Module::Allocator, m::wasm::and, IF, 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, bool ValueInPlace>

std::pair< HashTable::entry_t, Boolx1 > OpenAddressingHashTable::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 1702 of file WasmAlgo.cpp.

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

◆ update_high_watermark()

template<bool IsGlobal, bool ValueInPlace>

void m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::update_high_watermark ( )

inlineoverrideprivatevirtual

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

Reimplemented from m::wasm::OpenAddressingHashTableBase.

Definition at line 945 of file WasmAlgo.hpp.

References m::wasm::OpenAddressingHashTableBase::capacity(), m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::high_watermark_absolute_, m::wasm::OpenAddressingHashTableBase::high_watermark_percentage_, M_insist, m::wasm::make_unsigned(), m::wasm::HashTable::Select, and Wasm_insist.

◆ value_entry()

template<bool IsGlobal, bool ValueInPlace>

HashTable::entry_t OpenAddressingHashTable::value_entry ( Ptr< void > ptr ) const

private

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

If

Template Parameters

ValueInPlace,the given pointer ptr is interpreted as slot pointer, otherwise, it is interpreted as pointer to the out-of-place values.

Definition at line 2058 of file WasmAlgo.cpp.

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

Field Documentation

◆ address_

template<bool IsGlobal, bool ValueInPlace>

std::optional<Var<Ptr<void> > > m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::address_

private

base address of hash table

Definition at line 907 of file WasmAlgo.hpp.

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

◆ dummy_allocations_

template<bool IsGlobal, bool ValueInPlace>

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

private

address-size pairs of dummy entry allocations

Definition at line 915 of file WasmAlgo.hpp.

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

◆ entry_max_alignment_in_bytes_

HashTable::size_t m::wasm::OpenAddressingHashTableBase::entry_max_alignment_in_bytes_

protectedinherited

alignment requirement in bytes of a single entry

Definition at line 795 of file WasmAlgo.hpp.

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

◆ entry_size_in_bytes_

HashTable::size_t m::wasm::OpenAddressingHashTableBase::entry_size_in_bytes_

protectedinherited

entry size in bytes

Definition at line 794 of file WasmAlgo.hpp.

Referenced by m::wasm::OpenAddressingHashTableBase::clear(), m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::create_predication_dummy(), m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::end(), m::wasm::OpenAddressingHashTableBase::entry_size_in_bytes(), m::wasm::OpenAddressingHashTableBase::hash_to_bucket(), m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::OpenAddressingHashTable(), and m::wasm::OpenAddressingHashTableBase::size_in_bytes().

◆ high_watermark_absolute_

template<bool IsGlobal, bool ValueInPlace>

std::optional<Var<U32x1> > m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::high_watermark_absolute_

private

maximum number of entries before growing the hash table is required

Definition at line 910 of file WasmAlgo.hpp.

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

◆ high_watermark_percentage_

double m::wasm::OpenAddressingHashTableBase::high_watermark_percentage_ = 1.0

protectedinherited

fraction of occupied entries before growing the hash table is required

Definition at line 796 of file WasmAlgo.hpp.

Referenced by m::wasm::OpenAddressingHashTableBase::set_high_watermark(), and m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::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().

◆ layout_

template<bool IsGlobal, bool ValueInPlace>

open_addressing_hash_table_layout<ValueInPlace> m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::layout_

private

layout of hash table

Definition at line 906 of file WasmAlgo.hpp.

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

◆ mask_

template<bool IsGlobal, bool ValueInPlace>

std::optional<Var<U32x1> > m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::mask_

private

mask of hash table; always a power of 2 minus 1, i.e. 0b0..01..1

Definition at line 908 of file WasmAlgo.hpp.

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

◆ num_entries_

template<bool IsGlobal, bool ValueInPlace>

std::optional<Var<U32x1> > m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::num_entries_

private

number of occupied entries of hash table

Definition at line 909 of file WasmAlgo.hpp.

◆ predication_dummy_

template<bool IsGlobal, bool ValueInPlace>

std::optional<var_t<Ptr<void> > > m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::predication_dummy_

private

dummy entry used for predication

Definition at line 916 of file WasmAlgo.hpp.

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

◆ probing_strategy_

std::unique_ptr<ProbingStrategy> m::wasm::OpenAddressingHashTableBase::probing_strategy_

protectedinherited

probing strategy to handle collisions

Definition at line 792 of file WasmAlgo.hpp.

Referenced by m::wasm::OpenAddressingHashTableBase::probing_strategy(), and m::wasm::OpenAddressingHashTableBase::set_probing_strategy().

◆ refs_offset_in_bytes_

HashTable::offset_t m::wasm::OpenAddressingHashTableBase::refs_offset_in_bytes_

protectedinherited

offset in bytes for reference counter

Definition at line 793 of file WasmAlgo.hpp.

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

◆ rehash_

template<bool IsGlobal, bool ValueInPlace>

std::optional<FunctionProxy<void(void)> > m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::rehash_

private

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

Definition at line 914 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, bool ValueInPlace>

open_addressing_hash_table_storage<IsGlobal> m::wasm::OpenAddressingHashTable< IsGlobal, ValueInPlace >::storage_

private

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

Definition at line 912 of file WasmAlgo.hpp.

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

◆ 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

◆ ref_t

◆ reference_t

◆ size_t

◆ value_t

◆ var_t

Constructor & Destructor Documentation

◆ OpenAddressingHashTable() [1/2]

◆ OpenAddressingHashTable() [2/2]

◆ ~OpenAddressingHashTable()

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

◆ entry_size_in_bytes()

◆ equal_key()

◆ find() [1/2]

◆ find() [2/2]

◆ for_each()

◆ for_each_in_equal_range()

◆ hash_to_bucket()

◆ insert_key()

◆ mask()

◆ operator T()

◆ operator==()

◆ probing_strategy()

◆ reference_count()

◆ rehash()

◆ schema()

◆ set_byte_offsets()

◆ set_high_watermark()

◆ set_not_null()

◆ set_null()

◆ set_null_bit()

◆ set_probing_strategy()

◆ 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_size_in_bytes_

◆ high_watermark_absolute_