|
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 {
|
|
|
50 key = 0;
|
|
|
51
|
|
58
|
52 for (i = 0; i < name->len; i++) {
|
|
|
53 key += ngx_tolower(name->data[i]);
|
|
56
|
54 }
|
|
|
55
|
|
|
56 key %= size;
|
|
|
57
|
|
|
58 if (test[key] == hash->bucket_limit) {
|
|
|
59 break;
|
|
|
60 }
|
|
|
61
|
|
|
62 test[key]++;
|
|
|
63
|
|
|
64 if (buckets < test[key]) {
|
|
|
65 buckets = test[key];
|
|
|
66 }
|
|
|
67 }
|
|
|
68
|
|
58
|
69 if (n == nelts) {
|
|
56
|
70 if (min_buckets > buckets) {
|
|
|
71 min_buckets = buckets;
|
|
|
72 best = size;
|
|
|
73 }
|
|
|
74
|
|
|
75 if (hash->bucket_limit == 1) {
|
|
|
76 break;
|
|
|
77 }
|
|
|
78 }
|
|
|
79 }
|
|
|
80
|
|
|
81 if (min_buckets == hash->bucket_limit + 1) {
|
|
|
82 ngx_log_error(NGX_LOG_EMERG, pool->log, 0,
|
|
|
83 "could not build the %s hash, you should increase "
|
|
|
84 "either %s_size: %i or %s_bucket_limit: %i",
|
|
|
85 hash->name, hash->name, hash->max_size,
|
|
|
86 hash->name, hash->bucket_limit);
|
|
|
87 ngx_free(test);
|
|
|
88 return NGX_ERROR;
|
|
|
89 }
|
|
|
90
|
|
|
91 hash->buckets = ngx_pcalloc(pool, best * hash->bucket_size);
|
|
|
92 if (hash->buckets == NULL) {
|
|
|
93 ngx_free(test);
|
|
|
94 return NGX_ERROR;
|
|
|
95 }
|
|
|
96
|
|
|
97 if (hash->bucket_limit != 1) {
|
|
|
98
|
|
|
99 for (i = 0; i < best; i++) {
|
|
|
100 test[i] = 0;
|
|
|
101 }
|
|
|
102
|
|
58
|
103 for (n = 0, name = (ngx_str_t *) names;
|
|
|
104 n < nelts;
|
|
|
105 n++, name = (ngx_str_t *) ((char *) name + hash->bucket_size))
|
|
56
|
106 {
|
|
|
107 key = 0;
|
|
|
108
|
|
58
|
109 for (i = 0; i < name->len; i++) {
|
|
|
110 key += ngx_tolower(name->data[i]);
|
|
56
|
111 }
|
|
|
112
|
|
|
113 key %= best;
|
|
|
114
|
|
|
115 test[key]++;
|
|
|
116 }
|
|
|
117
|
|
|
118 for (i = 0; i < best; i++) {
|
|
|
119 if (test[i] == 0) {
|
|
|
120 continue;
|
|
|
121 }
|
|
|
122
|
|
|
123 bucket = ngx_palloc(pool, test[i] * hash->bucket_size);
|
|
|
124 if (bucket == NULL) {
|
|
|
125 ngx_free(test);
|
|
|
126 return NGX_ERROR;
|
|
|
127 }
|
|
|
128
|
|
|
129 hash->buckets[i] = bucket;
|
|
|
130 bucket->len = 0;
|
|
|
131 }
|
|
|
132 }
|
|
|
133
|
|
58
|
134 for (n = 0, name = (ngx_str_t *) names;
|
|
|
135 n < nelts;
|
|
|
136 n++, name = (ngx_str_t *) ((char *) name + hash->bucket_size))
|
|
56
|
137 {
|
|
|
138 key = 0;
|
|
|
139
|
|
58
|
140 for (i = 0; i < name->len; i++) {
|
|
|
141 key += ngx_tolower(name->data[i]);
|
|
56
|
142 }
|
|
|
143
|
|
|
144 key %= best;
|
|
|
145
|
|
|
146 if (hash->bucket_limit == 1) {
|
|
|
147 p = (u_char *) hash->buckets + key * hash->bucket_size;
|
|
58
|
148 ngx_memcpy(p, name, hash->bucket_size);
|
|
56
|
149 continue;
|
|
|
150 }
|
|
|
151
|
|
|
152 for (bucket = hash->buckets[key];
|
|
|
153 bucket->len;
|
|
|
154 bucket = (ngx_str_t *) ((char *) bucket + hash->bucket_size))
|
|
|
155 {
|
|
|
156 bucket->len &= 0x7fffffff;
|
|
|
157 }
|
|
|
158
|
|
58
|
159 ngx_memcpy(bucket, name, hash->bucket_size);
|
|
56
|
160 bucket->len |= 0x80000000;
|
|
|
161 }
|
|
|
162
|
|
|
163 ngx_free(test);
|
|
|
164
|
|
|
165 hash->hash_size = best;
|
|
|
166 hash->min_buckets = min_buckets;
|
|
|
167
|
|
|
168 return NGX_OK;
|
|
|
169 }
|
