1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2007 AT&T Knowledge Ventures * 5 * and is licensed under the * 6 * Common Public License, Version 1.0 * 7 * by AT&T Knowledge Ventures * 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 239