1 /* radare - BSD 3 Clause License - Copyright 2017 - MaskRay */
2
3 #include <stdio.h>
4
5 #include <r_util/r_rbtree.h>
6 #include <r_util.h>
7
red(RBNode * x)8 static inline bool red(RBNode *x) {
9 return x && x->red;
10 }
11
zag(RBNode * x,int dir,RBNodeSum sum)12 static inline RBNode *zag(RBNode *x, int dir, RBNodeSum sum) {
13 RBNode *y = x->child[dir];
14 x->child[dir] = y->child[!dir];
15 y->child[!dir] = x;
16 x->red = true;
17 y->red = false;
18 if (sum) {
19 sum (x);
20 }
21 return y;
22 }
23
zig_zag(RBNode * x,int dir,RBNodeSum sum)24 static inline RBNode *zig_zag(RBNode *x, int dir, RBNodeSum sum) {
25 RBNode *y = x->child[dir], *z = y->child[!dir];
26 y->child[!dir] = z->child[dir];
27 z->child[dir] = y;
28 x->child[dir] = z->child[!dir];
29 z->child[!dir] = x;
30 x->red = y->red = true;
31 z->red = false;
32 if (sum) {
33 sum (x);
34 sum (y);
35 }
36 return z;
37 }
38
bound_iter(RBNode * x,void * data,RBComparator cmp,bool upper,void * user)39 static inline RBIter bound_iter(RBNode *x, void *data, RBComparator cmp, bool upper, void *user) {
40 RBIter it;
41 it.len = 0;
42 while (x) {
43 int d = cmp (data, x, user);
44
45 if (d == 0) {
46 it.path[it.len++] = x;
47 return it;
48 }
49
50 if (d < 0) {
51 if (!upper) {
52 it.path[it.len++] = x;
53 }
54 x = x->child[0];
55 } else {
56 if (upper) {
57 it.path[it.len++] = x;
58 }
59 x = x->child[1];
60 }
61 }
62
63 return it;
64 }
65
66 /*
67 static void _check1(RBNode *x, int dep, int black, bool leftmost) {
68 static int black_;
69 if (x) {
70 black += !x->red;
71 if (x->red && ((x->child[0] && x->child[0]->red) || (x->child[1] && x->child[1]->red))) {
72 printf ("error: red violation\n");
73 }
74 _check1 (x->child[0], dep + 1, black, leftmost);
75 _check1 (x->child[1], dep + 1, black, false);
76 } else if (leftmost) {
77 black_ = black;
78 } else if (black_ != black) {
79 printf ("error: different black height\n");
80 }
81 }
82
83 static void _check(RBNode *x) {
84 _check1 (x, 0, 0, true);
85 }
86 */
87
88 // Returns true if a node with an equal key is deleted
r_rbtree_aug_delete(RBNode ** root,void * data,RBComparator cmp,void * cmp_user,RBNodeFree freefn,void * free_user,RBNodeSum sum)89 R_API bool r_rbtree_aug_delete(RBNode **root, void *data, RBComparator cmp, void *cmp_user, RBNodeFree freefn, void *free_user, RBNodeSum sum) {
90 RBNode head, *del = NULL, **del_link = NULL, *g = NULL, *p = NULL, *q = &head, *path[R_RBTREE_MAX_HEIGHT];
91 int d = 1, d2, dep = 0;
92 head.child[0] = NULL;
93 head.child[1] = *root;
94 while (q->child[d]) {
95 d2 = d;
96 g = p;
97 p = q;
98 if (del_link) {
99 d = 1;
100 } else {
101 d = cmp (data, q->child[d2], cmp_user);
102 if (d < 0) {
103 d = 0;
104 } else if (d > 0) {
105 d = 1;
106 } else {
107 del_link = &q->child[d2];
108 }
109 }
110 if (q != &head) {
111 if (dep >= R_RBTREE_MAX_HEIGHT) {
112 eprintf ("Too deep tree\n");
113 break;
114 }
115 path[dep++] = q;
116 }
117 q = q->child[d2];
118 if (q->red || red (q->child[d])) {
119 continue;
120 }
121 if (red (q->child[!d])) {
122 if (del_link && *del_link == q) {
123 del_link = &q->child[!d]->child[d];
124 }
125 p->child[d2] = zag (q, !d, sum);
126 p = p->child[d2];
127 if (dep >= R_RBTREE_MAX_HEIGHT) {
128 eprintf ("Too deep tree\n");
129 break;
130 }
131 path[dep++] = p;
132 } else {
133 RBNode *s = p->child[!d2];
134 if (!s) {
135 continue;
136 }
137 if (!red (s->child[0]) && !red (s->child[1])) {
138 p->red = false;
139 q->red = s->red = true;
140 } else {
141 int d3 = g->child[0] != p;
142 RBNode *t;
143 if (red (s->child[d2])) {
144 if (del_link && *del_link == p) {
145 del_link = &s->child[d2]->child[d2];
146 }
147 t = zig_zag (p, !d2, sum);
148 } else {
149 if (del_link && *del_link == p) {
150 del_link = &s->child[d2];
151 }
152 t = zag (p, !d2, sum);
153 }
154 t->red = q->red = true;
155 t->child[0]->red = t->child[1]->red = false;
156 g->child[d3] = t;
157 path[dep - 1] = t;
158 path[dep++] = p;
159 }
160 }
161 }
162 if (del_link) {
163 del = *del_link;
164 p->child[q != p->child[0]] = q->child[q->child[0] == NULL];
165 if (del != q) {
166 *q = *del;
167 *del_link = q;
168 }
169 if (freefn) {
170 freefn (del, free_user);
171 }
172 }
173 if (sum) {
174 while (dep--) {
175 sum (path[dep] == del ? q : path[dep]);
176 }
177 }
178 if ((*root = head.child[1])) {
179 (*root)->red = false;
180 }
181 return del;
182 }
183
184 // Returns true if stuff got inserted, else false
r_rbtree_aug_insert(RBNode ** root,void * data,RBNode * node,RBComparator cmp,void * cmp_user,RBNodeSum sum)185 R_API bool r_rbtree_aug_insert(RBNode **root, void *data, RBNode *node, RBComparator cmp, void *cmp_user, RBNodeSum sum) {
186 node->child[0] = node->child[1] = NULL;
187 if (!*root) {
188 *root = node;
189 node->red = false;
190 if (sum) {
191 sum (node);
192 }
193 return true;
194 }
195 RBNode *t = NULL, *g = NULL, *p = NULL, *q = *root;
196 int d = 0, dep = 0;
197 bool done = false;
198 RBNode *path[R_RBTREE_MAX_HEIGHT];
199 for (;;) {
200 if (!q) {
201 q = node;
202 q->red = true;
203 p->child[d] = q;
204 done = true;
205 } else if (red (q->child[0]) && red (q->child[1])) {
206 q->child[0]->red = q->child[1]->red = false;
207 if (q != *root) {
208 q->red = true;
209 }
210 }
211 if (q->red && p && p->red) {
212 int d3 = t ? t->child[0] != g : -1, d2 = g->child[0] != p;
213 if (p->child[d2] == q) {
214 g = zag (g, d2, sum);
215 dep--;
216 path[dep - 1] = g;
217 } else {
218 g = zig_zag (g, d2, sum);
219 dep -= 2;
220 }
221 if (t) {
222 t->child[d3] = g;
223 } else {
224 *root = g;
225 }
226 }
227 if (done) {
228 break;
229 }
230 d = cmp (data, q, cmp_user);
231 t = g;
232 g = p;
233 p = q;
234 if (dep >= R_RBTREE_MAX_HEIGHT) {
235 eprintf ("Too deep tree\n");
236 break;
237 }
238 path[dep++] = q;
239 if (d < 0) {
240 d = 0;
241 q = q->child[0];
242 } else {
243 d = 1;
244 q = q->child[1];
245 }
246 }
247 if (sum) {
248 sum (q);
249 while (dep) {
250 sum (path[--dep]);
251 }
252 }
253 return done;
254 }
255
256 // returns true if the sum has been updated, false if node has not been found
r_rbtree_aug_update_sum(RBNode * root,void * data,RBNode * node,RBComparator cmp,void * cmp_user,RBNodeSum sum)257 R_API bool r_rbtree_aug_update_sum(RBNode *root, void *data, RBNode *node, RBComparator cmp, void *cmp_user, RBNodeSum sum) {
258 size_t dep = 0;
259 RBNode *path[R_RBTREE_MAX_HEIGHT];
260 RBNode *cur = root;
261 for (;;) {
262 if (!cur) {
263 return false;
264 }
265 if (dep >= R_RBTREE_MAX_HEIGHT) {
266 eprintf ("Too deep tree\n");
267 return false;
268 }
269 path[dep] = cur;
270 dep++;
271 if (cur == node) {
272 break;
273 }
274 int d = cmp (data, cur, cmp_user);
275 cur = cur->child[(d < 0)? 0: 1];
276 }
277
278 for (; dep > 0; dep--) {
279 sum (path[dep - 1]);
280 }
281 return true;
282 }
283
r_rbtree_delete(RBNode ** root,void * data,RBComparator cmp,void * cmp_user,RBNodeFree freefn,void * free_user)284 R_API bool r_rbtree_delete(RBNode **root, void *data, RBComparator cmp, void *cmp_user, RBNodeFree freefn, void *free_user) {
285 return r_rbtree_aug_delete (root, data, cmp, cmp_user, freefn, free_user, NULL);
286 }
287
r_rbtree_find(RBNode * x,void * data,RBComparator cmp,void * user)288 R_API RBNode *r_rbtree_find(RBNode *x, void *data, RBComparator cmp, void *user) {
289 while (x) {
290 int d = cmp (data, x, user);
291 if (d < 0) {
292 x = x->child[0];
293 } else if (d > 0) {
294 x = x->child[1];
295 } else {
296 return x;
297 }
298 }
299 return NULL;
300 }
301
r_rbtree_free(RBNode * x,RBNodeFree freefn,void * user)302 R_API void r_rbtree_free(RBNode *x, RBNodeFree freefn, void *user) {
303 if (x) {
304 r_rbtree_free (x->child[0], freefn, user);
305 r_rbtree_free (x->child[1], freefn, user);
306 freefn (x, user);
307 }
308 }
309
r_rbtree_insert(RBNode ** root,void * data,RBNode * node,RBComparator cmp,void * user)310 R_API void r_rbtree_insert(RBNode **root, void *data, RBNode *node, RBComparator cmp, void *user) {
311 r_rbtree_aug_insert (root, data, node, cmp, user, NULL);
312 }
313
r_rbtree_lower_bound(RBNode * x,void * data,RBComparator cmp,void * user)314 R_API RBNode *r_rbtree_lower_bound(RBNode *x, void *data, RBComparator cmp, void *user) {
315 RBNode *ret = NULL;
316 while (x) {
317 int d = cmp (data, x, user);
318 if (d <= 0) {
319 ret = x;
320 x = x->child[0];
321 } else {
322 x = x->child[1];
323 }
324 }
325 return ret;
326 }
327
r_rbtree_lower_bound_forward(RBNode * root,void * data,RBComparator cmp,void * user)328 R_API RBIter r_rbtree_lower_bound_forward(RBNode *root, void *data, RBComparator cmp, void *user) {
329 return bound_iter (root, data, cmp, false, user);
330 }
331
r_rbtree_upper_bound(RBNode * x,void * data,RBComparator cmp,void * user)332 R_API RBNode *r_rbtree_upper_bound(RBNode *x, void *data, RBComparator cmp, void *user) {
333 void *ret = NULL;
334 while (x) {
335 int d = cmp (data, x, user);
336 if (d < 0) {
337 x = x->child[0];
338 } else {
339 ret = x;
340 x = x->child[1];
341 }
342 }
343 return ret;
344 }
345
r_rbtree_upper_bound_backward(RBNode * root,void * data,RBComparator cmp,void * user)346 R_API RBIter r_rbtree_upper_bound_backward(RBNode *root, void *data, RBComparator cmp, void *user) {
347 return bound_iter (root, data, cmp, true, user);
348 }
349
_first(RBNode * x,int dir)350 static RBIter _first(RBNode *x, int dir) {
351 RBIter it;
352 it.len = 0;
353 for (; x; x = x->child[dir]) {
354 it.path[it.len++] = x;
355 }
356 return it;
357 }
358
r_rbtree_first(RBNode * tree)359 R_API RBIter r_rbtree_first(RBNode *tree) {
360 return _first (tree, 0);
361 }
362
r_rbtree_last(RBNode * tree)363 R_API RBIter r_rbtree_last(RBNode *tree) {
364 return _first (tree, 1);
365 }
366
_next(RBIter * it,int dir)367 static inline void _next(RBIter *it, int dir) {
368 RBNode *x = it->path[--it->len];
369 for (x = x->child[!dir]; x; x = x->child[dir]) {
370 it->path[it->len++] = x;
371 }
372 }
373
r_rbtree_iter_next(RBIter * it)374 R_API void r_rbtree_iter_next(RBIter *it) {
375 _next (it, 0);
376 }
377
r_rbtree_iter_prev(RBIter * it)378 R_API void r_rbtree_iter_prev(RBIter *it) {
379 _next (it, 1);
380 }
381
r_rbtree_cont_new(void)382 R_API RContRBTree *r_rbtree_cont_new(void) {
383 return R_NEW0 (RContRBTree);
384 }
385
r_rbtree_cont_newf(RContRBFree f)386 R_API RContRBTree *r_rbtree_cont_newf(RContRBFree f) {
387 RContRBTree *tree = r_rbtree_cont_new ();
388 if (tree) {
389 tree->free = f;
390 }
391 return tree;
392 }
393
394 typedef struct rcrb_cmp_wrap_t {
395 RContRBCmp cmp;
396 RContRBFree free;
397 void *user;
398 } RCRBCmpWrap;
399
cont_rbtree_cmp_wrapper(const void * incoming,const RBNode * in_tree,void * user)400 static int cont_rbtree_cmp_wrapper(const void *incoming, const RBNode *in_tree, void *user) {
401 RCRBCmpWrap *cmp_wrap = (RCRBCmpWrap *)user;
402 RContRBNode *incoming_node = (RContRBNode *)incoming;
403 RContRBNode *in_tree_node = container_of ((RBNode*)in_tree, RContRBNode, node);
404 return cmp_wrap->cmp (incoming_node->data, in_tree_node->data, cmp_wrap->user);
405 }
406
cont_rbtree_search_cmp_wrapper(const void * incoming,const RBNode * in_tree,void * user)407 static int cont_rbtree_search_cmp_wrapper(const void *incoming, const RBNode *in_tree, void *user) {
408 RCRBCmpWrap *cmp_wrap = (RCRBCmpWrap *)user;
409 RContRBNode *in_tree_node = container_of ((RBNode*)in_tree, RContRBNode, node);
410 return cmp_wrap->cmp ((void *)incoming, in_tree_node->data, cmp_wrap->user);
411 }
412
cont_rbtree_free_cmp_wrapper(const void * data,const RBNode * in_tree,void * user)413 static int cont_rbtree_free_cmp_wrapper(const void *data, const RBNode *in_tree, void *user) {
414 RCRBCmpWrap *cmp_wrap = (RCRBCmpWrap *)user;
415 const int ret = cont_rbtree_cmp_wrapper ((void*)data, in_tree, user);
416 if (!ret && cmp_wrap->free) { //this is for deleting
417 RContRBNode *in_tree_node = container_of ((void*)in_tree, RContRBNode, node);
418 cmp_wrap->free (in_tree_node->data);
419 }
420 return ret;
421 }
422
r_rbtree_cont_insert(RContRBTree * tree,void * data,RContRBCmp cmp,void * user)423 R_API bool r_rbtree_cont_insert(RContRBTree *tree, void *data, RContRBCmp cmp, void *user) {
424 r_return_val_if_fail (tree && cmp, false);
425 if (!tree->root) {
426 tree->root = R_NEW0 (RContRBNode);
427 if (tree->root) {
428 tree->root->data = data;
429 // tree->root->node.red = false; // not needed since R_NEW0 initializes with false anyway
430 return true;
431 }
432 eprintf ("Allocation failed\n");
433 return false;
434 }
435 RContRBNode *incoming_node = R_NEW0 (RContRBNode);
436 if (!incoming_node) {
437 eprintf ("Allocation failed\n");
438 return false;
439 }
440 incoming_node->data = data;
441 RCRBCmpWrap cmp_wrap = { cmp, NULL, user };
442 RBNode *root_node = &tree->root->node;
443 const bool ret = r_rbtree_aug_insert (&root_node, incoming_node,
444 &incoming_node->node, cont_rbtree_cmp_wrapper, &cmp_wrap, NULL);
445 if (root_node != (&tree->root->node)) {
446 tree->root = container_of (root_node, RContRBNode, node); //cursed augmentation garbage
447 }
448 if (!ret) {
449 eprintf ("Insertion failed\n");
450 free (incoming_node);
451 }
452 return ret;
453 }
454
cont_node_free(RBNode * node,void * user)455 static void cont_node_free(RBNode *node, void *user) {
456 RContRBNode *contnode = container_of (node, RContRBNode, node);
457 if (user) {
458 ((RContRBFree)user) (contnode->data);
459 }
460 free (contnode);
461 }
462
r_rbtree_cont_delete(RContRBTree * tree,void * data,RContRBCmp cmp,void * user)463 R_API bool r_rbtree_cont_delete(RContRBTree *tree, void *data, RContRBCmp cmp, void *user) {
464 if (!(tree && cmp && tree->root)) {
465 return false;
466 }
467 RCRBCmpWrap cmp_wrap = { cmp, tree->free, user };
468 RContRBNode data_wrap = { { { NULL, NULL }, false }, data };
469 RBNode *root_node = &tree->root->node;
470 const bool ret = r_rbtree_aug_delete (&root_node, &data_wrap, cont_rbtree_free_cmp_wrapper, &cmp_wrap, cont_node_free, NULL, NULL);
471 if (root_node != (&tree->root->node)) { //can this crash?
472 tree->root = container_of (root_node, RContRBNode, node); //cursed augmentation garbage
473 }
474 return ret;
475 }
476
r_rbtree_cont_find(RContRBTree * tree,void * data,RContRBCmp cmp,void * user)477 R_API void *r_rbtree_cont_find(RContRBTree *tree, void *data, RContRBCmp cmp, void *user) {
478 r_return_val_if_fail (tree && cmp, NULL);
479 if (!tree->root) {
480 return NULL;
481 }
482 RCRBCmpWrap cmp_wrap = { cmp, NULL, user };
483 // RBNode search_node = tree->root->node;
484 RBNode *result_node = r_rbtree_find (&tree->root->node, data, cont_rbtree_search_cmp_wrapper, &cmp_wrap);
485 if (result_node) {
486 return (container_of (result_node, RContRBNode, node))->data;
487 }
488 return NULL;
489 }
490
491 // not a direct pendant to r_rbtree_first, but similar
492 // returns first element in the tree, not an iter or a node
r_rbtree_cont_first(RContRBTree * tree)493 R_API void *r_rbtree_cont_first(RContRBTree *tree) {
494 r_return_val_if_fail (tree, NULL);
495 if (!tree->root) {
496 // empty tree
497 return NULL;
498 }
499 RBIter iter = r_rbtree_first (&tree->root->node);
500 if (iter.len == 0) {
501 // also empty tree
502 return NULL;
503 }
504 RBNode *first_rbnode = iter.path[iter.len-1];
505 return (container_of (first_rbnode, RContRBNode, node))->data;
506 }
507
r_rbtree_cont_free(RContRBTree * tree)508 R_API void r_rbtree_cont_free(RContRBTree *tree) {
509 if (tree && tree->root) {
510 r_rbtree_free (&tree->root->node, cont_node_free, tree->free);
511 }
512 free (tree);
513 }
514