Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

[arlie@worldash.org (Arlie Stephens)]

Hi Dave,

Thank you very much. 

On Mar 19 2013, Dave Hylands wrote:
> 
> Hi Arlie,
> 
[SNIP]

> 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.

It's good to have confirmation of this. 
> 
> 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.

And this feels right, in a way that what I was doing did not. 
> 
> 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.

Good introduction. And a great link at the end. 

Interestingly, part of the debate yesterday probably resulted from one
engineer having Love's 2nd edition, and me having his 3rd
edition. Apparently RPDay pointed out some problems to Love which
resulted in him changing his linked list discussion in his 3rd
edition ;-) 

--
Arlie

(Arlie Stephens						 arlie at worldash.org)