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

[Liu Yuan]

On Tue, Sep 03, 2013 at 06:13:50PM +0900, MORITA Kazutaka wrote:
> 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...

Okay, I'll take rb_nsearch

> 
> > +({                                                                      \
> > +        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.
> 

If we think of sorted elements as a ring, then the first one is the next one to
return. And if there is no users that need rb_find return NULL for out of range
search, I'd insist on returning first element. (If we have such users later, we
can then make it more generic)

Thanks
Yuan