Memory-optimized Cuckoo Filter with bit-packed fingerprints. More...

#include <compact-cuckoo-filter.H>

Collaboration diagram for Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >:

Classes
struct	Bucket

struct	Victim
	Victim entry: a fingerprint that was displaced during a failed insert. More...

Public Member Functions
	Compact_Cuckoo_Filter (size_t capacity, const std::optional< std::uint32_t > seed=std::nullopt)
	Construct a Compact Cuckoo Filter with a given capacity.

size_t	size () const noexcept
	Return the number of items currently in the filter.

bool	empty () const noexcept
	Return whether the filter contains no items.

bool	is_empty () const noexcept
	Synonym for empty() in traditional Aleph style.

size_t	capacity () const noexcept
	Return the total number of fingerprint slots (including stash).

double	load_factor () const noexcept
	Return the load factor of the filter (relative to capacity()).

size_t	memory_usage () const noexcept
	Return approximate memory usage in bytes.

bool	insert (const T &item)
	Insert an item into the filter.

bool	append (const T &item)
	Alias for insert().

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

bool	remove (const T &item)
	Remove an item from the filter.

void	clear ()
	Clear the filter.

Private Types
using	Fingerprint = uint32_t

Private Member Functions
Fingerprint	get_fingerprint (const T &item) const

size_t	index_hash (const T &item) const noexcept

size_t	alt_index (const size_t i, Fingerprint fp) const

Private Attributes
Aleph::Array< Bucket >	buckets

size_t	num_items = 0

size_t	num_buckets = 0

size_t	bucket_mask = 0

std::mt19937	rng_

Victim	stash_ [stash_size] = {}

size_t	stash_count_ = 0

Static Private Attributes
static constexpr size_t	max_kicks = 500

static constexpr size_t	stash_size = 4

static constexpr double	kTargetLoad = 0.9

static constexpr Fingerprint	fp_mask = (FingerprintBits == 32) ? 0xFFFFFFFF : (1U << FingerprintBits) - 1

Detailed Description

template<typename T, size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>
class Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >

Memory-optimized Cuckoo Filter with bit-packed fingerprints.

Note: Not thread-safe. Concurrent reads (contains / size / etc.) are safe; any concurrent write (insert / remove / clear) requires external synchronisation.

Definition at line 94 of file compact-cuckoo-filter.H.

Member Typedef Documentation

◆ Fingerprint

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

using Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::Fingerprint = uint32_t

private

Definition at line 99 of file compact-cuckoo-filter.H.

Constructor & Destructor Documentation

◆ Compact_Cuckoo_Filter()

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::Compact_Cuckoo_Filter	(	size_t	capacity,
		const std::optional< std::uint32_t >	seed = `std::nullopt`
	)

inlineexplicit

Construct a Compact Cuckoo Filter with a given capacity.

Parameters

capacity	Minimum number of items to support.
seed	Optional RNG seed for deterministic kick sequences. Pass a fixed value in tests to eliminate flakiness. Defaults to a non-deterministic device seed.

Exceptions

std::bad_alloc if memory allocation fails.

Note: O(capacity / EntriesPerBucket).

Definition at line 236 of file compact-cuckoo-filter.H.

References Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::bucket_mask, Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::buckets, Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::capacity(), Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::kTargetLoad, Aleph::next_power_of_2(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::num_buckets.

Member Function Documentation

◆ alt_index()

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

size_t Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::alt_index	(	const size_t	i,
		Fingerprint	fp
	)		const

inlineprivate

Definition at line 218 of file compact-cuckoo-filter.H.

References Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::bucket_mask, and Aleph::murmur3hash().

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::contains(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::insert(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::remove().

◆ append()

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

bool Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::append ( const T & item )

inline

Alias for insert().

Parameters

item	Item to insert.

Returns: true if insertion succeeded, false if filter is full.

Exceptions

none.

Definition at line 379 of file compact-cuckoo-filter.H.

References Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::insert().

◆ capacity()

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

size_t Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::capacity ( ) const

inlinenoexcept

Return the total number of fingerprint slots (including stash).

Returns: Total slot count.

Exceptions

none.

Definition at line 281 of file compact-cuckoo-filter.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::num_buckets, and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::stash_size.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::Compact_Cuckoo_Filter(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::load_factor().

◆ clear()

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

void Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::clear ( )

inline

Clear the filter.

Exceptions

none.

Note: O(num_buckets * EntriesPerBucket).

Definition at line 442 of file compact-cuckoo-filter.H.

References Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::buckets, Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::num_buckets, Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::num_items, and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::stash_count_.

◆ contains()

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

bool Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::contains ( const T & item ) const

inline

Test membership.

Parameters

item	Item to check.

Returns: true if item is likely present, false if definitely not.

Exceptions

none.

Note: O(1).

Definition at line 391 of file compact-cuckoo-filter.H.

References Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::alt_index(), Aleph::and, Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::buckets, Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::contains(), Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::get_fingerprint(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::index_hash(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::stash_, and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::stash_count_.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::contains().

◆ empty()

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

bool Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::empty ( ) const

inlinenoexcept

Return whether the filter contains no items.

Returns: true if the filter has no items.

Exceptions

none.

Definition at line 263 of file compact-cuckoo-filter.H.

References Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::num_items.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::is_empty().

◆ get_fingerprint()

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

Fingerprint Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::get_fingerprint ( const T & item ) const

inlineprivate

Definition at line 205 of file compact-cuckoo-filter.H.

References Aleph::dft_hash_fct(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::fp_mask.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::contains(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::insert(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::remove().

◆ index_hash()

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

size_t Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::index_hash ( const T & item ) const

inlineprivatenoexcept

Definition at line 213 of file compact-cuckoo-filter.H.

References Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::bucket_mask, and Aleph::dft_hash_fct().

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::contains(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::insert(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::remove().

◆ insert()

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

bool Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::insert ( const T & item )

inline

Insert an item into the filter.

Parameters

item	Item to insert.

Returns: true if insertion succeeded, false if filter is full.

Exceptions

none.

Note: Amortised O(1).

Definition at line 314 of file compact-cuckoo-filter.H.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::append(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::insert().

◆ is_empty()

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

bool Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::is_empty ( ) const

inlinenoexcept

Synonym for empty() in traditional Aleph style.

Returns: true if the filter has no items.

Exceptions

none.

Definition at line 272 of file compact-cuckoo-filter.H.

References Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::empty().

◆ load_factor()

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

double Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::load_factor ( ) const

inlinenoexcept

Return the load factor of the filter (relative to capacity()).

Returns: Ratio of stored items to total slots.

Exceptions

none.

Definition at line 290 of file compact-cuckoo-filter.H.

References Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::capacity(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::num_items.

◆ memory_usage()

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

size_t Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::memory_usage ( ) const

inlinenoexcept

Return approximate memory usage in bytes.

Returns: Byte count used by the bucket array.

Exceptions

none.

Definition at line 299 of file compact-cuckoo-filter.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::num_buckets.

Referenced by example_custom_fingerprints().

◆ remove()

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

bool Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::remove ( const T & item )

inline

Remove an item from the filter.

Parameters

item	Item to remove.

Returns: true if an instance of the item was removed.

Exceptions

none.

Note: O(1).

Definition at line 414 of file compact-cuckoo-filter.H.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::remove().

◆ size()

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

size_t Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::size ( ) const

inlinenoexcept

Return the number of items currently in the filter.

Returns: Current item count.

Exceptions

none.

Definition at line 254 of file compact-cuckoo-filter.H.

References Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::num_items.

Member Data Documentation

◆ bucket_mask

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

size_t Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::bucket_mask = 0

private

Definition at line 193 of file compact-cuckoo-filter.H.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::Compact_Cuckoo_Filter(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::alt_index(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::index_hash().

◆ buckets

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

Aleph::Array<Bucket> Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::buckets

private

Definition at line 190 of file compact-cuckoo-filter.H.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::Compact_Cuckoo_Filter(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::clear(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::contains(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::insert(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::remove().

◆ fp_mask

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

constexpr Fingerprint Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::fp_mask = (FingerprintBits == 32) ? 0xFFFFFFFF : (1U << FingerprintBits) - 1

staticconstexprprivate

Definition at line 203 of file compact-cuckoo-filter.H.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::get_fingerprint().

◆ kTargetLoad

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

constexpr double Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::kTargetLoad = 0.9

staticconstexprprivate

Definition at line 198 of file compact-cuckoo-filter.H.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::Compact_Cuckoo_Filter().

◆ max_kicks

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

constexpr size_t Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::max_kicks = 500

staticconstexprprivate

Definition at line 196 of file compact-cuckoo-filter.H.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::insert().

◆ num_buckets

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

size_t Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::num_buckets = 0

private

Definition at line 192 of file compact-cuckoo-filter.H.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::Compact_Cuckoo_Filter(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::capacity(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::clear(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::memory_usage().

◆ num_items

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

size_t Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::num_items = 0

private

Definition at line 191 of file compact-cuckoo-filter.H.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::clear(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::empty(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::insert(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::load_factor(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::remove(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::size().

◆ rng_

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

std::mt19937 Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::rng_

mutableprivate

Definition at line 194 of file compact-cuckoo-filter.H.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::insert().

◆ stash_

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

Victim Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::stash_[stash_size] = {}

private

Definition at line 199 of file compact-cuckoo-filter.H.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::contains(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::insert(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::remove().

◆ stash_count_

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

size_t Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::stash_count_ = 0

private

Definition at line 200 of file compact-cuckoo-filter.H.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::clear(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::contains(), Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::insert(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::remove().

◆ stash_size

template<typename T , size_t FingerprintBits = 8, size_t EntriesPerBucket = 4>

constexpr size_t Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::stash_size = 4

staticconstexprprivate

Definition at line 197 of file compact-cuckoo-filter.H.

Referenced by Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::capacity(), and Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::insert().

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

compact-cuckoo-filter.H

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ Fingerprint

Constructor & Destructor Documentation

◆ Compact_Cuckoo_Filter()

Member Function Documentation

◆ alt_index()

◆ append()

◆ capacity()

◆ clear()

◆ contains()

◆ empty()

◆ get_fingerprint()

◆ index_hash()

◆ insert()

◆ is_empty()

◆ load_factor()

◆ memory_usage()

◆ remove()

◆ size()

Member Data Documentation

◆ bucket_mask

◆ buckets

◆ fp_mask

◆ kTargetLoad

◆ max_kicks

◆ num_buckets

◆ num_items

◆ rng_

◆ stash_

◆ stash_count_

◆ stash_size