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
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
55/*	POSIX tsearch library based on libcdt
56**	Written by Kiem-Phong Vo (AT&T Research, 07/19/95)
57*/
58
59typedef struct _tree_s
60{	Dtlink_t	link;
61	Void_t*		key;
62} Tree_t;
63
64typedef 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
75static int treecompare(Dt_t* dt, char* one, char* two, Dtdisc_t* disc)
76#else
77static int treecompare(dt, one, two, disc)
78Dt_t*		dt;
79char*		one;
80char*		two;
81Dtdisc_t*	disc;
82#endif
83{
84	return (*((Treedisc_t*)disc)->comparf)((Void_t*)one,(Void_t*)two);
85}
86
87static 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
99extern
100#if __STD_C
101Void_t* tsearch(const Void_t* key, Void_t** rootp,
102		int(*comparf)(const Void_t*,const Void_t*) )
103#else
104Void_t* tsearch(key, rootp, comparf)
105Void_t*		key;
106Void_t**	rootp;
107int(*		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
135extern
136#if __STD_C
137Void_t* tfind(const Void_t* key, Void_t*const* rootp,
138		int(*comparf)(const Void_t*, const Void_t*) )
139#else
140Void_t* tfind(key, rootp, comparf)
141Void_t*		key;
142Void_t**	rootp;
143int(*		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*/
161extern
162#if __STD_C
163Void_t* tdelete(const Void_t* key, Void_t** rootp,
164		int(*comparf)(const Void_t*, const Void_t*) )
165#else
166Void_t* tdelete(key, rootp, comparf)
167Void_t*		key;
168Void_t**	rootp;
169int(*		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
199static void _twalk(Tree_t* obj, void(*action)(const Void_t*,VISIT,int), int level)
200#else
201static void _twalk(obj,action,level)
202Tree_t*	obj;
203void(*		action)();
204int		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*/
223extern
224#if __STD_C
225void twalk(const Void_t* root, void(*action)(const Void_t*,VISIT,int) )
226#else
227void twalk(root, action)
228Void_t*	root;
229void(*	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