|
56
|
1
|
|
|
2 /*
|
|
|
3 * Copyright (C) Igor Sysoev
|
|
|
4 */
|
|
|
5
|
|
|
6
|
|
|
7 #include <ngx_config.h>
|
|
|
8 #include <ngx_core.h>
|
|
|
9
|
|
|
10
|
|
|
11 ngx_int_t
|
|
|
12 ngx_hash_init(ngx_hash_t *hash, ngx_pool_t *pool, void *names)
|
|
|
13 {
|
|
|
14 u_char *p;
|
|
|
15 ngx_str_t *n, *bucket;
|
|
|
16 ngx_uint_t i, key, size, best, *test, buckets, min_buckets;
|
|
|
17
|
|
|
18 test = ngx_alloc(hash->max_size * sizeof(ngx_uint_t), pool->log);
|
|
|
19 if (test == NULL) {
|
|
|
20 return NGX_ERROR;
|
|
|
21 }
|
|
|
22
|
|
|
23 min_buckets = hash->bucket_limit + 1;
|
|
|
24
|
|
|
25 #if (NGX_SUPPRESS_WARN)
|
|
|
26 best = 0;
|
|
|
27 #endif
|
|
|
28
|
|
|
29 for (size = 1; size < hash->max_size; size++) {
|
|
|
30
|
|
|
31 buckets = 0;
|
|
|
32
|
|
|
33 for (i = 0; i < size; i++) {
|
|
|
34 test[i] = 0;
|
|
|
35 }
|
|
|
36
|
|
|
37 for (n = (ngx_str_t *) names;
|
|
|
38 n->len;
|
|
|
39 n = (ngx_str_t *) ((char *) n + hash->bucket_size))
|
|
|
40 {
|
|
|
41 key = 0;
|
|
|
42
|
|
|
43 for (i = 0; i < n->len; i++) {
|
|
|
44 key += ngx_tolower(n->data[i]);
|
|
|
45 }
|
|
|
46
|
|
|
47 key %= size;
|
|
|
48
|
|
|
49 if (test[key] == hash->bucket_limit) {
|
|
|
50 break;
|
|
|
51 }
|
|
|
52
|
|
|
53 test[key]++;
|
|
|
54
|
|
|
55 if (buckets < test[key]) {
|
|
|
56 buckets = test[key];
|
|
|
57 }
|
|
|
58 }
|
|
|
59
|
|
|
60 if (n->len == 0) {
|
|
|
61 if (min_buckets > buckets) {
|
|
|
62 min_buckets = buckets;
|
|
|
63 best = size;
|
|
|
64 }
|
|
|
65
|
|
|
66 if (hash->bucket_limit == 1) {
|
|
|
67 break;
|
|
|
68 }
|
|
|
69 }
|
|
|
70 }
|
|
|
71
|
|
|
72 if (min_buckets == hash->bucket_limit + 1) {
|
|
|
73 ngx_log_error(NGX_LOG_EMERG, pool->log, 0,
|
|
|
74 "could not build the %s hash, you should increase "
|
|
|
75 "either %s_size: %i or %s_bucket_limit: %i",
|
|
|
76 hash->name, hash->name, hash->max_size,
|
|
|
77 hash->name, hash->bucket_limit);
|
|
|
78 ngx_free(test);
|
|
|
79 return NGX_ERROR;
|
|
|
80 }
|
|
|
81
|
|
|
82 hash->buckets = ngx_pcalloc(pool, best * hash->bucket_size);
|
|
|
83 if (hash->buckets == NULL) {
|
|
|
84 ngx_free(test);
|
|
|
85 return NGX_ERROR;
|
|
|
86 }
|
|
|
87
|
|
|
88 if (hash->bucket_limit != 1) {
|
|
|
89
|
|
|
90 for (i = 0; i < best; i++) {
|
|
|
91 test[i] = 0;
|
|
|
92 }
|
|
|
93
|
|
|
94 for (n = (ngx_str_t *) names;
|
|
|
95 n->len;
|
|
|
96 n = (ngx_str_t *) ((char *) n + hash->bucket_size))
|
|
|
97 {
|
|
|
98 key = 0;
|
|
|
99
|
|
|
100 for (i = 0; i < n->len; i++) {
|
|
|
101 key += ngx_tolower(n->data[i]);
|
|
|
102 }
|
|
|
103
|
|
|
104 key %= best;
|
|
|
105
|
|
|
106 test[key]++;
|
|
|
107 }
|
|
|
108
|
|
|
109 for (i = 0; i < best; i++) {
|
|
|
110 if (test[i] == 0) {
|
|
|
111 continue;
|
|
|
112 }
|
|
|
113
|
|
|
114 bucket = ngx_palloc(pool, test[i] * hash->bucket_size);
|
|
|
115 if (bucket == NULL) {
|
|
|
116 ngx_free(test);
|
|
|
117 return NGX_ERROR;
|
|
|
118 }
|
|
|
119
|
|
|
120 hash->buckets[i] = bucket;
|
|
|
121 bucket->len = 0;
|
|
|
122 }
|
|
|
123 }
|
|
|
124
|
|
|
125 for (n = (ngx_str_t *) names;
|
|
|
126 n->len;
|
|
|
127 n = (ngx_str_t *) ((char *) n + hash->bucket_size))
|
|
|
128 {
|
|
|
129 key = 0;
|
|
|
130
|
|
|
131 for (i = 0; i < n->len; i++) {
|
|
|
132 key += ngx_tolower(n->data[i]);
|
|
|
133 }
|
|
|
134
|
|
|
135 key %= best;
|
|
|
136
|
|
|
137 if (hash->bucket_limit == 1) {
|
|
|
138 p = (u_char *) hash->buckets + key * hash->bucket_size;
|
|
|
139 ngx_memcpy(p, n, hash->bucket_size);
|
|
|
140 continue;
|
|
|
141 }
|
|
|
142
|
|
|
143 for (bucket = hash->buckets[key];
|
|
|
144 bucket->len;
|
|
|
145 bucket = (ngx_str_t *) ((char *) bucket + hash->bucket_size))
|
|
|
146 {
|
|
|
147 bucket->len &= 0x7fffffff;
|
|
|
148 }
|
|
|
149
|
|
|
150 ngx_memcpy(bucket, n, hash->bucket_size);
|
|
|
151 bucket->len |= 0x80000000;
|
|
|
152 }
|
|
|
153
|
|
|
154 ngx_free(test);
|
|
|
155
|
|
|
156 hash->hash_size = best;
|
|
|
157 hash->min_buckets = min_buckets;
|
|
|
158
|
|
|
159 return NGX_OK;
|
|
|
160 }
|
