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
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
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.