libevent中的数据结构之单链表
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中的链表实现
评论