src/hash.c

   1 /*
   2     MiddleMan filtering proxy server
   3     Copyright (C) 2002  Jason McLaughlin
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with this program; if not, write to the Free Software
  17     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18 */
  19
  20 #include <stdlib.h>
  21 #include <string.h>
  22 #include "proto.h"
  23 #include "hash.h"
  24
  25 /*
  26 return a slot index for a string
  27 */
  28 unsigned int hash_key(int max, char *string)
  29 {
  30         int i;
  31         unsigned int ret = 0;
  32
  33         i = strlen(string);
  34
  35         while (i--) {
  36                 ret <<= i;
  37                 ret += string[i];
  38         }
  39
  40         return ret % max;
  41 }
  42
  43 /*
  44 create a hash table
  45 */
  46 HASH_TABLE *hash_create(int size)
  47 {
  48         HASH_TABLE *hash_table;
  49
  50         hash_table = xmalloc(sizeof(HASH_TABLE));
  51
  52         hash_table->hit = 0;
  53         hash_table->miss = 0;
  54         hash_table->size = size;
  55
  56         hash_table->hash_list = xmalloc(sizeof(struct HASH_LIST *) * size);
  57
  58         memset(hash_table->hash_list, 0, sizeof(struct HASH_LIST *) * size);
  59
  60         return hash_table;
  61 }
  62
  63 /*
  64 insert item into hash table
  65 */
  66 void hash_insert(HASH_TABLE * hash_table, char *ref, void *string)
  67 {
  68         unsigned int key;
  69         struct HASH_LIST *hash_list;
  70
  71         ASSERT(hash_table);
  72
  73         if (hash_search(hash_table, ref) != NULL)
  74                 return;
  75
  76         key = hash_key(hash_table->size, ref);
  77
  78         hash_list = hash_table->hash_list[key];
  79
  80         HASH_LIST_ADD(hash_list, ref, string);
  81
  82         if (hash_table->hash_list[key] == NULL)
  83                 hash_table->hash_list[key] = hash_list;
  84 }
  85
  86 /*
  87 purge item from hash table
  88 */
  89 void hash_purge(HASH_TABLE * hash_table, char *ref)
  90 {
  91         unsigned int key;
  92         struct HASH_LIST *hash_list, *prev = NULL;
  93
  94         ASSERT(hash_table);
  95
  96         key = hash_key(hash_table->size, ref);
  97
  98         hash_list = hash_table->hash_list[key];
  99
 100         while (hash_list != NULL) {
 101                 if (!strcasecmp(hash_list->ref, ref)) {
 102                         if (hash_table->hash_list[key] == hash_list)
 103                                 hash_table->hash_list[key] = hash_list->next;
 104                         else if (prev != NULL)
 105                                 prev->next = hash_list->next;
 106
 107                         xfree(hash_list->ref);
 108                         xfree(hash_list->data);
 109                         xfree(hash_list);
 110
 111                         break;
 112                 }
 113
 114                 prev = hash_list;
 115                 hash_list = hash_list->next;
 116         }
 117 }
 118
 119 /*
 120 search for item in hash table
 121 */
 122 char *hash_search(HASH_TABLE * hash_table, char *ref)
 123 {
 124         unsigned int key;
 125         struct HASH_LIST *hash_list;
 126
 127         ASSERT(hash_table);
 128
 129         key = hash_key(hash_table->size, ref);
 130
 131         hash_list = hash_table->hash_list[key];
 132
 133         while (hash_list != NULL) {
 134                 if (!strcasecmp(hash_list->ref, ref)) {
 135                         hash_table->hit++;
 136
 137                         return hash_list->data;
 138                 }
 139
 140                 hash_list = hash_list->next;
 141         }
 142
 143         hash_table->miss++;
 144
 145         return NULL;
 146 }
 147
 148 /*
 149 wipe out a hash table and free all used memory
 150 */
 151 void hash_destroy(HASH_TABLE * hash_table)
 152 {
 153         int i;
 154         struct HASH_LIST *hash_list, *tmp_list;
 155
 156         ASSERT(hash_table);
 157
 158         for (i = 0; i < hash_table->size; i++) {
 159                 hash_list = hash_table->hash_list[i];
 160
 161                 while (hash_list != NULL) {
 162                         tmp_list = hash_list->next;
 163
 164                         xfree(hash_list->ref);
 165                         xfree(hash_list->data);
 166                         xfree(hash_list);
 167
 168                         hash_list = tmp_list;
 169                 }
 170         }
 171
 172         xfree(hash_table->hash_list);
 173         xfree(hash_table);
 174 }
 175
 176 /*
 177 remove old items from hash table
 178 */
 179 int hash_expire(HASH_TABLE * hash_table, unsigned int age)
 180 {
 181         int i, x = 0;
 182         time_t t;
 183         struct HASH_LIST *hash_list, *tmp_list, *prev = NULL;
 184
 185         ASSERT(hash_table);
 186
 187         t = time(NULL);
 188
 189         for (i = 0; i < hash_table->size; i++) {
 190                 hash_list = hash_table->hash_list[i];
 191
 192                 while (hash_list != NULL) {
 193                         tmp_list = hash_list->next;
 194
 195                         if (hash_list->age <= (t - age)) {
 196                                 if (hash_table->hash_list[i] == hash_list)
 197                                         hash_table->hash_list[i] = tmp_list;
 198                                 else if (prev != NULL)
 199                                         prev->next = tmp_list;
 200
 201                                 xfree(hash_list->ref);
 202                                 xfree(hash_list->data);
 203                                 xfree(hash_list);
 204
 205                                 x++;
 206                         } else
 207                                 prev = hash_list;
 208
 209                         hash_list = tmp_list;
 210                 }
 211         }
 212
 213         return x;
 214 }