Linux内核list/hlist解读

pdf版本下载:

Linux内核list&hlist解读.pdf

1. 前言

Linux内核实现了一批优雅而功能强大的双向循环列表操作宏,它们位于/usr/include/linux/list.h(请注意直接#include会报编译错误),这些宏可以直接扣出来,在需要时使用。

2. 通用宏

2.1. typeof

请注意typeof并不是一个宏,而是GCC的一个内建操作符。

2.1.1. 定义

typeof(variable)

2.1.2. 用途

得到变量variable的类型,这个类型可以用来定义同类型的其它变量。

2.1.3. 示例

int m = 1;

typeof(m) n = m; // 等同于int n = m;

2.2. offset_of

2.2.1. 定义

// type:结构体类型

// member:结构体成员

#define offsetof(type, member) \

((size_t) &((type *)0)->member)

2.2.2. 作用

计算出一个结构体type中,指定成员member在该结构体中的位置。

2.2.3. 原理

(type *)0是一个类型为type的指针,其指针地址为0x0。&((type *)0)->member)是得到成员member的地址,由于结构体本身的地址为0x0,所以成员member的地址亦为member在该type中的偏移位置。

2.2.4. 示例

假设有如下一个结构体:

#pragma pack(4)

struct X

{

int32_t  a;

int32_t  b;

int32_t  c;

};

#pragma pack()

那么offsetof(Struct X, b)的值等于4。

2.3. container_of

2.3.1. 定义

// ptr:结构体成员member的地址

// type:结构体类型

// member:结构体成员member

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

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

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

2.3.2. 作用

通过结构体一个成员的地址,得到该结构体的地址。

2.3.3. 示例

定义结构体变量:

struct X x;

那么container_of(&x.b, struct X, b)的值将和&x相等。

2.4. prefetch

2.4.1. 定义

// x:需要预读的变量

#define prefetch(x) __builtin_prefetch(x)

2.4.2. 作用

这里使用到的__builtin_prefetch是GCC内建函数,它的作用是告诉cpu括号中的x可能马上就要用到,以便cpu预取一下,这样可以提高效率。

3. list

3.1. list结构

3.1.1. 定义

struct list_head

{

        struct list_head *next;  // 指向下一个结点

        struct list_head *prev;  // 指向前一个结点

};

这个定义虽然简单,但却是核心。

3.1.2. 作用

用来实现通用的双向链表,只包括前后指针,并不包含数据成员。

3.1.3. 解读

struct list_head有点类似于C++基类:

class list_head

{

public:

list_head()

: next(NULL)

, prev(NULL)

{

}

public: // 实际使用时,应当改为private,采用成员函数操作方式

list_head* next;

list_head* prev;

};

3.1.4. 示例

在C++语言中,基类是子类实例的一个子对象。在设计模式中,有template模式与strategy两个可以相互转化的模式,template模式采用的是继承,而strategy模式采用的是子对象方式。

由于在C语言中,没有继承的概念,所以只能采用子对象的方式。因此需要这样使用:

struct MyData

{

// 它在结构体中出现的顺序没有要求,

// 因为可以通过下面将要介绍的container_of宏来取得它所归属结构体的地址

struct list_head list;

char* data;

};

如果是在C++中,则:

class MyData: pubic list_head

{

private:

char* _data;

};

在C++中,如果:

list_head* data = new MyData;

则可以这样:

MyData* mydata = dynamic_cast(data);

即可由基类子对象的地址,来得到子类对象的地址。而在C语言中,则需要借助container_of宏:container_of(data, MyData, list);

3.2. 遍历方向

双向循环列表头尾相连,有2个遍历方向:

1) 顺时针

2) 逆时针

3.3. list_entry

3.3.1. 定义

// ptr:结构体成员member的地址

// type:结构体类型

// member:结构体成员member

#define list_entry(ptr, type, member)  \

container_of(ptr, type, member)

3.3.2. 作用

从list_entry的定义可以看出,它等同于container_of,即通过结构体type一个成员member的地址ptr,得到该结构本的地址。

3.4. list_for_each

3.4.1. 定义

// pos:指向当前结点的指针

// head:指向双向链表的头的指针

#define list_for_each(pos, head)  \

        for (pos = (head)->next;  \

prefetch(pos->next), pos != (head);  \

                pos = pos->next)

这里的prefetch(pos->next)不是必须的,只是为提升效率。

3.4.2. 作用

以顺时针方向遍历双向循环链表,由于是双向循环链表,所以循环终止条件是“pos != (head)”。在遍历过程中,不能删除pos(必须保证pos->next有效),否则会造成SIGSEGV错误。

3.4.3. 示例

struct list_head cur;

struct list_head list;

list_for_each(cur, &list)

{

// 使用cur

}

3.5. __list_for_each

3.5.1. 定义

// pos:指向当前结点的指针

// head:指向双向链表的头的指针

#define __list_for_each(pos, head) \

        for (pos = (head)->next;  \

pos != (head);  \

pos = pos->next)

3.5.2. 作用

功能和list_for_each相同,即以顺时针方向遍历双向循环链表,只不过省去了prefetch(pos->next)。在遍历过程中,不能删除pos(必须保证pos->next有效),否则会造成SIGSEGV错误。

3.6. list_for_each_prev

3.6.1. 定义

// pos:指向当前结点的指针

// head:指向双向链表的头的指针

#define list_for_each_prev(pos, head) \

        for (pos = (head)->prev; \

prefetch(pos->prev), pos != (head); \

                pos = pos->prev)

3.6.2. 作用

以逆时针方向遍历双向循环链表。在遍历过程中,不能删除pos(必须保证pos->prev有效),否则会造成SIGSEGV错误。

3.7. list_for_each_safe

3.7.1. 定义

// pos:指向当前结点的指针

// head:指向双向链表的头的指针

// n:临时用来保存指向pos的下一个结点的指针

#define list_for_each_safe(pos, n, head) \

        for (pos = (head)->next, n = pos->next;  \

pos != (head); \

                pos = n, n = pos->next)

3.7.2. 作用

以顺时针方向遍历双向循环链表。在遍历过程中,允许删除pos,因为每次都保存了pos->next

3.7.3. 区别

list_for_each_safe(pos, n, head)

list_for_each(pos, head)

遍历中,可删除pos

遍历中,不可删除pos

3.7.4. 示例

struct list_head cur;

struct list_head tmp; // 临时用来保存cur的next

struct list_head list;

list_for_each_safe(cur, tmp, &list)

{

// 使用pos

list_del(pos); // 将pos从链表中剔除

delete pos; // 删除pos

}

3.8. list_for_each_entry

3.8.1. 定义

为方便讲解,假设有:

struct MyNode

{

struct list_head list;

};

实际中,应当将MyNode替代成需要的类型的,但不管叫什么,总是聚合了struct list_head。

// pos:指向当前结点(在这里,类型为MyNode)的指针

// head:指向双向链表list_head的头的指针

// member:list_head类型在MyNode中的成员(在这里为list)

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

3.8.2. 作用

以顺时针方向遍历双向循环链表。它和list_for_each一样是做链表遍历,但pos的类型不一样。在list_for_each中,pos类型是“struct list_head*”,而在list_for_each_entry是typeof(*pos)类型。

3.8.3. 区别

list_for_each_entry(pos, head, member)

list_for_each(pos, head)

遍历链表,pos和head是typeof(*pos)类型

遍历链表,pos和head是struct list_head类型

3.8.4. 完整示例

// 这个示例,是可以编译成功,并可运行查看效果

// 假设文件名为x.cpp,则编译方法为:g++ -g -o x x.cpp

#include 

#include 

struct list_head {

        struct list_head *next, *prev;

};

static inline void INIT_LIST_HEAD(struct list_head *list)

{

        list->next = list; 

        list->prev = list; 

}

static inline void __list_add(struct list_head *inserted,

                              struct list_head *prev,

                              struct list_head *next)

{

        next->prev = inserted;

        inserted->next = next; 

        inserted->prev = prev; 

        prev->next = inserted;

}

static inline void list_add_tail(struct list_head *inserted, struct list_head *head)

{

        __list_add(inserted, head->prev, head);

}

#define prefetch(x) __builtin_prefetch(x)

#define offsetof(type, member) \

        ((size_t) &((type *)0)->member)

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

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

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

#define list_entry(ptr, type, member) \

        container_of(ptr, type, member)

#define list_for_each(pos, head) \

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

                pos = pos->next)

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

// 以上除#include外的代码,是从/usr/include/linux/list.h直接抄过来的,

// 但请注意直接#include ,将无法编译通过

// 定义一个结构体

struct MyData

{

public:

        struct list_head list; // 功能上相当于从list_head继承

        char* data;

};

int main()

{

        MyData* head = new MyData; // 必须有个空闲头结点

        MyData* data1 = new MyData; // 第一个结点

        data1->data = reinterpret_cast(0x01);

        MyData* data2 = new MyData; // 第二个结点

        data2->data = reinterpret_cast(0x02);

        INIT_LIST_HEAD(&head->list);

        list_add_tail(&data1->list, &head->list);

        list_add_tail(&data2->list, &head->list);

        // 请注意cur1和cur2的数据类型

        MyData* cur1 = NULL;

        list_head* cur2 = NULL; 

    // 请注意下面两个循环的区别,它们是互通的

        list_for_each_entry(cur1, &head->list, list)

        {

                printf("%p\n", cur1->data);

        }

list_for_each(cur2, &head->list)

        {       

                MyData* dd = container_of(cur2, MyData, list);  

                printf("%p\n", dd->data);

        }

        return 0;

}

上段代码运行后,将输出以下四行信息:

0x1

0x2

0x1

0x2

3.9. list_for_each_entry_safe

3.9.1. 定义

// pos:指向当前结点(在这里,类型为MyNode)的指针

// head:指向双向链表list_head的头的指针

// member:list_head类型在MyNode中的成员(在这里为list)

// n:用来临时存储pos的下一个结点(类型和pos相同)

#define list_for_each_entry_safe(pos, n, head, member)                  \

        for (pos = list_entry((head)->next, typeof(*pos), member),       \

                n = list_entry(pos->member.next, typeof(*pos), member);  \

&pos->member != (head);                                    \

pos = n, n = list_entry(n->member.next, typeof(*n), member))

3.9.2. 作用

list_for_each_entry的可删除结点版本。

3.10. list_for_each_entry_reverse

3.10.1. 定义

#define list_for_each_entry_reverse(pos, head, member)                  \

        for (pos = list_entry((head)->prev, typeof(*pos), member);      \

             prefetch(pos->member.prev), &pos->member != (head);        \

             pos = list_entry(pos->member.prev, typeof(*pos), member))

3.10.2. 作用

作用和list_for_each_entry相同,只不过它是逆时针方向遍历。

3.11. list_for_each_entry_continue

3.11.1. 定义

#define list_for_each_entry_continue(pos, head, member)                 \

        for (pos = list_entry(pos->member.next, typeof(*pos), member);  \

             prefetch(pos->member.next), &pos->member != (head);        \

             pos = list_entry(pos->member.next, typeof(*pos), member))

3.11.2. 作用

以顺时针方向,从pos点开始遍历链表。

3.11.3. 区别

list_for_each_entry_continue(pos, head, member)

list_for_each_entry(pos, head, member)

从pos点开始遍历链表

从头开始遍历链表

传入的pos不能为NULL,必须是已经指向链表某个结点的有效指针

对传入的pos无要求,可以为NULL

3.12. list_for_each_safe_rcu

这个牵涉到RCU(Read-Copy-Update),在这里不详细讲解了,如有兴趣,请参考《玩转多线程编程.ppt》一文。

4. hlist(hash list)

4.1. hlist(hash list)结构

4.1.1. 简述

hlist也是 一种双向链表,但不同于list_head,它的头部只有一个指针,常被用作哈希表的bucket数组,这样就可减少哈希bucket一半的内存消耗。

4.1.2. 定义

struct hlist_head {

        struct hlist_node *first; 

};

struct hlist_node {

        struct hlist_node *next, **pprev;

};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏河湾欢儿的专栏

第五节正则

9120
来自专栏C/C++基础

字符数组的初始化与赋值

C语言中表示字符串有两种方式,数组和指针,字符数组是我们经常使用的方式。变量的定义包括指明变量所属类型、变量名称、分配空间以及初始化。可以看出,变量的初始化是变...

29220
来自专栏desperate633

LintCode 字符大小写排序题目分析代码

8810
来自专栏从流域到海域

Python dict(字典)

Python dict即字典,是一种非常有用的数据结构,相当于其他语言的Map,这种数据结构采用键值对(key-value)形式存储,具有非常快的查询速度...

38890
来自专栏极乐技术社区

使用ES6新特性开发微信小程序(2)

Template Literals(模板对象) ES6中的模板字符串(Template String)是一种能在字符串文本中内嵌表达式的字符串字面量(Strin...

33060
来自专栏PHP在线

PHP部分字符串函数汇总

我们大家知道无论哪种语言,字符串操作都是一个重要的基础,往往是简单而重要。PHP给我们提供了大量的字符串操作函数,功能强大,使用也比较简单,这里为大家总结九类字...

36060
来自专栏codingforever

经典算法巡礼(五) -- 排序之归并排序

归并排序是创建在归并操作上的一种有效排序算法。所谓归并操作,指的是将两个已经排序的序列合并成一个序列的操作。归并排序是分治思想的典型示范。

5020
来自专栏java一日一条

继承、接口与多态的相关问题

继承:通过继承实现代码复用。Java中所有的类都是通过直接或间接地继程java.lang.Object类得到的。继承而得到的类称为子类,被继承的类称为父类。子类...

10120
来自专栏GreenLeaves

JavaScript引用类型之Object类型

在JavaScript中大多数的引用类型都是Object的实例,Object类型也是使用最多的类型! 创建Object类型实例的方式有两种,下面分别来分析一下:...

21950
来自专栏Rovo89

JavaScript闭包与箭头函数

10720

扫码关注云+社区

领取腾讯云代金券