diff options
Diffstat (limited to 'source3/ubiqx/ubi_BinTree.h')
| -rw-r--r-- | source3/ubiqx/ubi_BinTree.h | 44 |
1 files changed, 34 insertions, 10 deletions
diff --git a/source3/ubiqx/ubi_BinTree.h b/source3/ubiqx/ubi_BinTree.h index 4b918a4609..f3c49c95e1 100644 --- a/source3/ubiqx/ubi_BinTree.h +++ b/source3/ubiqx/ubi_BinTree.h @@ -3,7 +3,7 @@ /* ========================================================================== ** * ubi_BinTree.h * - * Copyright (C) 1991-1997 by Christopher R. Hertel + * Copyright (C) 1991-1998 by Christopher R. Hertel * * Email: crh@ubiqx.mn.org * -------------------------------------------------------------------------- ** @@ -29,6 +29,16 @@ * -------------------------------------------------------------------------- ** * * Log: ubi_BinTree.h,v + * Revision 4.0 1998/03/10 03:16:04 crh + * Added the AVL field 'balance' to the ubi_btNode structure. This means + * that all BinTree modules now use the same basic node structure, which + * greatly simplifies the AVL module. + * Decided that this was a big enough change to justify a new major revision + * number. 3.0 was an error, so we're at 4.0. + * + * Revision 2.6 1998/01/24 06:27:30 crh + * Added ubi_trCount() macro. + * * Revision 2.5 1997/12/23 03:59:21 crh * In this version, all constants & macros defined in the header file have * the ubi_tr prefix. Also cleaned up anything that gcc complained about @@ -81,10 +91,9 @@ * * To further complicate matters, only those portions of the base module * (ubi_BinTree) that were superceeded in the new module had the new names. - * For example, if you were using ubi_AVLtree, the AVL node structure was - * named "ubi_avlNode", but the root structure was still "ubi_btRoot". Using - * SplayTree, the locate function was called "ubi_sptLocate", but the next - * and previous functions remained "ubi_btNext" and "ubi_btPrev". + * For example, if you were using ubi_SplayTree, the locate function was + * called "ubi_sptLocate", but the next and previous functions remained + * "ubi_btNext" and "ubi_btPrev". * * This was not too terrible if you were familiar with the modules and knew * exactly which tree model you wanted to use. If you wanted to be able to @@ -198,6 +207,16 @@ typedef enum { ((ubi_trOVERWRITE & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE)) /* -------------------------------------------------------------------------- ** + * A quickie for consistency. + * ubi_trCount() - Given a pointer to a tree root, this macro returns the + * number of nodes currently in the tree. + * + * -------------------------------------------------------------------------- ** + */ + +#define ubi_trCount( R ) (((ubi_trRootPtr)(R))->count) + +/* -------------------------------------------------------------------------- ** * Typedefs... * * ubi_trBool - Your typcial true or false... @@ -211,7 +230,7 @@ typedef enum { typedef unsigned char ubi_trBool; -typedef void *ubi_btItemPtr; /* A pointer to data within a node. */ +typedef void *ubi_btItemPtr; /* A pointer to key data within a node. */ /* ------------------------------------------------------------------------- ** * Binary Tree Node Structure: This structure defines the basic elements of @@ -230,11 +249,16 @@ typedef void *ubi_btItemPtr; /* A pointer to data within a node. */ * 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; + signed char gender; + signed char balance; } ubi_btNode; typedef ubi_btNode *ubi_btNodePtr; /* Pointer to an ubi_btNode structure. */ @@ -272,8 +296,8 @@ typedef void (*ubi_btKillNodeRtn)( ubi_btNodePtr ); /* -------------------------------------------------------------------------- ** * Tree Root Structure: This structure gives us a convenient handle for - * accessing whole AVL trees. The fields are: - * root - A pointer to the root node of the AVL tree. + * 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. @@ -294,8 +318,8 @@ typedef void (*ubi_btKillNodeRtn)( ubi_btNodePtr ); typedef struct { ubi_btNodePtr root; /* A pointer to the root node of the tree */ - unsigned long count; /* A count of the number of nodes in 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 */ unsigned char flags; /* Overwrite Y|N, Duplicate keys Y|N... */ } ubi_btRoot; |