ubi_bintree.c

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

   *           ItemPtr  -  A pointer to the sort key that is stored within
   *                       *NewNode.  ItemPtr MUST point to information stored
   *                       in *NewNode or an EXACT DUPLICATE.  The key data
   *                       indicated by ItemPtr is used to place the new node
   *                       into the tree.
   *           OldNode  -  a pointer to an ubi_btNodePtr.  When searching
   *                       the tree, a duplicate node may be found.  If
   *                       duplicates are allowed, then the new node will
   *                       be simply placed into the tree.  If duplicates
   *                       are not allowed, however, then one of two things
   *                       may happen.
   *                       1) if overwritting *is not* allowed, this
   *                          function will return FALSE (indicating that
   *                          the new node could not be inserted), and
   *                          *OldNode will point to the duplicate that is
   *                          still in the tree.
   *                       2) if overwritting *is* allowed, then this
   *                          function will swap **OldNode for *NewNode.
   *                          In this case, *OldNode will point to the node
   *                          that was removed (thus allowing you to free
   *                          the node).
   *                          **  If you are using overwrite mode, ALWAYS  **
   *                          ** check the return value of this parameter! **
   *                 Note: You may pass NULL in this parameter, the
   *                       function knows how to cope.  If you do this,
   *                       however, there will be no way to return a
   *                       pointer to an old (ie. replaced) node (which is
   *                       a problem if you are using overwrite mode).
   *
   *  Output:  a boolean value indicating success or failure.  The function
   *           will return FALSE if the node could not be added to the tree.
   *           Such failure will only occur if duplicates are not allowed,
   *           nodes cannot be overwritten, AND a duplicate key was found
   *           within the tree.
   * ------------------------------------------------------------------------ **
   */
  {
  ubi_btNodePtr OtherP,
                parent = NULL;
  char          tmp;

  if( NULL == OldNode ) /* If they didn't give us a pointer, supply our own.  */
    OldNode = &OtherP;

  (void)ubi_btInitNode( NewNode );     /* Init the new node's BinTree fields. */

  /* Find a place for the new node. */
  *OldNode = TreeFind(ItemPtr, (RootPtr->root), &parent, &tmp, (RootPtr->cmp));

  /* Now add the node to the tree... */
  if( NULL == (*OldNode) )  /* The easy one: we have a space for a new node!  */
    {
    if( NULL == parent )
      RootPtr->root = NewNode;
    else
      {
      parent->Link[(int)tmp]      = NewNode;
      NewNode->Link[ubi_trPARENT] = parent;
      NewNode->gender             = tmp;
      }
    (RootPtr->count)++;
    return( ubi_trTRUE );
    }

  /* If we reach this point, we know that a duplicate node exists.  This
   * section adds the node to the tree if duplicate keys are allowed.
   */
  if( ubi_trDups_OK(RootPtr) )    /* Key exists, add duplicate */
    {
    ubi_btNodePtr q;

    tmp = ubi_trRIGHT;
    q = (*OldNode);
    *OldNode = NULL;
    while( NULL != q )
      {
      parent = q;
      if( tmp == ubi_trEQUAL )
        tmp = ubi_trRIGHT;
      q = q->Link[(int)tmp];
      if ( q )
        tmp = ubi_trAbNormal( (*(RootPtr->cmp))(ItemPtr, q) );
      }
    parent->Link[(int)tmp]       = NewNode;
    NewNode->Link[ubi_trPARENT]  = parent;
    NewNode->gender              = tmp;
    (RootPtr->count)++;
    return( ubi_trTRUE );
    }

  /* If we get to *this* point, we know that we are not allowed to have
   * duplicate nodes, but our node keys match, so... may we replace the
   * old one?
   */
  if( ubi_trOvwt_OK(RootPtr) )    /* Key exists, we replace */
    {
    if( NULL == parent )
      ReplaceNode( &(RootPtr->root), *OldNode, NewNode );
    else
      ReplaceNode( &(parent->Link[(int)((*OldNode)->gender)]),
                   *OldNode, NewNode );
    return( ubi_trTRUE );
    }

  return( ubi_trFALSE );      /* Failure: could not replace an existing node. */
  } /* ubi_btInsert */

ubi_btNodePtr ubi_btRemove( ubi_btRootPtr RootPtr,
                            ubi_btNodePtr DeadNode )
  /* ------------------------------------------------------------------------ **
   * This function removes the indicated node from the tree.
   *
   *  Input:   RootPtr  -  A pointer to the header of the tree that contains
   *                       the node to be removed.
   *           DeadNode -  A pointer to the node that will be removed.
   *
   *  Output:  This function returns a pointer to the node that was removed
   *           from the tree (ie. the same as DeadNode).
   *
   *  Note:    The node MUST be in the tree indicated by RootPtr.  If not,
   *           strange and evil things will happen to your trees.
   * ------------------------------------------------------------------------ **
   */
  {
  ubi_btNodePtr p,
               *parentp;
  int           tmp;

  /* if the node has both left and right subtrees, then we have to swap
   * it with another node.  The other node we choose will be the Prev()ious
   * node, which is garunteed to have no RIGHT child.
   */
  if( (NULL != DeadNode->Link[ubi_trLEFT])
   && (NULL != DeadNode->Link[ubi_trRIGHT]) )
    SwapNodes( RootPtr, DeadNode, ubi_btPrev( DeadNode ) );

  /* The parent of the node to be deleted may be another node, or it may be
   * the root of the tree.  Since we're not sure, it's best just to have
   * a pointer to the parent pointer, whatever it is.
   */
  if( NULL == DeadNode->Link[ubi_trPARENT] )
    parentp = &( RootPtr->root );
  else
    parentp = &((DeadNode->Link[ubi_trPARENT])->Link[(int)(DeadNode->gender)]);

  /* Now link the parent to the only grand-child and patch up the gender. */
  tmp = ((DeadNode->Link[ubi_trLEFT])?ubi_trLEFT:ubi_trRIGHT);

  p = (DeadNode->Link[tmp]);
  if( NULL != p )
    {
    p->Link[ubi_trPARENT] = DeadNode->Link[ubi_trPARENT];
    p->gender       = DeadNode->gender;
    }
  (*parentp) = p;

  /* Finished, reduce the node count and return. */
  (RootPtr->count)--;
  return( DeadNode );
  } /* ubi_btRemove */

ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr,
                            ubi_btItemPtr FindMe,
                            ubi_trCompOps CompOp )
  /* ------------------------------------------------------------------------ **
   * The purpose of ubi_btLocate() is to find a node or set of nodes given
   * a target value and a "comparison operator".  The Locate() function is
   * more flexible and (in the case of trees that may contain dupicate keys)
   * more precise than the ubi_btFind() function.  The latter is faster,
   * but it only searches for exact matches and, if the tree contains
   * duplicates, Find() may return a pointer to any one of the duplicate-
   * keyed records.
   *
   *  Input:
   *     RootPtr  -  A pointer to the header of the tree to be searched.
   *     FindMe   -  An ubi_btItemPtr that indicates the key for which to
   *                 search.
   *     CompOp   -  One of the following:
   *                    CompOp     Return a pointer to the node with
   *                    ------     ---------------------------------
   *                   ubi_trLT - the last key value that is less
   *                              than FindMe.
   *                   ubi_trLE - the first key matching FindMe, or
   *                              the last key that is less than
   *                              FindMe.
   *                   ubi_trEQ - the first key matching FindMe.
   *                   ubi_trGE - the first key matching FindMe, or the
   *                              first key greater than FindMe.
   *                   ubi_trGT - the first key greater than FindMe.
   *  Output:
   *     A pointer to the node matching the criteria listed above under
   *     CompOp, or NULL if no node matched the criteria.
   *
   *  Notes:
   *     In the case of trees with duplicate keys, Locate() will behave as
   *     follows:
   *
   *     Find:  3                       Find: 3
   *     Keys:  1 2 2 2 3 3 3 3 3 4 4   Keys: 1 1 2 2 2 4 4 5 5 5 6
   *                  ^ ^         ^                   ^ ^
   *                 LT EQ        GT                 LE GE
   *
   *     That is, when returning a pointer to a node with a key that is LESS
   *     THAN the target key (FindMe), Locate() will return a pointer to the
   *     LAST matching node.
   *     When returning a pointer to a node with a key that is GREATER
   *     THAN the target key (FindMe), Locate() will return a pointer to the
   *     FIRST matching node.
   *
   *  See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf().
   * ------------------------------------------------------------------------ **
   */
  {
  register ubi_btNodePtr p;
  ubi_btNodePtr   parent;
  char            whichkid;

  /* Start by searching for a matching node. */
  p = TreeFind( FindMe,
                RootPtr->root,
                &parent,
                &whichkid,
                RootPtr->cmp );

  if( NULL != p )    /* If we have found a match, we can resolve as follows:  */
    {
    switch( CompOp )
      {
      case ubi_trLT:            /* It's just a jump to the left...  */
        p = Border( RootPtr, FindMe, p, ubi_trLEFT );
        return( Neighbor( p, ubi_trLEFT ) );
      case ubi_trGT:            /* ...and then a jump to the right. */
        p = Border( RootPtr, FindMe, p, ubi_trRIGHT );
        return( Neighbor( p, ubi_trRIGHT ) );
      default:
        p = Border( RootPtr, FindMe, p, ubi_trLEFT );
        return( p );
      }
    }

  /* Else, no match. */
  if( ubi_trEQ == CompOp )    /* If we were looking for an exact match... */
    return( NULL );           /* ...forget it.                            */

  /* We can still return a valid result for GT, GE, LE, and LT.
   * <parent> points to a node with a value that is either just before or
   * just after the target value.
   * Remaining possibilities are LT and GT (including LE & GE).
   */
  if( (ubi_trLT == CompOp) || (ubi_trLE == CompOp) )
    return( (ubi_trLEFT == whichkid) ? Neighbor( parent, whichkid ) : parent );
  else
    return( (ubi_trRIGHT == whichkid) ? Neighbor( parent, whichkid ) : parent );
  } /* ubi_btLocate */

ubi_btNodePtr ubi_btFind( ubi_btRootPtr RootPtr,
                          ubi_btItemPtr FindMe )
  /* ------------------------------------------------------------------------ **
   * This function performs a non-recursive search of a tree for any node
   * matching a specific key.
   *
   *  Input:
   *     RootPtr  -  a pointer to the header of the tree to be searched.
   *     FindMe   -  a pointer to the key value for which to search.
   *
   *  Output:
   *     A pointer to a node with a key that matches the key indicated by
   *     FindMe, or NULL if no such node was found.
   *
   *  Note:   In a tree that allows duplicates, the pointer returned *might
   *          not* point to the (sequentially) first occurance of the
   *          desired key.  In such a tree, it may be more useful to use
   *          ubi_btLocate().
   * ------------------------------------------------------------------------ **
   */
  {
  return( qFind( RootPtr->cmp, FindMe, RootPtr->root ) );
  } /* ubi_btFind */

ubi_btNodePtr ubi_btNext( ubi_btNodePtr P )
  /* ------------------------------------------------------------------------ **
   * Given the node indicated by P, find the (sorted order) Next node in the
   * tree.
   *  Input:   P  -  a pointer to a node that exists in a binary tree.
   *  Output:  A pointer to the "next" node in the tree, or NULL if P pointed
   *           to the "last" node in the tree or was NULL.
   * ------------------------------------------------------------------------ **
   */
  {
  return( Neighbor( P, ubi_trRIGHT ) );
  } /* ubi_btNext */

ubi_btNodePtr ubi_btPrev( ubi_btNodePtr P )
  /* ------------------------------------------------------------------------ **