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?