(Counting) Bloom Filter

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

Structs

struct counting_bloom_filter {
    uint8_t  *counters;
    size_t   num_counters;
    size_t   num_hashes;
    size_t   live_elements;
};

enum bloom_remove_result {
    BLOOM_REMOVE_OK = 0,
    BLOOM_REMOVE_NOT_FOUND = -1,
    BLOOM_REMOVE_SATURATED = -2,
};

enum bloom_remove_result cbf_remove(struct counting_bloom_filter *cbf, const char *element);

bool cbf_contains(const struct counting_bloom_filter *cbf, const char *element);

fx32_32_t cbf_estimated_fpr(const struct counting_bloom_filter *cbf);

void cbf_add(struct counting_bloom_filter *cbf, const char *element);

void cbf_destroy(struct counting_bloom_filter *cbf);

struct counting_bloom_filter * cbf_create(size_t capacity, fx32_32_t false_positive_rate);

#define COUNTER_BITS 4

#define COUNTER_MAX ((1u << COUNTER_BITS) - 1) /* 15 */

#define COUNTERS_PER_BYTE (8 / COUNTER_BITS)   /* 2  */