Libuv 源码解析 - QUEUE（双向循环队列）

Libuv 源码解析 - QUEUE（双向循环队列）

参考链接：

https://blog.csdn.net/AnitaSun/article/details/123968659

https://blog.csdn.net/yinanmo5569/article/details/82085461

简介

  Libuv中的高效双向循环队列结构是使用C语言构建，且所有方法均使用宏定义实现。Libuv中该结构使用指针数组构建而成，其中指针数组中只包含两个元素，类型均为void*类型，分别表示next、prev指针。我们联想双链表这类结构，不是应该还包含一个value类型吗？Libuv中QUEUE结构直接使用指针偏移来指向value。每一个节点尾部是一个QUEUE类型，通过向上偏移sizeof(节点类型) - sizeof(QUEUE)大小个字节来获得value。

元素类型

typedef void *QUEUE[2];//其中两个元素均为void*类型，[0]:next,[1]:prev
1

  务必注意，作为一个双向循环队列结构，其中next、prev指向的节点理应为QUEUE类型，虽然本质为void*类型，但是我们联想双链表，双向循环链表，其next、prev都是节点本身类型。

基本方法

#define QUEUE_NEXT(q)       (*(QUEUE **) &((*(q))[0]))      
#define QUEUE_PREV(q)       (*(QUEUE **) &((*(q))[1]))
1
2

  我们查阅Libuv源代码得知，其使用方式如下：

QUEUE queue;
QUEUE_NEXT(&queue);
1
2

指针数组学习链接：https://blog.csdn.net/qq135595696/article/details/118738261

  QUEUE_NEXT扩展为(*(QUEUE **) &((*(&queue))[0]))。在我们具备指针数组的原理的情况下，我们知道，扩展形式本质为(*queue)[0]。那么问题来了，为何Libuv将其扩展的如此复杂？最主要的两点原因是类型保持（上述元素类型有稍微提及）、成为左值。

  在具体解析QUEUE结构之前，这里描述一下什么是左值。左值必须占有实际的内存空间，同时可对其进行取地址操作。比如int a = 1，如果我们想将其变为其他类型的左值，如char类型，那么就是(char)a = 2；但是如果对一个变量进行强制类型转换，其实它并不是改变变量实际占用空间的类型，编译器会为其生成一个副本，但是这个副本是只是临时的，并不能对其进行取地址操作，即不是左值。那么如果要将其变成左值，我们能做的就是改变变量实际占用空间的类型，即对其地址进行操作，比如上述int a例子，我们先对a取地址，获取a的实际空间地址，&a，然后对该片内存进行强制类型转换(char*)(&a)，这时我们已经将a的实际空间地址的类型进行强制类型转换，而不是对一个副本进行操作，那么我们如果修改该片内存空间的值呢？我们对于一个普通的一级指针如何修改其指向的值我们在这里就如何操作，那么就是*(char*)(&a) = 2。

  我们知道QUEUE中每个元素就是void*类型，(*(&queue))[0]的原因不做过多叙述（只需理解什么为指针数组），我们要将void*转换为一个左值，如何做？那么就是 &(*(&queue))[0]，此时元素的类型为void**，但是我们需要让next、prev指向一个QUEUE*类型的值（这里我们无需在意QUEUE本质为什么类型，只需看作最基本的数据类型即可，它是一个自定义基础数据类型，不是指针，也不是引用等）。为什么是QUEUE*类型？联想以下双链表的next、prev是什么类型。那么这里我们先将其进行强转，为(QUEUE **) &(*(&queue))[0]，因为我们要修改的是其指向的值，也就是void**指向的值，其本身是一个指针的指针，即二级指针，指向的地址为一级指针的地址，这就是我们想要的，所以这里需要解引用，即*(QUEUE **) &(*(&queue))[0]。此时便是一个只接收QUEUE *类型节点的左值。

  从上述可以得知，Libuv这样做就是两点原因，一是类型保持，二是成为左值。

插入方法

#define QUEUE_HEAD(q)                                                         \
  (QUEUE_NEXT(q))

//h -> q -> p -> h，即q插入在h的后方。h是无意义的，只是头部标记，但是这种方式无法直接通过QUEUE_HEAD拿到head，需要遍历队列
#define QUEUE_INSERT_HEAD(h, q)                                               \
  do {                                                                        \
    QUEUE_NEXT(q) = QUEUE_NEXT(h);                                            \
    QUEUE_PREV(q) = (h);                                                      \
    QUEUE_NEXT_PREV(q) = (q);                                                 \
    QUEUE_NEXT(h) = (q);                                                      \
  }                                                                           \
  while (0)

// h -> p -> q -> h，即q是插入在h的前方，但由于是双向队列，所以实际上是插入在尾部的，QUEUE_HEAD方法可以直接拿到实际头节点
#define QUEUE_INSERT_TAIL(h, q)                                               \
  do {                                                                        \
    QUEUE_NEXT(q) = (h);                                                      \
    QUEUE_PREV(q) = QUEUE_PREV(h);                                            \
    QUEUE_PREV_NEXT(q) = (q);                                                 \
    QUEUE_PREV(h) = (q);                                                      \
  }                                                                           \
  while (0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22