Nginx源码分析(3)

自动草稿

前面分析了ngx_array_t数组,现在看一下ngx_queue队列和ngx_hash哈希表的实现。


ngx_queue队列

ngx_queue_t是一个双向链表,实现了一个队列的操作逻辑。但是它的结构只行指针的操作,因而在定义自己的节点时,需要自己定义数据结构和分配空间,并包含一个ngx_queue_t类型的成员。

这和Linux内核的数据结构很像。它们都将链表节点塞入数据结构。Linux内核的链表这样定义:

使用的时候

结构如图所示:

自动草稿

所以它用fox.list.next指向下一个节点,用fox.list.prev指向上一个节点。那我们如何从list_head找到fox的地址呢。内核提供了一个container_of()宏可以从链表指针找到父结构中包含的任何变量。

而在Nginx也是效仿采用一样的宏获取父结构地址。


##用法

它的API定义了初始化,插入,排序,找中位节点等一系列操作。

用法如下:


ngx_hash哈希表

ngx_hash表所用的hash算法为分桶后线性查找法,因而查找效率同key-value对成反比。对于常用的解决冲突的方法有线性探测、二次探测和开链法等。这里使用的是最常用的开链法(也是STL中使用的方法)。

哈希表整个结构如图所示:

自动草稿

哈希表用下列数据结构进行管理

在使用过程中,先会用ngx_hash_init_t实例化(类似于OOP思想,和内核驱动的用法相同)一个hash_init

然后对这个“对象”赋值。

第一行分配了ngx_hash_t大小的内存存储如下hash结构。

然后创建一个需要加到hash table中的数组。

最后将elements数组放到hash_init结构中,即将数组以hash table形式存储。

这就是整个hash结构的存储过程,查找相对简单,这里不再详述。

0

发表评论

邮箱地址不会被公开。