<!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>[186375] trunk/Source/WebCore</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/186375">186375</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2015-07-06 14:07:31 -0700 (Mon, 06 Jul 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Reduce the memory usage of the prefix tree
https://bugs.webkit.org/show_bug.cgi?id=146615
Reviewed by Sam Weinig.
This patch introduces two little changes that reduces the size
of the prefix tree by about 40%.
First, the Terms are interned. The new class CombinedFiltersAlphabet
takes care of keeping a unique version of each term for use
by the CombinedURLFilters.
Since each Term is fairly big but we have a small number of
unique term, we significantly reduce the edge size.
Second, the actions are no longer stored on each Vertex.
They are now stored on the side, in a HashMap indexed by
their Vertex.
This works well because the Actions are sparse over the tree.
Typically, only the leaves have actions. Internal vertices
sometime get actions but that's uncommon.
---
The next step to reduce the memory footprint would be to
make PrefixTreeVertex into a custom packed structure instead
of using a Vector.
Such change is very invasive and more error prone so I decided
against it for this patch.
* WebCore.xcodeproj/project.pbxproj:
* contentextensions/CombinedFiltersAlphabet.cpp: Copied from Source/WebCore/contentextensions/CombinedURLFilters.h.
(WebCore::ContentExtensions::TermCreatorTranslator::hash):
(WebCore::ContentExtensions::TermCreatorTranslator::equal):
(WebCore::ContentExtensions::TermCreatorTranslator::translate):
(WebCore::ContentExtensions::CombinedFiltersAlphabet::interned):
(WebCore::ContentExtensions::CombinedFiltersAlphabet::memoryUsed):
* contentextensions/CombinedFiltersAlphabet.h: Copied from Source/WebCore/contentextensions/CombinedURLFilters.h.
(WebCore::ContentExtensions::CombinedFiltersAlphabet::TermPointerHash::hash):
(WebCore::ContentExtensions::CombinedFiltersAlphabet::TermPointerHash::equal):
* contentextensions/CombinedURLFilters.cpp:
(WebCore::ContentExtensions::recursiveMemoryUsed):
(WebCore::ContentExtensions::CombinedURLFilters::memoryUsed):
(WebCore::ContentExtensions::prefixTreeVertexToString):
(WebCore::ContentExtensions::recursivePrint):
(WebCore::ContentExtensions::CombinedURLFilters::addPattern):
(WebCore::ContentExtensions::generateNFAForSubtree):
(WebCore::ContentExtensions::CombinedURLFilters::processNFAs):
* contentextensions/CombinedURLFilters.h:
* contentextensions/ContentExtensionsDebugging.h:
* contentextensions/Term.h:
(WebCore::ContentExtensions::Term::isValid):
(WebCore::ContentExtensions::Term::destroy):
(WebCore::ContentExtensions::Term::memoryUsed):
(WebCore::ContentExtensions::Term::toString): Deleted.
(WebCore::ContentExtensions::TermHash::hash): Deleted.
(WebCore::ContentExtensions::TermHash::equal): Deleted.
(WebCore::ContentExtensions::Term::Term): Deleted.
(WebCore::ContentExtensions::Term::isKnownToMatchAnyString): Deleted.
(WebCore::ContentExtensions::Term::hasFixedLength): Deleted.
(WebCore::ContentExtensions::Term::operator==): Deleted.
(WebCore::ContentExtensions::Term::hash): Deleted.
(WebCore::ContentExtensions::Term::isDeletedValue): Deleted.
(WebCore::ContentExtensions::Term::isUniversalTransition): Deleted.
(WebCore::ContentExtensions::Term::generateSubgraphForAtom): Deleted.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCoreWebCorexcodeprojprojectpbxproj">trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsCombinedURLFilterscpp">trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsCombinedURLFiltersh">trunk/Source/WebCore/contentextensions/CombinedURLFilters.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsTermh">trunk/Source/WebCore/contentextensions/Term.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceWebCorecontentextensionsCombinedFiltersAlphabetcpp">trunk/Source/WebCore/contentextensions/CombinedFiltersAlphabet.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsCombinedFiltersAlphabeth">trunk/Source/WebCore/contentextensions/CombinedFiltersAlphabet.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (186374 => 186375)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog        2015-07-06 21:06:30 UTC (rev 186374)
+++ trunk/Source/WebCore/ChangeLog        2015-07-06 21:07:31 UTC (rev 186375)
</span><span class="lines">@@ -1,5 +1,75 @@
</span><span class="cx"> 2015-07-06 Benjamin Poulain <benjamin@webkit.org>
</span><span class="cx">
</span><ins>+ Reduce the memory usage of the prefix tree
+ https://bugs.webkit.org/show_bug.cgi?id=146615
+
+ Reviewed by Sam Weinig.
+
+ This patch introduces two little changes that reduces the size
+ of the prefix tree by about 40%.
+
+ First, the Terms are interned. The new class CombinedFiltersAlphabet
+ takes care of keeping a unique version of each term for use
+ by the CombinedURLFilters.
+
+ Since each Term is fairly big but we have a small number of
+ unique term, we significantly reduce the edge size.
+
+ Second, the actions are no longer stored on each Vertex.
+ They are now stored on the side, in a HashMap indexed by
+ their Vertex.
+
+ This works well because the Actions are sparse over the tree.
+ Typically, only the leaves have actions. Internal vertices
+ sometime get actions but that's uncommon.
+
+ ---
+
+ The next step to reduce the memory footprint would be to
+ make PrefixTreeVertex into a custom packed structure instead
+ of using a Vector.
+
+ Such change is very invasive and more error prone so I decided
+ against it for this patch.
+
+ * WebCore.xcodeproj/project.pbxproj:
+ * contentextensions/CombinedFiltersAlphabet.cpp: Copied from Source/WebCore/contentextensions/CombinedURLFilters.h.
+ (WebCore::ContentExtensions::TermCreatorTranslator::hash):
+ (WebCore::ContentExtensions::TermCreatorTranslator::equal):
+ (WebCore::ContentExtensions::TermCreatorTranslator::translate):
+ (WebCore::ContentExtensions::CombinedFiltersAlphabet::interned):
+ (WebCore::ContentExtensions::CombinedFiltersAlphabet::memoryUsed):
+ * contentextensions/CombinedFiltersAlphabet.h: Copied from Source/WebCore/contentextensions/CombinedURLFilters.h.
+ (WebCore::ContentExtensions::CombinedFiltersAlphabet::TermPointerHash::hash):
+ (WebCore::ContentExtensions::CombinedFiltersAlphabet::TermPointerHash::equal):
+ * contentextensions/CombinedURLFilters.cpp:
+ (WebCore::ContentExtensions::recursiveMemoryUsed):
+ (WebCore::ContentExtensions::CombinedURLFilters::memoryUsed):
+ (WebCore::ContentExtensions::prefixTreeVertexToString):
+ (WebCore::ContentExtensions::recursivePrint):
+ (WebCore::ContentExtensions::CombinedURLFilters::addPattern):
+ (WebCore::ContentExtensions::generateNFAForSubtree):
+ (WebCore::ContentExtensions::CombinedURLFilters::processNFAs):
+ * contentextensions/CombinedURLFilters.h:
+ * contentextensions/ContentExtensionsDebugging.h:
+ * contentextensions/Term.h:
+ (WebCore::ContentExtensions::Term::isValid):
+ (WebCore::ContentExtensions::Term::destroy):
+ (WebCore::ContentExtensions::Term::memoryUsed):
+ (WebCore::ContentExtensions::Term::toString): Deleted.
+ (WebCore::ContentExtensions::TermHash::hash): Deleted.
+ (WebCore::ContentExtensions::TermHash::equal): Deleted.
+ (WebCore::ContentExtensions::Term::Term): Deleted.
+ (WebCore::ContentExtensions::Term::isKnownToMatchAnyString): Deleted.
+ (WebCore::ContentExtensions::Term::hasFixedLength): Deleted.
+ (WebCore::ContentExtensions::Term::operator==): Deleted.
+ (WebCore::ContentExtensions::Term::hash): Deleted.
+ (WebCore::ContentExtensions::Term::isDeletedValue): Deleted.
+ (WebCore::ContentExtensions::Term::isUniversalTransition): Deleted.
+ (WebCore::ContentExtensions::Term::generateSubgraphForAtom): Deleted.
+
+2015-07-06 Benjamin Poulain <benjamin@webkit.org>
+
</ins><span class="cx"> [Content Extensions] Make the DFA transitions ranges instead of characters
</span><span class="cx"> https://bugs.webkit.org/show_bug.cgi?id=146575
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCoreWebCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (186374 => 186375)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj        2015-07-06 21:06:30 UTC (rev 186374)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj        2015-07-06 21:07:31 UTC (rev 186375)
</span><span class="lines">@@ -1034,7 +1034,7 @@
</span><span class="cx">                 26D4E8461B42539D00E033A2 /* DFANode.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26D4E8451B42539D00E033A2 /* DFANode.cpp */; };
</span><span class="cx">                 26E944D81AC4B2DD007B85B5 /* CombinedURLFilters.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26E944D41AC4B2DD007B85B5 /* CombinedURLFilters.cpp */; };
</span><span class="cx">                 26E944D91AC4B2DD007B85B5 /* CombinedURLFilters.h in Headers */ = {isa = PBXBuildFile; fileRef = 26E944D51AC4B2DD007B85B5 /* CombinedURLFilters.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><del>-                26E944DD1AC4B4EA007B85B5 /* Term.h in Headers */ = {isa = PBXBuildFile; fileRef = 26E944DC1AC4B4EA007B85B5 /* Term.h */; };
</del><ins>+                26E944DD1AC4B4EA007B85B5 /* Term.h in Headers */ = {isa = PBXBuildFile; fileRef = 26E944DC1AC4B4EA007B85B5 /* Term.h */; settings = {ATTRIBUTES = (Private, ); }; };
</ins><span class="cx">                 26E98A10130A9FCA008EB7B2 /* TextCodecASCIIFastPath.h in Headers */ = {isa = PBXBuildFile; fileRef = 26E98A0F130A9FCA008EB7B2 /* TextCodecASCIIFastPath.h */; };
</span><span class="cx">                 26F0C8971A2E724B002794F8 /* ContentExtensionParser.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26F0C8951A2E724B002794F8 /* ContentExtensionParser.cpp */; };
</span><span class="cx">                 26F0C8981A2E724B002794F8 /* ContentExtensionParser.h in Headers */ = {isa = PBXBuildFile; fileRef = 26F0C8961A2E724B002794F8 /* ContentExtensionParser.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="lines">@@ -1599,6 +1599,8 @@
</span><span class="cx">                 43B9336A13B261B1004584BF /* SVGAnimatedPointList.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 43B9336813B261B1004584BF /* SVGAnimatedPointList.cpp */; };
</span><span class="cx">                 43C092BC12D9E4EE00A989C3 /* RenderSVGForeignObject.h in Headers */ = {isa = PBXBuildFile; fileRef = 43C092BA12D9E4EE00A989C3 /* RenderSVGForeignObject.h */; };
</span><span class="cx">                 43D2597713C816F400608559 /* ImageBuffer.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 43D2597613C816F400608559 /* ImageBuffer.cpp */; };
</span><ins>+                43EDD67E1B485DBF00640E75 /* CombinedFiltersAlphabet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 43EDD67C1B485DBF00640E75 /* CombinedFiltersAlphabet.cpp */; };
+                43EDD67F1B485DBF00640E75 /* CombinedFiltersAlphabet.h in Headers */ = {isa = PBXBuildFile; fileRef = 43EDD67D1B485DBF00640E75 /* CombinedFiltersAlphabet.h */; settings = {ATTRIBUTES = (Private, ); }; };
</ins><span class="cx">                 43F6FD9613BCD0B100224052 /* SVGAnimatedInteger.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 43F6FD9513BCD0B100224052 /* SVGAnimatedInteger.cpp */; };
</span><span class="cx">                 4415292E0E1AE8A000C4A2D0 /* HTMLPlugInImageElement.h in Headers */ = {isa = PBXBuildFile; fileRef = 4415292C0E1AE8A000C4A2D0 /* HTMLPlugInImageElement.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx">                 4415292F0E1AE8A000C4A2D0 /* HTMLPlugInImageElement.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 4415292D0E1AE8A000C4A2D0 /* HTMLPlugInImageElement.cpp */; };
</span><span class="lines">@@ -8806,6 +8808,8 @@
</span><span class="cx">                 43C092B912D9E4EE00A989C3 /* RenderSVGForeignObject.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RenderSVGForeignObject.cpp; sourceTree = "<group>"; };
</span><span class="cx">                 43C092BA12D9E4EE00A989C3 /* RenderSVGForeignObject.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RenderSVGForeignObject.h; sourceTree = "<group>"; };
</span><span class="cx">                 43D2597613C816F400608559 /* ImageBuffer.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ImageBuffer.cpp; sourceTree = "<group>"; };
</span><ins>+                43EDD67C1B485DBF00640E75 /* CombinedFiltersAlphabet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CombinedFiltersAlphabet.cpp; sourceTree = "<group>"; };
+                43EDD67D1B485DBF00640E75 /* CombinedFiltersAlphabet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CombinedFiltersAlphabet.h; sourceTree = "<group>"; };
</ins><span class="cx">                 43F6FD9513BCD0B100224052 /* SVGAnimatedInteger.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SVGAnimatedInteger.cpp; sourceTree = "<group>"; };
</span><span class="cx">                 4415292C0E1AE8A000C4A2D0 /* HTMLPlugInImageElement.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = HTMLPlugInImageElement.h; sourceTree = "<group>"; };
</span><span class="cx">                 4415292D0E1AE8A000C4A2D0 /* HTMLPlugInImageElement.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = HTMLPlugInImageElement.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -15677,6 +15681,8 @@
</span><span class="cx">                 26F0C8901A2D79CB002794F8 /* contentextensions */ = {
</span><span class="cx">                         isa = PBXGroup;
</span><span class="cx">                         children = (
</span><ins>+                                43EDD67C1B485DBF00640E75 /* CombinedFiltersAlphabet.cpp */,
+                                43EDD67D1B485DBF00640E75 /* CombinedFiltersAlphabet.h */,
</ins><span class="cx">                                 26E944D41AC4B2DD007B85B5 /* CombinedURLFilters.cpp */,
</span><span class="cx">                                 26E944D51AC4B2DD007B85B5 /* CombinedURLFilters.h */,
</span><span class="cx">                                 7C93F3471AA6BA5E00A98BAB /* CompiledContentExtension.cpp */,
</span><span class="lines">@@ -26001,6 +26007,7 @@
</span><span class="cx">                                 6B3480940EEF50D400AC1B41 /* NativeImagePtr.h in Headers */,
</span><span class="cx">                                 E10B9B6C0B747599003ED890 /* NativeXPathNSResolver.h in Headers */,
</span><span class="cx">                                 93CCF0270AF6C52900018E89 /* NavigationAction.h in Headers */,
</span><ins>+                                43EDD67F1B485DBF00640E75 /* CombinedFiltersAlphabet.h in Headers */,
</ins><span class="cx">                                 979F43D41075E44A0000F83B /* NavigationScheduler.h in Headers */,
</span><span class="cx">                                 A9C6E5A60D746458006442E9 /* Navigator.h in Headers */,
</span><span class="cx">                                 E12719C70EEEC16800F61213 /* NavigatorBase.h in Headers */,
</span><span class="lines">@@ -28606,6 +28613,7 @@
</span><span class="cx">                                 516953971329A3C800B92D04 /* IconDatabaseBase.cpp in Sources */,
</span><span class="cx">                                 FED13D400CEA939400D89466 /* IconIOS.mm in Sources */,
</span><span class="cx">                                 513F14530AB634C400094DDF /* IconLoader.cpp in Sources */,
</span><ins>+                                43EDD67E1B485DBF00640E75 /* CombinedFiltersAlphabet.cpp in Sources */,
</ins><span class="cx">                                 B275358E0B053A66002CE64F /* IconMac.mm in Sources */,
</span><span class="cx">                                 51E1ECC00C91C90400DC255B /* IconRecord.cpp in Sources */,
</span><span class="cx">                                 51D719B9181106E00016DC51 /* IDBAny.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsCombinedFiltersAlphabetcppfromrev186374trunkSourceWebCorecontentextensionsCombinedURLFiltersh"></a>
<div class="copfile"><h4>Copied: trunk/Source/WebCore/contentextensions/CombinedFiltersAlphabet.cpp (from rev 186374, trunk/Source/WebCore/contentextensions/CombinedURLFilters.h) (0 => 186375)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/CombinedFiltersAlphabet.cpp         (rev 0)
+++ trunk/Source/WebCore/contentextensions/CombinedFiltersAlphabet.cpp        2015-07-06 21:07:31 UTC (rev 186375)
</span><span class="lines">@@ -0,0 +1,82 @@
</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 "CombinedFiltersAlphabet.h"
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+struct TermCreatorInput {
+ const Term& term;
+ Vector<std::unique_ptr<Term>>& internedTermsStorage;
+};
+
+struct TermCreatorTranslator {
+ static unsigned hash(const TermCreatorInput& input)
+ {
+ return input.term.hash();
+ }
+
+ static inline bool equal(const Term* term, const TermCreatorInput& input)
+ {
+ return *term == input.term;
+ }
+
+ static void translate(const Term*& location, const TermCreatorInput& input, unsigned)
+ {
+ std::unique_ptr<Term> newUniqueTerm(new Term(input.term));
+ location = newUniqueTerm.get();
+ input.internedTermsStorage.append(WTF::move(newUniqueTerm));
+ }
+};
+
+const Term* CombinedFiltersAlphabet::interned(const Term& term)
+{
+ TermCreatorInput input { term, m_internedTermsStorage };
+ auto addResult = m_uniqueTerms.add<TermCreatorTranslator>(input);
+ return *addResult.iterator;
+}
+
+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+size_t CombinedFiltersAlphabet::memoryUsed() const
+{
+ size_t termsSize = 0;
+ for (const auto& termPointer : m_internedTermsStorage)
+ termsSize += termPointer->memoryUsed();
+ return sizeof(CombinedFiltersAlphabet)
+ + termsSize
+ + m_uniqueTerms.capacity() * sizeof(Term*)
+ + m_internedTermsStorage.capacity() * sizeof(std::unique_ptr<Term>);
+}
+#endif
+
+} // namespace ContentExtensions
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
</ins></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsCombinedFiltersAlphabethfromrev186374trunkSourceWebCorecontentextensionsCombinedURLFiltersh"></a>
<div class="copfile"><h4>Copied: trunk/Source/WebCore/contentextensions/CombinedFiltersAlphabet.h (from rev 186374, trunk/Source/WebCore/contentextensions/CombinedURLFilters.h) (0 => 186375)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/CombinedFiltersAlphabet.h         (rev 0)
+++ trunk/Source/WebCore/contentextensions/CombinedFiltersAlphabet.h        2015-07-06 21:07:31 UTC (rev 186375)
</span><span class="lines">@@ -0,0 +1,66 @@
</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.
+ */
+
+#ifndef CombinedFiltersAlphabet_h
+#define CombinedFiltersAlphabet_h
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+#include "ContentExtensionsDebugging.h"
+#include "Term.h"
+#include <wtf/HashSet.h>
+#include <wtf/Vector.h>
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+class CombinedFiltersAlphabet {
+public:
+ const Term* interned(const Term&);
+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+ size_t memoryUsed() const;
+#endif
+
+private:
+ struct TermPointerHash {
+ static unsigned hash(const Term* key) { return key->hash(); }
+ static inline bool equal(const Term* a, const Term* b)
+ {
+ return *a == *b;
+ }
+ static const bool safeToCompareToEmptyOrDeleted = false;
+ };
+
+ HashSet<const Term*, TermPointerHash> m_uniqueTerms;
+ Vector<std::unique_ptr<Term>> m_internedTermsStorage;
+};
+
+} // namespace ContentExtensions
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
+
+#endif // CombinedFiltersAlphabet_h
</ins></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsCombinedURLFilterscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp (186374 => 186375)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp        2015-07-06 21:06:30 UTC (rev 186374)
+++ trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp        2015-07-06 21:07:31 UTC (rev 186375)
</span><span class="lines">@@ -38,7 +38,7 @@
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><span class="cx"> struct PrefixTreeEdge {
</span><del>- Term term;
</del><ins>+ const Term* term;
</ins><span class="cx"> std::unique_ptr<PrefixTreeVertex> child;
</span><span class="cx"> };
</span><span class="cx">
</span><span class="lines">@@ -46,15 +46,13 @@
</span><span class="cx">
</span><span class="cx"> struct PrefixTreeVertex {
</span><span class="cx"> PrefixTreeEdges edges;
</span><del>- ActionList finalActions;
</del><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
</span><span class="cx"> static size_t recursiveMemoryUsed(const PrefixTreeVertex& vertex)
</span><span class="cx"> {
</span><span class="cx"> size_t size = sizeof(PrefixTreeVertex)
</span><del>- + vertex.edges.capacity() * sizeof(PrefixTreeEdge)
- + vertex.finalActions.capacity() * sizeof(uint64_t);
</del><ins>+ + vertex.edges.capacity() * sizeof(PrefixTreeEdge);
</ins><span class="cx"> for (const auto& edge : vertex.edges) {
</span><span class="cx"> ASSERT(edge.child);
</span><span class="cx"> size += recursiveMemoryUsed(*edge.child.get());
</span><span class="lines">@@ -65,7 +63,17 @@
</span><span class="cx"> size_t CombinedURLFilters::memoryUsed() const
</span><span class="cx"> {
</span><span class="cx"> ASSERT(m_prefixTreeRoot);
</span><del>- return recursiveMemoryUsed(*m_prefixTreeRoot.get());
</del><ins>+
+ size_t actionsSize = 0;
+ for (const auto& slot : m_actions)
+ actionsSize += slot.value.capacity() * sizeof(uint64_t);
+
+ return sizeof(CombinedURLFilters)
+ + m_alphabet.memoryUsed()
+ + recursiveMemoryUsed(*m_prefixTreeRoot.get())
+ + sizeof(HashMap<PrefixTreeVertex*, ActionList>)
+ + m_actions.capacity() * (sizeof(PrefixTreeVertex*) + sizeof(ActionList))
+ + actionsSize;
</ins><span class="cx"> }
</span><span class="cx"> #endif
</span><span class="cx">
</span><span class="lines">@@ -76,9 +84,13 @@
</span><span class="cx"> while (depth--)
</span><span class="cx"> builder.append(" ");
</span><span class="cx"> builder.append("vertex actions: ");
</span><del>- for (auto action : vertex.finalActions) {
- builder.appendNumber(action);
- builder.append(',');
</del><ins>+
+ auto actionsSlot = m_actions.find(&vertex);
+ if (actionsSlot != m_actions.end()) {
+ for (auto action : *actionsSlot->value) {
+ builder.appendNumber(action);
+ builder.append(',');
+ }
</ins><span class="cx"> }
</span><span class="cx"> builder.append('\n');
</span><span class="cx"> return builder.toString();
</span><span class="lines">@@ -92,7 +104,7 @@
</span><span class="cx"> for (unsigned i = 0; i < depth * 2; ++i)
</span><span class="cx"> builder.append(' ');
</span><span class="cx"> builder.append("vertex edge: ");
</span><del>- builder.append(edge.term.toString());
</del><ins>+ builder.append(edge.term->toString());
</ins><span class="cx"> builder.append('\n');
</span><span class="cx"> dataLogF("%s", builder.toString().utf8().data());
</span><span class="cx"> ASSERT(edge.child);
</span><span class="lines">@@ -175,7 +187,7 @@
</span><span class="cx"> for (const Term& term : pattern) {
</span><span class="cx"> size_t nextEntryIndex = WTF::notFound;
</span><span class="cx"> for (size_t i = 0; i < lastPrefixTree->edges.size(); ++i) {
</span><del>- if (lastPrefixTree->edges[i].term == term) {
</del><ins>+ if (*lastPrefixTree->edges[i].term == term) {
</ins><span class="cx"> nextEntryIndex = i;
</span><span class="cx"> break;
</span><span class="cx"> }
</span><span class="lines">@@ -183,17 +195,18 @@
</span><span class="cx"> if (nextEntryIndex != WTF::notFound)
</span><span class="cx"> lastPrefixTree = lastPrefixTree->edges[nextEntryIndex].child.get();
</span><span class="cx"> else {
</span><del>- lastPrefixTree->edges.append(PrefixTreeEdge({term, std::make_unique<PrefixTreeVertex>()}));
</del><ins>+ lastPrefixTree->edges.append(PrefixTreeEdge({m_alphabet.interned(term), std::make_unique<PrefixTreeVertex>()}));
</ins><span class="cx"> lastPrefixTree = lastPrefixTree->edges.last().child.get();
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>- ActionList& actions = lastPrefixTree->finalActions;
</del><ins>+ auto addResult = m_actions.add(lastPrefixTree, ActionList());
+ ActionList& actions = addResult.iterator->value;
</ins><span class="cx"> if (actions.find(actionId) == WTF::notFound)
</span><span class="cx"> actions.append(actionId);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-static void generateNFAForSubtree(NFA& nfa, ImmutableCharNFANodeBuilder&& subtreeRoot, PrefixTreeVertex& root, size_t maxNFASize)
</del><ins>+static void generateNFAForSubtree(NFA& nfa, ImmutableCharNFANodeBuilder&& subtreeRoot, PrefixTreeVertex& root, HashMap<const PrefixTreeVertex*, ActionList>& actions, size_t maxNFASize)
</ins><span class="cx"> {
</span><span class="cx"> // This recurses the subtree of the prefix tree.
</span><span class="cx"> // For each edge that has fixed length (no quantifiers like ?, *, or +) it generates the nfa graph,
</span><span class="lines">@@ -233,26 +246,27 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Quantified edges in the subtree will be a part of another NFA.
</span><del>- if (!edge.term.hasFixedLength()) {
</del><ins>+ if (!edge.term->hasFixedLength()) {
</ins><span class="cx"> stack.last().edgeIndex++;
</span><span class="cx"> continue;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- ImmutableCharNFANodeBuilder newNode = edge.term.generateGraph(nfa, stack.last().nfaNode, edge.child->finalActions);
</del><ins>+
+ ImmutableCharNFANodeBuilder newNode = edge.term->generateGraph(nfa, stack.last().nfaNode, actions.get(edge.child.get()));
</ins><span class="cx"> ASSERT(edge.child.get());
</span><span class="cx"> stack.append(ActiveSubtree(*edge.child.get(), WTF::move(newNode), 0));
</span><span class="cx"> } else {
</span><span class="cx"> ASSERT(edgeIndex == vertex.edges.size());
</span><span class="cx"> vertex.edges.removeAllMatching([](PrefixTreeEdge& edge)
</span><span class="cx"> {
</span><del>- return edge.term.isDeletedValue();
</del><ins>+ return !edge.term;
</ins><span class="cx"> });
</span><span class="cx"> stack.removeLast();
</span><span class="cx"> if (!stack.isEmpty()) {
</span><span class="cx"> auto& activeSubtree = stack.last();
</span><span class="cx"> auto& edge = activeSubtree.vertex.edges[stack.last().edgeIndex];
</span><span class="cx"> if (edge.child->edges.isEmpty())
</span><del>- edge.term = Term(Term::DeletedValue); // Mark this leaf for deleting.
</del><ins>+ edge.term = nullptr; // Mark this leaf for deleting.
</ins><span class="cx"> activeSubtree.edgeIndex++;
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="lines">@@ -281,7 +295,7 @@
</span><span class="cx"> // Find the prefix root for this NFA. This is the vertex after the last term with a quantifier if there is one,
</span><span class="cx"> // or the root if there are no quantifiers left.
</span><span class="cx"> while (stack.size() > 1) {
</span><del>- if (!stack[stack.size() - 2]->edges.last().term.hasFixedLength())
</del><ins>+ if (!stack[stack.size() - 2]->edges.last().term->hasFixedLength())
</ins><span class="cx"> break;
</span><span class="cx"> stack.removeLast();
</span><span class="cx"> }
</span><span class="lines">@@ -294,13 +308,13 @@
</span><span class="cx"> ImmutableCharNFANodeBuilder lastNode(nfa);
</span><span class="cx"> for (unsigned i = 0; i < stack.size() - 1; ++i) {
</span><span class="cx"> const PrefixTreeEdge& edge = stack[i]->edges.last();
</span><del>- ImmutableCharNFANodeBuilder newNode = edge.term.generateGraph(nfa, lastNode, edge.child->finalActions);
</del><ins>+ ImmutableCharNFANodeBuilder newNode = edge.term->generateGraph(nfa, lastNode, m_actions.get(edge.child.get()));
</ins><span class="cx"> lastNode = WTF::move(newNode);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Put the non-quantified vertices in the subtree into the NFA and delete them.
</span><span class="cx"> ASSERT(stack.last());
</span><del>- generateNFAForSubtree(nfa, WTF::move(lastNode), *stack.last(), maxNFASize);
</del><ins>+ generateNFAForSubtree(nfa, WTF::move(lastNode), *stack.last(), m_actions, maxNFASize);
</ins><span class="cx"> }
</span><span class="cx"> nfa.finalize();
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsCombinedURLFiltersh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/CombinedURLFilters.h (186374 => 186375)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/CombinedURLFilters.h        2015-07-06 21:06:30 UTC (rev 186374)
+++ trunk/Source/WebCore/contentextensions/CombinedURLFilters.h        2015-07-06 21:07:31 UTC (rev 186375)
</span><span class="lines">@@ -28,6 +28,7 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(CONTENT_EXTENSIONS)
</span><span class="cx">
</span><ins>+#include "CombinedFiltersAlphabet.h"
</ins><span class="cx"> #include "ContentExtensionsDebugging.h"
</span><span class="cx"> #include "NFA.h"
</span><span class="cx"> #include <wtf/Forward.h>
</span><span class="lines">@@ -37,7 +38,6 @@
</span><span class="cx">
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><del>-class Term;
</del><span class="cx"> struct PrefixTreeVertex;
</span><span class="cx">
</span><span class="cx"> class WEBCORE_EXPORT CombinedURLFilters {
</span><span class="lines">@@ -59,7 +59,9 @@
</span><span class="cx"> #endif
</span><span class="cx">
</span><span class="cx"> private:
</span><ins>+ CombinedFiltersAlphabet m_alphabet;
</ins><span class="cx"> std::unique_ptr<PrefixTreeVertex> m_prefixTreeRoot;
</span><ins>+ HashMap<const PrefixTreeVertex*, ActionList> m_actions;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } // namespace ContentExtensions
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsTermh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/Term.h (186374 => 186375)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/Term.h        2015-07-06 21:06:30 UTC (rev 186374)
+++ trunk/Source/WebCore/contentextensions/Term.h        2015-07-06 21:07:31 UTC (rev 186375)
</span><span class="lines">@@ -71,9 +71,6 @@
</span><span class="cx"> enum EmptyValueTag { EmptyValue };
</span><span class="cx"> Term(EmptyValueTag);
</span><span class="cx">
</span><del>- enum DeletedValueTag { DeletedValue };
- Term(DeletedValueTag);
-
</del><span class="cx"> ~Term();
</span><span class="cx">
</span><span class="cx"> bool isValid() const;
</span><span class="lines">@@ -107,11 +104,14 @@
</span><span class="cx"> unsigned hash() const;
</span><span class="cx">
</span><span class="cx"> bool isEmptyValue() const;
</span><del>- bool isDeletedValue() const;
</del><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
</span><span class="cx"> String toString() const;
</span><span class="cx"> #endif
</span><ins>+
+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+ size_t memoryUsed() const;
+#endif
</ins><span class="cx">
</span><span class="cx"> private:
</span><span class="cx"> // This is exact for character sets but conservative for groups.
</span><span class="lines">@@ -124,7 +124,6 @@
</span><span class="cx">
</span><span class="cx"> enum class TermType : uint8_t {
</span><span class="cx"> Empty,
</span><del>- Deleted,
</del><span class="cx"> CharacterSet,
</span><span class="cx"> Group
</span><span class="cx"> };
</span><span class="lines">@@ -230,8 +229,6 @@
</span><span class="cx"> switch (m_termType) {
</span><span class="cx"> case TermType::Empty:
</span><span class="cx"> return "(Empty)";
</span><del>- case TermType::Deleted:
- return "(Deleted)";
</del><span class="cx"> case TermType::CharacterSet: {
</span><span class="cx"> StringBuilder builder;
</span><span class="cx"> builder.append('[');
</span><span class="lines">@@ -262,15 +259,7 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> #endif
</span><del>-
-struct TermHash {
- static unsigned hash(const Term& term) { return term.hash(); }
- static bool equal(const Term& a, const Term& b) { return a == b; }
- static const bool safeToCompareToEmptyOrDeleted = true;
-};
</del><span class="cx">
</span><del>-struct TermHashTraits : public WTF::CustomHashTraits<Term> { };
-
</del><span class="cx"> inline Term::Term()
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="lines">@@ -316,7 +305,6 @@
</span><span class="cx"> {
</span><span class="cx"> switch (m_termType) {
</span><span class="cx"> case TermType::Empty:
</span><del>- case TermType::Deleted:
</del><span class="cx"> break;
</span><span class="cx"> case TermType::CharacterSet:
</span><span class="cx"> new (NotNull, &m_atomData.characterSet) CharacterSet(other.m_atomData.characterSet);
</span><span class="lines">@@ -333,7 +321,6 @@
</span><span class="cx"> {
</span><span class="cx"> switch (m_termType) {
</span><span class="cx"> case TermType::Empty:
</span><del>- case TermType::Deleted:
</del><span class="cx"> break;
</span><span class="cx"> case TermType::CharacterSet:
</span><span class="cx"> new (NotNull, &m_atomData.characterSet) CharacterSet(WTF::move(other.m_atomData.characterSet));
</span><span class="lines">@@ -350,11 +337,6 @@
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><del>-inline Term::Term(DeletedValueTag)
- : m_termType(TermType::Deleted)
-{
-}
-
</del><span class="cx"> inline Term::~Term()
</span><span class="cx"> {
</span><span class="cx"> destroy();
</span><span class="lines">@@ -362,7 +344,7 @@
</span><span class="cx">
</span><span class="cx"> inline bool Term::isValid() const
</span><span class="cx"> {
</span><del>- return m_termType != TermType::Empty && m_termType != TermType::Deleted;
</del><ins>+ return m_termType != TermType::Empty;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> inline void Term::addCharacter(UChar character, bool isCaseSensitive)
</span><span class="lines">@@ -471,7 +453,6 @@
</span><span class="cx">
</span><span class="cx"> switch (m_termType) {
</span><span class="cx"> case TermType::Empty:
</span><del>- case TermType::Deleted:
</del><span class="cx"> ASSERT_NOT_REACHED();
</span><span class="cx"> break;
</span><span class="cx"> case TermType::CharacterSet:
</span><span class="lines">@@ -513,7 +494,6 @@
</span><span class="cx">
</span><span class="cx"> switch (m_termType) {
</span><span class="cx"> case TermType::Empty:
</span><del>- case TermType::Deleted:
</del><span class="cx"> ASSERT_NOT_REACHED();
</span><span class="cx"> break;
</span><span class="cx"> case TermType::CharacterSet:
</span><span class="lines">@@ -552,7 +532,6 @@
</span><span class="cx">
</span><span class="cx"> switch (m_termType) {
</span><span class="cx"> case TermType::Empty:
</span><del>- case TermType::Deleted:
</del><span class="cx"> return true;
</span><span class="cx"> case TermType::CharacterSet:
</span><span class="cx"> return m_atomData.characterSet == other.m_atomData.characterSet;
</span><span class="lines">@@ -571,9 +550,6 @@
</span><span class="cx"> case TermType::Empty:
</span><span class="cx"> secondary = 52184393;
</span><span class="cx"> break;
</span><del>- case TermType::Deleted:
- secondary = 40342988;
- break;
</del><span class="cx"> case TermType::CharacterSet:
</span><span class="cx"> secondary = m_atomData.characterSet.hash();
</span><span class="cx"> break;
</span><span class="lines">@@ -589,18 +565,12 @@
</span><span class="cx"> return m_termType == TermType::Empty;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-inline bool Term::isDeletedValue() const
-{
- return m_termType == TermType::Deleted;
-}
-
</del><span class="cx"> inline bool Term::isUniversalTransition() const
</span><span class="cx"> {
</span><span class="cx"> ASSERT(isValid());
</span><span class="cx">
</span><span class="cx"> switch (m_termType) {
</span><span class="cx"> case TermType::Empty:
</span><del>- case TermType::Deleted:
</del><span class="cx"> ASSERT_NOT_REACHED();
</span><span class="cx"> break;
</span><span class="cx"> case TermType::CharacterSet:
</span><span class="lines">@@ -616,7 +586,6 @@
</span><span class="cx"> {
</span><span class="cx"> switch (m_termType) {
</span><span class="cx"> case TermType::Empty:
</span><del>- case TermType::Deleted:
</del><span class="cx"> ASSERT_NOT_REACHED();
</span><span class="cx"> return ImmutableCharNFANodeBuilder();
</span><span class="cx"> case TermType::CharacterSet: {
</span><span class="lines">@@ -676,7 +645,6 @@
</span><span class="cx"> {
</span><span class="cx"> switch (m_termType) {
</span><span class="cx"> case TermType::Empty:
</span><del>- case TermType::Deleted:
</del><span class="cx"> break;
</span><span class="cx"> case TermType::CharacterSet:
</span><span class="cx"> m_atomData.characterSet.~CharacterSet();
</span><span class="lines">@@ -685,9 +653,21 @@
</span><span class="cx"> m_atomData.group.~Group();
</span><span class="cx"> break;
</span><span class="cx"> }
</span><del>- m_termType = TermType::Deleted;
</del><ins>+ m_termType = TermType::Empty;
</ins><span class="cx"> }
</span><span class="cx">
</span><ins>+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+inline size_t Term::memoryUsed() const
+{
+ size_t extraMemory = 0;
+ if (m_termType == TermType::Group) {
+ for (const Term& term : m_atomData.group.terms)
+ extraMemory += term.memoryUsed();
+ }
+ return sizeof(Term) + extraMemory;
+}
+#endif
+
</ins><span class="cx"> } // namespace ContentExtensions
</span><span class="cx"> } // namespace WebCore
</span><span class="cx">
</span></span></pre>
</div>
</div>
</body>
</html>