picotm-lib-treemap.h File Reference

Contains struct picotm_treemap and helpers. More...

#include <stdint.h>
#include "compiler.h"

Include dependency graph for picotm-lib-treemap.h:

Data Structures
struct	picotm_treemap
	Maps keys to values. More...

Typedefs
typedef uintptr_t(*	picotm_treemap_value_create_function) (unsigned long long key, struct picotm_treemap *treemap, struct picotm_error *error)
typedef void(*	picotm_treemap_value_destroy_function) (uintptr_t value, struct picotm_treemap *treemap)
typedef void(*	picotm_treemap_value_call_function) (uintptr_t value, unsigned long long key, struct picotm_treemap *treemap, void *data, struct picotm_error *error)

Functions
PICOTM_NOTHROW void	picotm_treemap_init (struct picotm_treemap *self, unsigned long level_nbits)
PICOTM_NOTHROW void	picotm_treemap_uninit (struct picotm_treemap *self, picotm_treemap_value_destroy_function value_destroy)
PICOTM_NOTHROW uintptr_t	picotm_treemap_find_value (struct picotm_treemap *self, unsigned long long key, picotm_treemap_value_create_function value_create, struct picotm_error *error)
PICOTM_NOTHROW void	picotm_treemap_for_each_value (struct picotm_treemap *self, void *data, picotm_treemap_value_call_function value_call, struct picotm_error *error)

Detailed Description

The data stucture struct picotm_treemap maps keys to values on single threads. Concurrent look-up by multiple transactions is not supported. Keys can be up to 64 bit in length, values are of type uintptr_t, so unsigned integers or pointers can be stored.

Initialize a treemap with a call to picotm_treemap_init().

struct picotm_treemap_init treemap;
picotm_treemap_init(&treemap, 13);

The second argument is the number of key bits handled per level of the tree hierarchy. Ideally this number is a remainder-free divider of the maximum key length. The maximum key length itself does not have ot be specified. The treemap's implementation will grow the internal tree to adapt to any key.

Call picotm_treemap_find_value() to retrieve a key's value from the treemap. If the key/value pair is not in the treemap, a creator function can generate a new value as part of the lookup. If you don't supply a creator function, 0 is returned for non-existing values.

The following example returns the value for the key 0x1234 from the treemap, or inserts a new value if the key/value pair is not present.

// creator function
uintptr_t
create_value(unsigned long long key,
             struct picotm_treemap* treemap,
             struct picotm_error* error)
{
    int* value = malloc(sizeof(*value));
    if (!value) {
        picotm_set_error_code(error, PICOTM_OUT_OF_MEMORY);
        return 0;
    }
    *value = 0;
    return (uintptr_t)value;
}

struct picotm_error error;
int* value = (int*)picotm_treemap_find_value(treemap, 0x1234,
                                             create_value,
                                             &error);
if (picotm_error_is_set()) {
    // perform error recovery
}

You can iterate over all key/value pairs stored in the treemap with picotm_treemap_for_each_value(). It invokes a call-back function for each value. Values will be sorted by their keys' order. The following example prints all key/value pairs to the terminal.

call_value(uintptr_t value, unsigned long long key,
           struct picotm_treemap* treemap, void* data,
           struct picotm_error* error)
{
    printf("key %ull is %zu\n", key, value);
}

picotm_treemap_for_each_value(&treemap, data, call_value, &error);
if (picotm_error_is_set()) {
    // perform error recovery
}

To uninitialize a treemap, call picotm_treemap_uninit(). This function requires a destroy function for the values. It walk over all keys in the treemap and invokes the destroy function on each key's value.

// destroy function
void
destroy_value(uintptr_t value, struct picotm_treemap* treemap)
{
    free((int*)value);
}

picotm_treemap_uninit(&treemap, destroy_value);

Typedef Documentation

picotm_treemap_value_call_function

typedef void(* picotm_treemap_value_call_function) (uintptr_t value, unsigned long long key, struct picotm_treemap *treemap, void *data, struct picotm_error *error)

Invoked by picotm's treemap to call a value.

Parameters

	value	The value.
	key	The value's key.
	treemap	The value's treemap.
	data	User data.
[out]	error	Returns an error from the creator function.

picotm_treemap_value_create_function

typedef uintptr_t(* picotm_treemap_value_create_function) (unsigned long long key, struct picotm_treemap *treemap, struct picotm_error *error)

Invoked by picotm's treemap to create a new value.

Parameters

	key	The value's key.
	treemap	The value's treemap.
[out]	error	Returns an error from the creator function.

Returns

A pointer to the created value.

picotm_treemap_value_destroy_function

typedef void(* picotm_treemap_value_destroy_function) (uintptr_t value, struct picotm_treemap *treemap)

Invoked by picotm's treemap to destroy a value.

Parameters

value	The value to destroy.
treemap	The value's treemap.

Function Documentation

picotm_treemap_find_value()

PICOTM_NOTHROW uintptr_t picotm_treemap_find_value	(	struct picotm_treemap *	self,
		unsigned long long	key,
		picotm_treemap_value_create_function	value_create,
		struct picotm_error *	error
	)

Retrieves the value for a key from a treemap.

Parameters

	self	The treemap.
	key	The value's key.
	value_create	The creator function for values.
[out]	error	Returns an error from the look-up function.

Returns

The key's element.

picotm_treemap_for_each_value()

PICOTM_NOTHROW void picotm_treemap_for_each_value	(	struct picotm_treemap *	self,
		void *	data,
		picotm_treemap_value_call_function	value_call,
		struct picotm_error *	error
	)

Iterates over all values stored in a treemap.

Parameters

	self	The treemap.
	data	User data.
	value_call	The call-back function for values.
[out]	error	Returns an error from the look-up function.

picotm_treemap_init()

PICOTM_NOTHROW void picotm_treemap_init	(	struct picotm_treemap *	self,
		unsigned long	level_nbits
	)

Initializes a treemap.

Parameters

self	The treemap to initialize.
level_nbits	The number of bits per directory level.

picotm_treemap_uninit()

PICOTM_NOTHROW void picotm_treemap_uninit	(	struct picotm_treemap *	self,
		picotm_treemap_value_destroy_function	value_destroy
	)

Uninitializes a treemap.

Parameters

self	The treemap to initialize.
value_destroy	The destroy function for values.