User: Password:
Subscribe / Log in / New account

Generic red-black trees

Generic red-black trees

Posted Jun 16, 2012 11:30 UTC (Sat) by ppisa (subscriber, #67307)
In reply to: Generic red-black trees by daniel.santos
Parent article: Generic red-black trees

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?

(Log in to post comments)

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