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