10
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • \$\begingroup\$ double underscore starts a reserved identifier for the implementation, I would recommend not using it. \$\endgroup\$
    – Rapptz
    Sep 22, 2014 at 4:42

4 Answers 4

10
\$\begingroup\$

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.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ All of my other null checks are done the way you suggest, but for some reason foo == NULL seemed more appropriate there. I guess I should use the same style everywhere though. \$\endgroup\$
    – Dagg
    Sep 21, 2014 at 18:45
  • 1
    \$\begingroup\$ Actually in production level code you often see if (NULL == pointer) to protect against accidental typos of = instead of ==. These days most compilers will spit out a warning for that but it's a habit you might want to consider getting into \$\endgroup\$
    – ChrisWue
    Sep 21, 2014 at 19:49
  • \$\begingroup\$ Setting the struct member to null post-release doesn't really accomplish much unless the pointer to the struct is also nulled. The dereference of the struct pointer would give you a segfault before the member could ever be touched. (Or were you saying he should change the function signature to take a double pointer and that he should free the pointer to struct?) \$\endgroup\$
    – Corbin
    Sep 21, 2014 at 23:10
  • \$\begingroup\$ @Corbin that's what I was thinking... wouldn't it be the caller's responsibility to set store = NULL after calling kvs_destroy(store)? Setting the local variable to NULL inside of kvs_destroy doesn't affect the copy of the pointer that was passed in. Using a double pointer just to be able to NULL it seems like overkill. \$\endgroup\$
    – Dagg
    Sep 21, 2014 at 23:39
  • \$\begingroup\$ @Corbin Yes, that is what I meant. I will re-word my answer to reflect that. \$\endgroup\$
    – syb0rg
    Sep 22, 2014 at 16:15
5
\$\begingroup\$
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);
}
\$\endgroup\$
3
  • \$\begingroup\$ But then I can't simply pass in strcmp, unless I cast compare to that function signature (which does seem to work under gcc but I imagine it's just asking for trouble). \$\endgroup\$
    – Dagg
    Sep 21, 2014 at 22:55
  • \$\begingroup\$ @Dagg: That is true. But if one desires that a user not have to write their own wrapper, that drawback can be mitigated in a number of ways: e.g. provide KVSstrcmp that forwards to strcmp, or provide two constructors one for each signature. \$\endgroup\$
    – user14393
    Sep 22, 2014 at 0:05
  • \$\begingroup\$ Incidentally, this sort of dilemma (do I provide robust functionality, or do I provide one that is simpler and easier to implement) is one of the reasons I strongly dislike C as compared to C++. \$\endgroup\$
    – user14393
    Sep 22, 2014 at 0:09
0
\$\begingroup\$

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.

\$\endgroup\$
-1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.