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
36char*
37hashlook(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