I've been working on this more and have gone through several
iterations.  I have a small problem: my mechanism will never inline the
key compare function call since it calls it by pointer.  I'm not sure if
this is dictated in the C specification or if it's just something gcc
can't currently detect as a compile-time constant and optimize out. 
Every other option specified via the struct rb_relationship is getting
nicely optimized, removing unused code, etc.

Here is the current feature set (all optimized out when not used):
* leftmost - keep a pointer to the leftmost (lowest value) node cached
in your container struct (thanks Peter)
* rightmost - ditto for rightmost (greatest value)
* unique or non-unique keys with some minor tuning options
* relative searches - when you already have a node that is likely near
another one you want to search for
* augmented / interval tree support (not yet tested)

So back to the problem, as I see it here are my options:
1. Create a header file where you #define your parameters and include it
to define your search, insert & remove functions.  Example:

#define RBTREE_CONTAINER_TYPE     struct my_container
#define RBTREE_CONTAINER_ROOT     rb_root       /* struct rb_root member */
#define RBTREE_CONTAINER_LEFTMOST leftmost      /* struct rb_node *member */
#define RBTREE_CONTAINER_RIGHTMOST              /* none */
#define RBTREE_OBJECT_TYPE        struct my_obj
#define RBTREE_OBJECT_NODE        rb_node       /* struct rb_node member */
#define RBTREE_OBJECT_KEY         mykey
#define RBTREE_KEY_COMPARE        compare_my_key
#define etc...
#include <linux/grbtree.h> /* expands parameters where needed and then
#undefs them. */

2. Use a big ugly macro to define them.  Example:
RB_DEFINE_CORE(struct my_container, rb_root, etc...) /* expands to all
function implementations */

3. Accept the compare function call overhead for search & insert
functions and keep them normal (i.e., __always_inline, non-preprocessor)
generic functions.

Here are the benefits of each, as I see it:
Debugging information will still point you to a real line of code
1. Yes, 2. No, 3. Yes

Type safety implemented (you pass pointers to your container & object
structs directly rather than node pointers)
1. Yes, 2. Yes, 3. No

Maximum efficiency (no function calls to inline-ables like compare and
augmented)
1. Yes, 2. Yes, 3. No

Relies primarily upon:
1. cpp, 2. cpp, 3. cc


To me, the first option seems like it makes the most sense, although I
despise heavy use of the preprocessor (it would be sweet if ANSI came
out with a C templates standard).  Attached is my current working
version which implements approach 3 as described above.  It has a
GRB_DEFINE_INTERFACE() macro, but it only defines a type a type-safe
interface and doesn't fix the compare function not inlined problem.
(Much of comment docs are out of date too.)

Thanks in advance.

Daniel