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
_STUB_tsearch()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
treecompare(Dt_t * dt,char * one,char * two,Dtdisc_t * disc)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
tsearch(const Void_t * key,Void_t ** rootp,int (* comparf)(const Void_t *,const Void_t *))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
tfind(const Void_t * key,Void_t * const * rootp,int (* comparf)(const Void_t *,const Void_t *))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
tdelete(const Void_t * key,Void_t ** rootp,int (* comparf)(const Void_t *,const Void_t *))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
_twalk(Tree_t * obj,void (* action)(const Void_t *,VISIT,int),int level)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
twalk(const Void_t * root,void (* action)(const Void_t *,VISIT,int))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