1 /* radare - LGPL - Copyright 2007-2020 - pancake, ret2libc */
2
3 #include <r_util.h>
4
5 enum {
6 WHITE_COLOR = 0,
7 GRAY_COLOR,
8 BLACK_COLOR
9 };
10
r_graph_node_new(void * data)11 static RGraphNode *r_graph_node_new (void *data) {
12 RGraphNode *p = R_NEW0 (RGraphNode);
13 if (p) {
14 p->data = data;
15 p->free = NULL;
16 p->out_nodes = r_list_new ();
17 p->in_nodes = r_list_new ();
18 p->all_neighbours = r_list_new ();
19 }
20 return p;
21 }
22
r_graph_node_free(RGraphNode * n)23 static void r_graph_node_free (RGraphNode *n) {
24 if (!n) {
25 return;
26 }
27 if (n->free) {
28 n->free (n->data);
29 }
30 r_list_free (n->out_nodes);
31 r_list_free (n->in_nodes);
32 r_list_free (n->all_neighbours);
33 free (n);
34 }
35
node_cmp(unsigned int idx,RGraphNode * b)36 static int node_cmp (unsigned int idx, RGraphNode *b) {
37 return idx == b->idx ? 0 : -1;
38 }
39
40 // direction == true => forwards
dfs_node(RGraph * g,RGraphNode * n,RGraphVisitor * vis,int color[],const bool direction)41 static void dfs_node (RGraph *g, RGraphNode *n, RGraphVisitor *vis, int color[], const bool direction) {
42 if (!n) {
43 return;
44 }
45 RStack *s = r_stack_new (2 * g->n_edges + 1);
46 if (!s) {
47 return;
48 }
49 RGraphEdge *edg = R_NEW0 (RGraphEdge);
50 if (!edg) {
51 r_stack_free (s);
52 return;
53 }
54 edg->from = NULL;
55 edg->to = n;
56 r_stack_push (s, edg);
57 while (!r_stack_is_empty (s)) {
58 RGraphEdge *cur_edge = (RGraphEdge *)r_stack_pop (s);
59 RGraphNode *v, *cur = cur_edge->to, *from = cur_edge->from;
60 RListIter *it;
61 int i;
62
63 if (from && cur) {
64 if (color[cur->idx] == WHITE_COLOR && vis->tree_edge) {
65 vis->tree_edge (cur_edge, vis);
66 } else if (color[cur->idx] == GRAY_COLOR && vis->back_edge) {
67 vis->back_edge (cur_edge, vis);
68 } else if (color[cur->idx] == BLACK_COLOR && vis->fcross_edge) {
69 vis->fcross_edge (cur_edge, vis);
70 }
71 } else if (!cur && from) {
72 if (color[from->idx] != BLACK_COLOR && vis->finish_node) {
73 vis->finish_node (from, vis);
74 }
75 color[from->idx] = BLACK_COLOR;
76 }
77 free (cur_edge);
78 if (!cur || color[cur->idx] != WHITE_COLOR) {
79 continue;
80 }
81 if (color[cur->idx] == WHITE_COLOR && vis->discover_node) {
82 vis->discover_node (cur, vis);
83 }
84 color[cur->idx] = GRAY_COLOR;
85
86 edg = R_NEW0 (RGraphEdge);
87 if (!edg) {
88 break;
89 }
90 edg->from = cur;
91 r_stack_push (s, edg);
92
93 i = 0;
94 const RList *neighbours = direction ? cur->out_nodes : cur->in_nodes;
95 r_list_foreach (neighbours, it, v) {
96 edg = R_NEW (RGraphEdge);
97 edg->from = cur;
98 edg->to = v;
99 edg->nth = i++;
100 r_stack_push (s, edg);
101 }
102 }
103 r_stack_free (s);
104 }
105
r_graph_new(void)106 R_API RGraph *r_graph_new(void) {
107 RGraph *t = R_NEW0 (RGraph);
108 if (!t) {
109 return NULL;
110 }
111 t->nodes = r_list_new ();
112 if (!t->nodes) {
113 r_graph_free(t);
114 return NULL;
115 }
116 t->nodes->free = (RListFree)r_graph_node_free;
117 t->n_nodes = 0;
118 t->last_index = 0;
119 return t;
120 }
121
r_graph_free(RGraph * t)122 R_API void r_graph_free(RGraph* t) {
123 r_list_free (t->nodes);
124 free (t);
125 }
126
r_graph_get_node(const RGraph * t,unsigned int idx)127 R_API RGraphNode *r_graph_get_node(const RGraph *t, unsigned int idx) {
128 RListIter *it = r_list_find (t->nodes, (void *)(size_t)idx, (RListComparator)node_cmp);
129 if (!it) {
130 return NULL;
131 }
132 return (RGraphNode *)it->data;
133 }
134
r_graph_node_iter(const RGraph * t,unsigned int idx)135 R_API RListIter *r_graph_node_iter(const RGraph *t, unsigned int idx) {
136 return r_list_find (t->nodes, (void *)(size_t)idx, (RListComparator)node_cmp);
137 }
138
r_graph_reset(RGraph * t)139 R_API void r_graph_reset (RGraph *t) {
140 r_list_free (t->nodes);
141 t->nodes = r_list_new ();
142 if (!t->nodes) {
143 return;
144 }
145 t->nodes->free = (RListFree)r_graph_node_free;
146 t->n_nodes = 0;
147 t->n_edges = 0;
148 t->last_index = 0;
149 }
150
r_graph_add_node(RGraph * t,void * data)151 R_API RGraphNode *r_graph_add_node(RGraph *t, void *data) {
152 if (!t) {
153 return NULL;
154 }
155 RGraphNode *n = r_graph_node_new (data);
156 if (!n) {
157 return NULL;
158 }
159 n->idx = t->last_index++;
160 r_list_append (t->nodes, n);
161 t->n_nodes++;
162 return n;
163 }
164
r_graph_add_nodef(RGraph * graph,void * data,RListFree user_free)165 R_API RGraphNode *r_graph_add_nodef(RGraph *graph, void *data, RListFree user_free) {
166 RGraphNode *node = r_graph_add_node (graph, data);
167 if (node) {
168 node->free = user_free;
169 }
170 return node;
171 }
172
173 /* remove the node from the graph and free the node */
174 /* users of this function should be aware they can't access n anymore */
r_graph_del_node(RGraph * t,RGraphNode * n)175 R_API void r_graph_del_node(RGraph *t, RGraphNode *n) {
176 RGraphNode *gn;
177 RListIter *it;
178 if (!n) {
179 return;
180 }
181 r_list_foreach (n->in_nodes, it, gn) {
182 r_list_delete_data (gn->out_nodes, n);
183 r_list_delete_data (gn->all_neighbours, n);
184 t->n_edges--;
185 }
186
187 r_list_foreach (n->out_nodes, it, gn) {
188 r_list_delete_data (gn->in_nodes, n);
189 r_list_delete_data (gn->all_neighbours, n);
190 t->n_edges--;
191 }
192
193 r_list_delete_data (t->nodes, n);
194 t->n_nodes--;
195 }
196
r_graph_add_edge(RGraph * t,RGraphNode * from,RGraphNode * to)197 R_API void r_graph_add_edge(RGraph *t, RGraphNode *from, RGraphNode *to) {
198 r_graph_add_edge_at (t, from, to, -1);
199 }
200
r_graph_add_edge_at(RGraph * t,RGraphNode * from,RGraphNode * to,int nth)201 R_API void r_graph_add_edge_at(RGraph *t, RGraphNode *from, RGraphNode *to, int nth) {
202 if (from && to) {
203 r_list_insert (from->out_nodes, nth, to);
204 r_list_append (from->all_neighbours, to);
205 r_list_append (to->in_nodes, from);
206 r_list_append (to->all_neighbours, from);
207 t->n_edges++;
208 }
209 }
210
211 // splits the "split_me", so that new node has it's outnodes
r_graph_node_split_forward(RGraph * g,RGraphNode * split_me,void * data)212 R_API RGraphNode *r_graph_node_split_forward(RGraph *g, RGraphNode *split_me, void *data) {
213 RGraphNode *front = r_graph_add_node(g, data);
214 RList *tmp = front->out_nodes;
215 front->out_nodes = split_me->out_nodes;
216 split_me->out_nodes = tmp;
217 RListIter *iter;
218 RGraphNode *n;
219 r_list_foreach (front->out_nodes, iter, n) {
220 r_list_delete_data (n->in_nodes, split_me); // optimize me
221 r_list_delete_data (n->all_neighbours, split_me); // boy this all_neighbours is so retarding perf here
222 r_list_delete_data (split_me->all_neighbours, n);
223 r_list_append (n->all_neighbours, front);
224 r_list_append (n->in_nodes, front);
225 r_list_append (front->all_neighbours, n);
226 }
227 return front;
228 }
229
r_graph_del_edge(RGraph * t,RGraphNode * from,RGraphNode * to)230 R_API void r_graph_del_edge(RGraph *t, RGraphNode *from, RGraphNode *to) {
231 if (!from || !to || !r_graph_adjacent (t, from, to)) {
232 return;
233 }
234 r_list_delete_data (from->out_nodes, to);
235 r_list_delete_data (from->all_neighbours, to);
236 r_list_delete_data (to->in_nodes, from);
237 r_list_delete_data (to->all_neighbours, from);
238 t->n_edges--;
239 }
240
241 // XXX remove comments and static inline all this crap
242 /* returns the list of nodes reachable from `n` */
r_graph_get_neighbours(const RGraph * g,const RGraphNode * n)243 R_API const RList *r_graph_get_neighbours(const RGraph *g, const RGraphNode *n) {
244 return n? n->out_nodes: NULL;
245 }
246
247 /* returns the n-th nodes reachable from the give node `n`.
248 * This, of course, depends on the order of the nodes. */
r_graph_nth_neighbour(const RGraph * g,const RGraphNode * n,int nth)249 R_API RGraphNode *r_graph_nth_neighbour(const RGraph *g, const RGraphNode *n, int nth) {
250 return n? (RGraphNode *)r_list_get_n (n->out_nodes, nth): NULL;
251 }
252
253 /* returns the list of nodes that can reach `n` */
r_graph_innodes(const RGraph * g,const RGraphNode * n)254 R_API const RList *r_graph_innodes(const RGraph *g, const RGraphNode *n) {
255 return n? n->in_nodes: NULL;
256 }
257
258 /* returns the list of nodes reachable from `n` and that can reach `n`. */
r_graph_all_neighbours(const RGraph * g,const RGraphNode * n)259 R_API const RList *r_graph_all_neighbours(const RGraph *g, const RGraphNode *n) {
260 return n? n->all_neighbours: NULL;
261 }
262
r_graph_get_nodes(const RGraph * g)263 R_API const RList *r_graph_get_nodes(const RGraph *g) {
264 return g? g->nodes: NULL;
265 }
266
267 /* true if there is an edge from the node `from` to the node `to` */
r_graph_adjacent(const RGraph * g,const RGraphNode * from,const RGraphNode * to)268 R_API bool r_graph_adjacent(const RGraph *g, const RGraphNode *from, const RGraphNode *to) {
269 if (!g || !from) {
270 return false;
271 }
272 return r_list_contains (from->out_nodes, to);
273 }
274
r_graph_dfs_node(RGraph * g,RGraphNode * n,RGraphVisitor * vis)275 R_API void r_graph_dfs_node(RGraph *g, RGraphNode *n, RGraphVisitor *vis) {
276 if (!g || !n || !vis) {
277 return;
278 }
279 int *color = R_NEWS0 (int, g->last_index);
280 if (color) {
281 dfs_node (g, n, vis, color, true);
282 free (color);
283 }
284 }
285
r_graph_dfs_node_reverse(RGraph * g,RGraphNode * n,RGraphVisitor * vis)286 R_API void r_graph_dfs_node_reverse(RGraph *g, RGraphNode *n, RGraphVisitor *vis) {
287 if (!g || !n || !vis) {
288 return;
289 }
290 int *color = R_NEWS0 (int, g->last_index);
291 if (color) {
292 dfs_node (g, n, vis, color, false);
293 free (color);
294 }
295 }
296
r_graph_dfs(RGraph * g,RGraphVisitor * vis)297 R_API void r_graph_dfs(RGraph *g, RGraphVisitor *vis) {
298 r_return_if_fail (g && vis);
299 RGraphNode *n;
300 RListIter *it;
301
302 int *color = R_NEWS0 (int, g->last_index);
303 if (color) {
304 r_list_foreach (g->nodes, it, n) {
305 if (color[n->idx] == WHITE_COLOR) {
306 dfs_node (g, n, vis, color, true);
307 }
308 }
309 free (color);
310 }
311 }
312