Messages in this thread | | | Subject | Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation | From | Peter Zijlstra <> | Date | Mon, 06 Aug 2012 17:38:57 +0200 |
| |
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); }
| |