Imported Upstream version 93u+upstream

14 files changed, 2587 insertions, 0 deletions

diff --git a/src/lib/libast/cdt/cdtlib.h b/src/lib/libast/cdt/cdtlib.h
new file mode 100644
index 0000000..1972dd2
--- /dev/null
+++ b/src/lib/libast/cdt/cdtlib.h
@@ -0,0 +1,183 @@
+/***********************************************************************
+*                                                                      *
+*               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>                    *
+*                                                                      *
+***********************************************************************/
+#ifndef _CDTLIB_H
+#define _CDTLIB_H	1
+
+/*	cdt library/method implementation header
+**	this header is exported to the method libraries
+**	Written by Kiem-Phong Vo (5/25/96)
+*/
+
+#if _PACKAGE_ast
+#include	<ast.h>
+#if !_BLD_cdt
+#include	<dlldefs.h>
+#endif
+#endif
+
+#include	<cdt.h>
+#include	<unistd.h>
+#include	<aso.h>
+
+#include	"debug.h"
+
+/* short-hand notations */
+#define NIL(t)	((t)0)
+#define reg	register
+
+/* min #bits for a hash table. (1<<this) is table size */
+#define DT_HTABLE	10
+
+/* convenient types */
+#if !defined(uint)
+#define uint	unsigned int
+#endif
+#if !defined(uchar)
+#define uchar	unsigned char
+#endif
+
+/* This struct holds private method data created on DT_OPEN */
+struct _dtdata_s
+{	unsigned int	lock;	/* general dictionary lock	*/
+	Dtuser_t	user;	/* application's data		*/
+	unsigned int	type;	/* method type, control flags	*/
+	ssize_t		size;	/* number of objects		*/
+	Dt_t		dict;	/* when DT_INDATA is requested	*/
+};
+
+/* this structure holds the plugin information */
+typedef struct _dtlib_s
+{
+	char*		name;		/* short name */
+	char*		description;	/* short description */
+	char*		release;	/* release info */
+	char*		prefix;		/* name prefix */
+	Dtmethod_t**	methods;	/* method list */
+} Dtlib_t;
+
+#if _BLD_cdt
+
+#if defined(__STDC__)
+#define CDTLIB(m)	__DEFINE__(Dtmethod_t*,m,&_##m);
+#else
+#define CDTLIB(m)	__DEFINE__(Dtmethod_t*,m,&_/**/m);
+#endif
+
+#else
+
+#if defined(__STDC__)
+#define CDTLIB(m) \
+	void* cdt_lib(const char* name, Dtdisc_t* disc, const char* type) \
+	{ \
+		int	i; \
+		int	n; \
+		if (!type) \
+			return &cdt_lib_##m; \
+		n = strlen(cdt_lib_##m.prefix); \
+		if (!strncmp(type, cdt_lib_##m.prefix, n)) \
+			type += n; \
+		for (i = 0; cdt_lib_##m.methods[i]; i++) \
+			if (!strcmp(type, cdt_lib_##m.methods[i]->name + n)) \
+				return cdt_lib_##m.methods[i]; \
+		return 0; \
+	} \
+	unsigned long plugin_version(void) { return CDT_PLUGIN_VERSION; }
+#else
+#define CDTLIB(m) \
+	void* cdt_lib(name, disc, type) const char* name; Dtdisc_t* disc; const char* type; \
+	{ \
+		int	i; \
+		int	n; \
+		if (!type) \
+			return &cdt_lib_/**/m; \
+		n = strlen(cdt_lib_/**/m.prefix); \
+		if (!strncmp(type, cdt_lib_/**/m.prefix, n)) \
+			type += n; \
+		for (i = 0; cdt_lib_/**/m.methods[i]; i++) \
+			if (!strcmp(type, cdt_lib_/**/m.methods[i]->name + n)) \
+				return cdt_lib_/**/m.methods[i]; \
+		return 0; \
+	} \
+	unsigned long plugin_version() { return CDT_PLUGIN_VERSION; }
+#endif
+
+#endif /* _BLD_cdt */
+
+/* these macros lock/unlock dictionaries. DTRETURN substitutes for "return" */
+#define DTSETLOCK(dt)		(((dt)->data->type&DT_SHARE) ? asolock(&(dt)->data->lock,1,ASO_SPINLOCK) : 0 )
+#define DTCLRLOCK(dt)		(((dt)->data->type&DT_SHARE) ? asolock(&(dt)->data->lock,1,ASO_UNLOCK) : 0 )
+#define DTRETURN(ob,rv)		do { (ob) = (rv); goto dt_return; } while(0)
+#define DTERROR(dt, mesg) 	(!((dt)->disc && (dt)->disc->eventf) ? 0 : \
+				  (*(dt)->disc->eventf)((dt),DT_ERROR,(Void_t*)(mesg),(dt)->disc) )
+
+/* announce completion of an operation of type (ty) on some object (ob) in dictionary (dt) */
+#define DTANNOUNCE(dt,ob,ty)	( ((ob) && ((ty)&DT_TOANNOUNCE) && ((dt)->data->type&DT_ANNOUNCE) && \
+				   (dt)->disc && (dt)->disc->eventf ) ? \
+					(*(dt)->disc->eventf)((dt), DT_ANNOUNCE|(ty), (ob), (dt)->disc) : 0 )
+
+/* map bits for upward compabitibility */
+#define DTTYPE(dt,ty)		((dt)->typef ? (*(dt)->typef)((dt), (ty)) : (ty) )
+
+/* short-hands for fields in Dtlink_t.
+** note that __hash is used as a hash value
+** or as the position in the parent table.
+*/
+#define _left	lh.__left
+#define _hash	lh.__hash	
+#define _ppos	lh.__hash
+
+#define _rght	rh.__rght
+#define _ptbl	rh.__ptbl
+
+/* tree rotation/linking functions */
+#define rrotate(x,y)	((x)->_left = (y)->_rght, (y)->_rght = (x))
+#define lrotate(x,y)	((x)->_rght = (y)->_left, (y)->_left = (x))
+#define rlink(r,x)	((r) = (r)->_left = (x) )
+#define llink(l,x)	((l) = (l)->_rght = (x) )
+
+#define RROTATE(x,y)	(rrotate(x,y), (x) = (y))
+#define LROTATE(x,y)	(lrotate(x,y), (x) = (y))
+#define RRSHIFT(x,t)	((t) = (x)->_left->_left, (x)->_left->_left = (t)->_rght, \
+			 (t)->_rght = (x), (x) = (t) )
+#define LLSHIFT(x,t)	((t) = (x)->_rght->_rght, (x)->_rght->_rght = (t)->_left, \
+			 (t)->_left = (x), (x) = (t) )
+
+_BEGIN_EXTERNS_
+
+#if _BLD_cdt && defined(__EXPORT__)
+#define extern	__EXPORT__
+#endif
+
+extern Dtlink_t*	_dtmake _ARG_((Dt_t*, Void_t*, int));
+extern void		_dtfree _ARG_((Dt_t*, Dtlink_t*, int));
+extern int		_dtlock _ARG_((Dt_t*, int));
+
+#undef	extern
+
+#if !_PACKAGE_ast
+extern Void_t*		malloc _ARG_((size_t));
+extern Void_t*		realloc _ARG_((Void_t*, size_t));
+extern void		free _ARG_((Void_t*));
+#endif
+_END_EXTERNS_
+
+#endif /* _CDTLIB_H */
diff --git a/src/lib/libast/cdt/dtclose.c b/src/lib/libast/cdt/dtclose.c
new file mode 100644
index 0000000..45bca76
--- /dev/null
+++ b/src/lib/libast/cdt/dtclose.c
@@ -0,0 +1,66 @@
+/***********************************************************************
+*                                                                      *
+*               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"
+
+/*	Close a dictionary
+**
+**	Written by Kiem-Phong Vo (11/15/2010)
+*/
+#if __STD_C
+int dtclose(Dt_t* dt)
+#else
+int dtclose(dt)
+Dt_t*	dt;
+#endif
+{
+	int		ev, type;
+	Dt_t		pdt;
+	Dtdisc_t	*disc = dt->disc;
+
+	if(!dt || dt->nview > 0 ) /* can't close if being viewed */
+		return -1;
+
+	if(disc && disc->eventf) /* announce closing event */
+		ev = (*disc->eventf)(dt, DT_CLOSE, (Void_t*)1, disc);
+	else	ev = 0;
+	if(ev < 0) /* cannot close */
+		return -1;
+
+	if(dt->view) /* turn off viewing at this point */
+		dtview(dt,NIL(Dt_t*));
+
+	type = dt->data->type; /* save before memory is freed */
+	memcpy(&pdt, dt, sizeof(Dt_t));
+
+	if(ev == 0 ) /* release all allocated data */
+	{	(void)(*(dt->meth->searchf))(dt,NIL(Void_t*),DT_CLEAR);
+		(void)(*dt->meth->eventf)(dt, DT_CLOSE, (Void_t*)0);
+		/**/DEBUG_ASSERT(!dt->data);
+	}
+	if(!(type&DT_INDATA) )
+		(void)free(dt);
+
+	if(disc && disc->eventf) /* announce end of closing activities */
+		(void)(*disc->eventf)(&pdt, DT_ENDCLOSE, (Void_t*)0, disc);
+
+	return 0;
+}
diff --git a/src/lib/libast/cdt/dtcomp.c b/src/lib/libast/cdt/dtcomp.c
new file mode 100644
index 0000000..5308c70
--- /dev/null
+++ b/src/lib/libast/cdt/dtcomp.c
@@ -0,0 +1,60 @@
+/***********************************************************************
+*                                                                      *
+*               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>                    *
+*                                                                      *
+***********************************************************************/
+/*
+ * backwards binary compatibility
+ */
+
+#include <cdt.h>
+
+#if defined(__EXPORT__)
+#define extern	__EXPORT__
+#endif
+
+#undef dtflatten
+extern Dtlink_t* dtflatten(Dt_t* d)
+{
+	return (Dtlink_t*)(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_FLATTEN);
+}
+
+#undef dtextract
+extern Dtlink_t* dtextract(Dt_t* d)
+{
+	return (Dtlink_t*)(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_EXTRACT);
+}
+
+#undef dtrestore
+extern Dtlink_t* dtrestore(Dt_t* d, Void_t* l)
+{
+	return (Dtlink_t*)(*(_DT(d)->searchf))((d),(l),DT_RESTORE);
+}
+
+#undef dtsize
+extern ssize_t dtsize(Dt_t* d)
+{
+	return (ssize_t)(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_STAT);
+}
+
+#undef dtstat
+extern ssize_t dtstat(Dt_t* d)
+{
+	return (ssize_t)(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_STAT);
+}
diff --git a/src/lib/libast/cdt/dtdisc.c b/src/lib/libast/cdt/dtdisc.c
new file mode 100644
index 0000000..166aa7c
--- /dev/null
+++ b/src/lib/libast/cdt/dtdisc.c
@@ -0,0 +1,91 @@
+/***********************************************************************
+*                                                                      *
+*               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"
+
+/*	Change discipline.
+**	dt :	dictionary
+**	disc :	discipline
+**
+**	Written by Kiem-Phong Vo (5/26/96)
+*/
+
+#if __STD_C
+static Void_t* dtmemory(Dt_t* dt, Void_t* addr, size_t size, Dtdisc_t* disc)
+#else
+static Void_t* dtmemory(dt, addr, size, disc)
+Dt_t* 		dt;	/* dictionary			*/
+Void_t* 	addr;	/* address to be manipulate	*/
+size_t		size;	/* size to obtain		*/
+Dtdisc_t* 	disc;	/* discipline			*/
+#endif
+{
+	if(addr)
+	{	if(size == 0)
+		{	free(addr);
+			return NIL(Void_t*);
+		}
+		else	return realloc(addr,size);
+	}
+	else	return size > 0 ? malloc(size) : NIL(Void_t*);
+}
+
+#if __STD_C
+Dtdisc_t* dtdisc(Dt_t* dt, Dtdisc_t* disc, int type)
+#else
+Dtdisc_t* dtdisc(dt,disc,type)
+Dt_t*		dt;
+Dtdisc_t*	disc;
+int		type;
+#endif
+{
+	Dtsearch_f	searchf;
+	Dtdisc_t	*old;
+	Dtlink_t	*list;
+
+	if(!(old = dt->disc) )	/* initialization call from dtopen() */
+	{	dt->disc = disc;
+		if(!(dt->memoryf = disc->memoryf) )
+			dt->memoryf = dtmemory;
+		return disc;
+	}
+
+	if(!disc) /* only want to know current discipline */
+		return old;
+
+	searchf = dt->meth->searchf;
+
+	if(old->eventf && (*old->eventf)(dt,DT_DISC,(Void_t*)disc,old) < 0)
+		return NIL(Dtdisc_t*);
+
+	if((type & (DT_SAMEHASH|DT_SAMECMP)) != (DT_SAMEHASH|DT_SAMECMP) )
+		list = dtextract(dt); /* grab the list of objects if any */
+	else	list = NIL(Dtlink_t*);
+
+	dt->disc = disc;
+	if(!(dt->memoryf = disc->memoryf) )
+		dt->memoryf = dtmemory;
+
+	if(list ) /* reinsert extracted objects (with new discipline) */
+		dtrestore(dt, list);
+
+	return old;
+}
diff --git a/src/lib/libast/cdt/dthash.c b/src/lib/libast/cdt/dthash.c
new file mode 100644
index 0000000..984b2a5
--- /dev/null
+++ b/src/lib/libast/cdt/dthash.c
@@ -0,0 +1,431 @@
+/***********************************************************************
+*                                                                      *
+*               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"
+
+/*	Hash table with chaining for collisions.
+**
+**      Written by Kiem-Phong Vo (05/25/96)
+*/
+
+/* these bits should be outside the scope of DT_METHODS */
+#define H_FIXED		0100000	/* table size is fixed	*/
+#define	H_FLATTEN	0200000	/* table was flattened	*/
+
+#define HLOAD(n)	(n)	/* load one-to-one	*/
+
+/* internal data structure for hash table with chaining */
+typedef struct _dthash_s
+{	Dtdata_t	data;
+	int		type; 
+	Dtlink_t*	here;	/* fingered object	*/
+	Dtlink_t**	htbl;	/* hash table slots 	*/
+	ssize_t		tblz;	/* size of hash table 	*/
+} Dthash_t;
+
+/* make/resize hash table */
+static int htable(Dt_t* dt)
+{
+	Dtlink_t	**htbl, **t, **endt, *l, *next;
+	ssize_t		n, k;
+	Dtdisc_t	*disc = dt->disc;
+	Dthash_t	*hash = (Dthash_t*)dt->data;
+
+	if((n = hash->tblz) > 0 && (hash->type&H_FIXED) )
+		return 0; /* fixed size table */
+
+	if(n == 0 && disc && disc->eventf) /* let user have input */
+	{	if((*disc->eventf)(dt, DT_HASHSIZE, &n, disc) > 0 )
+		{	if(n < 0) /* fix table size */
+			{	hash->type |= H_FIXED;
+				n = -n;
+			}
+		}
+	}
+
+	/* table size should be a power of 2 */
+	n = n < HLOAD(hash->data.size) ? HLOAD(hash->data.size) : n;
+	for(k = (1<<DT_HTABLE); k < n; )
+		k *= 2;
+	if((n = k) <= hash->tblz)
+		return 0;
+
+	/* allocate new table */
+	if(!(htbl = (Dtlink_t**)(*dt->memoryf)(dt, 0, n*sizeof(Dtlink_t*), disc)) )
+	{	DTERROR(dt, "Error in allocating an extended hash table");
+		return -1;
+	}
+	memset(htbl, 0, n*sizeof(Dtlink_t*));
+
+	/* move objects into new table */
+	for(endt = (t = hash->htbl) + hash->tblz; t < endt; ++t)
+	{	for(l = *t; l; l = next)
+		{	next = l->_rght;
+			l->_rght = htbl[k = l->_hash&(n-1)];
+			htbl[k] = l;
+		}
+	}
+
+	if(hash->htbl) /* free old table and set new table */
+		(void)(*dt->memoryf)(dt, hash->htbl, 0, disc);
+	hash->htbl = htbl;
+	hash->tblz = n;
+
+	return 0;
+}
+
+static Void_t* hclear(Dt_t* dt)
+{
+	Dtlink_t	**t, **endt, *l, *next;
+	Dthash_t	*hash = (Dthash_t*)dt->data;
+
+	hash->here = NIL(Dtlink_t*);
+	hash->data.size = 0;
+
+	for(endt = (t = hash->htbl) + hash->tblz; t < endt; ++t)
+	{	for(l = *t; l; l = next)
+		{	next = l->_rght;
+			_dtfree(dt, l, DT_DELETE);
+		}
+		*t = NIL(Dtlink_t*);
+	}
+
+	return NIL(Void_t*);
+}
+
+static Void_t* hfirst(Dt_t* dt)
+{
+	Dtlink_t	**t, **endt, *l;
+	Dthash_t	*hash = (Dthash_t*)dt->data;
+
+	for(endt = (t = hash->htbl) + hash->tblz; t < endt; ++t)
+	{	if(!(l = *t) )
+			continue;
+		hash->here = l;
+		return _DTOBJ(dt->disc, l);
+	}
+
+	return NIL(Void_t*);
+}
+
+static Void_t* hnext(Dt_t* dt, Dtlink_t* l)
+{
+	Dtlink_t	**t, **endt, *next;
+	Dthash_t	*hash = (Dthash_t*)dt->data;
+
+	if((next = l->_rght) )
+	{	hash->here = next;
+		return _DTOBJ(dt->disc, next);
+	}
+	else
+	{	t = hash->htbl + (l->_hash & (hash->tblz-1)) + 1;
+		endt = hash->htbl + hash->tblz;
+		for(; t < endt; ++t)
+		{	if(!(l = *t) )
+				continue;
+			hash->here = l;
+			return _DTOBJ(dt->disc, l);
+		}
+		return NIL(Void_t*);
+	}
+}
+
+static Void_t* hflatten(Dt_t* dt, int type)
+{
+	Dtlink_t	**t, **endt, *head, *tail, *l;
+	Dthash_t	*hash = (Dthash_t*)dt->data;
+
+	if(type == DT_FLATTEN || type == DT_EXTRACT)
+	{	head = tail = NIL(Dtlink_t*);
+		for(endt = (t = hash->htbl) + hash->tblz; t < endt; ++t)
+		{	for(l = *t; l; l = l->_rght)
+			{	if(tail)
+					tail = (tail->_rght = l);
+				else	head = tail = l;
+
+				*t = type == DT_FLATTEN ? tail : NIL(Dtlink_t*);
+			}
+		}
+
+		if(type == DT_FLATTEN)
+		{	hash->here = head;
+			hash->type |= H_FLATTEN;
+		}
+		else	hash->data.size = 0;
+
+		return (Void_t*)head;
+	}
+	else /* restoring a previous flattened list */
+	{	head = hash->here;
+		for(endt = (t = hash->htbl) + hash->tblz; t < endt; ++t)
+		{	if(*t == NIL(Dtlink_t*))
+				continue;
+
+			/* find the tail of the list for this slot */
+			for(l = head; l && l != *t; l = l->_rght)
+				;
+			if(!l) /* something is seriously wrong */
+				return NIL(Void_t*);
+
+			*t = head; /* head of list for this slot */
+			head = l->_rght; /* head of next list */
+			l->_rght = NIL(Dtlink_t*);
+		}
+
+		hash->here = NIL(Dtlink_t*);
+		hash->type &= ~H_FLATTEN;
+
+		return NIL(Void_t*);
+	}
+}
+
+static Void_t* hlist(Dt_t* dt, Dtlink_t* list, int type)
+{
+	Void_t		*obj;
+	Dtlink_t	*l, *next;
+	Dtdisc_t	*disc = dt->disc;
+
+	if(type&DT_FLATTEN)
+		return hflatten(dt, DT_FLATTEN);
+	else if(type&DT_EXTRACT)
+		return hflatten(dt, DT_EXTRACT);
+	else /* if(type&DT_RESTORE) */
+	{	dt->data->size = 0;
+		for(l = list; l; l = next)
+		{	next = l->_rght;
+			obj = _DTOBJ(disc,l);
+			if((*dt->meth->searchf)(dt, (Void_t*)l, DT_RELINK) == obj)
+				dt->data->size += 1;
+		}
+		return (Void_t*)list;
+	}
+}
+
+static Void_t* hstat(Dt_t* dt, Dtstat_t* st)
+{
+	ssize_t		n;
+	Dtlink_t	**t, **endt, *l;
+	Dthash_t	*hash = (Dthash_t*)dt->data;
+
+	if(st)
+	{	memset(st, 0, sizeof(Dtstat_t));
+		st->meth  = dt->meth->type;
+		st->size  = hash->data.size;
+		st->space = sizeof(Dthash_t) + hash->tblz*sizeof(Dtlink_t*) +
+			    (dt->disc->link >= 0 ? 0 : hash->data.size*sizeof(Dthold_t));
+
+		for(endt = (t = hash->htbl) + hash->tblz; t < endt; ++t)
+		{	for(n = 0, l = *t; l; l = l->_rght)
+				n += 1;
+			st->mlev = n > st->mlev ? n : st->mlev;
+			if(n < DT_MAXSIZE) /* if chain length is small */
+			{	st->msize = n > st->msize ? n : st->msize;
+				st->lsize[n] += n;
+			}
+		}
+	}
+
+	return (Void_t*)hash->data.size;
+}
+
+#if __STD_C
+static Void_t* dthashchain(Dt_t* dt, Void_t* obj, int type)
+#else
+static Void_t* dthashchain(dt,obj,type)
+Dt_t*	dt;
+Void_t*	obj;
+int	type;
+#endif
+{
+	Dtlink_t	*lnk, *pp, *ll, *p, *l, **tbl;
+	Void_t		*key, *k, *o;
+	uint		hsh;
+	Dtdisc_t	*disc = dt->disc;
+	Dthash_t	*hash = (Dthash_t*)dt->data;
+
+	type = DTTYPE(dt,type); /* map type for upward compatibility */
+	if(!(type&DT_OPERATIONS) )
+		return NIL(Void_t*);
+
+	DTSETLOCK(dt);
+
+	if(!hash->htbl && htable(dt) < 0 ) /* initialize hash table */
+		DTRETURN(obj, NIL(Void_t*));
+
+	if(hash->type&H_FLATTEN) /* restore flattened list */
+		hflatten(dt, 0);
+
+	if(type&(DT_FIRST|DT_LAST|DT_CLEAR|DT_EXTRACT|DT_RESTORE|DT_FLATTEN|DT_STAT) )
+	{	if(type&(DT_FIRST|DT_LAST) )
+			DTRETURN(obj, hfirst(dt));
+		else if(type&DT_CLEAR)
+			DTRETURN(obj, hclear(dt));
+		else if(type&DT_STAT)
+			DTRETURN(obj, hstat(dt, (Dtstat_t*)obj));
+		else /*if(type&(DT_EXTRACT|DT_RESTORE|DT_FLATTEN))*/
+			DTRETURN(obj, hlist(dt, (Dtlink_t*)obj, type));
+	}
+
+	lnk = hash->here; /* fingered object */
+	hash->here = NIL(Dtlink_t*);
+
+	if(lnk && obj == _DTOBJ(disc,lnk))
+	{	if(type&DT_SEARCH)
+			DTRETURN(obj, obj);
+		else if(type&(DT_NEXT|DT_PREV) )
+			DTRETURN(obj, hnext(dt,lnk));
+	}
+
+	if(type&DT_RELINK)
+	{	lnk = (Dtlink_t*)obj;
+		obj = _DTOBJ(disc,lnk);
+		key = _DTKEY(disc,obj);
+	}
+	else 
+	{	lnk = NIL(Dtlink_t*);
+		if((type&DT_MATCH) )
+		{	key = obj;
+			obj = NIL(Void_t*);
+		}
+		else	key = _DTKEY(disc,obj);
+	}
+	hsh = _DTHSH(dt,key,disc);
+
+	tbl = hash->htbl + (hsh & (hash->tblz-1));
+	pp = ll = NIL(Dtlink_t*);
+	for(p = NIL(Dtlink_t*), l = *tbl; l; p = l, l = l->_rght)
+	{	if(hsh == l->_hash)
+		{	o = _DTOBJ(disc,l); k = _DTKEY(disc,o);
+			if(_DTCMP(dt, key, k, disc) != 0 )
+				continue;
+			else if((type&(DT_REMOVE|DT_NEXT|DT_PREV)) && o != obj )
+			{	if(type&(DT_NEXT|DT_PREV) )
+					{ pp = p; ll = l; }
+				continue;
+			}
+			else	break;
+		}
+	}
+	if(l) /* found an object, use it */ 
+		{ pp = p; ll = l; }
+
+	if(ll) /* found object */
+	{	if(type&(DT_SEARCH|DT_MATCH|DT_ATLEAST|DT_ATMOST) )
+		{	hash->here = ll;
+			DTRETURN(obj, _DTOBJ(disc,ll));
+		}
+		else if(type & (DT_NEXT|DT_PREV) )
+			DTRETURN(obj, hnext(dt, ll));
+		else if(type & (DT_DELETE|DT_DETACH|DT_REMOVE) )
+		{	hash->data.size -= 1;
+			if(pp)
+				pp->_rght = ll->_rght;
+			else	*tbl = ll->_rght;
+			_dtfree(dt, ll, type);
+			DTRETURN(obj, _DTOBJ(disc,ll));
+		}
+		else
+		{	/**/DEBUG_ASSERT(type&(DT_INSERT|DT_ATTACH|DT_APPEND|DT_RELINK));
+			if(!(dt->meth->type&DT_BAG) )
+			{	if(type&(DT_INSERT|DT_APPEND|DT_ATTACH) )
+					type |= DT_SEARCH; /* for announcement */
+				else if(lnk && (type&DT_RELINK) )
+					_dtfree(dt, lnk, DT_DELETE);
+				DTRETURN(obj, _DTOBJ(disc,ll));
+			}
+			else	goto do_insert;
+		}
+	}
+	else /* no matching object */
+	{	if(!(type&(DT_INSERT|DT_APPEND|DT_ATTACH|DT_RELINK)) )
+			DTRETURN(obj, NIL(Void_t*));
+
+	do_insert: /* inserting a new object */
+		if(hash->tblz < HLOAD(hash->data.size) )
+		{	htable(dt); /* resize table */
+			tbl = hash->htbl + (hsh & (hash->tblz-1));
+		}
+
+		if(!lnk) /* inserting a new object */
+		{	if(!(lnk = _dtmake(dt, obj, type)) )
+				DTRETURN(obj, NIL(Void_t*));
+			hash->data.size += 1;
+		}
+
+		lnk->_hash = hsh; /* memoize the hash value */
+		lnk->_rght = *tbl; *tbl = lnk;
+
+		hash->here = lnk;
+		DTRETURN(obj, _DTOBJ(disc,lnk));
+	}
+
+dt_return:
+	DTANNOUNCE(dt, obj, type);
+	DTCLRLOCK(dt);
+	return obj;
+}
+
+static int hashevent(Dt_t* dt, int event, Void_t* arg)
+{
+	Dtlink_t	*list;
+	Dthash_t	*hash = (Dthash_t*)dt->data;
+	int		rv = -1;
+
+	if(event == DT_OPEN)
+	{	if(hash)
+			return 0;
+		if(!(hash = (Dthash_t*)(*dt->memoryf)(dt, 0, sizeof(Dthash_t), dt->disc)) )
+		{	DTERROR(dt, "Error in allocating a hash table with chaining");
+			return -1;
+		}
+		memset(hash, 0, sizeof(Dthash_t));
+		dt->data = (Dtdata_t*)hash;
+		return 1;
+	}
+	else if(event == DT_CLOSE)
+	{	if(!hash)
+			return 0;
+		if(hash->data.size > 0 )
+			(void)hclear(dt);
+		if(hash->htbl)
+			(void)(*dt->memoryf)(dt, hash->htbl, 0, dt->disc);
+		(void)(*dt->memoryf)(dt, hash, 0, dt->disc);
+		dt->data = NIL(Dtdata_t*);
+		return 0;
+	}
+	else	return 0;
+}
+
+static Dtmethod_t	_Dtset = { dthashchain, DT_SET, hashevent, "Dtset" };
+static Dtmethod_t	_Dtbag = { dthashchain, DT_BAG, hashevent, "Dtbag" };
+__DEFINE__(Dtmethod_t*,Dtset,&_Dtset);
+__DEFINE__(Dtmethod_t*,Dtbag,&_Dtbag);
+
+/* backwards compatibility */
+#undef	Dthash
+#if defined(__EXPORT__)
+__EXPORT__
+#endif
+__DEFINE__(Dtmethod_t*,Dthash,&_Dtset);
+
+#ifdef NoF
+NoF(dthashchain)
+#endif
diff --git a/src/lib/libast/cdt/dthdr.h b/src/lib/libast/cdt/dthdr.h
new file mode 100644
index 0000000..d24ae0d
--- /dev/null
+++ b/src/lib/libast/cdt/dthdr.h
@@ -0,0 +1,37 @@
+/***********************************************************************
+*                                                                      *
+*               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>                    *
+*                                                                      *
+***********************************************************************/
+#ifndef _DTHDR_H
+#define _DTHDR_H	1
+
+#ifndef _BLD_cdt
+#define _BLD_cdt	1
+#endif
+
+/*	Internal definitions for libcdt.
+**	Written by Kiem-Phong Vo (5/25/96)
+*/
+
+#undef	_DTTRACE
+
+#include	<cdtlib.h>
+
+#endif /* _DTHDR_H */
diff --git a/src/lib/libast/cdt/dtlist.c b/src/lib/libast/cdt/dtlist.c
new file mode 100644
index 0000000..af0dfd1
--- /dev/null
+++ b/src/lib/libast/cdt/dtlist.c
@@ -0,0 +1,387 @@
+/***********************************************************************
+*                                                                      *
+*               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"
+
+/*	List, Deque, Stack, Queue.
+**
+**	Written by Kiem-Phong Vo (05/25/96)
+*/
+
+typedef struct _dtlist_s
+{	Dtdata_t	data;
+	Dtlink_t*	link;	/* list of objects		*/
+	Dtlink_t*	here;	/* finger to searched objects	*/
+} Dtlist_t;
+
+#ifdef DEBUG
+int dtlistprint(Dt_t* dt, Dtlink_t* here, char* (*objprintf)(Void_t*) )
+{
+	int		k;
+	char		*obj, *endb, buf[1024];
+	Dtdisc_t	*disc = dt->disc;
+	Dtlist_t	*list = (Dtlist_t*)dt->data;
+
+	if(!here && !(here = list->link) )
+		return -1;
+
+	for(; here; here = here->_rght)
+	{	endb = buf; /* indentation */
+		*endb++ = '(';
+		obj = (*objprintf)(_DTOBJ(disc, here));
+		k = strlen(obj); memcpy(endb, obj, k); endb += k;
+		*endb++ = ')';
+		*endb++ = '\n';
+		write(2, buf, endb-buf);
+	}
+
+	return 0;
+}
+#endif
+
+/* terminal objects: DT_FIRST|DT_LAST */
+#if __STD_C
+Void_t* lfirstlast(Dt_t* dt, int type)
+#else
+Void_t* lfirstlast(dt, type)
+Dt_t*	dt;
+int	type;
+#endif
+{
+	Dtlink_t	*lnk;
+	Dtdisc_t	*disc = dt->disc;
+	Dtlist_t	*list = (Dtlist_t*)dt->data;
+
+	if((lnk = list->link) )
+	{	if(type&DT_LAST)
+			lnk = lnk->_left;
+		list->here = lnk; /* finger points to this */
+	}
+
+	return lnk ? _DTOBJ(disc,lnk) : NIL(Void_t*);
+}
+
+/* DT_CLEAR */
+#if __STD_C
+Void_t* lclear(Dt_t* dt)
+#else
+Void_t* lclear(dt)
+Dt_t*	dt;
+#endif
+{
+	Dtlink_t	*lnk, *next;
+	Dtdisc_t	*disc = dt->disc;
+	Dtlist_t	*list = (Dtlist_t*)dt->data;
+
+	lnk = list->link;
+	list->link = list->here = NIL(Dtlink_t*);
+	list->data.size = 0;
+
+	if(disc->freef || disc->link < 0)
+	{	for(; lnk; lnk = next)
+		{	next = lnk->_rght;
+			_dtfree(dt, lnk, DT_DELETE);
+		}
+	}
+
+	return NIL(Void_t*);
+}
+
+/* DT_FLATTEN|DT_EXTRACT|DT_RESTORE */
+#if __STD_C
+Void_t* llist(Dt_t* dt, Dtlink_t* lnk, int type)
+#else
+Void_t* llist(dt, lnk, type)
+Dt_t*		dt;
+Dtlink_t*	lnk;
+int		type;
+#endif
+{
+	Dtlist_t	*list = (Dtlist_t*)dt->data;
+
+	if(type&(DT_FLATTEN|DT_EXTRACT) )
+	{	if(lnk) /* error on calling */
+			return NIL(Void_t*);
+
+		lnk = list->link;
+		if(type&DT_EXTRACT)
+		{	list->link = NIL(Dtlink_t*);
+			dt->data->size = 0;
+		}
+	}
+	else /* if(type&DT_RESTORE) */
+	{	if(list->link != NIL(Dtlink_t*))
+			return NIL(Void_t*);
+
+		list->link = lnk;
+
+		dt->data->size = 0;
+		for(; lnk; lnk = lnk->_rght)
+			dt->data->size += 1;
+	}
+
+	return (Void_t*)lnk;
+}
+
+#if __STD_C
+static Void_t* liststat(Dt_t* dt, Dtstat_t* st)
+#else
+static Void_t* liststat(dt, st)
+Dt_t*		dt;
+Dtstat_t*	st;
+#endif
+{
+	ssize_t		size;
+	Dtlink_t	*lnk;
+	Dtlist_t	*list = (Dtlist_t*)dt->data;
+
+	if(st)
+	{	memset(st, 0, sizeof(Dtstat_t));
+		st->meth  = dt->meth->type;
+		st->size  = dt->data->size;
+		st->space = sizeof(Dtlist_t) + (dt->disc->link >= 0 ? 0 : dt->data->size*sizeof(Dthold_t));
+	}
+
+	return (Void_t*)dt->data->size;
+}
+
+#if __STD_C
+static Void_t* dtlist(Dt_t* dt, Void_t* obj, int type)
+#else
+static Void_t* dtlist(dt, obj, type)
+Dt_t*	dt;
+Void_t*	obj;
+int	type;
+#endif
+{
+	Dtlink_t	*r, *t, *h;
+	Void_t		*key, *o, *k;
+	Dtdisc_t	*disc = dt->disc;
+	Dtlist_t	*list = (Dtlist_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, lfirstlast(dt, type));
+	else if(type&(DT_EXTRACT|DT_RESTORE|DT_FLATTEN) )
+		DTRETURN(obj, llist(dt, (Dtlink_t*)obj, type));
+	else if(type&DT_CLEAR)
+		DTRETURN(obj, lclear(dt));
+	else if(type&DT_STAT )
+		DTRETURN(obj, liststat(dt, (Dtstat_t*)obj));
+
+	h = list->here; /* save finger to last search object */
+	list->here = NIL(Dtlink_t*);
+
+	if(!obj)
+	{	if((type&(DT_DELETE|DT_DETACH|DT_REMOVE)) && (dt->meth->type&(DT_STACK|DT_QUEUE)) )
+			if((r = list->link) ) /* special case for destack or dequeue */
+				goto dt_delete;
+		DTRETURN(obj, NIL(Void_t*)); /* error, needing non-void object */
+	}
+
+	if(type&DT_RELINK) /* relink object after some processing */
+	{	r = (Dtlink_t*)obj;
+		goto do_insert;
+	}
+	else if(type&(DT_INSERT|DT_APPEND|DT_ATTACH))
+	{	if(!(r = _dtmake(dt, obj, type)) )
+			DTRETURN(obj, NIL(Void_t*));
+		dt->data->size += 1;
+
+	do_insert:
+		if(dt->meth->type&DT_DEQUE)
+		{	if(type&DT_APPEND)
+				goto dt_queue; /* append at end */
+			else	goto dt_stack; /* insert at top */
+		}
+		else if(dt->meth->type&DT_LIST)
+		{	if(type&DT_APPEND)
+			{	if(!h || !h->_rght)
+					goto dt_queue;
+				r->_rght = h->_rght;
+				r->_rght->_left = r;
+				r->_left = h;
+				r->_left->_rght = r;
+			}
+			else
+			{	if(!h || h == list->link )
+					goto dt_stack;
+				r->_left = h->_left;
+				r->_left->_rght = r;
+				r->_rght = h;
+				r->_rght->_left = r;
+			}
+		}
+		else if(dt->meth->type&DT_STACK)
+		{ dt_stack:
+			r->_rght = t = list->link;
+			if(t)
+			{	r->_left = t->_left;
+				t->_left = r;
+			}
+			else	r->_left = r;
+			list->link = r;
+		}
+		else /* if(dt->meth->type&DT_QUEUE) */
+		{ dt_queue:
+			if((t = list->link) )
+			{	t->_left->_rght = r;
+				r->_left = t->_left;
+				t->_left = r;
+			}
+			else
+			{	list->link = r;
+				r->_left = r;
+			}
+			r->_rght = NIL(Dtlink_t*);
+		}
+
+		list->here = r;
+		DTRETURN(obj, _DTOBJ(disc,r));
+	}
+
+	/* define key to match */
+	if(type&DT_MATCH)
+	{	key = obj;
+		obj = NIL(Void_t*);
+	}
+	else	key = _DTKEY(disc, obj);
+
+	/* try to find a matching object */
+	if(h && _DTOBJ(disc,h) == obj && (type & (DT_SEARCH|DT_NEXT|DT_PREV)) )
+		r = h; /* match at the finger, no search needed */
+	else /* linear search through the list */
+	{	h = NIL(Dtlink_t*); /* track first/last obj with same key */
+		for(r = list->link; r; r = r->_rght)
+		{	o = _DTOBJ(disc,r); k = _DTKEY(disc,o);
+			if(_DTCMP(dt, key, k, disc) != 0)
+				continue;
+			else if(type & (DT_REMOVE|DT_NEXT|DT_PREV) )
+			{	if(o == obj) /* got exact object, done */
+					break;
+				else if(type&DT_NEXT) /* track last object */
+					h = r;
+				else if(type&DT_PREV) /* track first object */
+					h = h ? h : r;
+				else	continue;
+			}
+			else if(type & DT_ATLEAST )
+				h = r; /* track last object */
+			else	break;
+		}
+		r = h ? h : r;
+	}
+	if(!r)
+		DTRETURN(obj, NIL(Void_t*));
+
+	if(type&(DT_DELETE|DT_DETACH|DT_REMOVE))
+	{ dt_delete:
+		if(r->_rght)
+			r->_rght->_left = r->_left;
+		if(r == (t = list->link) )
+		{	list->link = r->_rght;
+			if((h = list->link) )
+				h->_left = t->_left;
+		}
+		else
+		{	r->_left->_rght = r->_rght;
+			if(r == t->_left)
+				t->_left = r->_left;
+		}
+
+		list->here = r == list->here ? r->_rght : NIL(Dtlink_t*);
+
+		obj = _DTOBJ(disc,r);
+		_dtfree(dt, r, type);
+		dt->data->size -= 1;
+
+		DTRETURN(obj, obj);
+	}
+
+	if(type&DT_NEXT)
+		r = r->_rght;
+	else if(type&DT_PREV)
+		r = r == list->link ? NIL(Dtlink_t*) : r->_left;
+	/* else: if(type&(DT_SEARCH|DT_MATCH|DT_ATLEAST|DT_ATMOST)) */
+
+	list->here = r;
+	if(r)
+		DTRETURN(obj, _DTOBJ(disc,r));
+	else	DTRETURN(obj, NIL(Void_t*));
+
+dt_return:
+	DTANNOUNCE(dt,obj,type);
+	DTCLRLOCK(dt);
+	return obj;
+}
+
+#if __STD_C
+static int listevent(Dt_t* dt, int event, Void_t* arg)
+#else
+static int listevent(dt, event, arg)
+Dt_t*	dt;
+int	event;
+Void_t*	arg;
+#endif
+{
+	Dtlist_t	*list = (Dtlist_t*)dt->data;
+
+	if(event == DT_OPEN)
+	{	if(list) /* already initialized */
+			return 0;
+		if(!(list = (Dtlist_t*)(*dt->memoryf)(dt, 0, sizeof(Dtlist_t), dt->disc)) )
+		{	DTERROR(dt, "Error in allocating a list data structure");
+			return -1;
+		}
+		memset(list, 0, sizeof(Dtlist_t));
+		dt->data = (Dtdata_t*)list;
+		return 1;
+	}
+	else if(event == DT_CLOSE)
+	{	if(!list) /* already closed */
+			return 0;
+		if(list->link) /* remove all items */
+			(void)lclear(dt);
+		(void)(*dt->memoryf)(dt, (Void_t*)list, 0, dt->disc);
+		dt->data = NIL(Dtdata_t*);
+		return 0;
+	}
+	else	return 0;
+}
+
+static Dtmethod_t _Dtlist  = { dtlist, DT_LIST,  listevent, "Dtlist"  };
+static Dtmethod_t _Dtdeque = { dtlist, DT_DEQUE, listevent, "Dtdeque" };
+static Dtmethod_t _Dtstack = { dtlist, DT_STACK, listevent, "Dtstack" };
+static Dtmethod_t _Dtqueue = { dtlist, DT_QUEUE, listevent, "Dtqueue" };
+
+__DEFINE__(Dtmethod_t*,Dtlist,&_Dtlist);
+__DEFINE__(Dtmethod_t*,Dtdeque,&_Dtdeque);
+__DEFINE__(Dtmethod_t*,Dtstack,&_Dtstack);
+__DEFINE__(Dtmethod_t*,Dtqueue,&_Dtqueue);
+
+#ifdef NoF
+NoF(dtlist)
+#endif
diff --git a/src/lib/libast/cdt/dtmethod.c b/src/lib/libast/cdt/dtmethod.c
new file mode 100644
index 0000000..56a1d25
--- /dev/null
+++ b/src/lib/libast/cdt/dtmethod.c
@@ -0,0 +1,107 @@
+/***********************************************************************
+*                                                                      *
+*               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"
+
+/*	Change search method.
+**
+**	Written by Kiem-Phong Vo (05/25/96)
+*/
+
+#if __STD_C
+Dtmethod_t* dtmethod(Dt_t* dt, Dtmethod_t* meth)
+#else
+Dtmethod_t* dtmethod(dt, meth)
+Dt_t*		dt;
+Dtmethod_t*	meth;
+#endif
+{
+	Dtlink_t	*list;
+	Dtdisc_t	*disc = dt->disc;
+	Dtmethod_t	*oldmt = dt->meth;
+	Dtdata_t	*newdt, *olddt = dt->data;
+
+	if(!meth || meth == oldmt)
+		return oldmt;
+
+	/* ask discipline if switching to new method is ok */
+	if(disc->eventf && (*disc->eventf)(dt,DT_METH,(Void_t*)meth,disc) < 0)
+		return NIL(Dtmethod_t*);
+
+	list = dtextract(dt); /* extract elements out of dictionary */
+
+	/* try to create internal structure for new method */
+	if(dt->searchf == oldmt->searchf) /* ie, not viewpathing */
+		dt->searchf = meth->searchf;
+	dt->meth = meth;
+	dt->data = NIL(Dtdata_t*);
+	if((*dt->meth->eventf)(dt, DT_OPEN, NIL(Void_t*)) < 0 )
+		newdt = NIL(Dtdata_t*);
+	else	newdt = dt->data;
+
+	/* see what need to be done to data of the old method */ 
+	if(dt->searchf == meth->searchf)
+		dt->searchf = oldmt->searchf;
+	dt->meth = oldmt;
+	dt->data = olddt;
+	if(newdt) /* switch was successful, remove old data */
+	{	(void)(*dt->meth->eventf)(dt, DT_CLOSE, NIL(Void_t*));
+
+		if(dt->searchf == oldmt->searchf)
+			dt->searchf = meth->searchf;
+		dt->meth = meth;
+		dt->data = newdt;
+		dtrestore(dt, list);
+		return oldmt;
+	}
+	else /* switch failed, restore dictionary to previous states */
+	{	dtrestore(dt, list); 
+		return NIL(Dtmethod_t*);
+	}
+}
+
+/* customize certain actions in a container data structure */
+int dtcustomize(Dt_t* dt, int type, int action)
+{
+	int	done = 0;
+
+	if((type&DT_SHARE) &&
+	   (!dt->meth->eventf || (*dt->meth->eventf)(dt, DT_SHARE, (Void_t*)((long)action)) >= 0) )
+	{	if(action <= 0 )
+			dt->data->type &= ~DT_SHARE;
+		else	dt->data->type |=  DT_SHARE;
+		done |= DT_SHARE;
+	}
+
+	if((type&DT_ANNOUNCE) &&
+	   (!dt->meth->eventf || (*dt->meth->eventf)(dt, DT_ANNOUNCE, (Void_t*)((long)action)) >= 0) )
+	{	if(action <= 0 )
+			dt->data->type &= ~DT_ANNOUNCE;
+		else	dt->data->type |=  DT_ANNOUNCE;
+		done |= DT_ANNOUNCE;
+	}
+
+	if((type&DT_OPTIMIZE) &&
+	   (!dt->meth->eventf || (*dt->meth->eventf)(dt, DT_OPTIMIZE, (Void_t*)((long)action)) >= 0) )
+		done |= DT_OPTIMIZE;
+
+	return done;
+}
diff --git a/src/lib/libast/cdt/dtnew.c b/src/lib/libast/cdt/dtnew.c
new file mode 100644
index 0000000..5e1bb70
--- /dev/null
+++ b/src/lib/libast/cdt/dtnew.c
@@ -0,0 +1,81 @@
+/***********************************************************************
+*                                                                      *
+*               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>                    *
+*                                                                      *
+***********************************************************************/
+#pragma prototyped
+
+/*
+ * dtopen() with handle placed in specific vm region
+ */
+
+#include <dt.h>
+
+typedef struct Dc_s
+{
+	Dtdisc_t	ndisc;
+	Dtdisc_t*	odisc;
+	Vmalloc_t*	vm;
+} Dc_t;
+
+static int
+eventf(Dt_t* dt, int op, void* data, Dtdisc_t* disc)
+{
+	Dc_t*	dc = (Dc_t*)disc;
+	int	r;
+
+	if (dc->odisc->eventf && (r = (*dc->odisc->eventf)(dt, op, data, dc->odisc)))
+		return r;
+	return op == DT_ENDOPEN ? 1 : 0;
+}
+
+static void*
+memoryf(Dt_t* dt, void* addr, size_t size, Dtdisc_t* disc)
+{
+	return vmresize(((Dc_t*)disc)->vm, addr, size, VM_RSMOVE);
+}
+
+/*
+ * open a dictionary using disc->memoryf if set or vm otherwise
+ */
+
+Dt_t*
+_dtnew(Vmalloc_t* vm, Dtdisc_t* disc, Dtmethod_t* meth, unsigned long version)
+{
+	Dt_t*		dt;
+	Dc_t		dc;
+
+	dc.odisc = disc;
+	dc.ndisc = *disc;
+	dc.ndisc.eventf = eventf;
+	if (!dc.ndisc.memoryf)
+		dc.ndisc.memoryf = memoryf;
+	dc.vm = vm;
+	if (dt = _dtopen(&dc.ndisc, meth, version))
+		dtdisc(dt, disc, DT_SAMECMP|DT_SAMEHASH);
+	return dt;
+}
+
+#undef dtnew
+
+Dt_t*
+dtnew(Vmalloc_t* vm, Dtdisc_t* disc, Dtmethod_t* meth)
+{
+	return _dtnew(vm, disc, meth, 20050420L);
+}
diff --git a/src/lib/libast/cdt/dtopen.c b/src/lib/libast/cdt/dtopen.c
new file mode 100644
index 0000000..6411969
--- /dev/null
+++ b/src/lib/libast/cdt/dtopen.c
@@ -0,0 +1,177 @@
+/***********************************************************************
+*                                                                      *
+*               This software is part of the ast package               *
+*          Copyright (c) 1985-2012 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"
+static char*     Version = "\n@(#)$Id: cdt (AT&T Labs - Research) 2011-11-11 $\0\n";
+
+/* 	Make a new dictionary
+**
+**	Written by Kiem-Phong Vo (5/25/96)
+*/
+
+/* map operation bits from the 2005 version to the current version */
+static int _dttype2005(Dt_t* dt, int type)
+{
+	if (type == DT_DELETE && (dt->meth->type&(DT_OBAG|DT_BAG)))
+		type = DT_REMOVE;
+	return type;
+}
+
+#if __STD_C
+Dt_t* _dtopen(Dtdisc_t* disc, Dtmethod_t* meth, unsigned long version)
+#else
+Dt_t*	_dtopen(disc, meth, version)
+Dtdisc_t*	disc;
+Dtmethod_t*	meth;
+unsigned long	version;
+#endif
+{
+	Dtdata_t	*data;
+	Dt_t		*dt, pdt;
+	int		ev, type;
+
+	if(!disc || !meth)
+		return NIL(Dt_t*);
+
+	dt = NIL(Dt_t*);
+	data = NIL(Dtdata_t*);
+	type = meth->type;
+
+	memset(&pdt, 0, sizeof(Dt_t));
+	pdt.searchf = meth->searchf;
+	pdt.meth = meth;
+	dtdisc(&pdt,disc,0); /* note that this sets pdt.memoryf */
+
+	if(disc->eventf)
+	{	if((ev = (*disc->eventf)(&pdt,DT_OPEN,(Void_t*)(&data),disc)) < 0)
+			return NIL(Dt_t*); /* something bad happened */
+		else if(ev > 0)
+		{	if(data) /* shared data are being restored */
+			{	if((data->type & DT_METHODS) != meth->type)
+				{	DTERROR(&pdt, "Error in matching methods to restore dictionary");
+					return NIL(Dt_t*);
+				}
+				pdt.data = data;
+			}
+		}
+		else
+		{	if(data) /* dt should be allocated with dt->data */
+				type |= DT_INDATA;
+		}
+	}
+
+	if(!pdt.data) /* allocate method-specific data */
+		if((*meth->eventf)(&pdt, DT_OPEN, NIL(Void_t*)) < 0 || !pdt.data )
+			return NIL(Dt_t*);
+	pdt.data->type |= type;
+
+	/* now allocate/initialize the actual dictionary structure */
+	if(pdt.data->type&DT_INDATA)
+		dt = &pdt.data->dict;
+	else if(!(dt = (Dt_t*) malloc(sizeof(Dt_t))) )
+	{	(void)(*meth->eventf)(&pdt, DT_CLOSE, NIL(Void_t*));
+		DTERROR(&pdt, "Error in allocating a new dictionary");
+		return NIL(Dt_t*);
+	}
+
+	*dt = pdt;
+
+	dt->user = &dt->data->user; /* space allocated for application usage */
+
+	if(disc->eventf) /* signal opening is done */
+		(void)(*disc->eventf)(dt, DT_ENDOPEN, (Void_t*)0, disc);
+
+	/* set mapping of operation bits between versions as needed */
+	if(version < 20111111L)
+		dt->typef = _dttype2005;
+
+	return dt;
+}
+
+#undef dtopen /* deal with binary upward compatibility for op bits */
+#if __STD_C
+Dt_t* dtopen(Dtdisc_t* disc, Dtmethod_t* meth)
+#else
+Dt_t*	dtopen(disc, meth)
+Dtdisc_t*	disc;
+Dtmethod_t*	meth;
+#endif
+{
+	return _dtopen(disc, meth, 20050420L);
+}
+
+/* below are private functions used across CDT modules */
+Dtlink_t* _dtmake(Dt_t* dt, Void_t* obj, int type)
+{
+	Dthold_t	*h;
+	Dtdisc_t	*disc = dt->disc;
+
+	/* if obj is a prototype, make a real one */
+	if(!(type&DT_ATTACH) && disc->makef && !(obj = (*disc->makef)(dt, obj, disc)) )
+		return NIL(Dtlink_t*);
+
+	if(disc->link >= 0) /* holder is embedded in obj itself */
+		return _DTLNK(disc, obj);
+
+	/* create a holder to hold obj */
+	if((h = (Dthold_t*)(dt->memoryf)(dt, NIL(Void_t*), sizeof(Dthold_t), disc)) )
+		h->obj = obj;
+	else
+	{	DTERROR(dt, "Error in allocating an object holder");
+		if(!(type&DT_ATTACH) && disc->makef && disc->freef)
+			(void)(*disc->freef)(dt, obj, disc); /* free just-made obj */
+	}
+
+	return (Dtlink_t*)h;
+}
+
+void _dtfree(Dt_t* dt, Dtlink_t* l, int type)
+{
+	Dtdisc_t	*disc = dt->disc;
+
+	if(!(type&DT_DETACH) && disc->freef) /* free object */
+		(void)(*disc->freef)(dt, _DTOBJ(disc,l), disc);
+
+	if(disc->link < 0) /* free holder */
+		(void)(*dt->memoryf)(dt, (Void_t*)l, 0, disc);
+}
+
+int dtuserlock(Dt_t* dt, unsigned int key, int type)
+{
+	if(type > 0)
+		return asolock(&dt->data->user.lock, key, ASO_LOCK);
+	else if(type < 0)
+		return asolock(&dt->data->user.lock, key, ASO_UNLOCK);
+	else	return asolock(&dt->data->user.lock, key, ASO_TRYLOCK);
+}
+
+Void_t* dtuserdata(Dt_t* dt, Void_t* data, unsigned int key)
+{
+	if(key == 0)
+		return dt->data->user.data;
+	else if(dtuserlock(dt, key, 1) < 0 )
+		return NIL(Void_t*);
+	else
+	{	dt->data->user.data = data;
+		dtuserlock(dt, key, -1);
+		return data;
+	}
+}
diff --git a/src/lib/libast/cdt/dtstrhash.c b/src/lib/libast/cdt/dtstrhash.c
new file mode 100644
index 0000000..7eaac89
--- /dev/null
+++ b/src/lib/libast/cdt/dtstrhash.c
@@ -0,0 +1,61 @@
+/***********************************************************************
+*                                                                      *
+*               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"
+
+/* Hashing a string into an unsigned integer.
+** The basic method is to continuingly accumulate bytes and multiply
+** with some given prime. The length n of the string is added last.
+** The recurrent equation is like this:
+**	h[k] = (h[k-1] + bytes)*prime	for 0 <= k < n
+**	h[n] = (h[n-1] + n)*prime
+** The prime is chosen to have a good distribution of 1-bits so that
+** the multiplication will distribute the bits in the accumulator well.
+** The below code accumulates 2 bytes at a time for speed.
+**
+** Written by Kiem-Phong Vo (02/28/03)
+*/
+
+#if __STD_C
+uint dtstrhash(uint h, Void_t* args, ssize_t n)
+#else
+uint dtstrhash(h,args,n)
+reg uint	h;
+Void_t*		args;
+ssize_t		n;
+#endif
+{
+	unsigned char	*s = (unsigned char*)args;
+
+	if(n <= 0)
+	{	for(; *s != 0; s += s[1] ? 2 : 1)
+			h = (h + (s[0]<<8) + s[1])*DT_PRIME;
+		n = s - (unsigned char*)args;
+	}
+	else
+	{	unsigned char*	ends;
+		for(ends = s+n-1; s < ends; s += 2)
+			h = (h + (s[0]<<8) + s[1])*DT_PRIME;
+		if(s <= ends)
+			h = (h + (s[0]<<8))*DT_PRIME;
+	}
+	return (h+n)*DT_PRIME;
+}
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
diff --git a/src/lib/libast/cdt/dtview.c b/src/lib/libast/cdt/dtview.c
new file mode 100644
index 0000000..94f4a54
--- /dev/null
+++ b/src/lib/libast/cdt/dtview.c
@@ -0,0 +1,157 @@
+/***********************************************************************
+*                                                                      *
+*               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"
+
+/*	Set a view path from dict to view.
+**
+**	Written by Kiem-Phong Vo (5/25/96)
+*/
+
+/* these operations must be done without viewpathing */
+#define DT_NOVIEWPATH	(DT_INSERT|DT_APPEND|DT_DELETE|\
+			 DT_ATTACH|DT_DETACH|DT_RELINK|DT_CLEAR| \
+			 DT_FLATTEN|DT_EXTRACT|DT_RESTORE|DT_STAT)
+
+#if __STD_C
+static Void_t* dtvsearch(Dt_t* dt, reg Void_t* obj, reg int type)
+#else
+static Void_t* dtvsearch(dt,obj,type)
+Dt_t*		dt;
+reg Void_t*	obj;
+reg int		type;
+#endif
+{
+	int		cmp;
+	Dt_t		*d, *p;
+	Void_t		*o, *n, *oky, *nky;
+
+	if(type&DT_NOVIEWPATH)
+		return (*(dt->meth->searchf))(dt,obj,type);
+
+	o = NIL(Void_t*);
+
+	/* these ops look for the first appearance of an object of the right type */
+	if((type & (DT_MATCH|DT_SEARCH)) ||
+	   ((type & (DT_FIRST|DT_LAST|DT_ATLEAST|DT_ATMOST)) && !(dt->meth->type&DT_ORDERED) ) )
+	{	for(d = dt; d; d = d->view)
+			if((o = (*(d->meth->searchf))(d,obj,type)) )
+				break;
+		dt->walk = d;
+		return o;
+	}
+
+	if(dt->meth->type & DT_ORDERED) /* ordered sets/bags */
+	{	if(!(type & (DT_FIRST|DT_LAST|DT_NEXT|DT_PREV|DT_ATLEAST|DT_ATMOST)) )
+			return NIL(Void_t*);
+
+		/* find the min/max element that satisfies the op requirement */
+		n = nky = NIL(Void_t*); p = NIL(Dt_t*);
+		for(d = dt; d; d = d->view)
+		{	if(!(o = (*d->meth->searchf)(d, obj, type)) )
+				continue;
+			oky = _DTKEY(d->disc,o);
+
+			if(n) /* get the right one among all dictionaries */
+			{	cmp = _DTCMP(d,oky,nky,d->disc);
+				if(((type & (DT_NEXT|DT_FIRST|DT_ATLEAST)) && cmp < 0) ||
+				   ((type & (DT_PREV|DT_LAST|DT_ATMOST)) && cmp > 0) )
+					goto b_est;
+			}
+			else
+			{ b_est: /* current best element to fit op requirement */
+				p  = d;
+				n  = o;
+				nky = oky;
+			}
+		}
+
+		dt->walk = p;
+		return n;
+	}
+
+	/* unordered collections */
+	if(!(type&(DT_NEXT|DT_PREV)) )
+		return NIL(Void_t*);
+
+	if(!dt->walk )
+	{	for(d = dt; d; d = d->view)
+			if((o = (*(d->meth->searchf))(d, obj, DT_SEARCH)) )
+				break;
+		dt->walk = d;
+		if(!(obj = o) )
+			return NIL(Void_t*);
+	}
+
+	for(d = dt->walk, obj = (*d->meth->searchf)(d, obj, type);; )
+	{	while(obj) /* keep moving until finding an uncovered object */
+		{	for(p = dt; ; p = p->view)
+			{	if(p == d) /* adjacent object is uncovered */	
+					return obj;
+				if((*(p->meth->searchf))(p, obj, DT_SEARCH) )
+					break;
+			}
+			obj = (*d->meth->searchf)(d, obj, type);
+		}
+
+		if(!(d = dt->walk = d->view) ) /* move on to next dictionary */
+			return NIL(Void_t*);
+		else if(type&DT_NEXT)
+			obj = (*(d->meth->searchf))(d,NIL(Void_t*),DT_FIRST);
+		else	obj = (*(d->meth->searchf))(d,NIL(Void_t*),DT_LAST);
+	}
+}
+
+#if __STD_C
+Dt_t* dtview(reg Dt_t* dt, reg Dt_t* view)
+#else
+Dt_t* dtview(dt,view)
+reg Dt_t*	dt;
+reg Dt_t*	view;
+#endif
+{
+	reg Dt_t*	d;
+
+	if(view && view->meth != dt->meth) /* must use the same method */
+		return NIL(Dt_t*);
+
+	/* make sure there won't be a cycle */
+	for(d = view; d; d = d->view)
+		if(d == dt)
+			return NIL(Dt_t*);
+
+	/* no more viewing lower dictionary */
+	if((d = dt->view) )
+		d->nview -= 1;
+	dt->view = dt->walk = NIL(Dt_t*);
+
+	if(!view)
+	{	dt->searchf = dt->meth->searchf;
+		return d;
+	}
+
+	/* ok */
+	dt->view = view;
+	dt->searchf = dtvsearch;
+	view->nview += 1;
+
+	return view;
+}
diff --git a/src/lib/libast/cdt/dtwalk.c b/src/lib/libast/cdt/dtwalk.c
new file mode 100644
index 0000000..05c706c
--- /dev/null
+++ b/src/lib/libast/cdt/dtwalk.c
@@ -0,0 +1,53 @@
+/***********************************************************************
+*                                                                      *
+*               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"
+
+/*	Walk a dictionary and all dictionaries viewed through it.
+**	userf:	user function
+**
+**	Written by Kiem-Phong Vo (5/25/96)
+*/
+
+#if __STD_C
+int dtwalk(Dt_t* dt, int (*userf)(Dt_t*, Void_t*, Void_t*), Void_t* data)
+#else
+int dtwalk(dt,userf,data)
+Dt_t*	dt;
+int(*	userf)();
+Void_t*	data;
+#endif
+{
+	Void_t	*obj, *next;
+	Dt_t	*walk;
+	int	rv;
+
+	for(obj = dtfirst(dt); obj; )
+	{	if(!(walk = dt->walk) )
+			walk = dt;
+		next = dtnext(dt,obj);
+		if((rv = (*userf)(walk, obj, data )) < 0)
+			return rv;
+		obj = next;
+	}
+
+	return 0;
+}