Imported Upstream version 93u+upstream

1 files changed, 431 insertions, 0 deletions

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