mpls_avl.c

技术文件名称：MPLSv1.0软件模块测试规程

/****************************************************************************/
/*      Product Name:   MPLS PACK1.0
 *      Module  Name:   LDP/CR_LDP
 *      File    Name:   mpls_mrg.c
 *      Author  Name:   f.jun weng.qing gao.xiaoqing
 *      Creat   Date:   2002-6-18
 *      Version     :   1.0
 *      Function    :   MPLS pack1.0 avl function
 *      Note        :   
 *      2002.12.3  Huyonghong 将assert 调用改为 MPLS_ASSERT调用               */      
/****************************************************************************/

#include "string.h" 
#include "stdlib.h"
#include "stdio.h"
#include "assert.h"
#include "mpls_cmn.h"

#include <mpls_avl.h>

void mpls_avl_balance_tree(MPLS_AVL_TREE *, MPLS_AVL_NODE *);
void mpls_avl_rebalance(MPLS_AVL_NODE **);
void mpls_avl_rotate_right(MPLS_AVL_NODE **);
void mpls_avl_rotate_left(MPLS_AVL_NODE **);
void mpls_avl_swap_right_most(MPLS_AVL_TREE *, MPLS_AVL_NODE *, MPLS_AVL_NODE *);
void mpls_avl_swap_left_most(MPLS_AVL_TREE *, MPLS_AVL_NODE *, MPLS_AVL_NODE *);

/**PROC+**********************************************************************/
/* Name:      mpls_avl_insert_or_find                                        */
/*                                                                           */
/* Purpose:   Insert the supplied node into the specified AVL tree if key    */
/*            does not already exist, otherwise returning the existing node  */
/*                                                                           */
/* Returns:   void *               - Pointer to existing entry if found. */
/*                                       NULL if no such entry (implies node */
/*                                       successfully inserted)              */
/*                                                                           */
/* Params:    IN     tree              - a pointer to the AVL tree           */
/*            IN     node              - a pointer to the node to insert     */
/*                                                                           */
/* Operation: Scan down the tree looking for the insert point, going left    */
/*            if the insert key is less than the key in the tree and         */
/*            right if it is greater. When the insert point is found insert  */
/*            the new node and rebalance the tree if necessary. Return the   */
/*            existing entry instead, if found                               */
/*                                                                           */
/**PROC-**********************************************************************/
void *mpls_avl_insert_or_find(MPLS_AVL_TREE *tree, MPLS_AVL_NODE *node)
{
  /***************************************************************************/
  /* insert specified node into tree                                         */
  /***************************************************************************/
  MPLS_AVL_NODE *parent_node;
  int result;
  void *existing_entry = NULL;

  MPLS_ASSERT(!MPLS_AVL_IN_TREE(*node));

  node->r_height = 0;
  node->l_height = 0;

  if (tree->root == NULL)
  {
    /*************************************************************************/
    /* tree is empty, so insert at root                                      */
    /*************************************************************************/
    tree->root = node;
    tree->first = node;
    tree->last = node;
    goto EXIT;
  }

  /***************************************************************************/
  /* scan down the tree looking for the appropriate insert point             */
  /***************************************************************************/
  parent_node = tree->root;
  while (parent_node != NULL)
  {
    /*************************************************************************/
    /* go left or right, depending on comparison                             */
    /*************************************************************************/
    result = tree->compare(node->key, parent_node->key);

    if (result > 0)
    {
      /***********************************************************************/
      /* new key is greater than this node's key, so move down right subtree */
      /***********************************************************************/
      if (parent_node->right == NULL)
      {
        /*********************************************************************/
        /* right subtree is empty, so insert here                            */
        /*********************************************************************/
        node->parent = parent_node;
        parent_node->right = node;
        parent_node->r_height = 1;
        if (parent_node == tree->last)
        {
          /*******************************************************************/
          /* parent was the right-most node in the tree, so new node is now  */
          /* right-most                                                      */
          /*******************************************************************/
          tree->last = node;
        }
        break;
      }
      else
      {
        /*********************************************************************/
        /* right subtree is not empty                                        */
        /*********************************************************************/
        parent_node = parent_node->right;
      }
    }
    else if (result < 0)
    {
      /***********************************************************************/
      /* new key is less than this node's key, so move down left subtree     */
      /***********************************************************************/
      if (parent_node->left == NULL)
      {
        /*********************************************************************/
        /* left subtree is empty, so insert here                             */
        /*********************************************************************/
        node->parent = parent_node;
        parent_node->left = node;
        parent_node->l_height = 1;
        if (parent_node == tree->first)
        {
          /*******************************************************************/
          /* parent was the left-most node in the tree, so new node is now   */
          /* left-most                                                       */
          /*******************************************************************/
          tree->first = node;
        }
        break;
      }
      else
      {
        /*********************************************************************/
        /* left subtree is not empty                                         */
        /*********************************************************************/
        parent_node = parent_node->left;
      }
    }
    else
    {
      /***********************************************************************/
      /* found a matching key, so get out now and return entry found         */
      /***********************************************************************/
      existing_entry = parent_node->self;
      node->r_height = -1;
      node->l_height = -1;
      goto EXIT;
    }
  }

  /***************************************************************************/
  /* now rebalance the tree if necessary                                     */
  /***************************************************************************/
  mpls_avl_balance_tree(tree, parent_node);

EXIT:

  return(existing_entry);

} /* mpls_avl_insert_or_find */

/**PROC+**********************************************************************/
/* Name:      mpls_avl_delete                                                */
/*                                                                           */
/* Purpose:   Delete the specified node from the specified AVL tree          */
/*                                                                           */
/* Returns:   Nothing                                                        */
/*                                                                           */
/* Params:    IN     tree              - a pointer to the AVL tree           */
/*            IN     node              - a pointer to the node to delete     */
/*                                                                           */
/**PROC-**********************************************************************/
void mpls_avl_delete(MPLS_AVL_TREE *tree, MPLS_AVL_NODE *node)
{
  /***************************************************************************/
  /* delete specified node from tree                                         */
  /***************************************************************************/
  MPLS_AVL_NODE *replace_node;
  MPLS_AVL_NODE *parent_node;
  unsigned short new_height;

  MPLS_ASSERT(MPLS_AVL_IN_TREE(*node));

  if ((node->left == NULL) &&
      (node->right == NULL))
  {
    /*************************************************************************/
    /* barren node (no children), so just delete it                          */
    /*************************************************************************/
    replace_node = NULL;

    if (tree->first == node)
    {
      /***********************************************************************/
      /* node was first in tree, so replace it                               */
      /***********************************************************************/
      tree->first = node->parent;
    }

    if (tree->last == node)
    {
      /***********************************************************************/
      /* node was last in tree, so replace it                                */
      /***********************************************************************/
      tree->last = node->parent;
    }
  }
  else if (node->left == NULL)
  {
    /*************************************************************************/
    /* node has no left son, so replace with right son                       */
    /*************************************************************************/
    replace_node = node->right;

    if (tree->first == node)
    {
      /***********************************************************************/
      /* node was first in tree, so replace it                               */
      /***********************************************************************/
      tree->first = replace_node;
    }
  }
  else if (node->right == NULL)
  {
    /*************************************************************************/
    /* node has no right son, so replace with left son                       */
    /*************************************************************************/
    replace_node = node->left;

    if (tree->last == node)
    {
      /***********************************************************************/
      /* node was last in tree, so replace it                                */
      /***********************************************************************/
      tree->last = replace_node;
    }
  }
  else
  {
    /*************************************************************************/
    /* node has both left and right-sons                                     */
    /*************************************************************************/
    if (node->r_height > node->l_height)
    {
      /***********************************************************************/
      /* right subtree is higher than left subtree                           */
      /***********************************************************************/
      if (node->right->left == NULL)
      {
        /*********************************************************************/
        /* can replace node with right-son (since it has no left-son)        */
        /*********************************************************************/
        replace_node = node->right;
        replace_node->left = node->left;
        replace_node->left->parent = replace_node;
        replace_node->l_height = node->l_height;
      }
      else
      {
        /*********************************************************************/
        /* swap with left-most descendent of right subtree                   */
        /*********************************************************************/
        mpls_avl_swap_left_most(tree, node->right, node);
        replace_node = node->right;
      }
    }
    else
    {
      /***********************************************************************/
      /* left subtree is higher (or subtrees are of same height)             */
      /***********************************************************************/
      if (node->left->right == NULL)
      {
        /*********************************************************************/
        /* can replace node with left-son (since it has no right-son)        */
        /*********************************************************************/
        replace_node = node->left;
        replace_node->right = node->right;
        replace_node->right->parent = replace_node;
        replace_node->r_height = node->r_height;
      }
      else
      {
        /*********************************************************************/
        /* swap with right-most descendent of left subtree                   */
        /*********************************************************************/
        mpls_avl_swap_right_most(tree, node->left, node);
        replace_node = node->left;
      }
    }
  }

  /***************************************************************************/
  /* save parent node of deleted node                                        */
  /***************************************************************************/
  parent_node = node->parent;

  /***************************************************************************/
  /* reset deleted node                                                      */
  /***************************************************************************/
  node->parent = NULL;
  node->right = NULL;
  node->left = NULL;
  node->r_height = -1;
  node->l_height = -1;

  if (replace_node != NULL)
  {
    /*************************************************************************/
    /* fix-up parent pointer of replacement node, and calculate new height   */
    /* of subtree                                                            */
    /*************************************************************************/
    replace_node->parent = parent_node;
    new_height = (unsigned short)
                 (1 + MPLS_MAX(replace_node->l_height, replace_node->r_height));
  }
  else
  {
    /*************************************************************************/
    /* no replacement, so new height of subtree is zero                      */