lib/hash.c

   1 /*****************************************************************************
   2  *                                  _   _ ____  _
   3  *  Project                     ___| | | |  _ \| |
   4  *                             / __| | | | |_) | |
   5  *                            | (__| |_| |  _ <| |___
   6  *                             \___|\___/|_| \_\_____|
   7  *
   8  * Copyright (C) 1998 - 2002, Daniel Stenberg, <daniel@haxx.se>, et al.
   9  *
  10  * In order to be useful for every potential user, curl and libcurl are
  11  * dual-licensed under the MPL and the MIT/X-derivate licenses.
  12  *
  13  * You may opt to use, copy, modify, merge, publish, distribute and/or sell
  14  * copies of the Software, and permit persons to whom the Software is
  15  * furnished to do so, under the terms of the MPL or the MIT/X-derivate
  16  * licenses. You may pick one of these licenses.
  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 #include "hash.h"
  29 #include "llist.h"
  30
  31 #ifdef MALLOCDEBUG
  32 /* this must be the last include file */
  33 #include "memdebug.h"
  34 #endif
  35
  36
  37 static unsigned long
  38 curl_hash_str(const char *key, unsigned int key_length)
  39 {
  40   register unsigned long h = 0;
  41   register unsigned long g;
  42   register char *p = (char *) key;
  43   register char *end = (char *) key + key_length;
  44
  45   while (p < end) {
  46     h = (h << 4) + *p++;
  47     if ((g = (h & 0xF0000000))) {
  48       h = h ^ (g >> 24);
  49       h = h ^ g;
  50     }
  51   }
  52
  53   return h;
  54 }
  55
  56 static unsigned long
  57 curl_hash_num(unsigned long key)
  58 {
  59   key += ~(key << 15);
  60   key ^= (key >> 10);
  61   key += (key << 3);
  62   key ^= (key >> 6);
  63   key += (key << 11);
  64   key ^= (key >> 16);
  65
  66   return key;
  67 }
  68
  69 static void
  70 hash_element_dtor(void *u, void *ele)
  71 {
  72   curl_hash_element *e = (curl_hash_element *) ele;
  73   curl_hash         *h = (curl_hash *) u;
  74
  75   if (e->key.type == CURL_HASH_KEY_IS_STRING) {
  76     free(e->key.value.str.val);
  77   }
  78   h->dtor(e->ptr);
  79
  80   free(e);
  81   e = NULL;
  82 }
  83
  84 void
  85 curl_hash_init(curl_hash *h, int slots, curl_hash_dtor dtor)
  86 {
  87   int i;
  88
  89   h->dtor = dtor;
  90   h->size = 0;
  91   h->slots = slots;
  92
  93   h->table = (curl_llist **) malloc(slots * sizeof(curl_llist *));
  94   for (i = 0; i < h->slots; ++i) {
  95     h->table[i] = curl_llist_alloc((curl_llist_dtor) hash_element_dtor);
  96   }
  97 }
  98
  99 curl_hash *
 100 curl_hash_alloc(int slots, curl_hash_dtor dtor)
 101 {
 102   curl_hash *h;
 103
 104   h = (curl_hash *)malloc(sizeof(curl_hash));
 105   if(NULL == h)
 106     return NULL;
 107
 108   curl_hash_init(h, slots, dtor);
 109
 110   return h;
 111 }
 112
 113 #define FIND_SLOT(__h, __s_key, __s_key_len, __n_key) \
 114   ((__s_key ? curl_hash_str(__s_key, __s_key_len) : curl_hash_num(__n_key)) % (__h)->slots)
 115
 116 #define KEY_CREATE(__k, __s_key, __s_key_len, __n_key, __dup) \
 117   if (__s_key) { \
 118     if (__dup) { \
 119       (__k)->value.str.val = (char *) malloc(__s_key_len); \
 120       memcpy((__k)->value.str.val, __s_key, __s_key_len); \
 121     } else { \
 122       (__k)->value.str.val = __s_key; \
 123     } \
 124     (__k)->value.str.len = __s_key_len; \
 125     (__k)->type = CURL_HASH_KEY_IS_STRING; \
 126   } else { \
 127     (__k)->value.num = __n_key; \
 128     (__k)->type = CURL_HASH_KEY_IS_NUM; \
 129   }
 130
 131 #define MIN(a, b) (a > b ? b : a)
 132
 133 static int
 134 curl_hash_key_compare(curl_hash_key *key1, curl_hash_key *key2)
 135 {
 136   if (key1->type == CURL_HASH_KEY_IS_NUM) {
 137     if (key2->type == CURL_HASH_KEY_IS_STRING)
 138       return 0;
 139
 140     if (key1->value.num == key2->value.num)
 141       return 1;
 142   } else {
 143     if (key2->type == CURL_HASH_KEY_IS_NUM)
 144       return 0;
 145
 146     if (memcmp(key1->value.str.val, key2->value.str.val,
 147                MIN(key1->value.str.len, key2->value.str.len)) == 0)
 148       return 1;
 149   }
 150
 151   return 0;
 152 }
 153
 154 int
 155 curl_hash_add_or_update(curl_hash *h, char *str_key, unsigned int str_key_len,
 156                         unsigned long num_key, const void *p)
 157 {
 158   curl_hash_element  *e;
 159   curl_hash_key       tmp;
 160   curl_llist         *l;
 161   curl_llist_element *le;
 162   int                slot;
 163
 164   slot = FIND_SLOT(h, str_key, str_key_len, num_key);
 165   l = h->table[slot];
 166   KEY_CREATE(&tmp, str_key, str_key_len, num_key, 0);
 167   for (le = CURL_LLIST_HEAD(l); le != NULL; le = CURL_LLIST_NEXT(le)) {
 168     if (curl_hash_key_compare(&tmp, &((curl_hash_element *) CURL_LLIST_VALP(le))->key)) {
 169       curl_hash_element *to_update = CURL_LLIST_VALP(le);
 170       h->dtor(to_update->ptr);
 171       to_update->ptr = (void *) p;
 172       return 1;
 173     }
 174   }
 175
 176   e = (curl_hash_element *) malloc(sizeof(curl_hash_element));
 177   KEY_CREATE(&e->key, str_key, str_key_len, num_key, 1);
 178   e->ptr = (void *) p;
 179
 180   if (curl_llist_insert_next(l, CURL_LLIST_TAIL(l), e)) {
 181     ++h->size;
 182     return 1;
 183   } else {
 184     return 0;
 185   }
 186 }
 187
 188 int
 189 curl_hash_extended_delete(curl_hash *h, char *str_key, unsigned int str_key_len,
 190                           unsigned long num_key)
 191 {
 192   curl_llist         *l;
 193   curl_llist_element *le;
 194   curl_hash_key       tmp;
 195   int                slot;
 196
 197   slot = FIND_SLOT(h, str_key, str_key_len, num_key);
 198   l = h->table[slot];
 199
 200   KEY_CREATE(&tmp, str_key, str_key_len, num_key, 0);
 201   for (le = CURL_LLIST_HEAD(l); le != NULL; le = CURL_LLIST_NEXT(le)) {
 202     if (curl_hash_key_compare(&tmp, &((curl_hash_element *) CURL_LLIST_VALP(le))->key)) {
 203       curl_llist_remove(l, le, (void *) h);
 204       --h->size;
 205       return 1;
 206     }
 207   }
 208
 209   return 0;
 210 }
 211
 212 int
 213 curl_hash_extended_find(curl_hash *h, char *str_key, unsigned int str_key_len,
 214                         unsigned long num_key, void **p)
 215 {
 216   curl_llist         *l;
 217   curl_llist_element *le;
 218   curl_hash_key       tmp;
 219   int                slot;
 220
 221   slot = FIND_SLOT(h, str_key, str_key_len, num_key);
 222   l = h->table[slot];
 223
 224   KEY_CREATE(&tmp, str_key, str_key_len, num_key, 0);
 225   for (le = CURL_LLIST_HEAD(l); le != NULL; le = CURL_LLIST_NEXT(le)) {
 226     if (curl_hash_key_compare(&tmp, &((curl_hash_element *) CURL_LLIST_VALP(le))->key)) {
 227       *p = ((curl_hash_element *) CURL_LLIST_VALP(le))->ptr;
 228       return 1;
 229     }
 230   }
 231
 232   return 0;
 233 }
 234
 235 void
 236 curl_hash_apply(curl_hash *h, void *user, void (*cb)(void *, curl_hash_element *))
 237 {
 238   curl_llist_element  *le;
 239   int                  i;
 240
 241   for (i = 0; i < h->slots; ++i) {
 242     for (le = CURL_LLIST_HEAD(h->table[i]); le != NULL; le = CURL_LLIST_NEXT(le)) {
 243       cb(user, (curl_hash_element *) CURL_LLIST_VALP(le));
 244     }
 245   }
 246 }
 247
 248 void
 249 curl_hash_clean(curl_hash *h)
 250 {
 251   int i;
 252
 253   for (i = 0; i < h->slots; ++i) {
 254     curl_llist_destroy(h->table[i], (void *) h);
 255   }
 256
 257   free(h->table);
 258   h->table = NULL;
 259 }
 260
 261 size_t
 262 curl_hash_count(curl_hash *h)
 263 {
 264   return h->size;
 265 }
 266
 267 void
 268 curl_hash_destroy(curl_hash *h)
 269 {
 270   if (!h) {
 271     return;
 272   }
 273
 274   curl_hash_clean(h);
 275   free(h);
 276   h = NULL;
 277 }
 278
 279 /*
 280  * local variables:
 281  * eval: (load-file "../curl-mode.el")
 282  * end:
 283  * vim600: fdm=marker
 284  * vim: et sw=2 ts=2 sts=2 tw=78
 285  */