From 6f429912e7a2d8c3f83a92adb914cd89a55af43d Mon Sep 17 00:00:00 2001 From: "Christopher R. Hertel" Date: Wed, 24 Dec 1997 02:50:19 +0000 Subject: Backed out changes that attempted to address a pointer array using -1,0,1. Jeremy pointed out that there might be problems with this. Darn shame. (This used to be commit ce9acc96a6cbc91f0a3f95221c3e8f801cbdb602) --- source3/ubiqx/ubi_BinTree.h | 269 +++++++++++++++++++++----------------------- 1 file changed, 129 insertions(+), 140 deletions(-) (limited to 'source3/ubiqx/ubi_BinTree.h') diff --git a/source3/ubiqx/ubi_BinTree.h b/source3/ubiqx/ubi_BinTree.h index d5032b58a2..4b918a4609 100644 --- a/source3/ubiqx/ubi_BinTree.h +++ b/source3/ubiqx/ubi_BinTree.h @@ -8,7 +8,7 @@ * Email: crh@ubiqx.mn.org * -------------------------------------------------------------------------- ** * - * This module implements simple binary trees. + * This module implements a simple binary tree. * * -------------------------------------------------------------------------- ** * @@ -29,72 +29,69 @@ * -------------------------------------------------------------------------- ** * * Log: ubi_BinTree.h,v - * Revision 3.0 1997/12/08 06:49:15 crh - * This is a new major revision level for all ubiqx binary tree modules. - * In previous releases, the ubi_trNode structure looked like this: - * - * typedef struct ubi_btNodeStruct - * { - * struct ubi_btNodeStruct *Link[3]; - * signed char gender; - * } ubi_btNode; - * - * As a result, the pointers were indexed as - * - * Link[0] == Left Child - * Link[1] == Parent - * Link[2] == Right Child - * - * With this release, the node structure changes to: - * - * typedef struct ubi_btNodeStruct - * { - * struct ubi_btNodeStruct *leftlink - * struct ubi_btNodeStruct *Link[2]; - * signed char gender; - * } ubi_btNode; - * - * The leftlink field is used as a place holder, and the pointers are now - * index as - * - * Link[-1] == Left Child (aka. leftlink) - * Link[ 0] == Parent - * Link[ 1] == Right Child - * - * which is much nicer. Doing things this way removes the need to shift - * values between the two numbering schemes, thus removing one macro, - * simplifying another, and getting rid of a whole bunch of increment & - * decrement operations. - * - * Revision 2; 1995/02/27 - 1997/12/07 included: - * - The addition of the ModuleID static string and ubi_ModuleID() function. - * - The addition of the public functions FirstOf() and LastOf(). These - * functions are used with trees that allow duplicate keys. - * - The addition of the ubi_btLeafNode() function. - * - A rewrite of the Locate() function. - * - A change to the parameter list in function ubi_btInitTree(). - * - Bugfixes. - * - * Revision 1; 93/10/15 - 95/02/27: - * Revision 1 introduced a set of #define's that provide a single API to all - * of the existing tree modules. Each of these modules has a different name - * prefix, as follows: + * 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 + * when run with '-pedantic -fsyntax-only -Wall'. + * + * Revision 2.4 1997/07/26 04:11:14 crh + * + Just to be annoying I changed ubi_TRUE and ubi_FALSE to ubi_trTRUE + * and ubi_trFALSE. + * + There is now a type ubi_trBool to go with ubi_trTRUE and ubi_trFALSE. + * + There used to be something called "ubi_TypeDefs.h". I got rid of it. + * + Added function ubi_btLeafNode(). + * + * Revision 2.3 1997/06/03 05:15:27 crh + * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid conflicts. + * Also changed the interface to function InitTree(). See the comments + * for this function for more information. + * + * Revision 2.2 1995/10/03 22:00:40 CRH + * Ubisized! + * + * Revision 2.1 95/03/09 23:43:46 CRH + * Added the ModuleID static string and function. These modules are now + * self-identifying. + * + * Revision 2.0 95/02/27 22:00:33 CRH + * Revision 2.0 of this program includes the following changes: + * + * 1) A fix to a major typo in the RepaceNode() function. + * 2) The addition of the static function Border(). + * 3) The addition of the public functions FirstOf() and LastOf(), which + * use Border(). These functions are used with trees that allow + * duplicate keys. + * 4) A complete rewrite of the Locate() function. Locate() now accepts + * a "comparison" operator. + * 5) Overall enhancements to both code and comments. + * + * I decided to give this a new major rev number because the interface has + * changed. In particular, there are two new functions, and changes to the + * Locate() function. + * + * Revision 1.0 93/10/15 22:55:04 CRH + * With this revision, I have added a set of #define's that provide a single, + * standard API to all existing tree modules. Until now, each of the three + * existing modules had a different function and typedef prefix, as follows: * * Module Prefix * ubi_BinTree ubi_bt * ubi_AVLtree ubi_avl * ubi_SplayTree ubi_spt * - * Only those portions of the base module (ubi_BinTree) that are superceeded - * in the descendant module have new names. For example, the AVL node - * structure in ubi_AVLtree.h is named "ubi_avlNode", but the root structure - * is still "ubi_btRoot". Using SplayTree, the locate function is called - * "ubi_sptLocate", but the next and previous functions remained "ubi_btNext" - * and "ubi_btPrev". + * 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". * - * This is confusing. + * 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 + * change modules (for speed comparisons, etc), things could get messy very + * quickly. * - * So, I added a set of defined names that get redefined in any of the + * So, I have added a set of defined names that get redefined in any of the * descendant modules. To use this standardized interface in your code, * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with * "ubi_tr". The "ubi_tr" names will resolve to the correct function or @@ -106,8 +103,7 @@ * Note that the original names do still exist, and can be used if you wish * to write code directly to a specific module. This should probably only be * done if you are planning to implement a new descendant type, such as - * red/black trees, or if you plan to use two or more specific tree types - * in the same piece of code. CRH + * red/black trees. CRH * * V0.0 - June, 1991 - Written by Christopher R. Hertel (CRH). * @@ -115,7 +111,7 @@ */ /* -------------------------------------------------------------------------- ** - * Constants... + * Macros and constants. * * General purpose: * ubi_trTRUE - Boolean TRUE. @@ -125,16 +121,16 @@ * 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 allows duplicates, the overwrite - * flag is ignored. + * 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; pointer to the left child, - * pointer to the right child, and a pointer back to the parent node.) - * ubi_trLEFT - Left child pointer. - * ubi_trPARENT - Parent pointer. - * ubi_trRIGHT - Right child pointer. - * ubi_trEQUAL - Synonym for PARENT. + * 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 @@ -147,6 +143,7 @@ * 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 @@ -156,13 +153,12 @@ #define ubi_trDUPKEY 0x02 /* Turn on allow duplicate keys */ /* Pointer array index constants... */ -#define ubi_trLEFT -1 -#define ubi_trPARENT 0 -#define ubi_trRIGHT 1 -#define ubi_trEQUAL ubi_trPARENT +#define ubi_trLEFT 0x00 +#define ubi_trPARENT 0x01 +#define ubi_trRIGHT 0x02 +#define ubi_trEQUAL ubi_trPARENT -typedef enum - { +typedef enum { ubi_trLT = 1, ubi_trLE, ubi_trEQ, @@ -171,57 +167,59 @@ typedef enum } ubi_trCompOps; /* -------------------------------------------------------------------------- ** - * Macros... - * ubi_trNormalize() - "Normalize" a value with respect to ubi_trLEFT, - * ubi_trRIGHT, and ubi_trPARENT. This macro calls - * ubi_btSgn() to convert the input to -1, 0, or 1. - * The resultant value is returned as a signed char. - * - * ubi_trRevWay() - converts ubi_trLEFT to ubi_trRIGHT and vice versa. - * ubi_trPARENT (ubi_trEQUAL) is left as is. - * - * ubi_trDups_OK() - returns TRUE if the tree allows duplicates. - * - * ubi_trOvwt_OK() - returns TRUE if the overwrite flag is on. Note - * that overwrites will not occur in a tree that - * allows duplicates. + * 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( W )) + ubi_trEQUAL )) +#define ubi_trRevWay(W) ((char)( ubi_trEQUAL - ((W) - ubi_trEQUAL) )) -#define ubi_trNormalize(W) ((signed char)ubi_btSgn(W)) -#define ubi_trRevWay(W) (-(W)) - +/* -------------------------------------------------------------------------- ** + * 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)) + ((ubi_trDUPKEY & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE)) #define ubi_trOvwt_OK(A) \ - ((ubi_trOVERWRITE & ((A)->flags))? (ubi_trTRUE) : (ubi_trFALSE)) - + ((ubi_trOVERWRITE & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE)) /* -------------------------------------------------------------------------- ** * Typedefs... * - * ubi_trBool - Your typcial true or false... + * ubi_trBool - Your typcial true or false... * - * ubi_btItemPtr - The Item Pointer is a generic pointer. It is used to - * indicate a key for which to search within the tree. - * The ubi_trFind(), ubi_trLocate(), and ubi_trInsert() - * functions all perform searches. + * 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; /* Our own name for "boolean". */ +typedef unsigned char ubi_trBool; -typedef void *ubi_btItemPtr; /* A pointer to (key) data within a node. */ +typedef void *ubi_btItemPtr; /* A pointer to data within a node. */ -/* -------------------------------------------------------------------------- ** - * Typedefs continued... - * +/* ------------------------------------------------------------------------- ** * 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: - * leftlink - pointer to the left child of the node. This field will - * be accessed as Link[-1]. * 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 @@ -232,22 +230,18 @@ typedef void *ubi_btItemPtr; /* A pointer to (key) 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. + * ------------------------------------------------------------------------- ** */ - -typedef struct ubi_btNodeStruct - { - struct ubi_btNodeStruct *leftlink; /* Will be accessed as Link[-1]. */ - struct ubi_btNodeStruct *Link[2]; /* Parent & Right links. */ - signed char gender; /* Indicates Left/Right of parent. */ +typedef struct ubi_btNodeStruct { + struct ubi_btNodeStruct *Link[ 3 ]; + char gender; } ubi_btNode; typedef ubi_btNode *ubi_btNodePtr; /* Pointer to an ubi_btNode structure. */ -/* -------------------------------------------------------------------------- ** - * Typedefs continued... - * - * The next three typedefs define standard function types used by the binary - * tree management routines. In particular: +/* ------------------------------------------------------------------------- ** + * 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 @@ -267,6 +261,7 @@ typedef ubi_btNode *ubi_btNodePtr; /* Pointer to an ubi_btNode structure. */ * 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 ); @@ -276,10 +271,8 @@ typedef void (*ubi_btActionRtn)( ubi_btNodePtr, void * ); typedef void (*ubi_btKillNodeRtn)( ubi_btNodePtr ); /* -------------------------------------------------------------------------- ** - * Typedefs continued... - * - * Tree Root Structure: This structure gives us a convenient handle for - * accessing whole AVL trees. The fields are: + * 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. * 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 @@ -293,15 +286,13 @@ typedef void (*ubi_btKillNodeRtn)( ubi_btNodePtr ); * (bit 0x02) allowed to contain nodes with duplicate keys. * * NOTE: ubi_trInsert() tests ubi_trDUPKEY before ubi_trOVERWRITE. - * If duplicate keys are allowed, then no entry will be - * overwritten. * - * All of these values are set when you initialize the root structure by - * calling ubi_trInitTree(). + * All of these values are set when you initialize the root structure by + * calling ubi_trInitTree(). + * -------------------------------------------------------------------------- ** */ -typedef struct - { +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 */ @@ -321,15 +312,15 @@ long ubi_btSgn( long x ); * * Input: x - a signed long integer value. * - * Output: -1, 0, or 1 representing the "sign" of x as follows: + * Output: the "sign" of x, represented as follows: * -1 == negative * 0 == zero (no sign) * 1 == positive * - * Notes: This utility is provided in order to facilitate the conversion - * of C comparison function return values into BinTree direction - * values: {ubi_trLEFT, ubi_trPARENT, ubi_trEQUAL}. It is - * incorporated into the Normalize() conversion macro. + * 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! * * ------------------------------------------------------------------------ ** */ @@ -344,9 +335,9 @@ ubi_btNodePtr ubi_btInitNode( ubi_btNodePtr NodePtr ); * ------------------------------------------------------------------------ ** */ -ubi_btRootPtr ubi_btInitTree( ubi_btRootPtr RootPtr, - ubi_btCompFunc CompFunc, - unsigned char Flags ); +ubi_btRootPtr ubi_btInitTree( ubi_btRootPtr RootPtr, + ubi_btCompFunc CompFunc, + unsigned char Flags ); /* ------------------------------------------------------------------------ ** * Initialize the fields of a Tree Root header structure. * @@ -648,8 +639,6 @@ ubi_btNodePtr ubi_btLeafNode( ubi_btNodePtr leader ); * 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. - * + If using a splay tree, splaying the tree will tend to randomize - * things a bit too. See ubi_SplayTree for more info. * * ------------------------------------------------------------------------ ** */ -- cgit