Libevent源码学习之基本数据结构:单链表(queue.h)

Libevent库的基本数据结构单链表的实现在compat/sys/queue.h头文件中,主要实现单链表的基本功能,包括,插入,遍历,删除等等,该单链表包含头结点。nginx-release-1.14.0版本的实现源码如下:

/*
 * Singly-linked List definitions.
 */
// 定义单链表头结点结构
#define SLIST_HEAD(name, type)						\
struct name {								\
	struct type *slh_first;	/* first element */			\
}

#define	SLIST_HEAD_INITIALIZER(head)					\
	{ NULL }

// Linux系统往下走,Windows不做。我也不关心Windows编程,哈哈~
#ifndef _WIN32
#define SLIST_ENTRY(type)						\
struct {								\
	struct type *sle_next;	/* next element */			\
}
#endif
/*
 * Singly-linked List access methods.
 */
// 单链表第一数据结点
#define	SLIST_FIRST(head)	((head)->slh_first)
// 单链表最后一个数据结点的下一个结点(NULL)
#define	SLIST_END(head)		NULL
// 判断单链表是否为空,即第一个数据结点是否为NULL
#define	SLIST_EMPTY(head)	(SLIST_FIRST(head) == SLIST_END(head))
// 数据结点elm的下一个结点
#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
// 遍历整个单链表
#define	SLIST_FOREACH(var, head, field)					\
	for((var) = SLIST_FIRST(head);					\
	    (var) != SLIST_END(head);					\
	    (var) = SLIST_NEXT(var, field))

/*
 * Singly-linked List functions.
 */
// 单链表初始化,即一个空单链表
#define	SLIST_INIT(head) {						\
	SLIST_FIRST(head) = SLIST_END(head);				\
}
// 在数据结点slistelm后面插入数据结点elm
#define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
	(slistelm)->field.sle_next = (elm);				\
} while (0)
// 在head结点后面插入数据结点elm
#define	SLIST_INSERT_HEAD(head, elm, field) do {			\
	(elm)->field.sle_next = (head)->slh_first;			\
	(head)->slh_first = (elm);					\
} while (0)
// 删除head后面第一个数据结点
#define	SLIST_REMOVE_HEAD(head, field) do {				\
	(head)->slh_first = (head)->slh_first->field.sle_next;		\
} while (0)

下面我们来写个单链表测试例子:

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

// 单链表数据节点
struct simple_list_data
{
	int data;
	SLIST_ENTRY(simple_list_data) field;
};

// 单链表头结点
SLIST_HEAD(simple_list, simple_list_data);

// 打印单链表
void simple_list_print(struct simple_list *head)
{
	struct simple_list_data *var;

	SLIST_FOREACH(var, head, field)
	{
		printf("%d  ", var->data);
	}

	printf("\n");
}

int main(void)
{
	// 构造单链表头结点
	struct simple_list *head = malloc(sizeof(struct simple_list));
	SLIST_INIT(head);

	// 单链表插入
	for(int i=0; i<10; i++)
	{
		struct simple_list_data *elm = malloc(sizeof(struct simple_list_data));
		elm->data = i;
		SLIST_INSERT_HEAD(head, elm, field);

		simple_list_print(head);
	}

	// 单链表删除
	while(!SLIST_EMPTY(head))
	{
		struct simple_list_data *elm = SLIST_FIRST(head);

		SLIST_REMOVE_HEAD(head, field);

		if(!SLIST_EMPTY(head))
		{
			simple_list_print(head);
		}

		free(elm);
	}
	free(head);

	return 0;
}

运行结果如下:

[ycxie@fedora Workspace]$ gcc libevent_slist.c -o libevent_slist -Wall
[ycxie@fedora Workspace]$ ./libevent_slist
0  
1  0  
2  1  0  
3  2  1  0  
4  3  2  1  0  
5  4  3  2  1  0  
6  5  4  3  2  1  0  
7  6  5  4  3  2  1  0  
8  7  6  5  4  3  2  1  0  
9  8  7  6  5  4  3  2  1  0  
8  7  6  5  4  3  2  1  0  
7  6  5  4  3  2  1  0  
6  5  4  3  2  1  0  
5  4  3  2  1  0  
4  3  2  1  0  
3  2  1  0  
2  1  0  
1  0  
0 

Leave a Reply

Your email address will not be published. Required fields are marked *