1/***********************************************************************
2*                                                                      *
3*               This software is part of the ast package               *
4*          Copyright (c) 1985-2012 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#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
32typedef struct _dttree_s
33{	Dtdata_t	data;
34	Dtlink_t*	root;	/* tree root */
35} Dttree_t;
36
37#ifdef CDT_DEBUG
38int dttreeprint(Dt_t* dt, Dtlink_t* here, int lev, char* (*objprintf)(Void_t*) )
39{
40	int		k, rv;
41	char		*obj, *endb, buf[1024];
42	Dtdisc_t	*disc = dt->disc;
43	Dttree_t	*tree = (Dttree_t*)dt->data;
44
45	if(!here && !(here = tree->root) )
46		return -1;
47
48	endb = buf; /* indentation */
49	for(k = 0; k < lev; ++k)
50		{ *endb++ = ' '; *endb++ = ' '; }
51
52	*endb++ = '(';
53	obj = (*objprintf)(_DTOBJ(disc, here));
54	k = strlen(obj); memcpy(endb, obj, k); endb += k;
55	*endb++ = ')';
56	*endb++ = ':';
57	*endb++ = ' ';
58
59	*endb++ = '<';
60	if(here->_left)
61		obj = (*objprintf)(_DTOBJ(disc,here->_left));
62	else	obj = "NIL";
63	k = strlen(obj); memcpy(endb, obj, k); endb += k;
64	*endb++ = '>';
65	*endb++ = ' ';
66
67	*endb++ = '<';
68	if(here->_rght)
69		obj = (*objprintf)(_DTOBJ(disc,here->_rght));
70	else	obj = "NIL";
71	k = strlen(obj); memcpy(endb, obj, k); endb += k;
72	*endb++ = '>';
73	*endb++ = '\n';
74	write(2, buf, endb-buf);
75
76	if(here->_left)
77		dttreeprint(dt, here->_left, lev+1, objprintf);
78	if(here->_rght)
79		dttreeprint(dt, here->_rght, lev+1, objprintf);
80
81	return 0;
82}
83#endif
84
85/* terminal object: DT_FIRST|DT_LAST */
86#if __STD_C
87Void_t* tfirstlast(Dt_t* dt, int type)
88#else
89Void_t* tfirstlast(dt, type)
90Dt_t*	dt;
91int	type;
92#endif
93{
94	Dtlink_t	*t, *root;
95	Dtdisc_t	*disc = dt->disc;
96	Dttree_t	*tree = (Dttree_t*)dt->data;
97
98	if(!(root = tree->root) )
99		return NIL(Void_t*);
100
101	if(type&DT_LAST)
102	{	while((t = root->_rght) )
103			LROTATE(root,t);
104	}
105	else /* type&DT_FIRST */
106	{	while((t = root->_left) )
107			RROTATE(root,t);
108	}
109	tree->root = root;
110
111	return _DTOBJ(disc, root);
112}
113
114/* DT_CLEAR */
115#if __STD_C
116static Void_t* tclear(Dt_t* dt)
117#else
118static Void_t* tclear(dt)
119Dt_t*	dt;
120#endif
121{
122	Dtlink_t	*root, *t;
123	Dtdisc_t	*disc = dt->disc;
124	Dttree_t	*tree = (Dttree_t*)dt->data;
125
126	root = tree->root;
127	tree->root = NIL(Dtlink_t*);
128	tree->data.size = 0;
129
130	if(root && (disc->link < 0 || disc->freef) )
131	{	do
132		{	while((t = root->_left) )
133				RROTATE(root,t);
134			t = root->_rght;
135			_dtfree(dt, root, DT_DELETE);
136		} while((root = t) );
137	}
138
139	return NIL(Void_t*);
140}
141
142#if __STD_C
143static Void_t* tlist(Dt_t* dt, Dtlink_t* list, int type)
144#else
145static Void_t* tlist(dt, list, type)
146Dt_t*   	dt;
147Dtlink_t*	list;
148int     	type;
149#endif
150{
151	Void_t		*obj;
152	Dtlink_t	*last, *r, *t;
153	Dttree_t	*tree = (Dttree_t*)dt->data;
154	Dtdisc_t	*disc = dt->disc;
155
156	if(type&(DT_FLATTEN|DT_EXTRACT) )
157	{	if((list = tree->root) )
158		{	while((t = list->_left) ) /* make smallest object root */
159				RROTATE(list, t);
160			for(r = (last = list)->_rght; r; r = (last = r)->_rght)
161			{	while((t = r->_left) ) /* no left children */
162					RROTATE(r,t);
163				last->_rght = r;
164			}
165		}
166
167		if(type&DT_FLATTEN)
168			tree->root = list;
169		else
170		{	tree->root = NIL(Dtlink_t*);
171			dt->data->size = 0;
172		}
173	}
174	else /* if(type&DT_RESTORE) */
175	{	dt->data->size = 0;
176		for(r = list; r; r = t)
177		{	t = r->_rght;
178			obj = _DTOBJ(disc,r);
179			if((*dt->meth->searchf)(dt, (Void_t*)r, DT_RELINK) == obj )
180				dt->data->size += 1;
181		}
182	}
183
184	return (Void_t*)list;
185}
186
187#if __STD_C /* compute tree depth and number of nodes */
188static ssize_t tsize(Dtlink_t* root, ssize_t lev, Dtstat_t* st)
189#else
190static ssize_t tsize(root, lev, st)
191Dtlink_t*	root;
192ssize_t		lev;
193Dtstat_t*	st;
194#endif
195{
196	ssize_t		size, z;
197
198	if(!root) /* nothing to do */
199		return 0;
200
201	if(lev >= DT_MAXRECURSE) /* avoid blowing the stack */
202		return -1;
203
204	if(st)
205	{	st->mlev = lev > st->mlev ? lev : st->mlev;
206		if(lev < DT_MAXSIZE)
207		{	st->msize = lev > st->msize ? lev : st->msize;
208			st->lsize[lev] += 1; /* count #objects per level */
209		}
210	}
211
212	size = 1;
213
214	if((z = tsize(root->_left, lev+1, st)) < 0)
215		return -1;
216	else	size += z;
217
218	if((z = tsize(root->_rght, lev+1, st)) < 0)
219		return -1;
220	else	size += z;
221
222	return size;
223}
224
225#if __STD_C
226static Void_t* tstat(Dt_t* dt, Dtstat_t* st)
227#else
228static Void_t* tstat(dt, st)
229Dt_t*		dt;
230Dtstat_t*	st;
231#endif
232{
233	ssize_t		size;
234	Dttree_t	*tree = (Dttree_t*)dt->data;
235
236	if(!st)
237		return (Void_t*)dt->data->size;
238	else
239	{	memset(st, 0, sizeof(Dtstat_t));
240		size = tsize(tree->root, 0, st);
241		/**/DEBUG_ASSERT((dt->data->type&DT_SHARE) || size == dt->data->size);
242		st->meth  = dt->meth->type;
243		st->size  = size;
244		st->space = sizeof(Dttree_t) + (dt->disc->link >= 0 ? 0 : size*sizeof(Dthold_t));
245		return (Void_t*)size;
246	}
247}
248
249#if __STD_C /* make a list into a balanced tree */
250static Dtlink_t* tbalance(Dtlink_t* list, ssize_t size)
251#else
252static Dtlink_t* tbalance(list, size)
253Dtlink_t*	list;
254ssize_t		size;
255#endif
256{
257	ssize_t		n;
258	Dtlink_t	*l, *mid;
259
260	if(size <= 2)
261		return list;
262
263	for(l = list, n = size/2 - 1; n > 0; n -= 1)
264		l = l->_rght;
265
266	mid = l->_rght; l->_rght = NIL(Dtlink_t*);
267	mid->_left = tbalance(list, (n = size/2) );
268	mid->_rght = tbalance(mid->_rght, size - (n + 1));
269	return mid;
270}
271
272static void toptimize(Dt_t* dt)
273{
274	ssize_t		size;
275	Dtlink_t	*l, *list;
276	Dttree_t	*tree = (Dttree_t*)dt->data;
277
278	if((list = (Dtlink_t*)tlist(dt, NIL(Void_t*), DT_FLATTEN)) )
279	{	for(size = 0, l = list; l; l = l->_rght)
280			size += 1;
281		tree->root = tbalance(list, size);
282	}
283}
284
285static Dtlink_t* troot(Dt_t* dt, Dtlink_t* list, Dtlink_t* link, Void_t* obj, int type)
286{
287	Dtlink_t	*root, *last, *t, *r, *l;
288	Void_t		*key, *o, *k;
289	Dtdisc_t	*disc = dt->disc;
290
291	key = _DTKEY(disc, obj); /* key of object */
292
293	if(type&(DT_ATMOST|DT_ATLEAST) ) /* find the left-most or right-most element */
294	{	list->_left = link->_rght;
295		list->_rght = link->_left;
296		if(type&DT_ATMOST)
297		{	while((l = list->_left) )
298			{	while((r = l->_rght) ) /* get the max elt of left subtree */
299					LROTATE(l,r);
300				list->_left = l;
301
302				o = _DTOBJ(disc,l); k = _DTKEY(disc,o);
303				if(_DTCMP(dt, key, k, disc) != 0 )
304					break;
305				else	RROTATE(list,l);
306			}
307		}
308		else
309		{	while((r = list->_rght) )
310			{	while((l = r->_left) ) /* get the min elt of right subtree */
311					RROTATE(r,l);
312				list->_rght = r;
313
314				o = _DTOBJ(disc,r); k = _DTKEY(disc,o);
315				if(_DTCMP(dt, key, k, disc) != 0 )
316					break;
317				else	LROTATE(list,r);
318			}
319		}
320		link->_rght = list->_left;
321		link->_left = list->_rght;
322		return list;
323	}
324
325	last = list; list->_left = list->_rght = NIL(Dtlink_t*);
326	root = NIL(Dtlink_t*);
327
328	while(!root && (t = link->_rght) ) /* link->_rght is the left subtree <= obj */
329	{	while((r = t->_rght) ) /* make t the maximum element */
330			LROTATE(t,r);
331
332		o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
333		if(_DTCMP(dt, key, k, disc) != 0 )
334		{	link->_rght = t; /* no more of this group in subtree */
335			break;
336		}
337		else if((type & (DT_REMOVE|DT_NEXT|DT_PREV)) && o == obj)
338		{	link->_rght = t->_left; /* found the exact object */
339			root = t;
340		}
341		else /* add t to equal list in an order-preserving manner */
342		{	link->_rght = t->_left;
343			t->_left = t->_rght = NIL(Dtlink_t*);
344			if(type&DT_NEXT )
345				{ last->_left = t; last = t; }
346			else	{ t->_rght = list; list = t; }
347		}
348	}
349
350	while(!root && (t = link->_left) ) /* link->_left is the right subtree >= obj */
351	{	while((l = t->_left) ) /* make t the minimum element */
352			RROTATE(t,l);
353
354		o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
355		if(_DTCMP(dt, key, k, disc) != 0 )
356		{	link->_left = t; /* no more of this group in subtree */
357			break;
358		}
359		else if((type & (DT_REMOVE|DT_NEXT|DT_PREV)) && o == obj)
360		{	link->_left = t->_rght; /* found the exact object */
361			root = t;
362		}
363		else /* add t to equal list in an order-preserving manner */
364		{	link->_left = t->_rght;
365			t->_left = t->_rght = NIL(Dtlink_t*);
366			if(type&DT_NEXT )
367				{ t->_left = list; list = t; }
368			else	{ last->_rght = t; last = t; }
369		}
370	}
371
372	if(!root) /* always set a non-trivial root */
373	{	root = list;
374		if(type&DT_NEXT)
375			list = list->_left;
376		else	list = list->_rght;
377	}
378
379	if(list) /* add the rest of the equal-list to the proper subtree */
380	{	if(type&DT_NEXT)
381		{	last->_left = link->_rght;
382			link->_rght = list;
383		}
384		else
385		{	last->_rght = link->_left;
386			link->_left = list;
387		}
388	}
389
390	return root;
391}
392
393#if __STD_C
394static Void_t* dttree(Dt_t* dt, Void_t* obj, int type)
395#else
396static Void_t* dttree(dt,obj,type)
397Dt_t*		dt;
398Void_t* 	obj;
399int		type;
400#endif
401{
402	int		cmp;
403	Void_t		*o, *k, *key;
404	Dtlink_t	*root, *t, *l, *r, *me, link;
405	Dtdisc_t	*disc = dt->disc;
406	Dttree_t	*tree = (Dttree_t*)dt->data;
407
408	type = DTTYPE(dt, type); /* map type for upward compatibility */
409	if(!(type&DT_OPERATIONS) )
410		return NIL(Void_t*);
411
412	DTSETLOCK(dt);
413
414	if(type&(DT_FIRST|DT_LAST) )
415		DTRETURN(obj, tfirstlast(dt, type));
416	else if(type&(DT_EXTRACT|DT_RESTORE|DT_FLATTEN))
417		DTRETURN(obj, tlist(dt, (Dtlink_t*)obj, type));
418	else if(type&DT_CLEAR)
419		DTRETURN(obj, tclear(dt));
420	else if(type&DT_STAT)
421	{	toptimize(dt); /* balance tree to avoid deep recursion */
422		DTRETURN(obj, tstat(dt, (Dtstat_t*)obj));
423	}
424
425	if(!obj) /* from here on, an object prototype is required */
426		DTRETURN(obj, NIL(Void_t*));
427
428	if(type&DT_RELINK) /* relinking objects after some processing */
429	{	me = (Dtlink_t*)obj;
430		obj = _DTOBJ(disc,me);
431		key = _DTKEY(disc,obj);
432	}
433	else
434	{	me = NIL(Dtlink_t*);
435		if(type&DT_MATCH) /* no prototype object given, just the key */
436		{	key = obj;
437			obj = NIL(Void_t*);
438		}
439		else	key = _DTKEY(disc,obj); /* get key from prototype object */
440	}
441
442	memset(&link, 0, sizeof(link));
443	l = r = &link; /* link._rght(_left) will be LEFT(RIGHT) tree after splaying */
444	if((root = tree->root) && _DTOBJ(disc,root) != obj) /* splay-search for a matching object */
445	{	while(1)
446		{	o = _DTOBJ(disc,root); k = _DTKEY(disc,o);
447			if((cmp = _DTCMP(dt,key,k,disc)) == 0)
448				break;
449			else if(cmp < 0)
450			{	if((t = root->_left) )
451				{	o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
452					if((cmp = _DTCMP(dt,key,k,disc)) < 0)
453					{	rrotate(root,t);
454						rlink(r,t);
455						if(!(root = t->_left) )
456							break;
457					}
458					else if(cmp == 0)
459					{	rlink(r,root);
460						root = t;
461						break;
462					}
463					else /* if(cmp > 0) */
464					{	llink(l,t);
465						rlink(r,root);
466						if(!(root = t->_rght) )
467							break;
468					}
469				}
470				else
471				{	rlink(r,root);
472					root = NIL(Dtlink_t*);
473					break;
474				}
475			}
476			else /* if(cmp > 0) */
477			{	if((t = root->_rght) )
478				{	o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
479					if((cmp = _DTCMP(dt,key,k,disc)) > 0)
480					{	lrotate(root,t);
481						llink(l,t);
482						if(!(root = t->_rght) )
483							break;
484					}
485					else if(cmp == 0)
486					{	llink(l,root);
487						root = t;
488						break;
489					}
490					else /* if(cmp < 0) */
491					{	rlink(r,t);
492						llink(l,root);
493						if(!(root = t->_left) )
494							break;
495					}
496				}
497				else
498				{	llink(l,root);
499					root = NIL(Dtlink_t*);
500					break;
501				}
502			}
503		}
504	}
505	l->_rght = root ? root->_left : NIL(Dtlink_t*);
506	r->_left = root ? root->_rght : NIL(Dtlink_t*);
507
508	if(root)
509	{	if(dt->meth->type&DT_OBAG ) /* may need to reset root to the right object */
510		{	if((type&(DT_ATLEAST|DT_ATMOST)) ||
511			   ((type&(DT_NEXT|DT_PREV|DT_REMOVE)) && _DTOBJ(disc,root) != obj) )
512				root = troot(dt, root, &link, obj, type);
513		}
514
515		if(type&(DT_SEARCH|DT_MATCH|DT_ATMOST|DT_ATLEAST))
516		{ has_root: /* reconstitute the tree */
517			root->_left = link._rght;
518			root->_rght = link._left;
519			tree->root = root;
520			DTRETURN(obj, _DTOBJ(disc,root));
521		}
522		else if(type&DT_NEXT)
523		{	root->_left = link._rght;
524			root->_rght = NIL(Dtlink_t*);
525			link._rght = root;
526		dt_next:
527			if((root = link._left) )
528			{	while((t = root->_left) )
529					RROTATE(root,t);
530				link._left = root->_rght;
531				goto has_root;
532			}
533			else	goto no_root;
534		}
535		else if(type&DT_PREV)
536		{	root->_rght = link._left;
537			root->_left = NIL(Dtlink_t*);
538			link._left = root;
539		dt_prev:
540			if((root = link._rght) )
541			{	while((t = root->_rght) )
542					LROTATE(root,t);
543				link._rght = root->_left;
544				goto has_root;
545			}
546			else	goto no_root;
547		}
548		else if(type&DT_REMOVE) /* remove a particular element in the tree */
549		{	if(_DTOBJ(disc,root) == obj)
550				goto dt_delete;
551			else
552			{	root->_left = link._rght;
553				root->_rght = link._left;
554				tree->root = root;
555				DTRETURN(obj, NIL(Void_t*));
556			}
557		}
558		else if(type&(DT_DELETE|DT_DETACH))
559		{ dt_delete: /* remove an object from the dictionary */
560			obj = _DTOBJ(disc,root);
561			_dtfree(dt, root, type);
562			dt->data->size -= 1;
563			goto no_root;
564		}
565		else if(type&(DT_INSERT|DT_APPEND|DT_ATTACH))
566		{	if(dt->meth->type&DT_OSET)
567			{	type |= DT_SEARCH; /* for announcement */
568				goto has_root;
569			}
570			else
571			{	root->_left = NIL(Dtlink_t*);
572				root->_rght = link._left;
573				link._left = root;
574				goto dt_insert;
575			}
576		}
577		else if(type&DT_RELINK) /* a duplicate */
578		{	if(dt->meth->type&DT_OSET)
579				_dtfree(dt, me, DT_DELETE);
580			else
581			{	me->_left = NIL(Dtlink_t*);
582				me->_rght = link._left;
583				link._left = me;
584			}
585			goto has_root;
586		}
587	}
588	else /* no matching object, tree has been split to LEFT&RIGHT subtrees */
589	{	if(type&(DT_SEARCH|DT_MATCH))
590		{ no_root:
591			if(!(l = link._rght) ) /* no LEFT subtree */
592				tree->root = link._left; /* tree is RIGHT tree */
593			else
594			{	while((t = l->_rght) ) /* maximize root of LEFT tree */
595				{	if(t->_rght)
596						LLSHIFT(l,t);
597					else	LROTATE(l,t);
598				}
599				l->_rght = link._left; /* hook RIGHT tree to LEFT root */
600				tree->root = l; /* LEFT tree is now the entire tree */
601			}
602
603			if(type&(DT_DELETE|DT_DETACH|DT_REMOVE))
604				DTRETURN(obj, obj);
605			else	DTRETURN(obj, NIL(Void_t*));
606		}
607		else if(type&(DT_NEXT|DT_ATLEAST) )
608			goto dt_next;
609		else if(type&(DT_PREV|DT_ATMOST) )
610			goto dt_prev;
611		else if(type&(DT_DELETE|DT_DETACH|DT_REMOVE))
612		{	obj = NIL(Void_t*);
613			goto no_root;
614		}
615		else if(type&(DT_INSERT|DT_APPEND|DT_ATTACH))
616		{ dt_insert:
617			if(!(root = _dtmake(dt, obj, type)) )
618			{	obj = NIL(Void_t*);
619				goto no_root;
620			}
621			else
622			{	dt->data->size += 1;
623				goto has_root;
624			}
625		}
626		else if(type&DT_RELINK)
627		{	root = me;
628			goto has_root;
629		}
630	}
631	DTRETURN(obj, NIL(Void_t*));
632
633dt_return:
634	DTANNOUNCE(dt,obj,type);
635	DTCLRLOCK(dt);
636	return obj;
637}
638
639static int treeevent(Dt_t* dt, int event, Void_t* arg)
640{
641	Dttree_t	*tree = (Dttree_t*)dt->data;
642
643	if(event == DT_OPEN)
644	{	if(tree) /* already initialized */
645			return 0;
646		if(!(tree = (Dttree_t*)(*dt->memoryf)(dt, 0, sizeof(Dttree_t), dt->disc)) )
647		{	DTERROR(dt, "Error in allocating a tree data structure");
648			return -1;
649		}
650		memset(tree, 0, sizeof(Dttree_t));
651		dt->data = (Dtdata_t*)tree;
652		return 1;
653	}
654	else if(event == DT_CLOSE)
655	{	if(!tree)
656			return 0;
657		if(tree->root)
658			(void)tclear(dt);
659		(void)(*dt->memoryf)(dt, (Void_t*)tree, 0, dt->disc);
660                dt->data = NIL(Dtdata_t*);
661                return 0;
662	}
663	else if(event == DT_OPTIMIZE) /* balance the search tree */
664	{	toptimize(dt);
665		return 0;
666	}
667	else	return 0;
668}
669
670#if _UWIN
671
672Void_t* dtfinger(Dt_t* dt)
673{
674	return (dt && dt->meth && (dt->meth->type & DT_ORDERED)) ? (Void_t*)((Dttree_t*)dt->data)->root : NIL(Void_t*);
675}
676
677#endif
678
679/* make this method available */
680static Dtmethod_t	_Dtoset =  { dttree, DT_OSET, treeevent, "Dtoset" };
681static Dtmethod_t	_Dtobag =  { dttree, DT_OBAG, treeevent, "Dtobag" };
682__DEFINE__(Dtmethod_t*,Dtoset,&_Dtoset);
683__DEFINE__(Dtmethod_t*,Dtobag,&_Dtobag);
684
685/* backwards compatibility */
686#undef	Dttree
687#if defined(__EXPORT__)
688__EXPORT__
689#endif
690__DEFINE__(Dtmethod_t*,Dttree,&_Dtoset);
691
692#ifdef NoF
693NoF(dttree)
694#endif
695