StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>EDIT: sorry, it must be late, I've made a lot of typos.</p> <p>They are pure fun! :) The difference is that <code>list_for_each_entry</code> will break if you delete something while iterating the list and <code>list_for_each_entry_safe</code> won't (of course, at the expense of some extra CPU instructions).</p> <p>The kernel has settled on doubly-linked lists (which I'm presuming you understand), although there is a singingly linked list implementation in list.h. Your list is just:</p> <pre><code>struct list_head { struct list_head *next; struct list_head *prev; }; </code></pre> <p>Note that the same struct is used for both the "head" of the list as well as each node. When the list is empty, the head's <code>next</code> and <code>prev</code> members just point to the head its self. Thus, iterating the list is just a process of starting with the head's <code>next</code> member and calling that a node, unless it's the same address as <code>prev</code> (when you stop). Otherwise, your <code>for</code> body is invoked and you can use the <code>container_of()</code> macro to get a pointer to your actual struct and play with it. Then, in the 3rd field of the <code>for</code>, we just just move to the next <code>next</code>.</p> <p>EDIT: whoops, I apologize, you asked for an explanation of the parameters. Well, I would check it out directly if I were you rather than taking somebody's word for it. For those, I would suggest the <a href="https://www.kernel.org/doc/htmldocs/kernel-api/adt.html#id347958" rel="noreferrer">Kernel API docs</a> themselves, which at least exist for the linked list library. I'm trying to get a patch set through that will add them for the red-black tree library as well, but getting stuff through can be quite a process.</p> <p>Also of note: <a href="http://kernelnewbies.org/FAQ/LinkedLists" rel="noreferrer">http://kernelnewbies.org/FAQ/LinkedLists</a></p> <p>Here's a quick example:</p> <pre><code>struct list_head my_actual_list; struct my_struct { struct list_head node; /* some other members */ }; /* in a function body somewhere... */ struct list_head *i; list_for_each(i, &my_actual_list) { struct my_struct *obj = list_entry(i, struct my_struct, node); // do something with obj } </code></pre> <p><code>list_entry</code> is just an alias for <code>container_of</code></p> <p><strong>EDIT #2</strong></p> <p>OK, so in answer to your question in comments, I'm going to just expand my answer. I can actually appreciate the difficulty in grasping this concept as it does have a few strange things in it compared to C++ STL containers, C arrays, etc, but once you are accustom to the idioms, it will seem quite natural. Still in the future, I really urge you to start looking at the definition for these structs, functions & macros yourself and trying to piece together an understanding, then ask the questions.</p> <p>So first off, each node in your list is a struct that contains a member of type <code>struct list_head</code> and the list <strong><em>its self</em></strong> is of type <code>struct list_head</code>. Thus, who is the container and who is the contained in this case, simply depends upon how they are used, but typically, it will be expressed in the names these members are given. The type of the iterator is <code>struct list_head *</code>. Here's an example and I'll replace the normal function & macro calls with their equivalent code:</p> <pre><code>struct my_container { struct list_head list; int some_member; /* etc. */ }; struct my_obj { struct list_head node; int some_member; /* etc. */ }; void func() { struct my_container container; struct my_obj obj1, obj2; struct list_head *i; /* INIT_LIST_HEAD(&container.list); */ container.list.next = &container.list; container.list.prev = &container.list; /* list_add_tail(&obj1.node); */ container.list.prev = &obj1.node; obj1.node.next = &container.list; obj1.node.prev = &container.list; container.list.next = &obj1.node; /* list_add_tail(&obj2.node); */ container.list.prev = &obj2.node; obj2.node.next = &container.list; obj2.node.prev = &obj1.node; obj1.node.next = &obj2.node; /* list_for_each(i, &container.list) { */ for (i = container.list.next; i != &container.list; i = i->next) { struct my_obj *obj = list_entry(i, struct my_obj, node); /* do stuff */ } } </code></pre> <p><a href="http://en.wikipedia.org/wiki/Doubly_linked_list" rel="noreferrer">Now go read! :)</a></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload