| Code Coverage: vinyl-cache/include/vtree.h |
| |
| 82217aa4fc7094b3610340078afaf78cd95a8ec9 |
| |
| 0 |
|
/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */ |
| 1 |
|
/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ |
| 2 |
|
|
| 3 |
|
/*- |
| 4 |
|
* SPDX-License-Identifier: BSD-2-Clause |
| 5 |
|
* |
| 6 |
|
* Copyright 2002 Niels Provos <provos@citi.umich.edu> |
| 7 |
|
* All rights reserved. |
| 8 |
|
* |
| 9 |
|
* Redistribution and use in source and binary forms, with or without |
| 10 |
|
* modification, are permitted provided that the following conditions |
| 11 |
|
* are met: |
| 12 |
|
* 1. Redistributions of source code must retain the above copyright |
| 13 |
|
* notice, this list of conditions and the following disclaimer. |
| 14 |
|
* 2. Redistributions in binary form must reproduce the above copyright |
| 15 |
|
* notice, this list of conditions and the following disclaimer in the |
| 16 |
|
* documentation and/or other materials provided with the distribution. |
| 17 |
|
* |
| 18 |
|
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| 19 |
|
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| 20 |
|
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| 21 |
|
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| 22 |
|
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| 23 |
|
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 24 |
|
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 25 |
|
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 26 |
|
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| 27 |
|
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 28 |
|
*/ |
| 29 |
|
|
| 30 |
|
#ifndef _VTREE_H_ |
| 31 |
|
#define _VTREE_H_ |
| 32 |
|
|
| 33 |
|
/* XXX |
| 34 |
|
* Enable -Wall with gcc -O2 |
| 35 |
|
*/ |
| 36 |
|
#pragma GCC diagnostic ignored "-Wstrict-aliasing" |
| 37 |
|
|
| 38 |
|
/* |
| 39 |
|
* This file defines data structures for different types of trees: |
| 40 |
|
* splay trees and rank-balanced trees. |
| 41 |
|
* |
| 42 |
|
* A splay tree is a self-organizing data structure. Every operation |
| 43 |
|
* on the tree causes a splay to happen. The splay moves the requested |
| 44 |
|
* node to the root of the tree and partly rebalances it. |
| 45 |
|
* |
| 46 |
|
* This has the benefit that request locality causes faster lookups as |
| 47 |
|
* the requested nodes move to the top of the tree. On the other hand, |
| 48 |
|
* every lookup causes memory writes. |
| 49 |
|
* |
| 50 |
|
* The Balance Theorem bounds the total access time for m operations |
| 51 |
|
* and n inserts on an initially empty tree as O((m + n)lg n). The |
| 52 |
|
* amortized cost for a sequence of m accesses to a splay tree is O(lg n); |
| 53 |
|
* |
| 54 |
|
* A rank-balanced tree is a binary search tree with an integer |
| 55 |
|
* rank-difference as an attribute of each pointer from parent to child. |
| 56 |
|
* The sum of the rank-differences on any path from a node down to null is |
| 57 |
|
* the same, and defines the rank of that node. The rank of the null node |
| 58 |
|
* is -1. |
| 59 |
|
* |
| 60 |
|
* Different additional conditions define different sorts of balanced trees, |
| 61 |
|
* including "red-black" and "AVL" trees. The set of conditions applied here |
| 62 |
|
* are the "weak-AVL" conditions of Haeupler, Sen and Tarjan presented in in |
| 63 |
|
* "Rank Balanced Trees", ACM Transactions on Algorithms Volume 11 Issue 4 June |
| 64 |
|
* 2015 Article No.: 30pp 1–26 https://doi.org/10.1145/2689412 (the HST paper): |
| 65 |
|
* - every rank-difference is 1 or 2. |
| 66 |
|
* - the rank of any leaf is 1. |
| 67 |
|
* |
| 68 |
|
* For historical reasons, rank differences that are even are associated |
| 69 |
|
* with the color red (Rank-Even-Difference), and the child that a red edge |
| 70 |
|
* points to is called a red child. |
| 71 |
|
* |
| 72 |
|
* Every operation on a rank-balanced tree is bounded as O(lg n). |
| 73 |
|
* The maximum height of a rank-balanced tree is 2lg (n+1). |
| 74 |
|
*/ |
| 75 |
|
|
| 76 |
|
#ifndef __CHERI__ |
| 77 |
|
# define __no_subobject_bounds /* */ |
| 78 |
4270 |
# define ptraddr_t uintptr_t |
| 79 |
|
#endif |
| 80 |
|
|
| 81 |
|
#define VSPLAY_HEAD(name, type) \ |
| 82 |
|
struct name { \ |
| 83 |
|
struct type *sph_root; /* root of the tree */ \ |
| 84 |
|
} |
| 85 |
|
|
| 86 |
|
#define VSPLAY_INITIALIZER(root) \ |
| 87 |
|
{ NULL } |
| 88 |
|
|
| 89 |
|
#define VSPLAY_INIT(root) do { \ |
| 90 |
|
(root)->sph_root = NULL; \ |
| 91 |
|
} while (/*CONSTCOND*/ 0) |
| 92 |
|
|
| 93 |
|
#define VSPLAY_ENTRY(type) \ |
| 94 |
|
struct { \ |
| 95 |
|
struct type *spe_left __no_subobject_bounds; /* left element */ \ |
| 96 |
|
struct type *spe_right __no_subobject_bounds; /* right element */ \ |
| 97 |
|
} |
| 98 |
|
|
| 99 |
|
#define VSPLAY_LEFT(elm, field) (elm)->field.spe_left |
| 100 |
|
#define VSPLAY_RIGHT(elm, field) (elm)->field.spe_right |
| 101 |
|
#define VSPLAY_ROOT(head) (head)->sph_root |
| 102 |
|
#define VSPLAY_EMPTY(head) (VSPLAY_ROOT(head) == NULL) |
| 103 |
|
|
| 104 |
|
/* VSPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold VSPLAY_{RIGHT,LEFT} */ |
| 105 |
|
#define VSPLAY_ROTATE_RIGHT(head, tmp, field) do { \ |
| 106 |
|
VSPLAY_LEFT((head)->sph_root, field) = VSPLAY_RIGHT(tmp, field); \ |
| 107 |
|
VSPLAY_RIGHT(tmp, field) = (head)->sph_root; \ |
| 108 |
|
(head)->sph_root = tmp; \ |
| 109 |
|
} while (/*CONSTCOND*/ 0) |
| 110 |
|
|
| 111 |
|
#define VSPLAY_ROTATE_LEFT(head, tmp, field) do { \ |
| 112 |
|
VSPLAY_RIGHT((head)->sph_root, field) = VSPLAY_LEFT(tmp, field); \ |
| 113 |
|
VSPLAY_LEFT(tmp, field) = (head)->sph_root; \ |
| 114 |
|
(head)->sph_root = tmp; \ |
| 115 |
|
} while (/*CONSTCOND*/ 0) |
| 116 |
|
|
| 117 |
|
#define VSPLAY_LINKLEFT(head, tmp, field) do { \ |
| 118 |
|
VSPLAY_LEFT(tmp, field) = (head)->sph_root; \ |
| 119 |
|
tmp = (head)->sph_root; \ |
| 120 |
|
(head)->sph_root = VSPLAY_LEFT((head)->sph_root, field); \ |
| 121 |
|
} while (/*CONSTCOND*/ 0) |
| 122 |
|
|
| 123 |
|
#define VSPLAY_LINKRIGHT(head, tmp, field) do { \ |
| 124 |
|
VSPLAY_RIGHT(tmp, field) = (head)->sph_root; \ |
| 125 |
|
tmp = (head)->sph_root; \ |
| 126 |
|
(head)->sph_root = VSPLAY_RIGHT((head)->sph_root, field); \ |
| 127 |
|
} while (/*CONSTCOND*/ 0) |
| 128 |
|
|
| 129 |
|
#define VSPLAY_ASSEMBLE(head, node, left, right, field) do { \ |
| 130 |
|
VSPLAY_RIGHT(left, field) = VSPLAY_LEFT((head)->sph_root, field); \ |
| 131 |
|
VSPLAY_LEFT(right, field) = VSPLAY_RIGHT((head)->sph_root, field);\ |
| 132 |
|
VSPLAY_LEFT((head)->sph_root, field) = VSPLAY_RIGHT(node, field); \ |
| 133 |
|
VSPLAY_RIGHT((head)->sph_root, field) = VSPLAY_LEFT(node, field); \ |
| 134 |
|
} while (/*CONSTCOND*/ 0) |
| 135 |
|
|
| 136 |
|
/* Generates prototypes and inline functions */ |
| 137 |
|
|
| 138 |
|
#define VSPLAY_PROTOTYPE(name, type, field, cmp) \ |
| 139 |
|
void name##_VSPLAY(struct name *, struct type *); \ |
| 140 |
|
void name##_VSPLAY_MINMAX(struct name *, int); \ |
| 141 |
|
struct type *name##_VSPLAY_INSERT(struct name *, struct type *); \ |
| 142 |
|
struct type *name##_VSPLAY_REMOVE(struct name *, struct type *); \ |
| 143 |
|
\ |
| 144 |
|
/* Finds the node with the same key as elm */ \ |
| 145 |
|
static v_unused_ __inline struct type * \ |
| 146 |
|
name##_VSPLAY_FIND(struct name *head, struct type *elm) \ |
| 147 |
|
{ \ |
| 148 |
|
if (VSPLAY_EMPTY(head)) \ |
| 149 |
|
return(NULL); \ |
| 150 |
|
name##_VSPLAY(head, elm); \ |
| 151 |
|
if ((cmp)(elm, (head)->sph_root) == 0) \ |
| 152 |
|
return (head->sph_root); \ |
| 153 |
|
return (NULL); \ |
| 154 |
|
} \ |
| 155 |
|
\ |
| 156 |
|
static v_unused_ __inline struct type * \ |
| 157 |
|
name##_VSPLAY_NEXT(struct name *head, struct type *elm) \ |
| 158 |
|
{ \ |
| 159 |
|
name##_VSPLAY(head, elm); \ |
| 160 |
|
if (VSPLAY_RIGHT(elm, field) != NULL) { \ |
| 161 |
|
elm = VSPLAY_RIGHT(elm, field); \ |
| 162 |
|
while (VSPLAY_LEFT(elm, field) != NULL) { \ |
| 163 |
|
elm = VSPLAY_LEFT(elm, field); \ |
| 164 |
|
} \ |
| 165 |
|
} else \ |
| 166 |
|
elm = NULL; \ |
| 167 |
|
return (elm); \ |
| 168 |
|
} \ |
| 169 |
|
\ |
| 170 |
|
static v_unused_ __inline struct type * \ |
| 171 |
|
name##_VSPLAY_MIN_MAX(struct name *head, int val) \ |
| 172 |
|
{ \ |
| 173 |
|
name##_VSPLAY_MINMAX(head, val); \ |
| 174 |
|
return (VSPLAY_ROOT(head)); \ |
| 175 |
|
} |
| 176 |
|
|
| 177 |
|
/* Main splay operation. |
| 178 |
|
* Moves node close to the key of elm to top |
| 179 |
|
*/ |
| 180 |
|
#define VSPLAY_GENERATE(name, type, field, cmp) \ |
| 181 |
|
struct type * \ |
| 182 |
|
name##_VSPLAY_INSERT(struct name *head, struct type *elm) \ |
| 183 |
|
{ \ |
| 184 |
|
if (VSPLAY_EMPTY(head)) { \ |
| 185 |
|
VSPLAY_LEFT(elm, field) = VSPLAY_RIGHT(elm, field) = NULL; \ |
| 186 |
|
} else { \ |
| 187 |
|
__typeof(cmp(NULL, NULL)) __comp; \ |
| 188 |
|
name##_VSPLAY(head, elm); \ |
| 189 |
|
__comp = (cmp)(elm, (head)->sph_root); \ |
| 190 |
|
if (__comp < 0) { \ |
| 191 |
|
VSPLAY_LEFT(elm, field) = VSPLAY_LEFT((head)->sph_root, field);\ |
| 192 |
|
VSPLAY_RIGHT(elm, field) = (head)->sph_root; \ |
| 193 |
|
VSPLAY_LEFT((head)->sph_root, field) = NULL; \ |
| 194 |
|
} else if (__comp > 0) { \ |
| 195 |
|
VSPLAY_RIGHT(elm, field) = VSPLAY_RIGHT((head)->sph_root, field);\ |
| 196 |
|
VSPLAY_LEFT(elm, field) = (head)->sph_root; \ |
| 197 |
|
VSPLAY_RIGHT((head)->sph_root, field) = NULL; \ |
| 198 |
|
} else \ |
| 199 |
|
return ((head)->sph_root); \ |
| 200 |
|
} \ |
| 201 |
|
(head)->sph_root = (elm); \ |
| 202 |
|
return (NULL); \ |
| 203 |
|
} \ |
| 204 |
|
\ |
| 205 |
|
struct type * \ |
| 206 |
|
name##_VSPLAY_REMOVE(struct name *head, struct type *elm) \ |
| 207 |
|
{ \ |
| 208 |
|
struct type *__tmp; \ |
| 209 |
|
if (VSPLAY_EMPTY(head)) \ |
| 210 |
|
return (NULL); \ |
| 211 |
|
name##_VSPLAY(head, elm); \ |
| 212 |
|
if ((cmp)(elm, (head)->sph_root) == 0) { \ |
| 213 |
|
if (VSPLAY_LEFT((head)->sph_root, field) == NULL) { \ |
| 214 |
|
(head)->sph_root = VSPLAY_RIGHT((head)->sph_root, field);\ |
| 215 |
|
} else { \ |
| 216 |
|
__tmp = VSPLAY_RIGHT((head)->sph_root, field); \ |
| 217 |
|
(head)->sph_root = VSPLAY_LEFT((head)->sph_root, field);\ |
| 218 |
|
name##_VSPLAY(head, elm); \ |
| 219 |
|
VSPLAY_RIGHT((head)->sph_root, field) = __tmp; \ |
| 220 |
|
} \ |
| 221 |
|
return (elm); \ |
| 222 |
|
} \ |
| 223 |
|
return (NULL); \ |
| 224 |
|
} \ |
| 225 |
|
\ |
| 226 |
|
void \ |
| 227 |
|
name##_VSPLAY(struct name *head, struct type *elm) \ |
| 228 |
|
{ \ |
| 229 |
|
struct type __node, *__left, *__right, *__tmp; \ |
| 230 |
|
__typeof(cmp(NULL, NULL)) __comp; \ |
| 231 |
|
\ |
| 232 |
|
VSPLAY_LEFT(&__node, field) = VSPLAY_RIGHT(&__node, field) = NULL;\ |
| 233 |
|
__left = __right = &__node; \ |
| 234 |
|
\ |
| 235 |
|
while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ |
| 236 |
|
if (__comp < 0) { \ |
| 237 |
|
__tmp = VSPLAY_LEFT((head)->sph_root, field); \ |
| 238 |
|
if (__tmp == NULL) \ |
| 239 |
|
break; \ |
| 240 |
|
if ((cmp)(elm, __tmp) < 0){ \ |
| 241 |
|
VSPLAY_ROTATE_RIGHT(head, __tmp, field); \ |
| 242 |
|
if (VSPLAY_LEFT((head)->sph_root, field) == NULL)\ |
| 243 |
|
break; \ |
| 244 |
|
} \ |
| 245 |
|
VSPLAY_LINKLEFT(head, __right, field); \ |
| 246 |
|
} else if (__comp > 0) { \ |
| 247 |
|
__tmp = VSPLAY_RIGHT((head)->sph_root, field); \ |
| 248 |
|
if (__tmp == NULL) \ |
| 249 |
|
break; \ |
| 250 |
|
if ((cmp)(elm, __tmp) > 0){ \ |
| 251 |
|
VSPLAY_ROTATE_LEFT(head, __tmp, field); \ |
| 252 |
|
if (VSPLAY_RIGHT((head)->sph_root, field) == NULL)\ |
| 253 |
|
break; \ |
| 254 |
|
} \ |
| 255 |
|
VSPLAY_LINKRIGHT(head, __left, field); \ |
| 256 |
|
} \ |
| 257 |
|
} \ |
| 258 |
|
VSPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ |
| 259 |
|
} \ |
| 260 |
|
\ |
| 261 |
|
/* Splay with either the minimum or the maximum element \ |
| 262 |
|
* Used to find minimum or maximum element in tree. \ |
| 263 |
|
*/ \ |
| 264 |
|
void name##_VSPLAY_MINMAX(struct name *head, int __comp) \ |
| 265 |
|
{ \ |
| 266 |
|
struct type __node, *__left, *__right, *__tmp; \ |
| 267 |
|
\ |
| 268 |
|
VSPLAY_LEFT(&__node, field) = VSPLAY_RIGHT(&__node, field) = NULL;\ |
| 269 |
|
__left = __right = &__node; \ |
| 270 |
|
\ |
| 271 |
|
while (1) { \ |
| 272 |
|
if (__comp < 0) { \ |
| 273 |
|
__tmp = VSPLAY_LEFT((head)->sph_root, field); \ |
| 274 |
|
if (__tmp == NULL) \ |
| 275 |
|
break; \ |
| 276 |
|
if (__comp < 0){ \ |
| 277 |
|
VSPLAY_ROTATE_RIGHT(head, __tmp, field); \ |
| 278 |
|
if (VSPLAY_LEFT((head)->sph_root, field) == NULL)\ |
| 279 |
|
break; \ |
| 280 |
|
} \ |
| 281 |
|
VSPLAY_LINKLEFT(head, __right, field); \ |
| 282 |
|
} else if (__comp > 0) { \ |
| 283 |
|
__tmp = VSPLAY_RIGHT((head)->sph_root, field); \ |
| 284 |
|
if (__tmp == NULL) \ |
| 285 |
|
break; \ |
| 286 |
|
if (__comp > 0) { \ |
| 287 |
|
VSPLAY_ROTATE_LEFT(head, __tmp, field); \ |
| 288 |
|
if (VSPLAY_RIGHT((head)->sph_root, field) == NULL)\ |
| 289 |
|
break; \ |
| 290 |
|
} \ |
| 291 |
|
VSPLAY_LINKRIGHT(head, __left, field); \ |
| 292 |
|
} \ |
| 293 |
|
} \ |
| 294 |
|
VSPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ |
| 295 |
|
} |
| 296 |
|
|
| 297 |
|
#define VSPLAY_NEGINF -1 |
| 298 |
|
#define VSPLAY_INF 1 |
| 299 |
|
|
| 300 |
|
#define VSPLAY_INSERT(name, x, y) name##_VSPLAY_INSERT(x, y) |
| 301 |
|
#define VSPLAY_REMOVE(name, x, y) name##_VSPLAY_REMOVE(x, y) |
| 302 |
|
#define VSPLAY_FIND(name, x, y) name##_VSPLAY_FIND(x, y) |
| 303 |
|
#define VSPLAY_NEXT(name, x, y) name##_VSPLAY_NEXT(x, y) |
| 304 |
|
#define VSPLAY_MIN(name, x) (VSPLAY_EMPTY(x) ? NULL \ |
| 305 |
|
: name##_VSPLAY_MIN_MAX(x, VSPLAY_NEGINF)) |
| 306 |
|
#define VSPLAY_MAX(name, x) (VSPLAY_EMPTY(x) ? NULL \ |
| 307 |
|
: name##_VSPLAY_MIN_MAX(x, VSPLAY_INF)) |
| 308 |
|
|
| 309 |
|
#define VSPLAY_FOREACH(x, name, head) \ |
| 310 |
|
for ((x) = VSPLAY_MIN(name, head); \ |
| 311 |
|
(x) != NULL; \ |
| 312 |
|
(x) = VSPLAY_NEXT(name, head, x)) |
| 313 |
|
|
| 314 |
|
/* Macros that define a rank-balanced tree */ |
| 315 |
|
#define VRBT_HEAD(name, type) \ |
| 316 |
|
struct name { \ |
| 317 |
|
struct type *rbh_root; /* root of the tree */ \ |
| 318 |
|
} |
| 319 |
|
|
| 320 |
|
#define VRBT_INITIALIZER(root) \ |
| 321 |
|
{ NULL } |
| 322 |
|
|
| 323 |
19563 |
#define VRBT_INIT(root) do { \ |
| 324 |
19563 |
(root)->rbh_root = NULL; \ |
| 325 |
19563 |
} while (/*CONSTCOND*/ 0) |
| 326 |
|
|
| 327 |
|
#define VRBT_ENTRY(type) \ |
| 328 |
|
struct { \ |
| 329 |
|
struct type *rbe_link[3] __no_subobject_bounds; \ |
| 330 |
|
} |
| 331 |
|
|
| 332 |
|
/* |
| 333 |
|
* With the expectation that any object of struct type has an |
| 334 |
|
* address that is a multiple of 4, and that therefore the |
| 335 |
|
* 2 least significant bits of a pointer to struct type are |
| 336 |
|
* always zero, this implementation sets those bits to indicate |
| 337 |
|
* that the left or right child of the tree node is "red". |
| 338 |
|
*/ |
| 339 |
88903719 |
#define _VRBT_LINK(elm, dir, field) (elm)->field.rbe_link[dir] |
| 340 |
23334 |
#define _VRBT_UP(elm, field) _VRBT_LINK(elm, 0, field) |
| 341 |
9910 |
#define _VRBT_L ((ptraddr_t)1) |
| 342 |
4874 |
#define _VRBT_R ((ptraddr_t)2) |
| 343 |
17444 |
#define _VRBT_LR ((ptraddr_t)3) |
| 344 |
21432 |
#define _VRBT_BITS(elm) ((ptraddr_t)elm) |
| 345 |
4865 |
#define _VRBT_BITSUP(elm, field) _VRBT_BITS(_VRBT_UP(elm, field)) |
| 346 |
22283 |
#define _VRBT_PTR_OP(elm, op, dir) ((__typeof(elm)) \ |
| 347 |
22283 |
((uintptr_t)(elm) op (dir))) |
| 348 |
10657 |
#define _VRBT_PTR(elm) _VRBT_PTR_OP((elm), &, ~_VRBT_LR) |
| 349 |
2 |
#define _VRBT_MOD_OR(elm, dir) ((elm) = _VRBT_PTR_OP((elm), |, (dir))) |
| 350 |
8301 |
#define _VRBT_MOD_XOR(elm, dir) ((elm) = _VRBT_PTR_OP((elm), ^, (dir))) |
| 351 |
|
|
| 352 |
7205 |
#define VRBT_PARENT(elm, field) _VRBT_PTR(_VRBT_UP(elm, field)) |
| 353 |
47078618 |
#define VRBT_LEFT(elm, field) _VRBT_LINK(elm, _VRBT_L, field) |
| 354 |
41792020 |
#define VRBT_RIGHT(elm, field) _VRBT_LINK(elm, _VRBT_R, field) |
| 355 |
11157197 |
#define VRBT_ROOT(head) (head)->rbh_root |
| 356 |
8326 |
#define VRBT_EMPTY(head) (VRBT_ROOT(head) == NULL) |
| 357 |
|
|
| 358 |
3236 |
#define VRBT_SET_PARENT(dst, src, field) do { \ |
| 359 |
3236 |
_VRBT_UP(dst, field) = (__typeof(src))((uintptr_t)src | \ |
| 360 |
3236 |
(ptraddr_t)(_VRBT_BITSUP(dst, field) & _VRBT_LR)); \ |
| 361 |
3236 |
} while (/*CONSTCOND*/ 0) |
| 362 |
|
|
| 363 |
5115 |
#define VRBT_SET(elm, parent, field) do { \ |
| 364 |
5115 |
_VRBT_UP(elm, field) = parent; \ |
| 365 |
5115 |
VRBT_LEFT(elm, field) = VRBT_RIGHT(elm, field) = NULL; \ |
| 366 |
5115 |
} while (/*CONSTCOND*/ 0) |
| 367 |
|
|
| 368 |
|
/* |
| 369 |
|
* Either VRBT_AUGMENT or VRBT_AUGMENT_CHECK is invoked in a loop at the root of |
| 370 |
|
* every modified subtree, from the bottom up to the root, to update augmented |
| 371 |
|
* node data. VRBT_AUGMENT_CHECK returns true only when the update changes the |
| 372 |
|
* node data, so that updating can be stopped short of the root when it returns |
| 373 |
|
* false. |
| 374 |
|
*/ |
| 375 |
|
#ifndef VRBT_AUGMENT_CHECK |
| 376 |
|
#ifndef VRBT_AUGMENT |
| 377 |
14786 |
#define VRBT_AUGMENT_CHECK(x) 0 |
| 378 |
|
#else |
| 379 |
|
#define VRBT_AUGMENT_CHECK(x) (VRBT_AUGMENT(x), 1) |
| 380 |
|
#endif |
| 381 |
|
#endif |
| 382 |
|
|
| 383 |
|
#define VRBT_UPDATE_AUGMENT(elm, field) do { \ |
| 384 |
|
__typeof(elm) rb_update_tmp = (elm); \ |
| 385 |
|
while (VRBT_AUGMENT_CHECK(rb_update_tmp) && \ |
| 386 |
|
(rb_update_tmp = VRBT_PARENT(rb_update_tmp, field)) != NULL) \ |
| 387 |
|
; \ |
| 388 |
|
} while (0) |
| 389 |
|
|
| 390 |
3194 |
#define VRBT_SWAP_CHILD(head, par, out, in, field) do { \ |
| 391 |
3194 |
if (par == NULL) \ |
| 392 |
3194 |
VRBT_ROOT(head) = (in); \ |
| 393 |
3194 |
else if ((out) == VRBT_LEFT(par, field)) \ |
| 394 |
2386 |
VRBT_LEFT(par, field) = (in); \ |
| 395 |
2386 |
else \ |
| 396 |
2386 |
VRBT_RIGHT(par, field) = (in); \ |
| 397 |
3194 |
} while (/*CONSTCOND*/ 0) |
| 398 |
|
|
| 399 |
|
/* |
| 400 |
|
* VRBT_ROTATE macro partially restructures the tree to improve balance. In the |
| 401 |
|
* case when dir is _VRBT_L, tmp is a right child of elm. After rotation, elm |
| 402 |
|
* is a left child of tmp, and the subtree that represented the items between |
| 403 |
|
* them, which formerly hung to the left of tmp now hangs to the right of elm. |
| 404 |
|
* The parent-child relationship between elm and its former parent is not |
| 405 |
|
* changed; where this macro once updated those fields, that is now left to the |
| 406 |
|
* caller of VRBT_ROTATE to clean up, so that a pair of rotations does not twice |
| 407 |
|
* update the same pair of pointer fields with distinct values. |
| 408 |
|
*/ |
| 409 |
2446 |
#define VRBT_ROTATE(elm, tmp, dir, field) do { \ |
| 410 |
2446 |
if ((_VRBT_LINK(elm, dir ^ _VRBT_LR, field) = \ |
| 411 |
2446 |
_VRBT_LINK(tmp, dir, field)) != NULL) \ |
| 412 |
2446 |
VRBT_SET_PARENT(_VRBT_LINK(tmp, dir, field), elm, field); \ |
| 413 |
2446 |
_VRBT_LINK(tmp, dir, field) = (elm); \ |
| 414 |
2446 |
VRBT_SET_PARENT(elm, tmp, field); \ |
| 415 |
2446 |
} while (/*CONSTCOND*/ 0) |
| 416 |
|
|
| 417 |
|
/* Generates prototypes and inline functions */ |
| 418 |
|
#define VRBT_PROTOTYPE(name, type, field, cmp) \ |
| 419 |
|
VRBT_PROTOTYPE_INTERNAL(name, type, field, cmp,) |
| 420 |
|
#define VRBT_PROTOTYPE_STATIC(name, type, field, cmp) \ |
| 421 |
|
VRBT_PROTOTYPE_INTERNAL(name, type, field, cmp, v_unused_ static) |
| 422 |
|
#define VRBT_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ |
| 423 |
|
VRBT_PROTOTYPE_RANK(name, type, attr) \ |
| 424 |
|
VRBT_PROTOTYPE_INSERT_COLOR(name, type, attr); \ |
| 425 |
|
VRBT_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ |
| 426 |
|
VRBT_PROTOTYPE_INSERT_FINISH(name, type, attr); \ |
| 427 |
|
VRBT_PROTOTYPE_INSERT(name, type, attr); \ |
| 428 |
|
VRBT_PROTOTYPE_REMOVE(name, type, attr); \ |
| 429 |
|
VRBT_PROTOTYPE_FIND(name, type, attr); \ |
| 430 |
|
VRBT_PROTOTYPE_NFIND(name, type, attr); \ |
| 431 |
|
VRBT_PROTOTYPE_NEXT(name, type, attr); \ |
| 432 |
|
VRBT_PROTOTYPE_INSERT_NEXT(name, type, attr); \ |
| 433 |
|
VRBT_PROTOTYPE_PREV(name, type, attr); \ |
| 434 |
|
VRBT_PROTOTYPE_INSERT_PREV(name, type, attr); \ |
| 435 |
|
VRBT_PROTOTYPE_MINMAX(name, type, attr); \ |
| 436 |
|
VRBT_PROTOTYPE_REINSERT(name, type, attr); |
| 437 |
|
#ifdef _VRBT_DIAGNOSTIC |
| 438 |
|
#define VRBT_PROTOTYPE_RANK(name, type, attr) \ |
| 439 |
|
attr int name##_VRBT_RANK(struct type *); |
| 440 |
|
#else |
| 441 |
|
#define VRBT_PROTOTYPE_RANK(name, type, attr) |
| 442 |
|
#endif |
| 443 |
|
#define VRBT_PROTOTYPE_INSERT_COLOR(name, type, attr) \ |
| 444 |
|
attr struct type *name##_VRBT_INSERT_COLOR(struct name *, \ |
| 445 |
|
struct type *, struct type *) |
| 446 |
|
#define VRBT_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ |
| 447 |
|
attr struct type *name##_VRBT_REMOVE_COLOR(struct name *, \ |
| 448 |
|
struct type *, struct type *) |
| 449 |
|
#define VRBT_PROTOTYPE_REMOVE(name, type, attr) \ |
| 450 |
|
attr struct type *name##_VRBT_REMOVE(struct name *, struct type *) |
| 451 |
|
#define VRBT_PROTOTYPE_INSERT_FINISH(name, type, attr) \ |
| 452 |
|
attr struct type *name##_VRBT_INSERT_FINISH(struct name *, \ |
| 453 |
|
struct type *, struct type **, struct type *) |
| 454 |
|
#define VRBT_PROTOTYPE_INSERT(name, type, attr) \ |
| 455 |
|
attr struct type *name##_VRBT_INSERT(struct name *, struct type *) |
| 456 |
|
#define VRBT_PROTOTYPE_FIND(name, type, attr) \ |
| 457 |
|
attr struct type *name##_VRBT_FIND(const struct name *, const struct type *) |
| 458 |
|
#define VRBT_PROTOTYPE_NFIND(name, type, attr) \ |
| 459 |
|
attr struct type *name##_VRBT_NFIND(const struct name *, const struct type *) |
| 460 |
|
#define VRBT_PROTOTYPE_NEXT(name, type, attr) \ |
| 461 |
|
attr struct type *name##_VRBT_NEXT(struct type *) |
| 462 |
|
#define VRBT_PROTOTYPE_INSERT_NEXT(name, type, attr) \ |
| 463 |
|
attr struct type *name##_VRBT_INSERT_NEXT(struct name *, \ |
| 464 |
|
struct type *, struct type *) |
| 465 |
|
#define VRBT_PROTOTYPE_PREV(name, type, attr) \ |
| 466 |
|
attr struct type *name##_VRBT_PREV(struct type *) |
| 467 |
|
#define VRBT_PROTOTYPE_INSERT_PREV(name, type, attr) \ |
| 468 |
|
attr struct type *name##_VRBT_INSERT_PREV(struct name *, \ |
| 469 |
|
struct type *, struct type *) |
| 470 |
|
#define VRBT_PROTOTYPE_MINMAX(name, type, attr) \ |
| 471 |
|
attr struct type *name##_VRBT_MINMAX(const struct name *, int) |
| 472 |
|
#define VRBT_PROTOTYPE_REINSERT(name, type, attr) \ |
| 473 |
|
attr struct type *name##_VRBT_REINSERT(struct name *, struct type *) |
| 474 |
|
|
| 475 |
|
/* Main rb operation. |
| 476 |
|
* Moves node close to the key of elm to top |
| 477 |
|
*/ |
| 478 |
|
#define VRBT_GENERATE(name, type, field, cmp) \ |
| 479 |
|
VRBT_GENERATE_INTERNAL(name, type, field, cmp,) |
| 480 |
|
#define VRBT_GENERATE_STATIC(name, type, field, cmp) \ |
| 481 |
|
VRBT_GENERATE_INTERNAL(name, type, field, cmp, v_unused_ static) |
| 482 |
|
#define VRBT_GENERATE_INTERNAL(name, type, field, cmp, attr) \ |
| 483 |
|
VRBT_GENERATE_RANK(name, type, field, attr) \ |
| 484 |
|
VRBT_GENERATE_INSERT_COLOR(name, type, field, attr) \ |
| 485 |
|
VRBT_GENERATE_REMOVE_COLOR(name, type, field, attr) \ |
| 486 |
|
VRBT_GENERATE_INSERT_FINISH(name, type, field, attr) \ |
| 487 |
|
VRBT_GENERATE_INSERT(name, type, field, cmp, attr) \ |
| 488 |
|
VRBT_GENERATE_REMOVE(name, type, field, attr) \ |
| 489 |
|
VRBT_GENERATE_FIND(name, type, field, cmp, attr) \ |
| 490 |
|
VRBT_GENERATE_NFIND(name, type, field, cmp, attr) \ |
| 491 |
|
VRBT_GENERATE_NEXT(name, type, field, attr) \ |
| 492 |
|
VRBT_GENERATE_INSERT_NEXT(name, type, field, cmp, attr) \ |
| 493 |
|
VRBT_GENERATE_PREV(name, type, field, attr) \ |
| 494 |
|
VRBT_GENERATE_INSERT_PREV(name, type, field, cmp, attr) \ |
| 495 |
|
VRBT_GENERATE_MINMAX(name, type, field, attr) \ |
| 496 |
|
VRBT_GENERATE_REINSERT(name, type, field, cmp, attr) |
| 497 |
|
|
| 498 |
|
#ifdef _VRBT_DIAGNOSTIC |
| 499 |
|
#ifndef VRBT_AUGMENT |
| 500 |
|
#define _VRBT_AUGMENT_VERIFY(x) VRBT_AUGMENT_CHECK(x) |
| 501 |
|
#else |
| 502 |
|
#define _VRBT_AUGMENT_VERIFY(x) 0 |
| 503 |
|
#endif |
| 504 |
|
#define VRBT_GENERATE_RANK(name, type, field, attr) \ |
| 505 |
|
/* \ |
| 506 |
|
* Return the rank of the subtree rooted at elm, or -1 if the subtree \ |
| 507 |
|
* is not rank-balanced, or has inconsistent augmentation data. |
| 508 |
|
*/ \ |
| 509 |
|
attr int \ |
| 510 |
|
name##_VRBT_RANK(struct type *elm) \ |
| 511 |
|
{ \ |
| 512 |
|
struct type *left, *right, *up; \ |
| 513 |
|
int left_rank, right_rank; \ |
| 514 |
|
\ |
| 515 |
|
if (elm == NULL) \ |
| 516 |
|
return (0); \ |
| 517 |
|
up = _VRBT_UP(elm, field); \ |
| 518 |
|
left = VRBT_LEFT(elm, field); \ |
| 519 |
|
left_rank = ((_VRBT_BITS(up) & _VRBT_L) ? 2 : 1) + \ |
| 520 |
|
name##_VRBT_RANK(left); \ |
| 521 |
|
right = VRBT_RIGHT(elm, field); \ |
| 522 |
|
right_rank = ((_VRBT_BITS(up) & _VRBT_R) ? 2 : 1) + \ |
| 523 |
|
name##_VRBT_RANK(right); \ |
| 524 |
|
if (left_rank != right_rank || \ |
| 525 |
|
(left_rank == 2 && left == NULL && right == NULL) || \ |
| 526 |
|
_VRBT_AUGMENT_VERIFY(elm)) \ |
| 527 |
|
return (-1); \ |
| 528 |
|
return (left_rank); \ |
| 529 |
|
} |
| 530 |
|
#else |
| 531 |
|
#define VRBT_GENERATE_RANK(name, type, field, attr) |
| 532 |
|
#endif |
| 533 |
|
|
| 534 |
|
#define VRBT_GENERATE_INSERT_COLOR(name, type, field, attr) \ |
| 535 |
|
attr struct type * \ |
| 536 |
|
name##_VRBT_INSERT_COLOR(struct name *head, \ |
| 537 |
3297 |
struct type *parent, struct type *elm) \ |
| 538 |
3297 |
{ \ |
| 539 |
3297 |
/* \ |
| 540 |
3297 |
* Initially, elm is a leaf. Either its parent was previously \ |
| 541 |
3297 |
* a leaf, with two black null children, or an interior node \ |
| 542 |
3297 |
* with a black non-null child and a red null child. The \ |
| 543 |
3297 |
* balance criterion "the rank of any leaf is 1" precludes the \ |
| 544 |
3297 |
* possibility of two red null children for the initial parent. \ |
| 545 |
3297 |
* So the first loop iteration cannot lead to accessing an \ |
| 546 |
3297 |
* uninitialized 'child', and a later iteration can only happen \ |
| 547 |
3297 |
* when a value has been assigned to 'child' in the previous \ |
| 548 |
3297 |
* one. \ |
| 549 |
3297 |
*/ \ |
| 550 |
3297 |
struct type *child = NULL, *child_up, *gpar; \ |
| 551 |
3297 |
ptraddr_t elmdir, sibdir; \ |
| 552 |
3297 |
\ |
| 553 |
7159 |
do { \ |
| 554 |
7159 |
/* the rank of the tree rooted at elm grew */ \ |
| 555 |
7159 |
gpar = _VRBT_UP(parent, field); \ |
| 556 |
7159 |
elmdir = VRBT_RIGHT(parent, field) == elm ? _VRBT_R : _VRBT_L; \ |
| 557 |
7159 |
if (_VRBT_BITS(gpar) & elmdir) { \ |
| 558 |
505 |
/* shorten the parent-elm edge to rebalance */ \ |
| 559 |
505 |
_VRBT_MOD_XOR(_VRBT_UP(parent, field), elmdir); \ |
| 560 |
505 |
return (NULL); \ |
| 561 |
505 |
} \ |
| 562 |
7159 |
sibdir = elmdir ^ _VRBT_LR; \ |
| 563 |
6654 |
/* the other edge must change length */ \ |
| 564 |
6654 |
_VRBT_MOD_XOR(_VRBT_UP(parent, field), sibdir); \ |
| 565 |
6654 |
if ((_VRBT_BITS(gpar) & _VRBT_LR) == 0) { \ |
| 566 |
5025 |
/* both edges now short, retry from parent */ \ |
| 567 |
5025 |
child = elm; \ |
| 568 |
5025 |
elm = parent; \ |
| 569 |
5025 |
continue; \ |
| 570 |
5025 |
} \ |
| 571 |
6654 |
_VRBT_UP(parent, field) = gpar = _VRBT_PTR(gpar); \ |
| 572 |
1629 |
if (_VRBT_BITSUP(elm, field) & elmdir) { \ |
| 573 |
796 |
/* \ |
| 574 |
796 |
* Exactly one of the edges descending from elm \ |
| 575 |
796 |
* is long. The long one is in the same \ |
| 576 |
796 |
* direction as the edge from parent to elm, \ |
| 577 |
796 |
* so change that by rotation. The edge from \ |
| 578 |
796 |
* parent to z was shortened above. Shorten \ |
| 579 |
796 |
* the long edge down from elm, and adjust \ |
| 580 |
796 |
* other edge lengths based on the downward \ |
| 581 |
796 |
* edges from 'child'. \ |
| 582 |
796 |
* \ |
| 583 |
796 |
* par par \ |
| 584 |
796 |
* ╱ ╲ ╱ ╲ \ |
| 585 |
796 |
* elm z ╱ z \ |
| 586 |
796 |
* ╱ ╲ child \ |
| 587 |
796 |
* ╱ child ╱ ╲ \ |
| 588 |
796 |
* ╱ ╱ ╲ elm ╲ \ |
| 589 |
796 |
* w ╱ ╲ ╱ ╲ y \ |
| 590 |
796 |
* x y w ╲ \ |
| 591 |
796 |
* x \ |
| 592 |
796 |
*/ \ |
| 593 |
796 |
VRBT_ROTATE(elm, child, elmdir, field); \ |
| 594 |
796 |
child_up = _VRBT_UP(child, field); \ |
| 595 |
796 |
if (_VRBT_BITS(child_up) & sibdir) \ |
| 596 |
796 |
_VRBT_MOD_XOR(_VRBT_UP(parent, field), \ |
| 597 |
796 |
elmdir); \ |
| 598 |
796 |
if (_VRBT_BITS(child_up) & elmdir) \ |
| 599 |
796 |
_VRBT_MOD_XOR(_VRBT_UP(elm, field), \ |
| 600 |
796 |
_VRBT_LR); \ |
| 601 |
796 |
else \ |
| 602 |
796 |
_VRBT_MOD_XOR(_VRBT_UP(elm, field), \ |
| 603 |
796 |
elmdir); \ |
| 604 |
796 |
/* if child is a leaf, don't augment elm, \ |
| 605 |
796 |
* since it is restored to be a leaf again. */ \ |
| 606 |
796 |
if ((_VRBT_BITS(child_up) & _VRBT_LR) == 0) \ |
| 607 |
796 |
elm = child; \ |
| 608 |
796 |
} else \ |
| 609 |
1629 |
child = elm; \ |
| 610 |
1629 |
\ |
| 611 |
1629 |
/* \ |
| 612 |
1629 |
* The long edge descending from 'child' points back \ |
| 613 |
1629 |
* in the direction of 'parent'. Rotate to make \ |
| 614 |
1629 |
* 'parent' a child of 'child', then make both edges \ |
| 615 |
1629 |
* of 'child' short to rebalance. \ |
| 616 |
1629 |
* \ |
| 617 |
1629 |
* par child \ |
| 618 |
1629 |
* ╱ ╲ ╱ ╲ \ |
| 619 |
1629 |
* ╱ z x par \ |
| 620 |
1629 |
* child ╱ ╲ \ |
| 621 |
1629 |
* ╱ ╲ ╱ z \ |
| 622 |
1629 |
* x ╲ y \ |
| 623 |
1629 |
* y \ |
| 624 |
1629 |
*/ \ |
| 625 |
1629 |
VRBT_ROTATE(parent, child, sibdir, field); \ |
| 626 |
1629 |
_VRBT_UP(child, field) = gpar; \ |
| 627 |
1629 |
VRBT_SWAP_CHILD(head, gpar, parent, child, field); \ |
| 628 |
1629 |
/* \ |
| 629 |
1629 |
* Elements rotated down have new, smaller subtrees, \ |
| 630 |
1629 |
* so update augmentation for them. \ |
| 631 |
1629 |
*/ \ |
| 632 |
1629 |
if (elm != child) \ |
| 633 |
1629 |
(void)VRBT_AUGMENT_CHECK(elm); \ |
| 634 |
1629 |
(void)VRBT_AUGMENT_CHECK(parent); \ |
| 635 |
1629 |
return (child); \ |
| 636 |
6654 |
} while ((parent = gpar) != NULL); \ |
| 637 |
3297 |
return (NULL); \ |
| 638 |
3297 |
} |
| 639 |
|
|
| 640 |
|
#ifndef VRBT_STRICT_HST |
| 641 |
|
/* |
| 642 |
|
* In REMOVE_COLOR, the HST paper, in figure 3, in the single-rotate case, has |
| 643 |
|
* 'parent' with one higher rank, and then reduces its rank if 'parent' has |
| 644 |
|
* become a leaf. This implementation always has the parent in its new position |
| 645 |
|
* with lower rank, to avoid the leaf check. Define VRBT_STRICT_HST to 1 to get |
| 646 |
|
* the behavior that HST describes. |
| 647 |
|
*/ |
| 648 |
30 |
#define VRBT_STRICT_HST 0 |
| 649 |
|
#endif |
| 650 |
|
|
| 651 |
|
#define VRBT_GENERATE_REMOVE_COLOR(name, type, field, attr) \ |
| 652 |
|
attr struct type * \ |
| 653 |
|
name##_VRBT_REMOVE_COLOR(struct name *head, \ |
| 654 |
973 |
struct type *parent, struct type *elm) \ |
| 655 |
973 |
{ \ |
| 656 |
973 |
struct type *gpar, *sib, *up; \ |
| 657 |
973 |
ptraddr_t elmdir, sibdir; \ |
| 658 |
973 |
\ |
| 659 |
973 |
if (VRBT_RIGHT(parent, field) == elm && \ |
| 660 |
973 |
VRBT_LEFT(parent, field) == elm) { \ |
| 661 |
778 |
/* Deleting a leaf that is an only-child creates a \ |
| 662 |
778 |
* rank-2 leaf. Demote that leaf. */ \ |
| 663 |
778 |
_VRBT_UP(parent, field) = _VRBT_PTR(_VRBT_UP(parent, field)); \ |
| 664 |
778 |
elm = parent; \ |
| 665 |
778 |
if ((parent = _VRBT_UP(elm, field)) == NULL) \ |
| 666 |
778 |
return (NULL); \ |
| 667 |
778 |
} \ |
| 668 |
973 |
do { \ |
| 669 |
233 |
/* the rank of the tree rooted at elm shrank */ \ |
| 670 |
233 |
gpar = _VRBT_UP(parent, field); \ |
| 671 |
233 |
elmdir = VRBT_RIGHT(parent, field) == elm ? _VRBT_R : _VRBT_L; \ |
| 672 |
233 |
_VRBT_MOD_XOR(gpar, elmdir); \ |
| 673 |
233 |
if (_VRBT_BITS(gpar) & elmdir) { \ |
| 674 |
177 |
/* lengthen the parent-elm edge to rebalance */ \ |
| 675 |
177 |
_VRBT_UP(parent, field) = gpar; \ |
| 676 |
177 |
return (NULL); \ |
| 677 |
177 |
} \ |
| 678 |
233 |
if (_VRBT_BITS(gpar) & _VRBT_LR) { \ |
| 679 |
32 |
/* shorten other edge, retry from parent */ \ |
| 680 |
32 |
_VRBT_MOD_XOR(gpar, _VRBT_LR); \ |
| 681 |
32 |
_VRBT_UP(parent, field) = gpar; \ |
| 682 |
32 |
gpar = _VRBT_PTR(gpar); \ |
| 683 |
32 |
continue; \ |
| 684 |
32 |
} \ |
| 685 |
56 |
sibdir = elmdir ^ _VRBT_LR; \ |
| 686 |
24 |
sib = _VRBT_LINK(parent, sibdir, field); \ |
| 687 |
24 |
up = _VRBT_UP(sib, field); \ |
| 688 |
24 |
_VRBT_MOD_XOR(up, _VRBT_LR); \ |
| 689 |
24 |
if ((_VRBT_BITS(up) & _VRBT_LR) == 0) { \ |
| 690 |
5 |
/* shorten edges descending from sib, retry */ \ |
| 691 |
5 |
_VRBT_UP(sib, field) = up; \ |
| 692 |
5 |
continue; \ |
| 693 |
5 |
} \ |
| 694 |
24 |
if ((_VRBT_BITS(up) & sibdir) == 0) { \ |
| 695 |
2 |
/* \ |
| 696 |
2 |
* The edge descending from 'sib' away from \ |
| 697 |
2 |
* 'parent' is long. The short edge descending \ |
| 698 |
2 |
* from 'sib' toward 'parent' points to 'elm*' \ |
| 699 |
2 |
* Rotate to make 'sib' a child of 'elm*' \ |
| 700 |
2 |
* then adjust the lengths of the edges \ |
| 701 |
2 |
* descending from 'sib' and 'elm*'. \ |
| 702 |
2 |
* \ |
| 703 |
2 |
* par par \ |
| 704 |
2 |
* ╱ ╲ ╱ ╲ \ |
| 705 |
2 |
* ╱ sib elm ╲ \ |
| 706 |
2 |
* ╱ / ╲ elm* \ |
| 707 |
2 |
* elm elm* ╲ ╱ ╲ \ |
| 708 |
2 |
* ╱ ╲ ╲ ╱ ╲ \ |
| 709 |
2 |
* ╱ ╲ z ╱ ╲ \ |
| 710 |
2 |
* x y x sib \ |
| 711 |
2 |
* ╱ ╲ \ |
| 712 |
2 |
* ╱ z \ |
| 713 |
2 |
* y \ |
| 714 |
2 |
*/ \ |
| 715 |
2 |
elm = _VRBT_LINK(sib, elmdir, field); \ |
| 716 |
2 |
/* elm is a 1-child. First rotate at elm. */ \ |
| 717 |
2 |
VRBT_ROTATE(sib, elm, sibdir, field); \ |
| 718 |
2 |
up = _VRBT_UP(elm, field); \ |
| 719 |
2 |
_VRBT_MOD_XOR(_VRBT_UP(parent, field), \ |
| 720 |
2 |
(_VRBT_BITS(up) & elmdir) ? _VRBT_LR : elmdir); \ |
| 721 |
2 |
_VRBT_MOD_XOR(_VRBT_UP(sib, field), \ |
| 722 |
2 |
(_VRBT_BITS(up) & sibdir) ? _VRBT_LR : sibdir); \ |
| 723 |
2 |
_VRBT_MOD_OR(_VRBT_UP(elm, field), _VRBT_LR); \ |
| 724 |
17 |
} else { \ |
| 725 |
17 |
if ((_VRBT_BITS(up) & elmdir) == 0 && \ |
| 726 |
17 |
VRBT_STRICT_HST && elm != NULL) { \ |
| 727 |
0 |
/* if parent does not become a leaf, \ |
| 728 |
0 |
do not demote parent yet. */ \ |
| 729 |
0 |
_VRBT_MOD_XOR(_VRBT_UP(parent, field), \ |
| 730 |
0 |
sibdir); \ |
| 731 |
0 |
_VRBT_MOD_XOR(_VRBT_UP(sib, field), \ |
| 732 |
0 |
_VRBT_LR); \ |
| 733 |
17 |
} else if ((_VRBT_BITS(up) & elmdir) == 0) { \ |
| 734 |
13 |
/* demote parent. */ \ |
| 735 |
13 |
_VRBT_MOD_XOR(_VRBT_UP(parent, field), \ |
| 736 |
13 |
elmdir); \ |
| 737 |
13 |
_VRBT_MOD_XOR(_VRBT_UP(sib, field), \ |
| 738 |
13 |
sibdir); \ |
| 739 |
13 |
} else \ |
| 740 |
17 |
_VRBT_MOD_XOR(_VRBT_UP(sib, field), \ |
| 741 |
17 |
sibdir); \ |
| 742 |
17 |
elm = sib; \ |
| 743 |
17 |
} \ |
| 744 |
19 |
\ |
| 745 |
19 |
/* \ |
| 746 |
19 |
* The edge descending from 'elm' away from 'parent' \ |
| 747 |
19 |
* is short. Rotate to make 'parent' a child of 'elm', \ |
| 748 |
19 |
* then lengthen the short edges descending from \ |
| 749 |
19 |
* 'parent' and 'elm' to rebalance. \ |
| 750 |
19 |
* \ |
| 751 |
19 |
* par elm \ |
| 752 |
19 |
* ╱ ╲ ╱ ╲ \ |
| 753 |
19 |
* e ╲ ╱ ╲ \ |
| 754 |
19 |
* elm ╱ ╲ \ |
| 755 |
19 |
* ╱ ╲ par s \ |
| 756 |
19 |
* ╱ ╲ ╱ ╲ \ |
| 757 |
19 |
* ╱ ╲ e ╲ \ |
| 758 |
19 |
* x s x \ |
| 759 |
19 |
*/ \ |
| 760 |
19 |
VRBT_ROTATE(parent, elm, elmdir, field); \ |
| 761 |
19 |
VRBT_SET_PARENT(elm, gpar, field); \ |
| 762 |
19 |
VRBT_SWAP_CHILD(head, gpar, parent, elm, field); \ |
| 763 |
19 |
/* \ |
| 764 |
19 |
* An element rotated down, but not into the search \ |
| 765 |
19 |
* path has a new, smaller subtree, so update \ |
| 766 |
19 |
* augmentation for it. \ |
| 767 |
19 |
*/ \ |
| 768 |
19 |
if (sib != elm) \ |
| 769 |
19 |
(void)VRBT_AUGMENT_CHECK(sib); \ |
| 770 |
19 |
return (parent); \ |
| 771 |
37 |
} while (elm = parent, (parent = gpar) != NULL); \ |
| 772 |
224 |
return (NULL); \ |
| 773 |
224 |
} |
| 774 |
|
|
| 775 |
6088 |
#define _VRBT_AUGMENT_WALK(elm, match, field) \ |
| 776 |
6088 |
do { \ |
| 777 |
6088 |
if (match == elm) \ |
| 778 |
6088 |
match = NULL; \ |
| 779 |
6088 |
} while (VRBT_AUGMENT_CHECK(elm) && \ |
| 780 |
6088 |
(elm = VRBT_PARENT(elm, field)) != NULL) |
| 781 |
|
|
| 782 |
|
#define VRBT_GENERATE_REMOVE(name, type, field, attr) \ |
| 783 |
|
attr struct type * \ |
| 784 |
1546 |
name##_VRBT_REMOVE(struct name *head, struct type *out) \ |
| 785 |
1546 |
{ \ |
| 786 |
1546 |
struct type *child = NULL, *in, *opar, *parent; \ |
| 787 |
1546 |
\ |
| 788 |
1546 |
child = VRBT_LEFT(out, field); \ |
| 789 |
1546 |
in = VRBT_RIGHT(out, field); \ |
| 790 |
1546 |
opar = _VRBT_UP(out, field); \ |
| 791 |
1546 |
if (in == NULL || child == NULL) { \ |
| 792 |
1464 |
in = child = (in == NULL ? child : in); \ |
| 793 |
1464 |
parent = opar = _VRBT_PTR(opar); \ |
| 794 |
1464 |
} else { \ |
| 795 |
82 |
parent = in; \ |
| 796 |
82 |
while (VRBT_LEFT(in, field)) \ |
| 797 |
82 |
in = VRBT_LEFT(in, field); \ |
| 798 |
82 |
VRBT_SET_PARENT(child, in, field); \ |
| 799 |
82 |
VRBT_LEFT(in, field) = child; \ |
| 800 |
82 |
child = VRBT_RIGHT(in, field); \ |
| 801 |
82 |
if (parent != in) { \ |
| 802 |
23 |
VRBT_SET_PARENT(parent, in, field); \ |
| 803 |
23 |
VRBT_RIGHT(in, field) = parent; \ |
| 804 |
23 |
parent = VRBT_PARENT(in, field); \ |
| 805 |
23 |
VRBT_LEFT(parent, field) = child; \ |
| 806 |
23 |
} \ |
| 807 |
82 |
_VRBT_UP(in, field) = opar; \ |
| 808 |
82 |
opar = _VRBT_PTR(opar); \ |
| 809 |
82 |
} \ |
| 810 |
1546 |
VRBT_SWAP_CHILD(head, opar, out, in, field); \ |
| 811 |
1546 |
if (child != NULL) \ |
| 812 |
1546 |
_VRBT_UP(child, field) = parent; \ |
| 813 |
1546 |
if (parent != NULL) { \ |
| 814 |
973 |
opar = name##_VRBT_REMOVE_COLOR(head, parent, child); \ |
| 815 |
973 |
/* if rotation has made 'parent' the root of the same \ |
| 816 |
973 |
* subtree as before, don't re-augment it. */ \ |
| 817 |
973 |
if (parent == in && VRBT_LEFT(parent, field) == NULL) { \ |
| 818 |
3 |
opar = NULL; \ |
| 819 |
3 |
parent = VRBT_PARENT(parent, field); \ |
| 820 |
3 |
} \ |
| 821 |
973 |
_VRBT_AUGMENT_WALK(parent, opar, field); \ |
| 822 |
973 |
if (opar != NULL) { \ |
| 823 |
1 |
/* \ |
| 824 |
1 |
* Elements rotated into the search path have \ |
| 825 |
1 |
* changed subtrees, so update augmentation for \ |
| 826 |
1 |
* them if AUGMENT_WALK didn't. \ |
| 827 |
1 |
*/ \ |
| 828 |
1 |
(void)VRBT_AUGMENT_CHECK(opar); \ |
| 829 |
1 |
(void)VRBT_AUGMENT_CHECK(VRBT_PARENT(opar, field)); \ |
| 830 |
1 |
} \ |
| 831 |
973 |
} \ |
| 832 |
1546 |
return (out); \ |
| 833 |
1546 |
} |
| 834 |
|
|
| 835 |
|
#define VRBT_GENERATE_INSERT_FINISH(name, type, field, attr) \ |
| 836 |
|
/* Inserts a node into the RB tree */ \ |
| 837 |
|
attr struct type * \ |
| 838 |
|
name##_VRBT_INSERT_FINISH(struct name *head, struct type *parent, \ |
| 839 |
5115 |
struct type **pptr, struct type *elm) \ |
| 840 |
5115 |
{ \ |
| 841 |
5115 |
struct type *tmp = NULL; \ |
| 842 |
5115 |
\ |
| 843 |
5115 |
VRBT_SET(elm, parent, field); \ |
| 844 |
5115 |
*pptr = elm; \ |
| 845 |
5115 |
if (parent != NULL) \ |
| 846 |
5115 |
tmp = name##_VRBT_INSERT_COLOR(head, parent, elm); \ |
| 847 |
5115 |
_VRBT_AUGMENT_WALK(elm, tmp, field); \ |
| 848 |
5115 |
if (tmp != NULL) \ |
| 849 |
5115 |
/* \ |
| 850 |
5115 |
* An element rotated into the search path has a \ |
| 851 |
5115 |
* changed subtree, so update augmentation for it if \ |
| 852 |
5115 |
* AUGMENT_WALK didn't. \ |
| 853 |
5115 |
*/ \ |
| 854 |
5115 |
(void)VRBT_AUGMENT_CHECK(tmp); \ |
| 855 |
5115 |
return (NULL); \ |
| 856 |
5115 |
} |
| 857 |
|
|
| 858 |
|
#define VRBT_GENERATE_INSERT(name, type, field, cmp, attr) \ |
| 859 |
|
/* Inserts a node into the RB tree */ \ |
| 860 |
|
attr struct type * \ |
| 861 |
5921 |
name##_VRBT_INSERT(struct name *head, struct type *elm) \ |
| 862 |
5921 |
{ \ |
| 863 |
5921 |
struct type *tmp; \ |
| 864 |
5921 |
struct type **tmpp = &VRBT_ROOT(head); \ |
| 865 |
5921 |
struct type *parent = NULL; \ |
| 866 |
5921 |
\ |
| 867 |
22391 |
while ((tmp = *tmpp) != NULL) { \ |
| 868 |
17276 |
parent = tmp; \ |
| 869 |
17276 |
__typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent); \ |
| 870 |
17276 |
if (comp < 0) \ |
| 871 |
17276 |
tmpp = &VRBT_LEFT(parent, field); \ |
| 872 |
17276 |
else if (comp > 0) \ |
| 873 |
12966 |
tmpp = &VRBT_RIGHT(parent, field); \ |
| 874 |
12966 |
else \ |
| 875 |
12966 |
return (parent); \ |
| 876 |
17276 |
} \ |
| 877 |
5921 |
return (name##_VRBT_INSERT_FINISH(head, parent, tmpp, elm)); \ |
| 878 |
5921 |
} |
| 879 |
|
|
| 880 |
|
#define VRBT_GENERATE_FIND(name, type, field, cmp, attr) \ |
| 881 |
|
/* Finds the node with the same key as elm */ \ |
| 882 |
|
attr struct type * \ |
| 883 |
11121872 |
name##_VRBT_FIND(const struct name *head, const struct type *elm) \ |
| 884 |
11121872 |
{ \ |
| 885 |
11121872 |
struct type *tmp = VRBT_ROOT(head); \ |
| 886 |
11121872 |
__typeof(cmp(NULL, NULL)) comp; \ |
| 887 |
99939518 |
while (tmp) { \ |
| 888 |
99936721 |
comp = cmp(elm, tmp); \ |
| 889 |
99936721 |
if (comp < 0) \ |
| 890 |
99936721 |
tmp = VRBT_LEFT(tmp, field); \ |
| 891 |
99936721 |
else if (comp > 0) \ |
| 892 |
52875182 |
tmp = VRBT_RIGHT(tmp, field); \ |
| 893 |
52875182 |
else \ |
| 894 |
52875182 |
return (tmp); \ |
| 895 |
99936721 |
} \ |
| 896 |
11121872 |
return (NULL); \ |
| 897 |
11121872 |
} |
| 898 |
|
|
| 899 |
|
#define VRBT_GENERATE_NFIND(name, type, field, cmp, attr) \ |
| 900 |
|
/* Finds the first node greater than or equal to the search key */ \ |
| 901 |
|
attr struct type * \ |
| 902 |
49 |
name##_VRBT_NFIND(const struct name *head, const struct type *elm) \ |
| 903 |
49 |
{ \ |
| 904 |
49 |
struct type *tmp = VRBT_ROOT(head); \ |
| 905 |
49 |
struct type *res = NULL; \ |
| 906 |
49 |
__typeof(cmp(NULL, NULL)) comp; \ |
| 907 |
84 |
while (tmp) { \ |
| 908 |
45 |
comp = cmp(elm, tmp); \ |
| 909 |
45 |
if (comp < 0) { \ |
| 910 |
35 |
res = tmp; \ |
| 911 |
35 |
tmp = VRBT_LEFT(tmp, field); \ |
| 912 |
35 |
} \ |
| 913 |
45 |
else if (comp > 0) \ |
| 914 |
10 |
tmp = VRBT_RIGHT(tmp, field); \ |
| 915 |
10 |
else \ |
| 916 |
10 |
return (tmp); \ |
| 917 |
45 |
} \ |
| 918 |
49 |
return (res); \ |
| 919 |
49 |
} |
| 920 |
|
|
| 921 |
|
#define VRBT_GENERATE_NEXT(name, type, field, attr) \ |
| 922 |
|
/* ARGSUSED */ \ |
| 923 |
|
attr struct type * \ |
| 924 |
2851 |
name##_VRBT_NEXT(struct type *elm) \ |
| 925 |
2851 |
{ \ |
| 926 |
2851 |
if (VRBT_RIGHT(elm, field)) { \ |
| 927 |
1181 |
elm = VRBT_RIGHT(elm, field); \ |
| 928 |
1181 |
while (VRBT_LEFT(elm, field)) \ |
| 929 |
1181 |
elm = VRBT_LEFT(elm, field); \ |
| 930 |
1670 |
} else { \ |
| 931 |
2938 |
while (VRBT_PARENT(elm, field) && \ |
| 932 |
2938 |
(elm == VRBT_RIGHT(VRBT_PARENT(elm, field), field))) \ |
| 933 |
1670 |
elm = VRBT_PARENT(elm, field); \ |
| 934 |
1670 |
elm = VRBT_PARENT(elm, field); \ |
| 935 |
1670 |
} \ |
| 936 |
2851 |
return (elm); \ |
| 937 |
2851 |
} |
| 938 |
|
|
| 939 |
|
#if defined(_KERNEL) && defined(DIAGNOSTIC) |
| 940 |
|
#define _VRBT_ORDER_CHECK(cmp, lo, hi) do { \ |
| 941 |
|
KASSERT((cmp)(lo, hi) < 0, ("out of order insertion")); \ |
| 942 |
|
} while (0) |
| 943 |
|
#else |
| 944 |
|
#define _VRBT_ORDER_CHECK(cmp, lo, hi) do {} while (0) |
| 945 |
|
#endif |
| 946 |
|
|
| 947 |
|
#define VRBT_GENERATE_INSERT_NEXT(name, type, field, cmp, attr) \ |
| 948 |
|
/* Inserts a node into the next position in the RB tree */ \ |
| 949 |
|
attr struct type * \ |
| 950 |
|
name##_VRBT_INSERT_NEXT(struct name *head, \ |
| 951 |
|
struct type *elm, struct type *next) \ |
| 952 |
|
{ \ |
| 953 |
|
struct type *tmp; \ |
| 954 |
|
struct type **tmpp = &VRBT_RIGHT(elm, field); \ |
| 955 |
|
\ |
| 956 |
|
_VRBT_ORDER_CHECK(cmp, elm, next); \ |
| 957 |
|
if (name##_VRBT_NEXT(elm) != NULL) \ |
| 958 |
|
_VRBT_ORDER_CHECK(cmp, next, name##_VRBT_NEXT(elm)); \ |
| 959 |
|
while ((tmp = *tmpp) != NULL) { \ |
| 960 |
|
elm = tmp; \ |
| 961 |
|
tmpp = &VRBT_LEFT(elm, field); \ |
| 962 |
|
} \ |
| 963 |
|
return (name##_VRBT_INSERT_FINISH(head, elm, tmpp, next)); \ |
| 964 |
|
} |
| 965 |
|
|
| 966 |
|
#define VRBT_GENERATE_PREV(name, type, field, attr) \ |
| 967 |
|
/* ARGSUSED */ \ |
| 968 |
|
attr struct type * \ |
| 969 |
345 |
name##_VRBT_PREV(struct type *elm) \ |
| 970 |
345 |
{ \ |
| 971 |
345 |
if (VRBT_LEFT(elm, field)) { \ |
| 972 |
87 |
elm = VRBT_LEFT(elm, field); \ |
| 973 |
87 |
while (VRBT_RIGHT(elm, field)) \ |
| 974 |
87 |
elm = VRBT_RIGHT(elm, field); \ |
| 975 |
258 |
} else { \ |
| 976 |
385 |
while (VRBT_PARENT(elm, field) && \ |
| 977 |
385 |
(elm == VRBT_LEFT(VRBT_PARENT(elm, field), field))) \ |
| 978 |
258 |
elm = VRBT_PARENT(elm, field); \ |
| 979 |
258 |
elm = VRBT_PARENT(elm, field); \ |
| 980 |
258 |
} \ |
| 981 |
345 |
return (elm); \ |
| 982 |
345 |
} |
| 983 |
|
|
| 984 |
|
#define VRBT_GENERATE_INSERT_PREV(name, type, field, cmp, attr) \ |
| 985 |
|
/* Inserts a node into the prev position in the RB tree */ \ |
| 986 |
|
attr struct type * \ |
| 987 |
|
name##_VRBT_INSERT_PREV(struct name *head, \ |
| 988 |
|
struct type *elm, struct type *prev) \ |
| 989 |
|
{ \ |
| 990 |
|
struct type *tmp; \ |
| 991 |
|
struct type **tmpp = &VRBT_LEFT(elm, field); \ |
| 992 |
|
\ |
| 993 |
|
_VRBT_ORDER_CHECK(cmp, prev, elm); \ |
| 994 |
|
if (name##_VRBT_PREV(elm) != NULL) \ |
| 995 |
|
_VRBT_ORDER_CHECK(cmp, name##_VRBT_PREV(elm), prev); \ |
| 996 |
|
while ((tmp = *tmpp) != NULL) { \ |
| 997 |
|
elm = tmp; \ |
| 998 |
|
tmpp = &VRBT_RIGHT(elm, field); \ |
| 999 |
|
} \ |
| 1000 |
|
return (name##_VRBT_INSERT_FINISH(head, elm, tmpp, prev)); \ |
| 1001 |
|
} |
| 1002 |
|
|
| 1003 |
|
#define VRBT_GENERATE_MINMAX(name, type, field, attr) \ |
| 1004 |
|
attr struct type * \ |
| 1005 |
19156 |
name##_VRBT_MINMAX(const struct name *head, int val) \ |
| 1006 |
19156 |
{ \ |
| 1007 |
19156 |
struct type *tmp = VRBT_ROOT(head); \ |
| 1008 |
19156 |
struct type *parent = NULL; \ |
| 1009 |
19762 |
while (tmp) { \ |
| 1010 |
606 |
parent = tmp; \ |
| 1011 |
606 |
if (val < 0) \ |
| 1012 |
606 |
tmp = VRBT_LEFT(tmp, field); \ |
| 1013 |
606 |
else \ |
| 1014 |
606 |
tmp = VRBT_RIGHT(tmp, field); \ |
| 1015 |
606 |
} \ |
| 1016 |
19156 |
return (parent); \ |
| 1017 |
19156 |
} |
| 1018 |
|
|
| 1019 |
|
#define VRBT_GENERATE_REINSERT(name, type, field, cmp, attr) \ |
| 1020 |
|
attr struct type * \ |
| 1021 |
|
name##_VRBT_REINSERT(struct name *head, struct type *elm) \ |
| 1022 |
|
{ \ |
| 1023 |
|
struct type *cmpelm; \ |
| 1024 |
|
if (((cmpelm = VRBT_PREV(name, head, elm)) != NULL && \ |
| 1025 |
|
cmp(cmpelm, elm) >= 0) || \ |
| 1026 |
|
((cmpelm = VRBT_NEXT(name, head, elm)) != NULL && \ |
| 1027 |
|
cmp(elm, cmpelm) >= 0)) { \ |
| 1028 |
|
/* XXXLAS: Remove/insert is heavy handed. */ \ |
| 1029 |
|
VRBT_REMOVE(name, head, elm); \ |
| 1030 |
|
return (VRBT_INSERT(name, head, elm)); \ |
| 1031 |
|
} \ |
| 1032 |
|
return (NULL); \ |
| 1033 |
|
} \ |
| 1034 |
|
|
| 1035 |
19122 |
#define VRBT_NEGINF -1 |
| 1036 |
35 |
#define VRBT_INF 1 |
| 1037 |
|
|
| 1038 |
4473 |
#define VRBT_INSERT(name, x, y) name##_VRBT_INSERT(x, y) |
| 1039 |
|
#define VRBT_INSERT_NEXT(name, x, y, z) name##_VRBT_INSERT_NEXT(x, y, z) |
| 1040 |
|
#define VRBT_INSERT_PREV(name, x, y, z) name##_VRBT_INSERT_PREV(x, y, z) |
| 1041 |
1546 |
#define VRBT_REMOVE(name, x, y) name##_VRBT_REMOVE(x, y) |
| 1042 |
11121871 |
#define VRBT_FIND(name, x, y) name##_VRBT_FIND(x, y) |
| 1043 |
49 |
#define VRBT_NFIND(name, x, y) name##_VRBT_NFIND(x, y) |
| 1044 |
1200 |
#define VRBT_NEXT(name, x, y) name##_VRBT_NEXT(y) |
| 1045 |
199 |
#define VRBT_PREV(name, x, y) name##_VRBT_PREV(y) |
| 1046 |
19122 |
#define VRBT_MIN(name, x) name##_VRBT_MINMAX(x, VRBT_NEGINF) |
| 1047 |
35 |
#define VRBT_MAX(name, x) name##_VRBT_MINMAX(x, VRBT_INF) |
| 1048 |
|
#define VRBT_REINSERT(name, x, y) name##_VRBT_REINSERT(x, y) |
| 1049 |
|
|
| 1050 |
|
#define VRBT_FOREACH(x, name, head) \ |
| 1051 |
52 |
for ((x) = VRBT_MIN(name, head); \ |
| 1052 |
269 |
(x) != NULL; \ |
| 1053 |
217 |
(x) = name##_VRBT_NEXT(x)) |
| 1054 |
|
|
| 1055 |
|
#define VRBT_FOREACH_FROM(x, name, y) \ |
| 1056 |
|
for ((x) = (y); \ |
| 1057 |
|
((x) != NULL) && ((y) = name##_VRBT_NEXT(x), (x) != NULL); \ |
| 1058 |
|
(x) = (y)) |
| 1059 |
|
|
| 1060 |
|
#define VRBT_FOREACH_SAFE(x, name, head, y) \ |
| 1061 |
19047 |
for ((x) = VRBT_MIN(name, head); \ |
| 1062 |
20481 |
((x) != NULL) && ((y) = name##_VRBT_NEXT(x), (x) != NULL); \ |
| 1063 |
19047 |
(x) = (y)) |
| 1064 |
|
|
| 1065 |
|
#define VRBT_FOREACH_REVERSE(x, name, head) \ |
| 1066 |
35 |
for ((x) = VRBT_MAX(name, head); \ |
| 1067 |
181 |
(x) != NULL; \ |
| 1068 |
146 |
(x) = name##_VRBT_PREV(x)) |
| 1069 |
|
|
| 1070 |
|
#define VRBT_FOREACH_REVERSE_FROM(x, name, y) \ |
| 1071 |
|
for ((x) = (y); \ |
| 1072 |
|
((x) != NULL) && ((y) = name##_VRBT_PREV(x), (x) != NULL); \ |
| 1073 |
|
(x) = (y)) |
| 1074 |
|
|
| 1075 |
|
#define VRBT_FOREACH_REVERSE_SAFE(x, name, head, y) \ |
| 1076 |
|
for ((x) = VRBT_MAX(name, head); \ |
| 1077 |
|
((x) != NULL) && ((y) = name##_VRBT_PREV(x), (x) != NULL); \ |
| 1078 |
|
(x) = (y)) |
| 1079 |
|
|
| 1080 |
|
#endif /* _VTREE_H_ */ |