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