/src/curl/lib/u32_ptrset.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 "u32_ptrset.h"

/* random patterns for API verification */
#ifdef DEBUGBUILD
#define CURL_U32_PTRSET_MAGIC 0x75703272
#endif

#define CURL_U32_PTRSET_DEBUG      0

#ifndef CURL_SWAP
#define CURL_SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))
#endif

#define CURL_U32_SLOT_CNT(bits)        ((bits) ? (1U << (bits)) : 0)
#define CURL_U32_PTRSET_SLOT_CNT(s)    CURL_U32_SLOT_CNT((s)->slotbits)
#define CURL_U32_PTRSET_SLOT_IDX(s, i) (uint32_t)((i) & (s)->slotmask)

/* A hashset for tuples (id, ptr) using Robin Hood Hashing.
 * <https://www.cs.cornell.edu/courses/JavaAndDS/files/hashing_RobinHood.pdf>
 * The basic idea here to handle collisions by robbing "rich" entries and
 * giving to the "poor":
 * - We have an array: (id, ptr) are ideally placed at index "id % size".
 * - If slot at index is already occupied, we have a collision.
 * - A simple collision strategy would look at the next index, and the
 *   next until finding an empty slot.
 * - The drawback is that this may lead to many checks on lookups, as it
 *   will need to also look at subsequent slots until it finds the match.
 *   The amount of lookups is the "probe sequence length" (psl) and this
 *   may vary greatly between entries.
 * - Robin Hood Hashing balances the 'psl's of all entries more evenly:
 *   - psl == 0 means an entry is in exactly the right slot
 *   - psl == 1 means it is in the slot right after. psl == 2 is the slot
 *     after that, etc.
 *   - when inserting a new entry, track its psl. Finding a slot where
 *     the existing entry has a lower psl makes a swap. Put the new entry
 *     and its psl there, take the previous entry and its psl and find
 *     the next best slot for the previous entry. */
void Curl_u32_ptrset_init(struct u32_ptrset *set,
                          Curl_u32_ptrset_dtor *dtor)
{
  memset(set, 0, sizeof(*set));
  set->dtor = dtor;
#ifdef DEBUGBUILD
  set->init = CURL_U32_PTRSET_MAGIC;
#endif
}

void Curl_u32_ptrset_clear(struct u32_ptrset *set)
{
  uint32_t i;
  DEBUGASSERT(set->init == CURL_U32_PTRSET_MAGIC);
  if(set->dtor)
    for(i = 0; i < CURL_U32_PTRSET_SLOT_CNT(set); ++i)
      if(set->data[i])
        set->dtor(set->ids[i], set->data[i]);

  curlx_safefree(set->data);
  Curl_u32_ptrset_init(set, set->dtor);
}

static void u32_ptrset_add(struct u32_ptrset *set, uint32_t id, void *ptr)
{
  uint32_t i = CURL_U32_PTRSET_SLOT_IDX(set, id);
  uint32_t psl = 0;
  while(set->data[i]) {
    if(psl > set->psl[i]) { /* SWAP */
      void *tmpdata;
#if CURL_U32_PTRSET_DEBUG
  curl_mfprintf(stderr, "u32_ptrset_add %u=%p to idx=%u\n", id, ptr, i);
#endif
      tmpdata = set->data[i];
      set->data[i] = ptr;
      ptr = tmpdata;
      CURL_SWAP(set->psl[i], psl);
      CURL_SWAP(set->ids[i], id);
    }
    i = CURL_U32_PTRSET_SLOT_IDX(set, i + 1);
    ++psl;
  }
  set->ids[i] = id;
  set->data[i] = ptr;
  set->psl[i] = psl;
  ++set->count;
#if CURL_U32_PTRSET_DEBUG
  curl_mfprintf(stderr, "u32_ptrset_add %u=%p to idx=%u\n", id, ptr, i);
#endif
}

static bool u32_ptrset_grow(struct u32_ptrset *set)
{
  uint32_t i, *prev_ids;
  uint8_t nslotbits, pslotbits;
  void **prev_data;
  size_t nslots;
  const size_t slot_size = (sizeof(void *) + (2 * sizeof(uint32_t)));
  void *d;

  if(set->slotbits >= 31)
    return FALSE;
  nslotbits = set->slotbits ? (uint8_t)(set->slotbits + 1) : 5;
  nslots = CURL_U32_SLOT_CNT(nslotbits);
  if(nslots > (SIZE_MAX / slot_size)) /* 32-bit arch may trigger here */
    return FALSE;
#if CURL_U32_PTRSET_DEBUG
  curl_mfprintf(stderr, "u32_ptrset_grow from bits=%d to %d, slots=%zu\n",
                set->slotbits, nslotbits, nslots);
#endif
  d = curlx_calloc(1, nslots * slot_size);
  if(!d)
    return FALSE;

  prev_data = set->data;
  prev_ids = set->ids;
  pslotbits = set->slotbits;
#if defined(__GNUC__) && __GNUC__ >= 13
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wanalyzer-allocation-size"
#endif
  set->data = d;
  set->ids = (uint32_t *)(set->data + nslots);
  set->psl = (uint32_t *)(set->ids + nslots);
#if defined(__GNUC__) && __GNUC__ >= 13
#pragma GCC diagnostic pop
#endif

  set->slotbits = nslotbits;
  set->slotmask = (uint32_t)((1U << set->slotbits) - 1);
  set->count = 0;
  /* re-add previous entries */
  for(i = 0; i < CURL_U32_SLOT_CNT(pslotbits); ++i) {
    if(prev_data[i])
      u32_ptrset_add(set, prev_ids[i], prev_data[i]);
  }
  if(prev_data)
    curlx_free(prev_data);
  return TRUE;
}

static bool u32_ptrset_get_index(struct u32_ptrset *set,
                                 uint32_t id, uint32_t *pindex)
{
  uint32_t i = CURL_U32_PTRSET_SLOT_IDX(set, id);
  uint32_t psl = 0;
  if(!set->data)
    return FALSE;
  while(set->data[i] && (psl <= set->psl[i])) {
    if(set->ids[i] == id) {
      *pindex = i;
#if CURL_U32_PTRSET_DEBUG
      curl_mfprintf(stderr, "u32_ptrset_index %u=%p at idx=%u\n",
                    id, set->data[i], i);
#endif
      return TRUE;
    }
    i = CURL_U32_PTRSET_SLOT_IDX(set, i + 1);
    ++psl;
  }
#if CURL_U32_PTRSET_DEBUG
  curl_mfprintf(stderr, "u32_ptrset_index %u not found\n", id);
#endif
  *pindex = 0;
  return FALSE;
}

uint32_t Curl_u32_ptrset_count(struct u32_ptrset *set)
{
  return set->count;
}

void *Curl_u32_ptrset_get(struct u32_ptrset *set, uint32_t id)
{
  uint32_t i;
  DEBUGASSERT(set->init == CURL_U32_PTRSET_MAGIC);
  if(u32_ptrset_get_index(set, id, &i))
    return set->data[i];
  return NULL;
}

CURLcode Curl_u32_ptrset_set(struct u32_ptrset *set,
                             uint32_t id, void *ptr)
{
  uint32_t i;

  DEBUGASSERT(set->init == CURL_U32_PTRSET_MAGIC);
  if(!ptr) {
    Curl_u32_ptrset_unset(set, id);
    return CURLE_OK;
  }

  if(u32_ptrset_get_index(set, id, &i)) {
    /* `id` is in set, replace value */
    if(set->dtor && (set->data[i] != ptr))
      set->dtor(set->ids[i], set->data[i]);
#if CURL_U32_PTRSET_DEBUG
    curl_mfprintf(stderr, "u32_ptrset_set replace %u=%p at idx=%u\n",
                  id, ptr, i);
#endif
    set->data[i] = ptr;
    return CURLE_OK;
  }
  /* `id` not in set yet, grow if full */
  if((set->count >= CURL_U32_PTRSET_SLOT_CNT(set)) &&
     !u32_ptrset_grow(set)) {
    return CURLE_OUT_OF_MEMORY;
  }

  u32_ptrset_add(set, id, ptr);
  return CURLE_OK;
}

static void u32_ptrset_unset(struct u32_ptrset *set, uint32_t id)
{
  uint32_t i, j;

  DEBUGASSERT(set->init == CURL_U32_PTRSET_MAGIC);
  if(u32_ptrset_get_index(set, id, &i)) {
    /* `id` is in set */
#if CURL_U32_PTRSET_DEBUG
    curl_mfprintf(stderr, "u32_ptrset_unset %u at idx=%u\n", id, i);
#endif
    if(set->dtor)
      set->dtor(set->ids[i], set->data[i]);
    set->data[i] = NULL;
    set->ids[i] = set->psl[i] = 0;
    --set->count;
    j = CURL_U32_PTRSET_SLOT_IDX(set, i + 1);
    /* shift all entries with positive psl "down" */
    while(set->data[j] && set->psl[j]) {
      set->data[i] = set->data[j];
      set->ids[i] = set->ids[j];
      set->psl[i] = set->psl[j] - 1;
      set->data[j] = NULL;
      set->ids[j] = set->psl[j] = 0;
      i = j;
      j = CURL_U32_PTRSET_SLOT_IDX(set, i + 1);
    }
  }
}

void Curl_u32_ptrset_unset(struct u32_ptrset *set, uint32_t id)
{
  u32_ptrset_unset(set, id);
}

void Curl_u32_ptrset_visit(struct u32_ptrset *set,
                            Curl_u32_ptrset_visit_cb *cb,
                            void *user_data)
{
  uint32_t i;
  for(i = 0; i < CURL_U32_PTRSET_SLOT_CNT(set); ++i) {
    if(set->data[i] && !cb(set->ids[i], set->data[i], user_data))
      break;
  }
}

Coverage Report

Created: 2026-10-22 06:48

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		#include "curl_setup.h"
25
26		#include "u32_ptrset.h"
27
28		/* random patterns for API verification */
29		#ifdef DEBUGBUILD
30	0	#define CURL_U32_PTRSET_MAGIC 0x75703272
31		#endif
32
33		#define CURL_U32_PTRSET_DEBUG 0
34
35		#ifndef CURL_SWAP
36	0	#define CURL_SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))
37		#endif
38
39	0	#define CURL_U32_SLOT_CNT(bits) ((bits) ? (1U << (bits)) : 0)
40	0	#define CURL_U32_PTRSET_SLOT_CNT(s) CURL_U32_SLOT_CNT((s)->slotbits)
41	0	#define CURL_U32_PTRSET_SLOT_IDX(s, i) (uint32_t)((i) & (s)->slotmask)
42
43		/* A hashset for tuples (id, ptr) using Robin Hood Hashing.
44		* <https://www.cs.cornell.edu/courses/JavaAndDS/files/hashing_RobinHood.pdf>
45		* The basic idea here to handle collisions by robbing "rich" entries and
46		* giving to the "poor":
47		* - We have an array: (id, ptr) are ideally placed at index "id % size".
48		* - If slot at index is already occupied, we have a collision.
49		* - A simple collision strategy would look at the next index, and the
50		* next until finding an empty slot.
51		* - The drawback is that this may lead to many checks on lookups, as it
52		* will need to also look at subsequent slots until it finds the match.
53		* The amount of lookups is the "probe sequence length" (psl) and this
54		* may vary greatly between entries.
55		* - Robin Hood Hashing balances the 'psl's of all entries more evenly:
56		* - psl == 0 means an entry is in exactly the right slot
57		* - psl == 1 means it is in the slot right after. psl == 2 is the slot
58		* after that, etc.
59		* - when inserting a new entry, track its psl. Finding a slot where
60		* the existing entry has a lower psl makes a swap. Put the new entry
61		* and its psl there, take the previous entry and its psl and find
62		* the next best slot for the previous entry. */
63		void Curl_u32_ptrset_init(struct u32_ptrset *set,
64		Curl_u32_ptrset_dtor *dtor)
65	0	{
66	0	memset(set, 0, sizeof(*set));
67	0	set->dtor = dtor;
68	0	#ifdef DEBUGBUILD
69	0	set->init = CURL_U32_PTRSET_MAGIC;
70	0	#endif
71	0	}
72
73		void Curl_u32_ptrset_clear(struct u32_ptrset *set)
74	0	{
75	0	uint32_t i;
76	0	DEBUGASSERT(set->init == CURL_U32_PTRSET_MAGIC);
77	0	if(set->dtor)
78	0	for(i = 0; i < CURL_U32_PTRSET_SLOT_CNT(set); ++i)
79	0	if(set->data[i])
80	0	set->dtor(set->ids[i], set->data[i]);
81
82	0	curlx_safefree(set->data);
83	0	Curl_u32_ptrset_init(set, set->dtor);
84	0	}
85
86		static void u32_ptrset_add(struct u32_ptrset set, uint32_t id, void ptr)
87	0	{
88	0	uint32_t i = CURL_U32_PTRSET_SLOT_IDX(set, id);
89	0	uint32_t psl = 0;
90	0	while(set->data[i]) {
91	0	if(psl > set->psl[i]) { /* SWAP */
92	0	void *tmpdata;
93		#if CURL_U32_PTRSET_DEBUG
94		curl_mfprintf(stderr, "u32_ptrset_add %u=%p to idx=%u\n", id, ptr, i);
95		#endif
96	0	tmpdata = set->data[i];
97	0	set->data[i] = ptr;
98	0	ptr = tmpdata;
99	0	CURL_SWAP(set->psl[i], psl);
100	0	CURL_SWAP(set->ids[i], id);
101	0	}
102	0	i = CURL_U32_PTRSET_SLOT_IDX(set, i + 1);
103	0	++psl;
104	0	}
105	0	set->ids[i] = id;
106	0	set->data[i] = ptr;
107	0	set->psl[i] = psl;
108	0	++set->count;
109		#if CURL_U32_PTRSET_DEBUG
110		curl_mfprintf(stderr, "u32_ptrset_add %u=%p to idx=%u\n", id, ptr, i);
111		#endif
112	0	}
113
114		static bool u32_ptrset_grow(struct u32_ptrset *set)
115	0	{
116	0	uint32_t i, *prev_ids;
117	0	uint8_t nslotbits, pslotbits;
118	0	void **prev_data;
119	0	size_t nslots;
120	0	const size_t slot_size = (sizeof(void ) + (2 sizeof(uint32_t)));
121	0	void *d;
122
123	0	if(set->slotbits >= 31)
124	0	return FALSE;
125	0	nslotbits = set->slotbits ? (uint8_t)(set->slotbits + 1) : 5;
126	0	nslots = CURL_U32_SLOT_CNT(nslotbits);
127	0	if(nslots > (SIZE_MAX / slot_size)) /* 32-bit arch may trigger here */
128	0	return FALSE;
129		#if CURL_U32_PTRSET_DEBUG
130		curl_mfprintf(stderr, "u32_ptrset_grow from bits=%d to %d, slots=%zu\n",
131		set->slotbits, nslotbits, nslots);
132		#endif
133	0	d = curlx_calloc(1, nslots * slot_size);
134	0	if(!d)
135	0	return FALSE;
136
137	0	prev_data = set->data;
138	0	prev_ids = set->ids;
139	0	pslotbits = set->slotbits;
140		#if defined(__GNUC__) && __GNUC__ >= 13
141		#pragma GCC diagnostic push
142		#pragma GCC diagnostic ignored "-Wanalyzer-allocation-size"
143		#endif
144	0	set->data = d;
145	0	set->ids = (uint32_t *)(set->data + nslots);
146	0	set->psl = (uint32_t *)(set->ids + nslots);
147		#if defined(__GNUC__) && __GNUC__ >= 13
148		#pragma GCC diagnostic pop
149		#endif
150
151	0	set->slotbits = nslotbits;
152	0	set->slotmask = (uint32_t)((1U << set->slotbits) - 1);
153	0	set->count = 0;
154		/* re-add previous entries */
155	0	for(i = 0; i < CURL_U32_SLOT_CNT(pslotbits); ++i) {
156	0	if(prev_data[i])
157	0	u32_ptrset_add(set, prev_ids[i], prev_data[i]);
158	0	}
159	0	if(prev_data)
160	0	curlx_free(prev_data);
161	0	return TRUE;
162	0	}
163
164		static bool u32_ptrset_get_index(struct u32_ptrset *set,
165		uint32_t id, uint32_t *pindex)
166	0	{
167	0	uint32_t i = CURL_U32_PTRSET_SLOT_IDX(set, id);
168	0	uint32_t psl = 0;
169	0	if(!set->data)
170	0	return FALSE;
171	0	while(set->data[i] && (psl <= set->psl[i])) {
172	0	if(set->ids[i] == id) {
173	0	*pindex = i;
174		#if CURL_U32_PTRSET_DEBUG
175		curl_mfprintf(stderr, "u32_ptrset_index %u=%p at idx=%u\n",
176		id, set->data[i], i);
177		#endif
178	0	return TRUE;
179	0	}
180	0	i = CURL_U32_PTRSET_SLOT_IDX(set, i + 1);
181	0	++psl;
182	0	}
183		#if CURL_U32_PTRSET_DEBUG
184		curl_mfprintf(stderr, "u32_ptrset_index %u not found\n", id);
185		#endif
186	0	*pindex = 0;
187	0	return FALSE;
188	0	}
189
190		uint32_t Curl_u32_ptrset_count(struct u32_ptrset *set)
191	0	{
192	0	return set->count;
193	0	}
194
195		void Curl_u32_ptrset_get(struct u32_ptrset set, uint32_t id)
196	0	{
197	0	uint32_t i;
198	0	DEBUGASSERT(set->init == CURL_U32_PTRSET_MAGIC);
199	0	if(u32_ptrset_get_index(set, id, &i))
200	0	return set->data[i];
201	0	return NULL;
202	0	}
203
204		CURLcode Curl_u32_ptrset_set(struct u32_ptrset *set,
205		uint32_t id, void *ptr)
206	0	{
207	0	uint32_t i;
208
209	0	DEBUGASSERT(set->init == CURL_U32_PTRSET_MAGIC);
210	0	if(!ptr) {
211	0	Curl_u32_ptrset_unset(set, id);
212	0	return CURLE_OK;
213	0	}
214
215	0	if(u32_ptrset_get_index(set, id, &i)) {
216		/* `id` is in set, replace value */
217	0	if(set->dtor && (set->data[i] != ptr))
218	0	set->dtor(set->ids[i], set->data[i]);
219		#if CURL_U32_PTRSET_DEBUG
220		curl_mfprintf(stderr, "u32_ptrset_set replace %u=%p at idx=%u\n",
221		id, ptr, i);
222		#endif
223	0	set->data[i] = ptr;
224	0	return CURLE_OK;
225	0	}
226		/* `id` not in set yet, grow if full */
227	0	if((set->count >= CURL_U32_PTRSET_SLOT_CNT(set)) &&
228	0	!u32_ptrset_grow(set)) {
229	0	return CURLE_OUT_OF_MEMORY;
230	0	}
231
232	0	u32_ptrset_add(set, id, ptr);
233	0	return CURLE_OK;
234	0	}
235
236		static void u32_ptrset_unset(struct u32_ptrset *set, uint32_t id)
237	0	{
238	0	uint32_t i, j;
239
240	0	DEBUGASSERT(set->init == CURL_U32_PTRSET_MAGIC);
241	0	if(u32_ptrset_get_index(set, id, &i)) {
242		/* `id` is in set */
243		#if CURL_U32_PTRSET_DEBUG
244		curl_mfprintf(stderr, "u32_ptrset_unset %u at idx=%u\n", id, i);
245		#endif
246	0	if(set->dtor)
247	0	set->dtor(set->ids[i], set->data[i]);
248	0	set->data[i] = NULL;
249	0	set->ids[i] = set->psl[i] = 0;
250	0	--set->count;
251	0	j = CURL_U32_PTRSET_SLOT_IDX(set, i + 1);
252		/* shift all entries with positive psl "down" */
253	0	while(set->data[j] && set->psl[j]) {
254	0	set->data[i] = set->data[j];
255	0	set->ids[i] = set->ids[j];
256	0	set->psl[i] = set->psl[j] - 1;
257	0	set->data[j] = NULL;
258	0	set->ids[j] = set->psl[j] = 0;
259	0	i = j;
260	0	j = CURL_U32_PTRSET_SLOT_IDX(set, i + 1);
261	0	}
262	0	}
263	0	}
264
265		void Curl_u32_ptrset_unset(struct u32_ptrset *set, uint32_t id)
266	0	{
267	0	u32_ptrset_unset(set, id);
268	0	}
269
270		void Curl_u32_ptrset_visit(struct u32_ptrset *set,
271		Curl_u32_ptrset_visit_cb *cb,
272		void *user_data)
273	0	{
274	0	uint32_t i;
275	0	for(i = 0; i < CURL_U32_PTRSET_SLOT_CNT(set); ++i) {
276	0	if(set->data[i] && !cb(set->ids[i], set->data[i], user_data))
277	0	break;
278	0	}
279	0	}