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 #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 m = strlen(value); 223 if (b->name == ((char*)b + i) && strlen(b->name) <= m) 224 { 225 strcpy(b->name, value); 226 name = 0; 227 } 228 else 229 { 230 m++; 231 if (!(t = tab->root->local->region ? (char*)(*tab->root->local->region)(tab->root->local->handle, NiL, m, 0) : (char*)malloc(m))) 232 return(0); 233 b->name = strcpy(t, value); 234 } 235 } 236 if (name && (b->hash & HASH_FREENAME)) 237 { 238 b->hash &= ~HASH_FREENAME; 239 if (tab->root->local->region) (*tab->root->local->region)(tab->root->local->handle, (char*)name, 0, 0); 240 else free((char*)name); 241 } 242 tab->buckets--; 243 tab->table[n] = b->next; 244 flags = HASH_CREATE|HASH_INSTALL; 245 last->bucket = b; 246 i = last->hash; 247 goto create; 248 249 default: 250 if (!(b->hash & HASH_DELETED)) goto exists; 251 return(0); 252 } 253 } 254 } 255 if (!(flags & (HASH_CREATE|HASH_INSTALL))) return(0); 256 257 /* 258 * create a new bucket 259 */ 260 261 create: 262 if (tab == top) prev = 0; 263 else 264 { 265 if (prev = b) 266 { 267 name = (b->hash & HASH_HIDES) ? b->name : (char*)b; 268 i |= HASH_HIDES; 269 } 270 if (!(flags & HASH_SCOPE)) tab = top; 271 } 272 273 /* 274 * check for table expansion 275 */ 276 277 if (!tab->frozen && !(tab->flags & HASH_FIXED) && tab->buckets > tab->root->meanchain * tab->size) 278 hashsize(tab, tab->size << 1); 279 if (flags & HASH_INSTALL) 280 { 281 b = last->bucket; 282 i |= HASH_KEEP; 283 } 284 else 285 { 286 int m = tab->bucketsize * sizeof(char*); 287 288 if (flags & HASH_VALUE) 289 { 290 tab->flags |= HASH_VALUE; 291 if (m < sizeof(Hash_bucket_t)) 292 { 293 tab->bucketsize = (sizeof(Hash_bucket_t) + sizeof(char*) - 1) / sizeof(char*); 294 m = tab->bucketsize * sizeof(char*); 295 } 296 n = m; 297 } 298 else if (!(n = HASH_SIZEOF(flags))) 299 { 300 if (!(flags & HASH_FIXED)) n = m; 301 else if ((n = (int)integralof(value)) < m) n = m; 302 } 303 else if (n < m) n = m; 304 if (!prev && (tab->flags & HASH_ALLOCATE)) 305 { 306 m = tab->root->namesize ? tab->root->namesize : strlen(name) + 1; 307 if (tab->root->local->region) 308 { 309 if (!(b = (Hash_bucket_t*)(*tab->root->local->region)(tab->root->local->handle, NiL, n + m, 0))) 310 return(0); 311 memset(b, 0, n + m); 312 } 313 else if (!(b = newof(0, Hash_bucket_t, 0, n + m))) 314 return(0); 315 b->name = (char*)b + n; 316 memcpy(b->name, name, m); 317 } 318 else 319 { 320 if (tab->root->local->region) 321 { 322 if (!(b = (Hash_bucket_t*)(*tab->root->local->region)(tab->root->local->handle, NiL, n, 0))) 323 return(0); 324 memset(b, 0, n); 325 } 326 else if (!(b = newof(0, Hash_bucket_t, 0, n))) 327 return(0); 328 b->name = (char*)name; 329 } 330 } 331 b->hash = n = i; 332 HASHMOD(tab, n); 333 b->next = tab->table[n]; 334 tab->table[n] = b; 335 tab->buckets++; 336 if (flags & HASH_OPAQUE) 337 { 338 tab->buckets--; 339 b->hash |= HASH_DELETED|HASH_OPAQUED; 340 return(0); 341 } 342 343 /* 344 * finally got the bucket 345 */ 346 347 exists: 348 if (b->hash & HASH_DELETED) 349 { 350 b->hash &= ~HASH_DELETED; 351 tab->buckets++; 352 } 353 last->bucket = b; 354 last->table = tab; 355 switch (flags & (HASH_CREATE|HASH_VALUE)) 356 { 357 case HASH_CREATE|HASH_VALUE: 358 if (tab->root->local->free && !(tab->root->flags & HASH_BUCKET) && b->value) (*tab->root->local->free)(b->value); 359 if (value && tab->root->local->alloc) value = (*tab->root->local->alloc)((unsigned int)integralof(value)); 360 b->value = (char*)value; 361 return((char*)hashname(b)); 362 case HASH_VALUE: 363 return(b->value); 364 default: 365 return((char*)b); 366 } 367 } 368