10e552da7Schristos /*- 20e552da7Schristos * Copyright 2002 Niels Provos <provos@citi.umich.edu> 30e552da7Schristos * All rights reserved. 40e552da7Schristos * 50e552da7Schristos * Redistribution and use in source and binary forms, with or without 60e552da7Schristos * modification, are permitted provided that the following conditions 70e552da7Schristos * are met: 80e552da7Schristos * 1. Redistributions of source code must retain the above copyright 90e552da7Schristos * notice, this list of conditions and the following disclaimer. 100e552da7Schristos * 2. Redistributions in binary form must reproduce the above copyright 110e552da7Schristos * notice, this list of conditions and the following disclaimer in the 120e552da7Schristos * documentation and/or other materials provided with the distribution. 130e552da7Schristos * 140e552da7Schristos * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 150e552da7Schristos * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 160e552da7Schristos * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 170e552da7Schristos * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 180e552da7Schristos * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 190e552da7Schristos * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 200e552da7Schristos * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 210e552da7Schristos * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 220e552da7Schristos * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 230e552da7Schristos * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 240e552da7Schristos */ 250e552da7Schristos 260e552da7Schristos #ifndef UV_TREE_H_ 270e552da7Schristos #define UV_TREE_H_ 280e552da7Schristos 290e552da7Schristos #ifndef UV__UNUSED 300e552da7Schristos # if __GNUC__ 310e552da7Schristos # define UV__UNUSED __attribute__((unused)) 320e552da7Schristos # else 330e552da7Schristos # define UV__UNUSED 340e552da7Schristos # endif 350e552da7Schristos #endif 360e552da7Schristos 370e552da7Schristos /* 380e552da7Schristos * This file defines data structures for different types of trees: 390e552da7Schristos * splay trees and red-black trees. 400e552da7Schristos * 410e552da7Schristos * A splay tree is a self-organizing data structure. Every operation 420e552da7Schristos * on the tree causes a splay to happen. The splay moves the requested 430e552da7Schristos * node to the root of the tree and partly rebalances it. 440e552da7Schristos * 450e552da7Schristos * This has the benefit that request locality causes faster lookups as 460e552da7Schristos * the requested nodes move to the top of the tree. On the other hand, 470e552da7Schristos * every lookup causes memory writes. 480e552da7Schristos * 490e552da7Schristos * The Balance Theorem bounds the total access time for m operations 500e552da7Schristos * and n inserts on an initially empty tree as O((m + n)lg n). The 510e552da7Schristos * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 520e552da7Schristos * 530e552da7Schristos * A red-black tree is a binary search tree with the node color as an 540e552da7Schristos * extra attribute. It fulfills a set of conditions: 550e552da7Schristos * - every search path from the root to a leaf consists of the 560e552da7Schristos * same number of black nodes, 570e552da7Schristos * - each red node (except for the root) has a black parent, 580e552da7Schristos * - each leaf node is black. 590e552da7Schristos * 600e552da7Schristos * Every operation on a red-black tree is bounded as O(lg n). 610e552da7Schristos * The maximum height of a red-black tree is 2lg (n+1). 620e552da7Schristos */ 630e552da7Schristos 640e552da7Schristos #define SPLAY_HEAD(name, type) \ 650e552da7Schristos struct name { \ 660e552da7Schristos struct type *sph_root; /* root of the tree */ \ 670e552da7Schristos } 680e552da7Schristos 690e552da7Schristos #define SPLAY_INITIALIZER(root) \ 700e552da7Schristos { NULL } 710e552da7Schristos 720e552da7Schristos #define SPLAY_INIT(root) do { \ 730e552da7Schristos (root)->sph_root = NULL; \ 740e552da7Schristos } while (/*CONSTCOND*/ 0) 750e552da7Schristos 760e552da7Schristos #define SPLAY_ENTRY(type) \ 770e552da7Schristos struct { \ 780e552da7Schristos struct type *spe_left; /* left element */ \ 790e552da7Schristos struct type *spe_right; /* right element */ \ 800e552da7Schristos } 810e552da7Schristos 820e552da7Schristos #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 830e552da7Schristos #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 840e552da7Schristos #define SPLAY_ROOT(head) (head)->sph_root 850e552da7Schristos #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 860e552da7Schristos 870e552da7Schristos /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 880e552da7Schristos #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 890e552da7Schristos SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 900e552da7Schristos SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 910e552da7Schristos (head)->sph_root = tmp; \ 920e552da7Schristos } while (/*CONSTCOND*/ 0) 930e552da7Schristos 940e552da7Schristos #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 950e552da7Schristos SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 960e552da7Schristos SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 970e552da7Schristos (head)->sph_root = tmp; \ 980e552da7Schristos } while (/*CONSTCOND*/ 0) 990e552da7Schristos 1000e552da7Schristos #define SPLAY_LINKLEFT(head, tmp, field) do { \ 1010e552da7Schristos SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 1020e552da7Schristos tmp = (head)->sph_root; \ 1030e552da7Schristos (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 1040e552da7Schristos } while (/*CONSTCOND*/ 0) 1050e552da7Schristos 1060e552da7Schristos #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 1070e552da7Schristos SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 1080e552da7Schristos tmp = (head)->sph_root; \ 1090e552da7Schristos (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 1100e552da7Schristos } while (/*CONSTCOND*/ 0) 1110e552da7Schristos 1120e552da7Schristos #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 1130e552da7Schristos SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 1140e552da7Schristos SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field); \ 1150e552da7Schristos SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 1160e552da7Schristos SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 1170e552da7Schristos } while (/*CONSTCOND*/ 0) 1180e552da7Schristos 1190e552da7Schristos /* Generates prototypes and inline functions */ 1200e552da7Schristos 1210e552da7Schristos #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 1220e552da7Schristos void name##_SPLAY(struct name *, struct type *); \ 1230e552da7Schristos void name##_SPLAY_MINMAX(struct name *, int); \ 1240e552da7Schristos struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 1250e552da7Schristos struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 1260e552da7Schristos \ 1270e552da7Schristos /* Finds the node with the same key as elm */ \ 1280e552da7Schristos static __inline struct type * \ 1290e552da7Schristos name##_SPLAY_FIND(struct name *head, struct type *elm) \ 1300e552da7Schristos { \ 1310e552da7Schristos if (SPLAY_EMPTY(head)) \ 1320e552da7Schristos return(NULL); \ 1330e552da7Schristos name##_SPLAY(head, elm); \ 1340e552da7Schristos if ((cmp)(elm, (head)->sph_root) == 0) \ 1350e552da7Schristos return (head->sph_root); \ 1360e552da7Schristos return (NULL); \ 1370e552da7Schristos } \ 1380e552da7Schristos \ 1390e552da7Schristos static __inline struct type * \ 1400e552da7Schristos name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 1410e552da7Schristos { \ 1420e552da7Schristos name##_SPLAY(head, elm); \ 1430e552da7Schristos if (SPLAY_RIGHT(elm, field) != NULL) { \ 1440e552da7Schristos elm = SPLAY_RIGHT(elm, field); \ 1450e552da7Schristos while (SPLAY_LEFT(elm, field) != NULL) { \ 1460e552da7Schristos elm = SPLAY_LEFT(elm, field); \ 1470e552da7Schristos } \ 1480e552da7Schristos } else \ 1490e552da7Schristos elm = NULL; \ 1500e552da7Schristos return (elm); \ 1510e552da7Schristos } \ 1520e552da7Schristos \ 1530e552da7Schristos static __inline struct type * \ 1540e552da7Schristos name##_SPLAY_MIN_MAX(struct name *head, int val) \ 1550e552da7Schristos { \ 1560e552da7Schristos name##_SPLAY_MINMAX(head, val); \ 1570e552da7Schristos return (SPLAY_ROOT(head)); \ 1580e552da7Schristos } 1590e552da7Schristos 1600e552da7Schristos /* Main splay operation. 1610e552da7Schristos * Moves node close to the key of elm to top 1620e552da7Schristos */ 1630e552da7Schristos #define SPLAY_GENERATE(name, type, field, cmp) \ 1640e552da7Schristos struct type * \ 1650e552da7Schristos name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 1660e552da7Schristos { \ 1670e552da7Schristos if (SPLAY_EMPTY(head)) { \ 1680e552da7Schristos SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 1690e552da7Schristos } else { \ 1700e552da7Schristos int __comp; \ 1710e552da7Schristos name##_SPLAY(head, elm); \ 1720e552da7Schristos __comp = (cmp)(elm, (head)->sph_root); \ 1730e552da7Schristos if(__comp < 0) { \ 1740e552da7Schristos SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field); \ 1750e552da7Schristos SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 1760e552da7Schristos SPLAY_LEFT((head)->sph_root, field) = NULL; \ 1770e552da7Schristos } else if (__comp > 0) { \ 1780e552da7Schristos SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field); \ 1790e552da7Schristos SPLAY_LEFT(elm, field) = (head)->sph_root; \ 1800e552da7Schristos SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 1810e552da7Schristos } else \ 1820e552da7Schristos return ((head)->sph_root); \ 1830e552da7Schristos } \ 1840e552da7Schristos (head)->sph_root = (elm); \ 1850e552da7Schristos return (NULL); \ 1860e552da7Schristos } \ 1870e552da7Schristos \ 1880e552da7Schristos struct type * \ 1890e552da7Schristos name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 1900e552da7Schristos { \ 1910e552da7Schristos struct type *__tmp; \ 1920e552da7Schristos if (SPLAY_EMPTY(head)) \ 1930e552da7Schristos return (NULL); \ 1940e552da7Schristos name##_SPLAY(head, elm); \ 1950e552da7Schristos if ((cmp)(elm, (head)->sph_root) == 0) { \ 1960e552da7Schristos if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 1970e552da7Schristos (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 1980e552da7Schristos } else { \ 1990e552da7Schristos __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 2000e552da7Schristos (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 2010e552da7Schristos name##_SPLAY(head, elm); \ 2020e552da7Schristos SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 2030e552da7Schristos } \ 2040e552da7Schristos return (elm); \ 2050e552da7Schristos } \ 2060e552da7Schristos return (NULL); \ 2070e552da7Schristos } \ 2080e552da7Schristos \ 2090e552da7Schristos void \ 2100e552da7Schristos name##_SPLAY(struct name *head, struct type *elm) \ 2110e552da7Schristos { \ 2120e552da7Schristos struct type __node, *__left, *__right, *__tmp; \ 2130e552da7Schristos int __comp; \ 2140e552da7Schristos \ 2150e552da7Schristos SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ 2160e552da7Schristos __left = __right = &__node; \ 2170e552da7Schristos \ 2180e552da7Schristos while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 2190e552da7Schristos if (__comp < 0) { \ 2200e552da7Schristos __tmp = SPLAY_LEFT((head)->sph_root, field); \ 2210e552da7Schristos if (__tmp == NULL) \ 2220e552da7Schristos break; \ 2230e552da7Schristos if ((cmp)(elm, __tmp) < 0){ \ 2240e552da7Schristos SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 2250e552da7Schristos if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ 2260e552da7Schristos break; \ 2270e552da7Schristos } \ 2280e552da7Schristos SPLAY_LINKLEFT(head, __right, field); \ 2290e552da7Schristos } else if (__comp > 0) { \ 2300e552da7Schristos __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 2310e552da7Schristos if (__tmp == NULL) \ 2320e552da7Schristos break; \ 2330e552da7Schristos if ((cmp)(elm, __tmp) > 0){ \ 2340e552da7Schristos SPLAY_ROTATE_LEFT(head, __tmp, field); \ 2350e552da7Schristos if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ 2360e552da7Schristos break; \ 2370e552da7Schristos } \ 2380e552da7Schristos SPLAY_LINKRIGHT(head, __left, field); \ 2390e552da7Schristos } \ 2400e552da7Schristos } \ 2410e552da7Schristos SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 2420e552da7Schristos } \ 2430e552da7Schristos \ 2440e552da7Schristos /* Splay with either the minimum or the maximum element \ 2450e552da7Schristos * Used to find minimum or maximum element in tree. \ 2460e552da7Schristos */ \ 2470e552da7Schristos void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 2480e552da7Schristos { \ 2490e552da7Schristos struct type __node, *__left, *__right, *__tmp; \ 2500e552da7Schristos \ 2510e552da7Schristos SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ 2520e552da7Schristos __left = __right = &__node; \ 2530e552da7Schristos \ 254*5f2f4271Schristos for (;;) { \ 2550e552da7Schristos if (__comp < 0) { \ 2560e552da7Schristos __tmp = SPLAY_LEFT((head)->sph_root, field); \ 2570e552da7Schristos if (__tmp == NULL) \ 2580e552da7Schristos break; \ 2590e552da7Schristos if (__comp < 0){ \ 2600e552da7Schristos SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 2610e552da7Schristos if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ 2620e552da7Schristos break; \ 2630e552da7Schristos } \ 2640e552da7Schristos SPLAY_LINKLEFT(head, __right, field); \ 2650e552da7Schristos } else if (__comp > 0) { \ 2660e552da7Schristos __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 2670e552da7Schristos if (__tmp == NULL) \ 2680e552da7Schristos break; \ 2690e552da7Schristos if (__comp > 0) { \ 2700e552da7Schristos SPLAY_ROTATE_LEFT(head, __tmp, field); \ 2710e552da7Schristos if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ 2720e552da7Schristos break; \ 2730e552da7Schristos } \ 2740e552da7Schristos SPLAY_LINKRIGHT(head, __left, field); \ 2750e552da7Schristos } \ 2760e552da7Schristos } \ 2770e552da7Schristos SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 2780e552da7Schristos } 2790e552da7Schristos 2800e552da7Schristos #define SPLAY_NEGINF -1 2810e552da7Schristos #define SPLAY_INF 1 2820e552da7Schristos 2830e552da7Schristos #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 2840e552da7Schristos #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 2850e552da7Schristos #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 2860e552da7Schristos #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 2870e552da7Schristos #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 2880e552da7Schristos : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 2890e552da7Schristos #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 2900e552da7Schristos : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 2910e552da7Schristos 2920e552da7Schristos #define SPLAY_FOREACH(x, name, head) \ 2930e552da7Schristos for ((x) = SPLAY_MIN(name, head); \ 2940e552da7Schristos (x) != NULL; \ 2950e552da7Schristos (x) = SPLAY_NEXT(name, head, x)) 2960e552da7Schristos 2970e552da7Schristos /* Macros that define a red-black tree */ 2980e552da7Schristos #define RB_HEAD(name, type) \ 2990e552da7Schristos struct name { \ 3000e552da7Schristos struct type *rbh_root; /* root of the tree */ \ 3010e552da7Schristos } 3020e552da7Schristos 3030e552da7Schristos #define RB_INITIALIZER(root) \ 3040e552da7Schristos { NULL } 3050e552da7Schristos 3060e552da7Schristos #define RB_INIT(root) do { \ 3070e552da7Schristos (root)->rbh_root = NULL; \ 3080e552da7Schristos } while (/*CONSTCOND*/ 0) 3090e552da7Schristos 3100e552da7Schristos #define RB_BLACK 0 3110e552da7Schristos #define RB_RED 1 3120e552da7Schristos #define RB_ENTRY(type) \ 3130e552da7Schristos struct { \ 3140e552da7Schristos struct type *rbe_left; /* left element */ \ 3150e552da7Schristos struct type *rbe_right; /* right element */ \ 3160e552da7Schristos struct type *rbe_parent; /* parent element */ \ 3170e552da7Schristos int rbe_color; /* node color */ \ 3180e552da7Schristos } 3190e552da7Schristos 3200e552da7Schristos #define RB_LEFT(elm, field) (elm)->field.rbe_left 3210e552da7Schristos #define RB_RIGHT(elm, field) (elm)->field.rbe_right 3220e552da7Schristos #define RB_PARENT(elm, field) (elm)->field.rbe_parent 3230e552da7Schristos #define RB_COLOR(elm, field) (elm)->field.rbe_color 3240e552da7Schristos #define RB_ROOT(head) (head)->rbh_root 3250e552da7Schristos #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 3260e552da7Schristos 3270e552da7Schristos #define RB_SET(elm, parent, field) do { \ 3280e552da7Schristos RB_PARENT(elm, field) = parent; \ 3290e552da7Schristos RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 3300e552da7Schristos RB_COLOR(elm, field) = RB_RED; \ 3310e552da7Schristos } while (/*CONSTCOND*/ 0) 3320e552da7Schristos 3330e552da7Schristos #define RB_SET_BLACKRED(black, red, field) do { \ 3340e552da7Schristos RB_COLOR(black, field) = RB_BLACK; \ 3350e552da7Schristos RB_COLOR(red, field) = RB_RED; \ 3360e552da7Schristos } while (/*CONSTCOND*/ 0) 3370e552da7Schristos 3380e552da7Schristos #ifndef RB_AUGMENT 3390e552da7Schristos #define RB_AUGMENT(x) do {} while (0) 3400e552da7Schristos #endif 3410e552da7Schristos 3420e552da7Schristos #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 3430e552da7Schristos (tmp) = RB_RIGHT(elm, field); \ 3440e552da7Schristos if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 3450e552da7Schristos RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 3460e552da7Schristos } \ 3470e552da7Schristos RB_AUGMENT(elm); \ 3480e552da7Schristos if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 3490e552da7Schristos if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 3500e552da7Schristos RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 3510e552da7Schristos else \ 3520e552da7Schristos RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 3530e552da7Schristos } else \ 3540e552da7Schristos (head)->rbh_root = (tmp); \ 3550e552da7Schristos RB_LEFT(tmp, field) = (elm); \ 3560e552da7Schristos RB_PARENT(elm, field) = (tmp); \ 3570e552da7Schristos RB_AUGMENT(tmp); \ 3580e552da7Schristos if ((RB_PARENT(tmp, field))) \ 3590e552da7Schristos RB_AUGMENT(RB_PARENT(tmp, field)); \ 3600e552da7Schristos } while (/*CONSTCOND*/ 0) 3610e552da7Schristos 3620e552da7Schristos #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 3630e552da7Schristos (tmp) = RB_LEFT(elm, field); \ 3640e552da7Schristos if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 3650e552da7Schristos RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 3660e552da7Schristos } \ 3670e552da7Schristos RB_AUGMENT(elm); \ 3680e552da7Schristos if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 3690e552da7Schristos if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 3700e552da7Schristos RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 3710e552da7Schristos else \ 3720e552da7Schristos RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 3730e552da7Schristos } else \ 3740e552da7Schristos (head)->rbh_root = (tmp); \ 3750e552da7Schristos RB_RIGHT(tmp, field) = (elm); \ 3760e552da7Schristos RB_PARENT(elm, field) = (tmp); \ 3770e552da7Schristos RB_AUGMENT(tmp); \ 3780e552da7Schristos if ((RB_PARENT(tmp, field))) \ 3790e552da7Schristos RB_AUGMENT(RB_PARENT(tmp, field)); \ 3800e552da7Schristos } while (/*CONSTCOND*/ 0) 3810e552da7Schristos 3820e552da7Schristos /* Generates prototypes and inline functions */ 3830e552da7Schristos #define RB_PROTOTYPE(name, type, field, cmp) \ 3840e552da7Schristos RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 3850e552da7Schristos #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 3860e552da7Schristos RB_PROTOTYPE_INTERNAL(name, type, field, cmp, UV__UNUSED static) 3870e552da7Schristos #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 3880e552da7Schristos attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 3890e552da7Schristos attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 3900e552da7Schristos attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 3910e552da7Schristos attr struct type *name##_RB_INSERT(struct name *, struct type *); \ 3920e552da7Schristos attr struct type *name##_RB_FIND(struct name *, struct type *); \ 3930e552da7Schristos attr struct type *name##_RB_NFIND(struct name *, struct type *); \ 3940e552da7Schristos attr struct type *name##_RB_NEXT(struct type *); \ 3950e552da7Schristos attr struct type *name##_RB_PREV(struct type *); \ 3960e552da7Schristos attr struct type *name##_RB_MINMAX(struct name *, int); \ 3970e552da7Schristos \ 3980e552da7Schristos 3990e552da7Schristos /* Main rb operation. 4000e552da7Schristos * Moves node close to the key of elm to top 4010e552da7Schristos */ 4020e552da7Schristos #define RB_GENERATE(name, type, field, cmp) \ 4030e552da7Schristos RB_GENERATE_INTERNAL(name, type, field, cmp,) 4040e552da7Schristos #define RB_GENERATE_STATIC(name, type, field, cmp) \ 4050e552da7Schristos RB_GENERATE_INTERNAL(name, type, field, cmp, UV__UNUSED static) 4060e552da7Schristos #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 4070e552da7Schristos attr void \ 4080e552da7Schristos name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 4090e552da7Schristos { \ 4100e552da7Schristos struct type *parent, *gparent, *tmp; \ 4110e552da7Schristos while ((parent = RB_PARENT(elm, field)) != NULL && \ 4120e552da7Schristos RB_COLOR(parent, field) == RB_RED) { \ 4130e552da7Schristos gparent = RB_PARENT(parent, field); \ 4140e552da7Schristos if (parent == RB_LEFT(gparent, field)) { \ 4150e552da7Schristos tmp = RB_RIGHT(gparent, field); \ 4160e552da7Schristos if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 4170e552da7Schristos RB_COLOR(tmp, field) = RB_BLACK; \ 4180e552da7Schristos RB_SET_BLACKRED(parent, gparent, field); \ 4190e552da7Schristos elm = gparent; \ 4200e552da7Schristos continue; \ 4210e552da7Schristos } \ 4220e552da7Schristos if (RB_RIGHT(parent, field) == elm) { \ 4230e552da7Schristos RB_ROTATE_LEFT(head, parent, tmp, field); \ 4240e552da7Schristos tmp = parent; \ 4250e552da7Schristos parent = elm; \ 4260e552da7Schristos elm = tmp; \ 4270e552da7Schristos } \ 4280e552da7Schristos RB_SET_BLACKRED(parent, gparent, field); \ 4290e552da7Schristos RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 4300e552da7Schristos } else { \ 4310e552da7Schristos tmp = RB_LEFT(gparent, field); \ 4320e552da7Schristos if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 4330e552da7Schristos RB_COLOR(tmp, field) = RB_BLACK; \ 4340e552da7Schristos RB_SET_BLACKRED(parent, gparent, field); \ 4350e552da7Schristos elm = gparent; \ 4360e552da7Schristos continue; \ 4370e552da7Schristos } \ 4380e552da7Schristos if (RB_LEFT(parent, field) == elm) { \ 4390e552da7Schristos RB_ROTATE_RIGHT(head, parent, tmp, field); \ 4400e552da7Schristos tmp = parent; \ 4410e552da7Schristos parent = elm; \ 4420e552da7Schristos elm = tmp; \ 4430e552da7Schristos } \ 4440e552da7Schristos RB_SET_BLACKRED(parent, gparent, field); \ 4450e552da7Schristos RB_ROTATE_LEFT(head, gparent, tmp, field); \ 4460e552da7Schristos } \ 4470e552da7Schristos } \ 4480e552da7Schristos RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 4490e552da7Schristos } \ 4500e552da7Schristos \ 4510e552da7Schristos attr void \ 4520e552da7Schristos name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, \ 4530e552da7Schristos struct type *elm) \ 4540e552da7Schristos { \ 4550e552da7Schristos struct type *tmp; \ 4560e552da7Schristos while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 4570e552da7Schristos elm != RB_ROOT(head)) { \ 4580e552da7Schristos if (RB_LEFT(parent, field) == elm) { \ 4590e552da7Schristos tmp = RB_RIGHT(parent, field); \ 4600e552da7Schristos if (RB_COLOR(tmp, field) == RB_RED) { \ 4610e552da7Schristos RB_SET_BLACKRED(tmp, parent, field); \ 4620e552da7Schristos RB_ROTATE_LEFT(head, parent, tmp, field); \ 4630e552da7Schristos tmp = RB_RIGHT(parent, field); \ 4640e552da7Schristos } \ 4650e552da7Schristos if ((RB_LEFT(tmp, field) == NULL || \ 4660e552da7Schristos RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 4670e552da7Schristos (RB_RIGHT(tmp, field) == NULL || \ 4680e552da7Schristos RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 4690e552da7Schristos RB_COLOR(tmp, field) = RB_RED; \ 4700e552da7Schristos elm = parent; \ 4710e552da7Schristos parent = RB_PARENT(elm, field); \ 4720e552da7Schristos } else { \ 4730e552da7Schristos if (RB_RIGHT(tmp, field) == NULL || \ 4740e552da7Schristos RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \ 4750e552da7Schristos struct type *oleft; \ 4760e552da7Schristos if ((oleft = RB_LEFT(tmp, field)) \ 4770e552da7Schristos != NULL) \ 4780e552da7Schristos RB_COLOR(oleft, field) = RB_BLACK; \ 4790e552da7Schristos RB_COLOR(tmp, field) = RB_RED; \ 4800e552da7Schristos RB_ROTATE_RIGHT(head, tmp, oleft, field); \ 4810e552da7Schristos tmp = RB_RIGHT(parent, field); \ 4820e552da7Schristos } \ 4830e552da7Schristos RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 4840e552da7Schristos RB_COLOR(parent, field) = RB_BLACK; \ 4850e552da7Schristos if (RB_RIGHT(tmp, field)) \ 4860e552da7Schristos RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ 4870e552da7Schristos RB_ROTATE_LEFT(head, parent, tmp, field); \ 4880e552da7Schristos elm = RB_ROOT(head); \ 4890e552da7Schristos break; \ 4900e552da7Schristos } \ 4910e552da7Schristos } else { \ 4920e552da7Schristos tmp = RB_LEFT(parent, field); \ 4930e552da7Schristos if (RB_COLOR(tmp, field) == RB_RED) { \ 4940e552da7Schristos RB_SET_BLACKRED(tmp, parent, field); \ 4950e552da7Schristos RB_ROTATE_RIGHT(head, parent, tmp, field); \ 4960e552da7Schristos tmp = RB_LEFT(parent, field); \ 4970e552da7Schristos } \ 4980e552da7Schristos if ((RB_LEFT(tmp, field) == NULL || \ 4990e552da7Schristos RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 5000e552da7Schristos (RB_RIGHT(tmp, field) == NULL || \ 5010e552da7Schristos RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 5020e552da7Schristos RB_COLOR(tmp, field) = RB_RED; \ 5030e552da7Schristos elm = parent; \ 5040e552da7Schristos parent = RB_PARENT(elm, field); \ 5050e552da7Schristos } else { \ 5060e552da7Schristos if (RB_LEFT(tmp, field) == NULL || \ 5070e552da7Schristos RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \ 5080e552da7Schristos struct type *oright; \ 5090e552da7Schristos if ((oright = RB_RIGHT(tmp, field)) \ 5100e552da7Schristos != NULL) \ 5110e552da7Schristos RB_COLOR(oright, field) = RB_BLACK; \ 5120e552da7Schristos RB_COLOR(tmp, field) = RB_RED; \ 5130e552da7Schristos RB_ROTATE_LEFT(head, tmp, oright, field); \ 5140e552da7Schristos tmp = RB_LEFT(parent, field); \ 5150e552da7Schristos } \ 5160e552da7Schristos RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 5170e552da7Schristos RB_COLOR(parent, field) = RB_BLACK; \ 5180e552da7Schristos if (RB_LEFT(tmp, field)) \ 5190e552da7Schristos RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ 5200e552da7Schristos RB_ROTATE_RIGHT(head, parent, tmp, field); \ 5210e552da7Schristos elm = RB_ROOT(head); \ 5220e552da7Schristos break; \ 5230e552da7Schristos } \ 5240e552da7Schristos } \ 5250e552da7Schristos } \ 5260e552da7Schristos if (elm) \ 5270e552da7Schristos RB_COLOR(elm, field) = RB_BLACK; \ 5280e552da7Schristos } \ 5290e552da7Schristos \ 5300e552da7Schristos attr struct type * \ 5310e552da7Schristos name##_RB_REMOVE(struct name *head, struct type *elm) \ 5320e552da7Schristos { \ 5330e552da7Schristos struct type *child, *parent, *old = elm; \ 5340e552da7Schristos int color; \ 5350e552da7Schristos if (RB_LEFT(elm, field) == NULL) \ 5360e552da7Schristos child = RB_RIGHT(elm, field); \ 5370e552da7Schristos else if (RB_RIGHT(elm, field) == NULL) \ 5380e552da7Schristos child = RB_LEFT(elm, field); \ 5390e552da7Schristos else { \ 5400e552da7Schristos struct type *left; \ 5410e552da7Schristos elm = RB_RIGHT(elm, field); \ 5420e552da7Schristos while ((left = RB_LEFT(elm, field)) != NULL) \ 5430e552da7Schristos elm = left; \ 5440e552da7Schristos child = RB_RIGHT(elm, field); \ 5450e552da7Schristos parent = RB_PARENT(elm, field); \ 5460e552da7Schristos color = RB_COLOR(elm, field); \ 5470e552da7Schristos if (child) \ 5480e552da7Schristos RB_PARENT(child, field) = parent; \ 5490e552da7Schristos if (parent) { \ 5500e552da7Schristos if (RB_LEFT(parent, field) == elm) \ 5510e552da7Schristos RB_LEFT(parent, field) = child; \ 5520e552da7Schristos else \ 5530e552da7Schristos RB_RIGHT(parent, field) = child; \ 5540e552da7Schristos RB_AUGMENT(parent); \ 5550e552da7Schristos } else \ 5560e552da7Schristos RB_ROOT(head) = child; \ 5570e552da7Schristos if (RB_PARENT(elm, field) == old) \ 5580e552da7Schristos parent = elm; \ 5590e552da7Schristos (elm)->field = (old)->field; \ 5600e552da7Schristos if (RB_PARENT(old, field)) { \ 5610e552da7Schristos if (RB_LEFT(RB_PARENT(old, field), field) == old) \ 5620e552da7Schristos RB_LEFT(RB_PARENT(old, field), field) = elm; \ 5630e552da7Schristos else \ 5640e552da7Schristos RB_RIGHT(RB_PARENT(old, field), field) = elm; \ 5650e552da7Schristos RB_AUGMENT(RB_PARENT(old, field)); \ 5660e552da7Schristos } else \ 5670e552da7Schristos RB_ROOT(head) = elm; \ 5680e552da7Schristos RB_PARENT(RB_LEFT(old, field), field) = elm; \ 5690e552da7Schristos if (RB_RIGHT(old, field)) \ 5700e552da7Schristos RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 5710e552da7Schristos if (parent) { \ 5720e552da7Schristos left = parent; \ 5730e552da7Schristos do { \ 5740e552da7Schristos RB_AUGMENT(left); \ 5750e552da7Schristos } while ((left = RB_PARENT(left, field)) != NULL); \ 5760e552da7Schristos } \ 5770e552da7Schristos goto color; \ 5780e552da7Schristos } \ 5790e552da7Schristos parent = RB_PARENT(elm, field); \ 5800e552da7Schristos color = RB_COLOR(elm, field); \ 5810e552da7Schristos if (child) \ 5820e552da7Schristos RB_PARENT(child, field) = parent; \ 5830e552da7Schristos if (parent) { \ 5840e552da7Schristos if (RB_LEFT(parent, field) == elm) \ 5850e552da7Schristos RB_LEFT(parent, field) = child; \ 5860e552da7Schristos else \ 5870e552da7Schristos RB_RIGHT(parent, field) = child; \ 5880e552da7Schristos RB_AUGMENT(parent); \ 5890e552da7Schristos } else \ 5900e552da7Schristos RB_ROOT(head) = child; \ 5910e552da7Schristos color: \ 5920e552da7Schristos if (color == RB_BLACK) \ 5930e552da7Schristos name##_RB_REMOVE_COLOR(head, parent, child); \ 5940e552da7Schristos return (old); \ 5950e552da7Schristos } \ 5960e552da7Schristos \ 5970e552da7Schristos /* Inserts a node into the RB tree */ \ 5980e552da7Schristos attr struct type * \ 5990e552da7Schristos name##_RB_INSERT(struct name *head, struct type *elm) \ 6000e552da7Schristos { \ 6010e552da7Schristos struct type *tmp; \ 6020e552da7Schristos struct type *parent = NULL; \ 6030e552da7Schristos int comp = 0; \ 6040e552da7Schristos tmp = RB_ROOT(head); \ 6050e552da7Schristos while (tmp) { \ 6060e552da7Schristos parent = tmp; \ 6070e552da7Schristos comp = (cmp)(elm, parent); \ 6080e552da7Schristos if (comp < 0) \ 6090e552da7Schristos tmp = RB_LEFT(tmp, field); \ 6100e552da7Schristos else if (comp > 0) \ 6110e552da7Schristos tmp = RB_RIGHT(tmp, field); \ 6120e552da7Schristos else \ 6130e552da7Schristos return (tmp); \ 6140e552da7Schristos } \ 6150e552da7Schristos RB_SET(elm, parent, field); \ 6160e552da7Schristos if (parent != NULL) { \ 6170e552da7Schristos if (comp < 0) \ 6180e552da7Schristos RB_LEFT(parent, field) = elm; \ 6190e552da7Schristos else \ 6200e552da7Schristos RB_RIGHT(parent, field) = elm; \ 6210e552da7Schristos RB_AUGMENT(parent); \ 6220e552da7Schristos } else \ 6230e552da7Schristos RB_ROOT(head) = elm; \ 6240e552da7Schristos name##_RB_INSERT_COLOR(head, elm); \ 6250e552da7Schristos return (NULL); \ 6260e552da7Schristos } \ 6270e552da7Schristos \ 6280e552da7Schristos /* Finds the node with the same key as elm */ \ 6290e552da7Schristos attr struct type * \ 6300e552da7Schristos name##_RB_FIND(struct name *head, struct type *elm) \ 6310e552da7Schristos { \ 6320e552da7Schristos struct type *tmp = RB_ROOT(head); \ 6330e552da7Schristos int comp; \ 6340e552da7Schristos while (tmp) { \ 6350e552da7Schristos comp = cmp(elm, tmp); \ 6360e552da7Schristos if (comp < 0) \ 6370e552da7Schristos tmp = RB_LEFT(tmp, field); \ 6380e552da7Schristos else if (comp > 0) \ 6390e552da7Schristos tmp = RB_RIGHT(tmp, field); \ 6400e552da7Schristos else \ 6410e552da7Schristos return (tmp); \ 6420e552da7Schristos } \ 6430e552da7Schristos return (NULL); \ 6440e552da7Schristos } \ 6450e552da7Schristos \ 6460e552da7Schristos /* Finds the first node greater than or equal to the search key */ \ 6470e552da7Schristos attr struct type * \ 6480e552da7Schristos name##_RB_NFIND(struct name *head, struct type *elm) \ 6490e552da7Schristos { \ 6500e552da7Schristos struct type *tmp = RB_ROOT(head); \ 6510e552da7Schristos struct type *res = NULL; \ 6520e552da7Schristos int comp; \ 6530e552da7Schristos while (tmp) { \ 6540e552da7Schristos comp = cmp(elm, tmp); \ 6550e552da7Schristos if (comp < 0) { \ 6560e552da7Schristos res = tmp; \ 6570e552da7Schristos tmp = RB_LEFT(tmp, field); \ 6580e552da7Schristos } \ 6590e552da7Schristos else if (comp > 0) \ 6600e552da7Schristos tmp = RB_RIGHT(tmp, field); \ 6610e552da7Schristos else \ 6620e552da7Schristos return (tmp); \ 6630e552da7Schristos } \ 6640e552da7Schristos return (res); \ 6650e552da7Schristos } \ 6660e552da7Schristos \ 6670e552da7Schristos /* ARGSUSED */ \ 6680e552da7Schristos attr struct type * \ 6690e552da7Schristos name##_RB_NEXT(struct type *elm) \ 6700e552da7Schristos { \ 6710e552da7Schristos if (RB_RIGHT(elm, field)) { \ 6720e552da7Schristos elm = RB_RIGHT(elm, field); \ 6730e552da7Schristos while (RB_LEFT(elm, field)) \ 6740e552da7Schristos elm = RB_LEFT(elm, field); \ 6750e552da7Schristos } else { \ 6760e552da7Schristos if (RB_PARENT(elm, field) && \ 6770e552da7Schristos (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 6780e552da7Schristos elm = RB_PARENT(elm, field); \ 6790e552da7Schristos else { \ 6800e552da7Schristos while (RB_PARENT(elm, field) && \ 6810e552da7Schristos (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 6820e552da7Schristos elm = RB_PARENT(elm, field); \ 6830e552da7Schristos elm = RB_PARENT(elm, field); \ 6840e552da7Schristos } \ 6850e552da7Schristos } \ 6860e552da7Schristos return (elm); \ 6870e552da7Schristos } \ 6880e552da7Schristos \ 6890e552da7Schristos /* ARGSUSED */ \ 6900e552da7Schristos attr struct type * \ 6910e552da7Schristos name##_RB_PREV(struct type *elm) \ 6920e552da7Schristos { \ 6930e552da7Schristos if (RB_LEFT(elm, field)) { \ 6940e552da7Schristos elm = RB_LEFT(elm, field); \ 6950e552da7Schristos while (RB_RIGHT(elm, field)) \ 6960e552da7Schristos elm = RB_RIGHT(elm, field); \ 6970e552da7Schristos } else { \ 6980e552da7Schristos if (RB_PARENT(elm, field) && \ 6990e552da7Schristos (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 7000e552da7Schristos elm = RB_PARENT(elm, field); \ 7010e552da7Schristos else { \ 7020e552da7Schristos while (RB_PARENT(elm, field) && \ 7030e552da7Schristos (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 7040e552da7Schristos elm = RB_PARENT(elm, field); \ 7050e552da7Schristos elm = RB_PARENT(elm, field); \ 7060e552da7Schristos } \ 7070e552da7Schristos } \ 7080e552da7Schristos return (elm); \ 7090e552da7Schristos } \ 7100e552da7Schristos \ 7110e552da7Schristos attr struct type * \ 7120e552da7Schristos name##_RB_MINMAX(struct name *head, int val) \ 7130e552da7Schristos { \ 7140e552da7Schristos struct type *tmp = RB_ROOT(head); \ 7150e552da7Schristos struct type *parent = NULL; \ 7160e552da7Schristos while (tmp) { \ 7170e552da7Schristos parent = tmp; \ 7180e552da7Schristos if (val < 0) \ 7190e552da7Schristos tmp = RB_LEFT(tmp, field); \ 7200e552da7Schristos else \ 7210e552da7Schristos tmp = RB_RIGHT(tmp, field); \ 7220e552da7Schristos } \ 7230e552da7Schristos return (parent); \ 7240e552da7Schristos } 7250e552da7Schristos 7260e552da7Schristos #define RB_NEGINF -1 7270e552da7Schristos #define RB_INF 1 7280e552da7Schristos 7290e552da7Schristos #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 7300e552da7Schristos #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 7310e552da7Schristos #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 7320e552da7Schristos #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 7330e552da7Schristos #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 7340e552da7Schristos #define RB_PREV(name, x, y) name##_RB_PREV(y) 7350e552da7Schristos #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 7360e552da7Schristos #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 7370e552da7Schristos 7380e552da7Schristos #define RB_FOREACH(x, name, head) \ 7390e552da7Schristos for ((x) = RB_MIN(name, head); \ 7400e552da7Schristos (x) != NULL; \ 7410e552da7Schristos (x) = name##_RB_NEXT(x)) 7420e552da7Schristos 7430e552da7Schristos #define RB_FOREACH_FROM(x, name, y) \ 7440e552da7Schristos for ((x) = (y); \ 7450e552da7Schristos ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 7460e552da7Schristos (x) = (y)) 7470e552da7Schristos 7480e552da7Schristos #define RB_FOREACH_SAFE(x, name, head, y) \ 7490e552da7Schristos for ((x) = RB_MIN(name, head); \ 7500e552da7Schristos ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 7510e552da7Schristos (x) = (y)) 7520e552da7Schristos 7530e552da7Schristos #define RB_FOREACH_REVERSE(x, name, head) \ 7540e552da7Schristos for ((x) = RB_MAX(name, head); \ 7550e552da7Schristos (x) != NULL; \ 7560e552da7Schristos (x) = name##_RB_PREV(x)) 7570e552da7Schristos 7580e552da7Schristos #define RB_FOREACH_REVERSE_FROM(x, name, y) \ 7590e552da7Schristos for ((x) = (y); \ 7600e552da7Schristos ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 7610e552da7Schristos (x) = (y)) 7620e552da7Schristos 7630e552da7Schristos #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 7640e552da7Schristos for ((x) = RB_MAX(name, head); \ 7650e552da7Schristos ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 7660e552da7Schristos (x) = (y)) 7670e552da7Schristos 7680e552da7Schristos #endif /* UV_TREE_H_ */ 769