/* // Copyright 2002 Compaq Information Technologies Group, L.P. // // Compaq and the Compaq logo are trademarks of Compaq Information // Technologies Group, L.P. in the U.S. and/or other countries. // // Confidential computer software. Valid license from Compaq // required for possession, use or copying. Consistent with // FAR 12.211 and 12.212, Commercial Computer Software, Computer // Software Documentation, and Technical Data for Commercial // Items are licensed to the U.S. Government under vendor's // standard commercial license. */ /* **++ ** FACILITY: CRTL ** ** MODULE DESCRIPTION: ** ** tsearch/tfind/tdelete/twalk implement binary search trees ** (loosely) based on Knuth's algorithms. ** ** AUTHORS: ** ** Stephen Hoffman ** ** CREATION DATE: 12-Jun-1991 ** ** DESIGN ISSUES: ** ** ULTRIX compatibility: ** These routines produce trees identical to those produced by the ** tsearch tree routines in the ULTRIX system library. Tests were ** run using the same test program running on VMS V5.4-2 and on ** ULTRIX V4.2 (rev 96). ** ** MODIFICATION HISTORY: ** **-- */ /* ** ** INCLUDE FILES ** */ #include #include #include "tsearch.h" /* ** Local (internal) routines... */ static void * ttraverse( void *key,void **rootp, int (*compar)(), void *parent, int *ambidextrous ); static void twalk_recur( struct tree_node *q, void (*user_action)(), int level ); /* **++ ** FUNCTIONAL DESCRIPTION: ** ** tsearch tree search subroutine. this subroutine returns a pointer ** to a pointer to part of a binary tree; the pointer is the address ** of a matching node. (despite what the ULTRIX man page seems to ** imply, this is what ULTRIX actually does.) ** ** ** FORMAL PARAMETERS: ** ** void *key: ** the key to be searched for. If the key is not found, ** the subroutine inserts it into the binary tree, and ** returns it as the output value. ** ** void **rootp: ** the pointer to the root of the binary tree. A NULL pointer ** indicates an empty tree; in this case the root node pointer ** will be set to the key node, and a NULL pointer will be ** returned. ** ** int (*compar)(): ** the address of a user subroutine used to make the node ** comparisons. It is called with two arguments; pointers to ** the nodes being compared. It must return an integer less ** than, equal to, or greater than zero if the first argument ** is to be considered less than, equal to, or greater than ** the second argument. ** ** RETURN VALUE: ** ** Node pointer ** ** SIDE EFFECTS: ** ** None ** ** DESIGN: ** ** Based on Knuth 6.2.2 Algorithms. ** ** **-- */ extern void *tsearch (void *key, void **rootp, int (*compar)() ) { struct tree_node *t_curr, *t_parent; void *retnode; int ambidextrous; /* ** First, go find the node. ttraverse returns a pointer to ** the descriptor of the matching node (the descriptor is ** where the pointers are kept; it is the structure that ** maintains the structure and links of the binary tree.) */ t_curr = ttraverse( key, rootp, compar, &t_parent, &ambidextrous ); /* ** Three possiblities here: ** o The tree should be created ( amb == 0, t_curr == 0)... ** o We found the node (amb == 0 && t_curr != 0)... ** o We didn't find the node ( amb != 0)... ** - key > node (amb > 0): new node would be on t_curr hiside. ** - key < node (amb < 0): new node would be on t_curr loside. */ if ( ambidextrous < 0 ) { t_curr = malloc( sizeof( struct tree_node )); if ( !(int) t_curr ) return 0; t_curr->t_lo = t_parent->t_lo; t_curr->t_hi = 0; t_parent->t_lo = t_curr; t_curr->t_node = key; retnode = &t_curr->t_node; #if TSEARCH_DEBUG | TSEARCH_TSEARCH print_family( t_parent, t_curr, "tsearch(): tree insertion, on low side."); #endif } if ( ambidextrous > 0 ) { t_curr = malloc( sizeof( struct tree_node )); if ( !(int) t_curr ) return 0; t_curr->t_lo = 0; t_curr->t_hi = t_parent->t_hi; t_parent->t_hi = t_curr; t_curr->t_node = key; retnode = &t_curr->t_node; #if TSEARCH_DEBUG | TSEARCH_TSEARCH print_family( t_parent, t_curr, "tsearch(): tree insertion, on high side."); #endif } if ( ambidextrous == 0 ) { if ( (int) t_curr == 0 ) { /* ** Both are null if this is the first ** insertion into the binary tree. */ t_curr = *rootp = malloc( sizeof( struct tree_node )); if ( !(int) t_curr ) return 0; t_curr->t_lo = t_curr->t_hi = 0; t_curr->t_node = key; retnode = &t_curr->t_node; #if TSEARCH_DEBUG | TSEARCH_TSEARCH print_family( 0, retnode, "tsearch(): root created." ); #endif } else { /* ** The target node was matched. */ retnode = &t_curr->t_node; #if TSEARCH_DEBUG | TSEARCH_TSEARCH print_family( 0, retnode, "tsearch(): node located." ); #endif } } return retnode; } /* **++ ** FUNCTIONAL DESCRIPTION: ** ** tfind tree search subroutine. this subroutine returns a pointer to ** part of a binary tree; the pointer is the address of a matching node. ** This routine differs from tsearch only when the key is not found in ** the tree -- this routine returns a NULL, tsearch inserts the key. ** ** FORMAL PARAMETERS: ** ** void *key: ** the key to be searched for. Subroutine returns NULL if the ** key is not found. ** ** void **rootp: ** the pointer to the root of the binary tree. A NULL pointer ** indicates an empty tree; in this case the root node pointer ** will be set to the key node, and a NULL pointer will be ** returned. ** ** int (*compar)(): ** the address of a user subroutine used to make the node ** comparisons. It is called with two arguments; pointers to ** the nodes being compared. It must return an integer less ** than, equal to, or greater than zero if the first argument ** is to be considered less than, equal to, or greater than ** the second argument. ** [@additional subtags@]... ** ** RETURN VALUE: ** ** Node pointer ** ** SIDE EFFECTS: ** ** None ** ** DESIGN: ** ** Based on Knuth 6.2.2 Algorithm T. ** ** **-- */ extern void *tfind (void *key, void **rootp, int (*compar)() ) { struct tree_node *t_curr; void *retnode; #if TSEARCH_DEBUG | TSEARCH_TFIND print_family( 0, key, "tfind(): find commencing. Key:" ); #endif t_curr = ttraverse( key, rootp, compar, 0, 0 ); /* ** ttraverse returns a pointer to the matching ** node block, or a zero if a match was not found. ** (Avoid indirection through a null pointer, too.) */ if ( (int) t_curr ) retnode = &t_curr->t_node; else retnode = 0; return retnode; } /* **++ ** FUNCTIONAL DESCRIPTION: ** ** tdelete tree node deletion subroutine. this subroutine returns a ** pointer to part of a binary tree; the pointer is the address of a ** matching node. The node is deleted by this routine. If the node ** is the root node, tdelete adjusts the root node pointer. ** ** FORMAL PARAMETERS: ** ** void *key: ** the key to be searched for. Subroutine returns NULL if the ** key is not found. ** ** void **rootp: ** the pointer to the root of the binary tree. A NULL pointer ** indicates an empty tree; in this case the root node pointer ** will be set to the key node, and a NULL pointer will be ** returned. ** ** int (*compar)(): ** the address of a user subroutine used to make the node ** comparisons. It is called with two arguments; pointers to ** the nodes being compared. It must return an integer less ** than, equal to, or greater than zero if the first argument ** is to be considered less than, equal to, or greater than ** the second argument. ** [@additional subtags@]... ** ** RETURN VALUE: ** ** Node pointer ** ** SIDE EFFECTS: ** ** None ** ** DESIGN: ** ** Based on Knuth 6.2.2 Algorithm D. ** ** **-- */ extern void * tdelete (void *key, void **rootp, int (*compar)() ) { struct tree_node *t_parent, *q, *r, *s, *t, *tbf; void *retnode; int *target; #if TSEARCH_DEBUG | TSEARCH_TDELETE print_family( 0, key, "tdelete(): Deletion commencing. Key:" ); #endif q = tbf = ttraverse( key, rootp, compar, &t_parent, 0 ); #if TSEARCH_DEBUG | TSEARCH_TDELETE print_family( 0, (int) q, "tdelete(): the target is in sight:" ); #endif /* ** If the target node was not found, back out. */ if ( (void *) q == NULL ) { #if TSEARCH_DEBUG | TSEARCH_TDELETE print_family( 0, 0, "tdelete(): The specified node was not located." ); #endif return NULL; } /* ** The target node has been located. Start with a slight ** variant of Knuth's 6.6.2 Algorithm D. ** ** Locate the address of the pointer that references the node ** at ground zero. If it is the root node, point to it. In ** either case, set the retnode value correctly. */ if ( t_parent ) { retnode = &t_parent->t_node; if ( t_parent->t_lo == q ) target = (int *) &(t_parent->t_lo); else target = (int *) &(t_parent->t_hi); #if TSEARCH_DEBUG | TSEARCH_TDELETE print_family( t_parent, q, "tdelete(): node was located; the family is:" ); #endif } else { /* ** ULTRIX, for some undocumented reason, returns the ** address of the root node, if the root node is what ** gets deleted. */ target = (int *) rootp; retnode = &tbf->t_node; #if TSEARCH_DEBUG | TSEARCH_TDELETE print_family( 0, 0, "tdelete(): node was located; it is the root node." ); #endif } t = q; /* ** D1: Is the loside Null? (This one is relatively easy to deal ** with, just pull the high side up one level.) */ if ( t->t_lo == NULL ) { #if TSEARCH_DEBUG | TSEARCH_TDELETE print_family( 0, t, "tdelete(): D1: loside is null. Current node:" ); #endif q = t->t_hi; goto D4; } /* ** D1½: hiside optimization (This one works the same as the ** last test -- only it pulls the low side up one level.) */ if ( t->t_hi == NULL ) { #if TSEARCH_DEBUG | TSEARCH_TDELETE print_family( 0, t, "tdelete(): D1½: hiside is null. Current node:" ); #endif q = t->t_lo; goto D4; } /* ** D2 find the successor. */ r = t->t_hi; if ( r->t_lo == NULL ) { #if TSEARCH_DEBUG | TSEARCH_TDELETE print_family( 0, r, "tdelete(): passing D2." ); #endif r->t_lo = t->t_lo; q = r; goto D4; } /* ** D3 find a null loside */ s = t->t_hi; while ( s->t_lo != NULL ) { #if TSEARCH_DEBUG | TSEARCH_TDELETE print_family( 0, 0, "tdelete(): looking for a null hiside (D3)." ); print_family( 0, r, "tdelete(): D3/r." ); print_family( 0, s, "tdelete(): D3/s." ); print_family( 0, t, "tdelete(): D3/t." ); #endif r = s; s = r->t_lo; } s->t_lo = t->t_lo; r->t_lo = s->t_hi; s->t_hi = t->t_hi; q = s; D4: /* ** The D4 step (Knuth's idea of a name, not mine) updates only ** the in-memory pointer. We have to update the parent node ** pointer, the pointer that references the target node. */ *target = (int) q; free ( tbf ); #if TSEARCH_DEBUG | TSEARCH_TDELETE print_family( t_parent, q, "tdelete(): going where no one has gone: D4." ); #endif return retnode; } /* **++ ** FUNCTIONAL DESCRIPTION: ** ** twalk tree walking subroutine. this subroutine walks through ** the tree calling the specified action routine for each node. ** The action routine is called with preorder, postorder, endorder ** or leaf if the node has been visited once, twice, thrice, or ** is a leaf node, respectively. ** ** FORMAL PARAMETERS: ** ** void **rootp: ** the pointer to the root of the binary tree. ** ** int (*action)(): ** the address of a user subroutine called for each node in ** the tree. The action routine is called with three arguments, ** the first is the address of the node being visited, the second ** is the aforementioned preorder, postorder, endorder or leaf, ** (as defined in an enum in ) and the third is the ** level or depth of the node into the tree, the root node is ** at level 0. ** [@additional subtags@]... ** ** RETURN VALUE: ** ** Node pointer ** ** SIDE EFFECTS: ** ** None ** ** DESIGN: ** ** Not really based on anything. ** ** **-- */ extern void twalk( void *q, void (*action)() ) { /* ** The following is a recursive call to the tree-walking code. ** The following is not (knowingly) based on any particular ** Knuth algorithm, as the ULTRIX man page doesn't indicate ** twalk is based on any specific algorithm. */ #if TSEARCH_DEBUG | TSEARCH_TWALK print_family( 0, q, "twalk(): going out for a walk." ); #endif if ( q != NULL ) twalk_recur( q, action, 0 ); return; } static void twalk_recur( struct tree_node *q, void (*user_action)(), int level ) { #if TSEARCH_DEBUG | TSEARCH_TWALK_RECUR print_family( 0, q, "twalk(): twalk recursive routine called." ); #endif if (( q->t_lo == NULL ) && ( q->t_hi == NULL )) { #if TSEARCH_DEBUG | TSEARCH_TWALK_RECUR print_family( 0, q, "twalk(): twalk leaf node." ); #endif /* ** Both the low and the high side are null: we are ** definitely looking at a leaf node. Call the user ** routine and start backing out of this branch. */ user_action( &q->t_node, leaf, level ); } else { #if TSEARCH_DEBUG | TSEARCH_TWALK_RECUR print_family( 0, q, "twalk(): twalk non-leaf node." ); #endif user_action( &q->t_node, preorder, level ); if ( q->t_lo != NULL ) { /* ** The low side has a child. Continue the traversal ** downward; looking for the bottom. */ #if TSEARCH_DEBUG | TSEARCH_TWALK_RECUR print_family( q, q->t_lo, "twalk(): loside non-null, twalk going lower." ); #endif twalk_recur( q->t_lo, user_action, ( level + 1) ); user_action( &q->t_node, postorder, level ); } else { #if TSEARCH_DEBUG | TSEARCH_TWALK_RECUR print_family( q, q->t_lo, "twalk(): loside null, twalk can go no lower." ); #endif user_action( &q->t_node, postorder, level ); } if ( q->t_hi != NULL ) { /* ** The high side has a child. Continue the traversal ** downward; looking for the bottom. */ #if TSEARCH_DEBUG | TSEARCH_TWALK_RECUR print_family( q, q->t_hi, "twalk(): hiside non-null, twalk going higher." ); #endif twalk_recur( q->t_hi, user_action, ( level + 1) ); user_action( &q->t_node, endorder, level ); } else { #if TSEARCH_DEBUG | TSEARCH_TWALK_RECUR print_family( 0, q, "twalk(): hiside null, twalk unwinding." ); #endif user_action( &q->t_node, endorder, level ); } } return; } /* **++ ** FUNCTIONAL DESCRIPTION: ** ** ttraverse is the subroutine used to walk the tree by most ** of the other subroutines in this file. ** ** FORMAL PARAMETERS: ** ** void *key: ** the key to be searched for. If the key is not found, ** the subroutine inserts it into the binary tree, and ** returns it as the output value. ** ** void **rootp: ** the pointer to the root of the binary tree. A NULL pointer ** indicates an empty tree; in this case the root node pointer ** will be set to the key node, and a NULL pointer will be ** returned. ** ** int (*compar)(): ** the address of a user subroutine used to make the node ** comparisons. It is called with two arguments; pointers to ** the nodes being compared. It must return an integer less ** than, equal to, or greater than zero if the first argument ** is to be considered less than, equal to, or greater than ** the second argument. ** ** parent: ** the parent node of the matching node, or, if the subroutine ** is unable to match the specified key (the function will have ** a return status of NULL in this case), parent will point to the ** node that would be the parent had the key been found. If ** the node that matches the key is the root of the tree, parent ** will be NULL. ** ** ambidextrous: ** returns less than zero, equal to zero or greater than zero ** to indicate that the key would be placed as the left child ** or parent, was actually located/matched, or would be placed ** as the right child of the parent node. ** ** RETURN VALUE: ** ** pointer to the tree block that matches the specified key, or ** a NULL if no match was found or if the tree root was NULL. ** ** SIDE EFFECTS: ** ** NONE ** ** DESIGN: ** ** **-- */ static void * ttraverse(void *key,void **rootp, int (*compar)(), void *parent, int *ambidextrous ) { struct tree_node *p; int *mom, *amb; int dad, chrysler_lug_thread, twotone; /* ** Apply some defaults up front so that we can ignore the ** various was-it-or-wasn't-it-specified cases later on. ** ** (for the curious, various Chrysler corporation product models ** have used right *and* left handed lug threading on the same ** vehicle; the threading used depended on which side of the ** vehicle the lug nut was on.) */ mom = parent ? parent : &dad; amb = ambidextrous ? ambidextrous : &chrysler_lug_thread; /* ** "t1": initialize */ p = *rootp; *amb = *mom = 0; /* ** If the tree root is NULL, there can be no match, so return NULL. */ if ( (void *) p == NULL ) { #if TSEARCH_DEBUG | TSEARCH_ttraverse print_family( 0, 0, "ttraverse(): null root." ); #endif return NULL; } do { /* ** compare the two nodes. The ULTRIX documention ** implies the comparison "compar( p, key )" but ** tests indicate "compar( key, p )" is used. */ *amb = compar( key, p->t_node ); /* ** If the current node matches the key, success! */ if ( *amb == 0 ) break; /* ** Prepare the backlink pointer... ** ...then traverse further down the tree. */ *mom = (int) p; /* ** If the current node in the tree compares above the specified ** key, move to the low side. */ if ( *amb < 0 ) { p = p->t_lo; #if TSEARCH_DEBUG | TSEARCH_ttraverse print_family( p, ((int) p ? p->t_lo : 0), "ttraverse(): new node < tree node, going lower."); #endif } /* ** If the current node compares below the specified key, move ** to the high side. */ if ( *amb > 0 ) { p = p->t_hi; #if TSEARCH_DEBUG | TSEARCH_ttraverse print_family( p, ((int) p ? p->t_hi : 0 ), "ttraverse(): new node > tree node, going higher."); #endif } } while ( p != NULL ); #if TSEARCH_DEBUG | TSEARCH_ttraverse print_family( 0, 0, "ttraverse(): traversal complete." ); #endif return p; } #define TSEARCH_PRINT \ (TSEARCH_DEBUG|TSEARCH_TWALK|TSEARCH_TDELETE|\ TSEARCH_TSEARCH|TSEARCH_TFIND|TSEARCH_TWALK_RECUR) #if TSEARCH_PRINT /* ** Utility print routine. Used for debugging. Prints zero, one or ** two specified nodes. Implicit assumption (as far as the text that ** gets printed) is that the second node specified is a child of the ** first. Either or both arguments can be specified as null. */ print_family( struct tree_node *p, struct tree_node *c, char *msg ) { printf("# %s\n", msg ); if ( (int) p ) printf("# parent node: %08.8x [lo: %08.8x, hi: %08.8x]\n", (int) p, (int) p->t_lo, (int) p->t_hi ); if ( (int) c ) printf("# current node: %08.8x [lo: %08.8x, hi: %08.8x]\n", (int) c, (int) c->t_lo, (int) c->t_hi ); return; } #endif