mpls_avl.c

路由器协议平台mpls协议的设计与实现源代码。

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

    /*************************************************************************/
    /* now rotate the subtree right                                          */
    /*************************************************************************/
    mpls_avl_rotate_right(subtree);
  }

  return;

} /* avl_rebalance */

/**PROC+**********************************************************************/
/* Name:      mpls_avl_rotate_right                                          */
/*                                                                           */
/* Purpose:   Rotate a subtree of the AVL tree right                         */
/*                                                                           */
/* Returns:   Nothing                                                        */
/*                                                                           */
/* Params:    IN/OUT subtree           - a pointer to the subtree to rotate  */
/*                                                                           */
/**PROC-**********************************************************************/
void mpls_avl_rotate_right(MPLS_AVL_NODE **subtree)
{
  /***************************************************************************/
  /* rotate subtree of AVL tree right                                        */
  /***************************************************************************/
  MPLS_AVL_NODE *left_son;

  left_son = (*subtree)->left;

  (*subtree)->left = left_son->right;
  if ((*subtree)->left != NULL)
  {
    (*subtree)->left->parent = (*subtree);
  }
  (*subtree)->l_height = left_son->r_height;

  left_son->parent = (*subtree)->parent;

  left_son->right = *subtree;
  left_son->right->parent = left_son;
  left_son->r_height = (unsigned short)
                     (1 + MPLS_MAX((*subtree)->r_height, (*subtree)->l_height));

  *subtree = left_son;

  return;

} /* mpls_avl_rotate_right */

/**PROC+**********************************************************************/
/* Name:      mpls_avl_rotate_left                                           */
/*                                                                           */
/* Purpose:   Rotate a subtree of the AVL tree left                          */
/*                                                                           */
/* Returns:   Nothing                                                        */
/*                                                                           */
/* Params:    IN/OUT subtree           - a pointer to the subtree to rotate  */
/*                                                                           */
/**PROC-**********************************************************************/
void mpls_avl_rotate_left(MPLS_AVL_NODE **subtree)
{
  /***************************************************************************/
  /* rotate a subtree of the AVL tree left                                   */
  /***************************************************************************/
  MPLS_AVL_NODE *right_son;

  right_son = (*subtree)->right;

  (*subtree)->right = right_son->left;
  if ((*subtree)->right != NULL)
  {
    (*subtree)->right->parent = (*subtree);
  }
  (*subtree)->r_height = right_son->l_height;

  right_son->parent = (*subtree)->parent;

  right_son->left = *subtree;
  right_son->left->parent = right_son;
  right_son->l_height = (unsigned short)
                     (1 + MPLS_MAX((*subtree)->r_height, (*subtree)->l_height));

  *subtree = right_son;

  return;

} /* mpls_avl_rotate_left */

/**PROC+**********************************************************************/
/* Name:      mpls_avl_swap_right_most                                       */
/*                                                                           */
/* Purpose:   Swap node with right-most descendent of subtree                */
/*                                                                           */
/* Returns:   Nothing                                                        */
/*                                                                           */
/* Params:    IN     tree              - a pointer to the tree               */
/*            IN     subtree           - a pointer to the subtree            */
/*            IN     node              - a pointer to the node to swap       */
/*                                                                           */
/**PROC-**********************************************************************/
void mpls_avl_swap_right_most(MPLS_AVL_TREE *tree, MPLS_AVL_NODE *subtree, MPLS_AVL_NODE *node)
{
  /***************************************************************************/
  /* swap node with right-most descendent of specified subtree               */
  /***************************************************************************/
  MPLS_AVL_NODE *swap_node;
  MPLS_AVL_NODE *swap_parent;
  MPLS_AVL_NODE *swap_left;

  MPLS_ASSERT(node->right != NULL);
  MPLS_ASSERT(node->left != NULL);

  /***************************************************************************/
  /* find right-most descendent of subtree                                   */
  /***************************************************************************/
  swap_node = subtree;
  while (swap_node->right != NULL)
  {
    swap_node = swap_node->right;
  }

  MPLS_ASSERT(swap_node->r_height == 0);
  MPLS_ASSERT(swap_node->l_height <= 1);

  /***************************************************************************/
  /* save parent and left-son of right-most descendent                       */
  /***************************************************************************/
  swap_parent = swap_node->parent;
  swap_left = swap_node->left;

  /***************************************************************************/
  /* move swap node to its new position                                      */
  /***************************************************************************/
  swap_node->parent = node->parent;
  swap_node->right = node->right;
  swap_node->left = node->left;
  swap_node->r_height = node->r_height;
  swap_node->l_height = node->l_height;
  swap_node->right->parent = swap_node;
  swap_node->left->parent = swap_node;
  if (node->parent == NULL)
  {
    /*************************************************************************/
    /* node is at root of tree                                               */
    /*************************************************************************/
    tree->root = swap_node;
  }
  else if (node->parent->right == node)
  {
    /*************************************************************************/
    /* node is right-son of parent                                           */
    /*************************************************************************/
    swap_node->parent->right = swap_node;
  }
  else
  {
    /*************************************************************************/
    /* node is left-son of parent                                            */
    /*************************************************************************/
    swap_node->parent->left = swap_node;
  }

  /***************************************************************************/
  /* move node to its new position                                           */
  /***************************************************************************/
  node->parent = swap_parent;
  node->right = NULL;
  node->left = swap_left;
  if (node->left != NULL)
  {
    node->left->parent = node;
    node->l_height = 1;
  }
  else
  {
    node->l_height = 0;
  }
  node->r_height = 0;
  node->parent->right = node;

  return;

} /* mpls_avl_swap_right_most */

/**PROC+**********************************************************************/
/* Name:      mpls_avl_swap_left_most                                        */
/*                                                                           */
/* Purpose:   Swap node with left-most descendent of subtree                 */
/*                                                                           */
/* Returns:   Nothing                                                        */
/*                                                                           */
/* Params:    IN     tree              - a pointer to the tree               */
/*            IN     subtree           - a pointer to the subtree            */
/*            IN     node              - a pointer to the node to swap       */
/*                                                                           */
/**PROC-**********************************************************************/
void mpls_avl_swap_left_most(MPLS_AVL_TREE *tree, MPLS_AVL_NODE *subtree, MPLS_AVL_NODE *node)
{
  /***************************************************************************/
  /* swap node with left-most descendent of specified subtree                */
  /***************************************************************************/
  MPLS_AVL_NODE *swap_node;
  MPLS_AVL_NODE *swap_parent;
  MPLS_AVL_NODE *swap_right;

  MPLS_ASSERT(node->right != NULL);
  MPLS_ASSERT(node->left != NULL);

  /***************************************************************************/
  /* find left-most descendent of subtree                                    */
  /***************************************************************************/
  swap_node = subtree;
  while (swap_node->left != NULL)
  {
    swap_node = swap_node->left;
  }

  MPLS_ASSERT(swap_node->l_height == 0);
  MPLS_ASSERT(swap_node->r_height <= 1);

  /***************************************************************************/
  /* save parent and right-son of left-most descendent                       */
  /***************************************************************************/
  swap_parent = swap_node->parent;
  swap_right = swap_node->right;

  /***************************************************************************/
  /* move swap node to its new position                                      */
  /***************************************************************************/
  swap_node->parent = node->parent;
  swap_node->right = node->right;
  swap_node->left = node->left;
  swap_node->r_height = node->r_height;
  swap_node->l_height = node->l_height;
  swap_node->right->parent = swap_node;
  swap_node->left->parent = swap_node;
  if (node->parent == NULL)
  {
    /*************************************************************************/
    /* node is at root of tree                                               */
    /*************************************************************************/
    tree->root = swap_node;
  }
  else if (node->parent->right == node)
  {
    /*************************************************************************/
    /* node is right-son of parent                                           */
    /*************************************************************************/
    swap_node->parent->right = swap_node;
  }
  else
  {
    /*************************************************************************/
    /* node is left-son of parent                                            */
    /*************************************************************************/
    swap_node->parent->left = swap_node;
  }

  /***************************************************************************/
  /* move node to its new position                                           */
  /***************************************************************************/
  node->parent = swap_parent;
  node->right = swap_right;
  node->left = NULL;
  if (node->right != NULL)
  {
    node->right->parent = node;
    node->r_height = 1;
  }
  else
  {
    node->r_height = 0;
  }
  node->l_height = 0;
  node->parent->left = node;

  return;

} /* mpls_avl_swap_left_most */

/**PROC+**********************************************************************/
/* Name:      mpls_avl_find_or_find_next                                     */
/*                                                                           */
/* Purpose:   Find the successor node to the supplied key in the AVL tree    */
/*                                                                           */
/* Returns:   A pointer to the node                                          */
/*            NULL if no successor node to the supplied key is found         */
/*                                                                           */
/* Params:    IN     tree         - a pointer to the AVL tree                */
/*            IN     key          - a pointer to the key                     */
/*            IN     not_equal    - TRUE return a node strictly > key        */
/*                                  FALSE return a node >= key               */
/*                                                                           */
/**PROC-**********************************************************************/

void *mpls_avl_find_or_find_next(MPLS_AVL_TREE *tree, void *key, unsigned char not_equal)
{
  /***************************************************************************/
  /* Local Variables                                                         */
  /***************************************************************************/
  MPLS_AVL_NODE *node;
  void *found_node = NULL;
  int result;

  node = tree->root;

  if (node != NULL)
  {
    /*************************************************************************/
    /* There is something in the tree                                        */
    /*************************************************************************/
    for(;;)
    {
      /***********************************************************************/