The code implements a hash-based key-value map in C99 with a
hopefully user friendly API, which can easily integrated
into other code. It allows to store all kinds of objects,
from simple integers to pointers to structures etc.

A new map is created by defining and initializing a map object
For the initialization use the macro KV_MAP_INIT. E.g. for
creating and initializing a map that stores values of type
double use

    kv_map_t map = KV_MAP_INIT(double, true, NULL, NULL);

Instead of creating a variable of type kv_map_t in most cases you
can instead just create a pointer to a map instead and initialize
it like this

    kv_map_t * map = & KV_MAP_INIT(FILE *, true, NULL NULL);

This has the advantage that you don't have to use a '&' in all
function calls that require a map pointer. Just keep in mind that
the map will vanish when the memory obtained via the macro goes
out of scope (i.e. you can't use this value anymore even if you
have stored it somewhere else). The only situation where this
isn't possible is for local, static variables, they always must
be of type kv_map_t. In case of map pointers with global scope
the initialization must be done at the point of its definition.

The first argument of the macro is the type of what's to be stored
in the map.

The secoond argument is either 'true' or 'false'. If it is set to
'true' a new key-value pair will be created automatically when you
try to access one with a key not already in he map. While this is
often convenient this "auto-create" featire sometimes is not
desirable. So you can disable it by using 'false' for the second
argument.

If the third argument isn't NULL it must be is a pointer to a
function returning int and accepting a pointer to a const char
pointer and a pointer to the type of the map values. This function
is invoked each time a new node is created with the key of the
key-value pair and a pointer to its value. The function can be
used to initialize the value. If this function returns anything
but 0 creating the new node will be aborted. If the third argument
is NULL the memory for the value will just be zero-ed out.

Finally, when not NULL, the fourth argument must be a pointer to a
function returning void and accepting the same arguments as the
function for the third argumnt requires. It gets called after a
key-value pair is removed from the map and just before it is
deleted. It can be used to do clean-up before the key-value
pair vanishes.


With this you have a map you can start working with. As in the
process of adding key-value pairs memory gets allocated to avoid
memory leaks the map must be cleaned out when you're done with it.
For this there's the

    void map_clear(kv_map_t * map);

function, which frees all memory allocated for the map. This
does not destroy the map, you can re-use it.


If you have enabled the "auto-create" feature you can simple create
a new key-valuepair ("node" for short in the following) with

    void * kv_map_get(kv_map_t * map, const char * key);

On success it returns a pointer to the value, otherwise NULL.
So you could use it to set the value like this

    double * v = kv_map_get(&map, "Euler's number");
    if (v)
        *v = 2.7182818284590451;

to create and initialize a "node" accessible via the key "Euler's
number".

If you decided to disable the "auto-create" feature kv_map_get()
would habe returned NULL as no node with that key does exist yet.
Instead you'll have to use

    void * kv_map_add(kv_map_t * map, const char * key);

to create a new node. It also returns a pointer to the value on
success (and NULL on error). In case a node with that key already
exists the function returns a pointer to the value of that node
instead of creating a new one.

kv_map_add() can be used as well when the "auto-create" feature
is enabled, it's call is then equivalent to one of kv_map_get().


To test if a node with a certain key already exists use

    bool kv_map_exists(kv_map_t * map, const char * key);

As to be expected it returns 'true' if a node with the supplied
key exists, otherwise 'false'.


You can as well remove nodes from the map with

   void kv_map_remove(kv_map_t * map, const char * key);

When it returns the node with the given key is gone for good.


To iterate over all the nodes in a map you can use an iterator. Define
and initialize it with

    kv_map_iter_t iter = KV_MAP_ITER_INIT(&map);

The only argument the initialization macro takes is a pointer to
the  map the iterator is meant to iterate over.

As in the case of the map variable in most situations you can
instead define a pointer to the iterator and define it like this

    kv_map_iter_t * iter = & KV_MAP_ITER_INIT(map);

Once you have defined the iterator you can use it to access all
nodes in the map consecutively, using the functions

    const char * kv_map_next_key(kv_map_iter_t * iter);
    void * kv_map_next_value(kv_map_iter_t * iter);
    bool kv_map_next(kv_map_iter_t  * iter, const char ** key, void ** value);

The first one returns the key of the current node on each iteration
step with the iterator getting "incremented" in the process. The
second function instead returns a pointer to the value of the
current node. The third can be used to obtain both the key and
the pointer to the value.

The first two function return NULL after the last node. The third
normally returns 'true' and 'false' only when you have reached the
end of the map.

Once the iterator has reached the end of the map it automatically
is reset to the start of it, so it can be re-used immediately for
another iteration over the map. But you can as well re-initialize
it using the 'KV_MAP_ITER_INIT()' macro.

When iterating over the nodes in the map don't expect any particular
order the nodes are returned in. They are more or less randomly dis-
tributed over the map, and the order may change whenever you add or
remove a node.


A final function returns the number of key-value pairs currently
stored in a map

    size_t kv_map_count(const kv_map_t * map);


Here's a short example program, demonstrating the functionality.
Note the exampledefines a pointer to the map (and to the iterator)
instead of a map variable.

----8<---------------------------------------------------------
#include <stdio.h>
#include "kv_map.h"

typedef struct {
    const char * name;
    double       val;
    const char * desc;
} math_const_t;

static int set_default(const char   * key, math_const_t * v)
{
    *v = (math_const_t) {key, 0.0, "not available"};
    return 0;
}

int main(void)
{
    // Create a map for structures of typemath_const_t
    kv_map_t * map = & KV_MAP_INIT(math_const_t, false, set_default, NULL);

    // Add a few nodes
    math_const_t * v = kv_map_add(map, "pi");
    v->val  = 3.1415926535897931;
    v->desc = "ratio of circle's circumfence to diameter";

    v = kv_map_add(map, "e");
    v->val  = 2.7182818284590451;
    v->desc = "Euler's number";

    v = kv_map_add(map, "pht");
    v->val  = 1.6180339887498945;
    v->desc = "Golden ratio";

    kv_map_add(map, "dummy");

    // Get a node and print its description string
    printf("%s\n", ((math_const_t *) kv_map_get(map, "dummy"))->desc);

    /* Create an iterator for the map */
    kv_map_iter_t * iter = & KV_MAP_ITER_INIT(map);

    // Iterate over the map, printing content of allstructures
    while ((v = kv_map_next_value(iter)))
        printf("'%s' %lf '%s'\n", v->name, v->val, v->desc);

    // Remove a node
    kv_map_remove(map, "dummy");

    // Iterate again over the map, using the same iterator
    const char * k;
    while ((k = kv_map_next_key(iter)))
        printf("%s\n", k);

    // Free all memory that was allocated for the map
    kv_map_clear(map);
}
----8<---------------------------------------------------------

That's already everything there is to know about the API. See
the 'examples' directory for a few more example programs.


If you want to dig a bit deeper there are a few more functions that
allow to monitor the behaviour of  a map. The map is simply a hash
table, and uring run-time the number of buckets used for the map
grows and shrinks as nodes are added and removed. The number of
buckets will be doubled when a certain load factor (the ration of
nodes to buckets) is excceded. You can adjust it by changing the
LOAD_FACOR_INCR macro in kv_map.c. The number of buckets will be
halved when the load factor drops below another level, see macro
LOAD_FACOR_DECR.

You can obtain information about the number of buckets and the
current total heap memory usage (in bytes) using the functions

    size_t kv_map_bucket_count(const kv_map_t * map);
    size_t kv_map_mem_size(const kv_map_t * map);

June 29, 2020         Jens Thoms Toerring <jt@toerring.de>