/* 
 * What we need from our data type:
 * 	A hash function
 * 	Need to know what size it is
 * 	Need to be able to tell if a space is used
 * 	We don't need to know how to copy if just copying it bit by bit is ok
 * 	We can just return a memory address
 */

/*
 * Decisions:
 * 	Freespace table is an array of bits (not bytes)
 */

#include<stdlib.h>
#include<string.h>

struct table_description {
	void *data_start;
	unsigned char *freespace_table;
	size_t (*hash_function)(void*);
	size_t capacity;
	size_t item_size;
	size_t items;
};

void init(struct table_description *td, size_t item_size, size_t initial_capacity, size_t (*hash_function)(void*)){
	td->capacity = initial_capacity;
	size_t freespace_table_size = ((initial_capacity % 8)? 1:0) + (initial_capacity / 8);
	td->freespace_table = malloc(initial_capacity * item_size + freespace_table_size);
	td->data_start = td->freespace_table + freespace_table_size;
	memset(td->freespace_table, 0, freespace_table_size);
	td->item_size = item_size;
	td->hash_function = hash_function;	
	td->items = 0;
}

char freespace_check(struct table_description *td, size_t index){
	size_t freespace_byte = index / 8;
	size_t freespace_bit = index % 8;
	unsigned char mask = 1 << freespace_bit;
	return mask & td->freespace_table[freespace_byte];
}

void* lookup_item(struct table_description *td, size_t hash_value){
	size_t index = hash_value % td->capacity;
	while(freespace_check(td, index)){
		if(hash_value == td->hash_function(td->data_start + td->item_size * index))
			return td->data_start + td->item_size * index;
		index++;
		if(index >= td->capacity)
			index = 0;
	}
	return 0;
}	

void insert_item(struct table_description *td, void *item){
	size_t index = td->hash_function(item) % td->capacity;
	if(td->items > td->capacity / 2) {
		/* It's too full! */
		return;
	}
	while(freespace_check(td, index)){
		index++;
		if(index >= td->capacity)
			index = 0;
	}
	memcpy(td->data_start + index * td->item_size, item, td->item_size);
	size_t freespace_byte = index / 8;
	size_t freespace_bit = index % 8;
	unsigned char mask = 1 << freespace_bit;
	td->freespace_table[freespace_byte] |= mask;
}

void *iterate(struct table_description *td){
	static size_t index = 0;
	while(!freespace_check(td, index) && index < td->capacity)
		index++;
	if(index == td->capacity){
		index = 0;
		return 0;
	}
	index++;
	return td->data_start + td->item_size * (index - 1);
}