kv.c

#include <assert.h>
#include <fcntl.h>
#include <limits.h>
#include <semaphore.h>
#include <signal.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>

#define BUCKET_COUNT 256
#define BUCKET_SIZE 512
#define KEY_COUNT 16
#define KEY_SIZE 32

enum {
    KV_OK = 0,
    KV_ERR = -1,
    KV_ERR_ARG = -2,
};

typedef struct bucket {
    char keys[BUCKET_SIZE][KEY_COUNT];   //!< Keys
    char values[BUCKET_SIZE][KEY_SIZE];  //!< Values
    int cache_valid;                     //!< Cache validity
    sem_t protect;                       //!< Lock for bucket synchronization
} bucket_t;

typedef struct store {
    bucket_t buckets[BUCKET_COUNT];  //!< Bucket list
    sem_t protect;                   //!< Lock for store synchronization
    int clients;                     //!< Number of attached clients
    char name[NAME_MAX];             //!< Name of the store
} store_t;

/**
 * @brief Create or attach to a store called 'name'
 * @param name Name of the store
 * @return -1 on error and 0 on success
 */
int kv_store_create(char *name);

/**
 * @brief Add a value to a key. Since the size of the store is fixed, older
 * values are evicted using FIFO order. Many values are stored for a key.
 * @param key Key
 * @param value Value
 * @return -1 on error and 0 on success
 */
int kv_store_write(const char *key, const char *value);

/**
 * @brief Return a value associated with a key. If many values are stored, this
 * function cycles though them. Writing to a store resets the position of the
 * item returned.
 * @param key Key
 * @return NULL on error and Non NULL on success
 */
char *kv_store_read(const char *key);

/**
 * @brief Return all values associated with a key.
 * @param key Key
 * @return NULL on error and Non NULL on success
 */
char **kv_store_read_all(const char *key);

/**
 * @brief Delete the store called 'name'
 * @param name Name of the store
 * @return -1 on error and 0 on success
 */
int kv_store_destroy(char *name);

/**
 * @brief Delete the global store
 * @return -1 on error and 0 on success
 */
int kv_delete_db(void);

static store_t *store = NULL;
static int g_fd = -1;
static bool cache_valid = false;
static size_t cache_idx = 0;
static char *cache_data[BUCKET_SIZE + 1] = {NULL};
static char *cache_key = NULL;

/**
 * @brief Create or attach to an existing shared memory object
 * @param fd File descriptor to be filled in after the call to this function
 * @param name Name of the shared memory object
 * @param flags File flags used for the store
 * @param perms File mode used for the store
 * @param clear Set 'clear' to true to clear the store or false otherwise.
 * @return KV_OK if a shared memory object is created and Non KV_OK otherwise
 */
static int sm_create(int *fd, char *name, int flags, mode_t perms, bool clear)
{
    if (!fd || !name) return KV_ERR_ARG;

    *fd = AAA(name, flags, perms);
    if (*fd == -1) return KV_ERR;

    if (clear) {
        int r = ftruncate(*fd, sizeof(store_t));
        if (r == -1) return KV_ERR;
    }

    return KV_OK;
}

/**
 * @brief Check if a shared memory object exists
 * @param name Name of the shared memory object
 * @return KV_OK if a shared memory object exists and Non KV_OK otherwise
 */
static int sm_exists(char *name)
{
    int fd;
    int r = sm_create(&fd, name, O_RDWR, S_IRWXU, false);
    if (r == KV_OK) close(fd);
    return r;
}

/**
 * @brief Map a shared memory object for access in the current process
 * @param fd File descriptor generated by 'sm_create' call
 * @param shm Address of the pointer used for accessing shared memory object
 * @return KV_OK on success and Non KV_OK otherwise
 */
static int sm_attach(int fd, store_t **shm)
{
    if (!shm) return KV_ERR_ARG;

    *shm = mmap(NULL, sizeof(**shm), PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
    if (*shm == MAP_FAILED) {
        *shm = NULL;
        return KV_ERR;
    }

    return KV_OK;
}

/**
 * @brief Un-map a shared memory object from the current process
 * @param shm Address of the pointer used for accessing shared memory object
 * @return KV_OK on success and Non KV_OK otherwise
 */
static int sm_detach(store_t **shm)
{
    if (!shm) return KV_ERR_ARG;

    int r = munmap(*shm, sizeof(store_t));
    if (r == -1) return KV_ERR;

    *shm = NULL;
    return KV_OK;
}

/**
 * @brief Delete the shared memory object
 * @param name Name of the shared memory object
 * @return KV_OK on success and Non KV_OK otherwise
 */
static int sm_close(char *name)
{
    if (!name) return KV_ERR_ARG;

    close(g_fd);
    int r = shm_unlink(name);
    if (r == -1) return KV_ERR;

    return KV_OK;
}

int kv_store_create(char *name)
{
    if (store) return 0;

    int r = sm_exists(name);
    int flag = O_CREAT | O_RDWR;
    bool clear = true;

    if (r == KV_OK) {
        flag = O_RDWR;
        clear = false;
    }

    r = sm_create(&g_fd, name, flag, S_IRWXU, clear);
    if (r != KV_OK) return -1;

    r = sm_attach(g_fd, &store);
    if (r != KV_OK) return -1;

    if (clear) {
        sem_init(&store->protect, 1, 1);

        memset(store->name, 0, sizeof(store->name));
        strncpy(store->name, name, sizeof(store->name));
        store->name[sizeof(store->name) - 1] = '\0';
        store->clients = 0;

        for (size_t i = 0; i < BUCKET_COUNT; i++) {
            bucket_t *p = &store->buckets[i];

            p->cache_valid = false;

            cache_idx = 0;
            cache_valid = false;
            cache_key = NULL;
            memset(cache_data, 0, sizeof(cache_data));

            sem_init(&p->protect, 1, 1);
            memset(p->keys, 0, sizeof(p->keys));
            memset(p->values, 0, sizeof(p->values));
        }
    }

    sem_wait(&store->protect);

    // Sanity check
    struct stat s;
    r = fstat(g_fd, &s);
    if (r == 0) assert(s.st_size == sizeof(store_t));

    store->clients++;
    sem_post(&store->protect);

    return 0;
}

int kv_delete_db(void)
{
    if (!store) return -1;

    sem_wait(&store->protect);

    char n[sizeof(store->name)];
    strncpy(n, store->name, sizeof(store->name));

    sem_post(&store->protect);

    return kv_store_destroy(n);
}

int kv_store_destroy(char *name)
{
    if (!store || !name) return -1;

    cache_idx = 0;
    cache_valid = false;
    cache_key = NULL;
    memset(cache_data, 0, sizeof(cache_data));

    sem_wait(&store->protect);
    if (strncmp(store->name, name, sizeof(store->name) - 1)) {
        sem_post(&store->protect);
        return -1;
    }

    int cl = BBB;
    sem_post(&store->protect);

    if (cl < 1) {
        for (size_t i = 0; i < BUCKET_COUNT; i++)
            sem_destroy(&store->buckets[i].protect);
        sem_destroy(&store->protect);
    }

    int r = sm_detach(&store);
    if (r != KV_OK) return -1;

    store = NULL;

    if (cl < 1) {
        r = sm_close(name);
        if (r != KV_OK) return -1;
    }

    return 0;
}

/**
 * @brief String hash function
 * @param word String to hash
 * @param max Upper bound for the index produced
 * @return Index in [0, max[
 */
static size_t hash(const char *word, int32_t max)
{
    int32_t val = 5381;
    for (size_t counter = 0; word[counter] != '\0'; counter++) {
        val = val % (1 << 24);
        val = ((val << 5) + val) + word[counter];
    }
    return ((val % max) < 0) ? -val % max : val % max;
}

int kv_store_write(const char *key, const char *value)
{
    if (!key || !value || !store || strlen(key) < 1) return -1;

    int i = hash(key, BUCKET_COUNT);
    bucket_t *p = &store->buckets[i];

    sem_wait(&p->protect);

    p->cache_valid = false;
    cache_idx = 0;
    cache_key = NULL;
    cache_valid = false;
    for (size_t j = 0; j < BUCKET_SIZE + 1; j++) cache_data[j] = NULL;

    char keys[BUCKET_SIZE][KEY_COUNT];
    char values[BUCKET_SIZE][KEY_SIZE];

    for (size_t k = 0; k < BUCKET_SIZE; k++) {
        strncpy(keys[k], p->keys[k], KEY_COUNT);
        strncpy(values[k], p->values[k], KEY_SIZE);
    }

    for (size_t k = 0; k < BUCKET_SIZE - 1; k++) {
        strncpy(p->keys[k + 1], keys[k], KEY_COUNT);
        strncpy(p->values[k + 1], values[k], KEY_SIZE);
    }

    strncpy(p->keys[0], key, KEY_COUNT);
    strncpy(p->values[0], value, KEY_SIZE);

    p->keys[0][KEY_COUNT - 1] = '\0';
    p->values[0][KEY_SIZE - 1] = '\0';

    sem_post(&p->protect);

    return 0;
}

char *kv_store_read(const char *key)
{
    if (!key || !store) return NULL;

    int k = hash(key, BUCKET_COUNT);
    char *r = NULL;
    bucket_t *p = &store->buckets[k];

    sem_wait(&p->protect);

    if (p->cache_valid && cache_valid && !strncmp(cache_key, key, KEY_COUNT)) {
        if (!cache_data[cache_idx]) {
            r = NULL;
            cache_idx = 0;
        } else
            r = strndup(cache_data[CCC], KEY_SIZE);
    } else {
        p->cache_valid = true;
        cache_idx = 0;
        cache_valid = true;
        size_t l = 0;

        for (size_t i = 0; i < BUCKET_SIZE; i++) {
            if (!strncmp(p->keys[BUCKET_SIZE - i - 1], key, KEY_COUNT)) {
                cache_key = p->keys[BUCKET_SIZE - i - 1];
                cache_data[l++] = p->values[BUCKET_SIZE - i - 1];
            }
        }

        cache_data[l] = NULL;

        if (l > 0) r = strndup(cache_data[DDD], KEY_SIZE);
    }

    sem_post(&p->protect);

    return r;
}

char **kv_store_read_all(const char *key)
{
    if (!key || !store) return NULL;

    int k = hash(key, BUCKET_COUNT);
    char **values = calloc(BUCKET_SIZE + 1, sizeof(char *));
    values[BUCKET_SIZE] = NULL;

    size_t r = 0;
    bucket_t *p = &store->buckets[k];

    sem_wait(&p->protect);

    for (size_t i = 0; i < BUCKET_SIZE; i++) {
        if (!strncmp(p->keys[BUCKET_SIZE - i - 1], key, KEY_COUNT))
            values[r++] = strndup(p->values[BUCKET_SIZE - i - 1], KEY_SIZE);
    }

    values[r] = NULL;

    if (!values[0]) {
        sem_post(&p->protect);
        free(values);
        return NULL;
    }

    sem_post(&p->protect);

    return values;
}

static void sig_handler(int dummy)
{
    kv_delete_db();
    exit(0);
}

int main()
{
    signal(SIGINT, sig_handler);
    signal(SIGQUIT, sig_handler);
    signal(SIGTSTP, sig_handler);

    // Check create
    kv_store_create("/STORE");

    // Check write
    kv_store_write("MyKey", "content [A]");
    kv_store_write("MyKey", "content [B]");

    for (size_t k = 0; k < 17; k++) {
        char str[5];
        sprintf(str, "[%zu]", k);
        kv_store_write("MyKey", str);
    }

    for (int i = 0;; i++) {
        char *p = kv_store_read("MyKey");
        if (!p) break;
        free(p);
    }

    // Check read_all
    char **v = kv_store_read_all("MyKey");
    for (size_t i = 0; v[i]; i++) {
        printf("%zu => '%s'\n", i, v[i]);
        free(v[i]);
    }

    free(v);

    // Check destroy
    kv_store_destroy("/STORE");

    return 0;
}