Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	bin/ksh/table.c	Lines:	94	95	98.9 %
Date:	2016-12-06	Branches:	55	58	94.8 %


/*	$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		1623211	{
35		1623211	unsigned int h = 0;
36
37	✓✓	11937581	while (*n != '\0')
38		8691159	h = 33h + (unsigned char)(n++);
39		1623211	return h;
40			}
41
42			void
43			ktinit(struct table tp, Area ap, int tsize)
44		307850	{
45		307850	tp->areap = ap;
46		307850	tp->tbls = NULL;
47		307850	tp->size = tp->nfree = 0;
48	✓✓	307850	if (tsize)
49		10575	texpand(tp, tsize);
50		307850	}
51
52			static void
53			texpand(struct table *tp, int nsize)
54		42452	{
55			int i;
56			struct tbl tblp, *p;
57		42452	struct tbl ntblp, otblp = tp->tbls;
58		42452	int osize = tp->size;
59
60		42452	ntblp = areallocarray(NULL, nsize, sizeof(struct tbl *), tp->areap);
61	✓✓	1189316	for (i = 0; i < nsize; i++)
62		1146864	ntblp[i] = NULL;
63		42452	tp->size = nsize;
64		42452	tp->nfree = 7nsize/10; / table can get 70% full */
65		42452	tp->tbls = ntblp;
66	✓✓	42452	if (otblp == NULL)
67		21543	return;
68	✓✓	324869	for (i = 0; i < osize; i++)
69	✓✓	303960	if ((tblp = otblp[i]) != NULL) {
70	✓✓	203704	if ((tblp->flag&DEFINED)) {
71			for (p = &ntblp[hash(tblp->name) &
72	✓✓	269657	(tp->size-1)]; *p != NULL; p--)
73	✓✓	65973	if (p == ntblp) /* wrap */
74		4	p += tp->size;
75		203684	*p = tblp;
76		203684	tp->nfree--;
77	✓✗	20	} else if (!(tblp->flag & FINUSE)) {
78		20	afree(tblp, tp->areap);
79			}
80			}
81		20909	afree(otblp, tp->areap);
82			}
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		1373093	{
90			struct tbl *pp, p;
91
92	✓✓	1373093	if (tp->size == 0)
93		466193	return NULL;
94
95			/* search for name in hashed table */
96	✓✓	1953072	for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
97	✓✓✓✓ ✓✓	1550635	if (p->name == n && strcmp(p->name, n) == 0 &&
98			(p->flag&DEFINED))
99		504463	return p;
100	✓✓	1046172	if (pp == tp->tbls) /* wrap */
101		24687	pp += tp->size;
102			}
103
104		402437	return NULL;
105			}
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		519352	{
113			struct tbl *pp, p;
114			int len;
115
116	✓✓	519352	if (tp->size == 0)
117		10968	texpand(tp, INIT_TBLS);
118		540261	Search:
119			/* search for name in hashed table */
120	✓✓	1068523	for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
121	✓✓✓✓	556920	if (p->name == n && strcmp(p->name, n) == 0)
122		28658	return p; /* found */
123	✓✓	528262	if (pp == tp->tbls) /* wrap */
124		10814	pp += tp->size;
125			}
126
127	✓✓	511603	if (tp->nfree <= 0) { /* too full */
128	✓✗	20909	if (tp->size <= INT_MAX/2)
129		20909	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		490694	len = strlen(n) + 1;
137		490694	p = alloc(offsetof(struct tbl, name[0]) + len,
138			tp->areap);
139		490694	p->flag = 0;
140		490694	p->type = 0;
141		490694	p->areap = tp->areap;
142		490694	p->u2.field = 0;
143		490694	p->u.array = NULL;
144		490694	memcpy(p->name, n, len);
145
146			/* enter in tp->tbls */
147		490694	tp->nfree--;
148		490694	*pp = p;
149		490694	return p;
150			}
151
152			void
153			ktdelete(struct tbl *p)
154		6	{
155		6	p->flag = 0;
156		6	}
157
158			void
159			ktwalk(struct tstate ts, struct table tp)
160		7522	{
161		7522	ts->left = tp->size;
162		7522	ts->next = tp->tbls;
163		7522	}
164
165			struct tbl *
166			ktnext(struct tstate *ts)
167		16053	{
168	✓✓	38615	while (--ts->left >= 0) {
169		15040	struct tbl p = ts->next++;
170	✓✓✓✗	15040	if (p != NULL && (p->flag&DEFINED))
171		8531	return p;
172			}
173		7522	return NULL;
174			}
175
176			static int
177			tnamecmp(const void p1, const void p2)
178		62832	{
179		62832	char name1 = ((struct tbl **)p1)->name;
180		62832	char name2 = ((struct tbl **)p2)->name;
181		62832	return strcmp(name1, name2);
182			}
183
184			struct tbl **
185			ktsort(struct table *tp)
186		28	{
187			int i;
188			struct tbl p, sp, **dp;
189
190		28	p = areallocarray(NULL, tp->size + 1,
191			sizeof(struct tbl *), ATEMP);
192		28	sp = tp->tbls; /* source */
193		28	dp = p; /* dest */
194	✓✓	12828	for (i = 0; i < tp->size; i++)
195	✓✓✓✓	12800	if ((dp = sp++) != NULL && (((*dp)->flag&DEFINED) \|\|
196			((*dp)->flag&ARRAY)))
197		7122	dp++;
198		28	i = dp - p;
199		28	qsortp((void**)p, (size_t)i, tnamecmp);
200		28	p[i] = NULL;
201		28	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 */