1/* @title: (Counting) Bloom Filter */
2#pragma once
3#include <stdbool.h>
4#include <stddef.h>
5#include <stdint.h>
6#include <types/types.h>
7
8#define COUNTER_BITS 4
9#define COUNTER_MAX ((1u << COUNTER_BITS) - 1) /* 15 */
10#define COUNTERS_PER_BYTE (8 / COUNTER_BITS) /* 2 */
11
12struct counting_bloom_filter {
13 uint8_t *counters;
14 size_t num_counters;
15 size_t num_hashes;
16 size_t live_elements;
17};
18
19enum bloom_remove_result {
20 BLOOM_REMOVE_OK = 0,
21 BLOOM_REMOVE_NOT_FOUND = -1,
22 BLOOM_REMOVE_SATURATED = -2,
23};
24
25/*
26 * cbf_remove -- remove an element (decrements k counters).
27 *
28 * BLOOM_REMOVE_OK -- counters decremented, element logically removed.
29 * BLOOM_REMOVE_NOT_FOUND -- a counter is already 0, element not present
30 * BLOOM_REMOVE_SATURATED -- a counter is at max, decrementing it would
31 * corrupt counts for other elements sharing the
32 * slot, no counters are modified
33 *
34 * NOTE: only remove elements you actually inserted. Removing something
35 * that was never added can corrupt counters shared with other elements,
36 * potentially causing false negatives for those elements
37 */
38enum bloom_remove_result cbf_remove(struct counting_bloom_filter *cbf,
39 const char *element);
40bool cbf_contains(const struct counting_bloom_filter *cbf, const char *element);
41
42/* current theoretical false-positive rate */
43fx32_32_t cbf_estimated_fpr(const struct counting_bloom_filter *cbf);
44void cbf_add(struct counting_bloom_filter *cbf, const char *element);
45void cbf_destroy(struct counting_bloom_filter *cbf);
46
47/*
48 * cbf_create -- allocate a counting bloom filter sized for `capacity`
49 * simultaneous live elements at the desired `false_positive_rate`.
50 *
51 * Uses the standard optimal formulas:
52 * m = -n * ln(p) / ln(2)^2 (counter slots)
53 * k = (m/n) * ln(2) (hash functions)
54 */
55struct counting_bloom_filter *cbf_create(size_t capacity,
56 fx32_32_t false_positive_rate);
57