granicus.if.org Git - mutt/blob - hash.c

   1 /*
   2  * Copyright (C) 1996-2009 Michael R. Elkins <me@mutt.org>
   3  *
   4  *     This program is free software; you can redistribute it and/or modify
   5  *     it under the terms of the GNU General Public License as published by
   6  *     the Free Software Foundation; either version 2 of the License, or
   7  *     (at your option) any later version.
   8  *
   9  *     This program is distributed in the hope that it will be useful,
  10  *     but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  *     GNU General Public License for more details.
  13  *
  14  *     You should have received a copy of the GNU General Public License
  15  *     along with this program; if not, write to the Free Software
  16  *     Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  17  */
  18
  19 #if HAVE_CONFIG_H
  20 # include "config.h"
  21 #endif
  22
  23 #include <stdlib.h>
  24 #include <stdio.h>
  25 #include <string.h>
  26 #include <ctype.h>
  27
  28 #include "mutt.h"
  29
  30 #define SOMEPRIME 149711
  31
  32 static unsigned int gen_string_hash (union hash_key key, unsigned int n)
  33 {
  34   unsigned int h = 0;
  35   unsigned char *s = (unsigned char *)key.strkey;
  36
  37   while (*s)
  38     h += (h << 7) + *s++;
  39   h = (h * SOMEPRIME) % n;
  40
  41   return h;
  42 }
  43
  44 static int cmp_string_key (union hash_key a, union hash_key b)
  45 {
  46   return mutt_strcmp (a.strkey, b.strkey);
  47 }
  48
  49 static unsigned int gen_case_string_hash (union hash_key key, unsigned int n)
  50 {
  51   unsigned int h = 0;
  52   unsigned char *s = (unsigned char *)key.strkey;
  53
  54   while (*s)
  55     h += (h << 7) + tolower (*s++);
  56   h = (h * SOMEPRIME) % n;
  57
  58   return h;
  59 }
  60
  61 static int cmp_case_string_key (union hash_key a, union hash_key b)
  62 {
  63   return mutt_strcasecmp (a.strkey, b.strkey);
  64 }
  65
  66 static unsigned int gen_int_hash (union hash_key key, unsigned int n)
  67 {
  68   return key.intkey % n;
  69 }
  70
  71 static int cmp_int_key (union hash_key a, union hash_key b)
  72 {
  73   if (a.intkey == b.intkey)
  74     return 0;
  75   if (a.intkey < b.intkey)
  76     return -1;
  77   return 1;
  78 }
  79
  80 static HASH *new_hash (int nelem)
  81 {
  82   HASH *table = safe_calloc (1, sizeof (HASH));
  83   if (nelem == 0)
  84     nelem = 2;
  85   table->nelem = nelem;
  86   table->table = safe_calloc (nelem, sizeof (struct hash_elem *));
  87   return table;
  88 }
  89
  90 HASH *hash_create (int nelem, int flags)
  91 {
  92   HASH *table = new_hash (nelem);
  93   if (flags & MUTT_HASH_STRCASECMP)
  94   {
  95     table->gen_hash = gen_case_string_hash;
  96     table->cmp_key = cmp_case_string_key;
  97   }
  98   else
  99   {
 100     table->gen_hash = gen_string_hash;
 101     table->cmp_key = cmp_string_key;
 102   }
 103   if (flags & MUTT_HASH_STRDUP_KEYS)
 104     table->strdup_keys = 1;
 105   if (flags & MUTT_HASH_ALLOW_DUPS)
 106     table->allow_dups = 1;
 107   return table;
 108 }
 109
 110 HASH *int_hash_create (int nelem, int flags)
 111 {
 112   HASH *table = new_hash (nelem);
 113   table->gen_hash = gen_int_hash;
 114   table->cmp_key = cmp_int_key;
 115   if (flags & MUTT_HASH_ALLOW_DUPS)
 116     table->allow_dups = 1;
 117   return table;
 118 }
 119
 120 /* table        hash table to update
 121  * key          key to hash on
 122  * data         data to associate with `key'
 123  * allow_dup    if nonzero, duplicate keys are allowed in the table
 124  */
 125 static int union_hash_insert (HASH * table, union hash_key key, void *data)
 126 {
 127   struct hash_elem *ptr;
 128   unsigned int h;
 129
 130   ptr = (struct hash_elem *) safe_malloc (sizeof (struct hash_elem));
 131   h = table->gen_hash (key, table->nelem);
 132   ptr->key = key;
 133   ptr->data = data;
 134
 135   if (table->allow_dups)
 136   {
 137     ptr->next = table->table[h];
 138     table->table[h] = ptr;
 139   }
 140   else
 141   {
 142     struct hash_elem *tmp, *last;
 143     int r;
 144
 145     for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next)
 146     {
 147       r = table->cmp_key (tmp->key, key);
 148       if (r == 0)
 149       {
 150         FREE (&ptr);
 151         return (-1);
 152       }
 153       if (r > 0)
 154         break;
 155     }
 156     if (last)
 157       last->next = ptr;
 158     else
 159       table->table[h] = ptr;
 160     ptr->next = tmp;
 161   }
 162   return h;
 163 }
 164
 165 int hash_insert (HASH * table, const char *strkey, void *data)
 166 {
 167   union hash_key key;
 168   key.strkey = table->strdup_keys ? safe_strdup (strkey) : strkey;
 169   return union_hash_insert (table, key, data);
 170 }
 171
 172 int int_hash_insert (HASH * table, unsigned int intkey, void *data)
 173 {
 174   union hash_key key;
 175   key.intkey = intkey;
 176   return union_hash_insert (table, key, data);
 177 }
 178
 179 static struct hash_elem *union_hash_find_elem (const HASH *table, union hash_key key)
 180 {
 181   int hash;
 182   struct hash_elem *ptr;
 183
 184   if (!table)
 185     return NULL;
 186
 187   hash = table->gen_hash (key, table->nelem);
 188   ptr = table->table[hash];
 189   for (; ptr; ptr = ptr->next)
 190   {
 191     if (table->cmp_key (key, ptr->key) == 0)
 192       return (ptr);
 193   }
 194   return NULL;
 195 }
 196
 197 static void *union_hash_find (const HASH *table, union hash_key key)
 198 {
 199   struct hash_elem *ptr = union_hash_find_elem (table, key);
 200   if (ptr)
 201     return ptr->data;
 202   else
 203     return NULL;
 204 }
 205
 206 void *hash_find (const HASH *table, const char *strkey)
 207 {
 208   union hash_key key;
 209   key.strkey = strkey;
 210   return union_hash_find (table, key);
 211 }
 212
 213 struct hash_elem *hash_find_elem (const HASH *table, const char *strkey)
 214 {
 215   union hash_key key;
 216   key.strkey = strkey;
 217   return union_hash_find_elem (table, key);
 218 }
 219
 220 void *int_hash_find (const HASH *table, unsigned int intkey)
 221 {
 222   union hash_key key;
 223   key.intkey = intkey;
 224   return union_hash_find (table, key);
 225 }
 226
 227 struct hash_elem *hash_find_bucket (const HASH *table, const char *strkey)
 228 {
 229   union hash_key key;
 230   int hash;
 231
 232   if (!table)
 233     return NULL;
 234
 235   key.strkey = strkey;
 236   hash = table->gen_hash (key, table->nelem);
 237   return table->table[hash];
 238 }
 239
 240 static void union_hash_delete (HASH *table, union hash_key key, const void *data,
 241                                void (*destroy) (void *))
 242 {
 243   int hash;
 244   struct hash_elem *ptr, **last;
 245
 246   if (!table)
 247     return;
 248
 249   hash = table->gen_hash (key, table->nelem);
 250   ptr = table->table[hash];
 251   last = &table->table[hash];
 252
 253   while (ptr)
 254   {
 255     if ((data == ptr->data || !data)
 256         && table->cmp_key (ptr->key, key) == 0)
 257     {
 258       *last = ptr->next;
 259       if (destroy)
 260         destroy (ptr->data);
 261       if (table->strdup_keys)
 262         FREE (&ptr->key.strkey);
 263       FREE (&ptr);
 264
 265       ptr = *last;
 266     }
 267     else
 268     {
 269       last = &ptr->next;
 270       ptr = ptr->next;
 271     }
 272   }
 273 }
 274
 275 void hash_delete (HASH *table, const char *strkey, const void *data,
 276                   void (*destroy) (void *))
 277 {
 278   union hash_key key;
 279   key.strkey = strkey;
 280   union_hash_delete (table, key, data, destroy);
 281 }
 282
 283 void int_hash_delete (HASH *table, unsigned int intkey, const void *data,
 284                       void (*destroy) (void *))
 285 {
 286   union hash_key key;
 287   key.intkey = intkey;
 288   union_hash_delete (table, key, data, destroy);
 289 }
 290
 291 /* ptr          pointer to the hash table to be freed
 292  * destroy()    function to call to free the ->data member (optional)
 293  */
 294 void hash_destroy (HASH **ptr, void (*destroy) (void *))
 295 {
 296   int i;
 297   HASH *pptr;
 298   struct hash_elem *elem, *tmp;
 299
 300   if (!ptr || !*ptr)
 301     return;
 302
 303   pptr = *ptr;
 304   for (i = 0 ; i < pptr->nelem; i++)
 305   {
 306     for (elem = pptr->table[i]; elem; )
 307     {
 308       tmp = elem;
 309       elem = elem->next;
 310       if (destroy)
 311         destroy (tmp->data);
 312       if (pptr->strdup_keys)
 313         FREE (&tmp->key.strkey);
 314       FREE (&tmp);
 315     }
 316   }
 317   FREE (&pptr->table);
 318   FREE (ptr);           /* __FREE_CHECKED__ */
 319 }
 320
 321 struct hash_elem *hash_walk(const HASH *table, struct hash_walk_state *state)
 322 {
 323   if (state->last && state->last->next)
 324   {
 325     state->last = state->last->next;
 326     return state->last;
 327   }
 328
 329   if (state->last)
 330     state->index++;
 331
 332   while (state->index < table->nelem)
 333   {
 334     if (table->table[state->index])
 335     {
 336       state->last = table->table[state->index];
 337       return state->last;
 338     }
 339     state->index++;
 340   }
 341
 342   state->index = 0;
 343   state->last = NULL;
 344   return NULL;
 345 }