Simple key-value store in C, take 2

Question

Followup to Simple key-value store in C.

Response to previous reviews

---

You may want to hide the KVSstore structure

Done.

Add a comparison function pointer to KVSstore. If this pointer is null, kvs_sort_compare just compare key pointers, otherwise, it passes the keys to the comparison function.

Done, now kvs_create takes a pointer to a compare function matching the signature of strcmp (or NULL to compare pointers).

Add some comments

Done.

Make it explicit that you are casting the pointer from void* to another type, like:

const KVSpair *pairA = (const KVSpair*) a;

Not done. Is this really necessary? It feels redundant to me.

It is good practice to check for any memory allocation failure and maybe return here a boolean (0 or 1) indicating if the function have succeeded. Then change the callers of kvs_resize_pairs to check the return.

Done, sort of. In the interest of keeping it from getting too bloated, it just bails out if it runs out of memory.

I would pass the new desired length as parameter to kvs_resize_pairs instead of setting it prior to calling the function.

Good idea, I'm passing in an amount to adjust the current length by.

Your algorithm to remove an item from the array is not very good.

Fixed (I think).

---

I have an uneasy feeling about having to call kvs_put in order to remove the element. I'd recommend to provide a separate element removal function. Among other benefits it'd also simplify kvs_put itself.

Added a kvs_remove alias for that, but kept the functionality of kvs_put. Since kvs_get returns null anyway if it doesn't find a key, removing the pair when trying to store a null value seems like the most sensible thing to do.

find an insertion point and memmove the rest by one slot

Done.

---

Usage

The usage is pretty much the same as before, except now kvs_create takes a key comparison function and kvs_length and kvs_pair have been added for iterating over pairs:

KVSstore *store = kvs_create(strcmp);
KVSpair *p;
int i = 0;

kvs_put(store, "abc", "123");
kvs_put(store, "ghi", "789");
kvs_put(store, "def", "456");

while ((p = kvs_pair(store, i++))) {
    printf("%s: %s\n", (char *)p->key, (char *)p->value);
}

Questions

I have no specific questions at this point. I'm mostly looking to make sure I didn't do anything dumb since the last review.

Code

kvs.h

#ifndef __KVS_H__
#define __KVS_H__

#ifdef __cplusplus
extern "C" {
#endif

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

#define KVS_SPACE_INCREMENT 8

typedef int KVScompare(const char *a, const char *b);

typedef const void KVSkey;

typedef void KVSvalue;

typedef struct {
    KVSkey *key;
    KVSvalue *value;
} KVSpair;

typedef struct KVSstore KVSstore;

/** Create a new key-value store.

    @param compare
        A function to compare keys. If the store will only contain string keys,
        use strcmp, or use NULL for the default behavior of comparing memory
        addresses, or use a custom function matching the signature of strcmp.

    @return
        A pointer to the store.
*/
KVSstore *kvs_create(KVScompare *compare);

/** Destroy a key-value store.

    @param store
        A pointer to the store.
*/
void kvs_destroy(KVSstore *store);

/** Store a value.

    @param store
        A pointer to the store.

    @param key
        A key used to retrieve the value later. If the key already exists, the
        new value will be stored in place of the old one, unless value is NULL
        in which case the key-value pair will be removed from the store.

    @param value
        A pointer to the data being stored, or NULL to remove an existing value. 
*/
void kvs_put(KVSstore *store, KVSkey *key, KVSvalue *value);

/** Retrieve a value.

    @param store
        A pointer to the store.

    @param key
        A key used to retrieve the value.

    @return
        A pointer to the retrieved value, or NULL if not found.
*/
KVSvalue *kvs_get(KVSstore *store, KVSkey *key);

/** Remove a value from the store.

    @param store
        A pointer to the store.

    @param key
        A key identifying the value to be removed.
*/
void kvs_remove(KVSstore *store, KVSkey *key);

/** Get the number of values in a store.

    @param store
        A pointer to the store.

    @return
        The number of values contained in the store.
*/
size_t kvs_length(KVSstore *store);

/** Get a key-value pair at a given index.

    @param store
        A pointer to the store.

    @param index
        The index of the key-value pair.

    @return
        A pointer to the key-value pair, or NULL if the index is out or range.
*/
KVSpair *kvs_pair(KVSstore *store, size_t index);

#ifdef __cplusplus
}
#endif

#endif /* #define __KVS_H__ */

kvs.c

#include "kvs.h"
#include <stdio.h>

struct KVSstore {
    KVSpair *pairs;
    KVScompare *compare;
    size_t length;
    size_t space;
};

static const size_t kvs_pair_size = sizeof(KVSpair);

static const size_t kvs_store_size = sizeof(KVSstore);

static KVSpair *kvs_search(KVSstore *store, KVSkey *key, int exact) {
    KVSpair *pairs = store->pairs;
    size_t lbound = 0;
    size_t rbound = store->length;
    while (lbound < rbound) {
        size_t index = lbound + ((rbound - lbound) >> 1);
        KVSpair *element = pairs + index;
        int result = store->compare(key, element->key);
        if (result < 0) {
            rbound = index;
        } else if (result > 0) {
            lbound = index + 1;
        } else {
            return element;
        }
    }
    return exact ? NULL : pairs + lbound;
}

static KVSpair *kvs_get_pair(KVSstore *store, KVSkey *key) {
    if ((!store) || (!store->pairs)) {
        return NULL;
    }
    return kvs_search(store, key, 1);
}

static void kvs_abort_if_null(void *pointer, const char *message) {
    if (pointer == NULL) {
        fprintf(stderr, "%s\n", message);
        exit(-1);
    }
}

static void kvs_resize_pairs(KVSstore *store, size_t amount) {
    if (!store) {
        return;
    }
    store->length += amount;
    if (store->space > store->length) {
        return;
    }
    store->space += KVS_SPACE_INCREMENT;
    store->pairs = realloc(store->pairs, kvs_pair_size * store->space);
    kvs_abort_if_null(store->pairs, "out of memory");
}

static size_t kvs_get_pair_index(KVSstore *store, KVSpair *pair) {
    if ((!store) || (!pair)) {
        return -1;
    }
    return pair - store->pairs;
}

static size_t kvs_get_bytes_from_pair(KVSstore *store, KVSpair *pair) {
    size_t pair_index;
    if ((!store) || (!pair)) {
        return 0;
    }
    pair_index = kvs_get_pair_index(store, pair);
    return (store->length - pair_index) * kvs_pair_size;
}

static void kvs_create_pair(KVSstore *store, KVSkey *key, KVSvalue *value) {
    KVSpair *pair;
    if (!store) {
        return;
    }
    pair = kvs_search(store, key, 0);
    if (pair < store->pairs + store->length) {
        size_t bytes = kvs_get_bytes_from_pair(store, pair);
        memmove(pair + 1, pair, bytes);
    }
    pair->key = key;
    pair->value = value;
    kvs_resize_pairs(store, +1);
}

static void kvs_remove_pair(KVSstore *store, KVSpair *pair) {
    if ((!store) || (!pair)) {
        return;
    }
    memmove(pair, pair + 1, kvs_get_bytes_from_pair(store, pair + 1));
    kvs_resize_pairs(store, -1);
}

static int kvs_compare_pointers(const char *a, const char *b) {
    return a - b;
}

KVSstore *kvs_create(KVScompare compare) {
    KVSstore *store = malloc(kvs_store_size);
    kvs_abort_if_null(store, "out of memory");
    store->pairs = NULL;
    store->length = 0;
    store->space = 0;
    if (compare) {
        store->compare = compare;
    } else {
        store->compare = kvs_compare_pointers;
    }
    kvs_resize_pairs(store, 0);
    return store;
}

void kvs_destroy(KVSstore *store) {
    if (!store) {
        return;
    }
    if (store->pairs) {
        free(store->pairs);
    }
    free(store);
}

void kvs_put(KVSstore *store, KVSkey *key, void *value) {
    KVSpair *pair = kvs_get_pair(store, key);
    if (pair) {
        if (value) {
            pair->value = value;
        } else {
            kvs_remove_pair(store, pair);
        }
    } else if (value) {
        kvs_create_pair(store, key, value);
    }
}

KVSvalue *kvs_get(KVSstore *store, KVSkey *key) {
    KVSpair *pair = kvs_get_pair(store, key);
    return pair ? pair->value : NULL;
}

void kvs_remove(KVSstore *store, KVSkey *key) {
    kvs_put(store, key, NULL);
}

size_t kvs_length(KVSstore *store) {
    if (!store) {
        return 0;
    }
    return store->length;
}

KVSpair *kvs_pair(KVSstore *store, size_t index) {
    if ((!store) || (index < 0) || (index >= store->length)) {
        return NULL;
    }
    return store->pairs + index;
}

Answer 1

Pretty good stuff! A few minor notes:

• I would have different return codes for different errors. I noticed that you are returning -1 and 0 a lot when you encounter an error. Reusing error codes doesn't help narrow down a problem more when you do encounter an error and try to troubleshoot. Use unique error codes, or even better an enum.

  typedef enum {NO_MEM, NULL_POINTER, ETC} KeyError;
  

• In kvs_destroy, you need to set the pointer of the struct to NULL after you free() it. This is a safety measure often used in production level code so you don't accidentally try to access the information within the pointer after you free it. To do this you may need to re-write that function so that it accepts a double pointer as a parameter.

  In the comments you were stating how you thought this was overkill, and perhaps it is. If you want the user to have more freedom though, you need to tell him what freedom he has in the documentation of your source code then.

• In place of if (pointer == NULL), you could do if (!pointer). Again, this is something I commonly see in production level code. However, some developers consider it less readable so it is up to you if you want to implement the change or not. I did notice you did this in some other places, so make sure you stay consistent with your choice.

Answer 2

typedef int KVScompare(const char *a, const char *b);
KVSstore *kvs_create(KVScompare *compare);

While this good for many purposes, consider instead

typedef int KVScompare(const void *param, const char *a, const char *b);
KVSstore *kvs_create(KVScompare *compare, const void *param);

which can allow for more general comparison functions that allow runtime configuration; e.g.

int compare_tail(const void *param, const char *a, const char *b)
{
    int skip = *(const int*) param;
    return strcmp(a + skip, b + skip);
}

Answer 3

In the header file kvs.h you have the lines:

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

But there's no reason for those to be there as opposed to the kvs.c file. Nothing in the header file depends on <stdlib.h> or <string.h> so be a good neighbor to any other code that has #include "kvs.h" by not forcing unnecessary #includes. These directives should be in the kvs.c file (there's no law that requires #include directives to be in the .h file). The reason is that when you #include something it (a) slows down the preprocessor, and (b) pollutes the namespace (C++ is better in this regard as there are multiple namespaces, but you have the extern "C" which negates that). If the caller of your code defines a symbol with the same name as something from <stdlib.h> or <string.h> there will be a conflict.

Answer 4

Pretty nice code, but.. If key, val are allocated, then free() is missing when remove and destroy.. but with this is coming a lot of questions. I like such simple nice codes pieces, let it be simple. Do not make it robust. It can be easy cloned into special cases, like key and value with fixed length, or only pointers pair as index table or IP table. But for great flexibility and easy to apply for many small cases I prefer to make both key and value as strings and built in strdup() for creation pair key or value as well free() for removal. It will never be as fast as professional one with 100000 accesses per second, but it will be lovely simply tool for small things and also for joy. Goood luck!