int_array.c

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

/* 
 * Copyright (C) 1986, 1988, 1989, 1991-2011 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);

array_ptr int_array_func[] = {
	int_array_init,
	is_integer,
	int_lookup,
	int_exists,
	int_clear,
	int_remove,
	int_list,
	int_copy,
	int_dump,
};


/* int_array_init --- check relevant environment variables */

static NODE **
int_array_init(NODE *symbol ATTRIBUTE_UNUSED, NODE *subs ATTRIBUTE_UNUSED)
{
	long newval;

	if ((newval = getenv_long("INT_CHAIN_MAX")) > 0)
		INT_CHAIN_MAX = newval;
	return (NODE **) ! NULL;
}


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

NODE **
is_integer(NODE *symbol, NODE *subs)
{
	long l;
	AWKNUM d;

	if (subs == Nnull_string || do_mpfr)
		return NULL;

	if ((subs->flags & NUMINT) != 0)
		return (NODE **) ! NULL;

	if ((subs->flags & NUMBER) != 0) {
		d = subs->numbr;
		if (d <= INT32_MAX && d >= INT32_MIN && d == (int32_t) d) {
			subs->flags |= NUMINT;
			return (NODE **) ! NULL;
		}
		return NULL;
	}

	/* 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
	 */

	if ((subs->flags & (STRING|STRCUR)) != 0) {
		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 & MAYBE_NUM) != 0) {
				subs->flags &= ~MAYBE_NUM;
				subs->flags |= NUMBER;
			}
			subs->flags |= (NUMCUR|NUMINT);
			return (NODE **) ! NULL;
		}

		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 & MAYBE_NUM) != 0) {
			subs->flags &= ~MAYBE_NUM;
			subs->flags |= NUMBER;
		}
		subs->flags |= NUMCUR;
		if (l <= INT32_MAX && l >= INT32_MIN) {
			subs->flags |= NUMINT;
			return (NODE **) ! NULL;
		}
	}
	return NULL;
}


/* 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);
	init_array(symbol);	/* re-initialize symbol */
	symbol->flags &= ~ARRAYMAXED;
	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 (NODE **) ! NULL;
	}

	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);
		init_array(symbol);	/* re-initialize array 'symbol' */
		symbol->flags &= ~ARRAYMAXED;
	} 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 (NODE **) ! NULL;	/* 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 */
	emalloc(new, BUCKET **, cursize * sizeof(BUCKET *), "int_copy");
	memset(new, '\0', cursize * sizeof(BUCKET *));

	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;
			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;
			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];

	if (symbol->table_size == 0)
		return NULL;

	num_elems = symbol->table_size;
	if ((t->flags & (AINDEX|AVALUE|ADELETE)) == (AINDEX|ADELETE))
		num_elems = 1;

	if ((t->flags & (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 (t->flags & AISTR) {
					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 (t->flags & AVALUE) {
					r = b->aivalue[j];
					if (r->type == Node_val) {
						if ((t->flags & AVNUM) != 0)
							(void) force_number(r);
						else if ((t->flags & 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 */
	emalloc(new, BUCKET **, newsize * sizeof(BUCKET *), "grow_int_table");
	memset(new, '\0', newsize * sizeof(BUCKET *));

	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);
}