1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2007 AT&T Knowledge Ventures * 5 * and is licensed under the * 6 * Common Public License, Version 1.0 * 7 * by AT&T Knowledge Ventures * 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 #pragma prototyped 23 /* 24 * Glenn Fowler 25 * AT&T Research 26 * 27 * hash table library 28 */ 29 30 #include "hashlib.h" 31 32 /* 33 * hash table lookup 34 */ 35 36 char* 37 hashlook(register Hash_table_t* tab, const char* name, long flags, const char* value) 38 { 39 register Hash_bucket_t* b; 40 register unsigned int n; 41 register Hash_last_t* last; 42 Hash_table_t* top; 43 Hash_bucket_t* prev; 44 unsigned int i; 45 46 if ((flags & (HASH_LOOKUP|HASH_INTERNAL)) == (HASH_LOOKUP|HASH_INTERNAL)) 47 { 48 register char* s1; 49 register const char* s2; 50 register int c; 51 52 if (flags & HASH_HASHED) n = *((unsigned int*)value); 53 else 54 { 55 s2 = name; 56 n = 0; 57 while (c = *s2++) HASHPART(n, c); 58 } 59 i = n; 60 for (;;) 61 { 62 HASHMOD(tab, n); 63 for (b = tab->table[n]; b; b = b->next) 64 { 65 s1 = hashname(b); 66 s2 = name; 67 while ((c = *s1++) == *s2++) 68 if (!c) return((flags & HASH_VALUE) ? b->value : (char*)b); 69 } 70 if (!(tab = tab->scope) || (flags & HASH_NOSCOPE)) 71 return(0); 72 n = i; 73 } 74 } 75 tab->root->accesses++; 76 top = tab; 77 last = &tab->root->last; 78 if (name) 79 { 80 last->table = tab; 81 if (flags & (HASH_BUCKET|HASH_INSTALL)) 82 { 83 last->bucket = (Hash_bucket_t*)name; 84 name = hashname(last->bucket); 85 } 86 else last->bucket = 0; 87 last->name = name; 88 if (flags & HASH_BUCKET) n = last->bucket->hash; 89 else if (tab->flags & HASH_HASHED) 90 { 91 n = (unsigned int)integralof(name); 92 if (!(flags & HASH_HASHED)) n >>= 3; 93 } 94 else if (flags & HASH_HASHED) n = *((unsigned int*)value); 95 else HASH(tab->root, name, n); 96 last->hash = i = HASHVAL(n); 97 for (;;) 98 { 99 HASHMOD(tab, n); 100 for (prev = 0, b = tab->table[n]; b; prev = b, b = b->next) 101 { 102 if (i == HASHVAL(b->hash) && ((b->hash & (HASH_DELETED|HASH_OPAQUED)) != HASH_DELETED || (flags & (HASH_CREATE|HASH_DELETE|HASH_INSTALL|HASH_RENAME)))) 103 { 104 if (!tab->root->local->compare) 105 { 106 register char* s1 = hashname(b); 107 register const char* s2 = name; 108 109 if (tab->root->namesize) 110 { 111 register char* s3 = s1 + tab->root->namesize; 112 113 while (*s1++ == *s2++) 114 if (s1 >= s3) goto found; 115 } 116 else while (*s1 == *s2++) 117 if (!*s1++) goto found; 118 } 119 else if (tab->root->namesize) 120 { 121 if (!(*tab->root->local->compare)(hashname(b), name, tab->root->namesize)) goto found; 122 } 123 else if (!(*tab->root->local->compare)(hashname(b), name)) goto found; 124 } 125 tab->root->collisions++; 126 } 127 if (!tab->scope || (flags & (HASH_CREATE|HASH_INSTALL|HASH_NOSCOPE)) == HASH_NOSCOPE) break; 128 tab = tab->scope; 129 n = i; 130 } 131 } 132 else 133 { 134 tab = last->table; 135 name = last->name; 136 n = i = last->hash; 137 prev = 0; 138 HASHMOD(tab, n); 139 if (b = last->bucket) 140 { 141 /* 142 * found the bucket 143 */ 144 145 found: 146 if (prev && !tab->frozen) 147 { 148 /* 149 * migrate popular buckets to the front 150 */ 151 152 prev->next = b->next; 153 b->next = tab->table[n]; 154 tab->table[n] = b; 155 } 156 switch (flags & (HASH_CREATE|HASH_DELETE|HASH_INSTALL|HASH_RENAME)) 157 { 158 case HASH_CREATE: 159 case HASH_CREATE|HASH_INSTALL: 160 case HASH_INSTALL: 161 if (tab != top && !(flags & HASH_SCOPE)) break; 162 if (flags & HASH_OPAQUE) b->hash |= HASH_OPAQUED; 163 goto exists; 164 165 case HASH_DELETE: 166 value = 0; 167 if (tab == top || (flags & HASH_SCOPE)) 168 { 169 if (flags & HASH_OPAQUE) b->hash &= ~HASH_OPAQUED; 170 else if (!(tab->root->flags & HASH_BUCKET)) 171 { 172 if (tab->root->local->free && b->value) 173 { 174 (*tab->root->local->free)(b->value); 175 b->value = 0; 176 } 177 else if (tab->flags & HASH_VALUE) 178 { 179 value = b->value; 180 b->value = 0; 181 } 182 } 183 tab->buckets--; 184 if (tab->frozen || (b->hash & HASH_OPAQUED)) b->hash |= HASH_DELETED; 185 else 186 { 187 tab->table[n] = b->next; 188 name = (b->hash & HASH_FREENAME) ? (char*)b->name : (char*)0; 189 if (tab->root->local->free && (tab->root->flags & HASH_BUCKET)) (*tab->root->local->free)((char*)b); 190 else if (!(b->hash & HASH_KEEP)) 191 { 192 if (tab->root->local->region) (*tab->root->local->region)(tab->root->local->handle, b, 0, 0); 193 else free(b); 194 } 195 if (name) 196 { 197 if (tab->root->local->region) (*tab->root->local->region)(tab->root->local->handle, (char*)name, 0, 0); 198 else free((char*)name); 199 } 200 } 201 } 202 return((char*)value); 203 204 case HASH_RENAME: 205 if (tab != top || tab->frozen || (b->hash & (HASH_KEEP|HASH_OPAQUED)) || hashlook(top, value, (flags&(HASH_HASHED|HASH_INTERNAL))|HASH_LOOKUP, NiL)) 206 return(0); 207 name = (char*)b->name; 208 if (!(tab->flags & HASH_ALLOCATE)) b->name = (char*)value; 209 else if (b->name && tab->root->namesize) 210 { 211 memcpy(b->name, value, tab->root->namesize); 212 name = 0; 213 } 214 else 215 { 216 int m; 217 char* t; 218 219 if (!(i = tab->bucketsize)) 220 i = (sizeof(Hash_bucket_t) + sizeof(char*) - 1) / sizeof(char*); 221 i *= sizeof(char*); 222 if (b->name == ((char*)b + i) && strlen(b->name) <= (m = strlen(value))) 223 { 224 strcpy(b->name, value); 225 name = 0; 226 } 227 else 228 { 229 m++; 230 if (!(t = tab->root->local->region ? (char*)(*tab->root->local->region)(tab->root->local->handle, NiL, m, 0) : (char*)malloc(m))) 231 return(0); 232 b->name = strcpy(t, value); 233 } 234 } 235 if (name && (b->hash & HASH_FREENAME)) 236 { 237 b->hash &= ~HASH_FREENAME; 238 if (tab->root->local->region) (*tab->root->local->region)(tab->root->local->handle, (char*)name, 0, 0); 239 else free((char*)name); 240 } 241 tab->buckets--; 242 tab->table[n] = b->next; 243 flags = HASH_CREATE|HASH_INSTALL; 244 last->bucket = b; 245 i = last->hash; 246 goto create; 247 248 default: 249 if (!(b->hash & HASH_DELETED)) goto exists; 250 return(0); 251 } 252 } 253 } 254 if (!(flags & (HASH_CREATE|HASH_INSTALL))) return(0); 255 256 /* 257 * create a new bucket 258 */ 259 260 create: 261 if (tab == top) prev = 0; 262 else 263 { 264 if (prev = b) 265 { 266 name = (b->hash & HASH_HIDES) ? b->name : (char*)b; 267 i |= HASH_HIDES; 268 } 269 if (!(flags & HASH_SCOPE)) tab = top; 270 } 271 272 /* 273 * check for table expansion 274 */ 275 276 if (!tab->frozen && !(tab->flags & HASH_FIXED) && tab->buckets > tab->root->meanchain * tab->size) 277 hashsize(tab, tab->size << 1); 278 if (flags & HASH_INSTALL) 279 { 280 b = last->bucket; 281 i |= HASH_KEEP; 282 } 283 else 284 { 285 int m = tab->bucketsize * sizeof(char*); 286 287 if (flags & HASH_VALUE) 288 { 289 tab->flags |= HASH_VALUE; 290 if (m < sizeof(Hash_bucket_t)) 291 { 292 tab->bucketsize = (sizeof(Hash_bucket_t) + sizeof(char*) - 1) / sizeof(char*); 293 m = tab->bucketsize * sizeof(char*); 294 } 295 n = m; 296 } 297 else if (!(n = HASH_SIZEOF(flags))) 298 { 299 if (!(flags & HASH_FIXED)) n = m; 300 else if ((n = (int)integralof(value)) < m) n = m; 301 } 302 else if (n < m) n = m; 303 if (!prev && (tab->flags & HASH_ALLOCATE)) 304 { 305 m = tab->root->namesize ? tab->root->namesize : strlen(name) + 1; 306 if (tab->root->local->region) 307 { 308 if (!(b = (Hash_bucket_t*)(*tab->root->local->region)(tab->root->local->handle, NiL, n + m, 0))) 309 return(0); 310 memset(b, 0, n + m); 311 } 312 else if (!(b = newof(0, Hash_bucket_t, 0, n + m))) 313 return(0); 314 b->name = (char*)b + n; 315 memcpy(b->name, name, m); 316 } 317 else 318 { 319 if (tab->root->local->region) 320 { 321 if (!(b = (Hash_bucket_t*)(*tab->root->local->region)(tab->root->local->handle, NiL, n, 0))) 322 return(0); 323 memset(b, 0, n); 324 } 325 else if (!(b = newof(0, Hash_bucket_t, 0, n))) 326 return(0); 327 b->name = (char*)name; 328 } 329 } 330 b->hash = n = i; 331 HASHMOD(tab, n); 332 b->next = tab->table[n]; 333 tab->table[n] = b; 334 tab->buckets++; 335 if (flags & HASH_OPAQUE) 336 { 337 tab->buckets--; 338 b->hash |= HASH_DELETED|HASH_OPAQUED; 339 return(0); 340 } 341 342 /* 343 * finally got the bucket 344 */ 345 346 exists: 347 if (b->hash & HASH_DELETED) 348 { 349 b->hash &= ~HASH_DELETED; 350 tab->buckets++; 351 } 352 last->bucket = b; 353 last->table = tab; 354 switch (flags & (HASH_CREATE|HASH_VALUE)) 355 { 356 case HASH_CREATE|HASH_VALUE: 357 if (tab->root->local->free && !(tab->root->flags & HASH_BUCKET) && b->value) (*tab->root->local->free)(b->value); 358 if (value && tab->root->local->alloc) value = (*tab->root->local->alloc)((unsigned int)integralof(value)); 359 b->value = (char*)value; 360 return((char*)hashname(b)); 361 case HASH_VALUE: 362 return(b->value); 363 default: 364 return((char*)b); 365 } 366 } 367