Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help 
THMAP(3)		     Library Functions Manual			THMAP(3)

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 aver-
	 age.
     -	 Lookups are lock-free and inserts/deletes are using fine-grained  lock-
	 ing.
     -	 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 manu-
				 ally  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 asso-
		   ciated 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 al-
		   ready present, return the already existing  associated  value
		   without  changing it.  Otherwise, on a successful insert, re-
		   turn 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 as-
		   sociated 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 re-
		   leased after the deletion) for reclamation (G/C).  This oper-
		   ation 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 re-
		   sult in a memory leak.

     thmap_gc()    Reclaim  (G/C) the staged entries i.e. release any memory as-
		   sociated 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 bar-
		   rier which guarantees that there are no active readers refer-
		   encing 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() rou-
		    tine.  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
     The implementation uses pointer tagging and atomic  operations.   This  re-
     quires the base address and the allocations to provide at least word align-
     ment.

     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 spe-
     cial pointer value, such as (void *)(uintptr_t)0x1.

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

	     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>

FreeBSD ports 15.quarterly	December 11, 2018			THMAP(3)

Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=thmap&sektion=3&manpath=FreeBSD+Ports+15.1.quarterly>

home | help