Mercurial > hg > nginx

comparison src/core/ngx_hash.c @ 507:cd3117ad9aab release-0.1.28

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }