mpls_avl.c

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

    /*************************************************************************/
    new_height = 0;
  }

  if (parent_node != NULL)
  {
    /*************************************************************************/
    /* fixup parent node                                                     */
    /*************************************************************************/
    if (parent_node->right == node)
    {
      /***********************************************************************/
      /* node is right son of parent                                         */
      /***********************************************************************/
      parent_node->right = replace_node;
      parent_node->r_height = new_height;
    }
    else
    {
      /***********************************************************************/
      /* node is left son of parent                                          */
      /***********************************************************************/
      parent_node->left = replace_node;
      parent_node->l_height = new_height;
    }

    /*************************************************************************/
    /* now rebalance the tree (if necessary)                                 */
    /*************************************************************************/
    mpls_avl_balance_tree(tree, parent_node);
  }
  else
  {
    /*************************************************************************/
    /* replacement node is now root of tree                                  */
    /*************************************************************************/
    tree->root = replace_node;
  }

  return;

} /* mpls_avl_delete */

/**PROC+**********************************************************************/
/* Name:      mpls_avl_find                                                  */
/*                                                                           */
/* Purpose:   Find the node in the AVL tree with the supplied key            */
/*                                                                           */
/* Returns:   A pointer to the node                                          */
/*            NULL if no node is found with the specified key                */
/*                                                                           */
/* Params:    IN     tree              - a pointer to the AVL tree           */
/*            IN     key               - a pointer to the key                */
/*                                                                           */
/* Operation: Search down the tree going left if the search key is less than */
/*            the node in the tree and right if the search key is greater.   */
/*            When we run out of tree to search through either we've found   */
/*            it or the node is not in the tree.                             */
/*                                                                           */
/**PROC-**********************************************************************/
void *mpls_avl_find(MPLS_AVL_TREE *tree, void *key)
{
  /***************************************************************************/
  /* find node with specified key                                            */
  /***************************************************************************/
  MPLS_AVL_NODE *node;
  int result;

  node = tree->root;

  while (node != NULL)
  {
    /*************************************************************************/
    /* compare key of current node with supplied key                         */
    /*************************************************************************/
    result = tree->compare(key, node->key);

    if (result > 0)
    {
      /***********************************************************************/
      /* specified key is greater than key of this node, so look in right    */
      /* subtree                                                             */
      /***********************************************************************/
      node = node->right;
    }
    else if (result < 0)
    {
      /***********************************************************************/
      /* specified key is less than key of this node, so look in left        */
      /* subtree                                                             */
      /***********************************************************************/
      node = node->left;
    }
    else
    {
      /***********************************************************************/
      /* found the requested node                                            */
      /***********************************************************************/
      break;
    }
  }

  return((node != NULL) ? node->self : NULL);

} /* mpls_avl_find */

/**PROC+**********************************************************************/
/* Name:      mpls_avl_next                                                  */
/*                                                                           */
/* Purpose:   Find next node in the AVL tree                                 */
/*                                                                           */
/* Returns:   A pointer to the next node in the tree                         */
/*                                                                           */
/* Params:    IN     node              - a pointer to the current node in    */
/*                                       the tree                            */
/*                                                                           */
/* Operation: If the specified node has a right-son then return the left-    */
/*            most son of this. Otherwise search back up until we find a     */
/*            node of which we are in the left sub-tree and return that.     */
/*                                                                           */
/**PROC-**********************************************************************/
void *mpls_avl_next(MPLS_AVL_NODE *node)
{
  /***************************************************************************/
  /* find next node in tree                                                  */
  /***************************************************************************/

  MPLS_ASSERT(MPLS_AVL_IN_TREE(*node));

  if (node->right != NULL)
  {
    /*************************************************************************/
    /* next node is left-most node in right subtree                          */
    /*************************************************************************/
    node = node->right;
    while (node->left != NULL)
    {
      node = node->left;
    }
  }
  else
  {
    /*************************************************************************/
    /* no right-son, so find a node of which we are in the left subtree      */
    /*************************************************************************/
    while (node != NULL)
    {
      if ((node->parent == NULL) ||
          (node->parent->left == node))
      {
        node = node->parent;
        break;
      }
      node = node->parent;
    }
  }

  return((node != NULL) ? node->self : NULL);

} /* mpls_avl_next */

/**PROC+**********************************************************************/
/* Name:      mpls_avl_prev                                                  */
/*                                                                           */
/* Purpose:   Find previous node in the AVL tree                             */
/*                                                                           */
/* Returns:   A pointer to the previous node in the tree                     */
/*                                                                           */
/* Params:    IN     node              - a pointer to the current node in    */
/*                                       the tree                            */
/*                                                                           */
/* Operation: If we have a left-son then the previous node is the right-most */
/*            son of this. Otherwise, look for a node of whom we are in the  */
/*            left subtree and return that.                                  */
/*                                                                           */
/**PROC-**********************************************************************/
void *mpls_avl_prev(MPLS_AVL_NODE *node)
{
  /***************************************************************************/
  /* find previous node in tree                                              */
  /***************************************************************************/
  MPLS_ASSERT(MPLS_AVL_IN_TREE(*node));

  if (node->left != NULL)
  {
    /*************************************************************************/
    /* previous node is right-most node in left subtree                      */
    /*************************************************************************/
    node = node->left;
    while (node->right != NULL)
    {
      node = node->right;
    }
  }
  else
  {
    /*************************************************************************/
    /* no left-son, so find a node of which we are in the right subtree      */
    /*************************************************************************/
    while (node != NULL)
    {
      if ((node->parent == NULL) ||
          (node->parent->right == node))
      {
        node = node->parent;
        break;
      }
      node = node->parent;
    }
  }

  return((node != NULL) ? node->self : NULL);

} /* mpls_avl_prev */

/**PROC+**********************************************************************/
/* Name:      mpls_avl_balance_tree                                          */
/*                                                                           */
/* Purpose:   Reblance the tree starting at the supplied node and ending at  */
/*            the root of the tree                                           */
/*                                                                           */
/* Returns:   Nothing                                                        */
/*                                                                           */
/* Params:    IN     tree              - a pointer to the AVL tree           */
/*            IN     node              - a pointer to the node to start      */
/*                                       balancing from                      */
/*                                                                           */
/**PROC-**********************************************************************/
void mpls_avl_balance_tree(MPLS_AVL_TREE *tree, MPLS_AVL_NODE *node)
{
  /***************************************************************************/
  /* balance the tree starting at the supplied node, and ending at the root  */
  /* of the tree                                                             */
  /***************************************************************************/
  while (node->parent != NULL)
  {
    /*************************************************************************/
    /* node has uneven balance, so may need to rebalance it                  */
    /*************************************************************************/
    if (node->parent->right == node)
    {
      /***********************************************************************/
      /* node is right-son of its parent                                     */
      /***********************************************************************/
      node = node->parent;
      mpls_avl_rebalance(&node->right);

      /***********************************************************************/
      /* now update the right height of the parent                           */
      /***********************************************************************/
      node->r_height = (unsigned short)
                   (1 + MPLS_MAX(node->right->r_height, node->right->l_height));
    }
    else
    {
      /***********************************************************************/
      /* node is left-son of its parent                                      */
      /***********************************************************************/
      node = node->parent;
      mpls_avl_rebalance(&node->left);

      /***********************************************************************/
      /* now update the left height of the parent                            */
      /***********************************************************************/
      node->l_height = (unsigned short)
                     (1 + MPLS_MAX(node->left->r_height, node->left->l_height));
    }
  }

  if (node->l_height != node->r_height)
  {
    /*************************************************************************/
    /* rebalance root node                                                   */
    /*************************************************************************/
    mpls_avl_rebalance(&tree->root);
  }

  return;

} /* mpls_avl_balance_tree */

/**PROC+**********************************************************************/
/* Name:      mpls_avl_rebalance                                             */
/*                                                                           */
/* Purpose:   Reblance a subtree of the AVL tree (if necessary)              */
/*                                                                           */
/* Returns:   Nothing                                                        */
/*                                                                           */
/* Params:    IN/OUT subtree           - a pointer to the subtree to         */
/*                                       rebalance                           */
/*                                                                           */
/**PROC-**********************************************************************/
void mpls_avl_rebalance(MPLS_AVL_NODE **subtree)
{
  /***************************************************************************/
  /* Local data                                                              */
  /***************************************************************************/
  int moment;

  /***************************************************************************/
  /* rebalance a subtree of the AVL tree                                     */
  /***************************************************************************/
  /***************************************************************************/
  /* How unbalanced - don't want to recalculate                              */
  /***************************************************************************/
  moment = (*subtree)->r_height - (*subtree)->l_height;

  if (moment > 1)
  {
    /*************************************************************************/
    /* subtree is heavy on the right side                                    */
    /*************************************************************************/
    if ((*subtree)->right->l_height > (*subtree)->right->r_height)
    {
      /***********************************************************************/
      /* right subtree is heavier on left side, so must perform right        */
      /* rotation on this subtree to make it heavier on the right side       */
      /***********************************************************************/
      mpls_avl_rotate_right(&(*subtree)->right);
    }

    /*************************************************************************/
    /* now rotate the subtree left                                           */
    /*************************************************************************/
    mpls_avl_rotate_left(subtree);
  }
  else if (moment < -1)