Source/WebCore:

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

diff --git a/Source/WTF/ChangeLog b/Source/WTF/ChangeLog
index b7e70ae..1881ade 100644 (file)
--- a/Source/WTF/ChangeLog
+++ b/Source/WTF/ChangeLog
@@ -1,3 +1,47 @@
+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

diff --git a/Source/WTF/wtf/BloomFilter.h b/Source/WTF/wtf/BloomFilter.h
index 5013a86..0a3d22f 100644 (file)
--- a/Source/WTF/wtf/BloomFilter.h
+++ b/Source/WTF/wtf/BloomFilter.h
@@ -1,5 +1,5 @@
 /*
- * 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
@@ -26,29 +26,116 @@
 #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.
@@ -69,19 +156,27 @@ public:
 #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()))
@@ -89,13 +184,13 @@ inline void BloomFilter<keyBits>::add(unsigned hash)
 }
 
 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()))
@@ -103,27 +198,27 @@ inline void BloomFilter<keyBits>::remove(unsigned hash)
 }
     
 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;
@@ -133,5 +228,6 @@ bool BloomFilter<keyBits>::isClear() const
 }
 
 using WTF::BloomFilter;
+using WTF::CountingBloomFilter;
 
 #endif

diff --git a/Source/WebCore/ChangeLog b/Source/WebCore/ChangeLog
index bc4d506..6f105c4 100644 (file)
--- a/Source/WebCore/ChangeLog
+++ b/Source/WebCore/ChangeLog
@@ -1,3 +1,16 @@
+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.

diff --git a/Source/WebCore/css/SelectorFilter.cpp b/Source/WebCore/css/SelectorFilter.cpp
index 3b3fe95..02d3238 100644 (file)
--- a/Source/WebCore/css/SelectorFilter.cpp
+++ b/Source/WebCore/css/SelectorFilter.cpp
@@ -88,7 +88,7 @@ void SelectorFilter::setupParentStack(Element* parent)
     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);

diff --git a/Source/WebCore/css/SelectorFilter.h b/Source/WebCore/css/SelectorFilter.h
index a59e2cc..4ef343c 100644 (file)
--- a/Source/WebCore/css/SelectorFilter.h
+++ b/Source/WebCore/css/SelectorFilter.h
@@ -64,7 +64,7 @@ private:
 
     // 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>

diff --git a/Source/WebKit2/ChangeLog b/Source/WebKit2/ChangeLog
index f570e31..a2b2a2d 100644 (file)
--- a/Source/WebKit2/ChangeLog
+++ b/Source/WebKit2/ChangeLog
@@ -1,3 +1,12 @@
+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

diff --git a/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.h b/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.h
index c1be288..4cab39e 100644 (file)
--- a/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.h
+++ b/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.h
@@ -118,7 +118,7 @@ private:
 
     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 };

diff --git a/Tools/ChangeLog b/Tools/ChangeLog
index c06090b..faeca72 100644 (file)
--- a/Tools/ChangeLog
+++ b/Tools/ChangeLog
@@ -1,3 +1,15 @@
+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

diff --git a/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj b/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
index 308b24a..e40ae89 100644 (file)
--- a/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
+++ b/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
@@ -282,6 +282,7 @@
                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 */; };
@@ -687,6 +688,7 @@
                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; };
@@ -1025,6 +1027,7 @@
                                26F1B44215CA434F00D1E4BF /* AtomicString.cpp */,
                                A7A966DA140ECCC8005EF9B4 /* CheckedArithmeticOperations.cpp */,
                                26A2C72E15E2E73C005B1A14 /* CString.cpp */,
+                               E40019301ACE9B5C001B0A2A /* BloomFilter.cpp */,
                                7AA021BA1AB09EA70052953F /* DateMath.cpp */,
                                E4A757D3178AEA5B00B5D7A4 /* Deque.cpp */,
                                1AA9E55714980A9900001A8A /* Functional.cpp */,
@@ -1518,6 +1521,7 @@
                                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 */,

diff --git a/Tools/TestWebKitAPI/Tests/WTF/BloomFilter.cpp b/Tools/TestWebKitAPI/Tests/WTF/BloomFilter.cpp
new file mode 100644 (file)
index 0000000..2370dc2
--- /dev/null
+++ b/Tools/TestWebKitAPI/Tests/WTF/BloomFilter.cpp
@@ -0,0 +1,207 @@
+/*
+ * 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));
+}
+
+}