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

Diff of /hydra/src/hash.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1.3 by nmav, Sat Sep 28 16:32:37 2002 UTC revision 1.4 by nmav, Mon Oct 21 20:33:31 2002 UTC
# Line 1  Line 1 
1  /*  /*
2   *  Hydra, an http server   *  Boa, an http server
3   *  Copyright (C) 1995 Paul Phillips <paulp@go2net.com>   *  Copyright (C) 1995 Paul Phillips <paulp@go2net.com>
4   *  Some changes Copyright (C) 1996 Larry Doolittle <ldoolitt@boa.org>   *  Some changes Copyright (C) 1996 Larry Doolittle <ldoolitt@boa.org>
5   *  Some changes Copyright (C) 1997 Jon Nelson <jnelson@boa.org>   *  Some changes Copyright (C) 1997 Jon Nelson <jnelson@boa.org>
# Line 25  Line 25 
25  #include "boa.h"  #include "boa.h"
26  #include "parse.h"  #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   * There are two hash tables used, each with a key/value pair
33   * stored in a hash_struct.  They are:   * stored in a hash_struct.  They are:
# Line 51  static hash_struct *mime_hashtable[MIME_ Line 54  static hash_struct *mime_hashtable[MIME_
54  static hash_struct *passwd_hashtable[PASSWD_HASHTABLE_SIZE];  static hash_struct *passwd_hashtable[PASSWD_HASHTABLE_SIZE];
55    
56  #ifdef WANT_ICKY_HASH  #ifdef WANT_ICKY_HASH
57  static unsigned four_char_hash(char *buf);  static unsigned four_char_hash(const char *buf);
58  #define boa_hash four_char_hash   #define boa_hash four_char_hash
59  #else   #else
60  #ifdef WANT_SDBM_HASH   #ifdef WANT_SDBM_HASH
61  static unsigned sdbm_hash(char *str);    static unsigned sdbm_hash(const char *str);
62  #define boa_hash sdbm_hash    #define boa_hash sdbm_hash
63  #else   #else
64  static unsigned djb2_hash(char *str);    #ifdef WANT_DJB2_HASH
65  #define boa_hash djb2_hash     static unsigned djb2_hash(const char *str);
66  #endif     #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  #endif
73    
74  #ifdef WANT_ICKY_HASH  #ifdef WANT_ICKY_HASH
75  static unsigned four_char_hash(char *buf)  static unsigned four_char_hash(const char *buf)
76  {  {
77      unsigned int hash = (buf[0] +      unsigned int hash = (buf[0] +
78                       (buf[1] ? buf[1] : 241 +                           (buf[1] ? buf[1] : 241 +
79                       (buf[2] ? buf[2] : 251 +                            (buf[2] ? buf[2] : 251 +
80                        (buf[3] ? buf[3] : 257))));                             (buf[3] ? buf[3] : 257))));
81  #ifdef DEBUG_HASH      DEBUG(DEBUG_HASH) {
82      log_error_time();          log_error_time();
83      fprintf(stderr, "four_char_hash(%s) = %u\n", buf, hash);          fprintf(stderr, "four_char_hash(%s) = %u\n", buf, hash);
84  #endif      }
85      return hash;      return hash;
86  }  }
87    
# Line 87  static unsigned four_char_hash(char *buf Line 95  static unsigned four_char_hash(char *buf
95  #else  #else
96  #define MAX_HASH_LENGTH 4  #define MAX_HASH_LENGTH 4
97  #ifdef WANT_SDBM_HASH  #ifdef WANT_SDBM_HASH
98  static unsigned sdbm_hash(char *str)  static unsigned sdbm_hash(const char *str)
99  {  {
100      unsigned hash = 0;      unsigned hash = 0;
101      int c;      int c;
102      short count = MAX_HASH_LENGTH;      short count = MAX_HASH_LENGTH;
103    
104  #ifdef DEBUG_HASH      DEBUG(DEBUG_HASH) {
105      log_error_time();          log_error_time();
106      fprintf(stderr, "sdbm_hash(%s) = ", str);          fprintf(stderr, "sdbm_hash(%s) = ", str);
107  #endif      }
108    
109      while ((c = *str++) && count--)      while ((c = *str++) && count--)
110          hash = c + (hash << 6) + (hash << 16) - hash;          hash = c + (hash << 6) + (hash << 16) - hash;
111    
112  #ifdef DEBUG_HASH      DEBUG(DEBUG_HASH) {
113      fprintf(stderr, "%u\n", hash);          fprintf(stderr, "%u\n", hash);
114  #endif      }
115      return hash;      return hash;
116  }  }
117  #else  #else
118    #ifdef WANT_DJB2_HASH
119  static unsigned djb2_hash(char *str)  static unsigned djb2_hash(const char *str)
120  {  {
121      unsigned hash = 5381;      unsigned hash = 5381;
122      int c;      int c;
123      short count = MAX_HASH_LENGTH;      short count = MAX_HASH_LENGTH;
124    
125  #ifdef DEBUG_HASH      DEBUG(DEBUG_HASH) {
126      log_error_time();          log_error_time();
127      fprintf(stderr, "djb2_hash(%s) = ", str);          fprintf(stderr, "djb2_hash(%s) = ", str);
128  #endif      }
129    
130      while ((c = *(str++)) && count--)      while ((c = *(str++)) && count--)
131          hash = ((hash << 5) + hash) + c; /* hash * 33 + c */          hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
132    
133  #ifdef DEBUG_HASH      DEBUG(DEBUG_HASH) {
134      fprintf(stderr, "%u\n", hash);          fprintf(stderr, "%u\n", hash);
135  #endif      }
136      return hash;      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  #endif
164  #endif  #endif
165    
166  /*  /*
167   * Name: add_mime_type   * Name: hash_insert
168   * Description: Adds a key/value pair to the mime_hashtable   * Description: Adds a key/value pair to the provided hashtable
169   */   */
170    
171  void add_mime_type(char *extension, char *type)  static
172    hash_struct *hash_insert(hash_struct *table[], unsigned int hash, char *key, char *value)
173  {  {
174      unsigned int hash;      hash_struct *current, *trailer;
     hash_struct *current, *next;  
175    
176      if (!extension)      if (!key) {
177          return;          log_error_time();
178            fprintf(stderr, "Yipes! Null value sent as key to hash_insert!\n");
179            return NULL;
180        }
181    
182      hash = get_mime_hash_value(extension);      /* should we bother to check table, hash, and key for NULL/0 ? */
183    
184      current = mime_hashtable[hash];      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) {      while (current) {
191          if (!strcmp(current->key, extension))          if (!strcmp(current->key, key))
192              return;         /* don't add extension twice */              return current;         /* don't add extension twice */
193          if (current->next)          if (current->next)
194              current = current->next;              current = current->next;
195          else          else
196              break;              break;
197      }      }
198    
199      /* if here, we need to add a new one */      /* not found */
200      next = (hash_struct *) malloc(sizeof (hash_struct));      trailer = (hash_struct *) malloc(sizeof (hash_struct));
201      if (!next) {      if (trailer == NULL) {
202          DIE("malloc of hash_struct failed!");          WARN("unable to allocate memory for hash_insert");
203      }          return NULL;
204      next->key = strdup(extension);      }
205      if (!next->key)  
206          DIE("malloc of hash_struct->key failed!");      trailer->key = strdup(key);
207      next->value = strdup(type);      trailer->value = strdup(value);
208      if (!next->value)      trailer->next = NULL;
209          DIE("malloc of hash_struct->value failed!");  
210      next->next = NULL;      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) {      if (!current) {
222          mime_hashtable[hash] = next;          /* no entries for this hash value */
223            table[hash] = trailer;
224      } else {      } else {
225          current->next = next;          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  /*  /*
# Line 185  void add_mime_type(char *extension, char Line 272  void add_mime_type(char *extension, char
272    
273  unsigned get_mime_hash_value(char *extension)  unsigned get_mime_hash_value(char *extension)
274  {  {
     unsigned int hash = 0;  
   
275      if (extension == NULL || extension[0] == '\0') {      if (extension == NULL || extension[0] == '\0') {
276          /* FIXME */          /* FIXME */
277          log_error_time();          log_error_time();
278          fprintf(stderr, "Attempt to hash NULL or empty string!\n");          fprintf(stderr, "Attempt to hash NULL or empty string! [get_mime_hash_value]!\n");
279          return 0;          return 0;
280      }      }
281    
282      hash = boa_hash(extension);      return boa_hash(extension) % MIME_HASHTABLE_SIZE;
     hash %= MIME_HASHTABLE_SIZE;  
   
     return hash;  
283  }  }
284    
285  /*  /*
# Line 216  char *get_mime_type(const char *filename Line 298  char *get_mime_type(const char *filename
298    
299      extension = strrchr(filename, '.');      extension = strrchr(filename, '.');
300    
301      if (!extension || *extension++ == '\0')      /* 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;          return default_type;
308    
309      hash = get_mime_hash_value(extension);      /* make sure we hash on the 'bar' not the '.bar' */
310      current = mime_hashtable[hash];      ++extension;
   
     while (current) {  
         if (!strcmp(current->key, extension)) /* hit */  
             return current->value;  
         current = current->next;  
     }  
311    
312      return default_type;      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  /*  /*
# Line 245  unsigned get_homedir_hash_value(char *na Line 328  unsigned get_homedir_hash_value(char *na
328      if (name == NULL || name[0] == '\0') {      if (name == NULL || name[0] == '\0') {
329          /* FIXME */          /* FIXME */
330          log_error_time();          log_error_time();
331          fprintf(stderr, "Attempt to hash NULL or empty string!\n");          fprintf(stderr, "Attempt to hash NULL or empty string! [get_homedir_hash_value]\n");
332          return 0;          return 0;
333      }      }
334    
335      hash = boa_hash(name);      hash = boa_hash(name) % PASSWD_HASHTABLE_SIZE;
     hash %= PASSWD_HASHTABLE_SIZE;  
336    
337      return hash;      return hash;
338  }  }
# Line 266  unsigned get_homedir_hash_value(char *na Line 348  unsigned get_homedir_hash_value(char *na
348    
349  char *get_home_dir(char *name)  char *get_home_dir(char *name)
350  {  {
351      struct passwd *passwdbuf;      hash_struct *current;
352    
     hash_struct *current, *next;  
353      unsigned int hash;      unsigned int hash;
354    
     /* first check hash table -- if username is less than four characters,  
        just hash to zero (this should be very rare) */  
   
355      hash = get_homedir_hash_value(name);      hash = get_homedir_hash_value(name);
356    
357      for(current = passwd_hashtable[hash];current;current = current->next) {      current = find_in_hash(passwd_hashtable, name, hash);
         if (!strcmp(current->key, name)) /* hit */  
             return current->value;  
         if (!current->next)  
             break;  
     }  
   
     /* if here, we have to add a new one */  
358    
359      passwdbuf = getpwnam(name);      if (!current) {
360            /* not found */
361            struct passwd *passwdbuf;
362    
363      if (!passwdbuf)         /* does not exist */          passwdbuf = getpwnam(name);
         return NULL;  
364    
365      next = (hash_struct *) malloc(sizeof (hash_struct));          if (!passwdbuf)         /* does not exist */
366      if (!next) {              return NULL;
         WARN("malloc of hash_struct for passwd_hashtable failed!");  
         return NULL;  
     }  
367    
368      next->key = strdup(name);          current = hash_insert(passwd_hashtable, hash, name, passwdbuf->pw_dir);
     if (!next->key) {  
         WARN("malloc of passwd_hashtable[hash]->key failed!");  
         free(next);  
         return NULL;  
369      }      }
     next->value = strdup(passwdbuf->pw_dir);  
     if (!next->value) {  
         WARN("malloc of passwd_hashtable[hash]->value failed!");  
         free(next->key);  
         free(next);  
         return NULL;  
     }  
     next->next = NULL;  
370    
371      if (!current) {      return (current ? current->value : NULL);
         passwd_hashtable[hash] = next;  
     } else {  
         current->next = next;  
     }  
     return next->value;  
372  }  }
373    
374  void dump_mime(void)  static
375    void clear_hashtable(hash_struct *table[], int size)
376  {  {
377      int i;      int i;
378      hash_struct *temp;      hash_struct *temp;
379      for (i = 0; i < MIME_HASHTABLE_SIZE; ++i) { /* these limits OK? */      for (i = 0; i < size; ++i) { /* these limits OK? */
380          temp = mime_hashtable[i];          temp = table[i];
381          while (temp) {          while (temp) {
382              hash_struct *temp_next;              hash_struct *temp_next;
383    
# Line 335  void dump_mime(void) Line 388  void dump_mime(void)
388    
389              temp = temp_next;              temp = temp_next;
390          }          }
391          mime_hashtable[i] = NULL;          table[i] = NULL;
392      }      }
393  }  }
394    
395  void dump_passwd(void)  void dump_mime(void)
396  {  {
397      int i;      clear_hashtable(mime_hashtable, MIME_HASHTABLE_SIZE);
     hash_struct *temp;  
     for (i = 0; i < PASSWD_HASHTABLE_SIZE; ++i) { /* these limits OK? */  
         temp = passwd_hashtable[i];  
         while (temp) {  
             hash_struct *temp_next;  
   
             temp_next = temp->next;  
             free(temp->key);  
             free(temp->value);  
             free(temp);  
   
             temp = temp_next;  
         }  
         passwd_hashtable[i] = NULL;  
     }  
398  }  }
399    
400  extern int mmap_list_entries_used;  void dump_passwd(void)
401    {
402        clear_hashtable(passwd_hashtable, PASSWD_HASHTABLE_SIZE);
403    }
404    
405  void show_hash_stats(void)  void show_hash_stats(void)
406  {  {
# Line 388  void show_hash_stats(void) Line 429  void show_hash_stats(void)
429          }          }
430      }      }
431      log_error_time();      log_error_time();
432      fprintf(stderr, "mime_hashtable has %d total entries\n",      fprintf(stderr, "mime_hashtable has %d total entries\n", total);
             total);  
433    
434      total = 0;      total = 0;
435      for (i = 0; i < PASSWD_HASHTABLE_SIZE; ++i) { /* these limits OK? */      for (i = 0; i < PASSWD_HASHTABLE_SIZE; ++i) { /* these limits OK? */
Legend:
Removed from v.1.3  
changed lines
  Added in v.1.4
webmaster@linux.gr
 ViewVC Help
Powered by ViewVC 1.1.26