NAME

SYNOPSIS

thmap_t *
thmap_create(uintptr_t baseptr, const thmap_ops_t *ops, unsigned flags);

void
thmap_destroy(thmap_t *hmap);

void *
thmap_get(thmap_t *hmap, const void *key, size_t len);

void *
thmap_put(thmap_t *hmap, const void *key, size_t len, void *val);

void *
thmap_del(thmap_t *hmap, const void *key, size_t len);

void *
thmap_stage_gc(thmap_t *hmap);

void
thmap_gc(thmap_t *hmap, void *ref);

void
thmap_setroot(thmap_t *thmap, uintptr_t root_offset);

uintptr_t
thmap_getroot(const thmap_t *thmap);

DESCRIPTION

• Very competitive performance, with logarithmic time complexity on average.
• Lookups are lock-free and inserts/deletes are using fine-grained locking.
• Incremental growth of the data structure (no large resizing/rehashing).
• Optional support for use with shared memory, e.g. memory-mapped file.

Delete operations (the key/data destruction) must be synchronized with the readers using some reclamation mechanism.

FUNCTIONS

thmap_create()

Construct a new trie-hash map. The optional ops parameter can used to set the custom allocate/free operations (see the description of thmap_ops_t below). In such case, the baseptr is the base (start) address of the address space mapping (it must be word-aligned). If ops is set to NULL, then malloc(3) and free(3) will be used as the default operations and baseptr should be set to zero. Currently, the supported flags are:

THMAP_NOCOPY

The keys on insert will not be copied and the given pointers to them will be expected to be valid and the values constant until the key is deleted; by default, the put operation will make a copy of the key.

THMAP_SETROOT

Indicate that the root of the map will be manually set using the thmap_setroot() routine; by default, the map is initialized and the root node is set on thmap_create().

thmap_destroy()

Destroy the map, freeing the memory it uses.

thmap_get()

Lookup the key (of a given length) and return the value associated with it. Return NULL if the key is not found (see the CAVEATS section).

thmap_put()

Insert the key with an arbitrary value. If the key is already present, return the already existing associated value without changing it. Otherwise, on a successful insert, return the given value. Just compare the result against val to test whether the insert was successful.

thmap_del()

Remove the given key. If the key was present, return the associated value; otherwise return NULL. The memory associated with the entry is not released immediately, because in the concurrent environment (e.g., multi-threaded application) the caller may need to ensure it is safe to do so. It is managed using the thmap_stage_gc() and thmap_gc() routines.

thmap_stage_gc()

Stage the currently pending entries (the memory not yet released after the deletion) for reclamation (G/C). This operation should be called before the synchronization barrier.

Returns a reference which must be passed to thmap_gc(). Not calling the G/C function for the returned reference would result in a memory leak.

thmap_gc()

Reclaim (G/C) the staged entries i.e. release any memory associated with the deleted keys. The reference must be the value returned by the call to thmap_stage_gc().

This function must be called after the synchronization barrier which guarantees that there are no active readers referencing the staged entries.

If the map is created using the THMAP_SETROOT flag, then the following functions are applicable:

thmap_setroot()

Set the root node. The address must be relative to the base address, as if allocated by the thmap_ops_t::alloc() routine. Return 0 on success and -1 on failure (if already set).

thmap_getroot()

Get the root node address. The returned address will be relative to the base address.

Members of thmap_ops_t are

        uintptr_t (*alloc)(size_t len);
        void      (*free)(uintptr_t addr, size_t len);

CAVEATS

While the NULL values may be inserted, thmap_get() and thmap_del() cannot indicate whether the key was not found or a key with a NULL value was found. If the caller needs to indicate an "empty" value, it can use a special pointer value, such as (void *)(uintptr_t)0x1.

EXAMPLES

	thmap_t *kvmap;
	struct obj *obj;

	kvmap = thmap_create(0, NULL);
	assert(kvmap != NULL);
	...
	obj = obj_create();
	thmap_put(kvmap, "test", sizeof("test") - 1, obj);
	...
	obj = thmap_get(kvmap, "test", sizeof("test") - 1);
	...
	thmap_destroy(kvmap);

AUTHORS