原创 内核中双向循环链表的学习

List_head 结构定义在include/linux/types.h中

struct list_head {

      struct list_head *next, *prev;

};

其中仅包含两个指向相同结构的指针。

对双向链表的操作都在include/linux/list.h中定义

一．链表的初始化。

（1）LIST_HEAD_INIT

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

  (2)LIST_HEAD

 #define LIST_HEAD(name)  struct list_head name = LIST_HEAD_INIT(name)

这两个宏用于声明一个新的list_head对象，并将该对象的两个指针都指向自己。

二．链表元素的add操作。

 （1）__list_add()

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;

}

此操作用于将一个新的list_head对象加入到两个已知的list_head对象之间。并将这三个对象连接起来。

 （2）list_add()

/**

 * 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_head对象添加到一个链表中指定对象的后面。即将该对象插入到指定对象及该指定对象的后继对象之间。

 （3）list_add_tail()

/**

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

}

此操作用于将一个list_head对象添加到一个链表中指定对象的前面。即将该对象插入到指定对象及该指定对象的前仆对象之间。（前仆后继，哈哈）

三．链表元素的del操作。

 （1）__list_del()

/*

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

}

此操作用于删除一个链表中的一个元素，不需要知道该元素，但必须知道该元素的前仆和后继。操作后，此元素的前仆后继成为彼此的前仆后继，将指定元素挤出队伍。但被挤出链表队伍的那个元素仍然对他的前仆后继保有记忆，可以访问。

 （2）list_del_init()

/**

 * 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()的基础上，让被删除的元素恢复初始状态，指向自己。彻底断绝跟链表的瓜葛。

（3）list_del()

/**

 * 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.

static inline void list_del(struct list_head *entry)

{

      __list_del(entry->prev, entry->next);

      entry->next = LIST_POISON1;

      entry->prev = LIST_POISON2;

}

此操作删除一个链表中的指定元素。调用该函数后，指定元素从链表中消失，它的前仆后继成为彼此新的前仆后继。

至于LIST_POISON1和LIST_POISON2是两个什么东西？我们大致猜测一下：当把一个链表中的元素从链表中删除以后，该元素是不在链表队伍中了，但是该元素并没有消亡，而且如果不对其next和prev变量进行处理的话它仍然是指向它以前的前仆后继，也就是说将会导致从一个非链表中的对象可以访问链表对象，进而可以访问整个链表。这会引起安全问题。所以，一旦一个指定元素被和链表的关系结束，它就要与链表完全脱离关系，不能继续搞暧昧。

LIST_POISON1和LIST_POISON定义在include/linux/poison.h中：

/*

 * These are non-NULL pointers that will result in page faults

 * under normal circumstances, used to verify that nobody uses

 * non-initialized list entries.

 */

#define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)

#define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)

将该被抛弃的元素的内部指针指向两个内核空间不会用到的内存位置，当试图访问它的next和priew指针指向的空间时，会引发缺页错误。

四．链表元素的替换（replace）和移动（move）操作。

（1）list_replace()

/**

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

}

此操作可以称为“挖墙脚”，一个新的指定list_head对象抢走了旧的指定list_head对象的前仆后继。称为“挖墙脚”也是完全合适的，被挖墙脚的人总是心有不甘的，他仍然心念旧好，但旧好心里早已无他，悲剧啊。表现就是该操作并没有对旧的list_head对象做后续处理，也就是说它仍然指向它以前的前仆后继，但原来的前仆后继已经不指向它。

思考：假设一个链表只有一个元素，该元素的next和priew都指向它自己（调用LIST_HEAD宏可有此结果）时，对其执行list_replace操作会让old和new两个对象各自的两个指针都指向对方。

 （2）list_replace_init

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元素初始化为指向自身。相当于在挖了他墙角之后再给他喝一杯忘情水，还是挺人道的，少了过去的羁绊，成为自由身。当然，代价就是一穷二白了，啥都没有。

 (3)list_move()

/**

 * 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_head对象list从他原来所在的链表删除后，把他放到另外一个链表指定元素head的后面，即成为head的后继，成为head原来后继的前仆。

 （4）list_move_tail()

/**

 * 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_head对象list从他原来所在的链表删除后，把他放到另外一个链表指定元素head的前面，即成为head的前仆，成为head原来前仆的后继。在链表中，顺着next的方向叫head方向，顺着priew的方向叫tail方向。

 (5)list_rotate_left()

/**

 * list_rotate_left - rotate the list to the left

 * @head: the head of the list

 */

static inline void list_rotate_left(struct list_head *head)

{

      struct list_head *first;

      if (!list_empty(head)) {

           first = head->next;

           list_move_tail(first, head);

      }

}

该函数将head指向的链表元素与它后面的元素交换在链表中的位置。

（五）对链表元素或者链表状态的判断。

  （1）list_is_last()

/**

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

}

根据函数名，该函数的功能是判断一个链表元素是否是链表中最后一个元素。然而，事实上，这个函数的语义仅仅是判断一个链表元素（head指向的）是否是另外一个链表元素(list指向的)的后继，除次之外没其他功能。只有当head指向的是链表中第一个元素时，才能判断list指向的是链表中最后一个元素。

 （2）list_empty()

/**

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

}

同上，只有当确定head指向链表的第一个元素时，该函数才能判断该链表是否为空。否则，只能判断head指向的元素后面还没有元素。

 list_empty_careful()

/**

 * 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()仅以头指针的next是否指向自己来判断链表是否为空，Linux链表另行提供了一个list_empty_careful()宏，它同时判断头指针的next和prev，仅当两者都指向自己时才返回真。这主要是为了应付另一个cpu正在处理同一个链表而造成next、prev不一致的情况。但代码注释也承认，这一安全保障能力有限：除非其他cpu的链表操作只有list_del_init()，否则仍然不能保证安全，也就是说，还是需要加锁保护。

（3）

/**

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

}

该函数判断链表中除了head指向的元素外是否只有一个其他的链表元素。

（六）链表的分割。

（1）__list_cut_position()

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;

}

(2)list_cut_position()

/**

 * 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_positon()前，head,list,entry三者分布如下：（函数要求entry所指位于由head所指领头的链表内）

在拆分之后，如下图：

画的有些乱，惭愧，有时间再画一遍。结果叙述如下：

以head所指的元素为链表头的链表，从head的后继到entry所指的元素，依次链接到以list所指元素为链表头的链表中，形成一个新的双向循环链表。

原来head为头的链表中，entry原来的后继接替head所指元素原来的后继，即head为头的链表被移除一部分后，剩余的部分前移，继续保持双向循环链表的结构不变。

 七．链表的合并。

（1）__list_splice()

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;

}

 (2)list_splice

/**

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

}

 (3)list_splice_tail()

/**

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

}

 (4)list_splice_init()

/**

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

      }

}

 (5)list_splice_tail_init()

/**

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

      }

}

八．链表的遍历。

  （1）list_entry()

/**

 * 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_head的链表，且每个链表包含在另外一个结构体的对象里，这些外部结构体的对象通过list_head联系起来。如果ptr指向链表中一个已知的list_head对象，那么list_entry宏会返回包含这个对象的外部结构体对象的指针。这是个精妙的实现，linux内核中所有队列都与此有关。该宏实质是container_of(),其实现我们以后再进行详述，是灵活运用指针的典范。

   (2)list_first_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_head的链表，且每个链表包含在另外一个结构体的对象里，这些外部结构体的对象通过list_head联系起来。如果ptr指向的是list_head链表的链表头，该宏将返回链表的第一个list_head元素（即ptr所指的链表头的后继）所在的外部结构体对象的指针。

（3）list_for_each()

/**

 * 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)

它实际上是一个for循环，利用传入的pos作为循环变量，从表头head开始，逐项向后（next方向）移动pos，直至又回到head（prefetch()可以不考虑，用于预取以提高遍历速度）。

(4)__list_for_each()

/**

 * __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()功能差不多，只是去掉预取以提高遍历速度的功能。

 (5)list_for_each_entry()

/**

 * 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_head链表连接起来的的外部结构体对象，也就是说list_for_each()和list_entry()总是同时使用。对此Linux给出了一个list_for_each_entry()宏, 与list_for_each()不同，这里的pos是数据项结构指针类型，而不是(struct list_head *)。

某些应用需要反向遍历链表，Linux提供了list_for_each_prev()和list_for_each_entry_reverse()来完成这一操作，使用方法和上面介绍的list_for_each()、list_for_each_entry()完全相同。

如果遍历不是从链表头开始，而是从已知的某个节点pos开始，则可以使用list_for_each_entry_continue(pos,head,member)。有时还会出现这种需求，即经过一系列计算后，如果pos有值，则从pos开始遍历，如果没有，则从链表头开始，为此，Linux专门提供了一个list_prepare_entry(pos,head,member)宏，将它的返回值作为list_for_each_entry_continue()的pos参数，就可以满足这一要求。

本文部分叙述参考网址：http://www.ibm.com/developerworks/cn/linux/kernel/l-chain/