+ rev="2">

@@ -955,6 +955,182 @@

+ + +Hash table functions are are declared in src/core/ngx_string.h. +Exact and wildcard matching is supported. +The latter requires extra setup and is described in a separate section below. + + + +To initialize a hash, one needs to know the number of elements in advance, +so that nginx can build the hash optimally. +Two parameters that need to be configured are max_size +and bucket_size. +The details of setting up these are provided in a separate +document. +Usually, these two parameters are configurable by user. +Hash initialization settings are stored as the +ngx_hash_init_t type, +and the hash itself is ngx_hash_t: + +ngx_hash_t foo_hash; +ngx_hash_init_t hash; + +hash.hash = &foo_hash; +hash.key = ngx_hash_key; +hash.max_size = 512; +hash.bucket_size = ngx_align(64, ngx_cacheline_size); +hash.name = "foo_hash"; +hash.pool = cf->pool; +hash.temp_pool = cf->temp_pool; + +The key is a pointer to a function that creates hash integer +key from a string. +Two generic functions are provided: +ngx_hash_key(data, len) and +ngx_hash_key_lc(data, len). +The latter converts a string to lowercase and thus requires the passed string to +be writable. +If this is not true, NGX_HASH_READONLY_KEY flag +may be passed to the function, initializing array keys (see below). + + + +The hash keys are stored in ngx_hash_keys_arrays_t and +are initialized with ngx_hash_keys_array_init(arr, type): + +ngx_hash_keys_arrays_t foo_keys; + +foo_keys.pool = cf->pool; +foo_keys.temp_pool = cf->temp_pool; + +ngx_hash_keys_array_init(&foo_keys, NGX_HASH_SMALL); + +The second parameter can be either NGX_HASH_SMALL or +NGX_HASH_LARGE and controls the amount of preallocated +resources for the hash. +If you expect the hash to contain thousands elements, +use NGX_HASH_LARGE. + + + +The ngx_hash_add_key(keys_array, key, value, flags) +function is used to insert keys into hash keys array; + +ngx_str_t k1 = ngx_string("key1"); +ngx_str_t k2 = ngx_string("key2"); + +ngx_hash_add_key(&foo_keys, &k1, &my_data_ptr_1, NGX_HASH_READONLY_KEY); +ngx_hash_add_key(&foo_keys, &k2, &my_data_ptr_2, NGX_HASH_READONLY_KEY); + + + + +Now, the hash table may be built using the call to +ngx_hash_init(hinit, key_names, nelts): + + +ngx_hash_init(&hash, foo_keys.keys.elts, foo_keys.keys.nelts); + + +This may fail, if max_size or bucket_size +parameters are not big enough. +When the hash is built, ngx_hash_find(hash, key, name, len) +function may be used to look up elements: + +my_data_t *data; +ngx_uint_t key; + +key = ngx_hash_key(k1.data, k1.len); + +data = ngx_hash_find(&foo_hash, key, k1.data, k1.len); +if (data == NULL) { + /* key not found */ +} + + + + +

+ + +To create a hash that works with wildcards, +ngx_hash_combined_t type is used. +It includes the hash type described above and has two additional keys arrays: +dns_wc_head and dns_wc_tail. +The initialization of basic properties is done similarly to a usual hash: + +ngx_hash_init_t hash +ngx_hash_combined_t foo_hash; + +hash.hash = &foo_hash.hash; +hash.key = ...; + + + + +It is possible to add wildcard keys using the +NGX_HASH_WILDCARD_KEY flag: + +/* k1 = ".example.org"; */ +/* k2 = "foo.*"; */ +ngx_hash_add_key(&foo_keys, &k1, &data1, NGX_HASH_WILDCARD_KEY); +ngx_hash_add_key(&foo_keys, &k2, &data2, NGX_HASH_WILDCARD_KEY); + +The function recognizes wildcards and adds keys into corresponding arrays. +Please refer to the + module +documentation for the description of the wildcard syntax and +matching algorithm. + + + +Depending on the contents of added keys, you may need to initialize up to three +keys arrays: one for exact matching (described above), and two for matching +starting from head or tail of a string: + +if (foo_keys.dns_wc_head.nelts) { + + ngx_qsort(foo_keys.dns_wc_head.elts, + (size_t) foo_keys.dns_wc_head.nelts, + sizeof(ngx_hash_key_t), + cmp_dns_wildcards); + + hash.hash = NULL; + hash.temp_pool = pool; + + if (ngx_hash_wildcard_init(&hash, foo_keys.dns_wc_head.elts, + foo_keys.dns_wc_head.nelts) + != NGX_OK) + { + return NGX_ERROR; + } + + foo_hash.wc_head = (ngx_hash_wildcard_t *) hash.hash; +} + +The keys array needs to be sorted, and initialization results must be added +to the combined hash. +The initialization of dns_wc_tail array is done similarly. + + + +The lookup in a combined hash is handled by the +ngx_hash_find_combined(chash, key, name, len): + +/* key = "bar.example.org"; - will match ".example.org" */ +/* key = "foo.example.com"; - will match "foo.*" */ + +hkey = ngx_hash_key(key.data, key.len); +res = ngx_hash_find_combined(&foo_hash, hkey, key.data, key.len); + + + +

+ +