libevent中的数据结构之尾队列


尾队列,在libevent中也是个应用很高的数据结构。在核心结构event中就有使用到。现在我们来学习下这个数据结构。
    首先,我们来看下尾队列有哪些结构体。

结构体定义

尾队列头

/*
 * 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 */ \
}
我们发现,尾队列的队列头结构,同上一节学习的简单队列头定义相同。在这里就不多做介绍了。只是强调一点,尾队列的tqh_last指针,指向的是队列最后一个元素的next指针。

尾队列实体

#define TAILQ_ENTRY(type) \
struct { \
struct type *tqe_next; /* next element */ \
struct type **tqe_prev; /* address of previous next element */ \
}
     这个实体,就与简单队列中的实体不同了。它多了前驱指针。这个实体与链表中的实体结果相同,估计尾队列的接口也会与链表的接口相似。因为有了尾指针,我们在介绍简单队列时说的一些没有的接口也就有可能了。比如在指定位置前插入、在指定位置删除、逆向遍历等。那么,我们就来看下尾队列提供了哪些接口。

API接口

//获取尾队列的第一个实体
#define TAILQ_FIRST(head) 
//获取尾队列的结束元素
#define TAILQ_END(head)
//获取指定元素的下一个元素
#define TAILQ_NEXT(elm, field)
//获取队列的最后一个元素
#define TAILQ_LAST(head, headname)
//获取元素的前一个元素
#define TAILQ_PREV(elm, headname, field) 
//判断尾队列是否为空
#define TAILQ_EMPTY(head)
//正向遍历尾队列
#define TAILQ_FOREACH(var, head, field)
//反向遍历尾队列
#define TAILQ_FOREACH_REVERSE(var, head, headname, field)
//尾队列头的初始化
#define TAILQ_INIT(head)
//在尾队列头部之后插入
#define TAILQ_INSERT_HEAD(head, elm, field)
//在尾队列尾部之后插入
#define TAILQ_INSERT_TAIL(head, elm, field)
//在指定位置之后插入
#define TAILQ_INSERT_AFTER(head, listelm, elm, field) 
//在指定位置之前插入
#define TAILQ_INSERT_BEFORE(listelm, elm, field)
//删除指定位置的元素
#define TAILQ_REMOVE(head, elm, field)
//尾队列的元素替换
#define TAILQ_REPLACE(head, elm, elm2, field)
看到这接口,第一反应我是有点迷茫的。第一次看见headname,它是做什么用的,为什么逆向遍历里面需要它。先看下实现,最后我们再来反推这个过程。headname是head这个变量的结构体类型名称。

接口实现

首先看下几个简单的实现吧。
/*
 * 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))

/*
 * Tail queue functions.
 */
#define TAILQ_INIT(head) do { \
(head)->tqh_first = NULL; \
(head)->tqh_last = &(head)->tqh_first; \
} while (0)

照例,逆向遍历的暂时还没看懂,后续再解释。

还是先来看看尾队列的队头插入吧。简单的进行下思考,尾队列的这种数据结构,在队头插入会有哪些指针变化呢?
1. 队列头的first指针 2.如果队列不空,则队列的第一个实体的prev指针 3.如果队列为空,则队列头的last指针 4.新增元素的prev 5.新增元素的next。现在让我们来看下代码吧。
#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)
首先,代码行2照例是实现了两个功能的,一个是实现了我们的修改5,将队列头的指向赋值给新元素的next,并且判断了队列是否为空。而代码行3,则实现了我们的修改2,队列的原来的第一个实体的prev指针,指向了新增元素的next指针。反之,代码行6,则对应我们的修改3,队列为空的时候,要修改队列头的last指针,让它指向新增元素的next指针。代码行7对应了修改1,代码行8对应了修改4,新增元素的prev指向队列头元素的first指针,因为是在队列头之后插入。
    队列头插入的代码都熟悉了,我们再看下尾队列空时会是个什么样的状态。如图1

                                                

                                                                图1-空队列

可见和简单队列的空队列是一模一样。接下来,我们再看下插入第一个元素是什么情景。见图2.
    

                                                                                图2-空队列的时候插入第一个元素

从图中可以看出,队列头的first和last的指向都发生了变化,导致原来的两个指针的指向都被标识为无效,打上了红叉。而新元素的prev指向了队列头的first指针,而新元素的next指针则是指向了旧队列头first指针指向的地方。
    看完了在队头插入,我们再来看下在队尾插入,两者之间有何区别呢?如果是空队列,则两者之间并无区别,指针的指向变化与图2是相同的。但是如果是非空队列,则存在不同。那么,队尾插入,会有哪些指针发生变化呢?1. 队尾指针的last指针 2.如果队列非空,则旧的队尾指针的next指针 3.如果队列为空,则队列头结构中的first指针 4.新元素的prev指针 5.新元素的next指针。分析了指针变化的5种可能之后,我们再来看下代码的实现。
#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)
     其中,代码行2对应了上面的修改5,代码行3对应了修改4,新元素的prev指针指向旧的队尾元素,如果队尾元素不存在,则指向的是队列头的first指针。而这两个如果,都通过代码行3就搞定了。代码行4对应的是修改2和3。为什么说是2和3呢,因为2和3是两种情况,分别是队列空与不空。队列空的时候,修改的是队列头结构中的first指针,队列非空的时候,修改的则是旧的队尾元素的next指针。这里与代码行3实现的效果相同。代码行5,则对应于修改1,修改队尾指针的last指针,让它指向新增元素的next指针。
    前面说过,队列为空时的队尾插入的结果同图2,所以这里就不做这种情况的说明了,现在我们来看下队列非空时,队尾插入的情况。                                                     

                                                          图3-非空队列的队尾插入

从图中可以看出,队尾插入的两个无效指针,被打上红叉的,是因为队列头部的last指针指向发生了变化,以及旧的队尾指针的next指向发生了变化、而新元素的next指向了旧的队尾指针的next指向,而prev则是指向了旧的队尾指针的next指针。
    学完了在队尾插入,我们再来看看在指定位置之后的插入。假定我们要在指定位置之后插入,那么会有哪些指针需要变化呢?1. 指定位置的next指针 2.如果指定位置是队尾元素,那么队列头部的last指针要修改 3.如果指定位置不是队尾元素,那么指定位置的下一个节点的prev指针要修改  4.新元素的prev指针 5.新元素的next指针。看完这几个插入,好像每次涉及到的指针修改都不超过5个,其中还有两个是新元素的指针变化,也就是说,旧的节点的指针变化都在三个之内。现在我们看下代码实现。
#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)
     分析代码,代码行2对应的是修改5,而且也附带了对指定元素是否是队尾元素的判断。其中,代码行3是非队尾元素的情况,代码行6,则指定位置是队尾元素时的情况。所以代码行3对应了我们的修改3,修改指定位置的下一个节点的prev指针,指向我们的新元素的next指针。而代码行6则对应了我们的修改2,指向的是队尾元素时,修改队列头结构体中的last指针,指向新增元素的next指针。而代码行7对应我们的修改1,指定位置的next指针指向新增元素,而代码行8对应我们的修改4,新元素的prev指针指向指定元素的next指针。
    现在插入只剩下最后一种情况了:在指定位置之前插入。之前与之后的插入区别不是很大,受影响的其实是队列头的first还是last,因为在之前插入的时候,有可能就在第一个实体之前插入,那么队列头部中first指向就要修改了。但是在之前插入的话,last的指针是肯定不用改的。所以我们来分析一下在之前插入的话,有哪些指针会受到影响,需要发生变化。1. 指定位置的prev指针 2.如果指定位置不是队列第一个实体,则指定位置的前一个节点的next指针需要修改 3.如果指定位置的队列的第一个实体,那么队列头的first指针要修改。4.新元素的prev指针 5.新元素的next指针。分析完了之后,我们来看下代码是怎么样了。
#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)
     同在队尾插入的情况相同,如果涉及到修改队列头元素的first指针,还是前一个节点的next指针时,其实只需要一行代码。也就是说,我们猜测的修改2和3,其实对应的都是代码行4,这是因为指定位置的prev指针,会根据两种情况,分别指向不同的位置,而代码行4,对prev的解引用然后修改,就是修改了next指针或者first指针。那么还有修改1/4/5. 代码行2对应了修改4,新元素的prev指针完美的从指定位置的prev指针中接过。代码行3对应了修改5,新元素的next指针指向指定位置,代码行5.则对应了修改1,即修改指定位置的prev指针,让它指向新元素的next指针。
    现在插入已经介绍完了,我们来看下删除吧。拥有前驱指针的节点删除,是支持任意位置的删除的。所以我们来看下在指定位置删除时,哪些指针有可能发生变化。1. 如果删除的不是第一个实体,则删除的元素的前一个节点的next指针要发生变化 2.如果删除的是第一个实体,则队列头的first指针要变化 3. 如果删除的是队尾元素,那么队列头的last指针要变化 4.如果删除的不是队尾元素,则删除元素的下一个节点的prev指针要变化,

    其实可以看到,变化的指针就是删除节点的前节点的next指针,和后一个节点的prev指针。我们来看下代码。

#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)
代码行7再次印证了之前的说法,凡是涉及到first指针还是前一个节点的next指针变化的时候,都只用一行代码搞定。所以,代码行7,对应了我们猜测的修改1和2,让first指针或者next指针指向被删节点的下一个节点. 而代码行2,判断删除的元素是否是队尾元素,如果非空,则不是队尾元素,反之是。所以代码行3对应的是修改4,删除的元素不是队尾元素,那么修改删除元素的下一个节点的prev指针,把删除元素的prev值赋值给下一个节点的prev指针。而代码行6,对应的则是修改3,删除的是队尾元素,那么修改队列头的last指针,同样地,把删除元素的prev值,赋值给队列头的prev指针。
    我们看下删除队尾元素时的指针变化图。见图4.



                                                                   图4-删除队尾元素
从图中可以看到,被删除节点的出入指针都被标为无效,打上了红叉。被删元素的前一个节点的next指向了删除节点的next,即NULL,而队列头节点的last指针,则是指向了前一个节点的next指针。因为被删除的不是第一个实体,所以队列头的first指针未发生变化,
    最后,我们看下尾队列的替换。正如我们在讲链表的替换时候分析的一样,新节点要替换旧节点,首先要转移旧节点的next与prev,这个是与旧节点自身相关的修改。还有如下内容的修改:1。替换节点如果是队尾元素,则队列头结构中的last指针要修改 2.替换节点如果不是队尾元素,则替换节点的下一个节点的prev指针要修改; 3。如果替换节点是第一个实体,那么队列头的first指针要修改 4.如果替换节点的不是第一个实体,那么替换节点的前一个节点的next指针要修改。我们来看下实现。
#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,是转移旧节点的next指针,并且判断旧节点是否有下一个节点。而代码行3,则对应了修改2,替换节点不是队尾元素,则修改替换节点的下一个节点的prev指针,指向新节点的next指针。代码行6,对应了修改1,替换节点是队尾元素,修改队列头的last指针,指向新节点的next指针。代码行7是转移旧节点的prev指针。代码行8,则对应于修改3和4,正如前面所说,当存在判断是否第一个实体时,一行代码就足够。
    我们还有前面留下的逆序遍历的部分还没有解释。说起来,因为我是用C++,所以对C的部分不是很理解,特别是在强制转换上。刚开始,为了理解 TAILQ_LAST,我把代码中的宏编译展开给套进去,楞是没看明白。
#define TAILQ_LAST(head, headname) \
(*(((struct headname *)((head)->tqh_last))->tqh_last))

    首先,我们知道,headname是head的结构体名称,那么其实就是Head的结构,而我们知道,head->tqh->last的指针,是指向的entry,所以 ((struct headname *)((head)->tqh_last)) 这个强转看的我是莫名其妙。因为它们不具备类之间可以强转的关系。所以,我这是在照着C++的类的思维,去理解它这里的强转。但这显然是错的,直到我看了这篇博客。我才明白这里为什么可以强转。博客地址:https://blog.csdn.net/luotuo44/article/details/38374009。借用下博客的图。

下面是尾队列的头部与实体之间的指针映射关系。其中1和2是data数据。附上博客中的元素结构体类型
//队列中的元素结构体。它有一个值,并且有前向指针和后向指针
//通过前后像指针,把队列中的节点连接起来
struct queue_entry_t
{
    int value;
 
    struct
    {
        struct queue_entry_t *tqe_next;
        struct queue_entry_t **tqe_prev;
    }entry;

--------------------- 
作者:luotuo44 
来源:CSDN 
原文:https://blog.csdn.net/luotuo44/article/details/38374009 
版权声明:本文为博主原创文章,转载请附上博文链接!
    他的博客中,没有明显的说明为什么那个强制可以进行。而我在这里做下说明。
    首先,我们再分别看下链表头结构和实体结构。
#define TAILQ_HEAD(name, type) \
struct name { \
struct type *tqh_first; /* first element */ \
struct type **tqh_last; /* addr of last next element */ \
}

#define TAILQ_ENTRY(type) \
struct { \
struct type *tqe_next; /* next element */ \
struct type **tqe_prev; /* address of previous next element */ \
}
我们会发现,它们的结构体类型是一模一样的,都是type *,type **,哪怕它们的type类型不同,它们也是一样的类型,整体占用空间相同,且第一个成员占据的空间也相同。而也正是因为它们的总空间相同,且第一个成员占据的空间也相同,且成员个数都相同,第二个成员也都是指针的指针。所以,可以强转,并且强转后,可以使用强转后的成员,哪怕两个类型半毛钱关系都没有。我们现在来分析下这个宏的扩展、
//TAILQ_HEAD (evkeyvalq, evkeyval);
//宏扩展
struct evkeyvalq {				
	struct evkeyval *tqh_first;			
	struct evkeyval **tqh_last;			
}

struct evkeyval {
	//TAILQ_ENTRY(evkeyval) next;
struct {								
	struct evkeyval *tqe_next;	/* next element */			
	struct evkeyval **tqe_prev;	/* address of previous next element */	
} next;

	char *key;
	char *value;
};

//struct evkeyval *header = TAILQ_LAST(headers, evkeyvalq);
//宏扩展
struct evkeyval *header =  (*(((struct evkeyvalq *)((headers)->tqh_last))->tqh_last))
我们重点看下,(*(((struct evkeyvalq *)((headers)->tqh_last))->tqh_last))
从上面的代码,我们可以看出,((headers)->tqh_last)得到的类型还是结构体 next,指向的队尾元素的tqe_next指针;它的结构体类型与evkeyvalq相同,照着我们之前对强转的认知,此时,强转后的evkeyvalq->tqh-_last,实际上的还是next->tqe_prev,即队尾元素的tqe_prev指针指向的还是队尾元素自身。因为next->tqe->prev指向的是上一个节点的next指针。*(next->tqe_prev)获取了倒数第二个节点的tqe_next成员的值。它的值就是最后一个节点的地址。最后,将这个地址赋值给header,此时header指向队尾元素. 关于这两个宏的扩展具体的可以看我参考的博客链接。里面有具体的事例说明。
    记住,这里可以强转的关键在于两个结构体的构造相同。


评论

发表评论