Skip to content
charmOS docs

(Counting) Bloom Filter

include/structures/bloom.h View source View on GitHub

Structs

Section titled “Structs”

counting_bloom_filter

Section titled “counting_bloom_filter”
struct counting_bloom_filter (4 fields) source
§ uint8_t *counters
§ size_t num_counters
§ size_t num_hashes
§ size_t live_elements

Enums

Section titled “Enums”

bloom_remove_result

Section titled “bloom_remove_result”
enum bloom_remove_result (3 variants) source
§ BLOOM_REMOVE_OK = 0
§ BLOOM_REMOVE_NOT_FOUND = -1
§ BLOOM_REMOVE_SATURATED = -2

Functions

Section titled “Functions”

cbf_remove

Section titled “cbf_remove”
enum bloom_remove_result cbf_remove(
    struct counting_bloom_filter *cbf,
    const char *element
)
source

cbf_remove — remove an element (decrements k counters).

  BLOOM_REMOVE_OK — counters decremented, element logically removed.   BLOOM_REMOVE_NOT_FOUND — a counter is already 0, element not present   BLOOM_REMOVE_SATURATED — a counter is at max, decrementing it would                             corrupt counts for other elements sharing the                             slot, no counters are modified

NOTE

only remove elements you actually inserted. Removing something that was never added can corrupt counters shared with other elements, potentially causing false negatives for those elements

cbf_contains

Section titled “cbf_contains”
bool cbf_contains(
    const struct counting_bloom_filter *cbf,
    const char *element
)
source

cbf_estimated_fpr

Section titled “cbf_estimated_fpr”
fx32_32_t cbf_estimated_fpr(const struct counting_bloom_filter *cbf)
source

current theoretical false-positive rate

cbf_add

Section titled “cbf_add”
void cbf_add(struct counting_bloom_filter *cbf, const char *element)
source

cbf_destroy

Section titled “cbf_destroy”
void cbf_destroy(struct counting_bloom_filter *cbf)
source

cbf_create

Section titled “cbf_create”
struct counting_bloom_filter * cbf_create(
    size_t capacity,
    fx32_32_t false_positive_rate
)
source

cbf_create — allocate a counting bloom filter sized for capacity simultaneous live elements at the desired false_positive_rate.

Uses the standard optimal formulas:   m = -n * ln(p) / ln(2)^2 (counter slots)   k = (m/n) * ln(2) (hash functions)

Macros

Section titled “Macros”

COUNTER_BITS

Section titled “COUNTER_BITS”
#define COUNTER_BITS 4
source

COUNTER_MAX

Section titled “COUNTER_MAX”
#define COUNTER_MAX ((1u << COUNTER_BITS) - 1)
source

15

COUNTERS_PER_BYTE

Section titled “COUNTERS_PER_BYTE”
#define COUNTERS_PER_BYTE (8 / COUNTER_BITS)
source

2

CBF_COUNTERS_MIN

Section titled “CBF_COUNTERS_MIN”
#define CBF_COUNTERS_MIN ((size_t) 8)
source

CBF_HASHES_MIN

Section titled “CBF_HASHES_MIN”
#define CBF_HASHES_MIN ((size_t) 1)
source

CBF_HASHES_MAX

Section titled “CBF_HASHES_MAX”
#define CBF_HASHES_MAX ((size_t) 20)
source