Squashed 'shared/c-rbtree/' content from commit bf627e0c3

git-subtree-dir: shared/c-rbtree
git-subtree-split: bf627e0c32241915108f66ad9738444e4d045b45

21 files changed, 3914 insertions, 0 deletions

diff --git a/.cherryci/ci-test b/.cherryci/ci-test
new file mode 100755
index 0000000000..78b0423f6b
--- /dev/null
+++ b/.cherryci/ci-test
@@ -0,0 +1,12 @@
+#!/bin/bash
+
+set -e
+
+rm -Rf "./ci-build"
+mkdir "./ci-build"
+cd "./ci-build"
+
+${CHERRY_LIB_MESONSETUP} . "${CHERRY_LIB_SRCDIR}"
+${CHERRY_LIB_NINJABUILD}
+CRBTREE_TEST_PTRACE=1 ${CHERRY_LIB_MESONTEST}
+(( ! CHERRY_LIB_VALGRIND )) || ${CHERRY_LIB_MESONTEST} "--wrapper=${CHERRY_LIB_VALGRINDWRAP}"
diff --git a/.editorconfig b/.editorconfig
new file mode 100644
index 0000000000..b10bb4f3f8
--- /dev/null
+++ b/.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/.travis.yml b/.travis.yml
new file mode 100644
index 0000000000..99a7bb9461
--- /dev/null
+++ b/.travis.yml
@@ -0,0 +1,21 @@
+os: linux
+dist: trusty
+language: c
+
+services:
+  - docker
+
+before_install:
+  - curl -O -L "https://raw.githubusercontent.com/cherry-pick/cherry-images/v1/scripts/vmrun"
+  - curl -O -L "https://raw.githubusercontent.com/cherry-pick/cherry-ci/v1/scripts/cherryci"
+  - chmod +x "./vmrun" "./cherryci"
+
+jobs:
+  include:
+    - stage: test
+      script:
+        - ./vmrun -- ../src/cherryci -d ../src/.cherryci -s c-util -m
+    - script:
+        - ./vmrun -T armv7hl -- ../src/cherryci -d ../src/.cherryci -s c-util
+    - script:
+        - ./vmrun -T i686 -- ../src/cherryci -d ../src/.cherryci -s c-util
diff --git a/AUTHORS b/AUTHORS
new file mode 100644
index 0000000000..980d602337
--- /dev/null
+++ b/AUTHORS
@@ -0,0 +1,37 @@
+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-2018 Red Hat, Inc.
+
+AUTHORS: (ordered alphabetically)
+        David Herrmann <dh.herrmann@gmail.com>
+        Tom Gundersen <teg@jklm.no>
diff --git a/AUTHORS-ASL b/AUTHORS-ASL
new file mode 100644
index 0000000000..5d501a7284
--- /dev/null
+++ b/AUTHORS-ASL
@@ -0,0 +1,201 @@
+                              Apache License
+                        Version 2.0, January 2004
+                     http://www.apache.org/licenses/
+
+TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+1. Definitions.
+
+   "License" shall mean the terms and conditions for use, reproduction,
+   and distribution as defined by Sections 1 through 9 of this document.
+
+   "Licensor" shall mean the copyright owner or entity authorized by
+   the copyright owner that is granting the License.
+
+   "Legal Entity" shall mean the union of the acting entity and all
+   other entities that control, are controlled by, or are under common
+   control with that entity. For the purposes of this definition,
+   "control" means (i) the power, direct or indirect, to cause the
+   direction or management of such entity, whether by contract or
+   otherwise, or (ii) ownership of fifty percent (50%) or more of the
+   outstanding shares, or (iii) beneficial ownership of such entity.
+
+   "You" (or "Your") shall mean an individual or Legal Entity
+   exercising permissions granted by this License.
+
+   "Source" form shall mean the preferred form for making modifications,
+   including but not limited to software source code, documentation
+   source, and configuration files.
+
+   "Object" form shall mean any form resulting from mechanical
+   transformation or translation of a Source form, including but
+   not limited to compiled object code, generated documentation,
+   and conversions to other media types.
+
+   "Work" shall mean the work of authorship, whether in Source or
+   Object form, made available under the License, as indicated by a
+   copyright notice that is included in or attached to the work
+   (an example is provided in the Appendix below).
+
+   "Derivative Works" shall mean any work, whether in Source or Object
+   form, that is based on (or derived from) the Work and for which the
+   editorial revisions, annotations, elaborations, or other modifications
+   represent, as a whole, an original work of authorship. For the purposes
+   of this License, Derivative Works shall not include works that remain
+   separable from, or merely link (or bind by name) to the interfaces of,
+   the Work and Derivative Works thereof.
+
+   "Contribution" shall mean any work of authorship, including
+   the original version of the Work and any modifications or additions
+   to that Work or Derivative Works thereof, that is intentionally
+   submitted to Licensor for inclusion in the Work by the copyright owner
+   or by an individual or Legal Entity authorized to submit on behalf of
+   the copyright owner. For the purposes of this definition, "submitted"
+   means any form of electronic, verbal, or written communication sent
+   to the Licensor or its representatives, including but not limited to
+   communication on electronic mailing lists, source code control systems,
+   and issue tracking systems that are managed by, or on behalf of, the
+   Licensor for the purpose of discussing and improving the Work, but
+   excluding communication that is conspicuously marked or otherwise
+   designated in writing by the copyright owner as "Not a Contribution."
+
+   "Contributor" shall mean Licensor and any individual or Legal Entity
+   on behalf of whom a Contribution has been received by Licensor and
+   subsequently incorporated within the Work.
+
+2. Grant of Copyright License. Subject to the terms and conditions of
+   this License, each Contributor hereby grants to You a perpetual,
+   worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+   copyright license to reproduce, prepare Derivative Works of,
+   publicly display, publicly perform, sublicense, and distribute the
+   Work and such Derivative Works in Source or Object form.
+
+3. Grant of Patent License. Subject to the terms and conditions of
+   this License, each Contributor hereby grants to You a perpetual,
+   worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+   (except as stated in this section) patent license to make, have made,
+   use, offer to sell, sell, import, and otherwise transfer the Work,
+   where such license applies only to those patent claims licensable
+   by such Contributor that are necessarily infringed by their
+   Contribution(s) alone or by combination of their Contribution(s)
+   with the Work to which such Contribution(s) was submitted. If You
+   institute patent litigation against any entity (including a
+   cross-claim or counterclaim in a lawsuit) alleging that the Work
+   or a Contribution incorporated within the Work constitutes direct
+   or contributory patent infringement, then any patent licenses
+   granted to You under this License for that Work shall terminate
+   as of the date such litigation is filed.
+
+4. Redistribution. You may reproduce and distribute copies of the
+   Work or Derivative Works thereof in any medium, with or without
+   modifications, and in Source or Object form, provided that You
+   meet the following conditions:
+
+   (a) You must give any other recipients of the Work or
+       Derivative Works a copy of this License; and
+
+   (b) You must cause any modified files to carry prominent notices
+       stating that You changed the files; and
+
+   (c) You must retain, in the Source form of any Derivative Works
+       that You distribute, all copyright, patent, trademark, and
+       attribution notices from the Source form of the Work,
+       excluding those notices that do not pertain to any part of
+       the Derivative Works; and
+
+   (d) If the Work includes a "NOTICE" text file as part of its
+       distribution, then any Derivative Works that You distribute must
+       include a readable copy of the attribution notices contained
+       within such NOTICE file, excluding those notices that do not
+       pertain to any part of the Derivative Works, in at least one
+       of the following places: within a NOTICE text file distributed
+       as part of the Derivative Works; within the Source form or
+       documentation, if provided along with the Derivative Works; or,
+       within a display generated by the Derivative Works, if and
+       wherever such third-party notices normally appear. The contents
+       of the NOTICE file are for informational purposes only and
+       do not modify the License. You may add Your own attribution
+       notices within Derivative Works that You distribute, alongside
+       or as an addendum to the NOTICE text from the Work, provided
+       that such additional attribution notices cannot be construed
+       as modifying the License.
+
+   You may add Your own copyright statement to Your modifications and
+   may provide additional or different license terms and conditions
+   for use, reproduction, or distribution of Your modifications, or
+   for any such Derivative Works as a whole, provided Your use,
+   reproduction, and distribution of the Work otherwise complies with
+   the conditions stated in this License.
+
+5. Submission of Contributions. Unless You explicitly state otherwise,
+   any Contribution intentionally submitted for inclusion in the Work
+   by You to the Licensor shall be under the terms and conditions of
+   this License, without any additional terms or conditions.
+   Notwithstanding the above, nothing herein shall supersede or modify
+   the terms of any separate license agreement you may have executed
+   with Licensor regarding such Contributions.
+
+6. Trademarks. This License does not grant permission to use the trade
+   names, trademarks, service marks, or product names of the Licensor,
+   except as required for reasonable and customary use in describing the
+   origin of the Work and reproducing the content of the NOTICE file.
+
+7. Disclaimer of Warranty. Unless required by applicable law or
+   agreed to in writing, Licensor provides the Work (and each
+   Contributor provides its Contributions) on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+   implied, including, without limitation, any warranties or conditions
+   of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+   PARTICULAR PURPOSE. You are solely responsible for determining the
+   appropriateness of using or redistributing the Work and assume any
+   risks associated with Your exercise of permissions under this License.
+
+8. Limitation of Liability. In no event and under no legal theory,
+   whether in tort (including negligence), contract, or otherwise,
+   unless required by applicable law (such as deliberate and grossly
+   negligent acts) or agreed to in writing, shall any Contributor be
+   liable to You for damages, including any direct, indirect, special,
+   incidental, or consequential damages of any character arising as a
+   result of this License or out of the use or inability to use the
+   Work (including but not limited to damages for loss of goodwill,
+   work stoppage, computer failure or malfunction, or any and all
+   other commercial damages or losses), even if such Contributor
+   has been advised of the possibility of such damages.
+
+9. Accepting Warranty or Additional Liability. While redistributing
+   the Work or Derivative Works thereof, You may choose to offer,
+   and charge a fee for, acceptance of support, warranty, indemnity,
+   or other liability obligations and/or rights consistent with this
+   License. However, in accepting such obligations, You may act only
+   on Your own behalf and on Your sole responsibility, not on behalf
+   of any other Contributor, and only if You agree to indemnify,
+   defend, and hold each Contributor harmless for any liability
+   incurred by, or claims asserted against, such Contributor by reason
+   of your accepting any such warranty or additional liability.
+
+END OF TERMS AND CONDITIONS
+
+APPENDIX: How to apply the Apache License to your work.
+
+   To apply the Apache License to your work, attach the following
+   boilerplate notice, with the fields enclosed by brackets "{}"
+   replaced with your own identifying information. (Don't include
+   the brackets!)  The text should be enclosed in the appropriate
+   comment syntax for the file format. We also recommend that a
+   file or class name and description of purpose be included on the
+   same "printed page" as the copyright notice for easier
+   identification within third-party archives.
+
+Copyright {yyyy} {name of copyright owner}
+
+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.
diff --git a/AUTHORS-LGPL b/AUTHORS-LGPL
new file mode 100644
index 0000000000..4362b49151
--- /dev/null
+++ b/AUTHORS-LGPL
@@ -0,0 +1,502 @@
+                  GNU LESSER GENERAL PUBLIC LICENSE
+                       Version 2.1, February 1999
+
+ Copyright (C) 1991, 1999 Free Software Foundation, Inc.
+ 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ Everyone is permitted to copy and distribute verbatim copies
+ of this license document, but changing it is not allowed.
+
+[This is the first released version of the Lesser GPL.  It also counts
+ as the successor of the GNU Library Public License, version 2, hence
+ the version number 2.1.]
+
+                            Preamble
+
+  The licenses for most software are designed to take away your
+freedom to share and change it.  By contrast, the GNU General Public
+Licenses are intended to guarantee your freedom to share and change
+free software--to make sure the software is free for all its users.
+
+  This license, the Lesser General Public License, applies to some
+specially designated software packages--typically libraries--of the
+Free Software Foundation and other authors who decide to use it.  You
+can use it too, but we suggest you first think carefully about whether
+this license or the ordinary General Public License is the better
+strategy to use in any particular case, based on the explanations below.
+
+  When we speak of free software, we are referring to freedom of use,
+not price.  Our General Public Licenses are designed to make sure that
+you have the freedom to distribute copies of free software (and charge
+for this service if you wish); that you receive source code or can get
+it if you want it; that you can change the software and use pieces of
+it in new free programs; and that you are informed that you can do
+these things.
+
+  To protect your rights, we need to make restrictions that forbid
+distributors to deny you these rights or to ask you to surrender these
+rights.  These restrictions translate to certain responsibilities for
+you if you distribute copies of the library or if you modify it.
+
+  For example, if you distribute copies of the library, whether gratis
+or for a fee, you must give the recipients all the rights that we gave
+you.  You must make sure that they, too, receive or can get the source
+code.  If you link other code with the library, you must provide
+complete object files to the recipients, so that they can relink them
+with the library after making changes to the library and recompiling
+it.  And you must show them these terms so they know their rights.
+
+  We protect your rights with a two-step method: (1) we copyright the
+library, and (2) we offer you this license, which gives you legal
+permission to copy, distribute and/or modify the library.
+
+  To protect each distributor, we want to make it very clear that
+there is no warranty for the free library.  Also, if the library is
+modified by someone else and passed on, the recipients should know
+that what they have is not the original version, so that the original
+author's reputation will not be affected by problems that might be
+introduced by others.
+
+  Finally, software patents pose a constant threat to the existence of
+any free program.  We wish to make sure that a company cannot
+effectively restrict the users of a free program by obtaining a
+restrictive license from a patent holder.  Therefore, we insist that
+any patent license obtained for a version of the library must be
+consistent with the full freedom of use specified in this license.
+
+  Most GNU software, including some libraries, is covered by the
+ordinary GNU General Public License.  This license, the GNU Lesser
+General Public License, applies to certain designated libraries, and
+is quite different from the ordinary General Public License.  We use
+this license for certain libraries in order to permit linking those
+libraries into non-free programs.
+
+  When a program is linked with a library, whether statically or using
+a shared library, the combination of the two is legally speaking a
+combined work, a derivative of the original library.  The ordinary
+General Public License therefore permits such linking only if the
+entire combination fits its criteria of freedom.  The Lesser General
+Public License permits more lax criteria for linking other code with
+the library.
+
+  We call this license the "Lesser" General Public License because it
+does Less to protect the user's freedom than the ordinary General
+Public License.  It also provides other free software developers Less
+of an advantage over competing non-free programs.  These disadvantages
+are the reason we use the ordinary General Public License for many
+libraries.  However, the Lesser license provides advantages in certain
+special circumstances.
+
+  For example, on rare occasions, there may be a special need to
+encourage the widest possible use of a certain library, so that it becomes
+a de-facto standard.  To achieve this, non-free programs must be
+allowed to use the library.  A more frequent case is that a free
+library does the same job as widely used non-free libraries.  In this
+case, there is little to gain by limiting the free library to free
+software only, so we use the Lesser General Public License.
+
+  In other cases, permission to use a particular library in non-free
+programs enables a greater number of people to use a large body of
+free software.  For example, permission to use the GNU C Library in
+non-free programs enables many more people to use the whole GNU
+operating system, as well as its variant, the GNU/Linux operating
+system.
+
+  Although the Lesser General Public License is Less protective of the
+users' freedom, it does ensure that the user of a program that is
+linked with the Library has the freedom and the wherewithal to run
+that program using a modified version of the Library.
+
+  The precise terms and conditions for copying, distribution and
+modification follow.  Pay close attention to the difference between a
+"work based on the library" and a "work that uses the library".  The
+former contains code derived from the library, whereas the latter must
+be combined with the library in order to run.
+
+                  GNU LESSER GENERAL PUBLIC LICENSE
+   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
+
+  0. This License Agreement applies to any software library or other
+program which contains a notice placed by the copyright holder or
+other authorized party saying it may be distributed under the terms of
+this Lesser General Public License (also called "this License").
+Each licensee is addressed as "you".
+
+  A "library" means a collection of software functions and/or data
+prepared so as to be conveniently linked with application programs
+(which use some of those functions and data) to form executables.
+
+  The "Library", below, refers to any such software library or work
+which has been distributed under these terms.  A "work based on the
+Library" means either the Library or any derivative work under
+copyright law: that is to say, a work containing the Library or a
+portion of it, either verbatim or with modifications and/or translated
+straightforwardly into another language.  (Hereinafter, translation is
+included without limitation in the term "modification".)
+
+  "Source code" for a work means the preferred form of the work for
+making modifications to it.  For a library, complete source code means
+all the source code for all modules it contains, plus any associated
+interface definition files, plus the scripts used to control compilation
+and installation of the library.
+
+  Activities other than copying, distribution and modification are not
+covered by this License; they are outside its scope.  The act of
+running a program using the Library is not restricted, and output from
+such a program is covered only if its contents constitute a work based
+on the Library (independent of the use of the Library in a tool for
+writing it).  Whether that is true depends on what the Library does
+and what the program that uses the Library does.
+
+  1. You may copy and distribute verbatim copies of the Library's
+complete source code as you receive it, in any medium, provided that
+you conspicuously and appropriately publish on each copy an
+appropriate copyright notice and disclaimer of warranty; keep intact
+all the notices that refer to this License and to the absence of any
+warranty; and distribute a copy of this License along with the
+Library.
+
+  You may charge a fee for the physical act of transferring a copy,
+and you may at your option offer warranty protection in exchange for a
+fee.
+
+  2. You may modify your copy or copies of the Library or any portion
+of it, thus forming a work based on the Library, and copy and
+distribute such modifications or work under the terms of Section 1
+above, provided that you also meet all of these conditions:
+
+    a) The modified work must itself be a software library.
+
+    b) You must cause the files modified to carry prominent notices
+    stating that you changed the files and the date of any change.
+
+    c) You must cause the whole of the work to be licensed at no
+    charge to all third parties under the terms of this License.
+
+    d) If a facility in the modified Library refers to a function or a
+    table of data to be supplied by an application program that uses
+    the facility, other than as an argument passed when the facility
+    is invoked, then you must make a good faith effort to ensure that,
+    in the event an application does not supply such function or
+    table, the facility still operates, and performs whatever part of
+    its purpose remains meaningful.
+
+    (For example, a function in a library to compute square roots has
+    a purpose that is entirely well-defined independent of the
+    application.  Therefore, Subsection 2d requires that any
+    application-supplied function or table used by this function must
+    be optional: if the application does not supply it, the square
+    root function must still compute square roots.)
+
+These requirements apply to the modified work as a whole.  If
+identifiable sections of that work are not derived from the Library,
+and can be reasonably considered independent and separate works in
+themselves, then this License, and its terms, do not apply to those
+sections when you distribute them as separate works.  But when you
+distribute the same sections as part of a whole which is a work based
+on the Library, the distribution of the whole must be on the terms of
+this License, whose permissions for other licensees extend to the
+entire whole, and thus to each and every part regardless of who wrote
+it.
+
+Thus, it is not the intent of this section to claim rights or contest
+your rights to work written entirely by you; rather, the intent is to
+exercise the right to control the distribution of derivative or
+collective works based on the Library.
+
+In addition, mere aggregation of another work not based on the Library
+with the Library (or with a work based on the Library) on a volume of
+a storage or distribution medium does not bring the other work under
+the scope of this License.
+
+  3. You may opt to apply the terms of the ordinary GNU General Public
+License instead of this License to a given copy of the Library.  To do
+this, you must alter all the notices that refer to this License, so
+that they refer to the ordinary GNU General Public License, version 2,
+instead of to this License.  (If a newer version than version 2 of the
+ordinary GNU General Public License has appeared, then you can specify
+that version instead if you wish.)  Do not make any other change in
+these notices.
+
+  Once this change is made in a given copy, it is irreversible for
+that copy, so the ordinary GNU General Public License applies to all
+subsequent copies and derivative works made from that copy.
+
+  This option is useful when you wish to copy part of the code of
+the Library into a program that is not a library.
+
+  4. You may copy and distribute the Library (or a portion or
+derivative of it, under Section 2) in object code or executable form
+under the terms of Sections 1 and 2 above provided that you accompany
+it with the complete corresponding machine-readable source code, which
+must be distributed under the terms of Sections 1 and 2 above on a
+medium customarily used for software interchange.
+
+  If distribution of object code is made by offering access to copy
+from a designated place, then offering equivalent access to copy the
+source code from the same place satisfies the requirement to
+distribute the source code, even though third parties are not
+compelled to copy the source along with the object code.
+
+  5. A program that contains no derivative of any portion of the
+Library, but is designed to work with the Library by being compiled or
+linked with it, is called a "work that uses the Library".  Such a
+work, in isolation, is not a derivative work of the Library, and
+therefore falls outside the scope of this License.
+
+  However, linking a "work that uses the Library" with the Library
+creates an executable that is a derivative of the Library (because it
+contains portions of the Library), rather than a "work that uses the
+library".  The executable is therefore covered by this License.
+Section 6 states terms for distribution of such executables.
+
+  When a "work that uses the Library" uses material from a header file
+that is part of the Library, the object code for the work may be a
+derivative work of the Library even though the source code is not.
+Whether this is true is especially significant if the work can be
+linked without the Library, or if the work is itself a library.  The
+threshold for this to be true is not precisely defined by law.
+
+  If such an object file uses only numerical parameters, data
+structure layouts and accessors, and small macros and small inline
+functions (ten lines or less in length), then the use of the object
+file is unrestricted, regardless of whether it is legally a derivative
+work.  (Executables containing this object code plus portions of the
+Library will still fall under Section 6.)
+
+  Otherwise, if the work is a derivative of the Library, you may
+distribute the object code for the work under the terms of Section 6.
+Any executables containing that work also fall under Section 6,
+whether or not they are linked directly with the Library itself.
+
+  6. As an exception to the Sections above, you may also combine or
+link a "work that uses the Library" with the Library to produce a
+work containing portions of the Library, and distribute that work
+under terms of your choice, provided that the terms permit
+modification of the work for the customer's own use and reverse
+engineering for debugging such modifications.
+
+  You must give prominent notice with each copy of the work that the
+Library is used in it and that the Library and its use are covered by
+this License.  You must supply a copy of this License.  If the work
+during execution displays copyright notices, you must include the
+copyright notice for the Library among them, as well as a reference
+directing the user to the copy of this License.  Also, you must do one
+of these things:
+
+    a) Accompany the work with the complete corresponding
+    machine-readable source code for the Library including whatever
+    changes were used in the work (which must be distributed under
+    Sections 1 and 2 above); and, if the work is an executable linked
+    with the Library, with the complete machine-readable "work that
+    uses the Library", as object code and/or source code, so that the
+    user can modify the Library and then relink to produce a modified
+    executable containing the modified Library.  (It is understood
+    that the user who changes the contents of definitions files in the
+    Library will not necessarily be able to recompile the application
+    to use the modified definitions.)
+
+    b) Use a suitable shared library mechanism for linking with the
+    Library.  A suitable mechanism is one that (1) uses at run time a
+    copy of the library already present on the user's computer system,
+    rather than copying library functions into the executable, and (2)
+    will operate properly with a modified version of the library, if
+    the user installs one, as long as the modified version is
+    interface-compatible with the version that the work was made with.
+
+    c) Accompany the work with a written offer, valid for at
+    least three years, to give the same user the materials
+    specified in Subsection 6a, above, for a charge no more
+    than the cost of performing this distribution.
+
+    d) If distribution of the work is made by offering access to copy
+    from a designated place, offer equivalent access to copy the above
+    specified materials from the same place.
+
+    e) Verify that the user has already received a copy of these
+    materials or that you have already sent this user a copy.
+
+  For an executable, the required form of the "work that uses the
+Library" must include any data and utility programs needed for
+reproducing the executable from it.  However, as a special exception,
+the materials to be distributed need not include anything that is
+normally distributed (in either source or binary form) with the major
+components (compiler, kernel, and so on) of the operating system on
+which the executable runs, unless that component itself accompanies
+the executable.
+
+  It may happen that this requirement contradicts the license
+restrictions of other proprietary libraries that do not normally
+accompany the operating system.  Such a contradiction means you cannot
+use both them and the Library together in an executable that you
+distribute.
+
+  7. You may place library facilities that are a work based on the
+Library side-by-side in a single library together with other library
+facilities not covered by this License, and distribute such a combined
+library, provided that the separate distribution of the work based on
+the Library and of the other library facilities is otherwise
+permitted, and provided that you do these two things:
+
+    a) Accompany the combined library with a copy of the same work
+    based on the Library, uncombined with any other library
+    facilities.  This must be distributed under the terms of the
+    Sections above.
+
+    b) Give prominent notice with the combined library of the fact
+    that part of it is a work based on the Library, and explaining
+    where to find the accompanying uncombined form of the same work.
+
+  8. You may not copy, modify, sublicense, link with, or distribute
+the Library except as expressly provided under this License.  Any
+attempt otherwise to copy, modify, sublicense, link with, or
+distribute the Library is void, and will automatically terminate your
+rights under this License.  However, parties who have received copies,
+or rights, from you under this License will not have their licenses
+terminated so long as such parties remain in full compliance.
+
+  9. You are not required to accept this License, since you have not
+signed it.  However, nothing else grants you permission to modify or
+distribute the Library or its derivative works.  These actions are
+prohibited by law if you do not accept this License.  Therefore, by
+modifying or distributing the Library (or any work based on the
+Library), you indicate your acceptance of this License to do so, and
+all its terms and conditions for copying, distributing or modifying
+the Library or works based on it.
+
+  10. Each time you redistribute the Library (or any work based on the
+Library), the recipient automatically receives a license from the
+original licensor to copy, distribute, link with or modify the Library
+subject to these terms and conditions.  You may not impose any further
+restrictions on the recipients' exercise of the rights granted herein.
+You are not responsible for enforcing compliance by third parties with
+this License.
+
+  11. If, as a consequence of a court judgment or allegation of patent
+infringement or for any other reason (not limited to patent issues),
+conditions are imposed on you (whether by court order, agreement or
+otherwise) that contradict the conditions of this License, they do not
+excuse you from the conditions of this License.  If you cannot
+distribute so as to satisfy simultaneously your obligations under this
+License and any other pertinent obligations, then as a consequence you
+may not distribute the Library at all.  For example, if a patent
+license would not permit royalty-free redistribution of the Library by
+all those who receive copies directly or indirectly through you, then
+the only way you could satisfy both it and this License would be to
+refrain entirely from distribution of the Library.
+
+If any portion of this section is held invalid or unenforceable under any
+particular circumstance, the balance of the section is intended to apply,
+and the section as a whole is intended to apply in other circumstances.
+
+It is not the purpose of this section to induce you to infringe any
+patents or other property right claims or to contest validity of any
+such claims; this section has the sole purpose of protecting the
+integrity of the free software distribution system which is
+implemented by public license practices.  Many people have made
+generous contributions to the wide range of software distributed
+through that system in reliance on consistent application of that
+system; it is up to the author/donor to decide if he or she is willing
+to distribute software through any other system and a licensee cannot
+impose that choice.
+
+This section is intended to make thoroughly clear what is believed to
+be a consequence of the rest of this License.
+
+  12. If the distribution and/or use of the Library is restricted in
+certain countries either by patents or by copyrighted interfaces, the
+original copyright holder who places the Library under this License may add
+an explicit geographical distribution limitation excluding those countries,
+so that distribution is permitted only in or among countries not thus
+excluded.  In such case, this License incorporates the limitation as if
+written in the body of this License.
+
+  13. The Free Software Foundation may publish revised and/or new
+versions of the Lesser General Public License from time to time.
+Such new versions will be similar in spirit to the present version,
+but may differ in detail to address new problems or concerns.
+
+Each version is given a distinguishing version number.  If the Library
+specifies a version number of this License which applies to it and
+"any later version", you have the option of following the terms and
+conditions either of that version or of any later version published by
+the Free Software Foundation.  If the Library does not specify a
+license version number, you may choose any version ever published by
+the Free Software Foundation.
+
+  14. If you wish to incorporate parts of the Library into other free
+programs whose distribution conditions are incompatible with these,
+write to the author to ask for permission.  For software which is
+copyrighted by the Free Software Foundation, write to the Free
+Software Foundation; we sometimes make exceptions for this.  Our
+decision will be guided by the two goals of preserving the free status
+of all derivatives of our free software and of promoting the sharing
+and reuse of software generally.
+
+                            NO WARRANTY
+
+  15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO
+WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW.
+EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR
+OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY
+KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE
+LIBRARY IS WITH YOU.  SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME
+THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
+
+  16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN
+WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY
+AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU
+FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR
+CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE
+LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING
+RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A
+FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF
+SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
+DAMAGES.
+
+                     END OF TERMS AND CONDITIONS
+
+           How to Apply These Terms to Your New Libraries
+
+  If you develop a new library, and you want it to be of the greatest
+possible use to the public, we recommend making it free software that
+everyone can redistribute and change.  You can do so by permitting
+redistribution under these terms (or, alternatively, under the terms of the
+ordinary General Public License).
+
+  To apply these terms, attach the following notices to the library.  It is
+safest to attach them to the start of each source file to most effectively
+convey the exclusion of warranty; and each file should have at least the
+"copyright" line and a pointer to where the full notice is found.
+
+    <one line to give the library's name and a brief idea of what it does.>
+    Copyright (C) <year>  <name of author>
+
+    This library 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 library 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 library; if not, write to the Free Software
+    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+
+Also add information on how to contact you by electronic and paper mail.
+
+You should also get your employer (if you work as a programmer) or your
+school, if any, to sign a "copyright disclaimer" for the library, if
+necessary.  Here is a sample; alter the names:
+
+  Yoyodyne, Inc., hereby disclaims all copyright interest in the
+  library `Frob' (a library for tweaking knobs) written by James Random Hacker.
+
+  <signature of Ty Coon>, 1 April 1990
+  Ty Coon, President of Vice
+
+That's all there is to it!
diff --git a/LICENSE b/LICENSE
new file mode 120000
index 0000000000..da24c5e4a6
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1 @@
+AUTHORS-ASL
\ No newline at end of file
diff --git a/NEWS b/NEWS
new file mode 100644
index 0000000000..59c03c7ee8
--- /dev/null
+++ b/NEWS
@@ -0,0 +1,40 @@
+c-rbtree - Intrusive Red-Black Tree Collection
+
+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/README b/README
new file mode 100644
index 0000000000..069e15c65c
--- /dev/null
+++ b/README
@@ -0,0 +1,52 @@
+c-rbtree - Intrusive Red-Black Tree Collection
+
+ABOUT:
+        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.
+
+DETAILS:
+        https://c-util.github.io/c-rbtree
+
+BUG REPORTS:
+        https://github.com/c-util/c-rbtree/issues
+
+GIT:
+        git@github.com:c-util/c-rbtree.git
+        https://github.com/c-util/c-rbtree.git
+
+GITWEB:
+        https://github.com/c-util/c-rbtree
+
+LICENSE:
+        Apache Software License 2.0
+        Lesser General Public License 2.1+
+        See AUTHORS for details.
+
+REQUIREMENTS:
+        The requirements for c-siphash are:
+
+            libc (e.g., glibc >= 2.16)
+
+        At build-time, the following software is required:
+
+            meson >= 0.41
+            pkg-config >= 0.29
+
+INSTALL:
+        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:
+
+            $ mkdir build
+            $ cd build
+            $ meson setup ..
+            $ ninja
+            $ meson test
+            # ninja install
+
+        No custom configuration options are available.
diff --git a/meson.build b/meson.build
new file mode 100644
index 0000000000..ce57651e4b
--- /dev/null
+++ b/meson.build
@@ -0,0 +1,15 @@
+project(
+        'c-rbtree',
+        'c',
+        version: '3',
+        license: 'Apache',
+        default_options: [
+                'c_std=c11'
+        ],
+)
+project_description = 'Intrusive Red-Black Tree Collection'
+
+add_project_arguments('-D_GNU_SOURCE', language: 'c')
+mod_pkgconfig = import('pkgconfig')
+
+subdir('src')
diff --git a/src/c-rbtree-private.h b/src/c-rbtree-private.h
new file mode 100644
index 0000000000..25b9ba01c0
--- /dev/null
+++ b/src/c-rbtree-private.h
@@ -0,0 +1,40 @@
+#pragma once
+
+/*
+ * Private definitions
+ * This file contains private definitions for the RB-Tree implementation, but
+ * which are used by our test-suite.
+ */
+
+#include <stddef.h>
+#include "c-rbtree.h"
+
+/*
+ * Macros
+ */
+
+#define _public_ __attribute__((__visibility__("default")))
+
+/*
+ * Nodes
+ */
+
+static inline void *c_rbnode_raw(CRBNode *n) {
+        return (void *)(n->__parent_and_flags & ~C_RBNODE_FLAG_MASK);
+}
+
+static inline unsigned long c_rbnode_flags(CRBNode *n) {
+        return n->__parent_and_flags & C_RBNODE_FLAG_MASK;
+}
+
+static inline _Bool c_rbnode_is_red(CRBNode *n) {
+        return c_rbnode_flags(n) & C_RBNODE_RED;
+}
+
+static inline _Bool c_rbnode_is_black(CRBNode *n) {
+        return !(c_rbnode_flags(n) & C_RBNODE_RED);
+}
+
+static inline _Bool c_rbnode_is_root(CRBNode *n) {
+        return c_rbnode_flags(n) & C_RBNODE_ROOT;
+}
diff --git a/src/c-rbtree.c b/src/c-rbtree.c
new file mode 100644
index 0000000000..f58db849b6
--- /dev/null
+++ b/src/c-rbtree.c
@@ -0,0 +1,1118 @@
+/*
+ * 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
+ * occur. Those situations are enumerated as "Case 1" to "Case n" here, and
+ * follow closely the cases described in most RB-Tree documentations. This file
+ * does not explain why it is enough to handle just those cases, nor does it
+ * provide a proof of correctness. Dig out your algorithm 101 handbook if
+ * you're interested.
+ *
+ * This implementation is *not* straightforward. Usually, a handful of
+ * rotation, reparent, swap and link helpers can be used to implement the
+ * rebalance operations. However, those often perform unnecessary writes.
+ * Therefore, this implementation hard-codes all the operations. You're highly
+ * recommended to look at the two basic helpers before reading the code:
+ *     c_rbnode_swap_child()
+ *     c_rbnode_set_parent_and_flags()
+ * Those are the only helpers used, hence, you should really know what they do
+ * before digging into the code.
+ *
+ * For a highlevel documentation of the API, see the header file and docbook
+ * comments.
+ */
+
+#include <assert.h>
+#include <stdalign.h>
+#include <stddef.h>
+
+#include "c-rbtree-private.h"
+#include "c-rbtree.h"
+
+/*
+ * We use alignas(8) to enforce 64bit alignment of structure fields. This is
+ * according to ISO-C11, so we rely on the compiler to implement this. However,
+ * at the same time we don't want to exceed native malloc() alignment on target
+ * platforms. Hence, we also verify against max_align_t.
+ */
+static_assert(alignof(CRBNode) <= alignof(max_align_t), "Invalid RBNode alignment");
+static_assert(alignof(CRBNode) >= 8, "Invalid CRBNode alignment");
+static_assert(alignof(CRBTree) <= alignof(max_align_t), "Invalid RBTree alignment");
+static_assert(alignof(CRBTree) >= 8, "Invalid CRBTree alignment");
+
+/**
+ * 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.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to leftmost child, or NULL.
+ */
+_public_ CRBNode *c_rbnode_leftmost(CRBNode *n) {
+        if (n)
+                while (n->left)
+                        n = n->left;
+        return n;
+}
+
+/**
+ * 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.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to rightmost child, or NULL.
+ */
+_public_ CRBNode *c_rbnode_rightmost(CRBNode *n) {
+        if (n)
+                while (n->right)
+                        n = n->right;
+        return n;
+}
+
+/**
+ * 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.
+ *
+ * The left-deepest child is defined as the deepest child without any left
+ * (grand-...)siblings.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to left-deepest child, or NULL.
+ */
+_public_ CRBNode *c_rbnode_leftdeepest(CRBNode *n) {
+        if (n) {
+                for (;;) {
+                        if (n->left)
+                                n = n->left;
+                        else if (n->right)
+                                n = n->right;
+                        else
+                                break;
+                }
+        }
+        return n;
+}
+
+/**
+ * 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.
+ *
+ * The right-deepest child is defined as the deepest child without any right
+ * (grand-...)siblings.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to right-deepest child, or NULL.
+ */
+_public_ CRBNode *c_rbnode_rightdeepest(CRBNode *n) {
+        if (n) {
+                for (;;) {
+                        if (n->right)
+                                n = n->right;
+                        else if (n->left)
+                                n = n->left;
+                        else
+                                break;
+                }
+        }
+        return n;
+}
+
+/**
+ * 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
+ * unlinked, this returns NULL.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to next node, or NULL.
+ */
+_public_ CRBNode *c_rbnode_next(CRBNode *n) {
+        CRBNode *p;
+
+        if (!c_rbnode_is_linked(n))
+                return NULL;
+        if (n->right)
+                return c_rbnode_leftmost(n->right);
+
+        while ((p = c_rbnode_parent(n)) && n == p->right)
+                n = p;
+
+        return p;
+}
+
+/**
+ * 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.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to previous node, or NULL.
+ */
+_public_ CRBNode *c_rbnode_prev(CRBNode *n) {
+        CRBNode *p;
+
+        if (!c_rbnode_is_linked(n))
+                return NULL;
+        if (n->left)
+                return c_rbnode_rightmost(n->left);
+
+        while ((p = c_rbnode_parent(n)) && n == p->left)
+                n = p;
+
+        return p;
+}
+
+/**
+ * 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 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
+ * traversed recursively.
+ *
+ * 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);
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to next node, or NULL.
+ */
+_public_ CRBNode *c_rbnode_next_postorder(CRBNode *n) {
+        CRBNode *p;
+
+        if (!c_rbnode_is_linked(n))
+                return NULL;
+
+        p = c_rbnode_parent(n);
+        if (p && n == p->left && p->right)
+                return c_rbnode_leftdeepest(p->right);
+
+        return p;
+}
+
+/**
+ * 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 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:
+ *
+ *     n == c_rbnode_prev_postorder(c_rbnode_next_postorder(n))
+ *
+ * This function can be used to implement a right-to-left pre-order traversal,
+ * 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);
+ *
+ * This would effectively perform a right-to-left pre-order traversal: first
+ * visit a parent, then its right child, then its left child. Both children are
+ * traversed recursively.
+ *
+ * Worst case runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to previous node in post-order, or NULL.
+ */
+_public_ CRBNode *c_rbnode_prev_postorder(CRBNode *n) {
+        CRBNode *p;
+
+        if (!c_rbnode_is_linked(n))
+                return NULL;
+        if (n->right)
+                return n->right;
+        if (n->left)
+                return n->left;
+
+        while ((p = c_rbnode_parent(n))) {
+                if (p->left && n != p->left)
+                        return p->left;
+                n = p;
+        }
+
+        return NULL;
+}
+
+/**
+ * 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.
+ *
+ * Fixed runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to first node, or NULL.
+ */
+_public_ CRBNode *c_rbtree_first(CRBTree *t) {
+        assert(t);
+        return c_rbnode_leftmost(t->root);
+}
+
+/**
+ * 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.
+ *
+ * Fixed runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to last node, or NULL.
+ */
+_public_ CRBNode *c_rbtree_last(CRBTree *t) {
+        assert(t);
+        return c_rbnode_rightmost(t->root);
+}
+
+/**
+ * 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
+ * NULL.
+ *
+ * This can also be interpreted as the last node of a right-to-left pre-order
+ * traversal.
+ *
+ * Fixed runtime (n: number of elements in tree): O(log(n))
+ *
+ * Return: Pointer to first node in post-order, or NULL.
+ */
+_public_ CRBNode *c_rbtree_first_postorder(CRBTree *t) {
+        assert(t);
+        return c_rbnode_leftdeepest(t->root);
+}
+
+/**
+ * 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.
+ *
+ * This can also be interpreted as the first node of a right-to-left pre-order
+ * traversal.
+ *
+ * Fixed runtime (n: number of elements in tree): O(1)
+ *
+ * Return: Pointer to last node in post-order, or NULL.
+ */
+_public_ CRBNode *c_rbtree_last_postorder(CRBTree *t) {
+        assert(t);
+        return t->root;
+}
+
+static inline void c_rbtree_store(CRBNode **ptr, CRBNode *addr) {
+        /*
+         * 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.
+         * Note that you still need to properly synchronize your accesses via
+         * seqlocks, rcu, whatever. We just guarantee that you get *some*
+         * result on a lockless traversal and never run into endless loops, or
+         * undefined behavior.
+         */
+        *(volatile CRBNode **)ptr = addr;
+}
+
+/*
+ * Set the flags and parent of a node. This should be treated as a simple
+ * assignment of the 'flags' and 'parent' fields of the node. No other magic is
+ * applied. But since both fields share its backing memory, this helper
+ * function is provided.
+ */
+static inline void c_rbnode_set_parent_and_flags(CRBNode *n, CRBNode *p, unsigned long flags) {
+        n->__parent_and_flags = (unsigned long)p | flags;
+}
+
+/*
+ * Nodes in the tree do not separately store a point to the tree root. That is,
+ * there is no way to access the tree-root in O(1) given an arbitrary node.
+ * Fortunately, this is usually not required. The only situation where this is
+ * needed is when rotating the root-node itself.
+ *
+ * In case of the root node, c_rbnode_parent() returns NULL. We use this fact
+ * to re-use the parent-pointer storage of the root node to point to the
+ * CRBTree root. This way, we can rotate the root-node (or add/remove it)
+ * without requiring a separate tree-root pointer.
+ *
+ * However, to keep the tree-modification functions simple, we hide this detail
+ * whenever possible. This means, c_rbnode_parent() will continue to return
+ * NULL, and tree modifications will boldly reset the pointer to NULL on
+ * rotation. Hence, the only way to retain this pointer is to call
+ * c_rbnode_pop_root() on a possible root-node before rotating. This returns
+ * NULL if the node in question is not the root node. Otherwise, it returns the
+ * tree-root, and clears the pointer/flag from the node in question. This way,
+ * you can perform tree operations as usual. Afterwards, use
+ * c_rbnode_push_root() to restore the root-pointer on any possible new root.
+ */
+static inline CRBTree *c_rbnode_pop_root(CRBNode *n) {
+        CRBTree *t = NULL;
+
+        if (c_rbnode_is_root(n)) {
+                t = c_rbnode_raw(n);
+                n->__parent_and_flags = c_rbnode_flags(n) & ~C_RBNODE_ROOT;
+        }
+
+        return t;
+}
+
+/* counter-part to c_rbnode_pop_root() */
+static inline CRBTree *c_rbnode_push_root(CRBNode *n, CRBTree *t) {
+        if (t) {
+                if (n)
+                        n->__parent_and_flags = (unsigned long)t
+                                                | c_rbnode_flags(n)
+                                                | C_RBNODE_ROOT;
+                c_rbtree_store(&t->root, n);
+        }
+
+        return NULL;
+}
+
+/*
+ * This function partially swaps a child node with another one. That is, this
+ * function changes the parent of @old to point to @new. That is, you use it
+ * when swapping @old with @new, to update the parent's left/right pointer.
+ * This function does *NOT* perform a full swap, nor does it touch any 'parent'
+ * pointer.
+ *
+ * The sole purpose of this function is to shortcut left/right conditionals
+ * like this:
+ *
+ *     if (old == old->parent->left)
+ *             old->parent->left = new;
+ *     else
+ *             old->parent->right = new;
+ *
+ * That's it! If @old is the root node, this will do nothing. The caller must
+ * employ c_rbnode_pop_root() and c_rbnode_push_root().
+ */
+static inline void c_rbnode_swap_child(CRBNode *old, CRBNode *new) {
+        CRBNode *p = c_rbnode_parent(old);
+
+        if (p) {
+                if (p->left == old)
+                        c_rbtree_store(&p->left, new);
+                else
+                        c_rbtree_store(&p->right, new);
+        }
+}
+
+/**
+ * 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.
+ *
+ * Note that this operates in O(1) time. Only the root-entry is updated to
+ * point to the new tree-root.
+ */
+_public_ void c_rbtree_move(CRBTree *to, CRBTree *from) {
+        CRBTree *t;
+
+        assert(!to->root);
+
+        if (from->root) {
+                t = c_rbnode_pop_root(from->root);
+                assert(t == from);
+
+                to->root = from->root;
+                from->root = NULL;
+
+                c_rbnode_push_root(to->root, to);
+        }
+}
+
+static inline void c_rbtree_paint_terminal(CRBNode *n) {
+        CRBNode *p, *g, *gg, *x;
+        CRBTree *t;
+
+        /*
+         * Case 4:
+         * This path assumes @n is red, @p is red, but the uncle is unset or
+         * black. This implies @g exists and is black.
+         *
+         * This case requires up to 2 rotations to restore the tree invariants.
+         * That is, it runs in O(1) time and fully restores the RB-Tree
+         * invariants, all at the cost of performing at mots 2 rotations.
+         */
+
+        p = c_rbnode_parent(n);
+        g = c_rbnode_parent(p);
+        gg = c_rbnode_parent(g);
+
+        assert(c_rbnode_is_red(p));
+        assert(c_rbnode_is_black(g));
+        assert(p == g->left || !g->left || c_rbnode_is_black(g->left));
+        assert(p == g->right || !g->right || c_rbnode_is_black(g->right));
+
+        if (p == g->left) {
+                if (n == p->right) {
+                        /*
+                         * We're the right red child of a red parent, which is
+                         * a left child. Rotate on parent and consider us to be
+                         * the old parent and the old parent to be us, making us
+                         * the left child instead of the right child so we can
+                         * handle it the same as below. Rotating two red nodes
+                         * changes none of the invariants.
+                         */
+                        x = n->left;
+                        c_rbtree_store(&p->right, x);
+                        c_rbtree_store(&n->left, p);
+                        if (x)
+                                c_rbnode_set_parent_and_flags(x, p, c_rbnode_flags(x));
+                        c_rbnode_set_parent_and_flags(p, n, c_rbnode_flags(p));
+                        p = n;
+                }
+
+                /* 'n' is invalid from here on! */
+
+                /*
+                 * We're the red left child of a red parent, black grandparent
+                 * and uncle. Rotate parent on grandparent and switch their
+                 * colors, making the parent black and the grandparent red. The
+                 * root of this subtree was changed from the grandparent to the
+                 * parent, but the color remained black, so the number of black
+                 * nodes on each path stays the same. However, we got rid of
+                 * the double red path as we are still the (red) child of the
+                 * parent, which has now turned black. Note that had we been
+                 * the right child, rather than the left child, we would now be
+                 * the left child of the old grandparent, and we would still
+                 * have a double red path. As the new grandparent remains
+                 * black, we're done.
+                 */
+                x = p->right;
+                t = c_rbnode_pop_root(g);
+                c_rbtree_store(&g->left, x);
+                c_rbtree_store(&p->right, g);
+                c_rbnode_swap_child(g, p);
+                if (x)
+                        c_rbnode_set_parent_and_flags(x, g, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                c_rbnode_set_parent_and_flags(p, gg, c_rbnode_flags(p) & ~C_RBNODE_RED);
+                c_rbnode_set_parent_and_flags(g, p, c_rbnode_flags(g) | C_RBNODE_RED);
+                c_rbnode_push_root(p, t);
+        } else /* if (p == g->right) */ { /* same as above, but mirrored */
+                if (n == p->left) {
+                        x = n->right;
+                        c_rbtree_store(&p->left, n->right);
+                        c_rbtree_store(&n->right, p);
+                        if (x)
+                                c_rbnode_set_parent_and_flags(x, p, c_rbnode_flags(x));
+                        c_rbnode_set_parent_and_flags(p, n, c_rbnode_flags(p));
+                        p = n;
+                }
+
+                x = p->left;
+                t = c_rbnode_pop_root(g);
+                c_rbtree_store(&g->right, x);
+                c_rbtree_store(&p->left, g);
+                c_rbnode_swap_child(g, p);
+                if (x)
+                        c_rbnode_set_parent_and_flags(x, g, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                c_rbnode_set_parent_and_flags(p, gg, c_rbnode_flags(p) & ~C_RBNODE_RED);
+                c_rbnode_set_parent_and_flags(g, p, c_rbnode_flags(g) | C_RBNODE_RED);
+                c_rbnode_push_root(p, t);
+        }
+}
+
+static inline CRBNode *c_rbtree_paint_path(CRBNode *n) {
+        CRBNode *p, *g, *u;
+
+        for (;;) {
+                p = c_rbnode_parent(n);
+                if (!p) {
+                        /*
+                         * Case 1:
+                         * We reached the root. Mark it black and be done. As
+                         * all leaf-paths share the root, the ratio of black
+                         * nodes on each path stays the same.
+                         */
+                        c_rbnode_set_parent_and_flags(n, c_rbnode_raw(n), c_rbnode_flags(n) & ~C_RBNODE_RED);
+                        return NULL;
+                } else if (c_rbnode_is_black(p)) {
+                        /*
+                         * Case 2:
+                         * The parent is already black. As our node is red, we
+                         * did not change the number of black nodes on any
+                         * path, nor do we have multiple consecutive red nodes.
+                         * There is nothing to be done.
+                         */
+                        return NULL;
+                }
+
+                g = c_rbnode_parent(p);
+                u = (p == g->left) ? g->right : g->left;
+                if (!u || !c_rbnode_is_red(u)) {
+                        /*
+                         * Case 4:
+                         * The parent is red, but its uncle is black. By
+                         * rotating the parent above the uncle, we distribute
+                         * the red nodes and thus restore the tree invariants.
+                         * No recursive fixup will be needed afterwards. Hence,
+                         * just let the caller know about @n and make them do
+                         * the rotations.
+                         */
+                        return n;
+                }
+
+                /*
+                 * Case 3:
+                 * Parent and uncle are both red, and grandparent is black.
+                 * Repaint parent and uncle black, the grandparent red and
+                 * recurse into the grandparent. Note that this is the only
+                 * recursive case. That is, this step restores the tree
+                 * invariants for the sub-tree below @p (including @n), but
+                 * needs to continue the re-coloring two levels up.
+                 */
+                c_rbnode_set_parent_and_flags(p, g, c_rbnode_flags(p) & ~C_RBNODE_RED);
+                c_rbnode_set_parent_and_flags(u, g, c_rbnode_flags(u) & ~C_RBNODE_RED);
+                c_rbnode_set_parent_and_flags(g, c_rbnode_raw(g), c_rbnode_flags(g) | C_RBNODE_RED);
+                n = g;
+        }
+}
+
+static inline void c_rbtree_paint(CRBNode *n) {
+        /*
+         * When a new node is inserted into an RB-Tree, we always link it as a
+         * tail-node and paint it red. This way, the node will not violate the
+         * rb-tree invariants regarding the number of black nodes on all paths.
+         *
+         * However, a red node must never have another bordering red-node (ie.,
+         * child or parent). Since the node is newly linked, it does not have
+         * any children. Therefore, all we need to do is fix the path upwards
+         * through all parents until we hit a black parent or can otherwise fix
+         * the coloring.
+         *
+         * This function first walks up the path from @n towards the tree root
+         * (done in c_rbtree_paint_path()). This recolors its parent/uncle, if
+         * possible, until it hits a sub-tree that cannot be fixed via
+         * re-coloring. After c_rbtree_paint_path() returns, there are two
+         * possible outcomes:
+         *
+         *         1) @n is NULL, in which case the tree invariants were
+         *            restored by mere recoloring. Nothing is to be done.
+         *
+         *         2) @n is non-NULL, but points to a red ancestor of the
+         *            original node. In this case we need to restore the tree
+         *            invariants via a simple left or right rotation. This will
+         *            be done by c_rbtree_paint_terminal().
+         *
+         * As a summary, this function runs O(log(n)) re-coloring operations in
+         * the worst case, followed by O(1) rotations as final restoration. The
+         * amortized cost, however, is O(1), since re-coloring only recurses
+         * upwards if it hits a red uncle (which can only happen if a previous
+         * operation terminated its operation on that layer).
+         * While amortized painting of inserted nodes is O(1), finding the
+         * correct spot to link the node (before painting it) still requires a
+         * search in the binary tree in O(log(n)).
+         */
+        n = c_rbtree_paint_path(n);
+        if (n)
+                c_rbtree_paint_terminal(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
+ *
+ * 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().
+ *
+ * In most cases you are better off using c_rbtree_add(). See there for details
+ * how tree-insertion works.
+ */
+_public_ void c_rbnode_link(CRBNode *p, CRBNode **l, CRBNode *n) {
+        assert(p);
+        assert(l);
+        assert(n);
+        assert(l == &p->left || l == &p->right);
+
+        c_rbnode_set_parent_and_flags(n, p, C_RBNODE_RED);
+        c_rbtree_store(&n->left, NULL);
+        c_rbtree_store(&n->right, NULL);
+        c_rbtree_store(l, n);
+
+        c_rbtree_paint(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.
+ *
+ * A typical insertion would look like this (@t is your tree, @n is your node):
+ *
+ *        CRBNode **i, *p;
+ *
+ *        i = &t->root;
+ *        p = NULL;
+ *        while (*i) {
+ *                p = *i;
+ *                if (compare(n, *i) < 0)
+ *                        i = &(*i)->left;
+ *                else
+ *                        i = &(*i)->right;
+ *        }
+ *
+ *        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:
+ *
+ *        CRBNode *i;
+ *
+ *        i = t->root;
+ *        while (i) {
+ *                int v = compare(n, i);
+ *                if (v < 0)
+ *                        i = (*i)->left;
+ *                else if (v > 0)
+ *                        i = (*i)->right;
+ *                else
+ *                        break;
+ *        }
+ *
+ * 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().
+ * 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().
+ */
+_public_ void c_rbtree_add(CRBTree *t, CRBNode *p, CRBNode **l, CRBNode *n) {
+        assert(t);
+        assert(l);
+        assert(n);
+        assert(!p || l == &p->left || l == &p->right);
+        assert(p || l == &t->root);
+
+        c_rbnode_set_parent_and_flags(n, p, C_RBNODE_RED);
+        c_rbtree_store(&n->left, NULL);
+        c_rbtree_store(&n->right, NULL);
+
+        if (p)
+                c_rbtree_store(l, n);
+        else
+                c_rbnode_push_root(n, t);
+
+        c_rbtree_paint(n);
+}
+
+static inline void c_rbnode_rebalance_terminal(CRBNode *p, CRBNode *previous) {
+        CRBNode *s, *x, *y, *g;
+        CRBTree *t;
+
+        if (previous == p->left) {
+                s = p->right;
+                if (c_rbnode_is_red(s)) {
+                        /*
+                         * Case 2:
+                         * We have a red node as sibling. Rotate it onto our
+                         * side so we can later on turn it black. This way, we
+                         * gain the additional black node in our path.
+                         */
+                        t = c_rbnode_pop_root(p);
+                        g = c_rbnode_parent(p);
+                        x = s->left;
+                        c_rbtree_store(&p->right, x);
+                        c_rbtree_store(&s->left, p);
+                        c_rbnode_swap_child(p, s);
+                        c_rbnode_set_parent_and_flags(x, p, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                        c_rbnode_set_parent_and_flags(s, g, c_rbnode_flags(s) & ~C_RBNODE_RED);
+                        c_rbnode_set_parent_and_flags(p, s, c_rbnode_flags(p) | C_RBNODE_RED);
+                        c_rbnode_push_root(s, t);
+                        s = x;
+                }
+
+                x = s->right;
+                if (!x || c_rbnode_is_black(x)) {
+                        y = s->left;
+                        if (!y || c_rbnode_is_black(y)) {
+                                /*
+                                 * Case 3+4:
+                                 * Our sibling is black and has only black
+                                 * children. Flip it red and turn parent black.
+                                 * This way we gained a black node in our path.
+                                 * Note that the parent must be red, otherwise
+                                 * it must have been handled by our caller.
+                                 */
+                                assert(c_rbnode_is_red(p));
+                                c_rbnode_set_parent_and_flags(s, p, c_rbnode_flags(s) | C_RBNODE_RED);
+                                c_rbnode_set_parent_and_flags(p, c_rbnode_parent(p), c_rbnode_flags(p) & ~C_RBNODE_RED);
+                                return;
+                        }
+
+                        /*
+                         * Case 5:
+                         * Left child of our sibling is red, right one is black.
+                         * Rotate on parent so the right child of our sibling is
+                         * now red, and we can fall through to case 6.
+                         */
+                        x = y->right;
+                        c_rbtree_store(&s->left, y->right);
+                        c_rbtree_store(&y->right, s);
+                        c_rbtree_store(&p->right, y);
+                        if (x)
+                                c_rbnode_set_parent_and_flags(x, s, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                        x = s;
+                        s = y;
+                }
+
+                /*
+                 * Case 6:
+                 * The right child of our sibling is red. Rotate left and flip
+                 * colors, which gains us an additional black node in our path,
+                 * that was previously on our sibling.
+                 */
+                t = c_rbnode_pop_root(p);
+                g = c_rbnode_parent(p);
+                y = s->left;
+                c_rbtree_store(&p->right, y);
+                c_rbtree_store(&s->left, p);
+                c_rbnode_swap_child(p, s);
+                c_rbnode_set_parent_and_flags(x, s, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                if (y)
+                        c_rbnode_set_parent_and_flags(y, p, c_rbnode_flags(y));
+                c_rbnode_set_parent_and_flags(s, g, c_rbnode_flags(p));
+                c_rbnode_set_parent_and_flags(p, s, c_rbnode_flags(p) & ~C_RBNODE_RED);
+                c_rbnode_push_root(s, t);
+        } else /* if (previous == p->right) */ { /* same as above, but mirrored */
+                s = p->left;
+                if (c_rbnode_is_red(s)) {
+                        t = c_rbnode_pop_root(p);
+                        g = c_rbnode_parent(p);
+                        x = s->right;
+                        c_rbtree_store(&p->left, x);
+                        c_rbtree_store(&s->right, p);
+                        c_rbnode_swap_child(p, s);
+                        c_rbnode_set_parent_and_flags(x, p, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                        c_rbnode_set_parent_and_flags(s, g, c_rbnode_flags(s) & ~C_RBNODE_RED);
+                        c_rbnode_set_parent_and_flags(p, s, c_rbnode_flags(p) | C_RBNODE_RED);
+                        c_rbnode_push_root(s, t);
+                        s = x;
+                }
+
+                x = s->left;
+                if (!x || c_rbnode_is_black(x)) {
+                        y = s->right;
+                        if (!y || c_rbnode_is_black(y)) {
+                                assert(c_rbnode_is_red(p));
+                                c_rbnode_set_parent_and_flags(s, p, c_rbnode_flags(s) | C_RBNODE_RED);
+                                c_rbnode_set_parent_and_flags(p, c_rbnode_parent(p), c_rbnode_flags(p) & ~C_RBNODE_RED);
+                                return;
+                        }
+
+                        x = y->left;
+                        c_rbtree_store(&s->right, y->left);
+                        c_rbtree_store(&y->left, s);
+                        c_rbtree_store(&p->left, y);
+                        if (x)
+                                c_rbnode_set_parent_and_flags(x, s, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                        x = s;
+                        s = y;
+                }
+
+                t = c_rbnode_pop_root(p);
+                g = c_rbnode_parent(p);
+                y = s->right;
+                c_rbtree_store(&p->left, y);
+                c_rbtree_store(&s->right, p);
+                c_rbnode_swap_child(p, s);
+                c_rbnode_set_parent_and_flags(x, s, c_rbnode_flags(x) & ~C_RBNODE_RED);
+                if (y)
+                        c_rbnode_set_parent_and_flags(y, p, c_rbnode_flags(y));
+                c_rbnode_set_parent_and_flags(s, g, c_rbnode_flags(p));
+                c_rbnode_set_parent_and_flags(p, s, c_rbnode_flags(p) & ~C_RBNODE_RED);
+                c_rbnode_push_root(s, t);
+        }
+}
+
+static inline CRBNode *c_rbnode_rebalance_path(CRBNode *p, CRBNode **previous) {
+        CRBNode *s, *nl, *nr;
+
+        while (p) {
+                s = (*previous == p->left) ? p->right : p->left;
+                nl = s->left;
+                nr = s->right;
+
+                /*
+                 * If the sibling under @p is black and exclusively has black
+                 * children itself (i.e., nephews/nieces in @nl/@nr), then we
+                 * can easily re-color to fix this sub-tree, and continue one
+                 * layer up. However, if that's not the case, we have tree
+                 * rotations at our hands to move one of the black nodes into
+                 * our path, then turning the red node black to fully restore
+                 * the RB-Tree invariants again. This fixup will be done by the
+                 * caller, so we just let them know where to do that.
+                 */
+                if (c_rbnode_is_red(s) ||
+                    (nl && c_rbnode_is_red(nl)) ||
+                    (nr && c_rbnode_is_red(nr)))
+                        return p;
+
+                /*
+                 * Case 3+4:
+                 * Sibling is black, and all nephews/nieces are black. Flip
+                 * sibling red. This way the sibling lost a black node in its
+                 * path, thus getting even with our path. However, paths not
+                 * going through @p haven't been fixed up, hence we proceed
+                 * recursively one layer up.
+                 * Before we continue one layer up, there are two possible
+                 * terminations: If the parent is red, we can turn it black.
+                 * This terminates the rebalancing, since the entire point of
+                 * rebalancing is that everything below @p has one black node
+                 * less than everything else. Lastly, if there is no layer
+                 * above, we hit the tree root and nothing is left to be done.
+                 */
+                c_rbnode_set_parent_and_flags(s, p, c_rbnode_flags(s) | C_RBNODE_RED);
+                if (c_rbnode_is_red(p)) {
+                        c_rbnode_set_parent_and_flags(p, c_rbnode_parent(p), c_rbnode_flags(p) & ~C_RBNODE_RED);
+                        return NULL;
+                }
+
+                *previous = p;
+                p = c_rbnode_parent(p);
+        }
+
+        return NULL;
+}
+
+static inline void c_rbnode_rebalance(CRBNode *n) {
+        CRBNode *previous = NULL;
+
+        /*
+         * Rebalance a tree after a node was removed. This function must be
+         * called on the parent of the leaf that was removed. It will first
+         * perform a recursive re-coloring on the parents of @n, until it
+         * either hits the tree-root, or a condition where a tree-rotation is
+         * needed to restore the RB-Tree invariants.
+         */
+
+        n = c_rbnode_rebalance_path(n, &previous);
+        if (n)
+                c_rbnode_rebalance_terminal(n, previous);
+}
+
+/**
+ * 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().
+ */
+_public_ void c_rbnode_unlink_stale(CRBNode *n) {
+        CRBTree *t;
+
+        assert(n);
+        assert(c_rbnode_is_linked(n));
+
+        /*
+         * There are three distinct cases during node removal of a tree:
+         *  * The node has no children, in which case it can simply be removed.
+         *  * The node has exactly one child, in which case the child displaces
+         *    its parent.
+         *  * The node has two children, in which case there is guaranteed to
+         *    be a successor to the node (successor being the node ordered
+         *    directly after it). This successor is the leftmost descendant of
+         *    the node's right child, so it cannot have a left child of its own.
+         *    Therefore, we can simply swap the node with its successor (including
+         *    color) and remove the node from its new place, which will be one of
+         *    the first two cases.
+         *
+         * Whenever the node we removed was black, we have to rebalance the
+         * tree. Note that this affects the actual node we _remove_, not @n (in
+         * case we swap it).
+         */
+
+        if (!n->left && !n->right) {
+                /*
+                 * Case 1.0
+                 * The node has no children, it is a leaf-node and we
+                 * can simply unlink it. If it was also black, we have
+                 * to rebalance.
+                 */
+                t = c_rbnode_pop_root(n);
+                c_rbnode_swap_child(n, NULL);
+                c_rbnode_push_root(NULL, t);
+
+                if (c_rbnode_is_black(n))
+                        c_rbnode_rebalance(c_rbnode_parent(n));
+        } else if (!n->left && n->right) {
+                /*
+                 * Case 1.1:
+                 * The node has exactly one child, and it is on the
+                 * right. The child *must* be red (otherwise, the right
+                 * path has more black nodes than the non-existing left
+                 * path), and the node to be removed must hence be
+                 * black. We simply replace the node with its child,
+                 * turning the red child black, and thus no rebalancing
+                 * is required.
+                 */
+                t = c_rbnode_pop_root(n);
+                c_rbnode_swap_child(n, n->right);
+                c_rbnode_set_parent_and_flags(n->right, c_rbnode_parent(n), c_rbnode_flags(n->right) & ~C_RBNODE_RED);
+                c_rbnode_push_root(n->right, t);
+        } else if (n->left && !n->right) {
+                /*
+                 * Case 1.2:
+                 * The node has exactly one child, and it is on the left. Treat
+                 * it as mirrored case of Case 1.1 (i.e., replace the node by
+                 * its child).
+                 */
+                t = c_rbnode_pop_root(n);
+                c_rbnode_swap_child(n, n->left);
+                c_rbnode_set_parent_and_flags(n->left, c_rbnode_parent(n), c_rbnode_flags(n->left) & ~C_RBNODE_RED);
+                c_rbnode_push_root(n->left, t);
+        } else /* if (n->left && n->right) */ {
+                CRBNode *s, *p, *c, *next = NULL;
+
+                /* Cache possible tree-root during tree-rotations. */
+                t = c_rbnode_pop_root(n);
+
+                /*
+                 * Case 1.3:
+                 * We are dealing with a full interior node with a child on
+                 * both sides. We want to find its successor and swap it,
+                 * then remove the node similar to Case 1. For performance
+                 * reasons we don't perform the full swap, but skip links
+                 * that are about to be removed, anyway.
+                 *
+                 * First locate the successor, remember its child and the
+                 * parent the original node should have been linked on,
+                 * before being removed. Then link up both the successor's
+                 * new children and old child.
+                 *
+                 *      s: successor
+                 *      p: parent
+                 *      c: right (and only potential) child of successor
+                 *      next: next node to rebalance on
+                 */
+                s = n->right;
+                if (!s->left) {
+                        /*
+                         * The immediate right child is the successor,
+                         * the successor's right child remains linked
+                         * as before.
+                         */
+                        p = s;
+                        c = s->right;
+                } else {
+                        s = c_rbnode_leftmost(s);
+                        p = c_rbnode_parent(s);
+                        c = s->right;
+
+                        /*
+                         * The new parent pointer of the successor's
+                         * child is set below.
+                         */
+                        c_rbtree_store(&p->left, c);
+
+                        c_rbtree_store(&s->right, n->right);
+                        c_rbnode_set_parent_and_flags(n->right, s, c_rbnode_flags(n->right));
+                }
+
+                /*
+                 * In both the above cases, the successor's left child
+                 * needs to be replaced with the left child of the node
+                 * that is being removed.
+                 */
+                c_rbtree_store(&s->left, n->left);
+                c_rbnode_set_parent_and_flags(n->left, s, c_rbnode_flags(n->left));
+
+                /*
+                 * As in cases 1.1 and 1.0 above, if successor was a
+                 * black leaf, we need to rebalance the tree, otherwise
+                 * it must have a red child, so simply recolor that black
+                 * and continue. Note that @next must be stored here, as
+                 * the original color of the successor is forgotten below.
+                 */
+                if (c)
+                        c_rbnode_set_parent_and_flags(c, p, c_rbnode_flags(c) & ~C_RBNODE_RED);
+                else
+                        next = c_rbnode_is_black(s) ? p : NULL;
+
+                /*
+                 * Update the successor, to inherit the parent and color
+                 * from the node being removed.
+                 */
+                if (c_rbnode_is_red(n))
+                        c_rbnode_set_parent_and_flags(s, c_rbnode_parent(n), c_rbnode_flags(s) | C_RBNODE_RED);
+                else
+                        c_rbnode_set_parent_and_flags(s, c_rbnode_parent(n), c_rbnode_flags(s) & ~C_RBNODE_RED);
+
+                /*
+                 * Update the parent of the node being removed. Note that this
+                 * needs to happen after the parent of the successor is set
+                 * above, as that call would clear the root pointer, if set.
+                 */
+                c_rbnode_swap_child(n, s);
+
+                /* Possibly restore saved tree-root. */
+                c_rbnode_push_root(s, t);
+
+                if (next)
+                        c_rbnode_rebalance(next);
+        }
+}
diff --git a/src/c-rbtree.h b/src/c-rbtree.h
new file mode 100644
index 0000000000..cb33fcf7a8
--- /dev/null
+++ b/src/c-rbtree.h
@@ -0,0 +1,430 @@
+#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.
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <assert.h>
+#include <stdalign.h>
+#include <stddef.h>
+
+typedef struct CRBNode CRBNode;
+typedef struct CRBTree CRBTree;
+
+/* implementation detail */
+#define C_RBNODE_RED                    (0x1UL)
+#define C_RBNODE_ROOT                   (0x2UL)
+#define C_RBNODE_UNUSED3                (0x4UL)
+#define C_RBNODE_FLAG_MASK              (0x7UL)
+
+/**
+ * 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.
+ *
+ * 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.
+ */
+struct CRBNode {
+        alignas(8) unsigned long __parent_and_flags;
+        CRBNode *left;
+        CRBNode *right;
+};
+
+#define C_RBNODE_INIT(_var) { .__parent_and_flags = (unsigned long)&(_var) }
+
+CRBNode *c_rbnode_leftmost(CRBNode *n);
+CRBNode *c_rbnode_rightmost(CRBNode *n);
+CRBNode *c_rbnode_leftdeepest(CRBNode *n);
+CRBNode *c_rbnode_rightdeepest(CRBNode *n);
+CRBNode *c_rbnode_next(CRBNode *n);
+CRBNode *c_rbnode_prev(CRBNode *n);
+CRBNode *c_rbnode_next_postorder(CRBNode *n);
+CRBNode *c_rbnode_prev_postorder(CRBNode *n);
+
+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
+ *
+ * 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.
+ *
+ * To initialize an RB-Tree, set it to NULL / all zero.
+ */
+struct CRBTree {
+        alignas(8) CRBNode *root;
+};
+
+#define C_RBTREE_INIT {}
+
+CRBNode *c_rbtree_first(CRBTree *t);
+CRBNode *c_rbtree_last(CRBTree *t);
+CRBNode *c_rbtree_first_postorder(CRBTree *t);
+CRBNode *c_rbtree_last_postorder(CRBTree *t);
+
+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
+ *
+ * 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.
+ *
+ * Use the 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
+ *
+ * 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.
+ *
+ * Return: Pointer to parent container, or NULL.
+ */
+#define c_rbnode_entry(_what, _t, _m) \
+        ((_t *)(void *)(((unsigned long)(void *)(_what) ?: \
+                         offsetof(_t, _m)) - offsetof(_t, _m)))
+
+/**
+ * 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.
+ *
+ * You should not call this on unlinked or uninitialized nodes! If you do, you
+ * better know its semantics.
+ *
+ * Return: Pointer to parent.
+ */
+static inline CRBNode *c_rbnode_parent(CRBNode *n) {
+        return (n->__parent_and_flags & C_RBNODE_ROOT) ?
+                        NULL :
+                        (void *)(n->__parent_and_flags & ~C_RBNODE_FLAG_MASK);
+}
+
+/**
+ * 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
+ * returns true.
+ *
+ * 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.
+ *
+ * Return: true if the node is linked, false if not.
+ */
+static inline _Bool c_rbnode_is_linked(CRBNode *n) {
+        return n && c_rbnode_parent(n) != n;
+}
+
+/**
+ * c_rbnode_unlink() - safely remove node from tree and reinitialize it
+ * @n:          node to remove, or NULL
+ *
+ * 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
+ */
+static inline void c_rbnode_unlink(CRBNode *n) {
+        if (c_rbnode_is_linked(n)) {
+                c_rbnode_unlink_stale(n);
+                c_rbnode_init(n);
+        }
+}
+
+/**
+ * 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.
+ */
+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
+ *
+ * This checks whether the passed RB-Tree is empty.
+ *
+ * Return: True if tree is empty, false otherwise.
+ */
+static inline _Bool c_rbtree_is_empty(CRBTree *t) {
+        return !t->root;
+}
+
+/**
+ * CRBCompareFunc - compare a node to a key
+ * @t:          tree where the node is linked to
+ * @k:          key to compare
+ * @n:          node to compare
+ *
+ * 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.
+ */
+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
+ * where duplicate entries are allowed, you better code your own lookup.
+ *
+ * Return: Pointer to matching node, or NULL.
+ */
+static inline CRBNode *c_rbtree_find_node(CRBTree *t, CRBCompareFunc f, const void *k) {
+        CRBNode *i;
+
+        assert(t);
+        assert(f);
+
+        i = t->root;
+        while (i) {
+                int v = f(t, (void *)k, i);
+                if (v < 0)
+                        i = i->left;
+                else if (v > 0)
+                        i = i->right;
+                else
+                        return i;
+        }
+
+        return NULL;
+}
+
+/**
+ * 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.
+ *
+ * Return: Pointer to found entry, NULL if not found.
+ */
+#define c_rbtree_find_entry(_t, _f, _k, _s, _m) \
+        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.
+ *
+ * If you want trees that allow duplicate nodes, you better code your own
+ * insertion function.
+ *
+ * Return: Pointer to slot to insert node, or NULL on conflicts.
+ */
+static inline CRBNode **c_rbtree_find_slot(CRBTree *t, CRBCompareFunc f, const void *k, CRBNode **p) {
+        CRBNode **i;
+
+        assert(t);
+        assert(f);
+        assert(p);
+
+        i = &t->root;
+        *p = NULL;
+        while (*i) {
+                int v = f(t, (void *)k, *i);
+                *p = *i;
+                if (v < 0)
+                        i = &(*i)->left;
+                else if (v > 0)
+                        i = &(*i)->right;
+                else
+                        return NULL;
+        }
+
+        return i;
+}
+
+/**
+ * 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.
+ */
+
+#define c_rbtree_for_each(_iter, _tree)                                                                 \
+        for (_iter = c_rbtree_first(_tree);                                                             \
+             _iter;                                                                                     \
+             _iter = c_rbnode_next(_iter))
+
+#define c_rbtree_for_each_entry(_iter, _tree, _m)                                                       \
+        for (_iter = c_rbnode_entry(c_rbtree_first(_tree), __typeof__(*_iter), _m);                     \
+             _iter;                                                                                     \
+             _iter = c_rbnode_entry(c_rbnode_next(&_iter->_m), __typeof__(*_iter), _m))
+
+#define c_rbtree_for_each_safe(_iter, _safe, _tree)                                                     \
+        for (_iter = c_rbtree_first(_tree), _safe = c_rbnode_next(_iter);                               \
+             _iter;                                                                                     \
+             _iter = _safe, _safe = c_rbnode_next(_safe))
+
+#define c_rbtree_for_each_entry_safe(_iter, _safe, _tree, _m)                                           \
+        for (_iter = c_rbnode_entry(c_rbtree_first(_tree), __typeof__(*_iter), _m),                     \
+             _safe = _iter ? c_rbnode_entry(c_rbnode_next(&_iter->_m), __typeof__(*_iter), _m) : NULL;  \
+             _iter;                                                                                     \
+             _iter = _safe,                                                                             \
+             _safe = _safe ? c_rbnode_entry(c_rbnode_next(&_safe->_m), __typeof__(*_iter), _m) : NULL)
+
+#define c_rbtree_for_each_postorder(_iter, _tree)                                                       \
+        for (_iter = c_rbtree_first_postorder(_tree);                                                   \
+             _iter;                                                                                     \
+             _iter = c_rbnode_next_postorder(_iter))                                                    \
+
+#define c_rbtree_for_each_entry_postorder(_iter, _tree, _m)                                             \
+        for (_iter = c_rbnode_entry(c_rbtree_first_postorder(_tree), __typeof__(*_iter), _m);           \
+             _iter;                                                                                     \
+             _iter = c_rbnode_entry(c_rbnode_next_postorder(&_iter->_m), __typeof__(*_iter), _m))
+
+#define c_rbtree_for_each_safe_postorder(_iter, _safe, _tree)                                           \
+        for (_iter = c_rbtree_first_postorder(_tree), _safe = c_rbnode_next_postorder(_iter);           \
+             _iter;                                                                                     \
+             _iter = _safe, _safe = c_rbnode_next_postorder(_safe))
+
+#define c_rbtree_for_each_entry_safe_postorder(_iter, _safe, _tree, _m)                                                 \
+        for (_iter = c_rbnode_entry(c_rbtree_first_postorder(_tree), __typeof__(*_iter), _m),                           \
+             _safe = _iter ? c_rbnode_entry(c_rbnode_next_postorder(&_iter->_m), __typeof__(*_iter), _m) : NULL;        \
+             _iter;                                                                                                     \
+             _iter = _safe,                                                                                             \
+             _safe = _safe ? c_rbnode_entry(c_rbnode_next_postorder(&_safe->_m), __typeof__(*_iter), _m) : NULL)
+
+#define c_rbtree_for_each_safe_postorder_unlink(_iter, _safe, _tree)                                    \
+        for (_iter = c_rbtree_first_postorder(_tree), _safe = c_rbnode_next_postorder(_iter);           \
+             _iter ? ((*_iter = (CRBNode)C_RBNODE_INIT(*_iter)), 1) : (((_tree)->root = NULL), 0);      \
+             _iter = _safe, _safe = c_rbnode_next_postorder(_safe))                                     \
+
+#define c_rbtree_for_each_entry_safe_postorder_unlink(_iter, _safe, _tree, _m)                                          \
+        for (_iter = c_rbnode_entry(c_rbtree_first_postorder(_tree), __typeof__(*_iter), _m),                           \
+             _safe = _iter ? c_rbnode_entry(c_rbnode_next_postorder(&_iter->_m), __typeof__(*_iter), _m) : NULL;        \
+             _iter ? ((_iter->_m = (CRBNode)C_RBNODE_INIT(_iter->_m)), 1) : (((_tree)->root = NULL), 0);                \
+             _iter = _safe,                                                                                             \
+             _safe = _safe ? c_rbnode_entry(c_rbnode_next_postorder(&_safe->_m), __typeof__(*_iter), _m) : NULL)
+
+#ifdef __cplusplus
+}
+#endif
diff --git a/src/libcrbtree.sym b/src/libcrbtree.sym
new file mode 100644
index 0000000000..e7b801b81a
--- /dev/null
+++ b/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/meson.build b/src/meson.build
new file mode 100644
index 0000000000..47ccf63aaa
--- /dev/null
+++ b/src/meson.build
@@ -0,0 +1,69 @@
+#
+# target: libcrbtree.so
+#
+
+libcrbtree_symfile = join_paths(meson.current_source_dir(), 'libcrbtree.sym')
+
+libcrbtree_private = static_library(
+        'crbtree-private',
+        [
+                'c-rbtree.c',
+        ],
+        c_args: [
+                '-fvisibility=hidden',
+                '-fno-common',
+        ],
+        pic: true,
+)
+
+libcrbtree_shared = shared_library(
+        'crbtree',
+        objects: libcrbtree_private.extract_all_objects(),
+        install: not meson.is_subproject(),
+        soversion: 0,
+        link_depends: libcrbtree_symfile,
+        link_args: [
+                '-Wl,--no-undefined',
+                '-Wl,--version-script=@0@'.format(libcrbtree_symfile),
+        ],
+)
+
+libcrbtree_dep = declare_dependency(
+        include_directories: include_directories('.'),
+        link_with: libcrbtree_private,
+        version: meson.project_version(),
+)
+
+if not meson.is_subproject()
+        install_headers('c-rbtree.h')
+
+        mod_pkgconfig.generate(
+                libraries: libcrbtree_shared,
+                version: meson.project_version(),
+                name: 'libcrbtree',
+                filebase: 'libcrbtree',
+                description: project_description,
+        )
+endif
+
+#
+# target: test-*
+#
+
+test_api = executable('test-api', ['test-api.c'], link_with: libcrbtree_shared)
+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)
+
+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)
diff --git a/src/test-api.c b/src/test-api.c
new file mode 100644
index 0000000000..55c37af6c4
--- /dev/null
+++ b/src/test-api.c
@@ -0,0 +1,108 @@
+/*
+ * 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/test-basic.c b/src/test-basic.c
new file mode 100644
index 0000000000..534a10966f
--- /dev/null
+++ b/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 <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;
+
+        assert(t);
+        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 */
+                assert(n > o);
+                o = n;
+
+                /* verify consistency */
+                assert(!n->right || c_rbnode_parent(n->right) == n);
+                assert(!n->left || c_rbnode_parent(n->left) == n);
+
+                /* verify 2) */
+                if (!c_rbnode_parent(n))
+                        assert(c_rbnode_is_black(n));
+
+                if (c_rbnode_is_red(n)) {
+                        /* verify 4) */
+                        assert(!n->left || c_rbnode_is_black(n->left));
+                        assert(!n->right || c_rbnode_is_black(n->right));
+                } else {
+                        /* verify 1) */
+                        assert(c_rbnode_is_black(n));
+                }
+
+                /* verify 5) */
+                if (!n->left && !n->right)
+                        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;
+
+        assert(t);
+        assert(n);
+        assert(!c_rbnode_is_linked(n));
+
+        i = &t->root;
+        p = NULL;
+        while (*i) {
+                p = *i;
+                if (n < *i) {
+                        i = &(*i)->left;
+                } else {
+                        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]));
+                assert(nodes[i]);
+                c_rbnode_init(nodes[i]);
+        }
+
+        /* shuffle nodes and validate *empty* tree */
+        shuffle(nodes, sizeof(nodes) / sizeof(*nodes));
+        n = validate(&t);
+        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);
+                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);
+                assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
+        }
+
+        /* shuffle nodes and validate *empty* tree again */
+        shuffle(nodes, sizeof(nodes) / sizeof(*nodes));
+        n = validate(&t);
+        assert(n == 0);
+
+        /* add all nodes again */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                insert(&t, nodes[i]);
+                n = validate(&t);
+                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);
+                        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);
+                        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);
+                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/test-map.c b/src/test-map.c
new file mode 100644
index 0000000000..3601ee495e
--- /dev/null
+++ b/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 <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]));
+                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) {
+                assert(!c_rbnode_is_linked(&nodes[i]->rb));
+                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);
+                assert(slot);
+                c_rbtree_add(&t, p, slot, &nodes[i]->rb);
+
+                assert(c_rbnode_is_linked(&nodes[i]->rb));
+                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;
+                assert(!node_from_rb(p)->marker);
+                node_from_rb(p)->marker = 1;
+
+                assert(v <= node_from_rb(p)->key);
+                v = node_from_rb(p)->key;
+
+                assert(!c_rbnode_next(p) || p == c_rbnode_prev(c_rbnode_next(p)));
+        }
+        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;
+                assert(node_from_rb(p)->marker);
+                node_from_rb(p)->marker = 0;
+
+                assert(v >= node_from_rb(p)->key);
+                v = node_from_rb(p)->key;
+        }
+        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;
+                assert(!node_from_rb(p)->marker);
+                assert(!c_rbnode_parent(p) || !node_from_rb(c_rbnode_parent(p))->marker);
+                assert(!p->left || node_from_rb(p->left)->marker);
+                assert(!p->right || node_from_rb(p->right)->marker);
+                node_from_rb(p)->marker = 1;
+
+                assert(!c_rbnode_next_postorder(p) || p == c_rbnode_prev_postorder(c_rbnode_next_postorder(p)));
+        }
+        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;
+                assert(node_from_rb(p)->marker);
+                assert(!c_rbnode_parent(p) || !node_from_rb(c_rbnode_parent(p))->marker);
+                assert(!p->left || node_from_rb(p->left)->marker);
+                assert(!p->right || node_from_rb(p->right)->marker);
+                node_from_rb(p)->marker = 0;
+        }
+        assert(i == sizeof(nodes) / sizeof(*nodes));
+
+        /* verify in-order traversal works via helper */
+        i = 0;
+        v = 0;
+        c_rbtree_for_each(p, &t) {
+                ++i;
+                assert(!node_from_rb(p)->marker);
+                node_from_rb(p)->marker = 1;
+
+                assert(v <= node_from_rb(p)->key);
+                v = node_from_rb(p)->key;
+
+                assert(!c_rbnode_next(p) || p == c_rbnode_prev(c_rbnode_next(p)));
+        }
+        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;
+                assert(n->marker);
+                n->marker = 0;
+
+                assert(v <= n->key);
+                v = n->key;
+        }
+        assert(i == sizeof(nodes) / sizeof(*nodes));
+
+        /* verify post-order traversal works via helper */
+        i = 0;
+        c_rbtree_for_each_postorder(p, &t) {
+                ++i;
+                assert(!node_from_rb(p)->marker);
+                assert(!c_rbnode_parent(p) || !node_from_rb(c_rbnode_parent(p))->marker);
+                assert(!p->left || node_from_rb(p->left)->marker);
+                assert(!p->right || node_from_rb(p->right)->marker);
+                node_from_rb(p)->marker = 1;
+
+                assert(!c_rbnode_next_postorder(p) || p == c_rbnode_prev_postorder(c_rbnode_next_postorder(p)));
+        }
+        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;
+                assert(n->marker);
+                assert(!c_rbnode_parent(&n->rb) || node_from_rb(c_rbnode_parent(&n->rb))->marker);
+                assert(!n->rb.left || !node_from_rb(n->rb.left)->marker);
+                assert(!n->rb.right || !node_from_rb(n->rb.right)->marker);
+                n->marker = 0;
+        }
+        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) {
+                assert(c_rbnode_is_linked(&nodes[i]->rb));
+                assert(nodes[i] == c_rbtree_find_entry(&t, test_compare, (void *)nodes[i]->key, Node, rb));
+
+                c_rbnode_unlink(&nodes[i]->rb);
+
+                assert(!c_rbnode_is_linked(&nodes[i]->rb));
+                assert(!c_rbtree_find_entry(&t, test_compare, (void *)nodes[i]->key, Node, rb));
+        }
+        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);
+                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);
+        }
+        assert(i == sizeof(nodes) / sizeof(*nodes));
+        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);
+                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);
+        }
+        assert(i == sizeof(nodes) / sizeof(*nodes));
+        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);
+                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;
+                assert(!c_rbnode_is_linked(p));
+        }
+        assert(i == sizeof(nodes) / sizeof(*nodes));
+        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);
+                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;
+                assert(!c_rbnode_is_linked(&n->rb));
+        }
+        assert(i == sizeof(nodes) / sizeof(*nodes));
+        assert(c_rbtree_is_empty(&t));
+
+        /* free nodes again */
+        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
+                assert(!nodes[i]->marker);
+                free(nodes[i]);
+        }
+
+        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/test-misc.c b/src/test-misc.c
new file mode 100644
index 0000000000..e5b3289c3c
--- /dev/null
+++ b/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 <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;
+
+        assert(t);
+        assert(n);
+        assert(!c_rbnode_is_linked(n));
+
+        i = &t->root;
+        p = NULL;
+        while (*i) {
+                p = *i;
+                if (n < *i) {
+                        i = &(*i)->left;
+                } else {
+                        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]);
+        }
+
+        assert(!c_rbtree_is_empty(&t1));
+        assert(c_rbtree_is_empty(&t2));
+
+        c_rbtree_move(&t2, &t1);
+
+        assert(c_rbtree_is_empty(&t1));
+        assert(!c_rbtree_is_empty(&t2));
+
+        while (t2.root)
+                c_rbnode_unlink(t2.root);
+
+        assert(c_rbtree_is_empty(&t1));
+        assert(c_rbtree_is_empty(&t2));
+}
+
+int main(int argc, char **argv) {
+        test_move();
+
+        return 0;
+}
diff --git a/src/test-parallel.c b/src/test-parallel.c
new file mode 100644
index 0000000000..4513d9ece2
--- /dev/null
+++ b/src/test-parallel.c
@@ -0,0 +1,384 @@
+/*
+ * 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 <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);
+        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)
+                assert(!c_rbnode_is_linked(ctx->nodes[i]));
+
+        r = munmap(ctx->map, ctx->mapsize);
+        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 */
+                assert(!fetch_visit(n));
+
+                /* verify @n is a valid node */
+                for (i = 0; i < ctx->n_nodes; ++i)
+                        if (n == ctx->nodes[i])
+                                break;
+                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();
+        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;
+
+                        assert(r >= 0);
+                        break;
+
+                case SIGURG:
+                        n_event |= 0x2;
+                        test_parent_middle(&ctx);
+
+                        /* step child */
+                        r = ptrace(PTRACE_SINGLESTEP, pid, 0, 0);
+                        assert(r >= 0);
+                        break;
+
+                case SIGUSR2:
+                        n_event |= 0x4;
+                        test_parent_end(&ctx);
+
+                        /* continue child */
+                        r = ptrace(PTRACE_CONT, pid, 0, 0);
+                        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);
+                        assert(r >= 0);
+                        break;
+
+                default:
+                        assert(0);
+                        break;
+                }
+        }
+
+        /* verify our child exited cleanly */
+        assert(r == pid);
+        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:
+                assert(0);
+                break;
+        }
+
+        /* verify we hit all child states */
+        assert(n_event & 0x1);
+        assert(n_event & 0x2);
+        assert(n_event & 0x4);
+        assert(n_instr > 0);
+
+        return 0;
+}
+
+int main(int argc, char **argv) {
+        unsigned int i;
+        int r;
+
+        if (!getenv("CRBTREE_TEST_PTRACE"))
+                return 77;
+
+        /* 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/test-posix.c b/src/test-posix.c
new file mode 100644
index 0000000000..213d85fefe
--- /dev/null
+++ b/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 <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);
+        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);
+        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);
+        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:
+                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]));
+                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);
+                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;
+
+                assert(v <= node_from_rb(p)->key);
+                v = node_from_rb(p)->key;
+        }
+        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)
+                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)
+                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;
+}