/*
 * XXX Copyright
 */
#include <sys/param.h>
#include <sys/systm.h>
#include <sys/malloc.h>

#include "hashtable.h"	// XXX fix path later

struct new_obj {
	struct new_obj *next;	/* Next object in the list */
	char obj[0];		/* actually bigger */
};

/* Hash table */
struct ipfw_ht {
	int table_size;		/* Size of the table (buckets) */
	int table_obj; 		/* number of object in the table */
	int obj_size;		/* size of object (key + value) */
	/* Hash function for this table */
	uint32_t (*hash)(const void *key, uint32_t size);
	int (*cmp)(const void *obj1, const void *obj2, int sz);
	int hash_arg;		/* hash function parameter */
	struct malloc_type *mtype;
	struct new_obj **table_ptr;	/* Pointer to the table */
};

/*
 * initialize an hash table
 * - size:	size of table (number of buckets)
 * - obj_size:	size of the object to store in the table (key + value)
 * - hf:	pointer to the hash function for this table
 * - compare:	function to compare two objects
 *
 * Return value: pointer to the hash table, NULL if error occurs
 */
struct ipfw_ht *
ipfw_ht_new(int size, int obj_size,
	uint32_t (hf)(const void *, uint32_t size),
	int (compare)(const void *, const void *, int),
	struct malloc_type *mtype)
{
	struct ipfw_ht *h;

	h = malloc(sizeof(*h), mtype, M_NOWAIT | M_ZERO);
	if (h == NULL)
		return NULL;

	h->table_ptr = malloc(size * sizeof(struct new_obj*), mtype,
			       M_NOWAIT | M_ZERO);
	if (h->table_ptr == NULL) { /* no memory */
		free (h, mtype);
		return 0;
	}
	h->table_size = size;
	h->hash = hf;
	h->cmp = compare;
	h->mtype = mtype;
	h->obj_size = obj_size;

	return h;
}

int
ipfw_ht_insert(struct ipfw_ht *h, const void *obj)
{
	int i; /* array index */
	struct new_obj *o, *ot;
	
	i = h->hash(obj, h->table_size);
	
	/* same key not allowed */
	for (ot = h->table_ptr[i]; ot; ot = ot->next) {
		if (h->cmp(obj, ot->obj, h->obj_size) == 0)
			return 1; /* error */
	}
	/* allocate a single chunk of memory */
	o = malloc(sizeof(*o) + h->obj_size, h->mtype, M_NOWAIT);
	if (o == NULL)
		return 1;
	bcopy(obj, o->obj, h->obj_size);

	/* put at the head */
	o->next = h->table_ptr[i];
	h->table_ptr[i] = o;

	h->table_obj++;

	return 0;
}

int
ipfw_ht_remove(struct ipfw_ht *h, const void *obj)
{
	int i;
	struct new_obj *obj1, *prev;

	i = h->hash(obj, h->table_size);

	for (prev = NULL, obj1 = h->table_ptr[i]; obj1; obj1 = obj1->next) {
		if (h->cmp(obj, obj1->obj, h->obj_size) != 0)
			continue;
		/* Object found, delete */
		if (prev != NULL)
			prev->next = obj1->next;
		else
			h->table_ptr[i] = obj1->next;
		free(obj1, h->mtype);
		h->table_obj--;
		return 0;
	}
	return 1; /* Not found */
}

const void *
ipfw_ht_extract(struct ipfw_ht *h, const void *obj)
{
	struct new_obj *o;
	int i;
	if (h == NULL || h->table_obj == 0)
		return NULL;

	i = h->hash(obj, h->table_size);
	for (o =  h->table_ptr[i]; o; o = o->next) {
		if (h->cmp(o->obj, obj, h->obj_size) == 0)
			return o->obj;
	}
	return NULL;
}

void *
ipfw_ht_destroy(struct ipfw_ht *h)
{
	int i;
	struct new_obj *cur, *next;

	if (!h || !h->table_ptr)
		return NULL;
	for (i = 0; i < h->table_size; i++)  {
		for (cur = h->table_ptr[i]; cur; cur = next) {
			next = cur->next;
			free(cur, h->mtype);
		}
	}
	free (h->table_ptr, h->mtype);
	free (h, h->mtype);

	return NULL;
}

/* returns the number of elements in the table */
int
ipfw_ht_count(const struct ipfw_ht *h)
{
	return h ? h->table_obj : 0;
}

const void * 
table_next(struct ipfw_ht *h, const void *o)
{
	int i;
	struct new_obj *obj;

	if (h == NULL || h->table_obj == 0)
		return NULL;
	if (o == NULL) {
		for (i = 0; i < h->table_size; i++)
			if (h->table_ptr[i])
				return h->table_ptr[i]->obj;
		return NULL; /* XXX should not happen */
	}

	/* here we can optimize if we can map o to the bucket,
	 * otherwise locate o and find the next one.
	 */
	i = h->hash(o, h->table_size);
	for (obj = h->table_ptr[i]; obj; obj = obj->next) {
		if (h->cmp(obj->obj, o, h->obj_size) == 0)
			break;
	}
	if (obj && obj->next != NULL)
		return obj->next->obj;
	/* take the first of the next bucket */
	for (i++; i < h->table_size; i++) {
		if (h->table_ptr[i])
			return h->table_ptr[i]->obj;
	}
	return NULL;
}