Re: [PATCH v4 11/13] rbtree.h: Generic Red-Black Trees

Peter Zijlstra
2012-06-27T13:00:48Z

On Fri, 2012-06-22 at 23:00 -0500, Daniel Santos wrote:

> +typedef long (*rb_compare_f)(const void *a, const void *b);

> +struct rb_relationship {
> + ssize_t root_offset;
> + ssize_t left_offset;
> + ssize_t right_offset;
> + ssize_t count_offset;
> + ssize_t node_offset;
> + ssize_t key_offset;
> + int flags;
> + const rb_compare_f compare;
> + const rb_augment_f augment;
> +};

> +static __always_inline __flatten
> +struct rb_node *__rb_find(
> + struct rb_node *node,
> + const void *key,
> + const struct rb_relationship *rel)
> +{
> + __rb_assert_good_rel(rel);
> + while (node) {
> + long diff = rel->compare(key, __rb_node_to_key(node, rel));
> +
> + if (diff > 0)
> + node = node->rb_right;
> + else if (diff < 0)
> + node = node->rb_left;
> + else
> + return node;
> + }
> +
> + return 0;
> +}

> +#define RB_RELATIONSHIP( \
> + cont_type, root, left, right, count, \
> + obj_type, node, key, \
> + _flags, _compare, _augment) { \
> + .root_offset = offsetof(cont_type, root), \
> + .left_offset = OPT_OFFSETOF(cont_type, left), \
> + .right_offset = OPT_OFFSETOF(cont_type, right), \
> + .count_offset = OPT_OFFSETOF(cont_type, count), \
> + .node_offset = offsetof(obj_type, node), \
> + .key_offset = offsetof(obj_type, key), \
> + .flags = (_flags) \
> + | IFF_EMPTY(left , 0, RB_HAS_LEFTMOST) \
> + | IFF_EMPTY(right, 0, RB_HAS_RIGHTMOST) \
> + | IFF_EMPTY(count, 0, RB_HAS_COUNT) \
> + | IFF_EMPTY(_augment, 0, RB_IS_AUGMENTED), \
> + .compare = (const rb_compare_f) (_compare), \
> + .augment = IFF_EMPTY(_augment, 0, _augment) \
> +}

> +#define RB_DEFINE_INTERFACE( \
> + prefix, \
> + cont_type, root, left, right, count, \
> + obj_type, node, key, \
> + flags, compare, augment, \
> + find_mod, insert_mod, find_near_mod, insert_near_mod) \
> + \
> \
> +static const struct rb_relationship prefix ## _rel = \
> +RB_RELATIONSHIP( \
> + cont_type, root, left, right, count, \
> + obj_type, node, key, \
> + flags, compare, augment); \
> + \
> +IFF_EMPTY(find_mod, static __always_inline, find_mod) \
> +obj_type *prefix ## _find(cont_type *cont, \
> + const typeof(((obj_type *)0)->key) *_key) \
> +{ \
> + struct rb_node *ret = rb_find( \
> + &cont->root, _key, &prefix ## _rel); \
> + return ret ? rb_entry(ret, obj_type, node) : 0; \
> +} \

So the one thing I noticed was your 'fixed' long return type for
compare. I guess that's one of the things that inspired your CFS compare
'hack' since on 32bit that's too short.

I tried playing with typeof() and return types of function pointers, but
I couldn't make it work. Bummer. That leaves explicitly passing it to
the RB_DEFINE_INTERFACE() and pulling all relevant inline functions into
the macro as well.