// to compile you might use:
//    g++ -o ex41_building_hash_tables -Wall ex41_building_hash_tables.cpp

#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE  9

struct node {
	int key;
	struct node *next;
};

static node *hash_table[TABLE_SIZE] = {};

int hash(int key)
{
	return key % TABLE_SIZE;
}

node *new_node()
{
        node *n = (node *) malloc(sizeof(node));
        return n;
}

void insert(int key)
{
	int hashkey = hash(key);
	node *tmp = new_node();
	tmp->key = key;
	tmp->next = hash_table[hashkey];
	hash_table[hashkey] = tmp;
}

void dump_hash_table()
{
	for(int i = 0; i<TABLE_SIZE; i++)
	{
		printf("%d :", i);
		node *tmp = hash_table[i];
		while(tmp)
		{
			printf(" %d", tmp->key);
			tmp = tmp->next;
		}
		printf("\n");
	}
}

void cleanup()
{
	for(int i = 0; i<TABLE_SIZE; i++)
	{
		while(node *tmp = hash_table[i])
		{
			hash_table[i] = hash_table[i]->next;
			free(tmp);
		}
	}
	
}

int main(int argc, char **argv)
{
	int keys[] = {5, 28, 19, 15, 20, 33, 12, 17, 10};
	for(unsigned int i = 0; i<sizeof(keys)/sizeof(int); i++)
		insert(keys[i]);
	dump_hash_table();
	cleanup();
	return(0);
}