4
\$\begingroup\$

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.

Linked list implementation

linked_list.h

#ifndef LLIST_H
#define LLIST_H

/* A generic-ish typed circular doubly linked list implementation
 * A part of the DSLIBC
 * This is loosely based on the Linux kernel's list.h
 */
#include <stddef.h>

typedef struct ll_node 
{
  struct ll_node * next, * prev;
} LL_Node;

void ll_push_back(LL_Node * head, LL_Node * new_node);
void ll_push_front(LL_Node * head, LL_Node * new_node);
void ll_delete(LL_Node * node);
void ll_replace(LL_Node * old, LL_Node * new);
void ll_create_list(LL_Node * new_head_ptr);

/*
 * Get the struct stored in that node location
 * A neat trick that gets the address of the struct housing the \
 * LL_Node
 */
#define ll_get(node, struct_type, struct_member)            \
  ((struct_type *)((char *)(node) - (unsigned long)(offsetof(struct_type, struct_member))))

/*
 * Iterate over the list
 */
#define ll_foreach(ptr, head)           \
  for (ptr = (head)->next; ptr != head;     \
       ptr = ptr->next)

/*
 * Iterate backwards
 */
#define ll_foreach_back(ptr, head)      \
  for (ptr = (head)->prev; ptr != head;     \
       ptr = ptr->prev)
/*
 * Iterate over each item safely 
 * Allows for freeing of objects without any errors
 */
#define ll_foreach_safe(ptr, temp, head)            \
  for (ptr = (head)->next, temp = ptr->next; ptr != head;   \
       ptr = temp, temp = ptr->next)

#endif

linked_list.c:

#include "linked_list.h"

/**
 * Initialize the list
 * Supply the head ptr address from the actual structure that is to be stored
 */
void ll_create_list(LL_Node * new_head_ptr)
{
  new_head_ptr->next = new_head_ptr;
  new_head_ptr->prev = new_head_ptr;
}

void __ll_push_between(LL_Node * prev, LL_Node * next, LL_Node * new)
{
  prev->next = new;
  new->prev = prev;

  new->next = next;
  next->prev = new;
}
/*
 * Insert an element at the end of the list
 * Having a circular list makes sense since we don't have to \
 * traverse all the way to to end to insert an element
 */
void ll_push_back(LL_Node * head, LL_Node * new_node)
{
  __ll_push_between(head->prev, head, new_node);
}

void ll_push_front(LL_Node * head, LL_Node * new_node)
{
  __ll_push_between(head, head->next, new_node);
}

void __ll_re_link(LL_Node * prev, LL_Node * next)
{
  prev->next = next;
  next->prev = prev;
}

void __ll_nullify(LL_Node * node)
{
  node->next = NULL;
  node->prev = NULL;
}
void ll_delete(LL_Node * node)
{
  __ll_re_link(node->prev, node->next);
  __ll_nullify(node);
}

void ll_replace(LL_Node * old, LL_Node * new)
{
  __ll_re_link(old->prev, new);
  __ll_re_link(new, old->next);

  __ll_nullify(old);
}

Note: The above linked list is a generic circular doubly linked list implementation and not specifically made for the hash table. I understand that a singly linked list should suffice for this, but since I made the Linked List library to be used somewhere else, I went ahead and reused it for the hash table.

\$\endgroup\$
  • \$\begingroup\$ The code looks incomplete now because the linked list functions are not included but are used. Could you please add the linked list header and c file. \$\endgroup\$ – pacmaninbw Jun 9 at 13:42
  • \$\begingroup\$ @pacmaninbw Thanks for the suggestion, I have added the linked list implementation as well. \$\endgroup\$ – 2dsharp Jun 9 at 15:26
0
\$\begingroup\$

Don't Hide the Use of Macros

Currently it is unclear in the main program that you are calling macros rather than functions in this line res = hashtable_get(ht, "john", Entry, bucket);. It is not really clear why you are using a macro rather than a function. There does not seem to be a real benefit to using a macro over a function here. Anything that needs to be hidden in the implementation should be hidden in hashtable.c in static functions.

Protect the Global Name Space

All the functions in linked_list.c and hashtable.c are currently global symbols, the use of the double underscore does not hide them from the global name space. The way to remove these functions from the global name space is to make them all static functions. It would also be better to remove the double underscore, this is reserved for library functions.

Two examples would be :

static unsigned long hash_sdbm(char *str)
{
    unsigned long hash = 0;
    int c;

    while ((c = *str++))
        hash = c + (hash << 6) + (hash << 16) - hash;

    return hash;
}

static int key_matches(char * source, char * target)
{
    return (strcmp(source, target) == 0);
}

This might require changes to hashtable.h because of the prototype declaration of

Bucket * __hashtable_get_bucket(Hashtable * hashtable, char * key);

Prefer Calloc Over Malloc When Allocating Arrays

The function calloc(size_t n_items, size_t item_size); is specifically for allocating arrays. In addition to calculating the space necessary to allocate it also clears the values in the entire array. The method it uses to clear the values in the array is more efficient then the method the code is currently using.

\$\endgroup\$
  • \$\begingroup\$ I'm using macros so that I can supply the struct type and the member name of the Bucket so that I can calculate the address of the struct and return the necessary value with the correct datatype, thus making it slightly "generic". Could you suggest a replacement using functions to those macros? That would be very helpful. \$\endgroup\$ – 2dsharp Jun 10 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.