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

#define TABLE_SIZE (102400)
#define HASH_TABLE_SIZE (32)

void initHashTable();

/*
 * ハッシュテーブル。
 *
 * 各テーブルはリスト構造によって構築。
 */

/* テーブル上のデータにint型サイズでアクセスするためのもの */
union U {
	int *addr;
	char *ptr;
};

char table[TABLE_SIZE]; /* 全てのデータの格納 */
union U freeptr; /* データの追加ポイントへの参照 */

/* テーブルの先頭アドレスの取得 */
char *getTableHeadPtr() {
	return &table[0] + sizeof(int);
}

/* データの追加場所のアドレスを登録 */
void setFreePtr(char *ptr) {
	*freeptr.addr = (int)ptr;
}

/* データの追加場所のアドレスの移動 */
char *moveFreePtr(int add) {
	*freeptr.addr += add;
	return (char*)*freeptr.addr;
}

/* データの追加場所のアドレスの取得 */
char *getFreePtr() {
	return (char*)*freeptr.addr;
}

/* ハッシュ関数 */
int hash(char *str) {
	int h = 0;
	int i;
	for (i = 0; (*str != '\0') && (i < 10); ++i) {
		h += (str[0]) * (str[1]);
		++str;
	}
	return h % HASH_TABLE_SIZE;
}

/* ハッシュテーブルの初期化 */
void initHashTable() {
	union U u;
	int i;
	
	/* テーブルの初期化 */
	u.ptr = getTableHeadPtr();
	for (i = 0; i < HASH_TABLE_SIZE; ++i) {
		*u.addr = (int)NULL;
		u.ptr += sizeof(int);
	}
	
	/* データの追加場所を記録する場所はテーブルの先頭 */
	freeptr.ptr = &table[0];
	
	/* データの追加場所の指定 */
	setFreePtr(u.ptr);
}

/* テーブルへのデータの追加 */
void addHashTable(const char *key, const void *data, const int size) {
	union U u, v;
	int h = hash(key);
	int len;
	char *p;
	
	/* リストの先頭アドレスの取得 */
	u.ptr = getTableHeadPtr() + h * sizeof(int);
	
	/* リスト上のデータ追加する場所を探す */
	if (*u.addr != (int)NULL) {
		do {
			u.ptr = (char*)*u.addr;
			p = u.ptr + sizeof(int);
			if (strcmp(p, key) == 0) {
				printf("invalid key: %s\n", key); /* キー重複面倒 */
				return;
			}
		} while (*u.addr != (int)NULL);
	}
	
	/* 新しいデータのアドレス格納 */
	*u.addr = (int)getFreePtr();
	
	/* ここから新しいデータの編集 */
	
	/* 次のデータへのポインタを0(NULL)で初期化 */
	v.ptr = getFreePtr();
	*v.addr = (int)NULL;
	moveFreePtr(sizeof(int));
	
	/* キーの登録 */
	len = strlen(key) + 1;
	memcpy(getFreePtr(), key, len);
	moveFreePtr(len);
	
	/* データサイズの登録 */
	/* 不精なのでunion Uを代用 */
	v.ptr = getFreePtr();
	*v.addr = size;
	moveFreePtr(sizeof(int));
	
	/* データの登録 */
	memcpy(getFreePtr(), data, size);
	moveFreePtr(size);
}

void getAllData(void (*func)(const char*, const void*, const int)) {
	union U u, v, w;
	int i, len;
	char *p;
	u.ptr = getTableHeadPtr();
	for (i = 0; i < HASH_TABLE_SIZE; ++i) {
		if (*u.addr != (int)NULL) {
			v = u;
			do {
				v.ptr = (char*)*v.addr;
				p = v.ptr + sizeof(int);
				len = strlen(p);
				w.ptr = p + len + 1;
				(*func)(p, w.ptr + sizeof(int), *w.addr);
			} while (*v.addr != (int)NULL);
		}
		u.ptr += sizeof(int);
	}
}

void myfunc(const char* key, const void* data, const int size) {
	printf("key: %s, size: %d, data address: %d\n", key, size, data);
}

int main(void) {
	int v = 0xABCDEF12;
	
	initHashTable();
	
	addHashTable("abcde", &v, sizeof(v));
	addHashTable("abcde", &v, sizeof(v));
	addHashTable("abcde", &v, sizeof(v));
	
	v = 0xAABBCC;
	addHashTable("XYZ", &v, sizeof(v));

	v = 0x112233;
	addHashTable("ABCDE", &v, sizeof(v));
	
	getAllData(myfunc);
	
	for (v = 0; v < 256; ++v) {
		if (v % 8 == 0) {
			if (v % 16 == 0) {
				printf("\n%04X: ", v);
			} else {
				printf(" ");
			}
		}
		printf("%02x ", 0xFF & table[v]);
	}
	
	return 0;
}