<!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>[191424] 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/191424">191424</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-10-21 18:46:06 -0700 (Wed, 21 Oct 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Factor out the graph node worklists from DFG into WTF
https://bugs.webkit.org/show_bug.cgi?id=150411
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
Rewrite the DFGBlockWorklist.h file as a bunch of typedefs and aliases for things in
wtf/GraphNodeWorklist.h. Most users won't notice, except that some small things got
renamed. For example PreOrder becomes VisitOrder::Pre and item.block becomes item.node.
* CMakeLists.txt:
* JavaScriptCore.xcodeproj/project.pbxproj:
* dfg/DFGBlockWorklist.cpp: Removed.
* dfg/DFGBlockWorklist.h:
(JSC::DFG::BlockWorklist::notEmpty): Deleted.
(JSC::DFG::BlockWith::BlockWith): Deleted.
(JSC::DFG::BlockWith::operator bool): Deleted.
(JSC::DFG::ExtendedBlockWorklist::ExtendedBlockWorklist): Deleted.
(JSC::DFG::ExtendedBlockWorklist::forcePush): Deleted.
(JSC::DFG::ExtendedBlockWorklist::push): Deleted.
(JSC::DFG::ExtendedBlockWorklist::notEmpty): Deleted.
(JSC::DFG::ExtendedBlockWorklist::pop): Deleted.
(JSC::DFG::BlockWithOrder::BlockWithOrder): Deleted.
(JSC::DFG::BlockWithOrder::operator bool): Deleted.
(JSC::DFG::PostOrderBlockWorklist::push): Deleted.
(JSC::DFG::PostOrderBlockWorklist::notEmpty): Deleted.
* dfg/DFGDominators.cpp:
(JSC::DFG::Dominators::compute):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::blocksInPostOrder):
* dfg/DFGPrePostNumbering.cpp:
(JSC::DFG::PrePostNumbering::compute):
Source/WTF:
The new GraphNodeWorklist.h file is basically just the functionality from the old
DFGBlockWorklist.h, but templatized to work for any graph node type and any kind of graph
node set.
* WTF.xcodeproj/project.pbxproj:
* wtf/CMakeLists.txt:
* wtf/GraphNodeWorklist.h: Added.
(WTF::GraphNodeWorklist::push):
(WTF::GraphNodeWorklist::notEmpty):
(WTF::GraphNodeWorklist::pop):
(WTF::GraphNodeWith::GraphNodeWith):
(WTF::GraphNodeWith::operator bool):
(WTF::ExtendedGraphNodeWorklist::ExtendedGraphNodeWorklist):
(WTF::ExtendedGraphNodeWorklist::forcePush):
(WTF::ExtendedGraphNodeWorklist::push):
(WTF::ExtendedGraphNodeWorklist::notEmpty):
(WTF::ExtendedGraphNodeWorklist::pop):
(WTF::GraphNodeWithOrder::GraphNodeWithOrder):
(WTF::GraphNodeWithOrder::operator bool):
(WTF::PostOrderGraphNodeWorklist::PostOrderGraphNodeWorklist):
(WTF::PostOrderGraphNodeWorklist::~PostOrderGraphNodeWorklist):
(WTF::PostOrderGraphNodeWorklist::pushPre):
(WTF::PostOrderGraphNodeWorklist::pushPost):
(WTF::PostOrderGraphNodeWorklist::push):
(WTF::PostOrderGraphNodeWorklist::notEmpty):
(WTF::PostOrderGraphNodeWorklist::pop):
* wtf/HashTable.h:
(WTF::HashTableAddResult::HashTableAddResult):
(WTF::HashTableAddResult::operator bool):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreCMakeListstxt">trunk/Source/JavaScriptCore/CMakeLists.txt</a></li>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj">trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGBlockWorklisth">trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGDominatorscpp">trunk/Source/JavaScriptCore/dfg/DFGDominators.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGGraphcpp">trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGPrePostNumberingcpp">trunk/Source/JavaScriptCore/dfg/DFGPrePostNumbering.cpp</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFWTFxcodeprojprojectpbxproj">trunk/Source/WTF/WTF.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWTFwtfCMakeListstxt">trunk/Source/WTF/wtf/CMakeLists.txt</a></li>
<li><a href="#trunkSourceWTFwtfHashTableh">trunk/Source/WTF/wtf/HashTable.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceWTFwtfGraphNodeWorklisth">trunk/Source/WTF/wtf/GraphNodeWorklist.h</a></li>
</ul>
<h3>Removed Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoredfgDFGBlockWorklistcpp">trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/CMakeLists.txt (191423 => 191424)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/CMakeLists.txt 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/JavaScriptCore/CMakeLists.txt 2015-10-22 01:46:06 UTC (rev 191424)
</span><span class="lines">@@ -150,7 +150,6 @@
</span><span class="cx"> dfg/DFGBasicBlock.cpp
</span><span class="cx"> dfg/DFGBlockInsertionSet.cpp
</span><span class="cx"> dfg/DFGBlockSet.cpp
</span><del>- dfg/DFGBlockWorklist.cpp
</del><span class="cx"> dfg/DFGByteCodeParser.cpp
</span><span class="cx"> dfg/DFGCFAPhase.cpp
</span><span class="cx"> dfg/DFGCFGSimplificationPhase.cpp
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (191423 => 191424)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-10-22 01:46:06 UTC (rev 191424)
</span><span class="lines">@@ -1,3 +1,37 @@
</span><ins>+2015-10-21 Filip Pizlo <fpizlo@apple.com>
+
+ Factor out the graph node worklists from DFG into WTF
+ https://bugs.webkit.org/show_bug.cgi?id=150411
+
+ Reviewed by Geoffrey Garen.
+
+ Rewrite the DFGBlockWorklist.h file as a bunch of typedefs and aliases for things in
+ wtf/GraphNodeWorklist.h. Most users won't notice, except that some small things got
+ renamed. For example PreOrder becomes VisitOrder::Pre and item.block becomes item.node.
+
+ * CMakeLists.txt:
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * dfg/DFGBlockWorklist.cpp: Removed.
+ * dfg/DFGBlockWorklist.h:
+ (JSC::DFG::BlockWorklist::notEmpty): Deleted.
+ (JSC::DFG::BlockWith::BlockWith): Deleted.
+ (JSC::DFG::BlockWith::operator bool): Deleted.
+ (JSC::DFG::ExtendedBlockWorklist::ExtendedBlockWorklist): Deleted.
+ (JSC::DFG::ExtendedBlockWorklist::forcePush): Deleted.
+ (JSC::DFG::ExtendedBlockWorklist::push): Deleted.
+ (JSC::DFG::ExtendedBlockWorklist::notEmpty): Deleted.
+ (JSC::DFG::ExtendedBlockWorklist::pop): Deleted.
+ (JSC::DFG::BlockWithOrder::BlockWithOrder): Deleted.
+ (JSC::DFG::BlockWithOrder::operator bool): Deleted.
+ (JSC::DFG::PostOrderBlockWorklist::push): Deleted.
+ (JSC::DFG::PostOrderBlockWorklist::notEmpty): Deleted.
+ * dfg/DFGDominators.cpp:
+ (JSC::DFG::Dominators::compute):
+ * dfg/DFGGraph.cpp:
+ (JSC::DFG::Graph::blocksInPostOrder):
+ * dfg/DFGPrePostNumbering.cpp:
+ (JSC::DFG::PrePostNumbering::compute):
+
</ins><span class="cx"> 2015-10-21 Sukolsak Sakshuwong <sukolsak@gmail.com>
</span><span class="cx">
</span><span class="cx"> [INTL] Implement Intl.Collator.prototype.resolvedOptions ()
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (191423 => 191424)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-10-22 01:46:06 UTC (rev 191424)
</span><span class="lines">@@ -545,7 +545,6 @@
</span><span class="cx"> 0FC3CCFC19ADA410006AC72A /* DFGBlockMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF519ADA410006AC72A /* DFGBlockMap.h */; };
</span><span class="cx"> 0FC3CCFD19ADA410006AC72A /* DFGBlockMapInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */; };
</span><span class="cx"> 0FC3CCFE19ADA410006AC72A /* DFGBlockSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */; };
</span><del>- 0FC3CCFF19ADA410006AC72A /* DFGBlockWorklist.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC3CCF819ADA410006AC72A /* DFGBlockWorklist.cpp */; };
</del><span class="cx"> 0FC3CD0019ADA410006AC72A /* DFGBlockWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */; };
</span><span class="cx"> 0FC3CD0119ADA411006AC72A /* DFGNaiveDominators.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */; };
</span><span class="cx"> 0FC3CD0219ADA411006AC72A /* DFGNaiveDominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */; };
</span><span class="lines">@@ -2410,7 +2409,6 @@
</span><span class="cx"> 0FC3CCF519ADA410006AC72A /* DFGBlockMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockMap.h; path = dfg/DFGBlockMap.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockMapInlines.h; path = dfg/DFGBlockMapInlines.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockSet.h; path = dfg/DFGBlockSet.h; sourceTree = "<group>"; };
</span><del>- 0FC3CCF819ADA410006AC72A /* DFGBlockWorklist.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGBlockWorklist.cpp; path = dfg/DFGBlockWorklist.cpp; sourceTree = "<group>"; };
</del><span class="cx"> 0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockWorklist.h; path = dfg/DFGBlockWorklist.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGNaiveDominators.cpp; path = dfg/DFGNaiveDominators.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNaiveDominators.h; path = dfg/DFGNaiveDominators.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -5217,7 +5215,6 @@
</span><span class="cx"> 0FBF158A19B7A53100695DD0 /* DFGBlockSet.cpp */,
</span><span class="cx"> 0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */,
</span><span class="cx"> 0FBF158B19B7A53100695DD0 /* DFGBlockSetInlines.h */,
</span><del>- 0FC3CCF819ADA410006AC72A /* DFGBlockWorklist.cpp */,
</del><span class="cx"> 0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */,
</span><span class="cx"> 0F8364B5164B0C0E0053329A /* DFGBranchDirection.h */,
</span><span class="cx"> 86EC9DB41328DF82002B2AD7 /* DFGByteCodeParser.cpp */,
</span><span class="lines">@@ -7568,7 +7565,6 @@
</span><span class="cx"> A7D89CF217A0B8CC00773AD8 /* DFGBasicBlock.cpp in Sources */,
</span><span class="cx"> A7D89CF317A0B8CC00773AD8 /* DFGBlockInsertionSet.cpp in Sources */,
</span><span class="cx"> 0FBF158C19B7A53100695DD0 /* DFGBlockSet.cpp in Sources */,
</span><del>- 0FC3CCFF19ADA410006AC72A /* DFGBlockWorklist.cpp in Sources */,
</del><span class="cx"> 86EC9DC41328DF82002B2AD7 /* DFGByteCodeParser.cpp in Sources */,
</span><span class="cx"> 0FD82E2114172CE300179C94 /* DFGCapabilities.cpp in Sources */,
</span><span class="cx"> 0FFFC95714EF90A000C72532 /* DFGCFAPhase.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGBlockWorklistcpp"></a>
<div class="delfile"><h4>Deleted: trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.cpp (191423 => 191424)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.cpp 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.cpp 2015-10-22 01:46:06 UTC (rev 191424)
</span><span class="lines">@@ -1,86 +0,0 @@
</span><del>-/*
- * Copyright (C) 2014 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. ``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
- * 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 "DFGBlockWorklist.h"
-
-#if ENABLE(DFG_JIT)
-
-#include "DFGBasicBlock.h"
-
-namespace JSC { namespace DFG {
-
-BlockWorklist::BlockWorklist()
-{
-}
-
-BlockWorklist::~BlockWorklist()
-{
-}
-
-bool BlockWorklist::push(BasicBlock* block)
-{
- if (!m_seen.add(block))
- return false;
-
- m_stack.append(block);
- return true;
-}
-
-BasicBlock* BlockWorklist::pop()
-{
- if (m_stack.isEmpty())
- return nullptr;
-
- return m_stack.takeLast();
-}
-
-PostOrderBlockWorklist::PostOrderBlockWorklist()
-{
-}
-
-PostOrderBlockWorklist::~PostOrderBlockWorklist()
-{
-}
-
-bool PostOrderBlockWorklist::pushPre(BasicBlock* block)
-{
- return m_worklist.push(block, PreOrder);
-}
-
-void PostOrderBlockWorklist::pushPost(BasicBlock* block)
-{
- m_worklist.forcePush(block, PostOrder);
-}
-
-BlockWithOrder PostOrderBlockWorklist::pop()
-{
- BlockWith<VisitOrder> result = m_worklist.pop();
- return BlockWithOrder(result.block, result.data);
-}
-
-} } // namespace JSC::DFG
-
-#endif // ENABLE(DFG_JIT)
</del></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGBlockWorklisth"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.h (191423 => 191424)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.h 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.h 2015-10-22 01:46:06 UTC (rev 191424)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2014 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -30,152 +30,30 @@
</span><span class="cx">
</span><span class="cx"> #include "DFGBasicBlock.h"
</span><span class="cx"> #include "DFGBlockSet.h"
</span><ins>+#include <wtf/GraphNodeWorklist.h>
</ins><span class="cx"> #include <wtf/Vector.h>
</span><span class="cx">
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="cx">
</span><span class="cx"> struct BasicBlock;
</span><span class="cx">
</span><del>-class BlockWorklist {
-public:
- BlockWorklist();
- ~BlockWorklist();
-
- bool push(BasicBlock*); // Returns true if we didn't know about the block before.
-
- bool notEmpty() const { return !m_stack.isEmpty(); }
- BasicBlock* pop();
-
-private:
- BlockSet m_seen;
- Vector<BasicBlock*, 16> m_stack;
-};
</del><ins>+typedef GraphNodeWorklist<BasicBlock*, BlockSet> BlockWorklist;
</ins><span class="cx">
</span><span class="cx"> // When you say BlockWith<int> you should read it as "block with an int".
</span><del>-template<typename T>
-struct BlockWith {
- BlockWith()
- : block(nullptr)
- {
- }
-
- BlockWith(BasicBlock* block, const T& data)
- : block(block)
- , data(data)
- {
- }
-
- explicit operator bool() const { return block; }
</del><ins>+template<typename T> using BlockWith = GraphNodeWith<BasicBlock*, T>;
</ins><span class="cx">
</span><del>- BasicBlock* block;
- T data;
-};
-
</del><span class="cx"> // Extended block worklist is useful for enqueueing some meta-data along with the block. It also
</span><span class="cx"> // permits forcibly enqueueing things even if the block has already been seen. It's useful for
</span><span class="cx"> // things like building a spanning tree, in which case T (the auxiliary payload) would be the
</span><span class="cx"> // successor index.
</span><del>-template<typename T>
-class ExtendedBlockWorklist {
-public:
- ExtendedBlockWorklist() { }
-
- void forcePush(const BlockWith<T>& entry)
- {
- m_stack.append(entry);
- }
-
- void forcePush(BasicBlock* block, const T& data)
- {
- forcePush(BlockWith<T>(block, data));
- }
-
- bool push(const BlockWith<T>& entry)
- {
- if (!m_seen.add(entry.block))
- return false;
-
- forcePush(entry);
- return true;
- }
-
- bool push(BasicBlock* block, const T& data)
- {
- return push(BlockWith<T>(block, data));
- }
-
- bool notEmpty() const { return !m_stack.isEmpty(); }
-
- BlockWith<T> pop()
- {
- if (m_stack.isEmpty())
- return BlockWith<T>();
-
- return m_stack.takeLast();
- }
</del><ins>+template<typename T> using ExtendedBlockWorklist = ExtendedGraphNodeWorklist<BasicBlock*, T, BlockSet>;
</ins><span class="cx">
</span><del>-private:
- BlockSet m_seen;
- Vector<BlockWith<T>> m_stack;
-};
</del><ins>+typedef GraphVisitOrder VisitOrder;
</ins><span class="cx">
</span><del>-enum VisitOrder {
- PreOrder,
- PostOrder
-};
</del><ins>+typedef GraphNodeWithOrder<BasicBlock*> BlockWithOrder;
</ins><span class="cx">
</span><del>-struct BlockWithOrder {
- BlockWithOrder()
- : block(nullptr)
- , order(PreOrder)
- {
- }
-
- BlockWithOrder(BasicBlock* block, VisitOrder order)
- : block(block)
- , order(order)
- {
- }
-
- explicit operator bool() const { return block; }
</del><ins>+typedef PostOrderGraphNodeWorklist<BasicBlock*, BlockSet> PostOrderBlockWorklist;
</ins><span class="cx">
</span><del>- BasicBlock* block;
- VisitOrder order;
-};
-
-// Block worklist suitable for post-order traversal.
-class PostOrderBlockWorklist {
-public:
- PostOrderBlockWorklist();
- ~PostOrderBlockWorklist();
-
- bool pushPre(BasicBlock*);
- void pushPost(BasicBlock*);
-
- bool push(BasicBlock* block, VisitOrder order = PreOrder)
- {
- switch (order) {
- case PreOrder:
- return pushPre(block);
- case PostOrder:
- pushPost(block);
- return true;
- }
- RELEASE_ASSERT_NOT_REACHED();
- return false;
- }
- bool push(const BlockWithOrder& data)
- {
- return push(data.block, data.order);
- }
-
- bool notEmpty() const { return m_worklist.notEmpty(); }
- BlockWithOrder pop();
-
-private:
- ExtendedBlockWorklist<VisitOrder> m_worklist;
-};
-
</del><span class="cx"> } } // namespace JSC::DFG
</span><span class="cx">
</span><span class="cx"> #endif // ENABLE(DFG_JIT)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGDominatorscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGDominators.cpp (191423 => 191424)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGDominators.cpp 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/JavaScriptCore/dfg/DFGDominators.cpp 2015-10-22 01:46:06 UTC (rev 191424)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2011, 2014 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2011, 2014, 2015 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -108,7 +108,7 @@
</span><span class="cx"> worklist.push(m_graph.block(0), 0);
</span><span class="cx">
</span><span class="cx"> while (BlockWith<unsigned> item = worklist.pop()) {
</span><del>- BasicBlock* block = item.block;
</del><ins>+ BasicBlock* block = item.node;
</ins><span class="cx"> unsigned successorIndex = item.data;
</span><span class="cx">
</span><span class="cx"> // We initially push with successorIndex = 0 regardless of whether or not we have any
</span><span class="lines">@@ -355,18 +355,18 @@
</span><span class="cx">
</span><span class="cx"> // Plain stack-based worklist because we are guaranteed to see each block exactly once anyway.
</span><span class="cx"> Vector<BlockWithOrder> worklist;
</span><del>- worklist.append(BlockWithOrder(graph.block(0), PreOrder));
</del><ins>+ worklist.append(BlockWithOrder(graph.block(0), VisitOrder::Pre));
</ins><span class="cx"> while (!worklist.isEmpty()) {
</span><span class="cx"> BlockWithOrder item = worklist.takeLast();
</span><span class="cx"> switch (item.order) {
</span><del>- case PreOrder:
- m_data[item.block].preNumber = nextPreNumber++;
- worklist.append(BlockWithOrder(item.block, PostOrder));
- for (BasicBlock* kid : m_data[item.block].idomKids)
- worklist.append(BlockWithOrder(kid, PreOrder));
</del><ins>+ case VisitOrder::Pre:
+ m_data[item.node].preNumber = nextPreNumber++;
+ worklist.append(BlockWithOrder(item.node, VisitOrder::Post));
+ for (BasicBlock* kid : m_data[item.node].idomKids)
+ worklist.append(BlockWithOrder(kid, VisitOrder::Pre));
</ins><span class="cx"> break;
</span><del>- case PostOrder:
- m_data[item.block].postNumber = nextPostNumber++;
</del><ins>+ case VisitOrder::Post:
+ m_data[item.node].postNumber = nextPostNumber++;
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGGraphcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp (191423 => 191424)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp 2015-10-22 01:46:06 UTC (rev 191424)
</span><span class="lines">@@ -802,13 +802,13 @@
</span><span class="cx"> worklist.push(block(0));
</span><span class="cx"> while (BlockWithOrder item = worklist.pop()) {
</span><span class="cx"> switch (item.order) {
</span><del>- case PreOrder:
- worklist.pushPost(item.block);
- for (unsigned i = item.block->numSuccessors(); i--;)
- worklist.push(item.block->successor(i));
</del><ins>+ case VisitOrder::Pre:
+ worklist.pushPost(item.node);
+ for (unsigned i = item.node->numSuccessors(); i--;)
+ worklist.push(item.node->successor(i));
</ins><span class="cx"> break;
</span><del>- case PostOrder:
- result.append(item.block);
</del><ins>+ case VisitOrder::Post:
+ result.append(item.node);
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGPrePostNumberingcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGPrePostNumbering.cpp (191423 => 191424)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGPrePostNumbering.cpp 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/JavaScriptCore/dfg/DFGPrePostNumbering.cpp 2015-10-22 01:46:06 UTC (rev 191424)
</span><span class="lines">@@ -47,14 +47,14 @@
</span><span class="cx"> unsigned nextPostNumber = 0;
</span><span class="cx"> while (BlockWithOrder item = worklist.pop()) {
</span><span class="cx"> switch (item.order) {
</span><del>- case PreOrder:
- m_map[item.block].m_preNumber = nextPreNumber++;
- worklist.pushPost(item.block);
- for (BasicBlock* successor : item.block->successors())
</del><ins>+ case VisitOrder::Pre:
+ m_map[item.node].m_preNumber = nextPreNumber++;
+ worklist.pushPost(item.node);
+ for (BasicBlock* successor : item.node->successors())
</ins><span class="cx"> worklist.push(successor);
</span><span class="cx"> break;
</span><del>- case PostOrder:
- m_map[item.block].m_postNumber = nextPostNumber++;
</del><ins>+ case VisitOrder::Post:
+ m_map[item.node].m_postNumber = nextPostNumber++;
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (191423 => 191424)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/WTF/ChangeLog 2015-10-22 01:46:06 UTC (rev 191424)
</span><span class="lines">@@ -1,3 +1,40 @@
</span><ins>+2015-10-21 Filip Pizlo <fpizlo@apple.com>
+
+ Factor out the graph node worklists from DFG into WTF
+ https://bugs.webkit.org/show_bug.cgi?id=150411
+
+ Reviewed by Geoffrey Garen.
+
+ The new GraphNodeWorklist.h file is basically just the functionality from the old
+ DFGBlockWorklist.h, but templatized to work for any graph node type and any kind of graph
+ node set.
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/CMakeLists.txt:
+ * wtf/GraphNodeWorklist.h: Added.
+ (WTF::GraphNodeWorklist::push):
+ (WTF::GraphNodeWorklist::notEmpty):
+ (WTF::GraphNodeWorklist::pop):
+ (WTF::GraphNodeWith::GraphNodeWith):
+ (WTF::GraphNodeWith::operator bool):
+ (WTF::ExtendedGraphNodeWorklist::ExtendedGraphNodeWorklist):
+ (WTF::ExtendedGraphNodeWorklist::forcePush):
+ (WTF::ExtendedGraphNodeWorklist::push):
+ (WTF::ExtendedGraphNodeWorklist::notEmpty):
+ (WTF::ExtendedGraphNodeWorklist::pop):
+ (WTF::GraphNodeWithOrder::GraphNodeWithOrder):
+ (WTF::GraphNodeWithOrder::operator bool):
+ (WTF::PostOrderGraphNodeWorklist::PostOrderGraphNodeWorklist):
+ (WTF::PostOrderGraphNodeWorklist::~PostOrderGraphNodeWorklist):
+ (WTF::PostOrderGraphNodeWorklist::pushPre):
+ (WTF::PostOrderGraphNodeWorklist::pushPost):
+ (WTF::PostOrderGraphNodeWorklist::push):
+ (WTF::PostOrderGraphNodeWorklist::notEmpty):
+ (WTF::PostOrderGraphNodeWorklist::pop):
+ * wtf/HashTable.h:
+ (WTF::HashTableAddResult::HashTableAddResult):
+ (WTF::HashTableAddResult::operator bool):
+
</ins><span class="cx"> 2015-10-20 Tim Horton <timothy_horton@apple.com>
</span><span class="cx">
</span><span class="cx"> Try to fix the build by disabling MAC_GESTURE_EVENTS on 10.9 and 10.10
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (191423 => 191424)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-10-22 01:46:06 UTC (rev 191424)
</span><span class="lines">@@ -50,6 +50,7 @@
</span><span class="cx"> 0FE4479D1B7AAA03009498EB /* WordLock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FE4479B1B7AAA03009498EB /* WordLock.h */; };
</span><span class="cx"> 0FEB3DCF1BB5D684009D7AAD /* SharedTask.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEB3DCE1BB5D684009D7AAD /* SharedTask.h */; };
</span><span class="cx"> 0FEB3DD11BB7366B009D7AAD /* ParallelVectorIterator.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEB3DD01BB7366B009D7AAD /* ParallelVectorIterator.h */; };
</span><ins>+ 0FEC84AF1BD825310080FF74 /* GraphNodeWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */; };
</ins><span class="cx"> 0FED67B61B22D4D80066CE15 /* TinyPtrSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */; };
</span><span class="cx"> 0FF860951BCCBD740045127F /* PointerComparison.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF860941BCCBD740045127F /* PointerComparison.h */; };
</span><span class="cx"> 0FFF19DC1BB334EB00886D91 /* ParallelHelperPool.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FFF19DA1BB334EB00886D91 /* ParallelHelperPool.cpp */; };
</span><span class="lines">@@ -344,6 +345,7 @@
</span><span class="cx"> 0FE4479B1B7AAA03009498EB /* WordLock.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WordLock.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FEB3DCE1BB5D684009D7AAD /* SharedTask.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SharedTask.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FEB3DD01BB7366B009D7AAD /* ParallelVectorIterator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParallelVectorIterator.h; sourceTree = "<group>"; };
</span><ins>+ 0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = GraphNodeWorklist.h; sourceTree = "<group>"; };
</ins><span class="cx"> 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TinyPtrSet.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FF860941BCCBD740045127F /* PointerComparison.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PointerComparison.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FFF19DA1BB334EB00886D91 /* ParallelHelperPool.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParallelHelperPool.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -777,6 +779,7 @@
</span><span class="cx"> 1A1D8B9D1731879800141DA4 /* FunctionDispatcher.cpp */,
</span><span class="cx"> 1A1D8B9B173186CE00141DA4 /* FunctionDispatcher.h */,
</span><span class="cx"> A8A472A8151A825A004123FF /* GetPtr.h */,
</span><ins>+ 0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */,
</ins><span class="cx"> 2CCD892915C0390200285083 /* GregorianDateTime.cpp */,
</span><span class="cx"> 2C05385315BC819000F21B96 /* GregorianDateTime.h */,
</span><span class="cx"> A8A472B3151A825A004123FF /* HashCountedSet.h */,
</span><span class="lines">@@ -1249,6 +1252,7 @@
</span><span class="cx"> 1AFDE648195201C300C48FFA /* TypeCastsCF.h in Headers */,
</span><span class="cx"> A8A4746D151A825B004123FF /* UnionFind.h in Headers */,
</span><span class="cx"> 70ECA60F1B02426800449739 /* UniquedStringImpl.h in Headers */,
</span><ins>+ 0FEC84AF1BD825310080FF74 /* GraphNodeWorklist.h in Headers */,
</ins><span class="cx"> A8A4746A151A825B004123FF /* UTF8.h in Headers */,
</span><span class="cx"> A8A473B9151A825B004123FF /* utils.h in Headers */,
</span><span class="cx"> A8A4747D151A825B004123FF /* ValueCheck.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWTFwtfCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/CMakeLists.txt (191423 => 191424)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/CMakeLists.txt 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2015-10-22 01:46:06 UTC (rev 191424)
</span><span class="lines">@@ -29,6 +29,7 @@
</span><span class="cx"> FunctionDispatcher.h
</span><span class="cx"> Functional.h
</span><span class="cx"> GetPtr.h
</span><ins>+ GraphNodeWorklist.h
</ins><span class="cx"> GregorianDateTime.h
</span><span class="cx"> HashCountedSet.h
</span><span class="cx"> Hasher.h
</span></span></pre></div>
<a id="trunkSourceWTFwtfGraphNodeWorklisth"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/GraphNodeWorklist.h (0 => 191424)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/GraphNodeWorklist.h (rev 0)
+++ trunk/Source/WTF/wtf/GraphNodeWorklist.h 2015-10-22 01:46:06 UTC (rev 191424)
</span><span class="lines">@@ -0,0 +1,211 @@
</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. ``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
+ * 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 GraphNodeWorklist_h
+#define GraphNodeWorklist_h
+
+#include <wtf/HashSet.h>
+
+namespace WTF {
+
+template<typename Node, typename Set = HashSet<Node>>
+class GraphNodeWorklist {
+public:
+ GraphNodeWorklist() { }
+ ~GraphNodeWorklist() { }
+
+ // Returns true if we didn't know about the node before.
+ bool push(Node node)
+ {
+ if (!m_seen.add(node))
+ return false;
+ m_stack.append(node);
+ return true;
+ }
+
+ bool notEmpty() const { return !m_stack.isEmpty(); }
+
+ Node pop()
+ {
+ if (m_stack.isEmpty())
+ return Node();
+ return m_stack.takeLast();
+ }
+
+private:
+ Set m_seen;
+ Vector<Node, 16> m_stack;
+};
+
+template<typename Node, typename T>
+struct GraphNodeWith {
+ GraphNodeWith()
+ : node()
+ , data()
+ {
+ }
+
+ GraphNodeWith(Node node, const T& data)
+ : node(node)
+ , data(data)
+ {
+ }
+
+ explicit operator bool() const { return node; }
+
+ Node node;
+ T data;
+};
+
+template<typename Node, typename T, typename Set = HashSet<Node>>
+class ExtendedGraphNodeWorklist {
+public:
+ ExtendedGraphNodeWorklist() { }
+
+ void forcePush(const GraphNodeWith<Node, T>& entry)
+ {
+ m_stack.append(entry);
+ }
+
+ void forcePush(Node node, const T& data)
+ {
+ forcePush(GraphNodeWith<Node, T>(node, data));
+ }
+
+ bool push(const GraphNodeWith<Node, T>& entry)
+ {
+ if (!m_seen.add(entry.node))
+ return false;
+
+ forcePush(entry);
+ return true;
+ }
+
+ bool push(Node node, const T& data)
+ {
+ return push(GraphNodeWith<Node, T>(node, data));
+ }
+
+ bool notEmpty() const { return !m_stack.isEmpty(); }
+
+ GraphNodeWith<Node, T> pop()
+ {
+ if (m_stack.isEmpty())
+ return GraphNodeWith<Node, T>();
+
+ return m_stack.takeLast();
+ }
+
+private:
+ Set m_seen;
+ Vector<GraphNodeWith<Node, T>> m_stack;
+};
+
+enum class GraphVisitOrder : uint8_t {
+ Pre,
+ Post
+};
+
+template<typename Node>
+struct GraphNodeWithOrder {
+ GraphNodeWithOrder()
+ : node()
+ , order(GraphVisitOrder::Pre)
+ {
+ }
+
+ GraphNodeWithOrder(Node node, GraphVisitOrder order)
+ : node(node)
+ , order(order)
+ {
+ }
+
+ explicit operator bool() const { return node; }
+
+ Node node;
+ GraphVisitOrder order;
+};
+
+template<typename Node, typename Set = HashSet<Node>>
+class PostOrderGraphNodeWorklist {
+public:
+ PostOrderGraphNodeWorklist()
+ {
+ }
+
+ ~PostOrderGraphNodeWorklist()
+ {
+ }
+
+ bool pushPre(Node node)
+ {
+ return m_worklist.push(node, GraphVisitOrder::Pre);
+ }
+
+ void pushPost(Node node)
+ {
+ m_worklist.forcePush(node, GraphVisitOrder::Post);
+ }
+
+ bool push(Node node, GraphVisitOrder order = GraphVisitOrder::Pre)
+ {
+ switch (order) {
+ case GraphVisitOrder::Pre:
+ return pushPre(node);
+ case GraphVisitOrder::Post:
+ pushPost(node);
+ return true;
+ }
+ RELEASE_ASSERT_NOT_REACHED();
+ return false;
+ }
+ bool push(const GraphNodeWithOrder<Node>& data)
+ {
+ return push(data.node, data.order);
+ }
+
+ bool notEmpty() const { return m_worklist.notEmpty(); }
+
+ GraphNodeWithOrder<Node> pop()
+ {
+ GraphNodeWith<Node, GraphVisitOrder> result = m_worklist.pop();
+ return GraphNodeWithOrder<Node>(result.node, result.data);
+ }
+
+private:
+ ExtendedGraphNodeWorklist<Node, GraphVisitOrder, Set> m_worklist;
+};
+
+} // namespace WTF
+
+using WTF::GraphNodeWorklist;
+using WTF::GraphNodeWith;
+using WTF::ExtendedGraphNodeWorklist;
+using WTF::GraphVisitOrder;
+using WTF::GraphNodeWithOrder;
+using WTF::PostOrderGraphNodeWorklist;
+
+#endif // GraphNodeWorklist_h
+
</ins></span></pre></div>
<a id="trunkSourceWTFwtfHashTableh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/HashTable.h (191423 => 191424)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/HashTable.h 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/WTF/wtf/HashTable.h 2015-10-22 01:46:06 UTC (rev 191424)
</span><span class="lines">@@ -290,6 +290,8 @@
</span><span class="cx"> HashTableAddResult(IteratorType iter, bool isNewEntry) : iterator(iter), isNewEntry(isNewEntry) { }
</span><span class="cx"> IteratorType iterator;
</span><span class="cx"> bool isNewEntry;
</span><ins>+
+ explicit operator bool() const { return isNewEntry; }
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
</span></span></pre>
</div>
</div>
</body>
</html>