[PATCH] Documentation: Update augmented rbtree documentation

[PATCH] Documentation: Update augmented rbtree documentation

[Sasha Levin]

Current documentation referred to the old method
of handling augmented trees. Update documentation
to correspond with the changes done in commit
b945d6b2554d550fe95caadc61e521c0ad71fb9c.

Cc: Ingo Molnar <mingo@elte.hu>
Cc: Pekka Enberg <penberg@cs.helsinki.fi>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: David Woodhouse <David.Woodhouse@intel.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---
 Documentation/rbtree.txt |   23 ++++++++++++++---------
 1 files changed, 14 insertions(+), 9 deletions(-)

diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt
index 19f8278..b847598 100644
--- a/Documentation/rbtree.txt
+++ b/Documentation/rbtree.txt
@@ -196,15 +196,20 @@ Support for Augmented rbtrees
 Augmented rbtree is an rbtree with "some" additional data stored in each node.
 This data can be used to augment some new functionality to rbtree.
 Augmented rbtree is an optional feature built on top of basic rbtree
-infrastructure. rbtree user who wants this feature will have an augment
-callback function in rb_root initialized.
-
-This callback function will be called from rbtree core routines whenever
-a node has a change in one or both of its children. It is the responsibility
-of the callback function to recalculate the additional data that is in the
-rb node using new children information. Note that if this new additional
-data affects the parent node's additional data, then callback function has
-to handle it and do the recursive updates.
+infrastructure. rbtree user who wants this feature will have to call the
+augmentation functions with the user provided augmentation callback
+when inserting and erasing nodes.
+
+On insertion, The user must call rb_augment_insert() once the new node is in
+place. This will cause the augmentation function callback to be called for
+each node between the new node and the root which have been affected by the
+insertion.
+
+When erasing a node, The user must call rb_augment_erase_begin() first to
+retrieve the deepest node on the rebalance path. Then, After erasing the
+original node, the user must call rb_augment_erase_end() with the deepest
+node found earlier. This will cause the augmentation function to be called
+for each affected node between the deepest node and the root.
 
 
 Interval tree is an example of augmented rb tree. Reference -
-- 
1.7.5.rc3

Re: [PATCH] Documentation: Update augmented rbtree documentation

[Peter Zijlstra]

On Mon, 2011-05-16 at 12:56 +0300, Sasha Levin wrote:
> Current documentation referred to the old method
> of handling augmented trees. Update documentation
> to correspond with the changes done in commit
> b945d6b2554d550fe95caadc61e521c0ad71fb9c.
> 
> Cc: Ingo Molnar <mingo@elte.hu>
> Cc: Pekka Enberg <penberg@cs.helsinki.fi>

Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>

> Cc: Linus Torvalds <torvalds@linux-foundation.org>
> Cc: David Woodhouse <David.Woodhouse@intel.com>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
> ---
>  Documentation/rbtree.txt |   23 ++++++++++++++---------
>  1 files changed, 14 insertions(+), 9 deletions(-)
> 
> diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt
> index 19f8278..b847598 100644
> --- a/Documentation/rbtree.txt
> +++ b/Documentation/rbtree.txt
> @@ -196,15 +196,20 @@ Support for Augmented rbtrees
>  Augmented rbtree is an rbtree with "some" additional data stored in each node.
>  This data can be used to augment some new functionality to rbtree.
>  Augmented rbtree is an optional feature built on top of basic rbtree
> -infrastructure. rbtree user who wants this feature will have an augment
> -callback function in rb_root initialized.
> -
> -This callback function will be called from rbtree core routines whenever
> -a node has a change in one or both of its children. It is the responsibility
> -of the callback function to recalculate the additional data that is in the
> -rb node using new children information. Note that if this new additional
> -data affects the parent node's additional data, then callback function has
> -to handle it and do the recursive updates.
> +infrastructure. rbtree user who wants this feature will have to call the
> +augmentation functions with the user provided augmentation callback
> +when inserting and erasing nodes.
> +
> +On insertion, The user must call rb_augment_insert() once the new node is in
> +place. This will cause the augmentation function callback to be called for
> +each node between the new node and the root which have been affected by the
> +insertion.
> +
> +When erasing a node, The user must call rb_augment_erase_begin() first to
> +retrieve the deepest node on the rebalance path. Then, After erasing the
> +original node, the user must call rb_augment_erase_end() with the deepest
> +node found earlier. This will cause the augmentation function to be called
> +for each affected node between the deepest node and the root.
>  
> 
>  Interval tree is an example of augmented rb tree. Reference -

Re: [PATCH] Documentation: Update augmented rbtree documentation

[Ingo Molnar]

* Sasha Levin <levinsasha928@gmail.com> wrote:

> Current documentation referred to the old method
> of handling augmented trees. Update documentation
> to correspond with the changes done in commit
> b945d6b2554d550fe95caadc61e521c0ad71fb9c.

>  Augmented rbtree is an rbtree with "some" additional data stored in each node.
>  This data can be used to augment some new functionality to rbtree.
>  Augmented rbtree is an optional feature built on top of basic rbtree
> +infrastructure. rbtree user who wants this feature will have to call the

s/rbtree user/An rbtree user

> +augmentation functions with the user provided augmentation callback
> +when inserting and erasing nodes.
> +
> +On insertion, The user must call rb_augment_insert() once the new node is in
> +place. This will cause the augmentation function callback to be called for
> +each node between the new node and the root which have been affected by the
> +insertion.
> +
> +When erasing a node, The user must call rb_augment_erase_begin() first to
> +retrieve the deepest node on the rebalance path. Then, After erasing the
> +original node, the user must call rb_augment_erase_end() with the deepest
> +node found earlier. This will cause the augmentation function to be called
> +for each affected node between the deepest node and the root.

Acked-by: Ingo Molnar <mingo@elte.hu>

Thanks,

	Ingo

Re: [PATCH] Documentation: Update augmented rbtree documentation

[Randy Dunlap]

On Mon, 16 May 2011 12:56:42 +0300 Sasha Levin wrote:

> Current documentation referred to the old method
> of handling augmented trees. Update documentation
> to correspond with the changes done in commit
> b945d6b2554d550fe95caadc61e521c0ad71fb9c.
> 
> Cc: Ingo Molnar <mingo@elte.hu>
> Cc: Pekka Enberg <penberg@cs.helsinki.fi>
> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
> Cc: Linus Torvalds <torvalds@linux-foundation.org>
> Cc: David Woodhouse <David.Woodhouse@intel.com>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
> ---
>  Documentation/rbtree.txt |   23 ++++++++++++++---------
>  1 files changed, 14 insertions(+), 9 deletions(-)
> 
> diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt
> index 19f8278..b847598 100644
> --- a/Documentation/rbtree.txt
> +++ b/Documentation/rbtree.txt
> @@ -196,15 +196,20 @@ Support for Augmented rbtrees
>  Augmented rbtree is an rbtree with "some" additional data stored in each node.
>  This data can be used to augment some new functionality to rbtree.
>  Augmented rbtree is an optional feature built on top of basic rbtree
> -infrastructure. rbtree user who wants this feature will have an augment
> -callback function in rb_root initialized.
> -
> -This callback function will be called from rbtree core routines whenever
> -a node has a change in one or both of its children. It is the responsibility
> -of the callback function to recalculate the additional data that is in the
> -rb node using new children information. Note that if this new additional
> -data affects the parent node's additional data, then callback function has
> -to handle it and do the recursive updates.
> +infrastructure. rbtree user who wants this feature will have to call the
> +augmentation functions with the user provided augmentation callback
> +when inserting and erasing nodes.
> +
> +On insertion, The user must call rb_augment_insert() once the new node is in

                 the user

> +place. This will cause the augmentation function callback to be called for
> +each node between the new node and the root which have been affected by the

                                               which has been

> +insertion.
> +
> +When erasing a node, The user must call rb_augment_erase_begin() first to

                        the user

> +retrieve the deepest node on the rebalance path. Then, After erasing the

                                                          after

> +original node, the user must call rb_augment_erase_end() with the deepest
> +node found earlier. This will cause the augmentation function to be called
> +for each affected node between the deepest node and the root.
>  
>  
>  Interval tree is an example of augmented rb tree. Reference -
> -- 



---
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***

Re: [PATCH] Documentation: Update augmented rbtree documentation

[Ingo Molnar]

* Randy Dunlap <rdunlap@xenotime.net> wrote:

> On Mon, 16 May 2011 12:56:42 +0300 Sasha Levin wrote:
> 
> > Current documentation referred to the old method
> > of handling augmented trees. Update documentation
> > to correspond with the changes done in commit
> > b945d6b2554d550fe95caadc61e521c0ad71fb9c.
> > 
> > Cc: Ingo Molnar <mingo@elte.hu>
> > Cc: Pekka Enberg <penberg@cs.helsinki.fi>
> > Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
> > Cc: Linus Torvalds <torvalds@linux-foundation.org>
> > Cc: David Woodhouse <David.Woodhouse@intel.com>
> > Cc: Andrew Morton <akpm@linux-foundation.org>
> > Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
> > ---
> >  Documentation/rbtree.txt |   23 ++++++++++++++---------
> >  1 files changed, 14 insertions(+), 9 deletions(-)
> > 
> > diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt
> > index 19f8278..b847598 100644
> > --- a/Documentation/rbtree.txt
> > +++ b/Documentation/rbtree.txt
> > @@ -196,15 +196,20 @@ Support for Augmented rbtrees
> >  Augmented rbtree is an rbtree with "some" additional data stored in each node.
> >  This data can be used to augment some new functionality to rbtree.
> >  Augmented rbtree is an optional feature built on top of basic rbtree
> > -infrastructure. rbtree user who wants this feature will have an augment
> > -callback function in rb_root initialized.
> > -
> > -This callback function will be called from rbtree core routines whenever
> > -a node has a change in one or both of its children. It is the responsibility
> > -of the callback function to recalculate the additional data that is in the
> > -rb node using new children information. Note that if this new additional
> > -data affects the parent node's additional data, then callback function has
> > -to handle it and do the recursive updates.
> > +infrastructure. rbtree user who wants this feature will have to call the
> > +augmentation functions with the user provided augmentation callback
> > +when inserting and erasing nodes.
> > +
> > +On insertion, The user must call rb_augment_insert() once the new node is in
> 
>                  the user
> 
> > +place. This will cause the augmentation function callback to be called for
> > +each node between the new node and the root which have been affected by the
> 
>                                                which has been
> 
> > +insertion.
> > +
> > +When erasing a node, The user must call rb_augment_erase_begin() first to
> 
>                         the user
> 
> > +retrieve the deepest node on the rebalance path. Then, After erasing the
> 
>                                                           after
> 
> > +original node, the user must call rb_augment_erase_end() with the deepest
> > +node found earlier. This will cause the augmentation function to be called
> > +for each affected node between the deepest node and the root.

Heh, you really rock at reviewing documentation!

I went through the text and could have sworn that beyond the small detail i 
pointed out it's otherwise perfect ;-)

Thanks,

	Ingo