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

This article will explain in detail the source code analysis of the list linked list in the linux kernel. The content of the article is of high quality, so the editor shares it for you as a reference. I hope you will have a certain understanding of the relevant knowledge after reading this article.

Many data structures in linux kernel are classic, and the list linked list is one of them. The editor will introduce the list linked list from the following aspects: the definition of list, the operation methods provided by list, matters needing attention, and use examples.

Preface

Many data structures in linux kernel are classic, and list linked list is one of them.

List linked list

1 the file where the List is located

All operations of List can be found at include/linux/list.h

The definition of List head can be found at include/linux/types.h

2 definition

This is actually a two-way circular linked list with a header pointer.

Definition of list head:

In this definition, there are only forward and backward pointers, and there are no data parts, so we basically know that it is not used alone, but is embedded in the user-defined struct, stringing the user-defined data structures together into a list.

The idea is very ingenious, the intrusiveness to the user-defined data structure is very small, and the function of std::List template in C++ is realized.

Although this definition is called head, it is also embedded in user-defined data structures.

3 methods of operation provided by list

Initialization

Insert operation

Insert an element between two elements, that is, insert new into prev and next. This function is the basis for the following implementation of inserting at the head and tail

Insert in the header, between the header pointer and the first element

Insert at the tail, insert between the last element and the header pointer, because it's a circular linked list.

Delete operation

Delete an element between two elements

Delete a known element entry

Replace operation

It's all the transformation of the pointer.

Mobile operation

Move one element to the header of another list

Move one element to the end of another list

Split operation

Split a queue into two queues from a specified location

List is the head pointer to the new queue, including elements from the first element of the original head queue to entry, and the head queue includes only the remaining elements

Merge operation

Insert the list list between prev and next except list itself

Insert one list into the head of another list

Insert one list at the end of another list

List_ entry macro

As mentioned before, this list_head is to be embedded in the user-defined struct. This list_head ptr is used to get the pointer to the current struct object, using linux's classic macro to define the container_of.

A bunch of macro definitions for various traverses to get entry

4 points for attention

Just say one, that is, multi-thread operation of the same list, or need to be locked

5 use examples

On the linux kernel list linked list source code analysis is shared here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

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.