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.
