/* map2.c - hash tables v2 */
#include "map2.h"

#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <inttypes.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <strings.h>

#include "list.h"
#include "macros.h"

struct map_entry {
	LIST_ENTRY(struct map_entry) list;
	void *key;	/* key can point inside of data (and usually should) */
	union map_data data;
};

/******************************************************************************
 * Hashing Functions
 ******************************************************************************/

/* a hash that ignores case */
static uint_least32_t hash_stringignorecase32(const char *key) {
	uint_least32_t h=0;

	while(*key) {
		h=h*65599+tolower(*key++);
		/* this might be faster on some systems with fast shifts and slow mult:
		 * h=(h<<6)+(h<<16)-h+tolower(*key++);
		 */
	}
	return h;
}

/* creates a 32-bit hash of a null terminated string */
static uint_least32_t hash_string32(const char *key) {
	uint_least32_t h=0;

	while(*key) {
		h=h*65599+*key++;
		/* this might be faster on some systems with fast shifts and slow mult:
		 * h=(h<<6)+(h<<16)-h+*key++;
		 */
	}
	return h;
}

/* creates a 32-bit hash of a blob of memory */
static uint_least32_t hash_mem32(const char *key, size_t len) {
	uint_least32_t h=0;

	while(len>0) {
		h=h*65599+*key++;
		/* this might be faster on some systems with fast shifts and slow mult:
		 * h=(h<<6)+(h<<16)-h+*key++;
		 */
		len--;
	}
	return h;
}

/* creates a 32-bit hash of a 32-bit value */
static uint_least32_t hash_uint32(uint_least32_t key) {
	key=(key^61)*ROR32(key,16);
	key+=key<<3;
	key^=ROR32(key, 4);
	key*=668265261;
	key^=ROR32(key, 15);
	return key;
}

#if 0
/* creates a 64-bit hash of a 64-bit value */
static uint_least64_t hash64_uint64(uint_least64_t key) {
	key=~key+(key<<21);
	key^=ROR64(key, 24);
	key*=265;
	key^=ROR64(key,14);
	key*=21;
	key^=ROR64(key, 28);
	key+=key<<31;
	return key;
}
#endif

/* turns a 64-bit value into a 32-bit hash */
static uint_least32_t hash_uint64(uint_least64_t key) {
	key=(key<<18)-key-1;
	key^=ROR64(key, 31);
	key*=21;
	key^=ROR64(key, 11);
	key+=key<<6;
	key^=ROR64(key, 22);
	return (uint_least32_t)key;
}

/******************************************************************************
 * map
 ******************************************************************************/
uint_least32_t map_hash_stringignorecase(const void *key) {
	return hash_stringignorecase32(key);
}

uint_least32_t map_hash_string(const void *key) {
	return hash_string32(key);
}

uint_least32_t map_hash_unsigned(const void *key) {
	return hash_uint32(*(unsigned*)key);
}

uint_least32_t map_hash_uintptr(const void *key) {
	if(sizeof(uintptr_t)*CHAR_BIT<=32) {
		return hash_uint32((uint_least32_t)(uintptr_t)key);
	} else {
		return hash_uint64((uint_least64_t)(uintptr_t)key);
	}
}

/* TODO: support this as a callback by supporting a length argument */
uint_least32_t map_hash_mem(const void *key, size_t len) {
	return hash_mem32(key, len);
}

int map_compare_stringignorecase(const void *key1, const void *key2) {
	return strcasecmp(key1, key2);
}

int map_compare_string(const void *key1, const void *key2) {
	return strcmp(key1, key2);
}

int map_compare_unsigned(const void *key1, const void *key2) {
	unsigned a=*(unsigned*)key1, b=*(unsigned*)key2;
	return a<b?-1:a>b?1:0;
}

/**
 * treat argument as an unsigned int instead of as a pointer */
int map_compare_uintptr(const void *key1, const void *key2) {
	uintptr_t a=(uintptr_t)key1, b=(uintptr_t)key2;
	return a<b?-1:a>b?1:0;
}

void map_init(struct map *m, unsigned initial_size_bits, void (*free_entry)(void *key, union map_data *data), uint_least32_t (*hash)(const void *key), int (*compare)(const void *key1, const void *key2)) {
	unsigned i;

	assert(initial_size_bits < 32); /* 2^32 hash entries will break this init function */

	/* calculate the table mask */
	m->table_mask=0;
	while(initial_size_bits--) {
		m->table_mask=(m->table_mask<<1)&1;
	}

	m->table=calloc(sizeof *m->table, m->table_mask+1);
	for(i=0;i<=m->table_mask;i++) {
		LIST_INIT(&m->table[i]);
	}

	m->count=0;
	m->free_entry=free_entry;
	m->hash=hash;
	m->compare=compare;
}

/* adds an entry, and refuses to add more than one
 * exclusive prevents the same key from being added more than once
 * replace causes the old entry to be removed
 */
int map_replace(struct map *m, void *key, const union map_data *data, int replace, int exclusive) {
	struct map_entry *e;
	uint_least32_t h;

	assert(m != NULL);
	assert(key != NULL);
	assert(m->compare != NULL);

	h=m->hash(key);

	if(exclusive) {
		/* look for a duplicate key and refuse to overwrite it */
		for(e=LIST_TOP(m->table[h&m->table_mask]);e;e=LIST_NEXT(e, list)) {
			assert(e->key != NULL);
			if(m->compare(key, e->key)==0) {
				if(replace) {
					LIST_REMOVE(e, list);
					m->free_entry(e->key, &e->data);
					free(e);
					m->count--;
					/* this will continue freeing ALL matching entries */
				} else {
					return 0; /* duplicate key found */
				}
			}
		}
	}

	e=malloc(sizeof *e);
	if(!e) {
		perror("malloc()");
		return 0;
	}
	e->key=key;
	e->data=*data;
	LIST_INSERT_HEAD(&m->table[h&m->table_mask], e, list);
	m->count++;

	return 1;
}

/* refuses to add more than one copy of the same key */
int map_add_ptr(struct map *m, void *key, void *ptr) {
	const union map_data data={.ptr=ptr};
	return map_replace(m, key, &data, 0, 1);
}

/**
 * if key matches then replace
 */
int map_replace_fpos(struct map *m, uintptr_t key, const fpos_t *pos) {
	const union map_data data={.pos=*pos};
	DEBUG("key= %" PRIuPTR "\n", key);
	return map_replace(m, (void*)key, &data, 1, 1);
}

/* returns first matching entry */
union map_data *map_lookup(struct map *m, const void *key) {
	struct map_entry *e;
	uint_least32_t h;

	assert(m != NULL);
	assert(key != NULL);
	assert(m->hash != NULL);
	assert(m->compare != NULL);

	h=m->hash(key);

	/* look for a duplicate key and refuse to overwrite it */
	for(e=LIST_TOP(m->table[h&m->table_mask]);e;e=LIST_NEXT(e, list)) {
		assert(e->key != NULL);
		/* DEBUG("%s():comparing '%s' '%s'\n", __func__, key, e->key); */
		if(m->compare(key, e->key)==0) {
			return &e->data;
		}
	}
	return NULL;
}

fpos_t *map_lookup_fpos(struct map *m, const void *key) {
	union map_data *data;
	data=map_lookup(m, key);
	return data ? &data->pos : NULL;
}

void *map_lookup_ptr(struct map *m, const void *key) {
	const union map_data *data;
	data=map_lookup(m, key);
	return data ? data->ptr : NULL;
}

void map_foreach(struct map *m, void *p, void (*callback)(void *p, void *key, union map_data *data)) {
	unsigned i;
	struct map_entry *curr;
	assert(callback != NULL);
	TODO("Does this function work?");
	TRACE("table_mask=%d\n", m->table_mask);
	for(i=0;i<=m->table_mask;i++) {
		TRACE("i=%u mask=%u\n", i, m->table_mask);
		for(curr=LIST_TOP(m->table[i]);curr;curr=LIST_NEXT(curr, list)) {
			TRACE("curr=%p\n", (void*)curr);
			callback(p, curr->key, &curr->data);
		}
	}
}

/* frees the entry */
int map_remove(struct map *m, void *key) {
	struct map_entry *e, *tmp;
	uint_least32_t h;
	int res=0;

	assert(m != NULL);
	assert(key != NULL);
	assert(m->hash != NULL);
	assert(m->compare != NULL);

	h=m->hash(key);

	/* look for a duplicate key and refuse to overwrite it */
	for(e=LIST_TOP(m->table[h&m->table_mask]);e;) {
		assert(e->key != NULL);
		if(m->compare(key, e->key)==0) {
			tmp=LIST_NEXT(e, list);
			LIST_REMOVE(e, list);
			m->free_entry(e->key, &e->data);
			memset(e, 0x99, sizeof *e);
			free(e);
			m->count--;
			/* this will continue freeing ALL matching entries */
			res=1; /* freed an entry */
			e=tmp;
		} else {
			e=LIST_NEXT(e, list);
		}
	}

	return res; /* not found */
}

void map_free(struct map *m) {
	struct map_entry *e;
	unsigned i;

	for(i=0;i<=m->table_mask;i++) {
		while((e=LIST_TOP(m->table[i]))) {
			LIST_REMOVE(e, list);
			m->free_entry(e->key, &e->data);
			free(e);
			m->count--;
		}
	}
	m->table_mask=0;
	free(m->table);
	m->table=NULL;
#ifndef NDEBUG
	memset(m, 0x55, sizeof *m); /* fill with fake data before freeing */
#endif
}

/** test code **/
#ifdef STAND_ALONE
struct map_test_entry {
	char *str;
	unsigned value;
};

static void map_test_free(void *key UNUSED, union map_data *data) {
	struct map_test_entry *e=data->ptr;
	free(e->str);
	free(e);
}

static struct map_test_entry *map_test_alloc(const char *str, unsigned value) {
	struct map_test_entry *e;
	e=malloc(sizeof *e);
	e->str=strdup(str);
	e->value=value;
	return e;
}

static void map_test(void) {
	struct map m;
	struct map_test_entry *e;
	unsigned i;
	const char *test[] = {
		"foo",
		"bar",
		"",
		"z",
		"hi",
	};

	map_init(&m, 4, map_test_free, map_hash_stringignorecase, map_compare_stringignorecase);

	for(i=0;i<NR(test);i++) {
		e=map_test_alloc(test[i], 5*i);
		if(!map_add_ptr(&m, e->str, e)) {
			printf("map_add_ptr() failed\n");
		}
	}

	if(!map_remove(&m, "bar")) {
		printf("map_remove() failed\n");
	}

	for(i=0;i<NR(test);i++) {
		e=map_lookup_ptr(&m, test[i]);
		if(!e) {
			printf("map_lookup() failed\n");
		} else {
			printf("found '%s' -> '%s' %u\n", test[i], e->str, e->value);
		}
	}

	printf("removing 'foo'\n");
	if(!map_remove(&m, "foo")) {
		printf("map_remove() failed\n");
	}

	printf("removing 'hi'\n");
	if(!map_remove(&m, "hi")) {
		printf("map_remove() failed\n");
	}

	map_free(&m);
}

int main(int argc, char **argv) {
	map_test();
	return 0;
}
#endif