/[hydra]/hydra/src/hash.c
ViewVC logotype

Contents of /hydra/src/hash.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.3 - (show annotations)
Sat Sep 28 16:32:37 2002 UTC (21 years, 6 months ago) by nmav
Branch: MAIN
CVS Tags: hydra_0_0_3, hydra_0_0_6, hydra_0_0_7, hydra_0_0_4, hydra_0_0_5
Changes since 1.2: +2 -2 lines
File MIME type: text/plain
In sighup and sigterm, the HIC thread is terminated as well.

1 /*
2 * Hydra, an http server
3 * Copyright (C) 1995 Paul Phillips <paulp@go2net.com>
4 * Some changes Copyright (C) 1996 Larry Doolittle <ldoolitt@boa.org>
5 * Some changes Copyright (C) 1997 Jon Nelson <jnelson@boa.org>
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 1, or (at your option)
10 * any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20 *
21 */
22
23 /* $Id: hash.c,v 1.2 2002/09/28 16:04:01 nmav Exp $*/
24
25 #include "boa.h"
26 #include "parse.h"
27
28 /*
29 * There are two hash tables used, each with a key/value pair
30 * stored in a hash_struct. They are:
31 *
32 * mime_hashtable:
33 * key = file extension
34 * value = mime type
35 *
36 * passwd_hashtable:
37 * key = username
38 * value = home directory
39 *
40 */
41
42 struct _hash_struct_ {
43 char *key;
44 char *value;
45 struct _hash_struct_ *next;
46 };
47
48 typedef struct _hash_struct_ hash_struct;
49
50 static hash_struct *mime_hashtable[MIME_HASHTABLE_SIZE];
51 static hash_struct *passwd_hashtable[PASSWD_HASHTABLE_SIZE];
52
53 #ifdef WANT_ICKY_HASH
54 static unsigned four_char_hash(char *buf);
55 #define boa_hash four_char_hash
56 #else
57 #ifdef WANT_SDBM_HASH
58 static unsigned sdbm_hash(char *str);
59 #define boa_hash sdbm_hash
60 #else
61 static unsigned djb2_hash(char *str);
62 #define boa_hash djb2_hash
63 #endif
64 #endif
65
66 #ifdef WANT_ICKY_HASH
67 static unsigned four_char_hash(char *buf)
68 {
69 unsigned int hash = (buf[0] +
70 (buf[1] ? buf[1] : 241 +
71 (buf[2] ? buf[2] : 251 +
72 (buf[3] ? buf[3] : 257))));
73 #ifdef DEBUG_HASH
74 log_error_time();
75 fprintf(stderr, "four_char_hash(%s) = %u\n", buf, hash);
76 #endif
77 return hash;
78 }
79
80 /* The next two hashes taken from
81 * http://www.cs.yorku.ca/~oz/hash.html
82 *
83 * In my (admittedly) very brief testing, djb2_hash performed
84 * very slightly better than sdbm_hash.
85 */
86
87 #else
88 #define MAX_HASH_LENGTH 4
89 #ifdef WANT_SDBM_HASH
90 static unsigned sdbm_hash(char *str)
91 {
92 unsigned hash = 0;
93 int c;
94 short count = MAX_HASH_LENGTH;
95
96 #ifdef DEBUG_HASH
97 log_error_time();
98 fprintf(stderr, "sdbm_hash(%s) = ", str);
99 #endif
100
101 while ((c = *str++) && count--)
102 hash = c + (hash << 6) + (hash << 16) - hash;
103
104 #ifdef DEBUG_HASH
105 fprintf(stderr, "%u\n", hash);
106 #endif
107 return hash;
108 }
109 #else
110
111 static unsigned djb2_hash(char *str)
112 {
113 unsigned hash = 5381;
114 int c;
115 short count = MAX_HASH_LENGTH;
116
117 #ifdef DEBUG_HASH
118 log_error_time();
119 fprintf(stderr, "djb2_hash(%s) = ", str);
120 #endif
121
122 while ((c = *(str++)) && count--)
123 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
124
125 #ifdef DEBUG_HASH
126 fprintf(stderr, "%u\n", hash);
127 #endif
128 return hash;
129 }
130 #endif
131 #endif
132
133 /*
134 * Name: add_mime_type
135 * Description: Adds a key/value pair to the mime_hashtable
136 */
137
138 void add_mime_type(char *extension, char *type)
139 {
140 unsigned int hash;
141 hash_struct *current, *next;
142
143 if (!extension)
144 return;
145
146 hash = get_mime_hash_value(extension);
147
148 current = mime_hashtable[hash];
149
150 while (current) {
151 if (!strcmp(current->key, extension))
152 return; /* don't add extension twice */
153 if (current->next)
154 current = current->next;
155 else
156 break;
157 }
158
159 /* if here, we need to add a new one */
160 next = (hash_struct *) malloc(sizeof (hash_struct));
161 if (!next) {
162 DIE("malloc of hash_struct failed!");
163 }
164 next->key = strdup(extension);
165 if (!next->key)
166 DIE("malloc of hash_struct->key failed!");
167 next->value = strdup(type);
168 if (!next->value)
169 DIE("malloc of hash_struct->value failed!");
170 next->next = NULL;
171
172 if (!current) {
173 mime_hashtable[hash] = next;
174 } else {
175 current->next = next;
176 }
177 }
178
179 /*
180 * Name: get_mime_hash_value
181 *
182 * Description: adds the ASCII values of the file extension letters
183 * and mods by the hashtable size to get the hash value
184 */
185
186 unsigned get_mime_hash_value(char *extension)
187 {
188 unsigned int hash = 0;
189
190 if (extension == NULL || extension[0] == '\0') {
191 /* FIXME */
192 log_error_time();
193 fprintf(stderr, "Attempt to hash NULL or empty string!\n");
194 return 0;
195 }
196
197 hash = boa_hash(extension);
198 hash %= MIME_HASHTABLE_SIZE;
199
200 return hash;
201 }
202
203 /*
204 * Name: get_mime_type
205 *
206 * Description: Returns the mime type for a supplied filename.
207 * Returns default type if not found.
208 */
209
210 char *get_mime_type(const char *filename)
211 {
212 char *extension;
213 hash_struct *current;
214
215 unsigned int hash;
216
217 extension = strrchr(filename, '.');
218
219 if (!extension || *extension++ == '\0')
220 return default_type;
221
222 hash = get_mime_hash_value(extension);
223 current = mime_hashtable[hash];
224
225 while (current) {
226 if (!strcmp(current->key, extension)) /* hit */
227 return current->value;
228 current = current->next;
229 }
230
231 return default_type;
232 }
233
234 /*
235 * Name: get_homedir_hash_value
236 *
237 * Description: adds the ASCII values of the username letters
238 * and mods by the hashtable size to get the hash value
239 */
240
241 unsigned get_homedir_hash_value(char *name)
242 {
243 unsigned int hash = 0;
244
245 if (name == NULL || name[0] == '\0') {
246 /* FIXME */
247 log_error_time();
248 fprintf(stderr, "Attempt to hash NULL or empty string!\n");
249 return 0;
250 }
251
252 hash = boa_hash(name);
253 hash %= PASSWD_HASHTABLE_SIZE;
254
255 return hash;
256 }
257
258
259 /*
260 * Name: get_home_dir
261 *
262 * Description: Returns a point to the supplied user's home directory.
263 * Adds to the hashtable if it's not already present.
264 *
265 */
266
267 char *get_home_dir(char *name)
268 {
269 struct passwd *passwdbuf;
270
271 hash_struct *current, *next;
272 unsigned int hash;
273
274 /* first check hash table -- if username is less than four characters,
275 just hash to zero (this should be very rare) */
276
277 hash = get_homedir_hash_value(name);
278
279 for(current = passwd_hashtable[hash];current;current = current->next) {
280 if (!strcmp(current->key, name)) /* hit */
281 return current->value;
282 if (!current->next)
283 break;
284 }
285
286 /* if here, we have to add a new one */
287
288 passwdbuf = getpwnam(name);
289
290 if (!passwdbuf) /* does not exist */
291 return NULL;
292
293 next = (hash_struct *) malloc(sizeof (hash_struct));
294 if (!next) {
295 WARN("malloc of hash_struct for passwd_hashtable failed!");
296 return NULL;
297 }
298
299 next->key = strdup(name);
300 if (!next->key) {
301 WARN("malloc of passwd_hashtable[hash]->key failed!");
302 free(next);
303 return NULL;
304 }
305 next->value = strdup(passwdbuf->pw_dir);
306 if (!next->value) {
307 WARN("malloc of passwd_hashtable[hash]->value failed!");
308 free(next->key);
309 free(next);
310 return NULL;
311 }
312 next->next = NULL;
313
314 if (!current) {
315 passwd_hashtable[hash] = next;
316 } else {
317 current->next = next;
318 }
319 return next->value;
320 }
321
322 void dump_mime(void)
323 {
324 int i;
325 hash_struct *temp;
326 for (i = 0; i < MIME_HASHTABLE_SIZE; ++i) { /* these limits OK? */
327 temp = mime_hashtable[i];
328 while (temp) {
329 hash_struct *temp_next;
330
331 temp_next = temp->next;
332 free(temp->key);
333 free(temp->value);
334 free(temp);
335
336 temp = temp_next;
337 }
338 mime_hashtable[i] = NULL;
339 }
340 }
341
342 void dump_passwd(void)
343 {
344 int i;
345 hash_struct *temp;
346 for (i = 0; i < PASSWD_HASHTABLE_SIZE; ++i) { /* these limits OK? */
347 temp = passwd_hashtable[i];
348 while (temp) {
349 hash_struct *temp_next;
350
351 temp_next = temp->next;
352 free(temp->key);
353 free(temp->value);
354 free(temp);
355
356 temp = temp_next;
357 }
358 passwd_hashtable[i] = NULL;
359 }
360 }
361
362 extern int mmap_list_entries_used;
363
364 void show_hash_stats(void)
365 {
366 int i;
367 hash_struct *temp;
368 int total = 0;
369 int count;
370
371 log_error_time();
372 fprintf(stderr, "mmap_hashtable has %d entries\n", mmap_list_entries_used);
373
374 for (i = 0; i < MIME_HASHTABLE_SIZE; ++i) { /* these limits OK? */
375 if (mime_hashtable[i]) {
376 count = 0;
377 temp = mime_hashtable[i];
378 while (temp) {
379 temp = temp->next;
380 ++count;
381 }
382 #ifdef NOISY_SIGALRM
383 log_error_time();
384 fprintf(stderr, "mime_hashtable[%d] has %d entries\n",
385 i, count);
386 #endif
387 total += count;
388 }
389 }
390 log_error_time();
391 fprintf(stderr, "mime_hashtable has %d total entries\n",
392 total);
393
394 total = 0;
395 for (i = 0; i < PASSWD_HASHTABLE_SIZE; ++i) { /* these limits OK? */
396 if (passwd_hashtable[i]) {
397 temp = passwd_hashtable[i];
398 count = 0;
399 while (temp) {
400 temp = temp->next;
401 ++count;
402 }
403 #ifdef NOISY_SIGALRM
404 log_error_time();
405 fprintf(stderr, "passwd_hashtable[%d] has %d entries\n",
406 i, count);
407 #endif
408 total += count;
409 }
410 }
411
412 log_error_time();
413 fprintf(stderr, "passwd_hashtable has %d total entries\n",
414 total);
415
416 }

webmaster@linux.gr
ViewVC Help
Powered by ViewVC 1.1.26