usr/src/lib/libast/common/comp/tsearch.c

   1 /***********************************************************************
   2 *                                                                      *
   3 *               This software is part of the ast package               *
   4 *          Copyright (c) 1985-2010 AT&T Intellectual Property          *
   5 *                      and is licensed under the                       *
   6 *                  Common Public License, Version 1.0                  *
   7 *                    by AT&T Intellectual Property                     *
   8 *                                                                      *
   9 *                A copy of the License is available at                 *
  10 *            http://www.opensource.org/licenses/cpl1.0.txt             *
  11 *         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
  12 *                                                                      *
  13 *              Information and Software Systems Research               *
  14 *                            AT&T Research                             *
  15 *                           Florham Park NJ                            *
  16 *                                                                      *
  17 *                 Glenn Fowler <gsf@research.att.com>                  *
  18 *                  David Korn <dgk@research.att.com>                   *
  19 *                   Phong Vo <kpv@research.att.com>                    *
  20 *                                                                      *
  21 ***********************************************************************/
  22 /*
  23  * tsearch() for systems that have <search.h> but no tsearch()
  24  * why would such a system provide the interface but not the
  25  * implementation? that's what happens when one slimes their
  26  * way through standards compliance
  27  *
  28  * NOTE: please excuse the crude feature test
  29  */
  30
  31 #if !_UWIN
  32
  33 void _STUB_tsearch(){}
  34
  35 #else
  36
  37 #if _PACKAGE_ast
  38 #include        <ast.h>
  39 #endif
  40
  41 #define tdelete         ______tdelete
  42 #define tfind           ______tfind
  43 #define tsearch         ______tsearch
  44 #define twalk           ______twalk
  45
  46 #include        <search.h>
  47
  48 #undef  tdelete
  49 #undef  tfind
  50 #undef  tsearch
  51 #undef  twalk
  52
  53 #include        "dthdr.h"
  54
  55 /*      POSIX tsearch library based on libcdt
  56 **      Written by Kiem-Phong Vo (AT&T Research, 07/19/95)
  57 */
  58
  59 typedef struct _tree_s
  60 {       Dtlink_t        link;
  61         Void_t*         key;
  62 } Tree_t;
  63
  64 typedef struct _treedisc_s
  65 {       Dtdisc_t        disc;
  66         int(*           comparf)_ARG_((const Void_t*, const Void_t*));
  67 } Treedisc_t;
  68
  69 #if defined(__EXPORT__)
  70 #define extern  __EXPORT__
  71 #endif
  72
  73 /* compare function */
  74 #if __STD_C
  75 static int treecompare(Dt_t* dt, char* one, char* two, Dtdisc_t* disc)
  76 #else
  77 static int treecompare(dt, one, two, disc)
  78 Dt_t*           dt;
  79 char*           one;
  80 char*           two;
  81 Dtdisc_t*       disc;
  82 #endif
  83 {
  84         return (*((Treedisc_t*)disc)->comparf)((Void_t*)one,(Void_t*)two);
  85 }
  86
  87 static Treedisc_t       Treedisc =
  88 {       { sizeof(Dtlink_t), -1, /* object is key                */
  89           0,
  90           NIL(Dtmake_f), NIL(Dtfree_f),
  91           treecompare,
  92           NIL(Dthash_f),
  93           NIL(Dtmemory_f),
  94           NIL(Dtevent_f)
  95         },
  96         0
  97 };
  98
  99 extern
 100 #if __STD_C
 101 Void_t* tsearch(const Void_t* key, Void_t** rootp,
 102                 int(*comparf)(const Void_t*,const Void_t*) )
 103 #else
 104 Void_t* tsearch(key, rootp, comparf)
 105 Void_t*         key;
 106 Void_t**        rootp;
 107 int(*           comparf)();
 108 #endif
 109 {
 110         reg Dt_t*       dt;
 111         reg Tree_t*     o;
 112
 113         if(!rootp ||
 114            (!(dt = *((Dt_t**)rootp)) && !(dt = dtopen((Dtdisc_t*)(&Treedisc),Dtorder))) )
 115                 return NIL(Void_t*);
 116
 117         /* dangerous to set comparf on each call but that's tsearch */
 118         Treedisc.comparf = comparf;
 119
 120         if(!(o = (Tree_t*)dtmatch(dt,key)) )
 121         {       if(!(o = (Tree_t*)malloc(sizeof(Tree_t))) )
 122                         return NIL(Void_t*);
 123                 o->key = (Void_t*)key;
 124                 dtinsert(dt,o);
 125         }
 126
 127         if(o)
 128                 *rootp = (Void_t*)dt;
 129         else if(*rootp == NIL(Void_t*) )
 130                 dtclose(dt);
 131
 132         return (Void_t*)(&o->key);
 133 }
 134
 135 extern
 136 #if __STD_C
 137 Void_t* tfind(const Void_t* key, Void_t*const* rootp,
 138                 int(*comparf)(const Void_t*, const Void_t*) )
 139 #else
 140 Void_t* tfind(key, rootp, comparf)
 141 Void_t*         key;
 142 Void_t**        rootp;
 143 int(*           comparf)();
 144 #endif
 145 {
 146         reg Dt_t*       dt;
 147         reg Tree_t*     o;
 148
 149         if(!rootp || !(dt = *((Dt_t**)rootp)) )
 150                 return NIL(Void_t*);
 151         Treedisc.comparf = comparf;
 152
 153         return (o = (Tree_t*)dtmatch(dt,key)) ? (Void_t*)(&o->key) : NIL(Void_t*);
 154 }
 155
 156 /* the original tdelete() specifies that it will return the parent pointer
 157 ** in the tree if there is one. Since we are using a splay tree, a deleted
 158 ** node is always rotated to the root first. So this implementation always
 159 ** returns the key of the new root.
 160 */
 161 extern
 162 #if __STD_C
 163 Void_t* tdelete(const Void_t* key, Void_t** rootp,
 164                 int(*comparf)(const Void_t*, const Void_t*) )
 165 #else
 166 Void_t* tdelete(key, rootp, comparf)
 167 Void_t*         key;
 168 Void_t**        rootp;
 169 int(*           comparf)();
 170 #endif
 171 {
 172         reg Dt_t*       dt;
 173         reg Tree_t*     o;
 174         Tree_t          obj;
 175
 176         if(!rootp || !(dt = *((Dt_t**)rootp)) )
 177                 return NIL(Void_t*);
 178
 179         Treedisc.comparf = comparf;
 180
 181         obj.key = (Void_t*)key;
 182         dtdelete(dt,&obj);
 183
 184         if(!(o = dtfinger(dt)) )
 185         {       dtclose(dt);
 186                 *rootp = NIL(Void_t*);
 187         }
 188
 189         return o ? (Void_t*)(&o->key) : NIL(Void_t*);
 190 }
 191
 192 /* the below routine assumes a particular layout of Dtlink_t.
 193 ** If this ever gets changed, this routine should be redone.
 194 */
 195 #define lchild  link.hl._left
 196 #define rchild  link.right
 197
 198 #if __STD_C
 199 static void _twalk(Tree_t* obj, void(*action)(const Void_t*,VISIT,int), int level)
 200 #else
 201 static void _twalk(obj,action,level)
 202 Tree_t* obj;
 203 void(*          action)();
 204 int             level;
 205 #endif
 206 {       if(!obj->lchild && !obj->rchild)
 207                 (*action)((Void_t*)obj,leaf,level);
 208         else
 209         {       (*action)((Void_t*)obj,preorder,level);
 210                 if(obj->lchild)
 211                         _twalk((Tree_t*)obj->lchild,action,level+1);
 212                 (*action)((Void_t*)obj,postorder,level);
 213                 if(obj->rchild)
 214                         _twalk((Tree_t*)obj->rchild,action,level+1);
 215                 (*action)((Void_t*)obj,endorder,level);
 216         }
 217 }
 218
 219 /* the original twalk allows specifying arbitrary node to start traversal.
 220 ** Since our root is a dictionary structure, the search here will start
 221 ** at whichever node happens to be current root.
 222 */
 223 extern
 224 #if __STD_C
 225 void twalk(const Void_t* root, void(*action)(const Void_t*,VISIT,int) )
 226 #else
 227 void twalk(root, action)
 228 Void_t* root;
 229 void(*  action)();
 230 #endif
 231 {
 232         reg Tree_t*     o;
 233
 234         if(root && (o = (Tree_t*)dtfinger((Dt_t*)root)) )
 235                 _twalk(o,action,0);
 236 }
 237
 238 #endif