Circular Linked Lists – Attributes, Implementation and Uses(onebyezero.blogspot.com)
onebyezero.blogspot.com
Circular Linked Lists – Attributes, Implementation and Uses
http://onebyezero.blogspot.com/2014/06/circular-linked-lists-attributes.html
7 comments
Performance tip (for circular linked lists and linked lists in general): store your list nodes in a dynamically allocated array. Keep freed nodes in an in-place freed list inside the array and in a stack-like structure in-place beyond the part of the array that is currently in use. This cuts down on fragmentation in the memory allocator since you are allocating one larger contiguous chunk of memory instead of many smaller pieces, keeps your data closer together in the memory space to help with cache performance and prefetching, and allows you to switch to array indices instead of pointers. Why array indices? If the data uses indices for its references rather than pointers, sharing it across process memory spaces at different addresses is trivial. It also allows you to serialize the data to disk or the wire without having to perform any changes to the representation.
Is this a response to the blog post "The Worst Programming Interview Question" that went last time on HN?
https://news.ycombinator.com/item?id=7953725
https://news.ycombinator.com/item?id=7953725
Jiri Soukup (http://www.amazon.com/Taming-Pattern-Classes-Persistence-Pro... I've sworn off using C++ in the future, but keep this one book using it handy, it's got a lot of generally useful advice, much from hard lessons learned in VLSI CAD and other early industrial uses of C++) is fond of these, and I've found them very useful in times past. Particularly elegant in that they eliminate special case code for the beginning and ending of the list.
Oh geeze, list_heads. I remember wrangling with these when I was taking an OS class. In particular, my partner and I lost points on a project because we (and basically everybody else in the class) failed to recognize a subtle bug in how we were traversing lists.
Say you have a task_struct, and you want to iterate through the list of that task's children. You look through the code and you see
>struct list_head children; /* list of my children * /
>struct list_head sibling; /* linkage in my parent's children * /
And because it's late and you've been working for hours, you say "Ah ha! We'll just iterate through the children list_head, which is the list of the task's children, and that will give us what we want!"
But it turns out that's not how it works, because list_heads aren't linked lists like how you're used to thinking of them from your class on Data Structures! Here's what happens when you run your naive code iterating through children!
You start at task_struct foo, and you follow the pointer to a child of foo. Now, you follow children again, because you're still thinking that children is the list_head of foo's children. But you're wrong, because now you're in task_struct bar, and list_head children is now a list of bar's children; what you should be doing is iterating through list_head siblings!
We were pretty salty about losing the points, as I recall. On the other hand, after that experience we were very careful about keeping track of which struct we were in during any particular operation on a list_head, and I can remember how how they work (and how angry they made me) long after the class is over.
Say you have a task_struct, and you want to iterate through the list of that task's children. You look through the code and you see
>struct list_head children; /* list of my children * /
>struct list_head sibling; /* linkage in my parent's children * /
And because it's late and you've been working for hours, you say "Ah ha! We'll just iterate through the children list_head, which is the list of the task's children, and that will give us what we want!"
But it turns out that's not how it works, because list_heads aren't linked lists like how you're used to thinking of them from your class on Data Structures! Here's what happens when you run your naive code iterating through children!
You start at task_struct foo, and you follow the pointer to a child of foo. Now, you follow children again, because you're still thinking that children is the list_head of foo's children. But you're wrong, because now you're in task_struct bar, and list_head children is now a list of bar's children; what you should be doing is iterating through list_head siblings!
We were pretty salty about losing the points, as I recall. On the other hand, after that experience we were very careful about keeping track of which struct we were in during any particular operation on a list_head, and I can remember how how they work (and how angry they made me) long after the class is over.
Actually, the problem is that you're iterating through task_structs when you should be iterating through struct list_heads:
struct list_head* head = &this->children;
struct list_head* i = head->next;
for(; i!=head ;i=i->next)
{
task_struct* child = container_of(i,task_struct,sibling);
/* do stuff */
}This sounds like an issue of poor naming. The confusion goes away if "children" is renamed as"first_child". Perhaps not a likely option if that naming convention is spread through the Linux kernel, though.
This is not true for circular linked lists in general. A few special cases where this is true:
1. If the list is doubly linked.
2. If the list maintains pointers to both head and tail nodes (trivial).
3. If the list maintains a single pointer but uses it to refer to the tail node instead of the head node. Head node can then be easily reached as tail->next.
Of course, data structures can be tweaked in innumerable ways to add special properties. So one cannot possibly list all ways of adding easy tail-node-access to circular linked lists.