1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1985-2012 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Eclipse Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
8 * *
9 * A copy of the License is available at *
10 * http://www.eclipse.org/org/documents/epl-v10.html *
11 * (with md5 checksum b35adb5213ca9657e911e9befb180842) *
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 with chaining for collisions.
25 **
26 ** Written by Kiem-Phong Vo (05/25/96)
27 */
28
29 /* these bits should be outside the scope of DT_METHODS */
30 #define H_FIXED 0100000 /* table size is fixed */
31 #define H_FLATTEN 0200000 /* table was flattened */
32
33 #define HLOAD(n) (n) /* load one-to-one */
34
35 /* internal data structure for hash table with chaining */
36 typedef struct _dthash_s
37 { Dtdata_t data;
38 int type;
39 Dtlink_t* here; /* fingered object */
40 Dtlink_t** htbl; /* hash table slots */
41 ssize_t tblz; /* size of hash table */
42 } Dthash_t;
43
44 /* make/resize hash table */
htable(Dt_t * dt)45 static int htable(Dt_t* dt)
46 {
47 Dtlink_t **htbl, **t, **endt, *l, *next;
48 ssize_t n, k;
49 Dtdisc_t *disc = dt->disc;
50 Dthash_t *hash = (Dthash_t*)dt->data;
51
52 if((n = hash->tblz) > 0 && (hash->type&H_FIXED) )
53 return 0; /* fixed size table */
54
55 if(n == 0 && disc && disc->eventf) /* let user have input */
56 { if((*disc->eventf)(dt, DT_HASHSIZE, &n, disc) > 0 )
57 { if(n < 0) /* fix table size */
58 { hash->type |= H_FIXED;
59 n = -n;
60 }
61 }
62 }
63
64 /* table size should be a power of 2 */
65 n = n < HLOAD(hash->data.size) ? HLOAD(hash->data.size) : n;
66 for(k = (1<<DT_HTABLE); k < n; )
67 k *= 2;
68 if((n = k) <= hash->tblz)
69 return 0;
70
71 /* allocate new table */
72 if(!(htbl = (Dtlink_t**)(*dt->memoryf)(dt, 0, n*sizeof(Dtlink_t*), disc)) )
73 { DTERROR(dt, "Error in allocating an extended hash table");
74 return -1;
75 }
76 memset(htbl, 0, n*sizeof(Dtlink_t*));
77
78 /* move objects into new table */
79 for(endt = (t = hash->htbl) + hash->tblz; t < endt; ++t)
80 { for(l = *t; l; l = next)
81 { next = l->_rght;
82 l->_rght = htbl[k = l->_hash&(n-1)];
83 htbl[k] = l;
84 }
85 }
86
87 if(hash->htbl) /* free old table and set new table */
88 (void)(*dt->memoryf)(dt, hash->htbl, 0, disc);
89 hash->htbl = htbl;
90 hash->tblz = n;
91
92 return 0;
93 }
94
hclear(Dt_t * dt)95 static Void_t* hclear(Dt_t* dt)
96 {
97 Dtlink_t **t, **endt, *l, *next;
98 Dthash_t *hash = (Dthash_t*)dt->data;
99
100 hash->here = NIL(Dtlink_t*);
101 hash->data.size = 0;
102
103 for(endt = (t = hash->htbl) + hash->tblz; t < endt; ++t)
104 { for(l = *t; l; l = next)
105 { next = l->_rght;
106 _dtfree(dt, l, DT_DELETE);
107 }
108 *t = NIL(Dtlink_t*);
109 }
110
111 return NIL(Void_t*);
112 }
113
hfirst(Dt_t * dt)114 static Void_t* hfirst(Dt_t* dt)
115 {
116 Dtlink_t **t, **endt, *l;
117 Dthash_t *hash = (Dthash_t*)dt->data;
118
119 for(endt = (t = hash->htbl) + hash->tblz; t < endt; ++t)
120 { if(!(l = *t) )
121 continue;
122 hash->here = l;
123 return _DTOBJ(dt->disc, l);
124 }
125
126 return NIL(Void_t*);
127 }
128
hnext(Dt_t * dt,Dtlink_t * l)129 static Void_t* hnext(Dt_t* dt, Dtlink_t* l)
130 {
131 Dtlink_t **t, **endt, *next;
132 Dthash_t *hash = (Dthash_t*)dt->data;
133
134 if((next = l->_rght) )
135 { hash->here = next;
136 return _DTOBJ(dt->disc, next);
137 }
138 else
139 { t = hash->htbl + (l->_hash & (hash->tblz-1)) + 1;
140 endt = hash->htbl + hash->tblz;
141 for(; t < endt; ++t)
142 { if(!(l = *t) )
143 continue;
144 hash->here = l;
145 return _DTOBJ(dt->disc, l);
146 }
147 return NIL(Void_t*);
148 }
149 }
150
hflatten(Dt_t * dt,int type)151 static Void_t* hflatten(Dt_t* dt, int type)
152 {
153 Dtlink_t **t, **endt, *head, *tail, *l;
154 Dthash_t *hash = (Dthash_t*)dt->data;
155
156 if(type == DT_FLATTEN || type == DT_EXTRACT)
157 { head = tail = NIL(Dtlink_t*);
158 for(endt = (t = hash->htbl) + hash->tblz; t < endt; ++t)
159 { for(l = *t; l; l = l->_rght)
160 { if(tail)
161 tail = (tail->_rght = l);
162 else head = tail = l;
163
164 *t = type == DT_FLATTEN ? tail : NIL(Dtlink_t*);
165 }
166 }
167
168 if(type == DT_FLATTEN)
169 { hash->here = head;
170 hash->type |= H_FLATTEN;
171 }
172 else hash->data.size = 0;
173
174 return (Void_t*)head;
175 }
176 else /* restoring a previous flattened list */
177 { head = hash->here;
178 for(endt = (t = hash->htbl) + hash->tblz; t < endt; ++t)
179 { if(*t == NIL(Dtlink_t*))
180 continue;
181
182 /* find the tail of the list for this slot */
183 for(l = head; l && l != *t; l = l->_rght)
184 ;
185 if(!l) /* something is seriously wrong */
186 return NIL(Void_t*);
187
188 *t = head; /* head of list for this slot */
189 head = l->_rght; /* head of next list */
190 l->_rght = NIL(Dtlink_t*);
191 }
192
193 hash->here = NIL(Dtlink_t*);
194 hash->type &= ~H_FLATTEN;
195
196 return NIL(Void_t*);
197 }
198 }
199
hlist(Dt_t * dt,Dtlink_t * list,int type)200 static Void_t* hlist(Dt_t* dt, Dtlink_t* list, int type)
201 {
202 Void_t *obj;
203 Dtlink_t *l, *next;
204 Dtdisc_t *disc = dt->disc;
205
206 if(type&DT_FLATTEN)
207 return hflatten(dt, DT_FLATTEN);
208 else if(type&DT_EXTRACT)
209 return hflatten(dt, DT_EXTRACT);
210 else /* if(type&DT_RESTORE) */
211 { dt->data->size = 0;
212 for(l = list; l; l = next)
213 { next = l->_rght;
214 obj = _DTOBJ(disc,l);
215 if((*dt->meth->searchf)(dt, (Void_t*)l, DT_RELINK) == obj)
216 dt->data->size += 1;
217 }
218 return (Void_t*)list;
219 }
220 }
221
hstat(Dt_t * dt,Dtstat_t * st)222 static Void_t* hstat(Dt_t* dt, Dtstat_t* st)
223 {
224 ssize_t n;
225 Dtlink_t **t, **endt, *l;
226 Dthash_t *hash = (Dthash_t*)dt->data;
227
228 if(st)
229 { memset(st, 0, sizeof(Dtstat_t));
230 st->meth = dt->meth->type;
231 st->size = hash->data.size;
232 st->space = sizeof(Dthash_t) + hash->tblz*sizeof(Dtlink_t*) +
233 (dt->disc->link >= 0 ? 0 : hash->data.size*sizeof(Dthold_t));
234
235 for(endt = (t = hash->htbl) + hash->tblz; t < endt; ++t)
236 { for(n = 0, l = *t; l; l = l->_rght)
237 n += 1;
238 st->mlev = n > st->mlev ? n : st->mlev;
239 if(n < DT_MAXSIZE) /* if chain length is small */
240 { st->msize = n > st->msize ? n : st->msize;
241 st->lsize[n] += n;
242 }
243 }
244 }
245
246 return (Void_t*)hash->data.size;
247 }
248
249 #if __STD_C
dthashchain(Dt_t * dt,Void_t * obj,int type)250 static Void_t* dthashchain(Dt_t* dt, Void_t* obj, int type)
251 #else
252 static Void_t* dthashchain(dt,obj,type)
253 Dt_t* dt;
254 Void_t* obj;
255 int type;
256 #endif
257 {
258 Dtlink_t *lnk, *pp, *ll, *p, *l, **tbl;
259 Void_t *key, *k, *o;
260 uint hsh;
261 Dtdisc_t *disc = dt->disc;
262 Dthash_t *hash = (Dthash_t*)dt->data;
263
264 type = DTTYPE(dt,type); /* map type for upward compatibility */
265 if(!(type&DT_OPERATIONS) )
266 return NIL(Void_t*);
267
268 DTSETLOCK(dt);
269
270 if(!hash->htbl && htable(dt) < 0 ) /* initialize hash table */
271 DTRETURN(obj, NIL(Void_t*));
272
273 if(hash->type&H_FLATTEN) /* restore flattened list */
274 hflatten(dt, 0);
275
276 if(type&(DT_FIRST|DT_LAST|DT_CLEAR|DT_EXTRACT|DT_RESTORE|DT_FLATTEN|DT_STAT) )
277 { if(type&(DT_FIRST|DT_LAST) )
278 DTRETURN(obj, hfirst(dt));
279 else if(type&DT_CLEAR)
280 DTRETURN(obj, hclear(dt));
281 else if(type&DT_STAT)
282 DTRETURN(obj, hstat(dt, (Dtstat_t*)obj));
283 else /*if(type&(DT_EXTRACT|DT_RESTORE|DT_FLATTEN))*/
284 DTRETURN(obj, hlist(dt, (Dtlink_t*)obj, type));
285 }
286
287 lnk = hash->here; /* fingered object */
288 hash->here = NIL(Dtlink_t*);
289
290 if(lnk && obj == _DTOBJ(disc,lnk))
291 { if(type&DT_SEARCH)
292 DTRETURN(obj, obj);
293 else if(type&(DT_NEXT|DT_PREV) )
294 DTRETURN(obj, hnext(dt,lnk));
295 }
296
297 if(type&DT_RELINK)
298 { lnk = (Dtlink_t*)obj;
299 obj = _DTOBJ(disc,lnk);
300 key = _DTKEY(disc,obj);
301 }
302 else
303 { lnk = NIL(Dtlink_t*);
304 if((type&DT_MATCH) )
305 { key = obj;
306 obj = NIL(Void_t*);
307 }
308 else key = _DTKEY(disc,obj);
309 }
310 hsh = _DTHSH(dt,key,disc);
311
312 tbl = hash->htbl + (hsh & (hash->tblz-1));
313 pp = ll = NIL(Dtlink_t*);
314 for(p = NIL(Dtlink_t*), l = *tbl; l; p = l, l = l->_rght)
315 { if(hsh == l->_hash)
316 { o = _DTOBJ(disc,l); k = _DTKEY(disc,o);
317 if(_DTCMP(dt, key, k, disc) != 0 )
318 continue;
319 else if((type&(DT_REMOVE|DT_NEXT|DT_PREV)) && o != obj )
320 { if(type&(DT_NEXT|DT_PREV) )
321 { pp = p; ll = l; }
322 continue;
323 }
324 else break;
325 }
326 }
327 if(l) /* found an object, use it */
328 { pp = p; ll = l; }
329
330 if(ll) /* found object */
331 { if(type&(DT_SEARCH|DT_MATCH|DT_ATLEAST|DT_ATMOST) )
332 { hash->here = ll;
333 DTRETURN(obj, _DTOBJ(disc,ll));
334 }
335 else if(type & (DT_NEXT|DT_PREV) )
336 DTRETURN(obj, hnext(dt, ll));
337 else if(type & (DT_DELETE|DT_DETACH|DT_REMOVE) )
338 { hash->data.size -= 1;
339 if(pp)
340 pp->_rght = ll->_rght;
341 else *tbl = ll->_rght;
342 _dtfree(dt, ll, type);
343 DTRETURN(obj, _DTOBJ(disc,ll));
344 }
345 else
346 { /**/DEBUG_ASSERT(type&(DT_INSERT|DT_ATTACH|DT_APPEND|DT_RELINK));
347 if(!(dt->meth->type&DT_BAG) )
348 { if(type&(DT_INSERT|DT_APPEND|DT_ATTACH) )
349 type |= DT_SEARCH; /* for announcement */
350 else if(lnk && (type&DT_RELINK) )
351 _dtfree(dt, lnk, DT_DELETE);
352 DTRETURN(obj, _DTOBJ(disc,ll));
353 }
354 else goto do_insert;
355 }
356 }
357 else /* no matching object */
358 { if(!(type&(DT_INSERT|DT_APPEND|DT_ATTACH|DT_RELINK)) )
359 DTRETURN(obj, NIL(Void_t*));
360
361 do_insert: /* inserting a new object */
362 if(hash->tblz < HLOAD(hash->data.size) )
363 { htable(dt); /* resize table */
364 tbl = hash->htbl + (hsh & (hash->tblz-1));
365 }
366
367 if(!lnk) /* inserting a new object */
368 { if(!(lnk = _dtmake(dt, obj, type)) )
369 DTRETURN(obj, NIL(Void_t*));
370 hash->data.size += 1;
371 }
372
373 lnk->_hash = hsh; /* memoize the hash value */
374 lnk->_rght = *tbl; *tbl = lnk;
375
376 hash->here = lnk;
377 DTRETURN(obj, _DTOBJ(disc,lnk));
378 }
379
380 dt_return:
381 DTANNOUNCE(dt, obj, type);
382 DTCLRLOCK(dt);
383 return obj;
384 }
385
hashevent(Dt_t * dt,int event,Void_t * arg)386 static int hashevent(Dt_t* dt, int event, Void_t* arg)
387 {
388 Dthash_t *hash = (Dthash_t*)dt->data;
389
390 if(event == DT_OPEN)
391 { if(hash)
392 return 0;
393 if(!(hash = (Dthash_t*)(*dt->memoryf)(dt, 0, sizeof(Dthash_t), dt->disc)) )
394 { DTERROR(dt, "Error in allocating a hash table with chaining");
395 return -1;
396 }
397 memset(hash, 0, sizeof(Dthash_t));
398 dt->data = (Dtdata_t*)hash;
399 return 1;
400 }
401 else if(event == DT_CLOSE)
402 { if(!hash)
403 return 0;
404 if(hash->data.size > 0 )
405 (void)hclear(dt);
406 if(hash->htbl)
407 (void)(*dt->memoryf)(dt, hash->htbl, 0, dt->disc);
408 (void)(*dt->memoryf)(dt, hash, 0, dt->disc);
409 dt->data = NIL(Dtdata_t*);
410 return 0;
411 }
412 else return 0;
413 }
414
415 static Dtmethod_t _Dtset = { dthashchain, DT_SET, hashevent, "Dtset" };
416 static Dtmethod_t _Dtbag = { dthashchain, DT_BAG, hashevent, "Dtbag" };
417 __DEFINE__(Dtmethod_t*,Dtset,&_Dtset);
418 __DEFINE__(Dtmethod_t*,Dtbag,&_Dtbag);
419
420 /* backwards compatibility */
421 #undef Dthash
422 #if defined(__EXPORT__)
423 __EXPORT__
424 #endif
425 __DEFINE__(Dtmethod_t*,Dthash,&_Dtset);
426
427 #ifdef NoF
428 NoF(dthashchain)
429 #endif
430