nginx高级数据类型(4) - 键值对、散列键值对、散列表

键值对

ngx_keyval_t 是一个简单的键值对，主要用来存储配置文件里成对出现的配置，一般会配合 ngx_array_t 来存储多个键值对。

// key-value结构体，用于解析配置文件里的数据
typedef struct {
    ngx_str_t   key;        // key
    ngx_str_t   value;      // value
} ngx_keyval_t;

散列键值对

// 键值对结构, 主要用来表示HTTP头部信息
typedef struct {
    ngx_uint_t        hash;         //散列（哈希）标记
    ngx_str_t         key;          //键
    ngx_str_t         value;        //值
    u_char           *lowcase_key;  //key的小写字符串指针
} ngx_table_elt_t;

ngx_table_elt_t 主要是用来表示 http 头部信息，例如 "Server: nginx"，key 对应 Server，value 对应 nginx 。hash 是散列值，使用它可以在散列表结构里快速查找数据。

// 简单地对单个字符计算散列
#define ngx_hash(key, c)   ((ngx_uint_t) key * 31 + c)

// 计算散列值
ngx_uint_t ngx_hash_key(u_char *data, size_t len);

// 小写后再计算hash
ngx_uint_t ngx_hash_key_lc(u_char *data, size_t len);

// 小写化的同时计算出散列值
ngx_uint_t ngx_hash_strlow(u_char *dst, u_char *src, size_t n);

散列表

// 散列表结构体
typedef struct {
    // 散列桶存储位置
    // 二维数组，里面存储的是指针
    ngx_hash_elt_t  **buckets;

    // 数组的长度
    ngx_uint_t        size;
} ngx_hash_t;

buckets 是一个二维数组，包含 size 个元素，而每个元素也是数组，可以包含多个 ngx_hash_elt_t，这里的多个 ngx_hash_elt_t 在一个数组里因为他们的 hash 值是相同的，就是所谓的碰撞了，只能通过遍历来比对才能找出我们要找的元素。

// 散列的桶
typedef struct {
    // 指向实际的元素
    void             *value;

    // name的实际长度
    u_short           len;

    u_char            name[1];
} ngx_hash_elt_t;

生成好的 hash 内存结构大致如下图。

然后我们可以通过查找函数来查找。

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;

    //先定位在哪一行
    elt = hash->buckets[key % hash->size];

    if (elt == NULL) {
        return 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:
        //指针移到下一个元素
        elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
                                               sizeof(void *));
        continue;
    }

    return NULL;
}

生成散列表的相关结构体

ngx_hash_key_t 为用来初始化散列表的数组元素。 

typedef struct {
    ngx_str_t         key;
    ngx_uint_t        key_hash;
    void             *value;
} ngx_hash_key_t;

ngx_hash_init_t 可以设置散列表的一些属性。

typedef struct {
    // 待初始化的散列表结构体
    ngx_hash_t       *hash;

    // 散列函数
    ngx_hash_key_pt   key;

    // 散列表里的最大桶数量
    ngx_uint_t        max_size;

    // 桶的大小，即ngx_hash_elt_t加自定义数据
    ngx_uint_t        bucket_size;

    // 散列表的名字
    char             *name;

    // 使用的内存池
    ngx_pool_t       *pool;

    // 临时用的内存池
    ngx_pool_t       *temp_pool;
} ngx_hash_init_t;

ngx_hash_init 用来初始化生成散列表

// 初始化散列表hinit
// 输入一个ngx_hash_key_t数组，长度散nelts
ngx_int_t ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,
    ngx_uint_t nelts);

例子-1

注意：如果想自己测试下面的例子，必须搭建 nginx 测试环境，请参考 nginx编译成静态库  

#include <stdio.h>
#include <ngx_core.h>

int main (int argc, char *argv[])
{
    ngx_int_t rc;
    ngx_pool_t *pool1;
    ngx_hash_t hash;
    ngx_hash_init_t hash_init;
    
    ngx_array_t array;
    
    ngx_cacheline_size = NGX_CPU_CACHE_LINE;
    
	pool1 = ngx_create_pool(NGX_DEFAULT_POOL_SIZE, NULL);
	
	ngx_str_t k1 = ngx_string("url");
    ngx_str_t k2 = ngx_string("name");
    ngx_str_t k3 = ngx_string("age");
    
    ngx_str_t v1 = ngx_string("http://www.freecls.com");
    ngx_str_t v2 = ngx_string("沧浪水");
    ngx_str_t v3 = ngx_string("22");
	
	hash_init.hash        = &hash;
    hash_init.key         = ngx_hash_key_lc;
    hash_init.max_size    = 128;
    hash_init.bucket_size = 64;
    hash_init.name        = "hash_array_name";
    hash_init.pool        = pool1;
    hash_init.temp_pool   = NULL;
	
	//把键名和键值通过数组的方式初始化到hash表里。
	ngx_array_init(&array, pool1, 3, sizeof(ngx_hash_key_t));
	
	ngx_hash_key_t *hk1 = (ngx_hash_key_t *)ngx_array_push(&array);
	hk1->key = k1;
	hk1->key_hash = ngx_hash_key_lc(k1.data, k1.len);
	hk1->value = v1.data;
	
	ngx_hash_key_t *hk2 = (ngx_hash_key_t *)ngx_array_push(&array);
	hk2->key = k2;
	hk2->key_hash = ngx_hash_key_lc(k2.data, k2.len);
	hk2->value = v2.data;
	
	ngx_hash_key_t *hk3 = (ngx_hash_key_t *)ngx_array_push(&array);
	hk3->key = k3;
	hk3->key_hash = ngx_hash_key_lc(k3.data, k3.len);
	hk3->value = v3.data;

	//开始建立 hash 表
    if (ngx_hash_init(&hash_init, array.elts, array.nelts) != NGX_OK) {
        return 1;
    }

	//此时 hash 表建立完成，可用通过查找函数进行查找。

	int h;
	
	h = ngx_hash_key_lc((u_char *)k1.data, k1.len);
    u_char *r1 = ngx_hash_find(&hash, h, (u_char *)k1.data, k1.len);
    if (r1 == NULL) {
        perror("ngx_hash_find() failed.");
        return 1;
    }
    
    h = ngx_hash_key_lc((u_char *)k2.data, k2.len);
    u_char *r2 = ngx_hash_find(&hash, h, (u_char *)k2.data, k2.len);
    if (r2 == NULL) {
        perror("ngx_hash_find() failed.");
        return 1;
    }
    
    h = ngx_hash_key_lc((u_char *)k3.data, k3.len);
    u_char *r3 = ngx_hash_find(&hash, h, (u_char *)k3.data, k3.len);
    if (r3 == NULL) {
        perror("ngx_hash_find() failed.");
        return 1;
    }
    printf("url : %s\nname: %s\nage : %s\n", r1, r2, r3);

    return 0;
}

[root@localhost c]# gcc main.c -lnginx -lpthread -lpcre -lssl -lcrypto -lz -lcrypt \
                    -ldl -I /usr/include/nginx/ -g
[root@localhost c]# ./a.out 
url : http://www.freecls.com
name: 沧浪水
age : 22

也可以用另外一种方式生成散列表。

例子-2

#include <stdio.h>
#include <ngx_core.h>

int main (int argc, char *argv[])
{
    ngx_int_t rc;
    ngx_pool_t *pool1, *pool2;
    ngx_hash_t hash;
    ngx_hash_init_t hash_init;
    ngx_hash_keys_arrays_t hash_array;

    ngx_str_t k1 = ngx_string("url");
    ngx_str_t k2 = ngx_string("name");
    ngx_str_t k3 = ngx_string("age");
    
    ngx_str_t v1 = ngx_string("http://www.freecls.com");
    ngx_str_t v2 = ngx_string("沧浪水");
    ngx_str_t v3 = ngx_string("22");

    ngx_cacheline_size = NGX_CPU_CACHE_LINE;

    pool1 = ngx_create_pool(NGX_DEFAULT_POOL_SIZE, NULL);
    if (pool1 == NULL) {
        perror("ngx_create_pool() failed.");
        return 1;
    }
    pool2 = ngx_create_pool(NGX_DEFAULT_POOL_SIZE, NULL);
    if (pool2 == NULL) {
        perror("ngx_create_pool() failed.");
        return 1;
    }

    hash_array.keys.pool = pool1;
    hash_array.temp_pool = pool2;
    
    if (ngx_hash_keys_array_init(&hash_array, NGX_HASH_SMALL) != NGX_OK) {
        return NGX_ERROR;
    }
    
    rc = ngx_hash_add_key(&hash_array, &k1, v1.data, NGX_HASH_READONLY_KEY);
    if (rc == NGX_ERROR) {
        perror("ngx_hash_add_key() failed.");
        return 1;
    }
    rc = ngx_hash_add_key(&hash_array, &k2, v2.data, NGX_HASH_READONLY_KEY);
    if (rc == NGX_ERROR) {
        perror("ngx_hash_add_key() failed.");
        return 1;
    }
    rc = ngx_hash_add_key(&hash_array, &k3, v3.data, NGX_HASH_READONLY_KEY);
    if (rc == NGX_ERROR) {
        perror("ngx_hash_add_key() failed.");
        return 1;
    }

    hash_init.hash        = &hash;
    hash_init.key         = ngx_hash_key_lc;
    hash_init.max_size    = 128;
    hash_init.bucket_size = 64;
    hash_init.name        = "hash_array_name";
    hash_init.pool        = hash_array.keys.pool;
    hash_init.temp_pool   = NULL;

    if (ngx_hash_init(&hash_init, hash_array.keys.elts, hash_array.keys.nelts) != NGX_OK) {
        return 1;
    }

	int h;
	
	h = ngx_hash_key_lc((u_char *)k1.data, k1.len);
    u_char *r1 = ngx_hash_find(&hash, h, (u_char *)k1.data, k1.len);
    if (r1 == NULL) {
        perror("ngx_hash_find() failed.");
        return 1;
    }
    
    h = ngx_hash_key_lc((u_char *)k2.data, k2.len);
    u_char *r2 = ngx_hash_find(&hash, h, (u_char *)k2.data, k2.len);
    if (r2 == NULL) {
        perror("ngx_hash_find() failed.");
        return 1;
    }
    
    h = ngx_hash_key_lc((u_char *)k3.data, k3.len);
    u_char *r3 = ngx_hash_find(&hash, h, (u_char *)k3.data, k3.len);
    if (r3 == NULL) {
        perror("ngx_hash_find() failed.");
        return 1;
    }
    printf("url : %s\nname: %s\nage : %s\n", r1, r2, r3);

    return 0;
}

[root@localhost examples]# gcc hash.c -lnginx -lpthread -lpcre -lssl -lcrypto -lz \
                            -lcrypt -ldl -I /usr/include/nginx/
[root@localhost examples]# ./a.out 
url : http://www.freecls.com
name: 沧浪水
age : 22

例子 - 通配符

#include <ngx_core.h>

int main (int argc, char *argv[])
{
    ngx_int_t rc;
    ngx_pool_t *pool1, *pool2;
    ngx_hash_init_t hash_init;
    ngx_hash_keys_arrays_t hash_array;
    
    ngx_hash_combined_t combinedHash;
    
    //ngx_memzero(&hash_array, sizeof(ngx_hash_keys_arrays_t));
    //ngx_memzero(&combinedHash, sizeof(ngx_hash_combined_t));
	
	pool1 = ngx_create_pool(NGX_DEFAULT_POOL_SIZE, NULL);
    if (pool1 == NULL) {
        perror("ngx_create_pool() failed.");
        return 1;
    }
    pool2 = ngx_create_pool(NGX_DEFAULT_POOL_SIZE, NULL);
    if (pool2 == NULL) {
        perror("ngx_create_pool() failed.");
        return 1;
    }
	//bug
	//char *k2 = "test";
    
    ngx_str_t k3;
    k3.len = ngx_strlen("www.baidu.com");
    k3.data = ngx_pcalloc(pool1, k3.len);
    ngx_memcpy(k3.data, "www.baidu.com", k3.len);
    
    //注意，通配符key必须可以修改，所以不能使用静态的数据
    ngx_str_t k4;
    k4.len = ngx_strlen("*.baidu.com");
    k4.data = ngx_pcalloc(pool1, k4.len);
    ngx_memcpy(k4.data, "*.baidu.com", k4.len);
    
    ngx_str_t k5;
    k5.len = ngx_strlen("www.freecls.*");
    k5.data = ngx_pcalloc(pool1, k5.len);
    ngx_memcpy(k5.data, "www.freecls.*", k5.len);
    
    char *v3 = "www.baidu.com";
    char *v4 = "*.baidu.com";
	char *v5 = "www.freecls.*";
	
	//char *k2 = "1111";

    ngx_cacheline_size = NGX_CPU_CACHE_LINE;

    
    hash_array.pool = pool1;
    hash_array.temp_pool = pool2;
    
    if (ngx_hash_keys_array_init(&hash_array, NGX_HASH_SMALL) != NGX_OK) {
        return NGX_ERROR;
    }
    
    rc = ngx_hash_add_key(&hash_array, &k3, v3, NGX_HASH_READONLY_KEY);
    if (rc == NGX_ERROR) {
        perror("ngx_hash_add_key() failed.");
        return 1;
    }
    
    rc = ngx_hash_add_key(&hash_array, &k4, v4, NGX_HASH_WILDCARD_KEY);
    if (rc == NGX_ERROR) {
        perror("ngx_hash_add_key() failed.");
        return 1;
    }
    
    rc = ngx_hash_add_key(&hash_array, &k5, v5, NGX_HASH_WILDCARD_KEY);
    if (rc == NGX_ERROR) {
        perror("ngx_hash_add_key() failed.");
        return 1;
    }

    
    hash_init.key         = ngx_hash_key_lc;
    hash_init.max_size    = 128;
    hash_init.bucket_size = 64;
    hash_init.name        = "hash_array_name";
    hash_init.pool        = pool1;

	if(hash_array.keys.nelts){
		hash_init.hash        = &combinedHash.hash;
		hash_init.temp_pool   = NULL;
		if (ngx_hash_init(&hash_init, hash_array.keys.elts, hash_array.keys.nelts) != NGX_OK) {
        	return 1;
    	}
	}
    
    if(hash_array.dns_wc_head.nelts){
		hash_init.hash        = NULL;
		hash_init.temp_pool   = hash_array.temp_pool;
		if (ngx_hash_wildcard_init(&hash_init, hash_array.dns_wc_head.elts, hash_array.dns_wc_head.nelts) != NGX_OK) {
        	return 1;
    	}
    	
    	combinedHash.wc_head = (ngx_hash_wildcard_t *)hash_init.hash;
	}
	
	if(hash_array.dns_wc_tail.nelts){
		hash_init.hash        = NULL;
		hash_init.temp_pool   = hash_array.temp_pool;
		if (ngx_hash_wildcard_init(&hash_init, hash_array.dns_wc_tail.elts, hash_array.dns_wc_tail.nelts) != NGX_OK) {
        	return 1;
    	}
    	
    	combinedHash.wc_tail = (ngx_hash_wildcard_t *)hash_init.hash;
	}
    
    

	ngx_uint_t h;
	
	//查找利用通配符查找
	ngx_str_t k6 = ngx_string("a.baidu.com");
	h = ngx_hash_key_lc((u_char *)k6.data, k6.len);
    u_char *r1 = ngx_hash_find_combined(&combinedHash, h, (u_char *)k6.data, k6.len);
    if (r1 == NULL) {
        r1 = "not find";
    }else{
    	printf("k6: %s\n", r1);
    }
    
    ngx_str_t k7 = ngx_string("www.baidu.com");
	h = ngx_hash_key_lc((u_char *)k7.data, k7.len);
    r1 = ngx_hash_find_combined(&combinedHash, h, (u_char *)k7.data, k7.len);
    if (r1 == NULL) {
        r1 = "not find";
    }else{
    	printf("k7: %s\n", r1);
    }
    
    ngx_str_t k8 = ngx_string("www.freecls.com");
	h = ngx_hash_key_lc((u_char *)k8.data, k8.len);
    r1 = ngx_hash_find_combined(&combinedHash, h, (u_char *)k8.data, k8.len);
    if (r1 == NULL) {
        r1 = "not find";
    }else{
    	printf("k8: %s\n", r1);
    }
    
    ngx_str_t k9 = ngx_string("www.freecls.cn");
	h = ngx_hash_key_lc((u_char *)k9.data, k9.len);
    r1 = ngx_hash_find_combined(&combinedHash, h, (u_char *)k9.data, k9.len);
    if (r1 == NULL) {
        r1 = "not find";
    }else{
    	printf("k9: %s\n", r1);
    }
	
	
    return 0;
}

[root@192 c]# gcc test.c -lnginx -lpthread -lpcre -lssl -lcrypto -lz \
              -lcrypt -ldl -I /usr/include/nginx/ -g
[root@192 c]# ./a.out 
k6: *.baidu.com
k7: www.baidu.com
k8: www.freecls.*
k9: www.freecls.*

有一个问题待解决，当去掉上面 bug 标记的注释：

char *k2 = "test";

那么输出如下，k6返回的指针指向的地址往前移动了一位，导致为空，而不是正常的 *.baidu.com。

[root@192 c]# ./a.out 
k6: 
k7: www.baidu.com
k8: www.freecls.*
k9: www.freecls.*