list链表分析(二)

合并链表

//将prev,next的链表与list链表合并，prev代表新的头部
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链表与head链表合并，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);
}
//为队列设计的链表合并
static inline void list_splice_tail(struct list_head *list,struct list_head *head)
{
if(!list_empty(list))
__list_splice(list,head->prev,head);
}

类似函数有:

static inline void list_splice_init(struct list_head *list,struct list_head *head)
static inline void list_splice_tail_init(struct list_head *list,struct list_head *head);

链表遍历

最为复杂的部分为链表遍历，通过链表在被调用结构中的项，来获取整个结构的指针(精妙!!)

//ptr:struct list_head类型指针，type:被调用结构体类型，
//member:被调用结构体类型中的struct list_head成员名
#define list_entry(ptr,type,member)  \
    container_of(ptr,type,member)
#define container_of(ptr,type,member)  ({    \
    const typeof( ((type*)0)->member)*__mptr = (ptr);        \
    (type*)( (char*)__mptr – offsetof(type,member) );    })
#define offsetof(TYPE,MEMBER)  ((size_t)&((TYPE*)0)->MEMBER)

将指针指向member对象：const typeof( ((type*)0)->member) *__mptr = ptr;这是通过计算偏移量来实现，具体如下：

而下面一句就绝了:

(type*)( (char *)__mptr – offset(type,member)) //将指针直接偏移到ptr所指向的具体结构体头部，也就是获得到所指定的结构体指针:

这样通过它来遍历所有的结构体就简单多了：

获取目标结构体的项

#define list_entry(ptr,type,member)        \
    container_of(ptr,type,member)

获取链表指向的下一项

#define list_first_entry(ptr,type,member)     \
    list_entry((ptr)->next,type,member)

遍历整个链表

#define list_for_each(pos,head)    \
    for(pos = (head)->next;prefetch(pos->next),pos != (head); \
        pos = pos->next)

prefetch(pos->next):将pos->next 地址处所指向的内容预读到CPU L1级缓存

#define __list_for_each(pos,head)    \
    for(pos = (head)->next;pos!=(head);pos = pos->next)

最为常用的是下面的遍历方式：

/**
*pos:list所嵌入的目标结构体变量
*head: 需要进行遍历的链表
*member:目标结构体中链表的成员名称
*返回:具体指向每一项的pos
**/
#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))