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