Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

[Anuz Pratap Singh Tomar]

On Tue, Mar 19, 2013 at 3:53 PM, Dave Hylands <dhylands at gmail.com> wrote:

> Hi Arlie,
>
>
>
> On Tue, Mar 19, 2013 at 8:34 AM, Arlie Stephens <arlie at worldash.org>
> 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