Nginx源码研究（4）——hash结构ngx_hash_t

//hash结构
typedef struct {
    ngx_hash_elt_t  **buckets; //hash桶(有size个桶)
    ngx_uint_t        size;    //hash桶个数
} ngx_hash_t;


// <key,value> 结构，初始化时候使用
typedef struct {
    ngx_str_t         key;      //key，为nginx的字符串结构
    ngx_uint_t        key_hash; //由该key计算出的hash值(通过hash函数如ngx_hash_key_lc())
    void             *value;    //该key对应的值，组成一个键-值对<key,value>
} ngx_hash_key_t;

//hash元素结构
typedef struct {
    void             *value;    //value，即某个key对应的值，即<key,value>中的value
    u_short           len;      //name长度
    u_char            name[1];  //某个要hash的数据(在nginx中表现为字符串)，即<key,value>中的key
    // 这里数组长度为1，是一个小技巧。实现时，在具体分配ngx_hash_elt_t的大小时使用宏NGX_HASH_ELT_SIZE来确定(并且是内存对齐的)：
    // #define NGX_HASH_ELT_SIZE(name) (sizeof(void *) + ngx_align((name)->key.len + 2, sizeof(void *)))
} ngx_hash_elt_t;

//hash初始化结构，用来将其相关数据封装起来作为参数传递给ngx_hash_init()或ngx_hash_wildcard_init()函数
typedef struct {
    ngx_hash_t       *hash;         //指向待初始化的hash结构。
    ngx_hash_key_pt   key;          //hash函数指针

    // 散列表中槽的最大数目
    ngx_uint_t        max_size;     //bucket的最大个数

    // 散列表中一个槽的空间大小，它限制了每个散列表元素关键字的最大长度，通过NGX_HASH_ELT_SIZE(name)计算每个element的大小。
    // 如果这个bucket_size设置较大，那么他就能够容纳多个element，这样一个bucket里存放多个element，进而导致查找速度下降。
    // 为了更好的查找速度，请将bucket_size设置为所有element长度最大的那个。
    ngx_uint_t        bucket_size;

    // 散列表的名称
    char             *name;         //该hash结构的名字(仅在错误日志中使用)
    // 内存池，它分配散列表（最多3个，包括1个普通散列表，1个前置通配符散列表，1个后置通配符散列表）中的所有槽
    ngx_pool_t       *pool;         //该hash结构从pool指向的内存池中分配
    // 临时内存池，它仅存在于初始化散列表之前。它主要用于分配一些临时的动态数组，带通配符的元素在初始化时需要用到这些数组。
    ngx_pool_t       *temp_pool;    //分配临时数据空间的内存池
} ngx_hash_init_t;

// 第一个参数hinit是初始化的一些参数的一个集合。 names是初始化一个ngx_hash_t所需要的所有<key,value>对的一个数组，而nelts是该数组的个数。
// 备注：我倒是觉得可以直接使用一个ngx_array_t*作为参数呢？
//
//初始化步骤
//1. 遍历待初始化的ngx_hash_key_t数组, 保证占用空间最大的ngx_hash_elt_t元素可以装进bucket_size大小空间
//2. 预估一个可以装入所有元素的hash表长度start, 判断是否可以将所有元素装进这个size大小的hash表
//3. 装不下, 增加size, 如果size达到max_size仍然不能创建这个hash表, 则失败. 否则确定了要构建的hash表长度(buckets个数)
//4. found:处开始,, 计算所有元素占用总空间, 为hash表的各个bucket分配各自的空间
//5. 将ngx_hash_key_t数组元素分别放入对应的bucket中
//
//其中第2步中怎么计算初始的可能hash表的大小start?
//start = nelts / (bucket_size / (2 * sizeof(void *)));
//也即认为一个bucket最多放入的元素个数为bucket_size / (2 * sizeof(void *));
//64位机器上, sizeof(void *) 为8 Bytes,  sizeof(unsigned short)为2Bytes, sizeof(name)为1 Byte, sizeof(ngx_hash_elt_t)为16Bytes, 正好与2 * sizeof(void *)相等.
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;

    //检查names数组的每一个元素，判断桶的大小是否够存放key
    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;
        }
    }

    //分配 sizeof(u_short)*max_size 个字节的空间保存hash数据
    //(该内存分配操作不在nginx的内存池中进行，因为test只是临时的)
    test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log);
    if (test == NULL) {
        return NGX_ERROR;
    }

    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;
    }

    for (size = start; size < hinit->max_size; size++) {

        ngx_memzero(test, size * sizeof(u_short));
        //标记1：此块代码是检查bucket大小是否够分配hash数据
        for (n = 0; n < nelts; n++) {
            if (names[n].key.data == NULL) {
                continue;
            }

            //计算key和names中所有name长度，并保存在test[key]中
            key = names[n].key_hash % size; //若size=1，则key一直为0
            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

            //若超过了桶的大小，则到下一个桶重新计算
            if (test[key] > (u_short) bucket_size) {
                goto next;
            }
        }

        goto found;

    next:

        continue;
    }

    //若没有找到合适的bucket，退出
    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;

found: //找到合适的bucket

	//将test数组前size个元素初始化为sizeof(void *)
    for (i = 0; i < size; i++) {
        test[i] = sizeof(void *);
    }

    /** 标记2：与标记1代码基本相同，但此块代码是再次计算所有hash数据的总长度(标记1的检查已通过)
        但此处的test[i]已被初始化为sizeof(void *)，即相当于后续的计算再加上一个void指针的大小。
     */
    for (n = 0; n < nelts; n++) {
        if (names[n].key.data == NULL) {
            continue;
        }

        //计算key和names中所有name长度，并保存在test[key]中
        key = names[n].key_hash % size;//若size=1，则key一直为0
        test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
    }

    //计算hash数据的总长度
    len = 0;

    for (i = 0; i < size; i++) {
        if (test[i] == sizeof(void *)) {
        	//若test[i]仍为初始化的值为sizeof(void *)，即没有变化，则继续
            continue;
        }

        //对test[i]按ngx_cacheline_size对齐(32位平台，ngx_cacheline_size=32)
        test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size));

        len += test[i];
    }

    if (hinit->hash == NULL) {
    	//在内存池中分配hash头及buckets数组(size个ngx_hash_elt_t*结构)
        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_wildcard_t结构之后)
        buckets = (ngx_hash_elt_t **)
                      ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t));

    } else {
    	//在内存池中分配buckets数组(size个ngx_hash_elt_t*结构)
        buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));
        if (buckets == NULL) {
            ngx_free(test);
            return NGX_ERROR;
        }
    }

    //接着分配elts，大小为len+ngx_cacheline_size，此处为什么+ngx_cacheline_size？——下面要按ngx_cacheline_size字节对齐
    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);

    //将buckets数组与相应elts对应起来
    for (i = 0; i < size; i++) {
        if (test[i] == sizeof(void *)) {
            continue;
        }

        buckets[i] = (ngx_hash_elt_t *) elts;
        elts += test[i];
    }

    for (i = 0; i < size; i++) {
        test[i] = 0;
    }

    //将传进来的每一个hash数据存入hash表
    for (n = 0; n < nelts; n++) {
        if (names[n].key.data == NULL) {
            continue;
        }

        //计算key，即将被hash的数据在第几个bucket，并计算其对应的elts位置
        key = names[n].key_hash % size;
        elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]);

        //对ngx_hash_elt_t结构赋值
        elt->value = names[n].value;
        elt->len = (u_short) names[n].key.len;

        ngx_strlow(elt->name, names[n].key.data, names[n].key.len);

        //计算下一个要被hash的数据的长度偏移
        test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
    }

    for (i = 0; i < size; i++) {
        if (buckets[i] == NULL) {
            continue;
        }

        //test[i]相当于所有被hash的数据总长度
        elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);

        //将每个bucket的最后一个指针大小区域置NULL
        elt->value = NULL;
    }

    ngx_free(test);//释放该临时空间

    hinit->hash->buckets = buckets;
    hinit->hash->size = size;

    return NGX_OK;
}

static ngx_str_t names[] = {
    ngx_string("zieckey"),
    ngx_string("codeg"),
    ngx_string("jane") };

static char* descs[] = { "zieckey's id is 0", "codeg's id is 1", "jane's id is 2" };

// hash table的一些基本操作
TEST_UNIT(ngx_hash)
{
    ngx_uint_t          k;
    ngx_pool_t*         pool = g_pool;
    ngx_hash_init_t     hash_init;
    ngx_array_t*        elements;
    ngx_hash_key_t*     arr_node;
    char*               find;
    int                 i;

    ngx_cacheline_size = NGX_CPU_CACHE_LINE;

    hash_init.hash = NULL;                      // 置为NULL，让ngx_hash_init来初始化
    hash_init.key = &ngx_hash_key_lc;          // hash算法函数
    hash_init.max_size = 1024;                   // max_size
    hash_init.bucket_size = 64; // ngx_align(64, ngx_cacheline_size);
    hash_init.name = "codeg_hash";          // 在log里会用到
    hash_init.pool = pool;                 // 内存池
    hash_init.temp_pool = NULL;

    // 创建数组
    elements = ngx_array_create(pool, H_ARRAYSIZE(names), sizeof(ngx_hash_key_t));
    for (i = 0; i < H_ARRAYSIZE(names); 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);
    }

    H_TEST_ASSERT(ngx_hash_init(&hash_init, (ngx_hash_key_t*)elements->elts, elements->nelts) == NGX_OK);

    // 查找
    k = ngx_hash_key_lc(names[0].data, names[0].len);
    printf("%s key is %u\n", names[0].data, k);
    find = (char*)ngx_hash_find(hash_init.hash, k, (u_char*)names[0].data, names[0].len);
    H_TEST_ASSERT(find);
    if (find) {
        printf("get desc of %s : %s\n", (char*)names[0].data, (char*)find);
    }

    ngx_array_destroy(elements);
}