libevent是使用C语言实现的一套事件驱动的网络库，内部定义了五种常用的数据结构，分别是单向链表、链表，简单队列，尾队列，循环队列、实现在 compat/sys/queue.h中。其中对指针的指针的运用非常值得好好学习

   C语言中通过宏定义的，可以实现类似实现C++的模板类。

单链表

结构体定义

链表头

#define SLIST_HEAD(name, type)						\
struct name {								\
	struct type *slh_first;	/* first element */			\
}

#define	SLIST_HEAD_INITIALIZER(head)					\
	{ NULL }

分析代码，可知列表头的结构体名称由name决定，而链表头部的指针类型是type。链表头的作用是作为整个链表的头部元素，其中slh_first指针总是指向链表的第一个实体. 这一段代码实现的功能，类似于C++中的模板类。就是定义链表头部结构

链表实体

#ifndef _WIN32
#define SLIST_ENTRY(type)						\
struct {								\
	struct type *sle_next;	/* next element */			\
}
#endif

     单链表只有一个next指针指向下一个链表元素。所以sle_next指向下一个链表实体

API接口

//获取链表的第一个元素实体
#define	SLIST_FIRST(head)
//获取链表结束指针
#define	SLIST_END(head)
//判断链表是否为空
#define	SLIST_EMPTY(head)
//获取链表成员elm的下一个元素
#define	SLIST_NEXT(elm, field)
//遍历链表
#define	SLIST_FOREACH(var, head, field)
//初始化链表
#define	SLIST_INIT(head)
//在链表的指定位置之后插入新元素
#define	SLIST_INSERT_AFTER(slistelm, elm, field)
//将新元素插入链表头部
#define	SLIST_INSERT_HEAD(head, elm, field)
//删除链表头元素
#define	SLIST_REMOVE_HEAD(head, field)

上面这个API，是我将代码中的实现剥离后的结果，实际上c中实现与声明是在一起的，通过宏定义实现的一种函数定义。

其中head表示这个对象是链表头指针，elm表示包含链表实体的结构体指针，field表示链表实体指针在elm中的成员名称。field是elm中的一个类成员

函数实现

先将简单的几个实现贴上，其中包含初始化、遍历链表、判空、获取头部指针、获取尾部指针等

/*
 * Singly-linked List access methods.
 */
#define	SLIST_FIRST(head)	((head)->slh_first)
#define	SLIST_END(head)		NULL
#define	SLIST_EMPTY(head)	(SLIST_FIRST(head) == SLIST_END(head))
#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);				\

单链表的插入比较简单，首先看下在链表头部插入的实现。

#define	SLIST_INSERT_HEAD(head, elm, field) do {			\
	(elm)->field.sle_next = (head)->slh_first;			\
	(head)->slh_first = (elm);					\
} while (0)

从代码中可以看到就两行代码，先是修改elm的next指针，然后是修改链表头的first指针。下面我们用几张图片来详细解释下链表的插入情况。

链表为空时：

                                                 

此时在链表头部插入元素：

                                    

其中。1是SLIST_INSERT_HEAD第一行的代码结果，2是SLIST_INSERT_HEAD第二行的代码结果。最终结果如下：

                                   

继续执行N次后的效果如下：

理解了SLIST_INSERT_HEAD，那么SLIST_INSERT_AFTER应该也不难理解了。我们先看下实现

#define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
	(slistelm)->field.sle_next = (elm);				\
} while (0)

     仔细与SLIST_INSERT_HEAD对比，发现就是插入的位置不同而已，把head替换成slistelm，再把slh_first指针替换成sle_next即可。

    现在我们来看下链表的元素删除。libevent中的单链表只提供了删除链表头元素的接口与实现。先看代码

#define	SLIST_REMOVE_HEAD(head, field) do {				\
	(head)->slh_first = (head)->slh_first->field.sle_next;		\
} while (0)

    仔细分析代码，发现只要将head的first的指向替换成之前指针的next即可。如图所示：

sle_next中的红叉是节点被删除后的效果。

    以上就是单链表的实现，比较简单。接下来介绍libevent中的链表实现