From mboxrd@z Thu Jan 1 00:00:00 1970 From: chambilkethakur@gmail.com (Anuz Pratap Singh Tomar) Date: Tue, 19 Mar 2013 16:26:22 +0000 Subject: Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists In-Reply-To: References: <20130319153423.GA30406@worldash.org> Message-ID: To: kernelnewbies@lists.kernelnewbies.org List-Id: kernelnewbies.lists.kernelnewbies.org On Tue, Mar 19, 2013 at 3:53 PM, Dave Hylands wrote: > Hi Arlie, > > > > On Tue, Mar 19, 2013 at 8:34 AM, Arlie Stephens > 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. > > 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. > > So if you want your cursor object to be self-contained, then it should > include both a list head and a list current. > > If you want your cursor to be generic, then it should probably look > something like: > > struct list_cursor { > struct list_head *list; > struct list_head *curr; > }; > > 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. > > 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. -- > Dave Hylands > Shuswap, BC, Canada > http://www.davehylands.com > > _______________________________________________ > Kernelnewbies mailing list > Kernelnewbies at kernelnewbies.org > http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies > > -- Thank you Warm Regards Anuz -------------- next part -------------- An HTML attachment was scrubbed... URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20130319/a0beab40/attachment.html