Nginx数据结构之ngx_hash_t

Nginx数据结构之ngx_hash_t

hash结构在php、redis中均有用到,现在来看看Nginx中的hash是如何用的。

基础

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//hash 散列表中元素的结构,采用键值及其所对应的值<key, value>
typedef struct {
void *value; // 指向用户自定义的数组
u_short len; // 键值key的长度
u_char name[1]; // 键值key的第一个字符,数组名name表示指向键值key首地址
} ngx_hash_elt_t;

//基本hash散列表结构
typedef struct {
ngx_hash_elt_t **buckets; // 指向hash散列表第一个存储元素的桶
ngx_uint_t size; // hash散列表的桶个数
} ngx_hash_t;

//添加元素的hash元素结构
typedef struct {
ngx_str_t key; // 元素关键字
ngx_uint_t key_hash; // 元素关键字计算出的hash值
void *value; // 指向关键字key对应的值,组成hash表元素:<key, value>
} ngx_hash_key_t;

//初始hash结构
typedef struct {
ngx_hash_t *hash; // 指向待初始化的基本hash结构
ngx_hash_key_pt key; // hash函数指针

ngx_uint_t max_size; // hash表中桶bucket的最大个数
ngx_uint_t bucket_size; // 每个桶bucket的存储空间

char *name; // hash结构的名称
ngx_pool_t *pool; // 分配hash结构的内存池
ngx_pool_t *temp_pool; // 分配临时数据空间的内存池,仅在初始化hash表前,用于分配一些临时数组
} ngx_hash_init_t;

图解



好玩的基础函数

ngx_hash

1
2
// key * 31 + c字符串对应ASCII数值
#define ngx_hash(key, c) ((ngx_uint_t) key * 31 + c)

ngx_hash_key

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//计算字符串对应的hash值
ngx_uint_t
ngx_hash_key(u_char *data, size_t len)
{
ngx_uint_t i, key;

key = 0;

for (i = 0; i < len; i++) {
key = ngx_hash(key, data[i]); //((ngx_uint_t) key * 31 + c) 得出的值乘31,在加上当前字符对应ASCII
}

return key;
}

ngx_hash_key_lc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//将字符转化为小写,再去计算对应的hash值
ngx_uint_t
ngx_hash_key_lc(u_char *data, size_t len)
{
ngx_uint_t i, key;

key = 0;

for (i = 0; i < len; i++) {
key = ngx_hash(key, ngx_tolower(data[i])); //((ngx_uint_t) key * 31 + c) 得出的值乘31,在加上当前字符对应ASCII
}

return key;
}

ngx_hash_strlow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 把原始关键字符串的前n个字符转换为小写字母在计算hash值
* 只计算前n个字符的hash值
*/
ngx_uint_t
ngx_hash_strlow(u_char *dst, u_char *src, size_t n)
{
ngx_uint_t key;

key = 0;

while (n--) { //把src字符串的前n个字符转换为小写字母
*dst = ngx_tolower(*src);
key = ngx_hash(key, *dst); // 计算所转换的小写字母的hash值
dst++;
src++;
}

return key; //返回整型的hash值
}

ngx_tolower

1
2
3
4
5
6
7
8
9
10
/*
* 字符范围 十进制表示 二进制表示
* A-Z 65-90 0100 0001 - 0101 1010
* a-z 97-122 0110 0001 - 0111 1010
* 由于0x20(2^6)该位在大写二进制中是0,小写二进制中是1
* 则利用 | 将大写改为小写
* 则利用 & ~0x20 将小写改为大写
*/
#define ngx_tolower(c) (u_char) ((c >= 'A' && c <= 'Z') ? (c | 0x20) : c)
#define ngx_toupper(c) (u_char) ((c >= 'a' && c <= 'z') ? (c & ~0x20) : c)

重要函数

ngx_hash_find 查找函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
* hash查找函数
*
* 假设要在hash中找到k是abc对应的值
* @param key是字符串abc计算hash之后的int值
* @param name是字符串abc
*/
void *
ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len)
{
ngx_uint_t i;
ngx_hash_elt_t *elt;

#if 0
ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "hf:\"%*s\"", len, name);
#endif

//根据key对hash->size求余 得出索引位置 进而获得buckets中的元素elt
elt = hash->buckets[key % hash->size];

if (elt == NULL) {
return NULL;
}

//索引位置有值
while (elt->value) {
//先判断长度是否相等 发现php源码中也有这样的比较
if (len != (size_t) elt->len) {
goto next;
}

//循环key的每个字符
// * 假设要在hash中找到k是abc对应的值
// * @param key是字符串abc计算hash之后的int值
// * @param name是字符串abc
for (i = 0; i < len; i++) {
if (name[i] != elt->name[i]) {
goto next;
}
}

return elt->value;

next:

//由于ngx解决hash冲突时用的开发地址法
//向后遍历元素
elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
sizeof(void *));
continue;
}

return NULL;
}

源码注解:https://github.com/gxpisme/read_nginx/commit/04d638f7da21ca6669efbf06ce1086c94e95c9ce

xpisme wechat
微信号