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