Updated: 2020/Jul/29

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

     thmap - concurrent trie-hash map

     #include <thmap.h>

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

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

     thmap_gc(thmap_t *hmap, void *ref);

     thmap_setroot(thmap_t *thmap, uintptr_t root_offset);

     thmap_getroot(const thmap_t *thmap);

     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
     -   Lookups are lock-free and inserts/deletes are using fine-grained
     -   Incremental growth of the data structure (no large
     -   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.

                   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.

                                 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().

                   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.

                   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

                   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:

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

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

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

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

     Mindaugas Rasiukevicius <rmind@noxt.eu>

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

     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