Diff
Modified: trunk/Source/_javascript_Core/CMakeLists.txt (191423 => 191424)
--- trunk/Source/_javascript_Core/CMakeLists.txt 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/_javascript_Core/CMakeLists.txt 2015-10-22 01:46:06 UTC (rev 191424)
@@ -150,7 +150,6 @@
dfg/DFGBasicBlock.cpp
dfg/DFGBlockInsertionSet.cpp
dfg/DFGBlockSet.cpp
- dfg/DFGBlockWorklist.cpp
dfg/DFGByteCodeParser.cpp
dfg/DFGCFAPhase.cpp
dfg/DFGCFGSimplificationPhase.cpp
Modified: trunk/Source/_javascript_Core/ChangeLog (191423 => 191424)
--- trunk/Source/_javascript_Core/ChangeLog 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-10-22 01:46:06 UTC (rev 191424)
@@ -1,3 +1,37 @@
+2015-10-21 Filip Pizlo <[email protected]>
+
+ 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:
+ * _javascript_Core.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):
+
2015-10-21 Sukolsak Sakshuwong <[email protected]>
[INTL] Implement Intl.Collator.prototype.resolvedOptions ()
Modified: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (191423 => 191424)
--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2015-10-22 01:46:06 UTC (rev 191424)
@@ -545,7 +545,6 @@
0FC3CCFC19ADA410006AC72A /* DFGBlockMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF519ADA410006AC72A /* DFGBlockMap.h */; };
0FC3CCFD19ADA410006AC72A /* DFGBlockMapInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */; };
0FC3CCFE19ADA410006AC72A /* DFGBlockSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */; };
- 0FC3CCFF19ADA410006AC72A /* DFGBlockWorklist.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC3CCF819ADA410006AC72A /* DFGBlockWorklist.cpp */; };
0FC3CD0019ADA410006AC72A /* DFGBlockWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */; };
0FC3CD0119ADA411006AC72A /* DFGNaiveDominators.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */; };
0FC3CD0219ADA411006AC72A /* DFGNaiveDominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */; };
@@ -2410,7 +2409,6 @@
0FC3CCF519ADA410006AC72A /* DFGBlockMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockMap.h; path = dfg/DFGBlockMap.h; sourceTree = "<group>"; };
0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockMapInlines.h; path = dfg/DFGBlockMapInlines.h; sourceTree = "<group>"; };
0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockSet.h; path = dfg/DFGBlockSet.h; sourceTree = "<group>"; };
- 0FC3CCF819ADA410006AC72A /* DFGBlockWorklist.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGBlockWorklist.cpp; path = dfg/DFGBlockWorklist.cpp; sourceTree = "<group>"; };
0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockWorklist.h; path = dfg/DFGBlockWorklist.h; sourceTree = "<group>"; };
0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGNaiveDominators.cpp; path = dfg/DFGNaiveDominators.cpp; sourceTree = "<group>"; };
0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNaiveDominators.h; path = dfg/DFGNaiveDominators.h; sourceTree = "<group>"; };
@@ -5217,7 +5215,6 @@
0FBF158A19B7A53100695DD0 /* DFGBlockSet.cpp */,
0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */,
0FBF158B19B7A53100695DD0 /* DFGBlockSetInlines.h */,
- 0FC3CCF819ADA410006AC72A /* DFGBlockWorklist.cpp */,
0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */,
0F8364B5164B0C0E0053329A /* DFGBranchDirection.h */,
86EC9DB41328DF82002B2AD7 /* DFGByteCodeParser.cpp */,
@@ -7568,7 +7565,6 @@
A7D89CF217A0B8CC00773AD8 /* DFGBasicBlock.cpp in Sources */,
A7D89CF317A0B8CC00773AD8 /* DFGBlockInsertionSet.cpp in Sources */,
0FBF158C19B7A53100695DD0 /* DFGBlockSet.cpp in Sources */,
- 0FC3CCFF19ADA410006AC72A /* DFGBlockWorklist.cpp in Sources */,
86EC9DC41328DF82002B2AD7 /* DFGByteCodeParser.cpp in Sources */,
0FD82E2114172CE300179C94 /* DFGCapabilities.cpp in Sources */,
0FFFC95714EF90A000C72532 /* DFGCFAPhase.cpp in Sources */,
Deleted: trunk/Source/_javascript_Core/dfg/DFGBlockWorklist.cpp (191423 => 191424)
--- trunk/Source/_javascript_Core/dfg/DFGBlockWorklist.cpp 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/_javascript_Core/dfg/DFGBlockWorklist.cpp 2015-10-22 01:46:06 UTC (rev 191424)
@@ -1,86 +0,0 @@
-/*
- * 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)
Modified: trunk/Source/_javascript_Core/dfg/DFGBlockWorklist.h (191423 => 191424)
--- trunk/Source/_javascript_Core/dfg/DFGBlockWorklist.h 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/_javascript_Core/dfg/DFGBlockWorklist.h 2015-10-22 01:46:06 UTC (rev 191424)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2014, 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
@@ -30,152 +30,30 @@
#include "DFGBasicBlock.h"
#include "DFGBlockSet.h"
+#include <wtf/GraphNodeWorklist.h>
#include <wtf/Vector.h>
namespace JSC { namespace DFG {
struct BasicBlock;
-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;
-};
+typedef GraphNodeWorklist<BasicBlock*, BlockSet> BlockWorklist;
// When you say BlockWith<int> you should read it as "block with an int".
-template<typename T>
-struct BlockWith {
- BlockWith()
- : block(nullptr)
- {
- }
-
- BlockWith(BasicBlock* block, const T& data)
- : block(block)
- , data(data)
- {
- }
-
- explicit operator bool() const { return block; }
+template<typename T> using BlockWith = GraphNodeWith<BasicBlock*, T>;
- BasicBlock* block;
- T data;
-};
-
// Extended block worklist is useful for enqueueing some meta-data along with the block. It also
// permits forcibly enqueueing things even if the block has already been seen. It's useful for
// things like building a spanning tree, in which case T (the auxiliary payload) would be the
// successor index.
-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();
- }
+template<typename T> using ExtendedBlockWorklist = ExtendedGraphNodeWorklist<BasicBlock*, T, BlockSet>;
-private:
- BlockSet m_seen;
- Vector<BlockWith<T>> m_stack;
-};
+typedef GraphVisitOrder VisitOrder;
-enum VisitOrder {
- PreOrder,
- PostOrder
-};
+typedef GraphNodeWithOrder<BasicBlock*> BlockWithOrder;
-struct BlockWithOrder {
- BlockWithOrder()
- : block(nullptr)
- , order(PreOrder)
- {
- }
-
- BlockWithOrder(BasicBlock* block, VisitOrder order)
- : block(block)
- , order(order)
- {
- }
-
- explicit operator bool() const { return block; }
+typedef PostOrderGraphNodeWorklist<BasicBlock*, BlockSet> PostOrderBlockWorklist;
- 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;
-};
-
} } // namespace JSC::DFG
#endif // ENABLE(DFG_JIT)
Modified: trunk/Source/_javascript_Core/dfg/DFGDominators.cpp (191423 => 191424)
--- trunk/Source/_javascript_Core/dfg/DFGDominators.cpp 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/_javascript_Core/dfg/DFGDominators.cpp 2015-10-22 01:46:06 UTC (rev 191424)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2011, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2011, 2014, 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
@@ -108,7 +108,7 @@
worklist.push(m_graph.block(0), 0);
while (BlockWith<unsigned> item = worklist.pop()) {
- BasicBlock* block = item.block;
+ BasicBlock* block = item.node;
unsigned successorIndex = item.data;
// We initially push with successorIndex = 0 regardless of whether or not we have any
@@ -355,18 +355,18 @@
// Plain stack-based worklist because we are guaranteed to see each block exactly once anyway.
Vector<BlockWithOrder> worklist;
- worklist.append(BlockWithOrder(graph.block(0), PreOrder));
+ worklist.append(BlockWithOrder(graph.block(0), VisitOrder::Pre));
while (!worklist.isEmpty()) {
BlockWithOrder item = worklist.takeLast();
switch (item.order) {
- 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));
+ 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));
break;
- case PostOrder:
- m_data[item.block].postNumber = nextPostNumber++;
+ case VisitOrder::Post:
+ m_data[item.node].postNumber = nextPostNumber++;
break;
}
}
Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.cpp (191423 => 191424)
--- trunk/Source/_javascript_Core/dfg/DFGGraph.cpp 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.cpp 2015-10-22 01:46:06 UTC (rev 191424)
@@ -802,13 +802,13 @@
worklist.push(block(0));
while (BlockWithOrder item = worklist.pop()) {
switch (item.order) {
- case PreOrder:
- worklist.pushPost(item.block);
- for (unsigned i = item.block->numSuccessors(); i--;)
- worklist.push(item.block->successor(i));
+ case VisitOrder::Pre:
+ worklist.pushPost(item.node);
+ for (unsigned i = item.node->numSuccessors(); i--;)
+ worklist.push(item.node->successor(i));
break;
- case PostOrder:
- result.append(item.block);
+ case VisitOrder::Post:
+ result.append(item.node);
break;
}
}
Modified: trunk/Source/_javascript_Core/dfg/DFGPrePostNumbering.cpp (191423 => 191424)
--- trunk/Source/_javascript_Core/dfg/DFGPrePostNumbering.cpp 2015-10-22 00:58:24 UTC (rev 191423)
+++ trunk/Source/_javascript_Core/dfg/DFGPrePostNumbering.cpp 2015-10-22 01:46:06 UTC (rev 191424)
@@ -47,14 +47,14 @@
unsigned nextPostNumber = 0;
while (BlockWithOrder item = worklist.pop()) {
switch (item.order) {
- case PreOrder:
- m_map[item.block].m_preNumber = nextPreNumber++;
- worklist.pushPost(item.block);
- for (BasicBlock* successor : item.block->successors())
+ case VisitOrder::Pre:
+ m_map[item.node].m_preNumber = nextPreNumber++;
+ worklist.pushPost(item.node);
+ for (BasicBlock* successor : item.node->successors())
worklist.push(successor);
break;
- case PostOrder:
- m_map[item.block].m_postNumber = nextPostNumber++;
+ case VisitOrder::Post:
+ m_map[item.node].m_postNumber = nextPostNumber++;
break;
}
}
Modified: trunk/Source/WTF/ChangeLog (191423 => 191424)
--- 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)
@@ -1,3 +1,40 @@
+2015-10-21 Filip Pizlo <[email protected]>
+
+ 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):
+
2015-10-20 Tim Horton <[email protected]>
Try to fix the build by disabling MAC_GESTURE_EVENTS on 10.9 and 10.10
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (191423 => 191424)
--- 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)
@@ -50,6 +50,7 @@
0FE4479D1B7AAA03009498EB /* WordLock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FE4479B1B7AAA03009498EB /* WordLock.h */; };
0FEB3DCF1BB5D684009D7AAD /* SharedTask.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEB3DCE1BB5D684009D7AAD /* SharedTask.h */; };
0FEB3DD11BB7366B009D7AAD /* ParallelVectorIterator.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEB3DD01BB7366B009D7AAD /* ParallelVectorIterator.h */; };
+ 0FEC84AF1BD825310080FF74 /* GraphNodeWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */; };
0FED67B61B22D4D80066CE15 /* TinyPtrSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */; };
0FF860951BCCBD740045127F /* PointerComparison.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF860941BCCBD740045127F /* PointerComparison.h */; };
0FFF19DC1BB334EB00886D91 /* ParallelHelperPool.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FFF19DA1BB334EB00886D91 /* ParallelHelperPool.cpp */; };
@@ -344,6 +345,7 @@
0FE4479B1B7AAA03009498EB /* WordLock.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WordLock.h; sourceTree = "<group>"; };
0FEB3DCE1BB5D684009D7AAD /* SharedTask.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SharedTask.h; sourceTree = "<group>"; };
0FEB3DD01BB7366B009D7AAD /* ParallelVectorIterator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParallelVectorIterator.h; sourceTree = "<group>"; };
+ 0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = GraphNodeWorklist.h; sourceTree = "<group>"; };
0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TinyPtrSet.h; sourceTree = "<group>"; };
0FF860941BCCBD740045127F /* PointerComparison.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PointerComparison.h; sourceTree = "<group>"; };
0FFF19DA1BB334EB00886D91 /* ParallelHelperPool.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParallelHelperPool.cpp; sourceTree = "<group>"; };
@@ -777,6 +779,7 @@
1A1D8B9D1731879800141DA4 /* FunctionDispatcher.cpp */,
1A1D8B9B173186CE00141DA4 /* FunctionDispatcher.h */,
A8A472A8151A825A004123FF /* GetPtr.h */,
+ 0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */,
2CCD892915C0390200285083 /* GregorianDateTime.cpp */,
2C05385315BC819000F21B96 /* GregorianDateTime.h */,
A8A472B3151A825A004123FF /* HashCountedSet.h */,
@@ -1249,6 +1252,7 @@
1AFDE648195201C300C48FFA /* TypeCastsCF.h in Headers */,
A8A4746D151A825B004123FF /* UnionFind.h in Headers */,
70ECA60F1B02426800449739 /* UniquedStringImpl.h in Headers */,
+ 0FEC84AF1BD825310080FF74 /* GraphNodeWorklist.h in Headers */,
A8A4746A151A825B004123FF /* UTF8.h in Headers */,
A8A473B9151A825B004123FF /* utils.h in Headers */,
A8A4747D151A825B004123FF /* ValueCheck.h in Headers */,
Modified: trunk/Source/WTF/wtf/CMakeLists.txt (191423 => 191424)
--- 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)
@@ -29,6 +29,7 @@
FunctionDispatcher.h
Functional.h
GetPtr.h
+ GraphNodeWorklist.h
GregorianDateTime.h
HashCountedSet.h
Hasher.h
Added: trunk/Source/WTF/wtf/GraphNodeWorklist.h (0 => 191424)
--- trunk/Source/WTF/wtf/GraphNodeWorklist.h (rev 0)
+++ trunk/Source/WTF/wtf/GraphNodeWorklist.h 2015-10-22 01:46:06 UTC (rev 191424)
@@ -0,0 +1,211 @@
+/*
+ * 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
+
Modified: trunk/Source/WTF/wtf/HashTable.h (191423 => 191424)
--- 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)
@@ -290,6 +290,8 @@
HashTableAddResult(IteratorType iter, bool isNewEntry) : iterator(iter), isNewEntry(isNewEntry) { }
IteratorType iterator;
bool isNewEntry;
+
+ explicit operator bool() const { return isNewEntry; }
};
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
