[PATCH] Corrections to Documentation/rbtree.txt

[PATCH] Corrections to Documentation/rbtree.txt

[Ian Abbott]

From: Ian Abbott <abbotti@mev.co.uk>

The description of the rb_entry() macro in Documentation/rbtree.txt seems incorrect.
This patch improves it (hopefully).  Also I changed the example code to call the
previous 'my_search()' example instead of an undefined 'mysearch()'.

Signed-off-by: Ian Abbott <abbotti@mev.co.uk>
---
--- linux-2.6.24/Documentation/rbtree.txt.orig	2008-01-24 22:58:37.000000000 +0000
+++ linux-2.6.24/Documentation/rbtree.txt	2008-03-20 15:14:55.000000000 +0000
@@ -64,8 +64,8 @@
   };
 
 When dealing with a pointer to the embedded struct rb_node, the containing data
-structure may be accessed with the standard container_of() macro.  In addition,
-individual members may be accessed directly via rb_entry(node, type, member).
+structure may be accessed with the rb_entry() macro, which is a synonym for the
+standard container_of() macro.
 
 At the root of each rbtree is an rb_root structure, which is initialized to be
 empty via:
@@ -85,7 +85,7 @@
   	struct rb_node *node = root->rb_node;
 
   	while (node) {
-  		struct mytype *data = container_of(node, struct mytype, node);
+  		struct mytype *data = rb_entry(node, struct mytype, node);
 		int result;
 
 		result = strcmp(string, data->keystring);
@@ -118,7 +118,7 @@
 
   	/* Figure out where to put new node */
   	while (*new) {
-  		struct mytype *this = container_of(*new, struct mytype, node);
+  		struct mytype *this = rb_entry(*new, struct mytype, node);
   		int result = strcmp(data->keystring, this->keystring);
 
 		parent = *new;
@@ -146,7 +146,7 @@
 
 Example:
 
-  struct mytype *data = mysearch(mytree, "walrus");
+  struct mytype *data = my_search(mytree, "walrus");
 
   if (data) {
   	rb_erase(data->node, mytree);
@@ -180,13 +180,11 @@
 NULL when there are no more nodes left.
 
 The iterator functions return a pointer to the embedded struct rb_node, from
-which the containing data structure may be accessed with the container_of()
-macro, and individual members may be accessed directly via
-rb_entry(node, type, member).
+which the containing data structure may be accessed with the rb_entry() macro.
 
 Example:
 
   struct rb_node *node;
   for (node = rb_first(&mytree); node; node = rb_next(node))
-  	printk("key=%s\n", rb_entry(node, int, keystring));
+  	printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);
 

Re: [PATCH] Corrections to Documentation/rbtree.txt

[Rob Landley]

On Thursday 20 March 2008 10:29:57 Ian Abbott wrote:
> From: Ian Abbott <abbotti@mev.co.uk>
>
> The description of the rb_entry() macro in Documentation/rbtree.txt seems
> incorrect. This patch improves it (hopefully).  Also I changed the example
> code to call the previous 'my_search()' example instead of an undefined
> 'mysearch()'.

I have no objection to the patch (and the my_search thing seems like an 
obvious typo), but is there a reason to prefer rb_entry() rather than 
container_of()?  If so, the rationale might be a good thing to add to the 
documentation...

Rob
-- 
"One of my most productive days was throwing away 1000 lines of code."
  - Ken Thompson.

Re: [PATCH] Corrections to Documentation/rbtree.txt

[Ian Abbott]

On 20/03/08 18:39, Rob Landley wrote:
> On Thursday 20 March 2008 10:29:57 Ian Abbott wrote:
>> From: Ian Abbott <abbotti@mev.co.uk>
>>
>> The description of the rb_entry() macro in Documentation/rbtree.txt seems
>> incorrect. This patch improves it (hopefully).  Also I changed the example
>> code to call the previous 'my_search()' example instead of an undefined
>> 'mysearch()'.
> 
> I have no objection to the patch (and the my_search thing seems like an 
> obvious typo), but is there a reason to prefer rb_entry() rather than 
> container_of()?  If so, the rationale might be a good thing to add to the 
> documentation...

I don't know the rationale, but all the code I can see uses rb_entry() 
and not container_of().  The only rationale I can think of is that it 
abstracts away from the nodes being embedded in the data a little bit. 
(But not by much - in particular, an implementation of rb trees that 
stored data in the node explicitly would only need a single parameter in 
its rb_entry() accessor.  I like the approach taken in 
include/linux/elevator.h that uses the rb_entry() macro to create a 
specialized accessor macro (rb_entry_rq()) with a single parameter.

-- 
-=( Ian Abbott @ MEV Ltd.    E-mail: <abbotti@mev.co.uk>        )=-
-=( Tel: +44 (0)161 477 1898   FAX: +44 (0)161 718 3587         )=-

Re: [PATCH] Corrections to Documentation/rbtree.txt

[Rob Landley]

On Tuesday 25 March 2008 06:02:22 Ian Abbott wrote:
> On 20/03/08 18:39, Rob Landley wrote:
> > On Thursday 20 March 2008 10:29:57 Ian Abbott wrote:
> >> From: Ian Abbott <abbotti@mev.co.uk>
> >>
> >> The description of the rb_entry() macro in Documentation/rbtree.txt
> >> seems incorrect. This patch improves it (hopefully).  Also I changed the
> >> example code to call the previous 'my_search()' example instead of an
> >> undefined 'mysearch()'.
> >
> > I have no objection to the patch (and the my_search thing seems like an
> > obvious typo), but is there a reason to prefer rb_entry() rather than
> > container_of()?  If so, the rationale might be a good thing to add to the
> > documentation...
>
> I don't know the rationale, but all the code I can see uses rb_entry()
> and not container_of().

Except container_of() works, which is a nice thing to know, and it already 
mentions rb_entry() as another way to do it.  If someone could explain _why_ 
to use one over the other, that would be a good thing to add.

> The only rationale I can think of is that it 
> abstracts away from the nodes being embedded in the data a little bit.

If I wanted abstraction for its own sake I'd be using C++ to implement a 
microkernel.  I would also be certifiably insane.

> (But not by much - in particular, an implementation of rb trees that
> stored data in the node explicitly would only need a single parameter in
> its rb_entry() accessor.  I like the approach taken in
> include/linux/elevator.h that uses the rb_entry() macro to create a
> specialized accessor macro (rb_entry_rq()) with a single parameter.

And this can't be done with container_of()?

Again, I don't care much either way, I just want to know what the point is of 
choosing one over the other that makes changing what's there worth bothering 
with.  You're changing the documentation to hide the fact that rb_entry() is 
basically another name for container_of(), and this is supposed to be an 
improvement?

Rob
-- 
"One of my most productive days was throwing away 1000 lines of code."
  - Ken Thompson.

Re: [PATCH] Corrections to Documentation/rbtree.txt

[Ian Abbott]

On 25/03/08 18:24, Rob Landley wrote:
> On Tuesday 25 March 2008 06:02:22 Ian Abbott wrote:
>> On 20/03/08 18:39, Rob Landley wrote:
>>> On Thursday 20 March 2008 10:29:57 Ian Abbott wrote:
>>>> From: Ian Abbott <abbotti@mev.co.uk>
>>>>
>>>> The description of the rb_entry() macro in Documentation/rbtree.txt
>>>> seems incorrect. This patch improves it (hopefully).  Also I changed the
>>>> example code to call the previous 'my_search()' example instead of an
>>>> undefined 'mysearch()'.
>>> I have no objection to the patch (and the my_search thing seems like an
>>> obvious typo), but is there a reason to prefer rb_entry() rather than
>>> container_of()?  If so, the rationale might be a good thing to add to the
>>> documentation...
>> I don't know the rationale, but all the code I can see uses rb_entry()
>> and not container_of().
> 
> Except container_of() works, which is a nice thing to know, and it already 
> mentions rb_entry() as another way to do it.  If someone could explain _why_ 
> to use one over the other, that would be a good thing to add.

Let's see if Andrea Arcangeli can still remember the rationale from 9 
years ago! :-)

container_of() works just as well, but _none_ of the existing code in 
the kernel uses it to access the container of the struct rb_node; they 
all use rb_entry(), including the example code in include/linux/rbtree.h.

> Again, I don't care much either way, I just want to know what the point is of 
> choosing one over the other that makes changing what's there worth bothering 
> with.  You're changing the documentation to hide the fact that rb_entry() is 
> basically another name for container_of(), and this is supposed to be an 
> improvement?

Personally I have no preference for rb_entry() over container_of(), but 
as all the code in the kernel uses rb_entry() it seems better if the 
examples in the documentation use it too.

-- 
-=( Ian Abbott @ MEV Ltd.    E-mail: <abbotti@mev.co.uk>        )=-
-=( Tel: +44 (0)161 477 1898   FAX: +44 (0)161 718 3587         )=-

Re: [PATCH] Corrections to Documentation/rbtree.txt

[Ian Abbott]

On 20/03/08 18:39, Rob Landley wrote:
> On Thursday 20 March 2008 10:29:57 Ian Abbott wrote:
>> From: Ian Abbott <abbotti@mev.co.uk>
>>
>> The description of the rb_entry() macro in Documentation/rbtree.txt seems
>> incorrect. This patch improves it (hopefully).  Also I changed the example
>> code to call the previous 'my_search()' example instead of an undefined
>> 'mysearch()'.
> 
> I have no objection to the patch (and the my_search thing seems like an 
> obvious typo), but is there a reason to prefer rb_entry() rather than 
> container_of()?  If so, the rationale might be a good thing to add to the 
> documentation...

I forgot to mention this in my earlier post, but while we're on the
subject, it might be worth renaming the 'node' variable in the
'my_search()' and iteration examples to avoid confusion in the use of
the rb_entry() (or container_of() macro), for example in 'my_search()',
instead of:

	struct rb_node *node = root->rb_node;

	while (node) {
		struct mytype *data = rb_entry(node, struct mytype, node);

I think this is clearer:

	struct rb_node *pn = root->rb_node;

	while (pn) {
		struct mytype *data = rb_entry(pn, struct mytype, node);

(I used rb_entry instead of container_of in the above.  Also, there are
probably better, longer variable names than 'pn', e.g. 'rbn' or 'rbnode'
or 'pnode'.)

-- 
-=( Ian Abbott @ MEV Ltd.    E-mail: <abbotti@mev.co.uk>        )=-
-=( Tel: +44 (0)161 477 1898   FAX: +44 (0)161 718 3587         )=-