大家好，我是极客范的本期栏目编辑小友，现在为大家讲解了解Linux通用的双向循环链表问题。
在Linux操作系统操作系统内核中，有一种通用的双向循环链表，构成了各种队列的基础。链表的结构定义和相关函数均在include/linux/list.h中，下面就来全面的介绍这一链表的各种原料药。
struct list _ head { struct list _ head * next，* prev }；
这是链表的元素结构。因为是循环链表，表头和表中节点都是这一结构。有上一个和然后两个指针，分别指向链表中前一节点和后一节点。
/* *简单的双链表实现。* *一些内部函数(“__xxx”)在*操作整个列表而不是单个条目时很有用，因为*有时我们已经知道下一个/上一个条目，我们可以*直接使用它们而不是*使用通用的单条目例程来生成更好的代码*/#定义LIST _ HEAD _ INIT(名称){(名称)，(名称)} #定义LIST _ HEAD(名称)\ struct LIST _ HEAD名称=LIST _ HEAD _ INIT(名称)静态内联void INIT _ LIST _ HEAD(struct LIST _ HEAD * LIST){ LIST-next=LIST；list-prev=list；}
在初始化的时候，链表头的上一个和然后都是指向自身的。
/* *在两个已知的连续条目之间插入一个新条目。* *这仅用于我们已经知道*上一个/下一个条目的内部列表操作！*/# if ndef 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 -添加新条目* @new:要添加的新条目* @head:列表头将其添加到* *之后在指定的头后插入新条目。*这有利于实现堆栈。*/静态内联void list _ add(struct list _ head * new，struct list _ head * head){ _ _ list _ add(new，head，head-next)；}/*** list_add_tail -添加新条目* @new:要添加的新条目* @head:列表头将其添加到* *之前在指定的头之前插入新条目。*这对于实现队列很有用。*/静态内联void list _ add _ tail(struct list _ head * new，struct list _ head * head){ _ _ list _ add(new，head-prev，head)；}
t-indent: 2em;">双向循环链表的实现，很少有例外情况，基本都可以用公共的方式来处理。这里无论是加第一个节点，还是其它的节点，使用的方法都一样。另外，链表API实现时大致都是分为两层：一层外部的，如list_add、list_add_tail，用来消除一些例外情况，调用内部实现；一层是内部的，函数名前会加双下划线，如__list_add，往往是几个操作公共的部分，或者排除例外后的实现。/* * 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是链表中节点的删除。之所以在调用__list_del后又把被删除元素的next、prev指向特殊的LIST_POSITION1和LIST_POSITION2，是为了调试未定义的指针。list_del_init则是删除节点后，随即把节点中指针再次初始化，这种删除方式更为实用。
/** * 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是将链表中一个节点old，替换为另一个节点new。从实现来看，即使old所在地链表只有old一个节点，new也可以成功替换，这就是双向循环链表可怕的通用之处。list_replace_init将被替换的old随即又初始化。
/** * 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_move的作用是把list节点从原链表中去除，并加入新的链表head中。list_move_tail只在加入新链表时与list_move有所不同，list_move是加到head之后的链表头部，而list_move_tail是加到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 判断list是否处于head链表的尾部。
/** * 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_careful - tests whether a list is empty and not being modified * @head: the list to test * * Description: * tests whether a list is empty _and_ checks that no other CPU might be * in the process of modifying either member (next or prev) * * NOTE: using list_empty_careful() without synchronization * can only be safe if the only activity that can happen * to the list entry is list_del_init(). Eg. it cannot be used * if another CPU could re-list_add() it. */static inline int list_empty_careful(const struct list_head *head){ struct list_head *next = head->next; return (next == head) && (next == head->prev);}
list_empty 判断head链表是否为空，为空的意思就是只有一个链表头head。list_empty_careful 同样是判断head链表是否为空，只是检查更为严格。
/** * list_is_singular - tests whether a list has just one entry. * @head: the list to test. */static inline int list_is_singular(const struct list_head *head){ return !list_empty(head) && (head->next == head->prev);}
list_is_singular 判断head中是否只有一个节点，即除链表头head外只有一个节点。
static inline void __list_cut_position(struct list_head *list, struct list_head *head, struct list_head *entry){ struct list_head *new_first = entry->next; list->next = head->next; list->next->prev = list; list->prev = entry; entry->next = list; head->next = new_first; new_first->prev = head;}/** * list_cut_position - cut a list into two * @list: a new list to add all removed entries * @head: a list with entries * @entry: an entry within head, could be the head itself * and if so we won't cut the list * * This helper moves the initial part of @head, up to and * including @entry, from @head to @list. You should * pass on @entry an element you know is on @head. @list * should be an empty list or a list you do not care about * losing its data. * */static inline void list_cut_position(struct list_head *list, struct list_head *head, struct list_head *entry){ if (list_empty(head)) return; if (list_is_singular(head) && (head->next != entry && head != entry)) return; if (entry == head) INIT_LIST_HEAD(list); else __list_cut_position(list, head, entry);}
list_cut_position 用于把head链表分为两个部分。从head->next一直到entry被从head链表中删除，加入新的链表list。新链表list应该是空的，或者原来的节点都可以被忽略掉。可以看到，list_cut_position中排除了一些意外情况，保证调用__list_cut_position时至少有一个元素会被加入新链表。
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;}/** * list_splice - join two lists, this is designed for stacks * @list: the new list to add. * @head: the place to add it in the first list. */static inline void list_splice(const struct list_head *list, struct list_head *head){ if (!list_empty(list)) __list_splice(list, head, head->next);}/** * list_splice_tail - join two lists, each list being a queue * @list: the new list to add. * @head: the place to add it in the first list. */static inline void list_splice_tail(struct list_head *list, struct list_head *head){ if (!list_empty(list)) __list_splice(list, head->prev, head);}
list_splice的功能和list_cut_position正相反，它合并两个链表。list_splice把list链表中的节点加入head链表中。在实际操作之前，要先判断list链表是否为空。它保证调用__list_splice时list链表中至少有一个节点可以被合并到head链表中。list_splice_tail只是在合并链表时插入的位置不同。list_splice是把原来list链表中的节点全加到head链表的头部，而list_splice_tail则是把原来list链表中的节点全加到head链表的尾部。
/** * list_splice_init - join two lists and reinitialise 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_tail_init - join two lists and reinitialise the emptied list * @list: the new list to add. * @head: the place to add it in the first list. * * Each of the lists is a queue. * The list at @list is reinitialised */static inline void list_splice_tail_init(struct list_head *list, struct list_head *head){ if (!list_empty(list)) { __list_splice(list, head->prev, head); INIT_LIST_HEAD(list); }}
list_splice_init 除了完成list_splice的功能，还把变空了的list链表头重新初始化。list_splice_tail_init 除了完成list_splice_tail的功能，还吧变空了得list链表头重新初始化。list操作的API大致如以上所列，包括链表节点添加与删除、节点从一个链表转移到另一个链表、链表中一个节点被替换为另一个节点、链表的合并与拆分、查看链表当前是否为空或者只有一个节点。接下来，是操作链表遍历时的一些宏，我们也简单介绍一下。
/** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. */#define list_entry(ptr, type, member) \ container_of(ptr, type, member)
list_entry主要用于从list节点查找其内嵌在的结构。比如定义一个结构struct A{ struct list_head list; }; 如果知道结构中链表的地址ptrList，就可以从ptrList进而获取整个结构的地址(即整个结构的指针) struct A *ptrA = list_entry(ptrList, struct A, list);这种地址翻译的技巧是linux的拿手好戏，container_of随处可见，只是链表节点多被封装在更复杂的结构中，使用专门的list_entry定义也是为了使用方便
/** * list_first_entry - get the first element from a list * @ptr: the list head to take the element from. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. * * Note, that list is expected to be not empty. */#define list_first_entry(ptr, type, member) \ list_entry((ptr)->next, type, member)
list_first_entry是将ptr看完一个链表的链表头，取出其中第一个节点对应的结构地址。使用list_first_entry是应保证链表中至少有一个节点。
/** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */#define list_for_each(pos, head) \ for (pos = (head)->next; prefetch(pos->next), pos != (head); \ pos = pos->next)
list_for_each循环遍历链表中的每个节点，从链表头部的第一个节点，一直到链表尾部。中间的prefetch是为了利用平台特性加速链表遍历，在某些平台下定义为空，可以忽略。
/** * __list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. * * This variant differs from list_for_each() in that it's the * simplest possible list iteration code, no prefetching is done. * Use this for code that knows the list to be very short (empty * or 1 entry) most of the time. */#define __list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next)
__list_for_each与list_for_each没什么不同，只是少了prefetch的内容，实现上更为简单易懂。
/** * list_for_each_prev - iterate over a list backwards * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */#define list_for_each_prev(pos, head) \ for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \ pos = pos->prev)
list_for_each_prev与list_for_each的遍历顺序相反，从链表尾逆向遍历到链表头。
/** * list_for_each_safe - iterate over a list safe against removal of list entry * @pos: the &struct list_head to use as a loop cursor. * @n: another &struct list_head to use as temporary storage * @head: the head for your list. */#define list_for_each_safe(pos, n, head) \ for (pos = (head)->next, n = pos->next; pos != (head); \ pos = n, n = pos->next)
list_for_each_safe 也是链表顺序遍历，只是更加安全。即使在遍历过程中，当前节点从链表中删除，也不会影响链表的遍历。参数上需要加一个暂存的链表节点指针n。
/** * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry * @pos: the &struct list_head to use as a loop cursor. * @n: another &struct list_head to use as temporary storage * @head: the head for your list. */#define list_for_each_prev_safe(pos, n, head) \ for (pos = (head)->prev, n = pos->prev; \ prefetch(pos->prev), pos != (head); \ pos = n, n = pos->prev)
list_for_each_prev_safe 与list_for_each_prev同样是链表逆序遍历，只是加了链表节点删除保护。
/** * 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_struct within the struct. */#define list_for_each_entry(pos, head, member) \ for (pos = list_entry((head)->next, typeof(*pos), member); \ prefetch(pos->member.next), &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member))
list_for_each_entry不是遍历链表节点，而是遍历链表节点所嵌套进的结构。这个实现上较为复杂，但可以等价于list_for_each加上list_entry的组合。
/** * list_for_each_entry_reverse - iterate backwards 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_struct within the struct. */#define list_for_each_entry_reverse(pos, head, member) \ for (pos = list_entry((head)->prev, typeof(*pos), member); \ prefetch(pos->member.prev), &pos->member != (head); \ pos = list_entry(pos->member.prev, typeof(*pos), member))
list_for_each_entry_reverse 是逆序遍历链表节点所嵌套进的结构，等价于list_for_each_prev加上list_etnry的组合。
/** * list_for_each_entry_continue - continue iteration 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_struct within the struct. * * Continue to iterate over list of given type, continuing after * the current position. */#define list_for_each_entry_continue(pos, head, member) \ for (pos = list_entry(pos->member.next, typeof(*pos), member); \ prefetch(pos->member.next), &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member))
list_for_each_entry_continue也是遍历链表上的节点嵌套的结构。只是并非从链表头开始，而是从结构指针的下一个结构开始，一直到链表尾部。
/** * list_for_each_entry_continue_reverse - iterate backwards from the given point * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_struct within the struct. * * Start to iterate over list of given type backwards, continuing after * the current position. */#define list_for_each_entry_continue_reverse(pos, head, member) \ for (pos = list_entry(pos->member.prev, typeof(*pos), member); \ prefetch(pos->member.prev), &pos->member != (head); \ pos = list_entry(pos->member.prev, typeof(*pos), member))
list_for_each_entry_continue_reverse 是逆序遍历链表上的节点嵌套的结构。只是并非从链表尾开始，而是从结构指针的前一个结构开始，一直到链表头部。
/** * list_for_each_entry_from - iterate over list of given type from the current point * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_struct within the struct. * * Iterate over list of given type, continuing from current position. */#define list_for_each_entry_from(pos, head, member) \ for (; prefetch(pos->member.next), &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member))
list_for_each_entry_from 是从当前结构指针pos开始，顺序遍历链表上的结构指针。
/** * 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_struct within the struct. */#define list_for_each_entry_safe(pos, n, head, member) \ for (pos = list_entry((head)->next, typeof(*pos), member), \ n = list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(n->member.next, typeof(*n), member))
list_for_each_entry_safe 也是顺序遍历链表上节点嵌套的结构。只是加了删除节点的保护。
/** * list_for_each_entry_safe_continue - continue list iteration safe against removal * @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_struct within the struct. * * Iterate over list of given type, continuing after current point, * safe against removal of list entry. */#define list_for_each_entry_safe_continue(pos, n, head, member) \ for (pos = list_entry(pos->member.next, typeof(*pos), member), \ n = list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(n->member.next, typeof(*n), member))
list_for_each_entry_safe_continue 是从pos的下一个结构指针开始，顺序遍历链表上的结构指针，同时加了节点删除保护。
/** * list_for_each_entry_safe_from - iterate over list from current point safe against removal * @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_struct within the struct. * * Iterate over list of given type from current point, safe against * removal of list entry. */#define list_for_each_entry_safe_from(pos, n, head, member) \ for (n = list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(n->member.next, typeof(*n), member))
list_for_each_entry_safe_from 是从pos开始，顺序遍历链表上的结构指针，同时加了节点删除保护。
/** * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal * @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_struct within the struct. * * Iterate backwards over list of given type, safe against removal * of list entry. */#define list_for_each_entry_safe_reverse(pos, n, head, member) \ for (pos = list_entry((head)->prev, typeof(*pos), member), \ n = list_entry(pos->member.prev, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(n->member.prev, typeof(*n), member))
list_for_each_entry_safe_reverse 是从pos的前一个结构指针开始，逆序遍历链表上的结构指针，同时加了节点删除保护。至此为止，我们介绍了linux中双向循环链表的结构、所有的操作函数和遍历宏定义。相信以后在linux代码中遇到链表的使用，不会再陌生。