lib/hash.c

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