Re: [PATCH 4/6] rbtree: faster augmented insert

2012-07-27 Thread Michel Lespinasse
On Fri, Jul 27, 2012 at 1:04 PM, Peter Zijlstra wrote: > On Fri, 2012-07-20 at 05:31 -0700, Michel Lespinasse wrote: >> +static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new) >> +{ >> + struct test_node *old = rb_entry(rb_old, struct test_node, rb); >> + struct

Re: [PATCH 4/6] rbtree: faster augmented insert

2012-07-27 Thread Michel Lespinasse
On Fri, Jul 27, 2012 at 12:26 PM, Peter Zijlstra wrote: > On Fri, 2012-07-20 at 05:31 -0700, Michel Lespinasse wrote: >> --- a/lib/rbtree.c >> +++ b/lib/rbtree.c >> @@ -88,7 +88,8 @@ __rb_rotate_set_parents(struct rb_node *old, struct >> rb_node *new, >> root->rb_node = new; >>

Re: [PATCH 4/6] rbtree: faster augmented insert

2012-07-27 Thread Peter Zijlstra
On Fri, 2012-07-20 at 05:31 -0700, Michel Lespinasse wrote: > +static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new) > +{ > + struct test_node *old = rb_entry(rb_old, struct test_node, rb); > + struct test_node *new = rb_entry(rb_new, struct test_node, rb); > + > +

Re: [PATCH 4/6] rbtree: faster augmented insert

2012-07-27 Thread Peter Zijlstra
On Fri, 2012-07-20 at 05:31 -0700, Michel Lespinasse wrote: > > rb_insert_color() is now a special case of rb_insert_augmented() with > a do-nothing callback. I used inlining to optimize out the callback, > with the intent that this would generate the same code as previously > for

Re: [PATCH 4/6] rbtree: faster augmented insert

2012-07-27 Thread Peter Zijlstra
On Fri, 2012-07-20 at 05:31 -0700, Michel Lespinasse wrote: > --- a/lib/rbtree.c > +++ b/lib/rbtree.c > @@ -88,7 +88,8 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node > *new, > root->rb_node = new; > } > > -void rb_insert_color(struct rb_node *node, struct

Re: [PATCH 4/6] rbtree: faster augmented insert

2012-07-27 Thread Peter Zijlstra
On Fri, 2012-07-20 at 05:31 -0700, Michel Lespinasse wrote: --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -88,7 +88,8 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, root-rb_node = new; } -void rb_insert_color(struct rb_node *node, struct rb_root *root)

Re: [PATCH 4/6] rbtree: faster augmented insert

2012-07-27 Thread Peter Zijlstra
On Fri, 2012-07-20 at 05:31 -0700, Michel Lespinasse wrote: rb_insert_color() is now a special case of rb_insert_augmented() with a do-nothing callback. I used inlining to optimize out the callback, with the intent that this would generate the same code as previously for

Re: [PATCH 4/6] rbtree: faster augmented insert

2012-07-27 Thread Peter Zijlstra
On Fri, 2012-07-20 at 05:31 -0700, Michel Lespinasse wrote: +static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new) +{ + struct test_node *old = rb_entry(rb_old, struct test_node, rb); + struct test_node *new = rb_entry(rb_new, struct test_node, rb); + +

Re: [PATCH 4/6] rbtree: faster augmented insert

2012-07-27 Thread Michel Lespinasse
On Fri, Jul 27, 2012 at 12:26 PM, Peter Zijlstra pet...@infradead.org wrote: On Fri, 2012-07-20 at 05:31 -0700, Michel Lespinasse wrote: --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -88,7 +88,8 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, root-rb_node =

Re: [PATCH 4/6] rbtree: faster augmented insert

2012-07-27 Thread Michel Lespinasse
On Fri, Jul 27, 2012 at 1:04 PM, Peter Zijlstra pet...@infradead.org wrote: On Fri, 2012-07-20 at 05:31 -0700, Michel Lespinasse wrote: +static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new) +{ + struct test_node *old = rb_entry(rb_old, struct test_node, rb); +

Re: [PATCH 4/6] rbtree: faster augmented insert

2012-07-25 Thread Rik van Riel
On 07/20/2012 08:31 AM, Michel Lespinasse wrote: Introduce rb_insert_augmented(), which is a version of rb_insert_color() with an added callback on tree rotations. This can be used for insertion into an augmented tree: the handcoded search phase must be updated to maintain the augmented

Re: [PATCH 4/6] rbtree: faster augmented insert

2012-07-25 Thread Rik van Riel
On 07/20/2012 08:31 AM, Michel Lespinasse wrote: +++ b/lib/rbtree.c @@ -88,7 +88,8 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, root->rb_node = new; } -void rb_insert_color(struct rb_node *node, struct rb_root *root) +inline void

Re: [PATCH 4/6] rbtree: faster augmented insert

2012-07-25 Thread Rik van Riel
On 07/20/2012 08:31 AM, Michel Lespinasse wrote: +++ b/lib/rbtree.c @@ -88,7 +88,8 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, root-rb_node = new; } -void rb_insert_color(struct rb_node *node, struct rb_root *root) +inline void

Re: [PATCH 4/6] rbtree: faster augmented insert

2012-07-25 Thread Rik van Riel
On 07/20/2012 08:31 AM, Michel Lespinasse wrote: Introduce rb_insert_augmented(), which is a version of rb_insert_color() with an added callback on tree rotations. This can be used for insertion into an augmented tree: the handcoded search phase must be updated to maintain the augmented

[PATCH 4/6] rbtree: faster augmented insert

2012-07-20 Thread Michel Lespinasse
Introduce rb_insert_augmented(), which is a version of rb_insert_color() with an added callback on tree rotations. This can be used for insertion into an augmented tree: the handcoded search phase must be updated to maintain the augmented information on insertion, and then the rbtree

[PATCH 4/6] rbtree: faster augmented insert

2012-07-20 Thread Michel Lespinasse
Introduce rb_insert_augmented(), which is a version of rb_insert_color() with an added callback on tree rotations. This can be used for insertion into an augmented tree: the handcoded search phase must be updated to maintain the augmented information on insertion, and then the rbtree