linux内核链表

链表

linux中的链表将数据域与指针域进行分离。

通过list_head怎么访问其他成员变量？

这就要依靠container_of宏了。指针域相对于结构体首地址的偏移量是固定的

指针域地址-相当偏移地址=结构体首地址。偏移量求解的办法offset宏

c
1
2
3
#define container_of(ptr,type,member)    \
        const typeof((type *)0->member) *_ptr=(ptr); \
        (type *)((char *)_ptr-offset(type,member))

offset是内置的函数，也可以用上面的方法实现

c
1
#define offset(type,member) (unsigned long)(&(type)(0)->member)

使用0地址作为结构体的起始地址，成员的地址就是相对与0号地址的偏移地址

链表头

静态创建链表头

c
1
2
3
4
struct Node Head{
    .data=data;
    .list=List_Head_Init(Head.list),
}

动态创建链表头

c
1
2
3
struct Node* HeadNode=malloc()
Head->data;
List_Head_Init(Head->list);

添加节点

在某一位置插入

c
1
list_add(struct list_head *new,struct list_head *head)

在尾部插入

c
1
list_add_tail(struct list_head *new,struct list_head *head);

删除节点

c
1
list_del(struct list_head *entry)

具体实现

c
1
2
3
4
5
6
7
static inline void __list_del(struct list_head *prev,struct list_head *next){
    next->prev=prev;
    prev->next=next;
}
static inline void list_del(struct list_head *entry){
    __list_del(entry->prev,entry->next);
}

是否为空

c
1
list_empty(struct list_head *head);

遍历链表

c
1
list_for_each(p,list)/*temp:临时递归的变量*/

p表示循环中的临时变量，list表示遍历的起始位置

遍历实体

可以这样遍历

c
1
2
3
4
list_for_each(p,list){
    entry=list_entry()
    //后续操作
}

进行封装

c
1
2
3
4
5
6
7
/*
 *    pos:list_entry的返回值
 *  head:头节点/遍历的起始位置
 *  member:list_head的名字
 */

list_for_each_entry(pos,head,member)
c
1
2
3
list_for_each_entry(pos,head,member){
    printf(pos->member)
}

反向遍历链表

c
1
list_for_each_reverse(pos,head,member)

线程安全的链表