From 5534ae8a76cd3e0823b5a7bd3d5e9ee8939efec1 Mon Sep 17 00:00:00 2001 From: David Herrmann Date: Sun, 29 Nov 2015 18:18:45 +0100 Subject: [PATCH] crbtree: implement tree operations This adds the basic build-system and implements the RB-Tree API. It also adds a couple of tests to verify the RB-Tree works as expected. Signed-off-by: David Herrmann --- .gitignore | 31 ++ .vimrc | 4 + COPYING | 0 LICENSE.LGPL2.1 | 502 ++++++++++++++++++++++++++++++++ Makefile.am | 112 +++++++ autogen.sh | 31 ++ configure.ac | 154 ++++++++++ m4/attributes.m4 | 77 +++++ src/crbtree-private.h | 54 ++++ src/crbtree.c | 663 ++++++++++++++++++++++++++++++++++++++++++ src/crbtree.h | 178 ++++++++++++ src/libcrbtree.sym | 30 ++ src/test-api.c | 67 +++++ src/test-basic.c | 261 +++++++++++++++++ 14 files changed, 2164 insertions(+) create mode 100644 .gitignore create mode 100644 .vimrc create mode 100644 COPYING create mode 100644 LICENSE.LGPL2.1 create mode 100644 Makefile.am create mode 100755 autogen.sh create mode 100644 configure.ac create mode 100644 m4/attributes.m4 create mode 100644 src/crbtree-private.h create mode 100644 src/crbtree.c create mode 100644 src/crbtree.h create mode 100644 src/libcrbtree.sym create mode 100644 src/test-api.c create mode 100644 src/test-basic.c diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..8069b6f --- /dev/null +++ b/.gitignore @@ -0,0 +1,31 @@ +*.a +*.la +*.lo +*.log +*.m4 +*.o +*.stamp +*.swp +*.trs +*~ + +/.config.args +/.libs/ +/*.tar.xz +/Makefile +/Makefile.in +/autom4te.cache/ +/aclocal.m4 +/build-aux/ +/config.h +/config.h.in +/config.log +/config.status +/configure +/libtool +!/m4/attributes.m4 +/src/.deps/ +/src/.dirstamp +/stamp-* +/test-api +/test-basic diff --git a/.vimrc b/.vimrc new file mode 100644 index 0000000..366fbdc --- /dev/null +++ b/.vimrc @@ -0,0 +1,4 @@ +" 'set exrc' in ~/.vimrc will read .vimrc from the current directory +set tabstop=8 +set shiftwidth=8 +set expandtab diff --git a/COPYING b/COPYING new file mode 100644 index 0000000..e69de29 diff --git a/LICENSE.LGPL2.1 b/LICENSE.LGPL2.1 new file mode 100644 index 0000000..4362b49 --- /dev/null +++ b/LICENSE.LGPL2.1 @@ -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. + + + Copyright (C) + + 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. + + , 1 April 1990 + Ty Coon, President of Vice + +That's all there is to it! diff --git a/Makefile.am b/Makefile.am new file mode 100644 index 0000000..a460a7f --- /dev/null +++ b/Makefile.am @@ -0,0 +1,112 @@ +# ------------------------------------------------------------------------------ +# main + +ACLOCAL_AMFLAGS = -I m4 ${ACLOCAL_FLAGS} +AM_MAKEFLAGS = --no-print-directory +AUTOMAKE_OPTIONS = color-tests parallel-tests + +GCC_COLORS ?= 'ooh, shiny!' +export GCC_COLORS + +SUBDIRS = . + +# remove targets if the command fails +.DELETE_ON_ERROR: + +# keep intermediate files +.SECONDARY: + +# Keep the test-suite.log and Makefile around at all times +.PRECIOUS: $(TEST_SUITE_LOG) Makefile + +CLEANFILES = $(BUILT_SOURCES) +DISTCLEANFILES = +EXTRA_DIST = +BUILT_SOURCES = +lib_LTLIBRARIES = +noinst_LTLIBRARIES = +bin_PROGRAMS = +noinst_PROGRAMS = +check_PROGRAMS = +TESTS = +default_tests = + +AM_CPPFLAGS = \ + -include $(top_builddir)/config.h \ + -I $(top_srcdir)/src \ + -I $(top_builddir)/src \ + $(OUR_CPPFLAGS) + +AM_CFLAGS = $(OUR_CFLAGS) +AM_LDFLAGS = $(OUR_LDFLAGS) + +# ------------------------------------------------------------------------------ +# libcrbtree-private (used for our tests, which access internal data) + +noinst_LTLIBRARIES += \ + libcrbtree-private.la + +libcrbtree_private_la_SOURCES = \ + src/crbtree.h \ + src/crbtree-private.h \ + src/crbtree.c + +libcrbtree_private_la_CFLAGS = \ + $(AM_CFLAGS) + +libcrbtree_private_la_CPPFLAGS = \ + $(AM_CPPFLAGS) \ + -UNDEBUG + +libcrbtree_private_la_LDFLAGS = \ + $(AM_LDFLAGS) + +# ------------------------------------------------------------------------------ +# libcrbtree + +lib_LTLIBRARIES += \ + libcrbtree.la + +libcrbtree_la_SOURCES = \ + $(libcrbtree_private_la_SOURCES) + +libcrbtree_la_CFLAGS = \ + $(AM_CFLAGS) + +libcrbtree_la_CPPFLAGS = \ + $(AM_CPPFLAGS) + +libcrbtree_la_LDFLAGS = \ + $(AM_LDFLAGS) \ + -version-info $(LIBCRBTREE_CURRENT):$(LIBCRBTREE_REVISION):$(LIBCRBTREE_AGE) \ + -Wl,--version-script=$(top_srcdir)/src/libcrbtree.sym + +# ------------------------------------------------------------------------------ +# test-api + +default_tests += \ + test-api + +test_api_SOURCES = \ + src/test-api.c + +test_api_LDADD = \ + libcrbtree.la # explicitly linked against public library + +# ------------------------------------------------------------------------------ +# test-basic + +default_tests += \ + test-basic + +test_basic_SOURCES = \ + src/test-basic.c + +test_basic_LDADD = \ + libcrbtree-private.la + +# ------------------------------------------------------------------------------ +# test suite + +check_PROGRAMS += $(default_tests) +TESTS += $(default_tests) diff --git a/autogen.sh b/autogen.sh new file mode 100755 index 0000000..d969f8d --- /dev/null +++ b/autogen.sh @@ -0,0 +1,31 @@ +#!/bin/sh + +set -e + +oldpwd=$(pwd) +topdir=$(dirname $0) +cd $topdir + +autoreconf --force --install --symlink + +if [ -f "$topdir/.config.args" ]; then + args="$args $(cat $topdir/.config.args)" +fi + +cd $oldpwd + +if [ "x$1" = "xc" ]; then + $topdir/configure --enable-debug $args + make clean +elif [ "x$1" = "xl" ]; then + $topdir/configure CC=clang $args + make clean +else + echo + echo "----------------------------------------------------------------" + echo "Initialized build system. For a common configuration please run:" + echo "----------------------------------------------------------------" + echo + echo "$topdir/configure $args" + echo +fi diff --git a/configure.ac b/configure.ac new file mode 100644 index 0000000..02acd7e --- /dev/null +++ b/configure.ac @@ -0,0 +1,154 @@ +# ------------------------------------------------------------------------------ +# versions + +AC_PREREQ([2.64]) + +AC_INIT([crbtree], + [1], + [http://www.github.com/dvdhrm/crbtree], + [crbtree], + [http://www.github.com/dvdhrm/crbtree]) + +AC_SUBST([LIBCRBTREE_CURRENT], 0) +AC_SUBST([LIBCRBTREE_AGE], 0) +AC_SUBST([LIBCRBTREE_REVISION], 1) + +# ------------------------------------------------------------------------------ +# main + +AC_CONFIG_SRCDIR([src/crbtree.h]) +AC_CONFIG_MACRO_DIR([m4]) +AC_CONFIG_HEADERS([config.h]) +AC_CONFIG_AUX_DIR([build-aux]) + +AC_USE_SYSTEM_EXTENSIONS +AC_SYS_LARGEFILE +AM_MAINTAINER_MODE([enable]) +AM_INIT_AUTOMAKE([foreign 1.11 -Wall -Wno-portability silent-rules tar-pax no-dist-gzip dist-xz subdir-objects parallel-tests]) +AM_SILENT_RULES([yes]) +AC_CANONICAL_HOST +AC_DEFINE_UNQUOTED([CANONICAL_HOST], "$host", [Canonical host string.]) + +AC_PROG_MKDIR_P +AC_PROG_LN_S +AC_PROG_SED +AC_PROG_GREP +AC_PROG_AWK +AC_PROG_CC_C99 + +LT_PREREQ(2.2) +LT_INIT([disable-static]) + +AC_PATH_PROG([M4], [m4]) +AC_PATH_PROG([XSLTPROC], [xsltproc]) + +AS_IF([! ln --relative --help > /dev/null 2>&1], [AC_MSG_ERROR([*** ln doesn't support --relative ***])]) + +# ------------------------------------------------------------------------------ +# arguments + +AC_ARG_ENABLE(debug, AS_HELP_STRING([--enable-debug], [enable debug options])) + +# ------------------------------------------------------------------------------ +# toolchain + +CC_CHECK_FLAGS_APPEND([with_cflags], [CFLAGS], [\ + -pipe \ + -Wall \ + -Wextra \ + -Wno-inline \ + -Wundef \ + "-Wformat=2 -Wformat-security -Wformat-nonliteral" \ + -Wlogical-op \ + -Wsign-compare \ + -Wmissing-include-dirs \ + -Wold-style-definition \ + -Wpointer-arith \ + -Winit-self \ + -Wdeclaration-after-statement \ + -Wfloat-equal \ + -Wsuggest-attribute=noreturn \ + -Wmissing-prototypes \ + -Wstrict-prototypes \ + -Wredundant-decls \ + -Wmissing-declarations \ + -Wmissing-noreturn \ + -Wshadow \ + -Wendif-labels \ + -Wstrict-aliasing=2 \ + -Wwrite-strings \ + -Wno-long-long \ + -Wno-overlength-strings \ + -Wno-unused-parameter \ + -Wno-missing-field-initializers \ + -Wno-unused-result \ + -Werror=overflow \ + -Wdate-time \ + -Wnested-externs \ + -ffast-math \ + -fno-common \ + -fdiagnostics-show-option \ + -fno-strict-aliasing \ + -fvisibility=hidden \ + -ffunction-sections \ + -fdata-sections \ + -fstack-protector \ + -fstack-protector-strong \ + -fPIE \ + --param=ssp-buffer-size=4]) + +AS_CASE([$CC], [*clang*], + [CC_CHECK_FLAGS_APPEND([with_cppflags], [CPPFLAGS], [ \ + -Wno-typedef-redefinition \ + -Wno-gnu-variable-sized-type-not-at-end \ + ])]) + +CC_CHECK_FLAGS_APPEND([with_ldflags], [LDFLAGS], [\ + -Wl,--as-needed \ + -Wl,--no-undefined \ + -Wl,--gc-sections \ + -Wl,-z,relro \ + -Wl,-z,now \ + -pie]) + +AS_IF([test "x$enable_debug" = "xyes"], + [ + CC_CHECK_FLAGS_APPEND([with_cflags], [CFLAGS], [ \ + -g \ + -O0 \ + -ftrapv]) + ], [ + CC_CHECK_FLAGS_APPEND([with_cppflags], [CPPFLAGS], [\ + -Wp,-D_FORTIFY_SOURCE=2 \ + -DNDEBUG]) + ]) + +AC_SUBST([OUR_CFLAGS], "$with_cflags") +AC_SUBST([OUR_CPPFLAGS], "$with_cppflags") +AC_SUBST([OUR_LDFLAGS], "$with_ldflags") + +# ------------------------------------------------------------------------------ +# system features + +# This makes sure pkg.m4 is available. +m4_pattern_forbid([^_?PKG_[A-Z_]+$],[*** pkg.m4 missing, please install pkg-config]) + +# ------------------------------------------------------------------------------ +# report + +AC_CONFIG_FILES([Makefile]) + +AC_OUTPUT +AC_MSG_RESULT([ + $PACKAGE_NAME $VERSION ($LIBCRBTREE_CURRENT.$LIBCRBTREE_AGE.$LIBCRBTREE_REVISION) + debug: ${enable_debug} + + prefix: ${prefix} + exec_prefix: ${exec_prefix} + includedir: ${includedir} + libdir: ${libdir} + + CFLAGS: ${OUR_CFLAGS} ${CFLAGS} + CPPFLAGS: ${OUR_CPPFLAGS} ${CPPFLAGS} + LDFLAGS: ${OUR_LDFLAGS} ${LDFLAGS} +]) diff --git a/m4/attributes.m4 b/m4/attributes.m4 new file mode 100644 index 0000000..e145f49 --- /dev/null +++ b/m4/attributes.m4 @@ -0,0 +1,77 @@ +dnl Macros to check the presence of generic (non-typed) symbols. +dnl Copyright (c) 2006-2008 Diego Pettenò +dnl Copyright (c) 2006-2008 xine project +dnl Copyright (c) 2012 Lucas De Marchi +dnl +dnl This program is free software; you can redistribute it and/or modify +dnl it under the terms of the GNU General Public License as published by +dnl the Free Software Foundation; either version 2, or (at your option) +dnl any later version. +dnl +dnl This program is distributed in the hope that it will be useful, +dnl but WITHOUT ANY WARRANTY; without even the implied warranty of +dnl MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +dnl GNU General Public License for more details. +dnl +dnl You should have received a copy of the GNU General Public License +dnl along with this program; if not, write to the Free Software +dnl Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA +dnl 02110-1301, USA. +dnl +dnl As a special exception, the copyright owners of the +dnl macro gives unlimited permission to copy, distribute and modify the +dnl configure scripts that are the output of Autoconf when processing the +dnl Macro. You need not follow the terms of the GNU General Public +dnl License when using or distributing such scripts, even though portions +dnl of the text of the Macro appear in them. The GNU General Public +dnl License (GPL) does govern all other use of the material that +dnl constitutes the Autoconf Macro. +dnl +dnl This special exception to the GPL applies to versions of the +dnl Autoconf Macro released by this project. When you make and +dnl distribute a modified version of the Autoconf Macro, you may extend +dnl this special exception to the GPL to apply to your modified version as +dnl well. + +dnl Check if FLAG in ENV-VAR is supported by compiler and append it +dnl to WHERE-TO-APPEND variable. Note that we invert -Wno-* checks to +dnl -W* as gcc cannot test for negated warnings. +dnl CC_CHECK_FLAG_APPEND([WHERE-TO-APPEND], [ENV-VAR], [FLAG]) + +AC_DEFUN([CC_CHECK_FLAG_APPEND], [ + AC_CACHE_CHECK([if $CC supports flag $3 in envvar $2], + AS_TR_SH([cc_cv_$2_$3]), + [eval "AS_TR_SH([cc_save_$2])='${$2}'" + eval "AS_TR_SH([$2])='-Werror `echo "$3" | sed 's/^-Wno-/-W/'`'" + AC_LINK_IFELSE([AC_LANG_SOURCE([int main(void) { return 0; } ])], + [eval "AS_TR_SH([cc_cv_$2_$3])='yes'"], + [eval "AS_TR_SH([cc_cv_$2_$3])='no'"]) + eval "AS_TR_SH([$2])='$cc_save_$2'"]) + + AS_IF([eval test x$]AS_TR_SH([cc_cv_$2_$3])[ = xyes], + [eval "$1='${$1} $3'"]) +]) + +dnl CC_CHECK_FLAGS_APPEND([WHERE-TO-APPEND], [ENV-VAR], [FLAG1 FLAG2]) +AC_DEFUN([CC_CHECK_FLAGS_APPEND], [ + for flag in $3; do + CC_CHECK_FLAG_APPEND($1, $2, $flag) + done +]) + +dnl Check if the flag is supported by linker (cacheable) +dnl CC_CHECK_LDFLAGS([FLAG], [ACTION-IF-FOUND],[ACTION-IF-NOT-FOUND]) +AC_DEFUN([CC_CHECK_LDFLAGS], [ + AC_CACHE_CHECK([if $CC supports $1 flag], + AS_TR_SH([cc_cv_ldflags_$1]), + [ac_save_LDFLAGS="$LDFLAGS" + LDFLAGS="$LDFLAGS $1" + AC_LINK_IFELSE([int main() { return 1; }], + [eval "AS_TR_SH([cc_cv_ldflags_$1])='yes'"], + [eval "AS_TR_SH([cc_cv_ldflags_$1])="]) + LDFLAGS="$ac_save_LDFLAGS" + ]) + + AS_IF([eval test x$]AS_TR_SH([cc_cv_ldflags_$1])[ = xyes], + [$2], [$3]) +]) diff --git a/src/crbtree-private.h b/src/crbtree-private.h new file mode 100644 index 0000000..417ff75 --- /dev/null +++ b/src/crbtree-private.h @@ -0,0 +1,54 @@ +#pragma once + +/*** + This file is part of crbtree. See COPYING for details. + + crbtree 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. + + crbtree 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 crbtree; If not, see . +***/ + +/* + * Private definitions + * This file contains private definitions for the RB-Tree implementation, but + * which are used by our test-suite. + */ + +#include +#include "crbtree.h" + +/* + * Macros + */ + +#define _public_ __attribute__((__visibility__("default"))) + +/* + * Nodes + */ + +enum { + C_RBNODE_RED = 0, + C_RBNODE_BLACK = 1, +}; + +static inline unsigned long c_rbnode_color(CRBNode *n) { + return (unsigned long)n->__parent_and_color & 1UL; +} + +static inline _Bool c_rbnode_is_red(CRBNode *n) { + return c_rbnode_color(n) == C_RBNODE_RED; +} + +static inline _Bool c_rbnode_is_black(CRBNode *n) { + return c_rbnode_color(n) == C_RBNODE_BLACK; +} diff --git a/src/crbtree.c b/src/crbtree.c new file mode 100644 index 0000000..564bab2 --- /dev/null +++ b/src/crbtree.c @@ -0,0 +1,663 @@ +/*** + This file is part of crbtree. See COPYING for details. + + crbtree 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. + + crbtree 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 crbtree; If not, see . +***/ + +/* + * 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_rbtree_swap_child() + * c_rbtree_set_parent_and_color() + * 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 +#include +#include "crbtree.h" +#include "crbtree-private.h" + +/** + * 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_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_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); +} + +/* + * Set the color and parent of a node. This should be treated as a simple + * assignment of the 'color' 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_color(CRBNode *n, CRBNode *p, unsigned long c) { + assert(!((unsigned long)p & 1)); + assert(c < 2); + n->__parent_and_color = (CRBNode*)((unsigned long)p | c); +} + +/* same as c_rbnode_set_parent_and_color(), but keeps the current parent */ +static inline void c_rbnode_set_color(CRBNode *n, unsigned long c) { + c_rbnode_set_parent_and_color(n, c_rbnode_parent(n), c); +} + +/* same as c_rbnode_set_parent_and_color(), but keeps the current color */ +static inline void c_rbnode_set_parent(CRBNode *n, CRBNode *p) { + c_rbnode_set_parent_and_color(n, p, c_rbnode_color(n)); +} + +/* + * This function partially replaces an existing child pointer to a new one. The + * existing child must be given as @old, the new child as @new. @p must be the + * parent of @old (or NULL if it has no parent). + * This function ensures that the parent of @old now points to @new. However, + * it does *NOT* change the parent pointer of @new. The caller must ensure + * this. + * If @p is NULL, this function ensures that the root-pointer is adjusted + * instead (given as @t). + */ +static inline void c_rbtree_swap_child(CRBTree *t, CRBNode *p, CRBNode *old, CRBNode *new) { + if (p) { + if (p->left == old) + p->left = new; + else + p->right = new; + } else { + t->root = new; + } +} + +static inline CRBNode *c_rbtree_paint_one(CRBTree *t, CRBNode *n) { + CRBNode *p, *g, *gg, *u, *x; + + /* + * Paint a single node according to RB-Tree rules. The node must + * already be linked into the tree and painted red. + * We repaint the node or rotate the tree, if required. In case a + * recursive repaint is required, the next node to be re-painted + * is returned. + * p: parent + * g: grandparent + * gg: grandgrandparent + * u: uncle + * x: temporary + */ + + /* node is red, so we can access the parent directly */ + p = n->__parent_and_color; + + 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_color(n, p, C_RBNODE_BLACK); + n = 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. */ + n = NULL; + } else if (p == p->__parent_and_color->left) { /* parent is red, so grandparent exists */ + g = p->__parent_and_color; + gg = c_rbnode_parent(g); + u = g->right; + + if (u && c_rbnode_is_red(u)) { + /* Case 3: + * Parent and uncle are both red. We know the + * grandparent must be black then. Repaint parent and + * uncle black, the grandparent red and recurse into + * the grandparent. */ + c_rbnode_set_parent_and_color(p, g, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(u, g, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(g, gg, C_RBNODE_RED); + n = g; + } else { + /* parent is red, uncle is black */ + + if (n == p->right) { + /* Case 4: + * We're the right child. Rotate on parent to + * become left child, so we can handle it the + * same as case 5. */ + x = n->left; + p->right = n->left; + n->left = p; + if (x) + c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(p, n, C_RBNODE_RED); + p = n; + } + + /* 'n' is invalid from here on! */ + n = NULL; + + /* Case 5: + * We're the red left child or a red parent, black + * grandparent and uncle. Rotate on grandparent and + * switch color with parent. Number of black nodes on + * each path stays the same, but we got rid of the + * double red path. As the grandparent is still black, + * we're done. */ + x = p->right; + g->left = x; + p->right = g; + if (x) + c_rbnode_set_parent_and_color(x, g, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(p, gg, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(g, p, C_RBNODE_RED); + c_rbtree_swap_child(t, gg, g, p); + } + } else /* if (p == p->__parent_and_color->left) */ { /* same as above, but mirrored */ + g = p->__parent_and_color; + gg = c_rbnode_parent(g); + u = g->left; + + if (u && c_rbnode_is_red(u)) { + c_rbnode_set_parent_and_color(p, g, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(u, g, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(g, gg, C_RBNODE_RED); + n = g; + } else { + if (n == p->left) { + x = n->right; + p->left = n->right; + n->right = p; + if (x) + c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(p, n, C_RBNODE_RED); + p = n; + } + + n = NULL; + + x = p->left; + g->right = x; + p->left = g; + if (x) + c_rbnode_set_parent_and_color(x, g, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(p, gg, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(g, p, C_RBNODE_RED); + c_rbtree_swap_child(t, gg, g, p); + } + } + + return n; +} + +static inline void c_rbtree_paint(CRBTree *t, CRBNode *n) { + assert(t); + assert(n); + + while (n) + n = c_rbtree_paint_one(t, 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_rbtree_remove_init(). + * 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_color(n, p, C_RBNODE_RED); + n->left = n->right = NULL; + *l = n; + + c_rbtree_paint(t, n); +} + +static inline CRBNode *c_rbtree_rebalance_one(CRBTree *t, CRBNode *p, CRBNode *n) { + CRBNode *s, *x, *y, *g; + + /* + * Rebalance tree after a node was removed. This happens only if you + * remove a black node and one path is now left with an unbalanced + * number or black nodes. + * This function assumes all paths through p and n have one black node + * less than all other paths. If recursive fixup is required, the + * current node is returned. + */ + + if (n == p->left) { + s = p->right; + if (c_rbnode_is_red(s)) { + /* Case 3: + * 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. */ + g = c_rbnode_parent(p); + x = s->left; + p->right = x; + s->left = p; + c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(s, g, c_rbnode_color(p)); + c_rbnode_set_parent_and_color(p, s, C_RBNODE_RED); + c_rbtree_swap_child(t, g, p, s); + s = x; + } + + x = s->right; + if (!x || c_rbnode_is_black(x)) { + y = s->left; + if (!y || c_rbnode_is_black(y)) { + /* Case 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, + * or we fix it recursively one layer up, which + * will rotate the red sibling as parent. */ + c_rbnode_set_parent_and_color(s, p, C_RBNODE_RED); + if (c_rbnode_is_black(p)) + return p; + + c_rbnode_set_parent_and_color(p, c_rbnode_parent(p), C_RBNODE_BLACK); + return NULL; + } + + /* 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; + s->left = y->right; + y->right = s; + p->right = y; + if (x) + c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK); + 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. */ + g = c_rbnode_parent(p); + y = s->left; + p->right = y; + s->left = p; + c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK); + if (y) + c_rbnode_set_parent_and_color(y, p, c_rbnode_color(y)); + c_rbnode_set_parent_and_color(s, g, c_rbnode_color(p)); + c_rbnode_set_parent_and_color(p, s, C_RBNODE_BLACK); + c_rbtree_swap_child(t, g, p, s); + } else /* if (!n || n == p->right) */ { /* same as above, but mirrored */ + s = p->left; + if (c_rbnode_is_red(s)) { + g = c_rbnode_parent(p); + x = s->right; + p->left = x; + s->right = p; + c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(s, g, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(p, s, C_RBNODE_RED); + c_rbtree_swap_child(t, g, p, s); + s = x; + } + + x = s->left; + if (!x || c_rbnode_is_black(x)) { + y = s->right; + if (!y || c_rbnode_is_black(y)) { + c_rbnode_set_parent_and_color(s, p, C_RBNODE_RED); + if (c_rbnode_is_black(p)) + return p; + + c_rbnode_set_parent_and_color(p, c_rbnode_parent(p), C_RBNODE_BLACK); + return NULL; + } + + x = y->left; + s->right = y->left; + y->left = s; + p->left = y; + if (x) + c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK); + x = s; + s = y; + } + + g = c_rbnode_parent(p); + y = s->right; + p->left = y; + s->right = p; + c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK); + if (y) + c_rbnode_set_parent_and_color(y, p, c_rbnode_color(y)); + c_rbnode_set_parent_and_color(s, g, c_rbnode_color(p)); + c_rbnode_set_parent_and_color(p, s, C_RBNODE_BLACK); + c_rbtree_swap_child(t, g, p, s); + } + + return NULL; +} + +static inline void c_rbtree_rebalance(CRBTree *t, CRBNode *p) { + CRBNode *n = NULL; + + assert(t); + assert(p); + + do { + n = c_rbtree_rebalance_one(t, p, n); + p = n ? c_rbnode_parent(n) : NULL; + } while (p); +} + +/** + * c_rbtree_remove() - remove node from tree + * @t: tree to operate one + * @n: node to remove + * + * This removes the given node from its tree. Once unlinked, the tree is + * rebalanced. + * The caller *must* ensure that the given tree is actually the tree it is + * linked on. Otherwise, behavior is undefined. + * + * This does *NOT* reset @n to being unlinked (for performance reason, this + * function *never* modifies @n at all). If you need this, use + * c_rbtree_remove_init(). + */ +_public_ void c_rbtree_remove(CRBTree *t, CRBNode *n) { + CRBNode *p, *s, *gc, *x, *next = NULL; + unsigned long c; + + assert(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 cannot have two children by + * itself (two interior nodes can never be successive). Therefore, + * we can simply swap the node with its successor (including color) + * and have reduced this case to either of the first two. + * + * 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). + * + * p: parent + * s: successor + * gc: grand-...-child + * x: temporary + * next: next node to rebalance on + */ + + if (!n->left) { + /* + * Case 1: + * The node has no left child. If it neither has a right child, + * it is a leaf-node and we can simply unlink it. If it also + * was black, we have to rebalance, as always if we remove a + * black node. + * But if the node has a right child, the child *must* be red + * (otherwise, the right path has more black nodes as 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. + */ + p = c_rbnode_parent(n); + c = c_rbnode_color(n); + c_rbtree_swap_child(t, p, n, n->right); + if (n->right) + c_rbnode_set_parent_and_color(n->right, p, c); + else + next = (c == C_RBNODE_BLACK) ? p : NULL; + } else if (!n->right) { + /* + * Case 1.1: + * The node has exactly one child, and it is on the left. Treat + * it as mirrored case of Case 1 (i.e., replace the node by its + * child). + */ + p = c_rbnode_parent(n); + c = c_rbnode_color(n); + c_rbtree_swap_child(t, p, n, n->left); + c_rbnode_set_parent_and_color(n->left, p, c); + } else { + /* + * Case 2: + * We are dealing with a full interior node with a child not on + * both sides. 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. + */ + s = n->right; + if (!s->left) { + /* right child is next, no need to touch grandchild */ + p = s; + gc = s->right; + } else { + /* find successor and swap partially */ + s = c_rbnode_leftmost(s); + p = c_rbnode_parent(s); + + gc = s->right; + p->left = s->right; + s->right = n->right; + c_rbnode_set_parent(n->right, s); + } + + /* node is partially swapped, now remove as in Case 1 */ + s->left = n->left; + c_rbnode_set_parent(n->left, s); + + x = c_rbnode_parent(n); + c = c_rbnode_color(n); + c_rbtree_swap_child(t, x, n, s); + if (gc) + c_rbnode_set_parent_and_color(gc, p, C_RBNODE_BLACK); + else + next = c_rbnode_is_black(s) ? p : NULL; + c_rbnode_set_parent_and_color(s, x, c); + } + + if (next) + c_rbtree_rebalance(t, next); +} diff --git a/src/crbtree.h b/src/crbtree.h new file mode 100644 index 0000000..58e36c5 --- /dev/null +++ b/src/crbtree.h @@ -0,0 +1,178 @@ +#pragma once + +/*** + This file is part of crbtree. See COPYING for details. + + crbtree 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. + + crbtree 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 crbtree; If not, see . +***/ + +/** + * Standalone Red-Black-Tree Implementation in Standard ISO-C11 + * + * This header 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 a fully in control of 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 *singly* + * 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 an implementation detail + * and encodes the parent pointer and color of the node. + * 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 + +typedef struct CRBNode CRBNode; +typedef struct CRBTree CRBTree; + +/** + * struct CRBNode - Node of a Red-Black Tree + * @__parent_and_color: internal state + * @left: left child, or NULL + * @right: right child, or NULL + * + * Each node in an RB-Tree must embed an 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_color 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 { + CRBNode *__parent_and_color; + CRBNode *left; + CRBNode *right; +}; + +#define C_RBNODE_INIT(_var) { .__parent_and_color = &(_var) } + +CRBNode *c_rbnode_leftmost(CRBNode *n); +CRBNode *c_rbnode_rightmost(CRBNode *n); +CRBNode *c_rbnode_next(CRBNode *n); +CRBNode *c_rbnode_prev(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 { + CRBNode *root; +}; + +CRBNode *c_rbtree_first(CRBTree *t); +CRBNode *c_rbtree_last(CRBTree *t); + +void c_rbtree_add(CRBTree *t, CRBNode *p, CRBNode **l, CRBNode *n); +void c_rbtree_remove(CRBTree *t, CRBNode *n); + +/* inline shortcuts */ + +/** + * 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_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_rbtree_remove() does *NOT* mark the node + * as unlinked. You have to call c_rbnode_init() yourself after removal, or use + * the c_rbtree_remove_init() helper. + * + * Return: true if the node is linked, false if not. + */ +static inline _Bool c_rbnode_is_linked(CRBNode *n) { + return n && n->__parent_and_color != n; +} + +/** + * 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 how its semantics. + * + * Return: Pointer to parent. + */ +static inline CRBNode *c_rbnode_parent(CRBNode *n) { + return (CRBNode*)((unsigned long)n->__parent_and_color & ~1UL); +} + +/** + * c_rbtree_remove_init() - safely remove node from tree and reinitialize it + * @t: tree to operate on + * @n: node to remove, or NULL + * + * This is almost the same as c_rbtree_remove(), 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_rbtree_remove_init(CRBTree *t, CRBNode *n) { + if (c_rbnode_is_linked(n)) { + c_rbtree_remove(t, n); + c_rbnode_init(n); + } +} + +#ifdef __cplusplus +} +#endif diff --git a/src/libcrbtree.sym b/src/libcrbtree.sym new file mode 100644 index 0000000..23fa8ef --- /dev/null +++ b/src/libcrbtree.sym @@ -0,0 +1,30 @@ +/*** + This file is part of crbtree. See COPYING for details. + + crbtree 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. + + crbtree 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 crbtree; If not, see . +***/ + +LIBCRBTREE_1 { +global: + c_rbnode_leftmost; + c_rbnode_rightmost; + c_rbnode_next; + c_rbnode_prev; + c_rbtree_first; + c_rbtree_last; + c_rbtree_add; + c_rbtree_remove; +local: + *; +}; diff --git a/src/test-api.c b/src/test-api.c new file mode 100644 index 0000000..69b2958 --- /dev/null +++ b/src/test-api.c @@ -0,0 +1,67 @@ +/*** + This file is part of crbtree. See COPYING for details. + + crbtree 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. + + crbtree 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 crbtree; If not, see . +***/ + +/* + * 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 +#include +#include +#include +#include "crbtree.h" + +static void test_api(void) { + CRBTree t = {}; + CRBNode n = C_RBNODE_INIT(n); + + assert(!c_rbnode_is_linked(&n)); + + /* init, is_linked, add, remove, remove_init */ + + c_rbtree_add(&t, NULL, &t.root, &n); + assert(c_rbnode_is_linked(&n)); + + c_rbtree_remove_init(&t, &n); + assert(!c_rbnode_is_linked(&n)); + + c_rbtree_add(&t, NULL, &t.root, &n); + assert(c_rbnode_is_linked(&n)); + + c_rbtree_remove(&t, &n); + assert(c_rbnode_is_linked(&n)); /* @n wasn't touched */ + + c_rbnode_init(&n); + assert(!c_rbnode_is_linked(&n)); + + /* 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)); +} + +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 0000000..1f823e6 --- /dev/null +++ b/src/test-basic.c @@ -0,0 +1,261 @@ +/*** + This file is part of crbtree. See COPYING for details. + + crbtree 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. + + crbtree 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 crbtree; If not, see . +***/ + +/* + * 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. The tree operations performed are pseudo-random, and + * test all code-paths (see coverage report). However, full coverage does not + * necessarily guarantee absolute testing, so there are also some fixed tests + * for known special cases. + * + * For testing purposes, we use the memory address of a node as its key, and + * order nodes in ascending order. + */ + +#undef NDEBUG +#include +#include +#include +#include +#include +#include "crbtree.h" +#include "crbtree-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[2048]; + 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_rbtree_remove(&t, nodes[i]); + n = validate(&t); + assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1); + c_rbnode_init(nodes[i]); + } + + /* 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_rbtree_remove(&t, nodes[i]); + n = validate(&t); + assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1); + c_rbnode_init(nodes[i]); + } + + /* 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_rbtree_remove(&t, nodes[i]); + n = validate(&t); + assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1); + c_rbnode_init(nodes[i]); + } + + /* 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; +} -- 2.39.2