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