This is my second article about getting started

Using the traditional linked list structure will cause a lot of redundant code and reduce the problem of code reuse

// Traditional linked lists
struct listNode {
	struct list *pre;
	struct list *next;
	void *data;
};
Copy the code

There are many places in the Linux kernel source code that require bidirectional circular lists to organize data. For this reason, the Linux kernel source code provides a two-way circular linked list in include/ Linux /list.h. We can modify it directly or learn how to implement it.

In Linux, linked lists are implemented by separating data from nodes. In this way, the efficiency of traversal and other operations can be greatly improved.

// double loop linked list
struct list_head {
	struct list_head *next, *prev;
};

// A linked list for the hash table
/* List header */
struct hlist_head {
	struct hlist_node *first;
};
/* List node */
struct hlist_node {
	struct hlist_node *next, * *pprev;
};
Copy the code

In this struct type definition, there are no data members; their main function is to serve as nested links in the definitions of other struct types.

Initialize the

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)
/** * INIT_LIST_HEAD - Initialize a list_head structure * @list: list_head structure to be initialized. * * Initializes the list_head to point to itself. If it is a list header, * the result is an empty list. */
static inline void INIT_LIST_HEAD(struct list_head *list)
{
	WRITE_ONCE(list->next, list);
	list->prev = list;
}
Copy the code

The above macro completes the initialization of the linked list, pointing the front and back Pointers to itself.

Other Basic Operations

The instance

The following list construct links nodes of this structure type together to form a list by defining a list_head pointer member. No matter how the data structure of the nodes in a linked list changes, the head of the list only needs to be 8 bytes.

// The nodes in the list are defined as follows
struct list {
	struct list_head list_head;
	void *data;
};
Copy the code

Advantage:

One of the great advantages of Linux’s kernel linked lists is that all operations of any data linked list are completely unified because its standard implementation (or “small structure”) can be easily embedded into any node. In addition, even if the node members are upgraded and modified during code maintenance, the original linked list structure of the node is not affected at all.

The structure of kernel linked list is divided into two parts: data domain and pointer domain. The pointer field is divided into head pointer and tail pointer. The head pointer points to the previous data, and the tail pointer points to the next data. The header makes the whole list loop. The information stored in heap space is shown in Figure 3.

Data store status diagram

Usage scenarios

  1. If you want to allocate and release memory units dynamically according to the needs in C language program, you can usually use linked list structure to organize data.
  2. You can define one or more list_head Pointers in a user-defined structure type for linking different linked lists.