ubi_bintree.h

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

   *
   *  See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf().
   * ------------------------------------------------------------------------ **
   */

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().
   * ------------------------------------------------------------------------ **
   */

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.
   * ------------------------------------------------------------------------ **
   */

ubi_btNodePtr ubi_btPrev( ubi_btNodePtr P );
  /* ------------------------------------------------------------------------ **
   * 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.
   * ------------------------------------------------------------------------ **
   */

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.
   * ------------------------------------------------------------------------ **
   */

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.
   * ------------------------------------------------------------------------ **
   */

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.
   *
   * ------------------------------------------------------------------------ **
   */

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.
   *
   * ------------------------------------------------------------------------ **
   */

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.
   *             
   * ------------------------------------------------------------------------ **
   */


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 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.
   *
   * ------------------------------------------------------------------------ **
   */


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.
   * ------------------------------------------------------------------------ **
   */

/* -------------------------------------------------------------------------- **
 * Masquarade...
 *
 * This set of defines allows you to write programs that will use any of the
 * implemented binary tree modules (currently BinTree, AVLtree, and SplayTree).
 * Instead of using ubi_bt..., use ubi_tr..., and select the tree type by
 * including the appropriate module header.
 */

#define ubi_trItemPtr ubi_btItemPtr

#define ubi_trNode    ubi_btNode
#define ubi_trNodePtr ubi_btNodePtr

#define ubi_trRoot    ubi_btRoot
#define ubi_trRootPtr ubi_btRootPtr

#define ubi_trCompFunc    ubi_btCompFunc
#define ubi_trActionRtn   ubi_btActionRtn
#define ubi_trKillNodeRtn ubi_btKillNodeRtn

#define ubi_trSgn( x ) ubi_btSgn( x )

#define ubi_trInitNode( Np ) ubi_btInitNode( (ubi_btNodePtr)(Np) )

#define ubi_trInitTree( Rp, Cf, Fl ) \
        ubi_btInitTree( (ubi_btRootPtr)(Rp), (ubi_btCompFunc)(Cf), (Fl) )

#define ubi_trInsert( Rp, Nn, Ip, On ) \
        ubi_btInsert( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Nn), \
                      (ubi_btItemPtr)(Ip), (ubi_btNodePtr *)(On) )

#define ubi_trRemove( Rp, Dn ) \
        ubi_btRemove( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Dn) )

#define ubi_trLocate( Rp, Ip, Op ) \
        ubi_btLocate( (ubi_btRootPtr)(Rp), \
                      (ubi_btItemPtr)(Ip), \
                      (ubi_trCompOps)(Op) )

#define ubi_trFind( Rp, Ip ) \
        ubi_btFind( (ubi_btRootPtr)(Rp), (ubi_btItemPtr)(Ip) )

#define ubi_trNext( P ) ubi_btNext( (ubi_btNodePtr)(P) )

#define ubi_trPrev( P ) ubi_btPrev( (ubi_btNodePtr)(P) )

#define ubi_trFirst( P ) ubi_btFirst( (ubi_btNodePtr)(P) )

#define ubi_trLast( P ) ubi_btLast( (ubi_btNodePtr)(P) )

#define ubi_trFirstOf( Rp, Ip, P ) \
        ubi_btFirstOf( (ubi_btRootPtr)(Rp), \
                       (ubi_btItemPtr)(Ip), \
                       (ubi_btNodePtr)(P) )

#define ubi_trLastOf( Rp, Ip, P ) \
        ubi_btLastOf( (ubi_btRootPtr)(Rp), \
                      (ubi_btItemPtr)(Ip), \
                      (ubi_btNodePtr)(P) )

#define ubi_trTraverse( Rp, En, Ud ) \
        ubi_btTraverse((ubi_btRootPtr)(Rp), (ubi_btActionRtn)(En), (void *)(Ud))

#define ubi_trKillTree( Rp, Fn ) \
        ubi_btKillTree( (ubi_btRootPtr)(Rp), (ubi_btKillNodeRtn)(Fn) )

#define ubi_trLeafNode( Nd ) \
        ubi_btLeafNode( (ubi_btNodePtr)(Nd) )

#define ubi_trModuleID( s, l ) ubi_btModuleID( s, l )

/* ========================================================================== */
#endif /* UBI_BINTREE_H */