#include <stdlib.h>
#include <string.h>

#include "array.h"
#include "mode.h"
#include "place.h"
#include "macro.h"

struct macro {
	struct place defplace;
	struct place expansionplace;
	unsigned hash;
	char *name;
	char *expansion;
};
DECLARRAY(macro);
DEFARRAY(macro, );
DECLARRAY(macroarray);
DEFARRAY(macroarray, );

static struct macroarrayarray macros;
static unsigned total_macros;
static unsigned hashmask;

////////////////////////////////////////////////////////////
// macro structure ops

static
struct macro *
macro_create(struct place *p1, struct place *p2, unsigned hash,
	     const char *name, const char *expansion)
{
	struct macro *m;

	m = domalloc(sizeof(*m));
	m->defplace = *p1;
	m->expansionplace = *p2;
	m->hash = hash;
	m->name = dostrdup(name);
	m->expansion = dostrdup(expansion);
	return m;
}

static
void
macro_destroy(struct macro *m)
{
	free(m->name);
	free(m->expansion);
	free(m);
}

////////////////////////////////////////////////////////////
// macro table

/*
 * Unless I've screwed up, this is something called Fletcher's Checksum
 * that showed up in Dr. Dobbs in, according to my notes, May 1992. The
 * implementation is new.
 */
static
unsigned
hashfunc(const char *s)
{
	uint16_t x1, x2, a;
	size_t i, len;

	len = strlen(s);

	x1 = (uint16_t) (len >> 16);
	x2 = (uint16_t) (len);
	if (x1==0) {
		x1++;
	}
	if (x2==0) {
		x2++;
	}

	for (i=0; i<len; i+=2) {
		if (i==len-1) {
			a = (unsigned char)s[i];
			/* don't run off the end of the array */
		}
		else {
			a = (unsigned char)s[i] +
				((uint16_t)(unsigned char)s[i+1] << 8);
		}
		x1 += a;
		if (x1 < a) {
			x1++;
		}
		x2 += x1;
		if (x2 < x1) {
			x2++;
		}
	}

	x1 ^= 0xffff;
	x2 ^= 0xffff;
	return ((uint32_t)x2)*65535U + x1;
}

static
void
macrotable_init(void)
{
	unsigned i;

	macroarrayarray_init(&macros);
	macroarrayarray_setsize(&macros, 4);
	for (i=0; i<4; i++) {
		macroarrayarray_set(&macros, i, NULL);
	}
	total_macros = 0;
	hashmask = 0x3;
}

DESTROYALL_ARRAY(macro, );

static
void
macrotable_cleanup(void)
{
	struct macroarray *bucket;
	unsigned numbuckets, i;

	numbuckets = macroarrayarray_num(&macros);
	for (i=0; i<numbuckets; i++) {
		bucket = macroarrayarray_get(&macros, i);
		macroarray_destroyall(bucket);
		macroarray_destroy(bucket);
	}
	macroarrayarray_setsize(&macros, 0);
	macroarrayarray_cleanup(&macros);
}

static
struct macro *
macrotable_find(const char *name, bool remove)
{
	unsigned hash;
	struct macroarray *bucket;
	struct macro *m, *m2;
	unsigned i, num;

	hash = hashfunc(name);
	bucket = macroarrayarray_get(&macros, hash & hashmask);
	if (bucket == NULL) {
		return NULL;
	}
	num = macroarray_num(bucket);
	for (i=0; i<num; i++) {
		m = macroarray_get(bucket, i);
		if (hash != m->hash) {
			continue;
		}
		if (!strcmp(name, m->name)) {
			if (remove) {
				if (i < num-1) {
					m2 = macroarray_get(bucket, num-1);
					macroarray_set(bucket, i, m2);
				}
				macroarray_setsize(bucket, num-1);
				total_macros--;
			}
			return m;
		}
	}
	return NULL;
}

static
void
macrotable_rehash(void)
{
	struct macroarray *newbucket, *oldbucket;
	struct macro *m;
	unsigned newmask, tossbit;
	unsigned numbuckets, i;
	unsigned oldnum, j, k;

	numbuckets = macroarrayarray_num(&macros);
	macroarrayarray_setsize(&macros, numbuckets*2);

	assert(hashmask == numbuckets - 1);
	newmask = (hashmask << 1) | 1U;
	tossbit = newmask && ~hashmask;
	hashmask = newmask;

	for (i=0; i<numbuckets; i++) {
		newbucket = NULL;
		oldbucket = macroarrayarray_get(&macros, i);
		oldnum = macroarray_num(oldbucket);
		for (j=0; j<oldnum; j++) {
			m = macroarray_get(oldbucket, j);
			if (m->hash & tossbit) {
				if (newbucket == NULL) {
					newbucket = macroarray_create();
				}
				macroarray_set(oldbucket, j, NULL);
				macroarray_add(newbucket, m, NULL);
			}
		}
		for (j=k=0; j<oldnum; j++) {
			m = macroarray_get(oldbucket, j);
			if (m != NULL && k < j) {
				macroarray_set(oldbucket, k++, m);
			}
		}
		macroarray_setsize(oldbucket, k);
		macroarrayarray_set(&macros, numbuckets + i, newbucket);
	}
}

static
void
macrotable_add(struct macro *m)
{
	unsigned hash;
	struct macroarray *bucket;
	unsigned numbuckets;

	numbuckets = macroarrayarray_num(&macros);
	if (total_macros > 0 && total_macros / numbuckets > 9) {
		macrotable_rehash();
	}

	hash = hashfunc(m->name);
	bucket = macroarrayarray_get(&macros, hash & hashmask);
	if (bucket == NULL) {
		bucket = macroarray_create();
		macroarrayarray_set(&macros, hash & hashmask, bucket);
	}
	macroarray_add(bucket, m, NULL);
	total_macros++;
}

////////////////////////////////////////////////////////////
// external macro definition interface

void
macro_define(struct place *p1, const char *macro,
	     struct place *p2, const char *expansion)
{
	struct macro *m;

	m = macrotable_find(macro, false);
	if (m != NULL) {
		if (!strcmp(expansion, m->expansion)) {
			complain(p1, "Warning: redefinition of %s", macro);
			if (mode.werror) {
				complain_fail();
			}
			return;
		}
		complain(p1, "Redefinition of %s is not identical", macro);
		complain_fail();
		return;
	}

	m = macro_create(p1, p2, hashfunc(macro), macro, expansion);
	macrotable_add(m);
}

void
macro_undef(const char *macro)
{
	struct macro *m;

	m = macrotable_find(macro, true);
	if (m) {
		macro_destroy(m);
	}
}

bool
macro_isdefined(const char *macro)
{
	struct macro *m;

	m = macrotable_find(macro, false);
	return m != NULL;
}

////////////////////////////////////////////////////////////
// macro expansion

char *macroexpand(struct place *, char *buf, size_t len, bool honordefined);

void macro_sendline(struct place *, char *buf, size_t len);
void macro_sendeof(struct place *);

////////////////////////////////////////////////////////////
// module initialization

void
macros_init(void)
{
	macrotable_init();
}

void
macros_cleanup(void)
{
	macrotable_cleanup();
}