xref: /titanic_44/usr/src/lib/libast/common/cdt/dthash.c (revision 3e14f97f673e8a630f076077de35afdd43dc1587) 
1 /***********************************************************************
2 *                                                                      *
3 *               This software is part of the ast package               *
4 *          Copyright (c) 1985-2010 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
dthtab(Dt_t * dt)34 static void dthtab(Dt_t* dt)
35 #else
36 static void dthtab(dt)
37 Dt_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
dthash(Dt_t * dt,reg Void_t * obj,int type)100 static Void_t* dthash(Dt_t* dt, reg Void_t* obj, int type)
101 #else
102 static Void_t* dthash(dt,obj,type)
103 Dt_t*		dt;
104 reg Void_t*	obj;
105 int		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 
356 static Dtmethod_t	_Dtset = { dthash, DT_SET };
357 static 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 */
362 Dtmethod_t		_Dthash = { dthash, DT_SET };
363 __DEFINE__(Dtmethod_t*,Dthash,&_Dthash);
364 #endif
365 
366 #ifdef NoF
367 NoF(dthash)
368 #endif
369