xref: /titanic_50/usr/src/lib/libast/common/cdt/dthash.c (revision 3e14f97f673e8a630f076077de35afdd43dc1587)

/***********************************************************************
*                                                                      *
*               This software is part of the ast package               *
*          Copyright (c) 1985-2010 AT&T Intellectual Property          *
*                      and is licensed under the                       *
*                  Common Public License, Version 1.0                  *
*                    by AT&T Intellectual Property                     *
*                                                                      *
*                A copy of the License is available at                 *
*            http://www.opensource.org/licenses/cpl1.0.txt             *
*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
*                                                                      *
*              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.
**	dt:	dictionary
**	obj:	what to look for
**	type:	type of search
**
**      Written by Kiem-Phong Vo (05/25/96)
*/

/* resize the hash table */
#if __STD_C
static void dthtab(Dt_t* dt)
#else
static void dthtab(dt)
Dt_t*	dt;
#endif
{
	reg Dtlink_t	*t, *r, *p, **s, **hs, **is, **olds;
	int		n, k;

	if(dt->data->minp > 0 && dt->data->ntab > 0) /* fixed table size */
		return;
	dt->data->minp = 0;

	n = dt->data->ntab;
	if(dt->disc && dt->disc->eventf &&
	   (*dt->disc->eventf)(dt, DT_HASHSIZE, &n, dt->disc) > 0 )
	{	if(n < 0) /* fix table size */
		{	dt->data->minp = 1;
			if(dt->data->ntab > 0 )
				return;
		}
		else /* set a particular size */
		{	for(k = 2; k < n; k *= 2)
				;
			n = k;
		}
	}
	else	n = 0;

	/* compute new table size */
	if(n <= 0)
	{	if((n = dt->data->ntab) == 0)
			n = HSLOT;
		while(dt->data->size > HLOAD(n))
			n = HRESIZE(n);
	}
	if(n == dt->data->ntab)
		return;

	/* allocate new table */
	olds = dt->data->ntab == 0 ? NIL(Dtlink_t**) : dt->data->htab;
	if(!(s = (Dtlink_t**)(*dt->memoryf)(dt,olds,n*sizeof(Dtlink_t*),dt->disc)) )
		return;
	olds = s + dt->data->ntab;
	dt->data->htab = s;
	dt->data->ntab = n;

	/* rehash elements */
	for(hs = s+n-1; hs >= olds; --hs)
		*hs = NIL(Dtlink_t*);
	for(hs = s; hs < olds; ++hs)
	{	for(p = NIL(Dtlink_t*), t = *hs; t; t = r)
		{	r = t->right;
			if((is = s + HINDEX(n,t->hash)) == hs)
				p = t;
			else	/* move to a new chain */
			{	if(p)
					p->right = r;
				else	*hs = r;
				t->right = *is; *is = t;
			}
		}
	}
}

#if __STD_C
static Void_t* dthash(Dt_t* dt, reg Void_t* obj, int type)
#else
static Void_t* dthash(dt,obj,type)
Dt_t*		dt;
reg Void_t*	obj;
int		type;
#endif
{
	reg Dtlink_t	*t, *r, *p;
	reg Void_t	*k, *key;
	reg uint	hsh;
	reg int		lk, sz, ky;
	reg Dtcompar_f	cmpf;
	reg Dtdisc_t*	disc;
	reg Dtlink_t	**s, **ends;

	UNFLATTEN(dt);

	/* initialize discipline data */
	disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
	dt->type &= ~DT_FOUND;

	if(!obj)
	{	if(type&(DT_NEXT|DT_PREV))
			goto end_walk;

		if(dt->data->size <= 0 || !(type&(DT_CLEAR|DT_FIRST|DT_LAST)) )
			return NIL(Void_t*);

		ends = (s = dt->data->htab) + dt->data->ntab;
		if(type&DT_CLEAR)
		{	/* clean out all objects */
			for(; s < ends; ++s)
			{	t = *s;
				*s = NIL(Dtlink_t*);
				if(!disc->freef && disc->link >= 0)
					continue;
				while(t)
				{	r = t->right;
					if(disc->freef)
						(*disc->freef)(dt,_DTOBJ(t,lk),disc);
					if(disc->link < 0)
						(*dt->memoryf)(dt,(Void_t*)t,0,disc);
					t = r;
				}
			}
			dt->data->here = NIL(Dtlink_t*);
			dt->data->size = 0;
			dt->data->loop = 0;
			return NIL(Void_t*);
		}
		else	/* computing the first/last object */
		{	t = NIL(Dtlink_t*);
			while(s < ends && !t )
				t = (type&DT_LAST) ? *--ends : *s++;
			if(t && (type&DT_LAST))
				for(; t->right; t = t->right)
					;

			dt->data->loop += 1;
			dt->data->here = t;
			return t ? _DTOBJ(t,lk) : NIL(Void_t*);
		}
	}

	/* allow apps to delete an object "actually" in the dictionary */
	if(dt->meth->type == DT_BAG && (type&(DT_DELETE|DT_DETACH)) )
	{	if(!dtsearch(dt,obj) )
			return NIL(Void_t*);

		s = dt->data->htab + HINDEX(dt->data->ntab,dt->data->here->hash);
		r = NIL(Dtlink_t*);
		for(p = NIL(Dtlink_t*), t = *s; t; p = t, t = t->right)
		{	if(_DTOBJ(t,lk) == obj) /* delete this specific object */
				goto do_delete;
			if(t == dt->data->here)
				r = p;
		}

		/* delete some matching object */
		p = r; t = dt->data->here;
		goto do_delete;
	}

	if(type&(DT_MATCH|DT_SEARCH|DT_INSERT|DT_ATTACH) )
	{	key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
		hsh = _DTHSH(dt,key,disc,sz);
		goto do_search;
	}
	else if(type&(DT_RENEW|DT_VSEARCH) )
	{	r = (Dtlink_t*)obj;
		obj = _DTOBJ(r,lk);
		key = _DTKEY(obj,ky,sz);
		hsh = r->hash;
		goto do_search;
	}
	else /*if(type&(DT_DELETE|DT_DETACH|DT_NEXT|DT_PREV))*/
	{	if((t = dt->data->here) && _DTOBJ(t,lk) == obj)
		{	hsh = t->hash;
			s = dt->data->htab + HINDEX(dt->data->ntab,hsh);
			p = NIL(Dtlink_t*);
		}
		else
		{	key = _DTKEY(obj,ky,sz);
			hsh = _DTHSH(dt,key,disc,sz);
		do_search:
			t = dt->data->ntab <= 0 ? NIL(Dtlink_t*) :
			 	*(s = dt->data->htab + HINDEX(dt->data->ntab,hsh));
			for(p = NIL(Dtlink_t*); t; p = t, t = t->right)
			{	if(hsh == t->hash)
				{	k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
					if(_DTCMP(dt,key,k,disc,cmpf,sz) == 0)
						break;
				}
			}
		}
	}

	if(t) /* found matching object */
		dt->type |= DT_FOUND;

	if(type&(DT_MATCH|DT_SEARCH|DT_VSEARCH))
	{	if(!t)
			return NIL(Void_t*);
		if(p && (dt->data->type&DT_SET) && dt->data->loop <= 0)
		{	/* move-to-front heuristic */
			p->right = t->right;
			t->right = *s;
			*s = t;
		}
		dt->data->here = t;
		return _DTOBJ(t,lk);
	}
	else if(type&(DT_INSERT|DT_ATTACH))
	{	if(t && (dt->data->type&DT_SET) )
		{	dt->data->here = t;
			return _DTOBJ(t,lk);
		}

		if(disc->makef && (type&DT_INSERT) &&
		   !(obj = (*disc->makef)(dt,obj,disc)) )
			return NIL(Void_t*);
		if(lk >= 0)
			r = _DTLNK(obj,lk);
		else
		{	r = (Dtlink_t*)(*dt->memoryf)
				(dt,NIL(Void_t*),sizeof(Dthold_t),disc);
			if(r)
				((Dthold_t*)r)->obj = obj;
			else
			{	if(disc->makef && disc->freef && (type&DT_INSERT))
					(*disc->freef)(dt,obj,disc);
				return NIL(Void_t*);
			}
		}
		r->hash = hsh;

		/* insert object */
	do_insert:
		if((dt->data->size += 1) > HLOAD(dt->data->ntab) && dt->data->loop <= 0 )
			dthtab(dt);
		if(dt->data->ntab == 0)
		{	dt->data->size -= 1;
			if(disc->freef && (type&DT_INSERT))
				(*disc->freef)(dt,obj,disc);
			if(disc->link < 0)
				(*disc->memoryf)(dt,(Void_t*)r,0,disc);
			return NIL(Void_t*);
		}
		s = dt->data->htab + HINDEX(dt->data->ntab,hsh);
		if(t)
		{	r->right = t->right;
			t->right = r;
		}
		else
		{	r->right = *s;
			*s = r;
		}
		dt->data->here = r;
		return obj;
	}
	else if(type&DT_NEXT)
	{	if(t && !(p = t->right) )
		{	for(ends = dt->data->htab+dt->data->ntab, s += 1; s < ends; ++s)
				if((p = *s) )
					break;
		}
		goto done_adj;
	}
	else if(type&DT_PREV)
	{	if(t && !p)
		{	if((p = *s) != t)
			{	while(p->right != t)
					p = p->right;
			}
			else
			{	p = NIL(Dtlink_t*);
				for(s -= 1, ends = dt->data->htab; s >= ends; --s)
				{	if((p = *s) )
					{	while(p->right)
							p = p->right;
						break;
					}
				}
			}
		}
	done_adj:
		if(!(dt->data->here = p) )
		{ end_walk:
			if((dt->data->loop -= 1) < 0)
				dt->data->loop = 0;
			if(dt->data->size > HLOAD(dt->data->ntab) && dt->data->loop <= 0)
				dthtab(dt);
			return NIL(Void_t*);
		}
		else
		{	dt->data->type |= DT_WALK;
			return _DTOBJ(p,lk);
		}
	}
	else if(type&DT_RENEW)
	{	if(!t || (dt->data->type&DT_BAG) )
			goto do_insert;
		else
		{	if(disc->freef)
				(*disc->freef)(dt,obj,disc);
			if(disc->link < 0)
				(*dt->memoryf)(dt,(Void_t*)r,0,disc);
			return t ? _DTOBJ(t,lk) : NIL(Void_t*);
		}
	}
	else /*if(type&(DT_DELETE|DT_DETACH))*/
	{	/* take an element out of the dictionary */
	do_delete:
		if(!t)
			return NIL(Void_t*);
		else if(p)
			p->right = t->right;
		else if((p = *s) == t)
			p = *s = t->right;
		else
		{	while(p->right != t)
				p = p->right;
			p->right = t->right;
		}
		obj = _DTOBJ(t,lk);
		dt->data->size -= 1;
		dt->data->here = p;
		if(disc->freef && (type&DT_DELETE))
			(*disc->freef)(dt,obj,disc);
		if(disc->link < 0)
			(*dt->memoryf)(dt,(Void_t*)t,0,disc);
		return obj;
	}
}

static Dtmethod_t	_Dtset = { dthash, DT_SET };
static Dtmethod_t	_Dtbag = { dthash, DT_BAG };
__DEFINE__(Dtmethod_t*,Dtset,&_Dtset);
__DEFINE__(Dtmethod_t*,Dtbag,&_Dtbag);

#ifndef KPVDEL	/* for backward compatibility - remove next time */
Dtmethod_t		_Dthash = { dthash, DT_SET };
__DEFINE__(Dtmethod_t*,Dthash,&_Dthash);
#endif

#ifdef NoF
NoF(dthash)
#endif