1/***********************************************************************
2*                                                                      *
3*               This software is part of the ast package               *
4*          Copyright (c) 1985-2011 AT&T Intellectual Property          *
5*                      and is licensed under the                       *
6*                  Common Public License, Version 1.0                  *
7*                    by AT&T Intellectual Property                     *
8*                                                                      *
9*                A copy of the License is available at                 *
10*            http://www.opensource.org/licenses/cpl1.0.txt             *
11*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
12*                                                                      *
13*              Information and Software Systems Research               *
14*                            AT&T Research                             *
15*                           Florham Park NJ                            *
16*                                                                      *
17*                 Glenn Fowler <gsf@research.att.com>                  *
18*                  David Korn <dgk@research.att.com>                   *
19*                   Phong Vo <kpv@research.att.com>                    *
20*                                                                      *
21***********************************************************************/
22#include	"dthdr.h"
23
24/*	Hash table.
25**	dt:	dictionary
26**	obj:	what to look for
27**	type:	type of search
28**
29**      Written by Kiem-Phong Vo (05/25/96)
30*/
31
32/* resize the hash table */
33#if __STD_C
34static void dthtab(Dt_t* dt)
35#else
36static void dthtab(dt)
37Dt_t*	dt;
38#endif
39{
40	reg Dtlink_t	*t, *r, *p, **s, **hs, **is, **olds;
41	int		n, k;
42
43	if(dt->data->minp > 0 && dt->data->ntab > 0) /* fixed table size */
44		return;
45	dt->data->minp = 0;
46
47	n = dt->data->ntab;
48	if(dt->disc && dt->disc->eventf &&
49	   (*dt->disc->eventf)(dt, DT_HASHSIZE, &n, dt->disc) > 0 )
50	{	if(n < 0) /* fix table size */
51		{	dt->data->minp = 1;
52			if(dt->data->ntab > 0 )
53				return;
54		}
55		else /* set a particular size */
56		{	for(k = 2; k < n; k *= 2)
57				;
58			n = k;
59		}
60	}
61	else	n = 0;
62
63	/* compute new table size */
64	if(n <= 0)
65	{	if((n = dt->data->ntab) == 0)
66			n = HSLOT;
67		while(dt->data->size > HLOAD(n))
68			n = HRESIZE(n);
69	}
70	if(n == dt->data->ntab)
71		return;
72
73	/* allocate new table */
74	olds = dt->data->ntab == 0 ? NIL(Dtlink_t**) : dt->data->htab;
75	if(!(s = (Dtlink_t**)(*dt->memoryf)(dt,olds,n*sizeof(Dtlink_t*),dt->disc)) )
76		return;
77	olds = s + dt->data->ntab;
78	dt->data->htab = s;
79	dt->data->ntab = n;
80
81	/* rehash elements */
82	for(hs = s+n-1; hs >= olds; --hs)
83		*hs = NIL(Dtlink_t*);
84	for(hs = s; hs < olds; ++hs)
85	{	for(p = NIL(Dtlink_t*), t = *hs; t; t = r)
86		{	r = t->right;
87			if((is = s + HINDEX(n,t->hash)) == hs)
88				p = t;
89			else	/* move to a new chain */
90			{	if(p)
91					p->right = r;
92				else	*hs = r;
93				t->right = *is; *is = t;
94			}
95		}
96	}
97}
98
99#if __STD_C
100static Void_t* dthash(Dt_t* dt, reg Void_t* obj, int type)
101#else
102static Void_t* dthash(dt,obj,type)
103Dt_t*		dt;
104reg Void_t*	obj;
105int		type;
106#endif
107{
108	reg Dtlink_t	*t, *r, *p;
109	reg Void_t	*k, *key;
110	reg uint	hsh;
111	reg int		lk, sz, ky;
112	reg Dtcompar_f	cmpf;
113	reg Dtdisc_t*	disc;
114	reg Dtlink_t	**s, **ends;
115
116	UNFLATTEN(dt);
117
118	/* initialize discipline data */
119	disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
120	dt->type &= ~DT_FOUND;
121
122	if(!obj)
123	{	if(type&(DT_NEXT|DT_PREV))
124			goto end_walk;
125
126		if(dt->data->size <= 0 || !(type&(DT_CLEAR|DT_FIRST|DT_LAST)) )
127			return NIL(Void_t*);
128
129		ends = (s = dt->data->htab) + dt->data->ntab;
130		if(type&DT_CLEAR)
131		{	/* clean out all objects */
132			for(; s < ends; ++s)
133			{	t = *s;
134				*s = NIL(Dtlink_t*);
135				if(!disc->freef && disc->link >= 0)
136					continue;
137				while(t)
138				{	r = t->right;
139					if(disc->freef)
140						(*disc->freef)(dt,_DTOBJ(t,lk),disc);
141					if(disc->link < 0)
142						(*dt->memoryf)(dt,(Void_t*)t,0,disc);
143					t = r;
144				}
145			}
146			dt->data->here = NIL(Dtlink_t*);
147			dt->data->size = 0;
148			dt->data->loop = 0;
149			return NIL(Void_t*);
150		}
151		else	/* computing the first/last object */
152		{	t = NIL(Dtlink_t*);
153			while(s < ends && !t )
154				t = (type&DT_LAST) ? *--ends : *s++;
155			if(t && (type&DT_LAST))
156				for(; t->right; t = t->right)
157					;
158
159			dt->data->loop += 1;
160			dt->data->here = t;
161			return t ? _DTOBJ(t,lk) : NIL(Void_t*);
162		}
163	}
164
165	/* allow apps to delete an object "actually" in the dictionary */
166	if(dt->meth->type == DT_BAG && (type&(DT_DELETE|DT_DETACH)) )
167	{	if(!dtsearch(dt,obj) )
168			return NIL(Void_t*);
169
170		s = dt->data->htab + HINDEX(dt->data->ntab,dt->data->here->hash);
171		r = NIL(Dtlink_t*);
172		for(p = NIL(Dtlink_t*), t = *s; t; p = t, t = t->right)
173		{	if(_DTOBJ(t,lk) == obj) /* delete this specific object */
174				goto do_delete;
175			if(t == dt->data->here)
176				r = p;
177		}
178
179		/* delete some matching object */
180		p = r; t = dt->data->here;
181		goto do_delete;
182	}
183
184	if(type&(DT_MATCH|DT_SEARCH|DT_INSERT|DT_ATTACH) )
185	{	key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
186		hsh = _DTHSH(dt,key,disc,sz);
187		goto do_search;
188	}
189	else if(type&(DT_RENEW|DT_VSEARCH) )
190	{	r = (Dtlink_t*)obj;
191		obj = _DTOBJ(r,lk);
192		key = _DTKEY(obj,ky,sz);
193		hsh = r->hash;
194		goto do_search;
195	}
196	else /*if(type&(DT_DELETE|DT_DETACH|DT_NEXT|DT_PREV))*/
197	{	if((t = dt->data->here) && _DTOBJ(t,lk) == obj)
198		{	hsh = t->hash;
199			s = dt->data->htab + HINDEX(dt->data->ntab,hsh);
200			p = NIL(Dtlink_t*);
201		}
202		else
203		{	key = _DTKEY(obj,ky,sz);
204			hsh = _DTHSH(dt,key,disc,sz);
205		do_search:
206			t = dt->data->ntab <= 0 ? NIL(Dtlink_t*) :
207			 	*(s = dt->data->htab + HINDEX(dt->data->ntab,hsh));
208			for(p = NIL(Dtlink_t*); t; p = t, t = t->right)
209			{	if(hsh == t->hash)
210				{	k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
211					if(_DTCMP(dt,key,k,disc,cmpf,sz) == 0)
212						break;
213				}
214			}
215		}
216	}
217
218	if(t) /* found matching object */
219		dt->type |= DT_FOUND;
220
221	if(type&(DT_MATCH|DT_SEARCH|DT_VSEARCH))
222	{	if(!t)
223			return NIL(Void_t*);
224		if(p && (dt->data->type&DT_SET) && dt->data->loop <= 0)
225		{	/* move-to-front heuristic */
226			p->right = t->right;
227			t->right = *s;
228			*s = t;
229		}
230		dt->data->here = t;
231		return _DTOBJ(t,lk);
232	}
233	else if(type&(DT_INSERT|DT_ATTACH))
234	{	if(t && (dt->data->type&DT_SET) )
235		{	dt->data->here = t;
236			return _DTOBJ(t,lk);
237		}
238
239		if(disc->makef && (type&DT_INSERT) &&
240		   !(obj = (*disc->makef)(dt,obj,disc)) )
241			return NIL(Void_t*);
242		if(lk >= 0)
243			r = _DTLNK(obj,lk);
244		else
245		{	r = (Dtlink_t*)(*dt->memoryf)
246				(dt,NIL(Void_t*),sizeof(Dthold_t),disc);
247			if(r)
248				((Dthold_t*)r)->obj = obj;
249			else
250			{	if(disc->makef && disc->freef && (type&DT_INSERT))
251					(*disc->freef)(dt,obj,disc);
252				return NIL(Void_t*);
253			}
254		}
255		r->hash = hsh;
256
257		/* insert object */
258	do_insert:
259		if((dt->data->size += 1) > HLOAD(dt->data->ntab) && dt->data->loop <= 0 )
260			dthtab(dt);
261		if(dt->data->ntab == 0)
262		{	dt->data->size -= 1;
263			if(disc->freef && (type&DT_INSERT))
264				(*disc->freef)(dt,obj,disc);
265			if(disc->link < 0)
266				(*disc->memoryf)(dt,(Void_t*)r,0,disc);
267			return NIL(Void_t*);
268		}
269		s = dt->data->htab + HINDEX(dt->data->ntab,hsh);
270		if(t)
271		{	r->right = t->right;
272			t->right = r;
273		}
274		else
275		{	r->right = *s;
276			*s = r;
277		}
278		dt->data->here = r;
279		return obj;
280	}
281	else if(type&DT_NEXT)
282	{	if(t && !(p = t->right) )
283		{	for(ends = dt->data->htab+dt->data->ntab, s += 1; s < ends; ++s)
284				if((p = *s) )
285					break;
286		}
287		goto done_adj;
288	}
289	else if(type&DT_PREV)
290	{	if(t && !p)
291		{	if((p = *s) != t)
292			{	while(p->right != t)
293					p = p->right;
294			}
295			else
296			{	p = NIL(Dtlink_t*);
297				for(s -= 1, ends = dt->data->htab; s >= ends; --s)
298				{	if((p = *s) )
299					{	while(p->right)
300							p = p->right;
301						break;
302					}
303				}
304			}
305		}
306	done_adj:
307		if(!(dt->data->here = p) )
308		{ end_walk:
309			if((dt->data->loop -= 1) < 0)
310				dt->data->loop = 0;
311			if(dt->data->size > HLOAD(dt->data->ntab) && dt->data->loop <= 0)
312				dthtab(dt);
313			return NIL(Void_t*);
314		}
315		else
316		{	dt->data->type |= DT_WALK;
317			return _DTOBJ(p,lk);
318		}
319	}
320	else if(type&DT_RENEW)
321	{	if(!t || (dt->data->type&DT_BAG) )
322			goto do_insert;
323		else
324		{	if(disc->freef)
325				(*disc->freef)(dt,obj,disc);
326			if(disc->link < 0)
327				(*dt->memoryf)(dt,(Void_t*)r,0,disc);
328			return t ? _DTOBJ(t,lk) : NIL(Void_t*);
329		}
330	}
331	else /*if(type&(DT_DELETE|DT_DETACH))*/
332	{	/* take an element out of the dictionary */
333	do_delete:
334		if(!t)
335			return NIL(Void_t*);
336		else if(p)
337			p->right = t->right;
338		else if((p = *s) == t)
339			p = *s = t->right;
340		else
341		{	while(p->right != t)
342				p = p->right;
343			p->right = t->right;
344		}
345		obj = _DTOBJ(t,lk);
346		dt->data->size -= 1;
347		dt->data->here = p;
348		if(disc->freef && (type&DT_DELETE))
349			(*disc->freef)(dt,obj,disc);
350		if(disc->link < 0)
351			(*dt->memoryf)(dt,(Void_t*)t,0,disc);
352		return obj;
353	}
354}
355
356static Dtmethod_t	_Dtset = { dthash, DT_SET };
357static Dtmethod_t	_Dtbag = { dthash, DT_BAG };
358__DEFINE__(Dtmethod_t*,Dtset,&_Dtset);
359__DEFINE__(Dtmethod_t*,Dtbag,&_Dtbag);
360
361#ifndef KPVDEL	/* for backward compatibility - remove next time */
362Dtmethod_t		_Dthash = { dthash, DT_SET };
363__DEFINE__(Dtmethod_t*,Dthash,&_Dthash);
364#endif
365
366#ifdef NoF
367NoF(dthash)
368#endif
369