Updated: 2022/Sep/29

Please read Privacy Policy. It's for your privacy.

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

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

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

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

     void *
     thmap_stage_gc(thmap_t *thmap);

     thmap_gc(thmap_t *thmap, 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.

     thmap_create(baseptr, ops, flags)
           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

           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

           Destroy the map, freeing the memory it uses.

     thmap_get(thmap, key, len)
           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

     thmap_put(thmap, key, len, val)
           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(thmap, key, len)
           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 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(thmap, ref)
           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(thmap, root_offset)
           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