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