chromium/third_party/spirv-tools/src/source/opt/tree_iterator.h

// Copyright (c) 2017 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef SOURCE_OPT_TREE_ITERATOR_H_
#define SOURCE_OPT_TREE_ITERATOR_H_

#include <stack>
#include <type_traits>
#include <utility>

namespace spvtools {
namespace opt {

// Helper class to iterate over a tree in a depth first order.
// The class assumes the data structure is a tree, tree node type implements a
// forward iterator.
// At each step, the iterator holds the pointer to the current node and state of
// the walk.
// The state is recorded by stacking the iteration position of the node
// children. To move to the next node, the iterator:
//  - Looks at the top of the stack;
//  - Sets the node behind the iterator as the current node;
//  - Increments the iterator if it has more children to visit, pops otherwise;
//  - If the current node has children, the children iterator is pushed into the
//    stack.
template <typename NodeTy>
class TreeDFIterator { … };

// Helper class to iterate over a tree in a depth first post-order.
// The class assumes the data structure is a tree, tree node type implements a
// forward iterator.
// At each step, the iterator holds the pointer to the current node and state of
// the walk.
// The state is recorded by stacking the iteration position of the node
// children. To move to the next node, the iterator:
//  - Looks at the top of the stack;
//  - If the children iterator has reach the end, then the node become the
//    current one and we pop the stack;
//  - Otherwise, we save the child and increment the iterator;
//  - We walk the child sub-tree until we find a leaf, stacking all non-leaves
//    states (pair of node pointer and child iterator) as we walk it.
template <typename NodeTy>
class PostOrderTreeDFIterator { … };

}  // namespace opt
}  // namespace spvtools

#endif  // SOURCE_OPT_TREE_ITERATOR_H_