I'm attempting to implement a hash table with separate chaining in C. It works fine, but is there something that I should optimize, fix or maybe add some features?
hashtable.h
#ifndef HASHTABLE_H
#define HASHTABLE_H
enum data_type {
INTEGER, FLOAT, DOUBLE,
CHARACTER, STRING,
SET, LIST, HASH
};
struct node_t {
char *key;
void *value;
enum data_type type;
struct node_t *next, *prev;
};
struct hashtable_t {
int size, used;
struct node_t **table;
};
struct hashtable_t *create_ht();
void delete_ht(struct hashtable_t *ht);
void ht_insert(struct hashtable_t *ht, char *key, void *value, enum data_type type);
struct node_t *ht_search(struct hashtable_t *ht, char *key);
void ht_delete(struct hashtable_t *ht, char *key);
void ht_update(struct hashtable_t *ht, char *key, void *value, enum data_type type);
#endif // HASHTABLE_H
hashtable.c
#include "hashtable.h"
#include <stdlib.h>
#include <string.h>
#define HT_INITIAL_SIZE 11
static int hash(char *key, int size) {
long hash = strlen(key);
for (int i = 0; i < strlen(key); ++key, ++i) {
hash = ((hash << 5) ^ (hash >> 27)) ^ (*key);
hash %= size;
}
return (int) hash;
}
static int check_prime(int n) {
if (n <= 1)
return 0;
for (int i = 2; i*i <= n; i++) {
if (n % i == 0)
return 0;
}
return 1;
}
static int next_prime(int n) {
while (check_prime(n) != 1)
n++;
return n;
}
static struct hashtable_t *create_new_sized_ht(int size) {
struct hashtable_t *ht = malloc(sizeof(struct hashtable_t));
ht->table = calloc((size_t) size, sizeof(struct node_t *));
ht->size = size;
ht->used = 0;
return ht;
}
static void resize_ht(struct hashtable_t *ht, int size) {
if (ht->used > size || size < HT_INITIAL_SIZE)
return;
struct hashtable_t *resized_ht = create_new_sized_ht(size);
for (int i = 0; i < ht->size; i++) {
struct node_t *nd = ht->table[i], *next;
while (nd) {
ht_insert(resized_ht, nd->key, nd->value, nd->type);
nd = nd->next;
}
}
ht->size = resized_ht->size;
struct node_t **temp_table = ht->table;
ht->table = resized_ht->table;
resized_ht->table = temp_table;
delete_ht(resized_ht);
}
static void resize_up_ht(struct hashtable_t *ht) {
int size = next_prime(ht->size * 2);
resize_ht(ht, size);
}
static void resize_down_ht(struct hashtable_t *ht) {
int size = next_prime(ht->size / 2);
resize_ht(ht, size);
}
struct hashtable_t *create_ht() {
return create_new_sized_ht(HT_INITIAL_SIZE);
}
void delete_ht(struct hashtable_t *ht) {
for (int i = 0; i < ht->size; i++) {
struct node_t *head = ht->table[i], *next;
while (head) {
next = head->next;
free(head);
head = next;
}
}
free(ht->table);
free(ht);
}
void ht_insert(struct hashtable_t *ht, char *key, void *value, enum data_type type) {
if (ht->used >= ht->size * 0.80)
resize_up_ht(ht);
int h = hash(key, ht->size);
struct node_t *head = ht->table[h], *prev = NULL;
while (head) {
prev = head;
head = head->next;
}
struct node_t *nd = malloc(sizeof(struct node_t));
nd->key = key;
nd->value = value;
nd->type = type;
nd->prev = prev;
nd->next = NULL;
if (prev)
prev->next = nd;
else
ht->table[h] = nd;
ht->used++;
}
struct node_t *ht_search(struct hashtable_t *ht, char *key) {
int h = hash(key, ht->size);
struct node_t *head = ht->table[h];
while (head) {
if (strcmp(head->key, key) == 0)
return head;
else
head = head->next;
}
return NULL;
}
void ht_delete(struct hashtable_t *ht, char *key) {
if (ht->used <= ht->size * 0.10)
resize_down_ht(ht);
struct node_t *nd = ht_search(ht, key);
if (nd) {
if (nd->prev && nd->next) {
nd->prev->next = nd->next;
nd->next->prev = nd->prev;
} else if (!nd->prev) {
ht->table[hash(nd->key, ht->size)] = nd->next;
} else if (nd->prev && !nd->next) {
nd->prev->next = NULL;
}
free(nd);
ht->used--;
}
}
void ht_update(struct hashtable_t *ht, char *key, void *value, enum data_type type) {
struct node_t *nd = ht_search(ht, key);
if (nd) {
nd->value = value;
nd->type = type;
}
}