GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: bin/ksh/table.c Lines: 92 93 98.9 %
Date: 2017-11-07 Branches: 58 62 93.5 %

Line Branch Exec Source
1
/*	$OpenBSD: table.c,v 1.23 2015/11/01 15:38:53 mmcc Exp $	*/
2
3
/*
4
 * dynamic hashed associative table for commands and variables
5
 */
6
7
#include <limits.h>
8
#include <stddef.h>
9
#include <string.h>
10
11
#include "sh.h"
12
13
#define	INIT_TBLS	8	/* initial table size (power of 2) */
14
15
struct table taliases;	/* tracked aliases */
16
struct table builtins;	/* built-in commands */
17
struct table aliases;	/* aliases */
18
struct table keywords;	/* keywords */
19
struct table homedirs;	/* homedir() cache */
20
21
char *path;		/* copy of either PATH or def_path */
22
const char *def_path;	/* path to use if PATH not set */
23
char *tmpdir;		/* TMPDIR value */
24
const char *prompt;
25
int cur_prompt;		/* PS1 or PS2 */
26
int current_lineno;	/* LINENO value */
27
28
static void	texpand(struct table *, int);
29
static int	tnamecmp(const void *, const void *);
30
31
32
unsigned int
33
hash(const char *n)
34
{
35
	unsigned int h = 0;
36
37
1749070333
	while (*n != '\0')
38
685573622
		h = 33*h + (unsigned char)(*n++);
39
125974363
	return h;
40
}
41
42
void
43
ktinit(struct table *tp, Area *ap, int tsize)
44
{
45
37027544
	tp->areap = ap;
46
18513772
	tp->tbls = NULL;
47
18513772
	tp->size = tp->nfree = 0;
48
18513772
	if (tsize)
49
653310
		texpand(tp, tsize);
50
18513772
}
51
52
static void
53
texpand(struct table *tp, int nsize)
54
{
55
	int i;
56
	struct tbl *tblp, **p;
57
5699320
	struct tbl **ntblp, **otblp = tp->tbls;
58
2849660
	int osize = tp->size;
59
60
2849660
	ntblp = areallocarray(NULL, nsize, sizeof(struct tbl *), tp->areap);
61
160840504
	for (i = 0; i < nsize; i++)
62
77570592
		ntblp[i] = NULL;
63
2849660
	tp->size = nsize;
64
2849660
	tp->nfree = 7*nsize/10;	/* table can get 70% full */
65
2849660
	tp->tbls = ntblp;
66
2849660
	if (otblp == NULL)
67
1505056
		return;
68
45571272
	for (i = 0; i < osize; i++)
69
21441032
		if ((tblp = otblp[i]) != NULL) {
70
14418194
			if ((tblp->flag&DEFINED)) {
71
49309814
				for (p = &ntblp[hash(tblp->name) &
72
34906606
				    (tp->size-1)]; *p != NULL; p--)
73
3050095
					if (p == ntblp) /* wrap */
74
145298
						p += tp->size;
75
14403208
				*p = tblp;
76
14403208
				tp->nfree--;
77
14418194
			} else if (!(tblp->flag & FINUSE)) {
78
14986
				afree(tblp, tp->areap);
79
14986
			}
80
		}
81
1344604
	afree(otblp, tp->areap);
82
4194264
}
83
84
/* table */
85
/* name to enter */
86
/* hash(n) */
87
struct tbl *
88
ktsearch(struct table *tp, const char *n, unsigned int h)
89
{
90
	struct tbl **pp, *p;
91
92
276132228
	if (tp->size == 0)
93
35676734
		return NULL;
94
95
	/* search for name in hashed table */
96
491080826
	for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
97

299279984
		if (*p->name == *n && strcmp(p->name, n) == 0 &&
98
48924648
		    (p->flag&DEFINED))
99
48762974
			return p;
100
143151033
		if (pp == tp->tbls) /* wrap */
101
5196865
			pp += tp->size;
102
	}
103
104
53626406
	return NULL;
105
138066114
}
106
107
/* table */
108
/* name to enter */
109
/* hash(n) */
110
struct tbl *
111
ktenter(struct table *tp, const char *n, unsigned int h)
112
{
113
	struct tbl **pp, *p;
114
	int len;
115
116
69821596
	if (tp->size == 0)
117
851746
		texpand(tp, INIT_TBLS);
118
  Search:
119
	/* search for name in hashed table */
120
151356692
	for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
121

46838770
		if (*p->name == *n && strcmp(p->name, n) == 0)
122
1813932
			return p;	/* found */
123
39422944
		if (pp == tp->tbls) /* wrap */
124
1303608
			pp += tp->size;
125
	}
126
127
34441470
	if (tp->nfree <= 0) {	/* too full */
128
1344604
		if (tp->size <= INT_MAX/2)
129
1344604
			texpand(tp, 2*tp->size);
130
		else
131
			internal_errorf(1, "too many vars");
132
		goto Search;
133
	}
134
135
	/* create new tbl entry */
136
33096866
	len = strlen(n) + 1;
137
66193732
	p = alloc(offsetof(struct tbl, name[0]) + len,
138
33096866
				 tp->areap);
139
33096866
	p->flag = 0;
140
33096866
	p->type = 0;
141
33096866
	p->areap = tp->areap;
142
33096866
	p->u2.field = 0;
143
33096866
	p->u.array = NULL;
144
33096866
	memcpy(p->name, n, len);
145
146
	/* enter in tp->tbls */
147
33096866
	tp->nfree--;
148
33096866
	*pp = p;
149
33096866
	return p;
150
34910798
}
151
152
void
153
ktdelete(struct tbl *p)
154
{
155
150
	p->flag = 0;
156
75
}
157
158
void
159
ktwalk(struct tstate *ts, struct table *tp)
160
{
161
964400
	ts->left = tp->size;
162
482200
	ts->next = tp->tbls;
163
482200
}
164
165
struct tbl *
166
ktnext(struct tstate *ts)
167
{
168
4619694
	while (--ts->left >= 0) {
169
1492544
		struct tbl *p = *ts->next++;
170

2332819
		if (p != NULL && (p->flag&DEFINED))
171
840275
			return p;
172
652269
	}
173
482200
	return NULL;
174
1322475
}
175
176
static int
177
tnamecmp(const void *p1, const void *p2)
178
{
179
266432
	char *name1 = (*(struct tbl **)p1)->name;
180
133216
	char *name2 = (*(struct tbl **)p2)->name;
181
133216
	return strcmp(name1, name2);
182
}
183
184
struct tbl **
185
ktsort(struct table *tp)
186
{
187
	int i;
188
	struct tbl **p, **sp, **dp;
189
190
717
	p = areallocarray(NULL, tp->size + 1,
191
239
	    sizeof(struct tbl *), ATEMP);
192
239
	sp = tp->tbls;		/* source */
193
	dp = p;			/* dest */
194
62430
	for (i = 0; i < tp->size; i++)
195

49029
		if ((*dp = *sp++) != NULL && (((*dp)->flag&DEFINED) ||
196
235
		    ((*dp)->flag&ARRAY)))
197
17583
			dp++;
198
239
	i = dp - p;
199
239
	qsortp((void**)p, (size_t)i, tnamecmp);
200
239
	p[i] = NULL;
201
239
	return p;
202
}
203
204
#ifdef PERF_DEBUG /* performance debugging */
205
206
void tprintinfo(struct table *tp);
207
208
void
209
tprintinfo(struct table *tp)
210
{
211
	struct tbl *te;
212
	char *n;
213
	unsigned int h;
214
	int ncmp;
215
	int totncmp = 0, maxncmp = 0;
216
	int nentries = 0;
217
	struct tstate ts;
218
219
	shellf("table size %d, nfree %d\n", tp->size, tp->nfree);
220
	shellf("    Ncmp name\n");
221
	ktwalk(&ts, tp);
222
	while ((te = ktnext(&ts))) {
223
		struct tbl **pp, *p;
224
225
		h = hash(n = te->name);
226
		ncmp = 0;
227
228
		/* taken from ktsearch() and added counter */
229
		for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp); pp--) {
230
			ncmp++;
231
			if (*p->name == *n && strcmp(p->name, n) == 0 &&
232
			    (p->flag&DEFINED))
233
				break; /* return p; */
234
			if (pp == tp->tbls) /* wrap */
235
				pp += tp->size;
236
		}
237
		shellf("    %4d %s\n", ncmp, n);
238
		totncmp += ncmp;
239
		nentries++;
240
		if (ncmp > maxncmp)
241
			maxncmp = ncmp;
242
	}
243
	if (nentries)
244
		shellf("  %d entries, worst ncmp %d, avg ncmp %d.%02d\n",
245
		    nentries, maxncmp,
246
		    totncmp / nentries,
247
		    (totncmp % nentries) * 100 / nentries);
248
}
249
#endif /* PERF_DEBUG */