[hashtable.git] / hashtable.c

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

typedef struct _Node {
	void* key;
	void* data;
	struct _Node* next;
} Node;

struct _Hashtable {
	uint32_t size;
	HashFunc hash;
	EqualFunc compare;
	FreeFunc free;
	PrintFunc print;
	Node** nodes;
};

typedef struct {
	Hashtable* table;
	void* dummy2;
	void* dummy3;
	int64_t pos;
} RealIter;

static uint32_t hash_table_index(Hashtable* ht, const void* key) {
	return (ht->hash(key) % ht->size);
}

static void hash_table_default_print(void* data) {
	printf("%p", data);
}

Hashtable* hash_table_create(HashFunc hf, EqualFunc ef) {
	return hash_table_create_full(hf, ef, TABLESIZE, NULL, NULL);
}

Hashtable* hash_table_create_notify(HashFunc hf, EqualFunc ef, FreeFunc ff) {
	return hash_table_create_full(hf, ef, TABLESIZE, ff, NULL);
}

Hashtable* hash_table_create_full(HashFunc hf, EqualFunc ef, uint32_t size, FreeFunc ff, PrintFunc pf) {
	Hashtable* ht = malloc(sizeof(*ht));
	ht->size = size;
	ht->hash = hf;
	ht->compare = ef;
	if (ff) {
		ht->free = ff;
	} else {
		ht->free = free;
	}
	if (pf) {
		ht->print = pf;
	} else {
		ht->print = hash_table_default_print;
	}
	ht->nodes = calloc(sizeof(Node*), ht->size);
	return ht;
}

void hash_table_destroy(Hashtable* ht) {
	for (uint32_t i = 0; i < ht->size; i++) {
		while (ht->nodes[i]) {
			Node* node = ht->nodes[i];
			ht->nodes[i] = ht->nodes[i]->next;
			ht->free(node->data);
			free(node);
		}
	}
	hash_table_print(ht);
	free(ht->nodes);
	free(ht);
}

void hash_table_set_print_func(Hashtable* ht, PrintFunc pf) {
	ht->print = pf;
}

void hash_table_print(Hashtable* ht) {
	printf("Start Table\n");
	for (uint32_t i = 0; i < ht->size; i++) {
		if (ht->nodes[i] == NULL) {
			//printf("\t%i\t---\n", i);
		} else {
			printf("\t%i\t\n", i);
			Node* node = ht->nodes[i];
			while (node != NULL) {
				printf("\"%p\" - (", node->key);
				ht->print(node->data);
				printf(")");
				node = node->next;
			}
			printf("\n");
		}
	}
	printf("End Table\n");
}

bool hash_table_insert(Hashtable* ht, const void* key, void* obj) {
	if (key == NULL || obj == NULL || ht == NULL) return false;

	// implement chaning
	if (hash_table_lookup(ht, key) != NULL) return false;

	uint32_t index = hash_table_index(ht, key);

	Node* node = malloc(sizeof(*node));
	node->data = obj;
	node->key = (void*)key;

	node->next = ht->nodes[index];
	ht->nodes[index] = node;
	return true;
}

void* hash_table_lookup(Hashtable* ht, const void* key) {
	if (key == NULL || ht == NULL) return false;
	uint32_t index = hash_table_index(ht, key);

	Node* node = ht->nodes[index];
	while (node != NULL && ht->compare(node->data, key) == false) {
		node = node->next;
	}

	if (node == NULL) return NULL;
	//printf("find: %p -> found: %p\n", key, node->data);

	return node->data;
}

void* hash_table_delete(Hashtable* ht, const void* key) {
	if (key == NULL || ht == NULL) return false;
	uint64_t index = hash_table_index(ht, key);

	Node* node = ht->nodes[index];
	Node* prev = NULL;
	while (node != NULL && ht->compare(node->data, key) == false) {
		prev = node;
		node = node->next;
	}

	if (node == NULL) return NULL;
	if (prev == NULL) {
		ht->nodes[index] = node->next;
	} else{
		prev->next = node->next;
	}

	void* result = node->data;
	free(node);
	return result;
}

List* hash_table_keys(Hashtable* ht) {
	List *keys, *head;
	keys = head = NULL;

	if (ht != NULL) {
		for (uint32_t i = 0; i < ht->size; i++) {
			if (ht->nodes[i] != NULL) {
				Node* node = ht->nodes[i];
				while (node != NULL) {
					if (head == NULL) {
						head = calloc(sizeof(List*), 1);
						keys = head;
					}
					else {
						head->next = calloc(sizeof(List*), 1);
						head = head->next;
					}
					head->data = ht->nodes[i]->key;
					node = node->next;
				}
			}
		}
	}

	return keys;
}

List* hash_table_values(Hashtable* ht) {
	List *values, *head;
	values = head = NULL;

	if (ht != NULL) {
		for (uint32_t i = 0; i < ht->size; i++) {
			if (ht->nodes[i] != NULL) {
				Node* node = ht->nodes[i];
				while (node != NULL) {
					if (head == NULL) {
						head = calloc(sizeof(List*), 1);
						values = head;
					}
					else {
						head->next = calloc(sizeof(List*), 1);
						head = head->next;
					}
					head->data = ht->nodes[i]->data;
					node = node->next;
				}
			}
		}
	}

	return values;
}

void hash_table_list_free(List* list) {
	while (list != NULL) {
		List* prev = list;
		list = list->next;
		free(prev);
	}
}

void hash_table_foreach(Hashtable* ht, ForeachFunc ff, void* userdata) {
	if (ht != NULL) {
		for (uint32_t i = 0; i < ht->size; i++) {
			if (ht->nodes[i] != NULL) {
				Node* node = ht->nodes[i];
				while (node != NULL) {
					ff(node->key, node->data, userdata);
					node = node->next;
				}
			}
		}
	}
}

void hash_table_iter_init (HashtableIter* iter, Hashtable* ht) {
	RealIter* ri = (RealIter*) iter;

	if (ri != NULL && ht != NULL) {
		ri->table = ht;
		ri->pos = -1;
	}
}

bool hash_table_iter_next(HashtableIter* iter, void** key, void** value) {
	RealIter* ri = (RealIter*) iter;
	Node* node;
	int64_t pos;

	if (ri != NULL) {
		pos = ri->pos;

		do {
			pos++;
			if (pos >= ri->table->size) {
				ri->pos = pos;
				return false;
			}
			node = ri->table->nodes[pos];
		} while (node == NULL);

		if (key != NULL)
			*key = node->key;
		if (value != NULL)
			*value = node->data;

		ri->pos = pos;
		return true;
	}
	return false;
}

bool hash_table_contains(Hashtable* ht, const void* key) {
	if (ht == NULL || key == NULL) return false;

	if (hash_table_lookup(ht, key) == NULL)
		return false;
	return true;
}

uint64_t hash_table_size(Hashtable *ht) {
	uint64_t size = 0;

	if (ht == NULL) return size;

	for (uint32_t i = 0; i < ht->size; i++) {
		if (ht->nodes[i] != NULL) {
			Node* node = ht->nodes[i];
			while (node != NULL) {
				size++;
				node = node->next;
			}
		}
	}

	return size;
}

bool hash_table_replace(Hashtable *ht, void* key, void* value) {
	if (ht == NULL || key == NULL || value == NULL) return false;

	uint32_t index = hash_table_index(ht, key);

	Node* node = ht->nodes[index];
	while (node != NULL && ht->compare(node->data, key) == false) {
		node = node->next;
	}

	if (node == NULL)
		return hash_table_insert(ht, key, value);
	else {
		free(node->data);
		node->key = key;
		node->data = value;
	}

	return true;
}

uint64_t int_hash(const void* key) {
	return *(uint64_t*) key;
}

uint64_t str_hash(const void* key) {
	const signed char* p;
	uint64_t h = 5381;

	for (p = key; *p != '\0'; p++) {
		h = (h << 5) + h + *p;
	}

	return h;
}

uint64_t ptr_hash(const void* key) {
	return (uint64_t)key;
}

bool int_equal(const void* a, const void* b) {
	return *((const int*) a) == *((const int*) b);
}

bool str_equal(const void* a, const void* b) {
  const char *string1 = (const char*) a;
  const char *string2 = (const char*) b;

  return strcmp (string1, string2) == 0;
}

bool ptr_equal(const void* a, const void* b) {
	return a == b;
}
Commit	Line	Data
1d8fe1f7 MR	1	#include <string.h>
	2	#include <stdio.h>
	3	#include <stdlib.h>
	4	#include "hashtable.h"
	5
8c5be416 MR	6	typedef struct _Node {
8c5be416 MR	7	void* key;
1d8fe1f7	8	void* data;
8c5be416 MR	9	struct _Node* next;
8c5be416 MR	10	} Node;
1d8fe1f7	11
8c5be416	12	struct _Hashtable {
1d8fe1f7 MR	13	uint32_t size;
	14	HashFunc hash;
	15	EqualFunc compare;
8c5be416	16	FreeFunc free;
f3e1ef9f	17	PrintFunc print;
8c5be416 MR	18	Node** nodes;
	19	};
	20
	21	typedef struct {
	22	Hashtable* table;
	23	void* dummy2;
	24	void* dummy3;
	25	int64_t pos;
	26	} RealIter;
1d8fe1f7 MR	27
	28	static uint32_t hash_table_index(Hashtable* ht, const void* key) {
	29	return (ht->hash(key) % ht->size);
	30	}
	31
f3e1ef9f MR	32	static void hash_table_default_print(void* data) {
	33	printf("%p", data);
	34	}
	35
1d8fe1f7	36	Hashtable* hash_table_create(HashFunc hf, EqualFunc ef) {
f3e1ef9f	37	return hash_table_create_full(hf, ef, TABLESIZE, NULL, NULL);
8c5be416 MR	38	}
	39
	40	Hashtable* hash_table_create_notify(HashFunc hf, EqualFunc ef, FreeFunc ff) {
f3e1ef9f	41	return hash_table_create_full(hf, ef, TABLESIZE, ff, NULL);
1d8fe1f7 MR	42	}
1d8fe1f7 MR	43
f3e1ef9f	44	Hashtable* hash_table_create_full(HashFunc hf, EqualFunc ef, uint32_t size, FreeFunc ff, PrintFunc pf) {
1d8fe1f7 MR	45	Hashtable* ht = malloc(sizeof(*ht));
	46	ht->size = size;
	47	ht->hash = hf;
	48	ht->compare = ef;
8c5be416 MR	49	if (ff) {
	50	ht->free = ff;
	51	} else {
	52	ht->free = free;
	53	}
f3e1ef9f MR	54	if (pf) {
	55	ht->print = pf;
	56	} else {
	57	ht->print = hash_table_default_print;
	58	}
8c5be416	59	ht->nodes = calloc(sizeof(Node*), ht->size);
1d8fe1f7 MR	60	return ht;
	61	}
	62
	63	void hash_table_destroy(Hashtable* ht) {
	64	for (uint32_t i = 0; i < ht->size; i++) {
8c5be416 MR	65	while (ht->nodes[i]) {
	66	Node* node = ht->nodes[i];
	67	ht->nodes[i] = ht->nodes[i]->next;
	68	ht->free(node->data);
	69	free(node);
1d8fe1f7 MR	70	}
	71	}
	72	hash_table_print(ht);
8c5be416	73	free(ht->nodes);
1d8fe1f7 MR	74	free(ht);
	75	}
	76
f3e1ef9f MR	77	void hash_table_set_print_func(Hashtable* ht, PrintFunc pf) {
	78	ht->print = pf;
	79	}
	80
1d8fe1f7 MR	81	void hash_table_print(Hashtable* ht) {
	82	printf("Start Table\n");
	83	for (uint32_t i = 0; i < ht->size; i++) {
8c5be416	84	if (ht->nodes[i] == NULL) {
1d8fe1f7 MR	85	//printf("\t%i\t---\n", i);
	86	} else {
	87	printf("\t%i\t\n", i);
8c5be416 MR	88	Node* node = ht->nodes[i];
8c5be416 MR	89	while (node != NULL) {
f3e1ef9f MR	90	printf("\"%p\" - (", node->key);
	91	ht->print(node->data);
	92	printf(")");
8c5be416	93	node = node->next;
1d8fe1f7 MR	94	}
	95	printf("\n");
	96	}
	97	}
	98	printf("End Table\n");
	99	}
	100
	101	bool hash_table_insert(Hashtable* ht, const void* key, void* obj) {
	102	if (key == NULL \|\| obj == NULL \|\| ht == NULL) return false;
	103
	104	// implement chaning
8c5be416	105	if (hash_table_lookup(ht, key) != NULL) return false;
1d8fe1f7 MR	106
	107	uint32_t index = hash_table_index(ht, key);
	108
8c5be416 MR	109	Node* node = malloc(sizeof(*node));
	110	node->data = obj;
	111	node->key = (void*)key;
1d8fe1f7	112
8c5be416 MR	113	node->next = ht->nodes[index];
8c5be416 MR	114	ht->nodes[index] = node;
1d8fe1f7 MR	115	return true;
	116	}
	117
	118	void* hash_table_lookup(Hashtable* ht, const void* key) {
	119	if (key == NULL \|\| ht == NULL) return false;
dd3da95a	120	uint32_t index = hash_table_index(ht, key);
1d8fe1f7	121
8c5be416 MR	122	Node* node = ht->nodes[index];
	123	while (node != NULL && ht->compare(node->data, key) == false) {
	124	node = node->next;
	125	}
	126
	127	if (node == NULL) return NULL;
dd3da95a	128	//printf("find: %p -> found: %p\n", key, node->data);
1d8fe1f7	129
8c5be416	130	return node->data;
1d8fe1f7 MR	131	}
	132
	133	void* hash_table_delete(Hashtable* ht, const void* key) {
	134	if (key == NULL \|\| ht == NULL) return false;
	135	uint64_t index = hash_table_index(ht, key);
	136
8c5be416 MR	137	Node* node = ht->nodes[index];
	138	Node* prev = NULL;
	139	while (node != NULL && ht->compare(node->data, key) == false) {
	140	prev = node;
	141	node = node->next;
	142	}
	143
	144	if (node == NULL) return NULL;
	145	if (prev == NULL) {
	146	ht->nodes[index] = node->next;
	147	} else{
	148	prev->next = node->next;
	149	}
1d8fe1f7	150
8c5be416 MR	151	void* result = node->data;
8c5be416 MR	152	free(node);
1d8fe1f7 MR	153	return result;
	154	}
	155
8c5be416 MR	156	List* hash_table_keys(Hashtable* ht) {
	157	List keys, head;
	158	keys = head = NULL;
	159
	160	if (ht != NULL) {
	161	for (uint32_t i = 0; i < ht->size; i++) {
	162	if (ht->nodes[i] != NULL) {
	163	Node* node = ht->nodes[i];
	164	while (node != NULL) {
	165	if (head == NULL) {
	166	head = calloc(sizeof(List*), 1);
	167	keys = head;
	168	}
	169	else {
	170	head->next = calloc(sizeof(List*), 1);
	171	head = head->next;
	172	}
	173	head->data = ht->nodes[i]->key;
	174	node = node->next;
	175	}
	176	}
	177	}
	178	}
	179
	180	return keys;
	181	}
	182
	183	List* hash_table_values(Hashtable* ht) {
	184	List values, head;
	185	values = head = NULL;
	186
	187	if (ht != NULL) {
	188	for (uint32_t i = 0; i < ht->size; i++) {
	189	if (ht->nodes[i] != NULL) {
	190	Node* node = ht->nodes[i];
	191	while (node != NULL) {
	192	if (head == NULL) {
	193	head = calloc(sizeof(List*), 1);
	194	values = head;
	195	}
	196	else {
	197	head->next = calloc(sizeof(List*), 1);
	198	head = head->next;
	199	}
	200	head->data = ht->nodes[i]->data;
	201	node = node->next;
	202	}
	203	}
	204	}
	205	}
	206
	207	return values;
	208	}
	209
	210	void hash_table_list_free(List* list) {
	211	while (list != NULL) {
	212	List* prev = list;
	213	list = list->next;
	214	free(prev);
	215	}
	216	}
	217
	218	void hash_table_foreach(Hashtable* ht, ForeachFunc ff, void* userdata) {
	219	if (ht != NULL) {
220	for (uint32_t i = 0; i < ht->size; i++) {
221	if (ht->nodes[i] != NULL) {
222	Node* node = ht->nodes[i];
223	while (node != NULL) {
224	ff(node->key, node->data, userdata);
225	node = node->next;
226	}
227	}
228	}
229	}
230	}
231
232	void hash_table_iter_init (HashtableIter* iter, Hashtable* ht) {
233	RealIter* ri = (RealIter*) iter;
234
235	if (ri != NULL && ht != NULL) {
236	ri->table = ht;
237	ri->pos = -1;
238	}
239	}
240
241	bool hash_table_iter_next(HashtableIter* iter, void key, void value) {
242	RealIter* ri = (RealIter*) iter;
243	Node* node;
244	int64_t pos;
245
246	if (ri != NULL) {
247	pos = ri->pos;
248
249	do {
250	pos++;
251	if (pos >= ri->table->size) {
252	ri->pos = pos;
253	return false;
254	}
255	node = ri->table->nodes[pos];
256	} while (node == NULL);
257
258	if (key != NULL)
259	*key = node->key;
260	if (value != NULL)
261	*value = node->data;
262
263	ri->pos = pos;
264	return true;
265	}
266	return false;
267	}
268
dd3da95a MR	269	bool hash_table_contains(Hashtable* ht, const void* key) {
	270	if (ht == NULL \|\| key == NULL) return false;
	271
	272	if (hash_table_lookup(ht, key) == NULL)
	273	return false;
	274	return true;
	275	}
	276
	277	uint64_t hash_table_size(Hashtable *ht) {
	278	uint64_t size = 0;
	279
	280	if (ht == NULL) return size;
	281
	282	for (uint32_t i = 0; i < ht->size; i++) {
	283	if (ht->nodes[i] != NULL) {
	284	Node* node = ht->nodes[i];
	285	while (node != NULL) {
	286	size++;
	287	node = node->next;
	288	}
	289	}
	290	}
	291
	292	return size;
	293	}
	294
	295	bool hash_table_replace(Hashtable ht, void key, void* value) {
	296	if (ht == NULL \|\| key == NULL \|\| value == NULL) return false;
	297
	298	uint32_t index = hash_table_index(ht, key);
	299
	300	Node* node = ht->nodes[index];
	301	while (node != NULL && ht->compare(node->data, key) == false) {
	302	node = node->next;
	303	}
	304
	305	if (node == NULL)
	306	return hash_table_insert(ht, key, value);
	307	else {
	308	free(node->data);
	309	node->key = key;
	310	node->data = value;
	311	}
	312
	313	return true;
	314	}
	315
1d8fe1f7 MR	316	uint64_t int_hash(const void* key) {
	317	return (uint64_t) key;
	318	}
	319
	320	uint64_t str_hash(const void* key) {
	321	const signed char* p;
	322	uint64_t h = 5381;
	323
	324	for (p = key; *p != '\0'; p++) {
	325	h = (h << 5) + h + *p;
	326	}
	327
	328	return h;
	329	}
	330
	331	uint64_t ptr_hash(const void* key) {
	332	return (uint64_t)key;
	333	}
	334
	335	bool int_equal(const void* a, const void* b) {
	336	return ((const int) a) == ((const int) b);
	337	}
	338
	339	bool str_equal(const void* a, const void* b) {
	340	const char string1 = (const char) a;
	341	const char string2 = (const char) b;
	342
	343	return strcmp (string1, string2) == 0;
	344	}
	345
	346	bool ptr_equal(const void* a, const void* b) {
	347	return a == b;
	348	}
	349