#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "htab.h"

/* Allocate and return a pointer to a key. Type is KEY_INT or KEY_STR.
 * key is a NUL-terminated string if type is KEY_STR, it will be
 * truncated to KEYLEN bytes on overflow.  */

htab_key_t *htab_mk_key(void *key, int type) {
    htab_key_t *k;
    
    if ( (k = malloc(sizeof *k)) == NULL) {
	perror("Failed to allocate htab key");
	return NULL;
    }
    
    if (type == KEY_INT)
	k->key.as_int = *(int *)key;
    else if (type == KEY_STR) {
	strncpy(k->key.as_str, key, KEYLEN - 1);
	k->key.as_str[KEYLEN] = '\0';
    }
    else
	return NULL;
    k->type = type;
    
    return k;
}

/* Return 1 if k1 and k2 are equal keys */
int htab_keycmp(htab_key_t *k1, htab_key_t *k2) {
    if (k1->type == k2->type) {
	if (k1->type == KEY_INT)
	    return (k1->key.as_int == k2->key.as_int);
	else 
	    return (! strncmp(k1->key.as_str, k2->key.as_str, KEYLEN));
    }

    return 1;
}

/* Return an allocated string containing the textual representation of k */
char *htab_key2str(htab_key_t *k) {
    char *rc, str[KEYLEN];

    if (k->type == KEY_INT) {
	snprintf(str, KEYLEN, "%d", k->key.as_int);
	rc = strdup(str);
    }
    else
	rc = strdup(k->key.as_str);
    
    return rc;
}

static inline int htab_hash(htab_key_t *k, int len) {
    int i;

#define KSTR k->key.as_str
#define KINT k->key.as_int
    if (k->type == KEY_STR)
	/* Bongobongo! */
	i = (((int)KSTR[0] + KSTR[strlen(KSTR) - 1]) % len);
    else
	/* Bongobongobongobongo!!!! */	
	i = KINT % len;
#undef KSTR
#undef KINT

    return i;
}

void htab_prettyprint(struct htab_table *tab) {
    struct htab_entry *e;
    char *p;
    int i;

    for (i = 0; i < tab->len; i++) {
	if (tab->ent[i]) {
	    printf("%d:", i);
	    e = tab->ent[i];
	    do {
		p = htab_key2str(e->key);
		printf(" \"%s\",", p);
		free(p);
	    } while (e = e->next);
	    printf("\n");
	}
    }
}

/* Return the items in the table one for each call.
 * Reset counter when argument is NULL, return value is then NULL.
 * Return NULL when all items have been returned. 
 * Modifying the table may cause undefined results.
 */
void *htab_iter(struct htab_table *tab) {
    static struct htab_entry *e = NULL;
    struct htab_entry *ret;
    static int i = -1;

    printf("htab_iter() called with e=%p and i=%d\n", e, i);
    if (tab == NULL) {
	e = NULL;
	i = -1;
	return NULL;
    }
    while (i < tab->len) {
	if (e) {
	    ret = e;
	    e = e->next;
	    return ret;
	}
	else {
	    i++;
	    e = tab->ent[i];
	}
    }

    return NULL;
}

/* Return 0 on failure. */
int htab_init(struct htab_table *tab, int len) {

    if ( (tab->ent = calloc(len, sizeof (struct htab_entry *))) == NULL) {
	perror("Failed to allocate htab table entries.");
	return -1;
    }
    tab->len = len;

    return 1;
}

int htab_grow(struct htab_table *tab, int grow_by) {
    int len = tab->len + grow_by;
    if ( (tab = realloc(tab, len * sizeof (struct htab_entry *))) == NULL) {
	perror("Failed to allocate htab table entries.");
	return -1;
    }
    tab->len = len;

    return 1;
}

int htab_insert(struct htab_table *tab, htab_key_t *key, void *data) {
    struct htab_entry *e, *new;
    char *p;
    int i;

    i = htab_hash(key, tab->len);

    if ( (new = malloc(sizeof *new)) == NULL) {
	perror("Failed to allocate new htab table entry.\n");
	return -1;
    }
    if (e = tab->ent[i]) {
	do {
	    if (htab_keycmp(e->key, key)) {
		p = htab_key2str(key);
		fprintf(stderr, "Tried to insert colliding key %s\n", p);
		free(new);
		free(p);
		return 0;
	    }
	    if (! e->next) {
		e->next = new;
		break;
	    }
	}
	while (e = e->next);
    }
    if (! e)
	tab->ent[i] = new;
    new->next = NULL;
    new->data = data;
    new->key = key;
    
    return 1;

}

/* Returns a pointer to the data if found, NULL otherwise */
void *htab_lookup(struct htab_table *tab, htab_key_t *key) {
    struct htab_entry *e;
    int i;

    i = htab_hash(key, tab->len);

    if (e = tab->ent[i]) {
	do {
	    if (htab_keycmp(e->key, key)) {
		return e->data;
	    }
	}
	while (e = e->next);
    }
    return NULL;
}

int htab_remove(struct htab_table *tab, htab_key_t *key) {
    struct htab_entry *e, *pe = NULL;
    int i;

    i = htab_hash(key, tab->len);

    if (e = tab->ent[i]) {
	do {
	    if (htab_keycmp(e->key, key)) {
		if (pe)
		    pe->next = e->next;
		else
		    tab->ent[i] = e->next;
		free(e);
	    }
	    pe = e;
	}
	while (e = e->next);
    }
    return 0;
}

/* Removes the first found allocated element in the table, returning
 * a pointer to the data. This allows you to free all data before
 * freeing the table.
 */
void *htab_remove_next(struct htab_table *tab) {
    struct htab_entry *e;
    void *p;
    int i;

    for (i = 0; i < tab->len; i++) {
	if (e = tab->ent[i]) {
	    tab->ent[i] = e->next;
	    p = e->data;
	    free(e->key);
	    free(e);
	    return p;
	}
    }
    
    return NULL;
}

void htab_free(struct htab_table *tab) {
    struct htab_entry *e;
    int i;

    for (i = 0; i < tab->len; i++) {
	if (tab->ent[i]) {
	    while (e = tab->ent[i]) {
		tab->ent[i] = e->next;
		free(e);
	    }
	}
    }
    free(tab->ent);
}

float htab_getload(struct htab_table *tab) {
    struct htab_entry *e;
    int i, acc;

    acc = 0;
    for (i = 0; i < tab->len; i++) {
	if (tab->ent[i]) {
	    while (e = tab->ent[i]) {
		tab->ent[i] = e->next;
		acc++;
	    }
	}
    }
    
    return (float)acc / tab->len;
}


/* Ignores low and high if less than zero */
int htab_bongohash(char *key, int low, int high) {
    static int l, h;
    
    low >= 0 ? l = low : 0 ;
    high >= 0 ? h = high : 0 ;
    return ((int)key[0] % (h - l)) + l;
}