lib/hash.c

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