定义如下：
// 文件名：ngx_queue.hstruct 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#
