1 2#include <zebra.h> 3#include "ospf6_bintree.h" 4 5static struct bintree_node * 6bintree_lookup_node_min (struct bintree_node *subroot) 7{ 8 struct bintree_node *node; 9 10 if (subroot == NULL) 11 return NULL; 12 13 node = subroot; 14 while (node->bl_left) 15 node = node->bl_left; 16 return node; 17} 18 19static struct bintree_node * 20bintree_lookup_node_max (struct bintree_node *subroot) 21{ 22 struct bintree_node *node; 23 24 assert (subroot != NULL); 25 node = subroot; 26 while (node->bl_right) 27 node = node->bl_right; 28 return node; 29} 30 31void * 32bintree_lookup (void *data, struct bintree *tree) 33{ 34 int cmp; 35 struct bintree_node *node; 36 37 node = tree->root; 38 39 while (node) 40 { 41 if (tree->cmp) 42 cmp = (*tree->cmp) (node->data, data); 43 else 44 cmp = (node->data - data); 45 46 if (cmp == 0) 47 break; 48 49 if (cmp > 0) 50 node = node->bl_left; 51 else /* if (cmp < 0) */ 52 node = node->bl_right; 53 } 54 55 if (node) 56 return node->data; 57 58 return NULL; 59} 60 61void * 62bintree_lookup_min (struct bintree *tree) 63{ 64 struct bintree_node *node; 65 node = bintree_lookup_node_min (tree->root); 66 if (node == NULL) 67 return NULL; 68 return node->data; 69} 70 71void * 72bintree_lookup_max (struct bintree *tree) 73{ 74 struct bintree_node *node; 75 node = bintree_lookup_node_max (tree->root); 76 if (node == NULL) 77 return NULL; 78 return node->data; 79} 80 81int 82bintree_add (void *data, struct bintree *tree) 83{ 84 int cmp = 0; 85 struct bintree_node *node, *parent; 86 87 node = tree->root; 88 parent = NULL; 89 90 while (node) 91 { 92 if (tree->cmp) 93 cmp = (*tree->cmp) (node->data, data); 94 else 95 cmp = (node->data - data); 96 97 if (cmp == 0) 98 break; 99 100 parent = node; 101 if (cmp > 0) 102 node = node->bl_left; 103 else /* if (cmp < 0) */ 104 node = node->bl_right; 105 } 106 107 if (node) 108 return -1; 109 110 node = malloc (sizeof (struct bintree_node)); 111 memset (node, 0, sizeof (struct bintree_node)); 112 node->tree = tree; 113 node->data = data; 114 115 if (parent) 116 { 117 node->parent = parent; 118 119 assert (cmp != 0); 120 if (cmp > 0) 121 { 122 node->parent_link = BL_LEFT; 123 parent->bl_left = node; 124 } 125 else /* if (cmp < 0) */ 126 { 127 node->parent_link = BL_RIGHT; 128 parent->bl_right = node; 129 } 130 } 131 else 132 tree->root = node; 133 134 tree->count++; 135 return 0; 136} 137 138static void 139bintree_remove_nochild (struct bintree_node *node) 140{ 141 assert (node->bl_left == NULL && node->bl_right == NULL); 142 143 if (node->parent == NULL) 144 node->tree->root = NULL; 145 else 146 node->parent->link[node->parent_link] = NULL; 147} 148 149static void 150bintree_remove_onechild (struct bintree_node *node) 151{ 152 assert ((node->bl_left == NULL && node->bl_right != NULL) || 153 (node->bl_left != NULL && node->bl_right == NULL)); 154 155 if (node->bl_left) 156 { 157 if (node->parent == NULL) 158 { 159 node->tree->root = node->bl_left; 160 node->bl_left->parent = NULL; 161 } 162 else 163 { 164 node->parent->link[node->parent_link] = node->bl_left; 165 node->bl_left->parent = node->parent; 166 node->bl_left->parent_link = node->parent_link; 167 } 168 } 169 else if (node->bl_right) 170 { 171 if (node->parent == NULL) 172 { 173 node->tree->root = node->bl_right; 174 node->bl_right->parent = NULL; 175 } 176 else 177 { 178 node->parent->link[node->parent_link] = node->bl_right; 179 node->bl_right->parent = node->parent; 180 node->bl_right->parent_link = node->parent_link; 181 } 182 } 183 else 184 assert (0); 185} 186 187int 188bintree_remove (void *data, struct bintree *tree) 189{ 190 int cmp; 191 struct bintree_node *node; 192 193 node = tree->root; 194 195 while (node) 196 { 197 if (tree->cmp) 198 cmp = (*tree->cmp) (node->data, data); 199 else 200 cmp = (node->data - data); 201 202 if (cmp == 0) 203 break; 204 205 if (cmp > 0) 206 node = node->bl_left; 207 else /* if (cmp < 0) */ 208 node = node->bl_right; 209 } 210 211 if (node == NULL) 212 return -1; 213 214 if (node->bl_left == NULL && node->bl_right == NULL) 215 { 216 bintree_remove_nochild (node); 217 free (node); 218 tree->count--; 219 return 0; 220 } 221 222 if ((node->bl_left == NULL && node->bl_right != NULL) || 223 (node->bl_left != NULL && node->bl_right == NULL)) 224 { 225 bintree_remove_onechild (node); 226 free (node); 227 tree->count--; 228 return 0; 229 } 230 231 if (node->bl_left != NULL && node->bl_right != NULL) 232 { 233 struct bintree_node *successor; 234 235 /* find successor of the removing node */ 236 successor = bintree_lookup_node_min (node->bl_right); 237 238 /* remove successor from tree */ 239 if (successor->bl_right) 240 bintree_remove_onechild (successor); 241 else 242 bintree_remove_nochild (successor); 243 244 /* swap removing node with successor */ 245 successor->parent = node->parent; 246 successor->parent_link = node->parent_link; 247 successor->bl_left = node->bl_left; 248 successor->bl_right = node->bl_right; 249 250 /* if the successor was the node->bl_right itself, 251 bintree_remove_**child may touch node->bl_right, 252 so only the successor->bl_right may be NULL 253 by above assignment */ 254 successor->bl_left->parent = successor; 255 if (successor->bl_right) 256 successor->bl_right->parent = successor; 257 258 if (successor->parent == NULL) 259 tree->root = successor; 260 else 261 successor->parent->link[successor->parent_link] = successor; 262 263 free (node); 264 tree->count--; 265 return 0; 266 } 267 268 /* not reached */ 269 return -1; 270} 271 272/* in-order traversal */ 273 274void 275bintree_head (struct bintree *tree, struct bintree_node *node) 276{ 277 struct bintree_node *head; 278 279 head = bintree_lookup_node_min (tree->root); 280 if (head == NULL) 281 { 282 node->parent = NULL; 283 node->bl_left = NULL; 284 node->bl_right = NULL; 285 node->data = NULL; 286 return; 287 } 288 289 node->tree = head->tree; 290 node->parent = head->parent; 291 node->parent_link = head->parent_link; 292 node->bl_left = head->bl_left; 293 node->bl_right = head->bl_right; 294 node->data = head->data; 295} 296 297int 298bintree_end (struct bintree_node *node) 299{ 300 if (node->parent || node->bl_left || node->bl_right || node->data) 301 return 0; 302 return 1; 303} 304 305#define GOTO_PROCED_SUBTREE_TOP(node) \ 306 while (node->parent && node->parent->bl_right && \ 307 node->parent->bl_right->data == node->data) \ 308 { \ 309 node->data = node->parent->data; \ 310 node->bl_left = node->parent->bl_left; \ 311 node->bl_right = node->parent->bl_right; \ 312 node->parent_link = node->parent->parent_link; \ 313 node->parent = node->parent->parent; \ 314 } 315 316void 317bintree_next (struct bintree_node *node) 318{ 319 struct bintree_node *next = NULL; 320 321 /* if node have just been removed, current point should have just been 322 replaced with its successor. that certainly will not be processed 323 yet, so process it */ 324 if (node->parent == NULL) 325 { 326 if (node->tree->root == NULL) 327 { 328 assert (node->tree->count == 0); 329 node->parent = NULL; 330 node->bl_left = NULL; 331 node->bl_right = NULL; 332 node->data = NULL; 333 return; 334 } 335 else if (node->tree->root->data != node->data) 336 next = node->tree->root; 337 } 338 else if (node->parent->link[node->parent_link] == NULL) 339 { 340 if (node->parent_link == BL_LEFT) 341 next = node->parent; 342 else 343 { 344 GOTO_PROCED_SUBTREE_TOP (node); 345 next = node->parent; 346 } 347 } 348 else if (node->parent->link[node->parent_link]->data != node->data) 349 next = node->parent->link[node->parent_link]; 350 351 if (next == NULL) 352 { 353 if (node->bl_right) 354 next = bintree_lookup_node_min (node->bl_right); 355 else 356 { 357 GOTO_PROCED_SUBTREE_TOP (node); 358 next = node->parent; 359 } 360 } 361 362 if (next) 363 { 364 node->tree = next->tree; 365 node->parent = next->parent; 366 node->parent_link = next->parent_link; 367 node->bl_left = next->bl_left; 368 node->bl_right = next->bl_right; 369 node->data = next->data; 370 } 371 else 372 { 373 node->parent = NULL; 374 node->bl_left = NULL; 375 node->bl_right = NULL; 376 node->data = NULL; 377 } 378} 379 380struct bintree * 381bintree_create () 382{ 383 struct bintree *tree; 384 385 tree = malloc (sizeof (struct bintree)); 386 memset (tree, 0, sizeof (struct bintree)); 387 388 return tree; 389} 390 391void 392bintree_delete (struct bintree *tree) 393{ 394 struct bintree_node node; 395 396 for (bintree_head (tree, &node); ! bintree_end (&node); 397 bintree_next (&node)) 398 bintree_remove (node.data, tree); 399 400 assert (tree->count == 0); 401 free (tree); 402} 403 404int indent_num = 0; 405 406void 407bintree_print_sub (void (*print) (int, void *), struct bintree_node *subroot) 408{ 409 if (subroot == NULL) 410 return; 411 412 if (subroot->bl_right) 413 { 414 indent_num++; 415 bintree_print_sub (print, subroot->bl_right); 416 indent_num--; 417 } 418 419 (*print) (indent_num, subroot->data); 420 421 if (subroot->bl_left) 422 { 423 indent_num++; 424 bintree_print_sub (print, subroot->bl_left); 425 indent_num--; 426 } 427} 428 429void 430bintree_print (void (*print) (int, void *), struct bintree *tree) 431{ 432 indent_num = 0; 433 bintree_print_sub (print, tree->root); 434} 435 436 437