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

Editor to share with you what the Linux kernel device driver kernel linked list is useful, I believe most people do not know much about it, so share this article for your reference, I hope you will learn a lot after reading this article, let's learn about it!

/ * * Application of linked lists in kernel * /

(1) introduction

A large number of linked list structures are used in the Linux kernel to organize data, including device lists and data organization in various functional modules. Most of these linked lists adopt a rather wonderful linked list data structure implemented in include/linux/list.h.

The definition of the linked list data structure is simple:

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

The list_head structure contains two pointers to the list_head structure, prev and next, and the kernel's data structures are usually organized into double circular linked lists.

Unlike the previously introduced double-linked list structure model, the list_head here has no data fields. In the Linux kernel linked list, instead of containing data in the linked list structure, the linked list nodes are included in the data structure. Such as:

Struct my_struct {struct list_head list; unsigned long dog; void * cat;}

Linked lists in linux do not have a fixed header and can be accessed from any element. Traversing the linked list simply starts at one node and accesses the next node along the pointer until it returns to the original node. Each individual node can be called a chain header.

(2) initialization of linked list

a. Static state

If you create the linked list statically at compile time and reference it directly, as follows:

Struct my_struct mine= {.dogs = LIST_HEAD_INIT (mine.list); .dog = 0, .cat = NULL}; / / or static LIST_HEAD (fox); / * equals struct list_head fox = LIST_HEAD_INIT (fox); * /

b. Dynamic

Struct my_struct * ptterp = kmalloc (GFP_KERNEL, sizeof (my_struct)); p-> dog = 0There p-> cat = NULL;INIT_LIST_HEAD (& p-> list)

(3) operate the linked list

The kernel provides a set of functions to manipulate linked lists.

Be careful! These functions take one or more list_head structure pointers as arguments. Defined in

a. Add nodes

List_add (struct list_head * new, struct list_head * head); / / insert a new node after the head node of the specified linked list

b. Add nodes to the end of the chain list

List_add_tail (struct list_head * new, struct list_head * head); / / insert a new node before the head node of the specified linked list

c. Remove a node from the linked list

List_del (struct list_head * entry); / / remove entry from the linked list

d. Move nodes from one linked list to another

List_move (struct list_head * list, struct list_head * head)

Remove the list item from a linked list and insert it after the head

E.list_empty (struct list_head * head)

A non-zero value is returned if the linked list is empty, otherwise 0 is returned.

f. Merge linked list

List_splice (struct list_head * list, struct list_head * head); / / attention! The new linked list does not include list nodes

(4) traversing linked list

The linked list itself is not important, it is important to access the structure that contains the linked list.

a. Get the pointer to the structure containing the linked list from the linked list pointer

List_entry (struct list_head * ptr, type_of_struct, field_name)

Ptr: list_head pointer

Type_of_struct: the structure type that contains ptr

Field_name: the name of the linked list field in the structure

Such as:

My_struct * p = (list_head * ptr, my_struct, list)

b. Traversing linked list

List_for_each (struct list_head * cursor, struct list_head * list); / / often used with list_entry / / Note! Traversing with list_for_each, excluding header nodes

c. Get the pointer of the large structure while traversing

List_for_each_entry (type * cursor, struct list_head * list, member)

d. Release each traversed node while traversing the linked list

List_for_each_entry_safe (type * cursor, type * tmp; struct list_head * list, member); these are all the contents of the article "what is the use of linked lists in Linux kernel device drivers?" Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

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.