root/trunk/hash.c

Revision 18, 1.9 kB (checked in by george, 13 years ago)

fixed hash function

  • Property svn:eol-style set to native
  • Property svn:executable set to *
  • Property svn:keywords set to Author Date Id Revision
Line 
1 /* ======================================================================
2  * Copyright (c) 2000 George Schlossnagle
3  * All rights reserved.
4  * The following code was written by George Schlossnagle <george@lethargy.org>
5  * This code was written to facilitate clustered logging via Spread,
6  * particularly in conjunction with the mod_log_spread module for Apache.
7  * More information on Spread can be found at http://www.spread.org/
8  * More information on mod_log_spread can be found at
9  * http://www.backhand.org/mod_log_spread/
10  * Please refer to the LICENSE file before using this software.
11  * ======================================================================
12 */
13
14 #include <stdlib.h>
15 #include <stdio.h>
16 #include <string.h>
17
18 #include "hash.h"
19
20 extern int nr_open;
21 static int myprime[20] = {
22         3,5,7,11,13,17,23,31,37,41,43,47,53,59,61,67,71,73,83,87
23 };
24
25 int gethash(void *hostheader, hash_element *hash) {
26   int a, i;
27   hash_element *elem;
28   a = hashpjw(hostheader,nr_open);
29   if(hash[a].fd == -1) return -1;  /* return -1 if element is not here */
30   for(i=0;i<nr_open; i++) {
31     elem = &hash[(a+(i*myprime[a%20]))%nr_open];
32     /* return -1 if element is not possibly in hsah*/
33     if (elem->fd == -1)
34       return -1;
35     /*return fd if the element matches */
36     if(!strcmp(hostheader,elem->hostheader))
37       return elem->fd;
38   }
39   return -1;
40 }
41
42 void inshash(hash_element b, hash_element *hash) {
43   int a, i;
44   a = hashpjw(b.hostheader,nr_open);
45   for(i=0;i<nr_open; i++)
46     if((hash[(a+(i*myprime[a%20]))%nr_open].fd) == -1) {
47       hash[(a+(i*myprime[a%20]))%nr_open] = b;
48       return;
49     }
50 }
51
52 int hashpjw(const void *key, const int size) {
53   const char *ptr;
54   unsigned int val = 0;
55   ptr = key;
56   while (*ptr != '\0') {
57     int tmp;
58         val = ((val << 1) + ((*ptr)*31 >> 5)) >> 1;
59     if ((tmp = (val & 0xf0000000)) != 0) {
60       val = val ^ (tmp >> 24);
61       val = val ^ tmp;
62     }
63     ptr++;
64   }
65   return (int) (val % size);
66 }
67
Note: See TracBrowser for help on using the browser.