ubi_bintree.c

samba-3.0.22.tar.gz 编译smb服务器的源码

   *
   * Input:
   *  parent   - A pointer to he parent pointer of the node to be
   *             replaced.  <parent> may point to the Link[] field of
   *             a parent node, or it may indicate the root pointer at
   *             the top of the tree.
   *  oldnode  - A pointer to the node that is to be replaced.
   *  newnode  - A pointer to the node that is to be installed in the
   *             place of <*oldnode>.
   *
   * Notes:    Don't forget to free oldnode.
   *           Also, this function used to have a really nasty typo
   *           bug.  "oldnode" and "newnode" were swapped in the line
   *           that now reads:
   *     ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
   *           Bleah!
   * ------------------------------------------------------------------------ **
   */
  {
  *newnode = *oldnode;  /* Copy node internals to new node. */

  (*parent) = newnode;  /* Old node's parent points to new child. */
  /* Now tell the children about their new step-parent. */
  if( oldnode->Link[ubi_trLEFT] )
    (oldnode->Link[ubi_trLEFT])->Link[ubi_trPARENT] = newnode;
  if( oldnode->Link[ubi_trRIGHT] )
    (oldnode->Link[ubi_trRIGHT])->Link[ubi_trPARENT] = newnode;
  } /* ReplaceNode */

static void SwapNodes( ubi_btRootPtr RootPtr,
                       ubi_btNodePtr Node1,
                       ubi_btNodePtr Node2 )
  /* ------------------------------------------------------------------------ **
   * This function swaps two nodes in the tree.  Node1 will take the place of
   * Node2, and Node2 will fill in the space left vacant by Node 1.
   *
   * Input:
   *  RootPtr  - pointer to the tree header structure for this tree.
   *  Node1    - \
   *              > These are the two nodes which are to be swapped.
   *  Node2    - /
   *
   * Notes:
   *  This function does a three step swap, using a dummy node as a place
   *  holder.  This function is used by ubi_btRemove().
   * ------------------------------------------------------------------------ **
   */
  {
  ubi_btNodePtr *Parent;
  ubi_btNode     dummy;
  ubi_btNodePtr  dummy_p = &dummy;

  /* Replace Node 1 with the dummy, thus removing Node1 from the tree. */
  if( NULL != Node1->Link[ubi_trPARENT] )
    Parent = &((Node1->Link[ubi_trPARENT])->Link[(int)(Node1->gender)]);
  else
    Parent = &(RootPtr->root);
  ReplaceNode( Parent, Node1, dummy_p );

  /* Swap Node 1 with Node 2, placing Node 1 back into the tree. */
  if( NULL != Node2->Link[ubi_trPARENT] )
    Parent = &((Node2->Link[ubi_trPARENT])->Link[(int)(Node2->gender)]);
  else
    Parent = &(RootPtr->root);
  ReplaceNode( Parent, Node2, Node1 );

  /* Swap Node 2 and the dummy, thus placing Node 2 back into the tree. */
  if( NULL != dummy_p->Link[ubi_trPARENT] )
    Parent = &((dummy_p->Link[ubi_trPARENT])->Link[(int)(dummy_p->gender)]);
  else
    Parent = &(RootPtr->root);
  ReplaceNode( Parent, dummy_p, Node2 );
  } /* SwapNodes */

/* -------------------------------------------------------------------------- **
 * These routines allow you to walk through the tree, forwards or backwards.
 */

static ubi_btNodePtr SubSlide( register ubi_btNodePtr P,
                               register int           whichway )
  /* ------------------------------------------------------------------------ **
   * Slide down the side of a subtree.
   *
   * Given a starting node, this function returns a pointer to the LEFT-, or
   * RIGHT-most descendent, *or* (if whichway is PARENT) to the tree root.
   *
   *  Input:  P         - a pointer to a starting place.
   *          whichway  - the direction (LEFT, RIGHT, or PARENT) in which to
   *                      travel.
   *  Output: A pointer to a node that is either the root, or has no
   *          whichway-th child but is within the subtree of P.  Note that
   *          the return value may be the same as P.  The return value *will
   *          be* NULL if P is NULL.
   * ------------------------------------------------------------------------ **
   */
  {

  if( NULL != P )
    while( NULL != P->Link[ whichway ] )
      P = P->Link[ whichway ];
  return( P );
  } /* SubSlide */

static ubi_btNodePtr Neighbor( register ubi_btNodePtr P,
                               register int           whichway )
  /* ------------------------------------------------------------------------ **
   * Given starting point p, return the (key order) next or preceeding node
   * in the tree.
   *
   *  Input:  P         - Pointer to our starting place node.
   *          whichway  - the direction in which to travel to find the
   *                      neighbor, i.e., the RIGHT neighbor or the LEFT
   *                      neighbor.
   *
   *  Output: A pointer to the neighboring node, or NULL if P was NULL.
   *
   *  Notes:  If whichway is PARENT, the results are unpredictable.
   * ------------------------------------------------------------------------ **
   */
  {
  if( P )
    {
    if( NULL != P->Link[ whichway ] )
      return( SubSlide( P->Link[ whichway ], (char)ubi_trRevWay(whichway) ) );
    else
      while( NULL != P->Link[ ubi_trPARENT ] )
        {
        if( whichway == P->gender )
          P = P->Link[ ubi_trPARENT ];
        else
          return( P->Link[ ubi_trPARENT ] );
        }
    }
  return( NULL );
  } /* Neighbor */

static ubi_btNodePtr Border( ubi_btRootPtr RootPtr,
                             ubi_btItemPtr FindMe,
                             ubi_btNodePtr p,
                             int           whichway )
  /* ------------------------------------------------------------------------ **
   * Given starting point p, which has a key value equal to *FindMe, locate
   * the first (index order) node with the same key value.
   *
   * This function is useful in trees that have can have duplicate keys.
   * For example, consider the following tree:
   *     Tree                                                      Traversal
   *       2    If <p> points to the root and <whichway> is RIGHT,     3
   *      / \    then the return value will be a pointer to the       / \
   *     2   2    RIGHT child of the root node.  The tree on         2   5
   *    /   / \    the right shows the order of traversal.          /   / \
   *   1   2   3                                                   1   4   6
   *
   *  Input:  RootPtr   - Pointer to the tree root structure.
   *          FindMe    - Key value for comparisons.
   *          p         - Pointer to the starting-point node.
   *          whichway  - the direction in which to travel to find the
   *                      neighbor, i.e., the RIGHT neighbor or the LEFT
   *                      neighbor.
   *
   *  Output: A pointer to the first (index, or "traversal", order) node with
   *          a Key value that matches *FindMe.
   *
   *  Notes:  If whichway is PARENT, or if the tree does not allow duplicate
   *          keys, this function will return <p>.
   * ------------------------------------------------------------------------ **
   */
  {
  register ubi_btNodePtr q;

  /* Exit if there's nothing that can be done. */
  if( !ubi_trDups_OK( RootPtr ) || (ubi_trPARENT == whichway) )
    return( p );

  /* First, if needed, move up the tree.  We need to get to the root of the
   * subtree that contains all of the matching nodes.
   */
  q = p->Link[ubi_trPARENT];
  while( (NULL != q)
      && (ubi_trEQUAL == ubi_trAbNormal( (*(RootPtr->cmp))(FindMe, q) )) )
    {
    p = q;
    q = p->Link[ubi_trPARENT];
    }

  /* Next, move back down in the "whichway" direction. */
  q = p->Link[whichway];
  while( NULL != q )
    {
    q = qFind( RootPtr->cmp, FindMe, q );
    if( q )
      {
      p = q;
      q = p->Link[whichway];
      }
    }
  return( p );
  } /* Border */


/* ========================================================================== **
 * Exported utilities.
 */

long ubi_btSgn( register long x )
  /* ------------------------------------------------------------------------ **
   * Return the sign of x; {negative,zero,positive} ==> {-1, 0, 1}.
   *
   *  Input:  x - a signed long integer value.
   *
   *  Output: the "sign" of x, represented as follows:
   *            -1 == negative
   *             0 == zero (no sign)
   *             1 == positive
   *
   * Note: This utility is provided in order to facilitate the conversion
   *       of C comparison function return values into BinTree direction
   *       values: {LEFT, PARENT, EQUAL}.  It is INCORPORATED into the
   *       ubi_trAbNormal() conversion macro!
   *
   * ------------------------------------------------------------------------ **
   */
  {
  return( (x)?((x>0)?(1):(-1)):(0) );
  } /* ubi_btSgn */

ubi_btNodePtr ubi_btInitNode( ubi_btNodePtr NodePtr )
  /* ------------------------------------------------------------------------ **
   * Initialize a tree node.
   *
   *  Input:  a pointer to a ubi_btNode structure to be initialized.
   *  Output: a pointer to the initialized ubi_btNode structure (ie. the
   *          same as the input pointer).
   * ------------------------------------------------------------------------ **
   */
  {
  NodePtr->Link[ ubi_trLEFT ]   = NULL;
  NodePtr->Link[ ubi_trPARENT ] = NULL;
  NodePtr->Link[ ubi_trRIGHT ]  = NULL;
  NodePtr->gender               = ubi_trEQUAL;
  NodePtr->balance              = ubi_trEQUAL;
  return( NodePtr );
  } /* ubi_btInitNode */

ubi_btRootPtr ubi_btInitTree( ubi_btRootPtr   RootPtr,
                              ubi_btCompFunc  CompFunc,
                              char            Flags )
  /* ------------------------------------------------------------------------ **
   * Initialize the fields of a Tree Root header structure.
   *
   *  Input:   RootPtr   - a pointer to an ubi_btRoot structure to be
   *                       initialized.
   *           CompFunc  - a pointer to a comparison function that will be used
   *                       whenever nodes in the tree must be compared against
   *                       outside values.
   *           Flags     - One bytes worth of flags.  Flags include
   *                       ubi_trOVERWRITE and ubi_trDUPKEY.  See the header
   *                       file for more info.
   *
   *  Output:  a pointer to the initialized ubi_btRoot structure (ie. the
   *           same value as RootPtr).
   *
   *  Note:    The interface to this function has changed from that of
   *           previous versions.  The <Flags> parameter replaces two
   *           boolean parameters that had the same basic effect.
   *
   * ------------------------------------------------------------------------ **
   */
  {
  if( RootPtr )
    {
    RootPtr->root   = NULL;
    RootPtr->count  = 0L;
    RootPtr->cmp    = CompFunc;
    RootPtr->flags  = (Flags & ubi_trDUPKEY) ? ubi_trDUPKEY : Flags;
    }                 /* There are only two supported flags, and they are
                       * mutually exclusive.  ubi_trDUPKEY takes precedence
                       * over ubi_trOVERWRITE.
                       */
  return( RootPtr );
  } /* ubi_btInitTree */

ubi_trBool ubi_btInsert( ubi_btRootPtr  RootPtr,
                         ubi_btNodePtr  NewNode,
                         ubi_btItemPtr  ItemPtr,
                         ubi_btNodePtr *OldNode )
  /* ------------------------------------------------------------------------ **
   * This function uses a non-recursive algorithm to add a new element to the
   * tree.
   *
   *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
   *                       the root of the tree to which NewNode is to be added.
   *           NewNode  -  a pointer to an ubi_btNode structure that is NOT
   *                       part of any tree.