Corrections to Documentation/rbtree.txt

PATCH In review Ian Abbott 2 participants 6 messages Mar 20, 2008 – Mar 26, 2008 Documentation

lore

Share & tools

lore

Ian Abbott

author

2008-03-20 16:00 UTC #0 lore raw

PATCH 1/1 Corrections to Documentation/rbtree.txt

From: Ian Abbott <[email protected]>

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 <[email protected]>

---

Documentation/rbtree.txt renamed from Documentation/rbtree.txt.orig +7 -9

@@ -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);

Rob Landley

2008-03-20 18:39 UTC #1 lore raw

Quoted 6 lines · On Thursday 20 March 2008 10:29:57 Ian Abbott wrote:

From: Ian Abbott <[email protected]>
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

Signature · 2 lines

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

Ian Abbott

author

2008-03-25 11:02 UTC #2 lore raw

Quoted 9 lines · Rob Landley

Quoted 6 lines · On Thursday 20 March 2008 10:29:57 Ian Abbott wrote:
From: Ian Abbott <[email protected]>
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.

Signature · 2 lines

-=( Ian Abbott @ MEV Ltd.    E-mail: <[email protected]>        )=-
-=( Tel: +44 (0)161 477 1898   FAX: +44 (0)161 718 3587         )=-

Rob Landley

2008-03-25 18:24 UTC #3 lore raw

Quoted 9 lines · On Tuesday 25 March 2008 06:02:22 Ian Abbott wrote:

Quoted 8 lines · Rob Landley
Quoted 6 lines · On Thursday 20 March 2008 10:29:57 Ian Abbott wrote:
From: Ian Abbott <[email protected]>
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()'.

Quoted 7 lines

Quoted 4 lines
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.

Quoted 2 lines

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.

Quoted 5 lines

(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

Signature · 2 lines

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

Ian Abbott

author

2008-03-26 14:09 UTC #4 lore raw

Quoted 9 lines · Rob Landley

Quoted 8 lines · On Tuesday 25 March 2008 06:02:22 Ian Abbott wrote:
Quoted 7 lines · Rob Landley
Quoted 6 lines · On Thursday 20 March 2008 10:29:57 Ian Abbott wrote:
From: Ian Abbott <[email protected]>
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()'.

Quoted 8 lines

Quoted 6 lines
Quoted 4 lines
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.

Quoted 1 line

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.

Signature · 2 lines

-=( Ian Abbott @ MEV Ltd.    E-mail: <[email protected]>        )=-
-=( Tel: +44 (0)161 477 1898   FAX: +44 (0)161 718 3587         )=-

Ian Abbott

author

2008-03-25 11:30 UTC #5 lore raw

In reply to Rob Landley

Quoted 9 lines · Rob Landley

Quoted 6 lines · On Thursday 20 March 2008 10:29:57 Ian Abbott wrote:
From: Ian Abbott <[email protected]>
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'.)

Signature · 2 lines

-=( Ian Abbott @ MEV Ltd.    E-mail: <[email protected]>        )=-
-=( Tel: +44 (0)161 477 1898   FAX: +44 (0)161 718 3587         )=-