Graphviz  2.41.20170921.2350
dthash.c
Go to the documentation of this file.
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 */
12 static 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 
73 static 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 
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 
323 static Dtmethod_t _Dtset = { dthash, DT_SET };
324 static Dtmethod_t _Dtbag = { dthash, DT_BAG };
325 Dtmethod_t* Dtset = &_Dtset;
326 Dtmethod_t* Dtbag = &_Dtbag;
327 
328 #ifndef KPVDEL /* for backward compatibility - remove next time */
329 Dtmethod_t _Dthash = { dthash, DT_SET };
331 #endif
332 
333 #ifdef NoF
334 NoF(dthash)
335 #endif
Dtdisc_t * disc
Definition: cdt.h:101
#define uint
Definition: dthdr.h:15
int(* Dtcompar_f)(Dt_t *, void *, void *, Dtdisc_t *)
Definition: cdt.h:40
#define DT_CLEAR
Definition: cdt.h:146
#define DT_HASHSIZE
Definition: cdt.h:162
int type
Definition: cdt.h:105
#define DT_FIRST
Definition: cdt.h:147
int type
Definition: cdt.h:61
#define reg
Definition: dthdr.h:14
CDT_API Dtmethod_t * Dtbag
Definition: cdt.h:165
#define HLOAD(s)
Definition: dthdr.h:35
Dtevent_f eventf
Definition: cdt.h:89
#define HSLOT
Definition: dthdr.h:33
Definition: cdt.h:80
#define DT_SET
Definition: cdt.h:125
#define DT_SEARCH
Definition: cdt.h:142
#define DT_BAG
Definition: cdt.h:126
#define DT_DETACH
Definition: cdt.h:152
#define DT_PREV
Definition: cdt.h:144
#define htab
Definition: dthdr.h:18
#define DT_FOUND
Definition: cdt.h:122
Definition: cdt.h:53
#define HINDEX(n, h)
Definition: dthdr.h:36
int size
Definition: cdt.h:73
#define NIL(t)
Definition: dthdr.h:13
#define _DTHSH(dt, ky, dc, sz)
Definition: cdt.h:214
#define DT_NEXT
Definition: cdt.h:143
#define dtsearch(d, o)
Definition: cdt.h:260
CDT_API Dtmethod_t _Dthash
Definition: cdt.h:179
CDT_API Dtmethod_t * Dtset
Definition: cdt.h:164
#define _DTDSC(dc, ky, sz, lk, cmpf)
Definition: cdt.h:205
#define _DTLNK(o, lk)
Definition: cdt.h:207
#define DT_ATTACH
Definition: cdt.h:151
#define DT_DELETE
Definition: cdt.h:141
#define _DTCMP(dt, k1, k2, dc, cmpf, sz)
Definition: cdt.h:211
Definition: grammar.c:79
struct _dthold_s Dthold_t
Definition: cdt.h:29
#define NULL
Definition: logic.h:39
#define DT_VSEARCH
Definition: cdt.h:150
#define UNFLATTEN(dt)
Definition: dthdr.h:38
#define DT_MATCH
Definition: cdt.h:149
Dtlink_t * here
Definition: cdt.h:67
CDT_API Dtmethod_t * Dthash
Definition: cdt.h:177
#define DT_INSERT
Definition: cdt.h:140
#define DT_WALK
Definition: dthdr.h:23
Dtmethod_t * meth
Definition: cdt.h:104
#define DT_LAST
Definition: cdt.h:148
int ntab
Definition: cdt.h:72
Definition: cdt.h:99
int minp
Definition: cdt.h:75
Dtdata_t * data
Definition: cdt.h:102
#define _DTKEY(o, ky, sz)
Definition: cdt.h:209
int type
Definition: cdt.h:66
int loop
Definition: cdt.h:74
#define _DTOBJ(e, lk)
Definition: cdt.h:208
#define HRESIZE(n)
Definition: dthdr.h:34
Dtmemory_f memoryf
Definition: cdt.h:103
Definition: legal.c:60
#define DT_RENEW
Definition: cdt.h:145