lib/hash.c

   1 /***************************************************************************
   2  *                                  _   _ ____  _
   3  *  Project                     ___| | | |  _ \| |
   4  *                             / __| | | | |_) | |
   5  *                            | (__| |_| |  _ <| |___
   6  *                             \___|\___/|_| \_\_____|
   7  *
   8  * Copyright (C) 1998 - 2003, 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 #ifdef CURLDEBUG
  33 /* this must be the last include file */
  34 #include "memdebug.h"
  35 #endif
  36
  37
  38 static unsigned long
  39 hash_str(const char *key, size_t key_length)
  40 {
  41   char *end = (char *) key + key_length;
  42   unsigned long h = 5381;
  43
  44   while (key < end) {
  45     h += h << 5;
  46     h ^= (unsigned long) *key++;
  47   }
  48
  49   return h;
  50 }
  51
  52 static void
  53 hash_element_dtor(void *user, void *element)
  54 {
  55   curl_hash         *h = (curl_hash *) user;
  56   curl_hash_element *e = (curl_hash_element *) element;
  57
  58   if (e->key) {
  59     free(e->key);
  60   }
  61
  62   h->dtor(e->ptr);
  63
  64   free(e);
  65 }
  66
  67 /* return 1 on error, 0 is fine */
  68 int
  69 Curl_hash_init(curl_hash *h, int slots, curl_hash_dtor dtor)
  70 {
  71   int i;
  72
  73   h->dtor = dtor;
  74   h->size = 0;
  75   h->slots = slots;
  76
  77   h->table = (curl_llist **) malloc(slots * sizeof(curl_llist *));
  78   if(h->table) {
  79     for (i = 0; i < slots; ++i) {
  80       h->table[i] = Curl_llist_alloc((curl_llist_dtor) hash_element_dtor);
  81       if(!h->table[i]) {
  82         while(i--)
  83           Curl_llist_destroy(h->table[i], NULL);
  84         free(h->table);
  85         return 1; /* failure */
  86       }
  87     }
  88     return 0; /* fine */
  89   }
  90   else
  91     return 1; /* failure */
  92 }
  93
  94 curl_hash *
  95 Curl_hash_alloc(int slots, curl_hash_dtor dtor)
  96 {
  97   curl_hash *h;
  98
  99   h = (curl_hash *) malloc(sizeof(curl_hash));
 100   if (h) {
 101     if(Curl_hash_init(h, slots, dtor)) {
 102       /* failure */
 103       free(h);
 104       h = NULL;
 105     }
 106   }
 107
 108   return h;
 109 }
 110
 111 static int
 112 hash_key_compare(char *key1, size_t key1_len, char *key2, size_t key2_len)
 113 {
 114   if (key1_len == key2_len &&
 115       *key1 == *key2 &&
 116       memcmp(key1, key2, key1_len) == 0) {
 117     return 1;
 118   }
 119
 120   return 0;
 121 }
 122
 123 static curl_hash_element *
 124 mk_hash_element(char *key, size_t key_len, const void *p)
 125 {
 126   curl_hash_element *he =
 127     (curl_hash_element *) malloc(sizeof(curl_hash_element));
 128
 129   if(he) {
 130     he->key = strdup(key);
 131     he->key_len = key_len;
 132     he->ptr = (void *) p;
 133   }
 134   return he;
 135 }
 136
 137 #define find_slot(__h, __k, __k_len) (hash_str(__k, __k_len) % (__h)->slots)
 138
 139 #define FETCH_LIST(x,y,z) x->table[find_slot(x, y, z)]
 140
 141 /* Return the data in the hash. If there already was a match in the hash,
 142    that data is returned. */
 143 void *
 144 Curl_hash_add(curl_hash *h, char *key, size_t key_len, void *p)
 145 {
 146   curl_hash_element  *he;
 147   curl_llist_element *le;
 148   curl_llist *l = FETCH_LIST(h, key, key_len);
 149
 150   for (le = l->head; le; le = le->next) {
 151     he = (curl_hash_element *) le->ptr;
 152     if (hash_key_compare(he->key, he->key_len, key, key_len)) {
 153       h->dtor(p);     /* remove the NEW entry */
 154       return he->ptr; /* return the EXISTING entry */
 155     }
 156   }
 157
 158   he = mk_hash_element(key, key_len, p);
 159   if (he) {
 160     if(Curl_llist_insert_next(l, l->tail, he)) {
 161       ++h->size;
 162       return p; /* return the new entry */
 163     }
 164     /* couldn't insert it, destroy the 'he' element again */
 165     hash_element_dtor(h, he);
 166   }
 167   h->dtor(p); /* remove the NEW entry */
 168   return NULL; /* failure */
 169 }
 170
 171 #if 0
 172 int
 173 Curl_hash_delete(curl_hash *h, char *key, size_t key_len)
 174 {
 175   curl_hash_element  *he;
 176   curl_llist_element *le;
 177   curl_llist *l = FETCH_LIST(h, key, key_len);
 178
 179   for (le = l->head;
 180        le;
 181        le = le->next) {
 182     he = le->ptr;
 183     if (hash_key_compare(he->key, he->key_len, key, key_len)) {
 184       Curl_llist_remove(l, le, (void *) h);
 185       --h->size;
 186       return 1;
 187     }
 188   }
 189
 190   return 0;
 191 }
 192 #endif
 193
 194 void *
 195 Curl_hash_pick(curl_hash *h, char *key, size_t key_len)
 196 {
 197   curl_llist_element *le;
 198   curl_hash_element  *he;
 199   curl_llist *l = FETCH_LIST(h, key, key_len);
 200
 201   for (le = l->head;
 202        le;
 203        le = le->next) {
 204     he = le->ptr;
 205     if (hash_key_compare(he->key, he->key_len, key, key_len)) {
 206       return he->ptr;
 207     }
 208   }
 209
 210   return NULL;
 211 }
 212
 213 #if defined(CURLDEBUG) && defined(AGGRESIVE_TEST)
 214 void
 215 Curl_hash_apply(curl_hash *h, void *user,
 216                 void (*cb)(void *user, void *ptr))
 217 {
 218   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(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   }
 240
 241   free(h->table);
 242 }
 243
 244 void
 245 Curl_hash_clean_with_criterium(curl_hash *h, void *user,
 246                                int (*comp)(void *, void *))
 247 {
 248   curl_llist_element *le;
 249   curl_llist_element *lnext;
 250   curl_llist *list;
 251   int i;
 252
 253   for (i = 0; i < h->slots; ++i) {
 254     list = h->table[i];
 255     le = list->head; /* get first list entry */
 256     while(le) {
 257       curl_hash_element *he = le->ptr;
 258       lnext = le->next;
 259       /* ask the callback function if we shall remove this entry or not */
 260       if (comp(user, he->ptr)) {
 261         Curl_llist_remove(list, le, (void *) h);
 262         --h->size; /* one less entry in the hash now */
 263       }
 264       le = lnext;
 265     }
 266   }
 267 }
 268
 269 #if 0
 270 int
 271 Curl_hash_count(curl_hash *h)
 272 {
 273   return h->size;
 274 }
 275 #endif
 276
 277 void
 278 Curl_hash_destroy(curl_hash *h)
 279 {
 280   if (!h)
 281     return;
 282
 283   Curl_hash_clean(h);
 284   free(h);
 285 }
 286