Hi Arlie,
On Tue, Mar 19, 2013 at 8:34 AM, Arlie Stephens <[email protected]> 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
_______________________________________________ Kernelnewbies mailing list [email protected] http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
