Shulou(Shulou.com)06/02 Report--

Description

A general bi-directional linked list library is encapsulated in the linux kernel. This general linked list library has good expansibility and encapsulation. It provides us with a fixed pointer domain structure. When we use it, we only need to include this pointer domain structure in our defined data domain structure. We do not need to care about the specific implementation and link. Just call the relevant interface provided to us.

Traditional linked list structure

Struct node {int key; int val; node* prev; node* next;}

General linked list Library structure of linux Kernel

The pointer domain structure provided to us:

Struct list_head {struct list_head * next, * prev;}

We just need to include it:

Struct node {int val; int key; struct list_head* head;}

You can see that our data layer is separated from the driver layer through this list_head structure, and the various operation method interfaces provided by the kernel only care about the list_head structure, that is, when you link to this list_head structure, you don't care about what type your data layer defines.

Some interface macro definitions

/ / initialize header pointer # define LIST_HEAD_INIT (name) {& (name), & (name)} # define LIST_HEAD (name)\ struct list_head name = LIST_HEAD_INIT (name) / / traversal linked list # define _ list_for_each (pos, head)\ for (pos = (head)-> next; pos! = (head) Pos = pos- > next) / / get the node header address (not the list_head address, but the data layer node header address) # define list_entry (ptr, type, member)\ container_of (ptr, type, member) / / container_of is a common macro in the Linux kernel to obtain a pointer to the structure itself from a pointer contained in a / / structure Generally speaking, it is to obtain the first address of the whole structural variable # define container_of (ptr, type, member) ({\ const typeof (type *) 0)-> member) * _ mptr = (ptr) through the first address of a member in the structural variable / quantity. \ (type *) ((char *) _ mptr-offsetof (type,member));}) # define offsetof (s * m) (size_t) & ((s *) 0)-> m)

Mode of use

Typedef struct node {int val; int key; struct list_head* list;} node;// initialize header pointer LIST_HEAD (head); / / create node node* a = malloc (sizeof (node)); node* b = malloc (sizeof (node)); / / insert linked list mode-list _ add (& a-> list,&head); list_add (& b-> list,&head); / / insert linked list mode 2 list _ add_tail (& a-> list,&head) List_add_tail (& b-> list,&head); / / iterate through the linked list struct list_head* psitstruct node* n itsranking listings for each (precedence head) {/ / return the list_head address, and then deduce / / the head address of the node structure through the list_head address. N = list_entry (pos,struct node,list);}

List_add interface, first-in-and-out principle, similar to stack

List_add- first in and out mode

List_add_tail interface, first-in, first-out principle, similar to fifo

List_add- first in first out mode

The actual display form of our linked list node in memory

Node description

You can see that the final form is by pointing to the list_head type pointers in each structure, and then concatenating them

The list_entry interface deduces the header address of the structure by changing the address of a member, just as the _ _ list_for_each interface only returns the list_head address, so we need to obtain the header address of the structure itself through this member address, and the underlying implementation method container_of macro

Extrapolate the head address of the structure

For instance

This example includes simple add, delete, and traversal.

# include # include MODULE_LICENSE ("GPL"); MODULE_AUTHOR ("David Xie"); MODULE_DESCRIPTION ("List Module"); MODULE_ALIAS ("List module"); struct student / / represents the structure of an actual node {char name; int num; struct list_head list; / / node structure in the kernel linked list}; struct student * pstudent; struct student * tmp_student; struct list_head student_list Struct list_head * pos; int mylist_init (void) {int I = 0; / / initialize a linked list, which actually points the prev and next of student_list to its own INIT_LIST_HEAD (& student_list); pstudent = kmalloc (sizeof (struct student) * 5); / / applies to the kernel for 5 student structure spaces memset (pstudent,0,sizeof (struct student) * 5) / / empty, these two functions can be done by kzalloc alone to for;} return 0;} void mylist_exit (void) {int I; / * experiment: replace for with list_for_each to traverse the deleted node, observe the phenomena to occur, and consider the solution * / for

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.