1e66f31c5Sopenharmony_ci/*- 2e66f31c5Sopenharmony_ci * Copyright 2002 Niels Provos <provos@citi.umich.edu> 3e66f31c5Sopenharmony_ci * All rights reserved. 4e66f31c5Sopenharmony_ci * 5e66f31c5Sopenharmony_ci * Redistribution and use in source and binary forms, with or without 6e66f31c5Sopenharmony_ci * modification, are permitted provided that the following conditions 7e66f31c5Sopenharmony_ci * are met: 8e66f31c5Sopenharmony_ci * 1. Redistributions of source code must retain the above copyright 9e66f31c5Sopenharmony_ci * notice, this list of conditions and the following disclaimer. 10e66f31c5Sopenharmony_ci * 2. Redistributions in binary form must reproduce the above copyright 11e66f31c5Sopenharmony_ci * notice, this list of conditions and the following disclaimer in the 12e66f31c5Sopenharmony_ci * documentation and/or other materials provided with the distribution. 13e66f31c5Sopenharmony_ci * 14e66f31c5Sopenharmony_ci * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 15e66f31c5Sopenharmony_ci * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 16e66f31c5Sopenharmony_ci * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 17e66f31c5Sopenharmony_ci * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 18e66f31c5Sopenharmony_ci * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 19e66f31c5Sopenharmony_ci * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 20e66f31c5Sopenharmony_ci * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 21e66f31c5Sopenharmony_ci * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22e66f31c5Sopenharmony_ci * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 23e66f31c5Sopenharmony_ci * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24e66f31c5Sopenharmony_ci */ 25e66f31c5Sopenharmony_ci 26e66f31c5Sopenharmony_ci#ifndef UV_TREE_H_ 27e66f31c5Sopenharmony_ci#define UV_TREE_H_ 28e66f31c5Sopenharmony_ci 29e66f31c5Sopenharmony_ci#ifndef UV__UNUSED 30e66f31c5Sopenharmony_ci# if __GNUC__ 31e66f31c5Sopenharmony_ci# define UV__UNUSED __attribute__((unused)) 32e66f31c5Sopenharmony_ci# else 33e66f31c5Sopenharmony_ci# define UV__UNUSED 34e66f31c5Sopenharmony_ci# endif 35e66f31c5Sopenharmony_ci#endif 36e66f31c5Sopenharmony_ci 37e66f31c5Sopenharmony_ci/* 38e66f31c5Sopenharmony_ci * This file defines data structures for different types of trees: 39e66f31c5Sopenharmony_ci * splay trees and red-black trees. 40e66f31c5Sopenharmony_ci * 41e66f31c5Sopenharmony_ci * A splay tree is a self-organizing data structure. Every operation 42e66f31c5Sopenharmony_ci * on the tree causes a splay to happen. The splay moves the requested 43e66f31c5Sopenharmony_ci * node to the root of the tree and partly rebalances it. 44e66f31c5Sopenharmony_ci * 45e66f31c5Sopenharmony_ci * This has the benefit that request locality causes faster lookups as 46e66f31c5Sopenharmony_ci * the requested nodes move to the top of the tree. On the other hand, 47e66f31c5Sopenharmony_ci * every lookup causes memory writes. 48e66f31c5Sopenharmony_ci * 49e66f31c5Sopenharmony_ci * The Balance Theorem bounds the total access time for m operations 50e66f31c5Sopenharmony_ci * and n inserts on an initially empty tree as O((m + n)lg n). The 51e66f31c5Sopenharmony_ci * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 52e66f31c5Sopenharmony_ci * 53e66f31c5Sopenharmony_ci * A red-black tree is a binary search tree with the node color as an 54e66f31c5Sopenharmony_ci * extra attribute. It fulfills a set of conditions: 55e66f31c5Sopenharmony_ci * - every search path from the root to a leaf consists of the 56e66f31c5Sopenharmony_ci * same number of black nodes, 57e66f31c5Sopenharmony_ci * - each red node (except for the root) has a black parent, 58e66f31c5Sopenharmony_ci * - each leaf node is black. 59e66f31c5Sopenharmony_ci * 60e66f31c5Sopenharmony_ci * Every operation on a red-black tree is bounded as O(lg n). 61e66f31c5Sopenharmony_ci * The maximum height of a red-black tree is 2lg (n+1). 62e66f31c5Sopenharmony_ci */ 63e66f31c5Sopenharmony_ci 64e66f31c5Sopenharmony_ci#define SPLAY_HEAD(name, type) \ 65e66f31c5Sopenharmony_cistruct name { \ 66e66f31c5Sopenharmony_ci struct type *sph_root; /* root of the tree */ \ 67e66f31c5Sopenharmony_ci} 68e66f31c5Sopenharmony_ci 69e66f31c5Sopenharmony_ci#define SPLAY_INITIALIZER(root) \ 70e66f31c5Sopenharmony_ci { NULL } 71e66f31c5Sopenharmony_ci 72e66f31c5Sopenharmony_ci#define SPLAY_INIT(root) do { \ 73e66f31c5Sopenharmony_ci (root)->sph_root = NULL; \ 74e66f31c5Sopenharmony_ci} while (/*CONSTCOND*/ 0) 75e66f31c5Sopenharmony_ci 76e66f31c5Sopenharmony_ci#define SPLAY_ENTRY(type) \ 77e66f31c5Sopenharmony_cistruct { \ 78e66f31c5Sopenharmony_ci struct type *spe_left; /* left element */ \ 79e66f31c5Sopenharmony_ci struct type *spe_right; /* right element */ \ 80e66f31c5Sopenharmony_ci} 81e66f31c5Sopenharmony_ci 82e66f31c5Sopenharmony_ci#define SPLAY_LEFT(elm, field) (elm)->field.spe_left 83e66f31c5Sopenharmony_ci#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 84e66f31c5Sopenharmony_ci#define SPLAY_ROOT(head) (head)->sph_root 85e66f31c5Sopenharmony_ci#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 86e66f31c5Sopenharmony_ci 87e66f31c5Sopenharmony_ci/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 88e66f31c5Sopenharmony_ci#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 89e66f31c5Sopenharmony_ci SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 90e66f31c5Sopenharmony_ci SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 91e66f31c5Sopenharmony_ci (head)->sph_root = tmp; \ 92e66f31c5Sopenharmony_ci} while (/*CONSTCOND*/ 0) 93e66f31c5Sopenharmony_ci 94e66f31c5Sopenharmony_ci#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 95e66f31c5Sopenharmony_ci SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 96e66f31c5Sopenharmony_ci SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 97e66f31c5Sopenharmony_ci (head)->sph_root = tmp; \ 98e66f31c5Sopenharmony_ci} while (/*CONSTCOND*/ 0) 99e66f31c5Sopenharmony_ci 100e66f31c5Sopenharmony_ci#define SPLAY_LINKLEFT(head, tmp, field) do { \ 101e66f31c5Sopenharmony_ci SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 102e66f31c5Sopenharmony_ci tmp = (head)->sph_root; \ 103e66f31c5Sopenharmony_ci (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 104e66f31c5Sopenharmony_ci} while (/*CONSTCOND*/ 0) 105e66f31c5Sopenharmony_ci 106e66f31c5Sopenharmony_ci#define SPLAY_LINKRIGHT(head, tmp, field) do { \ 107e66f31c5Sopenharmony_ci SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 108e66f31c5Sopenharmony_ci tmp = (head)->sph_root; \ 109e66f31c5Sopenharmony_ci (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 110e66f31c5Sopenharmony_ci} while (/*CONSTCOND*/ 0) 111e66f31c5Sopenharmony_ci 112e66f31c5Sopenharmony_ci#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 113e66f31c5Sopenharmony_ci SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 114e66f31c5Sopenharmony_ci SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field); \ 115e66f31c5Sopenharmony_ci SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 116e66f31c5Sopenharmony_ci SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 117e66f31c5Sopenharmony_ci} while (/*CONSTCOND*/ 0) 118e66f31c5Sopenharmony_ci 119e66f31c5Sopenharmony_ci/* Generates prototypes and inline functions */ 120e66f31c5Sopenharmony_ci 121e66f31c5Sopenharmony_ci#define SPLAY_PROTOTYPE(name, type, field, cmp) \ 122e66f31c5Sopenharmony_civoid name##_SPLAY(struct name *, struct type *); \ 123e66f31c5Sopenharmony_civoid name##_SPLAY_MINMAX(struct name *, int); \ 124e66f31c5Sopenharmony_cistruct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 125e66f31c5Sopenharmony_cistruct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 126e66f31c5Sopenharmony_ci \ 127e66f31c5Sopenharmony_ci/* Finds the node with the same key as elm */ \ 128e66f31c5Sopenharmony_cistatic __inline struct type * \ 129e66f31c5Sopenharmony_ciname##_SPLAY_FIND(struct name *head, struct type *elm) \ 130e66f31c5Sopenharmony_ci{ \ 131e66f31c5Sopenharmony_ci if (SPLAY_EMPTY(head)) \ 132e66f31c5Sopenharmony_ci return(NULL); \ 133e66f31c5Sopenharmony_ci name##_SPLAY(head, elm); \ 134e66f31c5Sopenharmony_ci if ((cmp)(elm, (head)->sph_root) == 0) \ 135e66f31c5Sopenharmony_ci return (head->sph_root); \ 136e66f31c5Sopenharmony_ci return (NULL); \ 137e66f31c5Sopenharmony_ci} \ 138e66f31c5Sopenharmony_ci \ 139e66f31c5Sopenharmony_cistatic __inline struct type * \ 140e66f31c5Sopenharmony_ciname##_SPLAY_NEXT(struct name *head, struct type *elm) \ 141e66f31c5Sopenharmony_ci{ \ 142e66f31c5Sopenharmony_ci name##_SPLAY(head, elm); \ 143e66f31c5Sopenharmony_ci if (SPLAY_RIGHT(elm, field) != NULL) { \ 144e66f31c5Sopenharmony_ci elm = SPLAY_RIGHT(elm, field); \ 145e66f31c5Sopenharmony_ci while (SPLAY_LEFT(elm, field) != NULL) { \ 146e66f31c5Sopenharmony_ci elm = SPLAY_LEFT(elm, field); \ 147e66f31c5Sopenharmony_ci } \ 148e66f31c5Sopenharmony_ci } else \ 149e66f31c5Sopenharmony_ci elm = NULL; \ 150e66f31c5Sopenharmony_ci return (elm); \ 151e66f31c5Sopenharmony_ci} \ 152e66f31c5Sopenharmony_ci \ 153e66f31c5Sopenharmony_cistatic __inline struct type * \ 154e66f31c5Sopenharmony_ciname##_SPLAY_MIN_MAX(struct name *head, int val) \ 155e66f31c5Sopenharmony_ci{ \ 156e66f31c5Sopenharmony_ci name##_SPLAY_MINMAX(head, val); \ 157e66f31c5Sopenharmony_ci return (SPLAY_ROOT(head)); \ 158e66f31c5Sopenharmony_ci} 159e66f31c5Sopenharmony_ci 160e66f31c5Sopenharmony_ci/* Main splay operation. 161e66f31c5Sopenharmony_ci * Moves node close to the key of elm to top 162e66f31c5Sopenharmony_ci */ 163e66f31c5Sopenharmony_ci#define SPLAY_GENERATE(name, type, field, cmp) \ 164e66f31c5Sopenharmony_cistruct type * \ 165e66f31c5Sopenharmony_ciname##_SPLAY_INSERT(struct name *head, struct type *elm) \ 166e66f31c5Sopenharmony_ci{ \ 167e66f31c5Sopenharmony_ci if (SPLAY_EMPTY(head)) { \ 168e66f31c5Sopenharmony_ci SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 169e66f31c5Sopenharmony_ci } else { \ 170e66f31c5Sopenharmony_ci int __comp; \ 171e66f31c5Sopenharmony_ci name##_SPLAY(head, elm); \ 172e66f31c5Sopenharmony_ci __comp = (cmp)(elm, (head)->sph_root); \ 173e66f31c5Sopenharmony_ci if(__comp < 0) { \ 174e66f31c5Sopenharmony_ci SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field); \ 175e66f31c5Sopenharmony_ci SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 176e66f31c5Sopenharmony_ci SPLAY_LEFT((head)->sph_root, field) = NULL; \ 177e66f31c5Sopenharmony_ci } else if (__comp > 0) { \ 178e66f31c5Sopenharmony_ci SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field); \ 179e66f31c5Sopenharmony_ci SPLAY_LEFT(elm, field) = (head)->sph_root; \ 180e66f31c5Sopenharmony_ci SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 181e66f31c5Sopenharmony_ci } else \ 182e66f31c5Sopenharmony_ci return ((head)->sph_root); \ 183e66f31c5Sopenharmony_ci } \ 184e66f31c5Sopenharmony_ci (head)->sph_root = (elm); \ 185e66f31c5Sopenharmony_ci return (NULL); \ 186e66f31c5Sopenharmony_ci} \ 187e66f31c5Sopenharmony_ci \ 188e66f31c5Sopenharmony_cistruct type * \ 189e66f31c5Sopenharmony_ciname##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 190e66f31c5Sopenharmony_ci{ \ 191e66f31c5Sopenharmony_ci struct type *__tmp; \ 192e66f31c5Sopenharmony_ci if (SPLAY_EMPTY(head)) \ 193e66f31c5Sopenharmony_ci return (NULL); \ 194e66f31c5Sopenharmony_ci name##_SPLAY(head, elm); \ 195e66f31c5Sopenharmony_ci if ((cmp)(elm, (head)->sph_root) == 0) { \ 196e66f31c5Sopenharmony_ci if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 197e66f31c5Sopenharmony_ci (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 198e66f31c5Sopenharmony_ci } else { \ 199e66f31c5Sopenharmony_ci __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 200e66f31c5Sopenharmony_ci (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 201e66f31c5Sopenharmony_ci name##_SPLAY(head, elm); \ 202e66f31c5Sopenharmony_ci SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 203e66f31c5Sopenharmony_ci } \ 204e66f31c5Sopenharmony_ci return (elm); \ 205e66f31c5Sopenharmony_ci } \ 206e66f31c5Sopenharmony_ci return (NULL); \ 207e66f31c5Sopenharmony_ci} \ 208e66f31c5Sopenharmony_ci \ 209e66f31c5Sopenharmony_civoid \ 210e66f31c5Sopenharmony_ciname##_SPLAY(struct name *head, struct type *elm) \ 211e66f31c5Sopenharmony_ci{ \ 212e66f31c5Sopenharmony_ci struct type __node, *__left, *__right, *__tmp; \ 213e66f31c5Sopenharmony_ci int __comp; \ 214e66f31c5Sopenharmony_ci \ 215e66f31c5Sopenharmony_ci SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ 216e66f31c5Sopenharmony_ci __left = __right = &__node; \ 217e66f31c5Sopenharmony_ci \ 218e66f31c5Sopenharmony_ci while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 219e66f31c5Sopenharmony_ci if (__comp < 0) { \ 220e66f31c5Sopenharmony_ci __tmp = SPLAY_LEFT((head)->sph_root, field); \ 221e66f31c5Sopenharmony_ci if (__tmp == NULL) \ 222e66f31c5Sopenharmony_ci break; \ 223e66f31c5Sopenharmony_ci if ((cmp)(elm, __tmp) < 0){ \ 224e66f31c5Sopenharmony_ci SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 225e66f31c5Sopenharmony_ci if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ 226e66f31c5Sopenharmony_ci break; \ 227e66f31c5Sopenharmony_ci } \ 228e66f31c5Sopenharmony_ci SPLAY_LINKLEFT(head, __right, field); \ 229e66f31c5Sopenharmony_ci } else if (__comp > 0) { \ 230e66f31c5Sopenharmony_ci __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 231e66f31c5Sopenharmony_ci if (__tmp == NULL) \ 232e66f31c5Sopenharmony_ci break; \ 233e66f31c5Sopenharmony_ci if ((cmp)(elm, __tmp) > 0){ \ 234e66f31c5Sopenharmony_ci SPLAY_ROTATE_LEFT(head, __tmp, field); \ 235e66f31c5Sopenharmony_ci if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ 236e66f31c5Sopenharmony_ci break; \ 237e66f31c5Sopenharmony_ci } \ 238e66f31c5Sopenharmony_ci SPLAY_LINKRIGHT(head, __left, field); \ 239e66f31c5Sopenharmony_ci } \ 240e66f31c5Sopenharmony_ci } \ 241e66f31c5Sopenharmony_ci SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 242e66f31c5Sopenharmony_ci} \ 243e66f31c5Sopenharmony_ci \ 244e66f31c5Sopenharmony_ci/* Splay with either the minimum or the maximum element \ 245e66f31c5Sopenharmony_ci * Used to find minimum or maximum element in tree. \ 246e66f31c5Sopenharmony_ci */ \ 247e66f31c5Sopenharmony_civoid name##_SPLAY_MINMAX(struct name *head, int __comp) \ 248e66f31c5Sopenharmony_ci{ \ 249e66f31c5Sopenharmony_ci struct type __node, *__left, *__right, *__tmp; \ 250e66f31c5Sopenharmony_ci \ 251e66f31c5Sopenharmony_ci SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ 252e66f31c5Sopenharmony_ci __left = __right = &__node; \ 253e66f31c5Sopenharmony_ci \ 254e66f31c5Sopenharmony_ci for (;;) { \ 255e66f31c5Sopenharmony_ci if (__comp < 0) { \ 256e66f31c5Sopenharmony_ci __tmp = SPLAY_LEFT((head)->sph_root, field); \ 257e66f31c5Sopenharmony_ci if (__tmp == NULL) \ 258e66f31c5Sopenharmony_ci break; \ 259e66f31c5Sopenharmony_ci if (__comp < 0){ \ 260e66f31c5Sopenharmony_ci SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 261e66f31c5Sopenharmony_ci if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ 262e66f31c5Sopenharmony_ci break; \ 263e66f31c5Sopenharmony_ci } \ 264e66f31c5Sopenharmony_ci SPLAY_LINKLEFT(head, __right, field); \ 265e66f31c5Sopenharmony_ci } else if (__comp > 0) { \ 266e66f31c5Sopenharmony_ci __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 267e66f31c5Sopenharmony_ci if (__tmp == NULL) \ 268e66f31c5Sopenharmony_ci break; \ 269e66f31c5Sopenharmony_ci if (__comp > 0) { \ 270e66f31c5Sopenharmony_ci SPLAY_ROTATE_LEFT(head, __tmp, field); \ 271e66f31c5Sopenharmony_ci if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ 272e66f31c5Sopenharmony_ci break; \ 273e66f31c5Sopenharmony_ci } \ 274e66f31c5Sopenharmony_ci SPLAY_LINKRIGHT(head, __left, field); \ 275e66f31c5Sopenharmony_ci } \ 276e66f31c5Sopenharmony_ci } \ 277e66f31c5Sopenharmony_ci SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 278e66f31c5Sopenharmony_ci} 279e66f31c5Sopenharmony_ci 280e66f31c5Sopenharmony_ci#define SPLAY_NEGINF -1 281e66f31c5Sopenharmony_ci#define SPLAY_INF 1 282e66f31c5Sopenharmony_ci 283e66f31c5Sopenharmony_ci#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 284e66f31c5Sopenharmony_ci#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 285e66f31c5Sopenharmony_ci#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 286e66f31c5Sopenharmony_ci#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 287e66f31c5Sopenharmony_ci#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 288e66f31c5Sopenharmony_ci : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 289e66f31c5Sopenharmony_ci#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 290e66f31c5Sopenharmony_ci : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 291e66f31c5Sopenharmony_ci 292e66f31c5Sopenharmony_ci#define SPLAY_FOREACH(x, name, head) \ 293e66f31c5Sopenharmony_ci for ((x) = SPLAY_MIN(name, head); \ 294e66f31c5Sopenharmony_ci (x) != NULL; \ 295e66f31c5Sopenharmony_ci (x) = SPLAY_NEXT(name, head, x)) 296e66f31c5Sopenharmony_ci 297e66f31c5Sopenharmony_ci/* Macros that define a red-black tree */ 298e66f31c5Sopenharmony_ci#define RB_HEAD(name, type) \ 299e66f31c5Sopenharmony_cistruct name { \ 300e66f31c5Sopenharmony_ci struct type *rbh_root; /* root of the tree */ \ 301e66f31c5Sopenharmony_ci} 302e66f31c5Sopenharmony_ci 303e66f31c5Sopenharmony_ci#define RB_INITIALIZER(root) \ 304e66f31c5Sopenharmony_ci { NULL } 305e66f31c5Sopenharmony_ci 306e66f31c5Sopenharmony_ci#define RB_INIT(root) do { \ 307e66f31c5Sopenharmony_ci (root)->rbh_root = NULL; \ 308e66f31c5Sopenharmony_ci} while (/*CONSTCOND*/ 0) 309e66f31c5Sopenharmony_ci 310e66f31c5Sopenharmony_ci#define RB_BLACK 0 311e66f31c5Sopenharmony_ci#define RB_RED 1 312e66f31c5Sopenharmony_ci#define RB_ENTRY(type) \ 313e66f31c5Sopenharmony_cistruct { \ 314e66f31c5Sopenharmony_ci struct type *rbe_left; /* left element */ \ 315e66f31c5Sopenharmony_ci struct type *rbe_right; /* right element */ \ 316e66f31c5Sopenharmony_ci struct type *rbe_parent; /* parent element */ \ 317e66f31c5Sopenharmony_ci int rbe_color; /* node color */ \ 318e66f31c5Sopenharmony_ci} 319e66f31c5Sopenharmony_ci 320e66f31c5Sopenharmony_ci#define RB_LEFT(elm, field) (elm)->field.rbe_left 321e66f31c5Sopenharmony_ci#define RB_RIGHT(elm, field) (elm)->field.rbe_right 322e66f31c5Sopenharmony_ci#define RB_PARENT(elm, field) (elm)->field.rbe_parent 323e66f31c5Sopenharmony_ci#define RB_COLOR(elm, field) (elm)->field.rbe_color 324e66f31c5Sopenharmony_ci#define RB_ROOT(head) (head)->rbh_root 325e66f31c5Sopenharmony_ci#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 326e66f31c5Sopenharmony_ci 327e66f31c5Sopenharmony_ci#define RB_SET(elm, parent, field) do { \ 328e66f31c5Sopenharmony_ci RB_PARENT(elm, field) = parent; \ 329e66f31c5Sopenharmony_ci RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 330e66f31c5Sopenharmony_ci RB_COLOR(elm, field) = RB_RED; \ 331e66f31c5Sopenharmony_ci} while (/*CONSTCOND*/ 0) 332e66f31c5Sopenharmony_ci 333e66f31c5Sopenharmony_ci#define RB_SET_BLACKRED(black, red, field) do { \ 334e66f31c5Sopenharmony_ci RB_COLOR(black, field) = RB_BLACK; \ 335e66f31c5Sopenharmony_ci RB_COLOR(red, field) = RB_RED; \ 336e66f31c5Sopenharmony_ci} while (/*CONSTCOND*/ 0) 337e66f31c5Sopenharmony_ci 338e66f31c5Sopenharmony_ci#ifndef RB_AUGMENT 339e66f31c5Sopenharmony_ci#define RB_AUGMENT(x) do {} while (0) 340e66f31c5Sopenharmony_ci#endif 341e66f31c5Sopenharmony_ci 342e66f31c5Sopenharmony_ci#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 343e66f31c5Sopenharmony_ci (tmp) = RB_RIGHT(elm, field); \ 344e66f31c5Sopenharmony_ci if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 345e66f31c5Sopenharmony_ci RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 346e66f31c5Sopenharmony_ci } \ 347e66f31c5Sopenharmony_ci RB_AUGMENT(elm); \ 348e66f31c5Sopenharmony_ci if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 349e66f31c5Sopenharmony_ci if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 350e66f31c5Sopenharmony_ci RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 351e66f31c5Sopenharmony_ci else \ 352e66f31c5Sopenharmony_ci RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 353e66f31c5Sopenharmony_ci } else \ 354e66f31c5Sopenharmony_ci (head)->rbh_root = (tmp); \ 355e66f31c5Sopenharmony_ci RB_LEFT(tmp, field) = (elm); \ 356e66f31c5Sopenharmony_ci RB_PARENT(elm, field) = (tmp); \ 357e66f31c5Sopenharmony_ci RB_AUGMENT(tmp); \ 358e66f31c5Sopenharmony_ci if ((RB_PARENT(tmp, field))) \ 359e66f31c5Sopenharmony_ci RB_AUGMENT(RB_PARENT(tmp, field)); \ 360e66f31c5Sopenharmony_ci} while (/*CONSTCOND*/ 0) 361e66f31c5Sopenharmony_ci 362e66f31c5Sopenharmony_ci#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 363e66f31c5Sopenharmony_ci (tmp) = RB_LEFT(elm, field); \ 364e66f31c5Sopenharmony_ci if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 365e66f31c5Sopenharmony_ci RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 366e66f31c5Sopenharmony_ci } \ 367e66f31c5Sopenharmony_ci RB_AUGMENT(elm); \ 368e66f31c5Sopenharmony_ci if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 369e66f31c5Sopenharmony_ci if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 370e66f31c5Sopenharmony_ci RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 371e66f31c5Sopenharmony_ci else \ 372e66f31c5Sopenharmony_ci RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 373e66f31c5Sopenharmony_ci } else \ 374e66f31c5Sopenharmony_ci (head)->rbh_root = (tmp); \ 375e66f31c5Sopenharmony_ci RB_RIGHT(tmp, field) = (elm); \ 376e66f31c5Sopenharmony_ci RB_PARENT(elm, field) = (tmp); \ 377e66f31c5Sopenharmony_ci RB_AUGMENT(tmp); \ 378e66f31c5Sopenharmony_ci if ((RB_PARENT(tmp, field))) \ 379e66f31c5Sopenharmony_ci RB_AUGMENT(RB_PARENT(tmp, field)); \ 380e66f31c5Sopenharmony_ci} while (/*CONSTCOND*/ 0) 381e66f31c5Sopenharmony_ci 382e66f31c5Sopenharmony_ci/* Generates prototypes and inline functions */ 383e66f31c5Sopenharmony_ci#define RB_PROTOTYPE(name, type, field, cmp) \ 384e66f31c5Sopenharmony_ci RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 385e66f31c5Sopenharmony_ci#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 386e66f31c5Sopenharmony_ci RB_PROTOTYPE_INTERNAL(name, type, field, cmp, UV__UNUSED static) 387e66f31c5Sopenharmony_ci#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 388e66f31c5Sopenharmony_ciattr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 389e66f31c5Sopenharmony_ciattr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 390e66f31c5Sopenharmony_ciattr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 391e66f31c5Sopenharmony_ciattr struct type *name##_RB_INSERT(struct name *, struct type *); \ 392e66f31c5Sopenharmony_ciattr struct type *name##_RB_FIND(struct name *, struct type *); \ 393e66f31c5Sopenharmony_ciattr struct type *name##_RB_NFIND(struct name *, struct type *); \ 394e66f31c5Sopenharmony_ciattr struct type *name##_RB_NEXT(struct type *); \ 395e66f31c5Sopenharmony_ciattr struct type *name##_RB_PREV(struct type *); \ 396e66f31c5Sopenharmony_ciattr struct type *name##_RB_MINMAX(struct name *, int); \ 397e66f31c5Sopenharmony_ci \ 398e66f31c5Sopenharmony_ci 399e66f31c5Sopenharmony_ci/* Main rb operation. 400e66f31c5Sopenharmony_ci * Moves node close to the key of elm to top 401e66f31c5Sopenharmony_ci */ 402e66f31c5Sopenharmony_ci#define RB_GENERATE(name, type, field, cmp) \ 403e66f31c5Sopenharmony_ci RB_GENERATE_INTERNAL(name, type, field, cmp,) 404e66f31c5Sopenharmony_ci#define RB_GENERATE_STATIC(name, type, field, cmp) \ 405e66f31c5Sopenharmony_ci RB_GENERATE_INTERNAL(name, type, field, cmp, UV__UNUSED static) 406e66f31c5Sopenharmony_ci#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 407e66f31c5Sopenharmony_ciattr void \ 408e66f31c5Sopenharmony_ciname##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 409e66f31c5Sopenharmony_ci{ \ 410e66f31c5Sopenharmony_ci struct type *parent, *gparent, *tmp; \ 411e66f31c5Sopenharmony_ci while ((parent = RB_PARENT(elm, field)) != NULL && \ 412e66f31c5Sopenharmony_ci RB_COLOR(parent, field) == RB_RED) { \ 413e66f31c5Sopenharmony_ci gparent = RB_PARENT(parent, field); \ 414e66f31c5Sopenharmony_ci if (parent == RB_LEFT(gparent, field)) { \ 415e66f31c5Sopenharmony_ci tmp = RB_RIGHT(gparent, field); \ 416e66f31c5Sopenharmony_ci if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 417e66f31c5Sopenharmony_ci RB_COLOR(tmp, field) = RB_BLACK; \ 418e66f31c5Sopenharmony_ci RB_SET_BLACKRED(parent, gparent, field); \ 419e66f31c5Sopenharmony_ci elm = gparent; \ 420e66f31c5Sopenharmony_ci continue; \ 421e66f31c5Sopenharmony_ci } \ 422e66f31c5Sopenharmony_ci if (RB_RIGHT(parent, field) == elm) { \ 423e66f31c5Sopenharmony_ci RB_ROTATE_LEFT(head, parent, tmp, field); \ 424e66f31c5Sopenharmony_ci tmp = parent; \ 425e66f31c5Sopenharmony_ci parent = elm; \ 426e66f31c5Sopenharmony_ci elm = tmp; \ 427e66f31c5Sopenharmony_ci } \ 428e66f31c5Sopenharmony_ci RB_SET_BLACKRED(parent, gparent, field); \ 429e66f31c5Sopenharmony_ci RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 430e66f31c5Sopenharmony_ci } else { \ 431e66f31c5Sopenharmony_ci tmp = RB_LEFT(gparent, field); \ 432e66f31c5Sopenharmony_ci if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 433e66f31c5Sopenharmony_ci RB_COLOR(tmp, field) = RB_BLACK; \ 434e66f31c5Sopenharmony_ci RB_SET_BLACKRED(parent, gparent, field); \ 435e66f31c5Sopenharmony_ci elm = gparent; \ 436e66f31c5Sopenharmony_ci continue; \ 437e66f31c5Sopenharmony_ci } \ 438e66f31c5Sopenharmony_ci if (RB_LEFT(parent, field) == elm) { \ 439e66f31c5Sopenharmony_ci RB_ROTATE_RIGHT(head, parent, tmp, field); \ 440e66f31c5Sopenharmony_ci tmp = parent; \ 441e66f31c5Sopenharmony_ci parent = elm; \ 442e66f31c5Sopenharmony_ci elm = tmp; \ 443e66f31c5Sopenharmony_ci } \ 444e66f31c5Sopenharmony_ci RB_SET_BLACKRED(parent, gparent, field); \ 445e66f31c5Sopenharmony_ci RB_ROTATE_LEFT(head, gparent, tmp, field); \ 446e66f31c5Sopenharmony_ci } \ 447e66f31c5Sopenharmony_ci } \ 448e66f31c5Sopenharmony_ci RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 449e66f31c5Sopenharmony_ci} \ 450e66f31c5Sopenharmony_ci \ 451e66f31c5Sopenharmony_ciattr void \ 452e66f31c5Sopenharmony_ciname##_RB_REMOVE_COLOR(struct name *head, struct type *parent, \ 453e66f31c5Sopenharmony_ci struct type *elm) \ 454e66f31c5Sopenharmony_ci{ \ 455e66f31c5Sopenharmony_ci struct type *tmp; \ 456e66f31c5Sopenharmony_ci while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 457e66f31c5Sopenharmony_ci elm != RB_ROOT(head)) { \ 458e66f31c5Sopenharmony_ci if (RB_LEFT(parent, field) == elm) { \ 459e66f31c5Sopenharmony_ci tmp = RB_RIGHT(parent, field); \ 460e66f31c5Sopenharmony_ci if (RB_COLOR(tmp, field) == RB_RED) { \ 461e66f31c5Sopenharmony_ci RB_SET_BLACKRED(tmp, parent, field); \ 462e66f31c5Sopenharmony_ci RB_ROTATE_LEFT(head, parent, tmp, field); \ 463e66f31c5Sopenharmony_ci tmp = RB_RIGHT(parent, field); \ 464e66f31c5Sopenharmony_ci } \ 465e66f31c5Sopenharmony_ci if ((RB_LEFT(tmp, field) == NULL || \ 466e66f31c5Sopenharmony_ci RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 467e66f31c5Sopenharmony_ci (RB_RIGHT(tmp, field) == NULL || \ 468e66f31c5Sopenharmony_ci RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 469e66f31c5Sopenharmony_ci RB_COLOR(tmp, field) = RB_RED; \ 470e66f31c5Sopenharmony_ci elm = parent; \ 471e66f31c5Sopenharmony_ci parent = RB_PARENT(elm, field); \ 472e66f31c5Sopenharmony_ci } else { \ 473e66f31c5Sopenharmony_ci if (RB_RIGHT(tmp, field) == NULL || \ 474e66f31c5Sopenharmony_ci RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \ 475e66f31c5Sopenharmony_ci struct type *oleft; \ 476e66f31c5Sopenharmony_ci if ((oleft = RB_LEFT(tmp, field)) \ 477e66f31c5Sopenharmony_ci != NULL) \ 478e66f31c5Sopenharmony_ci RB_COLOR(oleft, field) = RB_BLACK; \ 479e66f31c5Sopenharmony_ci RB_COLOR(tmp, field) = RB_RED; \ 480e66f31c5Sopenharmony_ci RB_ROTATE_RIGHT(head, tmp, oleft, field); \ 481e66f31c5Sopenharmony_ci tmp = RB_RIGHT(parent, field); \ 482e66f31c5Sopenharmony_ci } \ 483e66f31c5Sopenharmony_ci RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 484e66f31c5Sopenharmony_ci RB_COLOR(parent, field) = RB_BLACK; \ 485e66f31c5Sopenharmony_ci if (RB_RIGHT(tmp, field)) \ 486e66f31c5Sopenharmony_ci RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ 487e66f31c5Sopenharmony_ci RB_ROTATE_LEFT(head, parent, tmp, field); \ 488e66f31c5Sopenharmony_ci elm = RB_ROOT(head); \ 489e66f31c5Sopenharmony_ci break; \ 490e66f31c5Sopenharmony_ci } \ 491e66f31c5Sopenharmony_ci } else { \ 492e66f31c5Sopenharmony_ci tmp = RB_LEFT(parent, field); \ 493e66f31c5Sopenharmony_ci if (RB_COLOR(tmp, field) == RB_RED) { \ 494e66f31c5Sopenharmony_ci RB_SET_BLACKRED(tmp, parent, field); \ 495e66f31c5Sopenharmony_ci RB_ROTATE_RIGHT(head, parent, tmp, field); \ 496e66f31c5Sopenharmony_ci tmp = RB_LEFT(parent, field); \ 497e66f31c5Sopenharmony_ci } \ 498e66f31c5Sopenharmony_ci if ((RB_LEFT(tmp, field) == NULL || \ 499e66f31c5Sopenharmony_ci RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 500e66f31c5Sopenharmony_ci (RB_RIGHT(tmp, field) == NULL || \ 501e66f31c5Sopenharmony_ci RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 502e66f31c5Sopenharmony_ci RB_COLOR(tmp, field) = RB_RED; \ 503e66f31c5Sopenharmony_ci elm = parent; \ 504e66f31c5Sopenharmony_ci parent = RB_PARENT(elm, field); \ 505e66f31c5Sopenharmony_ci } else { \ 506e66f31c5Sopenharmony_ci if (RB_LEFT(tmp, field) == NULL || \ 507e66f31c5Sopenharmony_ci RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \ 508e66f31c5Sopenharmony_ci struct type *oright; \ 509e66f31c5Sopenharmony_ci if ((oright = RB_RIGHT(tmp, field)) \ 510e66f31c5Sopenharmony_ci != NULL) \ 511e66f31c5Sopenharmony_ci RB_COLOR(oright, field) = RB_BLACK; \ 512e66f31c5Sopenharmony_ci RB_COLOR(tmp, field) = RB_RED; \ 513e66f31c5Sopenharmony_ci RB_ROTATE_LEFT(head, tmp, oright, field); \ 514e66f31c5Sopenharmony_ci tmp = RB_LEFT(parent, field); \ 515e66f31c5Sopenharmony_ci } \ 516e66f31c5Sopenharmony_ci RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 517e66f31c5Sopenharmony_ci RB_COLOR(parent, field) = RB_BLACK; \ 518e66f31c5Sopenharmony_ci if (RB_LEFT(tmp, field)) \ 519e66f31c5Sopenharmony_ci RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ 520e66f31c5Sopenharmony_ci RB_ROTATE_RIGHT(head, parent, tmp, field); \ 521e66f31c5Sopenharmony_ci elm = RB_ROOT(head); \ 522e66f31c5Sopenharmony_ci break; \ 523e66f31c5Sopenharmony_ci } \ 524e66f31c5Sopenharmony_ci } \ 525e66f31c5Sopenharmony_ci } \ 526e66f31c5Sopenharmony_ci if (elm) \ 527e66f31c5Sopenharmony_ci RB_COLOR(elm, field) = RB_BLACK; \ 528e66f31c5Sopenharmony_ci} \ 529e66f31c5Sopenharmony_ci \ 530e66f31c5Sopenharmony_ciattr struct type * \ 531e66f31c5Sopenharmony_ciname##_RB_REMOVE(struct name *head, struct type *elm) \ 532e66f31c5Sopenharmony_ci{ \ 533e66f31c5Sopenharmony_ci struct type *child, *parent, *old = elm; \ 534e66f31c5Sopenharmony_ci int color; \ 535e66f31c5Sopenharmony_ci if (RB_LEFT(elm, field) == NULL) \ 536e66f31c5Sopenharmony_ci child = RB_RIGHT(elm, field); \ 537e66f31c5Sopenharmony_ci else if (RB_RIGHT(elm, field) == NULL) \ 538e66f31c5Sopenharmony_ci child = RB_LEFT(elm, field); \ 539e66f31c5Sopenharmony_ci else { \ 540e66f31c5Sopenharmony_ci struct type *left; \ 541e66f31c5Sopenharmony_ci elm = RB_RIGHT(elm, field); \ 542e66f31c5Sopenharmony_ci while ((left = RB_LEFT(elm, field)) != NULL) \ 543e66f31c5Sopenharmony_ci elm = left; \ 544e66f31c5Sopenharmony_ci child = RB_RIGHT(elm, field); \ 545e66f31c5Sopenharmony_ci parent = RB_PARENT(elm, field); \ 546e66f31c5Sopenharmony_ci color = RB_COLOR(elm, field); \ 547e66f31c5Sopenharmony_ci if (child) \ 548e66f31c5Sopenharmony_ci RB_PARENT(child, field) = parent; \ 549e66f31c5Sopenharmony_ci if (parent) { \ 550e66f31c5Sopenharmony_ci if (RB_LEFT(parent, field) == elm) \ 551e66f31c5Sopenharmony_ci RB_LEFT(parent, field) = child; \ 552e66f31c5Sopenharmony_ci else \ 553e66f31c5Sopenharmony_ci RB_RIGHT(parent, field) = child; \ 554e66f31c5Sopenharmony_ci RB_AUGMENT(parent); \ 555e66f31c5Sopenharmony_ci } else \ 556e66f31c5Sopenharmony_ci RB_ROOT(head) = child; \ 557e66f31c5Sopenharmony_ci if (RB_PARENT(elm, field) == old) \ 558e66f31c5Sopenharmony_ci parent = elm; \ 559e66f31c5Sopenharmony_ci (elm)->field = (old)->field; \ 560e66f31c5Sopenharmony_ci if (RB_PARENT(old, field)) { \ 561e66f31c5Sopenharmony_ci if (RB_LEFT(RB_PARENT(old, field), field) == old) \ 562e66f31c5Sopenharmony_ci RB_LEFT(RB_PARENT(old, field), field) = elm; \ 563e66f31c5Sopenharmony_ci else \ 564e66f31c5Sopenharmony_ci RB_RIGHT(RB_PARENT(old, field), field) = elm; \ 565e66f31c5Sopenharmony_ci RB_AUGMENT(RB_PARENT(old, field)); \ 566e66f31c5Sopenharmony_ci } else \ 567e66f31c5Sopenharmony_ci RB_ROOT(head) = elm; \ 568e66f31c5Sopenharmony_ci RB_PARENT(RB_LEFT(old, field), field) = elm; \ 569e66f31c5Sopenharmony_ci if (RB_RIGHT(old, field)) \ 570e66f31c5Sopenharmony_ci RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 571e66f31c5Sopenharmony_ci if (parent) { \ 572e66f31c5Sopenharmony_ci left = parent; \ 573e66f31c5Sopenharmony_ci do { \ 574e66f31c5Sopenharmony_ci RB_AUGMENT(left); \ 575e66f31c5Sopenharmony_ci } while ((left = RB_PARENT(left, field)) != NULL); \ 576e66f31c5Sopenharmony_ci } \ 577e66f31c5Sopenharmony_ci goto color; \ 578e66f31c5Sopenharmony_ci } \ 579e66f31c5Sopenharmony_ci parent = RB_PARENT(elm, field); \ 580e66f31c5Sopenharmony_ci color = RB_COLOR(elm, field); \ 581e66f31c5Sopenharmony_ci if (child) \ 582e66f31c5Sopenharmony_ci RB_PARENT(child, field) = parent; \ 583e66f31c5Sopenharmony_ci if (parent) { \ 584e66f31c5Sopenharmony_ci if (RB_LEFT(parent, field) == elm) \ 585e66f31c5Sopenharmony_ci RB_LEFT(parent, field) = child; \ 586e66f31c5Sopenharmony_ci else \ 587e66f31c5Sopenharmony_ci RB_RIGHT(parent, field) = child; \ 588e66f31c5Sopenharmony_ci RB_AUGMENT(parent); \ 589e66f31c5Sopenharmony_ci } else \ 590e66f31c5Sopenharmony_ci RB_ROOT(head) = child; \ 591e66f31c5Sopenharmony_cicolor: \ 592e66f31c5Sopenharmony_ci if (color == RB_BLACK) \ 593e66f31c5Sopenharmony_ci name##_RB_REMOVE_COLOR(head, parent, child); \ 594e66f31c5Sopenharmony_ci return (old); \ 595e66f31c5Sopenharmony_ci} \ 596e66f31c5Sopenharmony_ci \ 597e66f31c5Sopenharmony_ci/* Inserts a node into the RB tree */ \ 598e66f31c5Sopenharmony_ciattr struct type * \ 599e66f31c5Sopenharmony_ciname##_RB_INSERT(struct name *head, struct type *elm) \ 600e66f31c5Sopenharmony_ci{ \ 601e66f31c5Sopenharmony_ci struct type *tmp; \ 602e66f31c5Sopenharmony_ci struct type *parent = NULL; \ 603e66f31c5Sopenharmony_ci int comp = 0; \ 604e66f31c5Sopenharmony_ci tmp = RB_ROOT(head); \ 605e66f31c5Sopenharmony_ci while (tmp) { \ 606e66f31c5Sopenharmony_ci parent = tmp; \ 607e66f31c5Sopenharmony_ci comp = (cmp)(elm, parent); \ 608e66f31c5Sopenharmony_ci if (comp < 0) \ 609e66f31c5Sopenharmony_ci tmp = RB_LEFT(tmp, field); \ 610e66f31c5Sopenharmony_ci else if (comp > 0) \ 611e66f31c5Sopenharmony_ci tmp = RB_RIGHT(tmp, field); \ 612e66f31c5Sopenharmony_ci else \ 613e66f31c5Sopenharmony_ci return (tmp); \ 614e66f31c5Sopenharmony_ci } \ 615e66f31c5Sopenharmony_ci RB_SET(elm, parent, field); \ 616e66f31c5Sopenharmony_ci if (parent != NULL) { \ 617e66f31c5Sopenharmony_ci if (comp < 0) \ 618e66f31c5Sopenharmony_ci RB_LEFT(parent, field) = elm; \ 619e66f31c5Sopenharmony_ci else \ 620e66f31c5Sopenharmony_ci RB_RIGHT(parent, field) = elm; \ 621e66f31c5Sopenharmony_ci RB_AUGMENT(parent); \ 622e66f31c5Sopenharmony_ci } else \ 623e66f31c5Sopenharmony_ci RB_ROOT(head) = elm; \ 624e66f31c5Sopenharmony_ci name##_RB_INSERT_COLOR(head, elm); \ 625e66f31c5Sopenharmony_ci return (NULL); \ 626e66f31c5Sopenharmony_ci} \ 627e66f31c5Sopenharmony_ci \ 628e66f31c5Sopenharmony_ci/* Finds the node with the same key as elm */ \ 629e66f31c5Sopenharmony_ciattr struct type * \ 630e66f31c5Sopenharmony_ciname##_RB_FIND(struct name *head, struct type *elm) \ 631e66f31c5Sopenharmony_ci{ \ 632e66f31c5Sopenharmony_ci struct type *tmp = RB_ROOT(head); \ 633e66f31c5Sopenharmony_ci int comp; \ 634e66f31c5Sopenharmony_ci while (tmp) { \ 635e66f31c5Sopenharmony_ci comp = cmp(elm, tmp); \ 636e66f31c5Sopenharmony_ci if (comp < 0) \ 637e66f31c5Sopenharmony_ci tmp = RB_LEFT(tmp, field); \ 638e66f31c5Sopenharmony_ci else if (comp > 0) \ 639e66f31c5Sopenharmony_ci tmp = RB_RIGHT(tmp, field); \ 640e66f31c5Sopenharmony_ci else \ 641e66f31c5Sopenharmony_ci return (tmp); \ 642e66f31c5Sopenharmony_ci } \ 643e66f31c5Sopenharmony_ci return (NULL); \ 644e66f31c5Sopenharmony_ci} \ 645e66f31c5Sopenharmony_ci \ 646e66f31c5Sopenharmony_ci/* Finds the first node greater than or equal to the search key */ \ 647e66f31c5Sopenharmony_ciattr struct type * \ 648e66f31c5Sopenharmony_ciname##_RB_NFIND(struct name *head, struct type *elm) \ 649e66f31c5Sopenharmony_ci{ \ 650e66f31c5Sopenharmony_ci struct type *tmp = RB_ROOT(head); \ 651e66f31c5Sopenharmony_ci struct type *res = NULL; \ 652e66f31c5Sopenharmony_ci int comp; \ 653e66f31c5Sopenharmony_ci while (tmp) { \ 654e66f31c5Sopenharmony_ci comp = cmp(elm, tmp); \ 655e66f31c5Sopenharmony_ci if (comp < 0) { \ 656e66f31c5Sopenharmony_ci res = tmp; \ 657e66f31c5Sopenharmony_ci tmp = RB_LEFT(tmp, field); \ 658e66f31c5Sopenharmony_ci } \ 659e66f31c5Sopenharmony_ci else if (comp > 0) \ 660e66f31c5Sopenharmony_ci tmp = RB_RIGHT(tmp, field); \ 661e66f31c5Sopenharmony_ci else \ 662e66f31c5Sopenharmony_ci return (tmp); \ 663e66f31c5Sopenharmony_ci } \ 664e66f31c5Sopenharmony_ci return (res); \ 665e66f31c5Sopenharmony_ci} \ 666e66f31c5Sopenharmony_ci \ 667e66f31c5Sopenharmony_ci/* ARGSUSED */ \ 668e66f31c5Sopenharmony_ciattr struct type * \ 669e66f31c5Sopenharmony_ciname##_RB_NEXT(struct type *elm) \ 670e66f31c5Sopenharmony_ci{ \ 671e66f31c5Sopenharmony_ci if (RB_RIGHT(elm, field)) { \ 672e66f31c5Sopenharmony_ci elm = RB_RIGHT(elm, field); \ 673e66f31c5Sopenharmony_ci while (RB_LEFT(elm, field)) \ 674e66f31c5Sopenharmony_ci elm = RB_LEFT(elm, field); \ 675e66f31c5Sopenharmony_ci } else { \ 676e66f31c5Sopenharmony_ci if (RB_PARENT(elm, field) && \ 677e66f31c5Sopenharmony_ci (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 678e66f31c5Sopenharmony_ci elm = RB_PARENT(elm, field); \ 679e66f31c5Sopenharmony_ci else { \ 680e66f31c5Sopenharmony_ci while (RB_PARENT(elm, field) && \ 681e66f31c5Sopenharmony_ci (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 682e66f31c5Sopenharmony_ci elm = RB_PARENT(elm, field); \ 683e66f31c5Sopenharmony_ci elm = RB_PARENT(elm, field); \ 684e66f31c5Sopenharmony_ci } \ 685e66f31c5Sopenharmony_ci } \ 686e66f31c5Sopenharmony_ci return (elm); \ 687e66f31c5Sopenharmony_ci} \ 688e66f31c5Sopenharmony_ci \ 689e66f31c5Sopenharmony_ci/* ARGSUSED */ \ 690e66f31c5Sopenharmony_ciattr struct type * \ 691e66f31c5Sopenharmony_ciname##_RB_PREV(struct type *elm) \ 692e66f31c5Sopenharmony_ci{ \ 693e66f31c5Sopenharmony_ci if (RB_LEFT(elm, field)) { \ 694e66f31c5Sopenharmony_ci elm = RB_LEFT(elm, field); \ 695e66f31c5Sopenharmony_ci while (RB_RIGHT(elm, field)) \ 696e66f31c5Sopenharmony_ci elm = RB_RIGHT(elm, field); \ 697e66f31c5Sopenharmony_ci } else { \ 698e66f31c5Sopenharmony_ci if (RB_PARENT(elm, field) && \ 699e66f31c5Sopenharmony_ci (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 700e66f31c5Sopenharmony_ci elm = RB_PARENT(elm, field); \ 701e66f31c5Sopenharmony_ci else { \ 702e66f31c5Sopenharmony_ci while (RB_PARENT(elm, field) && \ 703e66f31c5Sopenharmony_ci (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 704e66f31c5Sopenharmony_ci elm = RB_PARENT(elm, field); \ 705e66f31c5Sopenharmony_ci elm = RB_PARENT(elm, field); \ 706e66f31c5Sopenharmony_ci } \ 707e66f31c5Sopenharmony_ci } \ 708e66f31c5Sopenharmony_ci return (elm); \ 709e66f31c5Sopenharmony_ci} \ 710e66f31c5Sopenharmony_ci \ 711e66f31c5Sopenharmony_ciattr struct type * \ 712e66f31c5Sopenharmony_ciname##_RB_MINMAX(struct name *head, int val) \ 713e66f31c5Sopenharmony_ci{ \ 714e66f31c5Sopenharmony_ci struct type *tmp = RB_ROOT(head); \ 715e66f31c5Sopenharmony_ci struct type *parent = NULL; \ 716e66f31c5Sopenharmony_ci while (tmp) { \ 717e66f31c5Sopenharmony_ci parent = tmp; \ 718e66f31c5Sopenharmony_ci if (val < 0) \ 719e66f31c5Sopenharmony_ci tmp = RB_LEFT(tmp, field); \ 720e66f31c5Sopenharmony_ci else \ 721e66f31c5Sopenharmony_ci tmp = RB_RIGHT(tmp, field); \ 722e66f31c5Sopenharmony_ci } \ 723e66f31c5Sopenharmony_ci return (parent); \ 724e66f31c5Sopenharmony_ci} 725e66f31c5Sopenharmony_ci 726e66f31c5Sopenharmony_ci#define RB_NEGINF -1 727e66f31c5Sopenharmony_ci#define RB_INF 1 728e66f31c5Sopenharmony_ci 729e66f31c5Sopenharmony_ci#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 730e66f31c5Sopenharmony_ci#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 731e66f31c5Sopenharmony_ci#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 732e66f31c5Sopenharmony_ci#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 733e66f31c5Sopenharmony_ci#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 734e66f31c5Sopenharmony_ci#define RB_PREV(name, x, y) name##_RB_PREV(y) 735e66f31c5Sopenharmony_ci#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 736e66f31c5Sopenharmony_ci#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 737e66f31c5Sopenharmony_ci 738e66f31c5Sopenharmony_ci#define RB_FOREACH(x, name, head) \ 739e66f31c5Sopenharmony_ci for ((x) = RB_MIN(name, head); \ 740e66f31c5Sopenharmony_ci (x) != NULL; \ 741e66f31c5Sopenharmony_ci (x) = name##_RB_NEXT(x)) 742e66f31c5Sopenharmony_ci 743e66f31c5Sopenharmony_ci#define RB_FOREACH_FROM(x, name, y) \ 744e66f31c5Sopenharmony_ci for ((x) = (y); \ 745e66f31c5Sopenharmony_ci ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 746e66f31c5Sopenharmony_ci (x) = (y)) 747e66f31c5Sopenharmony_ci 748e66f31c5Sopenharmony_ci#define RB_FOREACH_SAFE(x, name, head, y) \ 749e66f31c5Sopenharmony_ci for ((x) = RB_MIN(name, head); \ 750e66f31c5Sopenharmony_ci ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 751e66f31c5Sopenharmony_ci (x) = (y)) 752e66f31c5Sopenharmony_ci 753e66f31c5Sopenharmony_ci#define RB_FOREACH_REVERSE(x, name, head) \ 754e66f31c5Sopenharmony_ci for ((x) = RB_MAX(name, head); \ 755e66f31c5Sopenharmony_ci (x) != NULL; \ 756e66f31c5Sopenharmony_ci (x) = name##_RB_PREV(x)) 757e66f31c5Sopenharmony_ci 758e66f31c5Sopenharmony_ci#define RB_FOREACH_REVERSE_FROM(x, name, y) \ 759e66f31c5Sopenharmony_ci for ((x) = (y); \ 760e66f31c5Sopenharmony_ci ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 761e66f31c5Sopenharmony_ci (x) = (y)) 762e66f31c5Sopenharmony_ci 763e66f31c5Sopenharmony_ci#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 764e66f31c5Sopenharmony_ci for ((x) = RB_MAX(name, head); \ 765e66f31c5Sopenharmony_ci ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 766e66f31c5Sopenharmony_ci (x) = (y)) 767e66f31c5Sopenharmony_ci 768e66f31c5Sopenharmony_ci#endif /* UV_TREE_H_ */ 769