lkml.org 
[lkml]   [2012]   [Aug]   [6]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation
From
Date
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), 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);
}




\
 
 \ /
  Last update: 2012-08-06 18:21    [W:0.130 / U:0.344 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site