libevent中的数据结构之简单队列


这节我们学习libevent提供的五类数据结构中的简单队列。说到队列,我们的映像就是队头出元素,队尾入元素的那种。那么,简单队列,是什么样子的呢??我们先来看下它的结构体定义有哪些,它们又分别是什么样子的。

结构体定义

队列头部结构体

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

队列头部结构体中,除了指向第一个实体的first指针以外,还有指向队尾的last指针,不过last的指针的类型是指针的指针,看到注释里面的描述,我们就知道,它是指向队尾元素的next指针。上一节我们学习链表的时候,就看到了指针的指针的妙用。现在我们继续学习。链表头结构体的初始化语法中,first指针为NULL,然后last指针指向first指针。对比我们之前学习的链表的链表头部结构,今天学习的简单队列,头部结构中多了sqh_last指针,即指向了队尾元素。从这两个指针可以推测,简单队列支持在队头和队尾中插入元素。而单向链表是只支持队头插入元素。

队列实体结构体

#define SIMPLEQ_ENTRY(type)						\
struct {								\
	struct type *sqe_next;	/* next element */			\
}

可以看出,简单队列的实体结构还真是够简单的,就一个next指针。通过这个结构体,我们就可以知道简单队列有哪些功能是没有的,比如逆序遍历、任意位置删除、在指定位置之前插入等,因为这些都要求当前元素有前驱指针.

    看到了简单队列的结构体,那么,我们再来看看为这个数据结构,都提供了哪些API接口吧

API接口


//获取简单队列的第一个元素
#define	SIMPLEQ_FIRST(head)	
//获取简单队列的尾部元素
#define	SIMPLEQ_END(head)
//判断简单队列是否为空
#define	SIMPLEQ_EMPTY(head)	
//获取元素的下一个元素
#define	SIMPLEQ_NEXT(elm, field)
//遍历简单队列
#define SIMPLEQ_FOREACH(var, head, field)
//初始化简单队列的头部
#define	SIMPLEQ_INIT(head)
//在简单队列头部之后插入新元素
#define SIMPLEQ_INSERT_HEAD(head, elm, field)
//在简单队列的尾部插入新元素
#define SIMPLEQ_INSERT_TAIL(head, elm, field)
//在指定位置之后插入新元素
#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field)
//删除简单队列头部的第一个实体
#define SIMPLEQ_REMOVE_HEAD(head, elm, field)
看了3类数据结构的API描述,发现大部分功能都是大同小异。都是插入、删除。有点区别的无非就是插入的位置是否支持任意,删除的位置是否支持任意。既然队列头结构中有指向尾元素的,那么我们看下这些实现是否会与链表有些不同。


接口实现

首先,我们继续先看简单但基础的实现。比如队列的初始化、队列的遍历等。


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

/*
 * Simple queue functions.
 */
#define	SIMPLEQ_INIT(head) do {						\
	(head)->sqh_first = NULL;					\
	(head)->sqh_last = &(head)->sqh_first;				\
} while (0)
队列的初始化接口,同结构体的初始化宏实现功能相同。首先是设置first的指针为空指针,然后让last指针指向first。


    又到了经典的插入接口的实现了。而第一个看的当然是经典中的经典,在头部之后插入的实现。

     先不看代码,只是看着队列头和队列实体的结构体,我们来猜猜,要实现队列头之后插入,会有哪些指针需要变化。首先,1.队头的first指针要指向新元素 2.新元素的next指针 3.当队列为空时在队头插入,则队列头结构体中的last指针要指向第一个实体的next指针。


#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)
     现在看着代码,我们对比我们之前的分析,看下我们认为的指针变化的几个情况,代码中是否都有体现。首先,修改1,我们在代码行4中找到;修改2,在代码行2中找到;而修改3,则是在代码行2中判断了队列头的first满足空指针之后,在代码行3中找到。所以,对于这种简单的数据结构的插入删除,我们只需要把握住指针指向的变化,就可以学习到精髓。


    现在,我们看下简单队列为空时的指针指向。见图1所示。

                                                      

                                                                       图1-空队列

然后,我们给空队列,在队列头部之后插入新元素,指针变化过程,如图2.

                                     

                                                                                图2-空队列中插入新元素

其中,队列实体中的data,是泛指包含队列实体的结构中的其他类成员。从上图中很容易的就看出来,指针指向的变化。sqh_first指向的是elm的起始位置,而sqh_last,指向的则是elm中sqe_next的位置。而空队列中的两个指针,被打上红叉,标为无效。

    我们再来看看在队头中插入N个元素之后,队列的结果图。见图3.

                                                           图3-插入N个元素之后

     了解了在队头插入元素,那么我们再来看看在队尾插入元素的实现。

    照例,我们先不看代码,分析下在队尾插入元素,有哪些指针要发生改变。1.队列头结构中的last指针 2.新元素的next指针 3.如果队列不空,则原来的队尾元素的next指针 4.如果队列为空,则修改队列头结构中的first指针。分析结束之后,我们看下代码是怎么实现的。


#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)
    首先,代码行2,对应的是我们猜测的修改2,而代码行4,则命中了我们的猜测1。而神奇地,代码行3,既可以对应我们的猜测3,也可以是猜测4。为什么呢?这是因为last的指针的指针,在队列为空的时候,指向的是队列头结构中的first指针,而当队列非空的时候,指向的是则是队尾中的next指针。因此,代码行3中将两者的情况都包含了。而如果last的类型不是指针的指针,那么代码实现应该多2行 if ... else... 。这也就是指针的指针在这里的好处了。


    我们再看看简单队列中的在指定位置之后的插入。先分析场景,该场景下,需要修改的指针有哪些呢?1. 指定位置的next 2.新元素的next 3. 如果指定位置是队尾指针,则还要修改队列头结构体中的last指针。


#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)
     对照代码,首先代码行2实现了两个功能:完成了场景分析时的修改2;完成了对指定位置是否是队尾指针的判断。如果指定位置的next为NULL,则是队尾指针,反之不是。所以,代码行3对应了我们的修改3。最后,代码行4则是命中了我们的修改1,修改指定位置的next,让它指向新增元素。多简单。


    最后,我们学习下简单队列的最后一个方法,也是比不可少的方法,元素的删除。之前我们在看到队列实体的时候分析了下简单队列的删除,只能是删除队列头部。因为缺少前驱指针,所以只能正向的删除,而不能逆向。现在,我们来继续之前的场景分析。有哪些指针要修改的?1.队头结构体中的first指针 2.如果删除的是队列的最后一个元素,则还要修改队头结构中的last指针。看看实现是否有我们猜测的这么简单。


#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对应的是我们猜测的修改1,并且也附带地实现了判断删除的是否是队列的最后一个元素。而代码行3,则对应了我们的修改2。如果删除的是最后一个元素,则队列头中的last指针,将再次指向队列头中的first指针。所以,只有一个后驱的节点删除是很简单的,正如单向链表中的删除一样,只有一行代码,而简单队列因为还要修改队头中的last指针,所以多了一行。


    简单队列的代码认识过程就到这里了,码如其名,简单队列,很简单。下一节我们学习尾队列



评论

ed meds online without doctor prescription 说:

D http://cialisles.com/ http://cialisles.com/ - extremely medicamento llamado cialis http://cialisles.com also cialis online pharmacy

Jamal 说:

Ну все любят одиссеи и потом мистику, да кто ж мы без участия сего итого. Вот именно благодаря чему и конечно целиком в 2019м годике тебе точно можно посмотреть мини-сериал ведьмак на https://xn--80adgd1ak5i.com/. Посмотреть в лучшем качестве эту кинокартину дополнительно на пиратском сайте в режиме онлайн.

发表评论