/*

 * int_array.c - routines for arrays of integer indices.

 */

/*

 * Copyright (C) 1986, 1988, 1989, 1991-2013, 2016, 2017,

 * the Free Software Foundation, Inc.

 *

 * This file is part of GAWK, the GNU implementation of the

 * AWK Programming 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 3 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 this program; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA

 */

#include "awk.h"

extern FILE *output_fp;

extern void indent(int indent_level);

extern NODE **is_integer(NODE *symbol, NODE *subs);

static size_t INT_CHAIN_MAX = 2;

static NODE **int_array_init(NODE *symbol, NODE *subs);

static NODE **int_lookup(NODE *symbol, NODE *subs);

static NODE **int_exists(NODE *symbol, NODE *subs);

static NODE **int_clear(NODE *symbol, NODE *subs);

static NODE **int_remove(NODE *symbol, NODE *subs);

static NODE **int_list(NODE *symbol, NODE *t);

static NODE **int_copy(NODE *symbol, NODE *newsymb);

static NODE **int_dump(NODE *symbol, NODE *ndump);

static uint32_t int_hash(uint32_t k, uint32_t hsize);

static inline NODE **int_find(NODE *symbol, long k, uint32_t hash1);

static NODE **int_insert(NODE *symbol, long k, uint32_t hash1);

static void grow_int_table(NODE *symbol);

afunc_t int_array_func[] = {

	int_array_init,

	is_integer,

	null_length,

	int_lookup,

	int_exists,

	int_clear,

	int_remove,

	int_list,

	int_copy,

	int_dump,

	(afunc_t) 0,

};

/* int_array_init --- array initialization routine */

static NODE **

int_array_init(NODE *symbol, NODE *subs ATTRIBUTE_UNUSED)

{

	if (symbol == NULL) {	/* first time */

		long newval;

		/* check relevant environment variables */

		if ((newval = getenv_long("INT_CHAIN_MAX")) > 0)

			INT_CHAIN_MAX = newval;

	} else

		null_array(symbol);

	return & success_node;

}

/*

 * standard_integer_string -- check whether the string matches what

 * sprintf("%ld", <value>) would produce. This is accomplished by accepting

 * only strings that look like /^0$/ or /^-?[1-9][0-9]*$/. This should be

 * faster than comparing vs. the results of actually calling sprintf.

 */

static bool

standard_integer_string(const char *s, size_t len)

{

	const char *end;

	if (len == 0)

		return false;

	if (*s == '0' && len == 1)

		return true;

	end = s + len;

	/* ignore leading minus sign */

	if (*s == '-' && ++s == end)

		return false;

	/* check first char is [1-9] */

	if (*s < '1' || *s > '9')

		return false;

	while (++s < end) {

		if (*s < '0' || *s > '9')

			return false;

	}

	return true;

}

/* is_integer --- check if subscript is an integer */

NODE **

is_integer(NODE *symbol, NODE *subs)

{

#ifndef CHECK_INTEGER_USING_FORCE_NUMBER

	long l;

#endif

	AWKNUM d;

	if ((subs->flags & NUMINT) != 0)

		/* quick exit */

		return & success_node;

	if (subs == Nnull_string || do_mpfr)

		return NULL;

#ifdef CHECK_INTEGER_USING_FORCE_NUMBER

	/*

	 * This approach is much simpler, because we remove all of the strtol

	 * logic below. But this may be slower in some usage cases.

	 */

	if ((subs->flags & NUMCUR) == 0) {

		str2number(subs);

		/* check again in case force_number set NUMINT */

		if ((subs->flags & NUMINT) != 0)

			return & success_node;

	}

#else /* CHECK_INTEGER_USING_FORCE_NUMBER */

	if ((subs->flags & NUMCUR) != 0) {

#endif /* CHECK_INTEGER_USING_FORCE_NUMBER */

		d = subs->numbr;

		if (d <= INT32_MAX && d >= INT32_MIN && d == (int32_t) d) {

			/*

			 * The numeric value is an integer, but we must

			 * protect against strings that cannot be generated

			 * from sprintf("%ld", <subscript>). This can happen

			 * with strnum or string values. We could skip this

			 * check for pure NUMBER values, but unfortunately the

			 * code does not currently distinguish between NUMBER

			 * and strnum values.

			 */

			if (   (subs->flags & STRCUR) == 0

			    || standard_integer_string(subs->stptr, subs->stlen)) {

				subs->flags |= NUMINT;

				return & success_node;

			}

		}

		return NULL;

#ifndef CHECK_INTEGER_USING_FORCE_NUMBER

	}

	/* a[3]=1; print "3" in a    -- true

	 * a[3]=1; print "+3" in a   -- false

	 * a[3]=1; print "03" in a   -- false

	 * a[-3]=1; print "-3" in a  -- true

	 */

	/* must be a STRING */

	char *cp = subs->stptr, *cpend, *ptr;

	char save;

	size_t len = subs->stlen;

	if (len == 0 || (! isdigit((unsigned char) *cp) && *cp != '-'))

		return NULL;

	if (len > 1 &&

		((*cp == '0')		/* "00", "011" .. */

			|| (*cp == '-' && *(cp + 1) == '0')	/* "-0", "-011" .. */

		)

	)

		return NULL;

	if (len == 1 && *cp != '-') {	/* single digit */

		subs->numbr = (long) (*cp - '0');

		if ((subs->flags & USER_INPUT) != 0) {

			/* leave USER_INPUT set */

			subs->flags &= ~STRING;

			subs->flags |= NUMBER;

		}

		subs->flags |= (NUMCUR|NUMINT);

		return & success_node;

	}

	cpend = cp + len;

	save = *cpend;

	*cpend = '\0';

	errno = 0;

	l = strtol(cp, & ptr, 10);

	*cpend = save;

	if (errno != 0 || ptr != cpend)

		return NULL;

	subs->numbr = l;

	if ((subs->flags & USER_INPUT) != 0) {

		/* leave USER_INPUT set */

		subs->flags &= ~STRING;

		subs->flags |= NUMBER;

	}

	subs->flags |= NUMCUR;

	if (l <= INT32_MAX && l >= INT32_MIN) {

		subs->flags |= NUMINT;

		return & success_node;

	}

	return NULL;

#endif /* CHECK_INTEGER_USING_FORCE_NUMBER */

}

/*

 * int_lookup --- 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.

 */

static NODE **

int_lookup(NODE *symbol, NODE *subs)

{

	uint32_t hash1;

	long k;

	unsigned long size;

	NODE **lhs;

	NODE *xn;

	/*

	 * N.B: symbol->table_size is the total # of non-integers (symbol->xarray)

	 *	and integer elements. Also, symbol->xarray must have at least one

	 *	item in it, and can not exist if there are no integer elements.

	 * 	In that case, symbol->xarray is promoted to 'symbol' (See int_remove).

	 */

	if (! is_integer(symbol, subs)) {

		xn = symbol->xarray;

		if (xn == NULL) {

			xn = symbol->xarray = make_array();

			xn->vname = symbol->vname;	/* shallow copy */

			xn->flags |= XARRAY;

		} else if ((lhs = xn->aexists(xn, subs)) != NULL)

			return lhs;

		symbol->table_size++;

		return assoc_lookup(xn, subs);

	}

	k = subs->numbr;

	if (symbol->buckets == NULL)

		grow_int_table(symbol);

 	hash1 = int_hash(k, symbol->array_size);

	if ((lhs = int_find(symbol, k, hash1)) != NULL)

		return lhs;

	/* It's not there, install it */

	symbol->table_size++;

	/* first see if we would need to grow the array, before installing */

	size = symbol->table_size;

	if ((xn = symbol->xarray) != NULL)

		size -= xn->table_size;

	if ((symbol->flags & ARRAYMAXED) == 0

		    && (size / symbol->array_size) > INT_CHAIN_MAX) {

		grow_int_table(symbol);

		/* have to recompute hash value for new size */

		hash1 = int_hash(k, symbol->array_size);

	}

	return int_insert(symbol, k, hash1);

}

/*

 * int_exists --- test whether the array element symbol[subs] exists or not,

 *	return pointer to value if it does.

 */

static NODE **

int_exists(NODE *symbol, NODE *subs)

{

	long k;

	uint32_t hash1;

	if (! is_integer(symbol, subs)) {

		NODE *xn = symbol->xarray;

		if (xn == NULL)

			return NULL;

		return xn->aexists(xn, subs);

	}

	if (symbol->buckets == NULL)

		return NULL;

	k = subs->numbr;

	hash1 = int_hash(k, symbol->array_size);

	return int_find(symbol, k, hash1);

}

/* int_clear --- flush all the values in symbol[] */

static NODE **

int_clear(NODE *symbol, NODE *subs ATTRIBUTE_UNUSED)

{

	unsigned long i;

	int j;

	BUCKET *b, *next;

	NODE *r;

	if (symbol->xarray != NULL) {

		NODE *xn = symbol->xarray;

		assoc_clear(xn);

		freenode(xn);

		symbol->xarray = NULL;

	}

	for (i = 0; i < symbol->array_size; i++) {

		for (b = symbol->buckets[i]; b != NULL;	b = next) {

			next = b->ainext;

			for (j = 0; j < b->aicount; j++) {

				r = b->aivalue[j];

				if (r->type == Node_var_array) {

					assoc_clear(r);	/* recursively clear all sub-arrays */

					efree(r->vname);

					freenode(r);

				} else

					unref(r);

			}

			freebucket(b);

		}

		symbol->buckets[i] = NULL;

	}

	if (symbol->buckets != NULL)

		efree(symbol->buckets);

	symbol->ainit(symbol, NULL);	/* re-initialize symbol */

	return NULL;

}

/* int_remove --- If SUBS is already in the table, remove it. */

static NODE **

int_remove(NODE *symbol, NODE *subs)

{

	uint32_t hash1;

	BUCKET *b, *prev = NULL;

	long k;

	int i;

	NODE *xn = symbol->xarray;

	if (symbol->table_size == 0 || symbol->buckets == NULL)

		return NULL;

	if (! is_integer(symbol, subs)) {

		if (xn == NULL || xn->aremove(xn, subs) == NULL)

			return NULL;

		if (xn->table_size == 0) {

			freenode(xn);

			symbol->xarray = NULL;

		}

		symbol->table_size--;

		assert(symbol->table_size > 0);

		return & success_node;

	}

	k = subs->numbr;

	hash1 = int_hash(k, symbol->array_size);

	for (b = symbol->buckets[hash1]; b != NULL; prev = b, b = b->ainext) {

		for (i = 0; i < b->aicount; i++) {

			if (k != b->ainum[i])

				continue;

			/* item found */

			if (i == 0 && b->aicount == 2) {

				/* removing the 1st item; move 2nd item from position 1 to 0 */

				b->ainum[0] = b->ainum[1];

				b->aivalue[0] = b->aivalue[1];

			} /* else

				removing the only item or the 2nd item */

			goto removed;

		}

	}

	if (b == NULL)	/* item not in array */

		return NULL;

removed:

	b->aicount--;

	if (b->aicount == 0) {

		/* detach bucket */

		if (prev != NULL)

			prev->ainext = b->ainext;

		else

			symbol->buckets[hash1] = b->ainext;

		/* delete bucket */

		freebucket(b);

	} else if (b != symbol->buckets[hash1]) {

		BUCKET *head = symbol->buckets[hash1];

		assert(b->aicount == 1);

		/* move the last element from head to bucket to make it full. */

		i = --head->aicount;	/* head has one less element */

		b->ainum[1] = head->ainum[i];

		b->aivalue[1] = head->aivalue[i];

		b->aicount++;	/* bucket has one more element */

		if (i == 0) {

			/* head is now empty; delete head */

			symbol->buckets[hash1] = head->ainext;

			freebucket(head);

		}

	} /* else

		do nothing */

	symbol->table_size--;

	if (xn == NULL && symbol->table_size == 0) {

		efree(symbol->buckets);

		symbol->ainit(symbol, NULL);	/* re-initialize array 'symbol' */

	} else if (xn != NULL && symbol->table_size == xn->table_size) {

		/* promote xn (str_array) to symbol */

		xn->flags &= ~XARRAY;

		xn->parent_array = symbol->parent_array;

		efree(symbol->buckets);

		*symbol = *xn;

		freenode(xn);

	}

	return & success_node;	/* return success */

}

/* int_copy --- duplicate input array "symbol" */

static NODE **

int_copy(NODE *symbol, NODE *newsymb)

{

	BUCKET **old, **new, **pnew;

	BUCKET *chain, *newchain;

	int j;

	unsigned long i, cursize;

	assert(symbol->buckets != NULL);

	/* find the current hash size */

	cursize = symbol->array_size;

	/* allocate new table */

	ezalloc(new, BUCKET **, cursize * sizeof(BUCKET *), "int_copy");

	old = symbol->buckets;

	for (i = 0; i < cursize; i++) {

		for (chain = old[i], pnew = & new[i]; chain != NULL;

				chain = chain->ainext

		) {

			getbucket(newchain);

			newchain->aicount = chain->aicount;

			newchain->ainext = NULL;

			for (j = 0; j < chain->aicount; j++) {

				NODE *oldval;

				/*

				 * copy the corresponding key and

				 * value from the original input list

				 */

				newchain->ainum[j] = chain->ainum[j];

				oldval = chain->aivalue[j];

				if (oldval->type == Node_val)

					newchain->aivalue[j] = dupnode(oldval);

				else {

					NODE *r;

					r = make_array();

					r->vname = estrdup(oldval->vname, strlen(oldval->vname));

					r->parent_array = newsymb;

					newchain->aivalue[j] = assoc_copy(oldval, r);

				}

			}

			*pnew = newchain;

			newchain->ainext = NULL;

			pnew = & newchain->ainext;

		}

	}

	if (symbol->xarray != NULL) {

		NODE *xn, *n;

		xn = symbol->xarray;

		n = make_array();

		n->vname = newsymb->vname;	/* shallow copy */

		(void) xn->acopy(xn, n);

		newsymb->xarray = n;

	} else

		newsymb->xarray = NULL;

	newsymb->table_size = symbol->table_size;

	newsymb->buckets = new;

	newsymb->array_size = cursize;

	newsymb->flags = symbol->flags;

	return NULL;

}

/* int_list --- return a list of array items */

static NODE**

int_list(NODE *symbol, NODE *t)

{

	NODE **list = NULL;

	unsigned long num_elems, list_size, i, k = 0;

	BUCKET *b;

	NODE *r, *subs, *xn;

	int j, elem_size = 1;

	long num;

	static char buf[100];

	assoc_kind_t assoc_kind;

	if (symbol->table_size == 0)

		return NULL;

	assoc_kind = (assoc_kind_t) t->flags;

	num_elems = symbol->table_size;

	if ((assoc_kind & (AINDEX|AVALUE|ADELETE)) == (AINDEX|ADELETE))

		num_elems = 1;

	if ((assoc_kind & (AINDEX|AVALUE)) == (AINDEX|AVALUE))

		elem_size = 2;

	list_size = elem_size * num_elems;

	if (symbol->xarray != NULL) {

		xn = symbol->xarray;

		list = xn->alist(xn, t);

		assert(list != NULL);

		if (num_elems == 1 || num_elems == xn->table_size)

			return list;

		erealloc(list, NODE **, list_size * sizeof(NODE *), "int_list");

		k = elem_size * xn->table_size;

	} else

		emalloc(list, NODE **, list_size * sizeof(NODE *), "int_list");

	/* populate it */

	for (i = 0; i < symbol->array_size; i++) {

		for (b = symbol->buckets[i]; b != NULL;	b = b->ainext) {

			for (j = 0; j < b->aicount; j++) {

				/* index */

				num = b->ainum[j];

				if ((assoc_kind & AISTR) != 0) {

					sprintf(buf, "%ld", num);

					subs = make_string(buf, strlen(buf));

					subs->numbr = num;

					subs->flags |= (NUMCUR|NUMINT);

				} else {

					subs = make_number((AWKNUM) num);

					subs->flags |= (INTIND|NUMINT);

				}

				list[k++] = subs;

				/* value */

				if ((assoc_kind & AVALUE) != 0) {

					r = b->aivalue[j];

					if (r->type == Node_val) {

						if ((assoc_kind & AVNUM) != 0)

							(void) force_number(r);

						else if ((assoc_kind & AVSTR) != 0)

							r = force_string(r);

					}

					list[k++] = r;

				}

				if (k >= list_size)

					return list;

			}

		}

	}

	return list;

}

/* int_kilobytes --- calculate memory consumption of the assoc array */

AWKNUM

int_kilobytes(NODE *symbol)

{

	unsigned long i, bucket_cnt = 0;

	BUCKET *b;

	AWKNUM kb;

	extern AWKNUM str_kilobytes(NODE *symbol);

	for (i = 0; i < symbol->array_size; i++) {

		for (b = symbol->buckets[i]; b != NULL; b = b->ainext)

			bucket_cnt++;

	}

	kb = (((AWKNUM) bucket_cnt) * sizeof (BUCKET) +

			((AWKNUM) symbol->array_size) * sizeof (BUCKET *)) / 1024.0;

	if (symbol->xarray != NULL)

		kb += str_kilobytes(symbol->xarray);

	return kb;

}

/* int_dump --- dump array info */

static NODE **

int_dump(NODE *symbol, NODE *ndump)

{

#define HCNT	31

	int indent_level;

	BUCKET *b;

	NODE *xn = NULL;

	unsigned long str_size = 0, int_size = 0;

	unsigned long i;

	size_t j, bucket_cnt;

	static size_t hash_dist[HCNT + 1];

	indent_level = ndump->alevel;

	if (symbol->xarray != NULL) {

		xn = symbol->xarray;

		str_size = xn->table_size;

	}

	int_size = symbol->table_size - str_size;

	if ((symbol->flags & XARRAY) == 0)

		fprintf(output_fp, "%s `%s'\n",

				(symbol->parent_array == NULL) ? "array" : "sub-array",

				array_vname(symbol));

	indent_level++;

	indent(indent_level);

	fprintf(output_fp, "array_func: int_array_func\n");

	if (symbol->flags != 0) {

		indent(indent_level);

		fprintf(output_fp, "flags: %s\n", flags2str(symbol->flags));

	}

	indent(indent_level);

	fprintf(output_fp, "INT_CHAIN_MAX: %lu\n", (unsigned long) INT_CHAIN_MAX);

	indent(indent_level);

	fprintf(output_fp, "array_size: %lu (int)\n", (unsigned long) symbol->array_size);

	indent(indent_level);

	fprintf(output_fp, "table_size: %lu (total), %lu (int), %lu (str)\n",

			(unsigned long) symbol->table_size, int_size, str_size);

	indent(indent_level);

	fprintf(output_fp, "Avg # of items per chain (int): %.2g\n",

			((AWKNUM) int_size) / symbol->array_size);

	indent(indent_level);

	fprintf(output_fp, "memory: %.2g kB (total)\n", int_kilobytes(symbol));

	/* hash value distribution */

	memset(hash_dist, '\0', (HCNT + 1) * sizeof(size_t));

	for (i = 0; i < symbol->array_size; i++) {

		bucket_cnt = 0;

		for (b = symbol->buckets[i]; b != NULL;	b = b->ainext)

			bucket_cnt += b->aicount;

		if (bucket_cnt >= HCNT)

			bucket_cnt = HCNT;

		hash_dist[bucket_cnt]++;

	}

	indent(indent_level);

	fprintf(output_fp, "Hash distribution:\n");

	indent_level++;

	for (j = 0; j <= HCNT; j++) {

		if (hash_dist[j] > 0) {

			indent(indent_level);

			if (j == HCNT)

				fprintf(output_fp, "[>=%lu]:%lu\n",

					(unsigned long) HCNT, (unsigned long) hash_dist[j]);

			else

				fprintf(output_fp, "[%lu]:%lu\n",

					(unsigned long) j, (unsigned long) hash_dist[j]);

		}

	}

	indent_level--;

	/* dump elements */

	if (ndump->adepth >= 0) {

		NODE *subs;

		const char *aname;

		fprintf(output_fp, "\n");

		aname = make_aname(symbol);

		subs = make_number((AWKNUM) 0);

		subs->flags |= (INTIND|NUMINT);

		for (i = 0; i < symbol->array_size; i++) {

			for (b = symbol->buckets[i]; b != NULL; b = b->ainext) {

				for (j = 0; j < b->aicount; j++) {

					subs->numbr = b->ainum[j];

					assoc_info(subs, b->aivalue[j], ndump, aname);

				}

			}

		}

		unref(subs);

	}

	if (xn != NULL)	{

		fprintf(output_fp, "\n");

		xn->adump(xn, ndump);

	}

	return NULL;

#undef HCNT

}

/* int_hash --- calculate the hash function of the integer subs */

static uint32_t

int_hash(uint32_t k, uint32_t hsize)

{

/*

 * Code snippet copied from:

 *	Hash functions (http://www.azillionmonkeys.com/qed/hash.html).

 *	Copyright 2004-2008 by Paul Hsieh. Licenced under LGPL 2.1.

 */

	/* This is the final mixing function used by Paul Hsieh in SuperFastHash. */

	k ^= k << 3;

	k += k >> 5;

	k ^= k << 4;

	k += k >> 17;

	k ^= k << 25;

	k += k >> 6;

	if (k >= hsize)

		k %= hsize;

	return k;

}

/* int_find --- locate symbol[subs] */

static inline NODE **

int_find(NODE *symbol, long k, uint32_t hash1)

{

	BUCKET *b;

	int i;

	assert(symbol->buckets != NULL);

	for (b = symbol->buckets[hash1]; b != NULL; b = b->ainext) {

		for (i = 0; i < b->aicount; i++) {

			if (b->ainum[i] == k)

				return (b->aivalue + i);

		}

	}

	return NULL;

}

/* int_insert --- install subs in the assoc array */

static NODE **

int_insert(NODE *symbol, long k, uint32_t hash1)

{

	BUCKET *b;

	int i;

	b = symbol->buckets[hash1];

	/* Only the first bucket in the chain can be partially full, but is never empty. */

	if (b == NULL || (i = b->aicount) == 2) {

		getbucket(b);

		b->aicount = 0;

		b->ainext = symbol->buckets[hash1];

		symbol->buckets[hash1] = b;

		i = 0;

	}

	b->ainum[i] = k;

	b->aivalue[i] = dupnode(Nnull_string);

	b->aicount++;

	return & b->aivalue[i];

}

/* grow_int_table --- grow the hash table */

static void

grow_int_table(NODE *symbol)

{

	BUCKET **old, **new;

	BUCKET *chain, *next;

	int i, j;

	unsigned long oldsize, newsize, k;

	/*

	 * This is an array of primes. We grow the table by an order of

	 * magnitude each time (not just doubling) so that growing is a

	 * rare operation. We expect, on average, that it won't happen

	 * more than twice.  The final size is also chosen to be small

	 * enough so that MS-DOG mallocs can handle it. When things are

	 * very large (> 8K), we just double more or less, instead of

	 * just jumping from 8K to 64K.

	 */

	static const unsigned long sizes[] = {

		13, 127, 1021, 8191, 16381, 32749, 65497,

		131101, 262147, 524309, 1048583, 2097169,

		4194319, 8388617, 16777259, 33554467,

		67108879, 134217757, 268435459, 536870923,

		1073741827

	};

	/* find next biggest hash size */

	newsize = oldsize = symbol->array_size;

	for (i = 0, j = sizeof(sizes)/sizeof(sizes[0]); i < j; i++) {

		if (oldsize < sizes[i]) {

			newsize = sizes[i];

			break;

		}

	}

	if (newsize == oldsize) {	/* table already at max (!) */

		symbol->flags |= ARRAYMAXED;

		return;

	}

	/* allocate new table */

	ezalloc(new, BUCKET **, newsize * sizeof(BUCKET *), "grow_int_table");

	old = symbol->buckets;

	symbol->buckets = new;

	symbol->array_size = newsize;

	/* brand new hash table */

	if (old == NULL)

		return;		/* DO NOT initialize symbol->table_size */

	/* old hash table there, move stuff to new, free old */

	/* note that symbol->table_size does not change if an old array. */

	for (k = 0; k < oldsize; k++) {

		long num;

		for (chain = old[k]; chain != NULL; chain = next) {

			for (i = 0; i < chain->aicount; i++) {

				num = chain->ainum[i];

				*int_insert(symbol, num, int_hash(num, newsize)) = chain->aivalue[i];

			}

			next = chain->ainext;

			freebucket(chain);

		}

	}

	efree(old);

}