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