tree.h - webdump - HTML to plain-text converter for webpages (HTM) git clone git://git.codemadness.org/webdump (DIR) Log (DIR) Files (DIR) Refs (DIR) README (DIR) LICENSE --- tree.h (7303B) --- 1 /* $OpenBSD: tree.h,v 1.31 2023/03/08 04:43:09 guenther Exp $ */ 2 /* 3 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27 #ifndef TREE_H 28 #define TREE_H 29 30 /* 31 * This file defines a red-black tree structure. 32 * 33 * A red-black tree is a binary search tree with the node color as an 34 * extra attribute. It fulfills a set of conditions: 35 * - every search path from the root to a leaf consists of the 36 * same number of black nodes, 37 * - each red node (except for the root) has a black parent, 38 * - each leaf node is black. 39 * 40 * Every operation on a red-black tree is bounded as O(lg n). 41 * The maximum height of a red-black tree is 2lg (n+1). 42 */ 43 44 /* Macros that define a red-black tree */ 45 #define RB_HEAD(name, type) \ 46 struct name { \ 47 struct type *rbh_root; /* root of the tree */ \ 48 } 49 50 #define RB_INITIALIZER(root) \ 51 { NULL } 52 53 #define RB_INIT(root) do { \ 54 (root)->rbh_root = NULL; \ 55 } while (0) 56 57 #define RB_BLACK 0 58 #define RB_RED 1 59 #define RB_ENTRY(type) \ 60 struct { \ 61 struct type *rbe_left; /* left element */ \ 62 struct type *rbe_right; /* right element */ \ 63 struct type *rbe_parent; /* parent element */ \ 64 int rbe_color; /* node color */ \ 65 } 66 67 #define RB_LEFT(elm, field) (elm)->field.rbe_left 68 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 69 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 70 #define RB_COLOR(elm, field) (elm)->field.rbe_color 71 #define RB_ROOT(head) (head)->rbh_root 72 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 73 74 #define RB_SET(elm, parent, field) do { \ 75 RB_PARENT(elm, field) = parent; \ 76 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 77 RB_COLOR(elm, field) = RB_RED; \ 78 } while (0) 79 80 #define RB_SET_BLACKRED(black, red, field) do { \ 81 RB_COLOR(black, field) = RB_BLACK; \ 82 RB_COLOR(red, field) = RB_RED; \ 83 } while (0) 84 85 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 86 (tmp) = RB_RIGHT(elm, field); \ 87 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ 88 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 89 } \ 90 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 91 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 92 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 93 else \ 94 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 95 } else \ 96 (head)->rbh_root = (tmp); \ 97 RB_LEFT(tmp, field) = (elm); \ 98 RB_PARENT(elm, field) = (tmp); \ 99 } while (0) 100 101 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 102 (tmp) = RB_LEFT(elm, field); \ 103 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ 104 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 105 } \ 106 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 107 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 108 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 109 else \ 110 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 111 } else \ 112 (head)->rbh_root = (tmp); \ 113 RB_RIGHT(tmp, field) = (elm); \ 114 RB_PARENT(elm, field) = (tmp); \ 115 } while (0) 116 117 /* Moves node close to the key of elm to top 118 */ 119 #define RB_GENERATE(name, type, field, cmp) \ 120 RB_GENERATE_INTERNAL(name, type, field, cmp,) 121 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 122 attr void \ 123 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 124 { \ 125 struct type *parent, *gparent, *tmp; \ 126 while ((parent = RB_PARENT(elm, field)) && \ 127 RB_COLOR(parent, field) == RB_RED) { \ 128 gparent = RB_PARENT(parent, field); \ 129 if (parent == RB_LEFT(gparent, field)) { \ 130 tmp = RB_RIGHT(gparent, field); \ 131 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 132 RB_COLOR(tmp, field) = RB_BLACK; \ 133 RB_SET_BLACKRED(parent, gparent, field);\ 134 elm = gparent; \ 135 continue; \ 136 } \ 137 if (RB_RIGHT(parent, field) == elm) { \ 138 RB_ROTATE_LEFT(head, parent, tmp, field);\ 139 tmp = parent; \ 140 parent = elm; \ 141 elm = tmp; \ 142 } \ 143 RB_SET_BLACKRED(parent, gparent, field); \ 144 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 145 } else { \ 146 tmp = RB_LEFT(gparent, field); \ 147 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 148 RB_COLOR(tmp, field) = RB_BLACK; \ 149 RB_SET_BLACKRED(parent, gparent, field);\ 150 elm = gparent; \ 151 continue; \ 152 } \ 153 if (RB_LEFT(parent, field) == elm) { \ 154 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 155 tmp = parent; \ 156 parent = elm; \ 157 elm = tmp; \ 158 } \ 159 RB_SET_BLACKRED(parent, gparent, field); \ 160 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 161 } \ 162 } \ 163 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 164 } \ 165 \ 166 /* Inserts a node into the RB tree */ \ 167 attr struct type * \ 168 name##_RB_INSERT(struct name *head, struct type *elm) \ 169 { \ 170 struct type *tmp; \ 171 struct type *parent = NULL; \ 172 int comp = 0; \ 173 tmp = RB_ROOT(head); \ 174 while (tmp) { \ 175 parent = tmp; \ 176 comp = (cmp)(elm, parent); \ 177 if (comp < 0) \ 178 tmp = RB_LEFT(tmp, field); \ 179 else if (comp > 0) \ 180 tmp = RB_RIGHT(tmp, field); \ 181 else \ 182 return (tmp); \ 183 } \ 184 RB_SET(elm, parent, field); \ 185 if (parent != NULL) { \ 186 if (comp < 0) \ 187 RB_LEFT(parent, field) = elm; \ 188 else \ 189 RB_RIGHT(parent, field) = elm; \ 190 } else \ 191 RB_ROOT(head) = elm; \ 192 name##_RB_INSERT_COLOR(head, elm); \ 193 return (NULL); \ 194 } \ 195 \ 196 /* Finds the node with the same key as elm */ \ 197 attr struct type * \ 198 name##_RB_FIND(struct name *head, struct type *elm) \ 199 { \ 200 struct type *tmp = RB_ROOT(head); \ 201 int comp; \ 202 while (tmp) { \ 203 comp = cmp(elm, tmp); \ 204 if (comp < 0) \ 205 tmp = RB_LEFT(tmp, field); \ 206 else if (comp > 0) \ 207 tmp = RB_RIGHT(tmp, field); \ 208 else \ 209 return (tmp); \ 210 } \ 211 return (NULL); \ 212 } 213 214 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 215 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 216 217 #endif /* TREE_H */