1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this file,
5 * You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #include "mozilla/Assertions.h"
8 #include "mozilla/BloomFilter.h"
9 #include "mozilla/UniquePtr.h"
10
11 #include <stddef.h>
12 #include <stdio.h>
13
14 using mozilla::BitBloomFilter;
15 using mozilla::CountingBloomFilter;
16
17 class FilterChecker {
18 public:
FilterChecker(uint32_t aHash)19 explicit FilterChecker(uint32_t aHash) : mHash(aHash) {}
20
hash() const21 uint32_t hash() const { return mHash; }
22
23 private:
24 uint32_t mHash;
25 };
26
testBitBloomFilter()27 void testBitBloomFilter() {
28 const mozilla::UniquePtr filter =
29 mozilla::MakeUnique<BitBloomFilter<12, FilterChecker>>();
30 MOZ_RELEASE_ASSERT(filter);
31
32 FilterChecker one(1);
33 FilterChecker two(0x20000);
34
35 filter->add(&one);
36 MOZ_RELEASE_ASSERT(filter->mightContain(&one), "Filter should contain 'one'");
37
38 MOZ_RELEASE_ASSERT(!filter->mightContain(&two),
39 "Filter claims to contain 'two' when it should not");
40
41 // Test multiple addition
42 filter->add(&two);
43 MOZ_RELEASE_ASSERT(filter->mightContain(&two),
44 "Filter should contain 'two' after 'two' is added");
45 filter->add(&two);
46 MOZ_RELEASE_ASSERT(filter->mightContain(&two),
47 "Filter should contain 'two' after 'two' is added again");
48
49 filter->clear();
50
51 MOZ_RELEASE_ASSERT(!filter->mightContain(&one), "clear() failed to work");
52 MOZ_RELEASE_ASSERT(!filter->mightContain(&two), "clear() failed to work");
53 }
54
testCountingBloomFilter()55 void testCountingBloomFilter() {
56 const mozilla::UniquePtr filter =
57 mozilla::MakeUnique<CountingBloomFilter<12, FilterChecker>>();
58 MOZ_RELEASE_ASSERT(filter);
59
60 FilterChecker one(1);
61 FilterChecker two(0x20000);
62 FilterChecker many(0x10000);
63 FilterChecker multiple(0x20001);
64
65 filter->add(&one);
66 MOZ_RELEASE_ASSERT(filter->mightContain(&one), "Filter should contain 'one'");
67
68 MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),
69 "Filter claims to contain 'multiple' when it should not");
70
71 MOZ_RELEASE_ASSERT(filter->mightContain(&many),
72 "Filter should contain 'many' (false positive)");
73
74 filter->add(&two);
75 MOZ_RELEASE_ASSERT(filter->mightContain(&multiple),
76 "Filter should contain 'multiple' (false positive)");
77
78 // Test basic removals
79 filter->remove(&two);
80 MOZ_RELEASE_ASSERT(
81 !filter->mightContain(&multiple),
82 "Filter claims to contain 'multiple' when it should not after two "
83 "was removed");
84
85 // Test multiple addition/removal
86 const size_t FILTER_SIZE = 255;
87 for (size_t i = 0; i < FILTER_SIZE - 1; ++i) {
88 filter->add(&two);
89 }
90 MOZ_RELEASE_ASSERT(
91 filter->mightContain(&multiple),
92 "Filter should contain 'multiple' after 'two' added lots of times "
93 "(false positive)");
94
95 for (size_t i = 0; i < FILTER_SIZE - 1; ++i) {
96 filter->remove(&two);
97 }
98 MOZ_RELEASE_ASSERT(
99 !filter->mightContain(&multiple),
100 "Filter claims to contain 'multiple' when it should not after two "
101 "was removed lots of times");
102
103 // Test overflowing the filter buckets
104 for (size_t i = 0; i < FILTER_SIZE + 1; ++i) {
105 filter->add(&two);
106 }
107 MOZ_RELEASE_ASSERT(
108 filter->mightContain(&multiple),
109 "Filter should contain 'multiple' after 'two' added lots more "
110 "times (false positive)");
111
112 for (size_t i = 0; i < FILTER_SIZE + 1; ++i) {
113 filter->remove(&two);
114 }
115 MOZ_RELEASE_ASSERT(
116 filter->mightContain(&multiple),
117 "Filter claims to not contain 'multiple' even though we should "
118 "have run out of space in the buckets (false positive)");
119 MOZ_RELEASE_ASSERT(
120 filter->mightContain(&two),
121 "Filter claims to not contain 'two' even though we should have "
122 "run out of space in the buckets (false positive)");
123
124 filter->remove(&one);
125
126 MOZ_RELEASE_ASSERT(
127 !filter->mightContain(&one),
128 "Filter should not contain 'one', because we didn't overflow its "
129 "bucket");
130
131 filter->clear();
132
133 MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),
134 "clear() failed to work");
135 }
136
main()137 int main() {
138 testBitBloomFilter();
139 testCountingBloomFilter();
140
141 return 0;
142 }
143