1/*********************************************************************** 2* * 3* This software is part of the ast package * 4* Copyright (c) 1985-2011 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 33void _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 59typedef struct _tree_s 60{ Dtlink_t link; 61 Void_t* key; 62} Tree_t; 63 64typedef 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 75static int treecompare(Dt_t* dt, char* one, char* two, Dtdisc_t* disc) 76#else 77static int treecompare(dt, one, two, disc) 78Dt_t* dt; 79char* one; 80char* two; 81Dtdisc_t* disc; 82#endif 83{ 84 return (*((Treedisc_t*)disc)->comparf)((Void_t*)one,(Void_t*)two); 85} 86 87static 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 99extern 100#if __STD_C 101Void_t* tsearch(const Void_t* key, Void_t** rootp, 102 int(*comparf)(const Void_t*,const Void_t*) ) 103#else 104Void_t* tsearch(key, rootp, comparf) 105Void_t* key; 106Void_t** rootp; 107int(* 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 135extern 136#if __STD_C 137Void_t* tfind(const Void_t* key, Void_t*const* rootp, 138 int(*comparf)(const Void_t*, const Void_t*) ) 139#else 140Void_t* tfind(key, rootp, comparf) 141Void_t* key; 142Void_t** rootp; 143int(* 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*/ 161extern 162#if __STD_C 163Void_t* tdelete(const Void_t* key, Void_t** rootp, 164 int(*comparf)(const Void_t*, const Void_t*) ) 165#else 166Void_t* tdelete(key, rootp, comparf) 167Void_t* key; 168Void_t** rootp; 169int(* 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 199static void _twalk(Tree_t* obj, void(*action)(const Void_t*,VISIT,int), int level) 200#else 201static void _twalk(obj,action,level) 202Tree_t* obj; 203void(* action)(); 204int 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*/ 223extern 224#if __STD_C 225void twalk(const Void_t* root, void(*action)(const Void_t*,VISIT,int) ) 226#else 227void twalk(root, action) 228Void_t* root; 229void(* 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 239