diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/H5TB.c | 1418 | ||||
| -rw-r--r-- | src/H5TBprivate.h | 126 |
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 */ + |