了解Linux通用的雙向循環(huán)鏈表

?在linux內(nèi)核中，有一種通用的雙向循環(huán)鏈表，構(gòu)成了各種隊列的基礎(chǔ)。鏈表的結(jié)構(gòu)定義和相關(guān)函數(shù)均在include/linux/list.h中，下面就來全面的介紹這一鏈表的各種API。

struct list_head { struct list_head *next, *prev;};

這是鏈表的元素結(jié)構(gòu)。因為是循環(huán)鏈表，表頭和表中節(jié)點都是這一結(jié)構(gòu)。有prev和next兩個指針，分別指向鏈表中前一節(jié)點和后一節(jié)點。

/* * 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;}

在初始化的時候，鏈表頭的prev和next都是指向自身的。

/* * 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);}

雙向循環(huán)鏈表的實現(xiàn)，很少有例外情況，基本都可以用公共的方式來處理。這里無論是加第一個節(jié)點，還是其它的節(jié)點，使用的方法都一樣。
另外，鏈表API實現(xiàn)時大致都是分為兩層：一層外部的，如list_add、list_add_tail，用來消除一些例外情況，調(diào)用內(nèi)部實現(xiàn)；一層是內(nèi)部的，函數(shù)名前會加雙下劃線，如__list_add，往往是幾個操作公共的部分，或者排除例外后的實現(xiàn)。

/* * 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是鏈表中節(jié)點的刪除。之所以在調(diào)用__list_del后又把被刪除元素的next、prev指向特殊的LIST_POSITION1和LIST_POSITION2，是為了調(diào)試未定義的指針。
list_del_init則是刪除節(jié)點后，隨即把節(jié)點中指針再次初始化，這種刪除方式更為實用。

/** * 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是將鏈表中一個節(jié)點old，替換為另一個節(jié)點new。從實現(xiàn)來看，即使old所在地鏈表只有old一個節(jié)點，new也可以成功替換，這就是雙向循環(huán)鏈表可怕的通用之處。
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節(jié)點從原鏈表中去除，并加入新的鏈表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 判斷l(xiāng)ist是否處于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鏈表是否為空，只是檢查更為嚴(yán)格。

/** * 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中是否只有一個節(jié)點，即除鏈表頭head外只有一個節(jié)點。

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應(yīng)該是空的，或者原來的節(jié)點都可以被忽略掉?？梢钥吹?，list_cut_position中排除了一些意外情況，保證調(diào)用__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鏈表中的節(jié)點加入head鏈表中。在實際操作之前，要先判斷l(xiāng)ist鏈表是否為空。它保證調(diào)用__list_splice時list鏈表中至少有一個節(jié)點可以被合并到head鏈表中。
list_splice_tail只是在合并鏈表時插入的位置不同。list_splice是把原來list鏈表中的節(jié)點全加到head鏈表的頭部，而list_splice_tail則是把原來list鏈表中的節(jié)點全加到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大致如以上所列，包括鏈表節(jié)點添加與刪除、節(jié)點從一個鏈表轉(zhuǎn)移到另一個鏈表、鏈表中一個節(jié)點被替換為另一個節(jié)點、鏈表的合并與拆分、查看鏈表當(dāng)前是否為空或者只有一個節(jié)點。
接下來，是操作鏈表遍歷時的一些宏，我們也簡單介紹一下。

/** * 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節(jié)點查找其內(nèi)嵌在的結(jié)構(gòu)。比如定義一個結(jié)構(gòu)struct A{ struct list_head list; }; 如果知道結(jié)構(gòu)中鏈表的地址ptrList，就可以從ptrList進而獲取整個結(jié)構(gòu)的地址(即整個結(jié)構(gòu)的指針) struct A *ptrA = list_entry(ptrList, struct A, list);
這種地址翻譯的技巧是linux的拿手好戲，container_of隨處可見，只是鏈表節(jié)點多被封裝在更復(fù)雜的結(jié)構(gòu)中，使用專門的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看完一個鏈表的鏈表頭，取出其中第一個節(jié)點對應(yīng)的結(jié)構(gòu)地址。使用list_first_entry是應(yīng)保證鏈表中至少有一個節(jié)點。

/** * 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循環(huán)遍歷鏈表中的每個節(jié)點，從鏈表頭部的第一個節(jié)點，一直到鏈表尾部。中間的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的內(nèi)容，實現(xiàn)上更為簡單易懂。

/** * 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 也是鏈表順序遍歷，只是更加安全。即使在遍歷過程中，當(dāng)前節(jié)點從鏈表中刪除，也不會影響鏈表的遍歷。參數(shù)上需要加一個暫存的鏈表節(jié)點指針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同樣是鏈表逆序遍歷，只是加了鏈表節(jié)點刪除保護。

/** * 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不是遍歷鏈表節(jié)點，而是遍歷鏈表節(jié)點所嵌套進的結(jié)構(gòu)。這個實現(xiàn)上較為復(fù)雜，但可以等價于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 是逆序遍歷鏈表節(jié)點所嵌套進的結(jié)構(gòu)，等價于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也是遍歷鏈表上的節(jié)點嵌套的結(jié)構(gòu)。只是并非從鏈表頭開始，而是從結(jié)構(gòu)指針的下一個結(jié)構(gòu)開始，一直到鏈表尾部。

/** * 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 是逆序遍歷鏈表上的節(jié)點嵌套的結(jié)構(gòu)。只是并非從鏈表尾開始，而是從結(jié)構(gòu)指針的前一個結(jié)構(gòu)開始，一直到鏈表頭部。

/** * 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 是從當(dāng)前結(jié)構(gòu)指針pos開始，順序遍歷鏈表上的結(jié)構(gòu)指針。

/** * 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 也是順序遍歷鏈表上節(jié)點嵌套的結(jié)構(gòu)。只是加了刪除節(jié)點的保護。

/** * 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的下一個結(jié)構(gòu)指針開始，順序遍歷鏈表上的結(jié)構(gòu)指針，同時加了節(jié)點刪除保護。

/** * 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開始，順序遍歷鏈表上的結(jié)構(gòu)指針，同時加了節(jié)點刪除保護。

/** * 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的前一個結(jié)構(gòu)指針開始，逆序遍歷鏈表上的結(jié)構(gòu)指針，同時加了節(jié)點刪除保護。
至此為止，我們介紹了linux中雙向循環(huán)鏈表的結(jié)構(gòu)、所有的操作函數(shù)和遍歷宏定義。相信以后在linux代碼中遇到鏈表的使用，不會再陌生。

?