User: Password:
Subscribe / Log in / New account

Generic red-black trees

Generic red-black trees

Posted Jun 7, 2012 22:24 UTC (Thu) by ppisa (subscriber, #67307)
Parent article: Generic red-black trees

I like the second approach more. But the type of rb_compare_f with void pointers without providing compile time typecheck is quite bad solution.

The other problem is that generation of inlined only function means, that there is generic non inlined function for search which receives pointer to compare function. This function is used for all types for insert, remove, find ... processing and cannot be optimized for given type (if we do not count some future more clever LTO/whole project optimization).

I have thought about these problems many years ago for my projects. The result is an GAVL tree implementation in uLUt library. So I cannot hold myself to send pointer it there

section:Custom AVL Tree Instances

Generator macros in sources:




I have already send info about my approach to LKML many years ago.

The code has some disadvantages as well. It is AVL tree based, not R-B. At least from Linux kernel point it is worse. The naming of some functions is little obscure due to long history and extension from initial void * variant which is still available in the uLUt. Code is spread in many of our project and income from naming cleanup has not outweigh the version compatibility problems.

There exists Neal H. Walfield's R-B tree implementation with almost same interface as GAVL. It is directly inspired by my approach. It has been originally intended for Hurd-L4 core project. Sources are available at

So I believe, that it would worth for authors to look and take some ideas from these projects.

Other library which provides tree components trying to solve similar problem is Rusty Russell's CCAN

Another is Martin Mares's libUCW

I have seen even more similar attempts to generate type safe tree containers for C programs but I consider uLUt (Neal's) interface as the most safe, resulting in good ration of code size and ability to do tight optimization of compares in search function yet sharing all insert, balance code between different types.

(Log in to post comments)

Generic red-black trees

Posted Jun 16, 2012 4:16 UTC (Sat) by daniel.santos (guest, #85158) [Link]

Since the start of this, my documentation said to define your compare functions as accepting the actual types of your key pointers, but in version 4, I've solved the problem of the compare function's type not being verified (at least, when using the RB_DEFINE_INTERFACE macro). So it will still call compare as type rb_compare_f from the generic functions, but if the compare function you supply to the macro doesn't match up, it will generate an understandable error or warning. Here, I've given it the wrong return type (line 65 is where the macro is called):

/my/path/grbtest2.c: In function ‘__rb_sanity_check_my_objects_rel’:
/my/path/grbtest2.c:65:1: error: passing argument 1 of ‘__rb_verify_compare_fn_ret’ from incompatible pointer type [-Werror]
In file included from /my/path/grbtest.h:30:0,
                 from /my/path/grbtest2.c:21:
include/linux/rbtree.h:917:20: note: expected ‘long int *’ but argument is of type ‘unsigned int *’
cc1: all warnings being treated as errors

And here, I've defined the compare function as accepting types of const u32 instead of const *u32 (line 57 is the compare function's definition).

/my/path/grbtest2.c: In function ‘__rb_sanity_check_my_objects_rel’:
/my/path/grbtest2.c:65:1: error: passing argument 1 of ‘compare_u32’ makes integer from pointer without a cast [-Werror]
/my/path/grbtest2.c:57:15: note: expected ‘u32’ but argument is of type ‘u32 *’

I've implemented similar type checks for all other parameters as well, each calling a static inline function that tells you what it's checking for, i.e., __rb_verify_root(), __rb_verify_left(), etc. That way, you'll have a better chance at knowing what's actually wrong. In the generated code examinations I've made thus far, I haven't seen any compilers actually emit code for these type checks.

As far as calling compare by pointer, you will be most pleased to learn that as of version 4.6.? (4.6.0 maybe?, definitely in 4.6.2), gcc is now capable of optimizing out a call-by-constant-pointer-to-inline(able)-function. Thus, in gcc 4.6.2, optimization is perfect. I mentioned in my previous post the optimization from 4.1 to 4.5 was "acceptable", by this I mostly mean that gcc 4.5.3 did everything that it should do, except inline the call to the compare function (I don't have as many details from 4.1 to 4.4). In fact, the reason I had to add the __flatten attribute was because without it, neither gcc 4.6.3 nor 4.7.0 would inline the call-by-constant-struct-member-function-pointer (i.e., passing compare in struct rb_relationship), but it would if I passed it directly as a function parameter. I'm still not certain if this is a bug or I hit the max pseudo-instructions and it stopped inlining, but the result is actually smaller & faster code.

But anyway, thanks for these links! I've been studying everything I can find that might give me hints on how to make this better. One qunadry I'm still sorting out about my compare function is dealing with compound keys. Currently, if you have a compound key (that is, two fields that need comparing), you basically choose a key to pass for the key offset, and then in your compare function, use container_of() or rb_entry() to get a pointer to your struct and then access your other key(s). Here's an example for one rbtree in drivers/mtd/ubi/wl.c.

static inline long compare_ubi_wl_entry(const int *a_ec, const int *b_ec) {
       long diff = (long)*a_ec - (long)*b_ec;
       if (!diff) {
               diff = (long)container_of(a_ec, struct ubi_wl_entry, ec)->pnum -
                      (long)container_of(b_ec, struct ubi_wl_entry, ec)->pnum;
       return diff;

When you call insert, you will always have a full struct who's key will be examined by pointer. The drawback is that when you call find, you generally don't have a struct sitting around to access its key member and you run into the same issue as with Kent's implementation of needing to stick one on the stack. For this reason, I've been considering allowing the user to specify two different compare functions: one accpeting key pointers, and another accepting struct pointers, optionally using the same compare function for both (this would bloat the rbtree.h source code, but not the generated code).

I also meant to address my choice for choosing the return type of long over int in my last post. I made this decision when working on the fair scheduler, as it seemed to allow for a more optimal compare function than int when you need to compare 64-bit values. When doing this on a 64-bit build arch, you just compare them, but on a 32-bit build, you still have to do a bit more work since you have to fit the comparision result in a 32-bit long. But if I choose int, I would have to do that amount of work on both archs. Personally, I really wish there was a way in C to say "compare these two values, and use CPU's negative & zero flags on these branches", because I don't see gcc optimizing out code like this (on AMD64):

int diff = a > b ? 1 : (a < b ? -1 : 0);
if (diff > 0) {
    // do something
} else if (diff < 0) {
    // do something else
} else {
    // do something else else

Maybe I just need to file a gcc bug for this, because in every case, I've seen gcc store the 1, -1 or 0 in a register and compare it to zero later, and unless I missed something, I didn't see any instructions that would change those flags in between.

Generic red-black trees

Posted Jun 16, 2012 11:30 UTC (Sat) by ppisa (subscriber, #67307) [Link]

Hello Daniel, thanks for analysis and integration of ideas into generic RB tree code for the kernel. As for the comare function return value, I have observed same problems with int on GCC and have not found how to guide it to better code. Long is probably good idea for all mainstream Linux kernel target architectures. It would lead to a little worse code for H8S if (default) 16 bit int is used (as in our embedded builds). The -mint32 option is used for the kernel, so no difference in code size is caused by long there.

I like your idea with struct rb_relationship and it is great that GCC can optimize generated code.

As for use of empty macro parameters, it works great with GCC, but I have observed problems with MSVC with this approach for uLUt. The use of dummy comment /*dummy*/ in the place of the empty parameter resolved this issue.

Please, can you send URL to the actual patches version? Is it LKML only or you have some copy on FTP/WWW?

As I follow development of other OSes (RTEMS, sometimes HURD etc.) as well, I can see, that same problem is solved again and again. I would like to point RTEMS people to your implementation. But licensing would be problem there because RTEMS core requires GPL with linking exception (core is directly linked with APPs, GPL boundary is on API (regualar C) functions calls). Similar problem arises when used in LGPL licensed libraries. Do you think, that there is chance to provide this "STL" under more permissive license?

Generic red-black trees

Posted Jun 16, 2012 21:20 UTC (Sat) by daniel.santos (guest, #85158) [Link]

Ooh, I didn't even think about 16-bit ints. Thanks for the info on msvc. I did finally discover that empty macro arguments is part of the C99 standard -- no surprise that msvc doesn't fully support it yet, but nice to know that there's a work-around!

I don't have this on any web site right now. fail2ban is screwed up on my machine atm, so I closed all my firewall holes until I get it fixed, otherwise, I would make it available from here. Locally, I need to squash a few commits and amend comments and I can post something somewhere.

As far as GPL w/ link-time exception, I am a believer in that if the business/ethical circumstances warrant it. I have plans for C++11 (w/metaprogramming) game engine toolkit project (if I ever kick it off at all) that will be GPL w/ link-time exception as it's the only way it will get any appreciable commercial support.

Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds