#include <stdlib.h>
#include <stdio.h>
#include <string.h>

// www.cse.yorku.ca/~oz/hash.html
unsigned long stringHash(const char *str, unsigned long modulinho)
{
    unsigned long hash = 5381;
    int c;

    while ((c = (unsigned char)*str++))
        hash = ((hash << 5) + hash) + c;

    return hash % modulinho;
}


struct Bucket {
    char *key;
    char *value;
    struct Bucket *next;
};

struct Bucket *createBucket(const char *key, const char *value)
{
    if (!key || !value) {
        return NULL;
    }

    struct Bucket *bucket = malloc(sizeof(struct Bucket));
    if (!bucket) {
        return NULL;
    }

    bucket->key = malloc(strlen(key) + 1);
    if (!bucket->key) {
        free(bucket);
        return NULL;
    }
    bucket->value = malloc(strlen(value) + 1);
    if (!bucket->value) {
        free(bucket->key);
        free(bucket);
        return NULL;
    }
    
    strcpy(bucket->key, key);
    strcpy(bucket->value, value);

    bucket->next = NULL;
    return bucket;
}

void freeBucketList(struct Bucket *bucket)
{
    if (!bucket) {
        return;
    }

    free(bucket->key);
    free(bucket->value);

    if (bucket->next) {
        freeBucketList(bucket->next);
    }

    free(bucket);
}


struct Bucket *addBucketToList(struct Bucket *head, const char *key, const char *value)
{
    struct Bucket *newBucket = createBucket(key, value);
    if (!newBucket) {
        return NULL;
    }

    if (head) {
        struct Bucket *lastBucket = head;
        while (lastBucket->next) {
            lastBucket = lastBucket->next;
        }
        lastBucket->next = newBucket;
        return head;
    }

    return newBucket;  // new head
}

struct Bucket *findBucket(struct Bucket *head, const char *key)
{
    while (head) {
        if (!strcmp(head->key, key)) {
            return head;
        }
        head = head->next;
    }

    return NULL;
}

int replaceBucketValue(struct Bucket *bucket, const char *value)
{
    if (!bucket) {
        return 0;
    }

    char *newValue = malloc(strlen(value) + 1);
    if (!newValue) {
        return 0;
    }

    strcpy(newValue, value);
    free(bucket->value);
    bucket->value = newValue;

    return 1;
}

struct HashMap {
    unsigned long bucketsSize;
    struct Bucket **buckets;
};

struct HashMap *createHashMap(unsigned long bucketsSize)
{
    struct HashMap *map = malloc(sizeof(struct HashMap));
    if (!map) {
        return NULL;
    }

    map->bucketsSize = bucketsSize;
    map->buckets = calloc(bucketsSize, sizeof(struct Bucket*));
    if (!map->buckets) {
        free(map);
        return NULL;
    }

    return map;
}

void freeHashMap(struct HashMap *map)
{
    if (!map) {
        return;
    }

    for (unsigned long i = 0; i < map->bucketsSize; i++) {
        freeBucketList(map->buckets[i]);
    }

    free(map);
}

int mapAddKeyValue(struct HashMap *map, const char *key, const char *value)
{
    if (!map) {
        return 0;
    }

    unsigned long hash = stringHash(key, map->bucketsSize);
    struct Bucket *existingBucket = findBucket(map->buckets[hash], key);
    if (existingBucket) {
        return replaceBucketValue(existingBucket, value);
    } else {
        struct Bucket *newHead = addBucketToList(map->buckets[hash], key, value);
        if (!newHead) {
            return 0;
        }
        map->buckets[hash] = newHead;
    }

    return 1;
}

const char *mapGetValue(struct HashMap *map, const char *key)
{
    if (!map) {
        return NULL;
    }

    unsigned long hash = stringHash(key, map->bucketsSize);
    struct Bucket *bucket = map->buckets[hash];

    if (!bucket) {
        return NULL;
    }
    
    if (!bucket->next) {
        return bucket->value;
    }

    bucket = findBucket(bucket, key);
    if (bucket) {
        return bucket->value;
    } else {
        return NULL;
    }
}

int main()
{
    struct HashMap *map = createHashMap(100);
    if (!map) {
        printf("Map creating failed\n");
        return EXIT_FAILURE;
    }

    const char *pairs[2][2] = { {"govno", "shit"}, {"kod", "code"} };

    for (unsigned int i = 0; i < 2; i++) {
        mapAddKeyValue(map, pairs[i][0], pairs[i][1]);
    }

    for (unsigned int i = 0; i < 2; i++) {
        printf("map[%s] = %s\n", pairs[i][0], mapGetValue(map, pairs[i][0]));
    }

    freeHashMap(map);
    return EXIT_SUCCESS;
}