1 /***********************************************************************
2 *                                                                      *
3 *               This software is part of the ast package               *
4 *          Copyright (c) 1985-2011 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 #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