C Feedback on hash table implementation.

[skifli]

As C programmers will know, C doesn't have a implementation for dictionaries, and so you have to implement your own using hash maps. I am new to C, and created a hash map implementation, and would be grateful for any feedback. The program also uses a custom list implementation to allow easy resizing. I understand that I did not include many comments and if you need me to explain what something does (or what I think it does), I will try and explain it without confusing you even more ;-). Also, ignore the `TODOs` please, they're something I'll work on later.

main.c

#include <stdio.h>

#include "Map.c"

int main() {
    // Testing the map.
 
    struct map* mapObj = map_init();

    map_add(mapObj, "fizzbuzz", "I'm the value for the fizzbuzz key.");

    map_delete(mapObj, "fizzbuzz");

    map_add(mapObj, "fizz", "I'm the value for the fizz key.");
    map_add(mapObj, "buzz", "I'm the value for the buzz key.");

    printf("%s", map_find(mapObj, "fizz"));
    printf("%s", map_find(mapObj, "buzz"));

    return 0;
}

Map.c

#include <malloc.h>
#include <stdbool.h>

#include "List.c"

struct map {
    struct list* values;
};

unsigned int map__generateHash(const unsigned char *str) {
    // sdbm hashing algorithm - http://www.cse.yorku.ca/~oz/hash.html#sdbm.

    unsigned long hash = 0;
    int c;

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

    return hash;
}

bool map_add(struct map* self, void* key, void* value) {
    return list_addByIndex(self->values, map__generateHash(key), value);
}

bool map_delete(struct map* self, void *key) {
    return list_removeByIndex(self->values, map__generateHash(key));
}

void* map_find(struct map* self, void* key) {
    return list_getByIndex(self->values, map__generateHash(key));
}

struct map* map_init(void) {
    struct map* self = malloc(sizeof(struct map));

    self->values = list_init();

    return self;
}

List.c

#include <malloc.h>
#include <stdbool.h>
#include <stdint.h>

struct list {
    size_t bufSize, initBufSize, length;
    void** values;
};

bool list__realloc(struct list* self, size_t bufSize) {
    void **temp = realloc(self->values, bufSize);

    if (temp) {
        self->bufSize = bufSize;
        self->values = temp;
    } else { // TODO: Add error stating 'failure to reallocate memory to the list'.
        return false;
    }

    return true;
}

bool list__addByIndex(struct list* self, size_t index, void *value) {
    self->values[index-1] = value;

    size_t lengthTemp = (self->bufSize / self->initBufSize);

    if (lengthTemp > self->length) {
        self->length = lengthTemp;
    }

    return true;
}

bool list_addByIndex(struct list* self, size_t index, void *value) {
    if (index == 0) {
        return NULL;
    } else if (self->bufSize == 0 && index == 1) {
        self->bufSize = self->initBufSize;

        return list__addByIndex(self, index, value);
    } else if (self->length == 1 && index == 1) {
        list__realloc(self, self->initBufSize * 2);
    } else {
        list__realloc(self, self->bufSize + (self->initBufSize * (index - self->length)));
    }

    return list__addByIndex(self, index, value);
}

bool list_append(struct list* self, void *value) {
    return list_addByIndex(self, self->length+1, value);
}

void* list_getByIndex(struct list* self, size_t index) {
    if (index == 0) {
        return NULL;
    } else if (index > self->length) {
        return "Index not found!"; // TODO: Add error stating 'index was not found in list'.
    } else {
        return self->values[index-1];
    }
}

bool list_removeByIndex(struct list* self, size_t index) {
    if (index < 2) {
        return NULL;
    } else if (index > self->length) {
        return "Index not found!"; // TODO: Add error stating 'index was not found in list'.
    } else {
        for (size_t i = index; i < self->length; i++) {
            self->values[index-1] = self->values[index];
        }

        self->length--;
        self->values[index] = NULL;
        list__realloc(self, self->bufSize - self->initBufSize);
    }
}

struct list* list_init(void) {
    struct list* self = malloc(sizeof(struct list));

    self->bufSize = 0; // Not true, just used for starting the list.
    self->initBufSize = sizeof *self->values;
    self->length = 0;
    self->values = malloc(self->initBufSize);

    return self;
}

 

[Johna]

map_add(mapObj, "fizz", "I'm the value for the fizz key.);

In line 14 of main.c you don't have the closing quote for that string

 

[skifli]

In line 14 of main.c you don't have the closing quote for that string

Ah sorry, I didn't realize that, since I added those keys especially for the posting the code here.