diff options
author | Thomas Haller <thaller@redhat.com> | 2022-07-06 10:07:13 +0200 |
---|---|---|
committer | Thomas Haller <thaller@redhat.com> | 2022-07-06 10:07:14 +0200 |
commit | 8fdcd7030c97362793315b9df7e3d26cb57563b5 (patch) | |
tree | 7e4646cbaa7a35c8b5b104deff2323a5c5628c3b | |
parent | 7d2bf498caf06e3aea06bcf5aa33a4b0bf66f735 (diff) | |
parent | 49f854886e3fcbf5fef7658e73b0fbba22ad74c3 (diff) | |
download | NetworkManager-8fdcd7030c97362793315b9df7e3d26cb57563b5.tar.gz |
c-rbtree: re-import git-subtree for 'src/c-rbtree'
git subtree pull --prefix src/c-rbtree git@github.com:c-util/c-rbtree.git main --squash
-rw-r--r-- | src/c-rbtree/.github/workflows/ci.yml | 20 | ||||
-rw-r--r-- | src/c-rbtree/AUTHORS | 1 | ||||
-rw-r--r-- | src/c-rbtree/NEWS.md | 8 | ||||
-rw-r--r-- | src/c-rbtree/meson.build | 2 | ||||
-rw-r--r-- | src/c-rbtree/src/c-rbtree.c | 201 | ||||
-rw-r--r-- | src/c-rbtree/src/c-rbtree.h | 360 | ||||
-rw-r--r-- | src/c-rbtree/src/meson.build | 13 |
7 files changed, 354 insertions, 251 deletions
diff --git a/src/c-rbtree/.github/workflows/ci.yml b/src/c-rbtree/.github/workflows/ci.yml index 6350d3c746..9db40b619f 100644 --- a/src/c-rbtree/.github/workflows/ci.yml +++ b/src/c-rbtree/.github/workflows/ci.yml @@ -15,9 +15,29 @@ jobs: m32: true matrixmode: true valgrind: true + ci-ptrace: name: Reduced CI with PTrace uses: bus1/cabuild/.github/workflows/ci-c-util.yml@v1 with: cabuild_ref: "v1" mesonargs: '-Dptrace=true' + + ci-macos: + name: CI on MacOS + runs-on: macos-latest + steps: + - name: Fetch Sources + uses: actions/checkout@v2 + - name: Setup Python + uses: actions/setup-python@v2 + with: + python-version: '3.x' + - name: Install Python Dependencies + run: pip install meson ninja + - name: Prepare Build + run: meson setup build + - name: Run Build + run: meson compile -v -C build + - name: Run Test Suite + run: meson test -v -C build diff --git a/src/c-rbtree/AUTHORS b/src/c-rbtree/AUTHORS index cd557de26c..7e4f368d8b 100644 --- a/src/c-rbtree/AUTHORS +++ b/src/c-rbtree/AUTHORS @@ -34,6 +34,7 @@ COPYRIGHT: (ordered alphabetically) AUTHORS: (ordered alphabetically) David Rheinsberg <david.rheinsberg@gmail.com> + Evgeny Vereshchagin <evvers@ya.ru> Kay Sievers <kay@vrfy.org> Thomas Haller <thaller@redhat.com> Tom Gundersen <teg@jklm.no> diff --git a/src/c-rbtree/NEWS.md b/src/c-rbtree/NEWS.md index 3fe061d977..71415f6768 100644 --- a/src/c-rbtree/NEWS.md +++ b/src/c-rbtree/NEWS.md @@ -1,6 +1,6 @@ # c-rbtree - Intrusive Red-Black Tree Collection -## CHANGES WITH 4: +## CHANGES WITH 3.1.0: * Add 'ptrace' build option to enable running tests using 'ptrace' to verify extended execution properties. This option should not @@ -9,11 +9,9 @@ * meson-0.60.0 is now the minimum required meson version. - * TBD + Contributions from: David Rheinsberg, Evgeny Vereshchagin - Contributions from: David Rheinsberg - - - TBD, YYYY-MM-DD + - Brno, 2022-06-22 ## CHANGES WITH 3: diff --git a/src/c-rbtree/meson.build b/src/c-rbtree/meson.build index f3ae209dbb..3e7af9ce17 100644 --- a/src/c-rbtree/meson.build +++ b/src/c-rbtree/meson.build @@ -6,7 +6,7 @@ project( ], license: 'Apache', meson_version: '>=0.60.0', - version: '3.0.0', + version: '3.1.0', ) major = meson.project_version().split('.')[0] project_description = 'Intrusive Red-Black Tree Collection' diff --git a/src/c-rbtree/src/c-rbtree.c b/src/c-rbtree/src/c-rbtree.c index 28de4d952d..fbe7c85ba9 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 5c6fd0a559..2d9a1d20ba 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,54 +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. */ -/* - * 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(...))`. - */ -#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. @@ -172,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 @@ -181,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. */ @@ -192,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)) { @@ -208,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. * @@ -232,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. @@ -286,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. */ @@ -306,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. @@ -352,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); \ diff --git a/src/c-rbtree/src/meson.build b/src/c-rbtree/src/meson.build index c5cce8102c..94612031ce 100644 --- a/src/c-rbtree/src/meson.build +++ b/src/c-rbtree/src/meson.build @@ -19,10 +19,9 @@ libcrbtree_both = both_libraries( ], dependencies: libcrbtree_deps, install: not meson.is_subproject(), - link_args: [ - '-Wl,--no-undefined', + link_args: dep_cstdaux.get_variable('version-scripts') == 'yes' ? [ '-Wl,--version-script=@0@'.format(libcrbtree_symfile), - ], + ] : [], link_depends: libcrbtree_symfile, soversion: 0, ) @@ -62,10 +61,10 @@ test('Generic Map', test_map) test_misc = executable('test-misc', ['test-misc.c'], dependencies: libcrbtree_dep) test('Miscellaneous', test_misc) -test_parallel = executable('test-parallel', ['test-parallel.c'], dependencies: libcrbtree_dep) if use_ptrace + test_parallel = executable('test-parallel', ['test-parallel.c'], dependencies: libcrbtree_dep) test('Lockless Parallel Readers', test_parallel) -endif -test_posix = executable('test-posix', ['test-posix.c'], dependencies: libcrbtree_dep) -test('Posix tsearch(3p) Comparison', test_posix) + test_posix = executable('test-posix', ['test-posix.c'], dependencies: libcrbtree_dep) + test('Posix tsearch(3p) Comparison', test_posix) +endif |