GroupBlog

博客好长时间没有更新了，上一篇《Linux 内核中的种种(初步了解）》只是介绍了内核中链表的创建，插入，删除，和替换等操作，接下来，我将会把linux内核中的链表的其他功能是如何实现的展现出来。

static inline int list_is last(const struct list_head *node, const struct list_head *head)
{
      return node->next = head;
}

//判断node 这个元素是不是head这个链表的尾，因为是双向链表，这样判断比较容易。

static inline int list_empty(const struct list_head *head)
{
     return (head->next == head);
}

//判断head 这个链表是否为空，若head->next 指向head,则链表为空。

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();这个函数了，干嘛还要再写一个函数list_empty_careful();一直很郁闷，最后上网查了一下，网上给的说法是：用来判断链表为空的，并且不是被正在修改这样的状态之中。不过这个操作，得是在有同步技术支持的时候才起作用，或是只有单进程能执行相关代码的时候才能够起作用。感觉这两句话有点绕口，什么叫“ 不是被正在修改这样的状态之中”，不太懂。。。就我个人而言，我觉得这个函数就是在判断链表是否空上更加细致了而已，只有当（head->next == head） && (head->next == head->prev)时才返回true,只要有一个条件不满足，就不能说明这个链表为空。

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

//用来判断这个链表是不是只有单个元素，判断规则就是head不能为空，并且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;
}

//把entry 放到list 列表的左面，当作list 链表的prev 元素， list 的next 元素，指向原先的head 元素，entry后面的元素都链到head链表后面。

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

//这段代码呢，就是将head 这个链表里，上至表头（不含），下至entry这个元素，移到list链表内，组成一个新的链表，则head链表就与entry 后面的这个元素形成一个新的链表。这里就要求 entry这个元素在链表内，若head 这个链表里就只有entry一个元素，则初始化list。

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 *next = list->prev;

       first->prev = prev;
       prev->next = first;

       last->next = next;
       next->prev = last;
}

//这个函数我自己也不太清楚是怎么回事，在草纸上画了一下过程，发现这个函数就是把双向循环链表变成了不能再环起来的链表了，网上资料是这样解释这段函数的：这个函数的功能是让原链表的最后一个元素的next指向next参数，让原链表的第一个元素的prev指向prev参数，list这个表头就把架空了，通过它能访问链表，但链表不能访问它，已经链不起来了。我觉得这也就是list为什么要定义为 const struct list_head 的原因了，感觉这个理解起来就容易了好多。。。

static inline void list_splice(const struct list_head *list, struct list_head *head)
{
        if(!list_empty(list))
              __list_splice(list, head, head->next);
}

//这个函数就是把head链表直接链接到原list链表的头部。

static inline void list_splice_tail(const struct list_head *list, struct list_head *head)
{
         if(!list_empty(list))
              __list_splice(list, head->prev, head);
}

//这个函数就是把head链表加到原list链表的尾部。

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结点初始化，使其变成可用的结点。

以上就是在Linux的内核中链表的各种实现，最后的最后再加一个函数container_of();

#define offsetof(TYPE, MEMBER) ((size_t) & ((TYPE *) 0)->MEMBER)

container_of(ptr, type, member)

{

const typeof(((type*)0)->member) *__mptr = (ptr);

(type *)((char*) __mptr - offsetof(type, member));

} //它的作用就是根据一个结构体变量中的一个域成员变量的指针来获取整个结构体变量的指针，通过偏移量来获取整个链表的头，也就是所谓的从局部到整体。