libuv源码分析之queue

libuv的queue实现得很博大精深。严重考验了c指针的理解。今天就分享一下他的实现。首先从一个typedef开始

typedef void *QUEUE[2];

这个是c语言中定义类型别名的一种方式。比如我们定义一个变量

QUEUE q

就相当于

void *q[2];

即一个数组，他每个元素是void型的指针。

下面我们接着分析四个举足轻重的宏定义，理解他们就相当于理解了libuv的队列。在分析之前，我们先来回顾一下数组指针和二维数组的知识。

int a[2];
// 数组指针
int (*p)[2] = a;
// *(*(p+0)+1)取元素的值

二维数组

int a[2][2];

我们知道二维数组在内存中的布局是一维。

但是为了方便理解我们画成二维的。

1. &a代表二维数组的首地址。类型是int (*)[2][2]，他是一个指针，他指向的元素是一个二维数组。假设int是四个字节。数组首地址是0，那么&a + 1等于16.
2. a代表第一行的首地址，类型是int (*)[2]，他是一个指针，指向的元素是一个一维数组。a+1等于8。
3. a[0]也是第一行的首地址，类型是int *。
4. &a[0]也是第一行的首地址，类型是int (*)[2];
5. 如果int (p) = &a[0]，那么我们想取数组某个值的时候，可以使用((p+i) + j)的方式。(p+i)即把范围固定到第一行（这时候的指针类型是init ）,(*(p+i) + j)即在第一行的范围内定位到某一列，然后通过解引用取得内存的值。

下面开始分析libuv的具体实现

1 QUEUE_NEXT

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

QUEUE_NEXT看起来是获取当前节点的next字段的地址。但是他的实现非常巧妙。我们逐步分析这个宏定义。首先我们先看一下QUEUE_NEXT是怎么使用的。

 void *p[2][2];
 QUEUE* q = &p[0]; // void *(*q)[2] = &p[0];
 QUEUE_NEXT(q);

我们看到QUEUE_NEXT的参数是一个指针，他指向一个大小为2的数组，数组里的每个元素是void 。内存布局如下。

因为libuv的数组只有两个元素。相当于p[2][2]变成了*p[2][1]。所以上面的代码简化为。

 void *p[2];
 QUEUE* q = &p; // void *(*q)[2] = &p;
 QUEUE_NEXT(q);

根据上面的代码我们逐步展开宏定义。

1. q指向整个数组p的首地址，*(q)还指向数组第一行的首地址（这时候指针类型为void *，见上面二维数组的分析5）。
2. (*(q))[0]即把指针定位到第一行第一列的内存地址（这时候指针类型还是void *，见上面二维数组的分析5）。
3. &((*(q))[0])把2中的结果（即void *）转成二级指针（void **），然后强制转换类型(QUEUE **) 。为什么需要强制转成等于QUEUE **呢？因为需要保持类型。转成QUEUE **后（即void * (**)[2]）。说明他是一个二级指针，他指向一个指针数组，每个元素指向一个大小为2的数组。这个大小为2的数组就是下一个节点的地址。

在libuv中如下

1. *(QUEUE *) &(((q))[0])解引用取得q下一个节点的地址（作为右值），或者修改当前节点的next域内存里的值（作为左值）,类型是void (*)[2]。

2 QUEUE_PREV

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

prev的宏和next是类似的，区别是prev得到的是当前节点的上一个节点的地址。不再分析。

3 QUEUE_PREV_NEXT、QUEUE_NEXT_PREV

#define QUEUE_PREV_NEXT(q)  (QUEUE_NEXT(QUEUE_PREV(q))
#define QUEUE_NEXT_PREV(q)  (QUEUE_PREV(QUEUE_NEXT(q))

这两个宏就是取当前节点的前一个节点的下一个节点和取当前节点的后一个节点的前一个节点。那不就是自己吗？这就是libuv队列的亮点了。下面我们看一下这些宏的使用。

1 删除节点QUEUE_REMOVE

#define QUEUE_REMOVE(q)                                                       \
  do {                                                                        \
    QUEUE_PREV_NEXT(q) = QUEUE_NEXT(q);                                       \
    QUEUE_NEXT_PREV(q) = QUEUE_PREV(q);                                       \
  }                                                                           \
  while (0)

在这里插入图片描述 1 QUEUE_NEXT(q); 拿到q下一个节点的地址，即p 2 QUEUE_PREV_NEXT(q)分为两步，第一步拿到q前一个节点的地址。即o。然后再执行QUEUE_NEXT(o),分析之前我们先看一下关于指针变量作为左值和右值的问题。

int zym = 9297;
int *cyb = &zym;
int hello = *cyb; // hello等于9297
int *cyb = 1101;

我们看到一个指针变量，如果他在右边，对他解引用（p）的时候，得到的值是他指向内存里的值。而如果他在左边的时候，p就是修改他自己内存里的值。我们回顾对QUEUE_NEXT宏的分析。他返回的是一个指针void (*)[2]。所以 QUEUE_PREV_NEXT(q) = QUEUE_NEXT(q); 的效果其实是修改q的前置节点（o）的next指针的内存。让他指向q的下一个节点（p），就这样完成了q的删除。

2 头插法插入队列QUEUE_INSERT_TAIL

// q插入h，h是头节点
#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)

在这里插入图片描述 还有很多操作队列的方式，但是主要理解了四个宏的意义，就很容易理解了这些操作。