现在的位置: 首页 > 综合 > 正文

list.h分析

2013年01月09日 ⁄ 综合 ⁄ 共 3547字 ⁄ 字号 小 中 大 ⁄ 评论关闭

6.链表的修改：

    其实内核差不多都是把这些函数封装起来了，其实链表的修改也是这样的，代码其实很简单，没有什么解释的，就是把旧的结点的next和prev与原链表断开，再与新的结点的next和prev连接起来。如下函数：

  1. static inline void list_replace(struct list_head
    *new,struct list_head
    *old)
  2. {
  3.    new->next=old->next;
  4.    new->next->prev=new;
  5.    new->prev=old->prev;
  6.    new->prev->next=new;
  7. }

  1. static inline void list_replace_init(struct list_head
    *new,struct list_head
    *old)
  2. {
  3.     list_replace(new,old);
  4.     INIT_LIST_HEAD(old);
  5. }

 上面的函数调用了第一个函数，最后调用了初始化函数，让不用的结点指向自己，是安全的删除。

7.链表的移动
  链表的移动就是将一个结点移动到另一个结点，内核实现这个功能使用的是先把要移动的位置上的结点分离出来，再将要移动的结点添加到head之后进去就OK了：

  1. static inline void list_move(struct list_head
    *list, struct list_head
    *head)
  2. {
  3.     __list_del_entry(list);
  4.     list_add(list, head);
  5. }


  1. static inline void list_move_tail(struct list_head
    *list,
  2.                  struct list_head *head)
  3. {
  4.     __list_del_entry(list);
  5.     list_add_tail(list, head);
  6. }

     第一个函数调用的是list_add_tail(list,head),第二个函数调用的是list_add_tail(list,head),这两个函数的区别我就不细说了，前面提到过。

8.链表的合并
  链表的合并也比较简单，先看一下具体的实现函数：

  1. static inline void __list_splice(const struct list_head
    *list,struct list_head
    *prev,struct list_head
    *next)
  2. {
  3.     struct list_head *first
    =     list->next;
  4.     struct list_head *last
    =     list->prev;
  5.     first->prev
    = prev;
  6.     prev->next
    = first;
  7.     last->next
    = next;
  8.     next->prev
    = last;
  9. }

      这个函数首先列举出来的这段代码和上面的每一个功能的第一个函数一样，都是被后面的函数调用的。先看它的参数，list是一个头结点，要把它后面的那一串链表插入到别的链表中，prev和next就是链表要插入的位置的前后结点，在函数体中，先用first和last记录这串要插入的链表的头和尾，把first和要插入位置的前面prev相连，把last和要插入位置的后面next相连，就像插入一个大结点一样把链表插入到规定位置。

后面调用这个函数的代码如下：

  1. static inline void list_splice_init(struct list_head
    *list,struct list_head
    *head)
  2. {
  3.     if(!list_empty(list)){
  4.         __list_splice(list,head,head->next);
  5.     INIT_LIST_HEAD(list);
  6.    }
  7. }

  1. static inline void list_splice_tail_init(struct list_head
    *list,struct list_head
    *head)
  2. {
  3.     if(!list_empty(list)){
  4.         __list_splice(list,head->prev,head);
  5. INIT_LIST_HEAD(list);
  6.     }
  7. }

    第一个函数是把链表插入到head之后，head->next之前，就是说把链表插到头结点后，类似于头插法，第二个函数是把链表插入到head->prev之后，head之前，就是说把链表插到链表的最后，类似于尾插法。当然，在插入链表之前，要保证待插的那个链表不是空链表。最后一步初始化的作用就是释放了不用的那个链表头。

9.将链表一分为二
    能将链表合并就能将其一分为二，这个函数是将head后至entry之间（包括entry）的所有结点都“切开”，让他们成为一个以list为头结点的新链表。我们先从宏观上看，如果head本身是一个空链表则失败；如果head是一个单结点链表而且entry所指的那个结点又不再这个链表中，也失败；当entry恰好就是头结点，那么直接初始化list，为什么？因为按照刚才所说的切割规则，从head后到entry前事实上就是空结点。如果上述条件都不符合，那就可以“切割”了。上述的条件如下函数所写：

  1. static inline void list_cut_position(struct list_head
    *list,
  2.         struct list_head *head, struct list_head
    *entry)
  3. {
  4.     if (list_empty(head))
  5.         return;
  6.     if (list_is_singular(head)
    &&
  7.         (head->next
    != entry
    &    & head != entry))
  8.         return;
  9.     if (entry
    == head)
  10.         INIT_LIST_HEAD(list);
  11.     else
  12.         __list_cut_position(list, head, entry);
  13. }

调用的切割函数如下：

  1. static inline void __list_splice(const struct list_head
    *list,
  2.                  struct list_head *prev,
  3.                  struct list_head *next)
  4. {
  5.     struct list_head *first
    =     list->next;
  6.     struct list_head *last
    =     list->prev;
  8.     first->prev
    = prev;
  9.     prev->next
    = first;
  11.     last->next
    = next;
  12.     next->prev
    = last;
  13. }

10.测试函数  

 测试函数其实理解起来挺简单的，一看代码就能明白到底是要测试什么，如下代码就测试的就是list是否是最后一个结点：

  1. static inline int list_is_last(const struct list_head
    *list,
  2.                 const struct list_head
    *    head)
  3. {
  4.     return list->next
    == head;
  5. }
下面的函数是测试head链表是否只有一个结点：这个链表既不能是空而且head前后的两个结点都得是同一个结点。

  1. static inline int list_is_singular(const struct list_head
    *head)
  2. {
  3.     return !list_empty(head)
    &&
    (    head->next
    == head->prev);
  4. }

11.判空函数

  1. static inline int list_empty(const struct list_head
    *head)
  2. {
  3.     return head->next
    == head;
  4. }


  1. static inline int list_empty_careful(const struct list_head
    *head)
  2. {
  3.     struct list_head *next
    = head->next;
  4.     return (next
    == head)
    &&
    (    next == head->prev);
  5. }

    第二个比第一个函数“仔细”在哪里？前者只是认为只要一个结点的next指针指向头指针就算为空，但是后者还要去检查头节点的prev指针是否也指向头结点。另外，这种仔细也是有条件的，只有在删除节点时用list_del_init()，才能确保检测成功。

  仔细去分析这些代码收获真的挺大的，建议大家都去好好的分析一下list.h，会对你有帮助的！
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞