Analysis of Linux kernel linked list (20)
Let's take a look at the node definition of the Linux kernel linked list, as follows
So the question is, where does the data go? So, next we will use struct list_head custom linked list nodes. As follows
Let's add a custom linked list node.
/ * * list_replace-replace old entry by new one * @ old: the element to be replaced * @ new: the new element to insert * * If @ old was empty, it will be overwritten. * / static void list_replace (struct list_head * old, struct list_head * node) {node- > next = old- > next; node- > next- > prev = node; node- > prev = old- > prev; node- > prev- > next = node;} static void list_replace_init (struct list_head * old, struct list_head * node) {list_replace (old, node); INIT_LIST_HEAD (old);}
Let's take a look at the insert, delete, traversal and other operations of the Linux kernel linked list.
A, insert operation: a > insert at the head of the linked list: list_add (new,head), b > insert at the end of the linked list: list_add_tail (new,head); as follows
B. Delete operation:
Let's test the code, which is as follows
# include # include # include "LinuxList.h" void list_demo_1 () {struct Node {struct list_head head; int value;}; struct Node l = {0}; struct list_head* list = (struct list_head*) & 1; struct list_head* slider = NULL; int iTuno; INIT_LIST_HEAD (list); printf ("Insert begin...\ n"); for (iTun0; ivalue = I List_add_tail ((struct list_head*) n, list);} list_for_each (slider, list) {printf ("% d\ n", ((struct Node*) slider)-> value);} printf ("Insert end...\ n"); printf ("Delete begin...\ n") List_for_each (slider, list) {if (struct Node*) slider)-> value = = 3) {list_del (slider); free (slider); break;}} list_for_each (slider, list) {printf ("% d\ n", (struct Node*) slider)-> value) } printf ("Delete end...\ n");} void list_demo_2 () {struct Node {int value; struct list_head head;}; struct Node l = {0}; struct list_head* list = & l.head0; struct list_head* slider = NULL; int iTun0; INIT_LIST_HEAD (list); printf ("Insert begin...\ n"); for (iTun0) Ivalue = I; list_add (& n-> head, list);} list_for_each (slider, list) {printf ("% d\ n", list_entry (slider, struct Node, head)-> value);} printf ("Insert end...\ n"); printf ("Delete begin...\ n") List_for_each (slider, list) {struct Node* n = list_entry (slider, struct Node, head); if (n-> value = = 3) {list_del (slider); free (n); break } list_for_each (slider, list) {printf ("% d\ n", list_entry (slider, struct Node, head)-> value);} printf ("Delete end...\ n");} int main () {list_demo_1 (); list_demo_2 (); return 0;}
Let's compile and see the results.
The output is as we thought, and the migration is now complete. After today's transplantation of linked lists in the Linux kernel, the summary is as follows: 1. Linux kernel linked lists need to eliminate dependencies and platform-related code; 2. Linux kernel linked lists are two-way circular linked lists that lead nodes; 3. Custom linked list nodes are needed when using Linux kernel linked lists: a > take struct list_head as the first or last member of the node structure When b > struct list_head is the last member, you need to use the list_entry macro; the definition of c > list_entry uses the container_of macro.
