| OLD | NEW |
| 1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 the V8 project authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #ifndef V8_COMPILER_GENERIC_ALGORITHM_H_ | 5 #ifndef V8_COMPILER_GENERIC_ALGORITHM_H_ |
| 6 #define V8_COMPILER_GENERIC_ALGORITHM_H_ | 6 #define V8_COMPILER_GENERIC_ALGORITHM_H_ |
| 7 | 7 |
| 8 #include <stack> | 8 #include <stack> |
| 9 | 9 |
| 10 #include "src/compiler/generic-node.h" | |
| 11 #include "src/zone-containers.h" | 10 #include "src/zone-containers.h" |
| 12 | 11 |
| 13 namespace v8 { | 12 namespace v8 { |
| 14 namespace internal { | 13 namespace internal { |
| 15 namespace compiler { | 14 namespace compiler { |
| 16 | 15 |
| 16 class Graph; |
| 17 class Node; |
| 18 |
| 17 // GenericGraphVisit allows visitation of graphs of nodes and edges in pre- and | 19 // GenericGraphVisit allows visitation of graphs of nodes and edges in pre- and |
| 18 // post-order. Visitation uses an explicitly allocated stack rather than the | 20 // post-order. Visitation uses an explicitly allocated stack rather than the |
| 19 // execution stack to avoid stack overflow. Although GenericGraphVisit is | 21 // execution stack to avoid stack overflow. Although GenericGraphVisit is |
| 20 // primarily intended to traverse networks of nodes through their | 22 // primarily intended to traverse networks of nodes through their |
| 21 // dependencies and uses, it also can be used to visit any graph-like network | 23 // dependencies and uses, it also can be used to visit any graph-like network |
| 22 // by specifying custom traits. | 24 // by specifying custom traits. |
| 23 class GenericGraphVisit { | 25 class GenericGraphVisit { |
| 24 public: | 26 public: |
| 25 // struct Visitor { | 27 // struct Visitor { |
| 26 // void Pre(Traits::Node* current); | 28 // void Pre(Traits::Node* current); |
| (...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 81 } | 83 } |
| 82 } | 84 } |
| 83 | 85 |
| 84 template <class Visitor, class Traits> | 86 template <class Visitor, class Traits> |
| 85 static void Visit(Graph* graph, Zone* zone, typename Traits::Node* current, | 87 static void Visit(Graph* graph, Zone* zone, typename Traits::Node* current, |
| 86 Visitor* visitor) { | 88 Visitor* visitor) { |
| 87 typename Traits::Node* array[] = {current}; | 89 typename Traits::Node* array[] = {current}; |
| 88 Visit<Visitor, Traits>(graph, zone, &array[0], &array[1], visitor); | 90 Visit<Visitor, Traits>(graph, zone, &array[0], &array[1], visitor); |
| 89 } | 91 } |
| 90 | 92 |
| 91 template <class B, class S> | |
| 92 struct NullNodeVisitor { | 93 struct NullNodeVisitor { |
| 93 void Pre(GenericNode<B, S>* node) {} | 94 void Pre(Node* node) {} |
| 94 void Post(GenericNode<B, S>* node) {} | 95 void Post(Node* node) {} |
| 95 void PreEdge(GenericNode<B, S>* from, int index, GenericNode<B, S>* to) {} | 96 void PreEdge(Node* from, int index, Node* to) {} |
| 96 void PostEdge(GenericNode<B, S>* from, int index, GenericNode<B, S>* to) {} | 97 void PostEdge(Node* from, int index, Node* to) {} |
| 97 }; | 98 }; |
| 98 | 99 |
| 99 private: | 100 private: |
| 100 static void SetVisited(BoolVector* visited, int id) { | 101 static void SetVisited(BoolVector* visited, int id) { |
| 101 if (id >= static_cast<int>(visited->size())) { | 102 if (id >= static_cast<int>(visited->size())) { |
| 102 // Resize and set all values to unvisited. | 103 // Resize and set all values to unvisited. |
| 103 visited->resize((3 * id) / 2, false); | 104 visited->resize((3 * id) / 2, false); |
| 104 } | 105 } |
| 105 visited->at(id) = true; | 106 visited->at(id) = true; |
| 106 } | 107 } |
| 107 | 108 |
| 108 static bool GetVisited(BoolVector* visited, int id) { | 109 static bool GetVisited(BoolVector* visited, int id) { |
| 109 if (id >= static_cast<int>(visited->size())) return false; | 110 if (id >= static_cast<int>(visited->size())) return false; |
| 110 return visited->at(id); | 111 return visited->at(id); |
| 111 } | 112 } |
| 112 }; | 113 }; |
| 113 } | 114 } |
| 114 } | 115 } |
| 115 } // namespace v8::internal::compiler | 116 } // namespace v8::internal::compiler |
| 116 | 117 |
| 117 #endif // V8_COMPILER_GENERIC_ALGORITHM_H_ | 118 #endif // V8_COMPILER_GENERIC_ALGORITHM_H_ |
| OLD | NEW |