1 /* radare - LGPL - Copyright 2007-2015 - ret2libc */
2
3 #include <r_util.h>
4
tree_dfs_node(RTreeNode * r,RTreeVisitor * vis)5 static void tree_dfs_node (RTreeNode *r, RTreeVisitor *vis) {
6 RStack *s;
7 RListIter *it;
8 RTreeNode *n;
9
10 s = r_stack_new (16);
11 if (!s) {
12 return;
13 }
14 r_stack_push (s, r);
15 while (!r_stack_is_empty (s)) {
16 RTreeNode *el = (RTreeNode *)r_stack_pop (s);
17
18 if (vis->pre_visit) {
19 vis->pre_visit (el, vis);
20 }
21
22 r_list_foreach_prev (el->children, it, n) {
23 if (vis->discover_child) {
24 vis->discover_child (n, vis);
25 }
26 r_stack_push (s, n);
27 }
28
29 if (vis->post_visit) {
30 vis->post_visit (el, vis);
31 }
32 }
33
34 r_stack_free (s);
35 }
36
r_tree_node_free(RTreeNode * n)37 static void r_tree_node_free (RTreeNode *n) {
38 r_list_free (n->children);
39 if (n->free) {
40 n->free (n->data);
41 }
42 free (n);
43 }
44
node_free(RTreeNode * n,RTreeVisitor * vis)45 static void node_free (RTreeNode *n, RTreeVisitor *vis) {
46 r_tree_node_free (n);
47 }
48
free_all_children(RTree * t)49 static void free_all_children (RTree *t) {
50 RTreeVisitor vis = { 0 };
51 vis.post_visit = (RTreeNodeVisitCb)node_free;
52 r_tree_bfs (t, &vis);
53 }
54
update_depth(RTreeNode * n,RTreeVisitor * vis)55 static void update_depth (RTreeNode *n, RTreeVisitor *vis) {
56 n->depth = n->parent ? n->parent->depth + 1 : 0;
57 }
58
node_new(RTree * t,void * data)59 static RTreeNode *node_new (RTree *t, void *data) {
60 RTreeNode *n = R_NEW0 (RTreeNode);
61 if (!n) {
62 return NULL;
63 }
64 n->children = r_list_new ();
65 n->data = data;
66 n->tree = t;
67 return n;
68 }
69
r_tree_new(void)70 R_API RTree *r_tree_new (void) {
71 return R_NEW0 (RTree);
72 }
73
r_tree_free(RTree * t)74 R_API void r_tree_free (RTree* t) {
75 if (!t) {
76 return;
77 }
78
79 free_all_children (t);
80 free (t);
81 }
82
r_tree_reset(RTree * t)83 R_API void r_tree_reset (RTree *t) {
84 if (!t) {
85 return;
86 }
87
88 free_all_children (t);
89 t->root = NULL;
90 }
91
92 /* add a node in the RTree t as a child of the RTreeNode node.
93 * NOTE: the first call to this function, should add the root
94 * of the tree so the node will be NULL. */
95 /* TODO: allow to replace the root of the tree and make it a child of the new
96 * node */
r_tree_add_node(RTree * t,RTreeNode * node,void * child_data)97 R_API RTreeNode *r_tree_add_node (RTree *t, RTreeNode *node, void *child_data) {
98 RTreeNode *child;
99 RTreeVisitor vis = { 0 };
100
101 /* a NULL node is allowed only the first time, to set the root */
102 if (!t || (node && node->tree != t) || (t->root && !node)) {
103 return NULL;
104 }
105
106 child = node_new (t, child_data);
107 if (!node && !t->root) {
108 t->root = child;
109 } else if (node) {
110 r_list_append (node->children, child);
111 node->n_children++;
112 }
113 child->parent = node;
114
115 /* update depth */
116 vis.pre_visit = (RTreeNodeVisitCb)update_depth;
117 tree_dfs_node (child, &vis);
118
119 return child;
120 }
121
r_tree_dfs(RTree * t,RTreeVisitor * vis)122 R_API void r_tree_dfs (RTree *t, RTreeVisitor *vis) {
123 if (!t || !t->root) {
124 return;
125 }
126
127 tree_dfs_node (t->root, vis);
128 }
129
r_tree_bfs(RTree * t,RTreeVisitor * vis)130 R_API void r_tree_bfs (RTree *t, RTreeVisitor *vis) {
131 RQueue *q;
132
133 if (!t || !t->root) {
134 return;
135 }
136
137 q = r_queue_new (16);
138 if (!q) {
139 return;
140 }
141 r_queue_enqueue (q, t->root);
142 while (!r_queue_is_empty (q)) {
143 RTreeNode *el = (RTreeNode *)r_queue_dequeue (q);
144 if (!el) {
145 r_queue_free (q);
146 return;
147 }
148 RTreeNode *n;
149 RListIter *it;
150
151 if (vis->pre_visit) {
152 vis->pre_visit (el, vis);
153 }
154
155 r_list_foreach (el->children, it, n) {
156 if (vis->discover_child) {
157 vis->discover_child (n, vis);
158 }
159 r_queue_enqueue (q, n);
160 }
161
162 if (vis->post_visit) {
163 vis->post_visit (el, vis);
164 }
165 }
166
167 r_queue_free (q);
168 }
169