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