Industrial-grade Cuckoo Filter implementation. More...

#include <cuckoo-filter.H>

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

Classes
struct	Bucket

struct	Victim
	Victim entry: a fingerprint displaced during a failed kick chain. More...

Public Member Functions
	Cuckoo_Filter (size_t capacity, std::optional< std::uint32_t > seed=std::nullopt)
	Construct a 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()).

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 (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::Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >

Industrial-grade Cuckoo Filter implementation.

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

Definition at line 98 of file cuckoo-filter.H.

Member Typedef Documentation

◆ Fingerprint

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

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

private

Definition at line 103 of file cuckoo-filter.H.

Constructor & Destructor Documentation

◆ Cuckoo_Filter()

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

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

inlineexplicit

Construct a 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 216 of file cuckoo-filter.H.

References Aleph::Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::bucket_mask, Aleph::Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::buckets, Aleph::Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::capacity(), Aleph::divide_and_conquer_partition_dp(), Aleph::Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::kTargetLoad, Aleph::next_power_of_2(), and Aleph::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::Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::alt_index	(	size_t	i,
		Fingerprint	fp
	)		const

inlineprivate

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

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

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

◆ append()

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

bool Aleph::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 348 of file cuckoo-filter.H.

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

◆ capacity()

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

size_t Aleph::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 262 of file cuckoo-filter.H.

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

Referenced by Aleph::Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::Cuckoo_Filter(), example_memory_optimization(), example_performance(), and Aleph::Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::load_factor().

◆ clear()

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

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

inline

Clear the filter.

Exceptions

none.

Note: O(num_buckets * EntriesPerBucket).

Definition at line 410 of file cuckoo-filter.H.

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

◆ contains()

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

bool Aleph::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 360 of file cuckoo-filter.H.

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

Referenced by Aleph::Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::contains(), example_performance(), TEST(), and TEST().

◆ empty()

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

bool Aleph::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 244 of file cuckoo-filter.H.

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

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

◆ get_fingerprint()

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

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

inlineprivate

Definition at line 185 of file cuckoo-filter.H.

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

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

◆ index_hash()

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

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

inlineprivatenoexcept

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

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

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

◆ insert()

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

bool Aleph::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 283 of file cuckoo-filter.H.

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

◆ is_empty()

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

bool Aleph::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 253 of file cuckoo-filter.H.

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

◆ load_factor()

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

double Aleph::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 271 of file cuckoo-filter.H.

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

◆ remove()

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

bool Aleph::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 383 of file cuckoo-filter.H.

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

◆ size()

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

size_t Aleph::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 235 of file cuckoo-filter.H.

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

Referenced by TEST(), and TEST().

Member Data Documentation

◆ bucket_mask

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

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

private

Definition at line 173 of file cuckoo-filter.H.

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

◆ buckets

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

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

private

Definition at line 170 of file cuckoo-filter.H.

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

◆ fp_mask

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

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

staticconstexprprivate

Definition at line 183 of file cuckoo-filter.H.

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

◆ kTargetLoad

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

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

staticconstexprprivate

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

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

◆ max_kicks

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

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

staticconstexprprivate

Definition at line 176 of file cuckoo-filter.H.

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

◆ num_buckets

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

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

private

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

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

◆ num_items

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

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

private

Definition at line 171 of file cuckoo-filter.H.

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

◆ rng_

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

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

mutableprivate

Definition at line 174 of file cuckoo-filter.H.

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

◆ stash_

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

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

private

Definition at line 179 of file cuckoo-filter.H.

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

◆ stash_count_

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

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

private

Definition at line 180 of file cuckoo-filter.H.

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

◆ stash_size

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

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

staticconstexprprivate

Definition at line 177 of file cuckoo-filter.H.

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

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

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

◆ Cuckoo_Filter()

Member Function Documentation

◆ alt_index()

◆ append()

◆ capacity()

◆ clear()

◆ contains()

◆ empty()

◆ get_fingerprint()

◆ index_hash()

◆ insert()

◆ is_empty()

◆ load_factor()

◆ remove()

◆ size()

Member Data Documentation

◆ bucket_mask

◆ buckets

◆ fp_mask

◆ kTargetLoad

◆ max_kicks

◆ num_buckets

◆ num_items

◆ rng_

◆ stash_

◆ stash_count_

◆ stash_size