lib/hash.c

   1 /***************************************************************************
   2  *                                  _   _ ____  _
   3  *  Project                     ___| | | |  _ \| |
   4  *                             / __| | | | |_) | |
   5  *                            | (__| |_| |  _ <| |___
   6  *                             \___|\___/|_| \_\_____|
   7  *
   8  * Copyright (C) 1998 - 2013, Daniel Stenberg, <daniel@haxx.se>, et al.
   9  *
  10  * This software is licensed as described in the file COPYING, which
  11  * you should have received as part of this distribution. The terms
  12  * are also available at http://curl.haxx.se/docs/copyright.html.
  13  *
  14  * You may opt to use, copy, modify, merge, publish, distribute and/or sell
  15  * copies of the Software, and permit persons to whom the Software is
  16  * furnished to do so, under the terms of the COPYING file.
  17  *
  18  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  19  * KIND, either express or implied.
  20  *
  21  ***************************************************************************/
  22
  23 #include "curl_setup.h"
  24
  25 #include "hash.h"
  26 #include "llist.h"
  27
  28 #define _MPRINTF_REPLACE /* use our functions only */
  29 #include <curl/mprintf.h>
  30
  31 #include "curl_memory.h"
  32 /* The last #include file should be: */
  33 #include "memdebug.h"
  34
  35 static void
  36 hash_element_dtor(void *user, void *element)
  37 {
  38   struct curl_hash *h = (struct curl_hash *) user;
  39   struct curl_hash_element *e = (struct curl_hash_element *) element;
  40
  41   Curl_safefree(e->key);
  42
  43   if(e->ptr) {
  44     h->dtor(e->ptr);
  45     e->ptr = NULL;
  46   }
  47
  48   e->key_len = 0;
  49
  50   free(e);
  51 }
  52
  53 /* return 1 on error, 0 is fine */
  54 int
  55 Curl_hash_init(struct curl_hash *h,
  56                int slots,
  57                hash_function hfunc,
  58                comp_function comparator,
  59                curl_hash_dtor dtor)
  60 {
  61   int i;
  62
  63   if(!slots || !hfunc || !comparator ||!dtor) {
  64     return 1; /* failure */
  65   }
  66
  67   h->hash_func = hfunc;
  68   h->comp_func = comparator;
  69   h->dtor = dtor;
  70   h->size = 0;
  71   h->slots = slots;
  72
  73   h->table = malloc(slots * sizeof(struct curl_llist *));
  74   if(h->table) {
  75     for(i = 0; i < slots; ++i) {
  76       h->table[i] = Curl_llist_alloc((curl_llist_dtor) hash_element_dtor);
  77       if(!h->table[i]) {
  78         while(i--) {
  79           Curl_llist_destroy(h->table[i], NULL);
  80           h->table[i] = NULL;
  81         }
  82         free(h->table);
  83         h->table = NULL;
  84         h->slots = 0;
  85         return 1; /* failure */
  86       }
  87     }
  88     return 0; /* fine */
  89   }
  90   else {
  91     h->slots = 0;
  92     return 1; /* failure */
  93   }
  94 }
  95
  96 struct curl_hash *
  97 Curl_hash_alloc(int slots,
  98                 hash_function hfunc,
  99                 comp_function comparator,
 100                 curl_hash_dtor dtor)
 101 {
 102   struct curl_hash *h;
 103
 104   if(!slots || !hfunc || !comparator ||!dtor) {
 105     return NULL; /* failure */
 106   }
 107
 108   h = malloc(sizeof(struct curl_hash));
 109   if(h) {
 110     if(Curl_hash_init(h, slots, hfunc, comparator, dtor)) {
 111       /* failure */
 112       free(h);
 113       h = NULL;
 114     }
 115   }
 116
 117   return h;
 118 }
 119
 120
 121
 122 static struct curl_hash_element *
 123 mk_hash_element(const void *key, size_t key_len, const void *p)
 124 {
 125   struct curl_hash_element *he = malloc(sizeof(struct curl_hash_element));
 126
 127   if(he) {
 128     void *dupkey = malloc(key_len);
 129     if(dupkey) {
 130       /* copy the key */
 131       memcpy(dupkey, key, key_len);
 132
 133       he->key = dupkey;
 134       he->key_len = key_len;
 135       he->ptr = (void *) p;
 136     }
 137     else {
 138       /* failed to duplicate the key, free memory and fail */
 139       free(he);
 140       he = NULL;
 141     }
 142   }
 143   return he;
 144 }
 145
 146 #define FETCH_LIST(x,y,z) x->table[x->hash_func(y, z, x->slots)]
 147
 148 /* Insert the data in the hash. If there already was a match in the hash,
 149  * that data is replaced.
 150  *
 151  * @unittest: 1305
 152  */
 153 void *
 154 Curl_hash_add(struct curl_hash *h, void *key, size_t key_len, void *p)
 155 {
 156   struct curl_hash_element  *he;
 157   struct curl_llist_element *le;
 158   struct curl_llist *l = FETCH_LIST (h, key, key_len);
 159
 160   for(le = l->head; le; le = le->next) {
 161     he = (struct curl_hash_element *) le->ptr;
 162     if(h->comp_func(he->key, he->key_len, key, key_len)) {
 163       Curl_llist_remove(l, le, (void *)h);
 164       --h->size;
 165       break;
 166     }
 167   }
 168
 169   he = mk_hash_element(key, key_len, p);
 170   if(he) {
 171     if(Curl_llist_insert_next(l, l->tail, he)) {
 172       ++h->size;
 173       return p; /* return the new entry */
 174     }
 175     /*
 176      * Couldn't insert it, destroy the 'he' element and the key again. We
 177      * don't call hash_element_dtor() since that would also call the
 178      * "destructor" for the actual data 'p'. When we fail, we shall not touch
 179      * that data.
 180      */
 181     free(he->key);
 182     free(he);
 183   }
 184
 185   return NULL; /* failure */
 186 }
 187
 188 /* remove the identified hash entry, returns non-zero on failure */
 189 int Curl_hash_delete(struct curl_hash *h, void *key, size_t key_len)
 190 {
 191   struct curl_llist_element *le;
 192   struct curl_hash_element  *he;
 193   struct curl_llist *l = FETCH_LIST(h, key, key_len);
 194
 195   for(le = l->head; le; le = le->next) {
 196     he = le->ptr;
 197     if(h->comp_func(he->key, he->key_len, key, key_len)) {
 198       Curl_llist_remove(l, le, (void *) h);
 199       --h->size;
 200       return 0;
 201     }
 202   }
 203   return 1;
 204 }
 205
 206 void *
 207 Curl_hash_pick(struct curl_hash *h, void *key, size_t key_len)
 208 {
 209   struct curl_llist_element *le;
 210   struct curl_hash_element  *he;
 211   struct curl_llist *l;
 212
 213   if(h) {
 214     l = FETCH_LIST(h, key, key_len);
 215     for(le = l->head; le; le = le->next) {
 216       he = le->ptr;
 217       if(h->comp_func(he->key, he->key_len, key, key_len)) {
 218         return he->ptr;
 219       }
 220     }
 221   }
 222
 223   return NULL;
 224 }
 225
 226 #if defined(DEBUGBUILD) && defined(AGGRESIVE_TEST)
 227 void
 228 Curl_hash_apply(curl_hash *h, void *user,
 229                 void (*cb)(void *user, void *ptr))
 230 {
 231   struct curl_llist_element  *le;
 232   int                  i;
 233
 234   for(i = 0; i < h->slots; ++i) {
 235     for(le = (h->table[i])->head;
 236         le;
 237         le = le->next) {
 238       curl_hash_element *el = le->ptr;
 239       cb(user, el->ptr);
 240     }
 241   }
 242 }
 243 #endif
 244
 245 void
 246 Curl_hash_clean(struct curl_hash *h)
 247 {
 248   int i;
 249
 250   for(i = 0; i < h->slots; ++i) {
 251     Curl_llist_destroy(h->table[i], (void *) h);
 252     h->table[i] = NULL;
 253   }
 254
 255   Curl_safefree(h->table);
 256   h->size = 0;
 257   h->slots = 0;
 258 }
 259
 260 void
 261 Curl_hash_clean_with_criterium(struct curl_hash *h, void *user,
 262                                int (*comp)(void *, void *))
 263 {
 264   struct curl_llist_element *le;
 265   struct curl_llist_element *lnext;
 266   struct curl_llist *list;
 267   int i;
 268
 269   if(!h)
 270     return;
 271
 272   for(i = 0; i < h->slots; ++i) {
 273     list = h->table[i];
 274     le = list->head; /* get first list entry */
 275     while(le) {
 276       struct curl_hash_element *he = le->ptr;
 277       lnext = le->next;
 278       /* ask the callback function if we shall remove this entry or not */
 279       if(comp(user, he->ptr)) {
 280         Curl_llist_remove(list, le, (void *) h);
 281         --h->size; /* one less entry in the hash now */
 282       }
 283       le = lnext;
 284     }
 285   }
 286 }
 287
 288 void
 289 Curl_hash_destroy(struct curl_hash *h)
 290 {
 291   if(!h)
 292     return;
 293
 294   Curl_hash_clean(h);
 295
 296   free(h);
 297 }
 298
 299 size_t Curl_hash_str(void* key, size_t key_length, size_t slots_num)
 300 {
 301   const char* key_str = (const char *) key;
 302   const char *end = key_str + key_length;
 303   unsigned long h = 5381;
 304
 305   while(key_str < end) {
 306     h += h << 5;
 307     h ^= (unsigned long) *key_str++;
 308   }
 309
 310   return (h % slots_num);
 311 }
 312
 313 size_t Curl_str_key_compare(void*k1, size_t key1_len, void*k2, size_t key2_len)
 314 {
 315   char *key1 = (char *)k1;
 316   char *key2 = (char *)k2;
 317
 318   if(key1_len == key2_len &&
 319       *key1 == *key2 &&
 320       memcmp(key1, key2, key1_len) == 0) {
 321     return 1;
 322   }
 323
 324   return 0;
 325 }
 326
 327 void Curl_hash_start_iterate(struct curl_hash *hash,
 328                              struct curl_hash_iterator *iter)
 329 {
 330   iter->hash = hash;
 331   iter->slot_index = 0;
 332   iter->current_element = NULL;
 333 }
 334
 335 struct curl_hash_element *
 336 Curl_hash_next_element(struct curl_hash_iterator *iter)
 337 {
 338   int i;
 339   struct curl_hash *h = iter->hash;
 340
 341   /* Get the next element in the current list, if any */
 342   if(iter->current_element)
 343     iter->current_element = iter->current_element->next;
 344
 345   /* If we have reached the end of the list, find the next one */
 346   if(!iter->current_element) {
 347     for(i = iter->slot_index;i < h->slots;i++) {
 348       if(h->table[i]->head) {
 349         iter->current_element = h->table[i]->head;
 350         iter->slot_index = i+1;
 351         break;
 352       }
 353     }
 354   }
 355
 356   if(iter->current_element) {
 357     struct curl_hash_element *he = iter->current_element->ptr;
 358     return he;
 359   }
 360   else {
 361     iter->current_element = NULL;
 362     return NULL;
 363   }
 364 }
 365
 366 #if 0 /* useful function for debugging hashes and their contents */
 367 void Curl_hash_print(struct curl_hash *h,
 368                      void (*func)(void *))
 369 {
 370   struct curl_hash_iterator iter;
 371   struct curl_hash_element *he;
 372   int last_index = -1;
 373
 374   if(!h)
 375     return;
 376
 377   fprintf(stderr, "=Hash dump=\n");
 378
 379   Curl_hash_start_iterate(h, &iter);
 380
 381   he = Curl_hash_next_element(&iter);
 382   while(he) {
 383     if(iter.slot_index != last_index) {
 384       fprintf(stderr, "index %d:", iter.slot_index);
 385       if(last_index >= 0) {
 386         fprintf(stderr, "\n");
 387       }
 388       last_index = iter.slot_index;
 389     }
 390
 391     if(func)
 392       func(he->ptr);
 393     else
 394       fprintf(stderr, " [%p]", (void *)he->ptr);
 395
 396     he = Curl_hash_next_element(&iter);
 397   }
 398   fprintf(stderr, "\n");
 399 }
 400 #endif