#include "hashtable.h"
	
/* Hashtable initialization routine.
 * Establishes the comparator between keys, the size of the hashtable,
 * and memory-related setup.
 */
int init_table(HashTable * ht, int * hash_size, ulong (*hash) (void *), bool (*equal) (void *, void *), char * name)  
{
	Bucket * table;
	int 	i,
		orig = *hash_size,
		size = orig * BSIZE / PAGE_SIZE,
		count = 0;
	
	ht->bits = 0;

	


	while(size >>= 1)
		ht->bits++;

	*hash_size = (1 << ht->bits) * PAGE_SIZE / BSIZE;
	while((*hash_size) >>= 1)
		count++;

	//causes loss of memory usage. but calculations will be explained later.
	ht->ibits = count;
	*hash_size = 1 << count;

	/*
	 * Allocate memory for the table
	 *
	 * If the hashtable ever starts using extensive
	 * amounts of memory, I'll have to deal with expanding 
	 * its memory usage into high-memory.
	 */
	ht->table = (Bucket *) __get_free_pages(GFP_ATOMIC, ht->bits); 

	if(!ht->table) {
		printk(KERN_ALERT "Anemone Error: Failed to allocate hashtable memory. Bailing...\n");
		return -ENOMEM;
	}
	table = ht->table;

	if(strlen(name) >= TABLE_NAMESIZE) {
		printk(KERN_ALERT "Anemone Error: Hashtable name is too long.\n");
		return -EINVAL;
	}

	strcpy(ht->slab_name, name);

	ht->entries = kmem_cache_create(ht->slab_name, sizeof(Entry),
				        0, 0, 
					NULL, NULL);

	if (!ht->entries) {
		kmem_cache_destroy(ht->entries);
		printk(KERN_ALERT "Anemone error; Could not allocate HASHTABLE slab caches.\n");
		return -ENOMEM;
	}

	printk(KERN_ALERT "GFP granted %d/%d buckets (%lu bytes)\nSystem Page Size: %lu\n", *hash_size, orig, (ulong)(*hash_size * BSIZE), (ulong) PAGE_SIZE);

	ht->count = 0;
	ht->curr = -1;
	ht->hash_size = *hash_size;
	ht->hash = hash;
	ht->equal = equal;

	/*
	 * Initialize all the buckets 
	 */
	for(i=0; i < *hash_size; i++) {
		INIT_LIST_HEAD(&(table[i].bucket));
		table[i].count = 0;
		table[i].curr = 0;
	}
	return 0;
}

/* Hashtable memory cleanup of all buckets and linked lists */
void clean_table(HashTable * ht)
{
	int i; 
	list_head *x, *y;
	Entry * e;
	Bucket * table = ht->table;
	ulong * count;

	for(i = 0; i < ht->hash_size; i++) { 
		count = &table[i].count;
		list_for_each_safe(x, y, &(table[i].bucket)) {
			list_del(x);
			e = list_entry(x, Entry, mapping);
			kmem_cache_free(ht->entries, e);
			ht->count--;
			(*count)--;
		}
		if(table[i].count) {
			printk(KERN_ALERT "SERIOUS ERROR: Bucket #%d was not successfully emptied.\n", i);
		}
	}

	if(kmem_cache_destroy(ht->entries))
		printk(KERN_ALERT "Serious Anemone Error: HASHTABLE slab cache not empty. Free failed.\n");

	if(ht->count)
		printk(KERN_ALERT "SERIOUS error: Hash Table still has data inside it!");
	free_pages((ulong) ht->table, ht->bits); 
}

/* Insert a new entry into the hashtable */
inline void insert_table(HashTable * ht, void * key, void *data) 
{
	ulong hash_value = ht->hash(key);
	Bucket * b = &ht->table[hash_value];
	Entry * e = kmem_cache_alloc(ht->entries, GFP_ATOMIC);

	if(!e) {
		printk(KERN_ALERT "Could not allocate memory for the hashtable.\n");
		BUG();
	}

	e->key = key;
	e->data = data;

	list_add(&e->mapping, &(b->bucket));

	b->count++;
	ht->count++;
}

/* Remove an entry */
inline void * remove_table(HashTable * ht, void * key) {
	void * d = NULL;
	list_head * x;
	list_head * y;
	Entry * e;
	ulong hash_value = ht->hash(key);
       
	Bucket * b = &ht->table[hash_value];

	list_for_each_safe(x, y, &(b->bucket)) {
		e = list_entry(x, Entry, mapping);
		if(ht->equal(key, (u8 *) e->key)) {
			list_del(x);
			kmem_cache_free(ht->entries, e);
			ht->count--;
			b->count--;	
			d = e->data;
			break;
		}
	}	

	return d;
}

/* Lookup and entry in the hashtable */
inline void *lookup_table(HashTable * ht, void * key) { 
	void * d = NULL;
	ulong hash_value;
	Bucket * b;

	assert(ht, "checking hashtable pointer");

	hash_value = ht->hash(key);
	b = &ht->table[hash_value];

	assert(b, "checking debug pointer");

	if(b->count) {
		list_head * x;
		Entry * e;

		list_for_each(x, &(b->bucket)) {
			e = list_entry(x, Entry, mapping);

			assert(e, "checking entry pointer");

			if(ht->equal(key, (u8 *) e->key)) {
				d = e->data;
				break;
			}
		}	
	}

	return d;
}

/* These functions are used to traverse all the entries in the hashtable,
 * used in times of debugging.
 */
void rewind_table(HashTable * ht) 
{
	int i;

	ht->curr = -1;

	for(i = 0; i < ht->hash_size; i++)
		ht->table[i].curr = NULL;
}

inline void * remove_current_in_table(HashTable *ht) {
	Bucket * b = &ht->table[ht->curr];
	list_head * curr_save;

	if(!b->curr)
		return NULL;

	curr_save = b->curr;

	if(b->curr->prev == &b->bucket) 
		b->curr = NULL;
	else
		b->curr = b->curr->prev;

	return remove_table(ht, list_entry(curr_save, Entry, mapping)->key);
}

inline static void * next_entry(Bucket * b) {
	if(!b->curr)
		b->curr = b->bucket.next;
	else if (b->curr == b->bucket.prev)
		return NULL;
	else 
		b->curr = b->curr->next;

	return (b->curr ? list_entry(b->curr, Entry, mapping)->data : NULL);
}

inline void * next_in_table(HashTable * ht) 
{
	void * data = NULL;

	if(ht->curr == -1) 
		ht->curr = 0;
	
	while (!(data = next_entry(&ht->table[ht->curr]))) {
		if (ht->curr == (hash_size - 1)) 
			break;
		else 
			ht->curr++;
	}

	return data;
}

inline void * get_key_at_current(HashTable * ht) {
	Bucket * b = &ht->table[ht->curr];
	return (b->curr ? list_entry(b->curr, Entry, mapping)->key : NULL);
}