1 /* 2 * Copyright (c) 2023 Institute of Parallel And Distributed Systems (IPADS), Shanghai Jiao Tong University (SJTU) 3 * Licensed under the Mulan PSL v2. 4 * You can use this software according to the terms and conditions of the Mulan PSL v2. 5 * You may obtain a copy of Mulan PSL v2 at: 6 * http://license.coscl.org.cn/MulanPSL2 7 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR 8 * IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR 9 * PURPOSE. 10 * See the Mulan PSL v2 for more details. 11 */ 12 13 #pragma once 14 15 #include <chcore/container/rbtree.h> 16 #include <chcore/container/list.h> 17 18 /** 19 * @brief A node in a rbtree plus. Users can embed this struct like rb_node 20 * or list_head in their own types to achieve generic in C. 21 * 22 * In implementation, we exploit a "two-level" generic to re-use existing 23 * rbtree and list implementation while providing a simple interface to users. 24 * The first level generic is for users: they embed rbp_node in their types, 25 * pass rbp_node* to our APIs, and use rbp_entry to get their types back. 26 * 27 * The second level is internally used by us. We break a rbp_node into a 28 * rb_node and a list_head, then link them into a rbtree and a list 29 * respectively. Decided by the APIs invoked by users, we levergae rb_entry or 30 * list_entry to get rbp_node* back, and return them to users. 31 */ 32 struct rbp_node { 33 struct rb_node rbnode; 34 struct list_head list_node; 35 }; 36 37 /** 38 * @brief RB+ Tree, or rbtree plus, is a red-black tree variant which support 39 * fast traversal operation of its nodes in order. This name is inspired by 40 * B+ Tree, which has a similar traverse feature. 41 * 42 * It's implemented by combining a rbtree and a list, and hooking insert/erase 43 * operation to manipulate rbtree and list simultaneously. Although it's a 44 * combined data structure, users can still use it without any knowledge of the 45 * underlying data structures, they just need to embed a rbp_node in their own 46 * types, simliar to usages of rbtree and list. 47 */ 48 struct rbtree_plus { 49 struct rb_root root; 50 struct list_head head; 51 }; 52 53 void init_rbtree_plus(struct rbtree_plus *this); 54 55 #define rbp_entry(ptr, type, member) container_of(ptr, type, member) 56 57 /* 58 * compare functions defination 59 * We expect those functions have following semantics: 60 * cmp_xxx_func: 61 * return 0 if keys of left operand equal to right operand 62 * return <0 if left < right 63 * return >0 if left > right 64 * less_func: 65 * return true if left < right 66 * return false if left >= right 67 */ 68 typedef int (*comp_rbp_key_func)(const void *key, const struct rbp_node *node); 69 typedef bool (*less_rbp_func)(const struct rbp_node *lhs, 70 const struct rbp_node *rhs); 71 72 /* 73 * search interfaces 74 */ 75 /* 76 * rbp_search - search for a node matching @key in rbtree plus 77 * 78 * @this: rbtree plus to be searched 79 * @key: pointer to user-specific key. We use void* to implement generality 80 * @cmp: user-provided compare function, comparing @key and rbp_node in rbtree 81 * plus. Users should implement their logic to extract key from rbp_node 82 * pointer. 83 * 84 * return: 85 * pointer of targeted node if @key exists in rbtree plus. 86 * NULL if no matching node is found. 87 */ 88 struct rbp_node *rbp_search(struct rbtree_plus *this, const void *key, 89 comp_rbp_key_func cmp); 90 /* 91 * rbp_search - search for the **leftmost** node matching @key in rbtree plus 92 * 93 * @this: rbtree plus to be searched 94 * @key: pointer to user-specific key. We use void* to implement generality 95 * @cmp: user-provided compare function. 96 * 97 * return: 98 * pointer of targeted node if @key exists in rbtree plus. 99 * NULL if no matching node is found. 100 */ 101 struct rbp_node *rbp_search_first(struct rbtree_plus *this, const void *key, 102 comp_rbp_key_func cmp); 103 104 /* 105 * rbp_search - search for the node **nearest** to @key in rbtree plus 106 * 107 * If there is a node matches @key, it would be returned. Otherwhise, 108 * this method would return the node whose key is the greatest in nodes 109 * that are less than @key. Or the node whose key is the least in nodes 110 * that are greater than @key. In other words, it would return the node 111 * that serve as "insertion point" for @key. 112 * 113 * @this: rbtree plus to be searched 114 * @key: pointer to user-specific key. We use void* to implement generality 115 * @cmp: user-provided compare function. 116 * 117 * return: 118 * pointer of targeted node if @key exists in rbtree plus. 119 * NULL if no matching node is found. 120 */ 121 struct rbp_node *rbp_search_nearest(struct rbtree_plus *this, const void *key, 122 comp_rbp_key_func cmp); 123 124 /* 125 * insert interfaces 126 */ 127 /* 128 * rbp_insert - insert a given @node into rbtree plus. @node 129 * will be inserted as right child of existing nodes if they have the same key. 130 * 131 * @this: rbtree plus to be inserted 132 * @node: node to be inserted. Users should embed rbp_node in their custom types 133 * , allocate those types and provide pointers of rbp_node in those types. 134 * @less: user-provided less function 135 * 136 */ 137 void rbp_insert(struct rbtree_plus *this, struct rbp_node *data, 138 less_rbp_func less); 139 140 /* 141 * erase interfaces 142 */ 143 /* 144 * rbp_erase - remove @node from rbtree plus @this. Due to rbp_node embedded in 145 * users' custom types, @node is not a pointer to head of a heap block. So 146 * rbp_erase won't free memory of @node. User code should free memory using 147 * their types after erase rbp_node contained in those types from @this. 148 * 149 * @this: rbtree plus to be erased 150 * @node: node to be erased 151 */ 152 void rbp_erase(struct rbtree_plus *this, struct rbp_node *node); 153 154 /* 155 * replace interfaces 156 */ 157 /* 158 * rbp_replace_node - replace @old with @new directly without rebalancing and 159 * recoloring. Users should make sure that keys of old and new are identical, 160 * otherwise the rbtree plus would be inconsistent. 161 * 162 * @this: rbtree plus to be replaced 163 * @old: old node in @this 164 * @new: new node to take over @old, should has identical key with @old. 165 */ 166 void rbp_replace_node(struct rbtree_plus *this, struct rbp_node *old, 167 struct rbp_node *new); 168 169 /* 170 * traverse interfaces 171 */ 172 /* 173 * rbp_next - return the next node of @node in rbtree plus. If @node is the last 174 * node, return NULL. To check whether @node is the last node, rbtree_plus it 175 * belongs to is required: @this. 176 */ 177 struct rbp_node *rbp_next(const struct rbtree_plus *this, 178 const struct rbp_node *node); 179 /* 180 * rbp_prev - return the previous node of @node in rbtree plus. If @node is the 181 * first node, return NULL. To check whether @node is the first node, 182 * rbtree_plus it belongs to is required: @this. 183 */ 184 struct rbp_node *rbp_prev(const struct rbtree_plus *this, 185 const struct rbp_node *node); 186 /* 187 * rbp_first - return the first node of rbtree plus. If rbtree plus is empty, 188 * return NULL. 189 */ 190 struct rbp_node *rbp_first(const struct rbtree_plus *this); 191 /* 192 * rbp_last - return the last node of rbtree plus. If rbtree plus is empty, 193 * return NULL. 194 */ 195 struct rbp_node *rbp_last(const struct rbtree_plus *this); 196 /* 197 * rbp_next_match - return the next node of @node if it matches @key at the same 198 * time. Otherwise, return NULL. This function can be used to iterate over all 199 * nodes with a given key in rbtree plus. 200 */ 201 struct rbp_node *rbp_next_match(const struct rbtree_plus *this, 202 const struct rbp_node *node, const void *key, 203 comp_rbp_key_func cmp); 204 205 #define rbp_for_each(root, node) \ 206 for (node = rbp_first(root); node; node = rbp_next(root, node)) 207 208 #define rbp_key_for_each(root, node, key, cmp) \ 209 for (node = rbp_search_first(root, key, cmp); node; \ 210 node = rbp_next_match(root, node, key, cmp)) 211 212 #define rbp_for_each_safe(root, node, tmp) \ 213 for (node = rbp_first(root), tmp = rbp_next(root, node); node; \ 214 node = tmp, tmp = rbp_next(root, node)) 215