Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
FreeBSD/Linux Kernel Cross Reference
sys/lib/rbtree.c
Version:
- FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
SearchContext: - none - 3 - 10
1 /* 2 Red Black Trees 3 (C) 1999 Andrea Arcangeli <andrea@suse.de> 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 2 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program; if not, write to the Free Software 17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 18 19 linux/lib/rbtree.c 20 */ 21 22 #include <linux/rbtree.h> 23 #include <linux/module.h> 24 25 static void __rb_rotate_left(rb_node_t * node, rb_root_t * root) 26 { 27 rb_node_t * right = node->rb_right; 28 29 if ((node->rb_right = right->rb_left)) 30 right->rb_left->rb_parent = node; 31 right->rb_left = node; 32 33 if ((right->rb_parent = node->rb_parent)) 34 { 35 if (node == node->rb_parent->rb_left) 36 node->rb_parent->rb_left = right; 37 else 38 node->rb_parent->rb_right = right; 39 } 40 else 41 root->rb_node = right; 42 node->rb_parent = right; 43 } 44 45 static void __rb_rotate_right(rb_node_t * node, rb_root_t * root) 46 { 47 rb_node_t * left = node->rb_left; 48 49 if ((node->rb_left = left->rb_right)) 50 left->rb_right->rb_parent = node; 51 left->rb_right = node; 52 53 if ((left->rb_parent = node->rb_parent)) 54 { 55 if (node == node->rb_parent->rb_right) 56 node->rb_parent->rb_right = left; 57 else 58 node->rb_parent->rb_left = left; 59 } 60 else 61 root->rb_node = left; 62 node->rb_parent = left; 63 } 64 65 void rb_insert_color(rb_node_t * node, rb_root_t * root) 66 { 67 rb_node_t * parent, * gparent; 68 69 while ((parent = node->rb_parent) && parent->rb_color == RB_RED) 70 { 71 gparent = parent->rb_parent; 72 73 if (parent == gparent->rb_left) 74 { 75 { 76 register rb_node_t * uncle = gparent->rb_right; 77 if (uncle && uncle->rb_color == RB_RED) 78 { 79 uncle->rb_color = RB_BLACK; 80 parent->rb_color = RB_BLACK; 81 gparent->rb_color = RB_RED; 82 node = gparent; 83 continue; 84 } 85 } 86 87 if (parent->rb_right == node) 88 { 89 register rb_node_t * tmp; 90 __rb_rotate_left(parent, root); 91 tmp = parent; 92 parent = node; 93 node = tmp; 94 } 95 96 parent->rb_color = RB_BLACK; 97 gparent->rb_color = RB_RED; 98 __rb_rotate_right(gparent, root); 99 } else { 100 { 101 register rb_node_t * uncle = gparent->rb_left; 102 if (uncle && uncle->rb_color == RB_RED) 103 { 104 uncle->rb_color = RB_BLACK; 105 parent->rb_color = RB_BLACK; 106 gparent->rb_color = RB_RED; 107 node = gparent; 108 continue; 109 } 110 } 111 112 if (parent->rb_left == node) 113 { 114 register rb_node_t * tmp; 115 __rb_rotate_right(parent, root); 116 tmp = parent; 117 parent = node; 118 node = tmp; 119 } 120 121 parent->rb_color = RB_BLACK; 122 gparent->rb_color = RB_RED; 123 __rb_rotate_left(gparent, root); 124 } 125 } 126 127 root->rb_node->rb_color = RB_BLACK; 128 } 129 EXPORT_SYMBOL(rb_insert_color); 130 131 static void __rb_erase_color(rb_node_t * node, rb_node_t * parent, 132 rb_root_t * root) 133 { 134 rb_node_t * other; 135 136 while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node) 137 { 138 if (parent->rb_left == node) 139 { 140 other = parent->rb_right; 141 if (other->rb_color == RB_RED) 142 { 143 other->rb_color = RB_BLACK; 144 parent->rb_color = RB_RED; 145 __rb_rotate_left(parent, root); 146 other = parent->rb_right; 147 } 148 if ((!other->rb_left || 149 other->rb_left->rb_color == RB_BLACK) 150 && (!other->rb_right || 151 other->rb_right->rb_color == RB_BLACK)) 152 { 153 other->rb_color = RB_RED; 154 node = parent; 155 parent = node->rb_parent; 156 } 157 else 158 { 159 if (!other->rb_right || 160 other->rb_right->rb_color == RB_BLACK) 161 { 162 register rb_node_t * o_left; 163 if ((o_left = other->rb_left)) 164 o_left->rb_color = RB_BLACK; 165 other->rb_color = RB_RED; 166 __rb_rotate_right(other, root); 167 other = parent->rb_right; 168 } 169 other->rb_color = parent->rb_color; 170 parent->rb_color = RB_BLACK; 171 if (other->rb_right) 172 other->rb_right->rb_color = RB_BLACK; 173 __rb_rotate_left(parent, root); 174 node = root->rb_node; 175 break; 176 } 177 } 178 else 179 { 180 other = parent->rb_left; 181 if (other->rb_color == RB_RED) 182 { 183 other->rb_color = RB_BLACK; 184 parent->rb_color = RB_RED; 185 __rb_rotate_right(parent, root); 186 other = parent->rb_left; 187 } 188 if ((!other->rb_left || 189 other->rb_left->rb_color == RB_BLACK) 190 && (!other->rb_right || 191 other->rb_right->rb_color == RB_BLACK)) 192 { 193 other->rb_color = RB_RED; 194 node = parent; 195 parent = node->rb_parent; 196 } 197 else 198 { 199 if (!other->rb_left || 200 other->rb_left->rb_color == RB_BLACK) 201 { 202 register rb_node_t * o_right; 203 if ((o_right = other->rb_right)) 204 o_right->rb_color = RB_BLACK; 205 other->rb_color = RB_RED; 206 __rb_rotate_left(other, root); 207 other = parent->rb_left; 208 } 209 other->rb_color = parent->rb_color; 210 parent->rb_color = RB_BLACK; 211 if (other->rb_left) 212 other->rb_left->rb_color = RB_BLACK; 213 __rb_rotate_right(parent, root); 214 node = root->rb_node; 215 break; 216 } 217 } 218 } 219 if (node) 220 node->rb_color = RB_BLACK; 221 } 222 223 void rb_erase(rb_node_t * node, rb_root_t * root) 224 { 225 rb_node_t * child, * parent; 226 int color; 227 228 if (!node->rb_left) 229 child = node->rb_right; 230 else if (!node->rb_right) 231 child = node->rb_left; 232 else 233 { 234 rb_node_t * old = node, * left; 235 236 node = node->rb_right; 237 while ((left = node->rb_left)) 238 node = left; 239 child = node->rb_right; 240 parent = node->rb_parent; 241 color = node->rb_color; 242 243 if (child) 244 child->rb_parent = parent; 245 if (parent) 246 { 247 if (parent->rb_left == node) 248 parent->rb_left = child; 249 else 250 parent->rb_right = child; 251 } 252 else 253 root->rb_node = child; 254 255 if (node->rb_parent == old) 256 parent = node; 257 node->rb_parent = old->rb_parent; 258 node->rb_color = old->rb_color; 259 node->rb_right = old->rb_right; 260 node->rb_left = old->rb_left; 261 262 if (old->rb_parent) 263 { 264 if (old->rb_parent->rb_left == old) 265 old->rb_parent->rb_left = node; 266 else 267 old->rb_parent->rb_right = node; 268 } else 269 root->rb_node = node; 270 271 old->rb_left->rb_parent = node; 272 if (old->rb_right) 273 old->rb_right->rb_parent = node; 274 goto color; 275 } 276 277 parent = node->rb_parent; 278 color = node->rb_color; 279 280 if (child) 281 child->rb_parent = parent; 282 if (parent) 283 { 284 if (parent->rb_left == node) 285 parent->rb_left = child; 286 else 287 parent->rb_right = child; 288 } 289 else 290 root->rb_node = child; 291 292 color: 293 if (color == RB_BLACK) 294 __rb_erase_color(child, parent, root); 295 } 296 EXPORT_SYMBOL(rb_erase);
Cache object: dbd4e680f310d69c3ab957e26dec9f78
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]