Updated: 2020/Jul/29


THMAP(9)                   Kernel Developer's Manual                  THMAP(9)

NAME
     thmap - concurrent trie-hash map

SYNOPSIS
     #include <thmap.h>

     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
     Concurrent trie-hash map -- a general purpose associative array,
     combining the elements of hashing and radix trie.  Highlights:

     -   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);

EXAMPLES
     Simple case backed by malloc(3), which could be used in multi-threaded
     environment:

             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
     Mindaugas Rasiukevicius <rmind@noxt.eu>

CAVEATS
     The implementation uses pointer tagging and atomic operations.  This
     requires the base address and the allocations to provide at least word
     alignment.

     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.

NetBSD 9.99                    December 11, 2018                   NetBSD 9.99