hashtable.c

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