/src/curl/lib/hash.c

Source (jump to first uncovered line)
/***************************************************************************
 *                                  _   _ ____  _
 *  Project                     ___| | | |  _ \| |
 *                             / __| | | | |_) | |
 *                            | (__| |_| |  _ <| |___
 *                             \___|\___/|_| \_\_____|
 *
 * Copyright (C) Daniel Stenberg, <daniel@haxx.se>, et al.
 *
 * This software is licensed as described in the file COPYING, which
 * you should have received as part of this distribution. The terms
 * are also available at https://curl.se/docs/copyright.html.
 *
 * You may opt to use, copy, modify, merge, publish, distribute and/or sell
 * copies of the Software, and permit persons to whom the Software is
 * furnished to do so, under the terms of the COPYING file.
 *
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
 * KIND, either express or implied.
 *
 * SPDX-License-Identifier: curl
 *
 ***************************************************************************/

#include "curl_setup.h"

#include <curl/curl.h>

#include "hash.h"
#include "llist.h"
#include "curl_memory.h"

/* The last #include file should be: */
#include "memdebug.h"

static void
hash_element_dtor(void *user, void *element)
{
  struct Curl_hash *h = (struct Curl_hash *) user;
  struct Curl_hash_element *e = (struct Curl_hash_element *) element;

  if(e->ptr) {
    h->dtor(e->ptr);
    e->ptr = NULL;
  }

  e->key_len = 0;

  free(e);
}

/* Initializes a hash structure.
 * Return 1 on error, 0 is fine.
 *
 * @unittest: 1602
 * @unittest: 1603
 */
void
Curl_hash_init(struct Curl_hash *h,
               int slots,
               hash_function hfunc,
               comp_function comparator,
               Curl_hash_dtor dtor)
{
  DEBUGASSERT(h);
  DEBUGASSERT(slots);
  DEBUGASSERT(hfunc);
  DEBUGASSERT(comparator);
  DEBUGASSERT(dtor);

  h->table = NULL;
  h->hash_func = hfunc;
  h->comp_func = comparator;
  h->dtor = dtor;
  h->size = 0;
  h->slots = slots;
}

static struct Curl_hash_element *
mk_hash_element(const void *key, size_t key_len, const void *p)
{
  /* allocate the struct plus memory after it to store the key */
  struct Curl_hash_element *he = malloc(sizeof(struct Curl_hash_element) +
                                        key_len);
  if(he) {
    /* copy the key */
    memcpy(he->key, key, key_len);
    he->key_len = key_len;
    he->ptr = (void *) p;
  }
  return he;
}

#define FETCH_LIST(x,y,z) &x->table[x->hash_func(y, z, x->slots)]

/* Insert the data in the hash. If there already was a match in the hash, that
 * data is replaced. This function also "lazily" allocates the table if
 * needed, as it isn't done in the _init function (anymore).
 *
 * @unittest: 1305
 * @unittest: 1602
 * @unittest: 1603
 */
void *
Curl_hash_add(struct Curl_hash *h, void *key, size_t key_len, void *p)
{
  struct Curl_hash_element  *he;
  struct Curl_llist_element *le;
  struct Curl_llist *l;

  DEBUGASSERT(h);
  DEBUGASSERT(h->slots);
  if(!h->table) {
    int i;
    h->table = malloc(h->slots * sizeof(struct Curl_llist));
    if(!h->table)
      return NULL; /* OOM */
    for(i = 0; i < h->slots; ++i)
      Curl_llist_init(&h->table[i], hash_element_dtor);
  }

  l = FETCH_LIST(h, key, key_len);

  for(le = l->head; le; le = le->next) {
    he = (struct Curl_hash_element *) le->ptr;
    if(h->comp_func(he->key, he->key_len, key, key_len)) {
      Curl_llist_remove(l, le, (void *)h);
      --h->size;
      break;
    }
  }

  he = mk_hash_element(key, key_len, p);
  if(he) {
    Curl_llist_insert_next(l, l->tail, he, &he->list);
    ++h->size;
    return p; /* return the new entry */
  }

  return NULL; /* failure */
}

/* Remove the identified hash entry.
 * Returns non-zero on failure.
 *
 * @unittest: 1603
 */
int Curl_hash_delete(struct Curl_hash *h, void *key, size_t key_len)
{
  struct Curl_llist_element *le;
  struct Curl_llist *l;

  DEBUGASSERT(h);
  DEBUGASSERT(h->slots);
  if(h->table) {
    l = FETCH_LIST(h, key, key_len);

    for(le = l->head; le; le = le->next) {
      struct Curl_hash_element *he = le->ptr;
      if(h->comp_func(he->key, he->key_len, key, key_len)) {
        Curl_llist_remove(l, le, (void *) h);
        --h->size;
        return 0;
      }
    }
  }
  return 1;
}

/* Retrieves a hash element.
 *
 * @unittest: 1603
 */
void *
Curl_hash_pick(struct Curl_hash *h, void *key, size_t key_len)
{
  struct Curl_llist_element *le;
  struct Curl_llist *l;

  DEBUGASSERT(h);
  if(h->table) {
    DEBUGASSERT(h->slots);
    l = FETCH_LIST(h, key, key_len);
    for(le = l->head; le; le = le->next) {
      struct Curl_hash_element *he = le->ptr;
      if(h->comp_func(he->key, he->key_len, key, key_len)) {
        return he->ptr;
      }
    }
  }

  return NULL;
}

#if defined(DEBUGBUILD) && defined(AGGRESSIVE_TEST)
void
Curl_hash_apply(Curl_hash *h, void *user,
                void (*cb)(void *user, void *ptr))
{
  struct Curl_llist_element  *le;
  int                  i;

  for(i = 0; i < h->slots; ++i) {
    for(le = (h->table[i])->head;
        le;
        le = le->next) {
      Curl_hash_element *el = le->ptr;
      cb(user, el->ptr);
    }
  }
}
#endif

/* Destroys all the entries in the given hash and resets its attributes,
 * prepping the given hash for [static|dynamic] deallocation.
 *
 * @unittest: 1305
 * @unittest: 1602
 * @unittest: 1603
 */
void
Curl_hash_destroy(struct Curl_hash *h)
{
  if(h->table) {
    int i;
    for(i = 0; i < h->slots; ++i) {
      Curl_llist_destroy(&h->table[i], (void *) h);
    }
    Curl_safefree(h->table);
  }
  h->size = 0;
  h->slots = 0;
}

/* Removes all the entries in the given hash.
 *
 * @unittest: 1602
 */
void
Curl_hash_clean(struct Curl_hash *h)
{
  Curl_hash_clean_with_criterium(h, NULL, NULL);
}

/* Cleans all entries that pass the comp function criteria. */
void
Curl_hash_clean_with_criterium(struct Curl_hash *h, void *user,
                               int (*comp)(void *, void *))
{
  struct Curl_llist_element *le;
  struct Curl_llist_element *lnext;
  struct Curl_llist *list;
  int i;

  if(!h || !h->table)
    return;

  for(i = 0; i < h->slots; ++i) {
    list = &h->table[i];
    le = list->head; /* get first list entry */
    while(le) {
      struct Curl_hash_element *he = le->ptr;
      lnext = le->next;
      /* ask the callback function if we shall remove this entry or not */
      if(!comp || comp(user, he->ptr)) {
        Curl_llist_remove(list, le, (void *) h);
        --h->size; /* one less entry in the hash now */
      }
      le = lnext;
    }
  }
}

size_t Curl_hash_str(void *key, size_t key_length, size_t slots_num)
{
  const char *key_str = (const char *) key;
  const char *end = key_str + key_length;
  size_t h = 5381;

  while(key_str < end) {
    h += h << 5;
    h ^= *key_str++;
  }

  return (h % slots_num);
}

size_t Curl_str_key_compare(void *k1, size_t key1_len,
                            void *k2, size_t key2_len)
{
  if((key1_len == key2_len) && !memcmp(k1, k2, key1_len))
    return 1;

  return 0;
}

void Curl_hash_start_iterate(struct Curl_hash *hash,
                             struct Curl_hash_iterator *iter)
{
  iter->hash = hash;
  iter->slot_index = 0;
  iter->current_element = NULL;
}

struct Curl_hash_element *
Curl_hash_next_element(struct Curl_hash_iterator *iter)
{
  struct Curl_hash *h = iter->hash;

  if(!h->table)
    return NULL; /* empty hash, nothing to return */

  /* Get the next element in the current list, if any */
  if(iter->current_element)
    iter->current_element = iter->current_element->next;

  /* If we have reached the end of the list, find the next one */
  if(!iter->current_element) {
    int i;
    for(i = iter->slot_index; i < h->slots; i++) {
      if(h->table[i].head) {
        iter->current_element = h->table[i].head;
        iter->slot_index = i + 1;
        break;
      }
    }
  }

  if(iter->current_element) {
    struct Curl_hash_element *he = iter->current_element->ptr;
    return he;
  }
  iter->current_element = NULL;
  return NULL;
}

#if 0 /* useful function for debugging hashes and their contents */
void Curl_hash_print(struct Curl_hash *h,
                     void (*func)(void *))
{
  struct Curl_hash_iterator iter;
  struct Curl_hash_element *he;
  int last_index = -1;

  if(!h)
    return;

  fprintf(stderr, "=Hash dump=\n");

  Curl_hash_start_iterate(h, &iter);

  he = Curl_hash_next_element(&iter);
  while(he) {
    if(iter.slot_index != last_index) {
      fprintf(stderr, "index %d:", iter.slot_index);
      if(last_index >= 0) {
        fprintf(stderr, "\n");
      }
      last_index = iter.slot_index;
    }

    if(func)
      func(he->ptr);
    else
      fprintf(stderr, " [%p]", (void *)he->ptr);

    he = Curl_hash_next_element(&iter);
  }
  fprintf(stderr, "\n");
}
#endif

Coverage Report

Created: 2023-03-26 06:11

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