libevent源码剖析-基本数据结构

1 简介

    前面系列文章对libevent源码的主体结构，从reactor框架实现，到evbuffer和bufferevent实现原理，及libevent的例子进行了剖析，自此，我们便可基于libevent开发app了。

    从本文开始，主要来介绍下libevent源码的枝叶部分，包括基本数据结构、C开发技巧、工具函数等。

2 基本数据结构

2.1 单链表

    单链表相关操作都在libevent源码根目录compat/sys/queue.h文件下。这里简要介绍下单链表原理及其操作。

    单链表是一种链式存储的数据结构，每个节点包含数据域和指向下一个节点的指针。下面是单链表的主要优缺点：

优点

• 动态内存分配：单链表的节点可以在需要时动态分配和释放，不需要提前分配固定大小的内存，适合需要频繁插入和删除的情况。

• 插入和删除操作效率高：在已知位置进行插入和删除操作只需更改指针即可，时间复杂度为 O(1)。相比数组无需移动其他元素，因此适合频繁插入、删除操作的场景。

• 节省内存：单链表只需存储数据和一个指向下个节点的指针，比双向链表节省内存开销，适用于内存敏感的应用。

• 便于扩展：由于链表不需要连续的内存空间，所以扩展链表时只需增加节点，不会涉及整体内存的重新分配和复制操作。

缺点

• 随机访问性能差：单链表不支持随机访问，要访问某个特定位置的节点，必须从头开始逐个遍历，时间复杂度为 O(n)，在访问频繁的场景性能较低。

• 额外的存储开销：每个节点需要存储一个指针用于链接下一个节点，若数据较小或节点较多，指针的额外存储开销会显得较大。

• 不便于反向遍历：单链表只能从头到尾顺序遍历，无法反向遍；如果需要反向遍历的功能，需要转换成双向链表或借助栈等辅助数据结构。

• 链表操作的指针复杂性：在操作链表（如插入、删除）时，指针的使用容易导致错误，例如指针丢失、空指针访问等，增加了开发和调试的难度。

    单链表适合数据量动态变化、需要频繁插入和删除、但不要求随机访问的场景。

单链表结构图 

2.1.1 定义

    C单链表结构定义如下：

/** Singly-linked List definitions.*/
#define SLIST_HEAD(name, type)						\
struct name {								\struct type *slh_first;	/* first element */			\
}#define	SLIST_HEAD_INITIALIZER(head)					\{ NULL }#ifndef _WIN32
#define SLIST_ENTRY(type)						\
struct {								\struct type *sle_next;	/* next element */			\
}
#endif

2.1.2 访问方法

    libevent通过宏定义来访问单链表的数据成员及遍历：

/** 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))

2.1.3 操作函数 

    libevent实现的单链表操作主要有：初始化、中间插入、头部插入、尾部插入、头部移除：

/** Singly-linked List functions.*/
#define	SLIST_INIT(head) {						\SLIST_FIRST(head) = SLIST_END(head);				\
}#define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\(elm)->field.sle_next = (slistelm)->field.sle_next;		\(slistelm)->field.sle_next = (elm);				\
} while (0)#define	SLIST_INSERT_HEAD(head, elm, field) do {			\(elm)->field.sle_next = (head)->slh_first;			\(head)->slh_first = (elm);					\
} while (0)#define	SLIST_REMOVE_HEAD(head, field) do {				\(head)->slh_first = (head)->slh_first->field.sle_next;		\
} while (0)

    以上是SLIST单链表所有源码实现，相对简单，不赘述。

2.2 双向链表

    在libevent中，LIS链表是一种双向链表结构，其每个节点包含一个指向前后节点的指针。和单向链表不同，双向链表一般是用来表示事件的多重组织方式，即不同事件类型和优先级的事件链。下面是双向链表的优缺点：

优点

• 层级化的事件管理：双向链表可以将事件按优先级、事件类型等不同维度进行分层组织，方便事件循环时按需分配处理，尤其在多优先级事件的场景中非常有效。

• 便于按优先级调度：通过将高优先级事件和低优先级事件划分到不同链表层级中，处理事件时可以优先处理高优先级链表上的事件，便于实现调度控制，保证关键事件的及时性。

• 插入、删除操作简便：双向链表特性使得在任意位置插入或删除节点非常高效，只需调整前后指针，时间复杂度为 O(1)，适合频繁操作。

• 事件遍历灵活：可以在多层链表中进行迭代，适合多种情况下的事件遍历、优先级切换等。对于复杂事件处理逻辑，可以快速遍历特定层级事件，提升事件处理效率。

缺点

• 内存消耗较大：每个节点需要存储两个指针（指向前后节点），如果链表层级很多且节点较多，内存开销会明显增大。

• 操作复杂性增加：双向链表的多层级设计，尤其是在事件分层组织、删除和调整优先级时，对开发者理解和调试的要求较高，可能导致复杂的指针操作错误。

• 访问深层节点效率降低：如果事件在较低优先级的层级，处理时需要逐层遍历链表才能访问到这些事件，效率相对较低，适合优先级较为集中的场景。

• 对随机访问支持差：链表结构本身不支持随机访问，查找特定事件或位置的节点时需要顺序遍历，在大规模节点的情况下效率较低。

双向链表结构图 

2.2.1 定义

/** List definitions.*/
#define LIST_HEAD(name, type)						\
struct name {								\struct type *lh_first;	/* first element */			\
}#define LIST_HEAD_INITIALIZER(head)					\{ NULL }#define LIST_ENTRY(type)						\
struct {								\struct type *le_next;	/* next element */			\struct type **le_prev;	/* address of previous next element */	\
}

 2.2.2 访问方法 

/** List access methods*/
#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))

     2.2.3 操作函数

/** List functions.*/
#define	LIST_INIT(head) do {						\LIST_FIRST(head) = LIST_END(head);				\
} while (0)#define LIST_INSERT_AFTER(listelm, elm, field) do {			\if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\(listelm)->field.le_next->field.le_prev =		\&(elm)->field.le_next;				\(listelm)->field.le_next = (elm);				\(elm)->field.le_prev = &(listelm)->field.le_next;		\
} while (0)#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\(elm)->field.le_prev = (listelm)->field.le_prev;		\(elm)->field.le_next = (listelm);				\*(listelm)->field.le_prev = (elm);				\(listelm)->field.le_prev = &(elm)->field.le_next;		\
} while (0)#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)#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)#define LIST_REPLACE(elm, elm2, field) do {				\if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)	\(elm2)->field.le_next->field.le_prev =			\&(elm2)->field.le_next;				\(elm2)->field.le_prev = (elm)->field.le_prev;			\*(elm2)->field.le_prev = (elm2);				\
} while (0)

2.3 简单队列 

    libevent中的简单队列是一个由单链表来实现的。simple queue 是一种简单的队列数据结构，它通常用于按顺序存储和访问元素。队列是一种先进先出（FIFO, First In First Out）结构，元素总是从队尾插入，从队首删除。下面是 simple queue 的特点、基本操作和优缺点。

特点

• FIFO（先进先出）：最先进入队列的元素会最先被处理。
• 单向操作：通常只允许在队尾插入元素、在队首删除元素，保持队列有序性。
• 动态增长：可以在需要时动态添加元素，内存使用通常灵活。

优点

• 操作简单：只需操作队尾和队首，插入和删除的复杂度为 O(1)。
• 内存效率：链表实现的队列可以根据需要动态调整大小，适合存储不确定数量的数据。
• 无锁并发：在一些并发场景中，可以通过特定设计使队列支持无锁操作，提高并发访问的效率。

缺点

• 随机访问效率低：只能按顺序访问元素，无法高效地进行随机访问。
• 可能有内存开销：链表实现的队列会在每个节点上存储额外的指针信息，在大量节点时会增加内存使用。
• 阻塞问题：在生产者-消费者场景中，如果生产或消费速度不匹配，可能会导致队列过长或过短，需额外处理队列满或空的情况。 

 简单队列结构图

    2.3.1定义

/** Simple queue definitions.*/
#define SIMPLEQ_HEAD(name, type)					\
struct name {								\struct type *sqh_first;	/* first element */			\struct type **sqh_last;	/* addr of last next element */		\
}#define SIMPLEQ_HEAD_INITIALIZER(head)					\{ NULL, &(head).sqh_first }#define SIMPLEQ_ENTRY(type)						\
struct {								\struct type *sqe_next;	/* next element */			\
}

    2.3.2 访问方法

/** Simple queue access methods.*/
#define	SIMPLEQ_FIRST(head)	    ((head)->sqh_first)
#define	SIMPLEQ_END(head)	    NULL
#define	SIMPLEQ_EMPTY(head)	    (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
#define	SIMPLEQ_NEXT(elm, field)    ((elm)->field.sqe_next)#define SIMPLEQ_FOREACH(var, head, field)				\for((var) = SIMPLEQ_FIRST(head);				\(var) != SIMPLEQ_END(head);					\(var) = SIMPLEQ_NEXT(var, field))

    2.3.3 操作函数

/** Simple queue functions.*/
#define	SIMPLEQ_INIT(head) do {						\(head)->sqh_first = NULL;					\(head)->sqh_last = &(head)->sqh_first;				\
} while (0)#define SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\(head)->sqh_last = &(elm)->field.sqe_next;		\(head)->sqh_first = (elm);					\
} while (0)#define SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\(elm)->field.sqe_next = NULL;					\*(head)->sqh_last = (elm);					\(head)->sqh_last = &(elm)->field.sqe_next;			\
} while (0)#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\(head)->sqh_last = &(elm)->field.sqe_next;		\(listelm)->field.sqe_next = (elm);				\
} while (0)#define SIMPLEQ_REMOVE_HEAD(head, elm, field) do {			\if (((head)->sqh_first = (elm)->field.sqe_next) == NULL)	\(head)->sqh_last = &(head)->sqh_first;			\
} while (0)

2.4 尾队列

    TAILQ 是一种双向链表队列，广泛用于 BSD 系统和 libevent 库中。它支持从队列头部或尾部高效地插入、删除和访问元素，便于实现先进先出（FIFO）队列、双端队列等多种数据结构。TAILQ 的设计特点主要在于它使用双向链表维护队列顺序，尾部始终指向最后一个元素，因此插入和删除操作效率较高。

    相关操作在include/event2/event_struct.h文件下，如果对应平台有此<sys/queue.h>文件相应实现，则可直接用。

优点

• 双端操作高效：TAILQ 支持头部和尾部的高效插入和删除操作，时间复杂度均为 O(1)。
• 灵活性高：支持在任意位置插入和删除，适合实现各种类型的队列、链表、双端队列等。
• 结构简洁：TAILQ 数据结构相对简单，内存开销较低，适合内核、系统编程等低资源场景。

缺点

• 访问性能差：TAILQ 不支持随机访问，访问特定位置需要顺序遍历，效率较低。
• 指针操作复杂：TAILQ 的双向指针结构在操作中容易出现指针悬挂、泄漏等错误，增加开发难度。

 尾队列结构图

    2.4.1 定义

/** Tail queue definitions.*/
#define TAILQ_HEAD(name, type)						\
struct name {								\struct type *tqh_first;	/* first element */			\struct type **tqh_last;	/* addr of last next element */		\
}#define TAILQ_HEAD_INITIALIZER(head)					\{ NULL, &(head).tqh_first }#define TAILQ_ENTRY(type)						\
struct {								\struct type *tqe_next;	/* next element */			\struct type **tqe_prev;	/* address of previous next element */	\
}

    2.4.2 方法访问

/** tail queue access methods*/
#define	TAILQ_FIRST(head)		((head)->tqh_first)
#define	TAILQ_END(head)			NULL
#define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
#define TAILQ_LAST(head, headname)					\(*(((struct headname *)((head)->tqh_last))->tqh_last))
/* XXX */
#define TAILQ_PREV(elm, headname, field)				\(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
#define	TAILQ_EMPTY(head)						\(TAILQ_FIRST(head) == TAILQ_END(head))#define TAILQ_FOREACH(var, head, field)					\for((var) = TAILQ_FIRST(head);					\(var) != TAILQ_END(head);					\(var) = TAILQ_NEXT(var, field))#define TAILQ_FOREACH_REVERSE(var, head, headname, field)		\for((var) = TAILQ_LAST(head, headname);				\(var) != TAILQ_END(head);					\(var) = TAILQ_PREV(var, headname, field))

    2.4.3 操作函数

/** Tail queue functions.*/
#define	TAILQ_INIT(head) do {						\(head)->tqh_first = NULL;					\(head)->tqh_last = &(head)->tqh_first;				\
} while (0)#define TAILQ_INSERT_HEAD(head, elm, field) do {			\if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\(head)->tqh_first->field.tqe_prev =			\&(elm)->field.tqe_next;				\else								\(head)->tqh_last = &(elm)->field.tqe_next;		\(head)->tqh_first = (elm);					\(elm)->field.tqe_prev = &(head)->tqh_first;			\
} while (0)#define TAILQ_INSERT_TAIL(head, elm, field) do {			\(elm)->field.tqe_next = NULL;					\(elm)->field.tqe_prev = (head)->tqh_last;			\*(head)->tqh_last = (elm);					\(head)->tqh_last = &(elm)->field.tqe_next;			\
} while (0)#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\(elm)->field.tqe_next->field.tqe_prev =			\&(elm)->field.tqe_next;				\else								\(head)->tqh_last = &(elm)->field.tqe_next;		\(listelm)->field.tqe_next = (elm);				\(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
} while (0)#define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\(elm)->field.tqe_next = (listelm);				\*(listelm)->field.tqe_prev = (elm);				\(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
} while (0)#define TAILQ_REMOVE(head, elm, field) do {				\if (((elm)->field.tqe_next) != NULL)				\(elm)->field.tqe_next->field.tqe_prev =			\(elm)->field.tqe_prev;				\else								\(head)->tqh_last = (elm)->field.tqe_prev;		\*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
} while (0)#define TAILQ_REPLACE(head, elm, elm2, field) do {			\if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)	\(elm2)->field.tqe_next->field.tqe_prev =		\&(elm2)->field.tqe_next;				\else								\(head)->tqh_last = &(elm2)->field.tqe_next;		\(elm2)->field.tqe_prev = (elm)->field.tqe_prev;			\*(elm2)->field.tqe_prev = (elm2);				\
} while (0)

2.4 圆形队列

    Circular Queue（循环队列）是一种队列数据结构，它将队列逻辑上视为“环形结构”，通过在固定大小的数组中实现循环，来避免普通线性队列出现的“假溢出”问题。循环队列在系统编程和实时系统中常用，如 CPU 调度、任务管理等。

优点

• 内存效率高：循环队列的最大优势在于通过循环重用数组空间，避免了普通线性队列“假溢出”的问题。
• 固定大小：在实时和嵌入式系统中，循环队列的固定数组大小有助于内存管理。

缺点

• 容量限制：固定数组大小的循环队列有容量上限，超出限制会导致队列溢出。
• 指针计算复杂：由于指针的循环移动，操作比单纯的线性队列复杂，可能会产生边界问题。

 环形队列结构图

2.4.1 定义

/** Circular queue definitions.*/
#define CIRCLEQ_HEAD(name, type)					\
struct name {								\struct type *cqh_first;		/* first element */		\struct type *cqh_last;		/* last element */		\
}#define CIRCLEQ_HEAD_INITIALIZER(head)					\{ CIRCLEQ_END(&head), CIRCLEQ_END(&head) }#define CIRCLEQ_ENTRY(type)						\
struct {								\struct type *cqe_next;		/* next element */		\struct type *cqe_prev;		/* previous element */		\
}

 2.4.2 访问方法

/** Circular queue access methods*/
#define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
#define	CIRCLEQ_LAST(head)		((head)->cqh_last)
#define	CIRCLEQ_END(head)		((void *)(head))
#define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
#define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
#define	CIRCLEQ_EMPTY(head)						\(CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))#define CIRCLEQ_FOREACH(var, head, field)				\for((var) = CIRCLEQ_FIRST(head);				\(var) != CIRCLEQ_END(head);					\(var) = CIRCLEQ_NEXT(var, field))#define CIRCLEQ_FOREACH_REVERSE(var, head, field)			\for((var) = CIRCLEQ_LAST(head);					\(var) != CIRCLEQ_END(head);					\(var) = CIRCLEQ_PREV(var, fie

2.4.3 操作函数

/** Circular queue functions.*/
#define	CIRCLEQ_INIT(head) do {						\(head)->cqh_first = CIRCLEQ_END(head);				\(head)->cqh_last = CIRCLEQ_END(head);				\
} while (0)#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\(elm)->field.cqe_next = (listelm)->field.cqe_next;		\(elm)->field.cqe_prev = (listelm);				\if ((listelm)->field.cqe_next == CIRCLEQ_END(head))		\(head)->cqh_last = (elm);				\else								\(listelm)->field.cqe_next->field.cqe_prev = (elm);	\(listelm)->field.cqe_next = (elm);				\
} while (0)#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\(elm)->field.cqe_next = (listelm);				\(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\if ((listelm)->field.cqe_prev == CIRCLEQ_END(head))		\(head)->cqh_first = (elm);				\else								\(listelm)->field.cqe_prev->field.cqe_next = (elm);	\(listelm)->field.cqe_prev = (elm);				\
} while (0)#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\(elm)->field.cqe_next = (head)->cqh_first;			\(elm)->field.cqe_prev = CIRCLEQ_END(head);			\if ((head)->cqh_last == CIRCLEQ_END(head))			\(head)->cqh_last = (elm);				\else								\(head)->cqh_first->field.cqe_prev = (elm);		\(head)->cqh_first = (elm);					\
} while (0)#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\(elm)->field.cqe_next = CIRCLEQ_END(head);			\(elm)->field.cqe_prev = (head)->cqh_last;			\if ((head)->cqh_first == CIRCLEQ_END(head))			\(head)->cqh_first = (elm);				\else								\(head)->cqh_last->field.cqe_next = (elm);		\(head)->cqh_last = (elm);					\
} while (0)#define	CIRCLEQ_REMOVE(head, elm, field) do {				\if ((elm)->field.cqe_next == CIRCLEQ_END(head))			\(head)->cqh_last = (elm)->field.cqe_prev;		\else								\(elm)->field.cqe_next->field.cqe_prev =			\(elm)->field.cqe_prev;				\if ((elm)->field.cqe_prev == CIRCLEQ_END(head))			\(head)->cqh_first = (elm)->field.cqe_next;		\else								\(elm)->field.cqe_prev->field.cqe_next =			\(elm)->field.cqe_next;				\
} while (0)#define CIRCLEQ_REPLACE(head, elm, elm2, field) do {			\if (((elm2)->field.cqe_next = (elm)->field.cqe_next) ==		\CIRCLEQ_END(head))						\(head).cqh_last = (elm2);				\else								\(elm2)->field.cqe_next->field.cqe_prev = (elm2);	\if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) ==		\CIRCLEQ_END(head))						\(head).cqh_first = (elm2);				\else								\(elm2)->field.cqe_prev->field.cqe_next = (elm2);	\
} while (0)

2.5 哈希表

优点

• 高效查询和插入：哈希表的设计使其查询和插入的平均时间复杂度接近 O(1)，在管理大量事件（如定时器事件）时非常高效。

• 动态扩展：libevent 的哈希表可以根据负载因子动态扩展，降低碰撞率并保持性能。

• 空间利用率高：哈希表通过散列函数分布元素，避免了链表或树结构的空间浪费，适合事件数量较多的场景。

缺点

• 内存占用波动：在动态扩展过程中，哈希表需要重新分配内存，这可能导致内存使用不稳定。

• 碰撞处理开销：尽管有较低的碰撞概率，但在高负载情况下，链表长度可能增加，导致操作复杂度退化为 O(n)。

• 线程不安全：libevent 中的哈希表设计在多线程环境下不安全，使用时需要额外的锁机制来避免竞争。

    libevent在对IO事件和signal事件进行组织管理的时候，采用的哈希表，以IO事件为例，fd为哈希表的桶，哈希槽为evmap_io的双向链表，详见下图：

IO事件哈希表 

libevent在对signal事件的组织管理方式，与IO事件基本是一样的，以signal为桶，哈希槽为evmap_signal的双向链表，详见下图：

signal事件结构图 

3 小结

• 本文主要对libevent的基本数据结构进行介绍，包括单链表、双向链表、简单队列、尾队列、圆形队列以及哈希表的实现原理；
• 除了timer事件使用了小跟堆以外，libevent对event的组织和管理基本都可以用以上基本数据结构来组织，小跟堆将另起一文来加以介绍。