GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: bin/ksh/table.c Lines: 92 94 97.9 %
Date: 2017-11-13 Branches: 56 62 90.3 %

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
603251120
	while (*n != '\0')
38
232856425
		h = 33*h + (unsigned char)(*n++);
39
45846090
	return h;
40
}
41
42
void
43
ktinit(struct table *tp, Area *ap, int tsize)
44
{
45
11826840
	tp->areap = ap;
46
5913420
	tp->tbls = NULL;
47
5913420
	tp->size = tp->nfree = 0;
48
5913420
	if (tsize)
49
314289
		texpand(tp, tsize);
50
5913420
}
51
52
static void
53
texpand(struct table *tp, int nsize)
54
{
55
	int i;
56
	struct tbl *tblp, **p;
57
2558036
	struct tbl **ntblp, **otblp = tp->tbls;
58
1279018
	int osize = tp->size;
59
60
1279018
	ntblp = areallocarray(NULL, nsize, sizeof(struct tbl *), tp->areap);
61
72313796
	for (i = 0; i < nsize; i++)
62
34877880
		ntblp[i] = NULL;
63
1279018
	tp->size = nsize;
64
1279018
	tp->nfree = 7*nsize/10;	/* table can get 70% full */
65
1279018
	tp->tbls = ntblp;
66
1279018
	if (otblp == NULL)
67
646918
		return;
68
20071384
	for (i = 0; i < osize; i++)
69
9403592
		if ((tblp = otblp[i]) != NULL) {
70
6307393
			if ((tblp->flag&DEFINED)) {
71
21538409
				for (p = &ntblp[hash(tblp->name) &
72
15232580
				    (tp->size-1)]; *p != NULL; p--)
73
1310461
					if (p == ntblp) /* wrap */
74
49226
						p += tp->size;
75
6305829
				*p = tblp;
76
6305829
				tp->nfree--;
77
6307393
			} else if (!(tblp->flag & FINUSE)) {
78
1564
				afree(tblp, tp->areap);
79
1564
			}
80
		}
81
632100
	afree(otblp, tp->areap);
82
1911118
}
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
89620226
	if (tp->size == 0)
93
13246655
		return NULL;
94
95
	/* search for name in hashed table */
96
166490382
	for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
97

95370160
		if (*p->name == *n && strcmp(p->name, n) == 0 &&
98
13800602
		    (p->flag&DEFINED))
99
13800236
			return p;
100
51681733
		if (pp == tp->tbls) /* wrap */
101
1068021
			pp += tp->size;
102
	}
103
104
17763222
	return NULL;
105
44810113
}
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
48515034
	if (tp->size == 0)
117
332629
		texpand(tp, INIT_TBLS);
118
  Search:
119
	/* search for name in hashed table */
120
69611210
	for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
121

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

1166806
		if (p != NULL && (p->flag&DEFINED))
171
420134
			return p;
172
326538
	}
173
232861
	return NULL;
174
652995
}
175
176
static int
177
tnamecmp(const void *p1, const void *p2)
178
{
179
8244
	char *name1 = (*(struct tbl **)p1)->name;
180
4122
	char *name2 = (*(struct tbl **)p2)->name;
181
4122
	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
144
	p = areallocarray(NULL, tp->size + 1,
191
48
	    sizeof(struct tbl *), ATEMP);
192
48
	sp = tp->tbls;		/* source */
193
	dp = p;			/* dest */
194
3168
	for (i = 0; i < tp->size; i++)
195

2532
		if ((*dp = *sp++) != NULL && (((*dp)->flag&DEFINED) ||
196
		    ((*dp)->flag&ARRAY)))
197
996
			dp++;
198
48
	i = dp - p;
199
48
	qsortp((void**)p, (size_t)i, tnamecmp);
200
48
	p[i] = NULL;
201
48
	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 */