On Tue, Mar 19, 2013 at 3:53 PM, Dave Hylands <dhylands@xxxxxxxxx> wrote:
struct list_head *curr;struct list_head *list;struct list_cursor {If you want your cursor to be generic, then it should probably look something like:So if you want your cursor object to be self-contained, then it should include both a list head and a list current.So when you're advancing through the list, instead of testing list->next for NULL you check to see if list->next is equal to the list head.Hi Arlie,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 = somelistcursor->curr = somelistTo 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.
Besides the Robert's link you can also have a look at FAQ on kernel newbies
http://kernelnewbies.org/FAQ/LinkedLists
LDD also covers it
http://www.makelinux.net/ldd3/chp-11-sect-5
There is a good explanation of kernel linked list in Robert Love's book as well.
http://kernelnewbies.org/FAQ/LinkedLists
LDD also covers it
http://www.makelinux.net/ldd3/chp-11-sect-5
There is a good explanation of kernel linked list in Robert Love's book as well.
_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@xxxxxxxxxxxxxxxxx
http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
--
Thank you
Warm Regards
Anuz
_______________________________________________ Kernelnewbies mailing list Kernelnewbies@xxxxxxxxxxxxxxxxx http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
