Add non-counting bloom filter class
https://bugs.webkit.org/show_bug.cgi?id=143366
Reviewed by Sam Weinig.
* css/SelectorFilter.cpp:
(WebCore::SelectorFilter::setupParentStack):
* css/SelectorFilter.h:
Update names.
Source/WebKit2:
Add non-counting Bloom filter implementation
https://bugs.webkit.org/show_bug.cgi?id=143366
Reviewed by Sam Weinig.
* NetworkProcess/cache/NetworkCacheStorage.h:
Source/WTF:
Add non-counting Bloom filter implementation
https://bugs.webkit.org/show_bug.cgi?id=143366
Reviewed by Sam Weinig.
Add a traditional single-bit-per-bucket Bloom filter in addition to the existing counting implementation.
- rename BloomFilter -> CountingBloomFilter.
- add a new basic BloomFilter type.
- update some terminology to match http://en.wikipedia.org/wiki/Bloom_filter and modernize the code a bit.
- add API tests.
* wtf/BloomFilter.h:
(WTF::BloomFilter::BloomFilter):
(WTF::BloomFilter::add):
Also support merging.
(WTF::BloomFilter::mayContain):
(WTF::BloomFilter::arrayIndex):
(WTF::BloomFilter::bitMask):
(WTF::BloomFilter<keyBits>::mayContain):
(WTF::BloomFilter<keyBits>::add):
(WTF::BloomFilter<keyBits>::isBitSet):
(WTF::BloomFilter<keyBits>::setBit):
(WTF::BloomFilter<keyBits>::clear):
(WTF::CountingBloomFilter::CountingBloomFilter):
(WTF::CountingBloomFilter::mayContain):
(WTF::CountingBloomFilter::firstBucket):
(WTF::CountingBloomFilter::secondBucket):
(WTF::CountingBloomFilter<keyBits>::add):
(WTF::CountingBloomFilter<keyBits>::remove):
(WTF::CountingBloomFilter<keyBits>::clear):
(WTF::CountingBloomFilter<keyBits>::likelyEmpty):
(WTF::CountingBloomFilter<keyBits>::isClear):
(WTF::BloomFilter::maximumCount): Deleted.
(WTF::BloomFilter::firstSlot): Deleted.
(WTF::BloomFilter::secondSlot): Deleted.
(WTF::BloomFilter<keyBits>::remove): Deleted.
(WTF::BloomFilter<keyBits>::likelyEmpty): Deleted.
(WTF::BloomFilter<keyBits>::isClear): Deleted.
Tools:
Add non-counting bloom filter class
https://bugs.webkit.org/show_bug.cgi?id=143366
Reviewed by Sam Weinig.
* TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
* TestWebKitAPI/Tests/WTF/BloomFilter.cpp: Added.
(TestWebKitAPI::generateRandomHashes):
(TestWebKitAPI::TEST):
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@182321
268f45cc-cd09-0410-ab3c-
d52691b4dbfc
+2015-04-03 Antti Koivisto <antti@apple.com>
+
+ Add non-counting Bloom filter implementation
+ https://bugs.webkit.org/show_bug.cgi?id=143366
+
+ Reviewed by Sam Weinig.
+
+ Add a traditional single-bit-per-bucket Bloom filter in addition to the existing counting implementation.
+
+ - rename BloomFilter -> CountingBloomFilter.
+ - add a new basic BloomFilter type.
+ - update some terminology to match http://en.wikipedia.org/wiki/Bloom_filter and modernize the code a bit.
+ - add API tests.
+
+ * wtf/BloomFilter.h:
+ (WTF::BloomFilter::BloomFilter):
+ (WTF::BloomFilter::add):
+
+ Also support merging.
+
+ (WTF::BloomFilter::mayContain):
+ (WTF::BloomFilter::arrayIndex):
+ (WTF::BloomFilter::bitMask):
+ (WTF::BloomFilter<keyBits>::mayContain):
+ (WTF::BloomFilter<keyBits>::add):
+ (WTF::BloomFilter<keyBits>::isBitSet):
+ (WTF::BloomFilter<keyBits>::setBit):
+ (WTF::BloomFilter<keyBits>::clear):
+ (WTF::CountingBloomFilter::CountingBloomFilter):
+ (WTF::CountingBloomFilter::mayContain):
+ (WTF::CountingBloomFilter::firstBucket):
+ (WTF::CountingBloomFilter::secondBucket):
+ (WTF::CountingBloomFilter<keyBits>::add):
+ (WTF::CountingBloomFilter<keyBits>::remove):
+ (WTF::CountingBloomFilter<keyBits>::clear):
+ (WTF::CountingBloomFilter<keyBits>::likelyEmpty):
+ (WTF::CountingBloomFilter<keyBits>::isClear):
+ (WTF::BloomFilter::maximumCount): Deleted.
+ (WTF::BloomFilter::firstSlot): Deleted.
+ (WTF::BloomFilter::secondSlot): Deleted.
+ (WTF::BloomFilter<keyBits>::remove): Deleted.
+ (WTF::BloomFilter<keyBits>::likelyEmpty): Deleted.
+ (WTF::BloomFilter<keyBits>::isClear): Deleted.
+
015-04-01 Antti Koivisto <antti@apple.com>
Value assignment operator of Optional should be stricter
/*
- * Copyright (C) 2011 Apple Inc. All rights reserved.
+ * Copyright (C) 2011, 2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
#ifndef BloomFilter_h
#define BloomFilter_h
+#include <array>
#include <wtf/text/AtomicString.h>
namespace WTF {
-// Counting bloom filter with k=2 and 8 bit counters. Uses 2^keyBits bytes of memory.
+// Bloom filter with k=2. Uses 2^keyBits/8 bytes of memory.
// False positive rate is approximately (1-e^(-2n/m))^2, where n is the number of unique
// keys and m is the table size (==2^keyBits).
+// See http://en.wikipedia.org/wiki/Bloom_filter
template <unsigned keyBits>
class BloomFilter {
WTF_MAKE_FAST_ALLOCATED;
public:
static const size_t tableSize = 1 << keyBits;
+
+ BloomFilter();
+
+ void add(unsigned hash);
+ void add(const BloomFilter&);
+
+ // The filter may give false positives (claim it may contain a key it doesn't)
+ // but never false negatives (claim it doesn't contain a key it does).
+ bool mayContain(unsigned hash) const;
+
+ void clear();
+
+ void add(const AtomicString& string) { add(string.impl()->existingHash()); }
+ void add(const String& string) { add(string.impl()->hash()); }
+ bool mayContain(const AtomicString& string) const { return mayContain(string.impl()->existingHash()); }
+ bool mayContain(const String& string) const { return mayContain(string.impl()->hash()); }
+
+private:
+ static const unsigned bitsPerPosition = 8 * sizeof(unsigned);
static const unsigned keyMask = (1 << keyBits) - 1;
- static uint8_t maximumCount() { return std::numeric_limits<uint8_t>::max(); }
+ static unsigned arrayIndex(unsigned key) { return key / bitsPerPosition; }
+ static unsigned bitMask(unsigned key) { return 1 << (key % bitsPerPosition); }
+
+ bool isBitSet(unsigned key) const;
+ void setBit(unsigned key);
+
+ std::array<unsigned, tableSize / bitsPerPosition> m_bitArray;
+};
+
+template <unsigned keyBits>
+inline BloomFilter<keyBits>::BloomFilter()
+ : m_bitArray()
+{
+}
+
+template <unsigned keyBits>
+inline bool BloomFilter<keyBits>::mayContain(unsigned hash) const
+{
+ // The top and bottom bits of the incoming hash are treated as independent bloom filter hash functions.
+ // This works well as long as the filter size is not much above 2^16.
+ return isBitSet(hash) && isBitSet(hash >> 16);
+}
+
+template <unsigned keyBits>
+inline void BloomFilter<keyBits>::add(unsigned hash)
+{
+ setBit(hash);
+ setBit(hash >> 16);
+}
+
+template <unsigned keyBits>
+inline void BloomFilter<keyBits>::add(const BloomFilter& other)
+{
+ for (size_t i = 0; i < m_bitArray.size(); ++i)
+ m_bitArray[i] |= other.m_bitArray[i];
+}
+
+template <unsigned keyBits>
+bool BloomFilter<keyBits>::isBitSet(unsigned key) const
+{
+ unsigned maskedKey = key & keyMask;
+ ASSERT(arrayIndex(maskedKey) < m_bitArray.size());
+ return m_bitArray[arrayIndex(maskedKey)] & bitMask(maskedKey);
+}
+
+template <unsigned keyBits>
+void BloomFilter<keyBits>::setBit(unsigned key)
+{
+ unsigned maskedKey = key & keyMask;
+ ASSERT(arrayIndex(maskedKey) < m_bitArray.size());
+ m_bitArray[arrayIndex(maskedKey)] |= bitMask(maskedKey);
+}
+
+template <unsigned keyBits>
+inline void BloomFilter<keyBits>::clear()
+{
+ m_bitArray.fill(0);
+}
+
+// Counting bloom filter with 8 bit counters. Uses 2^keyBits bytes of memory. Error rates as above.
+// See http://en.wikipedia.org/wiki/Bloom_filter#Counting_filters
+template <unsigned keyBits>
+class CountingBloomFilter {
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ static const size_t tableSize = 1 << keyBits;
+ static unsigned maximumCount() { return std::numeric_limits<uint8_t>::max(); }
- BloomFilter() { clear(); }
+ CountingBloomFilter();
void add(unsigned hash);
void remove(unsigned hash);
// The filter may give false positives (claim it may contain a key it doesn't)
// but never false negatives (claim it doesn't contain a key it does).
- bool mayContain(unsigned hash) const { return firstSlot(hash) && secondSlot(hash); }
+ bool mayContain(unsigned hash) const { return firstBucket(hash) && secondBucket(hash); }
// The filter must be cleared before reuse even if all keys are removed.
// Otherwise overflowed keys will stick around.
#endif
private:
- uint8_t& firstSlot(unsigned hash) { return m_table[hash & keyMask]; }
- uint8_t& secondSlot(unsigned hash) { return m_table[(hash >> 16) & keyMask]; }
- const uint8_t& firstSlot(unsigned hash) const { return m_table[hash & keyMask]; }
- const uint8_t& secondSlot(unsigned hash) const { return m_table[(hash >> 16) & keyMask]; }
+ static const unsigned keyMask = (1 << keyBits) - 1;
- uint8_t m_table[tableSize];
+ uint8_t& firstBucket(unsigned hash) { return m_buckets[hash & keyMask]; }
+ uint8_t& secondBucket(unsigned hash) { return m_buckets[(hash >> 16) & keyMask]; }
+ const uint8_t& firstBucket(unsigned hash) const { return m_buckets[hash & keyMask]; }
+ const uint8_t& secondBucket(unsigned hash) const { return m_buckets[(hash >> 16) & keyMask]; }
+
+ std::array<uint8_t, tableSize> m_buckets;
};
-
+
template <unsigned keyBits>
-inline void BloomFilter<keyBits>::add(unsigned hash)
+inline CountingBloomFilter<keyBits>::CountingBloomFilter()
+ : m_buckets()
{
- uint8_t& first = firstSlot(hash);
- uint8_t& second = secondSlot(hash);
+}
+
+template <unsigned keyBits>
+inline void CountingBloomFilter<keyBits>::add(unsigned hash)
+{
+ auto& first = firstBucket(hash);
+ auto& second = secondBucket(hash);
if (LIKELY(first < maximumCount()))
++first;
if (LIKELY(second < maximumCount()))
}
template <unsigned keyBits>
-inline void BloomFilter<keyBits>::remove(unsigned hash)
+inline void CountingBloomFilter<keyBits>::remove(unsigned hash)
{
- uint8_t& first = firstSlot(hash);
- uint8_t& second = secondSlot(hash);
+ auto& first = firstBucket(hash);
+ auto& second = secondBucket(hash);
ASSERT(first);
ASSERT(second);
- // In case of an overflow, the slot sticks in the table until clear().
+ // In case of an overflow, the bucket sticks in the table until clear().
if (LIKELY(first < maximumCount()))
--first;
if (LIKELY(second < maximumCount()))
}
template <unsigned keyBits>
-inline void BloomFilter<keyBits>::clear()
+inline void CountingBloomFilter<keyBits>::clear()
{
- memset(m_table, 0, tableSize);
+ m_buckets.fill(0);
}
#if !ASSERT_DISABLED
template <unsigned keyBits>
-bool BloomFilter<keyBits>::likelyEmpty() const
+bool CountingBloomFilter<keyBits>::likelyEmpty() const
{
- for (size_t n = 0; n < tableSize; ++n) {
- if (m_table[n] && m_table[n] != maximumCount())
+ for (auto& bucket : m_buckets) {
+ if (bucket && bucket != maximumCount())
return false;
}
return true;
}
template <unsigned keyBits>
-bool BloomFilter<keyBits>::isClear() const
+bool CountingBloomFilter<keyBits>::isClear() const
{
- for (size_t n = 0; n < tableSize; ++n) {
- if (m_table[n])
+ for (auto& bucket : m_buckets) {
+ if (bucket)
return false;
}
return true;
}
using WTF::BloomFilter;
+using WTF::CountingBloomFilter;
#endif
+2015-04-03 Antti Koivisto <antti@apple.com>
+
+ Add non-counting bloom filter class
+ https://bugs.webkit.org/show_bug.cgi?id=143366
+
+ Reviewed by Sam Weinig.
+
+ * css/SelectorFilter.cpp:
+ (WebCore::SelectorFilter::setupParentStack):
+ * css/SelectorFilter.h:
+
+ Update names.
+
2015-04-03 Alex Christensen <achristensen@webkit.org>
Remove dead code.
ASSERT(m_parentStack.isEmpty() == !m_ancestorIdentifierFilter);
// Kill whatever we stored before.
m_parentStack.shrink(0);
- m_ancestorIdentifierFilter = std::make_unique<BloomFilter<bloomFilterKeyBits>>();
+ m_ancestorIdentifierFilter = std::make_unique<CountingBloomFilter<bloomFilterKeyBits>>();
// Fast version if parent is a root element:
if (!parent->parentNode() && !parent->isShadowRoot()) {
pushParentStackFrame(parent);
// With 100 unique strings in the filter, 2^12 slot table has false positive rate of ~0.2%.
static const unsigned bloomFilterKeyBits = 12;
- std::unique_ptr<BloomFilter<bloomFilterKeyBits>> m_ancestorIdentifierFilter;
+ std::unique_ptr<CountingBloomFilter<bloomFilterKeyBits>> m_ancestorIdentifierFilter;
};
template <unsigned maximumIdentifierCount>
+2015-04-03 Antti Koivisto <antti@apple.com>
+
+ Add non-counting Bloom filter implementation
+ https://bugs.webkit.org/show_bug.cgi?id=143366
+
+ Reviewed by Sam Weinig.
+
+ * NetworkProcess/cache/NetworkCacheStorage.h:
+
2015-04-03 Zan Dobersek <zdobersek@igalia.com>
Fix the EFL and GTK build after r182243
size_t m_maximumSize { std::numeric_limits<size_t>::max() };
- BloomFilter<20> m_contentsFilter;
+ CountingBloomFilter<20> m_contentsFilter;
std::atomic<bool> m_hasPopulatedContentsFilter { false };
std::atomic<size_t> m_approximateSize { 0 };
+2015-04-03 Antti Koivisto <antti@apple.com>
+
+ Add non-counting bloom filter class
+ https://bugs.webkit.org/show_bug.cgi?id=143366
+
+ Reviewed by Sam Weinig.
+
+ * TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
+ * TestWebKitAPI/Tests/WTF/BloomFilter.cpp: Added.
+ (TestWebKitAPI::generateRandomHashes):
+ (TestWebKitAPI::TEST):
+
2015-04-03 Csaba Osztrogonác <ossy@webkit.org>
FTL JIT tests should fail if LLVM library isn't available
CEA6CF2819CCF69D0064F5A7 /* open-and-close-window.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = CEA6CF2719CCF69D0064F5A7 /* open-and-close-window.html */; };
E1220DCA155B28AA0013E2FC /* MemoryCacheDisableWithinResourceLoadDelegate.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = E1220DC9155B287D0013E2FC /* MemoryCacheDisableWithinResourceLoadDelegate.html */; };
E194E1BD177E53C7009C4D4E /* StopLoadingFromDidReceiveResponse.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = E194E1BC177E534A009C4D4E /* StopLoadingFromDidReceiveResponse.html */; };
+ E40019331ACE9B88001B0A2A /* BloomFilter.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E40019301ACE9B5C001B0A2A /* BloomFilter.cpp */; };
F660AA1115A5F631003A1243 /* GetInjectedBundleInitializationUserDataCallback_Bundle.cpp in Sources */ = {isa = PBXBuildFile; fileRef = F660AA0F15A5F624003A1243 /* GetInjectedBundleInitializationUserDataCallback_Bundle.cpp */; };
F660AA1515A61ABF003A1243 /* InjectedBundleInitializationUserDataCallbackWins_Bundle.cpp in Sources */ = {isa = PBXBuildFile; fileRef = F660AA1415A61ABF003A1243 /* InjectedBundleInitializationUserDataCallbackWins_Bundle.cpp */; };
F6B7BE9517469212008A3445 /* DidAssociateFormControls_Bundle.cpp in Sources */ = {isa = PBXBuildFile; fileRef = F6B7BE92174691EF008A3445 /* DidAssociateFormControls_Bundle.cpp */; };
E1220DC9155B287D0013E2FC /* MemoryCacheDisableWithinResourceLoadDelegate.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = MemoryCacheDisableWithinResourceLoadDelegate.html; sourceTree = "<group>"; };
E194E1BA177E5145009C4D4E /* StopLoadingFromDidReceiveResponse.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = StopLoadingFromDidReceiveResponse.mm; sourceTree = "<group>"; };
E194E1BC177E534A009C4D4E /* StopLoadingFromDidReceiveResponse.html */ = {isa = PBXFileReference; lastKnownFileType = text.html; path = StopLoadingFromDidReceiveResponse.html; sourceTree = "<group>"; };
+ E40019301ACE9B5C001B0A2A /* BloomFilter.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = BloomFilter.cpp; sourceTree = "<group>"; };
E490296714E2E3A4002BEDD1 /* TypingStyleCrash.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = TypingStyleCrash.mm; sourceTree = "<group>"; };
E4A757D3178AEA5B00B5D7A4 /* Deque.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = Deque.cpp; sourceTree = "<group>"; };
F3FC3EE213678B7300126A65 /* libgtest.a */ = {isa = PBXFileReference; lastKnownFileType = archive.ar; path = libgtest.a; sourceTree = BUILT_PRODUCTS_DIR; };
26F1B44215CA434F00D1E4BF /* AtomicString.cpp */,
A7A966DA140ECCC8005EF9B4 /* CheckedArithmeticOperations.cpp */,
26A2C72E15E2E73C005B1A14 /* CString.cpp */,
+ E40019301ACE9B5C001B0A2A /* BloomFilter.cpp */,
7AA021BA1AB09EA70052953F /* DateMath.cpp */,
E4A757D3178AEA5B00B5D7A4 /* Deque.cpp */,
1AA9E55714980A9900001A8A /* Functional.cpp */,
7CCE7F161A411AE600447C4C /* TerminateTwice.cpp in Sources */,
7CCE7EA91A411A1D00447C4C /* TestBrowsingContextLoadDelegate.mm in Sources */,
7CCE7EAA1A411A2400447C4C /* TestProtocol.mm in Sources */,
+ E40019331ACE9B88001B0A2A /* BloomFilter.cpp in Sources */,
7CCE7EAE1A411A3400447C4C /* TestsController.cpp in Sources */,
7CCE7EDD1A411A9200447C4C /* TimeRanges.cpp in Sources */,
7CCE7ED31A411A7E00447C4C /* TypingStyleCrash.mm in Sources */,
--- /dev/null
+/*
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+
+#include <wtf/BloomFilter.h>
+#include <wtf/RandomNumber.h>
+
+namespace TestWebKitAPI {
+
+static Vector<unsigned> generateRandomHashes(size_t hashCount)
+{
+ Vector<unsigned> hashes;
+ for (unsigned i = 0; i < hashCount; ++i)
+ hashes.append(static_cast<unsigned>(randomNumber() * std::numeric_limits<unsigned>::max()));
+ return hashes;
+}
+
+TEST(WTF_BloomFilter, Basic)
+{
+ const unsigned hashCount = 1000;
+ auto hashes = generateRandomHashes(hashCount);
+
+ BloomFilter<16> filter;
+ for (auto hash : hashes)
+ filter.add(hash);
+
+ for (auto hash : hashes)
+ EXPECT_TRUE(filter.mayContain(hash));
+
+ auto moreHashes = generateRandomHashes(hashCount);
+ unsigned mayContainCount = 0;
+ for (auto hash : moreHashes)
+ mayContainCount += filter.mayContain(hash) ? 1 : 0;
+ // False positive rate is ~0.09% so this should always be true.
+ EXPECT_TRUE(mayContainCount < hashCount / 10);
+
+ for (auto hash : moreHashes)
+ filter.add(hash);
+
+ for (auto hash : hashes)
+ EXPECT_TRUE(filter.mayContain(hash));
+ for (auto hash : moreHashes)
+ EXPECT_TRUE(filter.mayContain(hash));
+}
+
+TEST(WTF_BloomFilter, BasicCounting)
+{
+ const unsigned hashCount = 1000;
+ auto hashes = generateRandomHashes(hashCount);
+
+ CountingBloomFilter<16> filter;
+ for (auto hash : hashes)
+ filter.add(hash);
+
+ for (auto hash : hashes)
+ EXPECT_TRUE(filter.mayContain(hash));
+
+ for (auto hash : hashes)
+ filter.add(hash);
+
+ for (auto hash : hashes)
+ EXPECT_TRUE(filter.mayContain(hash));
+
+ for (auto hash : hashes)
+ filter.remove(hash);
+
+ for (auto hash : hashes)
+ EXPECT_TRUE(filter.mayContain(hash));
+
+ auto moreHashes = generateRandomHashes(hashCount);
+ unsigned mayContainCount = 0;
+ for (auto hash : moreHashes)
+ mayContainCount += filter.mayContain(hash) ? 1 : 0;
+ // False positive rate is ~0.09% so this should always be true.
+ EXPECT_TRUE(mayContainCount < hashCount / 10);
+
+ for (auto hash : moreHashes)
+ filter.add(hash);
+ for (auto hash : hashes)
+ filter.remove(hash);
+
+ for (auto hash : moreHashes)
+ EXPECT_TRUE(filter.mayContain(hash));
+
+ for (auto hash : moreHashes)
+ filter.remove(hash);
+
+ for (auto hash : hashes)
+ EXPECT_TRUE(!filter.mayContain(hash));
+ for (auto hash : moreHashes)
+ EXPECT_TRUE(!filter.mayContain(hash));
+}
+
+TEST(WTF_BloomFilter, Clear)
+{
+ const unsigned hashCount = 1000;
+ auto hashes = generateRandomHashes(hashCount);
+
+ BloomFilter<16> filter;
+ for (auto hash : hashes)
+ filter.add(hash);
+
+ filter.clear();
+
+ for (auto hash : hashes)
+ EXPECT_TRUE(!filter.mayContain(hash));
+}
+
+TEST(WTF_BloomFilter, ClearCounting)
+{
+ const unsigned hashCount = 1000;
+ auto hashes = generateRandomHashes(hashCount);
+
+ CountingBloomFilter<16> filter;
+ for (auto hash : hashes)
+ filter.add(hash);
+ for (auto hash : hashes)
+ filter.add(hash);
+
+ filter.clear();
+
+ for (auto hash : hashes)
+ EXPECT_TRUE(!filter.mayContain(hash));
+}
+
+TEST(WTF_BloomFilter, CountingOverflow)
+{
+ const unsigned hashCount = 1000;
+ auto hashes = generateRandomHashes(hashCount);
+
+ CountingBloomFilter<16> filter;
+ for (auto hash : hashes)
+ filter.add(hash);
+
+ for (unsigned i = 0; i < filter.maximumCount() + 100; ++i)
+ filter.add(hashes[0]);
+
+ for (auto hash : hashes)
+ EXPECT_TRUE(filter.mayContain(hash));
+
+ for (auto hash : hashes)
+ filter.remove(hash);
+
+ unsigned mayContainCount = 0;
+ for (auto hash : hashes) {
+ if (hash == hashes[0])
+ EXPECT_TRUE(filter.mayContain(hash));
+ else
+ mayContainCount += filter.mayContain(hash) ? 1 : 0;
+ }
+ // False positive rate should be very low.
+ EXPECT_TRUE(mayContainCount < hashCount / 100);
+
+ for (unsigned i = 0; i < filter.maximumCount() + 100; ++i)
+ filter.remove(hashes[0]);
+
+ // The bucket has overflowed and is stuck.
+ EXPECT_TRUE(filter.mayContain(hashes[0]));
+}
+
+TEST(WTF_BloomFilter, Combine)
+{
+ const unsigned hashCount = 1000;
+ auto hashes = generateRandomHashes(hashCount);
+
+ BloomFilter<16> filter;
+ for (auto hash : hashes)
+ filter.add(hash);
+
+ auto moreHashes = generateRandomHashes(hashCount);
+
+ BloomFilter<16> anotherFilter;
+ for (auto hash : moreHashes)
+ anotherFilter.add(hash);
+
+ filter.add(anotherFilter);
+
+ for (auto hash : hashes)
+ EXPECT_TRUE(filter.mayContain(hash));
+ for (auto hash : moreHashes)
+ EXPECT_TRUE(filter.mayContain(hash));
+}
+
+}