In real work , We may often use linked list structure to store data , Especially embedded development , Often use linux Kernel's most classic bidirectional linked list list_head. This article introduces in detail Linux How to realize the general linked list of kernel , For the frequently used functions are given a detailed description and test cases , And transplanted it Linux The linked list structure of the kernel , On any platform, you can easily call the functions written by the kernel . Recommended collection , For a rainy day !


List of articles


Introduction of the list

Linked list is a kind of commonly used data structure to organize ordered data , It links data into a series of data nodes , Is an important implementation of linear table . Relative to the array , Linked lists are more dynamic , There is no need to know the total amount of data in advance when creating a linked list , You can allocate space at random , It can efficiently insert or delete data at any position in the linked list in real time .
Generally, the linked list data structure should contain at least two fields : Data fields and pointer fields , Data fields are used to store data , The pointer field is used to establish a connection with the next node . According to the organization of the pointer field and the connection form between the nodes , Linked list can be divided into single linked list 、 Double linked list 、 Circular linked list and other types , The following are the schematic diagrams of these common types of linked lists :

Single chain list

Single linked list is the simplest kind of linked list , It is characterized by only one pointer field pointing to the successor node (next), therefore , The traversal of a single linked list can only be done from the beginning to the end ( Usually NULL Null pointer ) Proceed in sequence .
 Insert picture description here

Double linked list

By designing two pointer fields, the first and the second , Double linked lists can be traversed in two directions , This is what distinguishes it from a single linked list . If you disrupt the antecedents 、 Subsequent dependencies , It can form " Binary tree "; If the precursor of the first node points to the last node of the list 、 The successor of the tail node points to the first node , It's a circular list ; If you design more pointer fields , Can form a variety of complex tree data structures .

 Insert picture description here

Circular linked list

The characteristic of circular linked list is that the successor of the tail node points to the first node . The diagram of double linked list has been given before , It is characterized by starting from any node , In either direction , You can find any data in the linked list . If you remove the precursor pointer , It's a single loop list .

 Insert picture description here

For more details on the linked list, see these two blogs
In the history, the most complete list of single chain operations such as adding, deleting, modifying, checking, reversing and so on 5 Sort algorithm
Explain the basic operation of double linked list .

Linux The linked list in the kernel

The implementation of common linked list is introduced above , You can see that the data fields are wrapped in the node pointer , Access the next set of data through the node pointer . however Linux The implementation of the linked list of the kernel can be said to be quite special , There's only the leading and subsequent pointers , And no data fields . The header file of the linked list is in include/list.h(Linux2.6 kernel ) Next . In practice , The linked list can also be used to copy the kernel , You need to stop making wheels .

Definition of linked list

The kernel list has only the preceding and subsequent pointers , It doesn't contain data fields , This list is universal , Easy to use . Therefore, it is easy to include the kernel linked list structure in any data structure , Very easy to expand . We just need to include the linked list structure in the data structure . Let's see the specific code .

 Insert picture description here
The structure of kernel linked list

// Chain table structure struct list_head{struct list_head *prev;struct list_head *next;};

When you need to use the linked list structure of the kernel , Just define one in the data structure struct list_head{} The structure member object of type can be . such , We can easily use a set of standard interfaces provided by the kernel to operate the linked list . We define a student structure , It contains student numbers and math scores . The structure is as follows :

 struct student{struct list_head list;// Put the linked list at the first place in the structure int ID;int math;   };

Initialization of linked list

Kernel Implementation

#define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)static inline void INIT_LIST_HEAD(struct list_head *list){
list->next = list;
list->prev = list;}

explain

INIT_LIST_HEAD and LIST_HEAD Can initialize the linked list , The difference between them is as follows :
LIST_HEAD(stu_list) When initializing the linked list, the linked list object will be created by the way .

//LIST_HEAD(stu_list) Expand as follows struct list_head stu_list= { &(stu_list), &(stu_list) };

INIT_LIST_HEAD(&stu1.stu_list) When initializing the linked list, we need to have a linked list object stu1_list.

` We can see that the initialization of the linked list is actually very simple , Is to let the precursor and successor of the linked list point to themselves .

give an example

INIT_LIST_HEAD(&stu1.stu_list);

Add nodes to linked list

Kernel Implementation

/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */#ifndef CONFIG_DEBUG_LISTstatic inline void __list_add(struct list_head *new,  struct list_head *prev,  struct list_head *next){
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;}#elseextern void __list_add(struct list_head *new,  struct list_head *prev,  struct list_head *next);#endif/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */#ifndef CONFIG_DEBUG_LISTstatic inline void list_add(struct list_head *new, struct list_head *head){__list_add(new, head, head->next);}#elseextern void list_add(struct list_head *new, struct list_head *head);#endif/**
 * list_add_tail - add a new entry
 * @new: new entry to be added
 * @head: list head to add it before
 *
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */static inline void list_add_tail(struct list_head *new, struct list_head *head){__list_add(new, head->prev, head);}

explain

list_add For head insertion , At the head of the list (head node ) Insert node before . At the end of the printing , Insert first, print first , Post insert post print . For example, the original linked list is 1->2->3, Use list_add Insert 4 After a ,4->1->2->3. Because linked lists are cyclical , And there's usually no concept of head and tail nodes , So any node can be regarded as head.
Empathy ,list_add_tail For tail insertion , At the end of the list (head node ) Insert node . At the end of the printing , Insert first and print later , The ones inserted later are printed first . For example, the original linked list is 1->2->3, Use list_add_tail Insert 4 After a ,1->2->3->4.

give an example

#include "mylist.h"#include <stdio.h>#include <stdlib.h>struct student{struct list_head stu_list;int ID;int math;   };int main(){struct student *p;struct student *q;struct student stu1;struct student stu2;  struct list_head *pos;// Initialization of linked list INIT_LIST_HEAD(&stu1.stu_list);INIT_LIST_HEAD(&stu2.stu_list);// Head insertion creates stu stu1 Linked list  for (int i = 0;i < 6;i++) { p = (struct student *)malloc(sizeof(struct student)); p->ID=i; p->math = i+80; // The first interpolation  list_add(&p->stu_list,&stu1.stu_list); // The tail interpolation  //list_add_tail(&p->list,&stu.list); } printf("list_add: \r\n");list_for_each(pos, &stu1.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos)->ID,((struct student*)pos)->math);}// Tail insertion creates stu stu1 Linked list  for (int i = 0;i < 6;i++) { p = (struct student *)malloc(sizeof(struct student)); p->ID=i; p->math = i+80; // The first interpolation  //list_add(&p->stu_list,&stu1.stu_list); // The tail interpolation  list_add_tail(&p->stu_list,&stu2.stu_list); } printf("list_add_tail: \r\n");list_for_each(pos, &stu2.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos)->ID,((struct student*)pos)->math);}return 0; }

 Insert picture description here

Linked list delete node

Kernel Implementation

// The original kernel set the location after deleting the linked list // # define POISON_POINTER_DELTA 0// #define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)// #define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)// So here we're going to set theta NULL  Defined in the kernel NULL  by 0#define NULL ((void *)0)#define LIST_POISON1  NULL#define LIST_POISON2  NULL/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */static inline void __list_del(struct list_head * prev, struct list_head * next){
next->prev = prev;
prev->next = next;}/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty() on entry does not return true after this, the entry is
 * in an undefined state.
 */#ifndef CONFIG_DEBUG_LISTstatic inline void list_del(struct list_head *entry){__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;}#elseextern void list_del(struct list_head *entry);#endif

explain

After the linked list is deleted ,entry The antecedent and successor of the will respectively point to LIST_POISON1 and LIST_POISON2, This is an area of kernel settings , But in this case, set it to NULL.

give an example

#include "mylist.h"#include <stdio.h>#include <stdlib.h>struct student{struct list_head stu_list;int ID;int math;   };int main(){struct student *p;struct student *q;struct student stu1;struct student stu2;  struct list_head *pos1;// Notice the pos2, We will explain why it is defined as struct student *pos2;//stu = (struct student*)malloc(sizeof(struct student));// Initialization of linked list INIT_LIST_HEAD(&stu1.stu_list);INIT_LIST_HEAD(&stu2.stu_list);LIST_HEAD(stu);// Head insertion creates stu stu1 Linked list  for (int i = 0;i < 6;i++) { p = (struct student *)malloc(sizeof(struct student)); p->ID=i; p->math = i+80; // The first interpolation  list_add(&p->stu_list,&stu1.stu_list); // The tail interpolation  //list_add_tail(&p->list,&stu.list); } printf("list_add: \r\n");list_for_each(pos1, &stu1.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);}// Delete list_for_each_entry(pos2,&stu1.stu_list,stu_list) {if (pos2->ID == 4) {list_del(&pos2->stu_list);break;}}printf("list_del\r\n");list_for_each_entry(pos2,&stu1.stu_list,stu_list) {printf("ID = %d,math = %d\n",pos2->ID,pos2->math);}return 0; }

 Insert picture description here

The linked list replaces the node

Kernel Implementation

/**
 * 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 inline void list_replace(struct list_head *old,struct list_head *new){
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;}static inline void list_replace_init(struct list_head *old,struct list_head *new){list_replace(old, new);INIT_LIST_HEAD(old);// Reinitialize }

explain

list_replace Replace the old node with a new node .
list_replace_init And list_replace The difference is ,list_replace_init The old node will be reinitialized , Let the forerunner and successor point to yourself .

give an example

#include "mylist.h"#include <stdio.h>#include <stdlib.h>struct student{struct list_head stu_list;int ID;int math;   };int main(){struct student *p;struct student *q;struct student stu1;struct student stu2;  struct list_head *pos1;struct student *pos2;struct student new_obj={.ID=100,.math=100}; //stu = (struct student*)malloc(sizeof(struct student));// Initialization of linked list INIT_LIST_HEAD(&stu1.stu_list);INIT_LIST_HEAD(&stu2.stu_list);LIST_HEAD(stu);// Head insertion creates stu stu1 Linked list  for (int i = 0;i < 6;i++) { p = (struct student *)malloc(sizeof(struct student)); p->ID=i; p->math = i+80; // The first interpolation  list_add(&p->stu_list,&stu1.stu_list); // The tail interpolation  //list_add_tail(&p->list,&stu.list); }printf("list_add: \r\n");list_for_each(pos1, &stu1.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);}
 // Replace list_for_each_entry(pos2,&stu1.stu_list,stu_list) {if (pos2->ID == 4) {list_replace(&pos2->stu_list,&new_obj.stu_list);break;}}printf("list_replace\r\n");list_for_each_entry(pos2,&stu1.stu_list,stu_list) {printf("ID = %d,math = %d\n",pos2->ID,pos2->math);}return 0; }

 Insert picture description here

Linked list delete and insert node

Kernel Implementation

/**
 * list_move - delete from one list and add as another's head
 * @list: the entry to move
 * @head: the head that will precede our entry
 */static inline void list_move(struct list_head *list, struct list_head *head){__list_del(list->prev, list->next);list_add(list, head);}/**
 * list_move_tail - delete from one list and add as another's tail
 * @list: the entry to move
 * @head: the head that will follow our entry
 */static inline void list_move_tail(struct list_head *list,
  struct list_head *head){__list_del(list->prev, list->next);list_add_tail(list, head);}

explain

list_move The function is to delete list Node to , At the same time, insert it into head in .list_move_tail and list_move The function is similar to , It's just that list The node is inserted into head Tail of .

give an example

#include "mylist.h"#include <stdio.h>#include <stdlib.h>struct student{struct list_head stu_list;int ID;int math;   };int main(){struct student *p;struct student *q;struct student stu1;struct student stu2;  struct list_head *pos1;struct student *pos2;struct student new_obj={.ID=100,.math=100}; //stu = (struct student*)malloc(sizeof(struct student));// Initialization of linked list INIT_LIST_HEAD(&stu1.stu_list);INIT_LIST_HEAD(&stu2.stu_list);LIST_HEAD(stu);// Head insertion creates stu stu1 Linked list  for (int i = 0;i < 6;i++) { p = (struct student *)malloc(sizeof(struct student)); p->ID=i; p->math = i+80; // The first interpolation  list_add(&p->stu_list,&stu1.stu_list); // The tail interpolation  //list_add_tail(&p->list,&stu.list); }printf("list_add: \r\n");list_for_each(pos1, &stu1.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);}
 // Shift and replace list_for_each_entry(pos2,&stu1.stu_list,stu_list) {if (pos2->ID == 0) {list_move(&pos2->stu_list,&stu1.stu_list);break;}}printf("list_move\r\n");list_for_each_entry(pos2,&stu1.stu_list,stu_list) {printf("ID = %d,math = %d\n",pos2->ID,pos2->math);}return 0; }

 Insert picture description here

The combination of linked lists

Kernel Implementation

static inline void __list_splice(struct list_head *list,
 struct list_head *head){struct list_head *first = list->next;struct list_head *last = list->prev;struct list_head *at = head->next;
first->prev = head;
head->next = first;
last->next = at;
at->prev = last;}/**
 * list_splice - join two lists
 * @list: the new list to add.
 * @head: the place to add it in the first list.
 */static inline void list_splice(struct list_head *list, struct list_head *head){if (!list_empty(list))__list_splice(list, head);}/**
 * list_splice_init - join two lists and reinitialise the emptied list.
 * @list: the new list to add.
 * @head: the place to add it in the first list.
 *
 * The list at @list is reinitialised
 */static inline void list_splice_init(struct list_head *list,struct list_head *head){if (!list_empty(list)) {__list_splice(list, head);INIT_LIST_HEAD(list);// empty }}

explain

list_splice The completed function is to merge two linked lists . Suppose there are two linked lists , The heads are stu_list1 and stu_list2( All are struct list_head Variable ), When calling list_splice(&stu_list1,&stu_list2) when , as long as stu_list1 Non empty ,stu_list1 The contents of the linked list will be linked to stu_list2 On the list , be located stu_list2 and stu_list2.next( primary stu_list2 The first node of the table ) Between . new stu_list2 The linked list will be original stu_list1 The first node of the table is the first node , And the tail node doesn't change .
 Insert picture description here

list_splice_init and list_splice similar , It's just after the merger , call INIT_LIST_HEAD(list) take list Set to empty chain .

Use cases

#include "mylist.h"#include <stdio.h>#include <stdlib.h>struct student{struct list_head stu_list;int ID;int math;   };int main(){struct student *p;struct student *q;struct student stu1;struct student stu2;  struct list_head *pos1;struct student *pos2;struct student new_obj={.ID=100,.math=100}; //stu = (struct student*)malloc(sizeof(struct student));// Initialization of linked list INIT_LIST_HEAD(&stu1.stu_list);INIT_LIST_HEAD(&stu2.stu_list);LIST_HEAD(stu);// Head insertion creates stu1 list Linked list  for (int i = 0;i < 6;i++) { p = (struct student *)malloc(sizeof(struct student)); p->ID=i; p->math = i+80; // The first interpolation  list_add(&p->stu_list,&stu1.stu_list); // The tail interpolation  //list_add_tail(&p->list,&stu.list); }printf("stu1: \r\n");list_for_each(pos1, &stu1.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);}// Head insertion creates stu2 list  Linked list  for (int i = 0;i < 3;i++) { q = (struct student *)malloc(sizeof(struct student)); q->ID=i; q->math = i+80; // The first interpolation  list_add(&q->stu_list,&stu2.stu_list); // The tail interpolation  //list_add_tail(&p->list,&stu.list); }printf("stu2: \r\n");list_for_each(pos1, &stu2.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);}// Merge list_splice(&stu1.stu_list,&stu2.stu_list);printf("list_splice\r\n");list_for_each(pos1, &stu2.stu_list) {printf("stu2 ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);}return 0; }

 Insert picture description here

Traversal of the list

Kernel Implementation

// Calculation member stay type Position in #define offsetof(type, member)  (size_t)(&((type*)0)->member)// according to member Get the address of type From #define container_of(ptr, type, member) ({          \
        const typeof(((type *)0)->member)*__mptr = (ptr);    \
    (type *)((char *)__mptr - offsetof(type, member)); })/**
 * list_entry - get the struct for this entry
 * @ptr: the &struct list_head pointer.
 * @type: the type of the struct this is embedded in.
 * @member: the name of the list_struct within the struct.
 */#define list_entry(ptr, type, member) \
container_of(ptr, type, member)/**
 * list_first_entry - get the first element from a list
 * @ptr: the list head to take the element from.
 * @type: the type of the struct this is embedded in.
 * @member: the name of the list_struct within the struct.
 *
 * Note, that list is expected to be not empty.
 */#define list_first_entry(ptr, type, member) \
list_entry((ptr)->next, type, member)/**
 * list_for_each - iterate over a list
 * @pos: the &struct list_head to use as a loop cursor.
 * @head: the head for your list.
 */#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
         pos = pos->next)/**
 * __list_for_each - iterate over a list
 * @pos: the &struct list_head to use as a loop cursor.
 * @head: the head for your list.
 *
 * This variant differs from list_for_each() in that it's the
 * simplest possible list iteration code, no prefetching is done.
 * Use this for code that knows the list to be very short (empty
 * or 1 entry) most of the time.
 */#define __list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)/**
 * list_for_each_prev - iterate over a list backwards
 * @pos: the &struct list_head to use as a loop cursor.
 * @head: the head for your list.
 */#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
         pos = pos->prev)/**
 * list_for_each_safe - iterate over a list safe against removal of list entry
 * @pos: the &struct list_head to use as a loop cursor.
 * @n: another &struct list_head to use as temporary storage
 * @head: the head for your list.
 */#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)/**
 * list_for_each_entry - iterate over list of given type
 * @pos: the type * to use as a loop cursor.
 * @head: the head for your list.
 * @member: the name of the list_struct within the struct.
 */#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
     prefetch(pos->member.next), &pos->member != (head);  \
     pos = list_entry(pos->member.next, typeof(*pos), member))/**
 * list_for_each_entry_reverse - iterate backwards over list of given type.
 * @pos: the type * to use as a loop cursor.
 * @head: the head for your list.
 * @member: the name of the list_struct within the struct.
 */#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_entry((head)->prev, typeof(*pos), member); \
     prefetch(pos->member.prev), &pos->member != (head);  \
     pos = list_entry(pos->member.prev, typeof(*pos), member))/**
 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
 * @pos: the type * to use as a start point
 * @head: the head of the list
 * @member: the name of the list_struct within the struct.
 *
 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
 */#define list_prepare_entry(pos, head, member) \
((pos) ? : list_entry(head, typeof(*pos), member))/**
 * list_for_each_entry_continue - continue iteration over list of given type
 * @pos: the type * to use as a loop cursor.
 * @head: the head for your list.
 * @member: the name of the list_struct within the struct.
 *
 * Continue to iterate over list of given type, continuing after
 * the current position.
 */#define list_for_each_entry_continue(pos, head, member)  \
for (pos = list_entry(pos->member.next, typeof(*pos), member); \
     prefetch(pos->member.next), &pos->member != (head); \
     pos = list_entry(pos->member.next, typeof(*pos), member))/**
 * list_for_each_entry_from - iterate over list of given type from the current point
 * @pos: the type * to use as a loop cursor.
 * @head: the head for your list.
 * @member: the name of the list_struct within the struct.
 *
 * Iterate over list of given type, continuing from current position.
 */#define list_for_each_entry_from(pos, head, member)  \
for (; prefetch(pos->member.next), &pos->member != (head); \
     pos = list_entry(pos->member.next, typeof(*pos), member))/**
 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 * @pos: the type * to use as a loop cursor.
 * @n: another type * to use as temporary storage
 * @head: the head for your list.
 * @member: the name of the list_struct within the struct.
 */#define list_for_each_entry_safe(pos, n, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member), \
n = list_entry(pos->member.next, typeof(*pos), member); \
     &pos->member != (head);  \
     pos = n, n = list_entry(n->member.next, typeof(*n), member))/**
 * list_for_each_entry_safe_continue
 * @pos: the type * to use as a loop cursor.
 * @n: another type * to use as temporary storage
 * @head: the head for your list.
 * @member: the name of the list_struct within the struct.
 *
 * Iterate over list of given type, continuing after current point,
 * safe against removal of list entry.
 */#define list_for_each_entry_safe_continue(pos, n, head, member)  \
for (pos = list_entry(pos->member.next, typeof(*pos), member),  \
n = list_entry(pos->member.next, typeof(*pos), member); \
     &pos->member != (head); \
     pos = n, n = list_entry(n->member.next, typeof(*n), member))/**
 * list_for_each_entry_safe_from
 * @pos: the type * to use as a loop cursor.
 * @n: another type * to use as temporary storage
 * @head: the head for your list.
 * @member: the name of the list_struct within the struct.
 *
 * Iterate over list of given type from current point, safe against
 * removal of list entry.
 */#define list_for_each_entry_safe_from(pos, n, head, member)  \
for (n = list_entry(pos->member.next, typeof(*pos), member); \
     &pos->member != (head); \
     pos = n, n = list_entry(n->member.next, typeof(*n), member))/**
 * list_for_each_entry_safe_reverse
 * @pos: the type * to use as a loop cursor.
 * @n: another type * to use as temporary storage
 * @head: the head for your list.
 * @member: the name of the list_struct within the struct.
 *
 * Iterate backwards over list of given type, safe against removal
 * of list entry.
 */#define list_for_each_entry_safe_reverse(pos, n, head, member) \
for (pos = list_entry((head)->prev, typeof(*pos), member), \
n = list_entry(pos->member.prev, typeof(*pos), member); \
     &pos->member != (head);  \
     pos = n, n = list_entry(n->member.prev, typeof(*n), member))

explain

list_entry(ptr, type, member) You can get the address of the node structure , After getting the address, you can operate on the elements in the structure . rely on list_entry(ptr, type, member) function , You don't need to know how to add, delete, check and modify the kernel linked list list_head Objects embedded in a structure , You can do all kinds of operations .( Why do we use container_of To define list_entry(ptr, type, member) The structure , It will be explained in detail below )
list_first_entry(ptr, type, member) What you get is the address of the first element in the structure
list_for_each(pos, head) Is used to traverse the linked list forward ,pos Equivalent to a temporary node , It's used to keep pointing to the next node .
list_for_each_prev(pos, head) and list_for_each_entry_reverse(pos, head, member) It's used to traverse the list backwards
list_for_each_safe(pos, n, head) and list_for_each_entry_safe(pos, n, head, member), These two functions are to avoid the process of traversing the linked list pos When a node is released, it will cause a chain break. In this case, we need to provide another link with pos Pointer of the same type n, stay for Temporary storage in the loop pos The address of the next node .( The design of the kernel is really comprehensive !)
list_prepare_entry(pos, head, member) Used to prepare the first address of a structure , Use in list_for_each_entry_contine() in
list_for_each_entry_continue(pos, head, member) From the current pos The next node starts to traverse the rest of the linked list , barring pos. If we were to pos、head、member Pass in list_for_each_entry, This macro will traverse from the head node of the linked list .
list_for_each_entry_continue_reverse(pos, head, member) From the present pos The previous node starts to traverse the rest of the linked list , barring pos.
list_for_each_entry_from(pos, head, member) from pos Start traversing the rest of the linked list .
list_for_each_entry_safe_continue(pos, n, head, member) from pos The next node of the node starts traversing the remaining linked list , And prevent the traversal error caused by deleting the linked list nodes .
list_for_each_entry_safe_from(pos, n, head, member) from pos Continue traversing the remaining nodes of the list , And prevent the traversal error caused by deleting the linked list nodes . And list_for_each_entry_safe_continue(pos, n, head, member) The difference is that in the first traversal ,pos It doesn't point to its next node , But from pos To traverse the .
list_for_each_entry_safe_reverse(pos, n, head, member) from pos The previous node starts traversing a linked list backward , And prevent the traversal error caused by deleting the linked list nodes .
list_safe_reset_next(pos, n, member) Returns the current pos Of the next node type The first address of the structure .

give an example

#include "mylist.h"#include <stdio.h>#include <stdlib.h>struct student{struct list_head stu_list;int ID;int math;   };int main(){struct student *p;struct student *q;struct student stu1;struct student stu2;  struct list_head *pos1;struct student *pos2;struct student new_obj={.ID=100,.math=100}; //stu = (struct student*)malloc(sizeof(struct student));// Initialization of linked list INIT_LIST_HEAD(&stu1.stu_list);INIT_LIST_HEAD(&stu2.stu_list);LIST_HEAD(stu);// Head insertion creates stu stu1 Linked list  for (int i = 0;i < 6;i++) { p = (struct student *)malloc(sizeof(struct student)); p->ID=i; p->math = i+80; // The first interpolation  list_add(&p->stu_list,&stu1.stu_list); // The tail interpolation  //list_add_tail(&p->list,&stu.list); }printf("stu1: \r\n");list_for_each(pos1, &stu1.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);}printf("list_for_each_prev\r\n");list_for_each_prev(pos1, &stu1.stu_list){printf("stu2 ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);}return 0; }

 Insert picture description here
The examples are not all written out , If you are interested, you can try it yourself .

Question answer

Before we defined the structure, we put struct list_head First of all , When using list_for_each When traversing ,pos The position obtained is the position of the structure , That is, the location of the linked list . As shown below

 struct student{struct list_head list;// Put the linked list at the first place in the structure int ID;int math;   };

    list_for_each(pos, &stu1.stu_list) {printf("ID = %d,math = %d\n",((struct student*)pos)->ID,((struct student*)pos)->math);}

But when we put struct list_head list; At the end of the day ,pos Obviously, the location of the list is not the location of the list , So when we call again list_for_each It's going to go wrong .

 struct student{  int ID;int math;   struct list_head list;// Put the linked list at the first place in the structure };

list_for_each_entry This function means to get... When traversing entry, In this macro pos Pointer whose type is a container structure type , This is the same as the front list_for_each The types used in are no longer the same ( That's why we define it separately pos1 and pos2 The reason why the ), But it's also a matter of course , After all, now pos, I'm going to use this pointer to access members of the data domain age 了 ;head You use INIT_LIST_HEAD The object initialized , Pointer to the head , Be careful , It's not the head node ;member It is the linked list element object in the container structure . Use this macro instead of the previous method . This is where it comes in container_of This macro .( Again, the greatness of the kernel designer ).

About container_of Macros will be detailed in the next article , Here you know how to use it .

list.h Porting source code

Here's a little bit of attention , If it's in GNU Use in GCC Program development , You can make no changes , Use the above function directly ; But if you want to port it to Windows Use in the environment , You can directly prefetch Delete the statement , because prefetch This function is used to manually prefetch data , Reduced read latency , This improves performance , That is to say prefetch yes GCC Functions used to improve efficiency , If you want to migrate to non GNU Environmental Science , It can be changed to prefetch function of corresponding environment or delete directly , It doesn't affect the function of the linked list .

/*
 * @Description:  transplant Linux2.6 kernel list.h
 * @Version: V1.0
 * @Autor: https://blog.csdn.net/qq_16933601
 * @Date: 2020-09-12 22:54:51
 * @LastEditors: Carlos
 * @LastEditTime: 2020-09-16 00:35:17
 */#ifndef _MYLIST_H#define _MYLIST_H
 // The original linked list after the deletion of the location , Here we change it to  0// # define POISON_POINTER_DELTA 0// #define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)// #define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)#define NULL ((void *)0)#define LIST_POISON1  NULL#define LIST_POISON2  NULL// Calculation member stay type Position in #define offsetof(type, member)  (size_t)(&((type*)0)->member)// according to member Get the address of type From #define container_of(ptr, type, member) ({          \
        const typeof(((type *)0)->member)*__mptr = (ptr);    \
    (type *)((char *)__mptr - offsetof(type, member)); })// Chain table structure struct list_head{struct list_head *prev;struct list_head *next;};#define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)static inline void INIT_LIST_HEAD(struct list_head *list){
list->next = list;
list->prev = list;}static inline void init_list_head(struct list_head *list){list->prev = list;list->next = list;}#ifndef CONFIG_DEBUG_LISTstatic inline void __list_add(struct list_head *new,  struct list_head *prev,  struct list_head *next){
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;}#elseextern void __list_add(struct list_head *new,  struct list_head *prev,  struct list_head *next);#endif// Add... From the head /**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */#ifndef CONFIG_DEBUG_LISTstatic inline void list_add(struct list_head *new, struct list_head *head){__list_add(new, head, head->next);}#elseextern void list_add(struct list_head *new, struct list_head *head);#endif// Add from tail static inline void list_add_tail(struct list_head *new, struct list_head *head){__list_add(new, head->prev, head);}static inline  void __list_del(struct list_head *prev, struct list_head *next){prev->next = next;next->prev = prev;}static inline void list_del(struct list_head *entry){__list_del(entry->prev, entry->next);entry->next = LIST_POISON1;entry->prev = LIST_POISON2;}static inline void __list_splice(struct list_head *list,
 struct list_head *head){struct list_head *first = list->next;struct list_head *last = list->prev;struct list_head *at = head->next;
first->prev = head;
head->next = first;
last->next = at;
at->prev = last;}/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */static inline int list_empty(const struct list_head *head){return head->next == head;}/**
 * list_splice - join two lists
 * @list: the new list to add.
 * @head: the place to add it in the first list.
 */static inline void list_splice(struct list_head *list, struct list_head *head){if (!list_empty(list))__list_splice(list, head);}/**
 * 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 inline void list_replace(struct list_head *old,struct list_head *new){
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;}static inline void list_replace_init(struct list_head *old,struct list_head *new){list_replace(old, new);INIT_LIST_HEAD(old);}/**
 * list_move - delete from one list and add as another's head
 * @list: the entry to move
 * @head: the head that will precede our entry
 */static inline void list_move(struct list_head *list, struct list_head *head){__list_del(list->prev, list->next);list_add(list, head);}/**
 * list_move_tail - delete from one list and add as another's tail
 * @list: the entry to move
 * @head: the head that will follow our entry
 */static inline void list_move_tail(struct list_head *list,
  struct list_head *head){__list_del(list->prev, list->next);list_add_tail(list, head);}#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)#define list_first_entry(ptr, type, member) \
    list_entry((ptr)->next, type, member)#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)/**
 * list_for_each_entry - iterate over list of given type
 * @pos: the type * to use as a loop cursor.
 * @head: the head for your list.
 * @member: the name of the list_struct within the struct.
 */#define list_for_each_entry(pos, head, member)      \
for (pos = list_entry((head)->next, typeof(*pos), member); \
     &pos->member != (head);  \
     pos = list_entry(pos->member.next, typeof(*pos), member))/**
 * list_for_each_prev - iterate over a list backwards
 * @pos: the &struct list_head to use as a loop cursor.
 * @head: the head for your list.
 */#define list_for_each_prev(pos, head) \
for (pos = (head)->prev;  pos != (head); \
         pos = pos->prev)

Develop habits , Praise first and then watch ! If you think it's good , Welcome to your attention , give the thumbs-up , Collection , forward , thank you !
The above code is the code after testing . If there are mistakes and mistakes , Welcome to point out .