lkml.org 
[lkml]   [2012]   [Aug]   [6]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
SubjectRe: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation
From
On Mon, Aug 6, 2012 at 8:38 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Mon, 2012-08-06 at 16:17 +0200, Peter Zijlstra wrote:
>
>> Why would every user need to replicate the propagate and rotate
>> boilerplate?
>
> So I don't have a tree near that any of this applies to (hence no actual
> patch)

All right, here are instructions to get a tree this will apply to :)
1- fetch linux-next tree
2- check out next-20120806
3- revert e406c4110c968b7691c4ccfadcd866a74a72fa5b (was sent as
previous RFC version of this series, didn't realize it had made it
into -mm)
4- apply patches 1 and 3-9 of this series (patch 2 was also sent as
previous RFC version and made it into -mm)

> but why can't we have something like:
>
> struct rb_augment_callback {
> const bool (*update)(struct rb_node *node);
> const int offset;
> const int size;
> };
>
> #define RB_AUGMENT_CALLBACK(_update, _type, _rb_member, _aug_member) \
> (struct rb_augment_callback){ \
> .update = _update, \
> .offset = offsetof(_type, _aug_member) - \
> offsetof(_type, _rb_member), \
> .size = sizeof(((_type *)NULL)->_aug_member), \
> }
>
> static __always_inline void
> augment_copy(struct rb_node *dst, struct rb_node *src,
> const rb_augment_callback *ac)
> {
> memcpy((void *)dst + ac->offset,
> (void *)src + ac->offset,
> ac->size);
> }
>
> static __always_inline void
> augment_propagate(struct rb_node *rb, struct rb_node *stop,
> const struct rb_augment_callback *ac)
> {
> while (rb != stop) {
> if (!ac->update(rb))
> break;
> rb = rb_parent(rb);
> }
> }
>
> static __always_inline void
> augment_rotate(struct rb_node *old, struct rb_node *new.
> const struct rb_augment_callback *ac)
> {
> augment_copy(new, old, ac);
> (void)ac->update(old);
> }

I don't think this would work well, because ac->offset and ac->size
wouldn't be known at the point where they are needed, so the memcpy
wouldn't be nicely optimized into a fetch and store of the desired
size.

However, I wouldn't have a problem with declaring all 3 callbacks (and
the struct holding them) using a preprocessor macro as you propose.
Would that seem fine with you ? I can send an add-on patch to do that.

--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.


\
 
 \ /
  Last update: 2012-08-07 00:41    [W:0.059 / U:0.192 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site