libevent中的数据结构之链表


上一节,我们学习了libevent中的单链表,现在我们再来看看链表的实现。这里我们要重点关注指针的指针的用法。

结构体定义

链表头结构体

/*
 * List definitions.
 */
#define LIST_HEAD(name, type)						\
struct name {								\
	struct type *lh_first;	/* first element */			\
}
实体结构体
#define LIST_ENTRY(type)						\
struct {								\
	struct type *le_next;	/* next element */			\
	struct type **le_prev;	/* address of previous next element */	\
}
可以看到,这里的实体相比单向链表,多了prev指针。通常来说,双向链表,都包含前驱指针和后驱指针,其中,前驱指针指向的是前一个节点,而后驱指针,则是指向的后一个节点。且通常两个指针的类型都是一样的,都是type *,但是在libevent的实现中,这有所不同。独特的定义prev的类型是指针的指针。这么做有什么好处呢?我们后面再讨论

API接口

//获取链表第一个实体
#define	LIST_FIRST(head)
//获取链表结束
#define	LIST_END(head)
//判断链表是否为空
#define	LIST_EMPTY(head)
//获取元素的下一个元素
#define	LIST_NEXT(elm, field)
//遍历链表
#define LIST_FOREACH(var, head, field)
//链表头初始化
#define	LIST_INIT(head) 
//在指定位置之后插入新元素
#define LIST_INSERT_AFTER(listelm, elm, field)
//在指定位置之前插入新元素
#define	LIST_INSERT_BEFORE(listelm, elm, field)
//在链表头部之后插入
#define LIST_INSERT_HEAD(head, elm, field)
//删除链表元素
#define LIST_REMOVE(elm, field)
//使用新元素替换旧元素
#define LIST_REPLACE(elm, elm2, field)
     对比单链表,我们发现链表多了一些方法,分别是LIST_INSERT_BEFORE和LIST_REPLACE。这两个多出的方法,是因为有了前驱指针之后才可以实现的。我们后面再看他们的具体实现。head、elm、field等同单链表一样,head表示链表头,elm表示包含链表实体的结构体的对象,而field是表示链表实体在elm中的成员名称。

接口实现

首先我们看下链表的一些简单函数的实现。

/*
 * 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))
/*
 * List functions.
 */
#define	LIST_INIT(head) do {						\
	LIST_FIRST(head) = LIST_END(head);				\
} while (0)
    从链表头的初始化定义中,我们可以看出,链表头的lh_first指针初始化为NULL。链表的遍历,类似于C++中的迭代器遍历,先获取链表的第一个实体,然后获取下一个,下一个,直到到达链表的尾部。

    我们接下来来介绍链表的插入、删除等操作。先从插入说起吧,首先看下链表头的插入实现。

#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)

       首先,来看下链表的初始状态。当链表为空的时候,链表内的指针结果如图1所示。

                      

                                                     图1-空链表

此时插入第一个节点的过程如图2所示:

         

                                                                      图2-空链表时在链表头插入新元素时的指针指向

执行该方法N次之后,结果如图3所示:

                                        图3-连续插入N个节点

    我们现在回过头去看代码。在链表头之后插入新元素,有以下修改:A。原来第一个实体的prev要更新;B。链表头的lh_first要修改 C。新元素的prev设置 D。新元素的next设置

    结合代码,我们可以看出,代码行2对应于D的修改,而代码行3则对应于A的修改,因为空链表是不存在第一个实体的,所以这里需要进行判断。代码行4对应于B,将链表头的first指向新元素,代码行5则对应于C,设置新元素的prev指向链表头的lh_first指针。为什么要这么做呢?这么做有什么好处吗?我们可以在后续的很多地方看到prev是指针的指针的好处。现在先看下链表的删除。

    链表的删除实现如下

#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)
     对比单链表的删除,我们会发现删除的第一个参数不同。在单链表中,我们只能删除head,而在链表中,我们可以删除任意的elm,而这极大地提高了链表的灵活性。

    在正常的双向链表的删除中,删除一个元素,要修改的内容有 A:被删节点的前一个节点的next B:被删节点的后一个节点的prev  C:如果被删除的是链表的第一个实体,还要修改链表头的指向。

    其中,被删节点不一定有后续节点,所以这点需要判断,代码行3对应于有后续节点的B。正常情况下的双向链表中,C的修改是需要一个判断语句的。但是我们在代码中,没有看到相关的语句。而这也是我为什么说prev使用指针的指针的巧妙之处。不管删除的是不是链表的第一个实体,我们只需要修改被删除的节点的prev即可。因为prev指向的是前一个节点的next,所以只要我们对prev进行解引用,然后进行修改,我们就对前一个节点的next进行了修改。而这就对应于A的修改。至于C的情况,因为如果是第一个实体,则prev指向的是链表头的lh_first,所以我们对prev进行解引用然后修改,也是对lh_first的修改。是不是很巧妙呢?即减少了if的判断,也方便了对前一个节点的next的修改。

    现在,我们再来看下指定位置之后的新元素插入的实现。

#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)
     在一个有前驱和后驱的节点之后插入一个新元素,需要修改的内容有:A。指定位置的下一个节点的prev指针。 B。指定位置自身的next指针。C。新元素的prev指针 D。新元素的next指针。而指定位置的下一个节点是否存在,则需要进行判断。

    代码行2对应于修改D,代码行3则对应于修改A,是在判断了下一个节点非空之后才执行。将下一个节点的prev指针重新指向指定元素的next指针,而代码行5则对应于修改B,让指定位置的next指向新增元素。代码行6则对应于修改C,新增元素的prev指向指定位置的next位置。

    我们再看看在指定元素之前插入新元素的实现。

#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)
     同在指定位置之后插入元素类似,只不过是相反的关系。在指定位置之后插入元素,受影响是的指定位置的下一个节点,而在指定位置之前插入元素,则受影响的是前一个节点。所以,修改的内容如下:A。指定位置的前一个节点的next指针; B。指定位置自身的prev指针; C。新元素的prev指针; D。新元素的next指针

    正常的双向链表中,应该还有一个修改情况:如果指定位置是链表的第一个实体,则要修改链表头的指向。不同在libevent的实现中,因为使用了指针的指针,所以E的修改与A的修改一起进行了,同删除的类似。

    代码行2对应于修改C,新元素的prev直接用指定位置的prev即可。代码行3则对应于D的修改。新增元素的next指向指定元素。代码行4对应于修改A,修改指定位置的前一个节点的next为新增元素,而代码行5则对应于修改B,指定位置自身的prev指向新增元素的next指针。

    我们看下当指定位置是链表的第一个实体时,在指定位置之前插入的指针变化过程。


        其中1对应于代码行2,即修改C,2对应于修改D,代码行是3,而3对应的则是代码行4,同时,因为链表头的指向发生了改变,导致了上面的那个红叉,即原来的指向无效。而4对应的是代码行5,指定位置的prev指向也发生了变化,导致下面的那个红叉,原来prev指向的链表头成为无效。

    最后,我们看下链表的替换实现。

#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)
     新节点要替换旧节点,首先要转移旧节点的next与prev,这个是与旧节点自身相关的修改。还有如下内容的修改:A。原来节点的下一个节点的prev; B。原来节点的前一个节点的next。而一如既往的,对于节点的下一个节点是否存在,需要做判断。

    代码行2对于与转移旧节点的next指针,代码行3对应于修改A,当下一个节点存在时,修改下一个节点的prev指向新节点的next指针。代码行5对应于转移旧节点的prev,而代码行6则对应于修改B,修改前一个节点的next,让它指向新节点。因为prev是指向前一个节点的next,所以解引用之后的修改,就是对前一个节点的next的修改。

    链表的所有方法到这里就已经介绍完了,会发现其实都很简单,只要在脑中能勾勒出链表节点的指向,就完全不是问题。还有,我们在这里学到了指针的指针的妙用,让我们不再需要对链表的第一个实体进行判断。让代码更优美。



评论

发表评论