1 files changed, 293 insertions, 0 deletions
diff --git a/gnu/usr.bin/awk/array.c b/gnu/usr.bin/awk/array.c
new file mode 100644
index 0000000..59be340
--- /dev/null
+++ b/gnu/usr.bin/awk/array.c
@@ -0,0 +1,293 @@
+/*
+ * array.c - routines for associative arrays.
+ */
+
+/* 
+ * Copyright (C) 1986, 1988, 1989, 1991, 1992 the Free Software Foundation, Inc.
+ * 
+ * This file is part of GAWK, the GNU implementation of the
+ * AWK Progamming Language.
+ * 
+ * GAWK is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * GAWK is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with GAWK; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+#include "awk.h"
+
+static NODE *assoc_find P((NODE *symbol, NODE *subs, int hash1));
+
+NODE *
+concat_exp(tree)
+register NODE *tree;
+{
+	register NODE *r;
+	char *str;
+	char *s;
+	unsigned len;
+	int offset;
+	int subseplen;
+	char *subsep;
+
+	if (tree->type != Node_expression_list)
+		return force_string(tree_eval(tree));
+	r = force_string(tree_eval(tree->lnode));
+	if (tree->rnode == NULL)
+		return r;
+	subseplen = SUBSEP_node->lnode->stlen;
+	subsep = SUBSEP_node->lnode->stptr;
+	len = r->stlen + subseplen + 2;
+	emalloc(str, char *, len, "concat_exp");
+	memcpy(str, r->stptr, r->stlen+1);
+	s = str + r->stlen;
+	free_temp(r);
+	tree = tree->rnode;
+	while (tree) {
+		if (subseplen == 1)
+			*s++ = *subsep;
+		else {
+			memcpy(s, subsep, subseplen+1);
+			s += subseplen;
+		}
+		r = force_string(tree_eval(tree->lnode));
+		len += r->stlen + subseplen;
+		offset = s - str;
+		erealloc(str, char *, len, "concat_exp");
+		s = str + offset;
+		memcpy(s, r->stptr, r->stlen+1);
+		s += r->stlen;
+		free_temp(r);
+		tree = tree->rnode;
+	}
+	r = make_str_node(str, s - str, ALREADY_MALLOCED);
+	r->flags |= TEMP;
+	return r;
+}
+
+/* Flush all the values in symbol[] before doing a split() */
+void
+assoc_clear(symbol)
+NODE *symbol;
+{
+	int i;
+	NODE *bucket, *next;
+
+	if (symbol->var_array == 0)
+		return;
+	for (i = 0; i < HASHSIZE; i++) {
+		for (bucket = symbol->var_array[i]; bucket; bucket = next) {
+			next = bucket->ahnext;
+			unref(bucket->ahname);
+			unref(bucket->ahvalue);
+			freenode(bucket);
+		}
+		symbol->var_array[i] = 0;
+	}
+}
+
+/*
+ * calculate the hash function of the string in subs
+ */
+unsigned int
+hash(s, len)
+register char *s;
+register int len;
+{
+	register unsigned long h = 0, g;
+
+	while (len--) {
+		h = (h << 4) + *s++;
+		g = (h & 0xf0000000);
+		if (g) {
+			h = h ^ (g >> 24);
+			h = h ^ g;
+		}
+	}
+	if (h < HASHSIZE)
+		return h;
+	else
+		return h%HASHSIZE;
+}
+
+/*
+ * locate symbol[subs]
+ */
+static NODE *				/* NULL if not found */
+assoc_find(symbol, subs, hash1)
+NODE *symbol;
+register NODE *subs;
+int hash1;
+{
+	register NODE *bucket, *prev = 0;
+
+	for (bucket = symbol->var_array[hash1]; bucket; bucket = bucket->ahnext) {
+		if (cmp_nodes(bucket->ahname, subs) == 0) {
+			if (prev) {	/* move found to front of chain */
+				prev->ahnext = bucket->ahnext;
+				bucket->ahnext = symbol->var_array[hash1];
+				symbol->var_array[hash1] = bucket;
+			}
+			return bucket;
+		} else
+			prev = bucket;	/* save previous list entry */
+	}
+	return NULL;
+}
+
+/*
+ * test whether the array element symbol[subs] exists or not 
+ */
+int
+in_array(symbol, subs)
+NODE *symbol, *subs;
+{
+	register int hash1;
+
+	if (symbol->type == Node_param_list)
+		symbol = stack_ptr[symbol->param_cnt];
+	if (symbol->var_array == 0)
+		return 0;
+	subs = concat_exp(subs);	/* concat_exp returns a string node */
+	hash1 = hash(subs->stptr, subs->stlen);
+	if (assoc_find(symbol, subs, hash1) == NULL) {
+		free_temp(subs);
+		return 0;
+	} else {
+		free_temp(subs);
+		return 1;
+	}
+}
+
+/*
+ * SYMBOL is the address of the node (or other pointer) being dereferenced.
+ * SUBS is a number or string used as the subscript. 
+ *
+ * Find SYMBOL[SUBS] in the assoc array.  Install it with value "" if it
+ * isn't there. Returns a pointer ala get_lhs to where its value is stored 
+ */
+NODE **
+assoc_lookup(symbol, subs)
+NODE *symbol, *subs;
+{
+	register int hash1;
+	register NODE *bucket;
+
+	(void) force_string(subs);
+	hash1 = hash(subs->stptr, subs->stlen);
+
+	if (symbol->var_array == 0) {	/* this table really should grow
+					 * dynamically */
+		unsigned size;
+
+		size = sizeof(NODE *) * HASHSIZE;
+		emalloc(symbol->var_array, NODE **, size, "assoc_lookup");
+		memset((char *)symbol->var_array, 0, size);
+		symbol->type = Node_var_array;
+	} else {
+		bucket = assoc_find(symbol, subs, hash1);
+		if (bucket != NULL) {
+			free_temp(subs);
+			return &(bucket->ahvalue);
+		}
+	}
+
+	/* It's not there, install it. */
+	if (do_lint && subs->stlen == 0)
+		warning("subscript of array `%s' is null string",
+			symbol->vname);
+	getnode(bucket);
+	bucket->type = Node_ahash;
+	if (subs->flags & TEMP)
+		bucket->ahname = dupnode(subs);
+	else {
+		unsigned int saveflags = subs->flags;
+
+		subs->flags &= ~MALLOC;
+		bucket->ahname = dupnode(subs);
+		subs->flags = saveflags;
+	}
+	free_temp(subs);
+
+	/* array subscripts are strings */
+	bucket->ahname->flags &= ~NUMBER;
+	bucket->ahname->flags |= STRING;
+	bucket->ahvalue = Nnull_string;
+	bucket->ahnext = symbol->var_array[hash1];
+	symbol->var_array[hash1] = bucket;
+	return &(bucket->ahvalue);
+}
+
+void
+do_delete(symbol, tree)
+NODE *symbol, *tree;
+{
+	register int hash1;
+	register NODE *bucket, *last;
+	NODE *subs;
+
+	if (symbol->type == Node_param_list)
+		symbol = stack_ptr[symbol->param_cnt];
+	if (symbol->var_array == 0)
+		return;
+	subs = concat_exp(tree);	/* concat_exp returns string node */
+	hash1 = hash(subs->stptr, subs->stlen);
+
+	last = NULL;
+	for (bucket = symbol->var_array[hash1]; bucket; last = bucket, bucket = bucket->ahnext)
+		if (cmp_nodes(bucket->ahname, subs) == 0)
+			break;
+	free_temp(subs);
+	if (bucket == NULL)
+		return;
+	if (last)
+		last->ahnext = bucket->ahnext;
+	else
+		symbol->var_array[hash1] = bucket->ahnext;
+	unref(bucket->ahname);
+	unref(bucket->ahvalue);
+	freenode(bucket);
+}
+
+void
+assoc_scan(symbol, lookat)
+NODE *symbol;
+struct search *lookat;
+{
+	if (!symbol->var_array) {
+		lookat->retval = NULL;
+		return;
+	}
+	lookat->arr_ptr = symbol->var_array;
+	lookat->arr_end = lookat->arr_ptr + HASHSIZE;	/* added */
+	lookat->bucket = symbol->var_array[0];
+	assoc_next(lookat);
+}
+
+void
+assoc_next(lookat)
+struct search *lookat;
+{
+	while (lookat->arr_ptr < lookat->arr_end) {
+		if (lookat->bucket != 0) {
+			lookat->retval = lookat->bucket->ahname;
+			lookat->bucket = lookat->bucket->ahnext;
+			return;
+		}
+		lookat->arr_ptr++;
+		if (lookat->arr_ptr < lookat->arr_end)
+			lookat->bucket = *(lookat->arr_ptr);
+		else
+			lookat->retval = NULL;
+	}
+	return;
+}