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