Nginx 源码学习-ngx的基本容器-ngx_hash

ngx_hash

ngx_hash.{c|h} 实现了nginx里面比较重要的一个hash结构， 这个在模块配置解析里经常被用到。该 hash 结构是只读的，即仅在初始创建时可以给出保存在其中的 key-val 对，其后就只能查询而不能进行增删改操作了。

下面是简单 hash 结构的内存布局：

虽然代码理解起来比较混乱，但是使用还是比较简单的，常用的有创建 hash 和在 hash 中进行查找两个操作，对于创建hash的操作,过程一般为：

1. 构造一个 ngx_hash_key_t 为成员的数组， 包含 key, value 和 使用key计算出的一个hash值
2. 构建一个 ngx_hash_init_t结构体的变量， 其中包含了ngx_hash_t 的成员， 为hash的结构体， 还包括一些其他初始设置，如bucket的大小，内存池等
3. 调用 ngx_hash_init 传入 ngx_hash_init_t 结构， ngx_hash_key_t 的数组，和数组的长度， 进行初始化，这样 ngx_hash_init_t的hash成员就是我们要的hash结构

查找的过程很简单

1. 计算 key 的hash值
2. 使用 ngx_hash_find 进行查找，需要同时传入 hash值和key ,返回的就是value的指针

需要注意的是，nginx 的 hash 在查找时使用的是分桶后线性查找法，因此当分桶数确定时查找效率同其中的总 key-val 对数量成反比。

下面是一些demo代码(可以从svn中找到)

#include <stdio.h>
#include "ngx_config.h"
#include "ngx_conf_file.h"
#include "nginx.h"
#include "ngx_core.h"
#include "ngx_string.h"
#include "ngx_palloc.h"
#include "ngx_array.h"
#include "ngx_hash.h"
volatile ngx_cycle_t  *ngx_cycle;
void ngx_log_error_core(ngx_uint_t level, ngx_log_t *log, ngx_err_t err, const char *fmt, ...) { }


static ngx_str_t names[] = {ngx_string("rainx"),
                            ngx_string("xiaozhe"),
                            ngx_string("zhoujian")};
static char* descs[] = {"rainx's id is 1","xiaozhe's id is 2","zhoujian's id is 3"};

// hash table的一些基本操作
int main()
{
    ngx_uint_t          k; //, p, h;
    ngx_pool_t*         pool;
    ngx_hash_init_t     hash_init;
    ngx_hash_t*         hash;
    ngx_array_t*        elements;
    ngx_hash_key_t*     arr_node;
    char*               find;
    int                 i;

    ngx_cacheline_size = 32;
    // hash key cal start
    ngx_str_t str       = ngx_string("hello, world");
    k                   = ngx_hash_key_lc( str.data, str.len);
    pool                = ngx_create_pool(1024*10, NULL);
    printf("caculated key is %u \n", k);
    // hask key cal end
    //
    hash = (ngx_hash_t*) ngx_pcalloc(pool, sizeof(hash));
    hash_init.hash      = hash;                      // hash结构
    hash_init.key       = &ngx_hash_key_lc;          // hash算法函数
    hash_init.max_size  = 1024*10;                   // max_size
    hash_init.bucket_size = 64; // ngx_align(64, ngx_cacheline_size);
    hash_init.name      = "yahoo_guy_hash";          // 在log里会用到
    hash_init.pool           = pool;                 // 内存池
    hash_init.temp_pool      = NULL;

    // 创建数组

    elements = ngx_array_create(pool, 32, sizeof(ngx_hash_key_t));
    for(i = 0; i < 3; i++) {
        arr_node            = (ngx_hash_key_t*) ngx_array_push(elements);
        arr_node->key       = (names[i]);
        arr_node->key_hash  = ngx_hash_key_lc(arr_node->key.data, arr_node->key.len);
        arr_node->value     = (void*) descs[i];
        //
        printf("key: %s , key_hash: %u\n", arr_node->key.data, arr_node->key_hash);
    }

    if (ngx_hash_init(&hash_init, (ngx_hash_key_t*) elements->elts, elements->nelts)!=NGX_OK){
        return 1;
    }

    // 查找
    k    = ngx_hash_key_lc(names[0].data, names[0].len);
    printf("%s key is %d\n", names[0].data, k);
    find = (char*)
        ngx_hash_find(hash, k, (u_char*) names[0].data, names[0].len);

    if (find) {
        printf("get desc of rainx: %s\n", (char*) find);
    }

    ngx_array_destroy(elements);
    ngx_destroy_pool(pool);

    return 0;
}

按照前面的方法编译运行：
hash_op.c

运行结果

caculated key is 3654358412
key: rainx , key_hash: 108275556
key: xiaozhe , key_hash: 2225329080
key: zhoujian , key_hash: 3269715264
rainx key is 108275556
get desc of rainx: rainx's id is 1