Update upstream source from tag 'upstream/1.39.90'

Update to upstream version '1.39.90'
with Debian dir 898f1bfdb7bf17595463e4195c78d8455df545e6

2 files changed, 323 insertions, 233 deletions

diff --git a/src/c-rbtree/src/c-rbtree.c b/src/c-rbtree/src/c-rbtree.c
index 28de4d95..fbe7c85b 100644
--- a/src/c-rbtree/src/c-rbtree.c
+++ b/src/c-rbtree/src/c-rbtree.c
@@ -1,5 +1,6 @@
 /*
  * RB-Tree Implementation
+ *
  * This implements the insertion/removal of elements in RB-Trees. You're highly
  * recommended to have an RB-Tree documentation at hand when reading this. Both
  * insertion and removal can be split into a handful of situations that can
@@ -57,12 +58,21 @@ static_assert(alignof(CRBTree) <= C_RBTREE_MAX_ALIGN, "Invalid RBTree alignment"
 static_assert(alignof(CRBTree) >= 4, "Invalid CRBTree alignment");
 
 /**
- * c_rbnode_leftmost() - return leftmost child
- * @n:          current node, or NULL
+ * DOC: Traversal
+ *
+ * If you prefer open-coding the tree traversal over the built-in iterators,
+ * c-rbtree provides a set of helpers to find starting position and end nodes
+ * for different kind of tree traversals.
+ */
+/**/
+
+/**
+ * c_rbnode_leftmost() - Return leftmost child
+ * @n:          Current node, or NULL
  *
- * This returns the leftmost child of @n. If @n is NULL, this will return NULL.
- * In all other cases, this function returns a valid pointer. That is, if @n
- * does not have any left children, this returns @n.
+ * This returns the leftmost child of ``n``. If ``n`` is NULL, this will return
+ * NULL. In all other cases, this function returns a valid pointer. That is, if
+ * ``n`` does not have any left children, this returns ``n``.
  *
  * Worst case runtime (n: number of elements in tree): O(log(n))
  *
@@ -76,12 +86,12 @@ _c_public_ CRBNode *c_rbnode_leftmost(CRBNode *n) {
 }
 
 /**
- * c_rbnode_rightmost() - return rightmost child
- * @n:          current node, or NULL
+ * c_rbnode_rightmost() - Return rightmost child
+ * @n:          Current node, or NULL
  *
- * This returns the rightmost child of @n. If @n is NULL, this will return
- * NULL. In all other cases, this function returns a valid pointer. That is, if
- * @n does not have any right children, this returns @n.
+ * This returns the rightmost child of ``n``. If ``n`` is NULL, this will
+ * return NULL. In all other cases, this function returns a valid pointer. That
+ * is, if ``n`` does not have any right children, this returns ``n``.
  *
  * Worst case runtime (n: number of elements in tree): O(log(n))
  *
@@ -95,12 +105,12 @@ _c_public_ CRBNode *c_rbnode_rightmost(CRBNode *n) {
 }
 
 /**
- * c_rbnode_leftdeepest() - return left-deepest child
- * @n:          current node, or NULL
+ * c_rbnode_leftdeepest() - Return left-deepest child
+ * @n:          Current node, or NULL
  *
- * This returns the left-deepest child of @n. If @n is NULL, this will return
- * NULL. In all other cases, this function returns a valid pointer. That is, if
- * @n does not have any children, this returns @n.
+ * This returns the left-deepest child of ``n``. If ``n`` is NULL, this will
+ * return NULL. In all other cases, this function returns a valid pointer. That
+ * is, if ``n`` does not have any children, this returns ``n``.
  *
  * The left-deepest child is defined as the deepest child without any left
  * (grand-...)siblings.
@@ -124,12 +134,12 @@ _c_public_ CRBNode *c_rbnode_leftdeepest(CRBNode *n) {
 }
 
 /**
- * c_rbnode_rightdeepest() - return right-deepest child
- * @n:          current node, or NULL
+ * c_rbnode_rightdeepest() - Return right-deepest child
+ * @n:          Current node, or NULL
  *
- * This returns the right-deepest child of @n. If @n is NULL, this will return
- * NULL. In all other cases, this function returns a valid pointer. That is, if
- * @n does not have any children, this returns @n.
+ * This returns the right-deepest child of ``n``. If ``n`` is NULL, this will
+ * return NULL. In all other cases, this function returns a valid pointer. That
+ * is, if ``n`` does not have any children, this returns ``n``.
  *
  * The right-deepest child is defined as the deepest child without any right
  * (grand-...)siblings.
@@ -153,11 +163,11 @@ _c_public_ CRBNode *c_rbnode_rightdeepest(CRBNode *n) {
 }
 
 /**
- * c_rbnode_next() - return next node
- * @n:          current node, or NULL
+ * c_rbnode_next() - Return next node
+ * @n:          Current node, or NULL
  *
  * An RB-Tree always defines a linear order of its elements. This function
- * returns the logically next node to @n. If @n is NULL, the last node or
+ * returns the logically next node to ``n``. If ``n`` is NULL, the last node or
  * unlinked, this returns NULL.
  *
  * Worst case runtime (n: number of elements in tree): O(log(n))
@@ -179,12 +189,12 @@ _c_public_ CRBNode *c_rbnode_next(CRBNode *n) {
 }
 
 /**
- * c_rbnode_prev() - return previous node
- * @n:          current node, or NULL
+ * c_rbnode_prev() - Return previous node
+ * @n:          Current node, or NULL
  *
  * An RB-Tree always defines a linear order of its elements. This function
- * returns the logically previous node to @n. If @n is NULL, the first node or
- * unlinked, this returns NULL.
+ * returns the logically previous node to ``n``. If ``n`` is NULL, the first
+ * node or unlinked, this returns NULL.
  *
  * Worst case runtime (n: number of elements in tree): O(log(n))
  *
@@ -205,11 +215,11 @@ _c_public_ CRBNode *c_rbnode_prev(CRBNode *n) {
 }
 
 /**
- * c_rbnode_next_postorder() - return next node in post-order
- * @n:          current node, or NULL
+ * c_rbnode_next_postorder() - Return next node in post-order
+ * @n:          Current node, or NULL
  *
- * This returns the next node to @n, based on a left-to-right post-order
- * traversal. If @n is NULL, the root node, or unlinked, this returns NULL.
+ * This returns the next node to ``n``, based on a left-to-right post-order
+ * traversal. If ``n`` is NULL, the root node, or unlinked, this returns NULL.
  *
  * This implements a left-to-right post-order traversal: First visit the left
  * child of a node, then the right, and lastly the node itself. Children are
@@ -217,6 +227,8 @@ _c_public_ CRBNode *c_rbnode_prev(CRBNode *n) {
  *
  * This function can be used to implement a left-to-right post-order traversal:
  *
+ * ::
+ *
  *     for (n = c_rbtree_first_postorder(t); n; n = c_rbnode_next_postorder(n))
  *             visit(n);
  *
@@ -238,18 +250,21 @@ _c_public_ CRBNode *c_rbnode_next_postorder(CRBNode *n) {
 }
 
 /**
- * c_rbnode_prev_postorder() - return previous node in post-order
- * @n:          current node, or NULL
+ * c_rbnode_prev_postorder() - Return previous node in post-order
+ * @n:          Current node, or NULL
  *
- * This returns the previous node to @n, based on a left-to-right post-order
- * traversal. That is, it is the inverse operation to c_rbnode_next_postorder().
- * If @n is NULL, the left-deepest node, or unlinked, this returns NULL.
+ * This returns the previous node to ``n``, based on a left-to-right post-order
+ * traversal. That is, it is the inverse operation to
+ * :c:func:`c_rbnode_next_postorder()`. If ``n`` is NULL, the left-deepest
+ * node, or unlinked, this returns NULL.
  *
  * This function returns the logical previous node in a directed post-order
  * traversal. That is, it effectively does a pre-order traversal (since a
  * reverse post-order traversal is a pre-order traversal). This function does
  * NOT do a right-to-left post-order traversal! In other words, the following
- * invariant is guaranteed, if c_rbnode_next_postorder(n) is non-NULL:
+ * invariant is guaranteed, if ``c_rbnode_next_postorder(n)`` is non-NULL:
+ *
+ * ::
  *
  *     n == c_rbnode_prev_postorder(c_rbnode_next_postorder(n))
  *
@@ -257,6 +272,8 @@ _c_public_ CRBNode *c_rbnode_next_postorder(CRBNode *n) {
  * using the fact that a reverse post-order traversal is also a valid pre-order
  * traversal:
  *
+ * ::
+ *
  *     for (n = c_rbtree_last_postorder(t); n; n = c_rbnode_prev_postorder(n))
  *             visit(n);
  *
@@ -288,11 +305,12 @@ _c_public_ CRBNode *c_rbnode_prev_postorder(CRBNode *n) {
 }
 
 /**
- * c_rbtree_first() - return first node
- * @t:          tree to operate on
+ * c_rbtree_first() - Return first node
+ * @t:          Tree to operate on
  *
  * An RB-Tree always defines a linear order of its elements. This function
- * returns the logically first node in @t. If @t is empty, NULL is returned.
+ * returns the logically first node in ``t``. If ``t`` is empty, NULL is
+ * returned.
  *
  * Fixed runtime (n: number of elements in tree): O(log(n))
  *
@@ -304,11 +322,12 @@ _c_public_ CRBNode *c_rbtree_first(CRBTree *t) {
 }
 
 /**
- * c_rbtree_last() - return last node
- * @t:          tree to operate on
+ * c_rbtree_last() - Return last node
+ * @t:          Tree to operate on
  *
  * An RB-Tree always defines a linear order of its elements. This function
- * returns the logically last node in @t. If @t is empty, NULL is returned.
+ * returns the logically last node in ``t``. If ``t`` is empty, NULL is
+ * returned.
  *
  * Fixed runtime (n: number of elements in tree): O(log(n))
  *
@@ -320,8 +339,8 @@ _c_public_ CRBNode *c_rbtree_last(CRBTree *t) {
 }
 
 /**
- * c_rbtree_first_postorder() - return first node in post-order
- * @t:          tree to operate on
+ * c_rbtree_first_postorder() - Return first node in post-order
+ * @t:          Tree to operate on
  *
  * This returns the first node of a left-to-right post-order traversal. That
  * is, it returns the left-deepest leaf. If the tree is empty, this returns
@@ -340,8 +359,8 @@ _c_public_ CRBNode *c_rbtree_first_postorder(CRBTree *t) {
 }
 
 /**
- * c_rbtree_last_postorder() - return last node in post-order
- * @t:          tree to operate on
+ * c_rbtree_last_postorder() - Return last node in post-order
+ * @t:          Tree to operate on
  *
  * This returns the last node of a left-to-right post-order traversal. That is,
  * it always returns the root node, or NULL if the tree is empty.
@@ -358,9 +377,18 @@ _c_public_ CRBNode *c_rbtree_last_postorder(CRBTree *t) {
         return t->root;
 }
 
+/**
+ * DOC: Tree Modification
+ *
+ * Insertion into and removal from an RB-Tree require rebalancing to make sure
+ * the tree stays balanced. The following functions ensure the tree integrity
+ * is kept.
+ */
+/**/
+
 static inline void c_rbtree_store(CRBNode **ptr, CRBNode *addr) {
         /*
-         * We use volatile accesses whenever we STORE @left or @right members
+         * We use volatile accesses whenever we STORE left or right members
          * of a node. This guarantees that any parallel, lockless lookup gets
          * to see those stores in the correct order, which itself guarantees
          * that there're no temporary loops during tree rotation.
@@ -437,6 +465,8 @@ static inline CRBTree *c_rbnode_push_root(CRBNode *n, CRBTree *t) {
  * The sole purpose of this function is to shortcut left/right conditionals
  * like this:
  *
+ * ::
+ *
  *     if (old == old->parent->left)
  *             old->parent->left = new;
  *     else
@@ -457,12 +487,12 @@ static inline void c_rbnode_swap_child(CRBNode *old, CRBNode *new) {
 }
 
 /**
- * c_rbtree_move() - move tree
- * @to:         destination tree
- * @from:       source tree
+ * c_rbtree_move() - Move tree
+ * @to:         Destination tree
+ * @from:       Source tree
  *
- * This imports the entire tree from @from into @to. @to must be empty! @from
- * will be empty afterwards.
+ * This imports the entire tree from ``from`` into ``to``. ``to`` must be
+ * empty! ``from`` will be empty afterwards.
  *
  * Note that this operates in O(1) time. Only the root-entry is updated to
  * point to the new tree-root.
@@ -672,21 +702,21 @@ static inline void c_rbtree_paint(CRBNode *n) {
 }
 
 /**
- * c_rbnode_link() - link node into tree
- * @p:          parent node to link under
- * @l:          left/right slot of @p to link at
- * @n:          node to add
+ * c_rbnode_link() - Link node into tree
+ * @p:          Parent node to link under
+ * @l:          Left/right slot of ``p`` to link at
+ * @n:          Node to add
  *
- * This links @n into an tree underneath another node. The caller must provide
- * the exact spot where to link the node. That is, the caller must traverse the
- * tree based on their search order. Once they hit a leaf where to insert the
- * node, call this function to link it and rebalance the tree.
+ * This links ``n`` into an tree underneath another node. The caller must
+ * provide the exact spot where to link the node. That is, the caller must
+ * traverse the tree based on their search order. Once they hit a leaf where to
+ * insert the node, call this function to link it and rebalance the tree.
  *
  * For this to work, the caller must provide a pointer to the parent node. If
- * the tree might be empty, you must resort to c_rbtree_add().
+ * the tree might be empty, you must resort to :c:func:`c_rbtree_add()`.
  *
- * In most cases you are better off using c_rbtree_add(). See there for details
- * how tree-insertion works.
+ * In most cases you are better off using :c:func:`c_rbtree_add()`. See there
+ * for details how tree-insertion works.
  */
 _c_public_ void c_rbnode_link(CRBNode *p, CRBNode **l, CRBNode *n) {
         c_assert(p);
@@ -703,18 +733,19 @@ _c_public_ void c_rbnode_link(CRBNode *p, CRBNode **l, CRBNode *n) {
 }
 
 /**
- * c_rbtree_add() - add node to tree
- * @t:          tree to operate one
- * @p:          parent node to link under, or NULL
- * @l:          left/right slot of @p (or root) to link at
- * @n:          node to add
- *
- * This links @n into the tree given as @t. The caller must provide the exact
- * spot where to link the node. That is, the caller must traverse the tree
- * based on their search order. Once they hit a leaf where to insert the node,
- * call this function to link it and rebalance the tree.
+ * c_rbtree_add() - Add node to tree
+ * @t:          Tree to operate one
+ * @p:          Parent node to link under, or NULL
+ * @l:          Left/right slot of @p (or root) to link at
+ * @n:          Node to add
+ *
+ * This links @n into the tree given as ``t``. The caller must provide the
+ * exact spot where to link the node. That is, the caller must traverse the
+ * tree based on their search order. Once they hit a leaf where to insert the
+ * node, call this function to link it and rebalance the tree.
  *
- * A typical insertion would look like this (@t is your tree, @n is your node):
+ * A typical insertion would look like this (``t`` is your tree, ``n`` is your
+ * node)::
  *
  *        CRBNode **i, *p;
  *
@@ -731,7 +762,7 @@ _c_public_ void c_rbnode_link(CRBNode *p, CRBNode **l, CRBNode *n) {
  *        c_rbtree_add(t, p, i, n);
  *
  * Once the node is linked into the tree, a simple lookup on the same tree can
- * be coded like this:
+ * be coded like this::
  *
  *        CRBNode *i;
  *
@@ -747,11 +778,13 @@ _c_public_ void c_rbnode_link(CRBNode *p, CRBNode **l, CRBNode *n) {
  *        }
  *
  * When you add nodes to a tree, the memory contents of the node do not matter.
- * That is, there is no need to initialize the node via c_rbnode_init().
+ * That is, there is no need to initialize the node via
+ * :c:func:`c_rbnode_init()`.
  * However, if you relink nodes multiple times during their lifetime, it is
- * usually very convenient to use c_rbnode_init() and c_rbnode_unlink() (rather
- * than c_rbnode_unlink_stale()). In those cases, you should validate that a
- * node is unlinked before you call c_rbtree_add().
+ * usually very convenient to use :c:func:`c_rbnode_init()` and
+ * :c:func:`c_rbnode_unlink()` (rather than :c:func:`c_rbnode_unlink_stale()`).
+ * In those cases, you should validate that a node is unlinked before you call
+ * :c:func:`c_rbtree_add()`.
  */
 _c_public_ void c_rbtree_add(CRBTree *t, CRBNode *p, CRBNode **l, CRBNode *n) {
         c_assert(t);
@@ -968,14 +1001,14 @@ static inline void c_rbnode_rebalance(CRBNode *n) {
 }
 
 /**
- * c_rbnode_unlink_stale() - remove node from tree
- * @n:          node to remove
+ * c_rbnode_unlink_stale() - Remove node from tree
+ * @n:          Node to remove
  *
  * This removes the given node from its tree. Once unlinked, the tree is
  * rebalanced.
  *
- * This does *NOT* reset @n to being unlinked. If you need this, use
- * c_rbtree_unlink().
+ * This does *NOT* reset ``n`` to being unlinked. If you need this, use
+ * :c:func:`c_rbtree_unlink()`.
  */
 _c_public_ void c_rbnode_unlink_stale(CRBNode *n) {
         CRBTree *t;
diff --git a/src/c-rbtree/src/c-rbtree.h b/src/c-rbtree/src/c-rbtree.h
index d4d0fe45..2d9a1d20 100644
--- a/src/c-rbtree/src/c-rbtree.h
+++ b/src/c-rbtree/src/c-rbtree.h
@@ -1,31 +1,36 @@
 #pragma once
 
-/**
- * Standalone Red-Black-Tree Implementation in Standard ISO-C11
- *
- * This library provides an RB-Tree API, that is fully implemented in ISO-C11
- * and has no external dependencies. Furthermore, tree traversal, memory
- * allocations, and key comparisons are completely controlled by the API user.
- * The implementation only provides the RB-Tree specific rebalancing and
- * coloring.
- *
- * A tree is represented by the "CRBTree" structure. It contains a *single*
- * field, which is a pointer to the root node. If NULL, the tree is empty. If
- * non-NULL, there is at least a single element in the tree.
- *
- * Each node of the tree is represented by the "CRBNode" structure. It has
- * three fields. The @left and @right members can be accessed by the API user
- * directly to traverse the tree. The third member is a combination of the
- * parent pointer and a set of flags.
- * API users are required to embed the CRBNode object into their own objects
- * and then use offsetof() (i.e., container_of() and friends) to turn CRBNode
- * pointers into pointers to their own structure.
+/*
+ * c-rbtree: Standalone Red-Black-Tree Implementation in Standard ISO-C11
+ *
+ * Main public header of the c-rbtree library.
  */
 
 #ifdef __cplusplus
 extern "C" {
 #endif
 
+/**
+ * DOC:
+ *
+ * The ``c-rbtree.h`` header exposes the full API of the c-rbtree library. It
+ * provides access to the Red-Black Tree structure as well as helper functions
+ * to perform standard tree operations.
+ *
+ * A tree is represented by the :c:struct:`CRBTree` structure. It contains a
+ * *single* field, which is a pointer to the root node. If NULL, the tree is
+ * empty. If non-NULL, there is at least a single element in the tree.
+ *
+ * Each node of the tree is represented by the :c:struct:`CRBNode` structure.
+ * It has three fields. The ``left`` and ``right`` members can be accessed by
+ * the API user directly to traverse the tree. The third member is a
+ * combination of the parent pointer and a set of flags. API users are required
+ * to embed the :c:struct:`CRBNode` object into their own objects and then use
+ * ``offsetof()`` (i.e., ``container_of()`` and friends) to turn
+ * :c:struct:`CRBNode` pointers into pointers to their own enclosing type:
+ */
+/**/
+
 #include <assert.h>
 #include <stdalign.h>
 #include <stddef.h>
@@ -39,35 +44,55 @@ typedef struct CRBTree CRBTree;
 #define C_RBNODE_FLAG_MASK              (0x3UL)
 
 /**
+ * DOC: Tree Structure
+ *
+ * The tree structure of c-rbtree is directly exposed in its API. Callers are
+ * allowed to access the node and tree structures directly to traverse the
+ * tree. Tree modifications, however, should be performed via the functions
+ * provided by the library.
+ */
+/**/
+
+/**
  * struct CRBNode - Node of a Red-Black Tree
- * @__parent_and_flags:         internal state
- * @left:                       left child, or NULL
- * @right:                      right child, or NULL
  *
- * Each node in an RB-Tree must embed a CRBNode object. This object contains
- * pointers to its left and right child, which can be freely accessed by the
- * API user at any time. They are NULL, if the node does not have a left/right
- * child.
+ * Each node in an RB-Tree must embed a :c:struct:`CRBNode` object. This object
+ * contains pointers to its left and right child, which can be freely accessed
+ * by the API user at any time. They are NULL, if the node does not have a
+ * left/right child.
  *
- * The @__parent_and_flags field must never be accessed directly. It encodes
+ * The ``__parent_and_flags`` field must never be accessed directly. It encodes
  * the pointer to the parent node, and the color of the node. Use the accessor
  * functions instead.
  *
- * There is no reason to initialize a CRBNode object before linking it.
- * However, if you need a boolean state that tells you whether the node is
- * linked or not, you should initialize the node via c_rbnode_init() or
- * C_RBNODE_INIT.
+ * There is no reason to initialize a :c:struct:`CRBNode` object before linking
+ * it. However, if you need a boolean state that tells you whether the node is
+ * linked or not, you should initialize the node via :c:func:`c_rbnode_init()`
+ * or :c:macro:`C_RBNODE_INIT()`.
  */
 struct CRBNode {
+        /** Anonymous union for alignment guarantees */
         union {
+                /** Internal state encoding the parent pointer and state */
                 unsigned long __parent_and_flags;
                 /* enforce >=4-byte alignment for @__parent_and_flags */
                 alignas(4) unsigned char __align_dummy;
         };
+        /** Left child, or NULL */
         CRBNode *left;
+        /** Right child, or NULL */
         CRBNode *right;
 };
 
+/**
+ * C_RBNODE_INIT() - Initialize RBNode Object
+ * @_var:               Backpointer to the variable
+ *
+ * Set the contents of the specified node to its unlinked, unused state, ready
+ * to be linked into a tree.
+ *
+ * Return: Evaluates to the initializer for `_var`.
+ */
 #define C_RBNODE_INIT(_var) { .__parent_and_flags = (unsigned long)&(_var) }
 
 CRBNode *c_rbnode_leftmost(CRBNode *n);
@@ -83,23 +108,31 @@ void c_rbnode_link(CRBNode *p, CRBNode **l, CRBNode *n);
 void c_rbnode_unlink_stale(CRBNode *n);
 
 /**
- * struct CRBTree - Red-Black Tree
- * @root:       pointer to the root node, or NULL
+ * struct CRBTree - Red-Black Tree Top-Level Structure
  *
  * Each Red-Black Tree is rooted in an CRBTree object. This object contains a
  * pointer to the root node of the tree. The API user is free to access the
- * @root member at any time, and use it to traverse the tree.
+ * ``root`` member at any time, and use it to traverse the tree.
  *
  * To initialize an RB-Tree, set it to NULL / all zero.
  */
 struct CRBTree {
+        /** Anonymous union for alignment guarantees */
         union {
+                /** Pointer to the root node, or NULL */
                 CRBNode *root;
                 /* enforce >=4-byte alignment for @root */
                 alignas(4) unsigned char __align_dummy;
         };
 };
 
+/**
+ * C_RBTREE_INIT() - Initialize RBTree Object
+ *
+ * Set the contents of the specified tree to its pristine, empty state.
+ *
+ * Return: Evaluates to the initializer for a :c:struct:`CRBTree` object.
+ */
 #define C_RBTREE_INIT {}
 
 CRBNode *c_rbtree_first(CRBTree *t);
@@ -111,49 +144,59 @@ void c_rbtree_move(CRBTree *to, CRBTree *from);
 void c_rbtree_add(CRBTree *t, CRBNode *p, CRBNode **l, CRBNode *n);
 
 /**
- * c_rbnode_init() - mark a node as unlinked
- * @n:          node to operate on
+ * c_rbnode_init() - Mark a node as unlinked
+ * @n:          Node to operate on
  *
- * This marks the node @n as unlinked. The node will be set to a valid state
+ * This marks the node ``n`` as unlinked. The node will be set to a valid state
  * that can never happen if the node is linked in a tree. Furthermore, this
  * state is fully known to the implementation, and as such handled gracefully
  * in all cases.
  *
- * You are *NOT* required to call this on your node. c_rbtree_add() can handle
- * uninitialized nodes just fine. However, calling this allows to use
- * c_rbnode_is_linked() to check for the state of a node. Furthermore,
- * iterators and accessors can be called on initialized (yet unlinked) nodes.
+ * You are *NOT* required to call this on your node. :c:func:`c_rbtree_add()`
+ * ca handle uninitialized nodes just fine. However, calling this allows to use
+ * :c:func:`c_rbnode_is_linked()` to check for the state of a node.
+ * Furthermore, iterators and accessors can be called on initialized (yet
+ * unlinked) nodes.
  *
- * Use the C_RBNODE_INIT macro if you want to initialize static variables.
+ * Use the :c:macro:`C_RBNODE_INIT` macro if you want to initialize static
+ * variables.
  */
 static inline void c_rbnode_init(CRBNode *n) {
         *n = (CRBNode)C_RBNODE_INIT(*n);
 }
 
 /**
- * c_rbnode_entry() - get parent container of tree node
- * @_what:              tree node, or NULL
- * @_t:                 type of parent container
- * @_m:                 member name of tree node in @_t
+ * c_rbnode_entry() - Get parent container of tree node
+ * @_what:              Tree node, or NULL
+ * @_t:                 Type of parent container
+ * @_m:                 Member name of tree node in ``_t``
  *
- * If the tree node @_what is embedded into a surrounding structure, this will
- * turn the tree node pointer @_what into a pointer to the parent container
- * (using offsetof(3), or sometimes called container_of(3)).
+ * If the tree node ``_what`` is embedded into a surrounding structure, this
+ * will turn the tree node pointer ``_what`` into a pointer to the parent
+ * container (using ``offsetof(3)``, or sometimes called
+ * ``container_of(3)``).
  *
- * If @_what is NULL, this will also return NULL.
+ * If ``_what`` is NULL, this will also return NULL.
  *
  * Return: Pointer to parent container, or NULL.
  */
-#define c_rbnode_entry(_what, _t, _m) \
-        ((_t *)(void *)(((unsigned long)(void *)(_what) ?: \
+#define c_rbnode_entry(_what, _t, _m)                                           \
+        /*                                                                      \
+         * Note: This was carefully designed to avoid multiple evaluation of    \
+         *       `_what`, but avoid context-expression-extensions. That is why  \
+         *       it uses the possibly odd style of                              \
+         *       `(x ?: offsetof(...)) - offsetof(...))`.                       \
+         */                                                                     \
+        ((_t *)(void *)(((unsigned long)(void *)(_what) ?:                      \
                          offsetof(_t, _m)) - offsetof(_t, _m)))
 
 /**
- * c_rbnode_parent() - return parent pointer
- * @n           node to access
+ * c_rbnode_parent() - Return parent pointer
+ * @n:          Node to access
  *
- * This returns a pointer to the parent of the given node @n. If @n does not
- * have a parent, NULL is returned. If @n is not linked, @n itself is returned.
+ * This returns a pointer to the parent of the given node ``n``. If ``n`` does
+ * not have a parent, NULL is returned. If ``n`` is not linked, ``n`` itself is
+ * returned.
  *
  * You should not call this on unlinked or uninitialized nodes! If you do, you
  * better know its semantics.
@@ -167,8 +210,8 @@ static inline CRBNode *c_rbnode_parent(CRBNode *n) {
 }
 
 /**
- * c_rbnode_is_linked() - check whether a node is linked
- * @n:          node to check, or NULL
+ * c_rbnode_is_linked() - Check whether a node is linked
+ * @n:          Node to check, or NULL
  *
  * This checks whether the passed node is linked. If you pass NULL, or if the
  * node is not linked into a tree, this will return false. Otherwise, this
@@ -176,9 +219,9 @@ static inline CRBNode *c_rbnode_parent(CRBNode *n) {
  *
  * Note that you must have either linked the node or initialized it, before
  * calling this function. Never call this function on uninitialized nodes.
- * Furthermore, removing a node via c_rbnode_unlink_stale() does *NOT* mark the
- * node as unlinked. You have to call c_rbnode_init() yourself after removal, or
- * use the c_rbnode_unlink() helper.
+ * Furthermore, removing a node via :c:func:`c_rbnode_unlink_stale()` does *NOT*
+ * mark the node as unlinked. You have to call :c:func:`c_rbnode_init()`
+ * yourself after removal, or use :c:func:`c_rbnode_unlink()`.
  *
  * Return: true if the node is linked, false if not.
  */
@@ -187,13 +230,15 @@ static inline _Bool c_rbnode_is_linked(CRBNode *n) {
 }
 
 /**
- * c_rbnode_unlink() - safely remove node from tree and reinitialize it
- * @n:          node to remove, or NULL
+ * c_rbnode_unlink() - Safely remove node from tree and reinitialize it
+ * @n:          Node to remove, or NULL
+ *
+ * This is almost the same as :c:func:`c_rbnode_unlink_stale()`, but extends it
+ * slightly, to be more convenient to use in many cases:
  *
- * This is almost the same as c_rbnode_unlink_stale(), but extends it slightly, to be
- * more convenient to use in many cases:
- *  - if @n is unlinked or NULL, this is a no-op
- *  - @n is reinitialized after being removed
+ *  - If ``n`` is unlinked or NULL, this is a no-op.
+ *
+ *  - ``n`` is reinitialized after being removed.
  */
 static inline void c_rbnode_unlink(CRBNode *n) {
         if (c_rbnode_is_linked(n)) {
@@ -203,20 +248,20 @@ static inline void c_rbnode_unlink(CRBNode *n) {
 }
 
 /**
- * c_rbtree_init() - initialize a new RB-Tree
- * @t:          tree to operate on
+ * c_rbtree_init() - Initialize a new RB-Tree
+ * @t:          Tree to operate on
  *
  * This initializes a new, empty RB-Tree. An RB-Tree must be initialized before
  * any other functions are called on it. Alternatively, you can zero its memory
- * or assign C_RBTREE_INIT.
+ * or assign :c:macro:`C_RBTREE_INIT`.
  */
 static inline void c_rbtree_init(CRBTree *t) {
         *t = (CRBTree)C_RBTREE_INIT;
 }
 
 /**
- * c_rbtree_is_empty() - check whether an RB-tree is empty
- * @t:          tree to operate on
+ * c_rbtree_is_empty() - Check whether an RB-tree is empty
+ * @t:          Tree to operate on
  *
  * This checks whether the passed RB-Tree is empty.
  *
@@ -227,35 +272,43 @@ static inline _Bool c_rbtree_is_empty(CRBTree *t) {
 }
 
 /**
- * CRBCompareFunc - compare a node to a key
- * @t:          tree where the node is linked to
- * @k:          key to compare
- * @n:          node to compare
+ * DOC: Search
+ *
+ * While the API supports direct traversal via the open-coded structures, it
+ * can be cumbersome to use at times. If you, instead, provide a callback to
+ * compare entries in the tree, you can use the following helpers to search the
+ * tree for specific entries, or slots to insert new entries.
+ */
+/**/
+
+/**
+ * CRBCompareFunc - Function type to compare a node to a key
  *
  * If you use the tree-traversal helpers (which are optional), you need to
  * provide this callback so they can compare nodes in a tree to the key you
  * look for.
  *
- * The tree @t is provided as optional context to this callback. The key you
- * look for is provided as @k, the current node that should be compared to is
- * provided as @n. This function should work like strcmp(), that is, return <0
- * if @key orders before @n, 0 if both compare equal, and >0 if it orders after
- * @n.
+ * The tree is provided as optional context ``t`` to this callback. The key you
+ * look for is provided as ``k``, the current node that should be compared to
+ * is provided as ``n``. This function should work like ``strcmp()``, that is,
+ * return <0 if ``key`` orders before ``n``, 0 if both compare equal, and >0 if
+ * it orders after ``n``.
  */
 typedef int (*CRBCompareFunc) (CRBTree *t, void *k, CRBNode *n);
 
 /**
- * c_rbtree_find_node() - find node
- * @t:          tree to search through
- * @f:          comparison function
- * @k:          key to search for
- *
- * This searches through @t for a node that compares equal to @k. The function
- * @f must be provided by the caller, which is used to compare nodes to @k. See
- * the documentation of CRBCompareFunc for details.
- *
- * If there are multiple entries that compare equal to @k, this will return a
- * pseudo-randomly picked node. If you need stable lookup functions for trees
+ * c_rbtree_find_node() - Find node
+ * @t:          Tree to search through
+ * @f:          Comparison function
+ * @k:          Key to search for
+ *
+ * This searches through ``t`` for a node that compares equal to ``k``. The
+ * function ``f`` must be provided by the caller, which is used to compare
+ * nodes to ``k``. See the documentation of :c:type:`CRBCompareFunc` for
+ * details.
+ *
+ * If there are multiple entries that compare equal to ``k``, this will return
+ * a pseudo-randomly picked node. If you need stable lookup functions for trees
  * where duplicate entries are allowed, you better code your own lookup.
  *
  * Return: Pointer to matching node, or NULL.
@@ -281,19 +334,21 @@ static inline CRBNode *c_rbtree_find_node(CRBTree *t, CRBCompareFunc f, const vo
 }
 
 /**
- * c_rbtree_find_entry() - find entry
- * @_t:         tree to search through
- * @_f:         comparison function
- * @_k:         key to search for
- * @_s:         type of the structure that embeds the nodes
- * @_m:         name of the node-member in type @_t
- *
- * This is very similar to c_rbtree_find_node(), but instead of returning a
- * pointer to the CRBNode, it returns a pointer to the surrounding object. This
- * object must embed the CRBNode object. The type of the surrounding object
- * must be given as @_s, and the name of the embedded CRBNode member as @_m.
- *
- * See c_rbtree_find_node() and c_rbnode_entry() for more details.
+ * c_rbtree_find_entry() - Find entry
+ * @_t:         Tree to search through
+ * @_f:         Comparison function
+ * @_k:         Key to search for
+ * @_s:         Type of the structure that embeds the nodes
+ * @_m:         Name of the node-member in type @_t
+ *
+ * This is very similar to :c:func:`c_rbtree_find_node()`, but instead of
+ * returning a pointer to the :c:struct:`CRBNode`, it returns a pointer to the
+ * surrounding object. This object must embed the :c:struct:`CRBNode` object.
+ * The type of the surrounding object must be given as ``_s``, and the name of
+ * the embedded :c:struct:`CRBNode` member as ``_m``.
+ *
+ * See :c:func:`c_rbtree_find_node()` and :c:macro:`c_rbnode_entry()` for more
+ * details.
  *
  * Return: Pointer to found entry, NULL if not found.
  */
@@ -301,22 +356,23 @@ static inline CRBNode *c_rbtree_find_node(CRBTree *t, CRBCompareFunc f, const vo
         c_rbnode_entry(c_rbtree_find_node((_t), (_f), (_k)), _s, _m)
 
 /**
- * c_rbtree_find_slot() - find slot to insert new node
- * @t:          tree to search through
- * @f:          comparison function
- * @k:          key to search for
- * @p:          output storage for parent pointer
- *
- * This searches through @t just like c_rbtree_find_node() does. However,
- * instead of returning a pointer to a node that compares equal to @k, this
- * searches for a slot to insert a node with key @k. A pointer to the slot is
- * returned, and a pointer to the parent of the slot is stored in @p. Both
- * can be passed directly to c_rbtree_add(), together with your node to insert.
- *
- * If there already is a node in the tree, that compares equal to @k, this will
- * return NULL and store the conflicting node in @p. In all other cases,
- * this will return a pointer (non-NULL) to the empty slot to insert the node
- * at. @p will point to the parent node of that slot.
+ * c_rbtree_find_slot() - Find slot to insert new node
+ * @t:          Tree to search through
+ * @f:          Comparison function
+ * @k:          Key to search for
+ * @p:          Output storage for parent pointer
+ *
+ * This searches through ``t`` just like :c:func:`c_rbtree_find_node()` does.
+ * However, instead of returning a pointer to a node that compares equal to
+ * ``k``, this searches for a slot to insert a node with key ``k``. A pointer
+ * to the slot is returned, and a pointer to the parent of the slot is stored
+ * in ``p``. Both can be passed directly to :c:func:`c_rbtree_add()`, together
+ * with your node to insert.
+ *
+ * If there already is a node in the tree, that compares equal to ``k``, this
+ * will return NULL and store the conflicting node in ``p``. In all other
+ * cases, this will return a pointer (non-NULL) to the empty slot to insert the
+ * node at. ``p`` will point to the parent node of that slot.
  *
  * If you want trees that allow duplicate nodes, you better code your own
  * insertion function.
@@ -347,34 +403,35 @@ static inline CRBNode **c_rbtree_find_slot(CRBTree *t, CRBCompareFunc f, const v
 }
 
 /**
- * c_rbtree_for_each*() - iterators
- *
- * The c_rbtree_for_each*() macros provide simple for-loop wrappers to iterate
- * an RB-Tree. They come in a set of flavours:
- *
- *   - "entry": This combines c_rbnode_entry() with the loop iterator, so the
- *              iterator always has the type of the surrounding object, rather
- *              than CRBNode.
- *
- *   - "safe": The loop iterator always keeps track of the next element to
- *             visit. This means, you can safely modify the current element,
- *             while retaining loop-integrity.
- *             You still must not touch any other entry of the tree. Otherwise,
- *             the loop-iterator will be corrupted. Also remember to only
- *             modify the tree in a way compatible with your iterator-order.
- *             That is, if you use in-order iteration (default), you can unlink
- *             your current object, including re-balancing the tree. However,
- *             if you use post-order, you must not trigger a tree rebalance
- *             operation, since it is not an invariant of post-order iteration.
- *
- *   - "postorder": Rather than the default in-order iteration, this iterates
- *                  the tree in post-order.
- *
- *   - "unlink": This unlinks the current element from the tree before the loop
- *               code is run. Note that the tree is not rebalanced. That is,
- *               you must never break out of the loop. If you do so, the tree
- *               is corrupted.
+ * DOC: Iterators
+ *
+ * The ``c_rbtree_for_each*()`` macros provide simple for-loop wrappers to
+ * iterate an RB-Tree. They come in a set of flavours:
+ *
+ * :entry: This combines :c:macro:`c_rbnode_entry()` with the loop iterator, so
+ *         the iterator always has the type of the surrounding object, rather
+ *         than :c:type:`CRBNode`.
+ *
+ * :safe: The loop iterator always keeps track of the next element to
+ *        visit. This means, you can safely modify the current element,
+ *        while retaining loop-integrity.
+ *        You still must not touch any other entry of the tree. Otherwise,
+ *        the loop-iterator will be corrupted. Also remember to only
+ *        modify the tree in a way compatible with your iterator-order.
+ *        That is, if you use in-order iteration (default), you can unlink
+ *        your current object, including re-balancing the tree. However,
+ *        if you use post-order, you must not trigger a tree rebalance
+ *        operation, since it is not an invariant of post-order iteration.
+ *
+ * :postorder: Rather than the default in-order iteration, this iterates
+ *             the tree in post-order.
+ *
+ * :unlink: This unlinks the current element from the tree before the loop
+ *          code is run. Note that the tree is not rebalanced. That is,
+ *          you must never break out of the loop. If you do so, the tree
+ *          is corrupted.
  */
+/**/
 
 #define c_rbtree_for_each(_iter, _tree)                                                                 \
         for (_iter = c_rbtree_first(_tree);                                                             \