1 /* radare2 - LGPL - Copyright 2019 - thestr4ng3r */
2
3 #ifndef R_INTERVALTREE_H
4 #define R_INTERVALTREE_H
5
6 #include "r_rbtree.h"
7 #include "../r_types.h"
8
9 /*
10 * RIntervalTree is a special RBTree (augmented red-black tree)
11 * that holds its entries, each associated with a interval,
12 * ordered by the start of the interval.
13 *
14 * It allows efficient lookup for intersections with a given interval or value.
15 * This is achieved by, at each node, saving the maximum value of the node
16 * and all of its children.
17 *
18 * It can hold multiple entries with the same start or end.
19 * For multiple entries with the same start, the ordering is undefined.
20 */
21
22 typedef struct r_interval_node_t {
23 RBNode node;
24 ut64 start; // inclusive, key of the node
25 ut64 end; // may be inclusive or exclusive, this is only determined by how they are queried
26 ut64 max_end; // augmented value, maximum end of this node and all of its children
27 void *data;
28 } RIntervalNode;
29
30 typedef void (*RIntervalNodeFree)(void *data);
31
32 typedef struct r_interval_tree_t {
33 RIntervalNode *root;
34 RIntervalNodeFree free;
35 } RIntervalTree;
36
37 R_API void r_interval_tree_init(RIntervalTree *tree, RIntervalNodeFree free);
38 R_API void r_interval_tree_fini(RIntervalTree *tree);
39
40 // return false if the insertion failed.
41 R_API bool r_interval_tree_insert(RIntervalTree *tree, ut64 start, ut64 end, void *data);
42
43 // Removes a given node from the tree. The node will be freed.
44 // If free is true, the data in the node is freed as well.
45 // false if the removal failed
46 // Complexity is O(log(n) + m) if there are m nodes with the same start as the given node.
47 R_API bool r_interval_tree_delete(RIntervalTree *tree, RIntervalNode *node, bool free);
48
49 // Change start/end of a given node.
50 // It is more efficient if only the end changed.
51 // The RIntervalNode pointer is INVALID after this operation!
52 // Complexity is O(log(n) + m) if there are m nodes with the same start as the given node.
53 R_API bool r_interval_tree_resize(RIntervalTree *tree, RIntervalNode *node, ut64 new_start, ut64 new_end);
54
55 // Returns an iterator that starts at the leftmost node that has the given start
56 // Iterating over it will yield all nodes with given start, then all with a higher one.
57 R_API RBIter r_interval_tree_first_at(RIntervalTree *tree, ut64 start);
58
59 // Returns a node that starts at exactly start or NULL
60 R_API RIntervalNode *r_interval_tree_node_at(RIntervalTree *tree, ut64 start);
61
62 // Returns a node that starts at exactly start and contains data or NULL
63 R_API RIntervalNode *r_interval_tree_node_at_data(RIntervalTree *tree, ut64 start, void *data);
64
65 // Same as r_interval_tree_node_at, but directly returns the contained value or NULL
r_interval_tree_at(RIntervalTree * tree,ut64 start)66 static inline void *r_interval_tree_at(RIntervalTree *tree, ut64 start) {
67 RIntervalNode *node = r_interval_tree_node_at (tree, start);
68 return node ? node->data : NULL;
69 }
70
71 typedef bool (*RIntervalIterCb)(RIntervalNode *node, void *user);
72
73 // Call cb for all entries starting at exactly start
74 R_API bool r_interval_tree_all_at(RIntervalTree *tree, ut64 start, RIntervalIterCb cb, void *user);
75
76 // Call cb for all entries whose intervals contain value
77 // end_inclusive if true, all start/end values are considered inclusive/inclusive, else inclusive/exclusive
78 R_API bool r_interval_tree_all_in(RIntervalTree *tree, ut64 value, bool end_inclusive, RIntervalIterCb cb, void *user);
79
80 // Call cb for all entries whose intervals intersect the given interval (might not contain it completely)
81 // end_inclusive if true, all start/end values are considered inclusive/inclusive, else inclusive/exclusive
82 R_API bool r_interval_tree_all_intersect(RIntervalTree *tree, ut64 start, ut64 end, bool end_inclusive, RIntervalIterCb cb, void *user);
83
84 typedef RBIter RIntervalTreeIter;
85
r_interval_tree_iter_get(RIntervalTreeIter * it)86 static inline RIntervalNode *r_interval_tree_iter_get(RIntervalTreeIter *it) {
87 return r_rbtree_iter_get (it, RIntervalNode, node);
88 }
89
90 #define r_interval_tree_foreach(tree, it, dat) \
91 for ((it) = r_rbtree_first (&(tree)->root->node); r_rbtree_iter_has (&it) && (dat = r_interval_tree_iter_get (&it)->data); r_rbtree_iter_next (&(it)))
92
93 #define r_interval_tree_foreach_prev(tree, it, dat) \
94 for ((it) = r_rbtree_last (&(tree)->root->node); r_rbtree_iter_has (&it) && (dat = r_rbtree_iter_get (&it, RIntervalNode, node)->data); r_rbtree_iter_prev (&(it)))
95
96
97 #endif //R_INTERVALTREE_H
98