1 #ifndef R2_RBTREE_H 2 #define R2_RBTREE_H 3 4 #include <limits.h> 5 #include <stdbool.h> 6 #include <stddef.h> 7 8 #include "r_list.h" 9 10 #ifdef __cplusplus 11 extern "C" { 12 #endif 13 14 // max height <= 2 * floor(log2(n + 1)) 15 // We use `int` for size, so <= 2 * 31 16 #define R_RBTREE_MAX_HEIGHT 62 17 18 // Singleton can be zero initialized 19 typedef struct r_rb_node_t { 20 struct r_rb_node_t *child[2]; 21 bool red; 22 } RBNode; 23 24 typedef RBNode* RBTree; 25 26 // incoming < in_tree => return < 0 27 // incoming == in_tree => return == 0 28 // incoming > in_tree => return > 0 29 typedef int (*RBComparator)(const void *incoming, const RBNode *in_tree, void *user); 30 31 typedef void (*RBNodeFree)(RBNode *node, void *user); 32 typedef void (*RBNodeSum)(RBNode *node); 33 34 typedef struct r_rb_iter_t { 35 // current depth 36 // if len == 0, the iterator is at the end/empty 37 // else path[len-1] is the current node 38 size_t len; 39 40 // current path from root to the current node 41 // excluding nodes into whose right (or left, for reverse iteration) branch the iterator has descended 42 // (these nodes are before the current) 43 RBNode *path[R_RBTREE_MAX_HEIGHT]; 44 } RBIter; 45 46 typedef int (*RContRBCmp)(void *incoming, void *in, void *user); 47 typedef void (*RContRBFree)(void *); 48 typedef struct r_containing_rb_node_t { 49 RBNode node; 50 void *data; 51 } RContRBNode; 52 53 typedef struct r_containing_rb_tree_t { 54 RContRBNode *root; 55 RContRBFree free; 56 } RContRBTree; 57 58 // Routines for augmented red-black trees. The user should provide an aggregation (monoid sum) callback `sum` 59 // to calculate extra information such as size, sum, ... 60 R_API bool r_rbtree_aug_delete(RBNode **root, void *data, RBComparator cmp, void *cmp_user, RBNodeFree freefn, void *free_user, RBNodeSum sum); 61 R_API bool r_rbtree_aug_insert(RBNode **root, void *data, RBNode *node, RBComparator cmp, void *cmp_user, RBNodeSum sum); 62 R_API bool r_rbtree_aug_update_sum(RBNode *root, void *data, RBNode *node, RBComparator cmp, void *cmp_user, RBNodeSum sum); 63 64 R_API bool r_rbtree_delete(RBNode **root, void *data, RBComparator cmp, void *cmp_user, RBNodeFree freefn, void *free_user); 65 R_API RBNode *r_rbtree_find(RBNode *root, void *data, RBComparator cmp, void *user); 66 R_API void r_rbtree_free(RBNode *root, RBNodeFree freefn, void *user); 67 R_API void r_rbtree_insert(RBNode **root, void *data, RBNode *node, RBComparator cmp, void *user); 68 // Return the smallest node that is greater than or equal to `data` 69 R_API RBNode *r_rbtree_lower_bound(RBNode *root, void *data, RBComparator cmp, void *user); 70 // Return the greatest node that is less than or equal to `data` 71 R_API RBNode *r_rbtree_upper_bound(RBNode *root, void *data, RBComparator cmp, void *user); 72 73 // Create a forward iterator starting from the leftmost node 74 R_API RBIter r_rbtree_first(RBNode *root); 75 // Create a backward iterator starting from the rightmost node 76 R_API RBIter r_rbtree_last(RBNode *root); 77 78 // Iterate [lower_bound, end] forward, used with r_rbtree_iter_next 79 R_API RBIter r_rbtree_lower_bound_forward(RBNode *root, void *data, RBComparator cmp, void *user); 80 // Iterate [begin, upper_bound] backward, used with r_rbtree_iter_prev 81 R_API RBIter r_rbtree_upper_bound_backward(RBNode *root, void *data, RBComparator cmp, void *user); 82 83 // struct Node { int key; RBNode rb; }; 84 // r_rbtree_iter_get (it, struct Node, rb) 85 #define r_rbtree_iter_get(it, struc, rb) (container_of ((it)->path[(it)->len-1], struc, rb)) 86 // If the iterator still contains elements, including the current 87 #define r_rbtree_iter_has(it) ((it)->len) 88 // Move forward 89 R_API void r_rbtree_iter_next(RBIter *it); 90 // Move backward 91 R_API void r_rbtree_iter_prev(RBIter *it); 92 93 // Iterate all elements of the forward iterator 94 #define r_rbtree_iter_while(it, data, struc, rb) \ 95 for (; r_rbtree_iter_has(&it) && (data = r_rbtree_iter_get (&it, struc, rb)); r_rbtree_iter_next (&(it))) 96 97 // Iterate all elements of the backward iterator 98 #define r_rbtree_iter_while_prev(it, data, struc, rb) \ 99 for (; r_rbtree_iter_has(&it) && (data = r_rbtree_iter_get (&it, struc, rb)); r_rbtree_iter_prev (&(it))) 100 101 #define r_rbtree_foreach(root, it, data, struc, rb) \ 102 for ((it) = r_rbtree_first (root); r_rbtree_iter_has(&it) && (data = r_rbtree_iter_get (&it, struc, rb)); r_rbtree_iter_next (&(it))) 103 104 #define r_rbtree_foreach_prev(root, it, data, struc, rb) \ 105 for ((it) = r_rbtree_last (root); r_rbtree_iter_has(&it) && (data = r_rbtree_iter_get (&it, struc, rb)); r_rbtree_iter_prev (&(it))) 106 107 108 R_API RContRBTree *r_rbtree_cont_new(void); 109 R_API RContRBTree *r_rbtree_cont_newf(RContRBFree f); 110 R_API bool r_rbtree_cont_insert(RContRBTree *tree, void *data, RContRBCmp cmp, void *user); 111 R_API bool r_rbtree_cont_delete(RContRBTree *tree, void *data, RContRBCmp cmp, void *user); 112 R_API void *r_rbtree_cont_find(RContRBTree *tree, void *data, RContRBCmp cmp, void *user); 113 R_API void *r_rbtree_cont_first(RContRBTree *tree); 114 115 #define r_rbtree_cont_foreach(tree, it, dat) \ 116 for ((it) = r_rbtree_first ((tree)->root ? &(tree)->root->node : NULL); r_rbtree_iter_has(&it) && (dat = r_rbtree_iter_get (&it, RContRBNode, node)->data); r_rbtree_iter_next (&(it))) 117 118 #define r_rbtree_cont_foreach_prev(tree, it, dat) \ 119 for ((it) = r_rbtree_last ((tree)->root ? &(tree)->root->node : NULL); r_rbtree_iter_has(&it) && (dat = r_rbtree_iter_get (&it, RContRBNode, node)->data); r_rbtree_iter_prev (&(it))) 120 121 R_API void r_rbtree_cont_free(RContRBTree *tree); 122 123 #ifdef __cplusplus 124 } 125 #endif 126 127 #endif 128