Libuv学习——队列
发布于 3 年前 作者 wanglei20116527 4719 次浏览 来自 分享

1568861665088-5963fe08-47a2-43cc-8ada-490dd1b6bcba.png

相信作为前端的我们对Node都比较熟悉,它以异步非阻塞IO模型闻名,特别擅长处理IO密集型的任务,这种优势是依靠Libuv实现的,想要更好的理解Node,学习Libuv是一个不错的途径。本文作为Libuv的第一篇文章,主要学习它的队列实现。为什么先从队列开始学习呢?原因有2点,一是它的代码少,容易学;二是作为基础结构,它被广泛的应用在Libuv中。

起航

学习的第一步,当然是获取源码写demo了。源码可以从github上获取,地址为libuv。队列的代码在源码中也很容易找到queue.h:

image.png

在写demo之前,先了解一下Libuv中队列的结构,它是通过带有头节点的双向循环列表实现的,具体结构如下图所示:

image.png

图中有几个图案需要解释一下:

image.png

上面的图案我们就叫做队列指针吧,可以认为它是一个具有2个元素的数组,第一个元素指向下一个队列元素,第二个元素指向上一个队列元素,它就是Libuv中队列的核心。

image.png

上面struct可以认为是JavaScript中的对象,他的一个属性就是队列指针,用来链接队列中的其他元素,当然struct可以包含任何其他属性。从这里我们可以看出Libuv的队列是一个通用实现,可以用在任何对象上。

demo

好了,了解了基本结构,让我们写个demo熟悉一下api吧。

image.png

demo的输出如下:

image.png

源码分析

初看queue.h,可以发现Libuv的队列是通过宏实现的,对于不了解宏的同学,可以参考https://www.runoob.com/cprogramming/c-preprocessors.html。上面demo用到了QUEUE_INIT、QUEUE_INSERT_TAIL、QUEUE_FOREACH、QUEUE_DATA,在介绍这几个宏之前,我们先看下面的代码。

image.png

上面代码定义了一个类型QUEUE——队列,它是一个包含两个元素的数组,数组中每个元素的类型为void *,可以用来放任何类型的指针。QUEUE_NEXT用来获取队列中下一个元素、QUEUE_PREV是用来获取队列中上一个元素,传参q的类型为QUEUE *,这两个宏很类似,所以只需要分析其中一个就好了,那就分析QUEUE_NEXT吧。

image.png

通过获取变量a的地址就可以到q,那么QUEUE_NEXT就可以转为图中形式,按理说QUEUE_NEXT直接写为(*(q))[0] 不就行了吗,为啥还需要对其取地址,然后转为QUEUE **后再取值呢?原因这里有两个,第一个原因是因为参数q的类型并不一定是QUEUE *,需要进行类型转换;第二个原因是将其变成左值,保证其能赋值,所谓的左值可以被认为是变量,能够将数据保存进去。

QUEUE_PREV_NEXT和QUEUE_NEXT_PREV两个宏的形式也差不多,所以分析其中一个就行了,就QUEUE_PREV_NEXT吧。从字面上理解,获取上一个元素的下一个元素,那不就是自身吗,为什么需要有这么奇怪的操作?这么理解其实是一个误导,潜意识下我们可能把这个宏用作取值了,这个宏其实是用来进行赋值的,对上一个元素的[0]进行赋值,这也呼应了上面QUEUE_NEXT、QUEUE_PREV写那么复杂的第二个原因——左值。QUEUE_PREV_NEXT本质上可以用下图表示。

image.png

好了,分析了上面的内容,就可以对demo中使用的几个宏进行分析了。

QUEUE_INIT

image.png

QUEUE_INIT可以用下图表示,将[0]、[1]上的元素都赋予自身。

image.png

这里有一点需要说明,为什么这个宏需要用do while包裹着?原因是这个宏有两条语句,需要将他们变成一个整体,不包裹可能会出现问题,比如下面代码中的for因为没有{}包裹,导致QUEUE_PREV就不在for循环体内了。

image.png

QUEUE_INSERT_TAIL

image.png

QUEUE_INSERT_TAIL就是简单的将元素q加入到队列h的尾部,具体过程如下图所示,上面部分表示将元素q插入到队列h中,下面表示插好的队列。其中红色的线表示新加的,灰色的线表示去掉的,数字表示顺序。

image.png

QUEUE_FOREACH

image.png

QUEUE_FOREACH通过for循环不断取队列h中的元素,将其赋给q。这里有意思的是,只有for循环的头部,却没有for循环的body,其实body是在使用的时候写,比如在demo中我们是这么写的:

image.png

QUEUE_DATA

可以看到在demo中我们用QUEUE_FOREACH遍历队列,可是我们拿到是只是队列的指针,那我们如何拿到work对象的内容呢?这个就得靠QUEUE_DATA了。

image.png

看起来好像很复杂的样子,先看下offsetof,它是用来获取属性filed在指定类型type的位置偏差(以字节来算),demo中的代码其实就是获取属性q在Work中的位置偏差。然后通过用q在内存中的地址减去该偏差就能得到Work对象在内存中的初始位置,通过类型转化就能到Work对象的指针,这样就能访问数据了,具体可以参考下图:

image.png

好了demo中用到的几个宏已经全部讲完了,队列其实还有一些其他的宏,这些宏都比较简单,这里也就不分析了,有兴趣的同学可以自己看下源码。

总结

作为前端的我们,可能对于c语言不熟悉,特别是内存管理和宏这块,如果能看完,真的是很不容易。本文是libuv学习的第一篇,接下来我会定期写一些关于Libuv的其他文章,比如目前真正写libuv中线程相关的内容,如果有兴趣的话,欢迎关注我们。

image.png

3 回复

看不到图片

@pzzcn 非常感谢提醒,已恢复

这其实就是linux内核list.h的变体,libuv主要考虑到版权问题,重写了。

回到顶部