I am trying to implement a hashtable that supports character keys and can return any type of value contained in a struct as long as it contains as long as it contains Bucket as one of its members.

The user has to supply the size of the hashtable (preferrably a large enough prime number) in the calling function.

It uses sdbm as a hash function. (Maybe adding a function pointer to let the user specify the kind of hash function they want to use could be a flexible option?)

Any code improvements/suggestions are welcome.

It uses a chaining mechanism using linked lists.

Here is the prototype:

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include "../linked_list/linked_list.h"
#include <stdlib.h>
#include <string.h>
#include <stddef.h>

#define HT_INIT_FAILURE -1
#define HT_INIT_SUCCESS 0

#define HT_MAGIC_SIZE 997

typedef struct bucket
{
  char * key;
  LL_Node ll_node;
} Bucket;

typedef struct hashtable
{
  Bucket ** buckets;
  unsigned int size;
} Hashtable;
  

int hashtable_init(Hashtable * hashtable, int size);
void hashtable_put(Hashtable * hashtable, char * key, Bucket * bucket);
int hashtable_key_exists(Hashtable * hashtable, char * key);
void hashtable_close(Hashtable * hashtable);
Bucket * __hashtable_get_bucket(Hashtable * hashtable, char * key);

#define hashtable_get_value(bucket, struct_type, struct_member)     \
  ((struct_type *)((char *)(bucket) - (unsigned long)(offsetof(struct_type, struct_member))))

#define hashtable_get(hashtable, key, struct_type, struct_member)   \
  hashtable_get_value(__hashtable_get_bucket(hashtable, key), struct_type, struct_member);

#endif

hashtable.c

#include "hashtable.h"

int hashtable_init(Hashtable * ht, int size)
{
  if ((ht->buckets = (Bucket **) malloc (sizeof(Bucket *) * size)) == NULL)
    return HT_INIT_FAILURE;
  ht->size = size;
  
  for (int i = 0; i < size; i++)
    ht->buckets[i] = NULL;

  return HT_INIT_SUCCESS;
}

unsigned long __hash_sdbm(char *str)
{
  unsigned long hash = 0;
  int c;
  
  while ((c = *str++))
    hash = c + (hash << 6) + (hash << 16) - hash;
  
  return hash;
}
int __key_matches(char * source, char * target)
{
  return (strcmp(source, target) == 0);
}

void __insert_bucket(Hashtable * hashtable, int index, Bucket * bucket)
{
  if (hashtable->buckets[index] == NULL) {
    
    LL_Node * head = &bucket->ll_node;  
    ll_create_list(head);
    hashtable->buckets[index] = bucket;
  }
  else {

    LL_Node * head = &(hashtable->buckets[index]->ll_node);
    LL_Node * ptr = head;
    int head_key_matches = (__key_matches(bucket->key,
                      hashtable->buckets[index]->key));
    
    Bucket * search_bucket;
    
    ll_foreach(ptr, head) { 
      search_bucket = ll_get(ptr, Bucket, ll_node); 
      if (head_key_matches || __key_matches(bucket->key, search_bucket->key)) { 
        ll_replace(ptr, &bucket->ll_node); 
    return; 
      }     
    }
    ll_push_front(head, &(bucket->ll_node));
  }
}

void hashtable_put(Hashtable * ht, char * key, Bucket * bucket)
{
  int index = __hash_sdbm(key) % ht->size;
  bucket->key = key;
  __insert_bucket(ht, index, bucket);
}

Bucket * __hashtable_get_bucket(Hashtable * hashtable, char * key)
{
  int index = __hash_sdbm(key) % hashtable->size;  

  if (hashtable->buckets[index] == NULL)
    return NULL;

  Bucket * bucket = hashtable->buckets[index];
  
  if (__key_matches(bucket->key, key)) {
    return bucket;
  }

  else {
    LL_Node * ptr;
    LL_Node * head = &(hashtable->buckets[index]->ll_node);
  
    ll_foreach(ptr, head) {
      bucket = ll_get(ptr, Bucket, ll_node);
      if (__key_matches(key, bucket->key)) {
    return bucket;
      }
    }
    return NULL;
  }
}

int hashtable_key_exists(Hashtable * ht, char * key)
{
  return (__hashtable_get_bucket(ht, key) == NULL);
}

void hashtable_close(Hashtable *ht)
{
  free(ht->buckets);
  ht->size = 0;
}

Here is an example of how it can be used:

#include "hashtable.h"
#include <stdlib.h>
#include <stdio.h>

typedef struct entry_t {
  int val;
  Bucket bucket;  
} Entry;

int main()
{
  Hashtable hashtable;
  Hashtable * ht = &hashtable;
  
  if (hashtable_init(ht, 10) == HT_INIT_FAILURE)
    return EXIT_FAILURE;
  
  Entry * entry = (Entry *) malloc(sizeof(Entry));
  entry->val = 10;
  
  hashtable_put(ht, "john", &(entry->bucket));

  Entry * res;

  Entry * entry2 = (Entry *) malloc(sizeof(Entry));
  entry2->val = 12;
  
  hashtable_put(ht, "pan", &(entry2->bucket));

  Entry * entry3 = (Entry *) malloc(sizeof(Entry));
  entry3->val = 15;
  
  hashtable_put(ht, "tran", &(entry3->bucket));

  res = hashtable_get(ht, "john", Entry, bucket);
  printf("%d\n", res->val);
  
  res = hashtable_get(ht, "pan", Entry, bucket);
  printf("%d\n", res->val);

  res = hashtable_get(ht, "tran", Entry, bucket);
  printf("%d\n", res->val);

  Entry * entry4 = (Entry *) malloc(sizeof(Entry));
  entry4->val = 100;
  
  hashtable_put(ht, "pan", &(entry4->bucket));

  res = hashtable_get(ht, "john", Entry, bucket);
  printf("Replaced\n%d\n", res->val);
  
  res = hashtable_get(ht, "pan", Entry, bucket);
  printf("%d\n", res->val);

  res = hashtable_get(ht, "tran", Entry, bucket);
  printf("%d\n", res->val);
  
  if (hashtable_key_exists(ht, "trans"))
    printf("Doesn't exist");
  else
    printf("Exists");

  if (hashtable_key_exists(ht, "tran"))
    printf("Doesn't exist");
  else
    printf("Exists");

  free(entry);
  free(entry3);
  free(entry2);
  free(entry4);

  hashtable_close(ht);

  return EXIT_SUCCESS;
}

Please excuse the lazily written test main function.