#include <varargs.h>
#include <stdio.h>
#include <setjmp.h>
#include <string.h>
#include <ctype.h>
#include <sys/time.h>
#include <sys/types.h>		/* sys/types.h and netinet/in.h are here to enable include of comm.h below */
#include <sys/stat.h>
/* #include <netinet/in.h> Included in comm.h below */
#include <memory.h>
#include <stdio.h>

#include "config.h"
#include "lint.h"
#include "exec.h"
#include "interpret.h"
#include "object.h"
#include "instrs.h"
#include "patchlevel.h"
#include "comm.h"
#include "switch.h"
#include "mapping.h"

#define EQSVALUE(ret,x,y) \
	if ((x)->type != (y)->type) {\
	    ret = 0;\
	} else {\
            switch((y)->type) {\
	    case T_NUMBER:\
		ret = (x)->u.number == (y)->u.number;\
		break;\
	    case T_POINTER:\
		ret = (x)->u.vec == (y)->u.vec;\
		break;\
	    case T_MAPPING:\
		ret = (x)->u.map == (y)->u.map;\
		break;\
	    case T_STRING:\
		if ((x)->string_type == STRING_SHARED && (y)->string_type == STRING_SHARED) \
		    ret = (x)->u.string == (y)->u.string; \
		else \
		    ret = (x)->u.string == (y)->u.string || strcmp((x)->u.string, (y)->u.string) == 0;\
		break;\
	    case T_OBJECT:\
		ret = (x)->u.ob == (y)->u.ob;\
		break;\
            case T_FLOAT:\
		ret = (x)->u.real == (y)->u.real;\
		break; \
	    default:\
		ret = 0;\
		break;\
	    }\
	}

extern struct svalue const0, const1;
static void rehash_map();

/* rehash when the mapping is filled to this many % */
#define FILL_FACTOR 250
#define FSIZE(s) (((s)*FILL_FACTOR)/100)
int num_mappings = 0, total_mapping_size = 0;

#if 0
void
abortmap(char *s)
{
    fprintf(stderr, "Mapping %s\n", s);
    error("Mappings not implemented");
}
#endif

void
free_apairs(struct apair *p)
{
    struct apair *next;
    
    for (;p;p = next) {
	free_svalue(&p->arg);
	free_svalue(&p->val);
	next = p->next;
	free((char *)p);
	total_mapping_size -= sizeof(struct apair);
    }
}

void
free_mapping(struct mapping *m)
{
    int i;

    m->ref--;
    if (m->ref > 0)
	return;
    for (i = 0; i < m->size; i++)
	free_apairs(m->pairs[i]);
    num_mappings--;
    total_mapping_size -= (sizeof(struct apair *) * m->size + 
			   sizeof(struct mapping));
    free((char *)m->pairs);
    free((char *)m);
}

struct mapping *
allocate_map(int msize)
{
    struct mapping *m;
    unsigned u;
    int size;

    for(size = 1, u = (msize*100)/FILL_FACTOR; u && size < MAX_MAPPING_SIZE; size <<= 1, u >>= 1)
	;

    num_mappings++;
    m = (struct mapping *) xalloc(sizeof(struct mapping));
    m->pairs = (struct apair **) xalloc(sizeof(struct apair *) * size);
    memset(m->pairs, 0, sizeof(struct apair *) * size);
    total_mapping_size += sizeof(struct mapping) + sizeof(struct apair *) * size;
    m->ref = 1;
    m->card = 0;
    m->size = size;
    m->mcard = FSIZE(m->size);

    return m;
}

int
card_mapping(struct mapping *m)
{
    return m->card;
}

static INLINE struct apair *
newpair(struct apair *n, struct svalue *k, struct svalue *v, int h)
{
    struct apair *p = (struct apair *)xalloc(sizeof(struct apair));
    p->next = n;
    p->hashval = h;
    assign_svalue_no_free(&p->arg, k);
    assign_svalue_no_free(&p->val, v);
    total_mapping_size += sizeof(struct apair);
    return p;
}

static INLINE int
hashsvalue(struct svalue *v)
{
    switch(v->type) {
    case T_NUMBER:
	return (unsigned short)v->u.number;
    case T_POINTER:
	return (unsigned short)((unsigned long)v->u.vec >> 4);
    case T_MAPPING:
	return (unsigned short)((unsigned long)v->u.map >> 4);
    case T_STRING:
	return hashstr16(v->u.string, 20);
    case T_OBJECT:
	return (unsigned short)((unsigned long)v->u.ob >> 4);
    case T_FLOAT:
	return (unsigned short)v->u.number;
    default:
        return 0;
    }
}

struct svalue *
get_map_lvalue(struct mapping *m, struct svalue *k, int c)
{
    int h, h16;
    struct apair *p;
/*    static struct svalue zero;*/

    h16 = hashsvalue(k);
    h = h16 & (m->size-1);

    for(p = m->pairs[h]; p; p = p->next) {
	int r;
	EQSVALUE(r, k, &p->arg);
	if (r)
	    break;
    }
    if (!p) {
	if (c) {
	    m->pairs[h] = p = newpair(m->pairs[h], k, &const0, h16);
	    if (++m->card > m->mcard) {
		/* We need to extend the hash table */
		rehash_map(m);
	    }
	} else {
	    /* Just in case! */
	    /*zero = const0;
	    return &zero;*/
	    return &const0;
	}
    }
    return &p->val;
}

struct vector *
map_domain(m)
struct mapping *m;
{
    struct vector *d;
    int cnt;
    int i;
    int k;
    struct apair *p;
    
    cnt = m->card;
    d = allocate_array(cnt);
    for (k = 0, i = 0; i < m->size; i++)
	for(p = m->pairs[i]; p; p = p->next)
	    assign_svalue_no_free (&d->item[k++], &p->arg);
    return d;
}

struct vector *
map_codomain(struct mapping *m)
{
    struct vector *d;
    int cnt;
    int i;
    int k;
    struct apair *p;
    
    cnt = m->card;
    d = allocate_array(cnt);
    for (k = 0, i = 0; i < m->size; i++)
	for(p = m->pairs[i]; p; p = p->next)
	    assign_svalue_no_free(&d->item[k++], &p->val);
    return d;
}

struct mapping *
make_mapping(struct vector *ind, struct vector *val)
{
    struct mapping *m;
    struct svalue tmp;
    int i, max;

    tmp.type = T_NUMBER;

    if (ind != NULL && val != NULL) {
	max = ind->size < val->size ? ind->size : val->size;
	m = allocate_map(max);
	for (i = 0 ; i < max ; i++)
	{
	    assign_svalue(get_map_lvalue(m, &ind->item[i], 1), 
				  &val->item[i]);
	}
    } else if (ind != NULL && val == NULL) {
	m = allocate_map(ind->size);
	for (i = 0 ; i < ind->size ; i++)
	{
	    tmp.u.number = i;
	    assign_svalue(get_map_lvalue(m, &ind->item[i], 1), &tmp);
	}
    } else if (ind == NULL && val != NULL) {
	m = allocate_map(val->size);
	for (i = 0 ; i < val->size ; i++)
	{
	    tmp.u.number = i;
	    assign_svalue_no_free(get_map_lvalue(m, &tmp, 1), &val->item[i]);
	}
    } else {
	m = allocate_map(0);
    }

    return m;
}

struct mapping *
add_mapping(struct mapping *m1, struct mapping *m2)
{
    int i;
    struct apair *p;
    struct mapping *retm;

    retm = allocate_map(m1->card + m2->card);

    for (i = 0 ; i < m1->size ; i++)
    {
	for (p = m1->pairs[i]; p ; p = p->next)
	    assign_svalue(get_map_lvalue(retm, &p->arg, 1), &p->val);
    }
    for (i = 0 ; i < m2->size ; i++)
    {
	for (p = m2->pairs[i]; p ; p = p->next)
	    assign_svalue(get_map_lvalue(retm, &p->arg, 1), &p->val);
    }
    return retm;
}

void
addto_mapping(struct mapping *m1, struct mapping *m2)
{
    int i;
    struct apair *p;

    for (i = 0 ; i < m2->size ; i++)
    {
	for (p = m2->pairs[i]; p ; p = p->next)
	    assign_svalue(get_map_lvalue(m1, &p->arg, 1), &p->val);
    }
}

struct mapping *
remove_mapping(struct mapping *m, struct svalue *val)
{
    struct mapping *retm;
    struct apair *p, *prev;
    int r, i, h;

    retm = allocate_map(m->size);
    h = hashsvalue(val) & (m->size-1);

    prev = NULL;
    for (i = 0 ; i < m->size ; i++)
    {
	for (p = m->pairs[i] ; p ; p = p->next)
	{
	    if (h == i)
	    {
		EQSVALUE(r, val, &p->arg);
		if (!r)
		    assign_svalue_no_free(get_map_lvalue(retm, &p->arg, 1), &p->val);
	    }
	    else
		assign_svalue_no_free(get_map_lvalue(retm, &p->arg, 1), &p->val);
	}
    }
    return retm;
}

static void
rehash_map(struct mapping *map)
{
    register struct apair **pairs, *next, *ptr;
    int i, hval;
    int nsize;

    nsize = map->size * 2;
    if (nsize > MAX_MAPPING_SIZE) {
	error("Warning, too large mapping.\n");
	return;
    }

    pairs = (struct apair **)xalloc(sizeof(struct apair *) * nsize);
    memset(pairs, 0, sizeof(struct apair *) * nsize);

    for (i = 0 ; i < map->size ; i++) {
	for (ptr = map->pairs[i]; ptr; ptr = next) {
	    hval = ptr->hashval & (nsize-1);
	    next = ptr->next;
	    ptr->next = pairs[hval];
	    pairs[hval] = ptr;
	}
    }

    free((char *)map->pairs);
    map->pairs = pairs;
    total_mapping_size += sizeof(struct apair *) * (nsize - map->size);
    map->size = nsize;
    map->mcard = FSIZE(map->size);
}


struct mapping *
copy_mapping(struct mapping *m)
{
    struct mapping *cm;
    struct apair *pair;
    int i;
    
    num_mappings++;
    cm = (struct mapping *) xalloc(sizeof(struct mapping));
    cm->pairs = (struct apair **) xalloc(sizeof(struct apair *) * m->size);
    memset(cm->pairs, 0, sizeof(struct apair *) * m->size);
    total_mapping_size += sizeof(struct mapping) + sizeof(struct apair *) * m->size;
    cm->ref = 1;
    cm->size = m->size;
    cm->card = m->card;
    cm->mcard = m->mcard;
    for (i = 0; i < m->size; i++)
	for(pair = m->pairs[i]; pair; pair = pair->next)
	    cm->pairs[i] = newpair(cm->pairs[i], &pair->arg, &pair->val, pair->hashval);
    return cm;
}

extern jmp_buf error_recovery_context;
extern int error_recovery_context_exists;

/* Runs all codomain elements of a mapping through ob::func
   and replaces each value in the codomain map by the value returned 
   by ob::func
   */
struct mapping *
map_map(struct mapping *map, char *func, struct object *ob,
	struct svalue *extra)
{
    struct mapping *r;
    struct svalue *v;
    struct apair *p;
    int i;
    char *cprogn, *srcpos;
    short funcix;
    jmp_buf save_error_recovery_context;
    int save_rec_exists;
    extern struct program *current_prog;

    r = allocate_map(map->card);

    if (map->card < 1) 
	return r;
/*    srcpos = get_srccode_position_if_any(); */
    cprogn = current_prog->name;

    memcpy((char *) save_error_recovery_context,
	   (char *) error_recovery_context, sizeof error_recovery_context);
    save_rec_exists = error_recovery_context_exists;
    error_recovery_context_exists = 1;
    
    for (i = 0 ; i < map->size ; i++)
    {
	for(p = map->pairs[i]; p ; p = p->next)
	{
	    if (setjmp(error_recovery_context)) 
	    {
		free_mapping(r);
		memcpy((char *) error_recovery_context,
		       (char *) save_error_recovery_context,
		       sizeof error_recovery_context);
		error_recovery_context_exists = save_rec_exists;
		error("Error in map_map(), (%s) %s::%s (File: %s)\n", 
		      ob->name, cprogn, func, "...deleted...");
/*
		error("Error in map_map(), (%s) %s::%s (File: %s)\n", 
		      ob->name, cprogn, func, srcpos);
*/
	    }
	    else
	    {
		if (ob->flags & O_DESTRUCTED)
		    error("object used by map_array destructed");
		push_svalue(&p->val);
		if (extra)
		{
		    push_svalue (extra);
		    v = apply(func, ob, 2, ob != current_object);
		}
		else 
		{
		    v = apply(func, ob, 1, ob != current_object);
		}
	    }
	    if (v)
		assign_svalue_no_free(get_map_lvalue(r, &p->arg, 1), v);
	}
    }
    memcpy((char *) error_recovery_context,
	   (char *) save_error_recovery_context,
	   sizeof error_recovery_context);
    error_recovery_context_exists = save_rec_exists;

    return r;
}


/* EFUN: filter (mapping part)
   
   Runs all codomaing elements of an map through ob->func()
   and returns a mapping holding those elements that ob->func
   returned 1 for.
   */
struct mapping *
filter_map(struct mapping *m, char *func, struct object *ob,
	   struct svalue *extra)
{
    struct mapping *r;
    struct svalue *v;
    struct apair *p;
    char *flags;
    int i, f_ix;
    short funcix;
    int fsize;

    if (m->card < 1)
    {
	m->ref++;
	return m;
    }

    flags = tmpalloc(m->card + 1); 

    for (fsize = 0, funcix = 0, f_ix = 0, i = 0 ; i < m->size ; i++)
    {
	for(p = m->pairs[i]; p ; p = p->next)
	{
	    if (ob->flags & O_DESTRUCTED)
		error("object used by filter() (map) destructed");
	    push_svalue(&p->val);
	    if (extra) 
	    {
		push_svalue(extra);
		v = apply(func, ob, 2, ob != current_object);
	    } 
	    else 
	    {
		v = apply(func, ob, 1, ob != current_object);
	    }
	    if (v && v->type == T_NUMBER && v->u.number) 
		flags[f_ix++] = 1, fsize++;
	    else
		flags[f_ix++] = 0;
	    if (f_ix > m->card)
		error("Mapping cardinality changed during map()\n");
	}
    }

    r = allocate_map(fsize);
    for (f_ix = 0, i = 0 ; i < m->size ; i++)
    {
	for(p = m->pairs[i]; p ; p = p->next)
	{
	    if (ob->flags & O_DESTRUCTED)
		error("object used by filter() (map) destructed");
	    if (flags[f_ix++])
		assign_svalue_no_free(get_map_lvalue(r, &p->arg, 1),
				      &p->val);
	    if (f_ix > m->card)
		fatal("Mapping cardinality is wrong in filter()\n");
	}
    }
    tmpfree(flags);
    return r;
}