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 <time.h>
  23 #include "proto.h"
  24 #include "hash.h"
  25
  26 /*
  27 return a slot index for a string
  28 */
  29 unsigned int hash_key(int max, char *string)
  30 {
  31         int i;
  32         unsigned int ret = 0;
  33
  34         i = strlen(string);
  35
  36         while (i--) {
  37                 ret <<= i;
  38                 ret += string[i];
  39         }
  40
  41         return ret % max;
  42 }
  43
  44 /*
  45 create a hash table
  46 */
  47 HASH_TABLE *hash_create(int size)
  48 {
  49         HASH_TABLE *hash_table;
  50
  51         hash_table = xmalloc(sizeof(HASH_TABLE));
  52
  53         hash_table->hit = 0;
  54         hash_table->miss = 0;
  55         hash_table->size = size;
  56
  57         hash_table->hash_list = xmalloc(sizeof(struct HASH_LIST *) * size);
  58
  59         memset(hash_table->hash_list, 0, sizeof(struct HASH_LIST *) * size);
  60
  61         return hash_table;
  62 }
  63
  64 /*
  65 insert item into hash table
  66 */
  67 void hash_insert(HASH_TABLE * hash_table, char *ref, void *string)
  68 {
  69         unsigned int key;
  70         struct HASH_LIST *hash_list;
  71
  72         ASSERT(hash_table);
  73
  74         if (hash_search(hash_table, ref) != NULL)
  75                 return;
  76
  77         key = hash_key(hash_table->size, ref);
  78
  79         hash_list = hash_table->hash_list[key];
  80
  81         HASH_LIST_ADD(hash_list, ref, string);
  82
  83         if (hash_table->hash_list[key] == NULL)
  84                 hash_table->hash_list[key] = hash_list;
  85 }
  86
  87 /*
  88 purge item from hash table
  89 */
  90 void hash_purge(HASH_TABLE * hash_table, char *ref)
  91 {
  92         unsigned int key;
  93         struct HASH_LIST *hash_list, *prev = NULL;
  94
  95         ASSERT(hash_table);
  96
  97         key = hash_key(hash_table->size, ref);
  98
  99         hash_list = hash_table->hash_list[key];
 100
 101         while (hash_list != NULL) {
 102                 if (!strcasecmp(hash_list->ref, ref)) {
 103                         if (hash_table->hash_list[key] == hash_list)
 104                                 hash_table->hash_list[key] = hash_list->next;
 105                         else if (prev != NULL)
 106                                 prev->next = hash_list->next;
 107
 108                         xfree(hash_list->ref);
 109                         xfree(hash_list->data);
 110                         xfree(hash_list);
 111
 112                         break;
 113                 }
 114
 115                 prev = hash_list;
 116                 hash_list = hash_list->next;
 117         }
 118 }
 119
 120 /*
 121 search for item in hash table
 122 */
 123 char *hash_search(HASH_TABLE * hash_table, char *ref)
 124 {
 125         unsigned int key;
 126         struct HASH_LIST *hash_list;
 127
 128         ASSERT(hash_table);
 129
 130         key = hash_key(hash_table->size, ref);
 131
 132         hash_list = hash_table->hash_list[key];
 133
 134         while (hash_list != NULL) {
 135                 if (!strcasecmp(hash_list->ref, ref)) {
 136                         hash_table->hit++;
 137
 138                         return hash_list->data;
 139                 }
 140
 141                 hash_list = hash_list->next;
 142         }
 143
 144         hash_table->miss++;
 145
 146         return NULL;
 147 }
 148
 149 /*
 150 wipe out a hash table and free all used memory
 151 */
 152 void hash_destroy(HASH_TABLE * hash_table)
 153 {
 154         int i;
 155         struct HASH_LIST *hash_list, *tmp_list;
 156
 157         ASSERT(hash_table);
 158
 159         for (i = 0; i < hash_table->size; i++) {
 160                 hash_list = hash_table->hash_list[i];
 161
 162                 while (hash_list != NULL) {
 163                         tmp_list = hash_list->next;
 164
 165                         xfree(hash_list->ref);
 166                         xfree(hash_list->data);
 167                         xfree(hash_list);
 168
 169                         hash_list = tmp_list;
 170                 }
 171         }
 172
 173         xfree(hash_table->hash_list);
 174         xfree(hash_table);
 175 }
 176
 177 /*
 178 remove old items from hash table
 179 */
 180 int hash_expire(HASH_TABLE * hash_table, unsigned int age)
 181 {
 182         int i, x = 0;
 183         time_t t;
 184         struct HASH_LIST *hash_list, *tmp_list, *prev = NULL;
 185
 186         ASSERT(hash_table);
 187
 188         t = time(NULL);
 189
 190         for (i = 0; i < hash_table->size; i++) {
 191                 hash_list = hash_table->hash_list[i];
 192
 193                 while (hash_list != NULL) {
 194                         tmp_list = hash_list->next;
 195
 196                         if (hash_list->age <= (t - age)) {
 197                                 if (hash_table->hash_list[i] == hash_list)
 198                                         hash_table->hash_list[i] = tmp_list;
 199                                 else if (prev != NULL)
 200                                         prev->next = tmp_list;
 201
 202                                 xfree(hash_list->ref);
 203                                 xfree(hash_list->data);
 204                                 xfree(hash_list);
 205
 206                                 x++;
 207                         } else
 208                                 prev = hash_list;
 209
 210                         hash_list = tmp_list;
 211                 }
 212         }
 213
 214         return x;
 215 }