hashtable.c

   1 #include <string.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include "hashtable.h"
   5
   6 typedef struct _Set {
   7         uint64_t key;
   8         void* data;
   9 } Set;
  10
  11 typedef struct _Hashtable {
  12         uint32_t size;
  13         HashFunc hash;
  14         EqualFunc compare;
  15         Set** sets;
  16 } Hashtable;
  17
  18 static uint32_t hash_table_index(Hashtable* ht, const void* key) {
  19         return (ht->hash(key) % ht->size);
  20 }
  21
  22 Hashtable* hash_table_create(HashFunc hf, EqualFunc ef) {
  23         return hash_table_create_full(hf, ef, TABLESIZE);
  24 }
  25
  26 Hashtable* hash_table_create_full(HashFunc hf, EqualFunc ef, uint32_t size) {
  27         Hashtable* ht = malloc(sizeof(*ht));
  28         ht->size = size;
  29         ht->hash = hf;
  30         ht->compare = ef;
  31         ht->sets = calloc(sizeof(Set*), ht->size);
  32         return ht;
  33 }
  34
  35 void hash_table_destroy(Hashtable* ht) {
  36         for (uint32_t i = 0; i < ht->size; i++) {
  37                 if (ht->sets[i] != NULL) {
  38                         Set* tmp = ht->sets[i];
  39                         if (tmp != NULL) {
  40                                 Set* set = tmp;
  41                                 free(set->data);
  42                                 free(set);
  43                         }
  44                         ht->sets[i] = NULL;
  45                 }
  46         }
  47         hash_table_print(ht);
  48         free(ht->sets);
  49         free(ht);
  50 }
  51
  52 void hash_table_print(Hashtable* ht) {
  53         printf("Start Table\n");
  54         for (uint32_t i = 0; i < ht->size; i++) {
  55                 if (ht->sets[i] == NULL) {
  56                         //printf("\t%i\t---\n", i);
  57                 } else {
  58                         printf("\t%i\t\n", i);
  59                         Set* tmp = ht->sets[i];
  60                         if (tmp != NULL) {
  61                                 printf("\"%ju\" - (%p)", tmp->key, tmp->data);
  62                         }
  63                         printf("\n");
  64                 }
  65         }
  66         printf("End Table\n");
  67 }
  68
  69 bool hash_table_insert(Hashtable* ht, const void* key, void* obj) {
  70         if (key == NULL || obj == NULL || ht == NULL) return false;
  71
  72         // implement chaning
  73         void* found = hash_table_lookup(ht, key);
  74         if (found != NULL) {
  75                 printf("[%s:%s] - %s: Missing chaining\n", (const char*) found, (const char*) key, (const char*) obj);
  76                 return false;
  77         }
  78
  79         uint32_t index = hash_table_index(ht, key);
  80
  81         Set* set = malloc(sizeof(*set));
  82         set->data = obj;
  83         set->key = index;
  84
  85         ht->sets[index] = set;
  86         return true;
  87 }
  88
  89 void* hash_table_lookup(Hashtable* ht, const void* key) {
  90         if (key == NULL || ht == NULL) return false;
  91         uint64_t index = hash_table_index(ht, key);
  92
  93         Set* set = ht->sets[index];
  94         if (set == NULL) return NULL;
  95         //printf("find: %p -> found: %p\n", key, set->data);
  96
  97         if (ht->compare(set->data, key))
  98                 return set->data;
  99         else
 100                 return NULL;
 101 }
 102
 103 void* hash_table_delete(Hashtable* ht, const void* key) {
 104         if (key == NULL || ht == NULL) return false;
 105         uint64_t index = hash_table_index(ht, key);
 106
 107         Set* tmp = ht->sets[index];
 108         if (tmp != NULL && ht->compare((void*)tmp->key, (void*)index) == false) return NULL;
 109         // just in case
 110         if (tmp == NULL) return NULL;
 111
 112         void* result = tmp->data;
 113         free(tmp);
 114         return result;
 115 }
 116
 117 uint64_t int_hash(const void* key) {
 118         return *(uint64_t*) key;
 119 }
 120
 121 uint64_t str_hash(const void* key) {
 122         const signed char* p;
 123         uint64_t h = 5381;
 124
 125         for (p = key; *p != '\0'; p++) {
 126                 h = (h << 5) + h + *p;
 127         }
 128
 129         return h;
 130 }
 131
 132 uint64_t ptr_hash(const void* key) {
 133         return (uint64_t)key;
 134 }
 135
 136 bool int_equal(const void* a, const void* b) {
 137         return *((const int*) a) == *((const int*) b);
 138 }
 139
 140 bool str_equal(const void* a, const void* b) {
 141   const char *string1 = (const char*) a;
 142   const char *string2 = (const char*) b;
 143
 144   return strcmp (string1, string2) == 0;
 145 }
 146
 147 bool ptr_equal(const void* a, const void* b) {
 148         return a == b;
 149 }
 150