#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>

#include "util.h"

typedef int T;

struct hash_item {
	struct hash_item *next;
	char *key;
	T data;
};

struct hash_tab {
	struct hash_item *table[251];		// fit for your needs...
};

static unsigned long
hash_key(const unsigned char *str)
{
	unsigned long hash = 5381;
	int c;

	while ( (c = *str++) != '\0' )
		hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

	return hash;
}

void
hash_init(struct hash_tab *ht)
{
	for ( int i = 0; i != NELEM(ht->table); ++i )
		ht->table[i] = NULL;
}

static struct hash_item *
hash_add(struct hash_item *next, const char *key, T data)
{
	struct hash_item *new_item;
	char *new_key;

	new_key = strdup(key);	// strdup: not standard but commonly used...
	new_item = malloc(sizeof(*new_item));

	if ( new_key == NULL || new_item == NULL ) {
		free(new_key);
		free(new_item);
		ERROR("out of memory");
		return NULL;
	}

	new_item->next = next;
	new_item->key = new_key;
	new_item->data = data;

	return new_item;
}

T *
hash_lookup(struct hash_tab *ht, const char *key, T data, int create)
{
	unsigned long h;
	struct hash_item *item;
   
	h = hash_key((const unsigned char *) key) % NELEM(ht->table);
	for ( item = ht->table[h]; item; item = item->next )
		if ( strcmp(key, item->key) == 0 )
			return &item->data;

	// not found! create?
	if ( create ) {
		item = hash_add(ht->table[h], key, data);
		if ( item != NULL )
			ht->table[h] = item;
		else
			ERROR("can't create item");
	}

	return item ? &item->data : NULL;
}

bool
hash_delete(struct hash_tab *ht, const char *key)
{
	unsigned long h;
	struct hash_item *prev, *p;

	h = hash_key((const unsigned char *) key) % NELEM(ht->table);
	prev = NULL;
	for ( p = ht->table[h]; p; p = p->next ) {
		if ( strcmp(key, p->key) == 0 ) {
			if ( prev == NULL )
				ht->table[h] = p->next;
			else
				prev->next = p->next;

			free(p->key);
			free(p);

			return true;		// successfully removed!
		}
		prev = p;
	}

	return false;
}

void
hash_apply(struct hash_tab *ht, void (*visit)(const char *key, T data, void *cl), void *cl)
{
	struct hash_item *item;

	for ( int i = 0; i != NELEM(ht->table); ++i )
		for ( item = ht->table[i]; item; item = item->next )
			visit(item->key, item->data, cl);
}

void
hash_free(struct hash_tab *ht)
{
	struct hash_item *p, *next;

	for ( int i = 0; i != NELEM(ht->table); ++i ) {
		for ( p = ht->table[i]; p; p = next ) {
			next = p->next;
			free(p->key);
			free(p);
		}
		ht->table[i] = NULL;
	}
}

int getword(FILE *fp, char *buf, int size, int first(int c), int rest(int c))
{
	int i = 0, c;

	c = getc(fp);
	for ( ; c != EOF; c = getc(fp) )
		if ( first(c) ) {
			if ( i < size-1 )
				buf[i++] = c;
			c = getc(fp);
			break;
		}

	for ( ; c != EOF && rest(c); c = getc(fp) )
		if ( i < size-1)
			buf[i++] = c;

	if ( i < size )
		buf[i] = 0;
	else
		buf[size-1] = 0;

	if ( c != EOF )
		ungetc(c, fp);

	return c > 0;
}

int first(int c) {
	return isalpha(c);
}

int rest(int c) {
	return isalpha(c) || c == '_';
}

void print(const char *key, T data, void *cl)
{
	fprintf(cl, "%s: %d\n", key, data);
}

int
main()
{
	struct hash_tab ht[1];
	char word[100];

	hash_init(ht);

	while ( getword(stdin, word, sizeof word, first, rest) ) {
		int *p = hash_lookup(ht, word, 0, 1);
		if ( p != NULL )
			++(*p);
	}

	hash_delete(ht, "new_item");

	hash_apply(ht, print, stdout);

	hash_free(ht);
}