diff options
Diffstat (limited to 'source3/ubiqx/ubi_SplayTree.c')
| -rw-r--r-- | source3/ubiqx/ubi_SplayTree.c | 108 |
1 files changed, 85 insertions, 23 deletions
diff --git a/source3/ubiqx/ubi_SplayTree.c b/source3/ubiqx/ubi_SplayTree.c index fb4cc9f7c8..799996b6cc 100644 --- a/source3/ubiqx/ubi_SplayTree.c +++ b/source3/ubiqx/ubi_SplayTree.c @@ -35,16 +35,78 @@ * -------------------------------------------------------------------------- ** * * Log: ubi_SplayTree.c,v - * Revision 3.0 1997/12/08 05:32:28 crh - * This is a new major revision level because of a redesign of the handling - * of the pointers in the ubi_trNode structure. See ubi_BinTree for more - * info. + * Revision 2.6 1997/12/23 04:01:12 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; 1995/02/27 - 1997/12/07: - * Major changes: added the function ubi_sptSplay(). + * Revision 2.5 1997/07/26 04:15:42 crh + * + Cleaned up a few minor syntax annoyances that gcc discovered for me. + * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE. * - * Revision 1; 93/10/15 - 95/02/27: - * Added the ubi_tr defines. See ubi_BinTree.h for more info. + * Revision 2.4 1997/06/03 04:42:21 crh + * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing + * problems. + * + * Revision 2.3 1995/10/03 22:19:07 CRH + * Ubisized! + * Also, added the function ubi_sptSplay(). + * + * Revision 2.1 95/03/09 23:54:42 CRH + * Added the ModuleID static string and function. These modules are now + * self-identifying. + * + * Revision 2.0 95/02/27 22:34:46 CRH + * This module was updated to match the interface changes made to the + * ubi_BinTree module. In particular, the interface to the Locate() function + * has changed. See ubi_BinTree for more information on changes and new + * functions. + * + * The revision number was also upped to match ubi_BinTree. + * + * Revision 1.1 93/10/18 20:35:16 CRH + * I removed the hard-coded logical device names from the include file + * specifications. CRH + * + * Revision 1.0 93/10/15 23:00:15 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 + * + * 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 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 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 + * datatype names for the module that you are using. Just remember to + * include the header for that module in your program file. Because these + * names are handled by the preprocessor, there is no added run-time + * overhead. + * + * 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. CRH + * + * Revision 0.1 93/04/25 22:03:32 CRH + * Simply changed the <exec/types.h> #include reference the .c file to + * use <stdlib.h> instead. The latter is portable, the former is not. * * Revision 0.0 93/04/21 23:05:52 CRH * Initial version, written by Christopher R. Hertel. @@ -61,8 +123,8 @@ */ static char ModuleID[] = "ubi_SplayTree\n\ -\tRevision: 3.0\n\ -\tDate: 1997/12/08 05:32:28\n\ +\tRevision: 2.6\n\ +\tDate: 1997/12/23 04:01:12\n\ \tAuthor: crh\n"; @@ -87,18 +149,18 @@ static void Rotate( ubi_btNodePtr p ) { ubi_btNodePtr parentp; ubi_btNodePtr tmp; - signed char way; - signed char revway; + char way; + char revway; parentp = p->Link[ubi_trPARENT]; /* Find parent. */ if( parentp ) /* If no parent, then we're already the root. */ { - way = p->gender; - revway = ubi_trRevWay(way); - tmp = p->Link[revway]; + way = p->gender; + revway = ubi_trRevWay(way); + tmp = p->Link[(int)revway]; - parentp->Link[way] = tmp; + parentp->Link[(int)way] = tmp; if( tmp ) { tmp->Link[ubi_trPARENT] = parentp; @@ -109,11 +171,11 @@ static void Rotate( ubi_btNodePtr p ) p->Link[ubi_trPARENT] = tmp; p->gender = parentp->gender; if( tmp ) - tmp->Link[p->gender] = p; + tmp->Link[(int)(p->gender)] = p; parentp->Link[ubi_trPARENT] = p; parentp->gender = revway; - p->Link[revway] = parentp; + p->Link[(int)revway] = parentp; } } /* Rotate */ @@ -141,7 +203,7 @@ static ubi_btNodePtr Splay( ubi_btNodePtr SplayWithMe ) Rotate( SplayWithMe ); } Rotate( SplayWithMe ); /* Zig */ - } + } /* while */ return( SplayWithMe ); } /* Splay */ @@ -238,9 +300,9 @@ ubi_btNodePtr ubi_sptRemove( ubi_btRootPtr RootPtr, ubi_btNodePtr DeadNode ) ubi_btNodePtr q = DeadNode->Link[ubi_trRIGHT]; p->Link[ubi_trPARENT] = NULL; /* Left subtree node becomes root.*/ - p->gender = ubi_trPARENT; - p = ubi_btLast( p ); /* Find rightmost left tree node..*/ - p->Link[ubi_trRIGHT] = q; /* ...attach right tree. */ + p->gender = ubi_trPARENT; + p = ubi_btLast( p ); /* Find rightmost left node... */ + p->Link[ubi_trRIGHT] = q; /* ...attach right tree. */ if( q ) q->Link[ubi_trPARENT] = p; RootPtr->root = Splay( p ); /* Resplay at p. */ @@ -368,7 +430,7 @@ void ubi_sptSplay( ubi_btRootPtr RootPtr, * Splaying the tree will not damage it (assuming that I've done * *my* job), but there is overhead involved. I don't recommend * that you use this function unless you understand the underlying - * Splay Tree. + * Splay Tree principles involved. * ------------------------------------------------------------------------ ** */ { |