path: root/src/H5TB.c

/*
 * Copyright (C) 2000-2001 NCSA
 *		           All rights reserved.
 *
 * Programmer: Quincey Koziol <koziol@ncsa.uiuc.edu>
 *	       Saturday, April 22, 2000
 *
 * Purpose: Routines for using threaded, balanced, binary trees.
 *      Extended from (added threads to) Knuth 6.2.3, Algorithm A (AVL trees)
 *      Basic tree structure by Adel'son-Vel'skii and Landis
 *
 * 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 ***H5TB_dmake( int (*cmp)(void *,void *,int), int arg );
 * ITM **root= NULL;        (* How to create an empty tree w/o H5TB_dmake() *)
 * ITM **H5TB_dfind( ITM ***tree, void *key, ITM ***pp );
 * ITM **H5TB_find( ITM **root, void *key, int (*cmp)(), int arg, ITM ***pp );
 * ITM **H5TB_dless( ITM ***tree, void *key, ITM ***pp );
 * ITM **H5TB_less( ITM **root, void *key, int (*cmp)(), int arg, ITM ***pp );
 * ITM **H5TB_indx( ITM **root, long indx );
 * ITM **H5TB_dins( ITM ***tree, ITM *item, void *key );
 * ITM **H5TB_ins( ITM ***root, ITM *item, void *key, int (*cmp)(), int arg );
 * ITM *H5TB_rem( ITM ***root, ITM **node, void **kp );
 * ITM **H5TB_first( ITM **root ), **H5TB_last( ITM **root );
 * ITM **H5TB_next( ITM **node ), **H5TB_prev( ITM **node );
 * ITM ***H5TB_dfree( ITM ***tree, void (*df)(ITM *), void (*kf)(void *) );
 * void H5TB_free( ITM ***root, void (*df)(ITM *), void (*kf)(void *) );
 */

/* $Id$ */

#include "H5private.h"		/*library		  */
#include "H5Eprivate.h"		/*error handling	  */
#include "H5Fprivate.h"        /* File address macros */
#include "H5MMprivate.h"	/*Core memory management	  */
#include "H5FLprivate.h"	/*Free Lists	  */
#include "H5TBprivate.h"    /*Threaded, balanced, binary trees	  */

# define   KEYcmp(k1,k2,a) ((NULL!=compar) ? (*compar)( k1, k2, a) \
                 : HDmemcmp( k1, k2, 0<(a) ? ((size_t)a) : HDstrlen(k1) )  )

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

/* Local Function Prototypes */
static H5TB_NODE * H5TB_end(H5TB_NODE * root, int side);
static H5TB_NODE *H5TB_ffind(H5TB_NODE * root, void * key, unsigned fast_compare,
    H5TB_NODE ** pp);
static herr_t H5TB_balance(H5TB_NODE ** root, H5TB_NODE * ptr, int side, int added);
static H5TB_NODE *H5TB_swapkid(H5TB_NODE ** root, H5TB_NODE * ptr, int side);
static H5TB_NODE *H5TB_nbr(H5TB_NODE * ptr, int side);

#ifdef H5TB_DEBUG
static herr_t H5TB_printNode(H5TB_NODE * node, void(*key_dump)(void *,void *));
static herr_t H5TB_dumpNode(H5TB_NODE *node, void (*key_dump)(void *,void *),
                          int method);
#endif /* H5TB_DEBUG */

/* Declare a free list to manage the H5TB_NODE struct */
H5FL_DEFINE_STATIC(H5TB_NODE);

#define PABLO_MASK	H5TB_mask
static int		interface_initialize_g = 0;
#define INTERFACE_INIT	NULL


/*-------------------------------------------------------------------------
 * Function:	H5TB_dmake
 *
 * Purpose:	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 H5TB_d* routines
 * (H5TB_dfind, H5TB_dins, H5TB_dfree) on them.
 * Examples:
 *     int keycmp();
 *     H5TB_ROOT *root= H5TB_dmake( keycmp, (int)keysiz , 0);
 * or
 *     void *root= H5TB_dmake( strcmp, 0 , 0);
 * or
 *     void *root= H5TB_dmake( keycmp, (int)keysiz , H5TB_FAST_HADDR_COMPARE);
 * or
 *     H5TB_NODE *root= NULL;        (* Don't use H5TB_d* routines *)
 *
 * `cmp' is the routine to be used to compare two key values [in H5TB_dfind()
 * and H5TB_dins()].  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
 *      haddr_t and int) 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 H5TB_dfind(), H5TB_dins(),
 * and H5TB_dfree() expect pointers to control structures).  However H5TB_TREE
 * is just defined as "**H5TB_NODE" (unless you have defined H5TB_INTERNALS so
 * you have access to the internal structure of the nodes) so
 *     H5TB_TREE *tree1= H5TB_dmake( NULL, 0 );
 * is equivalent to
 *     H5TB_NODE **tree1= H5TB_dmake( NULL, 0 );
 * So could be used as:
 *     node= H5TB_dfind( tree1, key, NULL );
 *     node= H5TB_find( *tree1, key, compar, arg, NULL );
 *     node= H5TB_dless( tree1, key, NULL );
 *     node= H5TB_less( *tree1, key, compar, arg, NULL );
 *     node= H5TB_dins( tree1, item, key );
 *     node= H5TB_ins( tree1, item, key, compar, arg );
 *     item= H5TB_rem( tree1, H5TB_dfind(tree1,key,NULL), NULL );
 *     item= H5TB_rem( tree1, H5TB_find(*tree1,key,compar,arg,NULL), NULL );
 *     tree1= H5TB_dfree( tree1, free, NULL );       (* or whatever *)
 * while
 *     H5TB_NODE *root= NULL;
 * would be used like:
 *     node= H5TB_find( root, key );
 *     node= H5TB_ins( &root, item, key );
 *     node= H5TB_rem( &root, H5TB_find(root,key), NULL );
 *     H5TB_free( &root, free, NULL );               (* or whatever *)
 * Never use H5TB_free() on a tree allocated with H5TB_dmake() or on a sub-tree
 * of ANY tree.  Never use H5TB_dfree() except on a H5TB_dmake()d tree.
 *
 * Return:	Success:	Pointer to a valid H5TB tree
 * 		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *              Saturday, April 22, 2000
 *
 * Modifications:
 * 	
 *-------------------------------------------------------------------------
 */
H5TB_TREE  *
H5TB_dmake(H5TB_cmp_t cmp, int arg, unsigned fast_compare)
{
    H5TB_TREE  *tree;

    FUNC_ENTER (H5TB_dmake, NULL);

    if (NULL == (tree = H5MM_malloc(sizeof(H5TB_TREE))))
        HRETURN_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");

    tree->root = NULL;
    tree->count = 0;
    tree->fast_compare=fast_compare;
    tree->compar = cmp;
    tree->cmparg = arg;

    FUNC_LEAVE (tree);
}   /* end H5TB_dmake() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_dfind
 *
 * Purpose: Look up a node in a "described" tree based on a key value
 * 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).  H5TB_dfind() is
 * used on trees created using H5TB_dmake() (so that `cmp' and `arg' don't have
 * to be passed).  [H5TB_find() can be used on the root or any subtree of a tree
 * create using H5TB_dmake() and is used on any tree (or subtree) created with-
 * out using H5TB_dmake().]
 *
 * Return:	Success:	Pointer to a valid H5TB node
 * 		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *              Thursday, May 5, 2000
 *
 * Modifications:
 * 	
 *-------------------------------------------------------------------------
 */
H5TB_NODE  *
H5TB_dfind(H5TB_TREE * tree, void * key, H5TB_NODE ** pp)
{
    H5TB_NODE *ret_value=NULL;

    FUNC_ENTER (H5TB_dfind, NULL);

    assert(tree);

    if(tree->fast_compare!=0)
        ret_value=H5TB_ffind(tree->root, key, tree->fast_compare, pp);
    else
        ret_value=H5TB_find(tree->root, key, tree->compar, tree->cmparg, pp);

    FUNC_LEAVE (ret_value);
}   /* end H5TB_dfind() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_find
 *
 * Purpose: Look up a node in a "non-described" tree based on a key value
 * 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).  H5TB_dfind() is
 * used on trees created using H5TB_dmake() (so that `cmp' and `arg' don't have
 * to be passed).  [H5TB_find() can be used on the root or any subtree of a tree
 * create using H5TB_dmake() and is used on any tree (or subtree) created with-
 * out using H5TB_dmake().]
 *
 * Return:	Success:	Pointer to a valid H5TB node
 * 		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *              Thursday, May 5, 2000
 *
 * Modifications:
 * 
 * Notes:
 *  H5TB_ffind is based on this routine - fix bugs in both places!
 * 	
 *-------------------------------------------------------------------------
 */
H5TB_NODE  *
H5TB_find(H5TB_NODE * root, void * key,
     H5TB_cmp_t compar, int arg, H5TB_NODE ** pp)
{
    H5TB_NODE  *ptr = root;
    H5TB_NODE  *parent = NULL;
    int        cmp = 1;
    int        side;

    FUNC_ENTER (H5TB_find, NULL);


    if(ptr) {
        while (0 != (cmp = KEYcmp(key, ptr->key, arg))) {
            parent = ptr;
            side = (cmp < 0) ? LEFT : RIGHT;
            if (!HasChild(ptr, side))
                break;
            ptr = ptr->link[side];
          } /* end while */
    } /* end if */

    if (NULL != pp)
        *pp = parent;
    FUNC_LEAVE ((0 == cmp) ? ptr : NULL);
}   /* end H5TB_find() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_dless
 *
 * Purpose: Look up a node in a "described" tree based on a key value.
 * Locate a node based on the key given.  A pointer to the node in the tree
 * with a key value less than or equal to `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).
 * H5TB_dless() is used on trees created using H5TB_dmake() (so that `cmp' and
 * `arg' don't have to be passed).  [H5TB_less() can be used on the root or any
 * subtree of a tree create using H5TB_dmake() and is used on any tree (or
 * subtree) created with-out using H5TB_dmake().]
 *
 * Return:	Success:	Pointer to a valid H5TB node
 * 		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *              Thursday, May 5, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
H5TB_NODE  *
H5TB_dless(H5TB_TREE * tree, void * key, H5TB_NODE ** pp)
{
    FUNC_ENTER(H5TB_dless,NULL);

    assert(tree);

    FUNC_LEAVE(H5TB_less(tree->root, key, tree->compar, tree->cmparg, pp));
}   /* end H5TB_dless() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_less
 *
 * Purpose: Look up a node in a "non-described" tree based on a key value.
 * Locate a node based on the key given.  A pointer to the node in the tree
 * with a key value less than or equal to `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).
 * H5TB_dless() is used on trees created using H5TB_dmake() (so that `cmp' and
 * `arg' don't have to be passed).  [H5TB_less() can be used on the root or any
 * subtree of a tree create using H5TB_dmake() and is used on any tree (or
 * subtree) created with-out using H5TB_dmake().]
 *
 * Return:	Success:	Pointer to a valid H5TB node
 * 		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *              Thursday, May 5, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
H5TB_NODE  *
H5TB_less(H5TB_NODE * root, void * key, H5TB_cmp_t compar, int arg, H5TB_NODE ** pp)
{
    H5TB_NODE  *ptr = root;
    H5TB_NODE  *parent = NULL;
    int        cmp = 1;
    int        side;

    FUNC_ENTER(H5TB_less,NULL);

    /* Try to find an exact match */
    if (ptr) {
        while (0 != (cmp = KEYcmp(key, ptr->key, arg))) {
            parent = ptr;
            side = (cmp < 0) ? LEFT : RIGHT;
            if (!HasChild(ptr, side))
                break;
            ptr = ptr->link[side];
        } /* end while */
    } /* end if */

	/* didn't find an exact match, search back up the tree until a node */
	/* is found with a key less than the key searched for */
    if(cmp!=0) {
        while((ptr=ptr->Parent)!=NULL) {
              cmp = KEYcmp(key, ptr->key, arg);
              if(cmp<0) /* found a node which is less than the search for one */
                  break;
          } /* end while */
        if(ptr==NULL) /* didn't find a node in the tree which was less */
            cmp=1;
        else /* reset this for cmp test below */
            cmp=0;
      } /* end if */

    if (NULL != pp)
        *pp = parent;

    FUNC_LEAVE((0 == cmp) ? ptr : NULL);
}   /* end H5TB_less */


/*-------------------------------------------------------------------------
 * Function:	H5TB_index
 *
 * Purpose: 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 H5TB_first()
 * followed by `indx' H5TB_next()s.  Thus `H5TB_index(&root,0L)' is equivalent to
 * (and almost as fast as) `H5TB_first(root)'.
 *
 * Return:	Success:	Pointer to a valid H5TB node
 * 		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *              Friday, May 6, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
H5TB_NODE  *
H5TB_index(H5TB_NODE * root, unsigned indx)
{
    H5TB_NODE  *ptr = root;

    FUNC_ENTER(H5TB_index,NULL);

    if (NULL != ptr) {
      /* Termination condition is if the index equals the number of children on
         out left plus the current node */
        while (ptr != NULL && indx != ((unsigned) LeftCnt(ptr)) + 1 ) {
            if (indx <= (unsigned) LeftCnt(ptr)) {
                ptr = ptr->Lchild;
              } /* end if */
            else if (HasChild(ptr, RIGHT)) {
                /* subtract children count from leftchild plus current node when
                   we descend into a right branch */
                indx -= (unsigned)(LeftCnt(ptr) + 1);  
                ptr = ptr->Rchild;
              } /* end if */
            else {
              /* Only `indx' or fewer nodes in tree */
              ptr=NULL;
              break;
            } /* end else */
        } /* end while */
    } /* end if */

    FUNC_LEAVE(ptr);
}   /* end H5TB_index() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_dins
 *
 * Purpose: Insert a new node into a "described" 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 H5TB_find().
 *
 * Return:	Success:	Pointer to a valid H5TB node
 * 		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *              Friday, May 6, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
H5TB_NODE  *
H5TB_dins(H5TB_TREE * tree, void * item, void * key)
{
    H5TB_NODE  *ret_node;       /* the node to return */

    FUNC_ENTER(H5TB_dins,NULL);

    assert(tree);

    /* Try to insert the node */
    ret_node = H5TB_ins(&(tree->root), item, key, tree->compar, tree->cmparg);

    /* If we successfully inserted the node, increment the node count in the tree */
    if (ret_node != NULL)
        tree->count++;

    FUNC_LEAVE(ret_node);
}   /* end H5TB_dins() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_ins
 *
 * Purpose: Insert a new node into a "non-described" 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 H5TB_find().
 *
 * Return:	Success:	Pointer to a valid H5TB node
 * 		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *              Friday, May 6, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
H5TB_NODE  *
H5TB_ins(H5TB_NODE ** root, void * item, void * key, H5TB_cmp_t compar, int arg)
{
    int        cmp;
    H5TB_NODE  *ptr, *parent;

    FUNC_ENTER(H5TB_ins,NULL);

    assert(root);
    assert(item);

    if (NULL != H5TB_find(*root, (key ? key : item), compar, arg, &parent))
        HRETURN_ERROR (H5E_TBBT, H5E_EXISTS, NULL, "node already in tree");
    if (NULL == (ptr = H5FL_ALLOC(H5TB_NODE,0)))
        HRETURN_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
    ptr->data = item;
    ptr->key = key ? key : item;
    ptr->Parent = parent;
    ptr->flags = 0L;    /* No children on either side */
    ptr->lcnt = 0;
    ptr->rcnt = 0;

    /* Adding first node to tree: */
    if (NULL == parent) {
          *root = ptr;
          ptr->Lchild = ptr->Rchild = NULL;
      }
    else {
        cmp = KEYcmp(ptr->key, parent->key, arg);
        if (cmp < 0) {
              ptr->Lchild = parent->Lchild;     /* Parent's thread now new node's */
              ptr->Rchild = parent;     /* New nodes right thread is parent */
              parent->Lchild = ptr;     /* Parent now has a left child */
          }
        else {
              ptr->Rchild = parent->Rchild;
              ptr->Lchild = parent;
              parent->Rchild = ptr;
          }
        H5TB_balance(root, parent, (cmp < 0) ? LEFT : RIGHT, 1);
    } /* end else */

    FUNC_LEAVE(ptr);
}   /* end H5TB_ins() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_rem
 *
 * Purpose: Remove a node from a tree.  You pass in the address of the
 * pointer to the root node of the tree along, a pointer to the node you wish
 * to remove, and optionally the address of a pointer to hold the address of
 * the key value of the deleted node.  The second argument is usually the
 * result from a lookup function call (H5TB_find, H5TB_dfind, or H5TB_index)
 * so if it is NULL, H5TB_rem returns NULL.  Otherwise H5TB_rem removes the
 * node from the tree and returns a pointer to the data item for that node and,
 * if the third argument is not NULL, the address of the key value for the
 * deleted node is placed in the buffer that it points to.
 *
 * Examples:
 *     data= H5TB_rem( tree, H5TB_dfind(tree,key), &kp );  free(data);  free(kp);
 *     data= H5TB_rem( &root, H5TB_find(root,key,compar,arg), NULL );
 *     data= H5TB_rem( &tree->root, H5TB_dfind(tree,key), NULL );
 *
 * Return:	Success:	Pointer to data item deleted
 * 		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *              Friday, May 6, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
void *
H5TB_rem(H5TB_NODE ** root, H5TB_NODE * node, void * *kp)
{
    H5TB_NODE  *leaf;   /* Node with one or zero children */
    H5TB_NODE  *par;    /* Parent of `leaf' */
    H5TB_NODE  *next;   /* Next/prev node near `leaf' (`leaf's `side' thread) */
    int        side;   /* `leaf' is `side' child of `par' */
    void *      data;   /* Saved pointer to data item of deleted node */

    FUNC_ENTER(H5TB_rem, NULL);

    if (NULL == root || NULL == node)
        HRETURN_ERROR (H5E_ARGS, H5E_BADVALUE, NULL, "bad arguments to delete");

    data = node->data;  /* Save pointer to data item to be returned at end */
    if (NULL != kp)
        *kp = node->key;

    /* If the node to be removed is "internal" (children on both sides), we
     * replace it with it's previous (or next) node in the tree and delete that
     * previous (next) node (which has one or no children) instead. */

    /* Replace with a non-internal node: */
    if (Intern(node)) {
          /* Pick "near-leaf" node from the */
          if (Heavy(node, RIGHT)) {
                side = LEFT;    /* heavier of the sub-trees. */
            }
          else if (Heavy(node, LEFT)) {
                side = RIGHT;
            }
          /* If no sub-tree heavier, pick at "random" for "better balance" */
          else {
                side = (0x10 & *(short *) &node) ? LEFT : RIGHT;    /* balance" */
            }
          leaf = H5TB_nbr(next = node, Other(side));
          par = leaf->Parent;

          /* Case 2x: `node' had exactly 2 descendants */
          if (par == next) {
                side = Other(side);     /* Transform this to Case 2 */
                next = leaf->link[side];
            }
          node->data = leaf->data;
          node->key = leaf->key;
      } /* end if */
    /* Node has one or zero children: */
    else {
          leaf = node;  /* Simply remove THIS node */
          par = leaf->Parent;

          /* Case 3: Remove root (of 1- or 2-node tree) */
          if (NULL == par) {
                side = (int) UnBal(node);  /* Which side root has a child on */

                /* Case 3a: Remove root of 2-node tree: */
                if (side) {
                      *root = leaf = node->link[side];
                      leaf->Parent = leaf->link[Other(side)] = NULL;
                      leaf->flags = 0;  /* No left children, balanced, not internal */
                  }
                /* Case 3b: Remove last node of tree: */
                else {
                      *root = NULL;
                  }     /* end else */
                H5FL_FREE(H5TB_NODE,node);
                HRETURN(data);
            }
          side = (par->Rchild == leaf) ? RIGHT : LEFT;
          next = leaf->link[side];
      } /* end else */

    /* Now the deletion has been reduced to the following cases (and Case 3 has
     * been handled completely above and Case 2x has been transformed into
     * Case 2).  `leaf' is a node with one or zero children that we are going
     * to remove.  `next' points where the `side' thread of `leaf' points.
     * `par' is the parent of `leaf'.  The only posibilities (not counting
     * left/right reversals) are shown below:
     *       [Case 1]                  [Case 2]              [Case 2x]
     *            (next)                 (next)         ^         (next & par)
     *           /  ^   \               /  ^   \        |        /  ^         \
     *     . . .    |             . . .    |            |  (leaf)   /
     *   /          |           /          |            \_/      \_/
     * (par)        |         (par)        |             ^threads^
     *      \       |              \       |
     *     (leaf)   /             (leaf)   /            [Case 3a]    [Case 3b]
     *    /  ^   \_/<thread             \_/<thread       (root)
     * (n)   /                                                 \       (root)
     *    \_/<thread        --"side"-->                         (n)
     * Note that in Cases 1 and 2, `leaf's `side' thread can be NULL making
     * `next' NULL as well.  If you remove a node from a 2-node tree, removing
     * the root falls into Case 3a while removing the only leaf falls into
     * Case 2 (with `next' NULL and `par' the root node). */

    /* Case 2: `leaf' has no children: */
    if (!UnBal(leaf)) {
          par->link[side] = leaf->link[side];
          par->flags &= (H5TB_flag)(~(H5TB_INTERN | H5TB_HEAVY(side)));
      } /* end if */
    /* Case 1: `leaf' has one child: */
    else {
          H5TB_NODE  *n;

          /* two-in-a-row cases */
          if (HasChild(leaf, side)) {
                n = leaf->link[side];
                par->link[side] = n;
                n->Parent = par;
                if (HasChild(n, Other(side)))
                    while (HasChild(n, Other(side)))
                        n = n->link[Other(side)];
                n->link[Other(side)] = par;
            }   /* end if */
          /* zig-zag cases */
          else {
                n = leaf->link[Other(side)];
                par->link[side] = n;
                n->Parent = par;
                if (HasChild(n, side))
                    while (HasChild(n, side))
                        n = n->link[side];
                n->link[side] = next;
            }   /* end else */
      } /* end else */

    H5FL_FREE(H5TB_NODE,leaf);
    H5TB_balance(root, par, side, -1);

    ((H5TB_TREE *) root)->count--;

    FUNC_LEAVE(data);
}   /* end H5TB_rem() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_first
 *
 * Purpose: Retrieves a pointer to node from the tree with the lowest(first)
 * key value.  If the tree is empy NULL is returned.  Examples:
 *     node= H5TB_first(*tree);
 *     node= H5TB_first(root);
 *
 * Return:	Success:	Pointer to a valid H5TB node
 * 		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *              Friday, May 6, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
H5TB_NODE  *
H5TB_first(H5TB_NODE * root)
{
    FUNC_ENTER(H5TB_first,NULL);

    FUNC_LEAVE(H5TB_end(root, LEFT));
}   /* end H5TB_first() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_last
 *
 * Purpose: Retrieves a pointer to node from the tree with the highest(last)
 * key value.  If the tree is empy NULL is returned.  Examples:
 *     node= H5TB_last(tree->root);
 *     node= H5TB_last(node);        (* Last node in a sub-tree *)
 *
 * Return:	Success:	Pointer to a valid H5TB node
 * 		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *              Friday, May 6, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
H5TB_NODE  *
H5TB_last(H5TB_NODE * root)
{
    FUNC_ENTER(H5TB_last,NULL);

    FUNC_LEAVE(H5TB_end(root, RIGHT));
}   /* end H5TB_last() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_next
 *
 * Purpose: Returns a pointer the node from the tree with the next highest
 * key value relative to the node pointed to by `node'.  If `node' points the
 * last node of the tree, NULL is returned.
 *
 * Return:	Success:	Pointer to a valid H5TB node
 * 		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *              Friday, May 6, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
H5TB_NODE  *
H5TB_next(H5TB_NODE * node)
{
    FUNC_ENTER(H5TB_next,NULL);

    FUNC_LEAVE(H5TB_nbr(node, RIGHT));
}   /* end H5TB_next() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_prev
 *
 * Purpose: Returns a pointer the node from the tree with the previous lowest
 * key value relative to the node pointed to by `node'.  If `node' points the
 * first node of the tree, NULL is returned.
 *
 * Return:	Success:	Pointer to a valid H5TB node
 * 		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *              Friday, May 6, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
H5TB_NODE  *
H5TB_prev(H5TB_NODE * node)
{
    FUNC_ENTER(H5TB_prev,NULL);

    FUNC_LEAVE (H5TB_nbr(node, LEFT));
}   /* end H5TB_prev() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_dfree
 *
 * Purpose: 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 );
 *       H5TB_free( &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'.  H5TB_dfree() always returns NULL and
 * H5TB_free() always sets `root' to be NULL.
 *
 * Return:	Always returns NULL
 *
 * Programmer:	Quincey Koziol
 *              Friday, May 6, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
H5TB_TREE  *
H5TB_dfree(H5TB_TREE * tree, void(*fd) (void * /* item */), void(*fk) (void * /* key */))
{
    FUNC_ENTER(H5TB_dfree,NULL);

    if (tree == NULL)
        HRETURN(NULL);

    /* Free the actual tree */
    H5TB_free(&tree->root, fd, fk);

    /* Free the tree root */
    H5MM_xfree(tree);

    FUNC_LEAVE(NULL);
}   /* end H5TB_dfree() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_free
 *
 * Purpose: 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 );
 *       H5TB_free( &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'.  H5TB_dfree() always returns NULL and
 * H5TB_free() always sets `root' to be NULL.
 *
 * Return:	Always returns NULL
 *
 * Programmer:	Quincey Koziol
 *              Friday, May 6, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
void *
H5TB_free(H5TB_NODE ** root, void(*fd) (void * /* item */), void(*fk) (void * /* key */))
{
    H5TB_NODE  *par, *node = *root;

    FUNC_ENTER(H5TB_free,NULL);

    /* While nodes left to be free()d */
    while (NULL != *root) {
          /* First time at this node (just moved down a new leg of tree) */
          if (!HasChild(node, LEFT))
              node->Lchild = NULL;
          if (!HasChild(node, RIGHT))
              node->Rchild = NULL;
          do {
                par = NULL;     /* Assume we aren't ready to move up tree yet */
                if (NULL != node->Lchild)
                    node = node->Lchild;    /* Move down this leg next */
                else if (NULL != node->Rchild)
                    node = node->Rchild;    /* Move down this leg next */
                /* No children; free node an move up: */
                else {
                      par = node->Parent;   /* Move up tree (stay in loop) */
                      if (NULL != fd)
                          (*fd) (node->data);
                      if (NULL != fk)
                          (*fk) (node->key);
                      if (NULL == par)  /* Just free()d last node */
                          *root = NULL;     /* NULL=par & NULL=*root gets fully out */
                      else if (node == par->Lchild)
                          par->Lchild = NULL;   /* Now no longer has this child */
                      else
                          par->Rchild = NULL;   /* Ditto */

                      H5FL_FREE(H5TB_NODE,node);

                      node = par;   /* Move up tree; remember which node to do next */
                  } /* end else */
            } while (NULL != par);  /* While moving back up tree */
      } /* end while */
    FUNC_LEAVE(NULL);
}   /* end H5TB_free() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_count
 *
 * Purpose: Returns the number of nodes in a tree
 *
 * Return:	Success - Number of nodes in the tree
 *          Failure - Negative value
 *
 * Programmer:	Quincey Koziol
 *              Friday, May 6, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
long
H5TB_count(H5TB_TREE * tree)
{
    FUNC_ENTER(H5TB_count,FAIL);

    FUNC_LEAVE((tree==NULL) ? FAIL : (long)tree->count );
}   /* end H5TB_count() */

#ifdef H5TB_DEBUG


/*-------------------------------------------------------------------------
 * Function:	H5TB_dump
 *
 * Purpose: Prints out information about 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
 *
 * Return:	Shouldn't fail
 *
 * Programmer:	Quincey Koziol
 *              Friday, May 6, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
herr_t
H5TB_dump(H5TB_TREE *tree, void (*key_dump)(void *,void *), int method)
{
    FUNC_ENTER(H5TB_dump,FAIL);

	printf("H5TB-tree dump  %p:\n",tree);
	printf("capacity = %ld\n\n",(long)tree->count);
	H5TB_dumpNode(tree->root,key_dump, method);

	FUNC_LEAVE(SUCCESS);
}   /* end H5TB_dump() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_printNode
 *
 * Purpose: Prints out information about a node in the tree
 *
 * Return:	Shouldn't fail
 *
 * Programmer:	Quincey Koziol
 *              Friday, May 6, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
static herr_t
H5TB_printNode(H5TB_NODE * node, void(*key_dump)(void *,void *))
{
    FUNC_ENTER_NOINIT(H5TB_printNode);

    if (node == NULL) {
        printf("ERROR:  null node pointer\n");
        HRETURN(FAIL);
      }

    printf("node=%p, key=%p, data=%p, flags=%x\n", node, node->key, node->data, (unsigned) node->flags);
    printf("Lcnt=%d, Rcnt=%d\n", (int) node->lcnt, (int) node->rcnt);
    printf("Lchild=%p, Rchild=%p, Parent=%p\n", node->Lchild, node->Rchild, node->Parent);
    if (key_dump != NULL) {
        (*key_dump)(node->key,node->data);
      }
    FUNC_LEAVE(SUCCESS);
}   /* end H5TB_printNode() */


/*-------------------------------------------------------------------------
 * Function:	H5TB_dumpNode
 *
 * Purpose: Internal routine to actually dump tree
 * The 'method' variable determines which sort of traversal is used:
 *      -1 : Pre-Order Traversal
 *       1 : Post-Order Traversal
 *       0 : In-Order Traversal
 *
 * Return:	Shouldn't fail
 *
 * Programmer:	Quincey Koziol
 *              Friday, May 6, 2000
 *
 * Modifications:
 * 
 * Notes:
 * 	
 *-------------------------------------------------------------------------
 */
static herr_t
H5TB_dumpNode(H5TB_NODE *node, void (*key_dump)(void *,void *),
                        int method)
{
    FUNC_ENTER_NOINIT(H5TB_dumpNode);

    if (node == NULL)
        HRETURN(FAIL);

    switch (method) {
          case -1:      /* Pre-Order Traversal */
              H5TB_printNode(node, key_dump);
              if (HasChild(node, LEFT))
                  H5TB_dumpNode(node->Lchild, key_dump, method);
              if (HasChild(node, RIGHT))
                  H5TB_dumpNode(node->Rchild, key_dump, method);
              break;

          case 1:   /* Post-Order Traversal */
              if (HasChild(node, LEFT))
                  H5TB_dumpNode(node->Lchild, key_dump, method);
              if (HasChild(node, RIGHT))
                  H5TB_dumpNode(node->Rchild, key_dump, method);
              H5TB_printNode(node, key_dump);
              break;

          case 0:   /* In-Order Traversal */
          default:
              if (HasChild(node, LEFT))
                  H5TB_dumpNode(node->Lchild, key_dump, method);
              H5TB_printNode(node, key_dump);
              if (HasChild(node, RIGHT))
                  H5TB_dumpNode(node->Rchild, key_dump, method);
              break;

      } /* end switch() */
    FUNC_LEAVE(SUCCESS);
}   /* end H5TB_dumpNode() */

#endif /* H5TB_DEBUG */



/*-------------------------------------------------------------------------
 * Function:	H5TB_end
 *
 * Purpose:	Returns pointer to end-most (to LEFT or RIGHT) node of tree:
 *
 * Return:	Success:	Valid pointer
 * 		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *              Saturday, April 22, 2000
 *
 * Modifications:
 * 	
 *-------------------------------------------------------------------------
 */
static H5TB_NODE *
H5TB_end(H5TB_NODE * root, int side)
{
    FUNC_ENTER_NOINIT(H5TB_end);

    assert(root);
    assert(side==LEFT || side==RIGHT);

    while (HasChild(root, side))
      root = root->link[side];

    FUNC_LEAVE(root);
}   /* end H5TB_end() */

/* Returns pointer to neighboring node (to LEFT or RIGHT): */
static H5TB_NODE *
H5TB_nbr(H5TB_NODE * ptr, int side)
{
    FUNC_ENTER_NOINIT(H5TB_nbr);

    if (!HasChild(ptr, side))
        HRETURN (ptr->link[side]);
    ptr = ptr->link[side];
    if(ptr==NULL)
        HRETURN(NULL);
    while (HasChild(ptr, Other(side)))
        ptr = ptr->link[Other(side)];
    FUNC_LEAVE(ptr);
}   /* end H5TB_nbr() */

/* H5TB_ffind -- Look up a node in a tree based on a key value */
/* This routine is based on tbbtfind (fix bugs in both places!) */
/* Returns a pointer to the found node (or NULL) */
static H5TB_NODE  *
H5TB_ffind(H5TB_NODE * root, void * key, unsigned fast_compare, H5TB_NODE ** pp)
{
    H5TB_NODE  *ptr = root;
    H5TB_NODE  *parent = NULL;
    int        side;
    int        cmp = 1;
    H5TB_NODE  *ret_value = NULL;

    FUNC_ENTER_NOINIT(H5TB_ffind);

    switch(fast_compare) {
        case H5TB_FAST_HADDR_COMPARE:
            if (ptr) {
                while (0 != (cmp = H5F_addr_cmp(*(haddr_t *)key,*(haddr_t *)ptr->key))) {
                      parent = ptr;
                      side = (cmp < 0) ? LEFT : RIGHT;
                      if (!HasChild(ptr, side))
                          break;
                      ptr = ptr->link[side];
                  } /* end while */
              } /* end if */
            if (NULL != pp)
                *pp = parent;

            /* Set return value */
            ret_value= (0 == cmp) ? ptr : NULL;
            break;

        case H5TB_FAST_INTN_COMPARE:
            if (ptr) {
                while (0 != (cmp = (*(int *)key - *(int *)ptr->key))) {
                      parent = ptr;
                      side = (cmp < 0) ? LEFT : RIGHT;
                      if (!HasChild(ptr, side))
                          break;
                      ptr = ptr->link[side];
                  } /* end while */
              } /* end if */
            if (NULL != pp)
                *pp = parent;

            /* Set return value */
            ret_value= (0 == cmp) ? ptr : NULL;
            break;

        default:
            break;
    } /* end switch */

    FUNC_LEAVE(ret_value);
} /* H5TB_ffind() */

/* swapkid -- Often refered to as "rotating" nodes.  ptr and ptr's `side'
 * child, kid, are swapped so ptr becomes kid's `Other(side)' child.
 * Here is how a single swap (rotate) works:
 *
 *           |           --side-->         |
 *         (ptr)                         (kid)
 *        /     \                       /     \
 *    +-A-+    (kid)                 (ptr)    +-C-+
 *    |   |   /     \               /     \   |   |
 *    |...| +-B-+  +-C-+         +-A-+  +-B-+ |...|
 *          |   |  |   |         |   |  |   |
 *          |...|  |...|         |...|  |...|
 * `deep' contains the relative depths of the subtrees so, since we set
 * `deep[1]' (the relative depth of subtree [B]) to 0, `deep[2]' is the depth
 * of [C] minus the depth of [B] (-1, 0, or 1 since `kid' is never too out of
 * balance) and `deep[0]' is the depth of [A] minus the depth of [B].  These
 * values are used to compute the balance levels after the rotation.  Note that
 * [A], [B], or [C] can have depth 0 so `link[]' contains threads rather than
 * pointers to children.
 */
static H5TB_NODE *
H5TB_swapkid(H5TB_NODE ** root, H5TB_NODE * ptr, int side)
{
    H5TB_NODE  *kid = ptr->link[side];  /* Sibling to be swapped with parent */
    int        deep[3];        /* Relative depths of three sub-trees involved. */
    /* 0:ptr->link[Other(side)], 1:kid->link[Other(side)], 2:kid->link[side] */
    H5TB_flag   ptrflg;         /* New value for ptr->flags (ptr->flags used after set) */
    H5TB_leaf   plcnt, prcnt,   /* current values of the ptr's and kid's leaf count */
                klcnt, krcnt;

    FUNC_ENTER_NOINIT(H5TB_swapkid);

    deep[2] = (deep[1] = 0) + Delta(kid, side);
    deep[0] = Max(0, deep[2]) + 1 - Delta(ptr, side);
    kid->Parent = ptr->Parent;
    ptrflg = (H5TB_flag)SetFlags(ptr, side, deep[0],
                  HasChild(ptr, Other(side)) && HasChild(kid, Other(side)));
    plcnt = LeftCnt(ptr);
    prcnt = RightCnt(ptr);
    klcnt = LeftCnt(kid);
    krcnt = RightCnt(kid);
    if (HasChild(kid, Other(side))) {
          ptr->link[side] = kid->link[Other(side)];     /* Real child */
          ptr->link[side]->Parent = ptr;
      }
    else {
          ptr->link[side] = kid;    /* Thread */
      }
    /* Update grand parent's pointer: */
    if (NULL == ptr->Parent) {
          *root = kid;
      }
    else if (ptr /*->Lchild*/  == ptr->Parent->Lchild) {
          ptr->Parent->Lchild = kid;
      }
    else {
          ptr->Parent->Rchild = kid;
      }
    ptr->Parent = kid;
    kid->link[Other(side)] = ptr;
    kid->flags = (H5TB_flag)SetFlags(kid, Other(side),
                        deep[2] - 1 - Max(deep[0], 0), HasChild(kid, side));

    /* update leaf counts */
    if (side == LEFT) {     /* kid's left count doesn't change, nor ptr's r-count */
          kid->rcnt = prcnt + krcnt + 1;    /* kid's leafs+former parent's leafs+parent */
          ptr->lcnt = krcnt;
      }     /* end if */
    else {     /* kid's right count doesn't change, nor ptr's l-count */
          kid->lcnt = plcnt + klcnt + 1;    /* kid's leafs+former parent's leafs+parent */
          ptr->rcnt = klcnt;
      }     /* end if */
    ptr->flags = ptrflg;

    FUNC_LEAVE(kid);
}   /* end H5TB_swapkid() */

/* balance -- Move up tree, incrimenting number of left children when needed
 * and looking for unbalanced ancestors.  Adjust all balance factors and re-
 * balance through "rotation"s when needed.
 */
/* Here is how rotatation rebalances a tree:
 * Either the deletion of a node shortened the sub-tree [A] (to length `h')
 * while [B] or [C] or both are length `h+1'  or  the addition of a node
 * lengthened [B] or [C] to length `h+1' while the other and [A] are both
 * length `h'.  Each case changes `ptr' from being "right heavy" to being
 * overly unbalanced.
 * This           |                      Becomes:      |
 * sub-tree:    (ptr)                                (kid)
 *             /     \          --side-->           /     \
 *         +-A-+    (kid)                        (ptr)   +-C-+
 *         |   |   /     \                      /     \  |   |
 *         | h | +-B-+  +-C-+               +-A-+  +-B-+ | h |
 *         |   | |   |  |   |               |   |  |   | |   |
 *         +---+ | h |  | h |               | h |  | h | +---+
 *         : - : |   |  |   |               |   |  |   | : 1 :
 *         `- -' +---+  +---+               +---+  +---+ + - +
 *               : 1 :  : 1 :                      : 1 :
 *               + - +  + - +                      + - +
 *
 * However, if [B] is long (h+1) while [C] is short (h), a double rotate is
 * required to rebalance.  In this case, [A] was shortened or [X] or [Y] was
 * lengthened so [A] is length `h' and one of [X] and [Y] is length `h' while
 * the other is length `h-1'.  Swap `kid' with `babe' then `ptr' with `babe'.
 * This          |                         Becomes:     |
 * sub-tree:   (ptr)                                  (babe)
 *            /     \             --side-->          /      \
 *       +-A-+       (kid)                      (ptr)       (kid)
 *       |   |      /     \                    /     \     /     \
 *       | h |    (babe)   +-C-+             +-A-+ +-X-+ +-Y-+ +-C-+
 *       |   |   /      \  |   |             |   | |h-1| |h-1| |   |
 *       +---+ +-X-+ +-Y-+ | h |             | h | +---+ +---+ | h |
 *       : - : |h-1| |h-1| |   |             |   | : 1 : : 1 : |   |
 *       `- -' +---+ +---+ +---+             +---+ + - + + - + +---+
 *             : 1 : : 1 :
 *             + - + + - +
 *
 * Note that in the node insertion cases total sub-tree length always increases
 * by one then decreases again so after the rotation(s) no more rebalancing is
 * required.  In the node removal cases, the single rotation reduces total sub-
 * tree length unless [B] is length `h+1' (`ptr' ends of "right heavy") while
 * the double rotation ALWAYS reduces total sub-tree length.  Thus removing a
 * single node can require log(N) rotations for rebalancing.  On average, only
 * are usually required.
 */
static      herr_t
H5TB_balance(H5TB_NODE ** root, H5TB_NODE * ptr, int side, int added)
{
    int        deeper = added; /* 1 if sub-tree got longer; -1 if got shorter */
    int        odelta;
    int        obal;

    FUNC_ENTER_NOINIT(H5TB_balance);

    while (NULL != ptr) {
          odelta = Delta(ptr, side);    /* delta before the node was added */
          obal = UnBal(ptr);
          if (LEFT == side)     /* One more/fewer left child: */
              if (0 < added)
                  ptr->lcnt++;  /* LeftCnt(ptr)++ */
              else
                  ptr->lcnt--;  /* LeftCnt(ptr)-- */
          else if (0 < added)
              ptr->rcnt++;  /* RightCnt(ptr)++ */
          else
              ptr->rcnt--;  /* RightCnt(ptr)-- */
          if (0 != deeper)
            {   /* One leg got longer or shorter: */
                if ((deeper < 0 && odelta < 0) || (deeper > 0 && odelta > 0))
                  {     /* Became too unbalanced: */
                      H5TB_NODE  *kid;

                      ptr->flags |= H5TB_DOUBLE;    /* Mark node too unbalanced */
                      if (deeper < 0)   /* Just removed a node: */
                          side = Other(side);   /* Swap with child from other side. */
                      else
                          /* Just inserted a node: */ if (ptr->Parent && UnBal(ptr->Parent))
                        {
                            deeper = 0;     /* Fix will re-shorten sub-tree. */
                        }
                      kid = ptr->link[side];
                      if (Heavy(kid, Other(side)))
                        {   /* Double rotate needed: */
                            kid = H5TB_swapkid(root, kid, Other(side));
                            ptr = H5TB_swapkid(root, ptr, side);
                        }
                      else
                        {   /* Just rotate parent and kid: */
                            if (HasChild(kid, side))    /* In this case, sub-tree gets */
                                if (ptr->Parent && UnBal(ptr->Parent))
                                  {
                                      deeper = 0;   /* re-lengthened after a node removed. */
                                  }
                            ptr = H5TB_swapkid(root, ptr, side);
                        }
                  }
                else if (obal)
                  {     /* Just became balanced: */
                      ptr->flags &= ~H5TB_UNBAL;
                      if (0 < deeper)
                        {   /* Shorter of legs lengthened */
                            ptr->flags |= H5TB_INTERN;  /* Mark as internal node now */
                            deeper = 0;     /* so max length unchanged */
                        }   /* end if */
                  }
                else if (deeper < 0)
                  {     /* Just became unbalanced: */
                      if (ptr->link[Other(side)] != NULL && ptr->link[Other(side)]->Parent == ptr)
                        {
                            ptr->flags |= (H5TB_flag)H5TB_HEAVY(Other(side));  /* Other side longer */
                            if (ptr->Parent) {
                                if (ptr->Parent->Rchild == ptr) {
                                    /* we're the right child */
                                    if (Heavy(ptr->Parent, RIGHT) && LeftCnt(ptr->Parent) == 1) {
                                        deeper = 0;
                                    } else {
                                        /* we're the left child */
                                        if (Heavy(ptr->Parent, LEFT)) {
                                            if (ptr->Parent->Rchild && !UnBal(ptr->Parent->Rchild)) {
                                                deeper = 0;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                  }
                else
                  {     /* Just became unbalanced: */
                      ptr->flags |= (H5TB_flag)H5TB_HEAVY(side);   /* 0<deeper: Our side longer */
                  }     /* end else */
            }
          if (ptr->Parent)
            {
                if (ptr == (ptr->Parent->Rchild))
                    side = RIGHT;
                else
                    side = LEFT;
            }   /* end if */
          ptr = ptr->Parent;    /* Move up the tree */
      }
    /* total tree depth += deeper; */
    FUNC_LEAVE(SUCCEED);
}   /* end H5TB_balance() */