itree.h - dedup - deduplicating backup program Err bitreich.org 70 hgit clone git://bitreich.org/dedup/ git://enlrupgkhuxnvlhsf6lc3fziv5h2hhfrinws65d7roiv6bfj7d652fid.onion/dedup/ URL:git://bitreich.org/dedup/ git://enlrupgkhuxnvlhsf6lc3fziv5h2hhfrinws65d7roiv6bfj7d652fid.onion/dedup/ bitreich.org 70 1Log /scm/dedup/log.gph bitreich.org 70 1Files /scm/dedup/files.gph bitreich.org 70 1Refs /scm/dedup/refs.gph bitreich.org 70 1Tags /scm/dedup/tag bitreich.org 70 1README /scm/dedup/file/README.gph bitreich.org 70 1LICENSE /scm/dedup/file/LICENSE.gph bitreich.org 70 i--- Err bitreich.org 70 itree.h (33874B) Err bitreich.org 70 i--- Err bitreich.org 70 i 1 /* $OpenBSD: tree.h,v 1.29 2017/07/30 19:27:20 deraadt Exp $ */ Err bitreich.org 70 i 2 /* Err bitreich.org 70 i 3 * Copyright 2002 Niels Provos Err bitreich.org 70 i 4 * All rights reserved. Err bitreich.org 70 i 5 * Err bitreich.org 70 i 6 * Redistribution and use in source and binary forms, with or without Err bitreich.org 70 i 7 * modification, are permitted provided that the following conditions Err bitreich.org 70 i 8 * are met: Err bitreich.org 70 i 9 * 1. Redistributions of source code must retain the above copyright Err bitreich.org 70 i 10 * notice, this list of conditions and the following disclaimer. Err bitreich.org 70 i 11 * 2. Redistributions in binary form must reproduce the above copyright Err bitreich.org 70 i 12 * notice, this list of conditions and the following disclaimer in the Err bitreich.org 70 i 13 * documentation and/or other materials provided with the distribution. Err bitreich.org 70 i 14 * Err bitreich.org 70 i 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR Err bitreich.org 70 i 16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES Err bitreich.org 70 i 17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. Err bitreich.org 70 i 18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, Err bitreich.org 70 i 19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT Err bitreich.org 70 i 20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, Err bitreich.org 70 i 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY Err bitreich.org 70 i 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT Err bitreich.org 70 i 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF Err bitreich.org 70 i 24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. Err bitreich.org 70 i 25 */ Err bitreich.org 70 i 26 Err bitreich.org 70 i 27 #ifndef _SYS_TREE_H_ Err bitreich.org 70 i 28 #define _SYS_TREE_H_ Err bitreich.org 70 i 29 Err bitreich.org 70 i 30 /* Err bitreich.org 70 i 31 * This file defines data structures for different types of trees: Err bitreich.org 70 i 32 * splay trees and red-black trees. Err bitreich.org 70 i 33 * Err bitreich.org 70 i 34 * A splay tree is a self-organizing data structure. Every operation Err bitreich.org 70 i 35 * on the tree causes a splay to happen. The splay moves the requested Err bitreich.org 70 i 36 * node to the root of the tree and partly rebalances it. Err bitreich.org 70 i 37 * Err bitreich.org 70 i 38 * This has the benefit that request locality causes faster lookups as Err bitreich.org 70 i 39 * the requested nodes move to the top of the tree. On the other hand, Err bitreich.org 70 i 40 * every lookup causes memory writes. Err bitreich.org 70 i 41 * Err bitreich.org 70 i 42 * The Balance Theorem bounds the total access time for m operations Err bitreich.org 70 i 43 * and n inserts on an initially empty tree as O((m + n)lg n). The Err bitreich.org 70 i 44 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); Err bitreich.org 70 i 45 * Err bitreich.org 70 i 46 * A red-black tree is a binary search tree with the node color as an Err bitreich.org 70 i 47 * extra attribute. It fulfills a set of conditions: Err bitreich.org 70 i 48 * - every search path from the root to a leaf consists of the Err bitreich.org 70 i 49 * same number of black nodes, Err bitreich.org 70 i 50 * - each red node (except for the root) has a black parent, Err bitreich.org 70 i 51 * - each leaf node is black. Err bitreich.org 70 i 52 * Err bitreich.org 70 i 53 * Every operation on a red-black tree is bounded as O(lg n). Err bitreich.org 70 i 54 * The maximum height of a red-black tree is 2lg (n+1). Err bitreich.org 70 i 55 */ Err bitreich.org 70 i 56 Err bitreich.org 70 i 57 #define SPLAY_HEAD(name, type) \ Err bitreich.org 70 i 58 struct name { \ Err bitreich.org 70 i 59 struct type *sph_root; /* root of the tree */ \ Err bitreich.org 70 i 60 } Err bitreich.org 70 i 61 Err bitreich.org 70 i 62 #define SPLAY_INITIALIZER(root) \ Err bitreich.org 70 i 63 { NULL } Err bitreich.org 70 i 64 Err bitreich.org 70 i 65 #define SPLAY_INIT(root) do { \ Err bitreich.org 70 i 66 (root)->sph_root = NULL; \ Err bitreich.org 70 i 67 } while (0) Err bitreich.org 70 i 68 Err bitreich.org 70 i 69 #define SPLAY_ENTRY(type) \ Err bitreich.org 70 i 70 struct { \ Err bitreich.org 70 i 71 struct type *spe_left; /* left element */ \ Err bitreich.org 70 i 72 struct type *spe_right; /* right element */ \ Err bitreich.org 70 i 73 } Err bitreich.org 70 i 74 Err bitreich.org 70 i 75 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left Err bitreich.org 70 i 76 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right Err bitreich.org 70 i 77 #define SPLAY_ROOT(head) (head)->sph_root Err bitreich.org 70 i 78 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) Err bitreich.org 70 i 79 Err bitreich.org 70 i 80 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ Err bitreich.org 70 i 81 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ Err bitreich.org 70 i 82 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ Err bitreich.org 70 i 83 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ Err bitreich.org 70 i 84 (head)->sph_root = tmp; \ Err bitreich.org 70 i 85 } while (0) Err bitreich.org 70 i 86 Err bitreich.org 70 i 87 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ Err bitreich.org 70 i 88 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ Err bitreich.org 70 i 89 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ Err bitreich.org 70 i 90 (head)->sph_root = tmp; \ Err bitreich.org 70 i 91 } while (0) Err bitreich.org 70 i 92 Err bitreich.org 70 i 93 #define SPLAY_LINKLEFT(head, tmp, field) do { \ Err bitreich.org 70 i 94 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ Err bitreich.org 70 i 95 tmp = (head)->sph_root; \ Err bitreich.org 70 i 96 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ Err bitreich.org 70 i 97 } while (0) Err bitreich.org 70 i 98 Err bitreich.org 70 i 99 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ Err bitreich.org 70 i 100 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ Err bitreich.org 70 i 101 tmp = (head)->sph_root; \ Err bitreich.org 70 i 102 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ Err bitreich.org 70 i 103 } while (0) Err bitreich.org 70 i 104 Err bitreich.org 70 i 105 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ Err bitreich.org 70 i 106 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ Err bitreich.org 70 i 107 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ Err bitreich.org 70 i 108 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ Err bitreich.org 70 i 109 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ Err bitreich.org 70 i 110 } while (0) Err bitreich.org 70 i 111 Err bitreich.org 70 i 112 /* Generates prototypes and inline functions */ Err bitreich.org 70 i 113 Err bitreich.org 70 i 114 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ Err bitreich.org 70 i 115 void name##_SPLAY(struct name *, struct type *); \ Err bitreich.org 70 i 116 void name##_SPLAY_MINMAX(struct name *, int); \ Err bitreich.org 70 i 117 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ Err bitreich.org 70 i 118 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ Err bitreich.org 70 i 119 \ Err bitreich.org 70 i 120 /* Finds the node with the same key as elm */ \ Err bitreich.org 70 i 121 static __unused __inline struct type * \ Err bitreich.org 70 i 122 name##_SPLAY_FIND(struct name *head, struct type *elm) \ Err bitreich.org 70 i 123 { \ Err bitreich.org 70 i 124 if (SPLAY_EMPTY(head)) \ Err bitreich.org 70 i 125 return(NULL); \ Err bitreich.org 70 i 126 name##_SPLAY(head, elm); \ Err bitreich.org 70 i 127 if ((cmp)(elm, (head)->sph_root) == 0) \ Err bitreich.org 70 i 128 return (head->sph_root); \ Err bitreich.org 70 i 129 return (NULL); \ Err bitreich.org 70 i 130 } \ Err bitreich.org 70 i 131 \ Err bitreich.org 70 i 132 static __unused __inline struct type * \ Err bitreich.org 70 i 133 name##_SPLAY_NEXT(struct name *head, struct type *elm) \ Err bitreich.org 70 i 134 { \ Err bitreich.org 70 i 135 name##_SPLAY(head, elm); \ Err bitreich.org 70 i 136 if (SPLAY_RIGHT(elm, field) != NULL) { \ Err bitreich.org 70 i 137 elm = SPLAY_RIGHT(elm, field); \ Err bitreich.org 70 i 138 while (SPLAY_LEFT(elm, field) != NULL) { \ Err bitreich.org 70 i 139 elm = SPLAY_LEFT(elm, field); \ Err bitreich.org 70 i 140 } \ Err bitreich.org 70 i 141 } else \ Err bitreich.org 70 i 142 elm = NULL; \ Err bitreich.org 70 i 143 return (elm); \ Err bitreich.org 70 i 144 } \ Err bitreich.org 70 i 145 \ Err bitreich.org 70 i 146 static __unused __inline struct type * \ Err bitreich.org 70 i 147 name##_SPLAY_MIN_MAX(struct name *head, int val) \ Err bitreich.org 70 i 148 { \ Err bitreich.org 70 i 149 name##_SPLAY_MINMAX(head, val); \ Err bitreich.org 70 i 150 return (SPLAY_ROOT(head)); \ Err bitreich.org 70 i 151 } Err bitreich.org 70 i 152 Err bitreich.org 70 i 153 /* Main splay operation. Err bitreich.org 70 i 154 * Moves node close to the key of elm to top Err bitreich.org 70 i 155 */ Err bitreich.org 70 i 156 #define SPLAY_GENERATE(name, type, field, cmp) \ Err bitreich.org 70 i 157 struct type * \ Err bitreich.org 70 i 158 name##_SPLAY_INSERT(struct name *head, struct type *elm) \ Err bitreich.org 70 i 159 { \ Err bitreich.org 70 i 160 if (SPLAY_EMPTY(head)) { \ Err bitreich.org 70 i 161 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ Err bitreich.org 70 i 162 } else { \ Err bitreich.org 70 i 163 int __comp; \ Err bitreich.org 70 i 164 name##_SPLAY(head, elm); \ Err bitreich.org 70 i 165 __comp = (cmp)(elm, (head)->sph_root); \ Err bitreich.org 70 i 166 if(__comp < 0) { \ Err bitreich.org 70 i 167 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ Err bitreich.org 70 i 168 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ Err bitreich.org 70 i 169 SPLAY_LEFT((head)->sph_root, field) = NULL; \ Err bitreich.org 70 i 170 } else if (__comp > 0) { \ Err bitreich.org 70 i 171 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ Err bitreich.org 70 i 172 SPLAY_LEFT(elm, field) = (head)->sph_root; \ Err bitreich.org 70 i 173 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ Err bitreich.org 70 i 174 } else \ Err bitreich.org 70 i 175 return ((head)->sph_root); \ Err bitreich.org 70 i 176 } \ Err bitreich.org 70 i 177 (head)->sph_root = (elm); \ Err bitreich.org 70 i 178 return (NULL); \ Err bitreich.org 70 i 179 } \ Err bitreich.org 70 i 180 \ Err bitreich.org 70 i 181 struct type * \ Err bitreich.org 70 i 182 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ Err bitreich.org 70 i 183 { \ Err bitreich.org 70 i 184 struct type *__tmp; \ Err bitreich.org 70 i 185 if (SPLAY_EMPTY(head)) \ Err bitreich.org 70 i 186 return (NULL); \ Err bitreich.org 70 i 187 name##_SPLAY(head, elm); \ Err bitreich.org 70 i 188 if ((cmp)(elm, (head)->sph_root) == 0) { \ Err bitreich.org 70 i 189 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ Err bitreich.org 70 i 190 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ Err bitreich.org 70 i 191 } else { \ Err bitreich.org 70 i 192 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ Err bitreich.org 70 i 193 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ Err bitreich.org 70 i 194 name##_SPLAY(head, elm); \ Err bitreich.org 70 i 195 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ Err bitreich.org 70 i 196 } \ Err bitreich.org 70 i 197 return (elm); \ Err bitreich.org 70 i 198 } \ Err bitreich.org 70 i 199 return (NULL); \ Err bitreich.org 70 i 200 } \ Err bitreich.org 70 i 201 \ Err bitreich.org 70 i 202 void \ Err bitreich.org 70 i 203 name##_SPLAY(struct name *head, struct type *elm) \ Err bitreich.org 70 i 204 { \ Err bitreich.org 70 i 205 struct type __node, *__left, *__right, *__tmp; \ Err bitreich.org 70 i 206 int __comp; \ Err bitreich.org 70 i 207 \ Err bitreich.org 70 i 208 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ Err bitreich.org 70 i 209 __left = __right = &__node; \ Err bitreich.org 70 i 210 \ Err bitreich.org 70 i 211 while ((__comp = (cmp)(elm, (head)->sph_root))) { \ Err bitreich.org 70 i 212 if (__comp < 0) { \ Err bitreich.org 70 i 213 __tmp = SPLAY_LEFT((head)->sph_root, field); \ Err bitreich.org 70 i 214 if (__tmp == NULL) \ Err bitreich.org 70 i 215 break; \ Err bitreich.org 70 i 216 if ((cmp)(elm, __tmp) < 0){ \ Err bitreich.org 70 i 217 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ Err bitreich.org 70 i 218 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ Err bitreich.org 70 i 219 break; \ Err bitreich.org 70 i 220 } \ Err bitreich.org 70 i 221 SPLAY_LINKLEFT(head, __right, field); \ Err bitreich.org 70 i 222 } else if (__comp > 0) { \ Err bitreich.org 70 i 223 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ Err bitreich.org 70 i 224 if (__tmp == NULL) \ Err bitreich.org 70 i 225 break; \ Err bitreich.org 70 i 226 if ((cmp)(elm, __tmp) > 0){ \ Err bitreich.org 70 i 227 SPLAY_ROTATE_LEFT(head, __tmp, field); \ Err bitreich.org 70 i 228 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ Err bitreich.org 70 i 229 break; \ Err bitreich.org 70 i 230 } \ Err bitreich.org 70 i 231 SPLAY_LINKRIGHT(head, __left, field); \ Err bitreich.org 70 i 232 } \ Err bitreich.org 70 i 233 } \ Err bitreich.org 70 i 234 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ Err bitreich.org 70 i 235 } \ Err bitreich.org 70 i 236 \ Err bitreich.org 70 i 237 /* Splay with either the minimum or the maximum element \ Err bitreich.org 70 i 238 * Used to find minimum or maximum element in tree. \ Err bitreich.org 70 i 239 */ \ Err bitreich.org 70 i 240 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ Err bitreich.org 70 i 241 { \ Err bitreich.org 70 i 242 struct type __node, *__left, *__right, *__tmp; \ Err bitreich.org 70 i 243 \ Err bitreich.org 70 i 244 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ Err bitreich.org 70 i 245 __left = __right = &__node; \ Err bitreich.org 70 i 246 \ Err bitreich.org 70 i 247 while (1) { \ Err bitreich.org 70 i 248 if (__comp < 0) { \ Err bitreich.org 70 i 249 __tmp = SPLAY_LEFT((head)->sph_root, field); \ Err bitreich.org 70 i 250 if (__tmp == NULL) \ Err bitreich.org 70 i 251 break; \ Err bitreich.org 70 i 252 if (__comp < 0){ \ Err bitreich.org 70 i 253 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ Err bitreich.org 70 i 254 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ Err bitreich.org 70 i 255 break; \ Err bitreich.org 70 i 256 } \ Err bitreich.org 70 i 257 SPLAY_LINKLEFT(head, __right, field); \ Err bitreich.org 70 i 258 } else if (__comp > 0) { \ Err bitreich.org 70 i 259 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ Err bitreich.org 70 i 260 if (__tmp == NULL) \ Err bitreich.org 70 i 261 break; \ Err bitreich.org 70 i 262 if (__comp > 0) { \ Err bitreich.org 70 i 263 SPLAY_ROTATE_LEFT(head, __tmp, field); \ Err bitreich.org 70 i 264 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ Err bitreich.org 70 i 265 break; \ Err bitreich.org 70 i 266 } \ Err bitreich.org 70 i 267 SPLAY_LINKRIGHT(head, __left, field); \ Err bitreich.org 70 i 268 } \ Err bitreich.org 70 i 269 } \ Err bitreich.org 70 i 270 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ Err bitreich.org 70 i 271 } Err bitreich.org 70 i 272 Err bitreich.org 70 i 273 #define SPLAY_NEGINF -1 Err bitreich.org 70 i 274 #define SPLAY_INF 1 Err bitreich.org 70 i 275 Err bitreich.org 70 i 276 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) Err bitreich.org 70 i 277 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) Err bitreich.org 70 i 278 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) Err bitreich.org 70 i 279 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) Err bitreich.org 70 i 280 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ Err bitreich.org 70 i 281 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) Err bitreich.org 70 i 282 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ Err bitreich.org 70 i 283 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) Err bitreich.org 70 i 284 Err bitreich.org 70 i 285 #define SPLAY_FOREACH(x, name, head) \ Err bitreich.org 70 i 286 for ((x) = SPLAY_MIN(name, head); \ Err bitreich.org 70 i 287 (x) != NULL; \ Err bitreich.org 70 i 288 (x) = SPLAY_NEXT(name, head, x)) Err bitreich.org 70 i 289 Err bitreich.org 70 i 290 /* Macros that define a red-black tree */ Err bitreich.org 70 i 291 #define RB_HEAD(name, type) \ Err bitreich.org 70 i 292 struct name { \ Err bitreich.org 70 i 293 struct type *rbh_root; /* root of the tree */ \ Err bitreich.org 70 i 294 } Err bitreich.org 70 i 295 Err bitreich.org 70 i 296 #define RB_INITIALIZER(root) \ Err bitreich.org 70 i 297 { NULL } Err bitreich.org 70 i 298 Err bitreich.org 70 i 299 #define RB_INIT(root) do { \ Err bitreich.org 70 i 300 (root)->rbh_root = NULL; \ Err bitreich.org 70 i 301 } while (0) Err bitreich.org 70 i 302 Err bitreich.org 70 i 303 #define RB_BLACK 0 Err bitreich.org 70 i 304 #define RB_RED 1 Err bitreich.org 70 i 305 #define RB_ENTRY(type) \ Err bitreich.org 70 i 306 struct { \ Err bitreich.org 70 i 307 struct type *rbe_left; /* left element */ \ Err bitreich.org 70 i 308 struct type *rbe_right; /* right element */ \ Err bitreich.org 70 i 309 struct type *rbe_parent; /* parent element */ \ Err bitreich.org 70 i 310 int rbe_color; /* node color */ \ Err bitreich.org 70 i 311 } Err bitreich.org 70 i 312 Err bitreich.org 70 i 313 #define RB_LEFT(elm, field) (elm)->field.rbe_left Err bitreich.org 70 i 314 #define RB_RIGHT(elm, field) (elm)->field.rbe_right Err bitreich.org 70 i 315 #define RB_PARENT(elm, field) (elm)->field.rbe_parent Err bitreich.org 70 i 316 #define RB_COLOR(elm, field) (elm)->field.rbe_color Err bitreich.org 70 i 317 #define RB_ROOT(head) (head)->rbh_root Err bitreich.org 70 i 318 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) Err bitreich.org 70 i 319 Err bitreich.org 70 i 320 #define RB_SET(elm, parent, field) do { \ Err bitreich.org 70 i 321 RB_PARENT(elm, field) = parent; \ Err bitreich.org 70 i 322 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ Err bitreich.org 70 i 323 RB_COLOR(elm, field) = RB_RED; \ Err bitreich.org 70 i 324 } while (0) Err bitreich.org 70 i 325 Err bitreich.org 70 i 326 #define RB_SET_BLACKRED(black, red, field) do { \ Err bitreich.org 70 i 327 RB_COLOR(black, field) = RB_BLACK; \ Err bitreich.org 70 i 328 RB_COLOR(red, field) = RB_RED; \ Err bitreich.org 70 i 329 } while (0) Err bitreich.org 70 i 330 Err bitreich.org 70 i 331 #ifndef RB_AUGMENT Err bitreich.org 70 i 332 #define RB_AUGMENT(x) do {} while (0) Err bitreich.org 70 i 333 #endif Err bitreich.org 70 i 334 Err bitreich.org 70 i 335 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ Err bitreich.org 70 i 336 (tmp) = RB_RIGHT(elm, field); \ Err bitreich.org 70 i 337 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ Err bitreich.org 70 i 338 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ Err bitreich.org 70 i 339 } \ Err bitreich.org 70 i 340 RB_AUGMENT(elm); \ Err bitreich.org 70 i 341 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ Err bitreich.org 70 i 342 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ Err bitreich.org 70 i 343 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ Err bitreich.org 70 i 344 else \ Err bitreich.org 70 i 345 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ Err bitreich.org 70 i 346 } else \ Err bitreich.org 70 i 347 (head)->rbh_root = (tmp); \ Err bitreich.org 70 i 348 RB_LEFT(tmp, field) = (elm); \ Err bitreich.org 70 i 349 RB_PARENT(elm, field) = (tmp); \ Err bitreich.org 70 i 350 RB_AUGMENT(tmp); \ Err bitreich.org 70 i 351 if ((RB_PARENT(tmp, field))) \ Err bitreich.org 70 i 352 RB_AUGMENT(RB_PARENT(tmp, field)); \ Err bitreich.org 70 i 353 } while (0) Err bitreich.org 70 i 354 Err bitreich.org 70 i 355 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ Err bitreich.org 70 i 356 (tmp) = RB_LEFT(elm, field); \ Err bitreich.org 70 i 357 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ Err bitreich.org 70 i 358 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ Err bitreich.org 70 i 359 } \ Err bitreich.org 70 i 360 RB_AUGMENT(elm); \ Err bitreich.org 70 i 361 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ Err bitreich.org 70 i 362 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ Err bitreich.org 70 i 363 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ Err bitreich.org 70 i 364 else \ Err bitreich.org 70 i 365 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ Err bitreich.org 70 i 366 } else \ Err bitreich.org 70 i 367 (head)->rbh_root = (tmp); \ Err bitreich.org 70 i 368 RB_RIGHT(tmp, field) = (elm); \ Err bitreich.org 70 i 369 RB_PARENT(elm, field) = (tmp); \ Err bitreich.org 70 i 370 RB_AUGMENT(tmp); \ Err bitreich.org 70 i 371 if ((RB_PARENT(tmp, field))) \ Err bitreich.org 70 i 372 RB_AUGMENT(RB_PARENT(tmp, field)); \ Err bitreich.org 70 i 373 } while (0) Err bitreich.org 70 i 374 Err bitreich.org 70 i 375 /* Generates prototypes and inline functions */ Err bitreich.org 70 i 376 #define RB_PROTOTYPE(name, type, field, cmp) \ Err bitreich.org 70 i 377 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) Err bitreich.org 70 i 378 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ Err bitreich.org 70 i 379 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) Err bitreich.org 70 i 380 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ Err bitreich.org 70 i 381 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ Err bitreich.org 70 i 382 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ Err bitreich.org 70 i 383 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ Err bitreich.org 70 i 384 attr struct type *name##_RB_INSERT(struct name *, struct type *); \ Err bitreich.org 70 i 385 attr struct type *name##_RB_FIND(struct name *, struct type *); \ Err bitreich.org 70 i 386 attr struct type *name##_RB_NFIND(struct name *, struct type *); \ Err bitreich.org 70 i 387 attr struct type *name##_RB_NEXT(struct type *); \ Err bitreich.org 70 i 388 attr struct type *name##_RB_PREV(struct type *); \ Err bitreich.org 70 i 389 attr struct type *name##_RB_MINMAX(struct name *, int); \ Err bitreich.org 70 i 390 \ Err bitreich.org 70 i 391 Err bitreich.org 70 i 392 /* Main rb operation. Err bitreich.org 70 i 393 * Moves node close to the key of elm to top Err bitreich.org 70 i 394 */ Err bitreich.org 70 i 395 #define RB_GENERATE(name, type, field, cmp) \ Err bitreich.org 70 i 396 RB_GENERATE_INTERNAL(name, type, field, cmp,) Err bitreich.org 70 i 397 #define RB_GENERATE_STATIC(name, type, field, cmp) \ Err bitreich.org 70 i 398 RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) Err bitreich.org 70 i 399 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ Err bitreich.org 70 i 400 attr void \ Err bitreich.org 70 i 401 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ Err bitreich.org 70 i 402 { \ Err bitreich.org 70 i 403 struct type *parent, *gparent, *tmp; \ Err bitreich.org 70 i 404 while ((parent = RB_PARENT(elm, field)) && \ Err bitreich.org 70 i 405 RB_COLOR(parent, field) == RB_RED) { \ Err bitreich.org 70 i 406 gparent = RB_PARENT(parent, field); \ Err bitreich.org 70 i 407 if (parent == RB_LEFT(gparent, field)) { \ Err bitreich.org 70 i 408 tmp = RB_RIGHT(gparent, field); \ Err bitreich.org 70 i 409 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ Err bitreich.org 70 i 410 RB_COLOR(tmp, field) = RB_BLACK; \ Err bitreich.org 70 i 411 RB_SET_BLACKRED(parent, gparent, field);\ Err bitreich.org 70 i 412 elm = gparent; \ Err bitreich.org 70 i 413 continue; \ Err bitreich.org 70 i 414 } \ Err bitreich.org 70 i 415 if (RB_RIGHT(parent, field) == elm) { \ Err bitreich.org 70 i 416 RB_ROTATE_LEFT(head, parent, tmp, field);\ Err bitreich.org 70 i 417 tmp = parent; \ Err bitreich.org 70 i 418 parent = elm; \ Err bitreich.org 70 i 419 elm = tmp; \ Err bitreich.org 70 i 420 } \ Err bitreich.org 70 i 421 RB_SET_BLACKRED(parent, gparent, field); \ Err bitreich.org 70 i 422 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ Err bitreich.org 70 i 423 } else { \ Err bitreich.org 70 i 424 tmp = RB_LEFT(gparent, field); \ Err bitreich.org 70 i 425 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ Err bitreich.org 70 i 426 RB_COLOR(tmp, field) = RB_BLACK; \ Err bitreich.org 70 i 427 RB_SET_BLACKRED(parent, gparent, field);\ Err bitreich.org 70 i 428 elm = gparent; \ Err bitreich.org 70 i 429 continue; \ Err bitreich.org 70 i 430 } \ Err bitreich.org 70 i 431 if (RB_LEFT(parent, field) == elm) { \ Err bitreich.org 70 i 432 RB_ROTATE_RIGHT(head, parent, tmp, field);\ Err bitreich.org 70 i 433 tmp = parent; \ Err bitreich.org 70 i 434 parent = elm; \ Err bitreich.org 70 i 435 elm = tmp; \ Err bitreich.org 70 i 436 } \ Err bitreich.org 70 i 437 RB_SET_BLACKRED(parent, gparent, field); \ Err bitreich.org 70 i 438 RB_ROTATE_LEFT(head, gparent, tmp, field); \ Err bitreich.org 70 i 439 } \ Err bitreich.org 70 i 440 } \ Err bitreich.org 70 i 441 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ Err bitreich.org 70 i 442 } \ Err bitreich.org 70 i 443 \ Err bitreich.org 70 i 444 attr void \ Err bitreich.org 70 i 445 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ Err bitreich.org 70 i 446 { \ Err bitreich.org 70 i 447 struct type *tmp; \ Err bitreich.org 70 i 448 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ Err bitreich.org 70 i 449 elm != RB_ROOT(head)) { \ Err bitreich.org 70 i 450 if (RB_LEFT(parent, field) == elm) { \ Err bitreich.org 70 i 451 tmp = RB_RIGHT(parent, field); \ Err bitreich.org 70 i 452 if (RB_COLOR(tmp, field) == RB_RED) { \ Err bitreich.org 70 i 453 RB_SET_BLACKRED(tmp, parent, field); \ Err bitreich.org 70 i 454 RB_ROTATE_LEFT(head, parent, tmp, field);\ Err bitreich.org 70 i 455 tmp = RB_RIGHT(parent, field); \ Err bitreich.org 70 i 456 } \ Err bitreich.org 70 i 457 if ((RB_LEFT(tmp, field) == NULL || \ Err bitreich.org 70 i 458 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ Err bitreich.org 70 i 459 (RB_RIGHT(tmp, field) == NULL || \ Err bitreich.org 70 i 460 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ Err bitreich.org 70 i 461 RB_COLOR(tmp, field) = RB_RED; \ Err bitreich.org 70 i 462 elm = parent; \ Err bitreich.org 70 i 463 parent = RB_PARENT(elm, field); \ Err bitreich.org 70 i 464 } else { \ Err bitreich.org 70 i 465 if (RB_RIGHT(tmp, field) == NULL || \ Err bitreich.org 70 i 466 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ Err bitreich.org 70 i 467 struct type *oleft; \ Err bitreich.org 70 i 468 if ((oleft = RB_LEFT(tmp, field)))\ Err bitreich.org 70 i 469 RB_COLOR(oleft, field) = RB_BLACK;\ Err bitreich.org 70 i 470 RB_COLOR(tmp, field) = RB_RED; \ Err bitreich.org 70 i 471 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ Err bitreich.org 70 i 472 tmp = RB_RIGHT(parent, field); \ Err bitreich.org 70 i 473 } \ Err bitreich.org 70 i 474 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ Err bitreich.org 70 i 475 RB_COLOR(parent, field) = RB_BLACK; \ Err bitreich.org 70 i 476 if (RB_RIGHT(tmp, field)) \ Err bitreich.org 70 i 477 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ Err bitreich.org 70 i 478 RB_ROTATE_LEFT(head, parent, tmp, field);\ Err bitreich.org 70 i 479 elm = RB_ROOT(head); \ Err bitreich.org 70 i 480 break; \ Err bitreich.org 70 i 481 } \ Err bitreich.org 70 i 482 } else { \ Err bitreich.org 70 i 483 tmp = RB_LEFT(parent, field); \ Err bitreich.org 70 i 484 if (RB_COLOR(tmp, field) == RB_RED) { \ Err bitreich.org 70 i 485 RB_SET_BLACKRED(tmp, parent, field); \ Err bitreich.org 70 i 486 RB_ROTATE_RIGHT(head, parent, tmp, field);\ Err bitreich.org 70 i 487 tmp = RB_LEFT(parent, field); \ Err bitreich.org 70 i 488 } \ Err bitreich.org 70 i 489 if ((RB_LEFT(tmp, field) == NULL || \ Err bitreich.org 70 i 490 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ Err bitreich.org 70 i 491 (RB_RIGHT(tmp, field) == NULL || \ Err bitreich.org 70 i 492 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ Err bitreich.org 70 i 493 RB_COLOR(tmp, field) = RB_RED; \ Err bitreich.org 70 i 494 elm = parent; \ Err bitreich.org 70 i 495 parent = RB_PARENT(elm, field); \ Err bitreich.org 70 i 496 } else { \ Err bitreich.org 70 i 497 if (RB_LEFT(tmp, field) == NULL || \ Err bitreich.org 70 i 498 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ Err bitreich.org 70 i 499 struct type *oright; \ Err bitreich.org 70 i 500 if ((oright = RB_RIGHT(tmp, field)))\ Err bitreich.org 70 i 501 RB_COLOR(oright, field) = RB_BLACK;\ Err bitreich.org 70 i 502 RB_COLOR(tmp, field) = RB_RED; \ Err bitreich.org 70 i 503 RB_ROTATE_LEFT(head, tmp, oright, field);\ Err bitreich.org 70 i 504 tmp = RB_LEFT(parent, field); \ Err bitreich.org 70 i 505 } \ Err bitreich.org 70 i 506 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ Err bitreich.org 70 i 507 RB_COLOR(parent, field) = RB_BLACK; \ Err bitreich.org 70 i 508 if (RB_LEFT(tmp, field)) \ Err bitreich.org 70 i 509 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ Err bitreich.org 70 i 510 RB_ROTATE_RIGHT(head, parent, tmp, field);\ Err bitreich.org 70 i 511 elm = RB_ROOT(head); \ Err bitreich.org 70 i 512 break; \ Err bitreich.org 70 i 513 } \ Err bitreich.org 70 i 514 } \ Err bitreich.org 70 i 515 } \ Err bitreich.org 70 i 516 if (elm) \ Err bitreich.org 70 i 517 RB_COLOR(elm, field) = RB_BLACK; \ Err bitreich.org 70 i 518 } \ Err bitreich.org 70 i 519 \ Err bitreich.org 70 i 520 attr struct type * \ Err bitreich.org 70 i 521 name##_RB_REMOVE(struct name *head, struct type *elm) \ Err bitreich.org 70 i 522 { \ Err bitreich.org 70 i 523 struct type *child, *parent, *old = elm; \ Err bitreich.org 70 i 524 int color; \ Err bitreich.org 70 i 525 if (RB_LEFT(elm, field) == NULL) \ Err bitreich.org 70 i 526 child = RB_RIGHT(elm, field); \ Err bitreich.org 70 i 527 else if (RB_RIGHT(elm, field) == NULL) \ Err bitreich.org 70 i 528 child = RB_LEFT(elm, field); \ Err bitreich.org 70 i 529 else { \ Err bitreich.org 70 i 530 struct type *left; \ Err bitreich.org 70 i 531 elm = RB_RIGHT(elm, field); \ Err bitreich.org 70 i 532 while ((left = RB_LEFT(elm, field))) \ Err bitreich.org 70 i 533 elm = left; \ Err bitreich.org 70 i 534 child = RB_RIGHT(elm, field); \ Err bitreich.org 70 i 535 parent = RB_PARENT(elm, field); \ Err bitreich.org 70 i 536 color = RB_COLOR(elm, field); \ Err bitreich.org 70 i 537 if (child) \ Err bitreich.org 70 i 538 RB_PARENT(child, field) = parent; \ Err bitreich.org 70 i 539 if (parent) { \ Err bitreich.org 70 i 540 if (RB_LEFT(parent, field) == elm) \ Err bitreich.org 70 i 541 RB_LEFT(parent, field) = child; \ Err bitreich.org 70 i 542 else \ Err bitreich.org 70 i 543 RB_RIGHT(parent, field) = child; \ Err bitreich.org 70 i 544 RB_AUGMENT(parent); \ Err bitreich.org 70 i 545 } else \ Err bitreich.org 70 i 546 RB_ROOT(head) = child; \ Err bitreich.org 70 i 547 if (RB_PARENT(elm, field) == old) \ Err bitreich.org 70 i 548 parent = elm; \ Err bitreich.org 70 i 549 (elm)->field = (old)->field; \ Err bitreich.org 70 i 550 if (RB_PARENT(old, field)) { \ Err bitreich.org 70 i 551 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ Err bitreich.org 70 i 552 RB_LEFT(RB_PARENT(old, field), field) = elm;\ Err bitreich.org 70 i 553 else \ Err bitreich.org 70 i 554 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ Err bitreich.org 70 i 555 RB_AUGMENT(RB_PARENT(old, field)); \ Err bitreich.org 70 i 556 } else \ Err bitreich.org 70 i 557 RB_ROOT(head) = elm; \ Err bitreich.org 70 i 558 RB_PARENT(RB_LEFT(old, field), field) = elm; \ Err bitreich.org 70 i 559 if (RB_RIGHT(old, field)) \ Err bitreich.org 70 i 560 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ Err bitreich.org 70 i 561 if (parent) { \ Err bitreich.org 70 i 562 left = parent; \ Err bitreich.org 70 i 563 do { \ Err bitreich.org 70 i 564 RB_AUGMENT(left); \ Err bitreich.org 70 i 565 } while ((left = RB_PARENT(left, field))); \ Err bitreich.org 70 i 566 } \ Err bitreich.org 70 i 567 goto color; \ Err bitreich.org 70 i 568 } \ Err bitreich.org 70 i 569 parent = RB_PARENT(elm, field); \ Err bitreich.org 70 i 570 color = RB_COLOR(elm, field); \ Err bitreich.org 70 i 571 if (child) \ Err bitreich.org 70 i 572 RB_PARENT(child, field) = parent; \ Err bitreich.org 70 i 573 if (parent) { \ Err bitreich.org 70 i 574 if (RB_LEFT(parent, field) == elm) \ Err bitreich.org 70 i 575 RB_LEFT(parent, field) = child; \ Err bitreich.org 70 i 576 else \ Err bitreich.org 70 i 577 RB_RIGHT(parent, field) = child; \ Err bitreich.org 70 i 578 RB_AUGMENT(parent); \ Err bitreich.org 70 i 579 } else \ Err bitreich.org 70 i 580 RB_ROOT(head) = child; \ Err bitreich.org 70 i 581 color: \ Err bitreich.org 70 i 582 if (color == RB_BLACK) \ Err bitreich.org 70 i 583 name##_RB_REMOVE_COLOR(head, parent, child); \ Err bitreich.org 70 i 584 return (old); \ Err bitreich.org 70 i 585 } \ Err bitreich.org 70 i 586 \ Err bitreich.org 70 i 587 /* Inserts a node into the RB tree */ \ Err bitreich.org 70 i 588 attr struct type * \ Err bitreich.org 70 i 589 name##_RB_INSERT(struct name *head, struct type *elm) \ Err bitreich.org 70 i 590 { \ Err bitreich.org 70 i 591 struct type *tmp; \ Err bitreich.org 70 i 592 struct type *parent = NULL; \ Err bitreich.org 70 i 593 int comp = 0; \ Err bitreich.org 70 i 594 tmp = RB_ROOT(head); \ Err bitreich.org 70 i 595 while (tmp) { \ Err bitreich.org 70 i 596 parent = tmp; \ Err bitreich.org 70 i 597 comp = (cmp)(elm, parent); \ Err bitreich.org 70 i 598 if (comp < 0) \ Err bitreich.org 70 i 599 tmp = RB_LEFT(tmp, field); \ Err bitreich.org 70 i 600 else if (comp > 0) \ Err bitreich.org 70 i 601 tmp = RB_RIGHT(tmp, field); \ Err bitreich.org 70 i 602 else \ Err bitreich.org 70 i 603 return (tmp); \ Err bitreich.org 70 i 604 } \ Err bitreich.org 70 i 605 RB_SET(elm, parent, field); \ Err bitreich.org 70 i 606 if (parent != NULL) { \ Err bitreich.org 70 i 607 if (comp < 0) \ Err bitreich.org 70 i 608 RB_LEFT(parent, field) = elm; \ Err bitreich.org 70 i 609 else \ Err bitreich.org 70 i 610 RB_RIGHT(parent, field) = elm; \ Err bitreich.org 70 i 611 RB_AUGMENT(parent); \ Err bitreich.org 70 i 612 } else \ Err bitreich.org 70 i 613 RB_ROOT(head) = elm; \ Err bitreich.org 70 i 614 name##_RB_INSERT_COLOR(head, elm); \ Err bitreich.org 70 i 615 return (NULL); \ Err bitreich.org 70 i 616 } \ Err bitreich.org 70 i 617 \ Err bitreich.org 70 i 618 /* Finds the node with the same key as elm */ \ Err bitreich.org 70 i 619 attr struct type * \ Err bitreich.org 70 i 620 name##_RB_FIND(struct name *head, struct type *elm) \ Err bitreich.org 70 i 621 { \ Err bitreich.org 70 i 622 struct type *tmp = RB_ROOT(head); \ Err bitreich.org 70 i 623 int comp; \ Err bitreich.org 70 i 624 while (tmp) { \ Err bitreich.org 70 i 625 comp = cmp(elm, tmp); \ Err bitreich.org 70 i 626 if (comp < 0) \ Err bitreich.org 70 i 627 tmp = RB_LEFT(tmp, field); \ Err bitreich.org 70 i 628 else if (comp > 0) \ Err bitreich.org 70 i 629 tmp = RB_RIGHT(tmp, field); \ Err bitreich.org 70 i 630 else \ Err bitreich.org 70 i 631 return (tmp); \ Err bitreich.org 70 i 632 } \ Err bitreich.org 70 i 633 return (NULL); \ Err bitreich.org 70 i 634 } \ Err bitreich.org 70 i 635 \ Err bitreich.org 70 i 636 /* Finds the first node greater than or equal to the search key */ \ Err bitreich.org 70 i 637 attr struct type * \ Err bitreich.org 70 i 638 name##_RB_NFIND(struct name *head, struct type *elm) \ Err bitreich.org 70 i 639 { \ Err bitreich.org 70 i 640 struct type *tmp = RB_ROOT(head); \ Err bitreich.org 70 i 641 struct type *res = NULL; \ Err bitreich.org 70 i 642 int comp; \ Err bitreich.org 70 i 643 while (tmp) { \ Err bitreich.org 70 i 644 comp = cmp(elm, tmp); \ Err bitreich.org 70 i 645 if (comp < 0) { \ Err bitreich.org 70 i 646 res = tmp; \ Err bitreich.org 70 i 647 tmp = RB_LEFT(tmp, field); \ Err bitreich.org 70 i 648 } \ Err bitreich.org 70 i 649 else if (comp > 0) \ Err bitreich.org 70 i 650 tmp = RB_RIGHT(tmp, field); \ Err bitreich.org 70 i 651 else \ Err bitreich.org 70 i 652 return (tmp); \ Err bitreich.org 70 i 653 } \ Err bitreich.org 70 i 654 return (res); \ Err bitreich.org 70 i 655 } \ Err bitreich.org 70 i 656 \ Err bitreich.org 70 i 657 /* ARGSUSED */ \ Err bitreich.org 70 i 658 attr struct type * \ Err bitreich.org 70 i 659 name##_RB_NEXT(struct type *elm) \ Err bitreich.org 70 i 660 { \ Err bitreich.org 70 i 661 if (RB_RIGHT(elm, field)) { \ Err bitreich.org 70 i 662 elm = RB_RIGHT(elm, field); \ Err bitreich.org 70 i 663 while (RB_LEFT(elm, field)) \ Err bitreich.org 70 i 664 elm = RB_LEFT(elm, field); \ Err bitreich.org 70 i 665 } else { \ Err bitreich.org 70 i 666 if (RB_PARENT(elm, field) && \ Err bitreich.org 70 i 667 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ Err bitreich.org 70 i 668 elm = RB_PARENT(elm, field); \ Err bitreich.org 70 i 669 else { \ Err bitreich.org 70 i 670 while (RB_PARENT(elm, field) && \ Err bitreich.org 70 i 671 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ Err bitreich.org 70 i 672 elm = RB_PARENT(elm, field); \ Err bitreich.org 70 i 673 elm = RB_PARENT(elm, field); \ Err bitreich.org 70 i 674 } \ Err bitreich.org 70 i 675 } \ Err bitreich.org 70 i 676 return (elm); \ Err bitreich.org 70 i 677 } \ Err bitreich.org 70 i 678 \ Err bitreich.org 70 i 679 /* ARGSUSED */ \ Err bitreich.org 70 i 680 attr struct type * \ Err bitreich.org 70 i 681 name##_RB_PREV(struct type *elm) \ Err bitreich.org 70 i 682 { \ Err bitreich.org 70 i 683 if (RB_LEFT(elm, field)) { \ Err bitreich.org 70 i 684 elm = RB_LEFT(elm, field); \ Err bitreich.org 70 i 685 while (RB_RIGHT(elm, field)) \ Err bitreich.org 70 i 686 elm = RB_RIGHT(elm, field); \ Err bitreich.org 70 i 687 } else { \ Err bitreich.org 70 i 688 if (RB_PARENT(elm, field) && \ Err bitreich.org 70 i 689 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ Err bitreich.org 70 i 690 elm = RB_PARENT(elm, field); \ Err bitreich.org 70 i 691 else { \ Err bitreich.org 70 i 692 while (RB_PARENT(elm, field) && \ Err bitreich.org 70 i 693 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ Err bitreich.org 70 i 694 elm = RB_PARENT(elm, field); \ Err bitreich.org 70 i 695 elm = RB_PARENT(elm, field); \ Err bitreich.org 70 i 696 } \ Err bitreich.org 70 i 697 } \ Err bitreich.org 70 i 698 return (elm); \ Err bitreich.org 70 i 699 } \ Err bitreich.org 70 i 700 \ Err bitreich.org 70 i 701 attr struct type * \ Err bitreich.org 70 i 702 name##_RB_MINMAX(struct name *head, int val) \ Err bitreich.org 70 i 703 { \ Err bitreich.org 70 i 704 struct type *tmp = RB_ROOT(head); \ Err bitreich.org 70 i 705 struct type *parent = NULL; \ Err bitreich.org 70 i 706 while (tmp) { \ Err bitreich.org 70 i 707 parent = tmp; \ Err bitreich.org 70 i 708 if (val < 0) \ Err bitreich.org 70 i 709 tmp = RB_LEFT(tmp, field); \ Err bitreich.org 70 i 710 else \ Err bitreich.org 70 i 711 tmp = RB_RIGHT(tmp, field); \ Err bitreich.org 70 i 712 } \ Err bitreich.org 70 i 713 return (parent); \ Err bitreich.org 70 i 714 } Err bitreich.org 70 i 715 Err bitreich.org 70 i 716 #define RB_NEGINF -1 Err bitreich.org 70 i 717 #define RB_INF 1 Err bitreich.org 70 i 718 Err bitreich.org 70 i 719 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) Err bitreich.org 70 i 720 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) Err bitreich.org 70 i 721 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) Err bitreich.org 70 i 722 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) Err bitreich.org 70 i 723 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) Err bitreich.org 70 i 724 #define RB_PREV(name, x, y) name##_RB_PREV(y) Err bitreich.org 70 i 725 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) Err bitreich.org 70 i 726 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) Err bitreich.org 70 i 727 Err bitreich.org 70 i 728 #define RB_FOREACH(x, name, head) \ Err bitreich.org 70 i 729 for ((x) = RB_MIN(name, head); \ Err bitreich.org 70 i 730 (x) != NULL; \ Err bitreich.org 70 i 731 (x) = name##_RB_NEXT(x)) Err bitreich.org 70 i 732 Err bitreich.org 70 i 733 #define RB_FOREACH_SAFE(x, name, head, y) \ Err bitreich.org 70 i 734 for ((x) = RB_MIN(name, head); \ Err bitreich.org 70 i 735 ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \ Err bitreich.org 70 i 736 (x) = (y)) Err bitreich.org 70 i 737 Err bitreich.org 70 i 738 #define RB_FOREACH_REVERSE(x, name, head) \ Err bitreich.org 70 i 739 for ((x) = RB_MAX(name, head); \ Err bitreich.org 70 i 740 (x) != NULL; \ Err bitreich.org 70 i 741 (x) = name##_RB_PREV(x)) Err bitreich.org 70 i 742 Err bitreich.org 70 i 743 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ Err bitreich.org 70 i 744 for ((x) = RB_MAX(name, head); \ Err bitreich.org 70 i 745 ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ Err bitreich.org 70 i 746 (x) = (y)) Err bitreich.org 70 i 747 Err bitreich.org 70 i 748 Err bitreich.org 70 i 749 /* Err bitreich.org 70 i 750 * Copyright (c) 2016 David Gwynne Err bitreich.org 70 i 751 * Err bitreich.org 70 i 752 * Permission to use, copy, modify, and distribute this software for any Err bitreich.org 70 i 753 * purpose with or without fee is hereby granted, provided that the above Err bitreich.org 70 i 754 * copyright notice and this permission notice appear in all copies. Err bitreich.org 70 i 755 * Err bitreich.org 70 i 756 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES Err bitreich.org 70 i 757 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF Err bitreich.org 70 i 758 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR Err bitreich.org 70 i 759 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES Err bitreich.org 70 i 760 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN Err bitreich.org 70 i 761 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF Err bitreich.org 70 i 762 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. Err bitreich.org 70 i 763 */ Err bitreich.org 70 i 764 Err bitreich.org 70 i 765 struct rb_type { Err bitreich.org 70 i 766 int (*t_compare)(const void *, const void *); Err bitreich.org 70 i 767 void (*t_augment)(void *); Err bitreich.org 70 i 768 unsigned int t_offset; /* offset of rb_entry in type */ Err bitreich.org 70 i 769 }; Err bitreich.org 70 i 770 Err bitreich.org 70 i 771 struct rb_tree { Err bitreich.org 70 i 772 struct rb_entry *rbt_root; Err bitreich.org 70 i 773 }; Err bitreich.org 70 i 774 Err bitreich.org 70 i 775 struct rb_entry { Err bitreich.org 70 i 776 struct rb_entry *rbt_parent; Err bitreich.org 70 i 777 struct rb_entry *rbt_left; Err bitreich.org 70 i 778 struct rb_entry *rbt_right; Err bitreich.org 70 i 779 unsigned int rbt_color; Err bitreich.org 70 i 780 }; Err bitreich.org 70 i 781 Err bitreich.org 70 i 782 #define RBT_HEAD(_name, _type) \ Err bitreich.org 70 i 783 struct _name { \ Err bitreich.org 70 i 784 struct rb_tree rbh_root; \ Err bitreich.org 70 i 785 } Err bitreich.org 70 i 786 Err bitreich.org 70 i 787 #define RBT_ENTRY(_type) struct rb_entry Err bitreich.org 70 i 788 Err bitreich.org 70 i 789 static inline void Err bitreich.org 70 i 790 _rb_init(struct rb_tree *rbt) Err bitreich.org 70 i 791 { Err bitreich.org 70 i 792 rbt->rbt_root = NULL; Err bitreich.org 70 i 793 } Err bitreich.org 70 i 794 Err bitreich.org 70 i 795 static inline int Err bitreich.org 70 i 796 _rb_empty(struct rb_tree *rbt) Err bitreich.org 70 i 797 { Err bitreich.org 70 i 798 return (rbt->rbt_root == NULL); Err bitreich.org 70 i 799 } Err bitreich.org 70 i 800 Err bitreich.org 70 i 801 void *_rb_insert(const struct rb_type *, struct rb_tree *, void *); Err bitreich.org 70 i 802 void *_rb_remove(const struct rb_type *, struct rb_tree *, void *); Err bitreich.org 70 i 803 void *_rb_find(const struct rb_type *, struct rb_tree *, const void *); Err bitreich.org 70 i 804 void *_rb_nfind(const struct rb_type *, struct rb_tree *, const void *); Err bitreich.org 70 i 805 void *_rb_root(const struct rb_type *, struct rb_tree *); Err bitreich.org 70 i 806 void *_rb_min(const struct rb_type *, struct rb_tree *); Err bitreich.org 70 i 807 void *_rb_max(const struct rb_type *, struct rb_tree *); Err bitreich.org 70 i 808 void *_rb_next(const struct rb_type *, void *); Err bitreich.org 70 i 809 void *_rb_prev(const struct rb_type *, void *); Err bitreich.org 70 i 810 void *_rb_left(const struct rb_type *, void *); Err bitreich.org 70 i 811 void *_rb_right(const struct rb_type *, void *); Err bitreich.org 70 i 812 void *_rb_parent(const struct rb_type *, void *); Err bitreich.org 70 i 813 void _rb_set_left(const struct rb_type *, void *, void *); Err bitreich.org 70 i 814 void _rb_set_right(const struct rb_type *, void *, void *); Err bitreich.org 70 i 815 void _rb_set_parent(const struct rb_type *, void *, void *); Err bitreich.org 70 i 816 void _rb_poison(const struct rb_type *, void *, unsigned long); Err bitreich.org 70 i 817 int _rb_check(const struct rb_type *, void *, unsigned long); Err bitreich.org 70 i 818 Err bitreich.org 70 i 819 #define RBT_INITIALIZER(_head) { { NULL } } Err bitreich.org 70 i 820 Err bitreich.org 70 i 821 #define RBT_PROTOTYPE(_name, _type, _field, _cmp) \ Err bitreich.org 70 i 822 extern const struct rb_type *const _name##_RBT_TYPE; \ Err bitreich.org 70 i 823 \ Err bitreich.org 70 i 824 __unused static inline void \ Err bitreich.org 70 i 825 _name##_RBT_INIT(struct _name *head) \ Err bitreich.org 70 i 826 { \ Err bitreich.org 70 i 827 _rb_init(&head->rbh_root); \ Err bitreich.org 70 i 828 } \ Err bitreich.org 70 i 829 \ Err bitreich.org 70 i 830 __unused static inline struct _type * \ Err bitreich.org 70 i 831 _name##_RBT_INSERT(struct _name *head, struct _type *elm) \ Err bitreich.org 70 i 832 { \ Err bitreich.org 70 i 833 return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm); \ Err bitreich.org 70 i 834 } \ Err bitreich.org 70 i 835 \ Err bitreich.org 70 i 836 __unused static inline struct _type * \ Err bitreich.org 70 i 837 _name##_RBT_REMOVE(struct _name *head, struct _type *elm) \ Err bitreich.org 70 i 838 { \ Err bitreich.org 70 i 839 return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm); \ Err bitreich.org 70 i 840 } \ Err bitreich.org 70 i 841 \ Err bitreich.org 70 i 842 __unused static inline struct _type * \ Err bitreich.org 70 i 843 _name##_RBT_FIND(struct _name *head, const struct _type *key) \ Err bitreich.org 70 i 844 { \ Err bitreich.org 70 i 845 return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key); \ Err bitreich.org 70 i 846 } \ Err bitreich.org 70 i 847 \ Err bitreich.org 70 i 848 __unused static inline struct _type * \ Err bitreich.org 70 i 849 _name##_RBT_NFIND(struct _name *head, const struct _type *key) \ Err bitreich.org 70 i 850 { \ Err bitreich.org 70 i 851 return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key); \ Err bitreich.org 70 i 852 } \ Err bitreich.org 70 i 853 \ Err bitreich.org 70 i 854 __unused static inline struct _type * \ Err bitreich.org 70 i 855 _name##_RBT_ROOT(struct _name *head) \ Err bitreich.org 70 i 856 { \ Err bitreich.org 70 i 857 return _rb_root(_name##_RBT_TYPE, &head->rbh_root); \ Err bitreich.org 70 i 858 } \ Err bitreich.org 70 i 859 \ Err bitreich.org 70 i 860 __unused static inline int \ Err bitreich.org 70 i 861 _name##_RBT_EMPTY(struct _name *head) \ Err bitreich.org 70 i 862 { \ Err bitreich.org 70 i 863 return _rb_empty(&head->rbh_root); \ Err bitreich.org 70 i 864 } \ Err bitreich.org 70 i 865 \ Err bitreich.org 70 i 866 __unused static inline struct _type * \ Err bitreich.org 70 i 867 _name##_RBT_MIN(struct _name *head) \ Err bitreich.org 70 i 868 { \ Err bitreich.org 70 i 869 return _rb_min(_name##_RBT_TYPE, &head->rbh_root); \ Err bitreich.org 70 i 870 } \ Err bitreich.org 70 i 871 \ Err bitreich.org 70 i 872 __unused static inline struct _type * \ Err bitreich.org 70 i 873 _name##_RBT_MAX(struct _name *head) \ Err bitreich.org 70 i 874 { \ Err bitreich.org 70 i 875 return _rb_max(_name##_RBT_TYPE, &head->rbh_root); \ Err bitreich.org 70 i 876 } \ Err bitreich.org 70 i 877 \ Err bitreich.org 70 i 878 __unused static inline struct _type * \ Err bitreich.org 70 i 879 _name##_RBT_NEXT(struct _type *elm) \ Err bitreich.org 70 i 880 { \ Err bitreich.org 70 i 881 return _rb_next(_name##_RBT_TYPE, elm); \ Err bitreich.org 70 i 882 } \ Err bitreich.org 70 i 883 \ Err bitreich.org 70 i 884 __unused static inline struct _type * \ Err bitreich.org 70 i 885 _name##_RBT_PREV(struct _type *elm) \ Err bitreich.org 70 i 886 { \ Err bitreich.org 70 i 887 return _rb_prev(_name##_RBT_TYPE, elm); \ Err bitreich.org 70 i 888 } \ Err bitreich.org 70 i 889 \ Err bitreich.org 70 i 890 __unused static inline struct _type * \ Err bitreich.org 70 i 891 _name##_RBT_LEFT(struct _type *elm) \ Err bitreich.org 70 i 892 { \ Err bitreich.org 70 i 893 return _rb_left(_name##_RBT_TYPE, elm); \ Err bitreich.org 70 i 894 } \ Err bitreich.org 70 i 895 \ Err bitreich.org 70 i 896 __unused static inline struct _type * \ Err bitreich.org 70 i 897 _name##_RBT_RIGHT(struct _type *elm) \ Err bitreich.org 70 i 898 { \ Err bitreich.org 70 i 899 return _rb_right(_name##_RBT_TYPE, elm); \ Err bitreich.org 70 i 900 } \ Err bitreich.org 70 i 901 \ Err bitreich.org 70 i 902 __unused static inline struct _type * \ Err bitreich.org 70 i 903 _name##_RBT_PARENT(struct _type *elm) \ Err bitreich.org 70 i 904 { \ Err bitreich.org 70 i 905 return _rb_parent(_name##_RBT_TYPE, elm); \ Err bitreich.org 70 i 906 } \ Err bitreich.org 70 i 907 \ Err bitreich.org 70 i 908 __unused static inline void \ Err bitreich.org 70 i 909 _name##_RBT_SET_LEFT(struct _type *elm, struct _type *left) \ Err bitreich.org 70 i 910 { \ Err bitreich.org 70 i 911 return _rb_set_left(_name##_RBT_TYPE, elm, left); \ Err bitreich.org 70 i 912 } \ Err bitreich.org 70 i 913 \ Err bitreich.org 70 i 914 __unused static inline void \ Err bitreich.org 70 i 915 _name##_RBT_SET_RIGHT(struct _type *elm, struct _type *right) \ Err bitreich.org 70 i 916 { \ Err bitreich.org 70 i 917 return _rb_set_right(_name##_RBT_TYPE, elm, right); \ Err bitreich.org 70 i 918 } \ Err bitreich.org 70 i 919 \ Err bitreich.org 70 i 920 __unused static inline void \ Err bitreich.org 70 i 921 _name##_RBT_SET_PARENT(struct _type *elm, struct _type *parent) \ Err bitreich.org 70 i 922 { \ Err bitreich.org 70 i 923 return _rb_set_parent(_name##_RBT_TYPE, elm, parent); \ Err bitreich.org 70 i 924 } \ Err bitreich.org 70 i 925 \ Err bitreich.org 70 i 926 __unused static inline void \ Err bitreich.org 70 i 927 _name##_RBT_POISON(struct _type *elm, unsigned long poison) \ Err bitreich.org 70 i 928 { \ Err bitreich.org 70 i 929 return _rb_poison(_name##_RBT_TYPE, elm, poison); \ Err bitreich.org 70 i 930 } \ Err bitreich.org 70 i 931 \ Err bitreich.org 70 i 932 __unused static inline int \ Err bitreich.org 70 i 933 _name##_RBT_CHECK(struct _type *elm, unsigned long poison) \ Err bitreich.org 70 i 934 { \ Err bitreich.org 70 i 935 return _rb_check(_name##_RBT_TYPE, elm, poison); \ Err bitreich.org 70 i 936 } Err bitreich.org 70 i 937 Err bitreich.org 70 i 938 #define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ Err bitreich.org 70 i 939 static int \ Err bitreich.org 70 i 940 _name##_RBT_COMPARE(const void *lptr, const void *rptr) \ Err bitreich.org 70 i 941 { \ Err bitreich.org 70 i 942 const struct _type *l = lptr, *r = rptr; \ Err bitreich.org 70 i 943 return _cmp(l, r); \ Err bitreich.org 70 i 944 } \ Err bitreich.org 70 i 945 static const struct rb_type _name##_RBT_INFO = { \ Err bitreich.org 70 i 946 _name##_RBT_COMPARE, \ Err bitreich.org 70 i 947 _aug, \ Err bitreich.org 70 i 948 offsetof(struct _type, _field), \ Err bitreich.org 70 i 949 }; \ Err bitreich.org 70 i 950 const struct rb_type *const _name##_RBT_TYPE = &_name##_RBT_INFO Err bitreich.org 70 i 951 Err bitreich.org 70 i 952 #define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ Err bitreich.org 70 i 953 static void \ Err bitreich.org 70 i 954 _name##_RBT_AUGMENT(void *ptr) \ Err bitreich.org 70 i 955 { \ Err bitreich.org 70 i 956 struct _type *p = ptr; \ Err bitreich.org 70 i 957 return _aug(p); \ Err bitreich.org 70 i 958 } \ Err bitreich.org 70 i 959 RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT) Err bitreich.org 70 i 960 Err bitreich.org 70 i 961 #define RBT_GENERATE(_name, _type, _field, _cmp) \ Err bitreich.org 70 i 962 RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) Err bitreich.org 70 i 963 Err bitreich.org 70 i 964 #define RBT_INIT(_name, _head) _name##_RBT_INIT(_head) Err bitreich.org 70 i 965 #define RBT_INSERT(_name, _head, _elm) _name##_RBT_INSERT(_head, _elm) Err bitreich.org 70 i 966 #define RBT_REMOVE(_name, _head, _elm) _name##_RBT_REMOVE(_head, _elm) Err bitreich.org 70 i 967 #define RBT_FIND(_name, _head, _key) _name##_RBT_FIND(_head, _key) Err bitreich.org 70 i 968 #define RBT_NFIND(_name, _head, _key) _name##_RBT_NFIND(_head, _key) Err bitreich.org 70 i 969 #define RBT_ROOT(_name, _head) _name##_RBT_ROOT(_head) Err bitreich.org 70 i 970 #define RBT_EMPTY(_name, _head) _name##_RBT_EMPTY(_head) Err bitreich.org 70 i 971 #define RBT_MIN(_name, _head) _name##_RBT_MIN(_head) Err bitreich.org 70 i 972 #define RBT_MAX(_name, _head) _name##_RBT_MAX(_head) Err bitreich.org 70 i 973 #define RBT_NEXT(_name, _elm) _name##_RBT_NEXT(_elm) Err bitreich.org 70 i 974 #define RBT_PREV(_name, _elm) _name##_RBT_PREV(_elm) Err bitreich.org 70 i 975 #define RBT_LEFT(_name, _elm) _name##_RBT_LEFT(_elm) Err bitreich.org 70 i 976 #define RBT_RIGHT(_name, _elm) _name##_RBT_RIGHT(_elm) Err bitreich.org 70 i 977 #define RBT_PARENT(_name, _elm) _name##_RBT_PARENT(_elm) Err bitreich.org 70 i 978 #define RBT_SET_LEFT(_name, _elm, _l) _name##_RBT_SET_LEFT(_elm, _l) Err bitreich.org 70 i 979 #define RBT_SET_RIGHT(_name, _elm, _r) _name##_RBT_SET_RIGHT(_elm, _r) Err bitreich.org 70 i 980 #define RBT_SET_PARENT(_name, _elm, _p) _name##_RBT_SET_PARENT(_elm, _p) Err bitreich.org 70 i 981 #define RBT_POISON(_name, _elm, _p) _name##_RBT_POISON(_elm, _p) Err bitreich.org 70 i 982 #define RBT_CHECK(_name, _elm, _p) _name##_RBT_CHECK(_elm, _p) Err bitreich.org 70 i 983 Err bitreich.org 70 i 984 #define RBT_FOREACH(_e, _name, _head) \ Err bitreich.org 70 i 985 for ((_e) = RBT_MIN(_name, (_head)); \ Err bitreich.org 70 i 986 (_e) != NULL; \ Err bitreich.org 70 i 987 (_e) = RBT_NEXT(_name, (_e))) Err bitreich.org 70 i 988 Err bitreich.org 70 i 989 #define RBT_FOREACH_SAFE(_e, _name, _head, _n) \ Err bitreich.org 70 i 990 for ((_e) = RBT_MIN(_name, (_head)); \ Err bitreich.org 70 i 991 (_e) != NULL && ((_n) = RBT_NEXT(_name, (_e)), 1); \ Err bitreich.org 70 i 992 (_e) = (_n)) Err bitreich.org 70 i 993 Err bitreich.org 70 i 994 #define RBT_FOREACH_REVERSE(_e, _name, _head) \ Err bitreich.org 70 i 995 for ((_e) = RBT_MAX(_name, (_head)); \ Err bitreich.org 70 i 996 (_e) != NULL; \ Err bitreich.org 70 i 997 (_e) = RBT_PREV(_name, (_e))) Err bitreich.org 70 i 998 Err bitreich.org 70 i 999 #define RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ Err bitreich.org 70 i 1000 for ((_e) = RBT_MAX(_name, (_head)); \ Err bitreich.org 70 i 1001 (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1); \ Err bitreich.org 70 i 1002 (_e) = (_n)) Err bitreich.org 70 i 1003 Err bitreich.org 70 i 1004 #endif /* _SYS_TREE_H_ */ Err bitreich.org 70 .