<br><br><div class="gmail_quote">On Tue, Mar 19, 2013 at 3:53 PM, Dave Hylands <span dir="ltr"><<a href="mailto:dhylands@gmail.com" target="_blank">dhylands@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><div><div><div><div><div><div><div><div>Hi Arlie,<div><div class="h5"><br><br><br>On Tue, Mar 19, 2013 at 8:34 AM, Arlie Stephens <<a href="mailto:arlie@worldash.org" target="_blank">arlie@worldash.org</a>> wrote:<br>
><br>> Hi Folks,<br>
><br>> I'm trying to understand the linux way of doing things, so as to write<br>> code which will be easier for experienced linux kernel people to<br>> understand. Yesterday I wound up in a 3 engineer discussion about<br>
> something conceptually simple, that just didn't want to be done with<br>> the tools at hand; what's worse, the only ways I could see to do it<br>> were (a) do my own linked lists or (b) write some routines that relied<br>
> kind of heavily on the never-mentioned-in-documentation details of<br>> linux/list.h I'll probably go with option (b), as that seems less<br>> insane, but I thought I might as well ask here as well.<br>><br>
> Here's the problem. I have a collection of resources. Call them<br>> A,B,C,D but note that resources get added at run time, so I don't know<br>> how many to expect. I want to go through them in a round robin<br>
> fashion, but not all at once. On the first request, I use A. On a<br>> later request I use B, etc. This seems to me to map naturally to a<br>> circular linked list, with a "cursor" - a pointer of some kind to the<br>
> next one I want to use. To make my specific situation more<br>> interesting, I actually have multiple cursors - that may or may not<br>> happen to point to the same node at any given time, but usually will<br>
> not.<br>
><br>> This is where I wish I could draw pictures in ascii emails ;-)<br>> Perhaps the following will come through halfway sanely:<br>><br>> C1 C2 C3<br>> V / V<br>> A<->B<->C-<->D<br>
> ^------------^<br>><br>> list.h implements a circular linked list - see for example<br>> <a href="http://www.makelinux.net/books/lkd2/app01lev1sec2" target="_blank">http://www.makelinux.net/books/lkd2/app01lev1sec2</a> - so I thought this<br>
> would be easy and natural. But then I discovered there was no such<br>> thing as a list_next(). OK, I can write it - Something like:<br>> cursor->resource = list_entry(cursor->resource->link.next, struct resource, link);<br>
> But the fact there was no interface made me ask advice from colleagues.<br>> And that's when the debate erupted.<br>><br>> First of all, it's unclear whether that would even work. If the list<br>> is initialized following the standard pardigm, there may be a "head"<br>
> element embedded in the list, which all the existing interfaces know<br>> to ignore. I.e.<br><br></div></div></div>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.<br>
<br></div>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.<br><br></div>So if you want your cursor object to be self-contained, then it should include both a list head and a list current.<br>
<br></div>If you want your cursor to be generic, then it should probably look something like:<br><br></div>struct list_cursor {<br></div> struct list_head *list;<br></div> struct list_head *curr;<br>};<br><br></div>
<div>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.<br></div><div><br></div><div>To initialize the cursor:<br>
<br></div><div>cursor->list = somelist<br></div><div>cursor->curr = somelist<br><br></div><div>To advance to the first node (remember the list has a dummy head node)<br><br></div><div>cursor->curr = cursor->curr->next<br>
<br></div><div>If the result is == cursor->head then there aren't any nodes except for the dummy node (i.e. list is empty)<br><br></div><div>To get at the actual entry, use list_entry as per usual.<br><br></div><div>
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.<br></div><div><br></div></div></blockquote><div>Besides the Robert's link you can also have a look at FAQ on kernel newbies<br>
<a href="http://kernelnewbies.org/FAQ/LinkedLists">http://kernelnewbies.org/FAQ/LinkedLists</a><br><br>LDD also covers it<br><a href="http://www.makelinux.net/ldd3/chp-11-sect-5">http://www.makelinux.net/ldd3/chp-11-sect-5</a><br>
<br>There is a good explanation of kernel linked list in Robert Love's book as well.<br><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>
</div><div><div><div><div><div><div>
<div><div>--<br>Dave Hylands<br>Shuswap, BC, Canada<br><a href="http://www.davehylands.com" target="_blank">http://www.davehylands.com</a></div></div></div></div></div></div></div></div></div>
<br>_______________________________________________<br>
Kernelnewbies mailing list<br>
<a href="mailto:Kernelnewbies@kernelnewbies.org">Kernelnewbies@kernelnewbies.org</a><br>
<a href="http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies" target="_blank">http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies</a><br>
<br></blockquote></div><br><br clear="all"><br>-- <br>Thank you <br>Warm Regards<br>Anuz<br>