picotm-lib-shared-treemap.h File Reference

Contains struct picotm_shared_treemap and helper functions. More...

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

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

Typedefs
typedef uintptr_t(*	picotm_shared_treemap_value_create_function) (unsigned long long key, struct picotm_shared_treemap *treemap, struct picotm_error *error)
typedef void(*	picotm_shared_treemap_value_destroy_function) (uintptr_t value, struct picotm_shared_treemap *treemap)

Functions
PICOTM_NOTHROW void	picotm_shared_treemap_init (struct picotm_shared_treemap *self, unsigned long key_nbits, unsigned long level_nbits)
PICOTM_NOTHROW void	picotm_shared_treemap_uninit (struct picotm_shared_treemap *self, picotm_shared_treemap_value_destroy_function value_destroy)
PICOTM_NOTHROW uintptr_t	picotm_shared_treemap_find_value (struct picotm_shared_treemap *self, unsigned long long key, picotm_shared_treemap_value_create_function value_create, picotm_shared_treemap_value_destroy_function value_destroy, struct picotm_error *error)

Detailed Description

The data stucture struct picotm_shared_treemap maps keys to values. Concurrent look-up by multiple transactions is 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 shared treemap with a call to picotm_shared_treemap_init().

struct picotm_shared_treemap_init treemap;
picotm_shared_treemap_init(&treemap, 52, 13);

The second parameter is the maximum number of bits in a key. The initializer function sets up the shared treemap instance to support keys up to this length. Using larger keys is undefined. The third argument is the number of key bits handled per level of the internal tree hierarchy. Ideally this number is a remainder-free divider of the key length.

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

The following example returns the value for the key 0x1234 from the shared 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_shared_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;
}

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

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

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

picotm_shared_treemap_uninit(&treemap, destroy_value);

Typedef Documentation

picotm_shared_treemap_value_create_function

typedef uintptr_t(* picotm_shared_treemap_value_create_function) (unsigned long long key, struct picotm_shared_treemap *treemap, struct picotm_error *error)

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

Parameters

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

Returns

A pointer to the created value.

picotm_shared_treemap_value_destroy_function

typedef void(* picotm_shared_treemap_value_destroy_function) (uintptr_t value, struct picotm_shared_treemap *treemap)

Invoked by picotm's shared treemap to destroy a value.

Parameters

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

Function Documentation

picotm_shared_treemap_find_value()

PICOTM_NOTHROW uintptr_t picotm_shared_treemap_find_value	(	struct picotm_shared_treemap *	self,
		unsigned long long	key,
		picotm_shared_treemap_value_create_function	value_create,
		picotm_shared_treemap_value_destroy_function	value_destroy,
		struct picotm_error *	error
	)

Retrieves the value for a key from a shared treemap.

Parameters

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

Returns

The key's element.

picotm_shared_treemap_init()

PICOTM_NOTHROW void picotm_shared_treemap_init	(	struct picotm_shared_treemap *	self,
		unsigned long	key_nbits,
		unsigned long	level_nbits
	)

Initializes a shared treemap.

Parameters

self	The shared treemap to initialize.
key_nbits	The maximum number of bits per key.
level_nbits	The number of bits per directory level.

picotm_shared_treemap_uninit()

PICOTM_NOTHROW void picotm_shared_treemap_uninit	(	struct picotm_shared_treemap *	self,
		picotm_shared_treemap_value_destroy_function	value_destroy
	)

Uninitializes a shared treemap.

Parameters

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