昨天我们一起学习了 Nginx基本数据结构之字符串，数组，链表， 今天我们接着看 队列 和 散列hash。

四、队列

我们都知道队列是一种先进先出的数据结构。在Nginx里是用双向链表循环链表来实现的，是一种双向队列。

定义如下：

// 文件名：ngx_queue.h
struct ngx_queue_s {
    ngx_queue_t  *prev;
    ngx_queue_t  *next;
};

这里可以看到 只有前驱和后继指针，没有看到数据的Node节点。后面我们再具体看。

我们先来看一下队列的初始化和插入过程。

实现如下：

// 文件名：ngx_queue.h
#define ngx_queue_init(q)                                                     \
    (q)->prev = q;                                                            \
    (q)->next = q

我们可以看到初始化队列 把前驱和后继指针都指向了自己。这时候一个空队列就已经有了。

队列数据如图：

Nginx的队列相关操作方法还有：

// 判断是否为空
#define ngx_queue_empty(h)                                                    \
    (h == (h)->prev)

// 头插法
#define ngx_queue_insert_head(h, x)                                           \
    (x)->next = (h)->next;                                                    \
    (x)->next->prev = x;                                                      \
    (x)->prev = h;                                                            \
    (h)->next = x


#define ngx_queue_insert_after   ngx_queue_insert_head

// 尾插法
#define ngx_queue_insert_tail(h, x)                                           \
    (x)->prev = (h)->prev;                                                    \
    (x)->prev->next = x;                                                      \
    (x)->next = h;                                                            \
    (h)->prev = x

// 获取队列的头节点
#define ngx_queue_head(h)                                                     \
    (h)->next

// 获取队列的尾节点 因为队列是双向循环队列 所以指针的前一个节点就是最后一个节点。
#define ngx_queue_last(h)                                                     \
    (h)->prev

// 获取队列结构指针
#define ngx_queue_sentinel(h)                                                 \
    (h)

// 获取节点q 下一个节点
#define ngx_queue_next(q)                                                     \
    (q)->next

// 获取节点q 一个节点
#define ngx_queue_prev(q)                                                     \
    (q)->prev

// 删除节点
#define ngx_queue_remove(x)                                                   \
    (x)->next->prev = (x)->prev;                                              \
    (x)->prev->next = (x)->next;                                              \
    (x)->prev = NULL;                                                         \
    (x)->next = NULL

#define ngx_queue_remove(x)                                                   \
    (x)->next->prev = (x)->prev;                                              \
    (x)->prev->next = (x)->next

// 以数据q为界，将队列h拆分为h和n两个队列，其中拆分后数据q位于第二个队列中。
// 队列拆分实际上是以数据q作为第二个队列的第一个节点，
// 数据q的前一个节点作为前一个队列的最后一个节点。
#define ngx_queue_split(h, q, n)                                              \
    (n)->prev = (h)->prev;                                                    \
    (n)->prev->next = n;                                                      \
    (n)->next = q;                                                            \
    (h)->prev = (q)->prev;                                                    \
    (h)->prev->next = h;                                                      \
    (q)->prev = n;

// 合并队列,将队列n添加到队列h的尾部。
#define ngx_queue_add(h, n)                                                   \
    (h)->prev->next = (n)->next;                                              \
    (n)->next->prev = (h)->prev;                                              \
    (h)->prev = (n)->prev;                                                    \
    (h)->prev->next = h;

我们可以看到队列的操作并不复杂，这里我们主要说下头插法（尾插法也是类似的）

插入数据逻辑如图：

头插法主要分4步:

1）修改新插入节点x的next指针指向h节点的下一个节点；

2）修改x的下一个节点的prev指针指向x；

3）修改x的prev指针指向h节点；

4）修改头指针指向x。

假设原队列除头节点外有两个数据，插入一个节点的效果如上图所示:

其中实线代表修改指针指向，虚线表示断开指针指向。

五、散列(hash)

我们知道hash是一种查询速度非常快的的数据结构只有O(1)。

这是一种以空间换时间的数据结构。将key经过hash算法映射到value上。

那么只要经过hash算法后 就会出现冲突的情况。

而解决hash冲突一般会用拉链法或开放地址法。

像PHP的数组，Redis的hash就是用拉链法来解决的。

而Nginx是采用的开发地址法。当key的散列值出现冲突时，则向后遍历，查看散列值+1的位置是否有值存在，如果无值则会占用这个位置，如果有值则继续向后遍历。在查找数据时，如果遇到的散列值不是想查找的数据，则向后遍历，直到找到相应的数据。

数据结构如下：

typedef struct {
    void             *value;
    u_short           len;
    u_char            name[1];
} ngx_hash_elt_t;

字段说明：

value：指向散列value的值。

len：散列key的长度。

name：柔性数组，散列key的值。

而value对应的字段的结构：

typedef struct {
    ngx_hash_elt_t  **buckets;
    ngx_uint_t        size;
} ngx_hash_t;

字段说明：

buckets：桶数组，数组中每个数据的类型为ngx_hash_elt_t*，buckets指向当前桶的第一个散列数据。

size：散列桶的数量。

所有的散列数据连续存储在一个字节数组buckets中。当散列冲突时，一个散列位置需要存储多个散列数据，这时候如何处理呢？我们看ngx_hash_elt_t结构体，很容易知道数据的长度，所以多个散列数据在冲突位置按顺序存储即可。为了使用方便，每个桶的最后都有一个8字节的NULL。

数据在hash中的存储示例如图:

ngx_hash_init_t结构用于提供创建散列所需要的信息：

typedef struct {
    ngx_hash_t       *hash;
    ngx_hash_key_pt   key;
    ngx_uint_t        max_size;
    ngx_uint_t        bucket_size;
    char             *name;
    ngx_pool_t       *pool;
    ngx_pool_t       *temp_pool;
} ngx_hash_init_t;

参数说明如下:

hash：指向散列。

key：hash函数，它是一个函数指针。

max_size：散列表中桶的最大数量。

bucket_size：每个桶的最大字节大小。

name：散列的名称。

pool：散列所在的内存池。

temp_tool：构建散列时所用的临时内存池，创建散列完成时被回收。

这里需要注意的是Nginx的hash在初始化后，就不会再修改，只能用于查询操作。所以在创建的时候就要先计算好bucket的数量，每个桶的字节大小及每个桶存储哪些数据。

明天我们继续学习剩下的结构。

#读书##Nginx##编程##程序员##IT#