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 sequential scan
34  *
35  *	Hash_position_t*	pos;
36  *	Hash_bucket_t*		b;
37  *	pos = hashscan(tab, flags);
38  *	while (b = hashnext(&pos)) ...;
39  *	hashdone(pos);
40  */
41 
42 /*
43  * return pos for scan on table
44  */
45 
46 Hash_position_t*
hashscan(register Hash_table_t * tab,register int flags)47 hashscan(register Hash_table_t* tab, register int flags)
48 {
49 	register Hash_position_t*	pos;
50 
51 	static Hash_bucket_t		empty;
52 
53 	if (!(pos = newof(0, Hash_position_t, 1, 0))) return(0);
54 	pos->tab = tab->root->last.table = tab;
55 	pos->bucket = &empty;
56 	pos->slot = tab->table - 1;
57 	pos->limit = tab->table + tab->size;
58 	if (tab->scope && !(flags & HASH_NOSCOPE))
59 	{
60 		pos->flags = HASH_SCOPE;
61 		do
62 		{
63 			register Hash_bucket_t*	b;
64 
65 			if (tab->frozen)
66 			{
67 				register Hash_bucket_t**	sp = tab->table;
68 				register Hash_bucket_t**	sx = tab->table + tab->size;
69 
70 				while (sp < sx)
71 					for (b = *sp++; b; b = b->next)
72 						b->hash &= ~HASH_HIDDEN;
73 			}
74 		} while (tab = tab->scope);
75 		tab = pos->tab;
76 	}
77 	else pos->flags = 0;
78 	tab->frozen++;
79 	return(pos);
80 }
81 
82 /*
83  * return next scan element
84  */
85 
86 Hash_bucket_t*
hashnext(register Hash_position_t * pos)87 hashnext(register Hash_position_t* pos)
88 {
89 	register Hash_bucket_t*	b;
90 
91 	if (!pos) return(0);
92 	b = pos->bucket;
93 	for (;;)
94 	{
95 		if (!(b = b->next))
96 		{
97 			do
98 			{
99 				if (++pos->slot >= pos->limit)
100 				{
101 					pos->tab->frozen--;
102 					if (!pos->flags || !pos->tab->scope) return(0);
103 					pos->tab = pos->tab->scope;
104 					pos->tab->root->last.table = pos->tab;
105 					pos->limit = (pos->slot = pos->tab->table) + pos->tab->size;
106 					pos->tab->frozen++;
107 				}
108 			} while (!(b = *pos->slot));
109 		}
110 		if (!(b->hash & HASH_DELETED) && (!(pos->tab->flags & HASH_VALUE) || b->value) && (!pos->flags || !(b->hash & (HASH_HIDDEN|HASH_HIDES)))) break;
111 		if (b->hash & HASH_HIDES)
112 		{
113 			register Hash_bucket_t*	h = (Hash_bucket_t*)b->name;
114 
115 			if (!(h->hash & HASH_HIDDEN))
116 			{
117 				h->hash |= HASH_HIDDEN;
118 				if (!(b->hash & HASH_DELETED)) break;
119 			}
120 		}
121 		else b->hash &= ~HASH_HIDDEN;
122 	}
123 	return(pos->tab->root->last.bucket = pos->bucket = b);
124 }
125 
126 /*
127  * terminate scan
128  */
129 
130 void
hashdone(register Hash_position_t * pos)131 hashdone(register Hash_position_t* pos)
132 {
133 	if (pos)
134 	{
135 		if (pos->tab->frozen)
136 			pos->tab->frozen--;
137 		free(pos);
138 	}
139 }
140