|
56
|
1
|
|
|
2 /*
|
|
|
3 * Copyright (C) Igor Sysoev
|
|
660
|
4 * Copyright (C) Nginx, Inc.
|
|
56
|
5 */
|
|
|
6
|
|
|
7
|
|
|
8 #include <ngx_config.h>
|
|
|
9 #include <ngx_core.h>
|
|
|
10
|
|
|
11
|
|
138
|
12 void *
|
|
|
13 ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len)
|
|
|
14 {
|
|
|
15 ngx_uint_t i;
|
|
|
16 ngx_hash_elt_t *elt;
|
|
|
17
|
|
|
18 #if 0
|
|
394
|
19 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "hf:\"%*s\"", len, name);
|
|
138
|
20 #endif
|
|
|
21
|
|
|
22 elt = hash->buckets[key % hash->size];
|
|
|
23
|
|
|
24 if (elt == NULL) {
|
|
|
25 return NULL;
|
|
|
26 }
|
|
|
27
|
|
|
28 while (elt->value) {
|
|
|
29 if (len != (size_t) elt->len) {
|
|
|
30 goto next;
|
|
|
31 }
|
|
|
32
|
|
|
33 for (i = 0; i < len; i++) {
|
|
|
34 if (name[i] != elt->name[i]) {
|
|
|
35 goto next;
|
|
|
36 }
|
|
|
37 }
|
|
|
38
|
|
|
39 return elt->value;
|
|
|
40
|
|
|
41 next:
|
|
|
42
|
|
|
43 elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
|
|
|
44 sizeof(void *));
|
|
|
45 continue;
|
|
|
46 }
|
|
|
47
|
|
|
48 return NULL;
|
|
|
49 }
|
|
|
50
|
|
|
51
|
|
|
52 void *
|
|
312
|
53 ngx_hash_find_wc_head(ngx_hash_wildcard_t *hwc, u_char *name, size_t len)
|
|
138
|
54 {
|
|
|
55 void *value;
|
|
|
56 ngx_uint_t i, n, key;
|
|
|
57
|
|
|
58 #if 0
|
|
394
|
59 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wch:\"%*s\"", len, name);
|
|
138
|
60 #endif
|
|
|
61
|
|
|
62 n = len;
|
|
|
63
|
|
|
64 while (n) {
|
|
|
65 if (name[n - 1] == '.') {
|
|
|
66 break;
|
|
|
67 }
|
|
|
68
|
|
|
69 n--;
|
|
|
70 }
|
|
|
71
|
|
|
72 key = 0;
|
|
|
73
|
|
|
74 for (i = n; i < len; i++) {
|
|
|
75 key = ngx_hash(key, name[i]);
|
|
|
76 }
|
|
|
77
|
|
|
78 #if 0
|
|
|
79 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "key:\"%ui\"", key);
|
|
|
80 #endif
|
|
|
81
|
|
|
82 value = ngx_hash_find(&hwc->hash, key, &name[n], len - n);
|
|
|
83
|
|
394
|
84 #if 0
|
|
|
85 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "value:\"%p\"", value);
|
|
|
86 #endif
|
|
|
87
|
|
138
|
88 if (value) {
|
|
140
|
89
|
|
|
90 /*
|
|
|
91 * the 2 low bits of value have the special meaning:
|
|
394
|
92 * 00 - value is data pointer for both "example.com"
|
|
|
93 * and "*.example.com";
|
|
|
94 * 01 - value is data pointer for "*.example.com" only;
|
|
|
95 * 10 - value is pointer to wildcard hash allowing
|
|
|
96 * both "example.com" and "*.example.com";
|
|
140
|
97 * 11 - value is pointer to wildcard hash allowing
|
|
394
|
98 * "*.example.com" only.
|
|
140
|
99 */
|
|
|
100
|
|
394
|
101 if ((uintptr_t) value & 2) {
|
|
|
102
|
|
|
103 if (n == 0) {
|
|
|
104
|
|
|
105 /* "example.com" */
|
|
|
106
|
|
|
107 if ((uintptr_t) value & 1) {
|
|
|
108 return NULL;
|
|
|
109 }
|
|
|
110
|
|
|
111 hwc = (ngx_hash_wildcard_t *)
|
|
|
112 ((uintptr_t) value & (uintptr_t) ~3);
|
|
|
113 return hwc->value;
|
|
|
114 }
|
|
140
|
115
|
|
|
116 hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~3);
|
|
|
117
|
|
312
|
118 value = ngx_hash_find_wc_head(hwc, name, n - 1);
|
|
138
|
119
|
|
|
120 if (value) {
|
|
|
121 return value;
|
|
|
122 }
|
|
|
123
|
|
|
124 return hwc->value;
|
|
|
125 }
|
|
|
126
|
|
394
|
127 if ((uintptr_t) value & 1) {
|
|
|
128
|
|
|
129 if (n == 0) {
|
|
|
130
|
|
|
131 /* "example.com" */
|
|
|
132
|
|
|
133 return NULL;
|
|
|
134 }
|
|
|
135
|
|
|
136 return (void *) ((uintptr_t) value & (uintptr_t) ~3);
|
|
|
137 }
|
|
|
138
|
|
138
|
139 return value;
|
|
|
140 }
|
|
|
141
|
|
|
142 return hwc->value;
|
|
|
143 }
|
|
|
144
|
|
|
145
|
|
312
|
146 void *
|
|
|
147 ngx_hash_find_wc_tail(ngx_hash_wildcard_t *hwc, u_char *name, size_t len)
|
|
|
148 {
|
|
|
149 void *value;
|
|
|
150 ngx_uint_t i, key;
|
|
|
151
|
|
|
152 #if 0
|
|
394
|
153 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wct:\"%*s\"", len, name);
|
|
312
|
154 #endif
|
|
|
155
|
|
|
156 key = 0;
|
|
|
157
|
|
|
158 for (i = 0; i < len; i++) {
|
|
|
159 if (name[i] == '.') {
|
|
|
160 break;
|
|
|
161 }
|
|
|
162
|
|
|
163 key = ngx_hash(key, name[i]);
|
|
|
164 }
|
|
|
165
|
|
|
166 if (i == len) {
|
|
|
167 return NULL;
|
|
|
168 }
|
|
|
169
|
|
|
170 #if 0
|
|
|
171 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "key:\"%ui\"", key);
|
|
|
172 #endif
|
|
|
173
|
|
|
174 value = ngx_hash_find(&hwc->hash, key, name, i);
|
|
|
175
|
|
394
|
176 #if 0
|
|
|
177 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "value:\"%p\"", value);
|
|
|
178 #endif
|
|
|
179
|
|
312
|
180 if (value) {
|
|
|
181
|
|
|
182 /*
|
|
|
183 * the 2 low bits of value have the special meaning:
|
|
394
|
184 * 00 - value is data pointer;
|
|
|
185 * 11 - value is pointer to wildcard hash allowing "example.*".
|
|
312
|
186 */
|
|
|
187
|
|
394
|
188 if ((uintptr_t) value & 2) {
|
|
312
|
189
|
|
|
190 i++;
|
|
|
191
|
|
|
192 hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~3);
|
|
|
193
|
|
|
194 value = ngx_hash_find_wc_tail(hwc, &name[i], len - i);
|
|
|
195
|
|
|
196 if (value) {
|
|
|
197 return value;
|
|
|
198 }
|
|
|
199
|
|
|
200 return hwc->value;
|
|
|
201 }
|
|
|
202
|
|
|
203 return value;
|
|
|
204 }
|
|
|
205
|
|
|
206 return hwc->value;
|
|
|
207 }
|
|
|
208
|
|
|
209
|
|
|
210 void *
|
|
|
211 ngx_hash_find_combined(ngx_hash_combined_t *hash, ngx_uint_t key, u_char *name,
|
|
|
212 size_t len)
|
|
|
213 {
|
|
|
214 void *value;
|
|
|
215
|
|
|
216 if (hash->hash.buckets) {
|
|
|
217 value = ngx_hash_find(&hash->hash, key, name, len);
|
|
|
218
|
|
|
219 if (value) {
|
|
|
220 return value;
|
|
|
221 }
|
|
|
222 }
|
|
|
223
|
|
400
|
224 if (len == 0) {
|
|
|
225 return NULL;
|
|
|
226 }
|
|
|
227
|
|
312
|
228 if (hash->wc_head && hash->wc_head->hash.buckets) {
|
|
|
229 value = ngx_hash_find_wc_head(hash->wc_head, name, len);
|
|
|
230
|
|
|
231 if (value) {
|
|
|
232 return value;
|
|
|
233 }
|
|
|
234 }
|
|
|
235
|
|
|
236 if (hash->wc_tail && hash->wc_tail->hash.buckets) {
|
|
|
237 value = ngx_hash_find_wc_tail(hash->wc_tail, name, len);
|
|
|
238
|
|
|
239 if (value) {
|
|
|
240 return value;
|
|
|
241 }
|
|
|
242 }
|
|
|
243
|
|
|
244 return NULL;
|
|
|
245 }
|
|
|
246
|
|
|
247
|
|
138
|
248 #define NGX_HASH_ELT_SIZE(name) \
|
|
570
|
249 (sizeof(void *) + ngx_align((name)->key.len + 2, sizeof(void *)))
|
|
138
|
250
|
|
56
|
251 ngx_int_t
|
|
138
|
252 ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts)
|
|
|
253 {
|
|
|
254 u_char *elts;
|
|
144
|
255 size_t len;
|
|
|
256 u_short *test;
|
|
138
|
257 ngx_uint_t i, n, key, size, start, bucket_size;
|
|
|
258 ngx_hash_elt_t *elt, **buckets;
|
|
|
259
|
|
|
260 for (n = 0; n < nelts; n++) {
|
|
|
261 if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *))
|
|
|
262 {
|
|
|
263 ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
|
|
144
|
264 "could not build the %s, you should "
|
|
138
|
265 "increase %s_bucket_size: %i",
|
|
|
266 hinit->name, hinit->name, hinit->bucket_size);
|
|
|
267 return NGX_ERROR;
|
|
|
268 }
|
|
|
269 }
|
|
|
270
|
|
144
|
271 test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log);
|
|
138
|
272 if (test == NULL) {
|
|
|
273 return NGX_ERROR;
|
|
|
274 }
|
|
|
275
|
|
180
|
276 bucket_size = hinit->bucket_size - sizeof(void *);
|
|
|
277
|
|
242
|
278 start = nelts / (bucket_size / (2 * sizeof(void *)));
|
|
138
|
279 start = start ? start : 1;
|
|
|
280
|
|
658
|
281 if (hinit->max_size > 10000 && nelts && hinit->max_size / nelts < 100) {
|
|
180
|
282 start = hinit->max_size - 1000;
|
|
|
283 }
|
|
138
|
284
|
|
|
285 for (size = start; size < hinit->max_size; size++) {
|
|
|
286
|
|
144
|
287 ngx_memzero(test, size * sizeof(u_short));
|
|
138
|
288
|
|
|
289 for (n = 0; n < nelts; n++) {
|
|
|
290 if (names[n].key.data == NULL) {
|
|
|
291 continue;
|
|
|
292 }
|
|
|
293
|
|
|
294 key = names[n].key_hash % size;
|
|
144
|
295 test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
|
|
138
|
296
|
|
|
297 #if 0
|
|
|
298 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
|
|
|
299 "%ui: %ui %ui \"%V\"",
|
|
|
300 size, key, test[key], &names[n].key);
|
|
|
301 #endif
|
|
|
302
|
|
144
|
303 if (test[key] > (u_short) bucket_size) {
|
|
138
|
304 goto next;
|
|
|
305 }
|
|
|
306 }
|
|
|
307
|
|
|
308 goto found;
|
|
|
309
|
|
|
310 next:
|
|
|
311
|
|
|
312 continue;
|
|
|
313 }
|
|
|
314
|
|
|
315 ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
|
|
144
|
316 "could not build the %s, you should increase "
|
|
138
|
317 "either %s_max_size: %i or %s_bucket_size: %i",
|
|
|
318 hinit->name, hinit->name, hinit->max_size,
|
|
|
319 hinit->name, hinit->bucket_size);
|
|
|
320
|
|
|
321 ngx_free(test);
|
|
|
322
|
|
|
323 return NGX_ERROR;
|
|
|
324
|
|
|
325 found:
|
|
|
326
|
|
|
327 for (i = 0; i < size; i++) {
|
|
|
328 test[i] = sizeof(void *);
|
|
|
329 }
|
|
|
330
|
|
|
331 for (n = 0; n < nelts; n++) {
|
|
|
332 if (names[n].key.data == NULL) {
|
|
|
333 continue;
|
|
|
334 }
|
|
|
335
|
|
|
336 key = names[n].key_hash % size;
|
|
144
|
337 test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
|
|
138
|
338 }
|
|
|
339
|
|
|
340 len = 0;
|
|
|
341
|
|
|
342 for (i = 0; i < size; i++) {
|
|
|
343 if (test[i] == sizeof(void *)) {
|
|
|
344 continue;
|
|
|
345 }
|
|
|
346
|
|
144
|
347 test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size));
|
|
138
|
348
|
|
|
349 len += test[i];
|
|
|
350 }
|
|
|
351
|
|
|
352 if (hinit->hash == NULL) {
|
|
|
353 hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t)
|
|
|
354 + size * sizeof(ngx_hash_elt_t *));
|
|
|
355 if (hinit->hash == NULL) {
|
|
|
356 ngx_free(test);
|
|
|
357 return NGX_ERROR;
|
|
|
358 }
|
|
|
359
|
|
|
360 buckets = (ngx_hash_elt_t **)
|
|
|
361 ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t));
|
|
|
362
|
|
|
363 } else {
|
|
|
364 buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));
|
|
|
365 if (buckets == NULL) {
|
|
|
366 ngx_free(test);
|
|
|
367 return NGX_ERROR;
|
|
|
368 }
|
|
|
369 }
|
|
|
370
|
|
|
371 elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size);
|
|
|
372 if (elts == NULL) {
|
|
|
373 ngx_free(test);
|
|
|
374 return NGX_ERROR;
|
|
|
375 }
|
|
|
376
|
|
|
377 elts = ngx_align_ptr(elts, ngx_cacheline_size);
|
|
|
378
|
|
|
379 for (i = 0; i < size; i++) {
|
|
|
380 if (test[i] == sizeof(void *)) {
|
|
|
381 continue;
|
|
|
382 }
|
|
|
383
|
|
|
384 buckets[i] = (ngx_hash_elt_t *) elts;
|
|
|
385 elts += test[i];
|
|
|
386
|
|
|
387 }
|
|
|
388
|
|
|
389 for (i = 0; i < size; i++) {
|
|
|
390 test[i] = 0;
|
|
|
391 }
|
|
|
392
|
|
|
393 for (n = 0; n < nelts; n++) {
|
|
|
394 if (names[n].key.data == NULL) {
|
|
|
395 continue;
|
|
|
396 }
|
|
|
397
|
|
|
398 key = names[n].key_hash % size;
|
|
|
399 elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]);
|
|
|
400
|
|
|
401 elt->value = names[n].value;
|
|
570
|
402 elt->len = (u_short) names[n].key.len;
|
|
138
|
403
|
|
392
|
404 ngx_strlow(elt->name, names[n].key.data, names[n].key.len);
|
|
138
|
405
|
|
144
|
406 test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
|
|
138
|
407 }
|
|
|
408
|
|
|
409 for (i = 0; i < size; i++) {
|
|
|
410 if (buckets[i] == NULL) {
|
|
|
411 continue;
|
|
|
412 }
|
|
|
413
|
|
|
414 elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);
|
|
|
415
|
|
|
416 elt->value = NULL;
|
|
|
417 }
|
|
|
418
|
|
|
419 ngx_free(test);
|
|
|
420
|
|
|
421 hinit->hash->buckets = buckets;
|
|
|
422 hinit->hash->size = size;
|
|
|
423
|
|
|
424 #if 0
|
|
|
425
|
|
|
426 for (i = 0; i < size; i++) {
|
|
|
427 ngx_str_t val;
|
|
|
428 ngx_uint_t key;
|
|
|
429
|
|
|
430 elt = buckets[i];
|
|
|
431
|
|
|
432 if (elt == NULL) {
|
|
|
433 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
|
|
|
434 "%ui: NULL", i);
|
|
|
435 continue;
|
|
|
436 }
|
|
|
437
|
|
|
438 while (elt->value) {
|
|
|
439 val.len = elt->len;
|
|
|
440 val.data = &elt->name[0];
|
|
|
441
|
|
|
442 key = hinit->key(val.data, val.len);
|
|
|
443
|
|
|
444 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
|
|
|
445 "%ui: %p \"%V\" %ui", i, elt, &val, key);
|
|
|
446
|
|
|
447 elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
|
|
|
448 sizeof(void *));
|
|
|
449 }
|
|
|
450 }
|
|
|
451
|
|
|
452 #endif
|
|
|
453
|
|
|
454 return NGX_OK;
|
|
|
455 }
|
|
|
456
|
|
|
457
|
|
|
458 ngx_int_t
|
|
|
459 ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,
|
|
|
460 ngx_uint_t nelts)
|
|
|
461 {
|
|
142
|
462 size_t len, dot_len;
|
|
140
|
463 ngx_uint_t i, n, dot;
|
|
138
|
464 ngx_array_t curr_names, next_names;
|
|
|
465 ngx_hash_key_t *name, *next_name;
|
|
|
466 ngx_hash_init_t h;
|
|
|
467 ngx_hash_wildcard_t *wdc;
|
|
|
468
|
|
|
469 if (ngx_array_init(&curr_names, hinit->temp_pool, nelts,
|
|
|
470 sizeof(ngx_hash_key_t))
|
|
|
471 != NGX_OK)
|
|
|
472 {
|
|
|
473 return NGX_ERROR;
|
|
|
474 }
|
|
|
475
|
|
|
476 if (ngx_array_init(&next_names, hinit->temp_pool, nelts,
|
|
|
477 sizeof(ngx_hash_key_t))
|
|
|
478 != NGX_OK)
|
|
|
479 {
|
|
|
480 return NGX_ERROR;
|
|
|
481 }
|
|
|
482
|
|
|
483 for (n = 0; n < nelts; n = i) {
|
|
|
484
|
|
|
485 #if 0
|
|
|
486 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
|
|
|
487 "wc0: \"%V\"", &names[n].key);
|
|
|
488 #endif
|
|
|
489
|
|
140
|
490 dot = 0;
|
|
|
491
|
|
138
|
492 for (len = 0; len < names[n].key.len; len++) {
|
|
|
493 if (names[n].key.data[len] == '.') {
|
|
140
|
494 dot = 1;
|
|
138
|
495 break;
|
|
|
496 }
|
|
|
497 }
|
|
|
498
|
|
|
499 name = ngx_array_push(&curr_names);
|
|
|
500 if (name == NULL) {
|
|
|
501 return NGX_ERROR;
|
|
|
502 }
|
|
|
503
|
|
140
|
504 name->key.len = len;
|
|
138
|
505 name->key.data = names[n].key.data;
|
|
|
506 name->key_hash = hinit->key(name->key.data, name->key.len);
|
|
|
507 name->value = names[n].value;
|
|
|
508
|
|
|
509 #if 0
|
|
|
510 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
|
|
142
|
511 "wc1: \"%V\" %ui", &name->key, dot);
|
|
138
|
512 #endif
|
|
|
513
|
|
142
|
514 dot_len = len + 1;
|
|
|
515
|
|
140
|
516 if (dot) {
|
|
|
517 len++;
|
|
|
518 }
|
|
|
519
|
|
138
|
520 next_names.nelts = 0;
|
|
|
521
|
|
|
522 if (names[n].key.len != len) {
|
|
|
523 next_name = ngx_array_push(&next_names);
|
|
|
524 if (next_name == NULL) {
|
|
|
525 return NGX_ERROR;
|
|
|
526 }
|
|
|
527
|
|
|
528 next_name->key.len = names[n].key.len - len;
|
|
|
529 next_name->key.data = names[n].key.data + len;
|
|
526
|
530 next_name->key_hash = 0;
|
|
138
|
531 next_name->value = names[n].value;
|
|
|
532
|
|
|
533 #if 0
|
|
|
534 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
|
|
|
535 "wc2: \"%V\"", &next_name->key);
|
|
|
536 #endif
|
|
|
537 }
|
|
|
538
|
|
|
539 for (i = n + 1; i < nelts; i++) {
|
|
|
540 if (ngx_strncmp(names[n].key.data, names[i].key.data, len) != 0) {
|
|
|
541 break;
|
|
|
542 }
|
|
|
543
|
|
142
|
544 if (!dot
|
|
|
545 && names[i].key.len > len
|
|
|
546 && names[i].key.data[len] != '.')
|
|
|
547 {
|
|
|
548 break;
|
|
|
549 }
|
|
|
550
|
|
138
|
551 next_name = ngx_array_push(&next_names);
|
|
|
552 if (next_name == NULL) {
|
|
|
553 return NGX_ERROR;
|
|
|
554 }
|
|
|
555
|
|
142
|
556 next_name->key.len = names[i].key.len - dot_len;
|
|
|
557 next_name->key.data = names[i].key.data + dot_len;
|
|
526
|
558 next_name->key_hash = 0;
|
|
138
|
559 next_name->value = names[i].value;
|
|
|
560
|
|
|
561 #if 0
|
|
|
562 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
|
|
140
|
563 "wc3: \"%V\"", &next_name->key);
|
|
138
|
564 #endif
|
|
|
565 }
|
|
|
566
|
|
|
567 if (next_names.nelts) {
|
|
142
|
568
|
|
138
|
569 h = *hinit;
|
|
|
570 h.hash = NULL;
|
|
|
571
|
|
|
572 if (ngx_hash_wildcard_init(&h, (ngx_hash_key_t *) next_names.elts,
|
|
|
573 next_names.nelts)
|
|
|
574 != NGX_OK)
|
|
|
575 {
|
|
|
576 return NGX_ERROR;
|
|
|
577 }
|
|
|
578
|
|
|
579 wdc = (ngx_hash_wildcard_t *) h.hash;
|
|
|
580
|
|
|
581 if (names[n].key.len == len) {
|
|
|
582 wdc->value = names[n].value;
|
|
|
583 }
|
|
|
584
|
|
446
|
585 name->value = (void *) ((uintptr_t) wdc | (dot ? 3 : 2));
|
|
394
|
586
|
|
|
587 } else if (dot) {
|
|
|
588 name->value = (void *) ((uintptr_t) name->value | 1);
|
|
138
|
589 }
|
|
|
590 }
|
|
|
591
|
|
|
592 if (ngx_hash_init(hinit, (ngx_hash_key_t *) curr_names.elts,
|
|
|
593 curr_names.nelts)
|
|
|
594 != NGX_OK)
|
|
|
595 {
|
|
|
596 return NGX_ERROR;
|
|
|
597 }
|
|
|
598
|
|
|
599 return NGX_OK;
|
|
|
600 }
|
|
|
601
|
|
|
602
|
|
|
603 ngx_uint_t
|
|
|
604 ngx_hash_key(u_char *data, size_t len)
|
|
|
605 {
|
|
|
606 ngx_uint_t i, key;
|
|
|
607
|
|
|
608 key = 0;
|
|
|
609
|
|
|
610 for (i = 0; i < len; i++) {
|
|
|
611 key = ngx_hash(key, data[i]);
|
|
|
612 }
|
|
|
613
|
|
|
614 return key;
|
|
|
615 }
|
|
|
616
|
|
|
617
|
|
|
618 ngx_uint_t
|
|
|
619 ngx_hash_key_lc(u_char *data, size_t len)
|
|
|
620 {
|
|
|
621 ngx_uint_t i, key;
|
|
|
622
|
|
|
623 key = 0;
|
|
|
624
|
|
|
625 for (i = 0; i < len; i++) {
|
|
|
626 key = ngx_hash(key, ngx_tolower(data[i]));
|
|
|
627 }
|
|
|
628
|
|
|
629 return key;
|
|
|
630 }
|
|
|
631
|
|
|
632
|
|
392
|
633 ngx_uint_t
|
|
|
634 ngx_hash_strlow(u_char *dst, u_char *src, size_t n)
|
|
|
635 {
|
|
|
636 ngx_uint_t key;
|
|
|
637
|
|
|
638 key = 0;
|
|
|
639
|
|
|
640 while (n--) {
|
|
|
641 *dst = ngx_tolower(*src);
|
|
|
642 key = ngx_hash(key, *dst);
|
|
|
643 dst++;
|
|
|
644 src++;
|
|
|
645 }
|
|
|
646
|
|
|
647 return key;
|
|
|
648 }
|
|
|
649
|
|
|
650
|
|
138
|
651 ngx_int_t
|
|
142
|
652 ngx_hash_keys_array_init(ngx_hash_keys_arrays_t *ha, ngx_uint_t type)
|
|
|
653 {
|
|
|
654 ngx_uint_t asize;
|
|
|
655
|
|
|
656 if (type == NGX_HASH_SMALL) {
|
|
|
657 asize = 4;
|
|
|
658 ha->hsize = 107;
|
|
|
659
|
|
|
660 } else {
|
|
|
661 asize = NGX_HASH_LARGE_ASIZE;
|
|
|
662 ha->hsize = NGX_HASH_LARGE_HSIZE;
|
|
|
663 }
|
|
|
664
|
|
|
665 if (ngx_array_init(&ha->keys, ha->temp_pool, asize, sizeof(ngx_hash_key_t))
|
|
|
666 != NGX_OK)
|
|
|
667 {
|
|
|
668 return NGX_ERROR;
|
|
|
669 }
|
|
|
670
|
|
312
|
671 if (ngx_array_init(&ha->dns_wc_head, ha->temp_pool, asize,
|
|
|
672 sizeof(ngx_hash_key_t))
|
|
|
673 != NGX_OK)
|
|
|
674 {
|
|
|
675 return NGX_ERROR;
|
|
|
676 }
|
|
|
677
|
|
|
678 if (ngx_array_init(&ha->dns_wc_tail, ha->temp_pool, asize,
|
|
142
|
679 sizeof(ngx_hash_key_t))
|
|
|
680 != NGX_OK)
|
|
|
681 {
|
|
|
682 return NGX_ERROR;
|
|
|
683 }
|
|
|
684
|
|
|
685 ha->keys_hash = ngx_pcalloc(ha->temp_pool, sizeof(ngx_array_t) * ha->hsize);
|
|
|
686 if (ha->keys_hash == NULL) {
|
|
|
687 return NGX_ERROR;
|
|
|
688 }
|
|
|
689
|
|
312
|
690 ha->dns_wc_head_hash = ngx_pcalloc(ha->temp_pool,
|
|
|
691 sizeof(ngx_array_t) * ha->hsize);
|
|
|
692 if (ha->dns_wc_head_hash == NULL) {
|
|
|
693 return NGX_ERROR;
|
|
|
694 }
|
|
|
695
|
|
|
696 ha->dns_wc_tail_hash = ngx_pcalloc(ha->temp_pool,
|
|
|
697 sizeof(ngx_array_t) * ha->hsize);
|
|
|
698 if (ha->dns_wc_tail_hash == NULL) {
|
|
142
|
699 return NGX_ERROR;
|
|
|
700 }
|
|
|
701
|
|
|
702 return NGX_OK;
|
|
|
703 }
|
|
|
704
|
|
|
705
|
|
|
706 ngx_int_t
|
|
|
707 ngx_hash_add_key(ngx_hash_keys_arrays_t *ha, ngx_str_t *key, void *value,
|
|
|
708 ngx_uint_t flags)
|
|
|
709 {
|
|
|
710 size_t len;
|
|
312
|
711 u_char *p;
|
|
142
|
712 ngx_str_t *name;
|
|
312
|
713 ngx_uint_t i, k, n, skip, last;
|
|
|
714 ngx_array_t *keys, *hwc;
|
|
142
|
715 ngx_hash_key_t *hk;
|
|
|
716
|
|
312
|
717 last = key->len;
|
|
|
718
|
|
|
719 if (flags & NGX_HASH_WILDCARD_KEY) {
|
|
142
|
720
|
|
312
|
721 /*
|
|
|
722 * supported wildcards:
|
|
|
723 * "*.example.com", ".example.com", and "www.example.*"
|
|
|
724 */
|
|
142
|
725
|
|
312
|
726 n = 0;
|
|
142
|
727
|
|
|
728 for (i = 0; i < key->len; i++) {
|
|
312
|
729
|
|
|
730 if (key->data[i] == '*') {
|
|
|
731 if (++n > 1) {
|
|
|
732 return NGX_DECLINED;
|
|
|
733 }
|
|
|
734 }
|
|
|
735
|
|
|
736 if (key->data[i] == '.' && key->data[i + 1] == '.') {
|
|
|
737 return NGX_DECLINED;
|
|
146
|
738 }
|
|
312
|
739 }
|
|
|
740
|
|
|
741 if (key->len > 1 && key->data[0] == '.') {
|
|
|
742 skip = 1;
|
|
|
743 goto wildcard;
|
|
|
744 }
|
|
|
745
|
|
|
746 if (key->len > 2) {
|
|
|
747
|
|
|
748 if (key->data[0] == '*' && key->data[1] == '.') {
|
|
|
749 skip = 2;
|
|
|
750 goto wildcard;
|
|
|
751 }
|
|
|
752
|
|
|
753 if (key->data[i - 2] == '.' && key->data[i - 1] == '*') {
|
|
|
754 skip = 0;
|
|
|
755 last -= 2;
|
|
|
756 goto wildcard;
|
|
|
757 }
|
|
142
|
758 }
|
|
|
759
|
|
312
|
760 if (n) {
|
|
|
761 return NGX_DECLINED;
|
|
|
762 }
|
|
|
763 }
|
|
|
764
|
|
|
765 /* exact hash */
|
|
|
766
|
|
|
767 k = 0;
|
|
|
768
|
|
|
769 for (i = 0; i < last; i++) {
|
|
|
770 if (!(flags & NGX_HASH_READONLY_KEY)) {
|
|
|
771 key->data[i] = ngx_tolower(key->data[i]);
|
|
|
772 }
|
|
|
773 k = ngx_hash(k, key->data[i]);
|
|
|
774 }
|
|
|
775
|
|
|
776 k %= ha->hsize;
|
|
|
777
|
|
|
778 /* check conflicts in exact hash */
|
|
|
779
|
|
|
780 name = ha->keys_hash[k].elts;
|
|
|
781
|
|
|
782 if (name) {
|
|
|
783 for (i = 0; i < ha->keys_hash[k].nelts; i++) {
|
|
|
784 if (last != name[i].len) {
|
|
|
785 continue;
|
|
|
786 }
|
|
|
787
|
|
|
788 if (ngx_strncmp(key->data, name[i].data, last) == 0) {
|
|
|
789 return NGX_BUSY;
|
|
|
790 }
|
|
|
791 }
|
|
142
|
792
|
|
312
|
793 } else {
|
|
|
794 if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
|
|
|
795 sizeof(ngx_str_t))
|
|
|
796 != NGX_OK)
|
|
|
797 {
|
|
|
798 return NGX_ERROR;
|
|
|
799 }
|
|
|
800 }
|
|
|
801
|
|
|
802 name = ngx_array_push(&ha->keys_hash[k]);
|
|
|
803 if (name == NULL) {
|
|
|
804 return NGX_ERROR;
|
|
|
805 }
|
|
|
806
|
|
|
807 *name = *key;
|
|
|
808
|
|
|
809 hk = ngx_array_push(&ha->keys);
|
|
|
810 if (hk == NULL) {
|
|
|
811 return NGX_ERROR;
|
|
|
812 }
|
|
|
813
|
|
|
814 hk->key = *key;
|
|
|
815 hk->key_hash = ngx_hash_key(key->data, last);
|
|
|
816 hk->value = value;
|
|
|
817
|
|
|
818 return NGX_OK;
|
|
|
819
|
|
|
820
|
|
|
821 wildcard:
|
|
|
822
|
|
|
823 /* wildcard hash */
|
|
|
824
|
|
392
|
825 k = ngx_hash_strlow(&key->data[skip], &key->data[skip], last - skip);
|
|
312
|
826
|
|
|
827 k %= ha->hsize;
|
|
|
828
|
|
|
829 if (skip == 1) {
|
|
|
830
|
|
|
831 /* check conflicts in exact hash for ".example.com" */
|
|
142
|
832
|
|
|
833 name = ha->keys_hash[k].elts;
|
|
|
834
|
|
|
835 if (name) {
|
|
312
|
836 len = last - skip;
|
|
|
837
|
|
142
|
838 for (i = 0; i < ha->keys_hash[k].nelts; i++) {
|
|
312
|
839 if (len != name[i].len) {
|
|
142
|
840 continue;
|
|
|
841 }
|
|
|
842
|
|
312
|
843 if (ngx_strncmp(&key->data[1], name[i].data, len) == 0) {
|
|
142
|
844 return NGX_BUSY;
|
|
|
845 }
|
|
|
846 }
|
|
|
847
|
|
|
848 } else {
|
|
|
849 if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
|
|
|
850 sizeof(ngx_str_t))
|
|
|
851 != NGX_OK)
|
|
|
852 {
|
|
|
853 return NGX_ERROR;
|
|
|
854 }
|
|
|
855 }
|
|
|
856
|
|
|
857 name = ngx_array_push(&ha->keys_hash[k]);
|
|
|
858 if (name == NULL) {
|
|
|
859 return NGX_ERROR;
|
|
|
860 }
|
|
|
861
|
|
312
|
862 name->len = last - 1;
|
|
382
|
863 name->data = ngx_pnalloc(ha->temp_pool, name->len);
|
|
312
|
864 if (name->data == NULL) {
|
|
142
|
865 return NGX_ERROR;
|
|
|
866 }
|
|
|
867
|
|
312
|
868 ngx_memcpy(name->data, &key->data[1], name->len);
|
|
|
869 }
|
|
142
|
870
|
|
|
871
|
|
312
|
872 if (skip) {
|
|
142
|
873
|
|
|
874 /*
|
|
|
875 * convert "*.example.com" to "com.example.\0"
|
|
|
876 * and ".example.com" to "com.example\0"
|
|
|
877 */
|
|
|
878
|
|
382
|
879 p = ngx_pnalloc(ha->temp_pool, last);
|
|
312
|
880 if (p == NULL) {
|
|
168
|
881 return NGX_ERROR;
|
|
|
882 }
|
|
|
883
|
|
142
|
884 len = 0;
|
|
|
885 n = 0;
|
|
|
886
|
|
312
|
887 for (i = last - 1; i; i--) {
|
|
142
|
888 if (key->data[i] == '.') {
|
|
312
|
889 ngx_memcpy(&p[n], &key->data[i + 1], len);
|
|
142
|
890 n += len;
|
|
312
|
891 p[n++] = '.';
|
|
142
|
892 len = 0;
|
|
|
893 continue;
|
|
|
894 }
|
|
|
895
|
|
|
896 len++;
|
|
|
897 }
|
|
|
898
|
|
|
899 if (len) {
|
|
312
|
900 ngx_memcpy(&p[n], &key->data[1], len);
|
|
142
|
901 n += len;
|
|
|
902 }
|
|
|
903
|
|
312
|
904 p[n] = '\0';
|
|
168
|
905
|
|
312
|
906 hwc = &ha->dns_wc_head;
|
|
|
907 keys = &ha->dns_wc_head_hash[k];
|
|
|
908
|
|
|
909 } else {
|
|
168
|
910
|
|
312
|
911 /* convert "www.example.*" to "www.example\0" */
|
|
168
|
912
|
|
312
|
913 last++;
|
|
|
914
|
|
382
|
915 p = ngx_pnalloc(ha->temp_pool, last);
|
|
330
|
916 if (p == NULL) {
|
|
|
917 return NGX_ERROR;
|
|
|
918 }
|
|
|
919
|
|
336
|
920 ngx_cpystrn(p, key->data, last);
|
|
330
|
921
|
|
312
|
922 hwc = &ha->dns_wc_tail;
|
|
|
923 keys = &ha->dns_wc_tail_hash[k];
|
|
|
924 }
|
|
142
|
925
|
|
|
926
|
|
312
|
927 /* check conflicts in wildcard hash */
|
|
|
928
|
|
|
929 name = keys->elts;
|
|
142
|
930
|
|
312
|
931 if (name) {
|
|
|
932 len = last - skip;
|
|
|
933
|
|
|
934 for (i = 0; i < keys->nelts; i++) {
|
|
|
935 if (len != name[i].len) {
|
|
|
936 continue;
|
|
142
|
937 }
|
|
|
938
|
|
312
|
939 if (ngx_strncmp(key->data + skip, name[i].data, len) == 0) {
|
|
|
940 return NGX_BUSY;
|
|
142
|
941 }
|
|
|
942 }
|
|
|
943
|
|
312
|
944 } else {
|
|
|
945 if (ngx_array_init(keys, ha->temp_pool, 4, sizeof(ngx_str_t)) != NGX_OK)
|
|
|
946 {
|
|
142
|
947 return NGX_ERROR;
|
|
|
948 }
|
|
312
|
949 }
|
|
142
|
950
|
|
312
|
951 name = ngx_array_push(keys);
|
|
|
952 if (name == NULL) {
|
|
|
953 return NGX_ERROR;
|
|
|
954 }
|
|
168
|
955
|
|
312
|
956 name->len = last - skip;
|
|
382
|
957 name->data = ngx_pnalloc(ha->temp_pool, name->len);
|
|
312
|
958 if (name->data == NULL) {
|
|
|
959 return NGX_ERROR;
|
|
142
|
960 }
|
|
|
961
|
|
312
|
962 ngx_memcpy(name->data, key->data + skip, name->len);
|
|
|
963
|
|
678
|
964
|
|
|
965 /* add to wildcard hash */
|
|
|
966
|
|
|
967 hk = ngx_array_push(hwc);
|
|
|
968 if (hk == NULL) {
|
|
|
969 return NGX_ERROR;
|
|
|
970 }
|
|
|
971
|
|
|
972 hk->key.len = last - 1;
|
|
|
973 hk->key.data = p;
|
|
|
974 hk->key_hash = 0;
|
|
|
975 hk->value = value;
|
|
|
976
|
|
142
|
977 return NGX_OK;
|
|
|
978 }
|
