Mercurial > hg > nginx
comparison src/core/ngx_hash.c @ 507:cd3117ad9aab release-0.1.28
nginx-0.1.28-RELEASE import
*) Bugfix: nginx hogs CPU while proxying the huge files.
*) Bugfix: nginx could not be built by gcc 4.0 on Linux.
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Fri, 08 Apr 2005 15:18:55 +0000 |
parents | |
children | 9b8c906f6e63 |
comparison
equal
deleted
inserted
replaced
506:005e65646622 | 507:cd3117ad9aab |
---|---|
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 } |