#include <stdlib.h>
#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");
}
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;
}
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;
}
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*);
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
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
+#include <stdbool.h>
#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];
}
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 <wordlist filename> <num guesses>\n", argv[0]);
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);
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);
}
projects / hashtable.git / commitdiff