From 8c5be41668150c79bc1c597f4313d6b6938fe559 Mon Sep 17 00:00:00 2001 From: Michael Rasmussen Date: Fri, 31 Mar 2023 00:06:03 +0200 Subject: [PATCH] almost complete Signed-off-by: Michael Rasmussen --- hashtable.c | 224 +++++++++++++++++++++++++++++++++++++++++----------- hashtable.h | 26 +++++- test.c | 150 ++++++++++++++++++++++++++++++++--- 3 files changed, 346 insertions(+), 54 deletions(-) diff --git a/hashtable.c b/hashtable.c index f5569fb..aa30132 100644 --- a/hashtable.c +++ b/hashtable.c @@ -3,62 +3,78 @@ #include #include "hashtable.h" -typedef struct _Set { - uint64_t key; +typedef struct _Node { + void* key; void* data; -} Set; + struct _Node* next; +} Node; -typedef struct _Hashtable { +struct _Hashtable { uint32_t size; HashFunc hash; EqualFunc compare; - Set** sets; -} Hashtable; + FreeFunc free; + 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); } Hashtable* hash_table_create(HashFunc hf, EqualFunc ef) { - return hash_table_create_full(hf, ef, TABLESIZE); + return hash_table_create_full(hf, ef, TABLESIZE, NULL); +} + +Hashtable* hash_table_create_notify(HashFunc hf, EqualFunc ef, FreeFunc ff) { + return hash_table_create_full(hf, ef, TABLESIZE, ff); } -Hashtable* hash_table_create_full(HashFunc hf, EqualFunc ef, uint32_t size) { +Hashtable* hash_table_create_full(HashFunc hf, EqualFunc ef, uint32_t size, FreeFunc ff) { Hashtable* ht = malloc(sizeof(*ht)); ht->size = size; ht->hash = hf; ht->compare = ef; - ht->sets = calloc(sizeof(Set*), ht->size); + if (ff) { + ht->free = ff; + } else { + ht->free = free; + } + ht->nodes = calloc(sizeof(Node*), ht->size); return ht; } void hash_table_destroy(Hashtable* ht) { for (uint32_t i = 0; i < ht->size; i++) { - if (ht->sets[i] != NULL) { - Set* tmp = ht->sets[i]; - if (tmp != NULL) { - Set* set = tmp; - free(set->data); - free(set); - } - ht->sets[i] = NULL; + 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->sets); + free(ht->nodes); free(ht); } void hash_table_print(Hashtable* ht) { printf("Start Table\n"); for (uint32_t i = 0; i < ht->size; i++) { - if (ht->sets[i] == NULL) { + if (ht->nodes[i] == NULL) { //printf("\t%i\t---\n", i); } else { printf("\t%i\t\n", i); - Set* tmp = ht->sets[i]; - if (tmp != NULL) { - printf("\"%ju\" - (%p)", tmp->key, tmp->data); + Node* node = ht->nodes[i]; + while (node != NULL) { + printf("\"%p\" - (%p)", node->key, node->data); + node = node->next; } printf("\n"); } @@ -70,19 +86,16 @@ bool hash_table_insert(Hashtable* ht, const void* key, void* obj) { if (key == NULL || obj == NULL || ht == NULL) return false; // implement chaning - void* found = hash_table_lookup(ht, key); - if (found != NULL) { - printf("[%s:%s] - %s: Missing chaining\n", (const char*) found, (const char*) key, (const char*) obj); - return false; - } + if (hash_table_lookup(ht, key) != NULL) return false; uint32_t index = hash_table_index(ht, key); - Set* set = malloc(sizeof(*set)); - set->data = obj; - set->key = index; + Node* node = malloc(sizeof(*node)); + node->data = obj; + node->key = (void*)key; - ht->sets[index] = set; + node->next = ht->nodes[index]; + ht->nodes[index] = node; return true; } @@ -90,30 +103,153 @@ void* hash_table_lookup(Hashtable* ht, const void* key) { if (key == NULL || ht == NULL) return false; uint64_t index = hash_table_index(ht, key); - Set* set = ht->sets[index]; - if (set == NULL) return NULL; - //printf("find: %p -> found: %p\n", key, set->data); + 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); - if (ht->compare(set->data, key)) - return set->data; - else - return NULL; + 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); - Set* tmp = ht->sets[index]; - if (tmp != NULL && ht->compare((void*)tmp->key, (void*)index) == false) return NULL; - // just in case - if (tmp == NULL) return NULL; + 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 = tmp->data; - free(tmp); + 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; +} + uint64_t int_hash(const void* key) { return *(uint64_t*) key; } diff --git a/hashtable.h b/hashtable.h index f510182..23c8838 100644 --- a/hashtable.h +++ b/hashtable.h @@ -9,7 +9,24 @@ typedef uint64_t (*HashFunc)(const void*); typedef bool (*EqualFunc)(const void*, const void*); +typedef void (*FreeFunc)(void*); typedef struct _Hashtable Hashtable; +typedef void (*ForeachFunc)(void*, void*, void*); + +typedef struct _HashtableIter { + /* Private */ + void* dummy1; + void* dummy2; + void* dummy3; + int64_t dummy4; +} HashtableIter; + + +typedef struct _List { + void* data; + struct _List* next; +} List; + uint64_t int_hash(const void*); uint64_t str_hash(const void*); @@ -19,12 +36,19 @@ bool str_equal(const void*, const void*); bool ptr_equal(const void*, const void*); Hashtable* hash_table_create(HashFunc hf, EqualFunc ef); -Hashtable* hash_table_create_full(HashFunc hf, EqualFunc ef, uint32_t size); +Hashtable* hash_table_create_notify(HashFunc hf, EqualFunc ef, FreeFunc ff); +Hashtable* hash_table_create_full(HashFunc hf, EqualFunc ef, uint32_t size, FreeFunc ff); void hash_table_destroy(Hashtable* ht); void hash_table_print(Hashtable* ht); bool hash_table_insert(Hashtable* ht, const void* key, void* obj); void* hash_table_lookup(Hashtable* ht, const void* key); void* hash_table_delete(Hashtable* ht, const void* key); +List* hash_table_keys(Hashtable* ht); +List* hash_table_values(Hashtable* ht); +void hash_table_list_free(List* list); +void hash_table_foreach(Hashtable* ht, ForeachFunc, void* userdata); +void hash_table_iter_init(HashtableIter* iter, Hashtable* ht); +bool hash_table_iter_next(HashtableIter* iter, void** key, void** value); #endif diff --git a/test.c b/test.c index 5259e7e..8cf65c4 100644 --- a/test.c +++ b/test.c @@ -2,13 +2,19 @@ #include #include #include +#include #include "hashtable.h" #define MAX_LINE 4096 -uint64_t word_hash_func(const char* name, size_t length) { +typedef struct _Node { + char* name; +} Node; + +uint64_t word_hash_func(const void* o) { uint64_t hash_value = 0; - for (size_t i = 0; i < length; i++) { + const char* name = o; + for (size_t i = 0; i < strlen(name); i++) { hash_value += name[i]; hash_value = hash_value * name[i]; } @@ -22,6 +28,40 @@ void generate_random_word(char* buffer, size_t length) { buffer[length - 1] = 0; } +void my_str_free(void* o) { + printf("Freeing %p\n", o); + free(o); +} + +void my_ptr_free(void* o) { + Node* node = o; + //printf("Freeing %p\n", node); + free(node->name); + free(node); +} + +bool my_ptr_equal(const void* a, const void* b) { + const Node* nodea = a; + const Node* nodeb = b; + + if (nodea == NULL || nodeb == NULL) return false; + if (nodea->name == NULL || nodeb->name == NULL) return false; + + printf("Comparing %s to %s\n", nodea->name, nodeb->name); + if (strcmp(nodea->name, nodeb->name) == 0) + return true; + return false; +} + +void count_good_guesses(void* key, void* value, void* userdata) { + uint32_t* good_guesses = userdata; + Node* node = value; + + (*good_guesses)++; + char* s1 = node->name; + printf("%u: Found: %p - %s\n", *good_guesses, key, s1); +} + int main(int argc, char** argv) { if (argc != 3) { printf("usage: %s \n", argv[0]); @@ -31,7 +71,7 @@ int main(int argc, char** argv) { char* filename = argv[1]; uint32_t num_guesses = atol(argv[2]); - Hashtable* table = hash_table_create(str_hash, str_equal); + Hashtable* table = /*hash_table_create(str_hash, str_equal)*/ hash_table_create_notify(ptr_hash, my_ptr_equal, my_ptr_free); FILE* fp = fopen(filename, "r"); char* buffer = calloc(sizeof(char), MAX_LINE); @@ -39,35 +79,127 @@ int main(int argc, char** argv) { uint32_t failed = 0; while (!feof(fp) && fgets(buffer, MAX_LINE, fp) != NULL) { buffer[strcspn(buffer, "\r\n")] = 0; - char* newentry = malloc(strlen(buffer) + 1); - strcpy(newentry, buffer); +/* char* newentry = strdup(buffer); bool result = hash_table_insert(table, newentry, newentry); if (result == false) { printf("Failed [%u] storing %s\n", ++failed, newentry); free(newentry); } else numwords++; +*/ + Node* node = calloc(sizeof(Node*), 1); + node->name = strdup(buffer); + bool result = hash_table_insert(table, node, node); + if (result == false) { + printf("Failed [%u] storing %s\n", ++failed, node->name); + free(node->name); + free(node); + } else + numwords++; } - fclose(fp); + printf("Loaded %d words into the table.\n", numwords); +/* + uint32_t good_guesses = 0; + fp = fopen(filename, "r"); + void* data = NULL; + Node* node = calloc(sizeof(Node*), 1); + while (!feof(fp) && fgets(buffer, MAX_LINE, fp) != NULL) { + buffer[strcspn(buffer, "\r\n")] = 0; + node->name = strdup(buffer); + //printf("Buffer: %s\n", node->name); + if ((data = hash_table_lookup(table, node)) != NULL) { + char* s1 = ((Node*) data)->name; + printf("Lookup: %s - Found: %s\n", node->name, s1); + good_guesses++; + } + free(node->name); + } + free(node); + + fclose(fp); +*/ +/* //hash_table_print(table); uint32_t good_guesses = 0; const int shortest_guess = 2; const int longest_guess = 15; void* data = NULL; + Node* lookup = calloc(sizeof(Node*), 1); for (uint32_t i = 0; i < num_guesses; i++) { generate_random_word(buffer, shortest_guess + (rand() % (longest_guess - shortest_guess))); - if ((data = hash_table_lookup(table, buffer)) != NULL) { - printf("Lookup: %s - Found: %s\n", buffer, (char*) data); + lookup->name = strdup(buffer); + printf("Buffer: %s\n", lookup->name); + if ((data = hash_table_lookup(table, lookup)) != NULL) { + char* s1 = ((Node*) data)->name; + printf("Lookup: %s - Found: %s\n", lookup->name, s1); good_guesses++; } + free(lookup->name); } + free(lookup); printf("%u out of %u guesses were in the table\n", good_guesses, num_guesses); - +*/ free(buffer); + + printf("---------------------------------------\n"); + List* values = hash_table_values(table); + List* head = values; + size_t i = 1; + void* data = NULL; + uint32_t good_guesses = 0; + while (head != NULL) { + Node* d = head->data; + printf("%lu: %s\n", i++, (char *) d->name); + if ((data = hash_table_lookup(table, d)) != NULL) { + char* s1 = ((Node*) data)->name; + printf("Lookup: %s - Found: %s\n", d->name, s1); + good_guesses++; + } + head = head->next; + } + hash_table_list_free(values); + + printf("%u out of %u inserted words in table were in the table\n", good_guesses, numwords); + +/* + List* keys = hash_table_keys(table); + head = keys; + data = NULL; + good_guesses = 0; + i = 1; + while (head != NULL) { + Node* d = head->data; + printf("%lu: %p\n", i++, d->name); + if ((data = hash_table_lookup(table, d)) != NULL) { + char* s1 = ((Node*) data)->name; + printf("Lookup: %s - Found: %s\n", d->name, s1); + good_guesses++; + } + head = head->next; + } + hash_table_list_free(keys); +*/ + good_guesses = 0; + hash_table_foreach(table, count_good_guesses, &good_guesses); + + printf("%u out of %u inserted words in table were in the table\n", good_guesses, numwords); + + HashtableIter iter; + void* key/* = malloc(sizeof(void*))*/; + void* value/* = malloc(sizeof(void*))*/; + + hash_table_iter_init(&iter, table); + while (hash_table_iter_next(&iter, &key, &value)) { + char* s1 = ((Node*) value)->name; + printf("Key: %p value: %s\n", key, s1); + } + //free(key); + //free(value); + hash_table_destroy(table); } -- 2.39.2