workflow源码分析：list

第一次阅读源码，选择的是搜狗的workflow，这次阅读的是list

内核链表的结构

1
2
3
struct list_head {
	struct list_head *next, *prev;
};

这里发现，链表中没有数据，只有前驱和后继指针

如果我们要使用到内核的链表结构，我们需要定义一个struct list_head{}类型的结构体成员对象就可以了

eg：

1
2
3
4
struct Task{
    struct list_head entry_list;
    int val;
}

链表初始化

这里我只看第二种，即INIT_LIST_HEAD

1
2
3
4
5
static inline void INIT_LIST_HEAD(struct list_head *list)
{
	list->next = list;
	list->prev = list;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include "list.h"

struct Task 
{
    struct list_head entry_list;
    int val;
};

int main() 
{
    struct Task task;
    INIT_LIST_HEAD(&task.entry_list);
    return 0;
}

链表增加节点：list_add

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
static inline void __list_add(struct list_head *node,
							  struct list_head *prev,
							  struct list_head *next)
{
	next->prev = node;
	node->next = next;
	node->prev = prev;
	prev->next = node;
}

/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void list_add(struct list_head *node, struct list_head *head)
{
	__list_add(node, head, head->next);
}

/**
 * list_add_tail - add a new entry
 * @new: new entry to be added
 * @head: list head to add it before
 *
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */
static inline void list_add_tail(struct list_head *node,
								 struct list_head *head)
{
	__list_add(node, head->prev, head);
}

list_add是头插法 list_add_tail是尾插法

__list_add的作用就是将第一个参数node，插到第二个参数和第三个参数之间

测试用例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include "list.h"
#include <stdlib.h>
#include <stdio.h>

struct Task 
{
    struct list_head entry_list;
    int val;
};

void list_add_test()
{
    struct Task task;
    INIT_LIST_HEAD(&task.entry_list);
    struct list_head *pos;
    for(int i = 0; i < 4; i++)
    {
        struct Task *t = (struct Task *)malloc(sizeof(struct Task));
        t->val = i;
        list_add(&t->entry_list, &task.entry_list);
    }
    // 3 - 2 - 1 - 0
    list_for_each(pos, &task.entry_list) {
        printf("val = %d\n", ((struct Task*)pos)->val);
    }
}

void list_tail_test()
{
    struct Task task;
    INIT_LIST_HEAD(&task.entry_list);
    struct list_head *pos;
    for(int i = 0; i < 4; i++)
    {
        struct Task *t = (struct Task *)malloc(sizeof(struct Task));
        t->val = i;
        list_add_tail(&t->entry_list, &task.entry_list);
    }
    // 0 - 1 - 2 - 3
    list_for_each(pos, &task.entry_list) 
    {
        printf("val = %d\n", ((struct Task*)pos)->val);
    }
}


int main() 
{
    printf("list_add_test : \n");
    list_add_test();

    printf("list_tail_test : \n");
    list_tail_test();
    return 0;
}

其中的list_for_each函数很简单，这里先贴一下，就是遍历

1
2
#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)
1
2
3
4
5
6
7
8
9
10
11
hoshea@hoshea-pc://home/hoshea/Desktop/workflow/workflow-0.9.0/test/mytest/list_test$ ./a.out 
list_add_test : 
val = 3
val = 2
val = 1
val = 0
list_tail_test : 
val = 0
val = 1
val = 2
val = 3

删除节点：list_del

1
2
3
4
5
6
7
8
9
10
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);
}

测试代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include "list.h"
#include <stdlib.h>
#include <stdio.h>

// list_del demo

struct Task 
{
    struct list_head entry_list;
    int val;
};

int main() 
{
    struct Task task;
    INIT_LIST_HEAD(&task.entry_list);
    struct list_head *pos;
    for(int i = 0; i < 4; i++)
    {
        struct Task *t = (struct Task *)malloc(sizeof(struct Task));
        t->val = i;
        list_add(&t->entry_list, &task.entry_list);
    }
    // 3 - 2 - 1 - 0
    list_for_each(pos, &task.entry_list) 
    {
        printf("val = %d\n", ((struct Task*)pos)->val);
    }

    struct Task *task_pos;
    list_for_each_entry(task_pos, &task.entry_list, entry_list) 
    {
        if (task_pos->val == 2) 
        {
            list_del(&task_pos->entry_list);
            break;
        }
    }

    printf("After del : \n");
    // 3 - 1 - 0
    list_for_each(pos, &task.entry_list) 
    {
        printf("val = %d\n", ((struct Task*)pos)->val);
    }

    return 0;
}

删除其实没啥看的，主要是看list_for_each_entry函数

1
2
3
4
5
6
7
\#define list_for_each_entry(pos, head, member) \

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

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

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

获取节点结构体的地址

1
2
\#define list_entry(ptr, type, member) \
	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

上一节31行展开就是：

1
2
3
4
5
6
for (task_pos = list_entry((&task.entry_list)->next, typeof (*task_pos), entry_list);
     &task_pos->entry_list != (&task.entry_list); 
     task_pos = list_entry(task_pos->entry_list.next, typeof (*task_pos), entry_list))
{
    xxxx
}

核心还是用到了list_entry

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct Task *task_pos = ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

这里的参数 ptr, type, member分别是

ptr - (&task.entry_list)->next

这里的 ptr是找容器的那个变量的指针，这可以理解，第一次调用就是list中第一个entry_list *这个指针

(char*)ptr是为了计算字节偏移

type - typeof (*task_pos)

ANSI C标准允许值为0的常量被强制转换成任何一种类型的指针，并且转换的结果是个NULL，因此((type *)0)的结果就是一个类型为type *的NULL指针.

如果利用这个NULL指针来访问type的成员当然是非法的，但typeof( ((type *)0)->member )是想取该成员的类型，编译器不会生成访问type成员的代码

&( ((type *)0)->member )在最前面有个取地址符&，它的意图是想取member的地址，所以编译器同样会优化为直接取地址。那我们可取到以“0”为基地址的一个type型变量member域的地址。那么这个地址也就等于member域到结构体基地址的偏移字节数。

(char *)(ptr)使得指针的加减操作步长为一字节，(unsigned long)(&((type *)0)->member)等于ptr指向的member到该member所在结构体基地址的偏移字节数。二者一减便得出该结构体的地址。转换为 (type *)型的指针

member - entry_list

==> 

struct Task *task_pos = ((struct Task *)((char *)(给的entry_list)-(unsigned long)(&((struct Task *)0)->entry_list)))