1d0c8c0bcSDag-Erling Smørgrav /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 24b17dab0SDag-Erling Smørgrav /* 34b17dab0SDag-Erling Smørgrav * Copyright 2002 Niels Provos <provos@citi.umich.edu> 44b17dab0SDag-Erling Smørgrav * All rights reserved. 54b17dab0SDag-Erling Smørgrav * 64b17dab0SDag-Erling Smørgrav * Redistribution and use in source and binary forms, with or without 74b17dab0SDag-Erling Smørgrav * modification, are permitted provided that the following conditions 84b17dab0SDag-Erling Smørgrav * are met: 94b17dab0SDag-Erling Smørgrav * 1. Redistributions of source code must retain the above copyright 104b17dab0SDag-Erling Smørgrav * notice, this list of conditions and the following disclaimer. 114b17dab0SDag-Erling Smørgrav * 2. Redistributions in binary form must reproduce the above copyright 124b17dab0SDag-Erling Smørgrav * notice, this list of conditions and the following disclaimer in the 134b17dab0SDag-Erling Smørgrav * documentation and/or other materials provided with the distribution. 144b17dab0SDag-Erling Smørgrav * 154b17dab0SDag-Erling Smørgrav * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 164b17dab0SDag-Erling Smørgrav * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 174b17dab0SDag-Erling Smørgrav * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 184b17dab0SDag-Erling Smørgrav * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 194b17dab0SDag-Erling Smørgrav * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 204b17dab0SDag-Erling Smørgrav * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 214b17dab0SDag-Erling Smørgrav * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 224b17dab0SDag-Erling Smørgrav * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 234b17dab0SDag-Erling Smørgrav * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 244b17dab0SDag-Erling Smørgrav * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 254b17dab0SDag-Erling Smørgrav */ 264b17dab0SDag-Erling Smørgrav 274b17dab0SDag-Erling Smørgrav #ifndef _SYS_TREE_H_ 284b17dab0SDag-Erling Smørgrav #define _SYS_TREE_H_ 294b17dab0SDag-Erling Smørgrav 304b17dab0SDag-Erling Smørgrav /* 314b17dab0SDag-Erling Smørgrav * This file defines data structures for different types of trees: 324b17dab0SDag-Erling Smørgrav * splay trees and red-black trees. 334b17dab0SDag-Erling Smørgrav * 344b17dab0SDag-Erling Smørgrav * A splay tree is a self-organizing data structure. Every operation 354b17dab0SDag-Erling Smørgrav * on the tree causes a splay to happen. The splay moves the requested 364b17dab0SDag-Erling Smørgrav * node to the root of the tree and partly rebalances it. 374b17dab0SDag-Erling Smørgrav * 384b17dab0SDag-Erling Smørgrav * This has the benefit that request locality causes faster lookups as 394b17dab0SDag-Erling Smørgrav * the requested nodes move to the top of the tree. On the other hand, 404b17dab0SDag-Erling Smørgrav * every lookup causes memory writes. 414b17dab0SDag-Erling Smørgrav * 424b17dab0SDag-Erling Smørgrav * The Balance Theorem bounds the total access time for m operations 434b17dab0SDag-Erling Smørgrav * and n inserts on an initially empty tree as O((m + n)lg n). The 444b17dab0SDag-Erling Smørgrav * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 454b17dab0SDag-Erling Smørgrav * 464b17dab0SDag-Erling Smørgrav * A red-black tree is a binary search tree with the node color as an 474b17dab0SDag-Erling Smørgrav * extra attribute. It fulfills a set of conditions: 484b17dab0SDag-Erling Smørgrav * - every search path from the root to a leaf consists of the 494b17dab0SDag-Erling Smørgrav * same number of black nodes, 504b17dab0SDag-Erling Smørgrav * - each red node (except for the root) has a black parent, 514b17dab0SDag-Erling Smørgrav * - each leaf node is black. 524b17dab0SDag-Erling Smørgrav * 534b17dab0SDag-Erling Smørgrav * Every operation on a red-black tree is bounded as O(lg n). 544b17dab0SDag-Erling Smørgrav * The maximum height of a red-black tree is 2lg (n+1). 554b17dab0SDag-Erling Smørgrav */ 564b17dab0SDag-Erling Smørgrav 574b17dab0SDag-Erling Smørgrav #define SPLAY_HEAD(name, type) \ 584b17dab0SDag-Erling Smørgrav struct name { \ 594b17dab0SDag-Erling Smørgrav struct type *sph_root; /* root of the tree */ \ 604b17dab0SDag-Erling Smørgrav } 614b17dab0SDag-Erling Smørgrav 624b17dab0SDag-Erling Smørgrav #define SPLAY_INITIALIZER(root) \ 634b17dab0SDag-Erling Smørgrav { NULL } 644b17dab0SDag-Erling Smørgrav 654b17dab0SDag-Erling Smørgrav #define SPLAY_INIT(root) do { \ 664b17dab0SDag-Erling Smørgrav (root)->sph_root = NULL; \ 674b17dab0SDag-Erling Smørgrav } while (0) 684b17dab0SDag-Erling Smørgrav 694b17dab0SDag-Erling Smørgrav #define SPLAY_ENTRY(type) \ 704b17dab0SDag-Erling Smørgrav struct { \ 714b17dab0SDag-Erling Smørgrav struct type *spe_left; /* left element */ \ 724b17dab0SDag-Erling Smørgrav struct type *spe_right; /* right element */ \ 734b17dab0SDag-Erling Smørgrav } 744b17dab0SDag-Erling Smørgrav 754b17dab0SDag-Erling Smørgrav #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 764b17dab0SDag-Erling Smørgrav #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 774b17dab0SDag-Erling Smørgrav #define SPLAY_ROOT(head) (head)->sph_root 784b17dab0SDag-Erling Smørgrav #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 794b17dab0SDag-Erling Smørgrav 804b17dab0SDag-Erling Smørgrav /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 814b17dab0SDag-Erling Smørgrav #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 824b17dab0SDag-Erling Smørgrav SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 834b17dab0SDag-Erling Smørgrav SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 844b17dab0SDag-Erling Smørgrav (head)->sph_root = tmp; \ 854b17dab0SDag-Erling Smørgrav } while (0) 864b17dab0SDag-Erling Smørgrav 874b17dab0SDag-Erling Smørgrav #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 884b17dab0SDag-Erling Smørgrav SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 894b17dab0SDag-Erling Smørgrav SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 904b17dab0SDag-Erling Smørgrav (head)->sph_root = tmp; \ 914b17dab0SDag-Erling Smørgrav } while (0) 924b17dab0SDag-Erling Smørgrav 934b17dab0SDag-Erling Smørgrav #define SPLAY_LINKLEFT(head, tmp, field) do { \ 944b17dab0SDag-Erling Smørgrav SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 954b17dab0SDag-Erling Smørgrav tmp = (head)->sph_root; \ 964b17dab0SDag-Erling Smørgrav (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 974b17dab0SDag-Erling Smørgrav } while (0) 984b17dab0SDag-Erling Smørgrav 994b17dab0SDag-Erling Smørgrav #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 1004b17dab0SDag-Erling Smørgrav SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 1014b17dab0SDag-Erling Smørgrav tmp = (head)->sph_root; \ 1024b17dab0SDag-Erling Smørgrav (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 1034b17dab0SDag-Erling Smørgrav } while (0) 1044b17dab0SDag-Erling Smørgrav 1054b17dab0SDag-Erling Smørgrav #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 1064b17dab0SDag-Erling Smørgrav SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 1074b17dab0SDag-Erling Smørgrav SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 1084b17dab0SDag-Erling Smørgrav SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 1094b17dab0SDag-Erling Smørgrav SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 1104b17dab0SDag-Erling Smørgrav } while (0) 1114b17dab0SDag-Erling Smørgrav 1124b17dab0SDag-Erling Smørgrav /* Generates prototypes and inline functions */ 1134b17dab0SDag-Erling Smørgrav 1144b17dab0SDag-Erling Smørgrav #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 1154b17dab0SDag-Erling Smørgrav void name##_SPLAY(struct name *, struct type *); \ 1164b17dab0SDag-Erling Smørgrav void name##_SPLAY_MINMAX(struct name *, int); \ 1174b17dab0SDag-Erling Smørgrav struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 1184b17dab0SDag-Erling Smørgrav struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 1194b17dab0SDag-Erling Smørgrav \ 1204b17dab0SDag-Erling Smørgrav /* Finds the node with the same key as elm */ \ 1214b17dab0SDag-Erling Smørgrav static __inline struct type * \ 1224b17dab0SDag-Erling Smørgrav name##_SPLAY_FIND(struct name *head, struct type *elm) \ 1234b17dab0SDag-Erling Smørgrav { \ 1244b17dab0SDag-Erling Smørgrav if (SPLAY_EMPTY(head)) \ 1254b17dab0SDag-Erling Smørgrav return(NULL); \ 1264b17dab0SDag-Erling Smørgrav name##_SPLAY(head, elm); \ 1274b17dab0SDag-Erling Smørgrav if ((cmp)(elm, (head)->sph_root) == 0) \ 1284b17dab0SDag-Erling Smørgrav return (head->sph_root); \ 1294b17dab0SDag-Erling Smørgrav return (NULL); \ 1304b17dab0SDag-Erling Smørgrav } \ 1314b17dab0SDag-Erling Smørgrav \ 1324b17dab0SDag-Erling Smørgrav static __inline struct type * \ 1334b17dab0SDag-Erling Smørgrav name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 1344b17dab0SDag-Erling Smørgrav { \ 1354b17dab0SDag-Erling Smørgrav name##_SPLAY(head, elm); \ 1364b17dab0SDag-Erling Smørgrav if (SPLAY_RIGHT(elm, field) != NULL) { \ 1374b17dab0SDag-Erling Smørgrav elm = SPLAY_RIGHT(elm, field); \ 1384b17dab0SDag-Erling Smørgrav while (SPLAY_LEFT(elm, field) != NULL) { \ 1394b17dab0SDag-Erling Smørgrav elm = SPLAY_LEFT(elm, field); \ 1404b17dab0SDag-Erling Smørgrav } \ 1414b17dab0SDag-Erling Smørgrav } else \ 1424b17dab0SDag-Erling Smørgrav elm = NULL; \ 1434b17dab0SDag-Erling Smørgrav return (elm); \ 1444b17dab0SDag-Erling Smørgrav } \ 1454b17dab0SDag-Erling Smørgrav \ 1464b17dab0SDag-Erling Smørgrav static __inline struct type * \ 1474b17dab0SDag-Erling Smørgrav name##_SPLAY_MIN_MAX(struct name *head, int val) \ 1484b17dab0SDag-Erling Smørgrav { \ 1494b17dab0SDag-Erling Smørgrav name##_SPLAY_MINMAX(head, val); \ 1504b17dab0SDag-Erling Smørgrav return (SPLAY_ROOT(head)); \ 1514b17dab0SDag-Erling Smørgrav } 1524b17dab0SDag-Erling Smørgrav 1534b17dab0SDag-Erling Smørgrav /* Main splay operation. 1544b17dab0SDag-Erling Smørgrav * Moves node close to the key of elm to top 1554b17dab0SDag-Erling Smørgrav */ 1564b17dab0SDag-Erling Smørgrav #define SPLAY_GENERATE(name, type, field, cmp) \ 1574b17dab0SDag-Erling Smørgrav struct type * \ 1584b17dab0SDag-Erling Smørgrav name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 1594b17dab0SDag-Erling Smørgrav { \ 1604b17dab0SDag-Erling Smørgrav if (SPLAY_EMPTY(head)) { \ 1614b17dab0SDag-Erling Smørgrav SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 1624b17dab0SDag-Erling Smørgrav } else { \ 1634b17dab0SDag-Erling Smørgrav int __comp; \ 1644b17dab0SDag-Erling Smørgrav name##_SPLAY(head, elm); \ 1654b17dab0SDag-Erling Smørgrav __comp = (cmp)(elm, (head)->sph_root); \ 1664b17dab0SDag-Erling Smørgrav if(__comp < 0) { \ 1674b17dab0SDag-Erling Smørgrav SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 1684b17dab0SDag-Erling Smørgrav SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 1694b17dab0SDag-Erling Smørgrav SPLAY_LEFT((head)->sph_root, field) = NULL; \ 1704b17dab0SDag-Erling Smørgrav } else if (__comp > 0) { \ 1714b17dab0SDag-Erling Smørgrav SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 1724b17dab0SDag-Erling Smørgrav SPLAY_LEFT(elm, field) = (head)->sph_root; \ 1734b17dab0SDag-Erling Smørgrav SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 1744b17dab0SDag-Erling Smørgrav } else \ 1754b17dab0SDag-Erling Smørgrav return ((head)->sph_root); \ 1764b17dab0SDag-Erling Smørgrav } \ 1774b17dab0SDag-Erling Smørgrav (head)->sph_root = (elm); \ 1784b17dab0SDag-Erling Smørgrav return (NULL); \ 1794b17dab0SDag-Erling Smørgrav } \ 1804b17dab0SDag-Erling Smørgrav \ 1814b17dab0SDag-Erling Smørgrav struct type * \ 1824b17dab0SDag-Erling Smørgrav name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 1834b17dab0SDag-Erling Smørgrav { \ 1844b17dab0SDag-Erling Smørgrav struct type *__tmp; \ 1854b17dab0SDag-Erling Smørgrav if (SPLAY_EMPTY(head)) \ 1864b17dab0SDag-Erling Smørgrav return (NULL); \ 1874b17dab0SDag-Erling Smørgrav name##_SPLAY(head, elm); \ 1884b17dab0SDag-Erling Smørgrav if ((cmp)(elm, (head)->sph_root) == 0) { \ 1894b17dab0SDag-Erling Smørgrav if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 1904b17dab0SDag-Erling Smørgrav (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 1914b17dab0SDag-Erling Smørgrav } else { \ 1924b17dab0SDag-Erling Smørgrav __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 1934b17dab0SDag-Erling Smørgrav (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 1944b17dab0SDag-Erling Smørgrav name##_SPLAY(head, elm); \ 1954b17dab0SDag-Erling Smørgrav SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 1964b17dab0SDag-Erling Smørgrav } \ 1974b17dab0SDag-Erling Smørgrav return (elm); \ 1984b17dab0SDag-Erling Smørgrav } \ 1994b17dab0SDag-Erling Smørgrav return (NULL); \ 2004b17dab0SDag-Erling Smørgrav } \ 2014b17dab0SDag-Erling Smørgrav \ 2024b17dab0SDag-Erling Smørgrav void \ 2034b17dab0SDag-Erling Smørgrav name##_SPLAY(struct name *head, struct type *elm) \ 2044b17dab0SDag-Erling Smørgrav { \ 2054b17dab0SDag-Erling Smørgrav struct type __node, *__left, *__right, *__tmp; \ 2064b17dab0SDag-Erling Smørgrav int __comp; \ 2074b17dab0SDag-Erling Smørgrav \ 2084b17dab0SDag-Erling Smørgrav SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 2094b17dab0SDag-Erling Smørgrav __left = __right = &__node; \ 2104b17dab0SDag-Erling Smørgrav \ 2114b17dab0SDag-Erling Smørgrav while ((__comp = (cmp)(elm, (head)->sph_root))) { \ 2124b17dab0SDag-Erling Smørgrav if (__comp < 0) { \ 2134b17dab0SDag-Erling Smørgrav __tmp = SPLAY_LEFT((head)->sph_root, field); \ 2144b17dab0SDag-Erling Smørgrav if (__tmp == NULL) \ 2154b17dab0SDag-Erling Smørgrav break; \ 2164b17dab0SDag-Erling Smørgrav if ((cmp)(elm, __tmp) < 0){ \ 2174b17dab0SDag-Erling Smørgrav SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 2184b17dab0SDag-Erling Smørgrav if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 2194b17dab0SDag-Erling Smørgrav break; \ 2204b17dab0SDag-Erling Smørgrav } \ 2214b17dab0SDag-Erling Smørgrav SPLAY_LINKLEFT(head, __right, field); \ 2224b17dab0SDag-Erling Smørgrav } else if (__comp > 0) { \ 2234b17dab0SDag-Erling Smørgrav __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 2244b17dab0SDag-Erling Smørgrav if (__tmp == NULL) \ 2254b17dab0SDag-Erling Smørgrav break; \ 2264b17dab0SDag-Erling Smørgrav if ((cmp)(elm, __tmp) > 0){ \ 2274b17dab0SDag-Erling Smørgrav SPLAY_ROTATE_LEFT(head, __tmp, field); \ 2284b17dab0SDag-Erling Smørgrav if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 2294b17dab0SDag-Erling Smørgrav break; \ 2304b17dab0SDag-Erling Smørgrav } \ 2314b17dab0SDag-Erling Smørgrav SPLAY_LINKRIGHT(head, __left, field); \ 2324b17dab0SDag-Erling Smørgrav } \ 2334b17dab0SDag-Erling Smørgrav } \ 2344b17dab0SDag-Erling Smørgrav SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 2354b17dab0SDag-Erling Smørgrav } \ 2364b17dab0SDag-Erling Smørgrav \ 2374b17dab0SDag-Erling Smørgrav /* Splay with either the minimum or the maximum element \ 2384b17dab0SDag-Erling Smørgrav * Used to find minimum or maximum element in tree. \ 2394b17dab0SDag-Erling Smørgrav */ \ 2404b17dab0SDag-Erling Smørgrav void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 2414b17dab0SDag-Erling Smørgrav { \ 2424b17dab0SDag-Erling Smørgrav struct type __node, *__left, *__right, *__tmp; \ 2434b17dab0SDag-Erling Smørgrav \ 2444b17dab0SDag-Erling Smørgrav SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 2454b17dab0SDag-Erling Smørgrav __left = __right = &__node; \ 2464b17dab0SDag-Erling Smørgrav \ 2474b17dab0SDag-Erling Smørgrav while (1) { \ 2484b17dab0SDag-Erling Smørgrav if (__comp < 0) { \ 2494b17dab0SDag-Erling Smørgrav __tmp = SPLAY_LEFT((head)->sph_root, field); \ 2504b17dab0SDag-Erling Smørgrav if (__tmp == NULL) \ 2514b17dab0SDag-Erling Smørgrav break; \ 2524b17dab0SDag-Erling Smørgrav if (__comp < 0){ \ 2534b17dab0SDag-Erling Smørgrav SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 2544b17dab0SDag-Erling Smørgrav if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 2554b17dab0SDag-Erling Smørgrav break; \ 2564b17dab0SDag-Erling Smørgrav } \ 2574b17dab0SDag-Erling Smørgrav SPLAY_LINKLEFT(head, __right, field); \ 2584b17dab0SDag-Erling Smørgrav } else if (__comp > 0) { \ 2594b17dab0SDag-Erling Smørgrav __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 2604b17dab0SDag-Erling Smørgrav if (__tmp == NULL) \ 2614b17dab0SDag-Erling Smørgrav break; \ 2624b17dab0SDag-Erling Smørgrav if (__comp > 0) { \ 2634b17dab0SDag-Erling Smørgrav SPLAY_ROTATE_LEFT(head, __tmp, field); \ 2644b17dab0SDag-Erling Smørgrav if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 2654b17dab0SDag-Erling Smørgrav break; \ 2664b17dab0SDag-Erling Smørgrav } \ 2674b17dab0SDag-Erling Smørgrav SPLAY_LINKRIGHT(head, __left, field); \ 2684b17dab0SDag-Erling Smørgrav } \ 2694b17dab0SDag-Erling Smørgrav } \ 2704b17dab0SDag-Erling Smørgrav SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 2714b17dab0SDag-Erling Smørgrav } 2724b17dab0SDag-Erling Smørgrav 2734b17dab0SDag-Erling Smørgrav #define SPLAY_NEGINF -1 2744b17dab0SDag-Erling Smørgrav #define SPLAY_INF 1 2754b17dab0SDag-Erling Smørgrav 2764b17dab0SDag-Erling Smørgrav #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 2774b17dab0SDag-Erling Smørgrav #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 2784b17dab0SDag-Erling Smørgrav #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 2794b17dab0SDag-Erling Smørgrav #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 2804b17dab0SDag-Erling Smørgrav #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 2814b17dab0SDag-Erling Smørgrav : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 2824b17dab0SDag-Erling Smørgrav #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 2834b17dab0SDag-Erling Smørgrav : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 2844b17dab0SDag-Erling Smørgrav 2854b17dab0SDag-Erling Smørgrav #define SPLAY_FOREACH(x, name, head) \ 2864b17dab0SDag-Erling Smørgrav for ((x) = SPLAY_MIN(name, head); \ 2874b17dab0SDag-Erling Smørgrav (x) != NULL; \ 2884b17dab0SDag-Erling Smørgrav (x) = SPLAY_NEXT(name, head, x)) 2894b17dab0SDag-Erling Smørgrav 2904b17dab0SDag-Erling Smørgrav /* Macros that define a red-back tree */ 2914b17dab0SDag-Erling Smørgrav #define RB_HEAD(name, type) \ 2924b17dab0SDag-Erling Smørgrav struct name { \ 2934b17dab0SDag-Erling Smørgrav struct type *rbh_root; /* root of the tree */ \ 2944b17dab0SDag-Erling Smørgrav } 2954b17dab0SDag-Erling Smørgrav 2964b17dab0SDag-Erling Smørgrav #define RB_INITIALIZER(root) \ 2974b17dab0SDag-Erling Smørgrav { NULL } 2984b17dab0SDag-Erling Smørgrav 2994b17dab0SDag-Erling Smørgrav #define RB_INIT(root) do { \ 3004b17dab0SDag-Erling Smørgrav (root)->rbh_root = NULL; \ 3014b17dab0SDag-Erling Smørgrav } while (0) 3024b17dab0SDag-Erling Smørgrav 3034b17dab0SDag-Erling Smørgrav #define RB_BLACK 0 3044b17dab0SDag-Erling Smørgrav #define RB_RED 1 3054b17dab0SDag-Erling Smørgrav #define RB_ENTRY(type) \ 3064b17dab0SDag-Erling Smørgrav struct { \ 3074b17dab0SDag-Erling Smørgrav struct type *rbe_left; /* left element */ \ 3084b17dab0SDag-Erling Smørgrav struct type *rbe_right; /* right element */ \ 3094b17dab0SDag-Erling Smørgrav struct type *rbe_parent; /* parent element */ \ 3104b17dab0SDag-Erling Smørgrav int rbe_color; /* node color */ \ 3114b17dab0SDag-Erling Smørgrav } 3124b17dab0SDag-Erling Smørgrav 3134b17dab0SDag-Erling Smørgrav #define RB_LEFT(elm, field) (elm)->field.rbe_left 3144b17dab0SDag-Erling Smørgrav #define RB_RIGHT(elm, field) (elm)->field.rbe_right 3154b17dab0SDag-Erling Smørgrav #define RB_PARENT(elm, field) (elm)->field.rbe_parent 3164b17dab0SDag-Erling Smørgrav #define RB_COLOR(elm, field) (elm)->field.rbe_color 3174b17dab0SDag-Erling Smørgrav #define RB_ROOT(head) (head)->rbh_root 3184b17dab0SDag-Erling Smørgrav #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 3194b17dab0SDag-Erling Smørgrav 3204b17dab0SDag-Erling Smørgrav #define RB_SET(elm, parent, field) do { \ 3214b17dab0SDag-Erling Smørgrav RB_PARENT(elm, field) = parent; \ 3224b17dab0SDag-Erling Smørgrav RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 3234b17dab0SDag-Erling Smørgrav RB_COLOR(elm, field) = RB_RED; \ 3244b17dab0SDag-Erling Smørgrav } while (0) 3254b17dab0SDag-Erling Smørgrav 3264b17dab0SDag-Erling Smørgrav #define RB_SET_BLACKRED(black, red, field) do { \ 3274b17dab0SDag-Erling Smørgrav RB_COLOR(black, field) = RB_BLACK; \ 3284b17dab0SDag-Erling Smørgrav RB_COLOR(red, field) = RB_RED; \ 3294b17dab0SDag-Erling Smørgrav } while (0) 3304b17dab0SDag-Erling Smørgrav 3314b17dab0SDag-Erling Smørgrav #ifndef RB_AUGMENT 3324b17dab0SDag-Erling Smørgrav #define RB_AUGMENT(x) 3334b17dab0SDag-Erling Smørgrav #endif 3344b17dab0SDag-Erling Smørgrav 3354b17dab0SDag-Erling Smørgrav #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 3364b17dab0SDag-Erling Smørgrav (tmp) = RB_RIGHT(elm, field); \ 3374b17dab0SDag-Erling Smørgrav if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ 3384b17dab0SDag-Erling Smørgrav RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 3394b17dab0SDag-Erling Smørgrav } \ 3404b17dab0SDag-Erling Smørgrav RB_AUGMENT(elm); \ 3414b17dab0SDag-Erling Smørgrav if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 3424b17dab0SDag-Erling Smørgrav if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 3434b17dab0SDag-Erling Smørgrav RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 3444b17dab0SDag-Erling Smørgrav else \ 3454b17dab0SDag-Erling Smørgrav RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 3464b17dab0SDag-Erling Smørgrav } else \ 3474b17dab0SDag-Erling Smørgrav (head)->rbh_root = (tmp); \ 3484b17dab0SDag-Erling Smørgrav RB_LEFT(tmp, field) = (elm); \ 3494b17dab0SDag-Erling Smørgrav RB_PARENT(elm, field) = (tmp); \ 3504b17dab0SDag-Erling Smørgrav RB_AUGMENT(tmp); \ 351d0c8c0bcSDag-Erling Smørgrav if ((RB_PARENT(tmp, field))) \ 352d0c8c0bcSDag-Erling Smørgrav RB_AUGMENT(RB_PARENT(tmp, field)); \ 3534b17dab0SDag-Erling Smørgrav } while (0) 3544b17dab0SDag-Erling Smørgrav 3554b17dab0SDag-Erling Smørgrav #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 3564b17dab0SDag-Erling Smørgrav (tmp) = RB_LEFT(elm, field); \ 3574b17dab0SDag-Erling Smørgrav if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ 3584b17dab0SDag-Erling Smørgrav RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 3594b17dab0SDag-Erling Smørgrav } \ 3604b17dab0SDag-Erling Smørgrav RB_AUGMENT(elm); \ 3614b17dab0SDag-Erling Smørgrav if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 3624b17dab0SDag-Erling Smørgrav if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 3634b17dab0SDag-Erling Smørgrav RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 3644b17dab0SDag-Erling Smørgrav else \ 3654b17dab0SDag-Erling Smørgrav RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 3664b17dab0SDag-Erling Smørgrav } else \ 3674b17dab0SDag-Erling Smørgrav (head)->rbh_root = (tmp); \ 3684b17dab0SDag-Erling Smørgrav RB_RIGHT(tmp, field) = (elm); \ 3694b17dab0SDag-Erling Smørgrav RB_PARENT(elm, field) = (tmp); \ 3704b17dab0SDag-Erling Smørgrav RB_AUGMENT(tmp); \ 371d0c8c0bcSDag-Erling Smørgrav if ((RB_PARENT(tmp, field))) \ 372d0c8c0bcSDag-Erling Smørgrav RB_AUGMENT(RB_PARENT(tmp, field)); \ 3734b17dab0SDag-Erling Smørgrav } while (0) 3744b17dab0SDag-Erling Smørgrav 3754b17dab0SDag-Erling Smørgrav /* Generates prototypes and inline functions */ 3764b17dab0SDag-Erling Smørgrav #define RB_PROTOTYPE(name, type, field, cmp) \ 3774b17dab0SDag-Erling Smørgrav void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 3784b17dab0SDag-Erling Smørgrav void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 3794b17dab0SDag-Erling Smørgrav struct type *name##_RB_REMOVE(struct name *, struct type *); \ 3804b17dab0SDag-Erling Smørgrav struct type *name##_RB_INSERT(struct name *, struct type *); \ 3814b17dab0SDag-Erling Smørgrav struct type *name##_RB_FIND(struct name *, struct type *); \ 3824b17dab0SDag-Erling Smørgrav struct type *name##_RB_NEXT(struct name *, struct type *); \ 3834b17dab0SDag-Erling Smørgrav struct type *name##_RB_MINMAX(struct name *, int); \ 3844b17dab0SDag-Erling Smørgrav \ 3854b17dab0SDag-Erling Smørgrav 3864b17dab0SDag-Erling Smørgrav /* Main rb operation. 3874b17dab0SDag-Erling Smørgrav * Moves node close to the key of elm to top 3884b17dab0SDag-Erling Smørgrav */ 3894b17dab0SDag-Erling Smørgrav #define RB_GENERATE(name, type, field, cmp) \ 3904b17dab0SDag-Erling Smørgrav void \ 3914b17dab0SDag-Erling Smørgrav name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 3924b17dab0SDag-Erling Smørgrav { \ 3934b17dab0SDag-Erling Smørgrav struct type *parent, *gparent, *tmp; \ 3944b17dab0SDag-Erling Smørgrav while ((parent = RB_PARENT(elm, field)) && \ 3954b17dab0SDag-Erling Smørgrav RB_COLOR(parent, field) == RB_RED) { \ 3964b17dab0SDag-Erling Smørgrav gparent = RB_PARENT(parent, field); \ 3974b17dab0SDag-Erling Smørgrav if (parent == RB_LEFT(gparent, field)) { \ 3984b17dab0SDag-Erling Smørgrav tmp = RB_RIGHT(gparent, field); \ 3994b17dab0SDag-Erling Smørgrav if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 4004b17dab0SDag-Erling Smørgrav RB_COLOR(tmp, field) = RB_BLACK; \ 4014b17dab0SDag-Erling Smørgrav RB_SET_BLACKRED(parent, gparent, field);\ 4024b17dab0SDag-Erling Smørgrav elm = gparent; \ 4034b17dab0SDag-Erling Smørgrav continue; \ 4044b17dab0SDag-Erling Smørgrav } \ 4054b17dab0SDag-Erling Smørgrav if (RB_RIGHT(parent, field) == elm) { \ 4064b17dab0SDag-Erling Smørgrav RB_ROTATE_LEFT(head, parent, tmp, field);\ 4074b17dab0SDag-Erling Smørgrav tmp = parent; \ 4084b17dab0SDag-Erling Smørgrav parent = elm; \ 4094b17dab0SDag-Erling Smørgrav elm = tmp; \ 4104b17dab0SDag-Erling Smørgrav } \ 4114b17dab0SDag-Erling Smørgrav RB_SET_BLACKRED(parent, gparent, field); \ 4124b17dab0SDag-Erling Smørgrav RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 4134b17dab0SDag-Erling Smørgrav } else { \ 4144b17dab0SDag-Erling Smørgrav tmp = RB_LEFT(gparent, field); \ 4154b17dab0SDag-Erling Smørgrav if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 4164b17dab0SDag-Erling Smørgrav RB_COLOR(tmp, field) = RB_BLACK; \ 4174b17dab0SDag-Erling Smørgrav RB_SET_BLACKRED(parent, gparent, field);\ 4184b17dab0SDag-Erling Smørgrav elm = gparent; \ 4194b17dab0SDag-Erling Smørgrav continue; \ 4204b17dab0SDag-Erling Smørgrav } \ 4214b17dab0SDag-Erling Smørgrav if (RB_LEFT(parent, field) == elm) { \ 4224b17dab0SDag-Erling Smørgrav RB_ROTATE_RIGHT(head, parent, tmp, field);\ 4234b17dab0SDag-Erling Smørgrav tmp = parent; \ 4244b17dab0SDag-Erling Smørgrav parent = elm; \ 4254b17dab0SDag-Erling Smørgrav elm = tmp; \ 4264b17dab0SDag-Erling Smørgrav } \ 4274b17dab0SDag-Erling Smørgrav RB_SET_BLACKRED(parent, gparent, field); \ 4284b17dab0SDag-Erling Smørgrav RB_ROTATE_LEFT(head, gparent, tmp, field); \ 4294b17dab0SDag-Erling Smørgrav } \ 4304b17dab0SDag-Erling Smørgrav } \ 4314b17dab0SDag-Erling Smørgrav RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 4324b17dab0SDag-Erling Smørgrav } \ 4334b17dab0SDag-Erling Smørgrav \ 4344b17dab0SDag-Erling Smørgrav void \ 4354b17dab0SDag-Erling Smørgrav name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 4364b17dab0SDag-Erling Smørgrav { \ 4374b17dab0SDag-Erling Smørgrav struct type *tmp; \ 4384b17dab0SDag-Erling Smørgrav while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 4394b17dab0SDag-Erling Smørgrav elm != RB_ROOT(head)) { \ 4404b17dab0SDag-Erling Smørgrav if (RB_LEFT(parent, field) == elm) { \ 4414b17dab0SDag-Erling Smørgrav tmp = RB_RIGHT(parent, field); \ 4424b17dab0SDag-Erling Smørgrav if (RB_COLOR(tmp, field) == RB_RED) { \ 4434b17dab0SDag-Erling Smørgrav RB_SET_BLACKRED(tmp, parent, field); \ 4444b17dab0SDag-Erling Smørgrav RB_ROTATE_LEFT(head, parent, tmp, field);\ 4454b17dab0SDag-Erling Smørgrav tmp = RB_RIGHT(parent, field); \ 4464b17dab0SDag-Erling Smørgrav } \ 4474b17dab0SDag-Erling Smørgrav if ((RB_LEFT(tmp, field) == NULL || \ 4484b17dab0SDag-Erling Smørgrav RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 4494b17dab0SDag-Erling Smørgrav (RB_RIGHT(tmp, field) == NULL || \ 4504b17dab0SDag-Erling Smørgrav RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 4514b17dab0SDag-Erling Smørgrav RB_COLOR(tmp, field) = RB_RED; \ 4524b17dab0SDag-Erling Smørgrav elm = parent; \ 4534b17dab0SDag-Erling Smørgrav parent = RB_PARENT(elm, field); \ 4544b17dab0SDag-Erling Smørgrav } else { \ 4554b17dab0SDag-Erling Smørgrav if (RB_RIGHT(tmp, field) == NULL || \ 4564b17dab0SDag-Erling Smørgrav RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 4574b17dab0SDag-Erling Smørgrav struct type *oleft; \ 4584b17dab0SDag-Erling Smørgrav if ((oleft = RB_LEFT(tmp, field)))\ 4594b17dab0SDag-Erling Smørgrav RB_COLOR(oleft, field) = RB_BLACK;\ 4604b17dab0SDag-Erling Smørgrav RB_COLOR(tmp, field) = RB_RED; \ 4614b17dab0SDag-Erling Smørgrav RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 4624b17dab0SDag-Erling Smørgrav tmp = RB_RIGHT(parent, field); \ 4634b17dab0SDag-Erling Smørgrav } \ 4644b17dab0SDag-Erling Smørgrav RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 4654b17dab0SDag-Erling Smørgrav RB_COLOR(parent, field) = RB_BLACK; \ 4664b17dab0SDag-Erling Smørgrav if (RB_RIGHT(tmp, field)) \ 4674b17dab0SDag-Erling Smørgrav RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 4684b17dab0SDag-Erling Smørgrav RB_ROTATE_LEFT(head, parent, tmp, field);\ 4694b17dab0SDag-Erling Smørgrav elm = RB_ROOT(head); \ 4704b17dab0SDag-Erling Smørgrav break; \ 4714b17dab0SDag-Erling Smørgrav } \ 4724b17dab0SDag-Erling Smørgrav } else { \ 4734b17dab0SDag-Erling Smørgrav tmp = RB_LEFT(parent, field); \ 4744b17dab0SDag-Erling Smørgrav if (RB_COLOR(tmp, field) == RB_RED) { \ 4754b17dab0SDag-Erling Smørgrav RB_SET_BLACKRED(tmp, parent, field); \ 4764b17dab0SDag-Erling Smørgrav RB_ROTATE_RIGHT(head, parent, tmp, field);\ 4774b17dab0SDag-Erling Smørgrav tmp = RB_LEFT(parent, field); \ 4784b17dab0SDag-Erling Smørgrav } \ 4794b17dab0SDag-Erling Smørgrav if ((RB_LEFT(tmp, field) == NULL || \ 4804b17dab0SDag-Erling Smørgrav RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 4814b17dab0SDag-Erling Smørgrav (RB_RIGHT(tmp, field) == NULL || \ 4824b17dab0SDag-Erling Smørgrav RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 4834b17dab0SDag-Erling Smørgrav RB_COLOR(tmp, field) = RB_RED; \ 4844b17dab0SDag-Erling Smørgrav elm = parent; \ 4854b17dab0SDag-Erling Smørgrav parent = RB_PARENT(elm, field); \ 4864b17dab0SDag-Erling Smørgrav } else { \ 4874b17dab0SDag-Erling Smørgrav if (RB_LEFT(tmp, field) == NULL || \ 4884b17dab0SDag-Erling Smørgrav RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 4894b17dab0SDag-Erling Smørgrav struct type *oright; \ 4904b17dab0SDag-Erling Smørgrav if ((oright = RB_RIGHT(tmp, field)))\ 4914b17dab0SDag-Erling Smørgrav RB_COLOR(oright, field) = RB_BLACK;\ 4924b17dab0SDag-Erling Smørgrav RB_COLOR(tmp, field) = RB_RED; \ 4934b17dab0SDag-Erling Smørgrav RB_ROTATE_LEFT(head, tmp, oright, field);\ 4944b17dab0SDag-Erling Smørgrav tmp = RB_LEFT(parent, field); \ 4954b17dab0SDag-Erling Smørgrav } \ 4964b17dab0SDag-Erling Smørgrav RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 4974b17dab0SDag-Erling Smørgrav RB_COLOR(parent, field) = RB_BLACK; \ 4984b17dab0SDag-Erling Smørgrav if (RB_LEFT(tmp, field)) \ 4994b17dab0SDag-Erling Smørgrav RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 5004b17dab0SDag-Erling Smørgrav RB_ROTATE_RIGHT(head, parent, tmp, field);\ 5014b17dab0SDag-Erling Smørgrav elm = RB_ROOT(head); \ 5024b17dab0SDag-Erling Smørgrav break; \ 5034b17dab0SDag-Erling Smørgrav } \ 5044b17dab0SDag-Erling Smørgrav } \ 5054b17dab0SDag-Erling Smørgrav } \ 5064b17dab0SDag-Erling Smørgrav if (elm) \ 5074b17dab0SDag-Erling Smørgrav RB_COLOR(elm, field) = RB_BLACK; \ 5084b17dab0SDag-Erling Smørgrav } \ 5094b17dab0SDag-Erling Smørgrav \ 5104b17dab0SDag-Erling Smørgrav struct type * \ 5114b17dab0SDag-Erling Smørgrav name##_RB_REMOVE(struct name *head, struct type *elm) \ 5124b17dab0SDag-Erling Smørgrav { \ 5134b17dab0SDag-Erling Smørgrav struct type *child, *parent, *old = elm; \ 5144b17dab0SDag-Erling Smørgrav int color; \ 5154b17dab0SDag-Erling Smørgrav if (RB_LEFT(elm, field) == NULL) \ 5164b17dab0SDag-Erling Smørgrav child = RB_RIGHT(elm, field); \ 5174b17dab0SDag-Erling Smørgrav else if (RB_RIGHT(elm, field) == NULL) \ 5184b17dab0SDag-Erling Smørgrav child = RB_LEFT(elm, field); \ 5194b17dab0SDag-Erling Smørgrav else { \ 5204b17dab0SDag-Erling Smørgrav struct type *left; \ 5214b17dab0SDag-Erling Smørgrav elm = RB_RIGHT(elm, field); \ 5224b17dab0SDag-Erling Smørgrav while ((left = RB_LEFT(elm, field))) \ 5234b17dab0SDag-Erling Smørgrav elm = left; \ 5244b17dab0SDag-Erling Smørgrav child = RB_RIGHT(elm, field); \ 5254b17dab0SDag-Erling Smørgrav parent = RB_PARENT(elm, field); \ 5264b17dab0SDag-Erling Smørgrav color = RB_COLOR(elm, field); \ 5274b17dab0SDag-Erling Smørgrav if (child) \ 5284b17dab0SDag-Erling Smørgrav RB_PARENT(child, field) = parent; \ 5294b17dab0SDag-Erling Smørgrav if (parent) { \ 5304b17dab0SDag-Erling Smørgrav if (RB_LEFT(parent, field) == elm) \ 5314b17dab0SDag-Erling Smørgrav RB_LEFT(parent, field) = child; \ 5324b17dab0SDag-Erling Smørgrav else \ 5334b17dab0SDag-Erling Smørgrav RB_RIGHT(parent, field) = child; \ 5344b17dab0SDag-Erling Smørgrav RB_AUGMENT(parent); \ 5354b17dab0SDag-Erling Smørgrav } else \ 5364b17dab0SDag-Erling Smørgrav RB_ROOT(head) = child; \ 5374b17dab0SDag-Erling Smørgrav if (RB_PARENT(elm, field) == old) \ 5384b17dab0SDag-Erling Smørgrav parent = elm; \ 5394b17dab0SDag-Erling Smørgrav (elm)->field = (old)->field; \ 5404b17dab0SDag-Erling Smørgrav if (RB_PARENT(old, field)) { \ 5414b17dab0SDag-Erling Smørgrav if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 5424b17dab0SDag-Erling Smørgrav RB_LEFT(RB_PARENT(old, field), field) = elm;\ 5434b17dab0SDag-Erling Smørgrav else \ 5444b17dab0SDag-Erling Smørgrav RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 5454b17dab0SDag-Erling Smørgrav RB_AUGMENT(RB_PARENT(old, field)); \ 5464b17dab0SDag-Erling Smørgrav } else \ 5474b17dab0SDag-Erling Smørgrav RB_ROOT(head) = elm; \ 5484b17dab0SDag-Erling Smørgrav RB_PARENT(RB_LEFT(old, field), field) = elm; \ 5494b17dab0SDag-Erling Smørgrav if (RB_RIGHT(old, field)) \ 5504b17dab0SDag-Erling Smørgrav RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 5514b17dab0SDag-Erling Smørgrav if (parent) { \ 5524b17dab0SDag-Erling Smørgrav left = parent; \ 5534b17dab0SDag-Erling Smørgrav do { \ 5544b17dab0SDag-Erling Smørgrav RB_AUGMENT(left); \ 5554b17dab0SDag-Erling Smørgrav } while ((left = RB_PARENT(left, field))); \ 5564b17dab0SDag-Erling Smørgrav } \ 5574b17dab0SDag-Erling Smørgrav goto color; \ 5584b17dab0SDag-Erling Smørgrav } \ 5594b17dab0SDag-Erling Smørgrav parent = RB_PARENT(elm, field); \ 5604b17dab0SDag-Erling Smørgrav color = RB_COLOR(elm, field); \ 5614b17dab0SDag-Erling Smørgrav if (child) \ 5624b17dab0SDag-Erling Smørgrav RB_PARENT(child, field) = parent; \ 5634b17dab0SDag-Erling Smørgrav if (parent) { \ 5644b17dab0SDag-Erling Smørgrav if (RB_LEFT(parent, field) == elm) \ 5654b17dab0SDag-Erling Smørgrav RB_LEFT(parent, field) = child; \ 5664b17dab0SDag-Erling Smørgrav else \ 5674b17dab0SDag-Erling Smørgrav RB_RIGHT(parent, field) = child; \ 5684b17dab0SDag-Erling Smørgrav RB_AUGMENT(parent); \ 5694b17dab0SDag-Erling Smørgrav } else \ 5704b17dab0SDag-Erling Smørgrav RB_ROOT(head) = child; \ 5714b17dab0SDag-Erling Smørgrav color: \ 5724b17dab0SDag-Erling Smørgrav if (color == RB_BLACK) \ 5734b17dab0SDag-Erling Smørgrav name##_RB_REMOVE_COLOR(head, parent, child); \ 5744b17dab0SDag-Erling Smørgrav return (old); \ 5754b17dab0SDag-Erling Smørgrav } \ 5764b17dab0SDag-Erling Smørgrav \ 5774b17dab0SDag-Erling Smørgrav /* Inserts a node into the RB tree */ \ 5784b17dab0SDag-Erling Smørgrav struct type * \ 5794b17dab0SDag-Erling Smørgrav name##_RB_INSERT(struct name *head, struct type *elm) \ 5804b17dab0SDag-Erling Smørgrav { \ 5814b17dab0SDag-Erling Smørgrav struct type *tmp; \ 5824b17dab0SDag-Erling Smørgrav struct type *parent = NULL; \ 5834b17dab0SDag-Erling Smørgrav int comp = 0; \ 5844b17dab0SDag-Erling Smørgrav tmp = RB_ROOT(head); \ 5854b17dab0SDag-Erling Smørgrav while (tmp) { \ 5864b17dab0SDag-Erling Smørgrav parent = tmp; \ 5874b17dab0SDag-Erling Smørgrav comp = (cmp)(elm, parent); \ 5884b17dab0SDag-Erling Smørgrav if (comp < 0) \ 5894b17dab0SDag-Erling Smørgrav tmp = RB_LEFT(tmp, field); \ 5904b17dab0SDag-Erling Smørgrav else if (comp > 0) \ 5914b17dab0SDag-Erling Smørgrav tmp = RB_RIGHT(tmp, field); \ 5924b17dab0SDag-Erling Smørgrav else \ 5934b17dab0SDag-Erling Smørgrav return (tmp); \ 5944b17dab0SDag-Erling Smørgrav } \ 5954b17dab0SDag-Erling Smørgrav RB_SET(elm, parent, field); \ 5964b17dab0SDag-Erling Smørgrav if (parent != NULL) { \ 5974b17dab0SDag-Erling Smørgrav if (comp < 0) \ 5984b17dab0SDag-Erling Smørgrav RB_LEFT(parent, field) = elm; \ 5994b17dab0SDag-Erling Smørgrav else \ 6004b17dab0SDag-Erling Smørgrav RB_RIGHT(parent, field) = elm; \ 6014b17dab0SDag-Erling Smørgrav RB_AUGMENT(parent); \ 6024b17dab0SDag-Erling Smørgrav } else \ 6034b17dab0SDag-Erling Smørgrav RB_ROOT(head) = elm; \ 6044b17dab0SDag-Erling Smørgrav name##_RB_INSERT_COLOR(head, elm); \ 6054b17dab0SDag-Erling Smørgrav return (NULL); \ 6064b17dab0SDag-Erling Smørgrav } \ 6074b17dab0SDag-Erling Smørgrav \ 6084b17dab0SDag-Erling Smørgrav /* Finds the node with the same key as elm */ \ 6094b17dab0SDag-Erling Smørgrav struct type * \ 6104b17dab0SDag-Erling Smørgrav name##_RB_FIND(struct name *head, struct type *elm) \ 6114b17dab0SDag-Erling Smørgrav { \ 6124b17dab0SDag-Erling Smørgrav struct type *tmp = RB_ROOT(head); \ 6134b17dab0SDag-Erling Smørgrav int comp; \ 6144b17dab0SDag-Erling Smørgrav while (tmp) { \ 6154b17dab0SDag-Erling Smørgrav comp = cmp(elm, tmp); \ 6164b17dab0SDag-Erling Smørgrav if (comp < 0) \ 6174b17dab0SDag-Erling Smørgrav tmp = RB_LEFT(tmp, field); \ 6184b17dab0SDag-Erling Smørgrav else if (comp > 0) \ 6194b17dab0SDag-Erling Smørgrav tmp = RB_RIGHT(tmp, field); \ 6204b17dab0SDag-Erling Smørgrav else \ 6214b17dab0SDag-Erling Smørgrav return (tmp); \ 6224b17dab0SDag-Erling Smørgrav } \ 6234b17dab0SDag-Erling Smørgrav return (NULL); \ 6244b17dab0SDag-Erling Smørgrav } \ 6254b17dab0SDag-Erling Smørgrav \ 6264b17dab0SDag-Erling Smørgrav struct type * \ 6274b17dab0SDag-Erling Smørgrav name##_RB_NEXT(struct name *head, struct type *elm) \ 6284b17dab0SDag-Erling Smørgrav { \ 6294b17dab0SDag-Erling Smørgrav if (RB_RIGHT(elm, field)) { \ 6304b17dab0SDag-Erling Smørgrav elm = RB_RIGHT(elm, field); \ 6314b17dab0SDag-Erling Smørgrav while (RB_LEFT(elm, field)) \ 6324b17dab0SDag-Erling Smørgrav elm = RB_LEFT(elm, field); \ 6334b17dab0SDag-Erling Smørgrav } else { \ 6344b17dab0SDag-Erling Smørgrav if (RB_PARENT(elm, field) && \ 6354b17dab0SDag-Erling Smørgrav (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 6364b17dab0SDag-Erling Smørgrav elm = RB_PARENT(elm, field); \ 6374b17dab0SDag-Erling Smørgrav else { \ 6384b17dab0SDag-Erling Smørgrav while (RB_PARENT(elm, field) && \ 6394b17dab0SDag-Erling Smørgrav (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 6404b17dab0SDag-Erling Smørgrav elm = RB_PARENT(elm, field); \ 6414b17dab0SDag-Erling Smørgrav elm = RB_PARENT(elm, field); \ 6424b17dab0SDag-Erling Smørgrav } \ 6434b17dab0SDag-Erling Smørgrav } \ 6444b17dab0SDag-Erling Smørgrav return (elm); \ 6454b17dab0SDag-Erling Smørgrav } \ 6464b17dab0SDag-Erling Smørgrav \ 6474b17dab0SDag-Erling Smørgrav struct type * \ 6484b17dab0SDag-Erling Smørgrav name##_RB_MINMAX(struct name *head, int val) \ 6494b17dab0SDag-Erling Smørgrav { \ 6504b17dab0SDag-Erling Smørgrav struct type *tmp = RB_ROOT(head); \ 6514b17dab0SDag-Erling Smørgrav struct type *parent = NULL; \ 6524b17dab0SDag-Erling Smørgrav while (tmp) { \ 6534b17dab0SDag-Erling Smørgrav parent = tmp; \ 6544b17dab0SDag-Erling Smørgrav if (val < 0) \ 6554b17dab0SDag-Erling Smørgrav tmp = RB_LEFT(tmp, field); \ 6564b17dab0SDag-Erling Smørgrav else \ 6574b17dab0SDag-Erling Smørgrav tmp = RB_RIGHT(tmp, field); \ 6584b17dab0SDag-Erling Smørgrav } \ 6594b17dab0SDag-Erling Smørgrav return (parent); \ 6604b17dab0SDag-Erling Smørgrav } 6614b17dab0SDag-Erling Smørgrav 6624b17dab0SDag-Erling Smørgrav #define RB_NEGINF -1 6634b17dab0SDag-Erling Smørgrav #define RB_INF 1 6644b17dab0SDag-Erling Smørgrav 6654b17dab0SDag-Erling Smørgrav #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 6664b17dab0SDag-Erling Smørgrav #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 6674b17dab0SDag-Erling Smørgrav #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 6684b17dab0SDag-Erling Smørgrav #define RB_NEXT(name, x, y) name##_RB_NEXT(x, y) 6694b17dab0SDag-Erling Smørgrav #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 6704b17dab0SDag-Erling Smørgrav #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 6714b17dab0SDag-Erling Smørgrav 6724b17dab0SDag-Erling Smørgrav #define RB_FOREACH(x, name, head) \ 6734b17dab0SDag-Erling Smørgrav for ((x) = RB_MIN(name, head); \ 6744b17dab0SDag-Erling Smørgrav (x) != NULL; \ 6754b17dab0SDag-Erling Smørgrav (x) = name##_RB_NEXT(head, x)) 6764b17dab0SDag-Erling Smørgrav 6774b17dab0SDag-Erling Smørgrav #endif /* _SYS_TREE_H_ */ 678