1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/ipc/chromium/src/third_party/libevent/WIN32-Code/tree.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1354 @@
1.4 +/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
1.5 +/*
1.6 + * Copyright 2002 Niels Provos <provos@citi.umich.edu>
1.7 + * All rights reserved.
1.8 + *
1.9 + * Redistribution and use in source and binary forms, with or without
1.10 + * modification, are permitted provided that the following conditions
1.11 + * are met:
1.12 + * 1. Redistributions of source code must retain the above copyright
1.13 + * notice, this list of conditions and the following disclaimer.
1.14 + * 2. Redistributions in binary form must reproduce the above copyright
1.15 + * notice, this list of conditions and the following disclaimer in the
1.16 + * documentation and/or other materials provided with the distribution.
1.17 + *
1.18 + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
1.19 + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
1.20 + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
1.21 + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
1.22 + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
1.23 + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.24 + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.25 + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.26 + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
1.27 + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.28 + */
1.29 +
1.30 +#ifndef _SYS_TREE_H_
1.31 +#define _SYS_TREE_H_
1.32 +
1.33 +/*
1.34 + * This file defines data structures for different types of trees:
1.35 + * splay trees and red-black trees.
1.36 + *
1.37 + * A splay tree is a self-organizing data structure. Every operation
1.38 + * on the tree causes a splay to happen. The splay moves the requested
1.39 + * node to the root of the tree and partly rebalances it.
1.40 + *
1.41 + * This has the benefit that request locality causes faster lookups as
1.42 + * the requested nodes move to the top of the tree. On the other hand,
1.43 + * every lookup causes memory writes.
1.44 + *
1.45 + * The Balance Theorem bounds the total access time for m operations
1.46 + * and n inserts on an initially empty tree as O((m + n)lg n). The
1.47 + * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
1.48 + *
1.49 + * A red-black tree is a binary search tree with the node color as an
1.50 + * extra attribute. It fulfills a set of conditions:
1.51 + * - every search path from the root to a leaf consists of the
1.52 + * same number of black nodes,
1.53 + * - each red node (except for the root) has a black parent,
1.54 + * - each leaf node is black.
1.55 + *
1.56 + * Every operation on a red-black tree is bounded as O(lg n).
1.57 + * The maximum height of a red-black tree is 2lg (n+1).
1.58 + */
1.59 +
1.60 +#define SPLAY_HEAD(name, type) \
1.61 +struct name { \
1.62 + struct type *sph_root; /* root of the tree */ \
1.63 +}
1.64 +
1.65 +#define SPLAY_INITIALIZER(root) \
1.66 + { NULL }
1.67 +
1.68 +#define SPLAY_INIT(root) do { \
1.69 + (root)->sph_root = NULL; \
1.70 +} while (0)
1.71 +
1.72 +#define SPLAY_ENTRY(type) \
1.73 +struct { \
1.74 + struct type *spe_left; /* left element */ \
1.75 + struct type *spe_right; /* right element */ \
1.76 +}
1.77 +
1.78 +#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
1.79 +#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
1.80 +#define SPLAY_ROOT(head) (head)->sph_root
1.81 +#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
1.82 +
1.83 +/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
1.84 +#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
1.85 + SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
1.86 + SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
1.87 + (head)->sph_root = tmp; \
1.88 +} while (0)
1.89 +
1.90 +#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
1.91 + SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
1.92 + SPLAY_LEFT(tmp, field) = (head)->sph_root; \
1.93 + (head)->sph_root = tmp; \
1.94 +} while (0)
1.95 +
1.96 +#define SPLAY_LINKLEFT(head, tmp, field) do { \
1.97 + SPLAY_LEFT(tmp, field) = (head)->sph_root; \
1.98 + tmp = (head)->sph_root; \
1.99 + (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
1.100 +} while (0)
1.101 +
1.102 +#define SPLAY_LINKRIGHT(head, tmp, field) do { \
1.103 + SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
1.104 + tmp = (head)->sph_root; \
1.105 + (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
1.106 +} while (0)
1.107 +
1.108 +#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
1.109 + SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
1.110 + SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
1.111 + SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
1.112 + SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
1.113 +} while (0)
1.114 +
1.115 +/* Generates prototypes and inline functions */
1.116 +
1.117 +#define SPLAY_PROTOTYPE(name, type, field, cmp) \
1.118 +void name##_SPLAY(struct name *, struct type *); \
1.119 +void name##_SPLAY_MINMAX(struct name *, int); \
1.120 +struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
1.121 +struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
1.122 + \
1.123 +/* Finds the node with the same key as elm */ \
1.124 +static __inline struct type * \
1.125 +name##_SPLAY_FIND(struct name *head, struct type *elm) \
1.126 +{ \
1.127 + if (SPLAY_EMPTY(head)) \
1.128 + return(NULL); \
1.129 + name##_SPLAY(head, elm); \
1.130 + if ((cmp)(elm, (head)->sph_root) == 0) \
1.131 + return (head->sph_root); \
1.132 + return (NULL); \
1.133 +} \
1.134 + \
1.135 +static __inline struct type * \
1.136 +name##_SPLAY_NEXT(struct name *head, struct type *elm) \
1.137 +{ \
1.138 + name##_SPLAY(head, elm); \
1.139 + if (SPLAY_RIGHT(elm, field) != NULL) { \
1.140 + elm = SPLAY_RIGHT(elm, field); \
1.141 + while (SPLAY_LEFT(elm, field) != NULL) { \
1.142 + elm = SPLAY_LEFT(elm, field); \
1.143 + } \
1.144 + } else \
1.145 + elm = NULL; \
1.146 + return (elm); \
1.147 +} \
1.148 + \
1.149 +static __inline struct type * \
1.150 +name##_SPLAY_MIN_MAX(struct name *head, int val) \
1.151 +{ \
1.152 + name##_SPLAY_MINMAX(head, val); \
1.153 + return (SPLAY_ROOT(head)); \
1.154 +}
1.155 +
1.156 +/* Main splay operation.
1.157 + * Moves node close to the key of elm to top
1.158 + */
1.159 +#define SPLAY_GENERATE(name, type, field, cmp) \
1.160 +struct type * \
1.161 +name##_SPLAY_INSERT(struct name *head, struct type *elm) \
1.162 +{ \
1.163 + if (SPLAY_EMPTY(head)) { \
1.164 + SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
1.165 + } else { \
1.166 + int __comp; \
1.167 + name##_SPLAY(head, elm); \
1.168 + __comp = (cmp)(elm, (head)->sph_root); \
1.169 + if(__comp < 0) { \
1.170 + SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
1.171 + SPLAY_RIGHT(elm, field) = (head)->sph_root; \
1.172 + SPLAY_LEFT((head)->sph_root, field) = NULL; \
1.173 + } else if (__comp > 0) { \
1.174 + SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
1.175 + SPLAY_LEFT(elm, field) = (head)->sph_root; \
1.176 + SPLAY_RIGHT((head)->sph_root, field) = NULL; \
1.177 + } else \
1.178 + return ((head)->sph_root); \
1.179 + } \
1.180 + (head)->sph_root = (elm); \
1.181 + return (NULL); \
1.182 +} \
1.183 + \
1.184 +struct type * \
1.185 +name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
1.186 +{ \
1.187 + struct type *__tmp; \
1.188 + if (SPLAY_EMPTY(head)) \
1.189 + return (NULL); \
1.190 + name##_SPLAY(head, elm); \
1.191 + if ((cmp)(elm, (head)->sph_root) == 0) { \
1.192 + if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
1.193 + (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
1.194 + } else { \
1.195 + __tmp = SPLAY_RIGHT((head)->sph_root, field); \
1.196 + (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
1.197 + name##_SPLAY(head, elm); \
1.198 + SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
1.199 + } \
1.200 + return (elm); \
1.201 + } \
1.202 + return (NULL); \
1.203 +} \
1.204 + \
1.205 +void \
1.206 +name##_SPLAY(struct name *head, struct type *elm) \
1.207 +{ \
1.208 + struct type __node, *__left, *__right, *__tmp; \
1.209 + int __comp; \
1.210 +\
1.211 + SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
1.212 + __left = __right = &__node; \
1.213 +\
1.214 + while ((__comp = (cmp)(elm, (head)->sph_root))) { \
1.215 + if (__comp < 0) { \
1.216 + __tmp = SPLAY_LEFT((head)->sph_root, field); \
1.217 + if (__tmp == NULL) \
1.218 + break; \
1.219 + if ((cmp)(elm, __tmp) < 0){ \
1.220 + SPLAY_ROTATE_RIGHT(head, __tmp, field); \
1.221 + if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
1.222 + break; \
1.223 + } \
1.224 + SPLAY_LINKLEFT(head, __right, field); \
1.225 + } else if (__comp > 0) { \
1.226 + __tmp = SPLAY_RIGHT((head)->sph_root, field); \
1.227 + if (__tmp == NULL) \
1.228 + break; \
1.229 + if ((cmp)(elm, __tmp) > 0){ \
1.230 + SPLAY_ROTATE_LEFT(head, __tmp, field); \
1.231 + if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
1.232 + break; \
1.233 + } \
1.234 + SPLAY_LINKRIGHT(head, __left, field); \
1.235 + } \
1.236 + } \
1.237 + SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
1.238 +} \
1.239 + \
1.240 +/* Splay with either the minimum or the maximum element \
1.241 + * Used to find minimum or maximum element in tree. \
1.242 + */ \
1.243 +void name##_SPLAY_MINMAX(struct name *head, int __comp) \
1.244 +{ \
1.245 + struct type __node, *__left, *__right, *__tmp; \
1.246 +\
1.247 + SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
1.248 + __left = __right = &__node; \
1.249 +\
1.250 + while (1) { \
1.251 + if (__comp < 0) { \
1.252 + __tmp = SPLAY_LEFT((head)->sph_root, field); \
1.253 + if (__tmp == NULL) \
1.254 + break; \
1.255 + if (__comp < 0){ \
1.256 + SPLAY_ROTATE_RIGHT(head, __tmp, field); \
1.257 + if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
1.258 + break; \
1.259 + } \
1.260 + SPLAY_LINKLEFT(head, __right, field); \
1.261 + } else if (__comp > 0) { \
1.262 + __tmp = SPLAY_RIGHT((head)->sph_root, field); \
1.263 + if (__tmp == NULL) \
1.264 + break; \
1.265 + if (__comp > 0) { \
1.266 + SPLAY_ROTATE_LEFT(head, __tmp, field); \
1.267 + if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
1.268 + break; \
1.269 + } \
1.270 + SPLAY_LINKRIGHT(head, __left, field); \
1.271 + } \
1.272 + } \
1.273 + SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
1.274 +}
1.275 +
1.276 +#define SPLAY_NEGINF -1
1.277 +#define SPLAY_INF 1
1.278 +
1.279 +#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
1.280 +#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
1.281 +#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
1.282 +#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
1.283 +#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
1.284 + : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
1.285 +#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
1.286 + : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
1.287 +
1.288 +#define SPLAY_FOREACH(x, name, head) \
1.289 + for ((x) = SPLAY_MIN(name, head); \
1.290 + (x) != NULL; \
1.291 + (x) = SPLAY_NEXT(name, head, x))
1.292 +
1.293 +/* Macros that define a red-back tree */
1.294 +#define RB_HEAD(name, type) \
1.295 +struct name { \
1.296 + struct type *rbh_root; /* root of the tree */ \
1.297 +}
1.298 +
1.299 +#define RB_INITIALIZER(root) \
1.300 + { NULL }
1.301 +
1.302 +#define RB_INIT(root) do { \
1.303 + (root)->rbh_root = NULL; \
1.304 +} while (0)
1.305 +
1.306 +#define RB_BLACK 0
1.307 +#define RB_RED 1
1.308 +#define RB_ENTRY(type) \
1.309 +struct { \
1.310 + struct type *rbe_left; /* left element */ \
1.311 + struct type *rbe_right; /* right element */ \
1.312 + struct type *rbe_parent; /* parent element */ \
1.313 + int rbe_color; /* node color */ \
1.314 +}
1.315 +
1.316 +#define RB_LEFT(elm, field) (elm)->field.rbe_left
1.317 +#define RB_RIGHT(elm, field) (elm)->field.rbe_right
1.318 +#define RB_PARENT(elm, field) (elm)->field.rbe_parent
1.319 +#define RB_COLOR(elm, field) (elm)->field.rbe_color
1.320 +#define RB_ROOT(head) (head)->rbh_root
1.321 +#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
1.322 +
1.323 +#define RB_SET(elm, parent, field) do { \
1.324 + RB_PARENT(elm, field) = parent; \
1.325 + RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
1.326 + RB_COLOR(elm, field) = RB_RED; \
1.327 +} while (0)
1.328 +
1.329 +#define RB_SET_BLACKRED(black, red, field) do { \
1.330 + RB_COLOR(black, field) = RB_BLACK; \
1.331 + RB_COLOR(red, field) = RB_RED; \
1.332 +} while (0)
1.333 +
1.334 +#ifndef RB_AUGMENT
1.335 +#define RB_AUGMENT(x)
1.336 +#endif
1.337 +
1.338 +#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
1.339 + (tmp) = RB_RIGHT(elm, field); \
1.340 + if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
1.341 + RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
1.342 + } \
1.343 + RB_AUGMENT(elm); \
1.344 + if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
1.345 + if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
1.346 + RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
1.347 + else \
1.348 + RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
1.349 + } else \
1.350 + (head)->rbh_root = (tmp); \
1.351 + RB_LEFT(tmp, field) = (elm); \
1.352 + RB_PARENT(elm, field) = (tmp); \
1.353 + RB_AUGMENT(tmp); \
1.354 + if ((RB_PARENT(tmp, field))) \
1.355 + RB_AUGMENT(RB_PARENT(tmp, field)); \
1.356 +} while (0)
1.357 +
1.358 +#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
1.359 + (tmp) = RB_LEFT(elm, field); \
1.360 + if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
1.361 + RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
1.362 + } \
1.363 + RB_AUGMENT(elm); \
1.364 + if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
1.365 + if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
1.366 + RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
1.367 + else \
1.368 + RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
1.369 + } else \
1.370 + (head)->rbh_root = (tmp); \
1.371 + RB_RIGHT(tmp, field) = (elm); \
1.372 + RB_PARENT(elm, field) = (tmp); \
1.373 + RB_AUGMENT(tmp); \
1.374 + if ((RB_PARENT(tmp, field))) \
1.375 + RB_AUGMENT(RB_PARENT(tmp, field)); \
1.376 +} while (0)
1.377 +
1.378 +/* Generates prototypes and inline functions */
1.379 +#define RB_PROTOTYPE(name, type, field, cmp) \
1.380 +void name##_RB_INSERT_COLOR(struct name *, struct type *); \
1.381 +void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
1.382 +struct type *name##_RB_REMOVE(struct name *, struct type *); \
1.383 +struct type *name##_RB_INSERT(struct name *, struct type *); \
1.384 +struct type *name##_RB_FIND(struct name *, struct type *); \
1.385 +struct type *name##_RB_NEXT(struct type *); \
1.386 +struct type *name##_RB_MINMAX(struct name *, int); \
1.387 + \
1.388 +
1.389 +/* Main rb operation.
1.390 + * Moves node close to the key of elm to top
1.391 + */
1.392 +#define RB_GENERATE(name, type, field, cmp) \
1.393 +void \
1.394 +name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
1.395 +{ \
1.396 + struct type *parent, *gparent, *tmp; \
1.397 + while ((parent = RB_PARENT(elm, field)) && \
1.398 + RB_COLOR(parent, field) == RB_RED) { \
1.399 + gparent = RB_PARENT(parent, field); \
1.400 + if (parent == RB_LEFT(gparent, field)) { \
1.401 + tmp = RB_RIGHT(gparent, field); \
1.402 + if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
1.403 + RB_COLOR(tmp, field) = RB_BLACK; \
1.404 + RB_SET_BLACKRED(parent, gparent, field);\
1.405 + elm = gparent; \
1.406 + continue; \
1.407 + } \
1.408 + if (RB_RIGHT(parent, field) == elm) { \
1.409 + RB_ROTATE_LEFT(head, parent, tmp, field);\
1.410 + tmp = parent; \
1.411 + parent = elm; \
1.412 + elm = tmp; \
1.413 + } \
1.414 + RB_SET_BLACKRED(parent, gparent, field); \
1.415 + RB_ROTATE_RIGHT(head, gparent, tmp, field); \
1.416 + } else { \
1.417 + tmp = RB_LEFT(gparent, field); \
1.418 + if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
1.419 + RB_COLOR(tmp, field) = RB_BLACK; \
1.420 + RB_SET_BLACKRED(parent, gparent, field);\
1.421 + elm = gparent; \
1.422 + continue; \
1.423 + } \
1.424 + if (RB_LEFT(parent, field) == elm) { \
1.425 + RB_ROTATE_RIGHT(head, parent, tmp, field);\
1.426 + tmp = parent; \
1.427 + parent = elm; \
1.428 + elm = tmp; \
1.429 + } \
1.430 + RB_SET_BLACKRED(parent, gparent, field); \
1.431 + RB_ROTATE_LEFT(head, gparent, tmp, field); \
1.432 + } \
1.433 + } \
1.434 + RB_COLOR(head->rbh_root, field) = RB_BLACK; \
1.435 +} \
1.436 + \
1.437 +void \
1.438 +name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
1.439 +{ \
1.440 + struct type *tmp; \
1.441 + while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
1.442 + elm != RB_ROOT(head)) { \
1.443 + if (RB_LEFT(parent, field) == elm) { \
1.444 + tmp = RB_RIGHT(parent, field); \
1.445 + if (RB_COLOR(tmp, field) == RB_RED) { \
1.446 + RB_SET_BLACKRED(tmp, parent, field); \
1.447 + RB_ROTATE_LEFT(head, parent, tmp, field);\
1.448 + tmp = RB_RIGHT(parent, field); \
1.449 + } \
1.450 + if ((RB_LEFT(tmp, field) == NULL || \
1.451 + RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
1.452 + (RB_RIGHT(tmp, field) == NULL || \
1.453 + RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
1.454 + RB_COLOR(tmp, field) = RB_RED; \
1.455 + elm = parent; \
1.456 + parent = RB_PARENT(elm, field); \
1.457 + } else { \
1.458 + if (RB_RIGHT(tmp, field) == NULL || \
1.459 + RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
1.460 + struct type *oleft; \
1.461 + if ((oleft = RB_LEFT(tmp, field)))\
1.462 + RB_COLOR(oleft, field) = RB_BLACK;\
1.463 + RB_COLOR(tmp, field) = RB_RED; \
1.464 + RB_ROTATE_RIGHT(head, tmp, oleft, field);\
1.465 + tmp = RB_RIGHT(parent, field); \
1.466 + } \
1.467 + RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
1.468 + RB_COLOR(parent, field) = RB_BLACK; \
1.469 + if (RB_RIGHT(tmp, field)) \
1.470 + RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
1.471 + RB_ROTATE_LEFT(head, parent, tmp, field);\
1.472 + elm = RB_ROOT(head); \
1.473 + break; \
1.474 + } \
1.475 + } else { \
1.476 + tmp = RB_LEFT(parent, field); \
1.477 + if (RB_COLOR(tmp, field) == RB_RED) { \
1.478 + RB_SET_BLACKRED(tmp, parent, field); \
1.479 + RB_ROTATE_RIGHT(head, parent, tmp, field);\
1.480 + tmp = RB_LEFT(parent, field); \
1.481 + } \
1.482 + if ((RB_LEFT(tmp, field) == NULL || \
1.483 + RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
1.484 + (RB_RIGHT(tmp, field) == NULL || \
1.485 + RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
1.486 + RB_COLOR(tmp, field) = RB_RED; \
1.487 + elm = parent; \
1.488 + parent = RB_PARENT(elm, field); \
1.489 + } else { \
1.490 + if (RB_LEFT(tmp, field) == NULL || \
1.491 + RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
1.492 + struct type *oright; \
1.493 + if ((oright = RB_RIGHT(tmp, field)))\
1.494 + RB_COLOR(oright, field) = RB_BLACK;\
1.495 + RB_COLOR(tmp, field) = RB_RED; \
1.496 + RB_ROTATE_LEFT(head, tmp, oright, field);\
1.497 + tmp = RB_LEFT(parent, field); \
1.498 + } \
1.499 + RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
1.500 + RB_COLOR(parent, field) = RB_BLACK; \
1.501 + if (RB_LEFT(tmp, field)) \
1.502 + RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
1.503 + RB_ROTATE_RIGHT(head, parent, tmp, field);\
1.504 + elm = RB_ROOT(head); \
1.505 + break; \
1.506 + } \
1.507 + } \
1.508 + } \
1.509 + if (elm) \
1.510 + RB_COLOR(elm, field) = RB_BLACK; \
1.511 +} \
1.512 + \
1.513 +struct type * \
1.514 +name##_RB_REMOVE(struct name *head, struct type *elm) \
1.515 +{ \
1.516 + struct type *child, *parent, *old = elm; \
1.517 + int color; \
1.518 + if (RB_LEFT(elm, field) == NULL) \
1.519 + child = RB_RIGHT(elm, field); \
1.520 + else if (RB_RIGHT(elm, field) == NULL) \
1.521 + child = RB_LEFT(elm, field); \
1.522 + else { \
1.523 + struct type *left; \
1.524 + elm = RB_RIGHT(elm, field); \
1.525 + while ((left = RB_LEFT(elm, field))) \
1.526 + elm = left; \
1.527 + child = RB_RIGHT(elm, field); \
1.528 + parent = RB_PARENT(elm, field); \
1.529 + color = RB_COLOR(elm, field); \
1.530 + if (child) \
1.531 + RB_PARENT(child, field) = parent; \
1.532 + if (parent) { \
1.533 + if (RB_LEFT(parent, field) == elm) \
1.534 + RB_LEFT(parent, field) = child; \
1.535 + else \
1.536 + RB_RIGHT(parent, field) = child; \
1.537 + RB_AUGMENT(parent); \
1.538 + } else \
1.539 + RB_ROOT(head) = child; \
1.540 + if (RB_PARENT(elm, field) == old) \
1.541 + parent = elm; \
1.542 + (elm)->field = (old)->field; \
1.543 + if (RB_PARENT(old, field)) { \
1.544 + if (RB_LEFT(RB_PARENT(old, field), field) == old)\
1.545 + RB_LEFT(RB_PARENT(old, field), field) = elm;\
1.546 + else \
1.547 + RB_RIGHT(RB_PARENT(old, field), field) = elm;\
1.548 + RB_AUGMENT(RB_PARENT(old, field)); \
1.549 + } else \
1.550 + RB_ROOT(head) = elm; \
1.551 + RB_PARENT(RB_LEFT(old, field), field) = elm; \
1.552 + if (RB_RIGHT(old, field)) \
1.553 + RB_PARENT(RB_RIGHT(old, field), field) = elm; \
1.554 + if (parent) { \
1.555 + left = parent; \
1.556 + do { \
1.557 + RB_AUGMENT(left); \
1.558 + } while ((left = RB_PARENT(left, field))); \
1.559 + } \
1.560 + goto color; \
1.561 + } \
1.562 + parent = RB_PARENT(elm, field); \
1.563 + color = RB_COLOR(elm, field); \
1.564 + if (child) \
1.565 + RB_PARENT(child, field) = parent; \
1.566 + if (parent) { \
1.567 + if (RB_LEFT(parent, field) == elm) \
1.568 + RB_LEFT(parent, field) = child; \
1.569 + else \
1.570 + RB_RIGHT(parent, field) = child; \
1.571 + RB_AUGMENT(parent); \
1.572 + } else \
1.573 + RB_ROOT(head) = child; \
1.574 +color: \
1.575 + if (color == RB_BLACK) \
1.576 + name##_RB_REMOVE_COLOR(head, parent, child); \
1.577 + return (old); \
1.578 +} \
1.579 + \
1.580 +/* Inserts a node into the RB tree */ \
1.581 +struct type * \
1.582 +name##_RB_INSERT(struct name *head, struct type *elm) \
1.583 +{ \
1.584 + struct type *tmp; \
1.585 + struct type *parent = NULL; \
1.586 + int comp = 0; \
1.587 + tmp = RB_ROOT(head); \
1.588 + while (tmp) { \
1.589 + parent = tmp; \
1.590 + comp = (cmp)(elm, parent); \
1.591 + if (comp < 0) \
1.592 + tmp = RB_LEFT(tmp, field); \
1.593 + else if (comp > 0) \
1.594 + tmp = RB_RIGHT(tmp, field); \
1.595 + else \
1.596 + return (tmp); \
1.597 + } \
1.598 + RB_SET(elm, parent, field); \
1.599 + if (parent != NULL) { \
1.600 + if (comp < 0) \
1.601 + RB_LEFT(parent, field) = elm; \
1.602 + else \
1.603 + RB_RIGHT(parent, field) = elm; \
1.604 + RB_AUGMENT(parent); \
1.605 + } else \
1.606 + RB_ROOT(head) = elm; \
1.607 + name##_RB_INSERT_COLOR(head, elm); \
1.608 + return (NULL); \
1.609 +} \
1.610 + \
1.611 +/* Finds the node with the same key as elm */ \
1.612 +struct type * \
1.613 +name##_RB_FIND(struct name *head, struct type *elm) \
1.614 +{ \
1.615 + struct type *tmp = RB_ROOT(head); \
1.616 + int comp; \
1.617 + while (tmp) { \
1.618 + comp = cmp(elm, tmp); \
1.619 + if (comp < 0) \
1.620 + tmp = RB_LEFT(tmp, field); \
1.621 + else if (comp > 0) \
1.622 + tmp = RB_RIGHT(tmp, field); \
1.623 + else \
1.624 + return (tmp); \
1.625 + } \
1.626 + return (NULL); \
1.627 +} \
1.628 + \
1.629 +struct type * \
1.630 +name##_RB_NEXT(struct type *elm) \
1.631 +{ \
1.632 + if (RB_RIGHT(elm, field)) { \
1.633 + elm = RB_RIGHT(elm, field); \
1.634 + while (RB_LEFT(elm, field)) \
1.635 + elm = RB_LEFT(elm, field); \
1.636 + } else { \
1.637 + if (RB_PARENT(elm, field) && \
1.638 + (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
1.639 + elm = RB_PARENT(elm, field); \
1.640 + else { \
1.641 + while (RB_PARENT(elm, field) && \
1.642 + (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
1.643 + elm = RB_PARENT(elm, field); \
1.644 + elm = RB_PARENT(elm, field); \
1.645 + } \
1.646 + } \
1.647 + return (elm); \
1.648 +} \
1.649 + \
1.650 +struct type * \
1.651 +name##_RB_MINMAX(struct name *head, int val) \
1.652 +{ \
1.653 + struct type *tmp = RB_ROOT(head); \
1.654 + struct type *parent = NULL; \
1.655 + while (tmp) { \
1.656 + parent = tmp; \
1.657 + if (val < 0) \
1.658 + tmp = RB_LEFT(tmp, field); \
1.659 + else \
1.660 + tmp = RB_RIGHT(tmp, field); \
1.661 + } \
1.662 + return (parent); \
1.663 +}
1.664 +
1.665 +#define RB_NEGINF -1
1.666 +#define RB_INF 1
1.667 +
1.668 +#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
1.669 +#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
1.670 +#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
1.671 +#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
1.672 +#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
1.673 +#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
1.674 +
1.675 +#define RB_FOREACH(x, name, head) \
1.676 + for ((x) = RB_MIN(name, head); \
1.677 + (x) != NULL; \
1.678 + (x) = name##_RB_NEXT(x))
1.679 +
1.680 +#endif /* _SYS_TREE_H_ */
1.681 +/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
1.682 +/*
1.683 + * Copyright 2002 Niels Provos <provos@citi.umich.edu>
1.684 + * All rights reserved.
1.685 + *
1.686 + * Redistribution and use in source and binary forms, with or without
1.687 + * modification, are permitted provided that the following conditions
1.688 + * are met:
1.689 + * 1. Redistributions of source code must retain the above copyright
1.690 + * notice, this list of conditions and the following disclaimer.
1.691 + * 2. Redistributions in binary form must reproduce the above copyright
1.692 + * notice, this list of conditions and the following disclaimer in the
1.693 + * documentation and/or other materials provided with the distribution.
1.694 + *
1.695 + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
1.696 + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
1.697 + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
1.698 + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
1.699 + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
1.700 + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.701 + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.702 + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.703 + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
1.704 + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.705 + */
1.706 +
1.707 +#ifndef _SYS_TREE_H_
1.708 +#define _SYS_TREE_H_
1.709 +
1.710 +/*
1.711 + * This file defines data structures for different types of trees:
1.712 + * splay trees and red-black trees.
1.713 + *
1.714 + * A splay tree is a self-organizing data structure. Every operation
1.715 + * on the tree causes a splay to happen. The splay moves the requested
1.716 + * node to the root of the tree and partly rebalances it.
1.717 + *
1.718 + * This has the benefit that request locality causes faster lookups as
1.719 + * the requested nodes move to the top of the tree. On the other hand,
1.720 + * every lookup causes memory writes.
1.721 + *
1.722 + * The Balance Theorem bounds the total access time for m operations
1.723 + * and n inserts on an initially empty tree as O((m + n)lg n). The
1.724 + * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
1.725 + *
1.726 + * A red-black tree is a binary search tree with the node color as an
1.727 + * extra attribute. It fulfills a set of conditions:
1.728 + * - every search path from the root to a leaf consists of the
1.729 + * same number of black nodes,
1.730 + * - each red node (except for the root) has a black parent,
1.731 + * - each leaf node is black.
1.732 + *
1.733 + * Every operation on a red-black tree is bounded as O(lg n).
1.734 + * The maximum height of a red-black tree is 2lg (n+1).
1.735 + */
1.736 +
1.737 +#define SPLAY_HEAD(name, type) \
1.738 +struct name { \
1.739 + struct type *sph_root; /* root of the tree */ \
1.740 +}
1.741 +
1.742 +#define SPLAY_INITIALIZER(root) \
1.743 + { NULL }
1.744 +
1.745 +#define SPLAY_INIT(root) do { \
1.746 + (root)->sph_root = NULL; \
1.747 +} while (0)
1.748 +
1.749 +#define SPLAY_ENTRY(type) \
1.750 +struct { \
1.751 + struct type *spe_left; /* left element */ \
1.752 + struct type *spe_right; /* right element */ \
1.753 +}
1.754 +
1.755 +#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
1.756 +#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
1.757 +#define SPLAY_ROOT(head) (head)->sph_root
1.758 +#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
1.759 +
1.760 +/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
1.761 +#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
1.762 + SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
1.763 + SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
1.764 + (head)->sph_root = tmp; \
1.765 +} while (0)
1.766 +
1.767 +#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
1.768 + SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
1.769 + SPLAY_LEFT(tmp, field) = (head)->sph_root; \
1.770 + (head)->sph_root = tmp; \
1.771 +} while (0)
1.772 +
1.773 +#define SPLAY_LINKLEFT(head, tmp, field) do { \
1.774 + SPLAY_LEFT(tmp, field) = (head)->sph_root; \
1.775 + tmp = (head)->sph_root; \
1.776 + (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
1.777 +} while (0)
1.778 +
1.779 +#define SPLAY_LINKRIGHT(head, tmp, field) do { \
1.780 + SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
1.781 + tmp = (head)->sph_root; \
1.782 + (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
1.783 +} while (0)
1.784 +
1.785 +#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
1.786 + SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
1.787 + SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
1.788 + SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
1.789 + SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
1.790 +} while (0)
1.791 +
1.792 +/* Generates prototypes and inline functions */
1.793 +
1.794 +#define SPLAY_PROTOTYPE(name, type, field, cmp) \
1.795 +void name##_SPLAY(struct name *, struct type *); \
1.796 +void name##_SPLAY_MINMAX(struct name *, int); \
1.797 +struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
1.798 +struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
1.799 + \
1.800 +/* Finds the node with the same key as elm */ \
1.801 +static __inline struct type * \
1.802 +name##_SPLAY_FIND(struct name *head, struct type *elm) \
1.803 +{ \
1.804 + if (SPLAY_EMPTY(head)) \
1.805 + return(NULL); \
1.806 + name##_SPLAY(head, elm); \
1.807 + if ((cmp)(elm, (head)->sph_root) == 0) \
1.808 + return (head->sph_root); \
1.809 + return (NULL); \
1.810 +} \
1.811 + \
1.812 +static __inline struct type * \
1.813 +name##_SPLAY_NEXT(struct name *head, struct type *elm) \
1.814 +{ \
1.815 + name##_SPLAY(head, elm); \
1.816 + if (SPLAY_RIGHT(elm, field) != NULL) { \
1.817 + elm = SPLAY_RIGHT(elm, field); \
1.818 + while (SPLAY_LEFT(elm, field) != NULL) { \
1.819 + elm = SPLAY_LEFT(elm, field); \
1.820 + } \
1.821 + } else \
1.822 + elm = NULL; \
1.823 + return (elm); \
1.824 +} \
1.825 + \
1.826 +static __inline struct type * \
1.827 +name##_SPLAY_MIN_MAX(struct name *head, int val) \
1.828 +{ \
1.829 + name##_SPLAY_MINMAX(head, val); \
1.830 + return (SPLAY_ROOT(head)); \
1.831 +}
1.832 +
1.833 +/* Main splay operation.
1.834 + * Moves node close to the key of elm to top
1.835 + */
1.836 +#define SPLAY_GENERATE(name, type, field, cmp) \
1.837 +struct type * \
1.838 +name##_SPLAY_INSERT(struct name *head, struct type *elm) \
1.839 +{ \
1.840 + if (SPLAY_EMPTY(head)) { \
1.841 + SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
1.842 + } else { \
1.843 + int __comp; \
1.844 + name##_SPLAY(head, elm); \
1.845 + __comp = (cmp)(elm, (head)->sph_root); \
1.846 + if(__comp < 0) { \
1.847 + SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
1.848 + SPLAY_RIGHT(elm, field) = (head)->sph_root; \
1.849 + SPLAY_LEFT((head)->sph_root, field) = NULL; \
1.850 + } else if (__comp > 0) { \
1.851 + SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
1.852 + SPLAY_LEFT(elm, field) = (head)->sph_root; \
1.853 + SPLAY_RIGHT((head)->sph_root, field) = NULL; \
1.854 + } else \
1.855 + return ((head)->sph_root); \
1.856 + } \
1.857 + (head)->sph_root = (elm); \
1.858 + return (NULL); \
1.859 +} \
1.860 + \
1.861 +struct type * \
1.862 +name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
1.863 +{ \
1.864 + struct type *__tmp; \
1.865 + if (SPLAY_EMPTY(head)) \
1.866 + return (NULL); \
1.867 + name##_SPLAY(head, elm); \
1.868 + if ((cmp)(elm, (head)->sph_root) == 0) { \
1.869 + if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
1.870 + (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
1.871 + } else { \
1.872 + __tmp = SPLAY_RIGHT((head)->sph_root, field); \
1.873 + (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
1.874 + name##_SPLAY(head, elm); \
1.875 + SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
1.876 + } \
1.877 + return (elm); \
1.878 + } \
1.879 + return (NULL); \
1.880 +} \
1.881 + \
1.882 +void \
1.883 +name##_SPLAY(struct name *head, struct type *elm) \
1.884 +{ \
1.885 + struct type __node, *__left, *__right, *__tmp; \
1.886 + int __comp; \
1.887 +\
1.888 + SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
1.889 + __left = __right = &__node; \
1.890 +\
1.891 + while ((__comp = (cmp)(elm, (head)->sph_root))) { \
1.892 + if (__comp < 0) { \
1.893 + __tmp = SPLAY_LEFT((head)->sph_root, field); \
1.894 + if (__tmp == NULL) \
1.895 + break; \
1.896 + if ((cmp)(elm, __tmp) < 0){ \
1.897 + SPLAY_ROTATE_RIGHT(head, __tmp, field); \
1.898 + if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
1.899 + break; \
1.900 + } \
1.901 + SPLAY_LINKLEFT(head, __right, field); \
1.902 + } else if (__comp > 0) { \
1.903 + __tmp = SPLAY_RIGHT((head)->sph_root, field); \
1.904 + if (__tmp == NULL) \
1.905 + break; \
1.906 + if ((cmp)(elm, __tmp) > 0){ \
1.907 + SPLAY_ROTATE_LEFT(head, __tmp, field); \
1.908 + if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
1.909 + break; \
1.910 + } \
1.911 + SPLAY_LINKRIGHT(head, __left, field); \
1.912 + } \
1.913 + } \
1.914 + SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
1.915 +} \
1.916 + \
1.917 +/* Splay with either the minimum or the maximum element \
1.918 + * Used to find minimum or maximum element in tree. \
1.919 + */ \
1.920 +void name##_SPLAY_MINMAX(struct name *head, int __comp) \
1.921 +{ \
1.922 + struct type __node, *__left, *__right, *__tmp; \
1.923 +\
1.924 + SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
1.925 + __left = __right = &__node; \
1.926 +\
1.927 + while (1) { \
1.928 + if (__comp < 0) { \
1.929 + __tmp = SPLAY_LEFT((head)->sph_root, field); \
1.930 + if (__tmp == NULL) \
1.931 + break; \
1.932 + if (__comp < 0){ \
1.933 + SPLAY_ROTATE_RIGHT(head, __tmp, field); \
1.934 + if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
1.935 + break; \
1.936 + } \
1.937 + SPLAY_LINKLEFT(head, __right, field); \
1.938 + } else if (__comp > 0) { \
1.939 + __tmp = SPLAY_RIGHT((head)->sph_root, field); \
1.940 + if (__tmp == NULL) \
1.941 + break; \
1.942 + if (__comp > 0) { \
1.943 + SPLAY_ROTATE_LEFT(head, __tmp, field); \
1.944 + if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
1.945 + break; \
1.946 + } \
1.947 + SPLAY_LINKRIGHT(head, __left, field); \
1.948 + } \
1.949 + } \
1.950 + SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
1.951 +}
1.952 +
1.953 +#define SPLAY_NEGINF -1
1.954 +#define SPLAY_INF 1
1.955 +
1.956 +#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
1.957 +#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
1.958 +#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
1.959 +#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
1.960 +#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
1.961 + : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
1.962 +#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
1.963 + : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
1.964 +
1.965 +#define SPLAY_FOREACH(x, name, head) \
1.966 + for ((x) = SPLAY_MIN(name, head); \
1.967 + (x) != NULL; \
1.968 + (x) = SPLAY_NEXT(name, head, x))
1.969 +
1.970 +/* Macros that define a red-back tree */
1.971 +#define RB_HEAD(name, type) \
1.972 +struct name { \
1.973 + struct type *rbh_root; /* root of the tree */ \
1.974 +}
1.975 +
1.976 +#define RB_INITIALIZER(root) \
1.977 + { NULL }
1.978 +
1.979 +#define RB_INIT(root) do { \
1.980 + (root)->rbh_root = NULL; \
1.981 +} while (0)
1.982 +
1.983 +#define RB_BLACK 0
1.984 +#define RB_RED 1
1.985 +#define RB_ENTRY(type) \
1.986 +struct { \
1.987 + struct type *rbe_left; /* left element */ \
1.988 + struct type *rbe_right; /* right element */ \
1.989 + struct type *rbe_parent; /* parent element */ \
1.990 + int rbe_color; /* node color */ \
1.991 +}
1.992 +
1.993 +#define RB_LEFT(elm, field) (elm)->field.rbe_left
1.994 +#define RB_RIGHT(elm, field) (elm)->field.rbe_right
1.995 +#define RB_PARENT(elm, field) (elm)->field.rbe_parent
1.996 +#define RB_COLOR(elm, field) (elm)->field.rbe_color
1.997 +#define RB_ROOT(head) (head)->rbh_root
1.998 +#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
1.999 +
1.1000 +#define RB_SET(elm, parent, field) do { \
1.1001 + RB_PARENT(elm, field) = parent; \
1.1002 + RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
1.1003 + RB_COLOR(elm, field) = RB_RED; \
1.1004 +} while (0)
1.1005 +
1.1006 +#define RB_SET_BLACKRED(black, red, field) do { \
1.1007 + RB_COLOR(black, field) = RB_BLACK; \
1.1008 + RB_COLOR(red, field) = RB_RED; \
1.1009 +} while (0)
1.1010 +
1.1011 +#ifndef RB_AUGMENT
1.1012 +#define RB_AUGMENT(x)
1.1013 +#endif
1.1014 +
1.1015 +#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
1.1016 + (tmp) = RB_RIGHT(elm, field); \
1.1017 + if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
1.1018 + RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
1.1019 + } \
1.1020 + RB_AUGMENT(elm); \
1.1021 + if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
1.1022 + if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
1.1023 + RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
1.1024 + else \
1.1025 + RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
1.1026 + } else \
1.1027 + (head)->rbh_root = (tmp); \
1.1028 + RB_LEFT(tmp, field) = (elm); \
1.1029 + RB_PARENT(elm, field) = (tmp); \
1.1030 + RB_AUGMENT(tmp); \
1.1031 + if ((RB_PARENT(tmp, field))) \
1.1032 + RB_AUGMENT(RB_PARENT(tmp, field)); \
1.1033 +} while (0)
1.1034 +
1.1035 +#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
1.1036 + (tmp) = RB_LEFT(elm, field); \
1.1037 + if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
1.1038 + RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
1.1039 + } \
1.1040 + RB_AUGMENT(elm); \
1.1041 + if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
1.1042 + if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
1.1043 + RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
1.1044 + else \
1.1045 + RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
1.1046 + } else \
1.1047 + (head)->rbh_root = (tmp); \
1.1048 + RB_RIGHT(tmp, field) = (elm); \
1.1049 + RB_PARENT(elm, field) = (tmp); \
1.1050 + RB_AUGMENT(tmp); \
1.1051 + if ((RB_PARENT(tmp, field))) \
1.1052 + RB_AUGMENT(RB_PARENT(tmp, field)); \
1.1053 +} while (0)
1.1054 +
1.1055 +/* Generates prototypes and inline functions */
1.1056 +#define RB_PROTOTYPE(name, type, field, cmp) \
1.1057 +void name##_RB_INSERT_COLOR(struct name *, struct type *); \
1.1058 +void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
1.1059 +struct type *name##_RB_REMOVE(struct name *, struct type *); \
1.1060 +struct type *name##_RB_INSERT(struct name *, struct type *); \
1.1061 +struct type *name##_RB_FIND(struct name *, struct type *); \
1.1062 +struct type *name##_RB_NEXT(struct type *); \
1.1063 +struct type *name##_RB_MINMAX(struct name *, int); \
1.1064 + \
1.1065 +
1.1066 +/* Main rb operation.
1.1067 + * Moves node close to the key of elm to top
1.1068 + */
1.1069 +#define RB_GENERATE(name, type, field, cmp) \
1.1070 +void \
1.1071 +name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
1.1072 +{ \
1.1073 + struct type *parent, *gparent, *tmp; \
1.1074 + while ((parent = RB_PARENT(elm, field)) && \
1.1075 + RB_COLOR(parent, field) == RB_RED) { \
1.1076 + gparent = RB_PARENT(parent, field); \
1.1077 + if (parent == RB_LEFT(gparent, field)) { \
1.1078 + tmp = RB_RIGHT(gparent, field); \
1.1079 + if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
1.1080 + RB_COLOR(tmp, field) = RB_BLACK; \
1.1081 + RB_SET_BLACKRED(parent, gparent, field);\
1.1082 + elm = gparent; \
1.1083 + continue; \
1.1084 + } \
1.1085 + if (RB_RIGHT(parent, field) == elm) { \
1.1086 + RB_ROTATE_LEFT(head, parent, tmp, field);\
1.1087 + tmp = parent; \
1.1088 + parent = elm; \
1.1089 + elm = tmp; \
1.1090 + } \
1.1091 + RB_SET_BLACKRED(parent, gparent, field); \
1.1092 + RB_ROTATE_RIGHT(head, gparent, tmp, field); \
1.1093 + } else { \
1.1094 + tmp = RB_LEFT(gparent, field); \
1.1095 + if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
1.1096 + RB_COLOR(tmp, field) = RB_BLACK; \
1.1097 + RB_SET_BLACKRED(parent, gparent, field);\
1.1098 + elm = gparent; \
1.1099 + continue; \
1.1100 + } \
1.1101 + if (RB_LEFT(parent, field) == elm) { \
1.1102 + RB_ROTATE_RIGHT(head, parent, tmp, field);\
1.1103 + tmp = parent; \
1.1104 + parent = elm; \
1.1105 + elm = tmp; \
1.1106 + } \
1.1107 + RB_SET_BLACKRED(parent, gparent, field); \
1.1108 + RB_ROTATE_LEFT(head, gparent, tmp, field); \
1.1109 + } \
1.1110 + } \
1.1111 + RB_COLOR(head->rbh_root, field) = RB_BLACK; \
1.1112 +} \
1.1113 + \
1.1114 +void \
1.1115 +name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
1.1116 +{ \
1.1117 + struct type *tmp; \
1.1118 + while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
1.1119 + elm != RB_ROOT(head)) { \
1.1120 + if (RB_LEFT(parent, field) == elm) { \
1.1121 + tmp = RB_RIGHT(parent, field); \
1.1122 + if (RB_COLOR(tmp, field) == RB_RED) { \
1.1123 + RB_SET_BLACKRED(tmp, parent, field); \
1.1124 + RB_ROTATE_LEFT(head, parent, tmp, field);\
1.1125 + tmp = RB_RIGHT(parent, field); \
1.1126 + } \
1.1127 + if ((RB_LEFT(tmp, field) == NULL || \
1.1128 + RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
1.1129 + (RB_RIGHT(tmp, field) == NULL || \
1.1130 + RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
1.1131 + RB_COLOR(tmp, field) = RB_RED; \
1.1132 + elm = parent; \
1.1133 + parent = RB_PARENT(elm, field); \
1.1134 + } else { \
1.1135 + if (RB_RIGHT(tmp, field) == NULL || \
1.1136 + RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
1.1137 + struct type *oleft; \
1.1138 + if ((oleft = RB_LEFT(tmp, field)))\
1.1139 + RB_COLOR(oleft, field) = RB_BLACK;\
1.1140 + RB_COLOR(tmp, field) = RB_RED; \
1.1141 + RB_ROTATE_RIGHT(head, tmp, oleft, field);\
1.1142 + tmp = RB_RIGHT(parent, field); \
1.1143 + } \
1.1144 + RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
1.1145 + RB_COLOR(parent, field) = RB_BLACK; \
1.1146 + if (RB_RIGHT(tmp, field)) \
1.1147 + RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
1.1148 + RB_ROTATE_LEFT(head, parent, tmp, field);\
1.1149 + elm = RB_ROOT(head); \
1.1150 + break; \
1.1151 + } \
1.1152 + } else { \
1.1153 + tmp = RB_LEFT(parent, field); \
1.1154 + if (RB_COLOR(tmp, field) == RB_RED) { \
1.1155 + RB_SET_BLACKRED(tmp, parent, field); \
1.1156 + RB_ROTATE_RIGHT(head, parent, tmp, field);\
1.1157 + tmp = RB_LEFT(parent, field); \
1.1158 + } \
1.1159 + if ((RB_LEFT(tmp, field) == NULL || \
1.1160 + RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
1.1161 + (RB_RIGHT(tmp, field) == NULL || \
1.1162 + RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
1.1163 + RB_COLOR(tmp, field) = RB_RED; \
1.1164 + elm = parent; \
1.1165 + parent = RB_PARENT(elm, field); \
1.1166 + } else { \
1.1167 + if (RB_LEFT(tmp, field) == NULL || \
1.1168 + RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
1.1169 + struct type *oright; \
1.1170 + if ((oright = RB_RIGHT(tmp, field)))\
1.1171 + RB_COLOR(oright, field) = RB_BLACK;\
1.1172 + RB_COLOR(tmp, field) = RB_RED; \
1.1173 + RB_ROTATE_LEFT(head, tmp, oright, field);\
1.1174 + tmp = RB_LEFT(parent, field); \
1.1175 + } \
1.1176 + RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
1.1177 + RB_COLOR(parent, field) = RB_BLACK; \
1.1178 + if (RB_LEFT(tmp, field)) \
1.1179 + RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
1.1180 + RB_ROTATE_RIGHT(head, parent, tmp, field);\
1.1181 + elm = RB_ROOT(head); \
1.1182 + break; \
1.1183 + } \
1.1184 + } \
1.1185 + } \
1.1186 + if (elm) \
1.1187 + RB_COLOR(elm, field) = RB_BLACK; \
1.1188 +} \
1.1189 + \
1.1190 +struct type * \
1.1191 +name##_RB_REMOVE(struct name *head, struct type *elm) \
1.1192 +{ \
1.1193 + struct type *child, *parent, *old = elm; \
1.1194 + int color; \
1.1195 + if (RB_LEFT(elm, field) == NULL) \
1.1196 + child = RB_RIGHT(elm, field); \
1.1197 + else if (RB_RIGHT(elm, field) == NULL) \
1.1198 + child = RB_LEFT(elm, field); \
1.1199 + else { \
1.1200 + struct type *left; \
1.1201 + elm = RB_RIGHT(elm, field); \
1.1202 + while ((left = RB_LEFT(elm, field))) \
1.1203 + elm = left; \
1.1204 + child = RB_RIGHT(elm, field); \
1.1205 + parent = RB_PARENT(elm, field); \
1.1206 + color = RB_COLOR(elm, field); \
1.1207 + if (child) \
1.1208 + RB_PARENT(child, field) = parent; \
1.1209 + if (parent) { \
1.1210 + if (RB_LEFT(parent, field) == elm) \
1.1211 + RB_LEFT(parent, field) = child; \
1.1212 + else \
1.1213 + RB_RIGHT(parent, field) = child; \
1.1214 + RB_AUGMENT(parent); \
1.1215 + } else \
1.1216 + RB_ROOT(head) = child; \
1.1217 + if (RB_PARENT(elm, field) == old) \
1.1218 + parent = elm; \
1.1219 + (elm)->field = (old)->field; \
1.1220 + if (RB_PARENT(old, field)) { \
1.1221 + if (RB_LEFT(RB_PARENT(old, field), field) == old)\
1.1222 + RB_LEFT(RB_PARENT(old, field), field) = elm;\
1.1223 + else \
1.1224 + RB_RIGHT(RB_PARENT(old, field), field) = elm;\
1.1225 + RB_AUGMENT(RB_PARENT(old, field)); \
1.1226 + } else \
1.1227 + RB_ROOT(head) = elm; \
1.1228 + RB_PARENT(RB_LEFT(old, field), field) = elm; \
1.1229 + if (RB_RIGHT(old, field)) \
1.1230 + RB_PARENT(RB_RIGHT(old, field), field) = elm; \
1.1231 + if (parent) { \
1.1232 + left = parent; \
1.1233 + do { \
1.1234 + RB_AUGMENT(left); \
1.1235 + } while ((left = RB_PARENT(left, field))); \
1.1236 + } \
1.1237 + goto color; \
1.1238 + } \
1.1239 + parent = RB_PARENT(elm, field); \
1.1240 + color = RB_COLOR(elm, field); \
1.1241 + if (child) \
1.1242 + RB_PARENT(child, field) = parent; \
1.1243 + if (parent) { \
1.1244 + if (RB_LEFT(parent, field) == elm) \
1.1245 + RB_LEFT(parent, field) = child; \
1.1246 + else \
1.1247 + RB_RIGHT(parent, field) = child; \
1.1248 + RB_AUGMENT(parent); \
1.1249 + } else \
1.1250 + RB_ROOT(head) = child; \
1.1251 +color: \
1.1252 + if (color == RB_BLACK) \
1.1253 + name##_RB_REMOVE_COLOR(head, parent, child); \
1.1254 + return (old); \
1.1255 +} \
1.1256 + \
1.1257 +/* Inserts a node into the RB tree */ \
1.1258 +struct type * \
1.1259 +name##_RB_INSERT(struct name *head, struct type *elm) \
1.1260 +{ \
1.1261 + struct type *tmp; \
1.1262 + struct type *parent = NULL; \
1.1263 + int comp = 0; \
1.1264 + tmp = RB_ROOT(head); \
1.1265 + while (tmp) { \
1.1266 + parent = tmp; \
1.1267 + comp = (cmp)(elm, parent); \
1.1268 + if (comp < 0) \
1.1269 + tmp = RB_LEFT(tmp, field); \
1.1270 + else if (comp > 0) \
1.1271 + tmp = RB_RIGHT(tmp, field); \
1.1272 + else \
1.1273 + return (tmp); \
1.1274 + } \
1.1275 + RB_SET(elm, parent, field); \
1.1276 + if (parent != NULL) { \
1.1277 + if (comp < 0) \
1.1278 + RB_LEFT(parent, field) = elm; \
1.1279 + else \
1.1280 + RB_RIGHT(parent, field) = elm; \
1.1281 + RB_AUGMENT(parent); \
1.1282 + } else \
1.1283 + RB_ROOT(head) = elm; \
1.1284 + name##_RB_INSERT_COLOR(head, elm); \
1.1285 + return (NULL); \
1.1286 +} \
1.1287 + \
1.1288 +/* Finds the node with the same key as elm */ \
1.1289 +struct type * \
1.1290 +name##_RB_FIND(struct name *head, struct type *elm) \
1.1291 +{ \
1.1292 + struct type *tmp = RB_ROOT(head); \
1.1293 + int comp; \
1.1294 + while (tmp) { \
1.1295 + comp = cmp(elm, tmp); \
1.1296 + if (comp < 0) \
1.1297 + tmp = RB_LEFT(tmp, field); \
1.1298 + else if (comp > 0) \
1.1299 + tmp = RB_RIGHT(tmp, field); \
1.1300 + else \
1.1301 + return (tmp); \
1.1302 + } \
1.1303 + return (NULL); \
1.1304 +} \
1.1305 + \
1.1306 +struct type * \
1.1307 +name##_RB_NEXT(struct type *elm) \
1.1308 +{ \
1.1309 + if (RB_RIGHT(elm, field)) { \
1.1310 + elm = RB_RIGHT(elm, field); \
1.1311 + while (RB_LEFT(elm, field)) \
1.1312 + elm = RB_LEFT(elm, field); \
1.1313 + } else { \
1.1314 + if (RB_PARENT(elm, field) && \
1.1315 + (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
1.1316 + elm = RB_PARENT(elm, field); \
1.1317 + else { \
1.1318 + while (RB_PARENT(elm, field) && \
1.1319 + (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
1.1320 + elm = RB_PARENT(elm, field); \
1.1321 + elm = RB_PARENT(elm, field); \
1.1322 + } \
1.1323 + } \
1.1324 + return (elm); \
1.1325 +} \
1.1326 + \
1.1327 +struct type * \
1.1328 +name##_RB_MINMAX(struct name *head, int val) \
1.1329 +{ \
1.1330 + struct type *tmp = RB_ROOT(head); \
1.1331 + struct type *parent = NULL; \
1.1332 + while (tmp) { \
1.1333 + parent = tmp; \
1.1334 + if (val < 0) \
1.1335 + tmp = RB_LEFT(tmp, field); \
1.1336 + else \
1.1337 + tmp = RB_RIGHT(tmp, field); \
1.1338 + } \
1.1339 + return (parent); \
1.1340 +}
1.1341 +
1.1342 +#define RB_NEGINF -1
1.1343 +#define RB_INF 1
1.1344 +
1.1345 +#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
1.1346 +#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
1.1347 +#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
1.1348 +#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
1.1349 +#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
1.1350 +#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
1.1351 +
1.1352 +#define RB_FOREACH(x, name, head) \
1.1353 + for ((x) = RB_MIN(name, head); \
1.1354 + (x) != NULL; \
1.1355 + (x) = name##_RB_NEXT(x))
1.1356 +
1.1357 +#endif /* _SYS_TREE_H_ */
