From 718e3744195351130f4ce7dbe0613f4b3e23df93 Mon Sep 17 00:00:00 2001
From: paul <paul>
Date: Fri, 13 Dec 2002 20:15:29 +0000
Subject: Initial revision

---
 ospf6d/ospf6_bintree.c | 436 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 436 insertions(+)
 create mode 100644 ospf6d/ospf6_bintree.c

(limited to 'ospf6d/ospf6_bintree.c')

diff --git a/ospf6d/ospf6_bintree.c b/ospf6d/ospf6_bintree.c
new file mode 100644
index 00000000..c1e9e558
--- /dev/null
+++ b/ospf6d/ospf6_bintree.c
@@ -0,0 +1,436 @@
+
+#include <zebra.h>
+#include "ospf6_bintree.h"
+
+static struct bintree_node *
+bintree_lookup_node_min (struct bintree_node *subroot)
+{
+  struct bintree_node *node;
+
+  if (subroot == NULL)
+    return NULL;
+
+  node = subroot;
+  while (node->bl_left)
+    node = node->bl_left;
+  return node;
+}
+
+static struct bintree_node *
+bintree_lookup_node_max (struct bintree_node *subroot)
+{
+  struct bintree_node *node;
+
+  assert (subroot != NULL);
+  node = subroot;
+  while (node->bl_right)
+    node = node->bl_right;
+  return node;
+}
+
+void *
+bintree_lookup (void *data, struct bintree *tree)
+{
+  int cmp;
+  struct bintree_node *node;
+
+  node = tree->root;
+
+  while (node)
+    {
+      if (tree->cmp)
+        cmp = (*tree->cmp) (node->data, data);
+      else
+        cmp = (node->data - data);
+
+      if (cmp == 0)
+        break;
+
+      if (cmp > 0)
+        node = node->bl_left;
+      else /* if (cmp < 0) */
+        node = node->bl_right;
+    }
+
+  if (node)
+    return node->data;
+
+  return NULL;
+}
+
+void *
+bintree_lookup_min (struct bintree *tree)
+{
+  struct bintree_node *node;
+  node = bintree_lookup_node_min (tree->root);
+  if (node == NULL)
+    return NULL;
+  return node->data;
+}
+
+void *
+bintree_lookup_max (struct bintree *tree)
+{
+  struct bintree_node *node;
+  node = bintree_lookup_node_max (tree->root);
+  if (node == NULL)
+    return NULL;
+  return node->data;
+}
+
+int
+bintree_add (void *data, struct bintree *tree)
+{
+  int cmp = 0;
+  struct bintree_node *node, *parent;
+
+  node = tree->root;
+  parent = NULL;
+
+  while (node)
+    {
+      if (tree->cmp)
+        cmp = (*tree->cmp) (node->data, data);
+      else
+        cmp = (node->data - data);
+
+      if (cmp == 0)
+        break;
+
+      parent = node;
+      if (cmp > 0)
+        node = node->bl_left;
+      else /* if (cmp < 0) */
+        node = node->bl_right;
+    }
+
+  if (node)
+    return -1;
+
+  node = malloc (sizeof (struct bintree_node));
+  memset (node, 0, sizeof (struct bintree_node));
+  node->tree = tree;
+  node->data = data;
+
+  if (parent)
+    {
+      node->parent = parent;
+
+      assert (cmp != 0);
+      if (cmp > 0)
+        {
+          node->parent_link = BL_LEFT;
+          parent->bl_left = node;
+        }
+      else /* if (cmp < 0) */
+        {
+          node->parent_link = BL_RIGHT;
+          parent->bl_right = node;
+        }
+    }
+  else
+    tree->root = node;
+
+  tree->count++;
+  return 0;
+}
+
+static void
+bintree_remove_nochild (struct bintree_node *node)
+{
+  assert (node->bl_left == NULL && node->bl_right == NULL);
+
+  if (node->parent == NULL)
+    node->tree->root = NULL;
+  else
+    node->parent->link[node->parent_link] = NULL;
+}
+
+static void
+bintree_remove_onechild (struct bintree_node *node)
+{
+  assert ((node->bl_left == NULL && node->bl_right != NULL) ||
+          (node->bl_left != NULL && node->bl_right == NULL));
+
+  if (node->bl_left)
+    {
+      if (node->parent == NULL)
+        {
+          node->tree->root = node->bl_left;
+          node->bl_left->parent = NULL;
+        }
+      else
+        {
+          node->parent->link[node->parent_link] = node->bl_left;
+          node->bl_left->parent = node->parent;
+          node->bl_left->parent_link = node->parent_link;
+        }
+    }
+  else if (node->bl_right)
+    {
+      if (node->parent == NULL)
+        {
+          node->tree->root = node->bl_right;
+          node->bl_right->parent = NULL;
+        }
+      else
+        {
+          node->parent->link[node->parent_link] = node->bl_right;
+          node->bl_right->parent = node->parent;
+          node->bl_right->parent_link = node->parent_link;
+        }
+    }
+  else
+    assert (0);
+}
+
+int
+bintree_remove (void *data, struct bintree *tree)
+{
+  int cmp;
+  struct bintree_node *node;
+
+  node = tree->root;
+
+  while (node)
+    {
+      if (tree->cmp)
+        cmp = (*tree->cmp) (node->data, data);
+      else
+        cmp = (node->data - data);
+
+      if (cmp == 0)
+        break;
+
+      if (cmp > 0)
+        node = node->bl_left;
+      else /* if (cmp < 0) */
+        node = node->bl_right;
+    }
+
+  if (node == NULL)
+    return -1;
+
+  if (node->bl_left == NULL && node->bl_right == NULL)
+    {
+      bintree_remove_nochild (node);
+      free (node);
+      tree->count--;
+      return 0;
+    }
+
+  if ((node->bl_left == NULL && node->bl_right != NULL) ||
+      (node->bl_left != NULL && node->bl_right == NULL))
+    {
+      bintree_remove_onechild (node);
+      free (node);
+      tree->count--;
+      return 0;
+    }
+
+  if (node->bl_left != NULL && node->bl_right != NULL)
+    {
+      struct bintree_node *successor;
+
+      /* find successor of the removing node */
+      successor = bintree_lookup_node_min (node->bl_right);
+
+      /* remove successor from tree */
+      if (successor->bl_right)
+        bintree_remove_onechild (successor);
+      else
+        bintree_remove_nochild (successor);
+
+      /* swap removing node with successor */
+      successor->parent = node->parent;
+      successor->parent_link = node->parent_link;
+      successor->bl_left = node->bl_left;
+      successor->bl_right = node->bl_right;
+
+      /* if the successor was the node->bl_right itself,
+         bintree_remove_**child may touch node->bl_right,
+         so only the successor->bl_right may be NULL
+         by above assignment */
+      successor->bl_left->parent = successor;
+      if (successor->bl_right)
+        successor->bl_right->parent = successor;
+
+      if (successor->parent == NULL)
+        tree->root = successor;
+      else
+        successor->parent->link[successor->parent_link] = successor;
+
+      free (node);
+      tree->count--;
+      return 0;
+    }
+
+  /* not reached */
+  return -1;
+}
+
+/* in-order traversal */
+
+void
+bintree_head (struct bintree *tree, struct bintree_node *node)
+{
+  struct bintree_node *head;
+
+  head = bintree_lookup_node_min (tree->root);
+  if (head == NULL)
+    {
+      node->parent = NULL;
+      node->bl_left = NULL;
+      node->bl_right = NULL;
+      node->data = NULL;
+      return;
+    }
+
+  node->tree = head->tree;
+  node->parent = head->parent;
+  node->parent_link = head->parent_link;
+  node->bl_left = head->bl_left;
+  node->bl_right = head->bl_right;
+  node->data = head->data;
+}
+
+int
+bintree_end (struct bintree_node *node)
+{
+  if (node->parent || node->bl_left || node->bl_right || node->data)
+    return 0;
+  return 1;
+}
+
+#define GOTO_PROCED_SUBTREE_TOP(node) \
+  while (node->parent && node->parent->bl_right && \
+         node->parent->bl_right->data == node->data) \
+    { \
+      node->data = node->parent->data; \
+      node->bl_left = node->parent->bl_left; \
+      node->bl_right = node->parent->bl_right; \
+      node->parent_link = node->parent->parent_link; \
+      node->parent = node->parent->parent; \
+    }
+
+void
+bintree_next (struct bintree_node *node)
+{
+  struct bintree_node *next = NULL;
+
+  /* if node have just been removed, current point should have just been
+     replaced with its successor. that certainly  will not be processed
+     yet, so process it */
+  if (node->parent == NULL)
+    {
+      if (node->tree->root == NULL)
+        {
+          assert (node->tree->count == 0);
+          node->parent = NULL;
+          node->bl_left = NULL;
+          node->bl_right = NULL;
+          node->data = NULL;
+          return;
+        }
+      else if (node->tree->root->data != node->data)
+        next = node->tree->root;
+    }
+  else if (node->parent->link[node->parent_link] == NULL)
+    {
+      if (node->parent_link == BL_LEFT)
+        next = node->parent;
+      else
+        {
+          GOTO_PROCED_SUBTREE_TOP (node);
+          next = node->parent;
+        }
+    }
+  else if (node->parent->link[node->parent_link]->data != node->data)
+    next = node->parent->link[node->parent_link];
+
+  if (next == NULL)
+    {
+      if (node->bl_right)
+        next = bintree_lookup_node_min (node->bl_right);
+      else
+        {
+          GOTO_PROCED_SUBTREE_TOP (node);
+          next = node->parent;
+        }
+    }
+
+  if (next)
+    {
+      node->tree = next->tree;
+      node->parent = next->parent;
+      node->parent_link = next->parent_link;
+      node->bl_left = next->bl_left;
+      node->bl_right = next->bl_right;
+      node->data = next->data;
+    }
+  else
+    {
+      node->parent = NULL;
+      node->bl_left = NULL;
+      node->bl_right = NULL;
+      node->data = NULL;
+    }
+}
+
+struct bintree *
+bintree_create ()
+{
+  struct bintree *tree;
+
+  tree = malloc (sizeof (struct bintree));
+  memset (tree, 0, sizeof (struct bintree));
+
+  return tree;
+}
+
+void
+bintree_delete (struct bintree *tree)
+{
+  struct bintree_node node;
+
+  for (bintree_head (tree, &node); ! bintree_end (&node);
+       bintree_next (&node))
+    bintree_remove (node.data, tree);
+
+  assert (tree->count == 0);
+  free (tree);
+}
+
+int indent_num = 0;
+
+void
+bintree_print_sub (void (*print) (int, void *), struct bintree_node *subroot)
+{
+  if (subroot == NULL)
+    return;
+
+  if (subroot->bl_right)
+    {
+      indent_num++;
+      bintree_print_sub (print, subroot->bl_right);
+      indent_num--;
+    }
+
+  (*print) (indent_num, subroot->data);
+
+  if (subroot->bl_left)
+    {
+      indent_num++;
+      bintree_print_sub (print, subroot->bl_left);
+      indent_num--;
+    }
+}
+
+void
+bintree_print (void (*print) (int, void *), struct bintree *tree)
+{
+  indent_num = 0;
+  bintree_print_sub (print, tree->root);
+}
+
+
-- 
cgit v1.2.1