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*                  Common Public License, Version 1.0                  *
7*                    by AT&T Intellectual Property                     *
8*                                                                      *
9*                A copy of the License is available at                 *
10*            http://www.opensource.org/licenses/cpl1.0.txt             *
11*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
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
46Hash_position_t*
47hashscan(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
86Hash_bucket_t*
87hashnext(register Hash_position_t* pos)
88{
89	register Hash_bucket_t*	b;
90
91	if (!pos) return(pos->tab->root->last.bucket = 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
130void
131hashdone(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