"In the Linux kernel, there is a general two-way circular linked list, which forms the basis of various queues. The structure definition and related functions of the linked list are in include / Linux / list. H. here is a comprehensive introduction to various APIs of the linked list.
struct list_ head { struct list_ head *next, *prev;};
This is the element structure of the linked list. Because it is a circular linked list, the header and nodes in the table are of this structure. There are two pointers, prev and next, which point to the previous node and the next node in the linked list respectively.
/* * Simple doubly linked list implementation. * * Some of the internal funcTIons (""__ xxx"") are useful when * manipulaTIng whole lists rather than single entries, as * someTImes we already know the next/prev entries and we can * generate better code by using them directly rather than * using the generic single-entry routines. */#define LIST_ HEAD_ INIT(name) { &(name), &(name) }#define LIST_ HEAD(name) \ struct list_ head name =LIST_ HEAD_ INIT(name)static inline void INIT_ LIST_ HEAD(struct list_ head *list){ list->next = list; list->prev = list;}
During initialization, the prev and next of the chain header point to itself.
/* * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */# ifndef CONFIG_ DEBUG_ LISTstatic 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;}# elseextern void __ list_ add(struct list_ head *new, struct list_ head *prev, struct list_ head *next);# endif/** * list_ add - add a new entry * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */static inline void list_ add(struct list_ head *new, struct list_ head *head){__ list_ add(new, head, head->next);}/** * list_ add_ tail - add a new entry * @new: new entry to be added * @head: list head to add it before * * Insert a new entry before the specified head. * This is useful for implementing queues. */static inline void list_ add_ tail(struct list_ head *new, struct list_ head *head){__ list_ add(new, head->prev, head);}
There are few exceptions to the implementation of two-way circular linked list, which can be handled in a public way. The method used here is the same whether adding the first node or other nodes.
In addition, the implementation of linked list API is generally divided into two layers: one is external, such as list_ add、list_ add_ Tail is used to eliminate some exceptions and call the internal implementation; The first layer is internal, and the function name will be double underlined, such as__ list_ Add is often the common part of several operations, or the implementation after excluding exceptions.
/* * Delete a list entry by making the prev/next entries * point to each other. * * This is only for internal list manipulation where we know * the prev/next entries already! */ static inline void __ list_ del(struct list_ head * prev, struct list_ head * next){ next->prev = prev; prev->next = next;}/** * list_ del - deletes entry from list. * @entry: the element to delete from the list. * Note: list_ empty() on entry does not return true after this, the entry is * in an undefined state. */#ifndef CONFIG_ DEBUG_ LISTstatic inline void list_ del(struct list_ head *entry){ __ list_ del(entry->prev, entry->next); entry->next = LIST_ POISON1; entry->prev = LIST_ POISON2;}# elseextern void list_ del(struct list_ head *entry);# endif/** * list_ del_ init - deletes entry from list and reinitialize it. * @entry: the element to delete from the list. */static inline void list_ del_ init(struct list_ head *entry){ __ list_ del(entry->prev, entry->next); INIT_ LIST_ HEAD(entry);}
list_ Del is the deletion of nodes in the linked list. Why are you calling__ list_ Del then points the next and prev of the deleted element to a special list_ Position1 and list_ Position2 is used to debug undefined pointers.
list_ del_ Init is to initialize the pointer in the node again after deleting the node. This deletion method is more practical.
/** * list_ replace - replace old entry by new one * @old : the element to be replaced * @new : the new element to insert * * If @old was empty, it will be overwritten. */static inline void list_ replace(struct list_ head *old, struct list_ head *new){ new->next = old->next; new->next->prev = new; new->prev = old->prev; new->prev->next = new;} static inline void list_ replace_ init(struct list_ head *old, struct list_ head *new){ list_ replace(old, new); INIT_ LIST_ HEAD(old);}
list_ Replace is to replace one node old in the linked list with another node new. From the implementation point of view, even if the linked list where old is located has only one node, new can be successfully replaced. This is the terrible universality of two-way circular linked lists.
list_ replace_ Init the old that will be replaced is initialized again.
/** * list_ move - delete from one list and add as another's head * @list: the entry to move * @head: the head that will precede our entry */static inline void list_ move(struct list_ head *list, struct list_ head *head){ __ list_ del(list->prev, list->next); list_ add(list, head);}/** * list_ move_ tail - delete from one list and add as another's tail * @list: the entry to move * @head: the head that will follow our entry */static inline void list_ move_ tail(struct list_ head *list, struct list_ head *head){ __ list_ del(list->prev, list->next); list_ add_ tail(list, head);}
list_ The function of move is to remove the list node from the original linked list and add it to the new linked list head.
list_ move_ Tail is only associated with list when adding a new linked list_ Move is different, list_ Move is the head of the linked list after the head, and list_ move_ Tail is the tail of the linked list before the head.
/** * list_ is_ last - tests whether @list is the last entry in list @head * @list: the entry to test * @head: the head of the list */static inline int list_ is_ last(const struct list_ head *list, const struct list_ head *head){ return list->next == head;}
list_ is_ Last determines whether the list is at the end of the head linked list.
/** * list_ empty - tests whether a list is empty * @head: the list to test. */static inline int list_ empty(const struct list_ head *head){ return head->next == head;}/** * list_ empty_ carefu
Our other product:
