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