#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;
}
projects / hashtable.git / blobdiff