Requirements for use
In order to use the linked list operation macro in list.h, we need to make a change to the structure when defining the structure, and add one more to the structure
structure
list_head
Type fields such as:
typedef struct student
{
char first_name[MAX_STRING_LENGTH];
char last_name[MAX_STRING_LENGTH];
unsigned int age;
struct list_head node_student;
}student_t;
So what is list_head used for in list.h? Let’s see its definition
// import from include/linux/types.h
struct list_head {
struct list_head *next, *prev;
};
Obviously this structure can be used to record the position of the previous element and the next element.
Initialization (INIT_LIST_HEAD)
Before operating the linked list, we first need to specify the linked list header for the linked list to facilitate management. Many parameters in the subsequent operation interface are also related to the linked list header. Before the operation, we must first define a
structure
list_head
The variable is used as the head of the linked list, and then passed
INIT_LIST_HEAD
Interface to initialize the head node.
struct list_head class; INIT_LIST_HEAD( & amp; class);
Where INIT_LIST_HEAD is defined in list.h as follows
static inline void INIT_LIST_HEAD(struct list_head *list) {
list->next = list;
list->prev = list;
}
As you can see, he initialized the list_head node so that it first points to itself.
Add element (list_add_tail)
After defining a node element, you can use the list_add_tail macro to add the node to the linked list
For example:
student_t *stu = NULL;
/* Create node. */
if ((stu = make_student("Pierre", "Dupont", 16)) == NULL)
{
fprintf(stderr, "Failed to create Pierre.\
");
return -1;
}
/*Add stu to the linked list*/
list_add_tail( &stu->node_student, &class);
It can be seen that the first parameter of list_add_tail is the node to be added
structure
list_head
The address of the type field, the second parameter is the address of the head node
Definitions in list.h
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
where __list_add is defined as
static 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;
}
Readers can draw a picture by themselves, and it is not difficult to find that what the list_add_tail macro implements is a header-like interpolation method, which inserts the node in front of the head node, but the position of the head node will not change, that is, as we defined at the beginning The head node is the head, and the new node is always inserted in front of the head node, so you can see that the operation in __list_add is to insert the new node between the head node and the element in front of the head node.
Traverse operation (list_for_each_entry)
Operation example:
student_t *stu = NULL;
/* Print all students in class. */
printf("All the students in class.\
");
list_for_each_entry(stu, & class, node_student)
{
printf("First name: %s\
", stu->first_name);
printf("Last name: %s\
", stu->last_name);
printf("Age: %u\
\
", stu->age);
}
Let’s take a look at how to define in list.h
list_for_each_entry
of
/** * 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_head within the struct. */ #define list_for_each_entry(pos, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member); \ &pos->member != (head); \ pos = list_next_entry(pos, member))
list_for_each_entry
The first parameter is a node pointer, used to access node elements, the second parameter is the head node pointer, and the third parameter is defined in the node
structure
list_head
the name of the type field,
list_first_entry
is to return the node address of the next node of the head node, because the head node is a
structure
list_head
Type, no data element field, only for management,
list_next_entry
is to find the next node, so list_for_each_entry
Managed a for loop to traverse the linked list elements.
Merge linked list (list_splice_init)
This operation is to use another head to manage this linked list or add one linked list to another linked list, for example:
list_splice_init( &class, &bus);
The above code means to add the linked list managed by the class to the bus and let the bus manage it.
where list.h is right
list_splice_init
is defined as:
/**
* list_splice_init - join two lists and reinitialize 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, head->next);
INIT_LIST_HEAD(list);
}
}
__list_splice is defined as follows
static inline void __list_splice(const struct list_head *list, struct list_head *prev, struct list_head *next)
{
struct list_head *first = list->next;
struct list_head *last = list->prev;
first->prev = prev;
prev->next = first;
last->next = next;
next->prev = last;
}
Readers can clearly know by drawing pictures, list_splice_init
It is to add the linked list managed by head head node to the linked list managed by list, INIT_LIST_HEAD
It is to initialize the head node, that is, to break away from the connection with the original linked list.
Delete element (list_del)
Example usage:
student_t *tmp = NULL;
student_t *stu = NULL;
list_for_each_entry_safe(stu, tmp, & bus, node_student)
{
if (strcmp(stu->first_name, "Celine") == 0)
{
list_del( & amp;stu->node_student);
free(stu);
}
}
The example is to delete the node whose first_name element is named Celine in the linked list, and use
list_for_each_entry_safe
Traversing the linked list, this is the same as what we mentioned earlier
list_for_each_entry
It is not the same, let’s first look at how to define in list.h
list_for_each_entry_safe
of
/** * 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_head within the struct. */ #define list_for_each_entry_safe(pos, n, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member), \ n = list_next_entry(pos, member); \ &pos->member != (head); \ pos = n, n = list_next_entry(n, member))
can be seen
list_for_each_entry_safe
relative to
list_for_each_entry
one more parameter
n,
It is used for traversal, because list_for_each_entry_safe
is to cooperate with the delete operation, so
pos
The node pointed to may be deleted, while n
Points to the node next to the node that may be deleted.
look again
list_del
Definition in list.h
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
where __list_del is defined as
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
next->prev = prev;
prev->next = next;
}
It is not difficult to see that list_del is to delete the entry node from the node, where LIST_POISON1 and LIST_POISON2 are
Used to verify that no one is using uninitialized list items.
#define POISON_POINTER_DELTA (0) #define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA) #define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)