1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1985-2010 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*
hashlook(register Hash_table_t * tab,const char * name,long flags,const char * value)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