Here is a widely-used example of a zero abstraction cost, type safe red black tree in C:

http://libredblack.sourceforge.net/

It supports a few modes of operation, including codegen, and preprocessor tricks. It’s clearly maintainable, given its age and continued use.

Your third complaint is that C with preprocessor macros is ugly. That’s subjective.

I think C++ is more elegant than C + macros, but the GTK people clearly disagree.