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