Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

[Victor Buciuc]

On Tue, Mar 19, 2013 at 8:50 PM, Victor Buciuc <victor.buciuc at gmail.com> wrote:
> On Tue, Mar 19, 2013 at 5:34 PM, 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
>> ^------------^
>>
>
> Hi,
>
> Another option might be to not iterate through the list but to simply
> move the element you're processing to the end of the list using
> list_rotate_left[1].
> And you could use list_next_entry[2] to get the next entry after the
> head. You'll
> have to check that the list is empty, tough.
>
> This would cost you some extra operations but you'll use the existing interface.
>
> [1] http://lxr.linux.no/linux+v3.8.3/include/linux/list.h#L214
> [2] http://lxr.linux.no/linux+v3.8.3/include/linux/list.h#L361
>
> Regards,
> Victor Buciuc.

Forgot to send to the list.

Regards,
Victor Buciuc.