17777dab0Sopenharmony_ci/*- 27777dab0Sopenharmony_ci * Copyright 2002 Niels Provos <provos@citi.umich.edu> 37777dab0Sopenharmony_ci * All rights reserved. 47777dab0Sopenharmony_ci * 57777dab0Sopenharmony_ci * Redistribution and use in source and binary forms, with or without 67777dab0Sopenharmony_ci * modification, are permitted provided that the following conditions 77777dab0Sopenharmony_ci * are met: 87777dab0Sopenharmony_ci * 1. Redistributions of source code must retain the above copyright 97777dab0Sopenharmony_ci * notice, this list of conditions and the following disclaimer. 107777dab0Sopenharmony_ci * 2. Redistributions in binary form must reproduce the above copyright 117777dab0Sopenharmony_ci * notice, this list of conditions and the following disclaimer in the 127777dab0Sopenharmony_ci * documentation and/or other materials provided with the distribution. 137777dab0Sopenharmony_ci * 147777dab0Sopenharmony_ci * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 157777dab0Sopenharmony_ci * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 167777dab0Sopenharmony_ci * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 177777dab0Sopenharmony_ci * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 187777dab0Sopenharmony_ci * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 197777dab0Sopenharmony_ci * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 207777dab0Sopenharmony_ci * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 217777dab0Sopenharmony_ci * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 227777dab0Sopenharmony_ci * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 237777dab0Sopenharmony_ci * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 247777dab0Sopenharmony_ci */ 257777dab0Sopenharmony_ci 267777dab0Sopenharmony_ci#ifndef UV_TREE_H_ 277777dab0Sopenharmony_ci#define UV_TREE_H_ 287777dab0Sopenharmony_ci 297777dab0Sopenharmony_ci#ifndef UV__UNUSED 307777dab0Sopenharmony_ci# if __GNUC__ 317777dab0Sopenharmony_ci# define UV__UNUSED __attribute__((unused)) 327777dab0Sopenharmony_ci# else 337777dab0Sopenharmony_ci# define UV__UNUSED 347777dab0Sopenharmony_ci# endif 357777dab0Sopenharmony_ci#endif 367777dab0Sopenharmony_ci 377777dab0Sopenharmony_ci/* 387777dab0Sopenharmony_ci * This file defines data structures for different types of trees: 397777dab0Sopenharmony_ci * splay trees and red-black trees. 407777dab0Sopenharmony_ci * 417777dab0Sopenharmony_ci * A splay tree is a self-organizing data structure. Every operation 427777dab0Sopenharmony_ci * on the tree causes a splay to happen. The splay moves the requested 437777dab0Sopenharmony_ci * node to the root of the tree and partly rebalances it. 447777dab0Sopenharmony_ci * 457777dab0Sopenharmony_ci * This has the benefit that request locality causes faster lookups as 467777dab0Sopenharmony_ci * the requested nodes move to the top of the tree. On the other hand, 477777dab0Sopenharmony_ci * every lookup causes memory writes. 487777dab0Sopenharmony_ci * 497777dab0Sopenharmony_ci * The Balance Theorem bounds the total access time for m operations 507777dab0Sopenharmony_ci * and n inserts on an initially empty tree as O((m + n)lg n). The 517777dab0Sopenharmony_ci * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 527777dab0Sopenharmony_ci * 537777dab0Sopenharmony_ci * A red-black tree is a binary search tree with the node color as an 547777dab0Sopenharmony_ci * extra attribute. It fulfills a set of conditions: 557777dab0Sopenharmony_ci * - every search path from the root to a leaf consists of the 567777dab0Sopenharmony_ci * same number of black nodes, 577777dab0Sopenharmony_ci * - each red node (except for the root) has a black parent, 587777dab0Sopenharmony_ci * - each leaf node is black. 597777dab0Sopenharmony_ci * 607777dab0Sopenharmony_ci * Every operation on a red-black tree is bounded as O(lg n). 617777dab0Sopenharmony_ci * The maximum height of a red-black tree is 2lg (n+1). 627777dab0Sopenharmony_ci */ 637777dab0Sopenharmony_ci 647777dab0Sopenharmony_ci#define SPLAY_HEAD(name, type) \ 657777dab0Sopenharmony_cistruct name { \ 667777dab0Sopenharmony_ci struct type *sph_root; /* root of the tree */ \ 677777dab0Sopenharmony_ci} 687777dab0Sopenharmony_ci 697777dab0Sopenharmony_ci#define SPLAY_INITIALIZER(root) \ 707777dab0Sopenharmony_ci { NULL } 717777dab0Sopenharmony_ci 727777dab0Sopenharmony_ci#define SPLAY_INIT(root) do { \ 737777dab0Sopenharmony_ci (root)->sph_root = NULL; \ 747777dab0Sopenharmony_ci} while (/*CONSTCOND*/ 0) 757777dab0Sopenharmony_ci 767777dab0Sopenharmony_ci#define SPLAY_ENTRY(type) \ 777777dab0Sopenharmony_cistruct { \ 787777dab0Sopenharmony_ci struct type *spe_left; /* left element */ \ 797777dab0Sopenharmony_ci struct type *spe_right; /* right element */ \ 807777dab0Sopenharmony_ci} 817777dab0Sopenharmony_ci 827777dab0Sopenharmony_ci#define SPLAY_LEFT(elm, field) (elm)->field.spe_left 837777dab0Sopenharmony_ci#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 847777dab0Sopenharmony_ci#define SPLAY_ROOT(head) (head)->sph_root 857777dab0Sopenharmony_ci#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 867777dab0Sopenharmony_ci 877777dab0Sopenharmony_ci/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 887777dab0Sopenharmony_ci#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 897777dab0Sopenharmony_ci SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 907777dab0Sopenharmony_ci SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 917777dab0Sopenharmony_ci (head)->sph_root = tmp; \ 927777dab0Sopenharmony_ci} while (/*CONSTCOND*/ 0) 937777dab0Sopenharmony_ci 947777dab0Sopenharmony_ci#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 957777dab0Sopenharmony_ci SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 967777dab0Sopenharmony_ci SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 977777dab0Sopenharmony_ci (head)->sph_root = tmp; \ 987777dab0Sopenharmony_ci} while (/*CONSTCOND*/ 0) 997777dab0Sopenharmony_ci 1007777dab0Sopenharmony_ci#define SPLAY_LINKLEFT(head, tmp, field) do { \ 1017777dab0Sopenharmony_ci SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 1027777dab0Sopenharmony_ci tmp = (head)->sph_root; \ 1037777dab0Sopenharmony_ci (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 1047777dab0Sopenharmony_ci} while (/*CONSTCOND*/ 0) 1057777dab0Sopenharmony_ci 1067777dab0Sopenharmony_ci#define SPLAY_LINKRIGHT(head, tmp, field) do { \ 1077777dab0Sopenharmony_ci SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 1087777dab0Sopenharmony_ci tmp = (head)->sph_root; \ 1097777dab0Sopenharmony_ci (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 1107777dab0Sopenharmony_ci} while (/*CONSTCOND*/ 0) 1117777dab0Sopenharmony_ci 1127777dab0Sopenharmony_ci#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 1137777dab0Sopenharmony_ci SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 1147777dab0Sopenharmony_ci SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field); \ 1157777dab0Sopenharmony_ci SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 1167777dab0Sopenharmony_ci SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 1177777dab0Sopenharmony_ci} while (/*CONSTCOND*/ 0) 1187777dab0Sopenharmony_ci 1197777dab0Sopenharmony_ci/* Generates prototypes and inline functions */ 1207777dab0Sopenharmony_ci 1217777dab0Sopenharmony_ci#define SPLAY_PROTOTYPE(name, type, field, cmp) \ 1227777dab0Sopenharmony_civoid name##_SPLAY(struct name *, struct type *); \ 1237777dab0Sopenharmony_civoid name##_SPLAY_MINMAX(struct name *, int); \ 1247777dab0Sopenharmony_cistruct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 1257777dab0Sopenharmony_cistruct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 1267777dab0Sopenharmony_ci \ 1277777dab0Sopenharmony_ci/* Finds the node with the same key as elm */ \ 1287777dab0Sopenharmony_cistatic __inline struct type * \ 1297777dab0Sopenharmony_ciname##_SPLAY_FIND(struct name *head, struct type *elm) \ 1307777dab0Sopenharmony_ci{ \ 1317777dab0Sopenharmony_ci if (SPLAY_EMPTY(head)) \ 1327777dab0Sopenharmony_ci return(NULL); \ 1337777dab0Sopenharmony_ci name##_SPLAY(head, elm); \ 1347777dab0Sopenharmony_ci if ((cmp)(elm, (head)->sph_root) == 0) \ 1357777dab0Sopenharmony_ci return (head->sph_root); \ 1367777dab0Sopenharmony_ci return (NULL); \ 1377777dab0Sopenharmony_ci} \ 1387777dab0Sopenharmony_ci \ 1397777dab0Sopenharmony_cistatic __inline struct type * \ 1407777dab0Sopenharmony_ciname##_SPLAY_NEXT(struct name *head, struct type *elm) \ 1417777dab0Sopenharmony_ci{ \ 1427777dab0Sopenharmony_ci name##_SPLAY(head, elm); \ 1437777dab0Sopenharmony_ci if (SPLAY_RIGHT(elm, field) != NULL) { \ 1447777dab0Sopenharmony_ci elm = SPLAY_RIGHT(elm, field); \ 1457777dab0Sopenharmony_ci while (SPLAY_LEFT(elm, field) != NULL) { \ 1467777dab0Sopenharmony_ci elm = SPLAY_LEFT(elm, field); \ 1477777dab0Sopenharmony_ci } \ 1487777dab0Sopenharmony_ci } else \ 1497777dab0Sopenharmony_ci elm = NULL; \ 1507777dab0Sopenharmony_ci return (elm); \ 1517777dab0Sopenharmony_ci} \ 1527777dab0Sopenharmony_ci \ 1537777dab0Sopenharmony_cistatic __inline struct type * \ 1547777dab0Sopenharmony_ciname##_SPLAY_MIN_MAX(struct name *head, int val) \ 1557777dab0Sopenharmony_ci{ \ 1567777dab0Sopenharmony_ci name##_SPLAY_MINMAX(head, val); \ 1577777dab0Sopenharmony_ci return (SPLAY_ROOT(head)); \ 1587777dab0Sopenharmony_ci} 1597777dab0Sopenharmony_ci 1607777dab0Sopenharmony_ci/* Main splay operation. 1617777dab0Sopenharmony_ci * Moves node close to the key of elm to top 1627777dab0Sopenharmony_ci */ 1637777dab0Sopenharmony_ci#define SPLAY_GENERATE(name, type, field, cmp) \ 1647777dab0Sopenharmony_cistruct type * \ 1657777dab0Sopenharmony_ciname##_SPLAY_INSERT(struct name *head, struct type *elm) \ 1667777dab0Sopenharmony_ci{ \ 1677777dab0Sopenharmony_ci if (SPLAY_EMPTY(head)) { \ 1687777dab0Sopenharmony_ci SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 1697777dab0Sopenharmony_ci } else { \ 1707777dab0Sopenharmony_ci int __comp; \ 1717777dab0Sopenharmony_ci name##_SPLAY(head, elm); \ 1727777dab0Sopenharmony_ci __comp = (cmp)(elm, (head)->sph_root); \ 1737777dab0Sopenharmony_ci if(__comp < 0) { \ 1747777dab0Sopenharmony_ci SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field); \ 1757777dab0Sopenharmony_ci SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 1767777dab0Sopenharmony_ci SPLAY_LEFT((head)->sph_root, field) = NULL; \ 1777777dab0Sopenharmony_ci } else if (__comp > 0) { \ 1787777dab0Sopenharmony_ci SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field); \ 1797777dab0Sopenharmony_ci SPLAY_LEFT(elm, field) = (head)->sph_root; \ 1807777dab0Sopenharmony_ci SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 1817777dab0Sopenharmony_ci } else \ 1827777dab0Sopenharmony_ci return ((head)->sph_root); \ 1837777dab0Sopenharmony_ci } \ 1847777dab0Sopenharmony_ci (head)->sph_root = (elm); \ 1857777dab0Sopenharmony_ci return (NULL); \ 1867777dab0Sopenharmony_ci} \ 1877777dab0Sopenharmony_ci \ 1887777dab0Sopenharmony_cistruct type * \ 1897777dab0Sopenharmony_ciname##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 1907777dab0Sopenharmony_ci{ \ 1917777dab0Sopenharmony_ci struct type *__tmp; \ 1927777dab0Sopenharmony_ci if (SPLAY_EMPTY(head)) \ 1937777dab0Sopenharmony_ci return (NULL); \ 1947777dab0Sopenharmony_ci name##_SPLAY(head, elm); \ 1957777dab0Sopenharmony_ci if ((cmp)(elm, (head)->sph_root) == 0) { \ 1967777dab0Sopenharmony_ci if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 1977777dab0Sopenharmony_ci (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 1987777dab0Sopenharmony_ci } else { \ 1997777dab0Sopenharmony_ci __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 2007777dab0Sopenharmony_ci (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 2017777dab0Sopenharmony_ci name##_SPLAY(head, elm); \ 2027777dab0Sopenharmony_ci SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 2037777dab0Sopenharmony_ci } \ 2047777dab0Sopenharmony_ci return (elm); \ 2057777dab0Sopenharmony_ci } \ 2067777dab0Sopenharmony_ci return (NULL); \ 2077777dab0Sopenharmony_ci} \ 2087777dab0Sopenharmony_ci \ 2097777dab0Sopenharmony_civoid \ 2107777dab0Sopenharmony_ciname##_SPLAY(struct name *head, struct type *elm) \ 2117777dab0Sopenharmony_ci{ \ 2127777dab0Sopenharmony_ci struct type __node, *__left, *__right, *__tmp; \ 2137777dab0Sopenharmony_ci int __comp; \ 2147777dab0Sopenharmony_ci \ 2157777dab0Sopenharmony_ci SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ 2167777dab0Sopenharmony_ci __left = __right = &__node; \ 2177777dab0Sopenharmony_ci \ 2187777dab0Sopenharmony_ci while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 2197777dab0Sopenharmony_ci if (__comp < 0) { \ 2207777dab0Sopenharmony_ci __tmp = SPLAY_LEFT((head)->sph_root, field); \ 2217777dab0Sopenharmony_ci if (__tmp == NULL) \ 2227777dab0Sopenharmony_ci break; \ 2237777dab0Sopenharmony_ci if ((cmp)(elm, __tmp) < 0){ \ 2247777dab0Sopenharmony_ci SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 2257777dab0Sopenharmony_ci if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ 2267777dab0Sopenharmony_ci break; \ 2277777dab0Sopenharmony_ci } \ 2287777dab0Sopenharmony_ci SPLAY_LINKLEFT(head, __right, field); \ 2297777dab0Sopenharmony_ci } else if (__comp > 0) { \ 2307777dab0Sopenharmony_ci __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 2317777dab0Sopenharmony_ci if (__tmp == NULL) \ 2327777dab0Sopenharmony_ci break; \ 2337777dab0Sopenharmony_ci if ((cmp)(elm, __tmp) > 0){ \ 2347777dab0Sopenharmony_ci SPLAY_ROTATE_LEFT(head, __tmp, field); \ 2357777dab0Sopenharmony_ci if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ 2367777dab0Sopenharmony_ci break; \ 2377777dab0Sopenharmony_ci } \ 2387777dab0Sopenharmony_ci SPLAY_LINKRIGHT(head, __left, field); \ 2397777dab0Sopenharmony_ci } \ 2407777dab0Sopenharmony_ci } \ 2417777dab0Sopenharmony_ci SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 2427777dab0Sopenharmony_ci} \ 2437777dab0Sopenharmony_ci \ 2447777dab0Sopenharmony_ci/* Splay with either the minimum or the maximum element \ 2457777dab0Sopenharmony_ci * Used to find minimum or maximum element in tree. \ 2467777dab0Sopenharmony_ci */ \ 2477777dab0Sopenharmony_civoid name##_SPLAY_MINMAX(struct name *head, int __comp) \ 2487777dab0Sopenharmony_ci{ \ 2497777dab0Sopenharmony_ci struct type __node, *__left, *__right, *__tmp; \ 2507777dab0Sopenharmony_ci \ 2517777dab0Sopenharmony_ci SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ 2527777dab0Sopenharmony_ci __left = __right = &__node; \ 2537777dab0Sopenharmony_ci \ 2547777dab0Sopenharmony_ci for (;;) { \ 2557777dab0Sopenharmony_ci if (__comp < 0) { \ 2567777dab0Sopenharmony_ci __tmp = SPLAY_LEFT((head)->sph_root, field); \ 2577777dab0Sopenharmony_ci if (__tmp == NULL) \ 2587777dab0Sopenharmony_ci break; \ 2597777dab0Sopenharmony_ci if (__comp < 0){ \ 2607777dab0Sopenharmony_ci SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 2617777dab0Sopenharmony_ci if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ 2627777dab0Sopenharmony_ci break; \ 2637777dab0Sopenharmony_ci } \ 2647777dab0Sopenharmony_ci SPLAY_LINKLEFT(head, __right, field); \ 2657777dab0Sopenharmony_ci } else if (__comp > 0) { \ 2667777dab0Sopenharmony_ci __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 2677777dab0Sopenharmony_ci if (__tmp == NULL) \ 2687777dab0Sopenharmony_ci break; \ 2697777dab0Sopenharmony_ci if (__comp > 0) { \ 2707777dab0Sopenharmony_ci SPLAY_ROTATE_LEFT(head, __tmp, field); \ 2717777dab0Sopenharmony_ci if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ 2727777dab0Sopenharmony_ci break; \ 2737777dab0Sopenharmony_ci } \ 2747777dab0Sopenharmony_ci SPLAY_LINKRIGHT(head, __left, field); \ 2757777dab0Sopenharmony_ci } \ 2767777dab0Sopenharmony_ci } \ 2777777dab0Sopenharmony_ci SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 2787777dab0Sopenharmony_ci} 2797777dab0Sopenharmony_ci 2807777dab0Sopenharmony_ci#define SPLAY_NEGINF -1 2817777dab0Sopenharmony_ci#define SPLAY_INF 1 2827777dab0Sopenharmony_ci 2837777dab0Sopenharmony_ci#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 2847777dab0Sopenharmony_ci#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 2857777dab0Sopenharmony_ci#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 2867777dab0Sopenharmony_ci#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 2877777dab0Sopenharmony_ci#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 2887777dab0Sopenharmony_ci : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 2897777dab0Sopenharmony_ci#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 2907777dab0Sopenharmony_ci : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 2917777dab0Sopenharmony_ci 2927777dab0Sopenharmony_ci#define SPLAY_FOREACH(x, name, head) \ 2937777dab0Sopenharmony_ci for ((x) = SPLAY_MIN(name, head); \ 2947777dab0Sopenharmony_ci (x) != NULL; \ 2957777dab0Sopenharmony_ci (x) = SPLAY_NEXT(name, head, x)) 2967777dab0Sopenharmony_ci 2977777dab0Sopenharmony_ci/* Macros that define a red-black tree */ 2987777dab0Sopenharmony_ci#define RB_HEAD(name, type) \ 2997777dab0Sopenharmony_cistruct name { \ 3007777dab0Sopenharmony_ci struct type *rbh_root; /* root of the tree */ \ 3017777dab0Sopenharmony_ci} 3027777dab0Sopenharmony_ci 3037777dab0Sopenharmony_ci#define RB_INITIALIZER(root) \ 3047777dab0Sopenharmony_ci { NULL } 3057777dab0Sopenharmony_ci 3067777dab0Sopenharmony_ci#define RB_INIT(root) do { \ 3077777dab0Sopenharmony_ci (root)->rbh_root = NULL; \ 3087777dab0Sopenharmony_ci} while (/*CONSTCOND*/ 0) 3097777dab0Sopenharmony_ci 3107777dab0Sopenharmony_ci#define RB_BLACK 0 3117777dab0Sopenharmony_ci#define RB_RED 1 3127777dab0Sopenharmony_ci#define RB_ENTRY(type) \ 3137777dab0Sopenharmony_cistruct { \ 3147777dab0Sopenharmony_ci struct type *rbe_left; /* left element */ \ 3157777dab0Sopenharmony_ci struct type *rbe_right; /* right element */ \ 3167777dab0Sopenharmony_ci struct type *rbe_parent; /* parent element */ \ 3177777dab0Sopenharmony_ci int rbe_color; /* node color */ \ 3187777dab0Sopenharmony_ci} 3197777dab0Sopenharmony_ci 3207777dab0Sopenharmony_ci#define RB_LEFT(elm, field) (elm)->field.rbe_left 3217777dab0Sopenharmony_ci#define RB_RIGHT(elm, field) (elm)->field.rbe_right 3227777dab0Sopenharmony_ci#define RB_PARENT(elm, field) (elm)->field.rbe_parent 3237777dab0Sopenharmony_ci#define RB_COLOR(elm, field) (elm)->field.rbe_color 3247777dab0Sopenharmony_ci#define RB_ROOT(head) (head)->rbh_root 3257777dab0Sopenharmony_ci#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 3267777dab0Sopenharmony_ci 3277777dab0Sopenharmony_ci#define RB_SET(elm, parent, field) do { \ 3287777dab0Sopenharmony_ci RB_PARENT(elm, field) = parent; \ 3297777dab0Sopenharmony_ci RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 3307777dab0Sopenharmony_ci RB_COLOR(elm, field) = RB_RED; \ 3317777dab0Sopenharmony_ci} while (/*CONSTCOND*/ 0) 3327777dab0Sopenharmony_ci 3337777dab0Sopenharmony_ci#define RB_SET_BLACKRED(black, red, field) do { \ 3347777dab0Sopenharmony_ci RB_COLOR(black, field) = RB_BLACK; \ 3357777dab0Sopenharmony_ci RB_COLOR(red, field) = RB_RED; \ 3367777dab0Sopenharmony_ci} while (/*CONSTCOND*/ 0) 3377777dab0Sopenharmony_ci 3387777dab0Sopenharmony_ci#ifndef RB_AUGMENT 3397777dab0Sopenharmony_ci#define RB_AUGMENT(x) do {} while (0) 3407777dab0Sopenharmony_ci#endif 3417777dab0Sopenharmony_ci 3427777dab0Sopenharmony_ci#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 3437777dab0Sopenharmony_ci (tmp) = RB_RIGHT(elm, field); \ 3447777dab0Sopenharmony_ci if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 3457777dab0Sopenharmony_ci RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 3467777dab0Sopenharmony_ci } \ 3477777dab0Sopenharmony_ci RB_AUGMENT(elm); \ 3487777dab0Sopenharmony_ci if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 3497777dab0Sopenharmony_ci if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 3507777dab0Sopenharmony_ci RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 3517777dab0Sopenharmony_ci else \ 3527777dab0Sopenharmony_ci RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 3537777dab0Sopenharmony_ci } else \ 3547777dab0Sopenharmony_ci (head)->rbh_root = (tmp); \ 3557777dab0Sopenharmony_ci RB_LEFT(tmp, field) = (elm); \ 3567777dab0Sopenharmony_ci RB_PARENT(elm, field) = (tmp); \ 3577777dab0Sopenharmony_ci RB_AUGMENT(tmp); \ 3587777dab0Sopenharmony_ci if ((RB_PARENT(tmp, field))) \ 3597777dab0Sopenharmony_ci RB_AUGMENT(RB_PARENT(tmp, field)); \ 3607777dab0Sopenharmony_ci} while (/*CONSTCOND*/ 0) 3617777dab0Sopenharmony_ci 3627777dab0Sopenharmony_ci#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 3637777dab0Sopenharmony_ci (tmp) = RB_LEFT(elm, field); \ 3647777dab0Sopenharmony_ci if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 3657777dab0Sopenharmony_ci RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 3667777dab0Sopenharmony_ci } \ 3677777dab0Sopenharmony_ci RB_AUGMENT(elm); \ 3687777dab0Sopenharmony_ci if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 3697777dab0Sopenharmony_ci if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 3707777dab0Sopenharmony_ci RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 3717777dab0Sopenharmony_ci else \ 3727777dab0Sopenharmony_ci RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 3737777dab0Sopenharmony_ci } else \ 3747777dab0Sopenharmony_ci (head)->rbh_root = (tmp); \ 3757777dab0Sopenharmony_ci RB_RIGHT(tmp, field) = (elm); \ 3767777dab0Sopenharmony_ci RB_PARENT(elm, field) = (tmp); \ 3777777dab0Sopenharmony_ci RB_AUGMENT(tmp); \ 3787777dab0Sopenharmony_ci if ((RB_PARENT(tmp, field))) \ 3797777dab0Sopenharmony_ci RB_AUGMENT(RB_PARENT(tmp, field)); \ 3807777dab0Sopenharmony_ci} while (/*CONSTCOND*/ 0) 3817777dab0Sopenharmony_ci 3827777dab0Sopenharmony_ci/* Generates prototypes and inline functions */ 3837777dab0Sopenharmony_ci#define RB_PROTOTYPE(name, type, field, cmp) \ 3847777dab0Sopenharmony_ci RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 3857777dab0Sopenharmony_ci#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 3867777dab0Sopenharmony_ci RB_PROTOTYPE_INTERNAL(name, type, field, cmp, UV__UNUSED static) 3877777dab0Sopenharmony_ci#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 3887777dab0Sopenharmony_ciattr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 3897777dab0Sopenharmony_ciattr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 3907777dab0Sopenharmony_ciattr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 3917777dab0Sopenharmony_ciattr struct type *name##_RB_INSERT(struct name *, struct type *); \ 3927777dab0Sopenharmony_ciattr struct type *name##_RB_FIND(struct name *, struct type *); \ 3937777dab0Sopenharmony_ciattr struct type *name##_RB_NFIND(struct name *, struct type *); \ 3947777dab0Sopenharmony_ciattr struct type *name##_RB_NEXT(struct type *); \ 3957777dab0Sopenharmony_ciattr struct type *name##_RB_PREV(struct type *); \ 3967777dab0Sopenharmony_ciattr struct type *name##_RB_MINMAX(struct name *, int); \ 3977777dab0Sopenharmony_ci \ 3987777dab0Sopenharmony_ci 3997777dab0Sopenharmony_ci/* Main rb operation. 4007777dab0Sopenharmony_ci * Moves node close to the key of elm to top 4017777dab0Sopenharmony_ci */ 4027777dab0Sopenharmony_ci#define RB_GENERATE(name, type, field, cmp) \ 4037777dab0Sopenharmony_ci RB_GENERATE_INTERNAL(name, type, field, cmp,) 4047777dab0Sopenharmony_ci#define RB_GENERATE_STATIC(name, type, field, cmp) \ 4057777dab0Sopenharmony_ci RB_GENERATE_INTERNAL(name, type, field, cmp, UV__UNUSED static) 4067777dab0Sopenharmony_ci#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 4077777dab0Sopenharmony_ciattr void \ 4087777dab0Sopenharmony_ciname##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 4097777dab0Sopenharmony_ci{ \ 4107777dab0Sopenharmony_ci struct type *parent, *gparent, *tmp; \ 4117777dab0Sopenharmony_ci while ((parent = RB_PARENT(elm, field)) != NULL && \ 4127777dab0Sopenharmony_ci RB_COLOR(parent, field) == RB_RED) { \ 4137777dab0Sopenharmony_ci gparent = RB_PARENT(parent, field); \ 4147777dab0Sopenharmony_ci if (parent == RB_LEFT(gparent, field)) { \ 4157777dab0Sopenharmony_ci tmp = RB_RIGHT(gparent, field); \ 4167777dab0Sopenharmony_ci if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 4177777dab0Sopenharmony_ci RB_COLOR(tmp, field) = RB_BLACK; \ 4187777dab0Sopenharmony_ci RB_SET_BLACKRED(parent, gparent, field); \ 4197777dab0Sopenharmony_ci elm = gparent; \ 4207777dab0Sopenharmony_ci continue; \ 4217777dab0Sopenharmony_ci } \ 4227777dab0Sopenharmony_ci if (RB_RIGHT(parent, field) == elm) { \ 4237777dab0Sopenharmony_ci RB_ROTATE_LEFT(head, parent, tmp, field); \ 4247777dab0Sopenharmony_ci tmp = parent; \ 4257777dab0Sopenharmony_ci parent = elm; \ 4267777dab0Sopenharmony_ci elm = tmp; \ 4277777dab0Sopenharmony_ci } \ 4287777dab0Sopenharmony_ci RB_SET_BLACKRED(parent, gparent, field); \ 4297777dab0Sopenharmony_ci RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 4307777dab0Sopenharmony_ci } else { \ 4317777dab0Sopenharmony_ci tmp = RB_LEFT(gparent, field); \ 4327777dab0Sopenharmony_ci if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 4337777dab0Sopenharmony_ci RB_COLOR(tmp, field) = RB_BLACK; \ 4347777dab0Sopenharmony_ci RB_SET_BLACKRED(parent, gparent, field); \ 4357777dab0Sopenharmony_ci elm = gparent; \ 4367777dab0Sopenharmony_ci continue; \ 4377777dab0Sopenharmony_ci } \ 4387777dab0Sopenharmony_ci if (RB_LEFT(parent, field) == elm) { \ 4397777dab0Sopenharmony_ci RB_ROTATE_RIGHT(head, parent, tmp, field); \ 4407777dab0Sopenharmony_ci tmp = parent; \ 4417777dab0Sopenharmony_ci parent = elm; \ 4427777dab0Sopenharmony_ci elm = tmp; \ 4437777dab0Sopenharmony_ci } \ 4447777dab0Sopenharmony_ci RB_SET_BLACKRED(parent, gparent, field); \ 4457777dab0Sopenharmony_ci RB_ROTATE_LEFT(head, gparent, tmp, field); \ 4467777dab0Sopenharmony_ci } \ 4477777dab0Sopenharmony_ci } \ 4487777dab0Sopenharmony_ci RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 4497777dab0Sopenharmony_ci} \ 4507777dab0Sopenharmony_ci \ 4517777dab0Sopenharmony_ciattr void \ 4527777dab0Sopenharmony_ciname##_RB_REMOVE_COLOR(struct name *head, struct type *parent, \ 4537777dab0Sopenharmony_ci struct type *elm) \ 4547777dab0Sopenharmony_ci{ \ 4557777dab0Sopenharmony_ci struct type *tmp; \ 4567777dab0Sopenharmony_ci while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 4577777dab0Sopenharmony_ci elm != RB_ROOT(head)) { \ 4587777dab0Sopenharmony_ci if (RB_LEFT(parent, field) == elm) { \ 4597777dab0Sopenharmony_ci tmp = RB_RIGHT(parent, field); \ 4607777dab0Sopenharmony_ci if (RB_COLOR(tmp, field) == RB_RED) { \ 4617777dab0Sopenharmony_ci RB_SET_BLACKRED(tmp, parent, field); \ 4627777dab0Sopenharmony_ci RB_ROTATE_LEFT(head, parent, tmp, field); \ 4637777dab0Sopenharmony_ci tmp = RB_RIGHT(parent, field); \ 4647777dab0Sopenharmony_ci } \ 4657777dab0Sopenharmony_ci if ((RB_LEFT(tmp, field) == NULL || \ 4667777dab0Sopenharmony_ci RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 4677777dab0Sopenharmony_ci (RB_RIGHT(tmp, field) == NULL || \ 4687777dab0Sopenharmony_ci RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 4697777dab0Sopenharmony_ci RB_COLOR(tmp, field) = RB_RED; \ 4707777dab0Sopenharmony_ci elm = parent; \ 4717777dab0Sopenharmony_ci parent = RB_PARENT(elm, field); \ 4727777dab0Sopenharmony_ci } else { \ 4737777dab0Sopenharmony_ci if (RB_RIGHT(tmp, field) == NULL || \ 4747777dab0Sopenharmony_ci RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \ 4757777dab0Sopenharmony_ci struct type *oleft; \ 4767777dab0Sopenharmony_ci if ((oleft = RB_LEFT(tmp, field)) \ 4777777dab0Sopenharmony_ci != NULL) \ 4787777dab0Sopenharmony_ci RB_COLOR(oleft, field) = RB_BLACK; \ 4797777dab0Sopenharmony_ci RB_COLOR(tmp, field) = RB_RED; \ 4807777dab0Sopenharmony_ci RB_ROTATE_RIGHT(head, tmp, oleft, field); \ 4817777dab0Sopenharmony_ci tmp = RB_RIGHT(parent, field); \ 4827777dab0Sopenharmony_ci } \ 4837777dab0Sopenharmony_ci RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 4847777dab0Sopenharmony_ci RB_COLOR(parent, field) = RB_BLACK; \ 4857777dab0Sopenharmony_ci if (RB_RIGHT(tmp, field)) \ 4867777dab0Sopenharmony_ci RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ 4877777dab0Sopenharmony_ci RB_ROTATE_LEFT(head, parent, tmp, field); \ 4887777dab0Sopenharmony_ci elm = RB_ROOT(head); \ 4897777dab0Sopenharmony_ci break; \ 4907777dab0Sopenharmony_ci } \ 4917777dab0Sopenharmony_ci } else { \ 4927777dab0Sopenharmony_ci tmp = RB_LEFT(parent, field); \ 4937777dab0Sopenharmony_ci if (RB_COLOR(tmp, field) == RB_RED) { \ 4947777dab0Sopenharmony_ci RB_SET_BLACKRED(tmp, parent, field); \ 4957777dab0Sopenharmony_ci RB_ROTATE_RIGHT(head, parent, tmp, field); \ 4967777dab0Sopenharmony_ci tmp = RB_LEFT(parent, field); \ 4977777dab0Sopenharmony_ci } \ 4987777dab0Sopenharmony_ci if ((RB_LEFT(tmp, field) == NULL || \ 4997777dab0Sopenharmony_ci RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 5007777dab0Sopenharmony_ci (RB_RIGHT(tmp, field) == NULL || \ 5017777dab0Sopenharmony_ci RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 5027777dab0Sopenharmony_ci RB_COLOR(tmp, field) = RB_RED; \ 5037777dab0Sopenharmony_ci elm = parent; \ 5047777dab0Sopenharmony_ci parent = RB_PARENT(elm, field); \ 5057777dab0Sopenharmony_ci } else { \ 5067777dab0Sopenharmony_ci if (RB_LEFT(tmp, field) == NULL || \ 5077777dab0Sopenharmony_ci RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \ 5087777dab0Sopenharmony_ci struct type *oright; \ 5097777dab0Sopenharmony_ci if ((oright = RB_RIGHT(tmp, field)) \ 5107777dab0Sopenharmony_ci != NULL) \ 5117777dab0Sopenharmony_ci RB_COLOR(oright, field) = RB_BLACK; \ 5127777dab0Sopenharmony_ci RB_COLOR(tmp, field) = RB_RED; \ 5137777dab0Sopenharmony_ci RB_ROTATE_LEFT(head, tmp, oright, field); \ 5147777dab0Sopenharmony_ci tmp = RB_LEFT(parent, field); \ 5157777dab0Sopenharmony_ci } \ 5167777dab0Sopenharmony_ci RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 5177777dab0Sopenharmony_ci RB_COLOR(parent, field) = RB_BLACK; \ 5187777dab0Sopenharmony_ci if (RB_LEFT(tmp, field)) \ 5197777dab0Sopenharmony_ci RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ 5207777dab0Sopenharmony_ci RB_ROTATE_RIGHT(head, parent, tmp, field); \ 5217777dab0Sopenharmony_ci elm = RB_ROOT(head); \ 5227777dab0Sopenharmony_ci break; \ 5237777dab0Sopenharmony_ci } \ 5247777dab0Sopenharmony_ci } \ 5257777dab0Sopenharmony_ci } \ 5267777dab0Sopenharmony_ci if (elm) \ 5277777dab0Sopenharmony_ci RB_COLOR(elm, field) = RB_BLACK; \ 5287777dab0Sopenharmony_ci} \ 5297777dab0Sopenharmony_ci \ 5307777dab0Sopenharmony_ciattr struct type * \ 5317777dab0Sopenharmony_ciname##_RB_REMOVE(struct name *head, struct type *elm) \ 5327777dab0Sopenharmony_ci{ \ 5337777dab0Sopenharmony_ci struct type *child, *parent, *old = elm; \ 5347777dab0Sopenharmony_ci int color; \ 5357777dab0Sopenharmony_ci if (RB_LEFT(elm, field) == NULL) \ 5367777dab0Sopenharmony_ci child = RB_RIGHT(elm, field); \ 5377777dab0Sopenharmony_ci else if (RB_RIGHT(elm, field) == NULL) \ 5387777dab0Sopenharmony_ci child = RB_LEFT(elm, field); \ 5397777dab0Sopenharmony_ci else { \ 5407777dab0Sopenharmony_ci struct type *left; \ 5417777dab0Sopenharmony_ci elm = RB_RIGHT(elm, field); \ 5427777dab0Sopenharmony_ci while ((left = RB_LEFT(elm, field)) != NULL) \ 5437777dab0Sopenharmony_ci elm = left; \ 5447777dab0Sopenharmony_ci child = RB_RIGHT(elm, field); \ 5457777dab0Sopenharmony_ci parent = RB_PARENT(elm, field); \ 5467777dab0Sopenharmony_ci color = RB_COLOR(elm, field); \ 5477777dab0Sopenharmony_ci if (child) \ 5487777dab0Sopenharmony_ci RB_PARENT(child, field) = parent; \ 5497777dab0Sopenharmony_ci if (parent) { \ 5507777dab0Sopenharmony_ci if (RB_LEFT(parent, field) == elm) \ 5517777dab0Sopenharmony_ci RB_LEFT(parent, field) = child; \ 5527777dab0Sopenharmony_ci else \ 5537777dab0Sopenharmony_ci RB_RIGHT(parent, field) = child; \ 5547777dab0Sopenharmony_ci RB_AUGMENT(parent); \ 5557777dab0Sopenharmony_ci } else \ 5567777dab0Sopenharmony_ci RB_ROOT(head) = child; \ 5577777dab0Sopenharmony_ci if (RB_PARENT(elm, field) == old) \ 5587777dab0Sopenharmony_ci parent = elm; \ 5597777dab0Sopenharmony_ci (elm)->field = (old)->field; \ 5607777dab0Sopenharmony_ci if (RB_PARENT(old, field)) { \ 5617777dab0Sopenharmony_ci if (RB_LEFT(RB_PARENT(old, field), field) == old) \ 5627777dab0Sopenharmony_ci RB_LEFT(RB_PARENT(old, field), field) = elm; \ 5637777dab0Sopenharmony_ci else \ 5647777dab0Sopenharmony_ci RB_RIGHT(RB_PARENT(old, field), field) = elm; \ 5657777dab0Sopenharmony_ci RB_AUGMENT(RB_PARENT(old, field)); \ 5667777dab0Sopenharmony_ci } else \ 5677777dab0Sopenharmony_ci RB_ROOT(head) = elm; \ 5687777dab0Sopenharmony_ci RB_PARENT(RB_LEFT(old, field), field) = elm; \ 5697777dab0Sopenharmony_ci if (RB_RIGHT(old, field)) \ 5707777dab0Sopenharmony_ci RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 5717777dab0Sopenharmony_ci if (parent) { \ 5727777dab0Sopenharmony_ci left = parent; \ 5737777dab0Sopenharmony_ci do { \ 5747777dab0Sopenharmony_ci RB_AUGMENT(left); \ 5757777dab0Sopenharmony_ci } while ((left = RB_PARENT(left, field)) != NULL); \ 5767777dab0Sopenharmony_ci } \ 5777777dab0Sopenharmony_ci goto color; \ 5787777dab0Sopenharmony_ci } \ 5797777dab0Sopenharmony_ci parent = RB_PARENT(elm, field); \ 5807777dab0Sopenharmony_ci color = RB_COLOR(elm, field); \ 5817777dab0Sopenharmony_ci if (child) \ 5827777dab0Sopenharmony_ci RB_PARENT(child, field) = parent; \ 5837777dab0Sopenharmony_ci if (parent) { \ 5847777dab0Sopenharmony_ci if (RB_LEFT(parent, field) == elm) \ 5857777dab0Sopenharmony_ci RB_LEFT(parent, field) = child; \ 5867777dab0Sopenharmony_ci else \ 5877777dab0Sopenharmony_ci RB_RIGHT(parent, field) = child; \ 5887777dab0Sopenharmony_ci RB_AUGMENT(parent); \ 5897777dab0Sopenharmony_ci } else \ 5907777dab0Sopenharmony_ci RB_ROOT(head) = child; \ 5917777dab0Sopenharmony_cicolor: \ 5927777dab0Sopenharmony_ci if (color == RB_BLACK) \ 5937777dab0Sopenharmony_ci name##_RB_REMOVE_COLOR(head, parent, child); \ 5947777dab0Sopenharmony_ci return (old); \ 5957777dab0Sopenharmony_ci} \ 5967777dab0Sopenharmony_ci \ 5977777dab0Sopenharmony_ci/* Inserts a node into the RB tree */ \ 5987777dab0Sopenharmony_ciattr struct type * \ 5997777dab0Sopenharmony_ciname##_RB_INSERT(struct name *head, struct type *elm) \ 6007777dab0Sopenharmony_ci{ \ 6017777dab0Sopenharmony_ci struct type *tmp; \ 6027777dab0Sopenharmony_ci struct type *parent = NULL; \ 6037777dab0Sopenharmony_ci int comp = 0; \ 6047777dab0Sopenharmony_ci tmp = RB_ROOT(head); \ 6057777dab0Sopenharmony_ci while (tmp) { \ 6067777dab0Sopenharmony_ci parent = tmp; \ 6077777dab0Sopenharmony_ci comp = (cmp)(elm, parent); \ 6087777dab0Sopenharmony_ci if (comp < 0) \ 6097777dab0Sopenharmony_ci tmp = RB_LEFT(tmp, field); \ 6107777dab0Sopenharmony_ci else if (comp > 0) \ 6117777dab0Sopenharmony_ci tmp = RB_RIGHT(tmp, field); \ 6127777dab0Sopenharmony_ci else \ 6137777dab0Sopenharmony_ci return (tmp); \ 6147777dab0Sopenharmony_ci } \ 6157777dab0Sopenharmony_ci RB_SET(elm, parent, field); \ 6167777dab0Sopenharmony_ci if (parent != NULL) { \ 6177777dab0Sopenharmony_ci if (comp < 0) \ 6187777dab0Sopenharmony_ci RB_LEFT(parent, field) = elm; \ 6197777dab0Sopenharmony_ci else \ 6207777dab0Sopenharmony_ci RB_RIGHT(parent, field) = elm; \ 6217777dab0Sopenharmony_ci RB_AUGMENT(parent); \ 6227777dab0Sopenharmony_ci } else \ 6237777dab0Sopenharmony_ci RB_ROOT(head) = elm; \ 6247777dab0Sopenharmony_ci name##_RB_INSERT_COLOR(head, elm); \ 6257777dab0Sopenharmony_ci return (NULL); \ 6267777dab0Sopenharmony_ci} \ 6277777dab0Sopenharmony_ci \ 6287777dab0Sopenharmony_ci/* Finds the node with the same key as elm */ \ 6297777dab0Sopenharmony_ciattr struct type * \ 6307777dab0Sopenharmony_ciname##_RB_FIND(struct name *head, struct type *elm) \ 6317777dab0Sopenharmony_ci{ \ 6327777dab0Sopenharmony_ci struct type *tmp = RB_ROOT(head); \ 6337777dab0Sopenharmony_ci int comp; \ 6347777dab0Sopenharmony_ci while (tmp) { \ 6357777dab0Sopenharmony_ci comp = cmp(elm, tmp); \ 6367777dab0Sopenharmony_ci if (comp < 0) \ 6377777dab0Sopenharmony_ci tmp = RB_LEFT(tmp, field); \ 6387777dab0Sopenharmony_ci else if (comp > 0) \ 6397777dab0Sopenharmony_ci tmp = RB_RIGHT(tmp, field); \ 6407777dab0Sopenharmony_ci else \ 6417777dab0Sopenharmony_ci return (tmp); \ 6427777dab0Sopenharmony_ci } \ 6437777dab0Sopenharmony_ci return (NULL); \ 6447777dab0Sopenharmony_ci} \ 6457777dab0Sopenharmony_ci \ 6467777dab0Sopenharmony_ci/* Finds the first node greater than or equal to the search key */ \ 6477777dab0Sopenharmony_ciattr struct type * \ 6487777dab0Sopenharmony_ciname##_RB_NFIND(struct name *head, struct type *elm) \ 6497777dab0Sopenharmony_ci{ \ 6507777dab0Sopenharmony_ci struct type *tmp = RB_ROOT(head); \ 6517777dab0Sopenharmony_ci struct type *res = NULL; \ 6527777dab0Sopenharmony_ci int comp; \ 6537777dab0Sopenharmony_ci while (tmp) { \ 6547777dab0Sopenharmony_ci comp = cmp(elm, tmp); \ 6557777dab0Sopenharmony_ci if (comp < 0) { \ 6567777dab0Sopenharmony_ci res = tmp; \ 6577777dab0Sopenharmony_ci tmp = RB_LEFT(tmp, field); \ 6587777dab0Sopenharmony_ci } \ 6597777dab0Sopenharmony_ci else if (comp > 0) \ 6607777dab0Sopenharmony_ci tmp = RB_RIGHT(tmp, field); \ 6617777dab0Sopenharmony_ci else \ 6627777dab0Sopenharmony_ci return (tmp); \ 6637777dab0Sopenharmony_ci } \ 6647777dab0Sopenharmony_ci return (res); \ 6657777dab0Sopenharmony_ci} \ 6667777dab0Sopenharmony_ci \ 6677777dab0Sopenharmony_ci/* ARGSUSED */ \ 6687777dab0Sopenharmony_ciattr struct type * \ 6697777dab0Sopenharmony_ciname##_RB_NEXT(struct type *elm) \ 6707777dab0Sopenharmony_ci{ \ 6717777dab0Sopenharmony_ci if (RB_RIGHT(elm, field)) { \ 6727777dab0Sopenharmony_ci elm = RB_RIGHT(elm, field); \ 6737777dab0Sopenharmony_ci while (RB_LEFT(elm, field)) \ 6747777dab0Sopenharmony_ci elm = RB_LEFT(elm, field); \ 6757777dab0Sopenharmony_ci } else { \ 6767777dab0Sopenharmony_ci if (RB_PARENT(elm, field) && \ 6777777dab0Sopenharmony_ci (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 6787777dab0Sopenharmony_ci elm = RB_PARENT(elm, field); \ 6797777dab0Sopenharmony_ci else { \ 6807777dab0Sopenharmony_ci while (RB_PARENT(elm, field) && \ 6817777dab0Sopenharmony_ci (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 6827777dab0Sopenharmony_ci elm = RB_PARENT(elm, field); \ 6837777dab0Sopenharmony_ci elm = RB_PARENT(elm, field); \ 6847777dab0Sopenharmony_ci } \ 6857777dab0Sopenharmony_ci } \ 6867777dab0Sopenharmony_ci return (elm); \ 6877777dab0Sopenharmony_ci} \ 6887777dab0Sopenharmony_ci \ 6897777dab0Sopenharmony_ci/* ARGSUSED */ \ 6907777dab0Sopenharmony_ciattr struct type * \ 6917777dab0Sopenharmony_ciname##_RB_PREV(struct type *elm) \ 6927777dab0Sopenharmony_ci{ \ 6937777dab0Sopenharmony_ci if (RB_LEFT(elm, field)) { \ 6947777dab0Sopenharmony_ci elm = RB_LEFT(elm, field); \ 6957777dab0Sopenharmony_ci while (RB_RIGHT(elm, field)) \ 6967777dab0Sopenharmony_ci elm = RB_RIGHT(elm, field); \ 6977777dab0Sopenharmony_ci } else { \ 6987777dab0Sopenharmony_ci if (RB_PARENT(elm, field) && \ 6997777dab0Sopenharmony_ci (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 7007777dab0Sopenharmony_ci elm = RB_PARENT(elm, field); \ 7017777dab0Sopenharmony_ci else { \ 7027777dab0Sopenharmony_ci while (RB_PARENT(elm, field) && \ 7037777dab0Sopenharmony_ci (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 7047777dab0Sopenharmony_ci elm = RB_PARENT(elm, field); \ 7057777dab0Sopenharmony_ci elm = RB_PARENT(elm, field); \ 7067777dab0Sopenharmony_ci } \ 7077777dab0Sopenharmony_ci } \ 7087777dab0Sopenharmony_ci return (elm); \ 7097777dab0Sopenharmony_ci} \ 7107777dab0Sopenharmony_ci \ 7117777dab0Sopenharmony_ciattr struct type * \ 7127777dab0Sopenharmony_ciname##_RB_MINMAX(struct name *head, int val) \ 7137777dab0Sopenharmony_ci{ \ 7147777dab0Sopenharmony_ci struct type *tmp = RB_ROOT(head); \ 7157777dab0Sopenharmony_ci struct type *parent = NULL; \ 7167777dab0Sopenharmony_ci while (tmp) { \ 7177777dab0Sopenharmony_ci parent = tmp; \ 7187777dab0Sopenharmony_ci if (val < 0) \ 7197777dab0Sopenharmony_ci tmp = RB_LEFT(tmp, field); \ 7207777dab0Sopenharmony_ci else \ 7217777dab0Sopenharmony_ci tmp = RB_RIGHT(tmp, field); \ 7227777dab0Sopenharmony_ci } \ 7237777dab0Sopenharmony_ci return (parent); \ 7247777dab0Sopenharmony_ci} 7257777dab0Sopenharmony_ci 7267777dab0Sopenharmony_ci#define RB_NEGINF -1 7277777dab0Sopenharmony_ci#define RB_INF 1 7287777dab0Sopenharmony_ci 7297777dab0Sopenharmony_ci#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 7307777dab0Sopenharmony_ci#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 7317777dab0Sopenharmony_ci#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 7327777dab0Sopenharmony_ci#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 7337777dab0Sopenharmony_ci#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 7347777dab0Sopenharmony_ci#define RB_PREV(name, x, y) name##_RB_PREV(y) 7357777dab0Sopenharmony_ci#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 7367777dab0Sopenharmony_ci#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 7377777dab0Sopenharmony_ci 7387777dab0Sopenharmony_ci#define RB_FOREACH(x, name, head) \ 7397777dab0Sopenharmony_ci for ((x) = RB_MIN(name, head); \ 7407777dab0Sopenharmony_ci (x) != NULL; \ 7417777dab0Sopenharmony_ci (x) = name##_RB_NEXT(x)) 7427777dab0Sopenharmony_ci 7437777dab0Sopenharmony_ci#define RB_FOREACH_FROM(x, name, y) \ 7447777dab0Sopenharmony_ci for ((x) = (y); \ 7457777dab0Sopenharmony_ci ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 7467777dab0Sopenharmony_ci (x) = (y)) 7477777dab0Sopenharmony_ci 7487777dab0Sopenharmony_ci#define RB_FOREACH_SAFE(x, name, head, y) \ 7497777dab0Sopenharmony_ci for ((x) = RB_MIN(name, head); \ 7507777dab0Sopenharmony_ci ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 7517777dab0Sopenharmony_ci (x) = (y)) 7527777dab0Sopenharmony_ci 7537777dab0Sopenharmony_ci#define RB_FOREACH_REVERSE(x, name, head) \ 7547777dab0Sopenharmony_ci for ((x) = RB_MAX(name, head); \ 7557777dab0Sopenharmony_ci (x) != NULL; \ 7567777dab0Sopenharmony_ci (x) = name##_RB_PREV(x)) 7577777dab0Sopenharmony_ci 7587777dab0Sopenharmony_ci#define RB_FOREACH_REVERSE_FROM(x, name, y) \ 7597777dab0Sopenharmony_ci for ((x) = (y); \ 7607777dab0Sopenharmony_ci ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 7617777dab0Sopenharmony_ci (x) = (y)) 7627777dab0Sopenharmony_ci 7637777dab0Sopenharmony_ci#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 7647777dab0Sopenharmony_ci for ((x) = RB_MAX(name, head); \ 7657777dab0Sopenharmony_ci ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 7667777dab0Sopenharmony_ci (x) = (y)) 7677777dab0Sopenharmony_ci 7687777dab0Sopenharmony_ci#endif /* UV_TREE_H_ */ 769