If you don't like macros (which are used quite a lot for this sort of thing - e.g. http://fxr.watson.org/fxr/source/sys/queue.h), void pointers and function pointers go a long way too. Nobody's writing red-black trees from scratch for every project, really.
