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