Hashtable Implementation in C

Please only implement the void ht_put(), void free_hashtable(), void ht_del(hashtable_t *ht, char *key) and void ht_rehash(hashtable_t *ht, unsigned long newsize)

------------------------

-------------------------

------------------------

#include

#include

#include "hashtable.h"

unsigned long hash(char *str) {

unsigned long hash = 5381;

int c;

while ((c = *str++))

hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

return hash;

}

hashtable_t *make_hashtable(unsigned long size) {

hashtable_t *ht = malloc(sizeof(hashtable_t));

ht->size = size;

ht->buckets = calloc(sizeof(bucket_t *), size);

return ht;

}

void ht_put(hashtable_t *ht, char *key, void *val) {

/* FIXME: the current implementation doesn't update existing entries */

unsigned int idx = hash(key) % ht->size;

bucket_t *b = malloc(sizeof(bucket_t));

b->key = key;

b->val = val;

b->next = ht->buckets[idx];

ht->buckets[idx] = b;

}

void *ht_get(hashtable_t *ht, char *key) {

unsigned int idx = hash(key) % ht->size;

bucket_t *b = ht->buckets[idx];

while (b) {

if (strcmp(b->key, key) == 0) {

return b->val;

}

b = b->next;

}

return NULL;

}

void ht_iter(hashtable_t *ht, int (*f)(char *, void *)) {

bucket_t *b;

unsigned long i;

for (i=0; isize; i++) {

b = ht->buckets[i];

while (b) {

if (!f(b->key, b->val)) {

return ; // abort iteration

}

b = b->next;

}

}

}

void free_hashtable(hashtable_t *ht) {

free(ht); // FIXME: must free all substructures!

}

/* TODO */

void ht_del(hashtable_t *ht, char *key) {

}

void ht_rehash(hashtable_t *ht, unsigned long newsize) {

}