[svn-r2221] Brought threaded, balanced binary tree code over from the HDF4 library and

updated it for integrating with the H5 library.  I'm thinking about using them
for the data-structures in some caching improvements I'm working on.

1 files changed, 1418 insertions, 0 deletions

diff --git a/src/H5TB.c b/src/H5TB.c
new file mode 100644
index 0000000..dc71318
--- /dev/null
+++ b/src/H5TB.c
@@ -0,0 +1,1418 @@
+/*
+ * Copyright (C) 2000 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 *) );
+ */
+
+#ifdef RCSID
+static char RcsId[] = "@(#)$Revision$";
+#endif
+
+/* $Id$ */
+
+#include <H5private.h>		/*library		  */
+#include <H5Eprivate.h>		/*error handling	  */
+#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) ? (a) : (intn)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 TBBT_NODE * H5TB_end(TBBT_NODE * root, intn side);
+static TBBT_NODE *H5TB_ffind(TBBT_NODE * root, void * key, uintn fast_compare,
+    TBBT_NODE ** pp);
+static herr_t H5TB_balance(TBBT_NODE ** root, TBBT_NODE * ptr, intn side, intn added);
+static TBBT_NODE *H5TB_swapkid(TBBT_NODE ** root, TBBT_NODE * ptr, intn side);
+static TBBT_NODE *H5TB_nbr(TBBT_NODE * ptr, intn side);
+
+#ifdef H5TB_DEBUG
+static herr_t tbbt_printNode(TBBT_NODE * node, void(*key_dump)(void *,void *));
+static herr_t tbbt_dumpNode(TBBT_NODE *node, void (*key_dump)(void *,void *),
+                          intn method);
+#endif /* H5TB_DEBUG */
+
+/* Declare a free list to manage the TBBT_NODE struct */
+H5FL_DEFINE_STATIC(TBBT_NODE);
+
+#define PABLO_MASK	H5TB_mask
+static intn		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();
+ *     TBBT_ROOT *root= H5TB_dmake( keycmp, (int)keysiz , 0);
+ * or
+ *     void *root= H5TB_dmake( strcmp, 0 , 0);
+ * or
+ *     void *root= H5TB_dmake( keycmp, (int)keysiz , TBBT_FAST_HADDR_COMPARE);
+ * or
+ *     TBBT_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 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= H5TB_dmake( NULL, 0 );
+ * is equivalent to
+ *     TBBT_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
+ *     TBBT_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 TBBT tree
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Saturday, April 22, 2000
+ *
+ * Modifications:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+TBBT_TREE  *
+H5TB_dmake(H5TB_cmp_t cmp, intn arg, uintn fast_compare)
+{
+    TBBT_TREE  *tree;
+
+    FUNC_ENTER (H5TB_dmake, NULL);
+
+    if (NULL == (tree = H5MM_malloc(sizeof(TBBT_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 TBBT node
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Thursday, May 5, 2000
+ *
+ * Modifications:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+TBBT_NODE  *
+H5TB_dfind(TBBT_TREE * tree, void * key, TBBT_NODE ** pp)
+{
+    TBBT_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 TBBT node
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Thursday, May 5, 2000
+ *
+ * Modifications:
+ * 
+ * Notes:
+ *  H5TB_ffind is based on this routine - fix bugs in both places!
+ * 	
+ *-------------------------------------------------------------------------
+ */
+TBBT_NODE  *
+H5TB_find(TBBT_NODE * root, void * key,
+     H5TB_cmp_t compar, intn arg, TBBT_NODE ** pp)
+{
+    TBBT_NODE  *ptr = root;
+    TBBT_NODE  *parent = NULL;
+    intn        cmp = 1;
+    intn        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 TBBT node
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Thursday, May 5, 2000
+ *
+ * Modifications:
+ * 
+ * Notes:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+TBBT_NODE  *
+H5TB_dless(TBBT_TREE * tree, void * key, TBBT_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 TBBT node
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Thursday, May 5, 2000
+ *
+ * Modifications:
+ * 
+ * Notes:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+TBBT_NODE  *
+H5TB_less(TBBT_NODE * root, void * key, H5TB_cmp_t compar, intn arg, TBBT_NODE ** pp)
+{
+    TBBT_NODE  *ptr = root;
+    TBBT_NODE  *parent = NULL;
+    intn        cmp = 1;
+    intn        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 TBBT node
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Friday, May 6, 2000
+ *
+ * Modifications:
+ * 
+ * Notes:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+TBBT_NODE  *
+H5TB_index(TBBT_NODE * root, unsigned indx)
+{
+    TBBT_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 TBBT node
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Friday, May 6, 2000
+ *
+ * Modifications:
+ * 
+ * Notes:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+TBBT_NODE  *
+H5TB_dins(TBBT_TREE * tree, void * item, void * key)
+{
+    TBBT_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 TBBT node
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Friday, May 6, 2000
+ *
+ * Modifications:
+ * 
+ * Notes:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+TBBT_NODE  *
+H5TB_ins(TBBT_NODE ** root, void * item, void * key, H5TB_cmp_t compar, intn arg)
+{
+    intn        cmp;
+    TBBT_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(TBBT_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(TBBT_NODE ** root, TBBT_NODE * node, void * *kp)
+{
+    TBBT_NODE  *leaf;   /* Node with one or zero children */
+    TBBT_NODE  *par;    /* Parent of `leaf' */
+    TBBT_NODE  *next;   /* Next/prev node near `leaf' (`leaf's `side' thread) */
+    intn        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 = (intn) 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(TBBT_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 &= (tbbt_flag)(~(TBBT_INTERN | TBBT_HEAVY(side)));
+      } /* end if */
+    /* Case 1: `leaf' has one child: */
+    else {
+          TBBT_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(TBBT_NODE,leaf);
+    H5TB_balance(root, par, side, -1);
+
+done:
+    ((TBBT_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 TBBT node
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Friday, May 6, 2000
+ *
+ * Modifications:
+ * 
+ * Notes:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+TBBT_NODE  *
+H5TB_first(TBBT_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 TBBT node
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Friday, May 6, 2000
+ *
+ * Modifications:
+ * 
+ * Notes:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+TBBT_NODE  *
+H5TB_last(TBBT_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 TBBT node
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Friday, May 6, 2000
+ *
+ * Modifications:
+ * 
+ * Notes:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+TBBT_NODE  *
+H5TB_next(TBBT_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 TBBT node
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Friday, May 6, 2000
+ *
+ * Modifications:
+ * 
+ * Notes:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+TBBT_NODE  *
+H5TB_prev(TBBT_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:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+TBBT_TREE  *
+H5TB_dfree(TBBT_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(TBBT_NODE ** root, void(*fd) (void * /* item */), void(*fk) (void * /* key */))
+{
+    TBBT_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(TBBT_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(TBBT_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(TBBT_TREE *tree, void (*key_dump)(void *,void *), intn method)
+{
+    FUNC_ENTER(H5TB_dump,FAIL);
+
+	printf("TBBT-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(TBBT_NODE * node, void(*key_dump)(void *,void *))
+{
+    FUNC_ENTER(H5TB_printNode,FAIL);
+
+    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(TBBT_NODE *node, void (*key_dump)(void *,void *),
+                        intn method)
+{
+    FUNC_ENTER(H5TB_dumpNode,FAIL);
+
+    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 TBBT_NODE *
+H5TB_end(TBBT_NODE * root, intn side)
+{
+    FUNC_ENTER (H5TB_end, NULL);
+
+    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 TBBT_NODE *
+H5TB_nbr(TBBT_NODE * ptr, intn side)
+{
+    FUNC_ENTER (H5TB_nbr, NULL);
+
+    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 TBBT_NODE  *
+H5TB_ffind(TBBT_NODE * root, void * key, uintn fast_compare, TBBT_NODE ** pp)
+{
+    TBBT_NODE  *ptr = root;
+    TBBT_NODE  *parent = NULL;
+    intn        side;
+    intn        cmp = 1;
+
+    FUNC_ENTER (H5TB_ffind, NULL);
+
+    switch(fast_compare) {
+        case TBBT_FAST_HADDR_COMPARE:
+            if (ptr) {
+                while (0 != (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;
+            break;
+
+        case TBBT_FAST_INTN_COMPARE:
+            if (ptr) {
+                while (0 != (cmp = (*(intn *)key - *(intn *)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;
+            break;
+
+        default:
+            break;
+    } /* end switch */
+
+    FUNC_LEAVE((0 == cmp) ? ptr : NULL);
+} /* 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 TBBT_NODE *
+H5TB_swapkid(TBBT_NODE ** root, TBBT_NODE * ptr, intn side)
+{
+    TBBT_NODE  *kid = ptr->link[side];  /* Sibling to be swapped with parent */
+    intn        deep[3];        /* Relative depths of three sub-trees involved. */
+    /* 0:ptr->link[Other(side)], 1:kid->link[Other(side)], 2:kid->link[side] */
+    tbbt_flag   ptrflg;         /* New value for ptr->flags (ptr->flags used after set) */
+    tbbt_leaf   plcnt, prcnt,   /* current values of the ptr's and kid's leaf count */
+                klcnt, krcnt;
+
+    FUNC_ENTER (H5TB_swapkid, NULL);
+
+    deep[2] = (deep[1] = 0) + Delta(kid, side);
+    deep[0] = Max(0, deep[2]) + 1 - Delta(ptr, side);
+    kid->Parent = ptr->Parent;
+    ptrflg = (tbbt_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 = (tbbt_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(TBBT_NODE ** root, TBBT_NODE * ptr, intn side, intn added)
+{
+    intn        deeper = added; /* 1 if sub-tree got longer; -1 if got shorter */
+    intn        odelta;
+    intn        obal;
+
+    FUNC_ENTER(H5TB_balance,FAIL);
+
+    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: */
+                      TBBT_NODE  *kid;
+
+                      ptr->flags |= TBBT_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 &= ~TBBT_UNBAL;
+                      if (0 < deeper)
+                        {   /* Shorter of legs lengthened */
+                            ptr->flags |= TBBT_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 |= (tbbt_flag)TBBT_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 |= (tbbt_flag)TBBT_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() */
+