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 */ 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 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 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 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 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 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 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 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 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