tree.h revision 1.2.2.2
1 1.2.2.2 snj /* $NetBSD: tree.h,v 1.2.2.2 2014/12/25 02:13:12 snj Exp $ */ 2 1.2.2.2 snj 3 1.2.2.2 snj /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 4 1.2.2.2 snj /* 5 1.2.2.2 snj * Copyright 2002 Niels Provos <provos (at) citi.umich.edu> 6 1.2.2.2 snj * All rights reserved. 7 1.2.2.2 snj * 8 1.2.2.2 snj * Redistribution and use in source and binary forms, with or without 9 1.2.2.2 snj * modification, are permitted provided that the following conditions 10 1.2.2.2 snj * are met: 11 1.2.2.2 snj * 1. Redistributions of source code must retain the above copyright 12 1.2.2.2 snj * notice, this list of conditions and the following disclaimer. 13 1.2.2.2 snj * 2. Redistributions in binary form must reproduce the above copyright 14 1.2.2.2 snj * notice, this list of conditions and the following disclaimer in the 15 1.2.2.2 snj * documentation and/or other materials provided with the distribution. 16 1.2.2.2 snj * 17 1.2.2.2 snj * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 1.2.2.2 snj * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 1.2.2.2 snj * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 1.2.2.2 snj * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 1.2.2.2 snj * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 1.2.2.2 snj * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 1.2.2.2 snj * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 1.2.2.2 snj * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 1.2.2.2 snj * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 1.2.2.2 snj * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 1.2.2.2 snj */ 28 1.2.2.2 snj 29 1.2.2.2 snj #ifndef _SYS_TREE_H_ 30 1.2.2.2 snj #define _SYS_TREE_H_ 31 1.2.2.2 snj 32 1.2.2.2 snj /* 33 1.2.2.2 snj * This file defines data structures for different types of trees: 34 1.2.2.2 snj * splay trees and red-black trees. 35 1.2.2.2 snj * 36 1.2.2.2 snj * A splay tree is a self-organizing data structure. Every operation 37 1.2.2.2 snj * on the tree causes a splay to happen. The splay moves the requested 38 1.2.2.2 snj * node to the root of the tree and partly rebalances it. 39 1.2.2.2 snj * 40 1.2.2.2 snj * This has the benefit that request locality causes faster lookups as 41 1.2.2.2 snj * the requested nodes move to the top of the tree. On the other hand, 42 1.2.2.2 snj * every lookup causes memory writes. 43 1.2.2.2 snj * 44 1.2.2.2 snj * The Balance Theorem bounds the total access time for m operations 45 1.2.2.2 snj * and n inserts on an initially empty tree as O((m + n)lg n). The 46 1.2.2.2 snj * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 47 1.2.2.2 snj * 48 1.2.2.2 snj * A red-black tree is a binary search tree with the node color as an 49 1.2.2.2 snj * extra attribute. It fulfills a set of conditions: 50 1.2.2.2 snj * - every search path from the root to a leaf consists of the 51 1.2.2.2 snj * same number of black nodes, 52 1.2.2.2 snj * - each red node (except for the root) has a black parent, 53 1.2.2.2 snj * - each leaf node is black. 54 1.2.2.2 snj * 55 1.2.2.2 snj * Every operation on a red-black tree is bounded as O(lg n). 56 1.2.2.2 snj * The maximum height of a red-black tree is 2lg (n+1). 57 1.2.2.2 snj */ 58 1.2.2.2 snj 59 1.2.2.2 snj #define SPLAY_HEAD(name, type) \ 60 1.2.2.2 snj struct name { \ 61 1.2.2.2 snj struct type *sph_root; /* root of the tree */ \ 62 1.2.2.2 snj } 63 1.2.2.2 snj 64 1.2.2.2 snj #define SPLAY_INITIALIZER(root) \ 65 1.2.2.2 snj { NULL } 66 1.2.2.2 snj 67 1.2.2.2 snj #define SPLAY_INIT(root) do { \ 68 1.2.2.2 snj (root)->sph_root = NULL; \ 69 1.2.2.2 snj } while (0) 70 1.2.2.2 snj 71 1.2.2.2 snj #define SPLAY_ENTRY(type) \ 72 1.2.2.2 snj struct { \ 73 1.2.2.2 snj struct type *spe_left; /* left element */ \ 74 1.2.2.2 snj struct type *spe_right; /* right element */ \ 75 1.2.2.2 snj } 76 1.2.2.2 snj 77 1.2.2.2 snj #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 78 1.2.2.2 snj #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 79 1.2.2.2 snj #define SPLAY_ROOT(head) (head)->sph_root 80 1.2.2.2 snj #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 81 1.2.2.2 snj 82 1.2.2.2 snj /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 83 1.2.2.2 snj #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 84 1.2.2.2 snj SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 85 1.2.2.2 snj SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 86 1.2.2.2 snj (head)->sph_root = tmp; \ 87 1.2.2.2 snj } while (0) 88 1.2.2.2 snj 89 1.2.2.2 snj #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 90 1.2.2.2 snj SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 91 1.2.2.2 snj SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 92 1.2.2.2 snj (head)->sph_root = tmp; \ 93 1.2.2.2 snj } while (0) 94 1.2.2.2 snj 95 1.2.2.2 snj #define SPLAY_LINKLEFT(head, tmp, field) do { \ 96 1.2.2.2 snj SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 97 1.2.2.2 snj tmp = (head)->sph_root; \ 98 1.2.2.2 snj (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 99 1.2.2.2 snj } while (0) 100 1.2.2.2 snj 101 1.2.2.2 snj #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 102 1.2.2.2 snj SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 103 1.2.2.2 snj tmp = (head)->sph_root; \ 104 1.2.2.2 snj (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 105 1.2.2.2 snj } while (0) 106 1.2.2.2 snj 107 1.2.2.2 snj #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 108 1.2.2.2 snj SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 109 1.2.2.2 snj SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 110 1.2.2.2 snj SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 111 1.2.2.2 snj SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 112 1.2.2.2 snj } while (0) 113 1.2.2.2 snj 114 1.2.2.2 snj /* Generates prototypes and inline functions */ 115 1.2.2.2 snj 116 1.2.2.2 snj #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 117 1.2.2.2 snj void name##_SPLAY(struct name *, struct type *); \ 118 1.2.2.2 snj void name##_SPLAY_MINMAX(struct name *, int); \ 119 1.2.2.2 snj struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 120 1.2.2.2 snj struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 121 1.2.2.2 snj \ 122 1.2.2.2 snj /* Finds the node with the same key as elm */ \ 123 1.2.2.2 snj static __inline struct type * \ 124 1.2.2.2 snj name##_SPLAY_FIND(struct name *head, struct type *elm) \ 125 1.2.2.2 snj { \ 126 1.2.2.2 snj if (SPLAY_EMPTY(head)) \ 127 1.2.2.2 snj return(NULL); \ 128 1.2.2.2 snj name##_SPLAY(head, elm); \ 129 1.2.2.2 snj if ((cmp)(elm, (head)->sph_root) == 0) \ 130 1.2.2.2 snj return (head->sph_root); \ 131 1.2.2.2 snj return (NULL); \ 132 1.2.2.2 snj } \ 133 1.2.2.2 snj \ 134 1.2.2.2 snj static __inline struct type * \ 135 1.2.2.2 snj name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 136 1.2.2.2 snj { \ 137 1.2.2.2 snj name##_SPLAY(head, elm); \ 138 1.2.2.2 snj if (SPLAY_RIGHT(elm, field) != NULL) { \ 139 1.2.2.2 snj elm = SPLAY_RIGHT(elm, field); \ 140 1.2.2.2 snj while (SPLAY_LEFT(elm, field) != NULL) { \ 141 1.2.2.2 snj elm = SPLAY_LEFT(elm, field); \ 142 1.2.2.2 snj } \ 143 1.2.2.2 snj } else \ 144 1.2.2.2 snj elm = NULL; \ 145 1.2.2.2 snj return (elm); \ 146 1.2.2.2 snj } \ 147 1.2.2.2 snj \ 148 1.2.2.2 snj static __inline struct type * \ 149 1.2.2.2 snj name##_SPLAY_MIN_MAX(struct name *head, int val) \ 150 1.2.2.2 snj { \ 151 1.2.2.2 snj name##_SPLAY_MINMAX(head, val); \ 152 1.2.2.2 snj return (SPLAY_ROOT(head)); \ 153 1.2.2.2 snj } 154 1.2.2.2 snj 155 1.2.2.2 snj /* Main splay operation. 156 1.2.2.2 snj * Moves node close to the key of elm to top 157 1.2.2.2 snj */ 158 1.2.2.2 snj #define SPLAY_GENERATE(name, type, field, cmp) \ 159 1.2.2.2 snj struct type * \ 160 1.2.2.2 snj name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 161 1.2.2.2 snj { \ 162 1.2.2.2 snj if (SPLAY_EMPTY(head)) { \ 163 1.2.2.2 snj SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 164 1.2.2.2 snj } else { \ 165 1.2.2.2 snj int __comp; \ 166 1.2.2.2 snj name##_SPLAY(head, elm); \ 167 1.2.2.2 snj __comp = (cmp)(elm, (head)->sph_root); \ 168 1.2.2.2 snj if(__comp < 0) { \ 169 1.2.2.2 snj SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 170 1.2.2.2 snj SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 171 1.2.2.2 snj SPLAY_LEFT((head)->sph_root, field) = NULL; \ 172 1.2.2.2 snj } else if (__comp > 0) { \ 173 1.2.2.2 snj SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 174 1.2.2.2 snj SPLAY_LEFT(elm, field) = (head)->sph_root; \ 175 1.2.2.2 snj SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 176 1.2.2.2 snj } else \ 177 1.2.2.2 snj return ((head)->sph_root); \ 178 1.2.2.2 snj } \ 179 1.2.2.2 snj (head)->sph_root = (elm); \ 180 1.2.2.2 snj return (NULL); \ 181 1.2.2.2 snj } \ 182 1.2.2.2 snj \ 183 1.2.2.2 snj struct type * \ 184 1.2.2.2 snj name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 185 1.2.2.2 snj { \ 186 1.2.2.2 snj struct type *__tmp; \ 187 1.2.2.2 snj if (SPLAY_EMPTY(head)) \ 188 1.2.2.2 snj return (NULL); \ 189 1.2.2.2 snj name##_SPLAY(head, elm); \ 190 1.2.2.2 snj if ((cmp)(elm, (head)->sph_root) == 0) { \ 191 1.2.2.2 snj if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 192 1.2.2.2 snj (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 193 1.2.2.2 snj } else { \ 194 1.2.2.2 snj __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 195 1.2.2.2 snj (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 196 1.2.2.2 snj name##_SPLAY(head, elm); \ 197 1.2.2.2 snj SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 198 1.2.2.2 snj } \ 199 1.2.2.2 snj return (elm); \ 200 1.2.2.2 snj } \ 201 1.2.2.2 snj return (NULL); \ 202 1.2.2.2 snj } \ 203 1.2.2.2 snj \ 204 1.2.2.2 snj void \ 205 1.2.2.2 snj name##_SPLAY(struct name *head, struct type *elm) \ 206 1.2.2.2 snj { \ 207 1.2.2.2 snj struct type __node, *__left, *__right, *__tmp; \ 208 1.2.2.2 snj int __comp; \ 209 1.2.2.2 snj \ 210 1.2.2.2 snj SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 211 1.2.2.2 snj __left = __right = &__node; \ 212 1.2.2.2 snj \ 213 1.2.2.2 snj while ((__comp = (cmp)(elm, (head)->sph_root))) { \ 214 1.2.2.2 snj if (__comp < 0) { \ 215 1.2.2.2 snj __tmp = SPLAY_LEFT((head)->sph_root, field); \ 216 1.2.2.2 snj if (__tmp == NULL) \ 217 1.2.2.2 snj break; \ 218 1.2.2.2 snj if ((cmp)(elm, __tmp) < 0){ \ 219 1.2.2.2 snj SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 220 1.2.2.2 snj if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 221 1.2.2.2 snj break; \ 222 1.2.2.2 snj } \ 223 1.2.2.2 snj SPLAY_LINKLEFT(head, __right, field); \ 224 1.2.2.2 snj } else if (__comp > 0) { \ 225 1.2.2.2 snj __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 226 1.2.2.2 snj if (__tmp == NULL) \ 227 1.2.2.2 snj break; \ 228 1.2.2.2 snj if ((cmp)(elm, __tmp) > 0){ \ 229 1.2.2.2 snj SPLAY_ROTATE_LEFT(head, __tmp, field); \ 230 1.2.2.2 snj if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 231 1.2.2.2 snj break; \ 232 1.2.2.2 snj } \ 233 1.2.2.2 snj SPLAY_LINKRIGHT(head, __left, field); \ 234 1.2.2.2 snj } \ 235 1.2.2.2 snj } \ 236 1.2.2.2 snj SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 237 1.2.2.2 snj } \ 238 1.2.2.2 snj \ 239 1.2.2.2 snj /* Splay with either the minimum or the maximum element \ 240 1.2.2.2 snj * Used to find minimum or maximum element in tree. \ 241 1.2.2.2 snj */ \ 242 1.2.2.2 snj void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 243 1.2.2.2 snj { \ 244 1.2.2.2 snj struct type __node, *__left, *__right, *__tmp; \ 245 1.2.2.2 snj \ 246 1.2.2.2 snj SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 247 1.2.2.2 snj __left = __right = &__node; \ 248 1.2.2.2 snj \ 249 1.2.2.2 snj while (1) { \ 250 1.2.2.2 snj if (__comp < 0) { \ 251 1.2.2.2 snj __tmp = SPLAY_LEFT((head)->sph_root, field); \ 252 1.2.2.2 snj if (__tmp == NULL) \ 253 1.2.2.2 snj break; \ 254 1.2.2.2 snj if (__comp < 0){ \ 255 1.2.2.2 snj SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 256 1.2.2.2 snj if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 257 1.2.2.2 snj break; \ 258 1.2.2.2 snj } \ 259 1.2.2.2 snj SPLAY_LINKLEFT(head, __right, field); \ 260 1.2.2.2 snj } else if (__comp > 0) { \ 261 1.2.2.2 snj __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 262 1.2.2.2 snj if (__tmp == NULL) \ 263 1.2.2.2 snj break; \ 264 1.2.2.2 snj if (__comp > 0) { \ 265 1.2.2.2 snj SPLAY_ROTATE_LEFT(head, __tmp, field); \ 266 1.2.2.2 snj if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 267 1.2.2.2 snj break; \ 268 1.2.2.2 snj } \ 269 1.2.2.2 snj SPLAY_LINKRIGHT(head, __left, field); \ 270 1.2.2.2 snj } \ 271 1.2.2.2 snj } \ 272 1.2.2.2 snj SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 273 1.2.2.2 snj } 274 1.2.2.2 snj 275 1.2.2.2 snj #define SPLAY_NEGINF -1 276 1.2.2.2 snj #define SPLAY_INF 1 277 1.2.2.2 snj 278 1.2.2.2 snj #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 279 1.2.2.2 snj #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 280 1.2.2.2 snj #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 281 1.2.2.2 snj #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 282 1.2.2.2 snj #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 283 1.2.2.2 snj : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 284 1.2.2.2 snj #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 285 1.2.2.2 snj : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 286 1.2.2.2 snj 287 1.2.2.2 snj #define SPLAY_FOREACH(x, name, head) \ 288 1.2.2.2 snj for ((x) = SPLAY_MIN(name, head); \ 289 1.2.2.2 snj (x) != NULL; \ 290 1.2.2.2 snj (x) = SPLAY_NEXT(name, head, x)) 291 1.2.2.2 snj 292 1.2.2.2 snj /* Macros that define a red-back tree */ 293 1.2.2.2 snj #define RB_HEAD(name, type) \ 294 1.2.2.2 snj struct name { \ 295 1.2.2.2 snj struct type *rbh_root; /* root of the tree */ \ 296 1.2.2.2 snj } 297 1.2.2.2 snj 298 1.2.2.2 snj #define RB_INITIALIZER(root) \ 299 1.2.2.2 snj { NULL } 300 1.2.2.2 snj 301 1.2.2.2 snj #define RB_INIT(root) do { \ 302 1.2.2.2 snj (root)->rbh_root = NULL; \ 303 1.2.2.2 snj } while (0) 304 1.2.2.2 snj 305 1.2.2.2 snj #define RB_BLACK 0 306 1.2.2.2 snj #define RB_RED 1 307 1.2.2.2 snj #define RB_ENTRY(type) \ 308 1.2.2.2 snj struct { \ 309 1.2.2.2 snj struct type *rbe_left; /* left element */ \ 310 1.2.2.2 snj struct type *rbe_right; /* right element */ \ 311 1.2.2.2 snj struct type *rbe_parent; /* parent element */ \ 312 1.2.2.2 snj int rbe_color; /* node color */ \ 313 1.2.2.2 snj } 314 1.2.2.2 snj 315 1.2.2.2 snj #define RB_LEFT(elm, field) (elm)->field.rbe_left 316 1.2.2.2 snj #define RB_RIGHT(elm, field) (elm)->field.rbe_right 317 1.2.2.2 snj #define RB_PARENT(elm, field) (elm)->field.rbe_parent 318 1.2.2.2 snj #define RB_COLOR(elm, field) (elm)->field.rbe_color 319 1.2.2.2 snj #define RB_ROOT(head) (head)->rbh_root 320 1.2.2.2 snj #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 321 1.2.2.2 snj 322 1.2.2.2 snj #define RB_SET(elm, parent, field) do { \ 323 1.2.2.2 snj RB_PARENT(elm, field) = parent; \ 324 1.2.2.2 snj RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 325 1.2.2.2 snj RB_COLOR(elm, field) = RB_RED; \ 326 1.2.2.2 snj } while (0) 327 1.2.2.2 snj 328 1.2.2.2 snj #define RB_SET_BLACKRED(black, red, field) do { \ 329 1.2.2.2 snj RB_COLOR(black, field) = RB_BLACK; \ 330 1.2.2.2 snj RB_COLOR(red, field) = RB_RED; \ 331 1.2.2.2 snj } while (0) 332 1.2.2.2 snj 333 1.2.2.2 snj #ifndef RB_AUGMENT 334 1.2.2.2 snj #define RB_AUGMENT(x) 335 1.2.2.2 snj #endif 336 1.2.2.2 snj 337 1.2.2.2 snj #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 338 1.2.2.2 snj (tmp) = RB_RIGHT(elm, field); \ 339 1.2.2.2 snj if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ 340 1.2.2.2 snj RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 341 1.2.2.2 snj } \ 342 1.2.2.2 snj RB_AUGMENT(elm); \ 343 1.2.2.2 snj if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 344 1.2.2.2 snj if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 345 1.2.2.2 snj RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 346 1.2.2.2 snj else \ 347 1.2.2.2 snj RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 348 1.2.2.2 snj } else \ 349 1.2.2.2 snj (head)->rbh_root = (tmp); \ 350 1.2.2.2 snj RB_LEFT(tmp, field) = (elm); \ 351 1.2.2.2 snj RB_PARENT(elm, field) = (tmp); \ 352 1.2.2.2 snj RB_AUGMENT(tmp); \ 353 1.2.2.2 snj if ((RB_PARENT(tmp, field))) \ 354 1.2.2.2 snj RB_AUGMENT(RB_PARENT(tmp, field)); \ 355 1.2.2.2 snj } while (0) 356 1.2.2.2 snj 357 1.2.2.2 snj #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 358 1.2.2.2 snj (tmp) = RB_LEFT(elm, field); \ 359 1.2.2.2 snj if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ 360 1.2.2.2 snj RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 361 1.2.2.2 snj } \ 362 1.2.2.2 snj RB_AUGMENT(elm); \ 363 1.2.2.2 snj if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 364 1.2.2.2 snj if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 365 1.2.2.2 snj RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 366 1.2.2.2 snj else \ 367 1.2.2.2 snj RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 368 1.2.2.2 snj } else \ 369 1.2.2.2 snj (head)->rbh_root = (tmp); \ 370 1.2.2.2 snj RB_RIGHT(tmp, field) = (elm); \ 371 1.2.2.2 snj RB_PARENT(elm, field) = (tmp); \ 372 1.2.2.2 snj RB_AUGMENT(tmp); \ 373 1.2.2.2 snj if ((RB_PARENT(tmp, field))) \ 374 1.2.2.2 snj RB_AUGMENT(RB_PARENT(tmp, field)); \ 375 1.2.2.2 snj } while (0) 376 1.2.2.2 snj 377 1.2.2.2 snj /* Generates prototypes and inline functions */ 378 1.2.2.2 snj #define RB_PROTOTYPE(name, type, field, cmp) \ 379 1.2.2.2 snj void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 380 1.2.2.2 snj void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 381 1.2.2.2 snj struct type *name##_RB_REMOVE(struct name *, struct type *); \ 382 1.2.2.2 snj struct type *name##_RB_INSERT(struct name *, struct type *); \ 383 1.2.2.2 snj struct type *name##_RB_FIND(struct name *, struct type *); \ 384 1.2.2.2 snj struct type *name##_RB_NEXT(struct type *); \ 385 1.2.2.2 snj struct type *name##_RB_MINMAX(struct name *, int); \ 386 1.2.2.2 snj \ 387 1.2.2.2 snj 388 1.2.2.2 snj /* Main rb operation. 389 1.2.2.2 snj * Moves node close to the key of elm to top 390 1.2.2.2 snj */ 391 1.2.2.2 snj #define RB_GENERATE(name, type, field, cmp) \ 392 1.2.2.2 snj void \ 393 1.2.2.2 snj name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 394 1.2.2.2 snj { \ 395 1.2.2.2 snj struct type *parent, *gparent, *tmp; \ 396 1.2.2.2 snj while ((parent = RB_PARENT(elm, field)) && \ 397 1.2.2.2 snj RB_COLOR(parent, field) == RB_RED) { \ 398 1.2.2.2 snj gparent = RB_PARENT(parent, field); \ 399 1.2.2.2 snj if (parent == RB_LEFT(gparent, field)) { \ 400 1.2.2.2 snj tmp = RB_RIGHT(gparent, field); \ 401 1.2.2.2 snj if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 402 1.2.2.2 snj RB_COLOR(tmp, field) = RB_BLACK; \ 403 1.2.2.2 snj RB_SET_BLACKRED(parent, gparent, field);\ 404 1.2.2.2 snj elm = gparent; \ 405 1.2.2.2 snj continue; \ 406 1.2.2.2 snj } \ 407 1.2.2.2 snj if (RB_RIGHT(parent, field) == elm) { \ 408 1.2.2.2 snj RB_ROTATE_LEFT(head, parent, tmp, field);\ 409 1.2.2.2 snj tmp = parent; \ 410 1.2.2.2 snj parent = elm; \ 411 1.2.2.2 snj elm = tmp; \ 412 1.2.2.2 snj } \ 413 1.2.2.2 snj RB_SET_BLACKRED(parent, gparent, field); \ 414 1.2.2.2 snj RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 415 1.2.2.2 snj } else { \ 416 1.2.2.2 snj tmp = RB_LEFT(gparent, field); \ 417 1.2.2.2 snj if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 418 1.2.2.2 snj RB_COLOR(tmp, field) = RB_BLACK; \ 419 1.2.2.2 snj RB_SET_BLACKRED(parent, gparent, field);\ 420 1.2.2.2 snj elm = gparent; \ 421 1.2.2.2 snj continue; \ 422 1.2.2.2 snj } \ 423 1.2.2.2 snj if (RB_LEFT(parent, field) == elm) { \ 424 1.2.2.2 snj RB_ROTATE_RIGHT(head, parent, tmp, field);\ 425 1.2.2.2 snj tmp = parent; \ 426 1.2.2.2 snj parent = elm; \ 427 1.2.2.2 snj elm = tmp; \ 428 1.2.2.2 snj } \ 429 1.2.2.2 snj RB_SET_BLACKRED(parent, gparent, field); \ 430 1.2.2.2 snj RB_ROTATE_LEFT(head, gparent, tmp, field); \ 431 1.2.2.2 snj } \ 432 1.2.2.2 snj } \ 433 1.2.2.2 snj RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 434 1.2.2.2 snj } \ 435 1.2.2.2 snj \ 436 1.2.2.2 snj void \ 437 1.2.2.2 snj name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 438 1.2.2.2 snj { \ 439 1.2.2.2 snj struct type *tmp; \ 440 1.2.2.2 snj while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 441 1.2.2.2 snj elm != RB_ROOT(head)) { \ 442 1.2.2.2 snj if (RB_LEFT(parent, field) == elm) { \ 443 1.2.2.2 snj tmp = RB_RIGHT(parent, field); \ 444 1.2.2.2 snj if (RB_COLOR(tmp, field) == RB_RED) { \ 445 1.2.2.2 snj RB_SET_BLACKRED(tmp, parent, field); \ 446 1.2.2.2 snj RB_ROTATE_LEFT(head, parent, tmp, field);\ 447 1.2.2.2 snj tmp = RB_RIGHT(parent, field); \ 448 1.2.2.2 snj } \ 449 1.2.2.2 snj if ((RB_LEFT(tmp, field) == NULL || \ 450 1.2.2.2 snj RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 451 1.2.2.2 snj (RB_RIGHT(tmp, field) == NULL || \ 452 1.2.2.2 snj RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 453 1.2.2.2 snj RB_COLOR(tmp, field) = RB_RED; \ 454 1.2.2.2 snj elm = parent; \ 455 1.2.2.2 snj parent = RB_PARENT(elm, field); \ 456 1.2.2.2 snj } else { \ 457 1.2.2.2 snj if (RB_RIGHT(tmp, field) == NULL || \ 458 1.2.2.2 snj RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 459 1.2.2.2 snj struct type *oleft; \ 460 1.2.2.2 snj if ((oleft = RB_LEFT(tmp, field)))\ 461 1.2.2.2 snj RB_COLOR(oleft, field) = RB_BLACK;\ 462 1.2.2.2 snj RB_COLOR(tmp, field) = RB_RED; \ 463 1.2.2.2 snj RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 464 1.2.2.2 snj tmp = RB_RIGHT(parent, field); \ 465 1.2.2.2 snj } \ 466 1.2.2.2 snj RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 467 1.2.2.2 snj RB_COLOR(parent, field) = RB_BLACK; \ 468 1.2.2.2 snj if (RB_RIGHT(tmp, field)) \ 469 1.2.2.2 snj RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 470 1.2.2.2 snj RB_ROTATE_LEFT(head, parent, tmp, field);\ 471 1.2.2.2 snj elm = RB_ROOT(head); \ 472 1.2.2.2 snj break; \ 473 1.2.2.2 snj } \ 474 1.2.2.2 snj } else { \ 475 1.2.2.2 snj tmp = RB_LEFT(parent, field); \ 476 1.2.2.2 snj if (RB_COLOR(tmp, field) == RB_RED) { \ 477 1.2.2.2 snj RB_SET_BLACKRED(tmp, parent, field); \ 478 1.2.2.2 snj RB_ROTATE_RIGHT(head, parent, tmp, field);\ 479 1.2.2.2 snj tmp = RB_LEFT(parent, field); \ 480 1.2.2.2 snj } \ 481 1.2.2.2 snj if ((RB_LEFT(tmp, field) == NULL || \ 482 1.2.2.2 snj RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 483 1.2.2.2 snj (RB_RIGHT(tmp, field) == NULL || \ 484 1.2.2.2 snj RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 485 1.2.2.2 snj RB_COLOR(tmp, field) = RB_RED; \ 486 1.2.2.2 snj elm = parent; \ 487 1.2.2.2 snj parent = RB_PARENT(elm, field); \ 488 1.2.2.2 snj } else { \ 489 1.2.2.2 snj if (RB_LEFT(tmp, field) == NULL || \ 490 1.2.2.2 snj RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 491 1.2.2.2 snj struct type *oright; \ 492 1.2.2.2 snj if ((oright = RB_RIGHT(tmp, field)))\ 493 1.2.2.2 snj RB_COLOR(oright, field) = RB_BLACK;\ 494 1.2.2.2 snj RB_COLOR(tmp, field) = RB_RED; \ 495 1.2.2.2 snj RB_ROTATE_LEFT(head, tmp, oright, field);\ 496 1.2.2.2 snj tmp = RB_LEFT(parent, field); \ 497 1.2.2.2 snj } \ 498 1.2.2.2 snj RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 499 1.2.2.2 snj RB_COLOR(parent, field) = RB_BLACK; \ 500 1.2.2.2 snj if (RB_LEFT(tmp, field)) \ 501 1.2.2.2 snj RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 502 1.2.2.2 snj RB_ROTATE_RIGHT(head, parent, tmp, field);\ 503 1.2.2.2 snj elm = RB_ROOT(head); \ 504 1.2.2.2 snj break; \ 505 1.2.2.2 snj } \ 506 1.2.2.2 snj } \ 507 1.2.2.2 snj } \ 508 1.2.2.2 snj if (elm) \ 509 1.2.2.2 snj RB_COLOR(elm, field) = RB_BLACK; \ 510 1.2.2.2 snj } \ 511 1.2.2.2 snj \ 512 1.2.2.2 snj struct type * \ 513 1.2.2.2 snj name##_RB_REMOVE(struct name *head, struct type *elm) \ 514 1.2.2.2 snj { \ 515 1.2.2.2 snj struct type *child, *parent, *old = elm; \ 516 1.2.2.2 snj int color; \ 517 1.2.2.2 snj if (RB_LEFT(elm, field) == NULL) \ 518 1.2.2.2 snj child = RB_RIGHT(elm, field); \ 519 1.2.2.2 snj else if (RB_RIGHT(elm, field) == NULL) \ 520 1.2.2.2 snj child = RB_LEFT(elm, field); \ 521 1.2.2.2 snj else { \ 522 1.2.2.2 snj struct type *left; \ 523 1.2.2.2 snj elm = RB_RIGHT(elm, field); \ 524 1.2.2.2 snj while ((left = RB_LEFT(elm, field))) \ 525 1.2.2.2 snj elm = left; \ 526 1.2.2.2 snj child = RB_RIGHT(elm, field); \ 527 1.2.2.2 snj parent = RB_PARENT(elm, field); \ 528 1.2.2.2 snj color = RB_COLOR(elm, field); \ 529 1.2.2.2 snj if (child) \ 530 1.2.2.2 snj RB_PARENT(child, field) = parent; \ 531 1.2.2.2 snj if (parent) { \ 532 1.2.2.2 snj if (RB_LEFT(parent, field) == elm) \ 533 1.2.2.2 snj RB_LEFT(parent, field) = child; \ 534 1.2.2.2 snj else \ 535 1.2.2.2 snj RB_RIGHT(parent, field) = child; \ 536 1.2.2.2 snj RB_AUGMENT(parent); \ 537 1.2.2.2 snj } else \ 538 1.2.2.2 snj RB_ROOT(head) = child; \ 539 1.2.2.2 snj if (RB_PARENT(elm, field) == old) \ 540 1.2.2.2 snj parent = elm; \ 541 1.2.2.2 snj (elm)->field = (old)->field; \ 542 1.2.2.2 snj if (RB_PARENT(old, field)) { \ 543 1.2.2.2 snj if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 544 1.2.2.2 snj RB_LEFT(RB_PARENT(old, field), field) = elm;\ 545 1.2.2.2 snj else \ 546 1.2.2.2 snj RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 547 1.2.2.2 snj RB_AUGMENT(RB_PARENT(old, field)); \ 548 1.2.2.2 snj } else \ 549 1.2.2.2 snj RB_ROOT(head) = elm; \ 550 1.2.2.2 snj RB_PARENT(RB_LEFT(old, field), field) = elm; \ 551 1.2.2.2 snj if (RB_RIGHT(old, field)) \ 552 1.2.2.2 snj RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 553 1.2.2.2 snj if (parent) { \ 554 1.2.2.2 snj left = parent; \ 555 1.2.2.2 snj do { \ 556 1.2.2.2 snj RB_AUGMENT(left); \ 557 1.2.2.2 snj } while ((left = RB_PARENT(left, field))); \ 558 1.2.2.2 snj } \ 559 1.2.2.2 snj goto color; \ 560 1.2.2.2 snj } \ 561 1.2.2.2 snj parent = RB_PARENT(elm, field); \ 562 1.2.2.2 snj color = RB_COLOR(elm, field); \ 563 1.2.2.2 snj if (child) \ 564 1.2.2.2 snj RB_PARENT(child, field) = parent; \ 565 1.2.2.2 snj if (parent) { \ 566 1.2.2.2 snj if (RB_LEFT(parent, field) == elm) \ 567 1.2.2.2 snj RB_LEFT(parent, field) = child; \ 568 1.2.2.2 snj else \ 569 1.2.2.2 snj RB_RIGHT(parent, field) = child; \ 570 1.2.2.2 snj RB_AUGMENT(parent); \ 571 1.2.2.2 snj } else \ 572 1.2.2.2 snj RB_ROOT(head) = child; \ 573 1.2.2.2 snj color: \ 574 1.2.2.2 snj if (color == RB_BLACK) \ 575 1.2.2.2 snj name##_RB_REMOVE_COLOR(head, parent, child); \ 576 1.2.2.2 snj return (old); \ 577 1.2.2.2 snj } \ 578 1.2.2.2 snj \ 579 1.2.2.2 snj /* Inserts a node into the RB tree */ \ 580 1.2.2.2 snj struct type * \ 581 1.2.2.2 snj name##_RB_INSERT(struct name *head, struct type *elm) \ 582 1.2.2.2 snj { \ 583 1.2.2.2 snj struct type *tmp; \ 584 1.2.2.2 snj struct type *parent = NULL; \ 585 1.2.2.2 snj int comp = 0; \ 586 1.2.2.2 snj tmp = RB_ROOT(head); \ 587 1.2.2.2 snj while (tmp) { \ 588 1.2.2.2 snj parent = tmp; \ 589 1.2.2.2 snj comp = (cmp)(elm, parent); \ 590 1.2.2.2 snj if (comp < 0) \ 591 1.2.2.2 snj tmp = RB_LEFT(tmp, field); \ 592 1.2.2.2 snj else if (comp > 0) \ 593 1.2.2.2 snj tmp = RB_RIGHT(tmp, field); \ 594 1.2.2.2 snj else \ 595 1.2.2.2 snj return (tmp); \ 596 1.2.2.2 snj } \ 597 1.2.2.2 snj RB_SET(elm, parent, field); \ 598 1.2.2.2 snj if (parent != NULL) { \ 599 1.2.2.2 snj if (comp < 0) \ 600 1.2.2.2 snj RB_LEFT(parent, field) = elm; \ 601 1.2.2.2 snj else \ 602 1.2.2.2 snj RB_RIGHT(parent, field) = elm; \ 603 1.2.2.2 snj RB_AUGMENT(parent); \ 604 1.2.2.2 snj } else \ 605 1.2.2.2 snj RB_ROOT(head) = elm; \ 606 1.2.2.2 snj name##_RB_INSERT_COLOR(head, elm); \ 607 1.2.2.2 snj return (NULL); \ 608 1.2.2.2 snj } \ 609 1.2.2.2 snj \ 610 1.2.2.2 snj /* Finds the node with the same key as elm */ \ 611 1.2.2.2 snj struct type * \ 612 1.2.2.2 snj name##_RB_FIND(struct name *head, struct type *elm) \ 613 1.2.2.2 snj { \ 614 1.2.2.2 snj struct type *tmp = RB_ROOT(head); \ 615 1.2.2.2 snj int comp; \ 616 1.2.2.2 snj while (tmp) { \ 617 1.2.2.2 snj comp = cmp(elm, tmp); \ 618 1.2.2.2 snj if (comp < 0) \ 619 1.2.2.2 snj tmp = RB_LEFT(tmp, field); \ 620 1.2.2.2 snj else if (comp > 0) \ 621 1.2.2.2 snj tmp = RB_RIGHT(tmp, field); \ 622 1.2.2.2 snj else \ 623 1.2.2.2 snj return (tmp); \ 624 1.2.2.2 snj } \ 625 1.2.2.2 snj return (NULL); \ 626 1.2.2.2 snj } \ 627 1.2.2.2 snj \ 628 1.2.2.2 snj struct type * \ 629 1.2.2.2 snj name##_RB_NEXT(struct type *elm) \ 630 1.2.2.2 snj { \ 631 1.2.2.2 snj if (RB_RIGHT(elm, field)) { \ 632 1.2.2.2 snj elm = RB_RIGHT(elm, field); \ 633 1.2.2.2 snj while (RB_LEFT(elm, field)) \ 634 1.2.2.2 snj elm = RB_LEFT(elm, field); \ 635 1.2.2.2 snj } else { \ 636 1.2.2.2 snj if (RB_PARENT(elm, field) && \ 637 1.2.2.2 snj (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 638 1.2.2.2 snj elm = RB_PARENT(elm, field); \ 639 1.2.2.2 snj else { \ 640 1.2.2.2 snj while (RB_PARENT(elm, field) && \ 641 1.2.2.2 snj (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 642 1.2.2.2 snj elm = RB_PARENT(elm, field); \ 643 1.2.2.2 snj elm = RB_PARENT(elm, field); \ 644 1.2.2.2 snj } \ 645 1.2.2.2 snj } \ 646 1.2.2.2 snj return (elm); \ 647 1.2.2.2 snj } \ 648 1.2.2.2 snj \ 649 1.2.2.2 snj struct type * \ 650 1.2.2.2 snj name##_RB_MINMAX(struct name *head, int val) \ 651 1.2.2.2 snj { \ 652 1.2.2.2 snj struct type *tmp = RB_ROOT(head); \ 653 1.2.2.2 snj struct type *parent = NULL; \ 654 1.2.2.2 snj while (tmp) { \ 655 1.2.2.2 snj parent = tmp; \ 656 1.2.2.2 snj if (val < 0) \ 657 1.2.2.2 snj tmp = RB_LEFT(tmp, field); \ 658 1.2.2.2 snj else \ 659 1.2.2.2 snj tmp = RB_RIGHT(tmp, field); \ 660 1.2.2.2 snj } \ 661 1.2.2.2 snj return (parent); \ 662 1.2.2.2 snj } 663 1.2.2.2 snj 664 1.2.2.2 snj #define RB_NEGINF -1 665 1.2.2.2 snj #define RB_INF 1 666 1.2.2.2 snj 667 1.2.2.2 snj #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 668 1.2.2.2 snj #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 669 1.2.2.2 snj #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 670 1.2.2.2 snj #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 671 1.2.2.2 snj #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 672 1.2.2.2 snj #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 673 1.2.2.2 snj 674 1.2.2.2 snj #define RB_FOREACH(x, name, head) \ 675 1.2.2.2 snj for ((x) = RB_MIN(name, head); \ 676 1.2.2.2 snj (x) != NULL; \ 677 1.2.2.2 snj (x) = name##_RB_NEXT(x)) 678 1.2.2.2 snj 679 1.2.2.2 snj #endif /* _SYS_TREE_H_ */ 680 1.2.2.2 snj /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 681 1.2.2.2 snj /* 682 1.2.2.2 snj * Copyright 2002 Niels Provos <provos (at) citi.umich.edu> 683 1.2.2.2 snj * All rights reserved. 684 1.2.2.2 snj * 685 1.2.2.2 snj * Redistribution and use in source and binary forms, with or without 686 1.2.2.2 snj * modification, are permitted provided that the following conditions 687 1.2.2.2 snj * are met: 688 1.2.2.2 snj * 1. Redistributions of source code must retain the above copyright 689 1.2.2.2 snj * notice, this list of conditions and the following disclaimer. 690 1.2.2.2 snj * 2. Redistributions in binary form must reproduce the above copyright 691 1.2.2.2 snj * notice, this list of conditions and the following disclaimer in the 692 1.2.2.2 snj * documentation and/or other materials provided with the distribution. 693 1.2.2.2 snj * 694 1.2.2.2 snj * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 695 1.2.2.2 snj * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 696 1.2.2.2 snj * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 697 1.2.2.2 snj * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 698 1.2.2.2 snj * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 699 1.2.2.2 snj * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 700 1.2.2.2 snj * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 701 1.2.2.2 snj * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 702 1.2.2.2 snj * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 703 1.2.2.2 snj * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 704 1.2.2.2 snj */ 705 1.2.2.2 snj 706 1.2.2.2 snj #ifndef _SYS_TREE_H_ 707 1.2.2.2 snj #define _SYS_TREE_H_ 708 1.2.2.2 snj 709 1.2.2.2 snj /* 710 1.2.2.2 snj * This file defines data structures for different types of trees: 711 1.2.2.2 snj * splay trees and red-black trees. 712 1.2.2.2 snj * 713 1.2.2.2 snj * A splay tree is a self-organizing data structure. Every operation 714 1.2.2.2 snj * on the tree causes a splay to happen. The splay moves the requested 715 1.2.2.2 snj * node to the root of the tree and partly rebalances it. 716 1.2.2.2 snj * 717 1.2.2.2 snj * This has the benefit that request locality causes faster lookups as 718 1.2.2.2 snj * the requested nodes move to the top of the tree. On the other hand, 719 1.2.2.2 snj * every lookup causes memory writes. 720 1.2.2.2 snj * 721 1.2.2.2 snj * The Balance Theorem bounds the total access time for m operations 722 1.2.2.2 snj * and n inserts on an initially empty tree as O((m + n)lg n). The 723 1.2.2.2 snj * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 724 1.2.2.2 snj * 725 1.2.2.2 snj * A red-black tree is a binary search tree with the node color as an 726 1.2.2.2 snj * extra attribute. It fulfills a set of conditions: 727 1.2.2.2 snj * - every search path from the root to a leaf consists of the 728 1.2.2.2 snj * same number of black nodes, 729 1.2.2.2 snj * - each red node (except for the root) has a black parent, 730 1.2.2.2 snj * - each leaf node is black. 731 1.2.2.2 snj * 732 1.2.2.2 snj * Every operation on a red-black tree is bounded as O(lg n). 733 1.2.2.2 snj * The maximum height of a red-black tree is 2lg (n+1). 734 1.2.2.2 snj */ 735 1.2.2.2 snj 736 1.2.2.2 snj #define SPLAY_HEAD(name, type) \ 737 1.2.2.2 snj struct name { \ 738 1.2.2.2 snj struct type *sph_root; /* root of the tree */ \ 739 1.2.2.2 snj } 740 1.2.2.2 snj 741 1.2.2.2 snj #define SPLAY_INITIALIZER(root) \ 742 1.2.2.2 snj { NULL } 743 1.2.2.2 snj 744 1.2.2.2 snj #define SPLAY_INIT(root) do { \ 745 1.2.2.2 snj (root)->sph_root = NULL; \ 746 1.2.2.2 snj } while (0) 747 1.2.2.2 snj 748 1.2.2.2 snj #define SPLAY_ENTRY(type) \ 749 1.2.2.2 snj struct { \ 750 1.2.2.2 snj struct type *spe_left; /* left element */ \ 751 1.2.2.2 snj struct type *spe_right; /* right element */ \ 752 1.2.2.2 snj } 753 1.2.2.2 snj 754 1.2.2.2 snj #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 755 1.2.2.2 snj #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 756 1.2.2.2 snj #define SPLAY_ROOT(head) (head)->sph_root 757 1.2.2.2 snj #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 758 1.2.2.2 snj 759 1.2.2.2 snj /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 760 1.2.2.2 snj #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 761 1.2.2.2 snj SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 762 1.2.2.2 snj SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 763 1.2.2.2 snj (head)->sph_root = tmp; \ 764 1.2.2.2 snj } while (0) 765 1.2.2.2 snj 766 1.2.2.2 snj #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 767 1.2.2.2 snj SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 768 1.2.2.2 snj SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 769 1.2.2.2 snj (head)->sph_root = tmp; \ 770 1.2.2.2 snj } while (0) 771 1.2.2.2 snj 772 1.2.2.2 snj #define SPLAY_LINKLEFT(head, tmp, field) do { \ 773 1.2.2.2 snj SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 774 1.2.2.2 snj tmp = (head)->sph_root; \ 775 1.2.2.2 snj (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 776 1.2.2.2 snj } while (0) 777 1.2.2.2 snj 778 1.2.2.2 snj #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 779 1.2.2.2 snj SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 780 1.2.2.2 snj tmp = (head)->sph_root; \ 781 1.2.2.2 snj (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 782 1.2.2.2 snj } while (0) 783 1.2.2.2 snj 784 1.2.2.2 snj #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 785 1.2.2.2 snj SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 786 1.2.2.2 snj SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 787 1.2.2.2 snj SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 788 1.2.2.2 snj SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 789 1.2.2.2 snj } while (0) 790 1.2.2.2 snj 791 1.2.2.2 snj /* Generates prototypes and inline functions */ 792 1.2.2.2 snj 793 1.2.2.2 snj #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 794 1.2.2.2 snj void name##_SPLAY(struct name *, struct type *); \ 795 1.2.2.2 snj void name##_SPLAY_MINMAX(struct name *, int); \ 796 1.2.2.2 snj struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 797 1.2.2.2 snj struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 798 1.2.2.2 snj \ 799 1.2.2.2 snj /* Finds the node with the same key as elm */ \ 800 1.2.2.2 snj static __inline struct type * \ 801 1.2.2.2 snj name##_SPLAY_FIND(struct name *head, struct type *elm) \ 802 1.2.2.2 snj { \ 803 1.2.2.2 snj if (SPLAY_EMPTY(head)) \ 804 1.2.2.2 snj return(NULL); \ 805 1.2.2.2 snj name##_SPLAY(head, elm); \ 806 1.2.2.2 snj if ((cmp)(elm, (head)->sph_root) == 0) \ 807 1.2.2.2 snj return (head->sph_root); \ 808 1.2.2.2 snj return (NULL); \ 809 1.2.2.2 snj } \ 810 1.2.2.2 snj \ 811 1.2.2.2 snj static __inline struct type * \ 812 1.2.2.2 snj name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 813 1.2.2.2 snj { \ 814 1.2.2.2 snj name##_SPLAY(head, elm); \ 815 1.2.2.2 snj if (SPLAY_RIGHT(elm, field) != NULL) { \ 816 1.2.2.2 snj elm = SPLAY_RIGHT(elm, field); \ 817 1.2.2.2 snj while (SPLAY_LEFT(elm, field) != NULL) { \ 818 1.2.2.2 snj elm = SPLAY_LEFT(elm, field); \ 819 1.2.2.2 snj } \ 820 1.2.2.2 snj } else \ 821 1.2.2.2 snj elm = NULL; \ 822 1.2.2.2 snj return (elm); \ 823 1.2.2.2 snj } \ 824 1.2.2.2 snj \ 825 1.2.2.2 snj static __inline struct type * \ 826 1.2.2.2 snj name##_SPLAY_MIN_MAX(struct name *head, int val) \ 827 1.2.2.2 snj { \ 828 1.2.2.2 snj name##_SPLAY_MINMAX(head, val); \ 829 1.2.2.2 snj return (SPLAY_ROOT(head)); \ 830 1.2.2.2 snj } 831 1.2.2.2 snj 832 1.2.2.2 snj /* Main splay operation. 833 1.2.2.2 snj * Moves node close to the key of elm to top 834 1.2.2.2 snj */ 835 1.2.2.2 snj #define SPLAY_GENERATE(name, type, field, cmp) \ 836 1.2.2.2 snj struct type * \ 837 1.2.2.2 snj name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 838 1.2.2.2 snj { \ 839 1.2.2.2 snj if (SPLAY_EMPTY(head)) { \ 840 1.2.2.2 snj SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 841 1.2.2.2 snj } else { \ 842 1.2.2.2 snj int __comp; \ 843 1.2.2.2 snj name##_SPLAY(head, elm); \ 844 1.2.2.2 snj __comp = (cmp)(elm, (head)->sph_root); \ 845 1.2.2.2 snj if(__comp < 0) { \ 846 1.2.2.2 snj SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 847 1.2.2.2 snj SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 848 1.2.2.2 snj SPLAY_LEFT((head)->sph_root, field) = NULL; \ 849 1.2.2.2 snj } else if (__comp > 0) { \ 850 1.2.2.2 snj SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 851 1.2.2.2 snj SPLAY_LEFT(elm, field) = (head)->sph_root; \ 852 1.2.2.2 snj SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 853 1.2.2.2 snj } else \ 854 1.2.2.2 snj return ((head)->sph_root); \ 855 1.2.2.2 snj } \ 856 1.2.2.2 snj (head)->sph_root = (elm); \ 857 1.2.2.2 snj return (NULL); \ 858 1.2.2.2 snj } \ 859 1.2.2.2 snj \ 860 1.2.2.2 snj struct type * \ 861 1.2.2.2 snj name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 862 1.2.2.2 snj { \ 863 1.2.2.2 snj struct type *__tmp; \ 864 1.2.2.2 snj if (SPLAY_EMPTY(head)) \ 865 1.2.2.2 snj return (NULL); \ 866 1.2.2.2 snj name##_SPLAY(head, elm); \ 867 1.2.2.2 snj if ((cmp)(elm, (head)->sph_root) == 0) { \ 868 1.2.2.2 snj if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 869 1.2.2.2 snj (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 870 1.2.2.2 snj } else { \ 871 1.2.2.2 snj __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 872 1.2.2.2 snj (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 873 1.2.2.2 snj name##_SPLAY(head, elm); \ 874 1.2.2.2 snj SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 875 1.2.2.2 snj } \ 876 1.2.2.2 snj return (elm); \ 877 1.2.2.2 snj } \ 878 1.2.2.2 snj return (NULL); \ 879 1.2.2.2 snj } \ 880 1.2.2.2 snj \ 881 1.2.2.2 snj void \ 882 1.2.2.2 snj name##_SPLAY(struct name *head, struct type *elm) \ 883 1.2.2.2 snj { \ 884 1.2.2.2 snj struct type __node, *__left, *__right, *__tmp; \ 885 1.2.2.2 snj int __comp; \ 886 1.2.2.2 snj \ 887 1.2.2.2 snj SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 888 1.2.2.2 snj __left = __right = &__node; \ 889 1.2.2.2 snj \ 890 1.2.2.2 snj while ((__comp = (cmp)(elm, (head)->sph_root))) { \ 891 1.2.2.2 snj if (__comp < 0) { \ 892 1.2.2.2 snj __tmp = SPLAY_LEFT((head)->sph_root, field); \ 893 1.2.2.2 snj if (__tmp == NULL) \ 894 1.2.2.2 snj break; \ 895 1.2.2.2 snj if ((cmp)(elm, __tmp) < 0){ \ 896 1.2.2.2 snj SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 897 1.2.2.2 snj if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 898 1.2.2.2 snj break; \ 899 1.2.2.2 snj } \ 900 1.2.2.2 snj SPLAY_LINKLEFT(head, __right, field); \ 901 1.2.2.2 snj } else if (__comp > 0) { \ 902 1.2.2.2 snj __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 903 1.2.2.2 snj if (__tmp == NULL) \ 904 1.2.2.2 snj break; \ 905 1.2.2.2 snj if ((cmp)(elm, __tmp) > 0){ \ 906 1.2.2.2 snj SPLAY_ROTATE_LEFT(head, __tmp, field); \ 907 1.2.2.2 snj if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 908 1.2.2.2 snj break; \ 909 1.2.2.2 snj } \ 910 1.2.2.2 snj SPLAY_LINKRIGHT(head, __left, field); \ 911 1.2.2.2 snj } \ 912 1.2.2.2 snj } \ 913 1.2.2.2 snj SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 914 1.2.2.2 snj } \ 915 1.2.2.2 snj \ 916 1.2.2.2 snj /* Splay with either the minimum or the maximum element \ 917 1.2.2.2 snj * Used to find minimum or maximum element in tree. \ 918 1.2.2.2 snj */ \ 919 1.2.2.2 snj void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 920 1.2.2.2 snj { \ 921 1.2.2.2 snj struct type __node, *__left, *__right, *__tmp; \ 922 1.2.2.2 snj \ 923 1.2.2.2 snj SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 924 1.2.2.2 snj __left = __right = &__node; \ 925 1.2.2.2 snj \ 926 1.2.2.2 snj while (1) { \ 927 1.2.2.2 snj if (__comp < 0) { \ 928 1.2.2.2 snj __tmp = SPLAY_LEFT((head)->sph_root, field); \ 929 1.2.2.2 snj if (__tmp == NULL) \ 930 1.2.2.2 snj break; \ 931 1.2.2.2 snj if (__comp < 0){ \ 932 1.2.2.2 snj SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 933 1.2.2.2 snj if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 934 1.2.2.2 snj break; \ 935 1.2.2.2 snj } \ 936 1.2.2.2 snj SPLAY_LINKLEFT(head, __right, field); \ 937 1.2.2.2 snj } else if (__comp > 0) { \ 938 1.2.2.2 snj __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 939 1.2.2.2 snj if (__tmp == NULL) \ 940 1.2.2.2 snj break; \ 941 1.2.2.2 snj if (__comp > 0) { \ 942 1.2.2.2 snj SPLAY_ROTATE_LEFT(head, __tmp, field); \ 943 1.2.2.2 snj if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 944 1.2.2.2 snj break; \ 945 1.2.2.2 snj } \ 946 1.2.2.2 snj SPLAY_LINKRIGHT(head, __left, field); \ 947 1.2.2.2 snj } \ 948 1.2.2.2 snj } \ 949 1.2.2.2 snj SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 950 1.2.2.2 snj } 951 1.2.2.2 snj 952 1.2.2.2 snj #define SPLAY_NEGINF -1 953 1.2.2.2 snj #define SPLAY_INF 1 954 1.2.2.2 snj 955 1.2.2.2 snj #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 956 1.2.2.2 snj #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 957 1.2.2.2 snj #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 958 1.2.2.2 snj #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 959 1.2.2.2 snj #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 960 1.2.2.2 snj : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 961 1.2.2.2 snj #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 962 1.2.2.2 snj : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 963 1.2.2.2 snj 964 1.2.2.2 snj #define SPLAY_FOREACH(x, name, head) \ 965 1.2.2.2 snj for ((x) = SPLAY_MIN(name, head); \ 966 1.2.2.2 snj (x) != NULL; \ 967 1.2.2.2 snj (x) = SPLAY_NEXT(name, head, x)) 968 1.2.2.2 snj 969 1.2.2.2 snj /* Macros that define a red-back tree */ 970 1.2.2.2 snj #define RB_HEAD(name, type) \ 971 1.2.2.2 snj struct name { \ 972 1.2.2.2 snj struct type *rbh_root; /* root of the tree */ \ 973 1.2.2.2 snj } 974 1.2.2.2 snj 975 1.2.2.2 snj #define RB_INITIALIZER(root) \ 976 1.2.2.2 snj { NULL } 977 1.2.2.2 snj 978 1.2.2.2 snj #define RB_INIT(root) do { \ 979 1.2.2.2 snj (root)->rbh_root = NULL; \ 980 1.2.2.2 snj } while (0) 981 1.2.2.2 snj 982 1.2.2.2 snj #define RB_BLACK 0 983 1.2.2.2 snj #define RB_RED 1 984 1.2.2.2 snj #define RB_ENTRY(type) \ 985 1.2.2.2 snj struct { \ 986 1.2.2.2 snj struct type *rbe_left; /* left element */ \ 987 1.2.2.2 snj struct type *rbe_right; /* right element */ \ 988 1.2.2.2 snj struct type *rbe_parent; /* parent element */ \ 989 1.2.2.2 snj int rbe_color; /* node color */ \ 990 1.2.2.2 snj } 991 1.2.2.2 snj 992 1.2.2.2 snj #define RB_LEFT(elm, field) (elm)->field.rbe_left 993 1.2.2.2 snj #define RB_RIGHT(elm, field) (elm)->field.rbe_right 994 1.2.2.2 snj #define RB_PARENT(elm, field) (elm)->field.rbe_parent 995 1.2.2.2 snj #define RB_COLOR(elm, field) (elm)->field.rbe_color 996 1.2.2.2 snj #define RB_ROOT(head) (head)->rbh_root 997 1.2.2.2 snj #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 998 1.2.2.2 snj 999 1.2.2.2 snj #define RB_SET(elm, parent, field) do { \ 1000 1.2.2.2 snj RB_PARENT(elm, field) = parent; \ 1001 1.2.2.2 snj RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 1002 1.2.2.2 snj RB_COLOR(elm, field) = RB_RED; \ 1003 1.2.2.2 snj } while (0) 1004 1.2.2.2 snj 1005 1.2.2.2 snj #define RB_SET_BLACKRED(black, red, field) do { \ 1006 1.2.2.2 snj RB_COLOR(black, field) = RB_BLACK; \ 1007 1.2.2.2 snj RB_COLOR(red, field) = RB_RED; \ 1008 1.2.2.2 snj } while (0) 1009 1.2.2.2 snj 1010 1.2.2.2 snj #ifndef RB_AUGMENT 1011 1.2.2.2 snj #define RB_AUGMENT(x) 1012 1.2.2.2 snj #endif 1013 1.2.2.2 snj 1014 1.2.2.2 snj #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 1015 1.2.2.2 snj (tmp) = RB_RIGHT(elm, field); \ 1016 1.2.2.2 snj if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ 1017 1.2.2.2 snj RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 1018 1.2.2.2 snj } \ 1019 1.2.2.2 snj RB_AUGMENT(elm); \ 1020 1.2.2.2 snj if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 1021 1.2.2.2 snj if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 1022 1.2.2.2 snj RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 1023 1.2.2.2 snj else \ 1024 1.2.2.2 snj RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 1025 1.2.2.2 snj } else \ 1026 1.2.2.2 snj (head)->rbh_root = (tmp); \ 1027 1.2.2.2 snj RB_LEFT(tmp, field) = (elm); \ 1028 1.2.2.2 snj RB_PARENT(elm, field) = (tmp); \ 1029 1.2.2.2 snj RB_AUGMENT(tmp); \ 1030 1.2.2.2 snj if ((RB_PARENT(tmp, field))) \ 1031 1.2.2.2 snj RB_AUGMENT(RB_PARENT(tmp, field)); \ 1032 1.2.2.2 snj } while (0) 1033 1.2.2.2 snj 1034 1.2.2.2 snj #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 1035 1.2.2.2 snj (tmp) = RB_LEFT(elm, field); \ 1036 1.2.2.2 snj if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ 1037 1.2.2.2 snj RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 1038 1.2.2.2 snj } \ 1039 1.2.2.2 snj RB_AUGMENT(elm); \ 1040 1.2.2.2 snj if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 1041 1.2.2.2 snj if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 1042 1.2.2.2 snj RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 1043 1.2.2.2 snj else \ 1044 1.2.2.2 snj RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 1045 1.2.2.2 snj } else \ 1046 1.2.2.2 snj (head)->rbh_root = (tmp); \ 1047 1.2.2.2 snj RB_RIGHT(tmp, field) = (elm); \ 1048 1.2.2.2 snj RB_PARENT(elm, field) = (tmp); \ 1049 1.2.2.2 snj RB_AUGMENT(tmp); \ 1050 1.2.2.2 snj if ((RB_PARENT(tmp, field))) \ 1051 1.2.2.2 snj RB_AUGMENT(RB_PARENT(tmp, field)); \ 1052 1.2.2.2 snj } while (0) 1053 1.2.2.2 snj 1054 1.2.2.2 snj /* Generates prototypes and inline functions */ 1055 1.2.2.2 snj #define RB_PROTOTYPE(name, type, field, cmp) \ 1056 1.2.2.2 snj void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 1057 1.2.2.2 snj void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 1058 1.2.2.2 snj struct type *name##_RB_REMOVE(struct name *, struct type *); \ 1059 1.2.2.2 snj struct type *name##_RB_INSERT(struct name *, struct type *); \ 1060 1.2.2.2 snj struct type *name##_RB_FIND(struct name *, struct type *); \ 1061 1.2.2.2 snj struct type *name##_RB_NEXT(struct type *); \ 1062 1.2.2.2 snj struct type *name##_RB_MINMAX(struct name *, int); \ 1063 1.2.2.2 snj \ 1064 1.2.2.2 snj 1065 1.2.2.2 snj /* Main rb operation. 1066 1.2.2.2 snj * Moves node close to the key of elm to top 1067 1.2.2.2 snj */ 1068 1.2.2.2 snj #define RB_GENERATE(name, type, field, cmp) \ 1069 1.2.2.2 snj void \ 1070 1.2.2.2 snj name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 1071 1.2.2.2 snj { \ 1072 1.2.2.2 snj struct type *parent, *gparent, *tmp; \ 1073 1.2.2.2 snj while ((parent = RB_PARENT(elm, field)) && \ 1074 1.2.2.2 snj RB_COLOR(parent, field) == RB_RED) { \ 1075 1.2.2.2 snj gparent = RB_PARENT(parent, field); \ 1076 1.2.2.2 snj if (parent == RB_LEFT(gparent, field)) { \ 1077 1.2.2.2 snj tmp = RB_RIGHT(gparent, field); \ 1078 1.2.2.2 snj if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 1079 1.2.2.2 snj RB_COLOR(tmp, field) = RB_BLACK; \ 1080 1.2.2.2 snj RB_SET_BLACKRED(parent, gparent, field);\ 1081 1.2.2.2 snj elm = gparent; \ 1082 1.2.2.2 snj continue; \ 1083 1.2.2.2 snj } \ 1084 1.2.2.2 snj if (RB_RIGHT(parent, field) == elm) { \ 1085 1.2.2.2 snj RB_ROTATE_LEFT(head, parent, tmp, field);\ 1086 1.2.2.2 snj tmp = parent; \ 1087 1.2.2.2 snj parent = elm; \ 1088 1.2.2.2 snj elm = tmp; \ 1089 1.2.2.2 snj } \ 1090 1.2.2.2 snj RB_SET_BLACKRED(parent, gparent, field); \ 1091 1.2.2.2 snj RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 1092 1.2.2.2 snj } else { \ 1093 1.2.2.2 snj tmp = RB_LEFT(gparent, field); \ 1094 1.2.2.2 snj if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 1095 1.2.2.2 snj RB_COLOR(tmp, field) = RB_BLACK; \ 1096 1.2.2.2 snj RB_SET_BLACKRED(parent, gparent, field);\ 1097 1.2.2.2 snj elm = gparent; \ 1098 1.2.2.2 snj continue; \ 1099 1.2.2.2 snj } \ 1100 1.2.2.2 snj if (RB_LEFT(parent, field) == elm) { \ 1101 1.2.2.2 snj RB_ROTATE_RIGHT(head, parent, tmp, field);\ 1102 1.2.2.2 snj tmp = parent; \ 1103 1.2.2.2 snj parent = elm; \ 1104 1.2.2.2 snj elm = tmp; \ 1105 1.2.2.2 snj } \ 1106 1.2.2.2 snj RB_SET_BLACKRED(parent, gparent, field); \ 1107 1.2.2.2 snj RB_ROTATE_LEFT(head, gparent, tmp, field); \ 1108 1.2.2.2 snj } \ 1109 1.2.2.2 snj } \ 1110 1.2.2.2 snj RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 1111 1.2.2.2 snj } \ 1112 1.2.2.2 snj \ 1113 1.2.2.2 snj void \ 1114 1.2.2.2 snj name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 1115 1.2.2.2 snj { \ 1116 1.2.2.2 snj struct type *tmp; \ 1117 1.2.2.2 snj while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 1118 1.2.2.2 snj elm != RB_ROOT(head)) { \ 1119 1.2.2.2 snj if (RB_LEFT(parent, field) == elm) { \ 1120 1.2.2.2 snj tmp = RB_RIGHT(parent, field); \ 1121 1.2.2.2 snj if (RB_COLOR(tmp, field) == RB_RED) { \ 1122 1.2.2.2 snj RB_SET_BLACKRED(tmp, parent, field); \ 1123 1.2.2.2 snj RB_ROTATE_LEFT(head, parent, tmp, field);\ 1124 1.2.2.2 snj tmp = RB_RIGHT(parent, field); \ 1125 1.2.2.2 snj } \ 1126 1.2.2.2 snj if ((RB_LEFT(tmp, field) == NULL || \ 1127 1.2.2.2 snj RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 1128 1.2.2.2 snj (RB_RIGHT(tmp, field) == NULL || \ 1129 1.2.2.2 snj RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 1130 1.2.2.2 snj RB_COLOR(tmp, field) = RB_RED; \ 1131 1.2.2.2 snj elm = parent; \ 1132 1.2.2.2 snj parent = RB_PARENT(elm, field); \ 1133 1.2.2.2 snj } else { \ 1134 1.2.2.2 snj if (RB_RIGHT(tmp, field) == NULL || \ 1135 1.2.2.2 snj RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 1136 1.2.2.2 snj struct type *oleft; \ 1137 1.2.2.2 snj if ((oleft = RB_LEFT(tmp, field)))\ 1138 1.2.2.2 snj RB_COLOR(oleft, field) = RB_BLACK;\ 1139 1.2.2.2 snj RB_COLOR(tmp, field) = RB_RED; \ 1140 1.2.2.2 snj RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 1141 1.2.2.2 snj tmp = RB_RIGHT(parent, field); \ 1142 1.2.2.2 snj } \ 1143 1.2.2.2 snj RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 1144 1.2.2.2 snj RB_COLOR(parent, field) = RB_BLACK; \ 1145 1.2.2.2 snj if (RB_RIGHT(tmp, field)) \ 1146 1.2.2.2 snj RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 1147 1.2.2.2 snj RB_ROTATE_LEFT(head, parent, tmp, field);\ 1148 1.2.2.2 snj elm = RB_ROOT(head); \ 1149 1.2.2.2 snj break; \ 1150 1.2.2.2 snj } \ 1151 1.2.2.2 snj } else { \ 1152 1.2.2.2 snj tmp = RB_LEFT(parent, field); \ 1153 1.2.2.2 snj if (RB_COLOR(tmp, field) == RB_RED) { \ 1154 1.2.2.2 snj RB_SET_BLACKRED(tmp, parent, field); \ 1155 1.2.2.2 snj RB_ROTATE_RIGHT(head, parent, tmp, field);\ 1156 1.2.2.2 snj tmp = RB_LEFT(parent, field); \ 1157 1.2.2.2 snj } \ 1158 1.2.2.2 snj if ((RB_LEFT(tmp, field) == NULL || \ 1159 1.2.2.2 snj RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 1160 1.2.2.2 snj (RB_RIGHT(tmp, field) == NULL || \ 1161 1.2.2.2 snj RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 1162 1.2.2.2 snj RB_COLOR(tmp, field) = RB_RED; \ 1163 1.2.2.2 snj elm = parent; \ 1164 1.2.2.2 snj parent = RB_PARENT(elm, field); \ 1165 1.2.2.2 snj } else { \ 1166 1.2.2.2 snj if (RB_LEFT(tmp, field) == NULL || \ 1167 1.2.2.2 snj RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 1168 1.2.2.2 snj struct type *oright; \ 1169 1.2.2.2 snj if ((oright = RB_RIGHT(tmp, field)))\ 1170 1.2.2.2 snj RB_COLOR(oright, field) = RB_BLACK;\ 1171 1.2.2.2 snj RB_COLOR(tmp, field) = RB_RED; \ 1172 1.2.2.2 snj RB_ROTATE_LEFT(head, tmp, oright, field);\ 1173 1.2.2.2 snj tmp = RB_LEFT(parent, field); \ 1174 1.2.2.2 snj } \ 1175 1.2.2.2 snj RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 1176 1.2.2.2 snj RB_COLOR(parent, field) = RB_BLACK; \ 1177 1.2.2.2 snj if (RB_LEFT(tmp, field)) \ 1178 1.2.2.2 snj RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 1179 1.2.2.2 snj RB_ROTATE_RIGHT(head, parent, tmp, field);\ 1180 1.2.2.2 snj elm = RB_ROOT(head); \ 1181 1.2.2.2 snj break; \ 1182 1.2.2.2 snj } \ 1183 1.2.2.2 snj } \ 1184 1.2.2.2 snj } \ 1185 1.2.2.2 snj if (elm) \ 1186 1.2.2.2 snj RB_COLOR(elm, field) = RB_BLACK; \ 1187 1.2.2.2 snj } \ 1188 1.2.2.2 snj \ 1189 1.2.2.2 snj struct type * \ 1190 1.2.2.2 snj name##_RB_REMOVE(struct name *head, struct type *elm) \ 1191 1.2.2.2 snj { \ 1192 1.2.2.2 snj struct type *child, *parent, *old = elm; \ 1193 1.2.2.2 snj int color; \ 1194 1.2.2.2 snj if (RB_LEFT(elm, field) == NULL) \ 1195 1.2.2.2 snj child = RB_RIGHT(elm, field); \ 1196 1.2.2.2 snj else if (RB_RIGHT(elm, field) == NULL) \ 1197 1.2.2.2 snj child = RB_LEFT(elm, field); \ 1198 1.2.2.2 snj else { \ 1199 1.2.2.2 snj struct type *left; \ 1200 1.2.2.2 snj elm = RB_RIGHT(elm, field); \ 1201 1.2.2.2 snj while ((left = RB_LEFT(elm, field))) \ 1202 1.2.2.2 snj elm = left; \ 1203 1.2.2.2 snj child = RB_RIGHT(elm, field); \ 1204 1.2.2.2 snj parent = RB_PARENT(elm, field); \ 1205 1.2.2.2 snj color = RB_COLOR(elm, field); \ 1206 1.2.2.2 snj if (child) \ 1207 1.2.2.2 snj RB_PARENT(child, field) = parent; \ 1208 1.2.2.2 snj if (parent) { \ 1209 1.2.2.2 snj if (RB_LEFT(parent, field) == elm) \ 1210 1.2.2.2 snj RB_LEFT(parent, field) = child; \ 1211 1.2.2.2 snj else \ 1212 1.2.2.2 snj RB_RIGHT(parent, field) = child; \ 1213 1.2.2.2 snj RB_AUGMENT(parent); \ 1214 1.2.2.2 snj } else \ 1215 1.2.2.2 snj RB_ROOT(head) = child; \ 1216 1.2.2.2 snj if (RB_PARENT(elm, field) == old) \ 1217 1.2.2.2 snj parent = elm; \ 1218 1.2.2.2 snj (elm)->field = (old)->field; \ 1219 1.2.2.2 snj if (RB_PARENT(old, field)) { \ 1220 1.2.2.2 snj if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 1221 1.2.2.2 snj RB_LEFT(RB_PARENT(old, field), field) = elm;\ 1222 1.2.2.2 snj else \ 1223 1.2.2.2 snj RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 1224 1.2.2.2 snj RB_AUGMENT(RB_PARENT(old, field)); \ 1225 1.2.2.2 snj } else \ 1226 1.2.2.2 snj RB_ROOT(head) = elm; \ 1227 1.2.2.2 snj RB_PARENT(RB_LEFT(old, field), field) = elm; \ 1228 1.2.2.2 snj if (RB_RIGHT(old, field)) \ 1229 1.2.2.2 snj RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 1230 1.2.2.2 snj if (parent) { \ 1231 1.2.2.2 snj left = parent; \ 1232 1.2.2.2 snj do { \ 1233 1.2.2.2 snj RB_AUGMENT(left); \ 1234 1.2.2.2 snj } while ((left = RB_PARENT(left, field))); \ 1235 1.2.2.2 snj } \ 1236 1.2.2.2 snj goto color; \ 1237 1.2.2.2 snj } \ 1238 1.2.2.2 snj parent = RB_PARENT(elm, field); \ 1239 1.2.2.2 snj color = RB_COLOR(elm, field); \ 1240 1.2.2.2 snj if (child) \ 1241 1.2.2.2 snj RB_PARENT(child, field) = parent; \ 1242 1.2.2.2 snj if (parent) { \ 1243 1.2.2.2 snj if (RB_LEFT(parent, field) == elm) \ 1244 1.2.2.2 snj RB_LEFT(parent, field) = child; \ 1245 1.2.2.2 snj else \ 1246 1.2.2.2 snj RB_RIGHT(parent, field) = child; \ 1247 1.2.2.2 snj RB_AUGMENT(parent); \ 1248 1.2.2.2 snj } else \ 1249 1.2.2.2 snj RB_ROOT(head) = child; \ 1250 1.2.2.2 snj color: \ 1251 1.2.2.2 snj if (color == RB_BLACK) \ 1252 1.2.2.2 snj name##_RB_REMOVE_COLOR(head, parent, child); \ 1253 1.2.2.2 snj return (old); \ 1254 1.2.2.2 snj } \ 1255 1.2.2.2 snj \ 1256 1.2.2.2 snj /* Inserts a node into the RB tree */ \ 1257 1.2.2.2 snj struct type * \ 1258 1.2.2.2 snj name##_RB_INSERT(struct name *head, struct type *elm) \ 1259 1.2.2.2 snj { \ 1260 1.2.2.2 snj struct type *tmp; \ 1261 1.2.2.2 snj struct type *parent = NULL; \ 1262 1.2.2.2 snj int comp = 0; \ 1263 1.2.2.2 snj tmp = RB_ROOT(head); \ 1264 1.2.2.2 snj while (tmp) { \ 1265 1.2.2.2 snj parent = tmp; \ 1266 1.2.2.2 snj comp = (cmp)(elm, parent); \ 1267 1.2.2.2 snj if (comp < 0) \ 1268 1.2.2.2 snj tmp = RB_LEFT(tmp, field); \ 1269 1.2.2.2 snj else if (comp > 0) \ 1270 1.2.2.2 snj tmp = RB_RIGHT(tmp, field); \ 1271 1.2.2.2 snj else \ 1272 1.2.2.2 snj return (tmp); \ 1273 1.2.2.2 snj } \ 1274 1.2.2.2 snj RB_SET(elm, parent, field); \ 1275 1.2.2.2 snj if (parent != NULL) { \ 1276 1.2.2.2 snj if (comp < 0) \ 1277 1.2.2.2 snj RB_LEFT(parent, field) = elm; \ 1278 1.2.2.2 snj else \ 1279 1.2.2.2 snj RB_RIGHT(parent, field) = elm; \ 1280 1.2.2.2 snj RB_AUGMENT(parent); \ 1281 1.2.2.2 snj } else \ 1282 1.2.2.2 snj RB_ROOT(head) = elm; \ 1283 1.2.2.2 snj name##_RB_INSERT_COLOR(head, elm); \ 1284 1.2.2.2 snj return (NULL); \ 1285 1.2.2.2 snj } \ 1286 1.2.2.2 snj \ 1287 1.2.2.2 snj /* Finds the node with the same key as elm */ \ 1288 1.2.2.2 snj struct type * \ 1289 1.2.2.2 snj name##_RB_FIND(struct name *head, struct type *elm) \ 1290 1.2.2.2 snj { \ 1291 1.2.2.2 snj struct type *tmp = RB_ROOT(head); \ 1292 1.2.2.2 snj int comp; \ 1293 1.2.2.2 snj while (tmp) { \ 1294 1.2.2.2 snj comp = cmp(elm, tmp); \ 1295 1.2.2.2 snj if (comp < 0) \ 1296 1.2.2.2 snj tmp = RB_LEFT(tmp, field); \ 1297 1.2.2.2 snj else if (comp > 0) \ 1298 1.2.2.2 snj tmp = RB_RIGHT(tmp, field); \ 1299 1.2.2.2 snj else \ 1300 1.2.2.2 snj return (tmp); \ 1301 1.2.2.2 snj } \ 1302 1.2.2.2 snj return (NULL); \ 1303 1.2.2.2 snj } \ 1304 1.2.2.2 snj \ 1305 1.2.2.2 snj struct type * \ 1306 1.2.2.2 snj name##_RB_NEXT(struct type *elm) \ 1307 1.2.2.2 snj { \ 1308 1.2.2.2 snj if (RB_RIGHT(elm, field)) { \ 1309 1.2.2.2 snj elm = RB_RIGHT(elm, field); \ 1310 1.2.2.2 snj while (RB_LEFT(elm, field)) \ 1311 1.2.2.2 snj elm = RB_LEFT(elm, field); \ 1312 1.2.2.2 snj } else { \ 1313 1.2.2.2 snj if (RB_PARENT(elm, field) && \ 1314 1.2.2.2 snj (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 1315 1.2.2.2 snj elm = RB_PARENT(elm, field); \ 1316 1.2.2.2 snj else { \ 1317 1.2.2.2 snj while (RB_PARENT(elm, field) && \ 1318 1.2.2.2 snj (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 1319 1.2.2.2 snj elm = RB_PARENT(elm, field); \ 1320 1.2.2.2 snj elm = RB_PARENT(elm, field); \ 1321 1.2.2.2 snj } \ 1322 1.2.2.2 snj } \ 1323 1.2.2.2 snj return (elm); \ 1324 1.2.2.2 snj } \ 1325 1.2.2.2 snj \ 1326 1.2.2.2 snj struct type * \ 1327 1.2.2.2 snj name##_RB_MINMAX(struct name *head, int val) \ 1328 1.2.2.2 snj { \ 1329 1.2.2.2 snj struct type *tmp = RB_ROOT(head); \ 1330 1.2.2.2 snj struct type *parent = NULL; \ 1331 1.2.2.2 snj while (tmp) { \ 1332 1.2.2.2 snj parent = tmp; \ 1333 1.2.2.2 snj if (val < 0) \ 1334 1.2.2.2 snj tmp = RB_LEFT(tmp, field); \ 1335 1.2.2.2 snj else \ 1336 1.2.2.2 snj tmp = RB_RIGHT(tmp, field); \ 1337 1.2.2.2 snj } \ 1338 1.2.2.2 snj return (parent); \ 1339 1.2.2.2 snj } 1340 1.2.2.2 snj 1341 1.2.2.2 snj #define RB_NEGINF -1 1342 1.2.2.2 snj #define RB_INF 1 1343 1.2.2.2 snj 1344 1.2.2.2 snj #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 1345 1.2.2.2 snj #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 1346 1.2.2.2 snj #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 1347 1.2.2.2 snj #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 1348 1.2.2.2 snj #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 1349 1.2.2.2 snj #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 1350 1.2.2.2 snj 1351 1.2.2.2 snj #define RB_FOREACH(x, name, head) \ 1352 1.2.2.2 snj for ((x) = RB_MIN(name, head); \ 1353 1.2.2.2 snj (x) != NULL; \ 1354 1.2.2.2 snj (x) = name##_RB_NEXT(x)) 1355 1.2.2.2 snj 1356 1.2.2.2 snj #endif /* _SYS_TREE_H_ */ 1357
Indexes created Wed Aug 05 00:25:39 UTC 2026