Hi Arlie, On Tue, Mar 19, 2013 at 8:34 AM, Arlie Stephens <arlie@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. -- Dave Hylands Shuswap, BC, Canada http://www.davehylands.com