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