ospf6d/ospf6_bintree.c

   1
   2 #include <zebra.h>
   3 #include "ospf6_bintree.h"
   4
   5 static struct bintree_node *
   6 bintree_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
  19 static struct bintree_node *
  20 bintree_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
  31 void *
  32 bintree_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
  61 void *
  62 bintree_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
  71 void *
  72 bintree_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
  81 int
  82 bintree_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
 138 static void
 139 bintree_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
 149 static void
 150 bintree_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
 187 int
 188 bintree_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
 274 void
 275 bintree_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
 297 int
 298 bintree_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
 316 void
 317 bintree_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
 380 struct bintree *
 381 bintree_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
 391 void
 392 bintree_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
 404 int indent_num = 0;
 405
 406 void
 407 bintree_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
 429 void
 430 bintree_print (void (*print) (int, void *), struct bintree *tree)
 431 {
 432   indent_num = 0;
 433   bintree_print_sub (print, tree->root);
 434 }
 435
 436