|
Graphviz 2.29.20120208.0545
|
00001 #include "dthdr.h" 00002 00003 /* Hash table. 00004 ** dt: dictionary 00005 ** obj: what to look for 00006 ** type: type of search 00007 ** 00008 ** Written by Kiem-Phong Vo (05/25/96) 00009 */ 00010 00011 /* resize the hash table */ 00012 #if __STD_C 00013 static void dthtab(Dt_t* dt) 00014 #else 00015 static void dthtab(dt) 00016 Dt_t* dt; 00017 #endif 00018 { 00019 reg Dtlink_t *t, *r, *p, **s, **hs, **is, **olds; 00020 int n, k; 00021 00022 if(dt->data->minp > 0 && dt->data->ntab > 0) /* fixed table size */ 00023 return; 00024 dt->data->minp = 0; 00025 00026 n = dt->data->ntab; 00027 if(dt->disc && dt->disc->eventf && 00028 (*dt->disc->eventf)(dt, DT_HASHSIZE, &n, dt->disc) > 0 ) 00029 { if(n < 0) /* fix table size */ 00030 { dt->data->minp = 1; 00031 if(dt->data->ntab > 0 ) 00032 return; 00033 } 00034 else /* set a particular size */ 00035 { for(k = 2; k < n; k *= 2) 00036 ; 00037 n = k; 00038 } 00039 } 00040 else n = 0; 00041 00042 /* compute new table size */ 00043 if(n <= 0) 00044 { if((n = dt->data->ntab) == 0) 00045 n = HSLOT; 00046 while(dt->data->size > HLOAD(n)) 00047 n = HRESIZE(n); 00048 } 00049 if(n == dt->data->ntab) 00050 return; 00051 00052 /* allocate new table */ 00053 olds = dt->data->ntab == 0 ? NIL(Dtlink_t**) : dt->data->htab; 00054 if(!(s = (Dtlink_t**)(*dt->memoryf)(dt,olds,n*sizeof(Dtlink_t*),dt->disc)) ) 00055 return; 00056 olds = s + dt->data->ntab; 00057 dt->data->htab = s; 00058 dt->data->ntab = n; 00059 00060 /* rehash elements */ 00061 for(hs = s+n-1; hs >= olds; --hs) 00062 *hs = NIL(Dtlink_t*); 00063 for(hs = s; hs < olds; ++hs) 00064 { for(p = NIL(Dtlink_t*), t = *hs; t; t = r) 00065 { r = t->right; 00066 if((is = s + HINDEX(n,t->hash)) == hs) 00067 p = t; 00068 else /* move to a new chain */ 00069 { if(p) 00070 p->right = r; 00071 else *hs = r; 00072 t->right = *is; *is = t; 00073 } 00074 } 00075 } 00076 } 00077 00078 #if __STD_C 00079 static Void_t* dthash(Dt_t* dt, reg Void_t* obj, int type) 00080 #else 00081 static Void_t* dthash(dt,obj,type) 00082 Dt_t* dt; 00083 reg Void_t* obj; 00084 int type; 00085 #endif 00086 { 00087 reg Dtlink_t *t, *r, *p; 00088 reg Void_t *k, *key; 00089 reg uint hsh; 00090 reg int lk, sz, ky; 00091 reg Dtcompar_f cmpf; 00092 reg Dtdisc_t* disc; 00093 reg Dtlink_t **s, **ends; 00094 00095 UNFLATTEN(dt); 00096 00097 /* initialize discipline data */ 00098 disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf); 00099 dt->type &= ~DT_FOUND; 00100 00101 if(!obj) 00102 { if(type&(DT_NEXT|DT_PREV)) 00103 goto end_walk; 00104 00105 if(dt->data->size <= 0 || !(type&(DT_CLEAR|DT_FIRST|DT_LAST)) ) 00106 return NIL(Void_t*); 00107 00108 ends = (s = dt->data->htab) + dt->data->ntab; 00109 if(type&DT_CLEAR) 00110 { /* clean out all objects */ 00111 for(; s < ends; ++s) 00112 { t = *s; 00113 *s = NIL(Dtlink_t*); 00114 if(!disc->freef && disc->link >= 0) 00115 continue; 00116 while(t) 00117 { r = t->right; 00118 if(disc->freef) 00119 (*disc->freef)(dt,_DTOBJ(t,lk),disc); 00120 if(disc->link < 0) 00121 (*dt->memoryf)(dt,(Void_t*)t,0,disc); 00122 t = r; 00123 } 00124 } 00125 dt->data->here = NIL(Dtlink_t*); 00126 dt->data->size = 0; 00127 dt->data->loop = 0; 00128 return NIL(Void_t*); 00129 } 00130 else /* computing the first/last object */ 00131 { t = NIL(Dtlink_t*); 00132 while(s < ends && !t ) 00133 t = (type&DT_LAST) ? *--ends : *s++; 00134 if(t && (type&DT_LAST)) 00135 for(; t->right; t = t->right) 00136 ; 00137 00138 dt->data->loop += 1; 00139 dt->data->here = t; 00140 return t ? _DTOBJ(t,lk) : NIL(Void_t*); 00141 } 00142 } 00143 00144 /* allow apps to delete an object "actually" in the dictionary */ 00145 if(dt->meth->type == DT_BAG && (type&(DT_DELETE|DT_DETACH)) ) 00146 { if(!dtsearch(dt,obj) ) 00147 return NIL(Void_t*); 00148 00149 s = dt->data->htab + HINDEX(dt->data->ntab,dt->data->here->hash); 00150 r = NIL(Dtlink_t*); 00151 for(p = NIL(Dtlink_t*), t = *s; t; p = t, t = t->right) 00152 { if(_DTOBJ(t,lk) == obj) /* delete this specific object */ 00153 goto do_delete; 00154 if(t == dt->data->here) 00155 r = p; 00156 } 00157 00158 /* delete some matching object */ 00159 p = r; t = dt->data->here; 00160 goto do_delete; 00161 } 00162 00163 if(type&(DT_MATCH|DT_SEARCH|DT_INSERT|DT_ATTACH) ) 00164 { key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz); 00165 hsh = _DTHSH(dt,key,disc,sz); 00166 goto do_search; 00167 } 00168 else if(type&(DT_RENEW|DT_VSEARCH) ) 00169 { r = (Dtlink_t*)obj; 00170 obj = _DTOBJ(r,lk); 00171 key = _DTKEY(obj,ky,sz); 00172 hsh = r->hash; 00173 goto do_search; 00174 } 00175 else /*if(type&(DT_DELETE|DT_DETACH|DT_NEXT|DT_PREV))*/ 00176 { if((t = dt->data->here) && _DTOBJ(t,lk) == obj) 00177 { hsh = t->hash; 00178 s = dt->data->htab + HINDEX(dt->data->ntab,hsh); 00179 p = NIL(Dtlink_t*); 00180 } 00181 else 00182 { key = _DTKEY(obj,ky,sz); 00183 hsh = _DTHSH(dt,key,disc,sz); 00184 do_search: 00185 t = dt->data->ntab <= 0 ? NIL(Dtlink_t*) : 00186 *(s = dt->data->htab + HINDEX(dt->data->ntab,hsh)); 00187 for(p = NIL(Dtlink_t*); t; p = t, t = t->right) 00188 { if(hsh == t->hash) 00189 { k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz); 00190 if(_DTCMP(dt,key,k,disc,cmpf,sz) == 0) 00191 break; 00192 } 00193 } 00194 } 00195 } 00196 00197 if(t) /* found matching object */ 00198 dt->type |= DT_FOUND; 00199 00200 if(type&(DT_MATCH|DT_SEARCH|DT_VSEARCH)) 00201 { if(!t) 00202 return NIL(Void_t*); 00203 if(p && (dt->data->type&DT_SET) && dt->data->loop <= 0) 00204 { /* move-to-front heuristic */ 00205 p->right = t->right; 00206 t->right = *s; 00207 *s = t; 00208 } 00209 dt->data->here = t; 00210 return _DTOBJ(t,lk); 00211 } 00212 else if(type&(DT_INSERT|DT_ATTACH)) 00213 { if(t && (dt->data->type&DT_SET) ) 00214 { dt->data->here = t; 00215 return _DTOBJ(t,lk); 00216 } 00217 00218 if(disc->makef && (type&DT_INSERT) && 00219 !(obj = (*disc->makef)(dt,obj,disc)) ) 00220 return NIL(Void_t*); 00221 if(lk >= 0) 00222 r = _DTLNK(obj,lk); 00223 else 00224 { r = (Dtlink_t*)(*dt->memoryf) 00225 (dt,NIL(Void_t*),sizeof(Dthold_t),disc); 00226 if(r) 00227 ((Dthold_t*)r)->obj = obj; 00228 else 00229 { if(disc->makef && disc->freef && (type&DT_INSERT)) 00230 (*disc->freef)(dt,obj,disc); 00231 return NIL(Void_t*); 00232 } 00233 } 00234 r->hash = hsh; 00235 00236 /* insert object */ 00237 do_insert: 00238 if((dt->data->size += 1) > HLOAD(dt->data->ntab) && dt->data->loop <= 0 ) 00239 dthtab(dt); 00240 if(dt->data->ntab == 0) 00241 { dt->data->size -= 1; 00242 if(disc->freef && (type&DT_INSERT)) 00243 (*disc->freef)(dt,obj,disc); 00244 if(disc->link < 0) 00245 (*disc->memoryf)(dt,(Void_t*)r,0,disc); 00246 return NIL(Void_t*); 00247 } 00248 s = dt->data->htab + HINDEX(dt->data->ntab,hsh); 00249 if(t) 00250 { r->right = t->right; 00251 t->right = r; 00252 } 00253 else 00254 { r->right = *s; 00255 *s = r; 00256 } 00257 dt->data->here = r; 00258 return obj; 00259 } 00260 else if(type&DT_NEXT) 00261 { if(t && !(p = t->right) ) 00262 { for(ends = dt->data->htab+dt->data->ntab, s += 1; s < ends; ++s) 00263 if((p = *s) ) 00264 break; 00265 } 00266 goto done_adj; 00267 } 00268 else if(type&DT_PREV) 00269 { if(t && !p) 00270 { if((p = *s) != t) 00271 { while(p->right != t) 00272 p = p->right; 00273 } 00274 else 00275 { p = NIL(Dtlink_t*); 00276 for(s -= 1, ends = dt->data->htab; s >= ends; --s) 00277 { if((p = *s) ) 00278 { while(p->right) 00279 p = p->right; 00280 break; 00281 } 00282 } 00283 } 00284 } 00285 done_adj: 00286 if(!(dt->data->here = p) ) 00287 { end_walk: 00288 if((dt->data->loop -= 1) < 0) 00289 dt->data->loop = 0; 00290 if(dt->data->size > HLOAD(dt->data->ntab) && dt->data->loop <= 0) 00291 dthtab(dt); 00292 return NIL(Void_t*); 00293 } 00294 else 00295 { dt->data->type |= DT_WALK; 00296 return _DTOBJ(p,lk); 00297 } 00298 } 00299 else if(type&DT_RENEW) 00300 { if(!t || (dt->data->type&DT_BAG) ) 00301 goto do_insert; 00302 else 00303 { if(disc->freef) 00304 (*disc->freef)(dt,obj,disc); 00305 if(disc->link < 0) 00306 (*dt->memoryf)(dt,(Void_t*)r,0,disc); 00307 return t ? _DTOBJ(t,lk) : NIL(Void_t*); 00308 } 00309 } 00310 else /*if(type&(DT_DELETE|DT_DETACH))*/ 00311 { /* take an element out of the dictionary */ 00312 do_delete: 00313 if(!t) 00314 return NIL(Void_t*); 00315 else if(p) 00316 p->right = t->right; 00317 else if((p = *s) == t) 00318 p = *s = t->right; 00319 else 00320 { while(p->right != t) 00321 p = p->right; 00322 p->right = t->right; 00323 } 00324 obj = _DTOBJ(t,lk); 00325 dt->data->size -= 1; 00326 dt->data->here = p; 00327 if(disc->freef && (type&DT_DELETE)) 00328 (*disc->freef)(dt,obj,disc); 00329 if(disc->link < 0) 00330 (*dt->memoryf)(dt,(Void_t*)t,0,disc); 00331 return obj; 00332 } 00333 } 00334 00335 static Dtmethod_t _Dtset = { dthash, DT_SET }; 00336 static Dtmethod_t _Dtbag = { dthash, DT_BAG }; 00337 __DEFINE__(Dtmethod_t*,Dtset,&_Dtset); 00338 __DEFINE__(Dtmethod_t*,Dtbag,&_Dtbag); 00339 00340 #ifndef KPVDEL /* for backward compatibility - remove next time */ 00341 Dtmethod_t _Dthash = { dthash, DT_SET }; 00342 __DEFINE__(Dtmethod_t*,Dthash,&_Dthash); 00343 #endif 00344 00345 #ifdef NoF 00346 NoF(dthash) 00347 #endif
1.7.4