New upstream version 1.47.90 upstream/1.47.90

22 files changed, 1748 insertions, 0 deletions

diff --git a/src/c-rbtree/.editorconfig b/src/c-rbtree/.editorconfig
new file mode 100644
index 00000000..b10bb4f3
--- /dev/null
+++ b/src/c-rbtree/.editorconfig
@@ -0,0 +1,11 @@
+root = true
+
+[*]
+end_of_line = lf
+insert_final_newline = true
+trim_trailing_whitespace = true
+charset = utf-8
+
+[*.{c,h}]
+indent_style = space
+indent_size = 8
diff --git a/src/c-rbtree/.github/workflows/ci.yml b/src/c-rbtree/.github/workflows/ci.yml
new file mode 100644
index 00000000..489433c2
--- /dev/null
+++ b/src/c-rbtree/.github/workflows/ci.yml
@@ -0,0 +1,41 @@
+name: Continuous Integration
+
+on:
+  push:
+  pull_request:
+  schedule:
+  - cron:  '0 0 * * *'
+
+jobs:
+  ci-linux:
+    name: Linux CI
+    uses: bus1/cabuild/.github/workflows/ci-c-util.yml@v1
+    with:
+      cabuild_ref: "v1"
+      linux: true
+      m32: true
+      matrixmode: true
+      valgrind: true
+
+  ci-linux-ptrace:
+    name: Linux CI with PTrace
+    uses: bus1/cabuild/.github/workflows/ci-c-util.yml@v1
+    with:
+      cabuild_ref: "v1"
+      linux: true
+      mesonargs: '-Dptrace=true'
+
+  ci-macos:
+    name: MacOS CI
+    uses: bus1/cabuild/.github/workflows/ci-c-util.yml@v1
+    with:
+      cabuild_ref: "v1"
+      linux: false
+      macos: true
+
+  ci-docs:
+    name: Documentation CI
+    uses: bus1/cabuild/.github/workflows/ci-sphinx.yml@v1
+    with:
+      meson: true
+      source: "./src/docs"
diff --git a/src/c-rbtree/.gitmodules b/src/c-rbtree/.gitmodules
new file mode 100644
index 00000000..e69de29b
--- /dev/null
+++ b/src/c-rbtree/.gitmodules
diff --git a/src/c-rbtree/.readthedocs.yaml b/src/c-rbtree/.readthedocs.yaml
new file mode 100644
index 00000000..fd02d297
--- /dev/null
+++ b/src/c-rbtree/.readthedocs.yaml
@@ -0,0 +1,23 @@
+# Read the Docs configuration file
+
+version: 2
+
+build:
+  apt_packages:
+  - "clang"
+  jobs:
+    pre_build:
+    - meson subprojects download
+  os: "ubuntu-22.04"
+  tools:
+    python: "3"
+
+formats: "all"
+
+python:
+  install:
+  - requirements: "src/docs/requirements.txt"
+  system_packages: true
+
+sphinx:
+  configuration: "src/docs/conf.py"
diff --git a/src/c-rbtree/AUTHORS b/src/c-rbtree/AUTHORS
new file mode 100644
index 00000000..7e4f368d
--- /dev/null
+++ b/src/c-rbtree/AUTHORS
@@ -0,0 +1,40 @@
+LICENSE:
+        This project is dual-licensed under both the Apache License, Version
+        2.0, and the GNU Lesser General Public License, Version 2.1+.
+
+AUTHORS-ASL:
+        Licensed under the Apache License, Version 2.0 (the "License");
+        you may not use this file except in compliance with the License.
+        You may obtain a copy of the License at
+
+                http://www.apache.org/licenses/LICENSE-2.0
+
+        Unless required by applicable law or agreed to in writing, software
+        distributed under the License is distributed on an "AS IS" BASIS,
+        WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+        See the License for the specific language governing permissions and
+        limitations under the License.
+
+AUTHORS-LGPL:
+        This program is free software; you can redistribute it and/or modify it
+        under the terms of the GNU Lesser General Public License as published
+        by the Free Software Foundation; either version 2.1 of the License, or
+        (at your option) any later version.
+
+        This program is distributed in the hope that it will be useful, but
+        WITHOUT ANY WARRANTY; without even the implied warranty of
+        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+        Lesser General Public License for more details.
+
+        You should have received a copy of the GNU Lesser General Public License
+        along with this program; If not, see <http://www.gnu.org/licenses/>.
+
+COPYRIGHT: (ordered alphabetically)
+        Copyright (C) 2015-2022 Red Hat, Inc.
+
+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
new file mode 100644
index 00000000..71415f67
--- /dev/null
+++ b/src/c-rbtree/NEWS.md
@@ -0,0 +1,53 @@
+# c-rbtree - Intrusive Red-Black Tree Collection
+
+## CHANGES WITH 3.1.0:
+
+        * Add 'ptrace' build option to enable running tests using 'ptrace'
+          to verify extended execution properties. This option should not
+          be used in setups where 'ptrace' cannot be employed (like running
+          under gdb or valgrind). This option only affects the test-suite.
+
+        * meson-0.60.0 is now the minimum required meson version.
+
+        Contributions from: David Rheinsberg, Evgeny Vereshchagin
+
+        - Brno, 2022-06-22
+
+## CHANGES WITH 3:
+
+        * Add more helpers. Add both a collection of iteratiors and helpers
+          for initializing a tree and checking if a tree is empty, without
+          explicitly accessing the data structure.
+
+        Contributions from: David Herrmann
+
+        - Berlin, 2017-08-13
+
+## CHANGES WITH 2:
+
+        * Relicense as ASL-2.0 to make c-rbtree useful for more projects. All
+          code is now fully available under the ASL-2.0. Nothing is covered by
+          the LGPL, anymore.
+
+        * Switch build-system from Autotools to Meson. This simplifies the code
+          base significantly. The Meson Build System is now used by many other
+          projects, including GStreamer, Weston, and several Gnome packages.
+          See http://mesonbuild.com/ for more information.
+
+        Contributions from: David Herrmann
+
+        - Berlin, 2016-12-14
+
+## CHANGES WITH 1:
+
+        * Initial release of c-rbtree.
+
+        * This projects 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.
+
+        Contributions from: David Herrmann, Kay Sievers, Tom Gundersen
+
+        - Berlin, 2016-08-31
diff --git a/src/c-rbtree/README.md b/src/c-rbtree/README.md
new file mode 100644
index 00000000..ff3e1cb7
--- /dev/null
+++ b/src/c-rbtree/README.md
@@ -0,0 +1,55 @@
+c-rbtree
+========
+
+Intrusive Red-Black Tree Collection
+
+The c-rbtree project implements an intrusive collection based on red-black
+trees in ISO-C11. Its API guarantees the user full control over its
+data-structures, and rather limits itself to just the tree-specific rebalancing
+and coloring operations. For API documentation, see the c-rbtree.h header file,
+as well as the docbook comments for each function.
+
+### Project
+
+ * **Website**: <https://c-util.github.io/c-rbtree>
+ * **Documentation**: <https://c-rbtree.readthedocs.io>
+ * **Bug Tracker**: <https://github.com/c-util/c-rbtree/issues>
+
+### Requirements
+
+The requirements for this project are:
+
+ * `libc` (e.g., `glibc >= 2.16`)
+
+At build-time, the following software is required:
+
+ * `meson >= 0.60`
+ * `pkg-config >= 0.29`
+
+### Build
+
+The meson build-system is used for this project. Contact upstream
+documentation for detailed help. In most situations the following
+commands are sufficient to build and install from source:
+
+```sh
+mkdir build
+cd build
+meson setup ..
+ninja
+meson test
+ninja install
+```
+
+No custom configuration options are available.
+
+### Repository:
+
+ - **web**:   <https://github.com/c-util/c-rbtree>
+ - **https**: `https://github.com/c-util/c-rbtree.git`
+ - **ssh**:   `git@github.com:c-util/c-rbtree.git`
+
+### License:
+
+ - **Apache-2.0** OR **LGPL-2.1-or-later**
+ - See AUTHORS file for details.
diff --git a/src/c-rbtree/meson.build b/src/c-rbtree/meson.build
new file mode 100644
index 00000000..3e7af9ce
--- /dev/null
+++ b/src/c-rbtree/meson.build
@@ -0,0 +1,22 @@
+project(
+        'c-rbtree',
+        'c',
+        default_options: [
+                'c_std=c11'
+        ],
+        license: 'Apache',
+        meson_version: '>=0.60.0',
+        version: '3.1.0',
+)
+major = meson.project_version().split('.')[0]
+project_description = 'Intrusive Red-Black Tree Collection'
+
+mod_pkgconfig = import('pkgconfig')
+use_ptrace = get_option('ptrace')
+
+dep_cstdaux = dependency('libcstdaux-1')
+add_project_arguments(dep_cstdaux.get_variable('cflags').split(' '), language: 'c')
+
+subdir('src')
+
+meson.override_dependency('libcrbtree-'+major, libcrbtree_dep, static: true)
diff --git a/src/c-rbtree/meson_options.txt b/src/c-rbtree/meson_options.txt
new file mode 100644
index 00000000..ec358180
--- /dev/null
+++ b/src/c-rbtree/meson_options.txt
@@ -0,0 +1 @@
+option('ptrace', type: 'boolean', value: false, description: 'Allow ptrace in test suite')
diff --git a/src/c-rbtree/src/docs/api.rst b/src/c-rbtree/src/docs/api.rst
new file mode 100644
index 00000000..fb41b9e8
--- /dev/null
+++ b/src/c-rbtree/src/docs/api.rst
@@ -0,0 +1,5 @@
+API
+===
+
+.. c:autodoc:: c-*.h c-*.c
+   :transform: kerneldoc
diff --git a/src/c-rbtree/src/docs/conf.py b/src/c-rbtree/src/docs/conf.py
new file mode 100644
index 00000000..f804486c
--- /dev/null
+++ b/src/c-rbtree/src/docs/conf.py
@@ -0,0 +1,45 @@
+#
+# Sphinx Documentation Configuration
+#
+
+import re
+import os
+import sys
+
+import capidocs.kerneldoc
+import hawkmoth
+
+# Global Setup
+
+project = 'c-rbtree'
+
+author = 'C-Util Community'
+copyright = '2015-2022, C-Util Community'
+
+# Hawkmoth C-Audodoc Setup
+
+capidocs.kerneldoc.hawkmoth_conf()
+
+# Extensions
+
+exclude_patterns = []
+
+extensions = [
+    'hawkmoth',
+]
+
+# Hawkmoth Options
+
+cautodoc_clang = capidocs.kerneldoc.hawkmoth_include_args()
+cautodoc_clang += ["-I" + os.path.abspath("..")]
+cautodoc_clang += capidocs.kerneldoc.hawkmoth_glob_includes("../../subprojects", "libc*/src")
+
+cautodoc_root = os.path.abspath('..')
+
+cautodoc_transformations = {
+    'kerneldoc': capidocs.kerneldoc.hawkmoth_converter,
+}
+
+# HTML Options
+
+html_theme = 'sphinx_rtd_theme'
diff --git a/src/c-rbtree/src/docs/index.rst b/src/c-rbtree/src/docs/index.rst
new file mode 100644
index 00000000..df281b0b
--- /dev/null
+++ b/src/c-rbtree/src/docs/index.rst
@@ -0,0 +1,15 @@
+Introduction
+============
+
+The **c-rbtree** project provides a Red-Black-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.
+
+.. toctree::
+   :caption: Library Documentation
+   :hidden:
+
+   self
+   api
diff --git a/src/c-rbtree/src/docs/requirements.txt b/src/c-rbtree/src/docs/requirements.txt
new file mode 100644
index 00000000..77973ebd
--- /dev/null
+++ b/src/c-rbtree/src/docs/requirements.txt
@@ -0,0 +1,5 @@
+c-apidocs>=0.0.3
+clang>=6
+hawkmoth>=0.7
+meson>=0.60
+ninja>=1.10
diff --git a/src/c-rbtree/src/libcrbtree.sym b/src/c-rbtree/src/libcrbtree.sym
new file mode 100644
index 00000000..e7b801b8
--- /dev/null
+++ b/src/c-rbtree/src/libcrbtree.sym
@@ -0,0 +1,21 @@
+LIBCRBTREE_3 {
+global:
+        c_rbnode_leftmost;
+        c_rbnode_rightmost;
+        c_rbnode_leftdeepest;
+        c_rbnode_rightdeepest;
+        c_rbnode_next;
+        c_rbnode_prev;
+        c_rbnode_next_postorder;
+        c_rbnode_prev_postorder;
+        c_rbnode_link;
+        c_rbnode_unlink_stale;
+        c_rbtree_first;
+        c_rbtree_last;
+        c_rbtree_first_postorder;
+        c_rbtree_last_postorder;
+        c_rbtree_add;
+        c_rbtree_move;
+local:
+       *;
+};
diff --git a/src/c-rbtree/src/meson.build b/src/c-rbtree/src/meson.build
new file mode 100644
index 00000000..94612031
--- /dev/null
+++ b/src/c-rbtree/src/meson.build
@@ -0,0 +1,70 @@
+#
+# target: libcrbtree.so
+#
+
+libcrbtree_symfile = join_paths(meson.current_source_dir(), 'libcrbtree.sym')
+
+libcrbtree_deps = [
+        dep_cstdaux,
+]
+
+libcrbtree_both = both_libraries(
+        'crbtree-'+major,
+        [
+                'c-rbtree.c',
+        ],
+        c_args: [
+                '-fvisibility=hidden',
+                '-fno-common',
+        ],
+        dependencies: libcrbtree_deps,
+        install: not meson.is_subproject(),
+        link_args: dep_cstdaux.get_variable('version-scripts') == 'yes' ? [
+                '-Wl,--version-script=@0@'.format(libcrbtree_symfile),
+        ] : [],
+        link_depends: libcrbtree_symfile,
+        soversion: 0,
+)
+
+libcrbtree_dep = declare_dependency(
+        dependencies: libcrbtree_deps,
+        include_directories: include_directories('.'),
+        link_with: libcrbtree_both.get_static_lib(),
+        version: meson.project_version(),
+)
+
+if not meson.is_subproject()
+        install_headers('c-rbtree.h')
+
+        mod_pkgconfig.generate(
+                description: project_description,
+                filebase: 'libcrbtree-'+major,
+                libraries: libcrbtree_both.get_shared_lib(),
+                name: 'libcrbtree',
+                version: meson.project_version(),
+        )
+endif
+
+#
+# target: test-*
+#
+
+test_api = executable('test-api', ['test-api.c'], link_with: libcrbtree_both.get_shared_lib())
+test('API Symbol Visibility', test_api)
+
+test_basic = executable('test-basic', ['test-basic.c'], dependencies: libcrbtree_dep)
+test('Basic API Behavior', test_basic)
+
+test_map = executable('test-map', ['test-map.c'], dependencies: libcrbtree_dep)
+test('Generic Map', test_map)
+
+test_misc = executable('test-misc', ['test-misc.c'], dependencies: libcrbtree_dep)
+test('Miscellaneous', test_misc)
+
+if use_ptrace
+        test_parallel = executable('test-parallel', ['test-parallel.c'], dependencies: libcrbtree_dep)
+        test('Lockless Parallel Readers', test_parallel)
+
+        test_posix = executable('test-posix', ['test-posix.c'], dependencies: libcrbtree_dep)
+        test('Posix tsearch(3p) Comparison', test_posix)
+endif
diff --git a/src/c-rbtree/src/test-api.c b/src/c-rbtree/src/test-api.c
new file mode 100644
index 00000000..295f6b9b
--- /dev/null
+++ b/src/c-rbtree/src/test-api.c
@@ -0,0 +1,107 @@
+/*
+ * Tests for Public API
+ * This test, unlikely the others, is linked against the real, distributed,
+ * shared library. Its sole purpose is to test for symbol availability.
+ */
+
+#undef NDEBUG
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "c-rbtree.h"
+
+typedef struct TestNode {
+        CRBNode rb;
+} TestNode;
+
+static void test_api(void) {
+        CRBTree t = C_RBTREE_INIT, t2 = C_RBTREE_INIT;
+        CRBNode *i, *is, n = C_RBNODE_INIT(n), m = C_RBNODE_INIT(m);
+        TestNode *ie, *ies;
+
+        assert(c_rbtree_is_empty(&t));
+        assert(!c_rbnode_is_linked(&n));
+        assert(!c_rbnode_entry(NULL, TestNode, rb));
+
+        /* init, is_linked, add, link, {unlink{,_stale}} */
+
+        c_rbtree_add(&t, NULL, &t.root, &n);
+        assert(c_rbnode_is_linked(&n));
+
+        c_rbnode_link(&n, &n.left, &m);
+        assert(c_rbnode_is_linked(&m));
+
+        c_rbnode_unlink(&m);
+        assert(!c_rbnode_is_linked(&m));
+
+        c_rbtree_add(&t, NULL, &t.root, &n);
+        assert(c_rbnode_is_linked(&n));
+
+        c_rbnode_link(&n, &n.left, &m);
+        assert(c_rbnode_is_linked(&m));
+
+        c_rbnode_unlink_stale(&m);
+        assert(c_rbnode_is_linked(&m)); /* @m wasn't touched */
+
+        c_rbnode_init(&n);
+        assert(!c_rbnode_is_linked(&n));
+
+        c_rbnode_init(&m);
+        assert(!c_rbnode_is_linked(&m));
+
+        c_rbtree_init(&t);
+        assert(c_rbtree_is_empty(&t));
+
+        /* move */
+
+        c_rbtree_move(&t2, &t);
+
+        /* first, last, leftmost, rightmost, next, prev */
+
+        assert(!c_rbtree_first(&t));
+        assert(!c_rbtree_last(&t));
+        assert(&n == c_rbnode_leftmost(&n));
+        assert(&n == c_rbnode_rightmost(&n));
+        assert(!c_rbnode_next(&n));
+        assert(!c_rbnode_prev(&n));
+
+        /* postorder traversal */
+
+        assert(!c_rbtree_first_postorder(&t));
+        assert(!c_rbtree_last_postorder(&t));
+        assert(&n == c_rbnode_leftdeepest(&n));
+        assert(&n == c_rbnode_rightdeepest(&n));
+        assert(!c_rbnode_next_postorder(&n));
+        assert(!c_rbnode_prev_postorder(&n));
+
+        /* iterators */
+
+        c_rbtree_for_each(i, &t)
+                assert(!i);
+        c_rbtree_for_each_safe(i, is, &t)
+                assert(!i);
+        c_rbtree_for_each_entry(ie, &t, rb)
+                assert(!ie);
+        c_rbtree_for_each_entry_safe(ie, ies, &t, rb)
+                assert(!ie);
+
+        c_rbtree_for_each_postorder(i, &t)
+                assert(!i);
+        c_rbtree_for_each_safe_postorder(i, is, &t)
+                assert(!i);
+        c_rbtree_for_each_entry_postorder(ie, &t, rb)
+                assert(!ie);
+        c_rbtree_for_each_entry_safe_postorder(ie, ies, &t, rb)
+                assert(!ie);
+
+        c_rbtree_for_each_safe_postorder_unlink(i, is, &t)
+                assert(!i);
+        c_rbtree_for_each_entry_safe_postorder_unlink(ie, ies, &t, rb)
+                assert(!ie);
+}
+
+int main(int argc, char **argv) {
+        test_api();
+        return 0;
+}
diff --git a/src/c-rbtree/src/test-basic.c b/src/c-rbtree/src/test-basic.c
new file mode 100644
index 00000000..8fee6468
--- /dev/null
+++ b/src/c-rbtree/src/test-basic.c
@@ -0,0 +1,239 @@
+/*
+ * Tests for Basic Tree Operations
+ * This test does some basic tree operations and verifies their correctness. It
+ * validates the RB-Tree invariants after each operation, to guarantee the
+ * stability of the tree.
+ *
+ * For testing purposes, we use the memory address of a node as its key, and
+ * order nodes in ascending order.
+ */
+
+#undef NDEBUG
+#include <assert.h>
+#include <c-stdaux.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include "c-rbtree.h"
+#include "c-rbtree-private.h"
+
+static size_t validate(CRBTree *t) {
+        unsigned int i_black, n_black;
+        CRBNode *n, *p, *o;
+        size_t count = 0;
+
+        c_assert(t);
+        c_assert(!t->root || c_rbnode_is_black(t->root));
+
+        /* traverse to left-most child, count black nodes */
+        i_black = 0;
+        n = t->root;
+        while (n && n->left) {
+                if (c_rbnode_is_black(n))
+                        ++i_black;
+                n = n->left;
+        }
+        n_black = i_black;
+
+        /*
+         * Traverse tree and verify correctness:
+         *  1) A node is either red or black
+         *  2) The root is black
+         *  3) All leaves are black
+         *  4) Every red node must have two black child nodes
+         *  5) Every path to a leaf contains the same number of black nodes
+         *
+         * Note that NULL nodes are considered black, which is why we don't
+         * check for 3).
+         */
+        o = NULL;
+        while (n) {
+                ++count;
+
+                /* verify natural order */
+                c_assert(n > o);
+                o = n;
+
+                /* verify consistency */
+                c_assert(!n->right || c_rbnode_parent(n->right) == n);
+                c_assert(!n->left || c_rbnode_parent(n->left) == n);
+
+                /* verify 2) */
+                if (!c_rbnode_parent(n))
+                        c_assert(c_rbnode_is_black(n));
+
+                if (c_rbnode_is_red(n)) {
+                        /* verify 4) */
+                        c_assert(!n->left || c_rbnode_is_black(n->left));
+                        c_assert(!n->right || c_rbnode_is_black(n->right));
+                } else {
+                        /* verify 1) */
+                        c_assert(c_rbnode_is_black(n));
+                }
+
+                /* verify 5) */
+                if (!n->left && !n->right)
+                        c_assert(i_black == n_black);
+
+                /* get next node */
+                if (n->right) {
+                        n = n->right;
+                        if (c_rbnode_is_black(n))
+                                ++i_black;
+
+                        while (n->left) {
+                                n = n->left;
+                                if (c_rbnode_is_black(n))
+                                        ++i_black;
+                        }
+                } else {
+                        while ((p = c_rbnode_parent(n)) && n == p->right) {
+                                n = p;
+                                if (c_rbnode_is_black(p->right))
+                                        --i_black;
+                        }
+
+                        n = p;
+                        if (p && c_rbnode_is_black(p->left))
+                                --i_black;
+                }
+        }
+
+        return count;
+}
+
+static void insert(CRBTree *t, CRBNode *n) {
+        CRBNode **i, *p;
+
+        c_assert(t);
+        c_assert(n);
+        c_assert(!c_rbnode_is_linked(n));
+
+        i = &t->root;
+        p = NULL;
+        while (*i) {
+                p = *i;
+                if (n < *i) {
+                        i = &(*i)->left;
+                } else {
+                        c_assert(n > *i);
+                        i = &(*i)->right;
+                }
+        }
+
+        c_rbtree_add(t, p, i, n);
+}
+
+static void shuffle(CRBNode **nodes, size_t n_memb) {
+        unsigned int i, j;
+        CRBNode *t;
+
+        for (i = 0; i < n_memb; ++i) {
+                j = rand() % n_memb;
+                t = nodes[j];
+                nodes[j] = nodes[i];
+                nodes[i] = t;
+        }
+}
+
+static void test_shuffle(void) {
+        CRBNode *nodes[512];
+        CRBTree t = {};
+        unsigned int i, j;
+        size_t n;
+
+        /* allocate and initialize all nodes */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                nodes[i] = malloc(sizeof(*nodes[i]));
+                c_assert(nodes[i]);
+                c_rbnode_init(nodes[i]);
+        }
+
+        /* shuffle nodes and validate *empty* tree */
+        shuffle(nodes, sizeof(nodes) / sizeof(*nodes));
+        n = validate(&t);
+        c_assert(n == 0);
+
+        /* add all nodes and validate after each insertion */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                insert(&t, nodes[i]);
+                n = validate(&t);
+                c_assert(n == i + 1);
+        }
+
+        /* shuffle nodes again */
+        shuffle(nodes, sizeof(nodes) / sizeof(*nodes));
+
+        /* remove all nodes (in different order) and validate on each round */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                c_rbnode_unlink(nodes[i]);
+                n = validate(&t);
+                c_assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
+        }
+
+        /* shuffle nodes and validate *empty* tree again */
+        shuffle(nodes, sizeof(nodes) / sizeof(*nodes));
+        n = validate(&t);
+        c_assert(n == 0);
+
+        /* add all nodes again */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                insert(&t, nodes[i]);
+                n = validate(&t);
+                c_assert(n == i + 1);
+        }
+
+        /* 4 times, remove half of the nodes and add them again */
+        for (j = 0; j < 4; ++j) {
+                /* shuffle nodes again */
+                shuffle(nodes, sizeof(nodes) / sizeof(*nodes));
+
+                /* remove half of the nodes */
+                for (i = 0; i < sizeof(nodes) / sizeof(*nodes) / 2; ++i) {
+                        c_rbnode_unlink(nodes[i]);
+                        n = validate(&t);
+                        c_assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
+                }
+
+                /* shuffle the removed half */
+                shuffle(nodes, sizeof(nodes) / sizeof(*nodes) / 2);
+
+                /* add the removed half again */
+                for (i = 0; i < sizeof(nodes) / sizeof(*nodes) / 2; ++i) {
+                        insert(&t, nodes[i]);
+                        n = validate(&t);
+                        c_assert(n == sizeof(nodes) / sizeof(*nodes) / 2 + i + 1);
+                }
+        }
+
+        /* shuffle nodes again */
+        shuffle(nodes, sizeof(nodes) / sizeof(*nodes));
+
+        /* remove all */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                c_rbnode_unlink(nodes[i]);
+                n = validate(&t);
+                c_assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
+        }
+
+        /* free nodes again */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
+                free(nodes[i]);
+}
+
+int main(int argc, char **argv) {
+        unsigned int i;
+
+        /* we want stable tests, so use fixed seed */
+        srand(0xdeadbeef);
+
+        /*
+         * The tests are pseudo random; run them multiple times, each run will
+         * have different orders and thus different results.
+         */
+        for (i = 0; i < 4; ++i)
+                test_shuffle();
+
+        return 0;
+}
diff --git a/src/c-rbtree/src/test-map.c b/src/c-rbtree/src/test-map.c
new file mode 100644
index 00000000..48a300d6
--- /dev/null
+++ b/src/c-rbtree/src/test-map.c
@@ -0,0 +1,277 @@
+/*
+ * RB-Tree based Map
+ * This implements a basic Map between integer keys and objects. It uses the
+ * lookup and insertion helpers, rather than open-coding it.
+ */
+
+#undef NDEBUG
+#include <assert.h>
+#include <c-stdaux.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include "c-rbtree.h"
+#include "c-rbtree-private.h"
+
+typedef struct {
+        unsigned long key;
+        unsigned int marker;
+        CRBNode rb;
+} Node;
+
+#define node_from_rb(_rb) ((Node *)((char *)(_rb) - offsetof(Node, rb)))
+
+static int test_compare(CRBTree *t, void *k, CRBNode *n) {
+        unsigned long key = (unsigned long)k;
+        Node *node = node_from_rb(n);
+
+        return (key < node->key) ? -1 : (key > node->key) ? 1 : 0;
+}
+
+static void shuffle(Node **nodes, size_t n_memb) {
+        unsigned int i, j;
+        Node *t;
+
+        for (i = 0; i < n_memb; ++i) {
+                j = rand() % n_memb;
+                t = nodes[j];
+                nodes[j] = nodes[i];
+                nodes[i] = t;
+        }
+}
+
+static void test_map(void) {
+        CRBNode **slot, *p, *safe_p;
+        CRBTree t = {};
+        Node *n, *safe_n, *nodes[2048];
+        unsigned long i, v;
+
+        /* allocate and initialize all nodes */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                nodes[i] = malloc(sizeof(*nodes[i]));
+                c_assert(nodes[i]);
+                nodes[i]->key = i;
+                nodes[i]->marker = 0;
+                c_rbnode_init(&nodes[i]->rb);
+        }
+
+        /* shuffle nodes */
+        shuffle(nodes, sizeof(nodes) / sizeof(*nodes));
+
+        /* add all nodes, and verify that each node is linked */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                c_assert(!c_rbnode_is_linked(&nodes[i]->rb));
+                c_assert(!c_rbtree_find_entry(&t, test_compare, (void *)nodes[i]->key, Node, rb));
+
+                slot = c_rbtree_find_slot(&t, test_compare, (void *)nodes[i]->key, &p);
+                c_assert(slot);
+                c_rbtree_add(&t, p, slot, &nodes[i]->rb);
+
+                c_assert(c_rbnode_is_linked(&nodes[i]->rb));
+                c_assert(nodes[i] == c_rbtree_find_entry(&t, test_compare, (void *)nodes[i]->key, Node, rb));
+        }
+
+        /* verify in-order traversal works */
+        i = 0;
+        v = 0;
+        for (p = c_rbtree_first(&t); p; p = c_rbnode_next(p)) {
+                ++i;
+                c_assert(!node_from_rb(p)->marker);
+                node_from_rb(p)->marker = 1;
+
+                c_assert(v <= node_from_rb(p)->key);
+                v = node_from_rb(p)->key;
+
+                c_assert(!c_rbnode_next(p) || p == c_rbnode_prev(c_rbnode_next(p)));
+        }
+        c_assert(i == sizeof(nodes) / sizeof(*nodes));
+
+        /* verify reverse in-order traversal works */
+        i = 0;
+        v = -1;
+        for (p = c_rbtree_last(&t); p; p = c_rbnode_prev(p)) {
+                ++i;
+                c_assert(node_from_rb(p)->marker);
+                node_from_rb(p)->marker = 0;
+
+                c_assert(v >= node_from_rb(p)->key);
+                v = node_from_rb(p)->key;
+        }
+        c_assert(i == sizeof(nodes) / sizeof(*nodes));
+
+        /* verify post-order traversal works */
+        i = 0;
+        for (p = c_rbtree_first_postorder(&t); p; p = c_rbnode_next_postorder(p)) {
+                ++i;
+                c_assert(!node_from_rb(p)->marker);
+                c_assert(!c_rbnode_parent(p) || !node_from_rb(c_rbnode_parent(p))->marker);
+                c_assert(!p->left || node_from_rb(p->left)->marker);
+                c_assert(!p->right || node_from_rb(p->right)->marker);
+                node_from_rb(p)->marker = 1;
+
+                c_assert(!c_rbnode_next_postorder(p) || p == c_rbnode_prev_postorder(c_rbnode_next_postorder(p)));
+        }
+        c_assert(i == sizeof(nodes) / sizeof(*nodes));
+
+        /* verify pre-order (inverse post-order) traversal works */
+        i = 0;
+        for (p = c_rbtree_last_postorder(&t); p; p = c_rbnode_prev_postorder(p)) {
+                ++i;
+                c_assert(node_from_rb(p)->marker);
+                c_assert(!c_rbnode_parent(p) || !node_from_rb(c_rbnode_parent(p))->marker);
+                c_assert(!p->left || node_from_rb(p->left)->marker);
+                c_assert(!p->right || node_from_rb(p->right)->marker);
+                node_from_rb(p)->marker = 0;
+        }
+        c_assert(i == sizeof(nodes) / sizeof(*nodes));
+
+        /* verify in-order traversal works via helper */
+        i = 0;
+        v = 0;
+        c_rbtree_for_each(p, &t) {
+                ++i;
+                c_assert(!node_from_rb(p)->marker);
+                node_from_rb(p)->marker = 1;
+
+                c_assert(v <= node_from_rb(p)->key);
+                v = node_from_rb(p)->key;
+
+                c_assert(!c_rbnode_next(p) || p == c_rbnode_prev(c_rbnode_next(p)));
+        }
+        c_assert(i == sizeof(nodes) / sizeof(*nodes));
+
+        /* verify in-order traversal works via entry-helper */
+        i = 0;
+        v = 0;
+        c_rbtree_for_each_entry(n, &t, rb) {
+                ++i;
+                c_assert(n->marker);
+                n->marker = 0;
+
+                c_assert(v <= n->key);
+                v = n->key;
+        }
+        c_assert(i == sizeof(nodes) / sizeof(*nodes));
+
+        /* verify post-order traversal works via helper */
+        i = 0;
+        c_rbtree_for_each_postorder(p, &t) {
+                ++i;
+                c_assert(!node_from_rb(p)->marker);
+                c_assert(!c_rbnode_parent(p) || !node_from_rb(c_rbnode_parent(p))->marker);
+                c_assert(!p->left || node_from_rb(p->left)->marker);
+                c_assert(!p->right || node_from_rb(p->right)->marker);
+                node_from_rb(p)->marker = 1;
+
+                c_assert(!c_rbnode_next_postorder(p) || p == c_rbnode_prev_postorder(c_rbnode_next_postorder(p)));
+        }
+        c_assert(i == sizeof(nodes) / sizeof(*nodes));
+
+        /* verify post-order traversal works via entry-helper */
+        i = 0;
+        c_rbtree_for_each_entry_postorder(n, &t, rb) {
+                ++i;
+                c_assert(n->marker);
+                c_assert(!c_rbnode_parent(&n->rb) || node_from_rb(c_rbnode_parent(&n->rb))->marker);
+                c_assert(!n->rb.left || !node_from_rb(n->rb.left)->marker);
+                c_assert(!n->rb.right || !node_from_rb(n->rb.right)->marker);
+                n->marker = 0;
+        }
+        c_assert(i == sizeof(nodes) / sizeof(*nodes));
+
+        /* shuffle nodes again */
+        shuffle(nodes, sizeof(nodes) / sizeof(*nodes));
+
+        /* remove all nodes (in different order) */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                c_assert(c_rbnode_is_linked(&nodes[i]->rb));
+                c_assert(nodes[i] == c_rbtree_find_entry(&t, test_compare, (void *)nodes[i]->key, Node, rb));
+
+                c_rbnode_unlink(&nodes[i]->rb);
+
+                c_assert(!c_rbnode_is_linked(&nodes[i]->rb));
+                c_assert(!c_rbtree_find_entry(&t, test_compare, (void *)nodes[i]->key, Node, rb));
+        }
+        c_assert(c_rbtree_is_empty(&t));
+
+        /* add all nodes again */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                slot = c_rbtree_find_slot(&t, test_compare, (void *)nodes[i]->key, &p);
+                c_assert(slot);
+                c_rbtree_add(&t, p, slot, &nodes[i]->rb);
+        }
+
+        /* remove all nodes via helper */
+        i = 0;
+        c_rbtree_for_each_safe(p, safe_p, &t) {
+                ++i;
+                c_rbnode_unlink(p);
+        }
+        c_assert(i == sizeof(nodes) / sizeof(*nodes));
+        c_assert(c_rbtree_is_empty(&t));
+
+        /* add all nodes again */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                slot = c_rbtree_find_slot(&t, test_compare, (void *)nodes[i]->key, &p);
+                c_assert(slot);
+                c_rbtree_add(&t, p, slot, &nodes[i]->rb);
+        }
+
+        /* remove all nodes via entry-helper */
+        i = 0;
+        c_rbtree_for_each_entry_safe(n, safe_n, &t, rb) {
+                ++i;
+                c_rbnode_unlink(&n->rb);
+        }
+        c_assert(i == sizeof(nodes) / sizeof(*nodes));
+        c_assert(c_rbtree_is_empty(&t));
+
+        /* add all nodes again */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                slot = c_rbtree_find_slot(&t, test_compare, (void *)nodes[i]->key, &p);
+                c_assert(slot);
+                c_rbtree_add(&t, p, slot, &nodes[i]->rb);
+        }
+
+        /* remove all nodes via unlink-helper */
+        i = 0;
+        c_rbtree_for_each_safe_postorder_unlink(p, safe_p, &t) {
+                ++i;
+                c_assert(!c_rbnode_is_linked(p));
+        }
+        c_assert(i == sizeof(nodes) / sizeof(*nodes));
+        c_assert(c_rbtree_is_empty(&t));
+
+        /* add all nodes again */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                slot = c_rbtree_find_slot(&t, test_compare, (void *)nodes[i]->key, &p);
+                c_assert(slot);
+                c_rbtree_add(&t, p, slot, &nodes[i]->rb);
+        }
+
+        /* remove all nodes via entry-unlink-helper */
+        i = 0;
+        c_rbtree_for_each_entry_safe_postorder_unlink(n, safe_n, &t, rb) {
+                ++i;
+                c_assert(!c_rbnode_is_linked(&n->rb));
+        }
+        c_assert(i == sizeof(nodes) / sizeof(*nodes));
+        c_assert(c_rbtree_is_empty(&t));
+
+        /* free nodes again */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                c_assert(!nodes[i]->marker);
+                free(nodes[i]);
+        }
+
+        c_assert(c_rbtree_is_empty(&t));
+}
+
+int main(int argc, char **argv) {
+        /* we want stable tests, so use fixed seed */
+        srand(0xdeadbeef);
+
+        test_map();
+        return 0;
+}
diff --git a/src/c-rbtree/src/test-misc.c b/src/c-rbtree/src/test-misc.c
new file mode 100644
index 00000000..ac2717cd
--- /dev/null
+++ b/src/c-rbtree/src/test-misc.c
@@ -0,0 +1,66 @@
+/*
+ * Tests for Miscellaneous Tree Operations
+ * This test contains all of the minor tests that did not fit anywhere else.
+ */
+
+#undef NDEBUG
+#include <assert.h>
+#include <c-stdaux.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "c-rbtree.h"
+#include "c-rbtree-private.h"
+
+static void insert(CRBTree *t, CRBNode *n) {
+        CRBNode **i, *p;
+
+        c_assert(t);
+        c_assert(n);
+        c_assert(!c_rbnode_is_linked(n));
+
+        i = &t->root;
+        p = NULL;
+        while (*i) {
+                p = *i;
+                if (n < *i) {
+                        i = &(*i)->left;
+                } else {
+                        c_assert(n > *i);
+                        i = &(*i)->right;
+                }
+        }
+
+        c_rbtree_add(t, p, i, n);
+}
+
+static void test_move(void) {
+        CRBTree t1 = C_RBTREE_INIT, t2 = C_RBTREE_INIT;
+        CRBNode n[128];
+        unsigned int i;
+
+        for (i = 0; i < sizeof(n) / sizeof(*n); ++i) {
+                n[i] = (CRBNode)C_RBNODE_INIT(n[i]);
+                insert(&t1, &n[i]);
+        }
+
+        c_assert(!c_rbtree_is_empty(&t1));
+        c_assert(c_rbtree_is_empty(&t2));
+
+        c_rbtree_move(&t2, &t1);
+
+        c_assert(c_rbtree_is_empty(&t1));
+        c_assert(!c_rbtree_is_empty(&t2));
+
+        while (t2.root)
+                c_rbnode_unlink(t2.root);
+
+        c_assert(c_rbtree_is_empty(&t1));
+        c_assert(c_rbtree_is_empty(&t2));
+}
+
+int main(int argc, char **argv) {
+        test_move();
+
+        return 0;
+}
diff --git a/src/c-rbtree/src/test-parallel.c b/src/c-rbtree/src/test-parallel.c
new file mode 100644
index 00000000..4baf8e70
--- /dev/null
+++ b/src/c-rbtree/src/test-parallel.c
@@ -0,0 +1,381 @@
+/*
+ * Tests Lockless Tree Lookups
+ * The RB-Tree implementation supports lockless tree lookups on shared
+ * data-structures. While it does not guarantee correct results (you might skip
+ * entire sub-trees), it does guarantee valid behavior (the traversal is
+ * guaranteed to end and produce some valid result).
+ * This test uses ptrace to run tree operations step-by-step in a separate
+ * process, and after each instruction verify the pseudo-validity of the tree.
+ * This means, a tree must only have valid left/right pointers (or NULL), and
+ * must not contain any loops in those pointers.
+ *
+ * This test runs two processes with a shared context and tree. It runs them in
+ * this order:
+ *
+ *         | PARENT             | CHILD     |
+ *         +--------------------+-----------+
+ *         ~                    ~           ~
+ *          test_parent_start
+ *                               test_child1
+ *          test_parent_middle
+ *                               test_child2
+ *          test_parent_end
+ *         ~                    ~           ~
+ *         +--------------------+-----------+
+ *
+ * Additionally, on each TRAP of CHILD, the parent runs test_parent_step(). The
+ * ptrace infrastructure generates a TRAP after each instruction, so this test
+ * is very CPU aggressive in the parent.
+ */
+
+#undef NDEBUG
+#include <assert.h>
+#include <c-stdaux.h>
+#include <errno.h>
+#include <inttypes.h>
+#include <sched.h>
+#include <signal.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/mman.h>
+#include <sys/ptrace.h>
+#include <sys/resource.h>
+#include <sys/types.h>
+#include <sys/wait.h>
+#include <sys/syscall.h>
+#include <time.h>
+#include <unistd.h>
+#include "c-rbtree.h"
+#include "c-rbtree-private.h"
+
+typedef struct {
+        CRBNode rb;
+        bool visited;
+} TestNode;
+
+typedef struct {
+        size_t mapsize;
+        char *map;
+        CRBTree *tree;
+        TestNode *node_mem;
+        CRBNode **nodes;
+        CRBNode **cache;
+        size_t n_nodes;
+} TestContext;
+
+/* avoid ptrace-sigstop by using SIGKILL errors in traced children */
+#define child_assert(_expr) ((void)(!!(_expr) ? 1 : (raise(SIGKILL), 0)))
+
+static int compare(CRBTree *t, void *k, CRBNode *n) {
+        return (char *)n - (char *)k;
+}
+
+static void shuffle(CRBNode **nodes, size_t n_memb) {
+        unsigned int i, j;
+        CRBNode *t;
+
+        for (i = 0; i < n_memb; ++i) {
+                j = rand() % n_memb;
+                t = nodes[j];
+                nodes[j] = nodes[i];
+                nodes[i] = t;
+        }
+}
+
+static void toggle_visit(CRBNode *n, bool set) {
+        c_rbnode_entry(n, TestNode, rb)->visited = set;
+}
+
+static bool fetch_visit(CRBNode *n) {
+        return c_rbnode_entry(n, TestNode, rb)->visited;
+}
+
+static void test_child1(TestContext *ctx) {
+        CRBNode *p, **slot;
+        size_t i;
+
+        for (i = 0; i < ctx->n_nodes; ++i) {
+                child_assert(!c_rbnode_is_linked(ctx->nodes[i]));
+                slot = c_rbtree_find_slot(ctx->tree, compare, ctx->nodes[i], &p);
+                c_rbtree_add(ctx->tree, p, slot, ctx->nodes[i]);
+        }
+}
+
+static void test_child2(TestContext *ctx) {
+        size_t i;
+
+        for (i = 0; i < ctx->n_nodes; ++i) {
+                child_assert(c_rbnode_is_linked(ctx->nodes[i]));
+                c_rbnode_unlink(ctx->nodes[i]);
+        }
+}
+
+static void test_parent_start(TestContext *ctx) {
+        size_t i;
+
+        /*
+         * Generate a tree with @n_nodes entries. We store the entries in
+         * @ctx->node_mem, generate a randomized access-map in @ctx->nodes
+         * (i.e., an array of pointers to entries in @ctx->node_mem, but in
+         * random order), and a temporary cache for free use in the parent.
+         *
+         * All this is stored in a MAP_SHARED memory region so it is equivalent
+         * in child and parent.
+         */
+
+        ctx->n_nodes = 32;
+        ctx->mapsize = sizeof(CRBTree);
+        ctx->mapsize += ctx->n_nodes * sizeof(TestNode);
+        ctx->mapsize += ctx->n_nodes * sizeof(CRBNode*);
+        ctx->mapsize += ctx->n_nodes * sizeof(CRBNode*);
+
+        ctx->map = mmap(NULL, ctx->mapsize, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANON, -1, 0);
+        c_assert(ctx->map != MAP_FAILED);
+
+        ctx->tree = (void *)ctx->map;
+        ctx->node_mem = (void *)(ctx->tree + 1);
+        ctx->nodes = (void *)(ctx->node_mem + ctx->n_nodes);
+        ctx->cache = (void *)(ctx->nodes + ctx->n_nodes);
+
+        for (i = 0; i < ctx->n_nodes; ++i) {
+                ctx->nodes[i] = &ctx->node_mem[i].rb;
+                c_rbnode_init(ctx->nodes[i]);
+        }
+
+        shuffle(ctx->nodes, ctx->n_nodes);
+}
+
+static void test_parent_middle(TestContext *ctx) {
+        size_t i;
+
+        shuffle(ctx->nodes, ctx->n_nodes);
+
+        for (i = 0; i < ctx->n_nodes; ++i)
+                child_assert(c_rbnode_is_linked(ctx->nodes[i]));
+}
+
+static void test_parent_end(TestContext *ctx) {
+        size_t i;
+        int r;
+
+        for (i = 0; i < ctx->n_nodes; ++i)
+                c_assert(!c_rbnode_is_linked(ctx->nodes[i]));
+
+        r = munmap(ctx->map, ctx->mapsize);
+        c_assert(r >= 0);
+}
+
+static void test_parent_step(TestContext *ctx) {
+        size_t i, i_level;
+        CRBNode *n, *p;
+
+        n = ctx->tree->root;
+        i_level = 0;
+
+        while (n) {
+                /* verify that we haven't visited @n, yet */
+                c_assert(!fetch_visit(n));
+
+                /* verify @n is a valid node */
+                for (i = 0; i < ctx->n_nodes; ++i)
+                        if (n == ctx->nodes[i])
+                                break;
+                c_assert(i < ctx->n_nodes);
+
+                /* pre-order traversal and marker for cycle detection */
+                if (n->left) {
+                        toggle_visit(n, true);
+                        ctx->cache[i_level++] = n;
+                        n = n->left;
+                } else if (n->right) {
+                        toggle_visit(n, true);
+                        ctx->cache[i_level++] = n;
+                        n = n->right;
+                } else {
+                        while (i_level > 0) {
+                                p = ctx->cache[i_level - 1];
+                                if (p->right && n != p->right) {
+                                        n = p->right;
+                                        break;
+                                }
+                                --i_level;
+                                n = p;
+                                toggle_visit(n, false);
+                        }
+                        if (i_level == 0)
+                                break;
+                }
+        }
+}
+
+static int test_parallel_child(TestContext *ctx) {
+        int r;
+
+        /*
+         * Make parent trace us and enter stopped state. In case of EPERM, we
+         * are either ptraced already, or are not privileged to run ptrace.
+         * Exit via 0xdf to signal this condition to our parent.
+         */
+        r = ptrace(PTRACE_TRACEME, 0, 0, 0);
+        if (r < 0 && errno == EPERM)
+                return 0xdf;
+
+        child_assert(r >= 0);
+
+        /* SIGUSR1 to signal readiness */
+        r = raise(SIGUSR1);
+        child_assert(r >= 0);
+
+        /* run first part */
+        test_child1(ctx);
+
+        /* SIGURG to cause re-shuffle */
+        r = raise(SIGURG);
+        child_assert(r >= 0);
+
+        /* run second part */
+        test_child2(ctx);
+
+        /* SIGUSR2 to signal end */
+        r = raise(SIGUSR2);
+        child_assert(r >= 0);
+
+        /* return known exit code to parent */
+        return 0xef;
+}
+
+static int test_parallel(void) {
+        TestContext ctx = {};
+        int r, pid, status;
+        uint64_t n_instr, n_event;
+
+        /* create shared area for tree verification */
+        test_parent_start(&ctx);
+
+        /* run child */
+        pid = fork();
+        c_assert(pid >= 0);
+        if (pid == 0) {
+                r = test_parallel_child(&ctx);
+                _exit(r);
+        }
+
+        /*
+         * After setup, the child immediately enters TRACE-operation and raises
+         * SIGUSR1. Once continued, the child performs the pre-configured tree
+         * operations. When done, it raises SIGUSR2, and then exits.
+         *
+         * Here in the parent we catch all trace-stops of the child via waitpid
+         * until we get no more such stop-events. Based on the stop-event we
+         * get, we verify child-state, STEP it, or perform other state tracking.
+         * We repeat this as long as we catch trace-stops from the child.
+         */
+        n_instr = 0;
+        n_event = 0;
+        for (r = waitpid(pid, &status, 0);
+             r == pid && WIFSTOPPED(status);
+             r = waitpid(pid, &status, 0)) {
+
+                switch (WSTOPSIG(status)) {
+                case SIGUSR1:
+                        n_event |= 0x1;
+
+                        /* step child */
+                        r = ptrace(PTRACE_SINGLESTEP, pid, 0, 0);
+
+                        /*
+                         * Some architectures (e.g., armv7hl) do not implement
+                         * SINGLESTEP, but return EIO. Skip the entire test in
+                         * this case.
+                         */
+                        if (r < 0 && errno == EIO)
+                                return 77;
+
+                        c_assert(r >= 0);
+                        break;
+
+                case SIGURG:
+                        n_event |= 0x2;
+                        test_parent_middle(&ctx);
+
+                        /* step child */
+                        r = ptrace(PTRACE_SINGLESTEP, pid, 0, 0);
+                        c_assert(r >= 0);
+                        break;
+
+                case SIGUSR2:
+                        n_event |= 0x4;
+                        test_parent_end(&ctx);
+
+                        /* continue child */
+                        r = ptrace(PTRACE_CONT, pid, 0, 0);
+                        c_assert(r >= 0);
+                        break;
+
+                case SIGTRAP:
+                        ++n_instr;
+                        test_parent_step(&ctx);
+
+                        /* step repeatedly as long as we get SIGTRAP */
+                        r = ptrace(PTRACE_SINGLESTEP, pid, 0, 0);
+                        c_assert(r >= 0);
+                        break;
+
+                default:
+                        c_assert(0);
+                        break;
+                }
+        }
+
+        /* verify our child exited cleanly */
+        c_assert(r == pid);
+        c_assert(!!WIFEXITED(status));
+
+        /*
+         * 0xdf is signalled if ptrace is not allowed or we are already
+         * ptraced. In this case we skip the test.
+         *
+         * 0xef is signalled on success.
+         *
+         * In any other case something went wobbly and we should fail hard.
+         */
+        switch (WEXITSTATUS(status)) {
+        case 0xef:
+                break;
+        case 0xdf:
+                return 77;
+        default:
+                c_assert(0);
+                break;
+        }
+
+        /* verify we hit all child states */
+        c_assert(n_event & 0x1);
+        c_assert(n_event & 0x2);
+        c_assert(n_event & 0x4);
+        c_assert(n_instr > 0);
+
+        return 0;
+}
+
+int main(int argc, char **argv) {
+        unsigned int i;
+        int r;
+
+        /* we want stable tests, so use fixed seed */
+        srand(0xdeadbeef);
+
+        /*
+         * The tests are pseudo random; run them multiple times, each run will
+         * have different orders and thus different results.
+         */
+        for (i = 0; i < 4; ++i) {
+                r = test_parallel();
+                if (r)
+                        return r;
+        }
+
+        return 0;
+}
diff --git a/src/c-rbtree/src/test-posix.c b/src/c-rbtree/src/test-posix.c
new file mode 100644
index 00000000..ee100ec5
--- /dev/null
+++ b/src/c-rbtree/src/test-posix.c
@@ -0,0 +1,270 @@
+/*
+ * Tests to compare against POSIX RB-Trees
+ * POSIX provides balanced binary trees via the tsearch(3p) API. glibc
+ * implements them as RB-Trees. This file compares the performance of both.
+ *
+ * The semantic differences are:
+ *
+ *   o The tsearch(3p) API does memory allocation of node structures itself,
+ *     rather than allowing the caller to embed it.
+ *
+ *   o The c-rbtree API exposes the tree structure, allowing efficient tree
+ *     operations. Furthermore, it allows tree creation/deletion without taking
+ *     the expensive insert/remove paths. For instance, imagine you want to
+ *     create an rb-tree from a set of objects you have. With c-rbtree you can
+ *     do that without a single rotation or tree-restructuring in O(n), while
+ *     tsearch(3p) requires O(n log n).
+ *
+ *   o The tsearch(3p) API requires one pointer-chase on each node access. This
+ *     is inherent to the design as it does not allow embedding the node in the
+ *     parent object. This slows down the API considerably.
+ *
+ *   o The tsearch(3p) API does not allow multiple entries with the same key.
+ *
+ *   o The tsearch(3p) API requires node lookup during removal. This does not
+ *     affect the worst-case runtime, but does reduce absolute performance.
+ *
+ *   o The tsearch(3p) API does not allow O(1) tests whether a node is linked
+ *     or not. It requires a separate state variable per node.
+ *
+ *   o The tsearch(3p) API does not allow walking the tree with context. The
+ *     only accessor twalk(3p) provides no tree context nor caller context to
+ *     the callback function.
+ *
+ *   o The glibc implementation of tsearch(3p) uses RB-Trees without parent
+ *     pointers. Hence, tree traversal requires back-tracking. Performance is
+ *     similar, but it reduces memory consumption (though, at the same time it
+ *     stores the key pointer, and allocates the node on the heap, so overall
+ *     the memory consumption is higher still).
+ *     But the more important issue is, a node itself is not enough context as
+ *     tree iterator, but the full depth parent pointers are needed as well.
+ */
+
+#undef NDEBUG
+#include <assert.h>
+#include <c-stdaux.h>
+#include <inttypes.h>
+#include <limits.h>
+#include <search.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include "c-rbtree.h"
+#include "c-rbtree-private.h"
+
+typedef struct {
+        int key;
+        CRBNode rb;
+} Node;
+
+#define node_from_rb(_rb) ((Node *)((char *)(_rb) - offsetof(Node, rb)))
+#define node_from_key(_key) ((Node *)((char *)(_key) - offsetof(Node, key)))
+
+static void shuffle(Node **nodes, size_t n_memb) {
+        unsigned int i, j;
+        Node *t;
+
+        for (i = 0; i < n_memb; ++i) {
+                j = rand() % n_memb;
+                t = nodes[j];
+                nodes[j] = nodes[i];
+                nodes[i] = t;
+        }
+}
+
+static int compare(CRBTree *t, void *k, CRBNode *n) {
+        int key = (int)(unsigned long)k;
+        Node *node = node_from_rb(n);
+
+        return key - node->key;
+}
+
+static uint64_t now(void) {
+        struct timespec ts;
+        int r;
+
+        r = clock_gettime(CLOCK_THREAD_CPUTIME_ID, &ts);
+        c_assert(r >= 0);
+        return ts.tv_sec * UINT64_C(1000000000) + ts.tv_nsec;
+}
+
+/*
+ * POSIX tsearch(3p) based RB-Tree API
+ *
+ * This implements a small rb-tree API alongside c-rbtree but based on
+ * tsearch(3p) and friends.
+ *
+ * Note that we don't care for OOM here, nor do we implement all the same
+ * features as c-rbtree. This just does basic insertion, removal, and lookup
+ * without any conflict detection.
+ *
+ * This also hard-codes 'Node' as object type that can be stored in the tree.
+ */
+
+typedef struct PosixRBTree PosixRBTree;
+
+struct PosixRBTree {
+        void *root;
+};
+
+static int posix_rbtree_compare(const void *a, const void *b) {
+        return *(const int *)a - *(const int *)b;
+}
+
+static void posix_rbtree_add(PosixRBTree *t, const Node *node) {
+        void *res;
+
+        res = tsearch(&node->key, &t->root, posix_rbtree_compare);
+        c_assert(*(int **)res == &node->key);
+}
+
+static void posix_rbtree_remove(PosixRBTree *t, const Node *node) {
+        void *res;
+
+        res = tdelete(&node->key, &t->root, posix_rbtree_compare);
+        c_assert(res);
+}
+
+static Node *posix_rbtree_find(PosixRBTree *t, int key) {
+        void *res;
+
+        res = tfind(&key, &t->root, posix_rbtree_compare);
+        return res ? node_from_key(*(int **)res) : NULL;
+}
+
+static void posix_rbtree_visit(const void *n, const VISIT o, const int depth) {
+        static int v;
+
+        /* HACK: twalk() has no context; use static context; reset on root */
+        if (depth == 0 && (o == preorder || o == leaf))
+                v = 0;
+
+        switch (o) {
+        case postorder:
+        case leaf:
+                c_assert(v <= node_from_key(*(int **)n)->key);
+                v = node_from_key(*(int **)n)->key;
+                break;
+        default:
+                break;
+        }
+}
+
+static void posix_rbtree_traverse(PosixRBTree *t) {
+        twalk(t->root, posix_rbtree_visit);
+}
+
+/*
+ * Comparison between c-rbtree and tsearch(3p)
+ *
+ * Based on the tsearch(3p) API above, this now implements some comparisons
+ * between c-rbtree and the POSIX API.
+ *
+ * The semantic differences are explained above. This does mostly performance
+ * comparisons.
+ */
+
+static void test_posix(void) {
+        uint64_t ts, ts_c1, ts_c2, ts_c3, ts_c4;
+        uint64_t ts_p1, ts_p2, ts_p3, ts_p4;
+        PosixRBTree pt = {};
+        CRBNode **slot, *p;
+        CRBTree t = {};
+        Node *nodes[2048];
+        unsigned long i;
+        int v;
+
+        /* allocate and initialize all nodes */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                nodes[i] = malloc(sizeof(*nodes[i]));
+                c_assert(nodes[i]);
+                nodes[i]->key = i;
+                c_rbnode_init(&nodes[i]->rb);
+        }
+
+        /* shuffle nodes */
+        shuffle(nodes, sizeof(nodes) / sizeof(*nodes));
+
+        /* add all nodes, and verify that each node is linked */
+        ts = now();
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                slot = c_rbtree_find_slot(&t, compare, (void *)(unsigned long)nodes[i]->key, &p);
+                c_assert(slot);
+                c_rbtree_add(&t, p, slot, &nodes[i]->rb);
+        }
+        ts_c1 = now() - ts;
+
+        ts = now();
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
+                posix_rbtree_add(&pt, nodes[i]);
+        ts_p1 = now() - ts;
+
+        /* shuffle nodes again */
+        shuffle(nodes, sizeof(nodes) / sizeof(*nodes));
+
+        /* traverse tree in-order */
+        ts = now();
+        i = 0;
+        v = 0;
+        for (p = c_rbtree_first(&t); p; p = c_rbnode_next(p)) {
+                ++i;
+
+                c_assert(v <= node_from_rb(p)->key);
+                v = node_from_rb(p)->key;
+        }
+        c_assert(i == sizeof(nodes) / sizeof(*nodes));
+        ts_c2 = now() - ts;
+
+        ts = now();
+        posix_rbtree_traverse(&pt);
+        ts_p2 = now() - ts;
+
+        /* shuffle nodes again */
+        shuffle(nodes, sizeof(nodes) / sizeof(*nodes));
+
+        /* lookup all nodes (in different order) */
+        ts = now();
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
+                c_assert(nodes[i] == c_rbtree_find_entry(&t, compare,
+                                                       (void *)(unsigned long)nodes[i]->key,
+                                                       Node, rb));
+        ts_c3 = now() - ts;
+
+        ts = now();
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
+                c_assert(nodes[i] == posix_rbtree_find(&pt, nodes[i]->key));
+        ts_p3 = now() - ts;
+
+        /* shuffle nodes again */
+        shuffle(nodes, sizeof(nodes) / sizeof(*nodes));
+
+        /* remove all nodes (in different order) */
+        ts = now();
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
+                c_rbnode_unlink(&nodes[i]->rb);
+        ts_c4 = now() - ts;
+
+        ts = now();
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
+                posix_rbtree_remove(&pt, nodes[i]);
+        ts_p4 = now() - ts;
+
+        /* free nodes again */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
+                free(nodes[i]);
+
+        fprintf(stderr, "              insertion  traversal     lookup    removal\n");
+        fprintf(stderr, "   c-rbtree: %8"PRIu64"ns %8"PRIu64"ns %8"PRIu64"ns %8"PRIu64"ns\n",
+                ts_c1, ts_c2, ts_c3, ts_c4);
+        fprintf(stderr, "tsearch(3p): %8"PRIu64"ns %8"PRIu64"ns %8"PRIu64"ns %8"PRIu64"ns\n",
+                ts_p1, ts_p2, ts_p3, ts_p4);
+}
+
+int main(int argc, char **argv) {
+        /* we want stable tests, so use fixed seed */
+        srand(0xdeadbeef);
+
+        test_posix();
+        return 0;
+}
diff --git a/src/c-rbtree/subprojects/libcstdaux-1 b/src/c-rbtree/subprojects/libcstdaux-1
new file mode 120000
index 00000000..589984f3
--- /dev/null
+++ b/src/c-rbtree/subprojects/libcstdaux-1
@@ -0,0 +1 @@
+../../c-stdaux
\ No newline at end of file