1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713
|
#ifndef UBI_BINTREE_H
#define UBI_BINTREE_H
/* $Id: ubi_BinTree.h,v 1.4 2004/02/02 18:49:51 droelker Exp $ */
/* ========================================================================== **
* ubi_BinTree.h
*
* Copyright (C) 1991-1998 by Christopher R. Hertel
*
* Email: crh@ubiqx.mn.org
* -------------------------------------------------------------------------- **
*
* This module implements a simple binary tree.
*
* -------------------------------------------------------------------------- **
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License along with this library; if not, write to the Free
* Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*
* ========================================================================== **
*/
#include "sys_include.h" /* Global include file, used to adapt the ubiqx
* modules to the host environment and the project
* with which the modules will be used. See
* sys_include.h for more info.
*/
/* -------------------------------------------------------------------------- **
* Macros and constants.
*
* General purpose:
* ubi_trTRUE - Boolean TRUE.
* ubi_trFALSE - Boolean FALSE.
*
* Flags used in the tree header:
* ubi_trOVERWRITE - This flag indicates that an existing node may be
* overwritten by a new node with a matching key.
* ubi_trDUPKEY - This flag indicates that the tree allows duplicate
* keys. If the tree does allow duplicates, the
* overwrite flag is ignored.
*
* Node link array index constants: (Each node has an array of three
* pointers. One to the left, one to the right, and one back to the
* parent.)
* ubi_trLEFT - Left child pointer.
* ubi_trPARENT - Parent pointer.
* ubi_trRIGHT - Right child pointer.
* ubi_trEQUAL - Synonym for PARENT.
*
* ubi_trCompOps: These values are used in the ubi_trLocate() function.
* ubi_trLT - request the first instance of the greatest key less than
* the search key.
* ubi_trLE - request the first instance of the greatest key that is less
* than or equal to the search key.
* ubi_trEQ - request the first instance of key that is equal to the
* search key.
* ubi_trGE - request the first instance of a key that is greater than
* or equal to the search key.
* ubi_trGT - request the first instance of the first key that is greater
* than the search key.
* -------------------------------------------------------------------------- **
*/
#define ubi_trTRUE 0xFF
#define ubi_trFALSE 0x00
#define ubi_trOVERWRITE 0x01 /* Turn on allow overwrite */
#define ubi_trDUPKEY 0x02 /* Turn on allow duplicate keys */
/* Pointer array index constants... */
#define ubi_trLEFT 0x00
#define ubi_trPARENT 0x01
#define ubi_trRIGHT 0x02
#define ubi_trEQUAL ubi_trPARENT
typedef enum {
ubi_trLT = 1,
ubi_trLE,
ubi_trEQ,
ubi_trGE,
ubi_trGT
} ubi_trCompOps;
/* -------------------------------------------------------------------------- **
* These three macros allow simple manipulation of pointer index values (LEFT,
* RIGHT, and PARENT).
*
* Normalize() - converts {LEFT, PARENT, RIGHT} into {-1, 0 ,1}. C
* uses {negative, zero, positive} values to indicate
* {less than, equal to, greater than}.
* AbNormal() - converts {negative, zero, positive} to {LEFT, PARENT,
* RIGHT} (opposite of Normalize()). Note: C comparison
* functions, such as strcmp(), return {negative, zero,
* positive} values, which are not necessarily {-1, 0,
* 1}. This macro uses the the ubi_btSgn() function to
* compensate.
* RevWay() - converts LEFT to RIGHT and RIGHT to LEFT. PARENT (EQUAL)
* is left as is.
* -------------------------------------------------------------------------- **
*/
#define ubi_trNormalize(W) ((char)( (W) - ubi_trEQUAL ))
#define ubi_trAbNormal(W) ((char)( ((char)ubi_btSgn( (long)(W) )) \
+ ubi_trEQUAL ))
#define ubi_trRevWay(W) ((char)( ubi_trEQUAL - ((W) - ubi_trEQUAL) ))
/* -------------------------------------------------------------------------- **
* These macros allow us to quickly read the values of the OVERWRITE and
* DUPlicate KEY bits of the tree root flags field.
* -------------------------------------------------------------------------- **
*/
#define ubi_trDups_OK(A) \
((ubi_trDUPKEY & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE))
#define ubi_trOvwt_OK(A) \
((ubi_trOVERWRITE & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE))
/* -------------------------------------------------------------------------- **
* Additional Macros...
*
* ubi_trCount() - Given a pointer to a tree root, this macro returns the
* number of nodes currently in the tree.
*
* ubi_trNewTree() - This macro makes it easy to declare and initialize a
* tree header in one step. The line
*
* static ubi_trNewTree( MyTree, cmpfn, ubi_trDUPKEY );
*
* is equivalent to
*
* static ubi_trRoot MyTree[1]
* = {{ NULL, cmpfn, 0, ubi_trDUPKEY }};
*
* -------------------------------------------------------------------------- **
*/
#define ubi_trCount( R ) (((ubi_trRootPtr)(R))->count)
#define ubi_trNewTree( N, C, F ) ubi_trRoot (N)[1] = {{ NULL, (C), 0, (F) }}
/* -------------------------------------------------------------------------- **
* Typedefs...
*
* ubi_trBool - Your typcial true or false...
*
* Item Pointer: The ubi_btItemPtr is a generic pointer. It is used to
* indicate a key that is being searched for within the tree.
* Searching occurs whenever the ubi_trFind(), ubi_trLocate(),
* or ubi_trInsert() functions are called.
* -------------------------------------------------------------------------- **
*/
typedef unsigned char ubi_trBool;
typedef void *ubi_btItemPtr; /* A pointer to key data within a node. */
/* ------------------------------------------------------------------------- **
* Binary Tree Node Structure: This structure defines the basic elements of
* the tree nodes. In general you *SHOULD NOT PLAY WITH THESE FIELDS*!
* But, of course, I have to put the structure into this header so that
* you can use it as a building block.
*
* The fields are as follows:
* Link - an array of pointers. These pointers are manipulated by
* the BT routines. The pointers indicate the left and right
* child nodes and the parent node. By keeping track of the
* parent pointer, we avoid the need for recursive routines or
* hand-tooled stacks to keep track of our path back to the
* root. The use of these pointers is subject to change without
* notice.
* gender - a one-byte field indicating whether the node is the RIGHT or
* LEFT child of its parent. If the node is the root of the
* tree, gender will be PARENT.
* balance - only used by the AVL tree module. This field indicates
* the height balance at a given node. See ubi_AVLtree for
* details.
*
* ------------------------------------------------------------------------- **
*/
typedef struct ubi_btNodeStruct {
struct ubi_btNodeStruct *Link[ 3 ];
char gender;
char balance;
} ubi_btNode;
typedef ubi_btNode *ubi_btNodePtr; /* Pointer to an ubi_btNode structure. */
/* ------------------------------------------------------------------------- **
* The next three typedefs define standard function types used by the binary
* tree management routines. In particular:
*
* ubi_btCompFunc is a pointer to a comparison function. Comparison
* functions are passed an ubi_btItemPtr and an
* ubi_btNodePtr. They return a value that is (<0), 0,
* or (>0) to indicate that the Item is (respectively)
* "less than", "equal to", or "greater than" the Item
* contained within the node. (See ubi_btInitTree()).
* ubi_btActionRtn is a pointer to a function that may be called for each
* node visited when performing a tree traversal (see
* ubi_btTraverse()). The function will be passed two
* parameters: the first is a pointer to a node in the
* tree, the second is a generic pointer that may point to
* anything that you like.
* ubi_btKillNodeRtn is a pointer to a function that will deallocate the
* memory used by a node (see ubi_btKillTree()). Since
* memory management is left up to you, deallocation may
* mean anything that you want it to mean. Just remember
* that the tree *will* be destroyed and that none of the
* node pointers will be valid any more.
* ------------------------------------------------------------------------- **
*/
typedef int (*ubi_btCompFunc)( ubi_btItemPtr, ubi_btNodePtr );
typedef void (*ubi_btActionRtn)( ubi_btNodePtr, void * );
typedef void (*ubi_btKillNodeRtn)( ubi_btNodePtr );
/* -------------------------------------------------------------------------- **
* Tree Root Structure: This structure gives us a convenient handle for
* accessing whole binary trees. The fields are:
* root - A pointer to the root node of the tree.
* count - A count of the number of nodes stored in the tree.
* cmp - A pointer to the comparison routine to be used when building or
* searching the tree.
* flags - A set of bit flags. Two flags are currently defined:
*
* ubi_trOVERWRITE - If set, this flag indicates that a new node should
* (bit 0x01) overwrite an old node if the two have identical
* keys (ie., the keys are equal).
* ubi_trDUPKEY - If set, this flag indicates that the tree is
* (bit 0x02) allowed to contain nodes with duplicate keys.
*
* NOTE: ubi_trInsert() tests ubi_trDUPKEY before ubi_trOVERWRITE.
*
* All of these values are set when you initialize the root structure by
* calling ubi_trInitTree().
* -------------------------------------------------------------------------- **
*/
typedef struct {
ubi_btNodePtr root; /* A pointer to the root node of the tree */
ubi_btCompFunc cmp; /* A pointer to the tree's comparison function */
unsigned long count; /* A count of the number of nodes in the tree */
char flags; /* Overwrite Y|N, Duplicate keys Y|N... */
} ubi_btRoot;
typedef ubi_btRoot *ubi_btRootPtr; /* Pointer to an ubi_btRoot structure. */
/* -------------------------------------------------------------------------- **
* Function Prototypes.
*/
long ubi_btSgn( long x );
/* ------------------------------------------------------------------------ **
* Return the sign of x; {negative,zero,positive} ==> {-1, 0, 1}.
*
* Input: x - a signed long integer value.
*
* Output: the "sign" of x, represented as follows:
* -1 == negative
* 0 == zero (no sign)
* 1 == positive
*
* Note: This utility is provided in order to facilitate the conversion
* of C comparison function return values into BinTree direction
* values: {LEFT, PARENT, EQUAL}. It is INCORPORATED into the
* AbNormal() conversion macro!
*
* ------------------------------------------------------------------------ **
*/
ubi_btNodePtr ubi_btInitNode( ubi_btNodePtr NodePtr );
/* ------------------------------------------------------------------------ **
* Initialize a tree node.
*
* Input: a pointer to a ubi_btNode structure to be initialized.
* Output: a pointer to the initialized ubi_btNode structure (ie. the
* same as the input pointer).
* ------------------------------------------------------------------------ **
*/
ubi_btRootPtr ubi_btInitTree( ubi_btRootPtr RootPtr,
ubi_btCompFunc CompFunc,
char Flags );
/* ------------------------------------------------------------------------ **
* Initialize the fields of a Tree Root header structure.
*
* Input: RootPtr - a pointer to an ubi_btRoot structure to be
* initialized.
* CompFunc - a pointer to a comparison function that will be used
* whenever nodes in the tree must be compared against
* outside values.
* Flags - One bytes worth of flags. Flags include
* ubi_trOVERWRITE and ubi_trDUPKEY. See the header
* file for more info.
*
* Output: a pointer to the initialized ubi_btRoot structure (ie. the
* same value as RootPtr).
*
* Note: The interface to this function has changed from that of
* previous versions. The <Flags> parameter replaces two
* boolean parameters that had the same basic effect.
* ------------------------------------------------------------------------ **
*/
ubi_trBool ubi_btInsert( ubi_btRootPtr RootPtr,
ubi_btNodePtr NewNode,
ubi_btItemPtr ItemPtr,
ubi_btNodePtr *OldNode );
/* ------------------------------------------------------------------------ **
* This function uses a non-recursive algorithm to add a new element to the
* tree.
*
* Input: RootPtr - a pointer to the ubi_btRoot structure that indicates
* the root of the tree to which NewNode is to be added.
* NewNode - a pointer to an ubi_btNode structure that is NOT
* part of any tree.
* ItemPtr - A pointer to the sort key that is stored within
* *NewNode. ItemPtr MUST point to information stored
* in *NewNode or an EXACT DUPLICATE. The key data
* indicated by ItemPtr is used to place the new node
* into the tree.
* OldNode - a pointer to an ubi_btNodePtr. When searching
* the tree, a duplicate node may be found. If
* duplicates are allowed, then the new node will
* be simply placed into the tree. If duplicates
* are not allowed, however, then one of two things
* may happen.
* 1) if overwritting *is not* allowed, this
* function will return FALSE (indicating that
* the new node could not be inserted), and
* *OldNode will point to the duplicate that is
* still in the tree.
* 2) if overwritting *is* allowed, then this
* function will swap **OldNode for *NewNode.
* In this case, *OldNode will point to the node
* that was removed (thus allowing you to free
* the node).
* ** If you are using overwrite mode, ALWAYS **
* ** check the return value of this parameter! **
* Note: You may pass NULL in this parameter, the
* function knows how to cope. If you do this,
* however, there will be no way to return a
* pointer to an old (ie. replaced) node (which is
* a problem if you are using overwrite mode).
*
* Output: a boolean value indicating success or failure. The function
* will return FALSE if the node could not be added to the tree.
* Such failure will only occur if duplicates are not allowed,
* nodes cannot be overwritten, AND a duplicate key was found
* within the tree.
* ------------------------------------------------------------------------ **
*/
ubi_btNodePtr ubi_btRemove( ubi_btRootPtr RootPtr,
ubi_btNodePtr DeadNode );
/* ------------------------------------------------------------------------ **
* This function removes the indicated node from the tree.
*
* Input: RootPtr - A pointer to the header of the tree that contains
* the node to be removed.
* DeadNode - A pointer to the node that will be removed.
*
* Output: This function returns a pointer to the node that was removed
* from the tree (ie. the same as DeadNode).
*
* Note: The node MUST be in the tree indicated by RootPtr. If not,
* strange and evil things will happen to your trees.
* ------------------------------------------------------------------------ **
*/
ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr,
ubi_btItemPtr FindMe,
ubi_trCompOps CompOp );
/* ------------------------------------------------------------------------ **
* The purpose of ubi_btLocate() is to find a node or set of nodes given
* a target value and a "comparison operator". The Locate() function is
* more flexible and (in the case of trees that may contain dupicate keys)
* more precise than the ubi_btFind() function. The latter is faster,
* but it only searches for exact matches and, if the tree contains
* duplicates, Find() may return a pointer to any one of the duplicate-
* keyed records.
*
* Input:
* RootPtr - A pointer to the header of the tree to be searched.
* FindMe - An ubi_btItemPtr that indicates the key for which to
* search.
* CompOp - One of the following:
* CompOp Return a pointer to the node with
* ------ ---------------------------------
* ubi_trLT - the last key value that is less
* than FindMe.
* ubi_trLE - the first key matching FindMe, or
* the last key that is less than
* FindMe.
* ubi_trEQ - the first key matching FindMe.
* ubi_trGE - the first key matching FindMe, or the
* first key greater than FindMe.
* ubi_trGT - the first key greater than FindMe.
* Output:
* A pointer to the node matching the criteria listed above under
* CompOp, or NULL if no node matched the criteria.
*
* Notes:
* In the case of trees with duplicate keys, Locate() will behave as
* follows:
*
* Find: 3 Find: 3
* Keys: 1 2 2 2 3 3 3 3 3 4 4 Keys: 1 1 2 2 2 4 4 5 5 5 6
* ^ ^ ^ ^ ^
* LT EQ GT LE GE
*
* That is, when returning a pointer to a node with a key that is LESS
* THAN the target key (FindMe), Locate() will return a pointer to the
* LAST matching node.
* When returning a pointer to a node with a key that is GREATER
* THAN the target key (FindMe), Locate() will return a pointer to the
* FIRST matching node.
*
* See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf().
* ------------------------------------------------------------------------ **
*/
ubi_btNodePtr ubi_btFind( ubi_btRootPtr RootPtr,
ubi_btItemPtr FindMe );
/* ------------------------------------------------------------------------ **
* This function performs a non-recursive search of a tree for any node
* matching a specific key.
*
* Input:
* RootPtr - a pointer to the header of the tree to be searched.
* FindMe - a pointer to the key value for which to search.
*
* Output:
* A pointer to a node with a key that matches the key indicated by
* FindMe, or NULL if no such node was found.
*
* Note: In a tree that allows duplicates, the pointer returned *might
* not* point to the (sequentially) first occurance of the
* desired key. In such a tree, it may be more useful to use
* ubi_btLocate().
* ------------------------------------------------------------------------ **
*/
ubi_btNodePtr ubi_btNext( ubi_btNodePtr P );
/* ------------------------------------------------------------------------ **
* Given the node indicated by P, find the (sorted order) Next node in the
* tree.
* Input: P - a pointer to a node that exists in a binary tree.
* Output: A pointer to the "next" node in the tree, or NULL if P pointed
* to the "last" node in the tree or was NULL.
* ------------------------------------------------------------------------ **
*/
ubi_btNodePtr ubi_btPrev( ubi_btNodePtr P );
/* ------------------------------------------------------------------------ **
* Given the node indicated by P, find the (sorted order) Previous node in
* the tree.
* Input: P - a pointer to a node that exists in a binary tree.
* Output: A pointer to the "previous" node in the tree, or NULL if P
* pointed to the "first" node in the tree or was NULL.
* ------------------------------------------------------------------------ **
*/
ubi_btNodePtr ubi_btFirst( ubi_btNodePtr P );
/* ------------------------------------------------------------------------ **
* Given the node indicated by P, find the (sorted order) First node in the
* subtree of which *P is the root.
* Input: P - a pointer to a node that exists in a binary tree.
* Output: A pointer to the "first" node in a subtree that has *P as its
* root. This function will return NULL only if P is NULL.
* Note: In general, you will be passing in the value of the root field
* of an ubi_btRoot structure.
* ------------------------------------------------------------------------ **
*/
ubi_btNodePtr ubi_btLast( ubi_btNodePtr P );
/* ------------------------------------------------------------------------ **
* Given the node indicated by P, find the (sorted order) Last node in the
* subtree of which *P is the root.
* Input: P - a pointer to a node that exists in a binary tree.
* Output: A pointer to the "last" node in a subtree that has *P as its
* root. This function will return NULL only if P is NULL.
* Note: In general, you will be passing in the value of the root field
* of an ubi_btRoot structure.
* ------------------------------------------------------------------------ **
*/
ubi_btNodePtr ubi_btFirstOf( ubi_btRootPtr RootPtr,
ubi_btItemPtr MatchMe,
ubi_btNodePtr p );
/* ------------------------------------------------------------------------ **
* Given a tree that a allows duplicate keys, and a pointer to a node in
* the tree, this function will return a pointer to the first (traversal
* order) node with the same key value.
*
* Input: RootPtr - A pointer to the root of the tree.
* MatchMe - A pointer to the key value. This should probably
* point to the key within node *p.
* p - A pointer to a node in the tree.
* Output: A pointer to the first node in the set of nodes with keys
* matching <FindMe>.
* Notes: Node *p MUST be in the set of nodes with keys matching
* <FindMe>. If not, this function will return NULL.
*
* 4.7: Bug found & fixed by Massimo Campostrini,
* Istituto Nazionale di Fisica Nucleare, Sezione di Pisa.
*
* ------------------------------------------------------------------------ **
*/
ubi_btNodePtr ubi_btLastOf( ubi_btRootPtr RootPtr,
ubi_btItemPtr MatchMe,
ubi_btNodePtr p );
/* ------------------------------------------------------------------------ **
* Given a tree that a allows duplicate keys, and a pointer to a node in
* the tree, this function will return a pointer to the last (traversal
* order) node with the same key value.
*
* Input: RootPtr - A pointer to the root of the tree.
* MatchMe - A pointer to the key value. This should probably
* point to the key within node *p.
* p - A pointer to a node in the tree.
* Output: A pointer to the last node in the set of nodes with keys
* matching <FindMe>.
* Notes: Node *p MUST be in the set of nodes with keys matching
* <FindMe>. If not, this function will return NULL.
*
* 4.7: Bug found & fixed by Massimo Campostrini,
* Istituto Nazionale di Fisica Nucleare, Sezione di Pisa.
*
* ------------------------------------------------------------------------ **
*/
unsigned long ubi_btTraverse( ubi_btRootPtr RootPtr,
ubi_btActionRtn EachNode,
void *UserData );
/* ------------------------------------------------------------------------ **
* Traverse a tree in sorted order (non-recursively). At each node, call
* (*EachNode)(), passing a pointer to the current node, and UserData as the
* second parameter.
*
* Input: RootPtr - a pointer to an ubi_btRoot structure that indicates
* the tree to be traversed.
* EachNode - a pointer to a function to be called at each node
* as the node is visited.
* UserData - a generic pointer that may point to anything that
* you choose.
*
* Output: A count of the number of nodes visited. This will be zero
* if the tree is empty.
*
* ------------------------------------------------------------------------ **
*/
unsigned long ubi_btKillTree( ubi_btRootPtr RootPtr,
ubi_btKillNodeRtn FreeNode );
/* ------------------------------------------------------------------------ **
* Delete an entire tree (non-recursively) and reinitialize the ubi_btRoot
* structure. Return a count of the number of nodes deleted.
*
* Input: RootPtr - a pointer to an ubi_btRoot structure that indicates
* the root of the tree to delete.
* FreeNode - a function that will be called for each node in the
* tree to deallocate the memory used by the node.
*
* Output: The number of nodes removed from the tree.
* A value of 0 will be returned if:
* - The tree actually contains 0 entries.
* - the value of <RootPtr> is NULL, in which case the tree is
* assumed to be empty
* - the value of <FreeNode> is NULL, in which case entries
* cannot be removed, so 0 is returned. *Make sure that you
* provide a valid value for <FreeNode>*.
* In all other cases, you should get a positive value equal to
* the value of RootPtr->count upon entry.
*
* ------------------------------------------------------------------------ **
*/
ubi_btNodePtr ubi_btLeafNode( ubi_btNodePtr leader );
/* ------------------------------------------------------------------------ **
* Returns a pointer to a leaf node.
*
* Input: leader - Pointer to a node at which to start the descent.
*
* Output: A pointer to a leaf node selected in a somewhat arbitrary
* manner.
*
* Notes: I wrote this function because I was using splay trees as a
* database cache. The cache had a maximum size on it, and I
* needed a way of choosing a node to sacrifice if the cache
* became full. In a splay tree, less recently accessed nodes
* tend toward the bottom of the tree, meaning that leaf nodes
* are good candidates for removal. (I really can't think of
* any other reason to use this function.)
* + In a simple binary tree or an AVL tree, the most recently
* added nodes tend to be nearer the bottom, making this a *bad*
* way to choose which node to remove from the cache.
* + Randomizing the traversal order is probably a good idea. You
* can improve the randomization of leaf node selection by passing
* in pointers to nodes other than the root node each time. A
* pointer to any node in the tree will do. Of course, if you
* pass a pointer to a leaf node you'll get the same thing back.
*
* ------------------------------------------------------------------------ **
*/
int ubi_btModuleID( int size, char *list[] );
/* ------------------------------------------------------------------------ **
* Returns a set of strings that identify the module.
*
* Input: size - The number of elements in the array <list>.
* list - An array of pointers of type (char *). This array
* should, initially, be empty. This function will fill
* in the array with pointers to strings.
* Output: The number of elements of <list> that were used. If this value
* is less than <size>, the values of the remaining elements are
* not guaranteed.
*
* Notes: Please keep in mind that the pointers returned indicate strings
* stored in static memory. Don't free() them, don't write over
* them, etc. Just read them.
* ------------------------------------------------------------------------ **
*/
/* -------------------------------------------------------------------------- **
* Masquarade...
*
* This set of defines allows you to write programs that will use any of the
* implemented binary tree modules (currently BinTree, AVLtree, and SplayTree).
* Instead of using ubi_bt..., use ubi_tr..., and select the tree type by
* including the appropriate module header.
*/
#define ubi_trItemPtr ubi_btItemPtr
#define ubi_trNode ubi_btNode
#define ubi_trNodePtr ubi_btNodePtr
#define ubi_trRoot ubi_btRoot
#define ubi_trRootPtr ubi_btRootPtr
#define ubi_trCompFunc ubi_btCompFunc
#define ubi_trActionRtn ubi_btActionRtn
#define ubi_trKillNodeRtn ubi_btKillNodeRtn
#define ubi_trSgn( x ) ubi_btSgn( x )
#define ubi_trInitNode( Np ) ubi_btInitNode( (ubi_btNodePtr)(Np) )
#define ubi_trInitTree( Rp, Cf, Fl ) \
ubi_btInitTree( (ubi_btRootPtr)(Rp), (ubi_btCompFunc)(Cf), (Fl) )
#define ubi_trInsert( Rp, Nn, Ip, On ) \
ubi_btInsert( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Nn), \
(ubi_btItemPtr)(Ip), (ubi_btNodePtr *)(On) )
#define ubi_trRemove( Rp, Dn ) \
ubi_btRemove( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Dn) )
#define ubi_trLocate( Rp, Ip, Op ) \
ubi_btLocate( (ubi_btRootPtr)(Rp), \
(ubi_btItemPtr)(Ip), \
(ubi_trCompOps)(Op) )
#define ubi_trFind( Rp, Ip ) \
ubi_btFind( (ubi_btRootPtr)(Rp), (ubi_btItemPtr)(Ip) )
#define ubi_trNext( P ) ubi_btNext( (ubi_btNodePtr)(P) )
#define ubi_trPrev( P ) ubi_btPrev( (ubi_btNodePtr)(P) )
#define ubi_trFirst( P ) ubi_btFirst( (ubi_btNodePtr)(P) )
#define ubi_trLast( P ) ubi_btLast( (ubi_btNodePtr)(P) )
#define ubi_trFirstOf( Rp, Ip, P ) \
ubi_btFirstOf( (ubi_btRootPtr)(Rp), \
(ubi_btItemPtr)(Ip), \
(ubi_btNodePtr)(P) )
#define ubi_trLastOf( Rp, Ip, P ) \
ubi_btLastOf( (ubi_btRootPtr)(Rp), \
(ubi_btItemPtr)(Ip), \
(ubi_btNodePtr)(P) )
#define ubi_trTraverse( Rp, En, Ud ) \
ubi_btTraverse((ubi_btRootPtr)(Rp), (ubi_btActionRtn)(En), (void *)(Ud))
#define ubi_trKillTree( Rp, Fn ) \
ubi_btKillTree( (ubi_btRootPtr)(Rp), (ubi_btKillNodeRtn)(Fn) )
#define ubi_trLeafNode( Nd ) \
ubi_btLeafNode( (ubi_btNodePtr)(Nd) )
#define ubi_trModuleID( s, l ) ubi_btModuleID( s, l )
/* ========================================================================== */
#endif /* UBI_BINTREE_H */
|