2.1 数据结构-queue.h

1. 概述

本文档要介绍的正是libevent中的queue.h文件中的一些数据结构, 这个文件是从一些操作系统中"借鉴"过来的, 是很经典的一个文件. 因为这里面的结构体中的定义格式是很多操作系统(包括Linux)中的双向循环列表和双向队列中的实现方式. 在大型的系统和开源项目中, 双向的数据结构用的稍微多点.

我们在大学学过的数据结构中, 对于链表(单链表, 双链表, 单循环链表, 双循环链表)和队列(链队列)等的定义方式根深蒂固, 下文中讲到这种结构我就会进行一些对比.

对于刚接触这种结构定义方式, 或许会感到有稍许抓狂, 刚才C++中"逃避"出来的宏定义, 在这里大行其道. 不过, 如果了解了本质的内容, 对于这种的定义和操作方式会从感叹到习惯!

下面就以文件中注释的方式来讲解这些结构.

2. 单链表

下面我会先摆出我们在数据结构书中看到的数据结构, 然后和libevent中的queue.h中的结构进行对比. 在我们的理解中, 单向链表(链式和非链式)都是由一个控制结构+数据节点来组成. 数据节点带有一个数据域, 但是在一些开源项目中的定义却不带数据, 这些我打算放在后面来说.

2.1 定义方式

2.1.1 带有数据的定义方式(数据结构书上的定义)

typedef int ElemType;

/*
	定义一个单向链表的数据节点
*/
typedef struct SLNode {
	ElemType data;
	SLNode *next;
} SLNode, *PSLNode;

/*
	定义一个控制结构
*/
typedef struct SList {
	SLNode *first;
}SList, *PSList;

// 使用
SList slist;

/*
	*  更加直接的方式
	*  数据节点定义
*/
struct {
	ElemType data;
	SLNode *next;
} SLNode node;
typedef SLNode *PSLNode;

/*
	* 更加直接的方式
	*  控制结构定义
*/
struct {
	SLNode *first;
} SList slist;
typedef SList *PSList;
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

2.1.2 libevent中单链表定义

/*
	定义一个嵌入数据中的节点
*/
#define SLIST_ENTRY(type)						\
struct {								\
	struct type *sle_next;	/* next element */			\
}
// 使用
SLIST_ENTRY(type) node;
//展开后
struct {
	type *sle_next;
} node;

/*
	定义一个控制结构
*/
#define SLIST_HEAD(name, type)						\
struct name {								\
	struct type *slh_first;	/* first element */			\
}
// 使用
SLIST_HEAD(SList, type) slist;
// 展开后如下
struct SList {
	type *slh_first;
} slist;
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

经过展开后, 发现是不是除了没有数据部分, 其他部分和我们在数据结构书中学到的定义很类似, 注意, 这两个结构体中的type为同一类型. 只不过, 在数据结构书中学到的是控制结构包含了数据节点, 是一个结构体, 因为数据节点中已经存在数据了. 而在queue.h中定义的单链表结构则是将控制结构和嵌入数据中的节点进行了解耦, 没有有意组合成一个结构体.
现在我们不得不要说明下SLIST_HEAD和SLIST_ENTRY在实际操作中的使用方式, 下面定义两个测试的group和node.

// 这里的控制结构可以放到一个结构体中, 也可以不放, 这里演示说明
// 对于TYPE的使用, 是不是特别灵活, 如果我这个group可以根据TYPE来放什么类型的节点
// 特别的, 如果TYPE就是node, 整个结构体连缀起来就和2.1.1节中定义的一样了! 一般情况都是这样. 
// 如果TYPE不是struct node, 需要保证node中存在成员能够指向(找到)struct node. 这种情况算是比较少见的, 
// 在libevent中见到过bufferevent_rate_limit_group和bufferevent_rate_limit两个结构(虽然这两个类是双向链表,原理一样)就是这样(见下图),
// 我们在使用中,将TYPE=struct node就行, 强烈建议不要使用下图的模式
SLIST_HEAD(test_group, TYPE) test_group;

struct node {
	...
	SLIST_ENTRY(TYPE) next_in_group;
	// struct {
	//	TYPE *sle_next;
	// } next_in_group;
	...
};
struct node test_node;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

[单链表结构]

2.2 获取结构中成员

这里使用上面2.1.2小节中后面使用使用的group和node的定义说明

/*
	head: 代表已经定义的SList控制结构的实例
	使用方式: SLIST_FIRST(test_group)
	展开为: test_group->slh_first
/*
#define	SLIST_FIRST(head)	((head)->slh_first)

/*
	这里的单链表控制结构中并没有定义last节点, end就是NULL
	使用方式: SLIST_END(test_group)
*/
#define	SLIST_END(head)		NULL

/*
	判断是否为空, 就是head->slh_first是否为空
	使用方式: SLIST_EMPTY(test_group) 
	展开为: (test_group->slh_first == NULL)
*/
#define	SLIST_EMPTY(head)	(SLIST_FIRST(head) == SLIST_END(head))

/*
	获取下一个节点
	使用方式: SLIST_NEXT(test_node, next_in_group) 
	展开为: test_node->next_in_group.sle_next
*/
#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)

/*
	遍历列表, 其中item为struct node类型的对象
	使用方式: SLIST_FOREACH(item, test_group, next_in_group)
	展开为: for (item = test_group->sln_first; item != NULL; item = item->next_in_group.sle_next)
*/	
#define	SLIST_FOREACH(var, head, field)					\
	for((var) = SLIST_FIRST(head);					\
	    (var) != SLIST_END(head);					\
	    (var) = SLIST_NEXT(var, field))
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

2.3 操作函数

单链表的操作函数就是一些宏函数

/*
	单链表初始化, 将sle_first=NULL即可
	使用方式: SLIST_INIT(slist)
	展开为: slist->sle_first = NULL
*/
#define	SLIST_INIT(head) {						\
	SLIST_FIRST(head) = SLIST_END(head);				\
}

/*
	将elm插入到slistelm后面, 其中slistelm和elm是同一类型, 且都为struct node类型
	使用方式: SLIST_INSERT_AFTER(slistelm, elm, next_in_group)
	展开为: do {
		elm->next_in_group.sle_next = slistelm->next_in_group.sle_next;
		slistelm->next_in_group.sle_next = elm;
	} while(0);
*/
#define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
	(slistelm)->field.sle_next = (elm);				\
} while (0)

/*
	将elm插入到头部, elm为struct node类型
	使用方式: SLIST_INSERT_HEAD(test_group, elm, next_in_group);
	展开为: do {
		elm->next_in_group.sle_next = test_group->slh_first;
		test->slh_first = elm;
	} while (0)
*/
#define	SLIST_INSERT_HEAD(head, elm, field) do {			\
	(elm)->field.sle_next = (head)->slh_first;			\
	(head)->slh_first = (elm);					\
} while (0)

/*
	从头部删除一个元素, 前提是已经将这个节点已经记录, 因为下面的方式是没有保存这个节点的位置
	使用方式: SLIST_REMOVE_HEAD(test_group, next_in_group);
	展开为: do {
		test_group->slh_first = test_group->slh_first->next_in_group.sle_next;
	} while (0);
*/
#define	SLIST_REMOVE_HEAD(head, field) do {				\
	(head)->slh_first = (head)->slh_first->field.sle_next;		\
} while (0)
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

3. 双链表

双链表和双端链队列是用的最多的两个结构, 但是原理上都差不多, 双端队列就仅仅只是将控制结构增加了一个last指针.
这里就不列举在数据结构书中定义的双链表的结构了.

3.1 定义

/*
	定义控制结构, 和单链表一样
*/
#define LIST_HEAD(name, type)						\
struct name {								\
	struct type *lh_first;	/* first element */			\
}

/*
	定义嵌入数据的节点的结构, 相对于单链表增加了le_prev指针, 而且是双指针
	而且这个指针有点特点, 是保存的是前一个节点的next的地址, 当然如果是首节点, 保存的是head->le_first的地址(参考下图)
*/
#define LIST_ENTRY(type)						\
struct {								\
	struct type *le_next;	/* next element */			\
	struct type **le_prev;	/* address of previous next element */	\
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

[双链表结构,注意le_prev蓝色字和红色字的区别]

3.2 获取成员

双链表获取成员的宏函数和单链表一样, 这里就不展开说明了

#define	LIST_FIRST(head)		((head)->lh_first)
#define	LIST_END(head)			NULL
#define	LIST_EMPTY(head)		(LIST_FIRST(head) == LIST_END(head))
#define	LIST_NEXT(elm, field)		((elm)->field.le_next)

#define LIST_FOREACH(var, head, field)					\
	for((var) = LIST_FIRST(head);					\
	    (var)!= LIST_END(head);					\
	    (var) = LIST_NEXT(var, field))

1
2
3
4
5
6
7
8
9
10

3.3 操作函数

重点讲下LIST_INSERT_HEAD, LIST_MOVE两个函数

// ....
/*
	双链表头部插入
	注意点: 
	1. 首节点的le_prev保存的是head->lh_first
	2. 下一个节点(除了首节点)的le_prev保存的是前一节点的le_next的地址(见上图)
*/
#define LIST_INSERT_HEAD(head, elm, field) do {				\
	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
	(head)->lh_first = (elm);					\
	(elm)->field.le_prev = &(head)->lh_first;			\
} while (0)

/*
	双链表移除一个节点
	le_prev指针的更改是很容易想到的, 而对于*(elm)->field.le_prev这波操作是不是让人看不懂?
	在上面讲到le_prev指针是保存的前一个节点le_next的地址, 那么解引用之后是不是就是le_next保存的值
	这里的意思是将前一个节点le_next值指向要删除节点elm节点的下一个le_next的值
*/
#define LIST_REMOVE(elm, field) do {					\
	if ((elm)->field.le_next != NULL)				\
		(elm)->field.le_next->field.le_prev =			\
		    (elm)->field.le_prev;				\
	*(elm)->field.le_prev = (elm)->field.le_next;			\
} while (0)
//.....
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

3.4 关于le_prev双指针的说明

相信第一次接触这个结构的同学, 多半都会犯晕,这里为啥使用二级指针, 在数据结构中一般都是使用

typedef struct Node {
	// .....
	Node *next;
	Node *prev;
}; 
1
2
3
4
5

这种结构. 就我的理解, 二级指针在这里有如下的特点:
1 . 兼容性 我们在数据结构书中的双链表中的prev和next节点初始化状态是指向头结点的, 就像下面的赋值语句 .

void InitDList(List *list)
{
	Node *s = (Node *)malloc(sizeof(Node));
	list->first = list->last = s;
	list->last->next = NULL;
	list->first->prio = NULL;
	list->size = 0;
}
1
2
3
4
5
6
7
8

而在本文档中这种类型的结构中LIST_HEAD和LIST_ENTRY是没有头节点的, 只有个lh_first指针爱用不用; 但是如果le_prev是一级指针在首节点(这里区分首节点和头结点)会发现指向的结构和非首节点指向的类型并不是一致.
2. 方便性 在LIST_REMOVE中我们看到可以通过elm的le_prev指针进行解引用后来操控指向下一个le_next指针,好像有点勉强

4. 几点思考

经过上面的说明, 在queue.h文件中的其他结构大体类似, 本节需要思考的几点如下:

1. 为啥要"发明"像queue.h中的这种链表结构, 而不是使用数据结构书中所讲的通用结构?
2. 链表的优劣在哪里?
3. 开源项目中都是怎么使用链表的?

先说说第一个问题, 就我的想法, 理由如下:

1. 灵活性 如果每个结构都需要链表, 按照数据结构书上的结构定义, 每个结构都要那么定义一次, 这样重复的工作是比较抓狂的, queue.h中的链表定义做到了.
2. 简单性 确实两个指针乃至三个指针非常简单, 但是我想说的简单是, 使用这种结构我不用考虑数据内容的构造, 数据内容的初始化, 数据内容的析构等问题. 我们在数据结构书中的结构是需要考虑这种问题的. 我们在数据结构书中得到的案例无非是typedef int ElemType;或者是#define ElemType int这种类型的定义, 对于数据的考虑是弱化的. 但是在实际项目中专注的问题还是数据方面的, 怎么创建性能更好, 怎么释放不会引起内存泄漏. 不过可以通过如下数据结构来解决数据的弱化问题.

typedef struct ListNode {

	struct ListNode *prev;
	struct ListNode *next;
	void *data;
} ListNode;

typedef struct List {

	ListNode *header;
	ListNode *tailer;
	int size;

	void *(*Dup)(void *data);
	void *(*Free)(void *data);
	int (*Cmp)(void *data1, void *data2);
	void (*Visit)(void *data);

} List;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在定义结构时候, 我提供数据的创建,释放等操作不就可以了! 这种问题在C++就相对轻松, 直接一个模板泛型就可以搞定了.

第二个问题, 链表这种结构, 对于插入操作比较多, 而且数据量不大的情况, 像linux内核中的进程就绪和运行等队列(早先版本, Linux内核是限制了进程的个数为64, 128, 具体数字没有考究)就很适合用队列(也就是双向链表). 链表的劣势我可以简单列举如下几点:

1. 缓存问题 程序利用局部性原理, 会预加载数据或指令到CPU缓存中, 或者往更高层考虑, 现在的缓存服务器(Redis, memcached等), 都需要通过空间换取时间. 然而链表采用的是指针的指向来保证逻辑上的顺序, 这样或多或少对缓存不友好, 需要加载的数据在不同的地方.
2. 性能问题 对于要求查询的容器中, 链表的查询需要遍历整个结构

第三个问题, 开源项目(C/C++开源项目)中用链表的地方很多, nginx中将内存池pool和buffer_chain链接起来都用到了链表. Redis在早期版本中使用的是普通的双链表, 但是在新一点的版本(没去考究哪个具体版本改善的)就将普通的链表废除了, 改用quicklist结构, 这个结构是结合了链表的特点, "尽量"避免了链表的缺点, 其实结构很简单, 将链表的每个节点先做成一个序列化容器(就形同于数组之类的), 然后节点之间用链表连缀起来.