summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorQuincey Koziol <koziol@hdfgroup.org>2000-05-08 23:08:41 (GMT)
committerQuincey Koziol <koziol@hdfgroup.org>2000-05-08 23:08:41 (GMT)
commitcf6470e7f0ddb439a77382136a708131f3255471 (patch)
treee8e91e4f4d9152846bde0b0ec0fb97b42b44c28b
parentbb7e34fad8b5f104c424236ea8dbd9860392ddc6 (diff)
downloadhdf5-cf6470e7f0ddb439a77382136a708131f3255471.zip
hdf5-cf6470e7f0ddb439a77382136a708131f3255471.tar.gz
hdf5-cf6470e7f0ddb439a77382136a708131f3255471.tar.bz2
[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.
-rw-r--r--src/H5TB.c1418
-rw-r--r--src/H5TBprivate.h126
2 files changed, 1544 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() */
+
diff --git a/src/H5TBprivate.h b/src/H5TBprivate.h
new file mode 100644
index 0000000..0cff99d
--- /dev/null
+++ b/src/H5TBprivate.h
@@ -0,0 +1,126 @@
+/*-------------------------------------------------------------------------
+ * Copyright (C) 2000 National Center for Supercomputing Applications.
+ * All rights reserved.
+ *
+ *-------------------------------------------------------------------------
+ *
+ * Created: H5TBprivate.h
+ * Apr 22 2000
+ * Quincey Koziol <koziol@ncsa.uiuc.edu>
+ *
+ * Purpose: Private non-prototype header.
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef _H5TBprivate_H
+#define _H5TBprivate_H
+
+/* Public headers needed by this file */
+#ifdef LATER
+#include <H5TBpublic.h> /*Public API prototypes */
+#endif /* LATER */
+
+/* Typedef for key comparison function */
+typedef int (*H5TB_cmp_t)(void *k1, void *k2, int cmparg);
+
+/* Shortcut macros for links */
+# define PARENT 0
+# define LEFT 1
+# define RIGHT 2
+
+# define Parent link[PARENT]
+# define Lchild link[LEFT]
+# define Rchild link[RIGHT]
+
+/* Tree-balancing flags */
+# define TBBT_HEAVY(s) s /* If the `s' sub-tree is deeper than the other */
+# define TBBT_DOUBLE 4 /* If "heavy" sub-tree is two levels deeper */
+# define TBBT_INTERN 8 /* If node is internal (has two children) */
+# define TBBT_UNBAL ( TBBT_HEAVY(LEFT) | TBBT_HEAVY(RIGHT) )
+# define TBBT_FLAGS ( TBBT_UNBAL | TBBT_INTERN | TBBT_DOUBLE )
+# define TBBT_CHILD(s) ( TBBT_INTERN | TBBT_HEAVY(s) )
+
+/* Internal macros */
+# define LeftCnt(node) ( (node)->lcnt ) /* Left descendants */
+# define RightCnt(node) ( (node)->rcnt ) /* Right descendants */
+# define Cnt(node,s) ( LEFT==(s) ? LeftCnt(node) : RightCnt(node) )
+# define HasChild(n,s) ( Cnt(n,s)>0 )
+# define Heavy(n,s) ( (s) & (LeftCnt(n)>RightCnt(n) ? LEFT : \
+ LeftCnt(n)==RightCnt(n) ? 0 : RIGHT))
+# define Intern(n) ( LeftCnt(n) && RightCnt(n) )
+# define UnBal(n) ( LeftCnt(n)>RightCnt(n) ? LEFT : \
+ LeftCnt(n)==RightCnt(n) ? 0 : RIGHT)
+# define Double(n) ( TBBT_DOUBLE & (n)->flags )
+# define Other(side) ( LEFT + RIGHT - (side) )
+# define Delta(n,s) ( ( Heavy(n,s) ? 1 : -1 ) \
+ * ( Double(n) ? 2 : UnBal(n) ? 1 : 0 ) )
+# define SetFlags(n,s,b,i) ( ( -2<(b) && (b)<2 ? 0 : TBBT_DOUBLE ) \
+ | ( 0>(b) ? TBBT_HEAVY(s) : (b)>0 ? TBBT_HEAVY(Other(s)) : 0 ) \
+ | ( (i) ? TBBT_INTERN : 0 ) )
+
+/* Internal types for flags & leaf counts */
+typedef unsigned long tbbt_flag;
+typedef unsigned long tbbt_leaf;
+
+/* Threaded node structure */
+typedef struct tbbt_node
+{
+ void * data; /* Pointer to user data to be associated with node */
+ void * key; /* Field to sort nodes on */
+
+ struct tbbt_node *link[3]; /* Pointers to parent, left child, and right child */
+ tbbt_flag flags; /* Combination of the bit fields */
+ tbbt_leaf lcnt; /* count of left children */
+ tbbt_leaf rcnt; /* count of right children */
+} TBBT_NODE;
+
+/* Threaded tree structure */
+typedef struct tbbt_tree
+{
+ TBBT_NODE *root; /* Pointer to actual root of tbbt tree */
+ unsigned long count; /* The number of nodes in the tree currently */
+ unsigned fast_compare; /* use a faster in-line compare (with casts) instead of function call */
+ H5TB_cmp_t compar; /* Key comparison function */
+ int cmparg;
+} TBBT_TREE;
+
+/* Define the "fast compare" values */
+#define TBBT_FAST_HADDR_COMPARE 1
+#define TBBT_FAST_INTN_COMPARE 2
+
+#if defined c_plusplus || defined __cplusplus
+extern "C"
+{
+#endif /* c_plusplus || __cplusplus */
+
+TBBT_TREE *H5TB_dmake (H5TB_cmp_t cmp, int arg, unsigned fast_compare);
+TBBT_NODE *H5TB_dfind (TBBT_TREE * tree, void * key, TBBT_NODE ** pp);
+TBBT_NODE *H5TB_find(TBBT_NODE * root, void * key, H5TB_cmp_t cmp,
+ int arg, TBBT_NODE ** pp);
+TBBT_NODE *H5TB_dless (TBBT_TREE * tree, void * key, TBBT_NODE ** pp);
+TBBT_NODE *H5TB_less (TBBT_NODE * root, void * key, H5TB_cmp_t cmp,
+ int arg, TBBT_NODE ** pp);
+TBBT_NODE *H5TB_index (TBBT_NODE * root, unsigned indx);
+TBBT_NODE *H5TB_dins (TBBT_TREE * tree, void * item, void * key);
+TBBT_NODE *H5TB_ins (TBBT_NODE ** root, void * item, void * key, H5TB_cmp_t cmp, int arg);
+void *H5TB_rem(TBBT_NODE ** root, TBBT_NODE * node, void * *kp);
+TBBT_NODE *H5TB_first (TBBT_NODE * root);
+TBBT_NODE *H5TB_last (TBBT_NODE * root);
+TBBT_NODE *H5TB_next (TBBT_NODE * node);
+TBBT_NODE *H5TB_prev (TBBT_NODE * node);
+TBBT_TREE *H5TB_dfree (TBBT_TREE * tree, void(*fd) (void *), void(*fk) (void *));
+void *H5TB_free (TBBT_NODE ** root, void(*fd) (void *), void(*fk) (void *));
+long H5TB_count (TBBT_TREE * tree);
+
+#ifdef H5TB_DEBUG
+herr_t H5TB_dump(TBBT_TREE *ptree, void (*key_dump)(void *,void *), intn method);
+#endif /* H5TB_DEBUG */
+
+#if defined c_plusplus || defined __cplusplus
+}
+#endif /* c_plusplus || __cplusplus */
+
+#endif /* _H5TBprivate_H */
+