【Nginx 源码学习】推荐：Hash表
文章目录
nginx 哈希结构的特色
Nginx的hash模块主要有如下几个特点：
1、静态只读。当初始化生成hash表结构后，是不能动态修改这个hash表结构的内容。
2、将内存利用最大化。Nginx的hash表，将内存利用率发挥到了极致。
3、查询速度快。Nginx的hash表做了内存对齐等优化。
4、主要解析配置数据。
数据设计图
数据结构
hash表的元素结构：
typedef struct {
void *value; /* 指向value的指针 */
u_short len; /* key的长度 */
u_char name[1]; /* 指向key的第一个地址，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_hash_t *hash; /* 指向hash数组结构 */
ngx_hash_key_pt key; /* 计算key散列的方法 */
ngx_uint_t max_size; /* 最大多少个 */
ngx_uint_t bucket_size; /* 桶的存储空间大小 */
char *name; /* hash表名称 */
ngx_pool_t *pool; /* 内存池 */
ngx_pool_t *temp_pool; /* 临时内存池*/
} ngx_hash_init_t;
1、Nginx的hash表主要存放在ngx_hash_t数据结构上。ngx_hash_t主要存放桶的指针值和桶的个数。
2、Nginx的hash表中桶的个数会在初始化的时候进行“探测”，决定hash表的桶的个数以及元素个数和大小，所有元素都会被分配到一个大的连续的内存块上。
3、每个bucket的长度会根据元素个数的实际长度决定，并且每个bucket之间通过NULL指针进行分割。NULL指针会在查找元素的时候用到。
4、每个桶都保存了桶的第一个元素ngx_hash_elt_t的指针值。
5、ngx_hash_elt_t存储每个元素的数据结构，并且key的长度是非定长的。
初始化哈希表
好长。。。
ngx_int_t ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,
ngx_uint_t nelts)
{
u_char *elts;
size_t len;
u_short *test;
ngx_uint_t i, n, key, size, start, bucket_size;
ngx_hash_elt_t *elt, **buckets;
/*
* 先检查每个元素是否会超过bucket_size的限制
* 如果超过限制，则说明需要重新处理
*/
for (n = 0; n < nelts; n++) {
if (hinit->bucket_size
< NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *)) {
ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
"could not build the %s, you should "
"increase %s_bucket_size: %i", hinit->name,
hinit->name, hinit->bucket_size);
return NGX_ERROR;
}
}
/*
* test是用来做探测用的，探测的目标是在当前bucket的数量下，冲突发生的是否频繁。
* 过于频繁则需要调整桶的个数。
* 检查是否频繁的标准是：判断元素总长度和bucket桶的容量bucket_size做比较
*/
test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log);
if (test == NULL) {
return NGX_ERROR;
}
/*
* 每个桶的元素实际所能容纳的空间大小
* 需要减去尾部的NULL指针结尾符号
*/
bucket_size = hinit->bucket_size - sizeof(void *);
//计算开始探测位置
start = nelts / (bucket_size / (2 * sizeof(void *)));
start = start ? start : 1;
if (hinit->max_size > 10000 && nelts && hinit->max_size / nelts < 100) {
start = hinit->max_size - 1000;
}
/*
* 探测会遍历所有的元素，并且计算落到同一个bucket上元素长度的总和和bucket_size比较
* 如果超过了bucket_size，则说明需要调整
* 最终会探测出比较合适的桶的个数
*/
for (size = start; size < hinit->max_size; size++) {
ngx_memzero(test, size * sizeof(u_short));
for (n = 0; n < nelts; n++) {
if (names[n].key.data == NULL) {
continue;
}
key = names[n].key_hash % size;
test[key] = (u_short)(test[key] + NGX_HASH_ELT_SIZE(&names[n]));
#if 0
ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
"%ui: %ui %ui "%V"",
size, key, test[key], &names[n].key);
#endif
/* 比较bucket_size和落到该bucket上的元素长度总和*/
if (test[key] > (u_short) bucket_size) {
goto next;
}
}
goto found;
next:
continue;
}
ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
"could not build the %s, you should increase "
"either %s_max_size: %i or %s_bucket_size: %i", hinit->name,
hinit->name, hinit->max_size, hinit->name, hinit->bucket_size);
ngx_free(test);
return NGX_ERROR;
/**
* 探测成功，则size为bucket桶的个数
*/
found:
/**
* 为了确定bucket的实际长度，初始化每个桶的长度计数器，初始值为一个NULL空指针长度
*/
for (i = 0; i < size; i++) {
test[i] = sizeof(void *);
}
/**
* 通过遍历，计算每个桶的大小。并且将每个桶的大小存储在test[n]数组上
*/
for (n = 0; n < nelts; n++) {
if (names[n].key.data == NULL) {
continue;
}
key = names[n].key_hash % size;
test[key] = (u_short)(test[key] + NGX_HASH_ELT_SIZE(&names[n]));
}
len = 0;
/**
* 获取所有元素需要分配的内存的总大小
*/
for (i = 0; i < size; i++) {
if (test[i] == sizeof(void *)) {
continue;
}
/* 总内存大小，需要通过内存对齐函数 */
test[i] = (u_short)(ngx_align(test[i], ngx_cacheline_size));
len += test[i];
}
/**
* 分配一块内存空间，存储：ngx_hash_t *hash和ngx_hash_elt_t *
* ngx_hash_elt_t用于存储桶。指针指向元素地址
*/
if (hinit->hash == NULL) {
hinit->hash = ngx_pcalloc(hinit->pool,
sizeof(ngx_hash_wildcard_t) + size * sizeof(ngx_hash_elt_t *));
if (hinit->hash == NULL) {
ngx_free(test);
return NGX_ERROR;
}
buckets = (ngx_hash_elt_t **) ((u_char *) hinit->hash
+ sizeof(ngx_hash_wildcard_t));
} else {
buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));
if (buckets == NULL) {
ngx_free(test);
return NGX_ERROR;
}
}
/**
* 分配一个桶，用于存储所有元素数据
*/
elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size);
if (elts == NULL) {
ngx_free(test);
return NGX_ERROR;
}
elts = ngx_align_ptr(elts, ngx_cacheline_size); //内存对齐
/**
* 将elts元素的内存，分割到buckets桶上
*/
for (i = 0; i < size; i++) {
if (test[i] == sizeof(void *)) {
continue;
}
buckets[i] = (ngx_hash_elt_t *) elts;
elts += test[i];
}
/**
* 将test清空，利用test于元素填充计数器
*/
for (i = 0; i < size; i++) {
test[i] = 0;
}
/**
* 往bucket的元素位上填充数据
*/
for (n = 0; n < nelts; n++) {
if (names[n].key.data == NULL) {
continue;
}
/* 计算在哪个桶上 */
key = names[n].key_hash % size;
elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]);
elt->value = names[n].value;
elt->len = (u_short) names[n].key.len;
/* 拷贝key数据,并且小写 */
ngx_strlow(elt->name, names[n].key.data, names[n].key.len);
/* test计数器计算新元素需要存放的位置 */
test[key] = (u_short)(test[key] + NGX_HASH_ELT_SIZE(&names[n]));
}
/**
* 设置bucket桶上最后一个元素设置为value为NULL
*/
for (i = 0; i < size; i++) {
if (buckets[i] == NULL) {
continue;
}
/*
* test[i] 其实是bucket的元素块的结束位置
* 由于前面bucket的处理中多留出了一个指针的空间，而此时的test[i]是bucket中实际数据的共长度，
* 所以bucket[i] + test[i]正好指向了末尾null指针所在的位置。处理的时候，把它当成一个ngx_hash_elt_t结构看，
* 在该结构中的第一个元素，正好是一个void指针，我们只处理它，别的都不去碰，所以没有越界的问题。
*/
elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);
elt->value = NULL;
}
ngx_free(test);
hinit->hash->buckets = buckets;
hinit->hash->size = size;
return NGX_OK;
}
查找一个元素
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
/* 获取对应的桶 */
elt = hash->buckets[key % hash->size];
if (elt == NULL) {
return NULL;
}
/* 在桶的链表上，查找具体的值;elt元素最后一个elt->value==NULL */
while (elt->value) {
if (len != (size_t) elt->len) {
goto next;
}
for (i = 0; i < len; i++) {
if (name[i] != elt->name[i]) {
goto next;
}
}
return elt->value;
next:
/* 因为在内存池上申请内存，并且是自己处理整块内存，为了CPU读取速度更快，进行了内存对齐 */
elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
sizeof(void *));
continue;
}
return NULL;
}
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
二维码