Quotient filter for probabilistic set membership with deletion. More...

#include <quotient-filter.H>

Collaboration diagram for Aleph::Quotient_Filter< T >:

Public Member Functions
	Quotient_Filter (uint8_t q, uint8_t r, uint32_t seed=0x5F3759DF)
	Construct a quotient filter.

Quotient_Filter &	insert (const T &item)
	Insert an element.

bool	contains (const T &item) const noexcept
	Test membership.

bool	remove (const T &item) noexcept
	Remove an element.

size_t	size () const noexcept
	Number of elements.

size_t	capacity () const noexcept
	Number of slots (2^q).

double	load_factor () const noexcept
	Current load factor.

bool	is_empty () const noexcept
	True if empty.

uint8_t	q () const noexcept
	Quotient bits.

uint8_t	r () const noexcept
	Remainder bits.

double	false_positive_rate () const noexcept
	Theoretical FP probability ~ 2^{-r}.

uint32_t	seed () const noexcept
	Hash seed.

size_t	memory_usage () const noexcept
	Memory usage in bytes.

void	clear () noexcept
	Remove all elements.

void	merge (const Quotient_Filter &other)
	Merge another filter (same q, r, seed).

void	swap (Quotient_Filter &other) noexcept
	Swap in O(1).

Static Public Member Functions
static Quotient_Filter	from_capacity (size_t expected_n, double fp_rate, uint32_t seed=0x5F3759DF)
	Construct from desired capacity and false positive rate.

static std::pair< uint8_t, uint8_t >	estimate (size_t n, double fp_rate)
	Estimate (q, r) for n elements and target FP rate.

Private Types
enum class	Insert_Result { inserted , duplicate , full }

Private Member Functions
uint64_t	rem_mask () const noexcept

bool	get_occ (size_t i) const noexcept

bool	get_cont (size_t i) const noexcept

bool	get_shft (size_t i) const noexcept

bool	slot_empty (size_t i) const noexcept

bool	has_element (const size_t i) const noexcept

bool	is_run_start (const size_t i) const noexcept

void	set_occ (const size_t i, const bool v) noexcept

void	set_cont (const size_t i, const bool v) noexcept

void	set_shft (const size_t i, const bool v) noexcept

uint64_t	get_rem (const size_t i) const noexcept

void	set_rem (const size_t i, const uint64_t rem) noexcept

void	set_element (const size_t i, const bool cont, const bool shft, const uint64_t rem) noexcept

void	clear_element (const size_t i) noexcept

size_t	incr (const size_t i) const noexcept

size_t	decr (const size_t i) const noexcept

std::pair< size_t, uint64_t >	fingerprint (const T &item) const

size_t	find_run_start (size_t fq) const noexcept

size_t	find_first_unused (size_t start) const noexcept

void	shift_elements_right (size_t pos, size_t empty) noexcept

Insert_Result	do_insert (size_t fq, uint64_t fr)

void	shift_elements_left (size_t pos) noexcept

Private Attributes
uint8_t	q_

uint8_t	r_

size_t	num_slots_

size_t	num_elems_

uint32_t	seed_

Array< uint64_t >	slots_

Static Private Attributes
static constexpr uint64_t	OCC_BIT = 1ULL << 0

static constexpr uint64_t	CONT_BIT = 1ULL << 1

static constexpr uint64_t	SHFT_BIT = 1ULL << 2

static constexpr uint64_t	META_MASK = 0x7ULL

Detailed Description

template<typename T>
class Aleph::Quotient_Filter< T >

Quotient filter for probabilistic set membership with deletion.

Template Parameters

T	Element type. Must be hashable via `murmur3hash(T, seed)`.

Definition at line 137 of file quotient-filter.H.

Member Enumeration Documentation

◆ Insert_Result

template<typename T >

enum class Aleph::Quotient_Filter::Insert_Result

strongprivate

Enumerator
inserted
duplicate
full

Definition at line 378 of file quotient-filter.H.

Constructor & Destructor Documentation

◆ Quotient_Filter()

template<typename T >

Aleph::Quotient_Filter< T >::Quotient_Filter	(	uint8_t	q,
		uint8_t	r,
		uint32_t	seed = `0x5F3759DF`
	)

inline

Construct a quotient filter.

Parameters

[in]	q	Number of quotient bits (2^q slots). Must be in [1, 32].
[in]	r	Remainder bits per slot (FP rate ~ 2^{-r}). Must be in [1, 60].
[in]	seed	Hash seed (default: 0x5F3759DF).

Exceptions

std::domain_error if q or r are out of range, or q + r > 64.

Definition at line 486 of file quotient-filter.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::num_slots_, Aleph::Quotient_Filter< T >::q(), Aleph::Quotient_Filter< T >::r(), and Aleph::Quotient_Filter< T >::slots_.

Member Function Documentation

◆ capacity()

template<typename T >

size_t Aleph::Quotient_Filter< T >::capacity ( ) const

inlinenoexcept

Number of slots (2^q).

O(1).

Definition at line 615 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::num_slots_.

◆ clear()

template<typename T >

void Aleph::Quotient_Filter< T >::clear ( )

inlinenoexcept

Remove all elements.

O(2^q).

Definition at line 663 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::num_elems_, Aleph::Quotient_Filter< T >::num_slots_, and Aleph::Quotient_Filter< T >::slots_.

◆ clear_element()

template<typename T >

void Aleph::Quotient_Filter< T >::clear_element ( const size_t i )

inlineprivatenoexcept

Definition at line 304 of file quotient-filter.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::get_occ(), Aleph::Quotient_Filter< T >::OCC_BIT, and Aleph::Quotient_Filter< T >::slots_.

Referenced by Aleph::Quotient_Filter< T >::shift_elements_left().

◆ contains()

template<typename T >

bool Aleph::Quotient_Filter< T >::contains ( const T & item ) const

inlinenoexcept

Test membership.

May return false positives (~2^{-r}), never false negatives.

Definition at line 545 of file quotient-filter.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::find_run_start(), Aleph::Quotient_Filter< T >::fingerprint(), Aleph::Quotient_Filter< T >::get_cont(), Aleph::Quotient_Filter< T >::get_occ(), Aleph::Quotient_Filter< T >::get_rem(), and Aleph::Quotient_Filter< T >::incr().

Referenced by demo_merge(), example_performance(), Aleph::Quotient_Filter< T >::insert(), TEST(), TEST(), and TEST().

◆ decr()

template<typename T >

size_t Aleph::Quotient_Filter< T >::decr ( const size_t i ) const

inlineprivatenoexcept

Definition at line 315 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::num_slots_.

Referenced by Aleph::Quotient_Filter< T >::find_run_start(), and Aleph::Quotient_Filter< T >::shift_elements_right().

◆ do_insert()

template<typename T >

Insert_Result Aleph::Quotient_Filter< T >::do_insert	(	size_t	fq,
		uint64_t	fr
	)

inlineprivate

Definition at line 386 of file quotient-filter.H.

Referenced by Aleph::Quotient_Filter< T >::insert(), and Aleph::Quotient_Filter< T >::merge().

◆ estimate()

template<typename T >

static std::pair< uint8_t, uint8_t > Aleph::Quotient_Filter< T >::estimate	(	size_t	n,
		double	fp_rate
	)

inlinestatic

Estimate (q, r) for n elements and target FP rate.

Definition at line 695 of file quotient-filter.H.

References ah_domain_error_if, and Aleph::divide_and_conquer_partition_dp().

Referenced by TEST().

◆ false_positive_rate()

template<typename T >

double Aleph::Quotient_Filter< T >::false_positive_rate ( ) const

inlinenoexcept

Theoretical FP probability ~ 2^{-r}.

Definition at line 645 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::r_.

◆ find_first_unused()

template<typename T >

size_t Aleph::Quotient_Filter< T >::find_first_unused ( size_t start ) const

inlineprivatenoexcept

Definition at line 354 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::has_element(), and Aleph::Quotient_Filter< T >::incr().

Referenced by Aleph::Quotient_Filter< T >::do_insert().

◆ find_run_start()

template<typename T >

size_t Aleph::Quotient_Filter< T >::find_run_start ( size_t fq ) const

inlineprivatenoexcept

Definition at line 330 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::decr(), Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::get_cont(), Aleph::Quotient_Filter< T >::get_occ(), Aleph::Quotient_Filter< T >::get_shft(), and Aleph::Quotient_Filter< T >::incr().

Referenced by Aleph::Quotient_Filter< T >::contains(), Aleph::Quotient_Filter< T >::do_insert(), and Aleph::Quotient_Filter< T >::remove().

◆ fingerprint()

template<typename T >

std::pair< size_t, uint64_t > Aleph::Quotient_Filter< T >::fingerprint ( const T & item ) const

inlineprivate

Definition at line 320 of file quotient-filter.H.

References Aleph::divide_and_conquer_partition_dp(), h, Aleph::murmur3hash(), Aleph::Quotient_Filter< T >::num_slots_, Aleph::Quotient_Filter< T >::q_, Aleph::Quotient_Filter< T >::rem_mask(), and Aleph::Quotient_Filter< T >::seed_.

Referenced by Aleph::Quotient_Filter< T >::contains(), Aleph::Quotient_Filter< T >::insert(), and Aleph::Quotient_Filter< T >::remove().

◆ from_capacity()

template<typename T >

static Quotient_Filter Aleph::Quotient_Filter< T >::from_capacity	(	size_t	expected_n,
		double	fp_rate,
		uint32_t	seed = `0x5F3759DF`
	)

inlinestatic

Construct from desired capacity and false positive rate.

Parameters

[in]	expected_n	Expected number of elements.
[in]	fp_rate	Target false positive probability.
[in]	seed	Hash seed.

Exceptions

std::domain_error if expected_n == 0 or fp_rate not in (0,1).

Definition at line 504 of file quotient-filter.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), and Aleph::Quotient_Filter< T >::seed().

Referenced by demo_cache(), and TEST().

◆ get_cont()

template<typename T >

bool Aleph::Quotient_Filter< T >::get_cont ( size_t i ) const

inlineprivatenoexcept

Definition at line 167 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::CONT_BIT, and Aleph::Quotient_Filter< T >::slots_.

Referenced by Aleph::Quotient_Filter< T >::contains(), Aleph::Quotient_Filter< T >::do_insert(), Aleph::Quotient_Filter< T >::find_run_start(), Aleph::Quotient_Filter< T >::is_run_start(), Aleph::Quotient_Filter< T >::remove(), and Aleph::Quotient_Filter< T >::shift_elements_left().

◆ get_occ()

template<typename T >

bool Aleph::Quotient_Filter< T >::get_occ ( size_t i ) const

inlineprivatenoexcept

Definition at line 162 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::OCC_BIT, and Aleph::Quotient_Filter< T >::slots_.

Referenced by Aleph::Quotient_Filter< T >::clear_element(), Aleph::Quotient_Filter< T >::contains(), Aleph::Quotient_Filter< T >::do_insert(), Aleph::Quotient_Filter< T >::find_run_start(), Aleph::Quotient_Filter< T >::remove(), Aleph::Quotient_Filter< T >::set_element(), Aleph::Quotient_Filter< T >::shift_elements_left(), and Aleph::Quotient_Filter< T >::shift_elements_right().

◆ get_rem()

template<typename T >

uint64_t Aleph::Quotient_Filter< T >::get_rem ( const size_t i ) const

inlineprivatenoexcept

Definition at line 285 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::rem_mask(), and Aleph::Quotient_Filter< T >::slots_.

Referenced by Aleph::Quotient_Filter< T >::contains(), Aleph::Quotient_Filter< T >::do_insert(), and Aleph::Quotient_Filter< T >::remove().

◆ get_shft()

template<typename T >

bool Aleph::Quotient_Filter< T >::get_shft ( size_t i ) const

inlineprivatenoexcept

Definition at line 172 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::SHFT_BIT, and Aleph::Quotient_Filter< T >::slots_.

Referenced by Aleph::Quotient_Filter< T >::find_run_start(), and Aleph::Quotient_Filter< T >::shift_elements_left().

◆ has_element()

template<typename T >

bool Aleph::Quotient_Filter< T >::has_element ( const size_t i ) const

inlineprivatenoexcept

Definition at line 250 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::META_MASK, and Aleph::Quotient_Filter< T >::slots_.

Referenced by Aleph::Quotient_Filter< T >::find_first_unused(), Aleph::Quotient_Filter< T >::is_run_start(), Aleph::Quotient_Filter< T >::remove(), and Aleph::Quotient_Filter< T >::shift_elements_left().

◆ incr()

template<typename T >

size_t Aleph::Quotient_Filter< T >::incr ( const size_t i ) const

inlineprivatenoexcept

Definition at line 310 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::num_slots_.

Referenced by Aleph::Quotient_Filter< T >::contains(), Aleph::Quotient_Filter< T >::do_insert(), Aleph::Quotient_Filter< T >::find_first_unused(), Aleph::Quotient_Filter< T >::find_run_start(), Aleph::Quotient_Filter< T >::remove(), and Aleph::Quotient_Filter< T >::shift_elements_left().

◆ insert()

template<typename T >

Quotient_Filter & Aleph::Quotient_Filter< T >::insert ( const T & item )

inline

Insert an element.

After insertion, contains(item) is guaranteed true. Duplicates are silently ignored.

Exceptions

std::overflow_error if the filter is full.

Definition at line 525 of file quotient-filter.H.

References ah_overflow_error, Aleph::Quotient_Filter< T >::contains(), Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::do_insert(), Aleph::Quotient_Filter< T >::duplicate, Aleph::Quotient_Filter< T >::fingerprint(), Aleph::Quotient_Filter< T >::full, Aleph::Quotient_Filter< T >::inserted, Aleph::Quotient_Filter< T >::num_elems_, and Aleph::Quotient_Filter< T >::num_slots_.

Referenced by demo_merge(), example_performance(), TEST(), TEST(), and TEST().

◆ is_empty()

template<typename T >

bool Aleph::Quotient_Filter< T >::is_empty ( ) const

inlinenoexcept

True if empty.

O(1).

Definition at line 627 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::num_elems_.

◆ is_run_start()

template<typename T >

bool Aleph::Quotient_Filter< T >::is_run_start ( const size_t i ) const

inlineprivatenoexcept

Definition at line 256 of file quotient-filter.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::get_cont(), and Aleph::Quotient_Filter< T >::has_element().

◆ load_factor()

template<typename T >

double Aleph::Quotient_Filter< T >::load_factor ( ) const

inlinenoexcept

Current load factor.

O(1).

Definition at line 621 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::num_elems_, and Aleph::Quotient_Filter< T >::num_slots_.

◆ memory_usage()

template<typename T >

size_t Aleph::Quotient_Filter< T >::memory_usage ( ) const

inlinenoexcept

Memory usage in bytes.

Definition at line 657 of file quotient-filter.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Quotient_Filter< T >::num_slots_.

Referenced by example_memory_optimization(), example_performance(), and TEST().

◆ merge()

template<typename T >

void Aleph::Quotient_Filter< T >::merge ( const Quotient_Filter< T > & other )

inline

Merge another filter (same q, r, seed).

O(2^q).

Exceptions

std::domain_error on parameter mismatch.

Definition at line 673 of file quotient-filter.H.

References ah_domain_error_if, ah_overflow_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::do_insert(), Aleph::Quotient_Filter< T >::full, Aleph::Quotient_Filter< T >::num_elems_, Aleph::Quotient_Filter< T >::num_slots_, Aleph::Quotient_Filter< T >::q_, Aleph::Quotient_Filter< T >::r_, and Aleph::Quotient_Filter< T >::seed_.

Referenced by demo_merge(), TEST(), TEST(), and TEST().

◆ q()

template<typename T >

uint8_t Aleph::Quotient_Filter< T >::q ( ) const

inlinenoexcept

Quotient bits.

Definition at line 633 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::q_.

Referenced by Aleph::Quotient_Filter< T >::Quotient_Filter().

◆ r()

template<typename T >

uint8_t Aleph::Quotient_Filter< T >::r ( ) const

inlinenoexcept

Remainder bits.

Definition at line 639 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::r_.

Referenced by Aleph::Quotient_Filter< T >::Quotient_Filter().

◆ rem_mask()

template<typename T >

uint64_t Aleph::Quotient_Filter< T >::rem_mask ( ) const

inlineprivatenoexcept

Definition at line 157 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::r_.

Referenced by Aleph::Quotient_Filter< T >::do_insert(), Aleph::Quotient_Filter< T >::fingerprint(), Aleph::Quotient_Filter< T >::get_rem(), Aleph::Quotient_Filter< T >::set_element(), and Aleph::Quotient_Filter< T >::set_rem().

◆ remove()

template<typename T >

bool Aleph::Quotient_Filter< T >::remove ( const T & item )

inlinenoexcept

Remove an element.

Returns: true if the fingerprint was found and removed.

Definition at line 570 of file quotient-filter.H.

◆ seed()

template<typename T >

uint32_t Aleph::Quotient_Filter< T >::seed ( ) const

inlinenoexcept

Hash seed.

Definition at line 651 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::seed_.

Referenced by Aleph::Quotient_Filter< T >::from_capacity().

◆ set_cont()

template<typename T >

void Aleph::Quotient_Filter< T >::set_cont	(	const size_t	i,
		const bool	v
	)

inlineprivatenoexcept

Definition at line 269 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::CONT_BIT, Aleph::divide_and_conquer_partition_dp(), and Aleph::Quotient_Filter< T >::slots_.

Referenced by Aleph::Quotient_Filter< T >::do_insert(), and Aleph::Quotient_Filter< T >::remove().

◆ set_element()

template<typename T >

void Aleph::Quotient_Filter< T >::set_element	(	const size_t	i,
		const bool	cont,
		const bool	shft,
		const uint64_t	rem
	)

inlineprivatenoexcept

Definition at line 297 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::CONT_BIT, Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::get_occ(), Aleph::Quotient_Filter< T >::OCC_BIT, Aleph::Quotient_Filter< T >::rem_mask(), Aleph::Quotient_Filter< T >::SHFT_BIT, and Aleph::Quotient_Filter< T >::slots_.

Referenced by Aleph::Quotient_Filter< T >::do_insert().

◆ set_occ()

template<typename T >

void Aleph::Quotient_Filter< T >::set_occ	(	const size_t	i,
		const bool	v
	)

inlineprivatenoexcept

Definition at line 261 of file quotient-filter.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::OCC_BIT, and Aleph::Quotient_Filter< T >::slots_.

Referenced by Aleph::Quotient_Filter< T >::do_insert(), Aleph::Quotient_Filter< T >::remove(), Aleph::Quotient_Filter< T >::shift_elements_left(), and Aleph::Quotient_Filter< T >::shift_elements_right().

◆ set_rem()

template<typename T >

void Aleph::Quotient_Filter< T >::set_rem	(	const size_t	i,
		const uint64_t	rem
	)

inlineprivatenoexcept

Definition at line 290 of file quotient-filter.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::META_MASK, Aleph::Quotient_Filter< T >::rem_mask(), and Aleph::Quotient_Filter< T >::slots_.

◆ set_shft()

template<typename T >

void Aleph::Quotient_Filter< T >::set_shft	(	const size_t	i,
		const bool	v
	)

inlineprivatenoexcept

Definition at line 277 of file quotient-filter.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::SHFT_BIT, and Aleph::Quotient_Filter< T >::slots_.

Referenced by Aleph::Quotient_Filter< T >::shift_elements_left(), and Aleph::Quotient_Filter< T >::shift_elements_right().

◆ shift_elements_left()

template<typename T >

void Aleph::Quotient_Filter< T >::shift_elements_left ( size_t pos )

inlineprivatenoexcept

Definition at line 453 of file quotient-filter.H.

References Aleph::and, Aleph::Quotient_Filter< T >::clear_element(), Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::get_cont(), Aleph::Quotient_Filter< T >::get_occ(), Aleph::Quotient_Filter< T >::get_shft(), Aleph::Quotient_Filter< T >::has_element(), Aleph::Quotient_Filter< T >::incr(), Aleph::Quotient_Filter< T >::set_occ(), Aleph::Quotient_Filter< T >::set_shft(), and Aleph::Quotient_Filter< T >::slots_.

Referenced by Aleph::Quotient_Filter< T >::remove().

◆ shift_elements_right()

template<typename T >

void Aleph::Quotient_Filter< T >::shift_elements_right	(	size_t	pos,
		size_t	empty
	)

inlineprivatenoexcept

Definition at line 365 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::decr(), Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::get_occ(), Aleph::Quotient_Filter< T >::set_occ(), Aleph::Quotient_Filter< T >::set_shft(), and Aleph::Quotient_Filter< T >::slots_.

Referenced by Aleph::Quotient_Filter< T >::do_insert().

◆ size()

template<typename T >

size_t Aleph::Quotient_Filter< T >::size ( ) const

inlinenoexcept

Number of elements.

O(1).

Definition at line 609 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::num_elems_.

Referenced by demo_merge(), and TEST().

◆ slot_empty()

template<typename T >

bool Aleph::Quotient_Filter< T >::slot_empty ( size_t i ) const

inlineprivatenoexcept

Definition at line 178 of file quotient-filter.H.

References Aleph::Quotient_Filter< T >::slots_.

Referenced by Aleph::Quotient_Filter< T >::do_insert().

◆ swap()

template<typename T >

void Aleph::Quotient_Filter< T >::swap ( Quotient_Filter< T > & other )

inlinenoexcept

Swap in O(1).

Definition at line 708 of file quotient-filter.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::num_elems_, Aleph::Quotient_Filter< T >::num_slots_, Aleph::Quotient_Filter< T >::q_, Aleph::Quotient_Filter< T >::r_, Aleph::Quotient_Filter< T >::seed_, Aleph::Quotient_Filter< T >::slots_, and Aleph::Array< T >::swap().

Referenced by TEST().

Member Data Documentation

◆ CONT_BIT

template<typename T >

constexpr uint64_t Aleph::Quotient_Filter< T >::CONT_BIT = 1ULL << 1

staticconstexprprivate

Definition at line 153 of file quotient-filter.H.

Referenced by Aleph::Quotient_Filter< T >::get_cont(), Aleph::Quotient_Filter< T >::set_cont(), and Aleph::Quotient_Filter< T >::set_element().

◆ META_MASK

template<typename T >

constexpr uint64_t Aleph::Quotient_Filter< T >::META_MASK = 0x7ULL

staticconstexprprivate

Definition at line 155 of file quotient-filter.H.

Referenced by Aleph::Quotient_Filter< T >::has_element(), and Aleph::Quotient_Filter< T >::set_rem().

◆ num_elems_

template<typename T >

size_t Aleph::Quotient_Filter< T >::num_elems_

private

Definition at line 142 of file quotient-filter.H.

Referenced by Aleph::Quotient_Filter< T >::clear(), Aleph::Quotient_Filter< T >::do_insert(), Aleph::Quotient_Filter< T >::insert(), Aleph::Quotient_Filter< T >::is_empty(), Aleph::Quotient_Filter< T >::load_factor(), Aleph::Quotient_Filter< T >::merge(), Aleph::Quotient_Filter< T >::remove(), Aleph::Quotient_Filter< T >::size(), and Aleph::Quotient_Filter< T >::swap().

◆ num_slots_

template<typename T >

size_t Aleph::Quotient_Filter< T >::num_slots_

private

Definition at line 141 of file quotient-filter.H.

◆ OCC_BIT

template<typename T >

constexpr uint64_t Aleph::Quotient_Filter< T >::OCC_BIT = 1ULL << 0

staticconstexprprivate

Definition at line 152 of file quotient-filter.H.

Referenced by Aleph::Quotient_Filter< T >::clear_element(), Aleph::Quotient_Filter< T >::do_insert(), Aleph::Quotient_Filter< T >::get_occ(), Aleph::Quotient_Filter< T >::set_element(), and Aleph::Quotient_Filter< T >::set_occ().

◆ q_

template<typename T >

uint8_t Aleph::Quotient_Filter< T >::q_

private

Definition at line 139 of file quotient-filter.H.

Referenced by Aleph::Quotient_Filter< T >::fingerprint(), Aleph::Quotient_Filter< T >::merge(), Aleph::Quotient_Filter< T >::q(), and Aleph::Quotient_Filter< T >::swap().

◆ r_

template<typename T >

uint8_t Aleph::Quotient_Filter< T >::r_

private

Definition at line 140 of file quotient-filter.H.

Referenced by Aleph::Quotient_Filter< T >::false_positive_rate(), Aleph::Quotient_Filter< T >::merge(), Aleph::Quotient_Filter< T >::r(), Aleph::Quotient_Filter< T >::rem_mask(), and Aleph::Quotient_Filter< T >::swap().

◆ seed_

template<typename T >

uint32_t Aleph::Quotient_Filter< T >::seed_

private

Definition at line 143 of file quotient-filter.H.

Referenced by Aleph::Quotient_Filter< T >::fingerprint(), Aleph::Quotient_Filter< T >::merge(), Aleph::Quotient_Filter< T >::seed(), and Aleph::Quotient_Filter< T >::swap().

◆ SHFT_BIT

template<typename T >

constexpr uint64_t Aleph::Quotient_Filter< T >::SHFT_BIT = 1ULL << 2

staticconstexprprivate

Definition at line 154 of file quotient-filter.H.

Referenced by Aleph::Quotient_Filter< T >::get_shft(), Aleph::Quotient_Filter< T >::set_element(), and Aleph::Quotient_Filter< T >::set_shft().

◆ slots_

template<typename T >

Array<uint64_t> Aleph::Quotient_Filter< T >::slots_

private

Definition at line 150 of file quotient-filter.H.

The documentation for this class was generated from the following file:

quotient-filter.H

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Enumeration Documentation

◆ Insert_Result

Constructor & Destructor Documentation

◆ Quotient_Filter()

Member Function Documentation

◆ capacity()

◆ clear()

◆ clear_element()

◆ contains()

◆ decr()

◆ do_insert()

◆ estimate()

◆ false_positive_rate()

◆ find_first_unused()

◆ find_run_start()

◆ fingerprint()

◆ from_capacity()

◆ get_cont()

◆ get_occ()

◆ get_rem()

◆ get_shft()

◆ has_element()

◆ incr()

◆ insert()

◆ is_empty()

◆ is_run_start()

◆ load_factor()

◆ memory_usage()

◆ merge()

◆ q()

◆ r()

◆ rem_mask()

◆ remove()

◆ seed()

◆ set_cont()

◆ set_element()

◆ set_occ()

◆ set_rem()

◆ set_shft()

◆ shift_elements_left()

◆ shift_elements_right()

◆ size()

◆ slot_empty()

◆ swap()

Member Data Documentation

◆ CONT_BIT

◆ META_MASK

◆ num_elems_

◆ num_slots_

◆ OCC_BIT

◆ q_

◆ r_

◆ seed_

◆ SHFT_BIT

◆ slots_