Hi Arlie,
On Tue, Mar 19, 2013 at 8:34 AM, Arlie Stephens <arlie@xxxxxxxxxxxx> wrote:
>
> Hi Folks,
>
> I'm trying to understand the linux way of doing things, so as to write
> code which will be easier for experienced linux kernel people to
> understand. Yesterday I wound up in a 3 engineer discussion about
> something conceptually simple, that just didn't want to be done with
> the tools at hand; what's worse, the only ways I could see to do it
> were (a) do my own linked lists or (b) write some routines that relied
> kind of heavily on the never-mentioned-in-documentation details of
> linux/list.h I'll probably go with option (b), as that seems less
> insane, but I thought I might as well ask here as well.
>
> Here's the problem. I have a collection of resources. Call them
> A,B,C,D but note that resources get added at run time, so I don't know
> how many to expect. I want to go through them in a round robin
> fashion, but not all at once. On the first request, I use A. On a
> later request I use B, etc. This seems to me to map naturally to a
> circular linked list, with a "cursor" - a pointer of some kind to the
> next one I want to use. To make my specific situation more
> interesting, I actually have multiple cursors - that may or may not
> happen to point to the same node at any given time, but usually will
> not.
>
> This is where I wish I could draw pictures in ascii emails ;-)
> Perhaps the following will come through halfway sanely:
>
> C1 C2 C3
> V / V
> A<->B<->C-<->D
> ^------------^
>
> list.h implements a circular linked list - see for example
> http://www.makelinux.net/books/lkd2/app01lev1sec2 - so I thought this
> would be easy and natural. But then I discovered there was no such
> thing as a list_next(). OK, I can write it - Something like:
> cursor->resource = list_entry(cursor->resource->link.next, struct resource, link);
> But the fact there was no interface made me ask advice from colleagues.
> And that's when the debate erupted.
>
> First of all, it's unclear whether that would even work. If the list
> is initialized following the standard pardigm, there may be a "head"
> element embedded in the list, which all the existing interfaces know
> to ignore. I.e.
So the real secret is that it's a circular list with a dummy node. This dummy node just has head/tail pointers and nothing else.On Tue, Mar 19, 2013 at 8:34 AM, Arlie Stephens <arlie@xxxxxxxxxxxx> wrote:
>
> Hi Folks,
>
> I'm trying to understand the linux way of doing things, so as to write
> code which will be easier for experienced linux kernel people to
> understand. Yesterday I wound up in a 3 engineer discussion about
> something conceptually simple, that just didn't want to be done with
> the tools at hand; what's worse, the only ways I could see to do it
> were (a) do my own linked lists or (b) write some routines that relied
> kind of heavily on the never-mentioned-in-documentation details of
> linux/list.h I'll probably go with option (b), as that seems less
> insane, but I thought I might as well ask here as well.
>
> Here's the problem. I have a collection of resources. Call them
> A,B,C,D but note that resources get added at run time, so I don't know
> how many to expect. I want to go through them in a round robin
> fashion, but not all at once. On the first request, I use A. On a
> later request I use B, etc. This seems to me to map naturally to a
> circular linked list, with a "cursor" - a pointer of some kind to the
> next one I want to use. To make my specific situation more
> interesting, I actually have multiple cursors - that may or may not
> happen to point to the same node at any given time, but usually will
> not.
>
> This is where I wish I could draw pictures in ascii emails ;-)
> Perhaps the following will come through halfway sanely:
>
> C1 C2 C3
> V / V
> A<->B<->C-<->D
> ^------------^
>
> list.h implements a circular linked list - see for example
> http://www.makelinux.net/books/lkd2/app01lev1sec2 - so I thought this
> would be easy and natural. But then I discovered there was no such
> thing as a list_next(). OK, I can write it - Something like:
> cursor->resource = list_entry(cursor->resource->link.next, struct resource, link);
> But the fact there was no interface made me ask advice from colleagues.
> And that's when the debate erupted.
>
> First of all, it's unclear whether that would even work. If the list
> is initialized following the standard pardigm, there may be a "head"
> element embedded in the list, which all the existing interfaces know
> to ignore. I.e.
};
I think you'll find that the cursor operations make a lot more sense if you keep the cursor generic and try not to include the type information about the list node.
To initialize the cursor:
cursor->list = somelist
cursor->curr = somelist
To advance to the first node (remember the list has a dummy head node)
cursor->curr = cursor->curr->next
If the result is == cursor->head then there aren't any nodes except for the dummy node (i.e. list is empty)
To get at the actual entry, use list_entry as per usual.
I see RPDay has posted the link to his little tutorial, and I was going to do the same, but I didn't have it saved anywhere. I highly recommend reading through that.
_______________________________________________ Kernelnewbies mailing list Kernelnewbies@xxxxxxxxxxxxxxxxx http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
