1/*
2 * Copyright (C) 2015 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27
28#include <wtf/BloomFilter.h>
29#include <wtf/RandomNumber.h>
30#include <wtf/SHA1.h>
31
32namespace TestWebKitAPI {
33
34static Vector<unsigned> generateRandomHashes(size_t hashCount)
35{
36 Vector<unsigned> hashes;
37 for (unsigned i = 0; i < hashCount; ++i)
38 hashes.append(static_cast<unsigned>(randomNumber() * std::numeric_limits<unsigned>::max()));
39 return hashes;
40}
41
42static Vector<SHA1::Digest> generateRandomDigests(size_t hashCount)
43{
44 Vector<SHA1::Digest> hashes;
45 SHA1 sha1;
46 for (unsigned i = 0; i < hashCount; ++i) {
47 double random = randomNumber();
48 sha1.addBytes(reinterpret_cast<uint8_t*>(&random), sizeof(double));
49 SHA1::Digest digest;
50 sha1.computeHash(digest);
51 hashes.append(digest);
52 }
53 return hashes;
54}
55
56TEST(WTF_BloomFilter, Basic)
57{
58 const unsigned hashCount = 1000;
59 auto hashes = generateRandomHashes(hashCount);
60
61 BloomFilter<16> filter;
62 for (auto hash : hashes)
63 filter.add(hash);
64
65 for (auto hash : hashes)
66 EXPECT_TRUE(filter.mayContain(hash));
67
68 auto moreHashes = generateRandomHashes(hashCount);
69 unsigned mayContainCount = 0;
70 for (auto hash : moreHashes)
71 mayContainCount += filter.mayContain(hash) ? 1 : 0;
72 // False positive rate is ~0.09% so this should always be true.
73 EXPECT_TRUE(mayContainCount < hashCount / 10);
74
75 for (auto hash : moreHashes)
76 filter.add(hash);
77
78 for (auto hash : hashes)
79 EXPECT_TRUE(filter.mayContain(hash));
80 for (auto hash : moreHashes)
81 EXPECT_TRUE(filter.mayContain(hash));
82}
83
84TEST(WTF_BloomFilter, BasicDigest)
85{
86 const unsigned hashCount = 1000;
87 auto hashes = generateRandomDigests(hashCount);
88
89 BloomFilter<20> filter;
90 for (auto hash : hashes)
91 filter.add(hash);
92
93 for (auto hash : hashes)
94 EXPECT_TRUE(filter.mayContain(hash));
95
96 auto moreHashes = generateRandomDigests(hashCount);
97 unsigned mayContainCount = 0;
98 for (auto hash : moreHashes)
99 mayContainCount += filter.mayContain(hash) ? 1 : 0;
100 // False positive rate is ~0.000004% so this should always be true.
101 EXPECT_TRUE(mayContainCount < hashCount / 10);
102
103 for (auto hash : moreHashes)
104 filter.add(hash);
105
106 for (auto hash : hashes)
107 EXPECT_TRUE(filter.mayContain(hash));
108 for (auto hash : moreHashes)
109 EXPECT_TRUE(filter.mayContain(hash));
110}
111
112TEST(WTF_BloomFilter, BasicCounting)
113{
114 const unsigned hashCount = 1000;
115 auto hashes = generateRandomHashes(hashCount);
116
117 CountingBloomFilter<16> filter;
118 for (auto hash : hashes)
119 filter.add(hash);
120
121 for (auto hash : hashes)
122 EXPECT_TRUE(filter.mayContain(hash));
123
124 for (auto hash : hashes)
125 filter.add(hash);
126
127 for (auto hash : hashes)
128 EXPECT_TRUE(filter.mayContain(hash));
129
130 for (auto hash : hashes)
131 filter.remove(hash);
132
133 for (auto hash : hashes)
134 EXPECT_TRUE(filter.mayContain(hash));
135
136 auto moreHashes = generateRandomHashes(hashCount);
137 unsigned mayContainCount = 0;
138 for (auto hash : moreHashes)
139 mayContainCount += filter.mayContain(hash) ? 1 : 0;
140 // False positive rate is ~0.09% so this should always be true.
141 EXPECT_TRUE(mayContainCount < hashCount / 10);
142
143 for (auto hash : moreHashes)
144 filter.add(hash);
145 for (auto hash : hashes)
146 filter.remove(hash);
147
148 for (auto hash : moreHashes)
149 EXPECT_TRUE(filter.mayContain(hash));
150
151 for (auto hash : moreHashes)
152 filter.remove(hash);
153
154 for (auto hash : hashes)
155 EXPECT_TRUE(!filter.mayContain(hash));
156 for (auto hash : moreHashes)
157 EXPECT_TRUE(!filter.mayContain(hash));
158}
159
160TEST(WTF_BloomFilter, Clear)
161{
162 const unsigned hashCount = 1000;
163 auto hashes = generateRandomHashes(hashCount);
164
165 BloomFilter<16> filter;
166 for (auto hash : hashes)
167 filter.add(hash);
168
169 filter.clear();
170
171 for (auto hash : hashes)
172 EXPECT_TRUE(!filter.mayContain(hash));
173}
174
175TEST(WTF_BloomFilter, ClearCounting)
176{
177 const unsigned hashCount = 1000;
178 auto hashes = generateRandomHashes(hashCount);
179
180 CountingBloomFilter<16> filter;
181 for (auto hash : hashes)
182 filter.add(hash);
183 for (auto hash : hashes)
184 filter.add(hash);
185
186 filter.clear();
187
188 for (auto hash : hashes)
189 EXPECT_TRUE(!filter.mayContain(hash));
190}
191
192TEST(WTF_BloomFilter, CountingOverflow)
193{
194 const unsigned hashCount = 1000;
195 auto hashes = generateRandomHashes(hashCount);
196
197 CountingBloomFilter<16> filter;
198 for (auto hash : hashes)
199 filter.add(hash);
200
201 for (unsigned i = 0; i < filter.maximumCount() + 100; ++i)
202 filter.add(hashes[0]);
203
204 for (auto hash : hashes)
205 EXPECT_TRUE(filter.mayContain(hash));
206
207 for (auto hash : hashes)
208 filter.remove(hash);
209
210 unsigned mayContainCount = 0;
211 for (auto hash : hashes) {
212 if (hash == hashes[0])
213 EXPECT_TRUE(filter.mayContain(hash));
214 else
215 mayContainCount += filter.mayContain(hash) ? 1 : 0;
216 }
217 // False positive rate should be very low.
218 EXPECT_TRUE(mayContainCount < hashCount / 100);
219
220 for (unsigned i = 0; i < filter.maximumCount() + 100; ++i)
221 filter.remove(hashes[0]);
222
223 // The bucket has overflowed and is stuck.
224 EXPECT_TRUE(filter.mayContain(hashes[0]));
225}
226
227TEST(WTF_BloomFilter, Combine)
228{
229 const unsigned hashCount = 1000;
230 auto hashes = generateRandomHashes(hashCount);
231
232 BloomFilter<16> filter;
233 for (auto hash : hashes)
234 filter.add(hash);
235
236 auto moreHashes = generateRandomHashes(hashCount);
237
238 BloomFilter<16> anotherFilter;
239 for (auto hash : moreHashes)
240 anotherFilter.add(hash);
241
242 filter.add(anotherFilter);
243
244 for (auto hash : hashes)
245 EXPECT_TRUE(filter.mayContain(hash));
246 for (auto hash : moreHashes)
247 EXPECT_TRUE(filter.mayContain(hash));
248}
249
250}
251