[sheepdog] [PATCH v2 1/4] rbtree: add rb_find helper

[MORITA Kazutaka]

At Tue,  3 Sep 2013 16:45:07 +0800,
Liu Yuan wrote:
> 
> This helper is used to find cloest node that is greater than the key.
> 
> Signed-off-by: Liu Yuan <namei.unix at gmail.com>
> ---
>  include/rbtree.h |   29 +++++++++++++++++++++++++++++
>  1 file changed, 29 insertions(+)
> 
> diff --git a/include/rbtree.h b/include/rbtree.h
> index 15f873a..f96e723 100644
> --- a/include/rbtree.h
> +++ b/include/rbtree.h
> @@ -138,6 +138,35 @@ static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
>  	__old;							\
>  })
>  
> +/*
> + * Find for a value in the rbtree.  When the key is not found in the rbtree,
> + * this returns the next greater node if one exists. Note, if key > greatest
> + * node, we'll return first node.
> + */
> +#define rb_find(root, key, member, compar)                              \

We are using rb_search for exactly matching.  I think we need a more
descriptive name.  Any ideas?

What I came up were rb_next_search, rb_nsearch, rb_greater...

> +({                                                                      \
> +        struct rb_node *__n = (root)->rb_node;                          \
> +        typeof(key) __ret = NULL, __data;                               \
> +                                                                        \
> +        while (__n) {                                                   \
> +                __data = rb_entry(__n, typeof(*key), member);           \
> +                int __cmp = compar(key, __data);                        \
> +                                                                        \
> +                if (__cmp < 0) {                                        \
> +                        __ret = __data;                                 \
> +                        __n = __n->rb_left;                             \
> +                } else if (__cmp > 0)                                   \
> +                        __n = __n->rb_right;                            \
> +                else {                                                  \
> +                        __ret = __data;                                 \
> +                        break;                                          \
> +                }                                                       \
> +        }                                                               \
> +        if (!__ret && (root)->rb_node)                                  \
> +                __ret = rb_entry(rb_first(root), typeof(*key), member); \

I think this line should move to oid_to_vdisk().  IMHO, to make this
macro more generic, rb_find() should return NULL when key is not in
the range of root.

Thanks,

Kazutaka