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 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 55extern 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 61typedef struct _tree_s 62{ Dtlink_t link; 63 Void_t* key; 64} Tree_t; 65 66typedef 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 77static int treecompare(Dt_t* dt, char* one, char* two, Dtdisc_t* disc) 78#else 79static int treecompare(dt, one, two, disc) 80Dt_t* dt; 81char* one; 82char* two; 83Dtdisc_t* disc; 84#endif 85{ 86 return (*((Treedisc_t*)disc)->comparf)((Void_t*)one,(Void_t*)two); 87} 88 89static 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 101extern 102#if __STD_C 103Void_t* tsearch(const Void_t* key, Void_t** rootp, 104 int(*comparf)(const Void_t*,const Void_t*) ) 105#else 106Void_t* tsearch(key, rootp, comparf) 107Void_t* key; 108Void_t** rootp; 109int(* 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 137extern 138#if __STD_C 139Void_t* tfind(const Void_t* key, Void_t*const* rootp, 140 int(*comparf)(const Void_t*, const Void_t*) ) 141#else 142Void_t* tfind(key, rootp, comparf) 143Void_t* key; 144Void_t** rootp; 145int(* 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*/ 163extern 164#if __STD_C 165Void_t* tdelete(const Void_t* key, Void_t** rootp, 166 int(*comparf)(const Void_t*, const Void_t*) ) 167#else 168Void_t* tdelete(key, rootp, comparf) 169Void_t* key; 170Void_t** rootp; 171int(* 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 201static void _twalk(Tree_t* obj, void(*action)(const Void_t*,VISIT,int), int level) 202#else 203static void _twalk(obj,action,level) 204Tree_t* obj; 205void(* action)(); 206int 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*/ 225extern 226#if __STD_C 227void twalk(const Void_t* root, void(*action)(const Void_t*,VISIT,int) ) 228#else 229void twalk(root, action) 230Void_t* root; 231void(* 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