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