Nginx源代码分析--基本数据结构--hash

我们来看一下wildcard初始化函数。

 

//函数ngx_int_t

 

//ngx_array_s结构体

 

 

 

//elts是指向内存池中的存储元素的指针。内存池pool需要进行元素对齐等，所以这个值不等于pool

//nelts是当前有的元素个数

//size是每个元素大小

//nalloc是元素的多少

//pool是内存池的指针

 

 

struct ngx_array_s {    void        *elts;    ngx_uint_t   nelts;    size_t       size;    ngx_uint_t   nalloc;    ngx_pool_t  *pool;};

 

 

 

 

 

 

//内联函数，进行数组初始化，其实是分配某个数量的元素的内存，以便于压栈等操作

 

 

//参数，数组管理结构体、内存池、元素多少，每个元素大小

 

 

static ngx_inline ngx_int_tngx_array_init(ngx_array_t *array, ngx_pool_t *pool, ngx_uint_t n, size_t size){    /*     * set "array->nelts" before "array->elts", otherwise MSVC thinks     * that "array->nelts" may be used without having been initialized     */    array->nelts = 0;    array->size = size;    array->nalloc = n;    array->pool = pool;    array->elts = ngx_palloc(pool, n * size);    if (array->elts == NULL) {        return NGX_ERROR;    }    return NGX_OK;}

 

 

 

 

 

 

 

 

 

//函数ngx_hash_wildcard_init

//这段代码，由于我从来没看过wildcard的相关代码，所以另我相当恶心

 

//一起看看吧

 

 

ngx_int_tngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,    ngx_uint_t nelts){    size_t                len, dot_len;    ngx_uint_t            i, n, dot;    ngx_array_t           curr_names, next_names;    ngx_hash_key_t       *name, *next_name;    ngx_hash_init_t       h;    ngx_hash_wildcard_t  *wdc;

 

    //在hinit->temp_pool中开辟内存，并分配nelts个大小为ngx_hash_key_t的元素的内存空间，对齐后，将指针赋给curr_names

    //该元素数组指针即 curr_names

 

 

    if (ngx_array_init(&curr_names, hinit->temp_pool, nelts,                       sizeof(ngx_hash_key_t))        != NGX_OK)    {        return NGX_ERROR;    }

 

    //同样在hinit->temp_pool中开辟内存，分配nelts个大小为ngx_hash_key_t的元素的内存空间，对齐后，将指针赋给next_names

    //该元素数组指针即 next_names

    if (ngx_array_init(&next_names, hinit->temp_pool, nelts,                       sizeof(ngx_hash_key_t))        != NGX_OK)    {        return NGX_ERROR;    }

 

 

 

   //对于整个数组

 

    for (n = 0; n < nelts; n = i) {#if 0        ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,                      "wc0: /"%V/"", &names[n].key);#endif

 

        //标识        dot = 0;        //如果这个数组的元素中，有dot则，赋dot为1，并跳出这个检测数组元素中是否有dot的循环，当前的len则是从数组开始到数组中的  

        //dot。        for (len = 0; len < names[n].key.len; len++) {            if (names[n].key.data[len] == '.') {                dot = 1;                break;            }        }

        //curr_names的指针发生移动，以便于给当前元素赋值。也就是“压栈”操作        name = ngx_array_push(&curr_names);        if (name == NULL) {            return NGX_ERROR;        }                 //压栈操作的赋值代码，将names这个数组，的当前元素的值填充到name这个数组中，包括计算这个当前元素的key_hash的值        name->key.len = len;        name->key.data = names[n].key.data;        name->key_hash = hinit->key(name->key.data, name->key.len);        name->value = names[n].value;#if 0        ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,                      "wc1: /"%V/" %ui", &name->key, dot);#endif

 

        //数组中dot后其余部分的开始

        dot_len = len + 1;

        //如果dot==1，则说明数组其余部分第一个是dot，应该将len+1指向dot后第一个字符        if (dot) {            len++;        }

 

 

       //初始化next_names指向的元素的实际个数为0

 

        next_names.nelts = 0;

 

        //如果names中的元素长度与当前长度不等，说明确实有dot。

        if (names[n].key.len != len) {

              //把这个压入next_names栈中

            next_name = ngx_array_push(&next_names);            if (next_name == NULL) {                return NGX_ERROR;            }

           //得到新的字串的长度            next_name->key.len = names[n].key.len - len;           //新的字串的指针

           next_name->key.data = names[n].key.data + len;           //新的字串的hash值

           next_name->key_hash = 0;

            //新的字串的值           next_name->value = names[n].value;#if 0            ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,                          "wc2: /"%V/"", &next_name->key);#endif        }

 

        //比较当前names[n]的值的数据是否有和n+1到nelts的元素的值相同的        for (i = n + 1; i < nelts; i++) {

            //如果names[n]的key值的数据和names[i]的key的数据相同不相同，则跳出循环。

            if (ngx_strncmp(names[n].key.data, names[i].key.data, len) != 0) {                break;            }

             //到这，意味着key数据值相同

              //如果dot==0并且names[i]的key的长度大于len并且names[i]的key的数据不是dot(.)则退出循环

            if (!dot                && names[i].key.len > len                && names[i].key.data[len] != '.')            {                break;            }

            //到这意味着dot==1，并且names[i]的后边也有字符。则将next_names压入栈，即names[i]与names[n]处理相同

            next_name = ngx_array_push(&next_names);            if (next_name == NULL) {                return NGX_ERROR;            }             //进行赋值与names[n]的相同

            next_name->key.len = names[i].key.len - dot_len;            next_name->key.data = names[i].key.data + dot_len;            next_name->key_hash = 0;            next_name->value = names[i].value;#if 0            ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,                          "wc3: /"%V/"", &next_name->key);#endif        }

 

 

 

 

        //如果当前没有执行过push_array_push操作，也就是dot后边没有元素

       //则意味着curr_names中已经不含有dot。

 

       //递归调用，对next_names进行

 

        if (next_names.nelts) {            h = *hinit;            h.hash = NULL;            if (ngx_hash_wildcard_init(&h, (ngx_hash_key_t *) next_names.elts,                                       next_names.nelts)                != NGX_OK)            {                return NGX_ERROR;            }

 

             //没看明白。。。。。。。。。。。。。。。。。。。。。。。。。。。。

 

            wdc = (ngx_hash_wildcard_t *) h.hash;            if (names[n].key.len == len) {                wdc->value = names[n].value;            }            name->value = (void *) ((uintptr_t) wdc | (dot ? 3 : 2));        } else if (dot) {            name->value = (void *) ((uintptr_t) name->value | 1);        }    }

 

 

  //最后，所有不含dot的元素都在curr_names中了，进行初始化hinit。

    if (ngx_hash_init(hinit, (ngx_hash_key_t *) curr_names.elts,                      curr_names.nelts)        != NGX_OK)    {        return NGX_ERROR;    }    return NGX_OK;}