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

[MORITA Kazutaka]

At Tue,  3 Sep 2013 17:27:57 +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(+)

The subject line should be updated, too.

> 
> diff --git a/include/rbtree.h b/include/rbtree.h
> index 15f873a..1fe2923 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;							\
>  })
>  
> +/*
> + * Search for a value in the rbtree.  When the key is not found in the rbtree,
> + * this returns the next greater node. Note, if key > greatest node, we'll
> + * return first node.
> + */

This macro returns NULL when the rbtree is empty, right?  If yes,
please document it too.

> +#define rb_nsearch(root, key, member, compar)                           \
> +({                                                                      \
> +        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)                                  \

(root)->rb_node should be !RB_EMPTY_ROOT(root).

Other parts in this series look good to me.

Thanks,

Kazutaka

> +                __ret = rb_entry(rb_first(root), typeof(*key), member); \
> +        __ret;                                                          \
> +})
> +
>  /* Iterate over a rbtree safe against removal of rbnode */
>  #define rb_for_each(pos, root)					\
>  	pos = rb_first(root);					\
> -- 
> 1.7.9.5
> 
> -- 
> sheepdog mailing list
> sheepdog at lists.wpkg.org
> http://lists.wpkg.org/mailman/listinfo/sheepdog