RB trees in the kernel (Arcangeli, 1999)

Kernel rbtrees go inside the payload, like lists

static void insert_line(struct line_rb *item,
            struct rb_root *root)
{
    struct rb_node **p = &root->rb_node;
    struct rb_node *parent = NULL;
    struct line_rb *lrb;

    while (*p)
    {
        parent = *p;
        lrb = rb_entry(parent, struct line_rb, rb);

        if (strcmp(item->line, lrb->line) < 0)
            p = &(*p)->rb_left;
        else
            p = &(*p)->rb_right;
    }

    rb_link_node(&item->rb, parent, p);
    rb_insert_color(&item->rb, root);
}
struct line_rb {
    char line[SLEN];
    struct rb_node rb;
};