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

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: %sn", (char *)p->key, (char *)p->value);
}

#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__ */

#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, "%sn", 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;
}