1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
//===-- DFSVisitor.cpp ------------------------------------------*- C++ -*-===//
//
// The KLEE Symbolic Virtual Machine
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#include "DFSVisitor.h"
#include <utility>
DFSVisitor::DFSVisitor(const Tree &tree, callbackT cb_intermediate,
callbackT cb_leaf) noexcept
: tree{tree},
cb_intermediate{std::move(cb_intermediate)}, cb_leaf{std::move(cb_leaf)} {
run();
}
void DFSVisitor::run() const noexcept {
// empty tree
if (tree.nodes.size() <= 1)
return;
std::vector<std::tuple<std::uint32_t, std::uint32_t>> stack{
{1, 1}}; // (id, depth)
while (!stack.empty()) {
std::uint32_t id, depth;
std::tie(id, depth) = stack.back();
stack.pop_back();
const auto &node = tree.nodes[id];
if (node.left || node.right) {
if (cb_intermediate)
cb_intermediate(id, node, depth);
if (node.right)
stack.emplace_back(node.right, depth + 1);
if (node.left)
stack.emplace_back(node.left, depth + 1);
} else {
if (cb_leaf)
cb_leaf(id, node, depth);
}
}
}
|
