[unix-history] / usr / src / contrib / rc-1.4 / hash.c

/* hash.c: hash table support for functions and variables. */

/*
   Functions and variables are cached in both internal and external
   form for performance. Thus a variable which is never "dereferenced"
   with a $ is passed on to rc's children untouched. This is not so
   important for variables, but is a big win for functions, where a call
   to yyparse() is involved.
*/

#include "rc.h"
#include "sigmsgs.h"

static bool var_exportable(char *);
static bool fn_exportable(char *);
static int hash(char *, int);
static int find(char *, Htab *, int);
static void free_fn(Function *);

Htab *fp;
Htab *vp;
static int fused, fsize, vused, vsize;
static char **env;
static int bozosize;
static int envsize;
static bool env_dirty = TRUE;
static char *dead = "";

#define HASHSIZE 64 /* rc was debugged with HASHSIZE == 2; 64 is about right for normal use */

extern void inithash() {
	Htab *fpp, *vpp;
	int i;
	fp = ealloc(sizeof(Htab) * HASHSIZE);
	vp = ealloc(sizeof(Htab) * HASHSIZE);
	fused = vused = 0;
	fsize = vsize = HASHSIZE;
	for (vpp = vp, fpp = fp, i = 0; i < HASHSIZE; i++, vpp++, fpp++)
		vpp->name = fpp->name = NULL;
}

#define ADV()   {if ((c = *s++) == '\0') break;}

/* hash function courtesy of paul haahr */

static int hash(char *s, int size) {
	int c, n = 0;
	while (1) {
		ADV();
		n += (c << 17) ^ (c << 11) ^ (c << 5) ^ (c >> 1);
		ADV();
		n ^= (c << 14) + (c << 7) + (c << 4) + c;
		ADV();
		n ^= (~c << 11) | ((c << 3) ^ (c >> 1));
		ADV();
		n -= (c << 16) | (c << 9) | (c << 2) | (c & 3);
	}
	if (n < 0)
		n = ~n;
	return n & (size - 1); /* need power of 2 size */
}

static bool rehash(Htab *ht) {
	int i, j, size;
	int newsize, newused;
	Htab *newhtab;
	if (ht == fp) {
		if (fsize > 2 * fused)
			return FALSE;
		size = fsize;
	} else {
		if (vsize > 2 * vused)
			return FALSE;
		size = vsize;
	}
	newsize = 2 * size;
	newhtab = ealloc(newsize * sizeof(Htab));
	for (i = 0; i < newsize; i++)
		newhtab[i].name = NULL;
	for (i = newused = 0; i < size; i++)
		if (ht[i].name != NULL && ht[i].name != dead) {
			newused++;
			j = hash(ht[i].name, newsize);
			while (newhtab[j].name != NULL) {
				j++;
				j &= (newsize - 1);
			}
			newhtab[j].name = ht[i].name;
			newhtab[j].p = ht[i].p;
		}
	if (ht == fp) {
		fused = newused;
		fp = newhtab;
		fsize = newsize;
	} else {
		vused = newused;
		vp = newhtab;
		vsize = newsize;
	}
	efree(ht);
	return TRUE;
}

#define varfind(s) find(s, vp, vsize)
#define fnfind(s) find(s, fp, fsize)

static int find(char *s, Htab *ht, int size) {
	int h = hash(s, size);
	while (ht[h].name != NULL && !streq(ht[h].name, s)) {
		h++;
		h &= size - 1;
	}
	return h;
}

extern void *lookup(char *s, Htab *ht) {
	int h = find(s, ht, ht == fp ? fsize : vsize);
	return (ht[h].name == NULL) ? NULL : ht[h].p;
}

extern Function *get_fn_place(char *s) {
	int h = fnfind(s);
	env_dirty = TRUE;
	if (fp[h].name == NULL) {
		if (rehash(fp))
			h = fnfind(s);
		fused++;
		fp[h].name = ecpy(s);
		fp[h].p = enew(Function);
	} else
		free_fn(fp[h].p);
	return fp[h].p;
}

extern Variable *get_var_place(char *s, bool stack) {
	Variable *new;
	int h = varfind(s);

	env_dirty = TRUE;

	if (vp[h].name == NULL) {
		if (rehash(vp))
			h = varfind(s);
		vused++;
		vp[h].name = ecpy(s);
		vp[h].p = enew(Variable);
		((Variable *)vp[h].p)->n = NULL;
		return vp[h].p;
	} else {
		if (stack) {	/* increase the stack by 1 */
			new = enew(Variable);
			new->n = vp[h].p;
			return vp[h].p = new;
		} else {	/* trample the top of the stack */
			new = vp[h].p;
			efree(new->extdef);
			listfree(new->def);
			return new;
		}
	}
}

extern void delete_fn(char *s) {
	int h = fnfind(s);
	if (fp[h].name == NULL)
		return; /* not found */
	env_dirty = TRUE;
	free_fn(fp[h].p);
	efree(fp[h].p);
	efree(fp[h].name);
	if (fp[(h+1)&(fsize-1)].name == NULL) {
		--fused;
		fp[h].name = NULL;
	} else {
		fp[h].name = dead;
	}
}

extern void delete_var(char *s, bool stack) {
	int h = varfind(s);
	Variable *v;
	if (vp[h].name == NULL)
		return; /* not found */
	env_dirty = TRUE;
	v = vp[h].p;
	efree(v->extdef);
	listfree(v->def);
	if (v->n != NULL) { /* This is the top of a stack */
		if (stack) { /* pop */
			vp[h].p = v->n;
			efree(v);
		} else { /* else just empty */
			v->extdef = NULL;
			v->def = NULL;
		}
	} else { /* needs to be removed from the hash table */
		efree(v);
		efree(vp[h].name);
		if (vp[(h+1)&(vsize-1)].name == NULL) {
			--vused;
			vp[h].name = NULL;
		} else {
			vp[h].name = dead;
		}
	}
}

static void free_fn(Function *f) {
	treefree(f->def);
	efree(f->extdef);
}

extern void initenv(char **envp) {
	int n;
	for (n = 0; envp[n] != NULL; n++)
		;
	n++; /* one for the null terminator */
	if (n < HASHSIZE)
		n = HASHSIZE;
	env = ealloc((envsize = 2 * n) * sizeof (char *));
	for (; *envp != NULL; envp++)
		if (strncmp(*envp, "fn_", conststrlen("fn_")) == 0) {
			if (!dashpee)
				fnassign_string(*envp);
		} else {
			if (!varassign_string(*envp)) /* add to bozo env */
				env[bozosize++] = *envp;
		}
}

static bool var_exportable(char *s) {
	static char *notforexport[] = {
		"apid", "pid", "apids", "*", "ifs"
	};
	int i;
	for (i = 0; i < arraysize(notforexport); i++)
		if (streq(s, notforexport[i]))
			return FALSE;
	return TRUE;
}

static bool fn_exportable(char *s) {
	int i;
	if (strncmp(s, "sig", conststrlen("sig")) == 0) { /* small speed hack */
		for (i = 0; i < NUMOFSIGNALS; i++)
			if (streq(s, signals[i].name))
				return FALSE;
		if (streq(s, "sigexit"))
			return FALSE;
	}
	return TRUE;
}

extern char **makeenv() {
	int ep, i;
	char *v;
	if (!env_dirty)
		return env;
	env_dirty = FALSE;
	ep = bozosize;
	if (vsize + fsize + 1 + bozosize > envsize) {
		envsize = 2 * (bozosize + vsize + fsize + 1);
		env = erealloc(env, envsize * sizeof(char *));
	}
	for (i = 0; i < vsize; i++) {
		if (vp[i].name == NULL || vp[i].name == dead || !var_exportable(vp[i].name))
			continue;
		v = varlookup_string(vp[i].name);
		if (v != NULL)
			env[ep++] = v;
	}
	for (i = 0; i < fsize; i++) {
		if (fp[i].name == NULL || fp[i].name == dead || !fn_exportable(fp[i].name))
			continue;
		env[ep++] = fnlookup_string(fp[i].name);
	}
	env[ep] = NULL;
	qsort(env, (size_t) ep, sizeof(char *), starstrcmp);
	return env;
}

extern void whatare_all_vars() {
	int i;
	List *s;
	for (i = 0; i < vsize; i++)
		if (vp[i].name != NULL && (s = varlookup(vp[i].name)) != NULL)
			prettyprint_var(1, vp[i].name, s);
	for (i = 0; i < fsize; i++)
		if (fp[i].name != NULL && fp[i].name != dead)
			prettyprint_fn(1, fp[i].name, fnlookup(fp[i].name));
}
Commit	Line	Data
cebbdce6 C	1	/* hash.c: hash table support for functions and variables. */
	2
	3	/*
	4	Functions and variables are cached in both internal and external
	5	form for performance. Thus a variable which is never "dereferenced"
	6	with a $ is passed on to rc's children untouched. This is not so
	7	important for variables, but is a big win for functions, where a call
	8	to yyparse() is involved.
	9	*/
	10
	11	#include "rc.h"
	12	#include "sigmsgs.h"
	13
	14	static bool var_exportable(char *);
	15	static bool fn_exportable(char *);
	16	static int hash(char *, int);
	17	static int find(char , Htab , int);
	18	static void free_fn(Function *);
	19
	20	Htab *fp;
	21	Htab *vp;
	22	static int fused, fsize, vused, vsize;
	23	static char **env;
	24	static int bozosize;
	25	static int envsize;
	26	static bool env_dirty = TRUE;
	27	static char *dead = "";
	28
	29	#define HASHSIZE 64 /* rc was debugged with HASHSIZE == 2; 64 is about right for normal use */
	30
	31	extern void inithash() {
	32	Htab fpp, vpp;
	33	int i;
	34	fp = ealloc(sizeof(Htab) * HASHSIZE);
	35	vp = ealloc(sizeof(Htab) * HASHSIZE);
	36	fused = vused = 0;
	37	fsize = vsize = HASHSIZE;
	38	for (vpp = vp, fpp = fp, i = 0; i < HASHSIZE; i++, vpp++, fpp++)
	39	vpp->name = fpp->name = NULL;
	40	}
	41
	42	#define ADV() {if ((c = *s++) == '\0') break;}
	43
	44	/* hash function courtesy of paul haahr */
	45
	46	static int hash(char *s, int size) {
	47	int c, n = 0;
	48	while (1) {
	49	ADV();
	50	n += (c << 17) ^ (c << 11) ^ (c << 5) ^ (c >> 1);
	51	ADV();
	52	n ^= (c << 14) + (c << 7) + (c << 4) + c;
	53	ADV();
	54	n ^= (~c << 11) \| ((c << 3) ^ (c >> 1));
	55	ADV();
	56	n -= (c << 16) \| (c << 9) \| (c << 2) \| (c & 3);
	57	}
	58	if (n < 0)
	59	n = ~n;
	60	return n & (size - 1); /* need power of 2 size */
	61	}
	62
	63	static bool rehash(Htab *ht) {
	64	int i, j, size;
65	int newsize, newused;
66	Htab *newhtab;
67	if (ht == fp) {
68	if (fsize > 2 * fused)
69	return FALSE;
70	size = fsize;
71	} else {
72	if (vsize > 2 * vused)
73	return FALSE;
74	size = vsize;
75	}
76	newsize = 2 * size;
77	newhtab = ealloc(newsize * sizeof(Htab));
78	for (i = 0; i < newsize; i++)
79	newhtab[i].name = NULL;
80	for (i = newused = 0; i < size; i++)
81	if (ht[i].name != NULL && ht[i].name != dead) {
82	newused++;
83	j = hash(ht[i].name, newsize);
84	while (newhtab[j].name != NULL) {
85	j++;
86	j &= (newsize - 1);
87	}
88	newhtab[j].name = ht[i].name;
89	newhtab[j].p = ht[i].p;
90	}
91	if (ht == fp) {
92	fused = newused;
93	fp = newhtab;
94	fsize = newsize;
95	} else {
96	vused = newused;
97	vp = newhtab;
98	vsize = newsize;
99	}
100	efree(ht);
101	return TRUE;
102	}
103
104	#define varfind(s) find(s, vp, vsize)
105	#define fnfind(s) find(s, fp, fsize)
106
107	static int find(char s, Htab ht, int size) {
108	int h = hash(s, size);
109	while (ht[h].name != NULL && !streq(ht[h].name, s)) {
110	h++;
111	h &= size - 1;
112	}
113	return h;
114	}
115
116	extern void lookup(char s, Htab *ht) {
117	int h = find(s, ht, ht == fp ? fsize : vsize);
118	return (ht[h].name == NULL) ? NULL : ht[h].p;
119	}
120
121	extern Function get_fn_place(char s) {
122	int h = fnfind(s);
123	env_dirty = TRUE;
124	if (fp[h].name == NULL) {
125	if (rehash(fp))
126	h = fnfind(s);
127	fused++;
128	fp[h].name = ecpy(s);
129	fp[h].p = enew(Function);
130	} else
131	free_fn(fp[h].p);
132	return fp[h].p;
133	}
134
135	extern Variable get_var_place(char s, bool stack) {
136	Variable *new;
137	int h = varfind(s);
138
139	env_dirty = TRUE;
140
141	if (vp[h].name == NULL) {
142	if (rehash(vp))
143	h = varfind(s);
144	vused++;
145	vp[h].name = ecpy(s);
146	vp[h].p = enew(Variable);
147	((Variable *)vp[h].p)->n = NULL;
148	return vp[h].p;
149	} else {
150	if (stack) { /* increase the stack by 1 */
151	new = enew(Variable);
152	new->n = vp[h].p;
153	return vp[h].p = new;
154	} else { /* trample the top of the stack */
155	new = vp[h].p;
156	efree(new->extdef);
157	listfree(new->def);
158	return new;
159	}
160	}
161	}
162
163	extern void delete_fn(char *s) {
164	int h = fnfind(s);
165	if (fp[h].name == NULL)
166	return; /* not found */
167	env_dirty = TRUE;
168	free_fn(fp[h].p);
169	efree(fp[h].p);
170	efree(fp[h].name);
171	if (fp[(h+1)&(fsize-1)].name == NULL) {
172	--fused;
173	fp[h].name = NULL;
174	} else {
175	fp[h].name = dead;
176	}
177	}
178
179	extern void delete_var(char *s, bool stack) {
180	int h = varfind(s);
181	Variable *v;
182	if (vp[h].name == NULL)
183	return; /* not found */
184	env_dirty = TRUE;
185	v = vp[h].p;
186	efree(v->extdef);
187	listfree(v->def);
188	if (v->n != NULL) { /* This is the top of a stack */
189	if (stack) { /* pop */
190	vp[h].p = v->n;
191	efree(v);
192	} else { /* else just empty */
193	v->extdef = NULL;
194	v->def = NULL;
195	}
196	} else { /* needs to be removed from the hash table */
197	efree(v);
198	efree(vp[h].name);
199	if (vp[(h+1)&(vsize-1)].name == NULL) {
200	--vused;
201	vp[h].name = NULL;
202	} else {
203	vp[h].name = dead;
204	}
205	}
206	}
207
208	static void free_fn(Function *f) {
209	treefree(f->def);
210	efree(f->extdef);
211	}
212
213	extern void initenv(char **envp) {
214	int n;
215	for (n = 0; envp[n] != NULL; n++)
216	;
217	n++; /* one for the null terminator */
218	if (n < HASHSIZE)
219	n = HASHSIZE;
220	env = ealloc((envsize = 2 * n) * sizeof (char *));
221	for (; *envp != NULL; envp++)
222	if (strncmp(*envp, "fn_", conststrlen("fn_")) == 0) {
223	if (!dashpee)
224	fnassign_string(*envp);
225	} else {
226	if (!varassign_string(envp)) / add to bozo env */
227	env[bozosize++] = *envp;
228	}
229	}
230
231	static bool var_exportable(char *s) {
232	static char *notforexport[] = {
233	"apid", "pid", "apids", "*", "ifs"
234	};
235	int i;
236	for (i = 0; i < arraysize(notforexport); i++)
237	if (streq(s, notforexport[i]))
238	return FALSE;
239	return TRUE;
240	}
241
242	static bool fn_exportable(char *s) {
243	int i;
244	if (strncmp(s, "sig", conststrlen("sig")) == 0) { /* small speed hack */
245	for (i = 0; i < NUMOFSIGNALS; i++)
246	if (streq(s, signals[i].name))
247	return FALSE;
248	if (streq(s, "sigexit"))
249	return FALSE;
250	}
251	return TRUE;
252	}
253
254	extern char **makeenv() {
255	int ep, i;
256	char *v;
257	if (!env_dirty)
258	return env;
259	env_dirty = FALSE;
260	ep = bozosize;
261	if (vsize + fsize + 1 + bozosize > envsize) {
262	envsize = 2 * (bozosize + vsize + fsize + 1);
263	env = erealloc(env, envsize * sizeof(char *));
264	}
265	for (i = 0; i < vsize; i++) {
266	if (vp[i].name == NULL \|\| vp[i].name == dead \|\| !var_exportable(vp[i].name))
267	continue;
268	v = varlookup_string(vp[i].name);
269	if (v != NULL)
270	env[ep++] = v;
271	}
272	for (i = 0; i < fsize; i++) {
273	if (fp[i].name == NULL \|\| fp[i].name == dead \|\| !fn_exportable(fp[i].name))
274	continue;
275	env[ep++] = fnlookup_string(fp[i].name);
276	}
277	env[ep] = NULL;
278	qsort(env, (size_t) ep, sizeof(char *), starstrcmp);
279	return env;
280	}
281
282	extern void whatare_all_vars() {
283	int i;
284	List *s;
285	for (i = 0; i < vsize; i++)
286	if (vp[i].name != NULL && (s = varlookup(vp[i].name)) != NULL)
287	prettyprint_var(1, vp[i].name, s);
288	for (i = 0; i < fsize; i++)
289	if (fp[i].name != NULL && fp[i].name != dead)
290	prettyprint_fn(1, fp[i].name, fnlookup(fp[i].name));
291	}