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