This repository contains a CTrie implementation as described in Cache-Aware Lock-Free Concurrent Hash Tries.
Note that this implementation in its current form:
- Does not implement node deletion. It was not required for the use-case for which this implementation was written. Consequently, we did not implement tomb node support.
- Resolves hashcode conflicts using array lists in what we call an "LNode".
- Leaks memory. None of the memory that is no longer used by the CTrie will be
freed, because at the time of removal, it is not clear whether a different
thread might still be using it. Implementing lock-free reference counting in
the
any_node_t
should probably allow you to fix this together withretain
/release
-style functions, whereretain
is called before a node is read, andrelease
is called after reading a node is finished. - Was written to support putting the CTrie into a shared memory area that is
mapped into multiple processes at different addresses. The requirement to
put the shared memory segment at different addresses in different processes
means that instead of pointers, raw offsets must be used and all offsets
must be interpreted relative to a shared memory segment base address. For
this reason, all pointer operations are abstracted using the
PTR()
andDEREF()
macros. Note that for this to work, you will need a memory allocator that supports obtaining and releasing memory from a shared memory area; the implementation should be refactored to support passing a malloc/realloc/free pointer set toctrie_new()
. - There is currently no support for arbitrary value types (i.e. using
size_t vallen
andvoid* value
). Instead we define avalue_t
that supports our use-case.
This source code is licensed under the BSD-2-Clause license.