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

Contents of /hydra/src/hash.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.4 - (show annotations)
Mon Oct 21 20:33:31 2002 UTC (19 years, 1 month ago) by nmav
Branch: MAIN
CVS Tags: hydra_0_1_6_without_hic, hydra_0_0_10, hydra_0_0_8, hydra_0_0_9, hydra_0_1_3, hydra_0_1_2, hydra_0_1_1, hydra_0_1_0, hydra_0_1_7, hydra_0_1_6, hydra_0_1_4, hydra_0_1_8, HEAD
Branch point for: hydra_0_1_0_patches
Changes since 1.3: +186 -146 lines
File MIME type: text/plain
Removed some optimizations from Boa, that made the code harder
to read. Added the hash.c from Boa.

1 /*
2 * Boa, 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.14.4.7 2002/09/23 03:44:08 jnelson Exp $*/
24
25 #include "boa.h"
26 #include "parse.h"
27
28 #define DEBUG if
29 #define DEBUG_HASH 0
30
31 /*
32 * There are two hash tables used, each with a key/value pair
33 * stored in a hash_struct. They are:
34 *
35 * mime_hashtable:
36 * key = file extension
37 * value = mime type
38 *
39 * passwd_hashtable:
40 * key = username
41 * value = home directory
42 *
43 */
44
45 struct _hash_struct_ {
46 char *key;
47 char *value;
48 struct _hash_struct_ *next;
49 };
50
51 typedef struct _hash_struct_ hash_struct;
52
53 static hash_struct *mime_hashtable[MIME_HASHTABLE_SIZE];
54 static hash_struct *passwd_hashtable[PASSWD_HASHTABLE_SIZE];
55
56 #ifdef WANT_ICKY_HASH
57 static unsigned four_char_hash(const char *buf);
58 #define boa_hash four_char_hash
59 #else
60 #ifdef WANT_SDBM_HASH
61 static unsigned sdbm_hash(const char *str);
62 #define boa_hash sdbm_hash
63 #else
64 #ifdef WANT_DJB2_HASH
65 static unsigned djb2_hash(const char *str);
66 #define boa_hash djb2_hash
67 #else
68 static unsigned fnv1a_hash(const char *str);
69 #define boa_hash fnv1a_hash
70 #endif
71 #endif
72 #endif
73
74 #ifdef WANT_ICKY_HASH
75 static unsigned four_char_hash(const char *buf)
76 {
77 unsigned int hash = (buf[0] +
78 (buf[1] ? buf[1] : 241 +
79 (buf[2] ? buf[2] : 251 +
80 (buf[3] ? buf[3] : 257))));
81 DEBUG(DEBUG_HASH) {
82 log_error_time();
83 fprintf(stderr, "four_char_hash(%s) = %u\n", buf, hash);
84 }
85 return hash;
86 }
87
88 /* The next two hashes taken from
89 * http://www.cs.yorku.ca/~oz/hash.html
90 *
91 * In my (admittedly) very brief testing, djb2_hash performed
92 * very slightly better than sdbm_hash.
93 */
94
95 #else
96 #define MAX_HASH_LENGTH 4
97 #ifdef WANT_SDBM_HASH
98 static unsigned sdbm_hash(const char *str)
99 {
100 unsigned hash = 0;
101 int c;
102 short count = MAX_HASH_LENGTH;
103
104 DEBUG(DEBUG_HASH) {
105 log_error_time();
106 fprintf(stderr, "sdbm_hash(%s) = ", str);
107 }
108
109 while ((c = *str++) && count--)
110 hash = c + (hash << 6) + (hash << 16) - hash;
111
112 DEBUG(DEBUG_HASH) {
113 fprintf(stderr, "%u\n", hash);
114 }
115 return hash;
116 }
117 #else
118 #ifdef WANT_DJB2_HASH
119 static unsigned djb2_hash(const char *str)
120 {
121 unsigned hash = 5381;
122 int c;
123 short count = MAX_HASH_LENGTH;
124
125 DEBUG(DEBUG_HASH) {
126 log_error_time();
127 fprintf(stderr, "djb2_hash(%s) = ", str);
128 }
129
130 while ((c = *(str++)) && count--)
131 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
132
133 DEBUG(DEBUG_HASH) {
134 fprintf(stderr, "%u\n", hash);
135 }
136 return hash;
137 }
138 #else
139 /*
140 * magic 32 bit FNV1a hash constants
141 *
142 * See: http://www.isthe.com/chongo/tech/comp/fnv/index.html
143 */
144 #define OFFSET_BASIS 2166136261U
145 #define FNV_PRIME 16777619U
146 static unsigned fnv1a_hash(const char *str)
147 {
148 unsigned int hash = OFFSET_BASIS;
149 short count = MAX_HASH_LENGTH;
150
151 /*
152 * compute FNV1a hash of the first file component
153 */
154 do {
155 hash ^= *str++;
156 hash *= FNV_PRIME;
157 } while (*str != '\0' && count--);
158
159 return hash;
160 }
161
162 #endif
163 #endif
164 #endif
165
166 /*
167 * Name: hash_insert
168 * Description: Adds a key/value pair to the provided hashtable
169 */
170
171 static
172 hash_struct *hash_insert(hash_struct *table[], unsigned int hash, char *key, char *value)
173 {
174 hash_struct *current, *trailer;
175
176 if (!key) {
177 log_error_time();
178 fprintf(stderr, "Yipes! Null value sent as key to hash_insert!\n");
179 return NULL;
180 }
181
182 /* should we bother to check table, hash, and key for NULL/0 ? */
183
184 DEBUG(DEBUG_HASH)
185 fprintf(stderr,
186 "Adding key \"%s\" for value \"%s\" (hash=%d)\n",
187 key, value, hash);
188
189 current = table[hash];
190 while (current) {
191 if (!strcmp(current->key, key))
192 return current; /* don't add extension twice */
193 if (current->next)
194 current = current->next;
195 else
196 break;
197 }
198
199 /* not found */
200 trailer = (hash_struct *) malloc(sizeof (hash_struct));
201 if (trailer == NULL) {
202 WARN("unable to allocate memory for hash_insert");
203 return NULL;
204 }
205
206 trailer->key = strdup(key);
207 trailer->value = strdup(value);
208 trailer->next = NULL;
209
210 if (trailer->key == NULL || trailer->value == NULL) {
211 free(trailer);
212 if (trailer->key)
213 free(trailer->key);
214 if (trailer->value)
215 free(trailer->value);
216 WARN("allocated key or value is NULL");
217 return NULL;
218 }
219
220 /* successfully allocated and built new hash structure */
221 if (!current) {
222 /* no entries for this hash value */
223 table[hash] = trailer;
224 } else {
225 current->next = trailer;
226 }
227
228 return trailer;
229 }
230
231 static
232 hash_struct *find_in_hash(hash_struct *table[], char *key, unsigned int hash)
233 {
234 hash_struct *current;
235
236 current = table[hash];
237
238 while (current) {
239 if (!strcmp(current->key, key)) /* hit */
240 return current;
241 current = current->next;
242 }
243
244 return NULL;
245 }
246
247 /*
248 * Name: add_mime_type
249 * Description: Adds a key/value pair to the mime_hashtable
250 */
251
252 void add_mime_type(char *extension, char *type)
253 {
254 unsigned int hash;
255
256 if (!extension || extension[0] == '\0') {
257 log_error_time();
258 fprintf(stderr, "Yipes! Null value sent as key to add_mime_type!\n");
259 return;
260 }
261
262 hash = get_mime_hash_value(extension);
263 hash_insert(mime_hashtable, hash, extension, type);
264 }
265
266 /*
267 * Name: get_mime_hash_value
268 *
269 * Description: adds the ASCII values of the file extension letters
270 * and mods by the hashtable size to get the hash value
271 */
272
273 unsigned get_mime_hash_value(char *extension)
274 {
275 if (extension == NULL || extension[0] == '\0') {
276 /* FIXME */
277 log_error_time();
278 fprintf(stderr, "Attempt to hash NULL or empty string! [get_mime_hash_value]!\n");
279 return 0;
280 }
281
282 return boa_hash(extension) % MIME_HASHTABLE_SIZE;
283 }
284
285 /*
286 * Name: get_mime_type
287 *
288 * Description: Returns the mime type for a supplied filename.
289 * Returns default type if not found.
290 */
291
292 char *get_mime_type(const char *filename)
293 {
294 char *extension;
295 hash_struct *current;
296
297 unsigned int hash;
298
299 extension = strrchr(filename, '.');
300
301 /* remember, extension points to the *last* '.' in the filename,
302 * which may be NULL or look like:
303 * foo.bar
304 * foo. (in which case extension[1] == '\0')
305 */
306 if (!extension || extension[1] == '\0')
307 return default_type;
308
309 /* make sure we hash on the 'bar' not the '.bar' */
310 ++extension;
311
312 hash = get_mime_hash_value(extension);
313 current = find_in_hash(mime_hashtable, extension, hash);
314 return (current ? current->value : default_type);
315 }
316
317 /*
318 * Name: get_homedir_hash_value
319 *
320 * Description: adds the ASCII values of the username letters
321 * and mods by the hashtable size to get the hash value
322 */
323
324 unsigned get_homedir_hash_value(char *name)
325 {
326 unsigned int hash = 0;
327
328 if (name == NULL || name[0] == '\0') {
329 /* FIXME */
330 log_error_time();
331 fprintf(stderr, "Attempt to hash NULL or empty string! [get_homedir_hash_value]\n");
332 return 0;
333 }
334
335 hash = boa_hash(name) % PASSWD_HASHTABLE_SIZE;
336
337 return hash;
338 }
339
340
341 /*
342 * Name: get_home_dir
343 *
344 * Description: Returns a point to the supplied user's home directory.
345 * Adds to the hashtable if it's not already present.
346 *
347 */
348
349 char *get_home_dir(char *name)
350 {
351 hash_struct *current;
352
353 unsigned int hash;
354
355 hash = get_homedir_hash_value(name);
356
357 current = find_in_hash(passwd_hashtable, name, hash);
358
359 if (!current) {
360 /* not found */
361 struct passwd *passwdbuf;
362
363 passwdbuf = getpwnam(name);
364
365 if (!passwdbuf) /* does not exist */
366 return NULL;
367
368 current = hash_insert(passwd_hashtable, hash, name, passwdbuf->pw_dir);
369 }
370
371 return (current ? current->value : NULL);
372 }
373
374 static
375 void clear_hashtable(hash_struct *table[], int size)
376 {
377 int i;
378 hash_struct *temp;
379 for (i = 0; i < size; ++i) { /* these limits OK? */
380 temp = table[i];
381 while (temp) {
382 hash_struct *temp_next;
383
384 temp_next = temp->next;
385 free(temp->key);
386 free(temp->value);
387 free(temp);
388
389 temp = temp_next;
390 }
391 table[i] = NULL;
392 }
393 }
394
395 void dump_mime(void)
396 {
397 clear_hashtable(mime_hashtable, MIME_HASHTABLE_SIZE);
398 }
399
400 void dump_passwd(void)
401 {
402 clear_hashtable(passwd_hashtable, PASSWD_HASHTABLE_SIZE);
403 }
404
405 void show_hash_stats(void)
406 {
407 int i;
408 hash_struct *temp;
409 int total = 0;
410 int count;
411
412 log_error_time();
413 fprintf(stderr, "mmap_hashtable has %d entries\n", mmap_list_entries_used);
414
415 for (i = 0; i < MIME_HASHTABLE_SIZE; ++i) { /* these limits OK? */
416 if (mime_hashtable[i]) {
417 count = 0;
418 temp = mime_hashtable[i];
419 while (temp) {
420 temp = temp->next;
421 ++count;
422 }
423 #ifdef NOISY_SIGALRM
424 log_error_time();
425 fprintf(stderr, "mime_hashtable[%d] has %d entries\n",
426 i, count);
427 #endif
428 total += count;
429 }
430 }
431 log_error_time();
432 fprintf(stderr, "mime_hashtable has %d total entries\n", total);
433
434 total = 0;
435 for (i = 0; i < PASSWD_HASHTABLE_SIZE; ++i) { /* these limits OK? */
436 if (passwd_hashtable[i]) {
437 temp = passwd_hashtable[i];
438 count = 0;
439 while (temp) {
440 temp = temp->next;
441 ++count;
442 }
443 #ifdef NOISY_SIGALRM
444 log_error_time();
445 fprintf(stderr, "passwd_hashtable[%d] has %d entries\n",
446 i, count);
447 #endif
448 total += count;
449 }
450 }
451
452 log_error_time();
453 fprintf(stderr, "passwd_hashtable has %d total entries\n",
454 total);
455
456 }

webmaster@linux.gr
ViewVC Help
Powered by ViewVC 1.1.26