您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识

xngx(西南工学院)

队列,节点,数据xngx(西南工学院)

发布时间：2016-12-08加入收藏来源：互联网点击：

很多朋友想了解关于xngx的一些资料信息，下面是小编整理的与xngx相关的内容分享给大家，一起来看看吧。

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

四、队列

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

定义如下：

// 文件名：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#

本文到此结束，希望对大家有所帮助呢。