Quadratic probing strategy, i.e. More...

#include <WasmAlgo.hpp>

Inheritance diagram for m::wasm::QuadraticProbing:

Collaboration diagram for m::wasm::QuadraticProbing:

Public Member Functions
	QuadraticProbing (const OpenAddressingHashTableBase &ht)

Ptr< void >	skip_slots (Ptr< void > bucket, U32x1 skips) const override
	Returns the address of the `skips` -th (starting with index 0) slot in the bucket starting at `bucket`.

Ptr< void >	advance_to_next_slot (Ptr< void > slot, U32x1 current_step) const override
	Returns the address of the `current_step` -th slot (starting with index 0) of a bucket which follows the slot `slot`.

Protected Attributes
const OpenAddressingHashTableBase &	ht_
	open addressing hash table which uses `this` probing strategy

Detailed Description

Quadratic probing strategy, i.e.

at each step i, the slot to access next in a bucket is computed by skipping i slots, e.g. the thirdly accessed slot in a bucket is slot number 1+2+3=6.

Definition at line 1027 of file WasmAlgo.hpp.

Constructor & Destructor Documentation

◆ QuadraticProbing()

m::wasm::QuadraticProbing::QuadraticProbing ( const OpenAddressingHashTableBase & ht )

inline

Definition at line 1029 of file WasmAlgo.hpp.

Member Function Documentation

◆ advance_to_next_slot()

Ptr< void > QuadraticProbing::advance_to_next_slot	(	Ptr< void >	slot,
		U32x1	current_step
	)		const

overridevirtual

Returns the address of the current_step -th slot (starting with index 0) of a bucket which follows the slot slot.

Implements m::wasm::OpenAddressingHashTableBase::ProbingStrategy.

Definition at line 2411 of file WasmAlgo.cpp.

References m::wasm::OpenAddressingHashTableBase::end(), m::wasm::OpenAddressingHashTableBase::entry_size_in_bytes(), m::wasm::OpenAddressingHashTableBase::ProbingStrategy::ht_, m::wasm::Select(), m::wasm::OpenAddressingHashTableBase::size_in_bytes(), and Wasm_insist.

◆ skip_slots()

Ptr< void > QuadraticProbing::skip_slots	(	Ptr< void >	bucket,
		U32x1	skips
	)		const

overridevirtual

Returns the address of the skips -th (starting with index 0) slot in the bucket starting at bucket.

Implements m::wasm::OpenAddressingHashTableBase::ProbingStrategy.

Definition at line 2401 of file WasmAlgo.cpp.

References m::wasm::OpenAddressingHashTableBase::end(), m::wasm::OpenAddressingHashTableBase::entry_size_in_bytes(), m::wasm::OpenAddressingHashTableBase::ProbingStrategy::ht_, m::wasm::OpenAddressingHashTableBase::mask(), m::wasm::Select(), m::wasm::OpenAddressingHashTableBase::size_in_bytes(), and Wasm_insist.

Field Documentation

◆ ht_

const OpenAddressingHashTableBase& m::wasm::OpenAddressingHashTableBase::ProbingStrategy::ht_

protectedinherited

open addressing hash table which uses this probing strategy

Definition at line 777 of file WasmAlgo.hpp.

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

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

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

Public Member Functions

Protected Attributes