klee
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
PTree.cpp
Go to the documentation of this file.
1 //===-- PTree.cpp ---------------------------------------------------------===//
2 //
3 // The KLEE Symbolic Virtual Machine
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "PTree.h"
11 
12 #include <klee/Expr.h>
13 #include <klee/util/ExprPPrinter.h>
14 
15 #include <vector>
16 
17 using namespace klee;
18 
19  /* *** */
20 
21 PTree::PTree(const data_type &_root) : root(new Node(0,_root)) {
22 }
23 
25 
26 std::pair<PTreeNode*, PTreeNode*>
28  const data_type &leftData,
29  const data_type &rightData) {
30  assert(n && !n->left && !n->right);
31  n->left = new Node(n, leftData);
32  n->right = new Node(n, rightData);
33  return std::make_pair(n->left, n->right);
34 }
35 
36 void PTree::remove(Node *n) {
37  assert(!n->left && !n->right);
38  do {
39  Node *p = n->parent;
40  delete n;
41  if (p) {
42  if (n == p->left) {
43  p->left = 0;
44  } else {
45  assert(n == p->right);
46  p->right = 0;
47  }
48  }
49  n = p;
50  } while (n && !n->left && !n->right);
51 }
52 
53 void PTree::dump(llvm::raw_ostream &os) {
55  pp->setNewline("\\l");
56  os << "digraph G {\n";
57  os << "\tsize=\"10,7.5\";\n";
58  os << "\tratio=fill;\n";
59  os << "\trotate=90;\n";
60  os << "\tcenter = \"true\";\n";
61  os << "\tnode [style=\"filled\",width=.1,height=.1,fontname=\"Terminus\"]\n";
62  os << "\tedge [arrowsize=.3]\n";
63  std::vector<PTree::Node*> stack;
64  stack.push_back(root);
65  while (!stack.empty()) {
66  PTree::Node *n = stack.back();
67  stack.pop_back();
68  if (n->condition.isNull()) {
69  os << "\tn" << n << " [label=\"\"";
70  } else {
71  os << "\tn" << n << " [label=\"";
72  pp->print(n->condition);
73  os << "\",shape=diamond";
74  }
75  if (n->data)
76  os << ",fillcolor=green";
77  os << "];\n";
78  if (n->left) {
79  os << "\tn" << n << " -> n" << n->left << ";\n";
80  stack.push_back(n->left);
81  }
82  if (n->right) {
83  os << "\tn" << n << " -> n" << n->right << ";\n";
84  stack.push_back(n->right);
85  }
86  }
87  os << "}\n";
88  delete pp;
89 }
90 
92  ExecutionState *_data)
93  : parent(_parent),
94  left(0),
95  right(0),
96  data(_data),
97  condition(0) {
98 }
99 
101 }
102 
void remove(Node *n)
Definition: PTree.cpp:36
class PTreeNode Node
Definition: PTree.h:22
void dump(llvm::raw_ostream &os)
Definition: PTree.cpp:53
PTreeNode(PTreeNode *_parent, ExecutionState *_data)
Definition: PTree.cpp:91
PTree(const data_type &_root)
Definition: PTree.cpp:21
Node * root
Definition: PTree.h:23
virtual void print(const ref< Expr > &e, unsigned indent=0)=0
static ExprPPrinter * create(llvm::raw_ostream &os)
virtual void setNewline(const std::string &newline)=0
std::pair< Node *, Node * > split(Node *n, const data_type &leftData, const data_type &rightData)
Definition: PTree.cpp:27