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:
GAVL_CUST_NODE_INT_DEC + GAVL_CUST_NODE_INT_IMP
GAVL_CUST_NODE_INT_DEC + GAVL_CUST_NODE_INT_REP_IMP
GAVL_FLES_INT_DEC + GAVL_FLES_INT_IMP
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.
Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds