Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Public Member Functions | Static Public Member Functions | Private Member Functions | Private Attributes | List of all members
Aleph::Compact_Quotient_Filter< T > Class Template Reference

Memory-optimized quotient filter with bit-packed slots. More...

#include <compact-quotient-filter.H>

Collaboration diagram for Aleph::Compact_Quotient_Filter< T >:
[legend]

Public Member Functions

 Compact_Quotient_Filter (uint8_t q, uint8_t r, uint32_t seed=0x5F3759DF)
 Construct a compact quotient filter.
 
Compact_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 Compact_Quotient_Filter &other)
 Merge another filter (same q, r, seed).
 
void swap (Compact_Quotient_Filter &other) noexcept
 Swap in O(1).
 

Static Public Member Functions

static Compact_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 Member Functions

size_t bits_per_slot () const noexcept
 
size_t slot_offset (const size_t i) const noexcept
 
uint64_t rem_mask () const noexcept
 
bool get_bit_at (const size_t slot, const size_t bit_idx) const noexcept
 
void set_bit_at (const size_t slot, const size_t bit_idx, const bool v) noexcept
 
bool get_occ (const size_t i) const noexcept
 
bool get_cont (const size_t i) const noexcept
 
bool get_shft (const size_t i) const noexcept
 
bool slot_empty (const 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 (const size_t fq) const noexcept
 
size_t find_first_unused (const size_t start) const noexcept
 
void shift_elements_right (const size_t pos, size_t empty) noexcept
 
bool do_insert (const size_t fq, const uint64_t fr)
 
void shift_elements_left (const size_t pos) noexcept
 

Private Attributes

uint8_t q_
 
uint8_t r_
 
size_t num_slots_
 
size_t num_elems_
 
uint32_t seed_
 
BitArray bits_
 

Detailed Description

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

Memory-optimized quotient filter with bit-packed slots.

Template Parameters
TElement type. Must be hashable via murmur3hash(T, seed).

Definition at line 85 of file compact-quotient-filter.H.

Constructor & Destructor Documentation

◆ Compact_Quotient_Filter()

template<typename T >
Aleph::Compact_Quotient_Filter< T >::Compact_Quotient_Filter ( uint8_t  q,
uint8_t  r,
uint32_t  seed = 0x5F3759DF 
)
inline

Construct a compact quotient filter.

Parameters
[in]qNumber of quotient bits (2^q slots). Must be in [1, 32].
[in]rRemainder bits per slot (FP rate ~ 2^{-r}). Must be in [1, 60].
[in]seedHash seed (default: 0x5F3759DF).
Exceptions
std::domain_errorif q or r are out of range, or q + r > 64.

Definition at line 360 of file compact-quotient-filter.H.

References ah_domain_error_if, Aleph::Compact_Quotient_Filter< T >::bits_, Aleph::Compact_Quotient_Filter< T >::bits_per_slot(), Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::num_slots_, Aleph::Compact_Quotient_Filter< T >::q(), Aleph::Compact_Quotient_Filter< T >::r(), and Aleph::BitArray::reserve().

Member Function Documentation

◆ bits_per_slot()

template<typename T >
size_t Aleph::Compact_Quotient_Filter< T >::bits_per_slot ( ) const
inlineprivatenoexcept

Definition at line 101 of file compact-quotient-filter.H.

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

Referenced by Aleph::Compact_Quotient_Filter< T >::Compact_Quotient_Filter(), Aleph::Compact_Quotient_Filter< T >::clear(), Aleph::Compact_Quotient_Filter< T >::memory_usage(), Aleph::Compact_Quotient_Filter< T >::slot_empty(), and Aleph::Compact_Quotient_Filter< T >::slot_offset().

◆ capacity()

template<typename T >
size_t Aleph::Compact_Quotient_Filter< T >::capacity ( ) const
inlinenoexcept

Number of slots (2^q).

O(1).

Definition at line 501 of file compact-quotient-filter.H.

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

◆ clear()

template<typename T >
void Aleph::Compact_Quotient_Filter< T >::clear ( )
inlinenoexcept

Remove all elements.

O(2^q).

Definition at line 549 of file compact-quotient-filter.H.

References Aleph::Compact_Quotient_Filter< T >::bits_, Aleph::Compact_Quotient_Filter< T >::bits_per_slot(), Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::num_elems_, Aleph::Compact_Quotient_Filter< T >::num_slots_, and Aleph::BitArray::write_bit().

◆ clear_element()

template<typename T >
void Aleph::Compact_Quotient_Filter< T >::clear_element ( const size_t  i)
inlineprivatenoexcept

Definition at line 201 of file compact-quotient-filter.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::get_occ(), Aleph::Compact_Quotient_Filter< T >::set_cont(), Aleph::Compact_Quotient_Filter< T >::set_occ(), Aleph::Compact_Quotient_Filter< T >::set_rem(), and Aleph::Compact_Quotient_Filter< T >::set_shft().

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

◆ contains()

template<typename T >
bool Aleph::Compact_Quotient_Filter< T >::contains ( const T &  item) const
inlinenoexcept

Test membership.

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

Definition at line 432 of file compact-quotient-filter.H.

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

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

◆ decr()

template<typename T >
size_t Aleph::Compact_Quotient_Filter< T >::decr ( const size_t  i) const
inlineprivatenoexcept

Definition at line 215 of file compact-quotient-filter.H.

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

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

◆ do_insert()

template<typename T >
bool Aleph::Compact_Quotient_Filter< T >::do_insert ( const size_t  fq,
const uint64_t  fr 
)
inlineprivate

Definition at line 273 of file compact-quotient-filter.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::find_first_unused(), Aleph::Compact_Quotient_Filter< T >::find_run_start(), Aleph::Compact_Quotient_Filter< T >::get_cont(), Aleph::Compact_Quotient_Filter< T >::get_occ(), Aleph::Compact_Quotient_Filter< T >::get_rem(), Aleph::Compact_Quotient_Filter< T >::incr(), Aleph::Compact_Quotient_Filter< T >::num_elems_, Aleph::Compact_Quotient_Filter< T >::num_slots_, Aleph::Compact_Quotient_Filter< T >::set_cont(), Aleph::Compact_Quotient_Filter< T >::set_element(), Aleph::Compact_Quotient_Filter< T >::set_occ(), Aleph::Compact_Quotient_Filter< T >::set_rem(), Aleph::Compact_Quotient_Filter< T >::shift_elements_right(), and Aleph::Compact_Quotient_Filter< T >::slot_empty().

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

◆ estimate()

template<typename T >
static std::pair< uint8_t, uint8_t > Aleph::Compact_Quotient_Filter< T >::estimate ( size_t  n,
double  fp_rate 
)
inlinestatic

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

Definition at line 580 of file compact-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::Compact_Quotient_Filter< T >::false_positive_rate ( ) const
inlinenoexcept

Theoretical FP probability ~ 2^{-r}.

Definition at line 531 of file compact-quotient-filter.H.

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

◆ find_first_unused()

template<typename T >
size_t Aleph::Compact_Quotient_Filter< T >::find_first_unused ( const size_t  start) const
inlineprivatenoexcept

Definition at line 248 of file compact-quotient-filter.H.

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

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

◆ find_run_start()

template<typename T >
size_t Aleph::Compact_Quotient_Filter< T >::find_run_start ( const size_t  fq) const
inlineprivatenoexcept

Definition at line 228 of file compact-quotient-filter.H.

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

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

◆ fingerprint()

template<typename T >
std::pair< size_t, uint64_t > Aleph::Compact_Quotient_Filter< T >::fingerprint ( const T &  item) const
inlineprivate

Definition at line 220 of file compact-quotient-filter.H.

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

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

◆ from_capacity()

template<typename T >
static Compact_Quotient_Filter Aleph::Compact_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_nExpected number of elements.
[in]fp_rateTarget false positive probability.
[in]seedHash seed.
Exceptions
std::domain_errorif expected_n == 0, fp_rate not in (0,1), or the requested (expected_n, fp_rate) cannot be represented within the supported parameter ranges.

Definition at line 384 of file compact-quotient-filter.H.

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

Referenced by example_from_capacity(), example_url_deduplication(), and TEST().

◆ get_bit_at()

template<typename T >
bool Aleph::Compact_Quotient_Filter< T >::get_bit_at ( const size_t  slot,
const size_t  bit_idx 
) const
inlineprivatenoexcept

Definition at line 116 of file compact-quotient-filter.H.

References Aleph::Compact_Quotient_Filter< T >::bits_, Aleph::divide_and_conquer_partition_dp(), Aleph::BitArray::read_bit(), and Aleph::Compact_Quotient_Filter< T >::slot_offset().

Referenced by Aleph::Compact_Quotient_Filter< T >::get_cont(), Aleph::Compact_Quotient_Filter< T >::get_occ(), and Aleph::Compact_Quotient_Filter< T >::get_shft().

◆ get_cont()

template<typename T >
bool Aleph::Compact_Quotient_Filter< T >::get_cont ( const size_t  i) const
inlineprivatenoexcept

Definition at line 131 of file compact-quotient-filter.H.

References Aleph::Compact_Quotient_Filter< T >::get_bit_at().

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

◆ get_occ()

template<typename T >
bool Aleph::Compact_Quotient_Filter< T >::get_occ ( const size_t  i) const
inlineprivatenoexcept

Definition at line 126 of file compact-quotient-filter.H.

References Aleph::Compact_Quotient_Filter< T >::get_bit_at().

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

◆ get_rem()

template<typename T >
uint64_t Aleph::Compact_Quotient_Filter< T >::get_rem ( const size_t  i) const
inlineprivatenoexcept

Definition at line 175 of file compact-quotient-filter.H.

References Aleph::Compact_Quotient_Filter< T >::bits_, Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::r_, Aleph::BitArray::read_bit(), and Aleph::Compact_Quotient_Filter< T >::slot_offset().

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

◆ get_shft()

template<typename T >
bool Aleph::Compact_Quotient_Filter< T >::get_shft ( const size_t  i) const
inlineprivatenoexcept

Definition at line 136 of file compact-quotient-filter.H.

References Aleph::Compact_Quotient_Filter< T >::get_bit_at().

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

◆ has_element()

template<typename T >
bool Aleph::Compact_Quotient_Filter< T >::has_element ( const size_t  i) const
inlineprivatenoexcept

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

References Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::get_cont(), Aleph::Compact_Quotient_Filter< T >::get_occ(), and Aleph::Compact_Quotient_Filter< T >::get_shft().

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

◆ incr()

template<typename T >
size_t Aleph::Compact_Quotient_Filter< T >::incr ( const size_t  i) const
inlineprivatenoexcept

Definition at line 210 of file compact-quotient-filter.H.

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

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

◆ insert()

template<typename T >
Compact_Quotient_Filter & Aleph::Compact_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_errorif the filter is full.

Definition at line 418 of file compact-quotient-filter.H.

References ah_overflow_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::do_insert(), Aleph::Compact_Quotient_Filter< T >::fingerprint(), Aleph::Compact_Quotient_Filter< T >::num_elems_, and Aleph::Compact_Quotient_Filter< T >::num_slots_.

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

◆ is_empty()

template<typename T >
bool Aleph::Compact_Quotient_Filter< T >::is_empty ( ) const
inlinenoexcept

True if empty.

O(1).

Definition at line 513 of file compact-quotient-filter.H.

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

◆ is_run_start()

template<typename T >
bool Aleph::Compact_Quotient_Filter< T >::is_run_start ( const size_t  i) const
inlineprivatenoexcept

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

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

◆ load_factor()

template<typename T >
double Aleph::Compact_Quotient_Filter< T >::load_factor ( ) const
inlinenoexcept

Current load factor.

O(1).

Definition at line 507 of file compact-quotient-filter.H.

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

◆ memory_usage()

template<typename T >
size_t Aleph::Compact_Quotient_Filter< T >::memory_usage ( ) const
inlinenoexcept

Memory usage in bytes.

Definition at line 543 of file compact-quotient-filter.H.

References Aleph::Compact_Quotient_Filter< T >::bits_per_slot(), and Aleph::Compact_Quotient_Filter< T >::num_slots_.

◆ merge()

template<typename T >
void Aleph::Compact_Quotient_Filter< T >::merge ( const Compact_Quotient_Filter< T > &  other)
inline

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

O(2^q).

Exceptions
std::domain_erroron parameter mismatch.

Definition at line 560 of file compact-quotient-filter.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::do_insert(), Aleph::Compact_Quotient_Filter< T >::q_, Aleph::Compact_Quotient_Filter< T >::r_, and Aleph::Compact_Quotient_Filter< T >::seed_.

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

◆ q()

template<typename T >
uint8_t Aleph::Compact_Quotient_Filter< T >::q ( ) const
inlinenoexcept

Quotient bits.

Definition at line 519 of file compact-quotient-filter.H.

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

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

◆ r()

template<typename T >
uint8_t Aleph::Compact_Quotient_Filter< T >::r ( ) const
inlinenoexcept

Remainder bits.

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

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

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

◆ rem_mask()

template<typename T >
uint64_t Aleph::Compact_Quotient_Filter< T >::rem_mask ( ) const
inlineprivatenoexcept

Definition at line 111 of file compact-quotient-filter.H.

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

Referenced by Aleph::Compact_Quotient_Filter< T >::fingerprint().

◆ remove()

template<typename T >
bool Aleph::Compact_Quotient_Filter< T >::remove ( const T &  item)
inlinenoexcept

Remove an element.

Returns
true if the fingerprint was found and removed.

Definition at line 457 of file compact-quotient-filter.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::find_run_start(), Aleph::Compact_Quotient_Filter< T >::fingerprint(), Aleph::Compact_Quotient_Filter< T >::get_cont(), Aleph::Compact_Quotient_Filter< T >::get_occ(), Aleph::Compact_Quotient_Filter< T >::get_rem(), Aleph::Compact_Quotient_Filter< T >::has_element(), Aleph::Compact_Quotient_Filter< T >::incr(), Aleph::Compact_Quotient_Filter< T >::num_elems_, Aleph::Compact_Quotient_Filter< T >::set_cont(), Aleph::Compact_Quotient_Filter< T >::set_occ(), and Aleph::Compact_Quotient_Filter< T >::shift_elements_left().

◆ seed()

template<typename T >
uint32_t Aleph::Compact_Quotient_Filter< T >::seed ( ) const
inlinenoexcept

Hash seed.

Definition at line 537 of file compact-quotient-filter.H.

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

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

◆ set_bit_at()

template<typename T >
void Aleph::Compact_Quotient_Filter< T >::set_bit_at ( const size_t  slot,
const size_t  bit_idx,
const bool  v 
)
inlineprivatenoexcept

Definition at line 121 of file compact-quotient-filter.H.

References Aleph::Compact_Quotient_Filter< T >::bits_, Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::slot_offset(), and Aleph::BitArray::write_bit().

Referenced by Aleph::Compact_Quotient_Filter< T >::set_cont(), Aleph::Compact_Quotient_Filter< T >::set_occ(), and Aleph::Compact_Quotient_Filter< T >::set_shft().

◆ set_cont()

template<typename T >
void Aleph::Compact_Quotient_Filter< T >::set_cont ( const size_t  i,
const bool  v 
)
inlineprivatenoexcept

Definition at line 165 of file compact-quotient-filter.H.

References Aleph::Compact_Quotient_Filter< T >::set_bit_at().

Referenced by Aleph::Compact_Quotient_Filter< T >::clear_element(), Aleph::Compact_Quotient_Filter< T >::do_insert(), Aleph::Compact_Quotient_Filter< T >::remove(), and Aleph::Compact_Quotient_Filter< T >::set_element().

◆ set_element()

template<typename T >
void Aleph::Compact_Quotient_Filter< T >::set_element ( const size_t  i,
const bool  cont,
const bool  shft,
const uint64_t  rem 
)
inlineprivatenoexcept

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

References Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::get_occ(), Aleph::Compact_Quotient_Filter< T >::set_cont(), Aleph::Compact_Quotient_Filter< T >::set_occ(), Aleph::Compact_Quotient_Filter< T >::set_rem(), and Aleph::Compact_Quotient_Filter< T >::set_shft().

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

◆ set_occ()

template<typename T >
void Aleph::Compact_Quotient_Filter< T >::set_occ ( const size_t  i,
const bool  v 
)
inlineprivatenoexcept

Definition at line 160 of file compact-quotient-filter.H.

References Aleph::Compact_Quotient_Filter< T >::set_bit_at().

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

◆ set_rem()

template<typename T >
void Aleph::Compact_Quotient_Filter< T >::set_rem ( const size_t  i,
const uint64_t  rem 
)
inlineprivatenoexcept

Definition at line 185 of file compact-quotient-filter.H.

References Aleph::Compact_Quotient_Filter< T >::bits_, Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::r_, Aleph::Compact_Quotient_Filter< T >::slot_offset(), and Aleph::BitArray::write_bit().

Referenced by Aleph::Compact_Quotient_Filter< T >::clear_element(), Aleph::Compact_Quotient_Filter< T >::do_insert(), and Aleph::Compact_Quotient_Filter< T >::set_element().

◆ set_shft()

template<typename T >
void Aleph::Compact_Quotient_Filter< T >::set_shft ( const size_t  i,
const bool  v 
)
inlineprivatenoexcept

Definition at line 170 of file compact-quotient-filter.H.

References Aleph::Compact_Quotient_Filter< T >::set_bit_at().

Referenced by Aleph::Compact_Quotient_Filter< T >::clear_element(), Aleph::Compact_Quotient_Filter< T >::set_element(), and Aleph::Compact_Quotient_Filter< T >::shift_elements_left().

◆ shift_elements_left()

template<typename T >
void Aleph::Compact_Quotient_Filter< T >::shift_elements_left ( const size_t  pos)
inlineprivatenoexcept

Definition at line 326 of file compact-quotient-filter.H.

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

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

◆ shift_elements_right()

template<typename T >
void Aleph::Compact_Quotient_Filter< T >::shift_elements_right ( const size_t  pos,
size_t  empty 
)
inlineprivatenoexcept

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

References Aleph::Compact_Quotient_Filter< T >::decr(), Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::get_cont(), Aleph::Compact_Quotient_Filter< T >::get_occ(), Aleph::Compact_Quotient_Filter< T >::get_rem(), Aleph::Compact_Quotient_Filter< T >::set_element(), and Aleph::Compact_Quotient_Filter< T >::set_occ().

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

◆ size()

template<typename T >
size_t Aleph::Compact_Quotient_Filter< T >::size ( ) const
inlinenoexcept

Number of elements.

O(1).

Definition at line 495 of file compact-quotient-filter.H.

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

◆ slot_empty()

template<typename T >
bool Aleph::Compact_Quotient_Filter< T >::slot_empty ( const size_t  i) const
inlineprivatenoexcept

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

References Aleph::Compact_Quotient_Filter< T >::bits_, Aleph::Compact_Quotient_Filter< T >::bits_per_slot(), Aleph::divide_and_conquer_partition_dp(), Aleph::BitArray::read_bit(), and Aleph::Compact_Quotient_Filter< T >::slot_offset().

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

◆ slot_offset()

template<typename T >
size_t Aleph::Compact_Quotient_Filter< T >::slot_offset ( const size_t  i) const
inlineprivatenoexcept

Definition at line 106 of file compact-quotient-filter.H.

References Aleph::Compact_Quotient_Filter< T >::bits_per_slot().

Referenced by Aleph::Compact_Quotient_Filter< T >::get_bit_at(), Aleph::Compact_Quotient_Filter< T >::get_rem(), Aleph::Compact_Quotient_Filter< T >::set_bit_at(), Aleph::Compact_Quotient_Filter< T >::set_rem(), and Aleph::Compact_Quotient_Filter< T >::slot_empty().

◆ swap()

template<typename T >
void Aleph::Compact_Quotient_Filter< T >::swap ( Compact_Quotient_Filter< T > &  other)
inlinenoexcept

Swap in O(1).

Definition at line 593 of file compact-quotient-filter.H.

References Aleph::Compact_Quotient_Filter< T >::bits_, Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::num_elems_, Aleph::Compact_Quotient_Filter< T >::num_slots_, Aleph::Compact_Quotient_Filter< T >::q_, Aleph::Compact_Quotient_Filter< T >::r_, Aleph::Compact_Quotient_Filter< T >::seed_, and Aleph::BitArray::swap().

Referenced by TEST().

Member Data Documentation

◆ bits_

template<typename T >
BitArray Aleph::Compact_Quotient_Filter< T >::bits_
private

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

Referenced by Aleph::Compact_Quotient_Filter< T >::Compact_Quotient_Filter(), Aleph::Compact_Quotient_Filter< T >::clear(), Aleph::Compact_Quotient_Filter< T >::get_bit_at(), Aleph::Compact_Quotient_Filter< T >::get_rem(), Aleph::Compact_Quotient_Filter< T >::set_bit_at(), Aleph::Compact_Quotient_Filter< T >::set_rem(), Aleph::Compact_Quotient_Filter< T >::slot_empty(), and Aleph::Compact_Quotient_Filter< T >::swap().

◆ num_elems_

template<typename T >
size_t Aleph::Compact_Quotient_Filter< T >::num_elems_
private

Definition at line 90 of file compact-quotient-filter.H.

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

◆ num_slots_

template<typename T >
size_t Aleph::Compact_Quotient_Filter< T >::num_slots_
private

Definition at line 89 of file compact-quotient-filter.H.

Referenced by Aleph::Compact_Quotient_Filter< T >::Compact_Quotient_Filter(), Aleph::Compact_Quotient_Filter< T >::capacity(), Aleph::Compact_Quotient_Filter< T >::clear(), Aleph::Compact_Quotient_Filter< T >::decr(), Aleph::Compact_Quotient_Filter< T >::do_insert(), Aleph::Compact_Quotient_Filter< T >::fingerprint(), Aleph::Compact_Quotient_Filter< T >::incr(), Aleph::Compact_Quotient_Filter< T >::insert(), Aleph::Compact_Quotient_Filter< T >::load_factor(), Aleph::Compact_Quotient_Filter< T >::memory_usage(), and Aleph::Compact_Quotient_Filter< T >::swap().

◆ q_

template<typename T >
uint8_t Aleph::Compact_Quotient_Filter< T >::q_
private

Definition at line 87 of file compact-quotient-filter.H.

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

◆ r_

template<typename T >
uint8_t Aleph::Compact_Quotient_Filter< T >::r_
private

Definition at line 88 of file compact-quotient-filter.H.

Referenced by Aleph::Compact_Quotient_Filter< T >::bits_per_slot(), Aleph::Compact_Quotient_Filter< T >::false_positive_rate(), Aleph::Compact_Quotient_Filter< T >::get_rem(), Aleph::Compact_Quotient_Filter< T >::merge(), Aleph::Compact_Quotient_Filter< T >::r(), Aleph::Compact_Quotient_Filter< T >::rem_mask(), Aleph::Compact_Quotient_Filter< T >::set_rem(), and Aleph::Compact_Quotient_Filter< T >::swap().

◆ seed_

template<typename T >
uint32_t Aleph::Compact_Quotient_Filter< T >::seed_
private

Definition at line 91 of file compact-quotient-filter.H.

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

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