Utilities/cmcurl/hash.c

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