/src/curl/lib/uint-hash.c

Source
/***************************************************************************
 *                                  _   _ ____  _
 *  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 "uint-hash.h"

/* random patterns for API verification */
#ifdef DEBUGBUILD
#define CURL_UINT32_HASHINIT 0x7117e779
#endif

static uint32_t uint32_hash_hash(uint32_t id, uint32_t slots)
{
  return (id % slots);
}


struct uint_hash_entry {
  struct uint_hash_entry *next;
  void   *value;
  uint32_t id;
};

void Curl_uint32_hash_init(struct uint_hash *h,
                           uint32_t slots,
                           Curl_uint32_hash_dtor *dtor)
{
  DEBUGASSERT(h);
  DEBUGASSERT(slots);

  h->table = NULL;
  h->dtor = dtor;
  h->size = 0;
  h->slots = slots;
#ifdef DEBUGBUILD
  h->init = CURL_UINT32_HASHINIT;
#endif
}

static struct uint_hash_entry *uint32_hash_mk_entry(uint32_t id, void *value)
{
  struct uint_hash_entry *e;

  /* allocate the struct for the hash entry */
  e = curlx_malloc(sizeof(*e));
  if(e) {
    e->id = id;
    e->next = NULL;
    e->value = value;
  }
  return e;
}

static void uint32_hash_entry_clear(struct uint_hash *h,
                                    struct uint_hash_entry *e)
{
  DEBUGASSERT(h);
  DEBUGASSERT(e);
  if(e->value) {
    if(h->dtor)
      h->dtor(e->id, e->value);
    e->value = NULL;
  }
}

static void uint32_hash_entry_destroy(struct uint_hash *h,
                                      struct uint_hash_entry *e)
{
  uint32_hash_entry_clear(h, e);
  curlx_free(e);
}

static void uint32_hash_entry_unlink(struct uint_hash *h,
                                     struct uint_hash_entry **he_anchor,
                                     struct uint_hash_entry *he)
{
  *he_anchor = he->next;
  --h->size;
}

static void uint32_hash_elem_link(struct uint_hash *h,
                                  struct uint_hash_entry **he_anchor,
                                  struct uint_hash_entry *he)
{
  he->next = *he_anchor;
  *he_anchor = he;
  ++h->size;
}

#define CURL_UINT32_HASH_SLOT(h,id) h->table[uint32_hash_hash(id, h->slots)]
#define CURL_UINT32_HASH_SLOT_ADDR(h,id) &CURL_UINT32_HASH_SLOT(h,id)

bool Curl_uint32_hash_set(struct uint_hash *h, uint32_t id, void *value)
{
  struct uint_hash_entry *he, **slot;

  DEBUGASSERT(h);
  DEBUGASSERT(h->slots);
  DEBUGASSERT(h->init == CURL_UINT32_HASHINIT);
  if(!h->table) {
    h->table = curlx_calloc(h->slots, sizeof(*he));
    if(!h->table)
      return FALSE; /* OOM */
  }

  slot = CURL_UINT32_HASH_SLOT_ADDR(h, id);
  for(he = *slot; he; he = he->next) {
    if(he->id == id) {
      /* existing key entry, overwrite by clearing old pointer */
      uint32_hash_entry_clear(h, he);
      he->value = value;
      return TRUE;
    }
  }

  he = uint32_hash_mk_entry(id, value);
  if(!he)
    return FALSE; /* OOM */

  uint32_hash_elem_link(h, slot, he);
  return TRUE;
}

bool Curl_uint32_hash_remove(struct uint_hash *h, uint32_t id)
{
  DEBUGASSERT(h);
  DEBUGASSERT(h->slots);
  DEBUGASSERT(h->init == CURL_UINT32_HASHINIT);
  if(h->table) {
    struct uint_hash_entry *he, **he_anchor;

    he_anchor = CURL_UINT32_HASH_SLOT_ADDR(h, id);
    while(*he_anchor) {
      he = *he_anchor;
      if(id == he->id) {
        uint32_hash_entry_unlink(h, he_anchor, he);
        uint32_hash_entry_destroy(h, he);
        return TRUE;
      }
      he_anchor = &he->next;
    }
  }
  return FALSE;
}

void *Curl_uint32_hash_get(struct uint_hash *h, uint32_t id)
{
  DEBUGASSERT(h);
  DEBUGASSERT(h->init == CURL_UINT32_HASHINIT);
  if(h->table) {
    struct uint_hash_entry *he;
    DEBUGASSERT(h->slots);
    he = CURL_UINT32_HASH_SLOT(h, id);
    while(he) {
      if(id == he->id) {
        return he->value;
      }
      he = he->next;
    }
  }
  return NULL;
}

static void uint_hash_clear(struct uint_hash *h)
{
  if(h && h->table) {
    struct uint_hash_entry *he, **he_anchor;
    size_t i;
    DEBUGASSERT(h->init == CURL_UINT32_HASHINIT);
    for(i = 0; i < h->slots; ++i) {
      he_anchor = &h->table[i];
      while(*he_anchor) {
        he = *he_anchor;
        uint32_hash_entry_unlink(h, he_anchor, he);
        uint32_hash_entry_destroy(h, he);
      }
    }
  }
}

#ifdef UNITTESTS
UNITTEST void Curl_uint32_hash_clear(struct uint_hash *h)
{
  uint_hash_clear(h);
}
#endif

void Curl_uint32_hash_destroy(struct uint_hash *h)
{
  DEBUGASSERT(h->init == CURL_UINT32_HASHINIT);
  if(h->table) {
    uint_hash_clear(h);
    Curl_safefree(h->table);
  }
  DEBUGASSERT(h->size == 0);
  h->slots = 0;
}

uint32_t Curl_uint32_hash_count(struct uint_hash *h)
{
  DEBUGASSERT(h->init == CURL_UINT32_HASHINIT);
  return h->size;
}

void Curl_uint32_hash_visit(struct uint_hash *h,
                            Curl_uint32_hash_visit_cb *cb,
                            void *user_data)
{
  if(h && h->table && cb) {
    struct uint_hash_entry *he;
    size_t i;
    DEBUGASSERT(h->init == CURL_UINT32_HASHINIT);
    for(i = 0; i < h->slots; ++i) {
      for(he = h->table[i]; he; he = he->next) {
        if(!cb(he->id, he->value, user_data))
          return;
      }
    }
  }
}

Coverage Report

Created: 2025-12-03 07:02

Line	Count	Source
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 "uint-hash.h"
30
31		/* random patterns for API verification */
32		#ifdef DEBUGBUILD
33	0	#define CURL_UINT32_HASHINIT 0x7117e779
34		#endif
35
36		static uint32_t uint32_hash_hash(uint32_t id, uint32_t slots)
37	0	{
38	0	return (id % slots);
39	0	}
40
41
42		struct uint_hash_entry {
43		struct uint_hash_entry *next;
44		void *value;
45		uint32_t id;
46		};
47
48		void Curl_uint32_hash_init(struct uint_hash *h,
49		uint32_t slots,
50		Curl_uint32_hash_dtor *dtor)
51	0	{
52	0	DEBUGASSERT(h);
53	0	DEBUGASSERT(slots);
54
55	0	h->table = NULL;
56	0	h->dtor = dtor;
57	0	h->size = 0;
58	0	h->slots = slots;
59	0	#ifdef DEBUGBUILD
60	0	h->init = CURL_UINT32_HASHINIT;
61	0	#endif
62	0	}
63
64		static struct uint_hash_entry uint32_hash_mk_entry(uint32_t id, void value)
65	0	{
66	0	struct uint_hash_entry *e;
67
68		/* allocate the struct for the hash entry */
69	0	e = curlx_malloc(sizeof(*e));
70	0	if(e) {
71	0	e->id = id;
72	0	e->next = NULL;
73	0	e->value = value;
74	0	}
75	0	return e;
76	0	}
77
78		static void uint32_hash_entry_clear(struct uint_hash *h,
79		struct uint_hash_entry *e)
80	0	{
81	0	DEBUGASSERT(h);
82	0	DEBUGASSERT(e);
83	0	if(e->value) {
84	0	if(h->dtor)
85	0	h->dtor(e->id, e->value);
86	0	e->value = NULL;
87	0	}
88	0	}
89
90		static void uint32_hash_entry_destroy(struct uint_hash *h,
91		struct uint_hash_entry *e)
92	0	{
93	0	uint32_hash_entry_clear(h, e);
94	0	curlx_free(e);
95	0	}
96
97		static void uint32_hash_entry_unlink(struct uint_hash *h,
98		struct uint_hash_entry **he_anchor,
99		struct uint_hash_entry *he)
100	0	{
101	0	*he_anchor = he->next;
102	0	--h->size;
103	0	}
104
105		static void uint32_hash_elem_link(struct uint_hash *h,
106		struct uint_hash_entry **he_anchor,
107		struct uint_hash_entry *he)
108	0	{
109	0	he->next = *he_anchor;
110	0	*he_anchor = he;
111	0	++h->size;
112	0	}
113
114	0	#define CURL_UINT32_HASH_SLOT(h,id) h->table[uint32_hash_hash(id, h->slots)]
115	0	#define CURL_UINT32_HASH_SLOT_ADDR(h,id) &CURL_UINT32_HASH_SLOT(h,id)
116
117		bool Curl_uint32_hash_set(struct uint_hash h, uint32_t id, void value)
118	0	{
119	0	struct uint_hash_entry he, *slot;
120
121	0	DEBUGASSERT(h);
122	0	DEBUGASSERT(h->slots);
123	0	DEBUGASSERT(h->init == CURL_UINT32_HASHINIT);
124	0	if(!h->table) {
125	0	h->table = curlx_calloc(h->slots, sizeof(*he));
126	0	if(!h->table)
127	0	return FALSE; /* OOM */
128	0	}
129
130	0	slot = CURL_UINT32_HASH_SLOT_ADDR(h, id);
131	0	for(he = *slot; he; he = he->next) {
132	0	if(he->id == id) {
133		/* existing key entry, overwrite by clearing old pointer */
134	0	uint32_hash_entry_clear(h, he);
135	0	he->value = value;
136	0	return TRUE;
137	0	}
138	0	}
139
140	0	he = uint32_hash_mk_entry(id, value);
141	0	if(!he)
142	0	return FALSE; /* OOM */
143
144	0	uint32_hash_elem_link(h, slot, he);
145	0	return TRUE;
146	0	}
147
148		bool Curl_uint32_hash_remove(struct uint_hash *h, uint32_t id)
149	0	{
150	0	DEBUGASSERT(h);
151	0	DEBUGASSERT(h->slots);
152	0	DEBUGASSERT(h->init == CURL_UINT32_HASHINIT);
153	0	if(h->table) {
154	0	struct uint_hash_entry he, *he_anchor;
155
156	0	he_anchor = CURL_UINT32_HASH_SLOT_ADDR(h, id);
157	0	while(*he_anchor) {
158	0	he = *he_anchor;
159	0	if(id == he->id) {
160	0	uint32_hash_entry_unlink(h, he_anchor, he);
161	0	uint32_hash_entry_destroy(h, he);
162	0	return TRUE;
163	0	}
164	0	he_anchor = &he->next;
165	0	}
166	0	}
167	0	return FALSE;
168	0	}
169
170		void Curl_uint32_hash_get(struct uint_hash h, uint32_t id)
171	0	{
172	0	DEBUGASSERT(h);
173	0	DEBUGASSERT(h->init == CURL_UINT32_HASHINIT);
174	0	if(h->table) {
175	0	struct uint_hash_entry *he;
176	0	DEBUGASSERT(h->slots);
177	0	he = CURL_UINT32_HASH_SLOT(h, id);
178	0	while(he) {
179	0	if(id == he->id) {
180	0	return he->value;
181	0	}
182	0	he = he->next;
183	0	}
184	0	}
185	0	return NULL;
186	0	}
187
188		static void uint_hash_clear(struct uint_hash *h)
189	0	{
190	0	if(h && h->table) {
191	0	struct uint_hash_entry he, *he_anchor;
192	0	size_t i;
193	0	DEBUGASSERT(h->init == CURL_UINT32_HASHINIT);
194	0	for(i = 0; i < h->slots; ++i) {
195	0	he_anchor = &h->table[i];
196	0	while(*he_anchor) {
197	0	he = *he_anchor;
198	0	uint32_hash_entry_unlink(h, he_anchor, he);
199	0	uint32_hash_entry_destroy(h, he);
200	0	}
201	0	}
202	0	}
203	0	}
204
205		#ifdef UNITTESTS
206		UNITTEST void Curl_uint32_hash_clear(struct uint_hash *h)
207		{
208		uint_hash_clear(h);
209		}
210		#endif
211
212		void Curl_uint32_hash_destroy(struct uint_hash *h)
213	0	{
214	0	DEBUGASSERT(h->init == CURL_UINT32_HASHINIT);
215	0	if(h->table) {
216	0	uint_hash_clear(h);
217	0	Curl_safefree(h->table);
218	0	}
219	0	DEBUGASSERT(h->size == 0);
220	0	h->slots = 0;
221	0	}
222
223		uint32_t Curl_uint32_hash_count(struct uint_hash *h)
224	0	{
225	0	DEBUGASSERT(h->init == CURL_UINT32_HASHINIT);
226	0	return h->size;
227	0	}
228
229		void Curl_uint32_hash_visit(struct uint_hash *h,
230		Curl_uint32_hash_visit_cb *cb,
231		void *user_data)
232	0	{
233	0	if(h && h->table && cb) {
234	0	struct uint_hash_entry *he;
235	0	size_t i;
236	0	DEBUGASSERT(h->init == CURL_UINT32_HASHINIT);
237	0	for(i = 0; i < h->slots; ++i) {
238	0	for(he = h->table[i]; he; he = he->next) {
239	0	if(!cb(he->id, he->value, user_data))
240	0	return;
241	0	}
242	0	}
243	0	}
244	0	}