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