lkml.org 
[lkml]   [2020]   [Apr]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC][PATCH 1/7] rbtree: Add generic add and find helpers
On Wed, Apr 29, 2020 at 06:04:05PM -0700, Michel Lespinasse wrote:
> Hi Peter,
>
> On Wed, Apr 29, 2020 at 05:32:59PM +0200, Peter Zijlstra wrote:
> > I've always been bothered by the endless (fragile) boilerplate for
> > rbtree, and I recently wrote some rbtree helpers for objtool and
> > figured I should lift them into the kernel and use them more widely.
> >
> > Provide:
> >
> > partial-order; less() based:
> > - rb_add(): add a new entry to the rbtree
> > - rb_add_cached(): like rb_add(), but for a rb_root_cached
> >
> > total-order; cmp() based:
> > - rb_find(): find an entry in an rbtree
> > - rb_find_first(): find the first (leftmost) matching entry
> > - rb_next_match(): continue from rb_find_first()
> > - rb_for_each(): for loop with rb_find_first() / rb_next_match()

I appear to have failed to mention rb_find_add(), which is a bit of a
specialty, but I could imagine there being more like it the many rbtree
users out there (I count 300+ rb_link_node occurences).

> >
> > Also make rb_add_cached() / rb_erase_cached() return true when
> > leftmost.
> >
> > Inlining and constant propagation should see the compiler inline the
> > whole thing, including the various compare functions.
>
> I really like the idea of this change. Also,I think it opens avenues
> for converting some users which had previously been avoiding raw rbtrees
> seemingly only because they didn't want to write this boilerplate.

Yeah; our current interface mandates you _understand_ binary trees, I
can imagine that's a step too far for some (sadly).

> Few questions:
>
> - Adding the rb_add_cached() / rb_erase_cached() return value looks
> like it almost belongs to a separate patch. Is this only used in
> patch 3/7 (sched/deadline) or did I miss other uses ? Not objecting
> to it, but it wasn't obvious to me when reading the patch what the
> return value was for.

I can certainly add it in a separate patch; as might be evident from the
(lack) of changelogs on the whole, I basically split and posted the
thing the moment it booted. I figured I shouldn't sink more time into it
if people were going to hate it ;-)

> - Have you considered passing a cmp() function to rb_add() and
> rb_add_cached(), and having these test cmp() < 0 rather than less() ?
> I figure every user will need to have a cmp() function, so it'd be
> nicer if they didn't also need a less() function, if the generated
> code is similar (if you checked and rejected it because of bad code,
> please just say so).

I did consider it; in fact I my original helpers had that.

The reaosn I went with less() over cmp() is that the add() vs find()
function signatures:

bool (*less)(struct rb_node *, const struct rb_node *);
int (*cmp)(const void *, const struct rb_node *);

differ anyway in the left-hand argument; this is 'fixable' when you
use an (on-stack) dummy object for find (as uprobes does), but that
doesn't always work, esp. when the object is big. And given you need two
functions anyway, I figured it was useful to name them differently.

If you've looked at the other patches a bit, you'll see I've implemented
both functions as 'trivial' wrappers around a single compare function in
many cases.

> Reviewed-by: Michel Lespinasse <walken@google.com>

Thanks, I suppose I'll go brush this up a bit more then.

\
 
 \ /
  Last update: 2020-04-30 10:46    [W:0.067 / U:0.744 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site