Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
att
GitHub Repository: att/ast
 Path: blob/master/src/lib/libast/hash/hashscan.c
1810 views
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 <[email protected]>                  *

18
*                  David Korn <[email protected]>                   *

19
*                   Phong Vo <[email protected]>                    *

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*

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*

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

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


141