ubi_bintree.c

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

   * Given the node indicated by P, find the (sorted order) Previous node in
   * the tree.
   *  Input:   P  -  a pointer to a node that exists in a binary tree.
   *  Output:  A pointer to the "previous" node in the tree, or NULL if P
   *           pointed to the "first" node in the tree or was NULL.
   * ------------------------------------------------------------------------ **
   */
  {
  return( Neighbor( P, ubi_trLEFT ) );
  } /* ubi_btPrev */

ubi_btNodePtr ubi_btFirst( ubi_btNodePtr P )
  /* ------------------------------------------------------------------------ **
   * Given the node indicated by P, find the (sorted order) First node in the
   * subtree of which *P is the root.
   *  Input:   P  -  a pointer to a node that exists in a binary tree.
   *  Output:  A pointer to the "first" node in a subtree that has *P as its
   *           root.  This function will return NULL only if P is NULL.
   *  Note:    In general, you will be passing in the value of the root field
   *           of an ubi_btRoot structure.
   * ------------------------------------------------------------------------ **
   */
  {
  return( SubSlide( P, ubi_trLEFT ) );
  } /* ubi_btFirst */

ubi_btNodePtr ubi_btLast( ubi_btNodePtr P )
  /* ------------------------------------------------------------------------ **
   * Given the node indicated by P, find the (sorted order) Last node in the
   * subtree of which *P is the root.
   *  Input:   P  -  a pointer to a node that exists in a binary tree.
   *  Output:  A pointer to the "last" node in a subtree that has *P as its
   *           root.  This function will return NULL only if P is NULL.
   *  Note:    In general, you will be passing in the value of the root field
   *           of an ubi_btRoot structure.
   * ------------------------------------------------------------------------ **
   */
  {
  return( SubSlide( P, ubi_trRIGHT ) );
  } /* ubi_btLast */

ubi_btNodePtr ubi_btFirstOf( ubi_btRootPtr RootPtr,
                             ubi_btItemPtr MatchMe,
                             ubi_btNodePtr p )
  /* ------------------------------------------------------------------------ **
   * Given a tree that a allows duplicate keys, and a pointer to a node in
   * the tree, this function will return a pointer to the first (traversal
   * order) node with the same key value.
   *
   *  Input:  RootPtr - A pointer to the root of the tree.
   *          MatchMe - A pointer to the key value.  This should probably
   *                    point to the key within node *p.
   *          p       - A pointer to a node in the tree.
   *  Output: A pointer to the first node in the set of nodes with keys
   *          matching <FindMe>.
   *  Notes:  Node *p MUST be in the set of nodes with keys matching
   *          <FindMe>.  If not, this function will return NULL.
   *
   *          4.7: Bug found & fixed by Massimo Campostrini,
   *               Istituto Nazionale di Fisica Nucleare, Sezione di Pisa.
   *
   * ------------------------------------------------------------------------ **
   */
  {
  /* If our starting point is invalid, return NULL. */
  if( (NULL == p)
   || (ubi_trEQUAL != ubi_trAbNormal( (*(RootPtr->cmp))( MatchMe, p ) )) )
    return( NULL );
  return( Border( RootPtr, MatchMe, p, ubi_trLEFT ) );
  } /* ubi_btFirstOf */

ubi_btNodePtr ubi_btLastOf( ubi_btRootPtr RootPtr,
                            ubi_btItemPtr MatchMe,
                            ubi_btNodePtr p )
  /* ------------------------------------------------------------------------ **
   * Given a tree that a allows duplicate keys, and a pointer to a node in
   * the tree, this function will return a pointer to the last (traversal
   * order) node with the same key value.
   *
   *  Input:  RootPtr - A pointer to the root of the tree.
   *          MatchMe - A pointer to the key value.  This should probably
   *                    point to the key within node *p.
   *          p       - A pointer to a node in the tree.
   *  Output: A pointer to the last node in the set of nodes with keys
   *          matching <FindMe>.
   *  Notes:  Node *p MUST be in the set of nodes with keys matching
   *          <FindMe>.  If not, this function will return NULL.
   *
   *          4.7: Bug found & fixed by Massimo Campostrini,
   *               Istituto Nazionale di Fisica Nucleare, Sezione di Pisa.
   *
   * ------------------------------------------------------------------------ **
   */
  {
  /* If our starting point is invalid, return NULL. */
  if( (NULL != p)
   || (ubi_trEQUAL != ubi_trAbNormal( (*(RootPtr->cmp))( MatchMe, p ) )) )
    return( NULL );
  return( Border( RootPtr, MatchMe, p, ubi_trRIGHT ) );
  } /* ubi_btLastOf */

unsigned long ubi_btTraverse( ubi_btRootPtr   RootPtr,
                              ubi_btActionRtn EachNode,
                              void           *UserData )
  /* ------------------------------------------------------------------------ **
   * Traverse a tree in sorted order (non-recursively).  At each node, call
   * (*EachNode)(), passing a pointer to the current node, and UserData as the
   * second parameter.
   *
   *  Input:   RootPtr  -  a pointer to an ubi_btRoot structure that indicates
   *                       the tree to be traversed.
   *           EachNode -  a pointer to a function to be called at each node
   *                       as the node is visited.
   *           UserData -  a generic pointer that may point to anything that
   *                       you choose.
   *
   *  Output:  A count of the number of nodes visited.  This will be zero
   *           if the tree is empty.
   *
   * ------------------------------------------------------------------------ **
   */
  {
  ubi_btNodePtr p = ubi_btFirst( RootPtr->root );
  unsigned long count = 0;

  while( NULL != p )
    {
    (*EachNode)( p, UserData );
    count++;
    p = ubi_btNext( p );
    }
  return( count );
  } /* ubi_btTraverse */

unsigned long ubi_btKillTree( ubi_btRootPtr     RootPtr,
                              ubi_btKillNodeRtn FreeNode )
  /* ------------------------------------------------------------------------ **
   * Delete an entire tree (non-recursively) and reinitialize the ubi_btRoot
   * structure.  Return a count of the number of nodes deleted.
   *
   *  Input:   RootPtr  -  a pointer to an ubi_btRoot structure that indicates
   *                       the root of the tree to delete.
   *           FreeNode -  a function that will be called for each node in the
   *                       tree to deallocate the memory used by the node.
   *
   *  Output:  The number of nodes removed from the tree.
   *           A value of 0 will be returned if:
   *           - The tree actually contains 0 entries.
   *           - the value of <RootPtr> is NULL, in which case the tree is
   *             assumed to be empty
   *           - the value of <FreeNode> is NULL, in which case entries
   *             cannot be removed, so 0 is returned.  *Make sure that you
   *             provide a valid value for <FreeNode>*.
   *           In all other cases, you should get a positive value equal to
   *           the value of RootPtr->count upon entry.
   *
   * ------------------------------------------------------------------------ **
   */
  {
  ubi_btNodePtr p, q;
  unsigned long count = 0;

  if( (NULL == RootPtr) || (NULL == FreeNode) )
    return( 0 );

  p = ubi_btFirst( RootPtr->root );
  while( NULL != p )
    {
    q = p;
    while( q->Link[ubi_trRIGHT] )
      q = SubSlide( q->Link[ubi_trRIGHT], ubi_trLEFT );
    p = q->Link[ubi_trPARENT];
    if( NULL != p )
      p->Link[ ((p->Link[ubi_trLEFT] == q)?ubi_trLEFT:ubi_trRIGHT) ] = NULL;
    (*FreeNode)((void *)q);
    count++;
    }

  /* overkill... */
  (void)ubi_btInitTree( RootPtr,
                        RootPtr->cmp,
                        RootPtr->flags );
  return( count );
  } /* ubi_btKillTree */

ubi_btNodePtr ubi_btLeafNode( ubi_btNodePtr leader )
  /* ------------------------------------------------------------------------ **
   * Returns a pointer to a leaf node.
   *
   *  Input:  leader  - Pointer to a node at which to start the descent.
   *
   *  Output: A pointer to a leaf node, selected in a somewhat arbitrary
   *          manner but with an effort to dig deep.
   *
   *  Notes:  I wrote this function because I was using splay trees as a
   *          database cache.  The cache had a maximum size on it, and I
   *          needed a way of choosing a node to sacrifice if the cache
   *          became full.  In a splay tree, less recently accessed nodes
   *          tend toward the bottom of the tree, meaning that leaf nodes
   *          are good candidates for removal.  (I really can't think of
   *          any other reason to use this function.)
   *        + In a simple binary tree, or in an AVL tree, the most recently
   *          added nodes tend to be nearer the bottom, making this a *bad*
   *          way to choose which node to remove from the cache.
   *        + Randomizing the traversal order is probably a good idea.  You
   *          can improve the randomization of leaf node selection by passing
   *          in pointers to nodes other than the root node each time.  A
   *          pointer to any node in the tree will do.  Of course, if you
   *          pass a pointer to a leaf node you'll get the same thing back.
   *        + In an unbalanced splay tree, if you simply traverse downward
   *          until you hit a leaf node it is possible to accidentally
   *          stumble onto a short path.  The result will be a leaf node
   *          that is actually very high in the tree--possibly a very
   *          recently accessed node.  Not good.  This function can follow
   *          multiple paths in an effort to find a leaf node deeper
   *          in the tree.  Following a single path, of course, is the
   *          fastest way to find a leaf node.  A complete traversal would
   *          be sure to find the deepest leaf but would be very costly in
   *          terms of time.  This function uses a compromise that has
   *          worked well in testing.
   *
   * ------------------------------------------------------------------------ **
   */
  {
  #define MAXPATHS 4  /* Set higher for more maximum paths, lower for fewer.  */
  ubi_trNodePtr p[MAXPATHS];
  ubi_trNodePtr q[MAXPATHS];
  int           whichway = ubi_trLEFT;
  int           paths;
  int           i, j;

  /* If the subtree is empty, return NULL.
   */
  if( NULL == leader )
    return( NULL );

  /* Initialize the p[] array with a pointer to the single node we've been
   * given as a starting point.
   */
  p[0]  = leader;
  paths = 1;
  while( paths > 0 )
    {
    for( i = 0; i < paths; i++ )
      q[i] = p[i];

    for( i = j = 0; (i < paths) && (j < MAXPATHS); i++ )
      {
      if( NULL != q[i]->Link[whichway] )
        p[j++] = q[i]->Link[whichway];
      whichway = ubi_trRevWay( whichway );
      if( (j < MAXPATHS) && (NULL != q[i]->Link[whichway]) )
        p[j++] = q[i]->Link[whichway];
      }
    paths = j;
    }

  return( q[0] );
  } /* ubi_btLeafNode */

int ubi_btModuleID( int size, char *list[] )
  /* ------------------------------------------------------------------------ **
   * Returns a set of strings that identify the module.
   *
   *  Input:  size  - The number of elements in the array <list>.
   *          list  - An array of pointers of type (char *).  This array
   *                  should, initially, be empty.  This function will fill
   *                  in the array with pointers to strings.
   *  Output: The number of elements of <list> that were used.  If this value
   *          is less than <size>, the values of the remaining elements are
   *          not guaranteed.
   *
   *  Notes:  Please keep in mind that the pointers returned indicate strings
   *          stored in static memory.  Don't free() them, don't write over
   *          them, etc.  Just read them.
   * ------------------------------------------------------------------------ **
   */
  {
  if( size > 0 )
    {
    list[0] = ModuleID;
    if( size > 1 )
      list[1] = NULL;
    return( 1 );
    }
  return( 0 );
  } /* ubi_btModuleID */


/* ========================================================================== */