On Sun, 23 Mar 2008, Manish Katiyar wrote:
> On Sun, Mar 23, 2008 at 12:46 PM, Robert P. J. Day
> <rpjday@xxxxxxxxxxxxxx> wrote:
> >
> > i'm sure i'm misreading something, but when i look at the macro
> > definition of "__list_for_each" in list.h:
> >
> > #define __list_for_each(pos, head) \
> > for (pos = (head)->next; pos != (head); pos = pos->next)
> >
> > i could swear that this traversal will visit each node in the list
> > except for the initial head element.
> >
> > look closely: given a starting address of "head", the
> > initialization starts things off at (head)->next, and continues
> > traversing as long as pos != head. so wouldn't this traversal end up
> > *not* visiting the list element addressed by "head" itself? or is
> > that what it's supposed to do?
>
> Yes, it will miss. And it is supposed to because your head is just
> kind of *sentinel* element and doesnt hold any *useful* data other
> than next and prev pointers.
ok, i grabbed some of the linked list code and copied it into
userspace just to see what's happening and, pictorially, here's what
happens if i create a new list and add two elements to it -- i've
simplified the addresses to show who points to who:
(head)
-----------------
(1) | 3 | 2 |
-----------------
(elt1) (elt2)
----------------- -----------------
(2) | 1 | 3 | (3) | 2 | 1 |
----------------- -----------------
so, in the above, the addresses 1, 2 and 3 represent the userspace
addresses of the "struct list_head"s and, as you can see, if i
initialize a list with that "sentinel" object, then use list_add to
add two new elements, sure enough, the "prev" and "next" links for
everyone involved show a circular list.
*but* ... the only way traversal will work properly (that is, if i
want to traverse the meaningful objects in that list: elt1 and elt2)
using __list_for_each() is if i always start the traversal at the
"head" or sentinel element.
but i thought the philosophy was that you could traverse a linked list
by arbitrarily starting at any element in the list. technically,
that's true, but if i choose to start at, say, elt1, my traversal will
produce visits to elt2 and (the null-valued) head structures -- not
exactly what i had in mind.
so, i can now appreciate what's happening here, but it does seem to be
a bit of an overreach for kernel documentation to suggest that linked
list traversal works equally well no matter where you start in the
list.
rday
--
========================================================================
Robert P. J. Day
Linux Consulting, Training and Annoying Kernel Pedantry:
Have classroom, will lecture.
http://crashcourse.ca Waterloo, Ontario, CANADA
========================================================================
--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx
Please read the FAQ at http://kernelnewbies.org/FAQ
