Head

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 %


/*	$OpenBSD: table.c,v 1.23 2015/11/01 15:38:53 mmcc Exp $	*/

/*
 * dynamic hashed associative table for commands and variables
 */

#include <limits.h>
#include <stddef.h>
#include <string.h>

#include "sh.h"

#define	INIT_TBLS	8	/* initial table size (power of 2) */

struct table taliases;	/* tracked aliases */
struct table builtins;	/* built-in commands */
struct table aliases;	/* aliases */
struct table keywords;	/* keywords */
struct table homedirs;	/* homedir() cache */

char *path;		/* copy of either PATH or def_path */
const char *def_path;	/* path to use if PATH not set */
char *tmpdir;		/* TMPDIR value */
const char *prompt;
int cur_prompt;		/* PS1 or PS2 */
int current_lineno;	/* LINENO value */

static void	texpand(struct table *, int);
static int	tnamecmp(const void *, const void *);


unsigned int
hash(const char *n)
{
	unsigned int h = 0;

	while (*n != '\0')
		h = 33*h + (unsigned char)(*n++);
	return h;
}

void
ktinit(struct table *tp, Area *ap, int tsize)
{
	tp->areap = ap;
	tp->tbls = NULL;
	tp->size = tp->nfree = 0;
	if (tsize)
		texpand(tp, tsize);
}

static void
texpand(struct table *tp, int nsize)
{
	int i;
	struct tbl *tblp, **p;
	struct tbl **ntblp, **otblp = tp->tbls;
	int osize = tp->size;

	ntblp = areallocarray(NULL, nsize, sizeof(struct tbl *), tp->areap);
	for (i = 0; i < nsize; i++)
		ntblp[i] = NULL;
	tp->size = nsize;
	tp->nfree = 7*nsize/10;	/* table can get 70% full */
	tp->tbls = ntblp;
	if (otblp == NULL)
		return;
	for (i = 0; i < osize; i++)
		if ((tblp = otblp[i]) != NULL) {
			if ((tblp->flag&DEFINED)) {
				for (p = &ntblp[hash(tblp->name) &
				    (tp->size-1)]; *p != NULL; p--)
					if (p == ntblp) /* wrap */
						p += tp->size;
				*p = tblp;
				tp->nfree--;
			} else if (!(tblp->flag & FINUSE)) {
				afree(tblp, tp->areap);
			}
		}
	afree(otblp, tp->areap);
}

/* table */
/* name to enter */
/* hash(n) */
struct tbl *
ktsearch(struct table *tp, const char *n, unsigned int h)
{
	struct tbl **pp, *p;

	if (tp->size == 0)
		return NULL;

	/* search for name in hashed table */
	for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
		if (*p->name == *n && strcmp(p->name, n) == 0 &&
		    (p->flag&DEFINED))
			return p;
		if (pp == tp->tbls) /* wrap */
			pp += tp->size;
	}

	return NULL;
}

/* table */
/* name to enter */
/* hash(n) */
struct tbl *
ktenter(struct table *tp, const char *n, unsigned int h)
{
	struct tbl **pp, *p;
	int len;

	if (tp->size == 0)
		texpand(tp, INIT_TBLS);
  Search:
	/* search for name in hashed table */
	for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
		if (*p->name == *n && strcmp(p->name, n) == 0)
			return p;	/* found */
		if (pp == tp->tbls) /* wrap */
			pp += tp->size;
	}

	if (tp->nfree <= 0) {	/* too full */
		if (tp->size <= INT_MAX/2)
			texpand(tp, 2*tp->size);
		else
			internal_errorf(1, "too many vars");
		goto Search;
	}

	/* create new tbl entry */
	len = strlen(n) + 1;
	p = alloc(offsetof(struct tbl, name[0]) + len,
				 tp->areap);
	p->flag = 0;
	p->type = 0;
	p->areap = tp->areap;
	p->u2.field = 0;
	p->u.array = NULL;
	memcpy(p->name, n, len);

	/* enter in tp->tbls */
	tp->nfree--;
	*pp = p;
	return p;
}

void
ktdelete(struct tbl *p)
{
	p->flag = 0;
}

void
ktwalk(struct tstate *ts, struct table *tp)
{
	ts->left = tp->size;
	ts->next = tp->tbls;
}

struct tbl *
ktnext(struct tstate *ts)
{
	while (--ts->left >= 0) {
		struct tbl *p = *ts->next++;
		if (p != NULL && (p->flag&DEFINED))
			return p;
	}
	return NULL;
}

static int
tnamecmp(const void *p1, const void *p2)
{
	char *name1 = (*(struct tbl **)p1)->name;
	char *name2 = (*(struct tbl **)p2)->name;
	return strcmp(name1, name2);
}

struct tbl **
ktsort(struct table *tp)
{
	int i;
	struct tbl **p, **sp, **dp;

	p = areallocarray(NULL, tp->size + 1,
	    sizeof(struct tbl *), ATEMP);
	sp = tp->tbls;		/* source */
	dp = p;			/* dest */
	for (i = 0; i < tp->size; i++)
		if ((*dp = *sp++) != NULL && (((*dp)->flag&DEFINED) ||
		    ((*dp)->flag&ARRAY)))
			dp++;
	i = dp - p;
	qsortp((void**)p, (size_t)i, tnamecmp);
	p[i] = NULL;
	return p;
}

#ifdef PERF_DEBUG /* performance debugging */

void tprintinfo(struct table *tp);

void
tprintinfo(struct table *tp)
{
	struct tbl *te;
	char *n;
	unsigned int h;
	int ncmp;
	int totncmp = 0, maxncmp = 0;
	int nentries = 0;
	struct tstate ts;

	shellf("table size %d, nfree %d\n", tp->size, tp->nfree);
	shellf("    Ncmp name\n");
	ktwalk(&ts, tp);
	while ((te = ktnext(&ts))) {
		struct tbl **pp, *p;

		h = hash(n = te->name);
		ncmp = 0;

		/* taken from ktsearch() and added counter */
		for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp); pp--) {
			ncmp++;
			if (*p->name == *n && strcmp(p->name, n) == 0 &&
			    (p->flag&DEFINED))
				break; /* return p; */
			if (pp == tp->tbls) /* wrap */
				pp += tp->size;
		}
		shellf("    %4d %s\n", ncmp, n);
		totncmp += ncmp;
		nentries++;
		if (ncmp > maxncmp)
			maxncmp = ncmp;
	}
	if (nentries)
		shellf("  %d entries, worst ncmp %d, avg ncmp %d.%02d\n",
		    nentries, maxncmp,
		    totncmp / nentries,
		    (totncmp % nentries) * 100 / nentries);
}
#endif /* PERF_DEBUG */


Generated by: GCOVR (Version 3.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 = 33h + (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 = 7nsize/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 */