1#include "structures/tests/test_internal.h"
2
3TEST_GROUP_DECLARE(bloom, .intensity_desc = {
4 .curve = SCALE_PIECEWISE_LOG,
5 .unit = "iters",
6 });
7
8TEST_DECLARE_UNIT(bloom, add_contains_remove) {
9 /* 50 element capacity, 0.05 false positive rate */
10 struct counting_bloom_filter *cbf = cbf_create(capacity: 50, FX(0.05));
11 TEST_ASSERT_NONNULL(cbf);
12
13 const char *words[] = {"kernel", "scheduler", "memory", "paging",
14 "turnstile"};
15 size_t nwords = sizeof(words) / sizeof(words[0]);
16
17 for (size_t i = 0; i < nwords; i++)
18 TEST_ASSERT(!cbf_contains(cbf, words[i]));
19
20 for (size_t i = 0; i < nwords; i++)
21 cbf_add(cbf, element: words[i]);
22
23 for (size_t i = 0; i < nwords; i++)
24 TEST_ASSERT(cbf_contains(cbf, words[i]));
25
26 TEST_ASSERT(!cbf_contains(cbf, "nonexistent_symbol"));
27
28 /* Removing words should succeed and dec element count */
29 for (size_t i = 0; i < nwords; i++) {
30 enum bloom_remove_result res = cbf_remove(cbf, element: words[i]);
31 TEST_ASSERT_EQ_S(res, BLOOM_REMOVE_OK);
32 }
33
34 TEST_ASSERT_EQ(cbf->live_elements, 0);
35
36 /* Removing again must return BLOOM_REMOVE_NOT_FOUND */
37 TEST_ASSERT_EQ_S(cbf_remove(cbf, words[0]), BLOOM_REMOVE_NOT_FOUND);
38
39 cbf_destroy(cbf);
40 return TEST_SUCCESS;
41}
42
43TEST_DECLARE_UNIT(bloom, counter_saturation, TEST_INTENSITY(16, 20, 64)) {
44 struct counting_bloom_filter *cbf = cbf_create(capacity: 10, FX(0.1));
45 TEST_ASSERT_NONNULL(cbf);
46
47 size_t adds = ctx->intensity_val ? ctx->intensity_val : 20;
48 if (adds < 16)
49 adds = 16;
50
51 /* Adding the same element >= 16 times saturates at COUNTER_MAX (15) */
52 for (size_t i = 0; i < adds; i++)
53 cbf_add(cbf, element: "saturate_me");
54
55 TEST_ASSERT(cbf_contains(cbf, "saturate_me"));
56
57 /* Removing a saturated element reports saturated and refuses decrement */
58 enum bloom_remove_result res = cbf_remove(cbf, element: "saturate_me");
59 TEST_ASSERT_EQ_S(res, BLOOM_REMOVE_SATURATED);
60
61 cbf_destroy(cbf);
62 return TEST_SUCCESS;
63}
64