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