Hash Dictionary implementation in C

hashdict.c

/*
    "Hashdict"
    Biblioteka do szybkiego wyszukiwania elementów w słowniku.
    Biblioteka nie jest zabezpieczona przed błędami użytkownika.
    Użytkownik musi zagwarantować, że nie będzie usuwał elementów z tablicy,
    do której wskazuje wartość zwracana przez funkcję hd_find.
    Biblioteka nie jest zabezpieczona przed błędami użytkownika.
*/

#include "hashdict.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <errno.h>

/*
    Funkcja tworzy nowy słownik.
    Wynik funkcji:
        wskaźnik na strukturę lub
        NULL – jeśli wystąpił błąd alokowania pamięci; funkcja ustawia wtedy errno na ENOMEM.
*/
hash_dict* hd_init(size_t size) {
    hash_dict* hd = (hash_dict*)malloc(sizeof(hash_dict));
    if (hd == NULL) {
        errno = ENOMEM;
        return NULL;
    }
    hd->size = size;
    hd->table = (hd_entry**)calloc(size, sizeof(hd_entry*));
    if (hd->table == NULL) {
        free(hd);
        errno = ENOMEM;
        return NULL;
    }
    return hd;
}

/*
    Funkcja zwraca hash dla ciągu znaków
    Parametry funkcji:
        str - ciąg do zhaszowania
        n - ile znaków wziąść
        size - rozmiar tablicy
    Założenia:
        wygenerowany hash będzie z przedziału [0;size)
*/
inline size_t hd_n_hashstr(const char* str, size_t n, size_t size) {
    size_t hash = 5381; // liczba pierwsza
    for (size_t i = 0; i < n; i++) {
        hash = ((hash << 5) + hash) + str[i]; // hash * 33 + str[i]
    }
    return hash % size;
}

/*
    Funkcja zwraca hash dla ciągu znaków
    Parametry funkcji:
        str - ciąg do zhaszowania
        size - rozmiar tablicy
    Założenia:
        wygenerowany hash będzie z przedziału [0;size)
*/
inline size_t hd_hashstr(const char* str, size_t size) {
    return hd_n_hashstr(str, strlen(str)+1, size);
}

/*
    Funkcja dodaje do słownika nowy element.
    Parametry funkcji:
        hd – wskaźnik na strukturę reprezentującą słownik;
        key – wskaźnik na napis reprezentujący klucz
        value – wskaźnik na wartość - użytkownik ma zagwarantować, że nie zostanie ona usunięta
    Wynik funkcji:
        1 – jeśli element został dodany;
        0 – jeśli element o podanym kluczu już istnieje;
       -1 – jeśli któryś z parametrów jest niepoprawny lub wystąpił błąd alokowania pamięci; funkcja ustawia wtedy errno odpowiednio na EINVAL lub ENOMEM.
*/
int hd_insert(hash_dict* hd, const char* key, hd_value* value) {
    if (hd == NULL || key == NULL || value == NULL) {
        errno = EINVAL;
        return -1;
    }

    return hd_n_insert(hd, key, strlen(key)+1, value);
}

/*
    Funkcja dodaje do słownika nowy element.
    Parametry funkcji:
        hd – wskaźnik na strukturę reprezentującą słownik;
        key – wskaźnik na napis reprezentujący klucz
        n - ile maksymalnie znaków klucza wziąć
        value – wskaźnik na wartość - użytkownik ma zagwarantować, że nie zostanie ona usunięta
    Wynik funkcji:
        1 – jeśli element został dodany;
        0 – jeśli element o podanym kluczu już istnieje;
       -1 – jeśli któryś z parametrów jest niepoprawny lub wystąpił błąd alokowania pamięci; funkcja ustawia wtedy errno odpowiednio na EINVAL lub ENOMEM.
*/
int hd_n_insert(hash_dict* hd, const char* key, size_t n, hd_value* value) {
    if (hd == NULL || key == NULL || value == NULL) {
        errno = EINVAL;
        return -1;
    }
    size_t hash = hd_n_hashstr(key, n, hd->size); // obliczamy hash
    hd_entry* entry = hd->table[hash];
    while (entry != NULL) {
        if (strcmp(entry->key, key) == 0) { // szukamy czy element o danym kluczu już istnieje
            return 0;
        }
        entry = entry->next;
    }

    // tworzymy nowy element
    entry = (hd_entry*)malloc(sizeof(hd_entry));
    if (entry == NULL) {
        errno = ENOMEM;
        return -1;
    }
    
    // tworzymy kopię klucza
    entry->key = strncpy((char*)malloc(n + 1), key, n);
    if (entry->key == NULL) {
        free(entry);
        errno = ENOMEM;
        return -1;
    }

    // dodajemy element do listy
    entry->value = value;
    entry->next = hd->table[hash];
    hd->table[hash] = entry;
    return 1;
}

/*
    Funkcja znajduje element w słowniku.
    Parametry funkcji:
        hd – wskaźnik na strukturę reprezentującą słownik;
        key – wskaźnik na napis reprezentujący klucz.
    Wynik funkcji:
        wskaźnik na wartość lub
        NULL – jeśli element o podanym kluczu nie istnieje lub któryś z parametrów jest niepoprawny.
*/
hd_value* hd_find(hash_dict* hd, const char *key) {
    if (hd == NULL || key == NULL) {
        errno = EINVAL;
        return NULL;
    }
    return hd_n_find(hd, key, strlen(key)+1);
}

/*
    Funkcja znajduje element w słowniku.
    Parametry funkcji:
        hd – wskaźnik na strukturę reprezentującą słownik;
        key – wskaźnik na napis reprezentujący klucz.
        n - ile maksymalnie znaków klucza porównywać
    Wynik funkcji:
        wskaźnik na wartość lub
        NULL – jeśli element o podanym kluczu nie istnieje lub któryś z parametrów jest niepoprawny.
*/
hd_value* hd_n_find(hash_dict* hd, const char *key, size_t n) {
    if (hd == NULL || key == NULL) {
        errno = EINVAL;
        return NULL;
    }
    size_t hash = hd_n_hashstr(key, n, hd->size); // obliczamy hash
    hd_entry* entry = hd->table[hash];
    while (entry != NULL) {
        if (strncmp(entry->key, key, n) == 0) { // szukamy czy element o danym kluczu istnieje
            return entry->value;
        }
        entry = entry->next;
    }
    return NULL;
}

/*
    Funkcja usuwa element z słownika.
    Parametry funkcji:
        hd – wskaźnik na strukturę reprezentującą słownik;
        key – wskaźnik na napis reprezentujący klucz.
    Wynik funkcji:
        1 – jeśli element został usunięty;
        0 – jeśli element o podanym kluczu nie istnieje
       -1 - jeśli któryś z parametrów jest niepoprawny.
*/
int hd_remove(hash_dict* hd, const char* key) {
    if (hd == NULL || key == NULL) {
        errno = EINVAL;
        return -1;
    }
    return hd_n_remove(hd, key, strlen(key)+1);
}

/*
    Funkcja usuwa element z słownika.
    Parametry funkcji:
        hd – wskaźnik na strukturę reprezentującą słownik;
        key – wskaźnik na napis reprezentujący klucz.
        n - ile maksymalnie znaków klucza porównywać
    Wynik funkcji:
        1 – jeśli element został usunięty;
        0 – jeśli element o podanym kluczu nie istnieje
       -1 - jeśli któryś z parametrów jest niepoprawny.
*/
int hd_n_remove(hash_dict* hd, const char* key, size_t n) {
    if (hd == NULL || key == NULL) {
        errno = EINVAL;
        return -1;
    }
    size_t hash = hd_n_hashstr(key, n, hd->size); // obliczamy hash
    hd_entry* entry = hd->table[hash];
    hd_entry* prev = NULL;
    while (entry != NULL) {
        if (strncmp(entry->key, key, n) == 0) { // szukamy czy element o danym kluczu istnieje
            if (prev == NULL) // usuwamy element z początku listy
                hd->table[hash] = entry->next;
            else // usuwamy element ze środka
                prev->next = entry->next;
            hd_deletevalue(entry->value);
            free(entry->key);
            free(entry);
            return 1;
        }
        prev = entry;
        entry = entry->next;
    }
    return 0;
}

/*
    Funkcja usuwa słownik i zwalnia zasoby zajmowane przez niego.
    Parametry funkcji:
        hd – wskaźnik na strukturę reprezentującą słownik.
*/
void hd_delete(hash_dict* hd) {
    if (hd == NULL) return;
    for (size_t i = 0; i < hd->size; i++) {
        hd_entry* entry = hd->table[i];
        while (entry != NULL) {
            hd_entry* next = entry->next;
            hd_deletevalue(entry->value);
            free(entry->key);
            free(entry);
            entry = next;
        }
    }
    free(hd->table);
    free(hd);
}

hashdict.h

#ifndef HASHDICT_H
#define HASHDICT_H

#include <stdio.h>

// Zaimplementowane przez użytkownika
typedef struct hash_dict_value hd_value;

// Implementacja słownika za pomocą hashtable
typedef struct hd_entry {
	char *key;
	hd_value *value;
	struct hd_entry *next;
} hd_entry;

typedef struct hash_dict  {
	size_t size;
	struct hd_entry **table;
} hash_dict;

hash_dict*      hd_init(size_t size);

int             hd_insert(hash_dict* hd, const char* key, hd_value* value);
int             hd_n_insert(hash_dict* hd, const char* key, size_t n, hd_value* value);

hd_value* 		  hd_find(hash_dict* hd, const char *key);
hd_value* 		  hd_n_find(hash_dict* hd, const char *key, size_t n);

int             hd_remove(hash_dict* hd, const char* key);
int             hd_n_remove(hash_dict* hd, const char* key, size_t n);

void            hd_delete(hash_dict* hd);


/*
    Implementacja jako makro, ponieważ nie chcę dodawać zbędnych funkcji do pliku końcowego
    Maktro wypisuje reprezentacje słownika jako JSON do pliku
    Parametry makra:
        hd – wskaźnik na strukturę reprezentującą słownik;
        fp – wskaźnik na strukturę reprezentującą plik.
        tostring - funkcja wypisującą wartość słownika
*/
#define HD_WRITEJSON(hd, fp, tostring)                                        \
  do {                                                                        \
    if (hd != NULL && fp != NULL) {                                           \
        fprintf(fp, "{");                                                     \
        for (size_t i = 0; i < hd->size; i++) {                               \
            hd_entry* entry = hd->table[i];                                   \
            while (entry != NULL) {                                           \
                fprintf(fp, "\"%s\":", entry->key);                           \
                fputs(tostring(entry->value), fp);                            \
                entry = entry->next;                                          \
                if (entry != NULL) fprintf(fp, ", ");                         \
            }                                                                 \
            if (i < hd->size - 1 && hd->table[i] != NULL) fprintf(fp, ", ");  \
        }                                                                     \
        fprintf(fp, "}");                                                     \
    }                                                                         \
  } while (0)

// Zaimplementowane przez użytkownika
void            hd_deletevalue(hd_value* value);

#endif // HASHDICT_H

hashdict_test.c

#include "hashdict.h"
#include <stdio.h>
#include <stdlib.h>

struct hash_dict_value {
    int v;
};
const size_t hash_dict_size = 2048u;
const int max_v = 12;

const size_t malloc_size = 3;

void hd_deletevalue(hd_value* value) {
    free(value);
}

char* tostring(hd_value* val) {
    char* str = malloc(malloc_size);
    sprintf(str, "%d", val->v);
    return str;
}

/*
    Program testuje implementacje słownika
*/
int main() {
    puts("Init");

    struct hash_dict *dict = hd_init(hash_dict_size);

    puts("Add hardcoded tests");
    
    hd_insert(dict, "hello", malloc(sizeof(hd_value)));
    hd_insert(dict, "hi", malloc(sizeof(hd_value)));

    puts("Created struct");

    for (int i = 0; i < max_v; i++) { // creating
        char* name = malloc(malloc_size);
        sprintf(name, "%d", i);
        hd_value *value = malloc(sizeof(hd_value));
        value->v = i;
        hd_insert(dict, name, value);
    }

    puts("Inserted values");

    HD_WRITEJSON(dict, stdout, tostring);

    putc('\n', stdout);

    for (int i = 0; i < max_v; i++) { // finding
        char* name = malloc(malloc_size);
        sprintf(name, "%d", i);
        hd_value *value = hd_find(dict, name);
        if (value == NULL) {
            printf("Key with name %d not found\n", i);
        } else if (value->v != i) {
            printf("Key with name %d has wrong value %d\n", i, value->v);
        }
    }

    puts("Found values");

    for (int i = 0; i < max_v; i+=2) { // removing
        char* name = malloc(malloc_size);
        sprintf(name, "%d", i);
        hd_remove(dict, name);
    }

    puts("Removed values");

    for (int i = 0; i < max_v; i+=2) { // checking if removed
        char* name = malloc(malloc_size);
        sprintf(name, "%d", i);
        hd_value *value = hd_find(dict, name);
        if (value != NULL) {
            printf("Key with name %d not removed\n", i);
        }
    }

    puts("Check if removed");

    HD_WRITEJSON(dict, stdout, tostring);

    putc('\n', stdout);

    hd_delete(dict);

    return 0;
}