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*                  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#include	"dthdr.h"
23
24/*	Ordered set/multiset
25**	dt:	dictionary being searched
26**	obj:	the object to look for.
27**	type:	search type.
28**
29**      Written by Kiem-Phong Vo (5/25/96)
30*/
31
32#if __STD_C
33static Void_t* dttree(Dt_t* dt, Void_t* obj, int type)
34#else
35static Void_t* dttree(dt,obj,type)
36Dt_t*		dt;
37Void_t* 	obj;
38int		type;
39#endif
40{
41	Dtlink_t	*root, *t;
42	int		cmp, lk, sz, ky;
43	Void_t		*o, *k, *key;
44	Dtlink_t	*l, *r, *me, link;
45	int		n, minp, turn[DT_MINP];
46	Dtcompar_f	cmpf;
47	Dtdisc_t*	disc;
48
49	UNFLATTEN(dt);
50	disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
51	dt->type &= ~DT_FOUND;
52
53	root = dt->data->here;
54	if(!obj)
55	{	if(!root || !(type&(DT_CLEAR|DT_FIRST|DT_LAST)) )
56			return NIL(Void_t*);
57
58		if(type&DT_CLEAR) /* delete all objects */
59		{	if(disc->freef || disc->link < 0)
60			{	do
61				{	while((t = root->left) )
62						RROTATE(root,t);
63					t = root->right;
64					if(disc->freef)
65						(*disc->freef)(dt,_DTOBJ(root,lk),disc);
66					if(disc->link < 0)
67						(*dt->memoryf)(dt,(Void_t*)root,0,disc);
68				} while((root = t) );
69			}
70
71			dt->data->size = 0;
72			dt->data->here = NIL(Dtlink_t*);
73			return NIL(Void_t*);
74		}
75		else /* computing largest/smallest element */
76		{	if(type&DT_LAST)
77			{	while((t = root->right) )
78					LROTATE(root,t);
79			}
80			else /* type&DT_FIRST */
81			{	while((t = root->left) )
82					RROTATE(root,t);
83			}
84
85			dt->data->here = root;
86			return _DTOBJ(root,lk);
87		}
88	}
89
90	/* note that link.right is LEFT tree and link.left is RIGHT tree */
91	l = r = &link;
92
93	/* allow apps to delete an object "actually" in the dictionary */
94	if(dt->meth->type == DT_OBAG && (type&(DT_DELETE|DT_DETACH)) )
95	{	key = _DTKEY(obj,ky,sz);
96		for(o = dtsearch(dt,obj); o; o = dtnext(dt,o) )
97		{	k = _DTKEY(o,ky,sz);
98			if(_DTCMP(dt,key,k,disc,cmpf,sz) != 0)
99				break;
100			if(o == obj)
101			{	root = dt->data->here;
102				l->right = root->left;
103				r->left  = root->right;
104				goto dt_delete;
105			}
106		}
107	}
108
109	if(type&(DT_MATCH|DT_SEARCH|DT_INSERT|DT_ATTACH))
110	{	key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
111		if(root)
112			goto do_search;
113	}
114	else if(type&DT_RENEW)
115	{	me = (Dtlink_t*)obj;
116		obj = _DTOBJ(me,lk);
117		key = _DTKEY(obj,ky,sz);
118		if(root)
119			goto do_search;
120	}
121	else if(root && _DTOBJ(root,lk) != obj)
122	{	key = _DTKEY(obj,ky,sz);
123	do_search:
124		if(dt->meth->type == DT_OSET &&
125		   (minp = dt->data->minp) != 0 && (type&(DT_MATCH|DT_SEARCH)) )
126		{	/* simple search, note that minp should be even */
127			for(t = root, n = 0; n < minp; ++n)
128			{	k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
129				if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) == 0)
130					return _DTOBJ(t,lk);
131				else
132				{	turn[n] = cmp;
133					if(!(t = cmp < 0 ? t->left : t->right) )
134						return NIL(Void_t*);
135				}
136			}
137
138			/* exceed search length, top-down splay now */
139			for(n = 0; n < minp; n += 2)
140			{	if(turn[n] < 0)
141				{	t = root->left;
142					if(turn[n+1] < 0)
143					{	rrotate(root,t);
144						rlink(r,t);
145						root = t->left;
146					}
147					else
148					{	llink(l,t);
149						rlink(r,root);
150						root = t->right;
151					}
152				}
153				else
154				{	t = root->right;
155					if(turn[n+1] > 0)
156					{	lrotate(root,t);
157						llink(l,t);
158						root = t->right;
159					}
160					else
161					{	rlink(r,t);
162						llink(l,root);
163						root = t->left;
164					}
165				}
166			}
167		}
168
169		while(1)
170		{	k = _DTOBJ(root,lk); k = _DTKEY(k,ky,sz);
171			if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) == 0)
172				break;
173			else if(cmp < 0)
174			{	if((t = root->left) )
175				{	k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
176					if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) < 0)
177					{	rrotate(root,t);
178						rlink(r,t);
179						if(!(root = t->left) )
180							break;
181					}
182					else if(cmp == 0)
183					{	rlink(r,root);
184						root = t;
185						break;
186					}
187					else /* if(cmp > 0) */
188					{	llink(l,t);
189						rlink(r,root);
190						if(!(root = t->right) )
191							break;
192					}
193				}
194				else
195				{	rlink(r,root);
196					root = NIL(Dtlink_t*);
197					break;
198				}
199			}
200			else /* if(cmp > 0) */
201			{	if((t = root->right) )
202				{	k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
203					if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) > 0)
204					{	lrotate(root,t);
205						llink(l,t);
206						if(!(root = t->right) )
207							break;
208					}
209					else if(cmp == 0)
210					{	llink(l,root);
211						root = t;
212						break;
213					}
214					else /* if(cmp < 0) */
215					{	rlink(r,t);
216						llink(l,root);
217						if(!(root = t->left) )
218							break;
219					}
220				}
221				else
222				{	llink(l,root);
223					root = NIL(Dtlink_t*);
224					break;
225				}
226			}
227		}
228	}
229
230	if(root)
231	{	/* found it, now isolate it */
232		dt->type |= DT_FOUND;
233		l->right = root->left;
234		r->left = root->right;
235
236		if(type&(DT_SEARCH|DT_MATCH))
237		{ has_root:
238			root->left = link.right;
239			root->right = link.left;
240			if((dt->meth->type&DT_OBAG) && (type&(DT_SEARCH|DT_MATCH)) )
241			{	key = _DTOBJ(root,lk); key = _DTKEY(key,ky,sz);
242				while((t = root->left) )
243				{	/* find max of left subtree */
244					while((r = t->right) )
245						LROTATE(t,r);
246					root->left = t;
247
248					/* now see if it's in the same group */
249					k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
250					if(_DTCMP(dt,key,k,disc,cmpf,sz) != 0)
251						break;
252					RROTATE(root,t);
253				}
254			}
255			dt->data->here = root;
256			return _DTOBJ(root,lk);
257		}
258		else if(type&DT_NEXT)
259		{	root->left = link.right;
260			root->right = NIL(Dtlink_t*);
261			link.right = root;
262		dt_next:
263			if((root = link.left) )
264			{	while((t = root->left) )
265					RROTATE(root,t);
266				link.left = root->right;
267				goto has_root;
268			}
269			else	goto no_root;
270		}
271		else if(type&DT_PREV)
272		{	root->right = link.left;
273			root->left = NIL(Dtlink_t*);
274			link.left = root;
275		dt_prev:
276			if((root = link.right) )
277			{	while((t = root->right) )
278					LROTATE(root,t);
279				link.right = root->left;
280				goto has_root;
281			}
282			else	goto no_root;
283		}
284		else if(type&(DT_DELETE|DT_DETACH))
285		{	/* taking an object out of the dictionary */
286		dt_delete:
287			obj = _DTOBJ(root,lk);
288			if(disc->freef && (type&DT_DELETE))
289				(*disc->freef)(dt,obj,disc);
290			if(disc->link < 0)
291				(*dt->memoryf)(dt,(Void_t*)root,0,disc);
292			if((dt->data->size -= 1) < 0)
293				dt->data->size = -1;
294			goto no_root;
295		}
296		else if(type&(DT_INSERT|DT_ATTACH))
297		{	if(dt->meth->type&DT_OSET)
298				goto has_root;
299			else
300			{	root->left = NIL(Dtlink_t*);
301				root->right = link.left;
302				link.left = root;
303				goto dt_insert;
304			}
305		}
306		else if(type&DT_RENEW) /* a duplicate */
307		{	if(dt->meth->type&DT_OSET)
308			{	if(disc->freef)
309					(*disc->freef)(dt,obj,disc);
310				if(disc->link < 0)
311					(*dt->memoryf)(dt,(Void_t*)me,0,disc);
312			}
313			else
314			{	me->left = NIL(Dtlink_t*);
315				me->right = link.left;
316				link.left = me;
317				dt->data->size += 1;
318			}
319			goto has_root;
320		}
321	}
322	else
323	{	/* not found, finish up LEFT and RIGHT trees */
324		r->left = NIL(Dtlink_t*);
325		l->right = NIL(Dtlink_t*);
326
327		if(type&DT_NEXT)
328			goto dt_next;
329		else if(type&DT_PREV)
330			goto dt_prev;
331		else if(type&(DT_SEARCH|DT_MATCH))
332		{ no_root:
333			while((t = r->left) )
334				r = t;
335			r->left = link.right;
336			dt->data->here = link.left;
337			return (type&DT_DELETE) ? obj : NIL(Void_t*);
338		}
339		else if(type&(DT_INSERT|DT_ATTACH))
340		{ dt_insert:
341			if(disc->makef && (type&DT_INSERT))
342				obj = (*disc->makef)(dt,obj,disc);
343			if(obj)
344			{	if(lk >= 0)
345					root = _DTLNK(obj,lk);
346				else
347				{	root = (Dtlink_t*)(*dt->memoryf)
348						(dt,NIL(Void_t*),sizeof(Dthold_t),disc);
349					if(root)
350						((Dthold_t*)root)->obj = obj;
351					else if(disc->makef && disc->freef &&
352						(type&DT_INSERT))
353						(*disc->freef)(dt,obj,disc);
354				}
355			}
356			if(root)
357			{	if(dt->data->size >= 0)
358					dt->data->size += 1;
359				goto has_root;
360			}
361			else	goto no_root;
362		}
363		else if(type&DT_RENEW)
364		{	root = me;
365			dt->data->size += 1;
366			goto has_root;
367		}
368		else /*if(type&DT_DELETE)*/
369		{	obj = NIL(Void_t*);
370			goto no_root;
371		}
372	}
373
374	return NIL(Void_t*);
375}
376
377/* make this method available */
378static Dtmethod_t	_Dtoset =  { dttree, DT_OSET };
379static Dtmethod_t	_Dtobag =  { dttree, DT_OBAG };
380__DEFINE__(Dtmethod_t*,Dtoset,&_Dtoset);
381__DEFINE__(Dtmethod_t*,Dtobag,&_Dtobag);
382
383#ifndef KPVDEL /* backward compatibility - delete next time around */
384Dtmethod_t		_Dttree = { dttree, DT_OSET };
385__DEFINE__(Dtmethod_t*,Dtorder,&_Dttree);
386__DEFINE__(Dtmethod_t*,Dttree,&_Dttree);
387#endif
388
389#ifdef NoF
390NoF(dttree)
391#endif
392