<!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>[183499] trunk/Source</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/183499">183499</a></dd>
<dt>Author</dt> <dd>commit-queue@webkit.org</dd>
<dt>Date</dt> <dd>2015-04-28 12:40:19 -0700 (Tue, 28 Apr 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>[Content Extensions] Use less memory for CombinedURLFilters.
https://bugs.webkit.org/show_bug.cgi?id=144290
Patch by Alex Christensen <achristensen@webkit.org> on 2015-04-28
Reviewed by Andreas Kling.
Source/WebCore:
* contentextensions/CombinedURLFilters.cpp:
(WebCore::ContentExtensions::recursiveMemoryUsed):
(WebCore::ContentExtensions::CombinedURLFilters::addPattern):
(WebCore::ContentExtensions::generateNFAForSubtree):
(WebCore::ContentExtensions::CombinedURLFilters::createNFAs):
* contentextensions/NFA.cpp:
(WebCore::ContentExtensions::NFA::memoryUsed):
(WebCore::ContentExtensions::NFA::setActions):
* contentextensions/NFA.h:
* contentextensions/NFANode.h:
* contentextensions/Term.h:
(WebCore::ContentExtensions::Term::Term::generateGraph):
(WebCore::ContentExtensions::Term::generateSubgraphForAtom):
Use Vectors instead of HashTables in PrefixTreeVertex because the sets stay small and need to be more memory efficient.
Source/WTF:
* wtf/Forward.h:
* wtf/Vector.h:
Added a minCapacity template parameter to allow changing the minimum size of an
allocated buffer. The default minCapacity is kept at 16 unless otherwise specified
to have no change on existing code, but this could be changed later. A smaller
default minCapacity would use less memory with small Vectors but spend more time
copying when expanding to large Vectors.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFwtfForwardh">trunk/Source/WTF/wtf/Forward.h</a></li>
<li><a href="#trunkSourceWTFwtfVectorh">trunk/Source/WTF/wtf/Vector.h</a></li>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsCombinedURLFilterscpp">trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFAcpp">trunk/Source/WebCore/contentextensions/NFA.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFAh">trunk/Source/WebCore/contentextensions/NFA.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFANodeh">trunk/Source/WebCore/contentextensions/NFANode.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsTermh">trunk/Source/WebCore/contentextensions/Term.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (183498 => 183499)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WTF/ChangeLog 2015-04-28 19:40:19 UTC (rev 183499)
</span><span class="lines">@@ -1,3 +1,18 @@
</span><ins>+2015-04-28 Alex Christensen <achristensen@webkit.org>
+
+ [Content Extensions] Use less memory for CombinedURLFilters.
+ https://bugs.webkit.org/show_bug.cgi?id=144290
+
+ Reviewed by Andreas Kling.
+
+ * wtf/Forward.h:
+ * wtf/Vector.h:
+ Added a minCapacity template parameter to allow changing the minimum size of an
+ allocated buffer. The default minCapacity is kept at 16 unless otherwise specified
+ to have no change on existing code, but this could be changed later. A smaller
+ default minCapacity would use less memory with small Vectors but spend more time
+ copying when expanding to large Vectors.
+
</ins><span class="cx"> 2015-04-27 Brent Fulgham <bfulgham@apple.com>
</span><span class="cx">
</span><span class="cx"> [Win] Deactivate WebGL until Windows tests work properly
</span></span></pre></div>
<a id="trunkSourceWTFwtfForwardh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/Forward.h (183498 => 183499)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/Forward.h 2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WTF/wtf/Forward.h 2015-04-28 19:40:19 UTC (rev 183499)
</span><span class="lines">@@ -33,7 +33,7 @@
</span><span class="cx"> template<typename T> class Ref;
</span><span class="cx"> template<typename T> class StringBuffer;
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler> class Vector;
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> class Vector;
</ins><span class="cx">
</span><span class="cx"> class AtomicString;
</span><span class="cx"> class AtomicStringImpl;
</span></span></pre></div>
<a id="trunkSourceWTFwtfVectorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/Vector.h (183498 => 183499)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/Vector.h 2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WTF/wtf/Vector.h 2015-04-28 19:40:19 UTC (rev 183499)
</span><span class="lines">@@ -581,7 +581,7 @@
</span><span class="cx"> }
</span><span class="cx"> };
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity = 0, typename OverflowHandler = CrashOnOverflow>
</del><ins>+template<typename T, size_t inlineCapacity = 0, typename OverflowHandler = CrashOnOverflow, size_t minCapacity = 16>
</ins><span class="cx"> class Vector : private VectorBuffer<T, inlineCapacity> {
</span><span class="cx"> WTF_MAKE_FAST_ALLOCATED;
</span><span class="cx"> private:
</span><span class="lines">@@ -754,7 +754,7 @@
</span><span class="cx">
</span><span class="cx"> MallocPtr<T> releaseBuffer();
</span><span class="cx">
</span><del>- void swap(Vector<T, inlineCapacity, OverflowHandler>& other)
</del><ins>+ void swap(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& other)
</ins><span class="cx"> {
</span><span class="cx"> #if ASAN_ENABLED
</span><span class="cx"> if (this == std::addressof(other)) // ASan will crash if we try to restrict access to the same buffer twice.
</span><span class="lines">@@ -804,8 +804,8 @@
</span><span class="cx"> #endif
</span><span class="cx"> };
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-Vector<T, inlineCapacity, OverflowHandler>::Vector(const Vector& other)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector& other)
</ins><span class="cx"> : Base(other.capacity(), other.size())
</span><span class="cx"> {
</span><span class="cx"> asanSetInitialBufferSizeTo(other.size());
</span><span class="lines">@@ -814,9 +814,9 @@
</span><span class="cx"> TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
</ins><span class="cx"> template<size_t otherCapacity, typename otherOverflowBehaviour>
</span><del>-Vector<T, inlineCapacity, OverflowHandler>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
</del><ins>+Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
</ins><span class="cx"> : Base(other.capacity(), other.size())
</span><span class="cx"> {
</span><span class="cx"> asanSetInitialBufferSizeTo(other.size());
</span><span class="lines">@@ -825,8 +825,8 @@
</span><span class="cx"> TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(const Vector<T, inlineCapacity, OverflowHandler>& other)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& other)
</ins><span class="cx"> {
</span><span class="cx"> if (&other == this)
</span><span class="cx"> return *this;
</span><span class="lines">@@ -850,9 +850,9 @@
</span><span class="cx">
</span><span class="cx"> inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
</ins><span class="cx"> template<size_t otherCapacity, typename otherOverflowBehaviour>
</span><del>-Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
</del><ins>+Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
</ins><span class="cx"> {
</span><span class="cx"> // If the inline capacities match, we should call the more specific
</span><span class="cx"> // template. If the inline capacities don't match, the two objects
</span><span class="lines">@@ -876,29 +876,29 @@
</span><span class="cx"> return *this;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline Vector<T, inlineCapacity, OverflowHandler>::Vector(Vector<T, inlineCapacity, OverflowHandler>&& other)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(Vector<T, inlineCapacity, OverflowHandler, minCapacity>&& other)
</ins><span class="cx"> {
</span><span class="cx"> swap(other);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(Vector<T, inlineCapacity, OverflowHandler>&& other)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(Vector<T, inlineCapacity, OverflowHandler, minCapacity>&& other)
</ins><span class="cx"> {
</span><span class="cx"> swap(other);
</span><span class="cx"> return *this;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
</ins><span class="cx"> template<typename U>
</span><del>-bool Vector<T, inlineCapacity, OverflowHandler>::contains(const U& value) const
</del><ins>+bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::contains(const U& value) const
</ins><span class="cx"> {
</span><span class="cx"> return find(value) != notFound;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
</ins><span class="cx"> template<typename U>
</span><del>-size_t Vector<T, inlineCapacity, OverflowHandler>::find(const U& value) const
</del><ins>+size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::find(const U& value) const
</ins><span class="cx"> {
</span><span class="cx"> for (size_t i = 0; i < size(); ++i) {
</span><span class="cx"> if (at(i) == value)
</span><span class="lines">@@ -907,9 +907,9 @@
</span><span class="cx"> return notFound;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
</ins><span class="cx"> template<typename U>
</span><del>-size_t Vector<T, inlineCapacity, OverflowHandler>::reverseFind(const U& value) const
</del><ins>+size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reverseFind(const U& value) const
</ins><span class="cx"> {
</span><span class="cx"> for (size_t i = 1; i <= size(); ++i) {
</span><span class="cx"> const size_t index = size() - i;
</span><span class="lines">@@ -919,8 +919,8 @@
</span><span class="cx"> return notFound;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-void Vector<T, inlineCapacity, OverflowHandler>::fill(const T& val, size_t newSize)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::fill(const T& val, size_t newSize)
</ins><span class="cx"> {
</span><span class="cx"> if (size() > newSize)
</span><span class="cx"> shrink(newSize);
</span><span class="lines">@@ -937,22 +937,22 @@
</span><span class="cx"> m_size = newSize;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
</ins><span class="cx"> template<typename Iterator>
</span><del>-void Vector<T, inlineCapacity, OverflowHandler>::appendRange(Iterator start, Iterator end)
</del><ins>+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendRange(Iterator start, Iterator end)
</ins><span class="cx"> {
</span><span class="cx"> for (Iterator it = start; it != end; ++it)
</span><span class="cx"> append(*it);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-void Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity)
</ins><span class="cx"> {
</span><del>- reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
</del><ins>+ reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-T* Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity, T* ptr)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+T* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity, T* ptr)
</ins><span class="cx"> {
</span><span class="cx"> if (ptr < begin() || ptr >= end()) {
</span><span class="cx"> expandCapacity(newMinCapacity);
</span><span class="lines">@@ -963,14 +963,14 @@
</span><span class="cx"> return begin() + index;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-bool Vector<T, inlineCapacity, OverflowHandler>::tryExpandCapacity(size_t newMinCapacity)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryExpandCapacity(size_t newMinCapacity)
</ins><span class="cx"> {
</span><del>- return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
</del><ins>+ return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-const T* Vector<T, inlineCapacity, OverflowHandler>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+const T* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
</ins><span class="cx"> {
</span><span class="cx"> if (ptr < begin() || ptr >= end()) {
</span><span class="cx"> if (!tryExpandCapacity(newMinCapacity))
</span><span class="lines">@@ -983,15 +983,15 @@
</span><span class="cx"> return begin() + index;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-inline U* Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity, U* ptr)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+inline U* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
</ins><span class="cx"> {
</span><span class="cx"> expandCapacity(newMinCapacity);
</span><span class="cx"> return ptr;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::resize(size_t size)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::resize(size_t size)
</ins><span class="cx"> {
</span><span class="cx"> if (size <= m_size) {
</span><span class="cx"> TypeOperations::destruct(begin() + size, end());
</span><span class="lines">@@ -1007,15 +1007,15 @@
</span><span class="cx"> m_size = size;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-void Vector<T, inlineCapacity, OverflowHandler>::resizeToFit(size_t size)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::resizeToFit(size_t size)
</ins><span class="cx"> {
</span><span class="cx"> reserveCapacity(size);
</span><span class="cx"> resize(size);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-void Vector<T, inlineCapacity, OverflowHandler>::shrink(size_t size)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrink(size_t size)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT(size <= m_size);
</span><span class="cx"> TypeOperations::destruct(begin() + size, end());
</span><span class="lines">@@ -1023,8 +1023,8 @@
</span><span class="cx"> m_size = size;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-void Vector<T, inlineCapacity, OverflowHandler>::grow(size_t size)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::grow(size_t size)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT(size >= m_size);
</span><span class="cx"> if (size > capacity())
</span><span class="lines">@@ -1035,8 +1035,8 @@
</span><span class="cx"> m_size = size;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::asanSetInitialBufferSizeTo(size_t size)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanSetInitialBufferSizeTo(size_t size)
</ins><span class="cx"> {
</span><span class="cx"> #if ASAN_ENABLED
</span><span class="cx"> if (!buffer())
</span><span class="lines">@@ -1051,8 +1051,8 @@
</span><span class="cx"> #endif
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::asanSetBufferSizeToFullCapacity()
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanSetBufferSizeToFullCapacity()
</ins><span class="cx"> {
</span><span class="cx"> #if ASAN_ENABLED
</span><span class="cx"> if (!buffer())
</span><span class="lines">@@ -1063,8 +1063,8 @@
</span><span class="cx"> #endif
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::asanBufferSizeWillChangeTo(size_t newSize)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanBufferSizeWillChangeTo(size_t newSize)
</ins><span class="cx"> {
</span><span class="cx"> #if ASAN_ENABLED
</span><span class="cx"> if (!buffer())
</span><span class="lines">@@ -1077,8 +1077,8 @@
</span><span class="cx"> #endif
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-void Vector<T, inlineCapacity, OverflowHandler>::reserveCapacity(size_t newCapacity)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveCapacity(size_t newCapacity)
</ins><span class="cx"> {
</span><span class="cx"> if (newCapacity <= capacity())
</span><span class="cx"> return;
</span><span class="lines">@@ -1096,8 +1096,8 @@
</span><span class="cx"> Base::deallocateBuffer(oldBuffer);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-bool Vector<T, inlineCapacity, OverflowHandler>::tryReserveCapacity(size_t newCapacity)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryReserveCapacity(size_t newCapacity)
</ins><span class="cx"> {
</span><span class="cx"> if (newCapacity <= capacity())
</span><span class="cx"> return true;
</span><span class="lines">@@ -1119,8 +1119,8 @@
</span><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::reserveInitialCapacity(size_t initialCapacity)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveInitialCapacity(size_t initialCapacity)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT(!m_size);
</span><span class="cx"> ASSERT(capacity() == inlineCapacity);
</span><span class="lines">@@ -1128,8 +1128,8 @@
</span><span class="cx"> Base::allocateBuffer(initialCapacity);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-void Vector<T, inlineCapacity, OverflowHandler>::shrinkCapacity(size_t newCapacity)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrinkCapacity(size_t newCapacity)
</ins><span class="cx"> {
</span><span class="cx"> if (newCapacity >= capacity())
</span><span class="cx"> return;
</span><span class="lines">@@ -1162,8 +1162,8 @@
</span><span class="cx"> // Templatizing these is better than just letting the conversion happen implicitly,
</span><span class="cx"> // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
</span><span class="cx"> // without refcount thrash.
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-void Vector<T, inlineCapacity, OverflowHandler>::append(const U* data, size_t dataSize)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::append(const U* data, size_t dataSize)
</ins><span class="cx"> {
</span><span class="cx"> size_t newSize = m_size + dataSize;
</span><span class="cx"> if (newSize > capacity()) {
</span><span class="lines">@@ -1178,8 +1178,8 @@
</span><span class="cx"> m_size = newSize;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-bool Vector<T, inlineCapacity, OverflowHandler>::tryAppend(const U* data, size_t dataSize)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryAppend(const U* data, size_t dataSize)
</ins><span class="cx"> {
</span><span class="cx"> size_t newSize = m_size + dataSize;
</span><span class="cx"> if (newSize > capacity()) {
</span><span class="lines">@@ -1197,8 +1197,8 @@
</span><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler>::append(U&& value)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::append(U&& value)
</ins><span class="cx"> {
</span><span class="cx"> if (size() != capacity()) {
</span><span class="cx"> asanBufferSizeWillChangeTo(m_size + 1);
</span><span class="lines">@@ -1210,8 +1210,8 @@
</span><span class="cx"> appendSlowCase(std::forward<U>(value));
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-void Vector<T, inlineCapacity, OverflowHandler>::appendSlowCase(U&& value)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendSlowCase(U&& value)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT(size() == capacity());
</span><span class="cx">
</span><span class="lines">@@ -1227,8 +1227,8 @@
</span><span class="cx"> // This version of append saves a branch in the case where you know that the
</span><span class="cx"> // vector's capacity is large enough for the append to succeed.
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-inline void Vector<T, inlineCapacity, OverflowHandler>::uncheckedAppend(U&& value)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::uncheckedAppend(U&& value)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT(size() < capacity());
</span><span class="cx">
</span><span class="lines">@@ -1239,14 +1239,14 @@
</span><span class="cx"> ++m_size;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U, size_t otherCapacity>
-inline void Vector<T, inlineCapacity, OverflowHandler>::appendVector(const Vector<U, otherCapacity>& val)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U, size_t otherCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendVector(const Vector<U, otherCapacity>& val)
</ins><span class="cx"> {
</span><span class="cx"> append(val.begin(), val.size());
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-void Vector<T, inlineCapacity, OverflowHandler>::insert(size_t position, const U* data, size_t dataSize)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size_t position, const U* data, size_t dataSize)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
</span><span class="cx"> size_t newSize = m_size + dataSize;
</span><span class="lines">@@ -1263,8 +1263,8 @@
</span><span class="cx"> m_size = newSize;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-inline void Vector<T, inlineCapacity, OverflowHandler>::insert(size_t position, U&& value)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size_t position, U&& value)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
</span><span class="cx">
</span><span class="lines">@@ -1282,14 +1282,14 @@
</span><span class="cx"> ++m_size;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U, size_t c>
-inline void Vector<T, inlineCapacity, OverflowHandler>::insertVector(size_t position, const Vector<U, c>& val)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U, size_t c>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insertVector(size_t position, const Vector<U, c>& val)
</ins><span class="cx"> {
</span><span class="cx"> insert(position, val.begin(), val.size());
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::remove(size_t position)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size_t position)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT_WITH_SECURITY_IMPLICATION(position < size());
</span><span class="cx"> T* spot = begin() + position;
</span><span class="lines">@@ -1299,8 +1299,8 @@
</span><span class="cx"> --m_size;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::remove(size_t position, size_t length)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size_t position, size_t length)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
</span><span class="cx"> ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size());
</span><span class="lines">@@ -1312,18 +1312,18 @@
</span><span class="cx"> m_size -= length;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
</ins><span class="cx"> template<typename U>
</span><del>-inline bool Vector<T, inlineCapacity, OverflowHandler>::removeFirst(const U& value)
</del><ins>+inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeFirst(const U& value)
</ins><span class="cx"> {
</span><span class="cx"> return removeFirstMatching([&value] (const T& current) {
</span><span class="cx"> return current == value;
</span><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
</ins><span class="cx"> template<typename MatchFunction>
</span><del>-inline bool Vector<T, inlineCapacity, OverflowHandler>::removeFirstMatching(const MatchFunction& matches)
</del><ins>+inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeFirstMatching(const MatchFunction& matches)
</ins><span class="cx"> {
</span><span class="cx"> for (size_t i = 0; i < size(); ++i) {
</span><span class="cx"> if (matches(at(i))) {
</span><span class="lines">@@ -1334,18 +1334,18 @@
</span><span class="cx"> return false;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
</ins><span class="cx"> template<typename U>
</span><del>-inline unsigned Vector<T, inlineCapacity, OverflowHandler>::removeAll(const U& value)
</del><ins>+inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeAll(const U& value)
</ins><span class="cx"> {
</span><span class="cx"> return removeAllMatching([&value] (const T& current) {
</span><span class="cx"> return current == value;
</span><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
</ins><span class="cx"> template<typename MatchFunction>
</span><del>-inline unsigned Vector<T, inlineCapacity, OverflowHandler>::removeAllMatching(const MatchFunction& matches)
</del><ins>+inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeAllMatching(const MatchFunction& matches)
</ins><span class="cx"> {
</span><span class="cx"> iterator holeBegin = end();
</span><span class="cx"> iterator holeEnd = end();
</span><span class="lines">@@ -1370,15 +1370,15 @@
</span><span class="cx"> return matchCount;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::reverse()
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reverse()
</ins><span class="cx"> {
</span><span class="cx"> for (size_t i = 0; i < m_size / 2; ++i)
</span><span class="cx"> std::swap(at(i), at(m_size - 1 - i));
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline MallocPtr<T> Vector<T, inlineCapacity, OverflowHandler>::releaseBuffer()
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline MallocPtr<T> Vector<T, inlineCapacity, OverflowHandler, minCapacity>::releaseBuffer()
</ins><span class="cx"> {
</span><span class="cx"> // FIXME: Find a way to preserve annotations on the returned buffer.
</span><span class="cx"> // ASan requires that all annotations are removed before deallocation,
</span><span class="lines">@@ -1399,8 +1399,8 @@
</span><span class="cx"> return buffer;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::checkConsistency()
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::checkConsistency()
</ins><span class="cx"> {
</span><span class="cx"> #if !ASSERT_DISABLED
</span><span class="cx"> for (size_t i = 0; i < size(); ++i)
</span><span class="lines">@@ -1408,14 +1408,14 @@
</span><span class="cx"> #endif
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void swap(Vector<T, inlineCapacity, OverflowHandler>& a, Vector<T, inlineCapacity, OverflowHandler>& b)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void swap(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
</ins><span class="cx"> {
</span><span class="cx"> a.swap(b);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-bool operator==(const Vector<T, inlineCapacity, OverflowHandler>& a, const Vector<T, inlineCapacity, OverflowHandler>& b)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+bool operator==(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
</ins><span class="cx"> {
</span><span class="cx"> if (a.size() != b.size())
</span><span class="cx"> return false;
</span><span class="lines">@@ -1423,8 +1423,8 @@
</span><span class="cx"> return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline bool operator!=(const Vector<T, inlineCapacity, OverflowHandler>& a, const Vector<T, inlineCapacity, OverflowHandler>& b)
</del><ins>+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline bool operator!=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
</ins><span class="cx"> {
</span><span class="cx"> return !(a == b);
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (183498 => 183499)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WebCore/ChangeLog 2015-04-28 19:40:19 UTC (rev 183499)
</span><span class="lines">@@ -1,3 +1,25 @@
</span><ins>+2015-04-28 Alex Christensen <achristensen@webkit.org>
+
+ [Content Extensions] Use less memory for CombinedURLFilters.
+ https://bugs.webkit.org/show_bug.cgi?id=144290
+
+ Reviewed by Andreas Kling.
+
+ * contentextensions/CombinedURLFilters.cpp:
+ (WebCore::ContentExtensions::recursiveMemoryUsed):
+ (WebCore::ContentExtensions::CombinedURLFilters::addPattern):
+ (WebCore::ContentExtensions::generateNFAForSubtree):
+ (WebCore::ContentExtensions::CombinedURLFilters::createNFAs):
+ * contentextensions/NFA.cpp:
+ (WebCore::ContentExtensions::NFA::memoryUsed):
+ (WebCore::ContentExtensions::NFA::setActions):
+ * contentextensions/NFA.h:
+ * contentextensions/NFANode.h:
+ * contentextensions/Term.h:
+ (WebCore::ContentExtensions::Term::Term::generateGraph):
+ (WebCore::ContentExtensions::Term::generateSubgraphForAtom):
+ Use Vectors instead of HashTables in PrefixTreeVertex because the sets stay small and need to be more memory efficient.
+
</ins><span class="cx"> 2015-04-28 Brady Eidson <beidson@apple.com>
</span><span class="cx">
</span><span class="cx"> Consolidate most "frame load" arguments into FrameLoadRequest.
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsCombinedURLFilterscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp (183498 => 183499)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-04-28 19:40:19 UTC (rev 183499)
</span><span class="lines">@@ -29,17 +29,17 @@
</span><span class="cx"> #if ENABLE(CONTENT_EXTENSIONS)
</span><span class="cx">
</span><span class="cx"> #include "Term.h"
</span><del>-#include <wtf/HashMap.h>
</del><ins>+#include <wtf/Vector.h>
</ins><span class="cx">
</span><span class="cx"> namespace WebCore {
</span><span class="cx">
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><del>-typedef HashMap<Term, std::unique_ptr<PrefixTreeVertex>, TermHash, TermHashTraits> PrefixTreeEdges;
</del><ins>+typedef Vector<std::pair<Term, std::unique_ptr<PrefixTreeVertex>>, 0, WTF::CrashOnOverflow, 1> PrefixTreeEdges;
</ins><span class="cx">
</span><span class="cx"> struct PrefixTreeVertex {
</span><span class="cx"> PrefixTreeEdges edges;
</span><del>- ActionSet finalActions;
</del><ins>+ ActionList finalActions;
</ins><span class="cx"> bool inVariableLengthPrefix { false };
</span><span class="cx"> };
</span><span class="cx">
</span><span class="lines">@@ -48,8 +48,8 @@
</span><span class="cx"> size_t size = sizeof(PrefixTreeVertex)
</span><span class="cx"> + node->edges.capacity() * sizeof(std::pair<Term, std::unique_ptr<PrefixTreeVertex>>)
</span><span class="cx"> + node->finalActions.capacity() * sizeof(uint64_t);
</span><del>- for (const auto& child : node->edges.values())
- size += recursiveMemoryUsed(child);
</del><ins>+ for (const auto& child : node->edges)
+ size += recursiveMemoryUsed(child.second);
</ins><span class="cx"> return size;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -88,23 +88,30 @@
</span><span class="cx"> prefixTreeVerticesForPattern.append(lastPrefixTree);
</span><span class="cx">
</span><span class="cx"> for (const Term& term : pattern) {
</span><del>- auto nextEntry = lastPrefixTree->edges.find(term);
- if (nextEntry != lastPrefixTree->edges.end())
- lastPrefixTree = nextEntry->value.get();
</del><ins>+ size_t nextEntryIndex = WTF::notFound;
+ for (size_t i = 0; i < lastPrefixTree->edges.size(); ++i) {
+ if (lastPrefixTree->edges[i].first == term) {
+ nextEntryIndex = i;
+ break;
+ }
+ }
+ if (nextEntryIndex != WTF::notFound)
+ lastPrefixTree = lastPrefixTree->edges[nextEntryIndex].second.get();
</ins><span class="cx"> else {
</span><span class="cx"> hasNewTerm = true;
</span><span class="cx">
</span><span class="cx"> std::unique_ptr<PrefixTreeVertex> nextPrefixTreeVertex = std::make_unique<PrefixTreeVertex>();
</span><span class="cx">
</span><del>- auto addResult = lastPrefixTree->edges.set(term, WTF::move(nextPrefixTreeVertex));
- ASSERT(addResult.isNewEntry);
-
- lastPrefixTree = addResult.iterator->value.get();
</del><ins>+ ASSERT(lastPrefixTree->edges.find(std::make_pair(term, std::make_unique<PrefixTreeVertex>())) == WTF::notFound);
+ lastPrefixTree->edges.append(std::make_pair(term, WTF::move(nextPrefixTreeVertex)));
+ lastPrefixTree = lastPrefixTree->edges.last().second.get();
</ins><span class="cx"> }
</span><span class="cx"> prefixTreeVerticesForPattern.append(lastPrefixTree);
</span><span class="cx"> }
</span><span class="cx">
</span><del>- prefixTreeVerticesForPattern.last()->finalActions.add(actionId);
</del><ins>+ ActionList& actions = prefixTreeVerticesForPattern.last()->finalActions;
+ if (actions.find(actionId) == WTF::notFound)
+ actions.append(actionId);
</ins><span class="cx">
</span><span class="cx"> if (!hasNewTerm)
</span><span class="cx"> return;
</span><span class="lines">@@ -142,13 +149,13 @@
</span><span class="cx"> while (true) {
</span><span class="cx"> ProcessSubtree:
</span><span class="cx"> for (ActiveNFASubtree& activeSubtree = activeStack.last(); activeSubtree.iterator != activeSubtree.vertex->edges.end(); ++activeSubtree.iterator) {
</span><del>- if (activeSubtree.iterator->value->inVariableLengthPrefix)
</del><ins>+ if (activeSubtree.iterator->second->inVariableLengthPrefix)
</ins><span class="cx"> continue;
</span><span class="cx">
</span><del>- const Term& term = activeSubtree.iterator->key;
- unsigned newEndNodeIndex = term.generateGraph(nfa, activeSubtree.lastNodeIndex, activeSubtree.iterator->value->finalActions);
</del><ins>+ const Term& term = activeSubtree.iterator->first;
+ unsigned newEndNodeIndex = term.generateGraph(nfa, activeSubtree.lastNodeIndex, activeSubtree.iterator->second->finalActions);
</ins><span class="cx">
</span><del>- PrefixTreeVertex* prefixTreeVertex = activeSubtree.iterator->value.get();
</del><ins>+ PrefixTreeVertex* prefixTreeVertex = activeSubtree.iterator->second.get();
</ins><span class="cx"> if (!prefixTreeVertex->edges.isEmpty()) {
</span><span class="cx"> activeStack.append(ActiveNFASubtree(prefixTreeVertex, prefixTreeVertex->edges.begin(), newEndNodeIndex));
</span><span class="cx"> goto ProcessSubtree;
</span><span class="lines">@@ -175,7 +182,7 @@
</span><span class="cx">
</span><span class="cx"> // We go depth first into the subtrees with variable prefix. Find the next subtree.
</span><span class="cx"> for (; activeSubtree.iterator != activeSubtree.vertex->edges.end(); ++activeSubtree.iterator) {
</span><del>- PrefixTreeVertex* prefixTreeVertex = activeSubtree.iterator->value.get();
</del><ins>+ PrefixTreeVertex* prefixTreeVertex = activeSubtree.iterator->second.get();
</ins><span class="cx"> if (prefixTreeVertex->inVariableLengthPrefix) {
</span><span class="cx"> activeStack.append(ActiveSubtree({ prefixTreeVertex, prefixTreeVertex->edges.begin() }));
</span><span class="cx"> goto ProcessSubtree;
</span><span class="lines">@@ -187,7 +194,7 @@
</span><span class="cx"> bool needToGenerate = activeSubtree.vertex->edges.isEmpty() && !activeSubtree.vertex->finalActions.isEmpty();
</span><span class="cx"> if (!needToGenerate) {
</span><span class="cx"> for (const auto& edge : activeSubtree.vertex->edges) {
</span><del>- if (!edge.value->inVariableLengthPrefix) {
</del><ins>+ if (!edge.second->inVariableLengthPrefix) {
</ins><span class="cx"> needToGenerate = true;
</span><span class="cx"> break;
</span><span class="cx"> }
</span><span class="lines">@@ -201,15 +208,15 @@
</span><span class="cx"> unsigned prefixEnd = generatingNFA.root();
</span><span class="cx">
</span><span class="cx"> for (unsigned i = 0; i < activeStack.size() - 1; ++i) {
</span><del>- const Term& term = activeStack[i].iterator->key;
- prefixEnd = term.generateGraph(generatingNFA, prefixEnd, activeStack[i].iterator->value->finalActions);
</del><ins>+ const Term& term = activeStack[i].iterator->first;
+ prefixEnd = term.generateGraph(generatingNFA, prefixEnd, activeStack[i].iterator->second->finalActions);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> for (const auto& edge : activeSubtree.vertex->edges) {
</span><del>- if (!edge.value->inVariableLengthPrefix) {
- const Term& term = edge.key;
- unsigned newSubtreeStart = term.generateGraph(generatingNFA, prefixEnd, edge.value->finalActions);
- generateNFAForSubtree(generatingNFA, newSubtreeStart, *edge.value);
</del><ins>+ if (!edge.second->inVariableLengthPrefix) {
+ const Term& term = edge.first;
+ unsigned newSubtreeStart = term.generateGraph(generatingNFA, prefixEnd, edge.second->finalActions);
+ generateNFAForSubtree(generatingNFA, newSubtreeStart, *edge.second);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFA.cpp (183498 => 183499)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFA.cpp 2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WebCore/contentextensions/NFA.cpp 2015-04-28 19:40:19 UTC (rev 183499)
</span><span class="lines">@@ -51,6 +51,8 @@
</span><span class="cx"> {
</span><span class="cx"> size_t size = 0;
</span><span class="cx"> for (const NFANode& node : m_nodes) {
</span><ins>+ for (const auto& transition : node.transitions)
+ size += transition.value.capacity() * sizeof(unsigned);
</ins><span class="cx"> size += sizeof(node)
</span><span class="cx"> + node.transitions.capacity() * sizeof(std::pair<uint16_t, NFANodeIndexSet>)
</span><span class="cx"> + node.transitionsOnAnyCharacter.capacity() * sizeof(unsigned)
</span><span class="lines">@@ -93,7 +95,7 @@
</span><span class="cx"> transitionSlot.value.remove(to);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void NFA::setActions(unsigned node, const ActionSet& actions)
</del><ins>+void NFA::setActions(unsigned node, const ActionList& actions)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT_WITH_MESSAGE(m_nodes[node].finalRuleIds.isEmpty(), "The final state should only be defined once.");
</span><span class="cx"> copyToVector(actions, m_nodes[node].finalRuleIds);
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFA.h (183498 => 183499)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFA.h 2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WebCore/contentextensions/NFA.h 2015-04-28 19:40:19 UTC (rev 183499)
</span><span class="lines">@@ -38,8 +38,6 @@
</span><span class="cx">
</span><span class="cx"> class NFAToDFA;
</span><span class="cx">
</span><del>-typedef HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> ActionSet;
-
</del><span class="cx"> // The NFA provides a way to build a NFA graph with characters or epsilon as transitions.
</span><span class="cx"> // The nodes are accessed through an identifier.
</span><span class="cx"> class NFA {
</span><span class="lines">@@ -51,13 +49,13 @@
</span><span class="cx"> void addTransition(unsigned from, unsigned to, char character);
</span><span class="cx"> void addEpsilonTransition(unsigned from, unsigned to);
</span><span class="cx"> void addTransitionsOnAnyCharacter(unsigned from, unsigned to);
</span><del>- void setActions(unsigned node, const ActionSet& finalActions);
</del><ins>+ void setActions(unsigned node, const ActionList& finalActions);
</ins><span class="cx">
</span><span class="cx"> unsigned graphSize() const;
</span><span class="cx"> void restoreToGraphSize(unsigned);
</span><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><del>- void addRuleId(unsigned node, const ActionSet& ruleIds);
</del><ins>+ void addRuleId(unsigned node, const ActionList& ruleIds);
</ins><span class="cx">
</span><span class="cx"> void debugPrintDot() const;
</span><span class="cx"> #else
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFANodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFANode.h (183498 => 183499)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFANode.h 2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WebCore/contentextensions/NFANode.h 2015-04-28 19:40:19 UTC (rev 183499)
</span><span class="lines">@@ -39,6 +39,7 @@
</span><span class="cx">
</span><span class="cx"> // A NFANode abstract the transition table out of a NFA state.
</span><span class="cx">
</span><ins>+typedef Vector<uint64_t, 0, WTF::CrashOnOverflow, 1> ActionList;
</ins><span class="cx"> typedef HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> NFANodeIndexSet;
</span><span class="cx"> typedef HashMap<uint16_t, NFANodeIndexSet, DefaultHash<uint16_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint16_t>> NFANodeTransitions;
</span><span class="cx">
</span><span class="lines">@@ -47,7 +48,7 @@
</span><span class="cx"> HashMap<uint16_t, NFANodeIndexSet, DefaultHash<uint16_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint16_t>> transitions;
</span><span class="cx"> NFANodeIndexSet transitionsOnAnyCharacter;
</span><span class="cx">
</span><del>- Vector<uint64_t> finalRuleIds;
</del><ins>+ ActionList finalRuleIds;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsTermh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/Term.h (183498 => 183499)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/Term.h 2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WebCore/contentextensions/Term.h 2015-04-28 19:40:19 UTC (rev 183499)
</span><span class="lines">@@ -83,7 +83,7 @@
</span><span class="cx">
</span><span class="cx"> void quantify(const AtomQuantifier&);
</span><span class="cx">
</span><del>- unsigned generateGraph(NFA&, unsigned start, const ActionSet& finalActions) const;
</del><ins>+ unsigned generateGraph(NFA&, unsigned start, const ActionList& finalActions) const;
</ins><span class="cx">
</span><span class="cx"> bool isEndOfLineAssertion() const;
</span><span class="cx">
</span><span class="lines">@@ -335,7 +335,7 @@
</span><span class="cx"> m_quantifier = quantifier;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-inline unsigned Term::Term::generateGraph(NFA& nfa, unsigned start, const ActionSet& finalActions) const
</del><ins>+inline unsigned Term::Term::generateGraph(NFA& nfa, unsigned start, const ActionList& finalActions) const
</ins><span class="cx"> {
</span><span class="cx"> ASSERT(isValid());
</span><span class="cx">
</span><span class="lines">@@ -581,7 +581,7 @@
</span><span class="cx"> case TermType::Group: {
</span><span class="cx"> unsigned lastTarget = source;
</span><span class="cx"> for (const Term& term : m_atomData.group.terms)
</span><del>- lastTarget = term.generateGraph(nfa, lastTarget, ActionSet());
</del><ins>+ lastTarget = term.generateGraph(nfa, lastTarget, ActionList());
</ins><span class="cx"> return lastTarget;
</span><span class="cx"> }
</span><span class="cx"> }
</span></span></pre>
</div>
</div>
</body>
</html>