Hashtable Implementation in C Please only implement the void ht_put(), void free
ID: 3785289 • Letter: H
Question
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 <stdlib.h>
#include <string.h>
#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; i<ht->size; 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) {
}
Explanation / Answer
Since the complete code has not been provided, I could not test the code..
void ht_rehash(hashtable_t *ht, unsigned long newsize) {
hashtable_t *working = make_hashtable(newsize);
for (unsigned long i = 0; i < ht->size; i++) {
bucket_t *b = ht->buckets[i];
while (b) {
ht_put(working, b->key, b->val);
b = b->next;
}
}
free_hashtable(ht);
}
void ht_del(hashtable_t* ht, char* key)
{
unsigned int h = hash(key) % ht->capacity;
hashtable_t* e = ht->table[h];
hashtable_t* prev = NULL;
while(e != NULL)
{
if(!strcmp(e->key, key))
{
void* ret = e->data;
if(prev != NULL)
prev->next = e->next;
else
hasht->table[h] = e->next;
free(e);
e = NULL;
ht->e_num --;
return ret;
}
prev = e;
e = e->next;
}
return NULL;
}
void free_hashtable(hashtable_t *ht) {
free(ht->buckets);
free(ht);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.