<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[182321] trunk</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/182321">182321</a></dd>
<dt>Author</dt> <dd>antti@apple.com</dd>
<dt>Date</dt> <dd>2015-04-03 10:23:39 -0700 (Fri, 03 Apr 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>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):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFwtfBloomFilterh">trunk/Source/WTF/wtf/BloomFilter.h</a></li>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCorecssSelectorFiltercpp">trunk/Source/WebCore/css/SelectorFilter.cpp</a></li>
<li><a href="#trunkSourceWebCorecssSelectorFilterh">trunk/Source/WebCore/css/SelectorFilter.h</a></li>
<li><a href="#trunkSourceWebKit2ChangeLog">trunk/Source/WebKit2/ChangeLog</a></li>
<li><a href="#trunkSourceWebKit2NetworkProcesscacheNetworkCacheStorageh">trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.h</a></li>
<li><a href="#trunkToolsChangeLog">trunk/Tools/ChangeLog</a></li>
<li><a href="#trunkToolsTestWebKitAPITestWebKitAPIxcodeprojprojectpbxproj">trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkToolsTestWebKitAPITestsWTFBloomFiltercpp">trunk/Tools/TestWebKitAPI/Tests/WTF/BloomFilter.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (182320 => 182321)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2015-04-03 16:46:27 UTC (rev 182320)
+++ trunk/Source/WTF/ChangeLog 2015-04-03 17:23:39 UTC (rev 182321)
</span><span class="lines">@@ -1,3 +1,47 @@
</span><ins>+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.
+
</ins><span class="cx"> 015-04-01 Antti Koivisto <antti@apple.com>
</span><span class="cx">
</span><span class="cx"> Value assignment operator of Optional should be stricter
</span></span></pre></div>
<a id="trunkSourceWTFwtfBloomFilterh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/BloomFilter.h (182320 => 182321)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/BloomFilter.h 2015-04-03 16:46:27 UTC (rev 182320)
+++ trunk/Source/WTF/wtf/BloomFilter.h 2015-04-03 17:23:39 UTC (rev 182321)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2011 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2011, 2015 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -26,29 +26,116 @@
</span><span class="cx"> #ifndef BloomFilter_h
</span><span class="cx"> #define BloomFilter_h
</span><span class="cx">
</span><ins>+#include <array>
</ins><span class="cx"> #include <wtf/text/AtomicString.h>
</span><span class="cx">
</span><span class="cx"> namespace WTF {
</span><span class="cx">
</span><del>-// Counting bloom filter with k=2 and 8 bit counters. Uses 2^keyBits bytes of memory.
</del><ins>+// Bloom filter with k=2. Uses 2^keyBits/8 bytes of memory.
</ins><span class="cx"> // False positive rate is approximately (1-e^(-2n/m))^2, where n is the number of unique
</span><span class="cx"> // keys and m is the table size (==2^keyBits).
</span><ins>+// See http://en.wikipedia.org/wiki/Bloom_filter
</ins><span class="cx"> template <unsigned keyBits>
</span><span class="cx"> class BloomFilter {
</span><span class="cx"> WTF_MAKE_FAST_ALLOCATED;
</span><span class="cx"> public:
</span><span class="cx"> static const size_t tableSize = 1 << keyBits;
</span><ins>+
+ 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);
</ins><span class="cx"> static const unsigned keyMask = (1 << keyBits) - 1;
</span><del>- static uint8_t maximumCount() { return std::numeric_limits<uint8_t>::max(); }
</del><ins>+ 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(); }
</ins><span class="cx">
</span><del>- BloomFilter() { clear(); }
</del><ins>+ CountingBloomFilter();
</ins><span class="cx">
</span><span class="cx"> void add(unsigned hash);
</span><span class="cx"> void remove(unsigned hash);
</span><span class="cx">
</span><span class="cx"> // The filter may give false positives (claim it may contain a key it doesn't)
</span><span class="cx"> // but never false negatives (claim it doesn't contain a key it does).
</span><del>- bool mayContain(unsigned hash) const { return firstSlot(hash) && secondSlot(hash); }
</del><ins>+ bool mayContain(unsigned hash) const { return firstBucket(hash) && secondBucket(hash); }
</ins><span class="cx">
</span><span class="cx"> // The filter must be cleared before reuse even if all keys are removed.
</span><span class="cx"> // Otherwise overflowed keys will stick around.
</span><span class="lines">@@ -69,19 +156,27 @@
</span><span class="cx"> #endif
</span><span class="cx">
</span><span class="cx"> private:
</span><del>- 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]; }
</del><ins>+ static const unsigned keyMask = (1 << keyBits) - 1;
</ins><span class="cx">
</span><del>- uint8_t m_table[tableSize];
</del><ins>+ 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;
</ins><span class="cx"> };
</span><del>-
</del><ins>+
</ins><span class="cx"> template <unsigned keyBits>
</span><del>-inline void BloomFilter<keyBits>::add(unsigned hash)
</del><ins>+inline CountingBloomFilter<keyBits>::CountingBloomFilter()
+ : m_buckets()
</ins><span class="cx"> {
</span><del>- uint8_t& first = firstSlot(hash);
- uint8_t& second = secondSlot(hash);
</del><ins>+}
+
+template <unsigned keyBits>
+inline void CountingBloomFilter<keyBits>::add(unsigned hash)
+{
+ auto& first = firstBucket(hash);
+ auto& second = secondBucket(hash);
</ins><span class="cx"> if (LIKELY(first < maximumCount()))
</span><span class="cx"> ++first;
</span><span class="cx"> if (LIKELY(second < maximumCount()))
</span><span class="lines">@@ -89,13 +184,13 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template <unsigned keyBits>
</span><del>-inline void BloomFilter<keyBits>::remove(unsigned hash)
</del><ins>+inline void CountingBloomFilter<keyBits>::remove(unsigned hash)
</ins><span class="cx"> {
</span><del>- uint8_t& first = firstSlot(hash);
- uint8_t& second = secondSlot(hash);
</del><ins>+ auto& first = firstBucket(hash);
+ auto& second = secondBucket(hash);
</ins><span class="cx"> ASSERT(first);
</span><span class="cx"> ASSERT(second);
</span><del>- // In case of an overflow, the slot sticks in the table until clear().
</del><ins>+ // In case of an overflow, the bucket sticks in the table until clear().
</ins><span class="cx"> if (LIKELY(first < maximumCount()))
</span><span class="cx"> --first;
</span><span class="cx"> if (LIKELY(second < maximumCount()))
</span><span class="lines">@@ -103,27 +198,27 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template <unsigned keyBits>
</span><del>-inline void BloomFilter<keyBits>::clear()
</del><ins>+inline void CountingBloomFilter<keyBits>::clear()
</ins><span class="cx"> {
</span><del>- memset(m_table, 0, tableSize);
</del><ins>+ m_buckets.fill(0);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> #if !ASSERT_DISABLED
</span><span class="cx"> template <unsigned keyBits>
</span><del>-bool BloomFilter<keyBits>::likelyEmpty() const
</del><ins>+bool CountingBloomFilter<keyBits>::likelyEmpty() const
</ins><span class="cx"> {
</span><del>- for (size_t n = 0; n < tableSize; ++n) {
- if (m_table[n] && m_table[n] != maximumCount())
</del><ins>+ for (auto& bucket : m_buckets) {
+ if (bucket && bucket != maximumCount())
</ins><span class="cx"> return false;
</span><span class="cx"> }
</span><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template <unsigned keyBits>
</span><del>-bool BloomFilter<keyBits>::isClear() const
</del><ins>+bool CountingBloomFilter<keyBits>::isClear() const
</ins><span class="cx"> {
</span><del>- for (size_t n = 0; n < tableSize; ++n) {
- if (m_table[n])
</del><ins>+ for (auto& bucket : m_buckets) {
+ if (bucket)
</ins><span class="cx"> return false;
</span><span class="cx"> }
</span><span class="cx"> return true;
</span><span class="lines">@@ -133,5 +228,6 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> using WTF::BloomFilter;
</span><ins>+using WTF::CountingBloomFilter;
</ins><span class="cx">
</span><span class="cx"> #endif
</span></span></pre></div>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (182320 => 182321)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-04-03 16:46:27 UTC (rev 182320)
+++ trunk/Source/WebCore/ChangeLog 2015-04-03 17:23:39 UTC (rev 182321)
</span><span class="lines">@@ -1,3 +1,16 @@
</span><ins>+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.
+
</ins><span class="cx"> 2015-04-03 Alex Christensen <achristensen@webkit.org>
</span><span class="cx">
</span><span class="cx"> Remove dead code.
</span></span></pre></div>
<a id="trunkSourceWebCorecssSelectorFiltercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/css/SelectorFilter.cpp (182320 => 182321)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/css/SelectorFilter.cpp 2015-04-03 16:46:27 UTC (rev 182320)
+++ trunk/Source/WebCore/css/SelectorFilter.cpp 2015-04-03 17:23:39 UTC (rev 182321)
</span><span class="lines">@@ -88,7 +88,7 @@
</span><span class="cx"> ASSERT(m_parentStack.isEmpty() == !m_ancestorIdentifierFilter);
</span><span class="cx"> // Kill whatever we stored before.
</span><span class="cx"> m_parentStack.shrink(0);
</span><del>- m_ancestorIdentifierFilter = std::make_unique<BloomFilter<bloomFilterKeyBits>>();
</del><ins>+ m_ancestorIdentifierFilter = std::make_unique<CountingBloomFilter<bloomFilterKeyBits>>();
</ins><span class="cx"> // Fast version if parent is a root element:
</span><span class="cx"> if (!parent->parentNode() && !parent->isShadowRoot()) {
</span><span class="cx"> pushParentStackFrame(parent);
</span></span></pre></div>
<a id="trunkSourceWebCorecssSelectorFilterh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/css/SelectorFilter.h (182320 => 182321)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/css/SelectorFilter.h 2015-04-03 16:46:27 UTC (rev 182320)
+++ trunk/Source/WebCore/css/SelectorFilter.h 2015-04-03 17:23:39 UTC (rev 182321)
</span><span class="lines">@@ -64,7 +64,7 @@
</span><span class="cx">
</span><span class="cx"> // With 100 unique strings in the filter, 2^12 slot table has false positive rate of ~0.2%.
</span><span class="cx"> static const unsigned bloomFilterKeyBits = 12;
</span><del>- std::unique_ptr<BloomFilter<bloomFilterKeyBits>> m_ancestorIdentifierFilter;
</del><ins>+ std::unique_ptr<CountingBloomFilter<bloomFilterKeyBits>> m_ancestorIdentifierFilter;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> template <unsigned maximumIdentifierCount>
</span></span></pre></div>
<a id="trunkSourceWebKit2ChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebKit2/ChangeLog (182320 => 182321)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebKit2/ChangeLog 2015-04-03 16:46:27 UTC (rev 182320)
+++ trunk/Source/WebKit2/ChangeLog 2015-04-03 17:23:39 UTC (rev 182321)
</span><span class="lines">@@ -1,3 +1,12 @@
</span><ins>+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:
+
</ins><span class="cx"> 2015-04-03 Zan Dobersek <zdobersek@igalia.com>
</span><span class="cx">
</span><span class="cx"> Fix the EFL and GTK build after r182243
</span></span></pre></div>
<a id="trunkSourceWebKit2NetworkProcesscacheNetworkCacheStorageh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.h (182320 => 182321)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.h 2015-04-03 16:46:27 UTC (rev 182320)
+++ trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.h 2015-04-03 17:23:39 UTC (rev 182321)
</span><span class="lines">@@ -118,7 +118,7 @@
</span><span class="cx">
</span><span class="cx"> size_t m_maximumSize { std::numeric_limits<size_t>::max() };
</span><span class="cx">
</span><del>- BloomFilter<20> m_contentsFilter;
</del><ins>+ CountingBloomFilter<20> m_contentsFilter;
</ins><span class="cx"> std::atomic<bool> m_hasPopulatedContentsFilter { false };
</span><span class="cx">
</span><span class="cx"> std::atomic<size_t> m_approximateSize { 0 };
</span></span></pre></div>
<a id="trunkToolsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Tools/ChangeLog (182320 => 182321)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/ChangeLog 2015-04-03 16:46:27 UTC (rev 182320)
+++ trunk/Tools/ChangeLog 2015-04-03 17:23:39 UTC (rev 182321)
</span><span class="lines">@@ -1,3 +1,15 @@
</span><ins>+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):
+
</ins><span class="cx"> 2015-04-03 Csaba Osztrogonác <ossy@webkit.org>
</span><span class="cx">
</span><span class="cx"> FTL JIT tests should fail if LLVM library isn't available
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestWebKitAPIxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj (182320 => 182321)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2015-04-03 16:46:27 UTC (rev 182320)
+++ trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2015-04-03 17:23:39 UTC (rev 182321)
</span><span class="lines">@@ -282,6 +282,7 @@
</span><span class="cx"> CEA6CF2819CCF69D0064F5A7 /* open-and-close-window.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = CEA6CF2719CCF69D0064F5A7 /* open-and-close-window.html */; };
</span><span class="cx"> E1220DCA155B28AA0013E2FC /* MemoryCacheDisableWithinResourceLoadDelegate.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = E1220DC9155B287D0013E2FC /* MemoryCacheDisableWithinResourceLoadDelegate.html */; };
</span><span class="cx"> E194E1BD177E53C7009C4D4E /* StopLoadingFromDidReceiveResponse.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = E194E1BC177E534A009C4D4E /* StopLoadingFromDidReceiveResponse.html */; };
</span><ins>+ E40019331ACE9B88001B0A2A /* BloomFilter.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E40019301ACE9B5C001B0A2A /* BloomFilter.cpp */; };
</ins><span class="cx"> F660AA1115A5F631003A1243 /* GetInjectedBundleInitializationUserDataCallback_Bundle.cpp in Sources */ = {isa = PBXBuildFile; fileRef = F660AA0F15A5F624003A1243 /* GetInjectedBundleInitializationUserDataCallback_Bundle.cpp */; };
</span><span class="cx"> F660AA1515A61ABF003A1243 /* InjectedBundleInitializationUserDataCallbackWins_Bundle.cpp in Sources */ = {isa = PBXBuildFile; fileRef = F660AA1415A61ABF003A1243 /* InjectedBundleInitializationUserDataCallbackWins_Bundle.cpp */; };
</span><span class="cx"> F6B7BE9517469212008A3445 /* DidAssociateFormControls_Bundle.cpp in Sources */ = {isa = PBXBuildFile; fileRef = F6B7BE92174691EF008A3445 /* DidAssociateFormControls_Bundle.cpp */; };
</span><span class="lines">@@ -687,6 +688,7 @@
</span><span class="cx"> E1220DC9155B287D0013E2FC /* MemoryCacheDisableWithinResourceLoadDelegate.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = MemoryCacheDisableWithinResourceLoadDelegate.html; sourceTree = "<group>"; };
</span><span class="cx"> E194E1BA177E5145009C4D4E /* StopLoadingFromDidReceiveResponse.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = StopLoadingFromDidReceiveResponse.mm; sourceTree = "<group>"; };
</span><span class="cx"> E194E1BC177E534A009C4D4E /* StopLoadingFromDidReceiveResponse.html */ = {isa = PBXFileReference; lastKnownFileType = text.html; path = StopLoadingFromDidReceiveResponse.html; sourceTree = "<group>"; };
</span><ins>+ E40019301ACE9B5C001B0A2A /* BloomFilter.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = BloomFilter.cpp; sourceTree = "<group>"; };
</ins><span class="cx"> E490296714E2E3A4002BEDD1 /* TypingStyleCrash.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = TypingStyleCrash.mm; sourceTree = "<group>"; };
</span><span class="cx"> E4A757D3178AEA5B00B5D7A4 /* Deque.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = Deque.cpp; sourceTree = "<group>"; };
</span><span class="cx"> F3FC3EE213678B7300126A65 /* libgtest.a */ = {isa = PBXFileReference; lastKnownFileType = archive.ar; path = libgtest.a; sourceTree = BUILT_PRODUCTS_DIR; };
</span><span class="lines">@@ -1025,6 +1027,7 @@
</span><span class="cx"> 26F1B44215CA434F00D1E4BF /* AtomicString.cpp */,
</span><span class="cx"> A7A966DA140ECCC8005EF9B4 /* CheckedArithmeticOperations.cpp */,
</span><span class="cx"> 26A2C72E15E2E73C005B1A14 /* CString.cpp */,
</span><ins>+ E40019301ACE9B5C001B0A2A /* BloomFilter.cpp */,
</ins><span class="cx"> 7AA021BA1AB09EA70052953F /* DateMath.cpp */,
</span><span class="cx"> E4A757D3178AEA5B00B5D7A4 /* Deque.cpp */,
</span><span class="cx"> 1AA9E55714980A9900001A8A /* Functional.cpp */,
</span><span class="lines">@@ -1518,6 +1521,7 @@
</span><span class="cx"> 7CCE7F161A411AE600447C4C /* TerminateTwice.cpp in Sources */,
</span><span class="cx"> 7CCE7EA91A411A1D00447C4C /* TestBrowsingContextLoadDelegate.mm in Sources */,
</span><span class="cx"> 7CCE7EAA1A411A2400447C4C /* TestProtocol.mm in Sources */,
</span><ins>+ E40019331ACE9B88001B0A2A /* BloomFilter.cpp in Sources */,
</ins><span class="cx"> 7CCE7EAE1A411A3400447C4C /* TestsController.cpp in Sources */,
</span><span class="cx"> 7CCE7EDD1A411A9200447C4C /* TimeRanges.cpp in Sources */,
</span><span class="cx"> 7CCE7ED31A411A7E00447C4C /* TypingStyleCrash.mm in Sources */,
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWTFBloomFiltercpp"></a>
<div class="addfile"><h4>Added: trunk/Tools/TestWebKitAPI/Tests/WTF/BloomFilter.cpp (0 => 182321)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WTF/BloomFilter.cpp (rev 0)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/BloomFilter.cpp 2015-04-03 17:23:39 UTC (rev 182321)
</span><span class="lines">@@ -0,0 +1,207 @@
</span><ins>+/*
+ * 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));
+}
+
+}
</ins></span></pre>
</div>
</div>
</body>
</html>