1 /***********************************************************************
2 *                                                                      *
3 *               This software is part of the ast package               *
4 *          Copyright (c) 1985-2012 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 <glenn.s.fowler@gmail.com>                *
18 *                    David Korn <dgkorn@gmail.com>                     *
19 *                     Phong Vo <phongvo@gmail.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 = 0;
57 	if (tab->scope && !(flags & HASH_NOSCOPE))
58 	{
59 		pos->flags = HASH_SCOPE;
60 		do
61 		{
62 			register Hash_bucket_t*	b;
63 
64 			if (tab->frozen)
65 			{
66 				register Hash_bucket_t**	sp = tab->table;
67 				register Hash_bucket_t**	sx = tab->table + tab->size;
68 
69 				while (sp < sx)
70 					for (b = *sp++; b; b = b->next)
71 						b->hash &= ~HASH_HIDDEN;
72 			}
73 		} while (tab = tab->scope);
74 		tab = pos->tab;
75 	}
76 	else pos->flags = 0;
77 	tab->frozen++;
78 	return(pos);
79 }
80 
81 /*
82  * return next scan element
83  */
84 
85 Hash_bucket_t*
hashnext(register Hash_position_t * pos)86 hashnext(register Hash_position_t* pos)
87 {
88 	register Hash_bucket_t*	b;
89 
90 	if (!pos) return(0);
91 	b = pos->bucket;
92 	for (;;)
93 	{
94 		if (!(b = b->next))
95 		{
96 			do
97 			{
98 				if (pos->slot >= pos->tab->size)
99 				{
100 					pos->tab->frozen--;
101 					if (!pos->flags || !pos->tab->scope) return(0);
102 					pos->tab = pos->tab->scope;
103 					pos->tab->root->last.table = pos->tab;
104 					pos->slot = 0;
105 					pos->tab->frozen++;
106 				}
107 			} while (!(b = pos->tab->table[pos->slot++]));
108 		}
109 		if (!(b->hash & HASH_DELETED) && (!(pos->tab->flags & HASH_VALUE) || b->value) && (!pos->flags || !(b->hash & (HASH_HIDDEN|HASH_HIDES)))) break;
110 		if (b->hash & HASH_HIDES)
111 		{
112 			register Hash_bucket_t*	h = (Hash_bucket_t*)b->name;
113 
114 			if (!(h->hash & HASH_HIDDEN))
115 			{
116 				h->hash |= HASH_HIDDEN;
117 				if (!(b->hash & HASH_DELETED)) break;
118 			}
119 		}
120 		else b->hash &= ~HASH_HIDDEN;
121 	}
122 	return(pos->tab->root->last.bucket = pos->bucket = b);
123 }
124 
125 /*
126  * terminate scan
127  */
128 
129 void
hashdone(register Hash_position_t * pos)130 hashdone(register Hash_position_t* pos)
131 {
132 	if (pos)
133 	{
134 		if (pos->tab->frozen)
135 			pos->tab->frozen--;
136 		free(pos);
137 	}
138 }
139