tbbt.h

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * Copyright by The HDF Group.                                               *
 * Copyright by the Board of Trustees of the University of Illinois.         *
 * All rights reserved.                                                      *
 *                                                                           *
 * This file is part of HDF.  The full HDF copyright notice, including       *
 * terms governing use, modification, and redistribution, is contained in    *
 * the files COPYING and Copyright.html.  COPYING can be found at the root   *
 * of the source code distribution tree; Copyright.html can be found at      *
 * http://hdfgroup.org/products/hdf4/doc/Copyright.html.  If you do not have *
 * access to either file, you may request a copy from help@hdfgroup.org.     *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/* $Id: tbbt.h 5444 2010-08-25 16:40:05Z byrn $ */

/* "tbbt.h" -- Data types/routines for threaded, balanced, binary trees. */
/* Extended from Knuth 6.2.3, Algorithm A */

#ifndef TBBT_H
#define TBBT_H

#include "H4api_adpt.h"

#ifdef lint     /* lint always complains but may complain more if... */
# define   TBBT_INTERNALS   /* TBBT_INTERNALS not always defined */
#endif /* lint */

typedef struct tbbt_node TBBT_NODE;

/* Threaded node structure */
struct tbbt_node
  {
      VOIDP       data;         /* Pointer to user data to be associated with node */
      VOIDP       key;          /* Field to sort nodes on */

#ifdef TBBT_INTERNALS
# define   PARENT  0
# define   LEFT    1
# define   RIGHT   2
      TBBT_NODE  *link[3];      /* Pointers to parent, left child, and right child */
# define  Parent    link[PARENT]
# define  Lchild    link[LEFT]
# define  Rchild    link[RIGHT]
# define  TBBT_FLAG unsigned long
# define  TBBT_LEAF unsigned long
      TBBT_FLAG   flags;        /* Combination of the following bit fields: */
# define  TBBT_HEAVY(s) s       /* If the `s' sub-tree is deeper than the other */
# define  TBBT_DOUBLE   4       /* If "heavy" sub-tree is two levels deeper */
# define  TBBT_INTERN   8       /* If node is internal (has two children) */
# define  TBBT_UNBAL    ( TBBT_HEAVY(LEFT) | TBBT_HEAVY(RIGHT) )
# define  TBBT_FLAGS    ( TBBT_UNBAL | TBBT_INTERN | TBBT_DOUBLE )
# define  TBBT_CHILD(s) ( TBBT_INTERN | TBBT_HEAVY(s) )
      TBBT_LEAF   lcnt;         /* count of left children */
      TBBT_LEAF   rcnt;         /* count of right children */
# define  LeftCnt(node) ( (node)->lcnt )    /* Left descendants */
# define  RightCnt(node) ( (node)->rcnt )   /* Left descendants */
#if defined macintosh || defined MAC || defined SYMANTEC_C     /* Macro substitution limit */
# define  Cnt(node,s)   ( 1==(s) ? LeftCnt(node) : RightCnt(node) )
#else                           /* !macintosh */
# define  Cnt(node,s)   ( LEFT==(s) ? LeftCnt(node) : RightCnt(node) )
#endif                          /* !macintosh */
# define  HasChild(n,s) ( Cnt(n,s)>0 )
# define  Heavy(n,s)    ( (s) & (LeftCnt(n)>RightCnt(n) ? LEFT : \
                 LeftCnt(n)==RightCnt(n) ? 0 : RIGHT))
# define  Intern(n)     ( LeftCnt(n) && RightCnt(n) )
# define  UnBal(n)      ( LeftCnt(n)>RightCnt(n) ? LEFT : \
                 LeftCnt(n)==RightCnt(n) ? 0 : RIGHT)
# define  Double(n)     ( TBBT_DOUBLE & (n)->flags )
# define  Other(side)   ( LEFT + RIGHT - (side) )
# define  Delta(n,s)    (  ( Heavy(n,s) ? 1 : -1 )                          \
                            *  ( Double(n) ? 2 : UnBal(n) ? 1 : 0 )  )
# define  SetFlags(n,s,b,i)   (  ( -2<(b) && (b)<2 ? 0 : TBBT_DOUBLE )   \
    |  ( 0>(b) ? TBBT_HEAVY(s) : (b)>0 ? TBBT_HEAVY(Other(s)) : 0 )        \
    |  ( (i) ? TBBT_INTERN : 0 )  )
  };

/* Pointer to the tbbt node free list */
static TBBT_NODE *tbbt_free_list=NULL;

typedef struct tbbt_tree TBBT_TREE;
/* Threaded tree structure */
struct tbbt_tree
  {
      TBBT_NODE  *root;
      unsigned long count;      /* The number of nodes in the tree currently */
      uintn       fast_compare; /* use a faster in-line compare (with casts) instead of function call */
      intn        (*compar) (VOIDP k1, VOIDP k2, intn cmparg);
      intn        cmparg;
#endif                          /* TBBT_INTERNALS */
  };

/* Define the "fast compare" values */
#define TBBT_FAST_UINT16_COMPARE    1
#define TBBT_FAST_INT32_COMPARE     2

#ifndef TBBT_INTERNALS
typedef TBBT_NODE **TBBT_TREE;
#endif /* TBBT_INTERNALS */

/* Return maximum of two scalar values (use arguments w/o side effects): */
#define   Max(a,b)  ( (a) > (b) ? (a) : (b) )

/* These routines are designed to allow use of a general-purpose balanced tree
 * implimentation.  These trees are appropriate for maintaining in memory one
 * or more lists of items, each list sorted according to key values (key values
 * must form a "completely ordered set") where no two items in a single list
 * can have the same key value.  The following operations are supported:
 *     Create an empty list
 *     Add an item to a list
 *     Look up an item in a list by key value
 *     Look up the Nth item in a list
 *     Delete an item from a list
 *     Find the first/last/next/previous item in a list
 *     Destroy a list
 * Each of the above operations requires Order(log(N)) time where N is the
 * number of items in the list (except for list creation which requires
 * constant time and list destruction which requires Order(N) time if the user-
 * supplied free-data-item or free-key-value routines require constant time).
 * Each of the above operations (except create and destroy) can be performed
 * on a subtree.
 *
 * Each node of a tree has associated with it a generic pointer (void *) which
 * is set to point to one such "item" and a generic pointer to point to that
 * item's "key value".  The structure of the items and key values is up to the
 * user to define.  The user must specify a method for comparing key values.
 * This routine takes three arguments, two pointers to key values and a third
 * integer argument.  You can specify a routine that expects pointers to "data
 * items" rather than key values in which case the pointer to the key value in
 * each node will be set equal to the pointer to the data item.
 *
 * Since the "data item" pointer is the first field of each tree node, these
 * routines may be used without this "tbbt.h" file.  For example, assume "ITM"
 * is the structre definition for the data items you want to store in lists:
 * ITM ***tbbtdmake( int (*cmp)(void *,void *,int), int arg );
 * ITM **root= NULL;        (* How to create an empty tree w/o tbbtdmake() *)
 * ITM **tbbtdfind( ITM ***tree, void *key, ITM ***pp );
 * ITM **tbbtfind( ITM **root, void *key, int (*cmp)(), int arg, ITM ***pp );
 * ITM **tbbtdless( ITM ***tree, void *key, ITM ***pp );
 * ITM **tbbtless( ITM **root, void *key, int (*cmp)(), int arg, ITM ***pp );
 * ITM **tbbtindx( ITM **root, long indx );
 * ITM **tbbtdins( ITM ***tree, ITM *item, void *key );
 * ITM **tbbtins( ITM ***root, ITM *item, void *key, int (*cmp)(), int arg );
 * ITM *tbbtrem( ITM ***root, ITM **node, void **kp );
 * ITM **tbbtfirst( ITM **root ), **tbbtlast( ITM **root );
 * ITM **tbbtnext( ITM **node ), **tbbtprev( ITM **node );
 * ITM ***tbbtdfree( ITM ***tree, void (*df)(ITM *), void (*kf)(void *) );
 * void tbbtfree( ITM ***root, void (*df)(ITM *), void (*kf)(void *) );
 */

#if defined c_plusplus || defined __cplusplus
extern      "C"
{
#endif                          /* c_plusplus || __cplusplus */

HDFLIBAPI TBBT_TREE  *tbbtdmake
                (intn (*compar) (VOIDP, VOIDP, intn), intn arg, uintn fast_compare);
/* Allocates and initializes an empty threaded, balanced, binary tree and
 * returns a pointer to the control structure for it.  You can also create
 * empty trees without this function as long as you never use tbbtd* routines
 * (tbbtdfind, tbbtdins, tbbtdfree) on them.
 * Examples:
 *     int keycmp();
 *     TBBT_ROOT *root= tbbtdmake( keycmp, (int)keysiz , 0);
 * or
 *     void *root= tbbtdmake( strcmp, 0 , 0);
 * or
 *     void *root= tbbtdmake( keycmp, (int)keysiz , TBBT_FAST_UINT16_COMPARE);
 * or
 *     TBBT_NODE *root= NULL;        (* Don't use tbbtd* routines *)
 * `cmp' is the routine to be used to compare two key values [in tbbtdfind()
 * and tbbtdins()].  The arguments to `cmp' are the two keys to compare
 * and `arg':  (*cmp)(k1,k2,arg).  `cmp' is expected to return 0 if its first
 * two arguments point to identical key values, -1 (or any integer less than 0)
 * if k1 points to a key value lower than that pointed to by k2, and 1 (or any
 * integer greater than 0) otherwise.  If `cmp' is NULL, memcmp is used.  If
 * `cmp' is NULL and `arg' is not greater than 0L, `1+strlen(key1)' is used in
 * place of `arg' to emulate strcmp():  memcmp( k1, k2, 1+strlen(k1) ).  You
 * can use strcmp() directly (as in the second example above) as long as your C
 * compiler does not assume strcmp() will always be passed exactly 2 arguments
 * (only newer, ANSI-influenced C compilers are likely to be able to make this
 * kind of assumption).  You can also use a key comparison routine that expects
 * pointers to data items rather than key values.
 *  The "fast compare" option is for keys of simple numeric types (currently
 *      uint16 and int32) and avoids the function call for faster searches in
 *      some cases.  The key comparison routine is still required for some
 *      insertion routines which use it.
 *
 * Most of the other routines expect a pointer to a root node of a tree, not
 * a pointer to the tree's control structure (only tbbtdfind(), tbbtdins(),
 * and tbbtdfree() expect pointers to control structures).  However TBBT_TREE
 * is just defined as "**TBBT_NODE" (unless you have defined TBBT_INTERNALS so
 * you have access to the internal structure of the nodes) so
 *     TBBT_TREE *tree1= tbbtdmake( NULL, 0 );
 * is equivalent to
 *     TBBT_NODE **tree1= tbbtdmake( NULL, 0 );
 * So could be used as:
 *     node= tbbtdfind( tree1, key, NULL );
 *     node= tbbtfind( *tree1, key, compar, arg, NULL );
 *     node= tbbtdless( tree1, key, NULL );
 *     node= tbbtless( *tree1, key, compar, arg, NULL );
 *     node= tbbtdins( tree1, item, key );
 *     node= tbbtins( tree1, item, key, compar, arg );
 *     item= tbbtrem( tree1, tbbtdfind(tree1,key,NULL), NULL );
 *     item= tbbtrem( tree1, tbbtfind(*tree1,key,compar,arg,NULL), NULL );
 *     tree1= tbbtdfree( tree1, free, NULL );       (* or whatever *)
 * while
 *     TBBT_NODE *root= NULL;
 * would be used like:
 *     node= tbbtfind( root, key );
 *     node= tbbtins( &root, item, key );
 *     node= tbbtrem( &root, tbbtfind(root,key), NULL );
 *     tbbtfree( &root, free, NULL );               (* or whatever *)
 * Never use tbbtfree() on a tree allocated with tbbtdmake() or on a sub-tree
 * of ANY tree.  Never use tbbtdfree() except on a tbbtdmake()d tree.
 */

HDFLIBAPI TBBT_NODE  *tbbtdfind
                (TBBT_TREE * tree, VOIDP key, TBBT_NODE ** pp);
HDFLIBAPI TBBT_NODE  *tbbtfind
                (TBBT_NODE * root, VOIDP key, intn (*cmp) (VOIDP, VOIDP, intn),
                 intn arg, TBBT_NODE ** pp);
HDFLIBAPI TBBT_NODE  *tbbtdless
                (TBBT_TREE * tree, VOIDP key, TBBT_NODE ** pp);
HDFLIBAPI TBBT_NODE  *tbbtless
                (TBBT_NODE * root, VOIDP key, intn (*cmp) (VOIDP, VOIDP, intn),
                 intn arg, TBBT_NODE ** pp);
/* Locate a node based on the key given.  A pointer to the node in the tree
 * with a key value matching `key' is returned.  If no such node exists, NULL
 * is returned.  Whether a node is found or not, if `pp' is not NULL, `*pp'
 * will be set to point to the parent of the node we are looking for (or that
 * node that would be the parent if the node is not found).  tbbtdfind() is
 * used on trees created using tbbtdmake() (so that `cmp' and `arg' don't have
 * to be passed).  tbbtfind() can be used on the root or any subtree of a tree
 * create using tbbtdmake() and is used on any tree (or subtree) created with-
 * out using tbbtdmake().  tbbtless() & tbbtdless() work exactly like tbbtfind()
 * and tbbtdfind() except that they find the node with a key which is less than
 * or equal to the key given to them.
 */

HDFLIBAPI TBBT_NODE  *tbbtindx
                (TBBT_NODE * root, int32 indx);
/* Locate the node that has `indx' nodes with lesser key values.  This is like
 * an array lookup with the first item in the list having index 0.  For large
 * values of `indx', this call is much faster than tbbtfirst() followed by
 * `indx' tbbtnext()s.  Thus `tbbtindx(&root,0L)' is equivalent to (and almost
 * as fast as) `tbbtfirst(root)'.
 */

HDFLIBAPI TBBT_NODE  *tbbtdins
                (TBBT_TREE * tree, VOIDP item, VOIDP key);
HDFLIBAPI TBBT_NODE  *tbbtins
                (TBBT_NODE ** root, VOIDP item, VOIDP key, intn (*cmp) (VOIDP, VOIDP, intn), intn arg);
/* Insert a new node to the tree having a key value of `key' and a data pointer
 * of `item'.  If a node already exists in the tree with key value `key' or if
 * malloc() fails, NULL is returned (no node is inserted), otherwise a pointer
 * to the inserted node is returned.  `cmp' and `arg' are as for tbbtfind().
 */

HDFLIBAPI VOIDP       tbbtrem
                (TBBT_NODE ** root, TBBT_NODE * node, VOIDP *kp);
/* Remove the node pointed to by `node' from the tree with root `root'.  The
 * data pointer for the deleted node is returned.  If the second argument is
 * NULL, NULL is returned.  If `kp' is not NULL, `*kp' is set to point to the
 * key value for the deleted node.  Examples:
 *     data= tbbtrem( tree, tbbtdfind(tree,key), &kp );  free(data);  free(kp);
 *     data= tbbtrem( &root, tbbtfind(root,key,compar,arg), NULL );
 *     data= tbbtrem( &tree->root, tbbtdfind(tree,key), NULL );
 */

HDFLIBAPI TBBT_NODE  *tbbtfirst
                (TBBT_NODE * root);
HDFLIBAPI TBBT_NODE  *tbbtlast
                (TBBT_NODE * root);
/* Returns a pointer to node from the tree with the lowest(first)/highest(last)
 * key value.  If the tree is empy NULL is returned.  Examples:
 *     node= tbbtfirst(*tree);
 *     node= tbbtfirst(root);
 *     node= tbbtlast(tree->root);
 *     node= tbbtlast(node);        (* Last node in a sub-tree *)
 */

HDFLIBAPI TBBT_NODE  *tbbtnext
                (TBBT_NODE * node);
HDFLIBAPI TBBT_NODE  *tbbtprev
                (TBBT_NODE * node);
/* Returns a pointer the node from the tree with the next highest (previous
 * lowest) key value relative to the node pointed to by `node'.  If `node'
 * points the last (first) node of the tree, NULL is returned.
 */

HDFLIBAPI TBBT_TREE  *tbbtdfree
                (TBBT_TREE * tree, VOID(*fd) (VOIDP), VOID(*fk) (VOIDP));
HDFLIBAPI VOID        tbbtfree
                (TBBT_NODE ** root, VOID(*fd) (VOIDP), VOID(*fk) (VOIDP));
/* Frees up an entire tree.  `fd' is a pointer to a function that frees/
 * destroys data items, and `fk' is the same for key values.
 *     void free();
 *       tree= tbbtdfree( tree, free, free );
 *       tbbtfree( &root, free, free );
 * is a typical usage, where keys and data are individually malloc()d.  If `fk'
 * is NULL, no action is done for the key values (they were allocated on the
 * stack, as a part of each data item, or together with one malloc() call, for
 * example) and likewise for `fd'.  tbbtdfree() always returns NULL and
 * tbbtfree() always sets `root' to be NULL.
 */

HDFLIBAPI VOID        tbbtprint
                (TBBT_NODE * node);
/* Prints out the data in a node */

HDFLIBAPI VOID        tbbtdump
                (TBBT_TREE * tree, intn method);
/* Prints an entire tree.  The method variable determines which sort of
 * traversal is used:
 *      -1 : Pre-Order Traversal
 *       1 : Post-Order Traversal
 *       0 : In-Order Traversal
 */

HDFLIBAPI long        tbbtcount
                (TBBT_TREE * tree);

/* Terminate the buffers used in the tbbt*() interface */
HDFPUBLIC intn tbbt_shutdown(void);

#if defined c_plusplus || defined __cplusplus
}
#endif                          /* c_plusplus || __cplusplus */

#endif                          /* TBBT_H */