source3/ubiqx/ubi_SplayTree.h

   1 #ifndef ubi_SplayTree_H
   2 #define ubi_SplayTree_H
   3 /* ========================================================================== **
   4  *                              ubi_SplayTree.h
   5  *
   6  *  Copyright (C) 1993,1995 by Christopher R. Hertel
   7  *
   8  *  Email: crh@ubiqx.mn.org
   9  * -------------------------------------------------------------------------- **
  10  *
  11  *  This module implements "splay" trees.  Splay trees are binary trees
  12  *  that are rearranged (splayed) whenever a node is accessed.  The
  13  *  splaying process *tends* to make the tree bushier (improves balance),
  14  *  and the nodes that are accessed most frequently *tend* to be closer to
  15  *  the top.
  16  *
  17  *  References: "Self-Adjusting Binary Search Trees", by Daniel Sleator and
  18  *              Robert Tarjan.  Journal of the Association for Computing
  19  *              Machinery Vol 32, No. 3, July 1985 pp. 652-686
  20  *
  21  * -------------------------------------------------------------------------- **
  22  *
  23  *  This library is free software; you can redistribute it and/or
  24  *  modify it under the terms of the GNU Library General Public
  25  *  License as published by the Free Software Foundation; either
  26  *  version 2 of the License, or (at your option) any later version.
  27  *
  28  *  This library is distributed in the hope that it will be useful,
  29  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  30  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  31  *  Library General Public License for more details.
  32  *
  33  *  You should have received a copy of the GNU Library General Public
  34  *  License along with this library; if not, write to the Free
  35  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  36  *
  37  * -------------------------------------------------------------------------- **
  38  *
  39  * Log: ubi_SplayTree.h,v
  40  * Revision 3.0  1997/12/08 05:32:35  crh
  41  * This is a new major revision level because of a redesign of the handling
  42  * of the pointers in the ubi_trNode structure.  See ubi_BinTree for more
  43  * info.
  44  *
  45  * Revision 2;  1995/02/27 - 1997/12/07:
  46  * Major changes: added the function ubi_sptSplay().
  47  *
  48  * Revision 1; 93/10/15 - 95/02/27:
  49  * Added the ubi_tr defines.  See ubi_BinTree.h for more info.
  50  *
  51  * Revision 0.0  93/04/21  23:07:13  CRH
  52  * Initial version, written by Christopher R. Hertel.
  53  * This module implements Splay Trees using the ubi_BinTree module as a basis.
  54  *
  55  * ========================================================================== **
  56  */
  57
  58 #include "ubi_BinTree.h" /* Base binary tree functions, types, etc.  */
  59
  60 /* ========================================================================== **
  61  * Function prototypes...
  62  */
  63
  64 ubi_trBool ubi_sptInsert( ubi_btRootPtr  RootPtr,
  65                           ubi_btNodePtr  NewNode,
  66                           ubi_btItemPtr  ItemPtr,
  67                           ubi_btNodePtr *OldNode );
  68   /* ------------------------------------------------------------------------ **
  69    * This function uses a non-recursive algorithm to add a new element to the
  70    * splay tree.
  71    *
  72    *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
  73    *                       the root of the tree to which NewNode is to be added.
  74    *           NewNode  -  a pointer to an ubi_btNode structure that is NOT
  75    *                       part of any tree.
  76    *           ItemPtr  -  A pointer to the sort key that is stored within
  77    *                       *NewNode.  ItemPtr MUST point to information stored
  78    *                       in *NewNode or an EXACT DUPLICATE.  The key data
  79    *                       indicated by ItemPtr is used to place the new node
  80    *                       into the tree.
  81    *           OldNode  -  a pointer to an ubi_btNodePtr.  When searching
  82    *                       the tree, a duplicate node may be found.  If
  83    *                       duplicates are allowed, then the new node will
  84    *                       be simply placed into the tree.  If duplicates
  85    *                       are not allowed, however, then one of two things
  86    *                       may happen.
  87    *                       1) if overwritting *is not* allowed, this
  88    *                          function will return FALSE (indicating that
  89    *                          the new node could not be inserted), and
  90    *                          *OldNode will point to the duplicate that is
  91    *                          still in the tree.
  92    *                       2) if overwritting *is* allowed, then this
  93    *                          function will swap **OldNode for *NewNode.
  94    *                          In this case, *OldNode will point to the node
  95    *                          that was removed (thus allowing you to free
  96    *                          the node).
  97    *                          **  If you are using overwrite mode, ALWAYS  **
  98    *                          ** check the return value of this parameter! **
  99    *                 Note: You may pass NULL in this parameter, the
 100    *                       function knows how to cope.  If you do this,
 101    *                       however, there will be no way to return a
 102    *                       pointer to an old (ie. replaced) node (which is
 103    *                       a problem if you are using overwrite mode).
 104    *
 105    *  Output:  a boolean value indicating success or failure.  The function
 106    *           will return FALSE if the node could not be added to the tree.
 107    *           Such failure will only occur if duplicates are not allowed,
 108    *           nodes cannot be overwritten, AND a duplicate key was found
 109    *           within the tree.
 110    * ------------------------------------------------------------------------ **
 111    */
 112
 113 ubi_btNodePtr ubi_sptRemove( ubi_btRootPtr RootPtr, ubi_btNodePtr DeadNode );
 114   /* ------------------------------------------------------------------------ **
 115    * This function removes the indicated node from the tree.
 116    *
 117    *  Input:   RootPtr  -  A pointer to the header of the tree that contains
 118    *                       the node to be removed.
 119    *           DeadNode -  A pointer to the node that will be removed.
 120    *
 121    *  Output:  This function returns a pointer to the node that was removed
 122    *           from the tree (ie. the same as DeadNode).
 123    *
 124    *  Note:    The node MUST be in the tree indicated by RootPtr.  If not,
 125    *           strange and evil things will happen to your trees.
 126    * ------------------------------------------------------------------------ **
 127    */
 128
 129 ubi_btNodePtr ubi_sptLocate( ubi_btRootPtr RootPtr,
 130                              ubi_btItemPtr FindMe,
 131                              ubi_trCompOps CompOp );
 132   /* ------------------------------------------------------------------------ **
 133    * The purpose of ubi_btLocate() is to find a node or set of nodes given
 134    * a target value and a "comparison operator".  The Locate() function is
 135    * more flexible and (in the case of trees that may contain dupicate keys)
 136    * more precise than the ubi_btFind() function.  The latter is faster,
 137    * but it only searches for exact matches and, if the tree contains
 138    * duplicates, Find() may return a pointer to any one of the duplicate-
 139    * keyed records.
 140    *
 141    *  Input:
 142    *     RootPtr  -  A pointer to the header of the tree to be searched.
 143    *     FindMe   -  An ubi_btItemPtr that indicates the key for which to
 144    *                 search.
 145    *     CompOp   -  One of the following:
 146    *                    CompOp     Return a pointer to the node with
 147    *                    ------     ---------------------------------
 148    *                   ubi_trLT - the last key value that is less
 149    *                              than FindMe.
 150    *                   ubi_trLE - the first key matching FindMe, or
 151    *                              the last key that is less than
 152    *                              FindMe.
 153    *                   ubi_trEQ - the first key matching FindMe.
 154    *                   ubi_trGE - the first key matching FindMe, or the
 155    *                              first key greater than FindMe.
 156    *                   ubi_trGT - the first key greater than FindMe.
 157    *  Output:
 158    *     A pointer to the node matching the criteria listed above under
 159    *     CompOp, or NULL if no node matched the criteria.
 160    *
 161    *  Notes:
 162    *     In the case of trees with duplicate keys, Locate() will behave as
 163    *     follows:
 164    *
 165    *     Find:  3                       Find: 3
 166    *     Keys:  1 2 2 2 3 3 3 3 3 4 4   Keys: 1 1 2 2 2 4 4 5 5 5 6
 167    *                  ^ ^         ^                   ^ ^
 168    *                 LT EQ        GT                 LE GE
 169    *
 170    *     That is, when returning a pointer to a node with a key that is LESS
 171    *     THAN the target key (FindMe), Locate() will return a pointer to the
 172    *     LAST matching node.
 173    *     When returning a pointer to a node with a key that is GREATER
 174    *     THAN the target key (FindMe), Locate() will return a pointer to the
 175    *     FIRST matching node.
 176    *
 177    *  See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf().
 178    * ------------------------------------------------------------------------ **
 179    */
 180
 181 ubi_btNodePtr ubi_sptFind( ubi_btRootPtr RootPtr,
 182                            ubi_btItemPtr FindMe );
 183   /* ------------------------------------------------------------------------ **
 184    * This function performs a non-recursive search of a tree for any node
 185    * matching a specific key.
 186    *
 187    *  Input:
 188    *     RootPtr  -  a pointer to the header of the tree to be searched.
 189    *     FindMe   -  a pointer to the key value for which to search.
 190    *
 191    *  Output:
 192    *     A pointer to a node with a key that matches the key indicated by
 193    *     FindMe, or NULL if no such node was found.
 194    *
 195    *  Note:   In a tree that allows duplicates, the pointer returned *might
 196    *          not* point to the (sequentially) first occurance of the
 197    *          desired key.  In such a tree, it may be more useful to use
 198    *          ubi_sptLocate().
 199    * ------------------------------------------------------------------------ **
 200    */
 201
 202 void ubi_sptSplay( ubi_btRootPtr RootPtr,
 203                    ubi_btNodePtr SplayMe );
 204   /* ------------------------------------------------------------------------ **
 205    *  This function allows you to splay the tree at a given node, thus moving
 206    *  the node to the top of the tree.
 207    *
 208    *  Input:
 209    *     RootPtr  -  a pointer to the header of the tree to be splayed.
 210    *     SplayMe  -  a pointer to a node within the tree.  This will become
 211    *                 the new root node.
 212    *  Output: None.
 213    *
 214    *  Notes:  This is an uncharacteristic function for this group of modules
 215    *          in that it provides access to the internal balancing routines,
 216    *          which would normally be hidden.
 217    *          Splaying the tree will not damage it (assuming that I've done
 218    *          *my* job), but there is overhead involved.  I don't recommend
 219    *          that you use this function unless you understand the underlying
 220    *          Splay Tree.
 221    * ------------------------------------------------------------------------ **
 222    */
 223
 224 int ubi_sptModuleID( int size, char *list[] );
 225   /* ------------------------------------------------------------------------ **
 226    * Returns a set of strings that identify the module.
 227    *
 228    *  Input:  size  - The number of elements in the array <list>.
 229    *          list  - An array of pointers of type (char *).  This array
 230    *                  should, initially, be empty.  This function will fill
 231    *                  in the array with pointers to strings.
 232    *  Output: The number of elements of <list> that were used.  If this value
 233    *          is less than <size>, the values of the remaining elements are
 234    *          not guaranteed.
 235    *
 236    *  Notes:  Please keep in mind that the pointers returned indicate strings
 237    *          stored in static memory.  Don't free() them, don't write over
 238    *          them, etc.  Just read them.
 239    * ------------------------------------------------------------------------ **
 240    */
 241
 242 /* -------------------------------------------------------------------------- **
 243  * Masquarade...
 244  *
 245  * This set of defines allows you to write programs that will use any of the
 246  * implemented binary tree modules (currently BinTree, AVLtree, and SplayTree).
 247  * Instead of using ubi_bt..., use ubi_tr..., and select the tree type by
 248  * including the appropriate module header.
 249  */
 250
 251 #undef ubi_trInsert
 252 #undef ubi_trRemove
 253 #undef ubi_trLocate
 254 #undef ubi_trFind
 255 #undef ubi_trModuleID
 256
 257 #define ubi_trInsert( Rp, Nn, Ip, On ) \
 258         ubi_sptInsert( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Nn), \
 259                        (ubi_btItemPtr)(Ip), (ubi_btNodePtr *)(On) )
 260
 261 #define ubi_trRemove( Rp, Dn ) \
 262         ubi_sptRemove( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Dn) )
 263
 264 #define ubi_trLocate( Rp, Ip, Op ) \
 265         ubi_sptLocate( (ubi_btRootPtr)(Rp), \
 266                        (ubi_btItemPtr)(Ip), \
 267                        (ubi_trCompOps)(Op) )
 268
 269 #define ubi_trFind( Rp, Ip ) \
 270         ubi_sptFind( (ubi_btRootPtr)(Rp), (ubi_btItemPtr)(Ip) )
 271
 272 #define ubi_trModuleID( s, l ) ubi_sptModuleID( s, l )
 273
 274 /* ================================ The End ================================= */
 275 #endif /* ubi_SplayTree_H */
 276
 277
 278
 279
 280