Imported Upstream version 93u+upstream

1 files changed, 696 insertions, 0 deletions

diff --git a/src/lib/libast/cdt/dttree.c b/src/lib/libast/cdt/dttree.c
new file mode 100644
index 0000000..2dd31d3
--- /dev/null
+++ b/src/lib/libast/cdt/dttree.c
@@ -0,0 +1,696 @@
+/***********************************************************************
+*                                                                      *
+*               This software is part of the ast package               *
+*          Copyright (c) 1985-2011 AT&T Intellectual Property          *
+*                      and is licensed under the                       *
+*                 Eclipse Public License, Version 1.0                  *
+*                    by AT&T Intellectual Property                     *
+*                                                                      *
+*                A copy of the License is available at                 *
+*          http://www.eclipse.org/org/documents/epl-v10.html           *
+*         (with md5 checksum b35adb5213ca9657e911e9befb180842)         *
+*                                                                      *
+*              Information and Software Systems Research               *
+*                            AT&T Research                             *
+*                           Florham Park NJ                            *
+*                                                                      *
+*                 Glenn Fowler <gsf@research.att.com>                  *
+*                  David Korn <dgk@research.att.com>                   *
+*                   Phong Vo <kpv@research.att.com>                    *
+*                                                                      *
+***********************************************************************/
+#include	"dthdr.h"
+
+/*	Ordered set/multiset
+**	dt:	dictionary being searched
+**	obj:	the object to look for.
+**	type:	search type.
+**
+**      Written by Kiem-Phong Vo (5/25/96)
+*/
+
+typedef struct _dttree_s
+{	Dtdata_t	data;
+	Dtlink_t*	root;	/* tree root */
+} Dttree_t;
+
+#ifdef CDT_DEBUG
+int dttreeprint(Dt_t* dt, Dtlink_t* here, int lev, char* (*objprintf)(Void_t*) )
+{
+	int		k, rv;
+	char		*obj, *endb, buf[1024];
+	Dtdisc_t	*disc = dt->disc;
+	Dttree_t	*tree = (Dttree_t*)dt->data;
+
+	if(!here && !(here = tree->root) )
+		return -1;
+
+	endb = buf; /* indentation */
+	for(k = 0; k < lev; ++k)
+		{ *endb++ = ' '; *endb++ = ' '; }
+
+	*endb++ = '(';
+	obj = (*objprintf)(_DTOBJ(disc, here));
+	k = strlen(obj); memcpy(endb, obj, k); endb += k;
+	*endb++ = ')';
+	*endb++ = ':';
+	*endb++ = ' ';
+
+	*endb++ = '<';
+	if(here->_left)
+		obj = (*objprintf)(_DTOBJ(disc,here->_left)); 
+	else	obj = "NIL";
+	k = strlen(obj); memcpy(endb, obj, k); endb += k;
+	*endb++ = '>';
+	*endb++ = ' ';
+
+	*endb++ = '<';
+	if(here->_rght)
+		obj = (*objprintf)(_DTOBJ(disc,here->_rght)); 
+	else	obj = "NIL";
+	k = strlen(obj); memcpy(endb, obj, k); endb += k;
+	*endb++ = '>';
+	*endb++ = '\n';
+	write(2, buf, endb-buf);
+
+	if(here->_left)
+		dttreeprint(dt, here->_left, lev+1, objprintf);
+	if(here->_rght)
+		dttreeprint(dt, here->_rght, lev+1, objprintf);
+
+	return 0;
+}
+#endif
+
+/* terminal object: DT_FIRST|DT_LAST */
+#if __STD_C
+Void_t* tfirstlast(Dt_t* dt, int type)
+#else
+Void_t* tfirstlast(dt, type)
+Dt_t*	dt;
+int	type;
+#endif
+{
+	Dtlink_t	*t, *root;
+	Dtdisc_t	*disc = dt->disc;
+	Dttree_t	*tree = (Dttree_t*)dt->data;
+
+	if(!(root = tree->root) )
+		return NIL(Void_t*);
+
+	if(type&DT_LAST)
+	{	while((t = root->_rght) )
+			LROTATE(root,t);
+	}
+	else /* type&DT_FIRST */
+	{	while((t = root->_left) )
+			RROTATE(root,t);
+	}
+	tree->root = root;
+
+	return _DTOBJ(disc, root);
+}
+
+/* DT_CLEAR */
+#if __STD_C
+static Void_t* tclear(Dt_t* dt)
+#else
+static Void_t* tclear(dt)
+Dt_t*	dt;
+#endif
+{
+	Dtlink_t	*root, *t;
+	Dtdisc_t	*disc = dt->disc;
+	Dttree_t	*tree = (Dttree_t*)dt->data;
+
+	root = tree->root;
+	tree->root = NIL(Dtlink_t*);
+	tree->data.size = 0;
+
+	if(root && (disc->link < 0 || disc->freef) )
+	{	do
+		{	while((t = root->_left) )
+				RROTATE(root,t);
+			t = root->_rght;
+			_dtfree(dt, root, DT_DELETE);
+		} while((root = t) );
+	}
+
+	return NIL(Void_t*);
+}
+
+#if __STD_C
+static Void_t* tlist(Dt_t* dt, Dtlink_t* list, int type)
+#else
+static Void_t* tlist(dt, list, type)
+Dt_t*   	dt;
+Dtlink_t*	list;    
+int     	type;
+#endif
+{
+	Void_t		*obj;
+	Dtlink_t	*last, *r, *t;
+	Dttree_t	*tree = (Dttree_t*)dt->data;
+	Dtdisc_t	*disc = dt->disc;
+
+	if(type&(DT_FLATTEN|DT_EXTRACT) )
+	{	if((list = tree->root) )
+		{	while((t = list->_left) ) /* make smallest object root */
+				RROTATE(list, t);
+			for(r = (last = list)->_rght; r; r = (last = r)->_rght)
+			{	while((t = r->_left) ) /* no left children */
+					RROTATE(r,t);
+				last->_rght = r;
+			}
+		}
+
+		if(type&DT_FLATTEN)
+			tree->root = list;
+		else
+		{	tree->root = NIL(Dtlink_t*);
+			dt->data->size = 0;
+		}
+	}
+	else /* if(type&DT_RESTORE) */
+	{	dt->data->size = 0;
+		for(r = list; r; r = t)
+		{	t = r->_rght;
+			obj = _DTOBJ(disc,r);
+			if((*dt->meth->searchf)(dt, (Void_t*)r, DT_RELINK) == obj )
+				dt->data->size += 1;
+		}
+	}
+
+	return (Void_t*)list;
+}
+
+#if __STD_C /* compute tree depth and number of nodes */
+static ssize_t tsize(Dtlink_t* root, ssize_t lev, Dtstat_t* st)
+#else
+static ssize_t tsize(root, lev, st)
+Dtlink_t*	root;
+ssize_t		lev;
+Dtstat_t*	st;
+#endif
+{
+	ssize_t		size, z;
+
+	if(!root) /* nothing to do */
+		return 0;
+
+	if(lev >= DT_MAXRECURSE) /* avoid blowing the stack */
+		return -1;
+
+	if(st)
+	{	st->mlev = lev > st->mlev ? lev : st->mlev;
+		if(lev < DT_MAXSIZE)
+		{	st->msize = lev > st->msize ? lev : st->msize;
+			st->lsize[lev] += 1; /* count #objects per level */
+		}
+	}
+
+	size = 1;
+
+	if((z = tsize(root->_left, lev+1, st)) < 0)
+		return -1;
+	else	size += z;
+
+	if((z = tsize(root->_rght, lev+1, st)) < 0)
+		return -1;
+	else	size += z;
+
+	return size;
+}
+
+#if __STD_C
+static Void_t* tstat(Dt_t* dt, Dtstat_t* st)
+#else
+static Void_t* tstat(dt, st)
+Dt_t*		dt;
+Dtstat_t*	st;
+#endif
+{
+	ssize_t		size;
+	Dttree_t	*tree = (Dttree_t*)dt->data;
+
+	if(!st)
+		return (Void_t*)dt->data->size;
+	else
+	{	memset(st, 0, sizeof(Dtstat_t));
+		size = tsize(tree->root, 0, st);
+		/**/DEBUG_ASSERT((dt->data->type&DT_SHARE) || size == dt->data->size);
+		st->meth  = dt->meth->type;
+		st->size  = size;
+		st->space = sizeof(Dttree_t) + (dt->disc->link >= 0 ? 0 : size*sizeof(Dthold_t));
+		return (Void_t*)size;
+	}
+}
+
+#if __STD_C /* make a list into a balanced tree */
+static Dtlink_t* tbalance(Dtlink_t* list, ssize_t size)
+#else
+static Dtlink_t* tbalance(list, size)
+Dtlink_t*	list;
+ssize_t		size;
+#endif
+{
+	ssize_t		n;
+	Dtlink_t	*l, *mid;
+
+	if(size <= 2)
+		return list;
+
+	for(l = list, n = size/2 - 1; n > 0; n -= 1)
+		l = l->_rght;
+
+	mid = l->_rght; l->_rght = NIL(Dtlink_t*);
+	mid->_left = tbalance(list, (n = size/2) );
+	mid->_rght = tbalance(mid->_rght, size - (n + 1));
+	return mid;
+}
+
+static void toptimize(Dt_t* dt)
+{
+	ssize_t		size;
+	Dtlink_t	*l, *list;
+	Dttree_t	*tree = (Dttree_t*)dt->data;
+
+	if((list = (Dtlink_t*)tlist(dt, NIL(Void_t*), DT_FLATTEN)) )
+	{	for(size = 0, l = list; l; l = l->_rght)
+			size += 1;
+		tree->root = tbalance(list, size);
+	}
+}
+
+static Dtlink_t* troot(Dt_t* dt, Dtlink_t* list, Dtlink_t* link, Void_t* obj, int type)
+{
+	Dtlink_t	*root, *last, *t, *r, *l;
+	Void_t		*key, *o, *k;
+	Dtdisc_t	*disc = dt->disc;
+
+	key = _DTKEY(disc, obj); /* key of object */
+
+	if(type&(DT_ATMOST|DT_ATLEAST) ) /* find the left-most or right-most element */
+	{	list->_left = link->_rght;
+		list->_rght = link->_left;
+		if(type&DT_ATMOST)
+		{	while((l = list->_left) )
+			{	while((r = l->_rght) ) /* get the max elt of left subtree */
+					LROTATE(l,r);
+				list->_left = l;
+
+				o = _DTOBJ(disc,l); k = _DTKEY(disc,o);
+				if(_DTCMP(dt, key, k, disc) != 0 )
+					break;
+				else	RROTATE(list,l);
+			}
+		}
+		else
+		{	while((r = list->_rght) )
+			{	while((l = r->_left) ) /* get the min elt of right subtree */
+					RROTATE(r,l);
+				list->_rght = r;
+
+				o = _DTOBJ(disc,r); k = _DTKEY(disc,o);
+				if(_DTCMP(dt, key, k, disc) != 0 )
+					break;
+				else	LROTATE(list,r);
+			}
+		}
+		link->_rght = list->_left;
+		link->_left = list->_rght;
+		return list;
+	}
+
+	last = list; list->_left = list->_rght = NIL(Dtlink_t*);
+	root = NIL(Dtlink_t*);
+
+	while(!root && (t = link->_rght) ) /* link->_rght is the left subtree <= obj */
+	{	while((r = t->_rght) ) /* make t the maximum element */
+			LROTATE(t,r);
+
+		o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
+		if(_DTCMP(dt, key, k, disc) != 0 )
+		{	link->_rght = t; /* no more of this group in subtree */
+			break;
+		}
+		else if((type & (DT_REMOVE|DT_NEXT|DT_PREV)) && o == obj)
+		{	link->_rght = t->_left; /* found the exact object */
+			root = t;
+		}
+		else /* add t to equal list in an order-preserving manner */
+		{	link->_rght = t->_left;
+			t->_left = t->_rght = NIL(Dtlink_t*);
+			if(type&DT_NEXT )
+				{ last->_left = t; last = t; }
+			else	{ t->_rght = list; list = t; }
+		}
+	}
+
+	while(!root && (t = link->_left) ) /* link->_left is the right subtree >= obj */
+	{	while((l = t->_left) ) /* make t the minimum element */
+			RROTATE(t,l);
+
+		o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
+		if(_DTCMP(dt, key, k, disc) != 0 )
+		{	link->_left = t; /* no more of this group in subtree */
+			break; 
+		}
+		else if((type & (DT_REMOVE|DT_NEXT|DT_PREV)) && o == obj)
+		{	link->_left = t->_rght; /* found the exact object */
+			root = t;
+		}
+		else /* add t to equal list in an order-preserving manner */
+		{	link->_left = t->_rght;
+			t->_left = t->_rght = NIL(Dtlink_t*);
+			if(type&DT_NEXT )
+				{ t->_left = list; list = t; }
+			else	{ last->_rght = t; last = t; }
+		}
+	}
+
+	if(!root) /* always set a non-trivial root */
+	{	root = list;
+		if(type&DT_NEXT)
+			list = list->_left;
+		else	list = list->_rght;
+	}
+
+	if(list) /* add the rest of the equal-list to the proper subtree */
+	{	if(type&DT_NEXT) 
+		{	last->_left = link->_rght;
+			link->_rght = list;
+		}
+		else
+		{	last->_rght = link->_left;
+			link->_left = list;
+		}
+	}
+
+	return root;
+}
+
+#if __STD_C
+static Void_t* dttree(Dt_t* dt, Void_t* obj, int type)
+#else
+static Void_t* dttree(dt,obj,type)
+Dt_t*		dt;
+Void_t* 	obj;
+int		type;
+#endif
+{
+	int		cmp;
+	Void_t		*o, *k, *key;
+	Dtlink_t	*root, *t, *l, *r, *me, link;
+	Dtdisc_t	*disc = dt->disc;
+	Dttree_t	*tree = (Dttree_t*)dt->data;
+
+	type = DTTYPE(dt, type); /* map type for upward compatibility */
+	if(!(type&DT_OPERATIONS) )
+		return NIL(Void_t*);
+
+	DTSETLOCK(dt);
+
+	if(type&(DT_FIRST|DT_LAST) )
+		DTRETURN(obj, tfirstlast(dt, type));
+	else if(type&(DT_EXTRACT|DT_RESTORE|DT_FLATTEN))
+		DTRETURN(obj, tlist(dt, (Dtlink_t*)obj, type));
+	else if(type&DT_CLEAR)
+		DTRETURN(obj, tclear(dt));
+	else if(type&DT_STAT)
+	{	toptimize(dt); /* balance tree to avoid deep recursion */
+		DTRETURN(obj, tstat(dt, (Dtstat_t*)obj));
+	}
+
+	if(!obj) /* from here on, an object prototype is required */
+		DTRETURN(obj, NIL(Void_t*));
+
+	if(type&DT_RELINK) /* relinking objects after some processing */
+	{	me = (Dtlink_t*)obj;
+		obj = _DTOBJ(disc,me);
+		key = _DTKEY(disc,obj);
+	}
+	else
+	{	me = NIL(Dtlink_t*);
+		if(type&DT_MATCH) /* no prototype object given, just the key */
+		{	key = obj;
+			obj = NIL(Void_t*);
+		}
+		else	key = _DTKEY(disc,obj); /* get key from prototype object */
+	}
+
+	memset(&link, 0, sizeof(link));
+	l = r = &link; /* link._rght(_left) will be LEFT(RIGHT) tree after splaying */
+	if((root = tree->root) && _DTOBJ(disc,root) != obj) /* splay-search for a matching object */
+	{	while(1)
+		{	o = _DTOBJ(disc,root); k = _DTKEY(disc,o);
+			if((cmp = _DTCMP(dt,key,k,disc)) == 0)
+				break;
+			else if(cmp < 0)
+			{	if((t = root->_left) )
+				{	o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
+					if((cmp = _DTCMP(dt,key,k,disc)) < 0)
+					{	rrotate(root,t);
+						rlink(r,t);
+						if(!(root = t->_left) )
+							break;
+					}
+					else if(cmp == 0)
+					{	rlink(r,root);
+						root = t;
+						break;
+					}
+					else /* if(cmp > 0) */
+					{	llink(l,t);
+						rlink(r,root);
+						if(!(root = t->_rght) )
+							break;
+					}
+				}
+				else
+				{	rlink(r,root);
+					root = NIL(Dtlink_t*);
+					break;
+				}
+			}
+			else /* if(cmp > 0) */
+			{	if((t = root->_rght) )
+				{	o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
+					if((cmp = _DTCMP(dt,key,k,disc)) > 0)
+					{	lrotate(root,t);
+						llink(l,t);
+						if(!(root = t->_rght) )
+							break;
+					}
+					else if(cmp == 0)
+					{	llink(l,root);
+						root = t;
+						break;
+					}
+					else /* if(cmp < 0) */
+					{	rlink(r,t);
+						llink(l,root);
+						if(!(root = t->_left) )
+							break;
+					}
+				}
+				else
+				{	llink(l,root);
+					root = NIL(Dtlink_t*);
+					break;
+				}
+			}
+		}
+	}
+	l->_rght = root ? root->_left : NIL(Dtlink_t*);
+	r->_left = root ? root->_rght : NIL(Dtlink_t*);
+
+	if(root)
+	{	if(dt->meth->type&DT_OBAG ) /* may need to reset root to the right object */
+		{	if((type&(DT_ATLEAST|DT_ATMOST)) ||
+			   ((type&(DT_NEXT|DT_PREV|DT_REMOVE)) && _DTOBJ(disc,root) != obj) )
+				root = troot(dt, root, &link, obj, type);
+		}
+
+		if(type&(DT_SEARCH|DT_MATCH|DT_ATMOST|DT_ATLEAST))
+		{ has_root: /* reconstitute the tree */
+			root->_left = link._rght;
+			root->_rght = link._left;
+			tree->root = root;
+			DTRETURN(obj, _DTOBJ(disc,root));
+		}
+		else if(type&DT_NEXT)
+		{	root->_left = link._rght;
+			root->_rght = NIL(Dtlink_t*);
+			link._rght = root;
+		dt_next:
+			if((root = link._left) )	
+			{	while((t = root->_left) )
+					RROTATE(root,t);
+				link._left = root->_rght;
+				goto has_root;
+			}
+			else	goto no_root;
+		}
+		else if(type&DT_PREV)
+		{	root->_rght = link._left;
+			root->_left = NIL(Dtlink_t*);
+			link._left = root;
+		dt_prev:
+			if((root = link._rght) )
+			{	while((t = root->_rght) )
+					LROTATE(root,t);
+				link._rght = root->_left;
+				goto has_root;
+			}
+			else	goto no_root;
+		}
+		else if(type&DT_REMOVE) /* remove a particular element in the tree */
+		{	if(_DTOBJ(disc,root) == obj)
+				goto dt_delete;
+			else
+			{	root->_left = link._rght;
+				root->_rght = link._left;
+				tree->root = root; 
+				DTRETURN(obj, NIL(Void_t*));
+			}
+		}
+		else if(type&(DT_DELETE|DT_DETACH))
+		{ dt_delete: /* remove an object from the dictionary */
+			obj = _DTOBJ(disc,root);
+			_dtfree(dt, root, type);
+			dt->data->size -= 1;
+			goto no_root;
+		}
+		else if(type&(DT_INSERT|DT_APPEND|DT_ATTACH))
+		{	if(dt->meth->type&DT_OSET)
+			{	type |= DT_SEARCH; /* for announcement */
+				goto has_root;
+			}
+			else
+			{	root->_left = NIL(Dtlink_t*);
+				root->_rght = link._left;
+				link._left = root;
+				goto dt_insert;
+			}
+		}
+		else if(type&DT_RELINK) /* a duplicate */
+		{	if(dt->meth->type&DT_OSET)
+				_dtfree(dt, me, DT_DELETE);
+			else
+			{	me->_left = NIL(Dtlink_t*);
+				me->_rght = link._left;
+				link._left = me;
+			}
+			goto has_root;
+		}
+	}
+	else /* no matching object, tree has been split to LEFT&RIGHT subtrees */
+	{	if(type&(DT_SEARCH|DT_MATCH))
+		{ no_root: 
+			if(!(l = link._rght) ) /* no LEFT subtree */
+				tree->root = link._left; /* tree is RIGHT tree */
+			else
+			{	while((t = l->_rght) ) /* maximize root of LEFT tree */
+				{	if(t->_rght)
+						LLSHIFT(l,t);
+					else	LROTATE(l,t);
+				}
+				l->_rght = link._left; /* hook RIGHT tree to LEFT root */
+				tree->root = l; /* LEFT tree is now the entire tree */
+			}
+
+			if(type&(DT_DELETE|DT_DETACH|DT_REMOVE))
+				DTRETURN(obj, obj);
+			else	DTRETURN(obj, NIL(Void_t*));
+		}
+		else if(type&(DT_NEXT|DT_ATLEAST) )
+			goto dt_next;
+		else if(type&(DT_PREV|DT_ATMOST) )
+			goto dt_prev;
+		else if(type&(DT_DELETE|DT_DETACH|DT_REMOVE))
+		{	obj = NIL(Void_t*);
+			goto no_root;
+		}
+		else if(type&(DT_INSERT|DT_APPEND|DT_ATTACH))
+		{ dt_insert:
+			if(!(root = _dtmake(dt, obj, type)) )
+			{	obj = NIL(Void_t*);
+				goto no_root;
+			}
+			else
+			{	dt->data->size += 1;
+				goto has_root;
+			}
+		}
+		else if(type&DT_RELINK)
+		{	root = me;
+			goto has_root;
+		}
+	}
+	DTRETURN(obj, NIL(Void_t*));
+
+dt_return:
+	DTANNOUNCE(dt,obj,type);
+	DTCLRLOCK(dt);
+	return obj;
+}
+
+static int treeevent(Dt_t* dt, int event, Void_t* arg)
+{
+	Dtlink_t	*l, *list;
+	ssize_t		size;
+	Dttree_t	*tree = (Dttree_t*)dt->data;
+
+	if(event == DT_OPEN)
+	{	if(tree) /* already initialized */
+			return 0;
+		if(!(tree = (Dttree_t*)(*dt->memoryf)(dt, 0, sizeof(Dttree_t), dt->disc)) )
+		{	DTERROR(dt, "Error in allocating a tree data structure");
+			return -1;
+		}
+		memset(tree, 0, sizeof(Dttree_t));
+		dt->data = (Dtdata_t*)tree;
+		return 1;
+	}
+	else if(event == DT_CLOSE)
+	{	if(!tree)
+			return 0;
+		if(tree->root)
+			(void)tclear(dt);
+		(void)(*dt->memoryf)(dt, (Void_t*)tree, 0, dt->disc);
+                dt->data = NIL(Dtdata_t*);
+                return 0;
+	}
+	else if(event == DT_OPTIMIZE) /* balance the search tree */
+	{	toptimize(dt);
+		return 0;
+	}
+	else	return 0;
+}
+
+#if _UWIN
+
+Void_t* dtfinger(Dt_t* dt)
+{
+	return (dt && dt->meth && (dt->meth->type & DT_ORDERED)) ? (Void_t*)((Dttree_t*)dt->data)->root : NIL(Void_t*);
+}
+
+#endif
+
+/* make this method available */
+static Dtmethod_t	_Dtoset =  { dttree, DT_OSET, treeevent, "Dtoset" };
+static Dtmethod_t	_Dtobag =  { dttree, DT_OBAG, treeevent, "Dtobag" };
+__DEFINE__(Dtmethod_t*,Dtoset,&_Dtoset);
+__DEFINE__(Dtmethod_t*,Dtobag,&_Dtobag);
+
+/* backwards compatibility */
+#undef	Dttree
+#if defined(__EXPORT__)
+__EXPORT__
+#endif
+__DEFINE__(Dtmethod_t*,Dttree,&_Dtoset);
+
+#ifdef NoF
+NoF(dttree)
+#endif