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 * Eclipse Public License, Version 1.0 * 7 * by AT&T Intellectual Property * 8 * * 9 * A copy of the License is available at * 10 * http://www.eclipse.org/org/documents/epl-v10.html * 11 * (with md5 checksum b35adb5213ca9657e911e9befb180842) * 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 extern Void_t* dtfinger(Dt_t*); 56 57 /* POSIX tsearch library based on libcdt 58 ** Written by Kiem-Phong Vo (AT&T Research, 07/19/95) 59 */ 60 61 typedef struct _tree_s 62 { Dtlink_t link; 63 Void_t* key; 64 } Tree_t; 65 66 typedef struct _treedisc_s 67 { Dtdisc_t disc; 68 int(* comparf)_ARG_((const Void_t*, const Void_t*)); 69 } Treedisc_t; 70 71 #if defined(__EXPORT__) 72 #define extern __EXPORT__ 73 #endif 74 75 /* compare function */ 76 #if __STD_C 77 static int treecompare(Dt_t* dt, char* one, char* two, Dtdisc_t* disc) 78 #else 79 static int treecompare(dt, one, two, disc) 80 Dt_t* dt; 81 char* one; 82 char* two; 83 Dtdisc_t* disc; 84 #endif 85 { 86 return (*((Treedisc_t*)disc)->comparf)((Void_t*)one,(Void_t*)two); 87 } 88 89 static Treedisc_t Treedisc = 90 { { sizeof(Dtlink_t), -1, /* object is key */ 91 0, 92 NIL(Dtmake_f), NIL(Dtfree_f), 93 treecompare, 94 NIL(Dthash_f), 95 NIL(Dtmemory_f), 96 NIL(Dtevent_f) 97 }, 98 0 99 }; 100 101 extern 102 #if __STD_C 103 Void_t* tsearch(const Void_t* key, Void_t** rootp, 104 int(*comparf)(const Void_t*,const Void_t*) ) 105 #else 106 Void_t* tsearch(key, rootp, comparf) 107 Void_t* key; 108 Void_t** rootp; 109 int(* comparf)(); 110 #endif 111 { 112 reg Dt_t* dt; 113 reg Tree_t* o; 114 115 if(!rootp || 116 (!(dt = *((Dt_t**)rootp)) && !(dt = dtopen((Dtdisc_t*)(&Treedisc),Dtoset))) ) 117 return NIL(Void_t*); 118 119 /* dangerous to set comparf on each call but that's tsearch */ 120 Treedisc.comparf = comparf; 121 122 if(!(o = (Tree_t*)dtmatch(dt,key)) ) 123 { if(!(o = (Tree_t*)malloc(sizeof(Tree_t))) ) 124 return NIL(Void_t*); 125 o->key = (Void_t*)key; 126 dtinsert(dt,o); 127 } 128 129 if(o) 130 *rootp = (Void_t*)dt; 131 else if(*rootp == NIL(Void_t*) ) 132 dtclose(dt); 133 134 return (Void_t*)(&o->key); 135 } 136 137 extern 138 #if __STD_C 139 Void_t* tfind(const Void_t* key, Void_t*const* rootp, 140 int(*comparf)(const Void_t*, const Void_t*) ) 141 #else 142 Void_t* tfind(key, rootp, comparf) 143 Void_t* key; 144 Void_t** rootp; 145 int(* comparf)(); 146 #endif 147 { 148 reg Dt_t* dt; 149 reg Tree_t* o; 150 151 if(!rootp || !(dt = *((Dt_t**)rootp)) ) 152 return NIL(Void_t*); 153 Treedisc.comparf = comparf; 154 155 return (o = (Tree_t*)dtmatch(dt,key)) ? (Void_t*)(&o->key) : NIL(Void_t*); 156 } 157 158 /* the original tdelete() specifies that it will return the parent pointer 159 ** in the tree if there is one. Since we are using a splay tree, a deleted 160 ** node is always rotated to the root first. So this implementation always 161 ** returns the key of the new root. 162 */ 163 extern 164 #if __STD_C 165 Void_t* tdelete(const Void_t* key, Void_t** rootp, 166 int(*comparf)(const Void_t*, const Void_t*) ) 167 #else 168 Void_t* tdelete(key, rootp, comparf) 169 Void_t* key; 170 Void_t** rootp; 171 int(* comparf)(); 172 #endif 173 { 174 reg Dt_t* dt; 175 reg Tree_t* o; 176 Tree_t obj; 177 178 if(!rootp || !(dt = *((Dt_t**)rootp)) ) 179 return NIL(Void_t*); 180 181 Treedisc.comparf = comparf; 182 183 obj.key = (Void_t*)key; 184 dtdelete(dt,&obj); 185 186 if(!(o = dtfinger(dt)) ) 187 { dtclose(dt); 188 *rootp = NIL(Void_t*); 189 } 190 191 return o ? (Void_t*)(&o->key) : NIL(Void_t*); 192 } 193 194 /* the below routine assumes a particular layout of Dtlink_t. 195 ** If this ever gets changed, this routine should be redone. 196 */ 197 #define lchild link.lh.__left 198 #define rchild link.rh.__rght 199 200 #if __STD_C 201 static void _twalk(Tree_t* obj, void(*action)(const Void_t*,VISIT,int), int level) 202 #else 203 static void _twalk(obj,action,level) 204 Tree_t* obj; 205 void(* action)(); 206 int level; 207 #endif 208 { if(!obj->lchild && !obj->rchild) 209 (*action)((Void_t*)obj,leaf,level); 210 else 211 { (*action)((Void_t*)obj,preorder,level); 212 if(obj->lchild) 213 _twalk((Tree_t*)obj->lchild,action,level+1); 214 (*action)((Void_t*)obj,postorder,level); 215 if(obj->rchild) 216 _twalk((Tree_t*)obj->rchild,action,level+1); 217 (*action)((Void_t*)obj,endorder,level); 218 } 219 } 220 221 /* the original twalk allows specifying arbitrary node to start traversal. 222 ** Since our root is a dictionary structure, the search here will start 223 ** at whichever node happens to be current root. 224 */ 225 extern 226 #if __STD_C 227 void twalk(const Void_t* root, void(*action)(const Void_t*,VISIT,int) ) 228 #else 229 void twalk(root, action) 230 Void_t* root; 231 void(* action)(); 232 #endif 233 { 234 reg Tree_t* o; 235 236 if(root && (o = (Tree_t*)dtfinger((Dt_t*)root)) ) 237 _twalk(o,action,0); 238 } 239 240 #endif 241