CMakeLua/Utilities/cmcurl-7.19.0/lib/hash.c

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