1 /* $NetBSD: rbtree.h,v 1.18 2022/02/27 14:18:34 riastradh Exp $ */ 2 3 /*- 4 * Copyright (c) 2013 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Taylor R. Campbell. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 #ifndef _LINUX_RBTREE_H_ 33 #define _LINUX_RBTREE_H_ 34 35 #include <sys/rbtree.h> 36 37 #include <lib/libkern/libkern.h> 38 39 struct rb_root { 40 struct rb_tree rbr_tree; 41 }; 42 43 struct rb_root_cached { 44 struct rb_root rb_root; /* Linux API name */ 45 }; 46 47 #define rb_entry(P, T, F) container_of(P, T, F) 48 #define rb_entry_safe(P, T, F) \ 49 ({ \ 50 __typeof__(P) __p = (P); \ 51 __p ? container_of(__p, T, F) : NULL; \ 52 }) 53 54 /* 55 * Several of these functions take const inputs and return non-const 56 * outputs. That is a deliberate choice. It would be better if these 57 * functions could be const-polymorphic -- return const if given const, 58 * return non-const if given non-const -- but C doesn't let us express 59 * that. We are using them to adapt Linux code that is defined in 60 * terms of token-substitution macros, without types of their own, 61 * which happen to work out with both const and non-const variants. 62 * Presumably the Linux code compiles upstream and has some level of 63 * const type-checking in Linux, so this abuse of __UNCONST does not 64 * carry substantial risk over to this code here. 65 */ 66 67 static inline bool 68 RB_EMPTY_ROOT(const struct rb_root *root) 69 { 70 71 return RB_TREE_MIN(__UNCONST(&root->rbr_tree)) == NULL; 72 } 73 74 static inline struct rb_node * 75 rb_first(const struct rb_root *root) 76 { 77 char *vnode = RB_TREE_MIN(__UNCONST(&root->rbr_tree)); 78 79 if (vnode) 80 vnode += root->rbr_tree.rbt_ops->rbto_node_offset; 81 return (struct rb_node *)vnode; 82 } 83 84 static inline struct rb_node * 85 rb_next2(const struct rb_root *root, const struct rb_node *rbnode) 86 { 87 char *vnode = (char *)__UNCONST(rbnode); 88 89 vnode -= root->rbr_tree.rbt_ops->rbto_node_offset; 90 vnode = RB_TREE_NEXT(__UNCONST(&root->rbr_tree), vnode); 91 if (vnode) 92 vnode += root->rbr_tree.rbt_ops->rbto_node_offset; 93 return (struct rb_node *)vnode; 94 } 95 96 static inline struct rb_node * 97 rb_last(const struct rb_root *root) 98 { 99 char *vnode = RB_TREE_MAX(__UNCONST(&root->rbr_tree)); 100 101 if (vnode) 102 vnode += root->rbr_tree.rbt_ops->rbto_node_offset; 103 return (struct rb_node *)vnode; 104 } 105 106 static inline struct rb_node * 107 rb_first_cached(const struct rb_root_cached *root) 108 { 109 return rb_first(&root->rb_root); 110 } 111 112 static inline void 113 rb_erase(struct rb_node *rbnode, struct rb_root *root) 114 { 115 struct rb_tree *tree = &root->rbr_tree; 116 void *node = (char *)rbnode - tree->rbt_ops->rbto_node_offset; 117 118 rb_tree_remove_node(tree, node); 119 } 120 121 static inline void 122 rb_erase_cached(struct rb_node *rbnode, struct rb_root_cached *root) 123 { 124 rb_erase(rbnode, &root->rb_root); 125 } 126 127 static inline void 128 rb_replace_node(struct rb_node *old, struct rb_node *new, struct rb_root *root) 129 { 130 void *vold = (char *)old - root->rbr_tree.rbt_ops->rbto_node_offset; 131 void *vnew = (char *)new - root->rbr_tree.rbt_ops->rbto_node_offset; 132 void *collision __diagused; 133 134 rb_tree_remove_node(&root->rbr_tree, vold); 135 collision = rb_tree_insert_node(&root->rbr_tree, vnew); 136 KASSERT(collision == vnew); 137 } 138 139 static inline void 140 rb_replace_node_cached(struct rb_node *old, struct rb_node *new, 141 struct rb_root_cached *root) 142 { 143 rb_replace_node(old, new, &root->rb_root); 144 } 145 146 /* 147 * This violates the abstraction of rbtree(3) for postorder traversal 148 * -- children first, then parents -- so it is safe for cleanup code 149 * that just frees all the nodes without removing them from the tree. 150 */ 151 static inline struct rb_node * 152 rb_first_postorder(const struct rb_root *root) 153 { 154 struct rb_node *node, *child; 155 156 if ((node = root->rbr_tree.rbt_root) == NULL) 157 return NULL; 158 for (;; node = child) { 159 if ((child = node->rb_left) != NULL) 160 continue; 161 if ((child = node->rb_right) != NULL) 162 continue; 163 return node; 164 } 165 } 166 167 static inline struct rb_node * 168 rb_next2_postorder(const struct rb_root *root, struct rb_node *node) 169 { 170 struct rb_node *parent, *child; 171 172 if (node == NULL) 173 return NULL; 174 175 /* 176 * If we're at the root, there are no more siblings and no 177 * parent, so post-order iteration is done. 178 */ 179 if (RB_ROOT_P(&root->rbr_tree, node)) 180 return NULL; 181 parent = RB_FATHER(node); /* kinda sexist, innit */ 182 KASSERT(parent != NULL); 183 184 /* 185 * If we're the right child, we've already processed the left 186 * child (which may be gone by now), so just return the parent. 187 */ 188 if (RB_RIGHT_P(node)) 189 return parent; 190 191 /* 192 * Otherwise, move down to the leftmost child of our right 193 * sibling -- or return the parent if there is none. 194 */ 195 if ((node = parent->rb_right) == NULL) 196 return parent; 197 for (;; node = child) { 198 if ((child = node->rb_left) != NULL) 199 continue; 200 if ((child = node->rb_right) != NULL) 201 continue; 202 return node; 203 } 204 } 205 206 /* 207 * Extension to Linux API, which allows copying a struct rb_root object 208 * with `=' or `memcpy' and no additional relocation. 209 */ 210 static inline void 211 rb_move(struct rb_root *to, struct rb_root *from) 212 { 213 struct rb_node *root; 214 215 *to = *from; 216 memset(from, 0, sizeof(*from)); /* paranoia */ 217 if ((root = to->rbr_tree.rbt_root) == NULL) 218 return; 219 220 /* 221 * The root node's `parent' is a strict-aliasing-unsafe hack 222 * pointing at the root of the tree. 223 */ 224 RB_SET_FATHER(root, (struct rb_node *)(void *)&to->rbr_tree.rbt_root); 225 } 226 227 #define rbtree_postorder_for_each_entry_safe(ENTRY, TMP, ROOT, FIELD) \ 228 for ((ENTRY) = rb_entry_safe(rb_first_postorder(ROOT), \ 229 __typeof__(*(ENTRY)), FIELD); \ 230 ((ENTRY) != NULL && \ 231 ((TMP) = rb_entry_safe(rb_next2_postorder((ROOT), \ 232 &(ENTRY)->FIELD), __typeof__(*(ENTRY)), FIELD), \ 233 1)); \ 234 (ENTRY) = (TMP)) 235 236 #endif /* _LINUX_RBTREE_H_ */ 237
Indexes created Sat Sep 20 22:09:52 GMT 2025