Simple key-value store in C

Question

I needed a simple key-value store. Here's what I came up with.

Usage

Use kvs_create and kvs_destroy to create stores and clean them up later:

KVSstore *store = kvs_create();
...
kvs_destroy(store);

Of course you can also create a store on the stack:

KVSstore s = {0};
KVSstore *store = &s;

Add values to the store or update existing values with kvs_put:

const char *nameKey = "name";
const char *jobKey = "job";
kvs_put(store, nameKey, "Bob"); // store->length is now 1
kvs_put(store, jobKey, "Janitor"); // store->length is now 2

Get values from the store with kvs_get:

const char *name = kvs_get(store, nameKey); // "Bob"
const char *job = kvs_get(store, jobKey); // "Janitor"

If the key isn't found, kvs_get returns NULL. Setting a value to NULL with kvs_put will remove the key-value pair from the store if the key was found.

kvs_put(store, jobKey, NULL); // store->length is now 1

These examples use strings, but keys and values are really opaque data pointers (void *). Care should be taken with string keys, since two otherwise identical strings existing at different memory locations are two different keys.

Questions

I'd like to make the length and pairs fields in KVSstore read-only with const (because any attempt to alter these would amount to user error under the use cases I have in mind for this), but I need some way to make them mutable internally. Casting back and forth between KVSstore and something like KVSmutablestore gets old really fast, and makes the code more difficult to follow. I'm trying to figure out a cleaner way to handle that.

Other than that, I'm just looking for a general review.

Code

kvs.h

#ifndef __KVS_H__
#define __KVS_H__
#ifdef __cplusplus
extern "C" {
#endif
#include <stdlib.h>
typedef struct {
 const void *key;
 void *value;
} KVSpair;
typedef struct {
 KVSpair *pairs;
 size_t length;
} KVSstore;
KVSstore *kvs_create(void);
void kvs_destroy(KVSstore *store);
void kvs_put(KVSstore *store, const void *key, void *value);
void *kvs_get(KVSstore *store, const void *key);
#ifdef __cplusplus
}
#endif
#endif /* #define __KVS_H__ */

kvs.c

#include "kvs.h"
static const size_t kvs_pair_size = sizeof(KVSpair);
static const size_t kvs_store_size = sizeof(KVSstore);
static int kvs_sort_compare(const void *a, const void *b) {
 const KVSpair *pairA = a;
 const KVSpair *pairB = b;
 if (pairA->key > pairB->key) {
 return -1;
 }
 if (pairA->key < pairB->key) {
 return 1;
 }
 return 0;
}
static int kvs_search_compare(const void *key, const void *element) {
 const KVSpair *pair = element;
 if (key > pair->key) {
 return -1;
 }
 if (key < pair->key) {
 return 1;
 }
 return 0;
}
static KVSpair *kvs_get_pair(KVSstore *store, const void *key) {
 if ((!store) || (!store->pairs)) {
 return NULL;
 }
 return bsearch(key, store->pairs, store->length, kvs_pair_size,
 kvs_search_compare);
}
static void kvs_sort_pairs(KVSstore *store) {
 if ((!store) || (!store->pairs)) {
 return;
 }
 qsort(store->pairs, store->length, kvs_pair_size, kvs_sort_compare);
}
static void kvs_resize_pairs(KVSstore *store) {
 if (!store) {
 return;
 }
 store->pairs = realloc(store->pairs, kvs_pair_size * store->length);
}
static void kvs_create_pair(KVSstore *store, const void *key, void *value) {
 KVSpair *pair;
 if (!store) {
 return;
 }
 ++store->length;
 kvs_resize_pairs(store);
 pair = &store->pairs[store->length - 1];
 pair->key = key;
 pair->value = value;
 kvs_sort_pairs(store);
}
static void kvs_remove_pair(KVSstore *store, KVSpair *pair) {
 if ((!store) || (!pair)) {
 return;
 }
 pair->key = NULL;
 kvs_sort_pairs(store);
 --store->length;
 kvs_resize_pairs(store);
}
KVSstore *kvs_create(void) {
 KVSstore *store = malloc(kvs_store_size);
 store->pairs = NULL;
 store->length = 0;
 return store;
}
void kvs_destroy(KVSstore *store) {
 if (!store) {
 return;
 }
 if (store->pairs) {
 free(store->pairs);
 }
 free(store);
}
void kvs_put(KVSstore *store, const void *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);
 }
}
void *kvs_get(KVSstore *store, const void *key) {
 KVSpair *pair = kvs_get_pair(store, key);
 return pair ? pair->value : NULL;
}

• Mat: "I'd like to make the length and pairs fields in KVSstore read-only with const" - why do you want to do that?
• Dagg: @Mat the user should never be messing with length or pairs in the use cases I have in mind, so it seemed like the thing to do. Maybe it's overkill, though.
• Mat: Then make it an opaque struct. (I don't really buy the on-stack use-case, you're going to be doing a dynamic allocation anyway.)
• buddy: Synchronisation protection you can add to make it thread safe.

Answer 1

Answer to the question

You may want to hide the KVSstore structure: just forward declare it in the header or use another opaque structure with just a void* pointing to a real internal representation. Then provide a method size_t kvs_length(KVSstore*), so users could know how many elements are stored.

However, you'll lose the feature of statically allocating KVSstore, and I can't think of any good solution to this. Both features (forbidding the user to change length and pairs and letting the user set initial values for length and pairs) are somewhat against each other.

Anyway, kvs_destroy doesn't work with statically allocated stores (see comments below).

Code review

General comments

The code style is good and consistent. You also paid attention to const correctness and some other details, like protecting the header to be included from C++ code and marking private function as static.

Interface

The interface is quite simple, but well defined and sufficient. I have just some comments:

The KVSpair could be a forward declaration.

You have commented that keys are just pointers and using strings as keys might not work as expected (and I believe in most practical applications, it wouldn't work indeed).

It is relatively easy to solve this. 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. The user could then just assign strcmp to that pointer.

Also, I couldn't know how to properly use your data structure by looking solely at the header file, specially to know about the removal operation. Add some comments, everyone that uses your code, including yourself, will thank you for that one day.

Implementation

Cast from void*

const KVSpair *pairA = a;
const KVSpair *pairB = b;
const KVSpair *pair = element;
store->pairs = realloc(store->pairs, kvs_pair_size * store->length);
KVSstore *store = malloc(kvs_store_size);

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

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

On my first reading, I didn't notice the cast and I though you had declared a useless redundant variable.

Memory allocation and reallocation

static void kvs_resize_pairs(KVSstore *store) {
 ...
 store->pairs = realloc(store->pairs, kvs_pair_size * store->length);

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.

Resizing the array of pairs is not just reallocating memory, but also controlling the value of store->length. Thinking this way, I would pass the new desired length as parameter to kvs_resize_pairs instead of setting it prior to calling the function.

Element removal

static void kvs_remove_pair(KVSstore *store, KVSpair *pair)

Your algorithm to remove an item from the array is not very good. Once you find the pair inside the array, you just have to move all following pairs to one position before, you don't need to set the key to NULL and sort it again. Substituting the kvs_sort_pairs(store); by the following should work (not tested):

memmove(pair, pair + 1, store->length - (pair - store->pairs) - 1);

Then just resize the array, as you are already doing.

Initialization and destruction

KVSstore *kvs_create(void)
void kvs_destroy(KVSstore *store)

The kvs_create dynamically allocates a KVSstore and initializes it. The kvs_destroy destroys and releases it. kvs_create shouldn't be needed when using allocation on stack, but how the user is supposed to destroy it, once kvs_destroy tries to free the pointer?

• Dagg: Thanks, I like the comparison function pointer idea and element removal suggestion. If you statically allocated it, you'd need to free kvs->pairs when you were done with it. Now that I think about it the static use case is probably no good. Hiding the KVSstore and adding functions to get the length and iterate over all the pairs is probably the way to go.
• Dagg: I followed almost all of your suggestions and posted a followup here. The only thing I wasn't sure about was the explicit cast.

Answer 2

Interface

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.

Implementation

It seems that you call realloc way too often. Let your store have some extra capacity.

Complexity

A n log(n) insertion complexity doesn't look right. I am not even sure it is n log(n), because the store is maintained sorted, and after an addition of an element it becomes a dreadful "almost sorted". It is very well possible that you are constantly hitting a worst case of qsort, and your insertion becomes quadratic.

My recommendation is to follow Andre Sassi suggestion for insertion as well: find an insertion point and memmove the rest by one slot. Of course that rules out bsearch, and you'd have to implement something akin to lower_bound of STL. This would guarantee a linear insertion time.

Depending on the use case it may be worth to go extra mile and implement a store as a tree.

• Dagg: The insertion suggestion is very useful, thank you. I posted a followup here.