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         PrintFunc print;
  18         Node** nodes;
  19 };
  20
  21 typedef struct {
  22         Hashtable* table;
  23         void* dummy2;
  24         void* dummy3;
  25         int64_t pos;
  26 } RealIter;
  27
  28 static uint32_t hash_table_index(Hashtable* ht, const void* key) {
  29         return (ht->hash(key) % ht->size);
  30 }
  31
  32 static void hash_table_default_print(void* data) {
  33         printf("%p", data);
  34 }
  35
  36 Hashtable* hash_table_create(HashFunc hf, EqualFunc ef) {
  37         return hash_table_create_full(hf, ef, TABLESIZE, NULL, NULL);
  38 }
  39
  40 Hashtable* hash_table_create_notify(HashFunc hf, EqualFunc ef, FreeFunc ff) {
  41         return hash_table_create_full(hf, ef, TABLESIZE, ff, NULL);
  42 }
  43
  44 Hashtable* hash_table_create_full(HashFunc hf, EqualFunc ef, uint32_t size, FreeFunc ff, PrintFunc pf) {
  45         Hashtable* ht = malloc(sizeof(*ht));
  46         ht->size = size;
  47         ht->hash = hf;
  48         ht->compare = ef;
  49         if (ff) {
  50                 ht->free = ff;
  51         } else {
  52                 ht->free = free;
  53         }
  54         if (pf) {
  55                 ht->print = pf;
  56         } else {
  57                 ht->print = hash_table_default_print;
  58         }
  59         ht->nodes = calloc(sizeof(Node*), ht->size);
  60         return ht;
  61 }
  62
  63 void hash_table_destroy(Hashtable* ht) {
  64         for (uint32_t i = 0; i < ht->size; i++) {
  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);
  70                 }
  71         }
  72         hash_table_print(ht);
  73         free(ht->nodes);
  74         free(ht);
  75 }
  76
  77 void hash_table_set_print_func(Hashtable* ht, PrintFunc pf) {
  78         ht->print = pf;
  79 }
  80
  81 void hash_table_print(Hashtable* ht) {
  82         printf("Start Table\n");
  83         for (uint32_t i = 0; i < ht->size; i++) {
  84                 if (ht->nodes[i] == NULL) {
  85                         //printf("\t%i\t---\n", i);
  86                 } else {
  87                         printf("\t%i\t\n", i);
  88                         Node* node = ht->nodes[i];
  89                         while (node != NULL) {
  90                                 printf("\"%p\" - (", node->key);
  91                                 ht->print(node->data);
  92                                 printf(")");
  93                                 node = node->next;
  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
 105         if (hash_table_lookup(ht, key) != NULL) return false;
 106
 107         uint32_t index = hash_table_index(ht, key);
 108
 109         Node* node = malloc(sizeof(*node));
 110         node->data = obj;
 111         node->key = (void*)key;
 112
 113         node->next = ht->nodes[index];
 114         ht->nodes[index] = node;
 115         return true;
 116 }
 117
 118 void* hash_table_lookup(Hashtable* ht, const void* key) {
 119         if (key == NULL || ht == NULL) return false;
 120         uint32_t index = hash_table_index(ht, key);
 121
 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;
 128         //printf("find: %p -> found: %p\n", key, node->data);
 129
 130         return node->data;
 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
 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         }
 150
 151         void* result = node->data;
 152         free(node);
 153         return result;
 154 }
 155
 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
 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
 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