/src/curl/lib/uint-spbset.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 "uint-bset.h"
#include "uint-spbset.h"

#ifdef DEBUGBUILD
#define CURL_UINT32_SPBSET_MAGIC  0x70737362
#endif

void Curl_uint32_spbset_init(struct uint32_spbset *bset)
{
  memset(bset, 0, sizeof(*bset));
#ifdef DEBUGBUILD
  bset->init = CURL_UINT32_SPBSET_MAGIC;
#endif
}

/* Clear the bitset, making it empty.

   @unittest 3213
 */
UNITTEST void uint32_spbset_clear(struct uint32_spbset *bset);
UNITTEST void uint32_spbset_clear(struct uint32_spbset *bset)
{
  struct uint32_spbset_chunk *next, *chunk;

  for(chunk = bset->head.next; chunk; chunk = next) {
    next = chunk->next;
    curlx_free(chunk);
  }
  memset(&bset->head, 0, sizeof(bset->head));
}

void Curl_uint32_spbset_destroy(struct uint32_spbset *bset)
{
  DEBUGASSERT(bset->init == CURL_UINT32_SPBSET_MAGIC);
  uint32_spbset_clear(bset);
}

uint32_t Curl_uint32_spbset_count(struct uint32_spbset *bset)
{
  struct uint32_spbset_chunk *chunk;
  uint32_t i, n = 0;

  for(chunk = &bset->head; chunk; chunk = chunk->next) {
    for(i = 0; i < CURL_UINT32_SPBSET_CH_SLOTS; ++i) {
      if(chunk->slots[i])
        n += CURL_POPCOUNT64(chunk->slots[i]);
    }
  }
  return n;
}

static bool uint32_spbset_empty_chunk(struct uint32_spbset_chunk *chunk)
{
  uint32_t i;
  for(i = 0; i < CURL_UINT32_SPBSET_CH_SLOTS; ++i) {
    if(chunk->slots[i])
      return FALSE;
  }
  return TRUE;
}

static struct uint32_spbset_chunk *uint32_spbset_unlink_empty(
  struct uint32_spbset *bset, uint32_t for_offset)
{
  struct uint32_spbset_chunk *chunk, **panchor = NULL;
  for(chunk = &bset->head; chunk;
      panchor = &chunk->next, chunk = chunk->next) {
    if(uint32_spbset_empty_chunk(chunk))
      break;
  }
  if(chunk) {
    if(chunk == &bset->head) { /* head chunk is empty */
      if(!bset->head.next || (for_offset < bset->head.next->offset)) {
        return &bset->head;
      }
      /* swap head and next, unlink */
      chunk = bset->head.next;
      memcpy(&bset->head, chunk, sizeof(bset->head));
      memset(chunk, 0, sizeof(*chunk));
    }
    else {
      *panchor = chunk->next; /* unlink */
      memset(chunk, 0, sizeof(*chunk));
    }
  }
  return chunk;
}

static struct uint32_spbset_chunk *uint32_spbset_insert_chunk(
  struct uint32_spbset *bset, struct uint32_spbset_chunk *nchunk)
{
  struct uint32_spbset_chunk *chunk, **panchor;

  /* insert nchunk into set's ordered chunk list */
  if(nchunk->offset < bset->head.offset) {
    /* swap chunk and head */
    uint32_t offset = nchunk->offset;
    memcpy(nchunk, &bset->head, sizeof(*nchunk));
    memset(&bset->head, 0, sizeof(bset->head));
    bset->head.next = nchunk;
    bset->head.offset = offset;
    return &bset->head;
  }
  DEBUGASSERT(nchunk->offset > bset->head.offset);
  panchor = &bset->head.next;
  for(chunk = *panchor; chunk;
      panchor = &chunk->next, chunk = chunk->next) {
    if(chunk->offset > nchunk->offset) { /* insert before this chunk */
      nchunk->next = chunk;
      *panchor = nchunk;
      return nchunk;
    }
  }
  /* no chunk with larger offset, append */
  *panchor = nchunk;
  return nchunk;
}

static struct uint32_spbset_chunk *uint32_spbset_get_chunk(
  struct uint32_spbset *bset, uint32_t i, bool grow)
{
  struct uint32_spbset_chunk *chunk;
  uint32_t i_offset = (i & ~CURL_UINT32_SPBSET_CH_MASK);

  if(!bset)
    return NULL;

  for(chunk = &bset->head; chunk; chunk = chunk->next) {
    if(chunk->offset == i_offset)
      return chunk;
    else if(chunk->offset > i_offset)
      break; /* need new chunk here */
  }
  if(!grow) /* just a check if the chunk exists */
    return NULL;

  /* Is there an empty chunk to reuse? */
  chunk = uint32_spbset_unlink_empty(bset, i_offset);
  if(chunk) {
    chunk->offset = i_offset;
    if(chunk == &bset->head) /* head chunk is empty, stayed linked */
      return &bset->head;
    /* was really unlinked, need to insert below */
  }
  else {
    /* need a new one */
    chunk = curlx_calloc(1, sizeof(*chunk));
    if(!chunk)
      return NULL;
    chunk->offset = i_offset;
  }

  return uint32_spbset_insert_chunk(bset, chunk);
}

bool Curl_uint32_spbset_add(struct uint32_spbset *bset, uint32_t i)
{
  struct uint32_spbset_chunk *chunk = uint32_spbset_get_chunk(bset, i, TRUE);
  if(!chunk)
    return FALSE;

  DEBUGASSERT(i >= chunk->offset);
  i -= chunk->offset;
  DEBUGASSERT(i < (CURL_UINT32_SPBSET_CH_SLOTS * 64));
  chunk->slots[(i / 64)] |= ((uint64_t)1 << (i % 64));
  return TRUE;
}

void Curl_uint32_spbset_remove(struct uint32_spbset *bset, uint32_t i)
{
  struct uint32_spbset_chunk *chunk = uint32_spbset_get_chunk(bset, i, FALSE);
  if(chunk) {
    DEBUGASSERT(i >= chunk->offset);
    i -= chunk->offset;
    DEBUGASSERT(i < (CURL_UINT32_SPBSET_CH_SLOTS * 64));
    chunk->slots[(i / 64)] &= ~((uint64_t)1 << (i % 64));
  }
}

bool Curl_uint32_spbset_contains(struct uint32_spbset *bset, uint32_t i)
{
  struct uint32_spbset_chunk *chunk = uint32_spbset_get_chunk(bset, i, FALSE);
  if(chunk) {
    DEBUGASSERT(i >= chunk->offset);
    i -= chunk->offset;
    DEBUGASSERT(i < (CURL_UINT32_SPBSET_CH_SLOTS * 64));
    return (chunk->slots[i / 64] & ((uint64_t)1 << (i % 64))) != 0;
  }
  return FALSE;
}

bool Curl_uint32_spbset_first(struct uint32_spbset *bset, uint32_t *pfirst)
{
  struct uint32_spbset_chunk *chunk;
  uint32_t i;

  for(chunk = &bset->head; chunk; chunk = chunk->next) {
    for(i = 0; i < CURL_UINT32_SPBSET_CH_SLOTS; ++i) {
      if(chunk->slots[i]) {
        *pfirst = chunk->offset + ((i * 64) + CURL_CTZ64(chunk->slots[i]));
        return TRUE;
      }
    }
  }
  *pfirst = 0; /* give it a defined value even if it should not be used */
  return FALSE;
}

static bool uint32_spbset_chunk_first(struct uint32_spbset_chunk *chunk,
                                      uint32_t *pfirst)
{
  uint32_t i;
  for(i = 0; i < CURL_UINT32_SPBSET_CH_SLOTS; ++i) {
    if(chunk->slots[i]) {
      *pfirst = chunk->offset + ((i * 64) + CURL_CTZ64(chunk->slots[i]));
      return TRUE;
    }
  }
  *pfirst = UINT32_MAX; /* a value we cannot store */
  return FALSE;
}

static bool uint32_spbset_chunk_next(struct uint32_spbset_chunk *chunk,
                                     uint32_t last,
                                     uint32_t *pnext)
{
  if(chunk->offset <= last) {
    uint64_t x;
    uint32_t i = ((last - chunk->offset) / 64);
    if(i < CURL_UINT32_SPBSET_CH_SLOTS) {
      x = (chunk->slots[i] >> (last % 64));
      if(x) {
        /* more bits set, next is `last` + trailing 0s of the shifted slot */
        *pnext = last + CURL_CTZ64(x);
        return TRUE;
      }
      /* no more bits set in the last slot, scan forward */
      for(i = i + 1; i < CURL_UINT32_SPBSET_CH_SLOTS; ++i) {
        if(chunk->slots[i]) {
          *pnext = chunk->offset + ((i * 64) + CURL_CTZ64(chunk->slots[i]));
          return TRUE;
        }
      }
    }
  }
  *pnext = UINT32_MAX;
  return FALSE;
}

bool Curl_uint32_spbset_next(struct uint32_spbset *bset, uint32_t last,
                             uint32_t *pnext)
{
  struct uint32_spbset_chunk *chunk;
  uint32_t last_offset;

  ++last; /* look for the next higher number */
  last_offset = (last & ~CURL_UINT32_SPBSET_CH_MASK);

  for(chunk = &bset->head; chunk; chunk = chunk->next) {
    if(chunk->offset >= last_offset) {
      break;
    }
  }

  if(chunk && (chunk->offset == last_offset)) {
    /* is there a number higher than last in this chunk? */
    if(uint32_spbset_chunk_next(chunk, last, pnext))
      return TRUE;
    /* not in this chunk */
    chunk = chunk->next;
  }
  /* look for the first in the "higher" chunks, if there are any. */
  while(chunk) {
    if(uint32_spbset_chunk_first(chunk, pnext))
      return TRUE;
    chunk = chunk->next;
  }
  *pnext = UINT32_MAX;
  return FALSE;
}

Coverage Report

Created: 2026-07-30 07:26

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 "uint-bset.h"
27		#include "uint-spbset.h"
28
29		#ifdef DEBUGBUILD
30	0	#define CURL_UINT32_SPBSET_MAGIC 0x70737362
31		#endif
32
33		void Curl_uint32_spbset_init(struct uint32_spbset *bset)
34	0	{
35	0	memset(bset, 0, sizeof(*bset));
36	0	#ifdef DEBUGBUILD
37	0	bset->init = CURL_UINT32_SPBSET_MAGIC;
38	0	#endif
39	0	}
40
41		/* Clear the bitset, making it empty.
42
43		@unittest 3213
44		*/
45		UNITTEST void uint32_spbset_clear(struct uint32_spbset *bset);
46		UNITTEST void uint32_spbset_clear(struct uint32_spbset *bset)
47	0	{
48	0	struct uint32_spbset_chunk next, chunk;
49
50	0	for(chunk = bset->head.next; chunk; chunk = next) {
51	0	next = chunk->next;
52	0	curlx_free(chunk);
53	0	}
54	0	memset(&bset->head, 0, sizeof(bset->head));
55	0	}
56
57		void Curl_uint32_spbset_destroy(struct uint32_spbset *bset)
58	0	{
59	0	DEBUGASSERT(bset->init == CURL_UINT32_SPBSET_MAGIC);
60	0	uint32_spbset_clear(bset);
61	0	}
62
63		uint32_t Curl_uint32_spbset_count(struct uint32_spbset *bset)
64	0	{
65	0	struct uint32_spbset_chunk *chunk;
66	0	uint32_t i, n = 0;
67
68	0	for(chunk = &bset->head; chunk; chunk = chunk->next) {
69	0	for(i = 0; i < CURL_UINT32_SPBSET_CH_SLOTS; ++i) {
70	0	if(chunk->slots[i])
71	0	n += CURL_POPCOUNT64(chunk->slots[i]);
72	0	}
73	0	}
74	0	return n;
75	0	}
76
77		static bool uint32_spbset_empty_chunk(struct uint32_spbset_chunk *chunk)
78	0	{
79	0	uint32_t i;
80	0	for(i = 0; i < CURL_UINT32_SPBSET_CH_SLOTS; ++i) {
81	0	if(chunk->slots[i])
82	0	return FALSE;
83	0	}
84	0	return TRUE;
85	0	}
86
87		static struct uint32_spbset_chunk *uint32_spbset_unlink_empty(
88		struct uint32_spbset *bset, uint32_t for_offset)
89	0	{
90	0	struct uint32_spbset_chunk chunk, *panchor = NULL;
91	0	for(chunk = &bset->head; chunk;
92	0	panchor = &chunk->next, chunk = chunk->next) {
93	0	if(uint32_spbset_empty_chunk(chunk))
94	0	break;
95	0	}
96	0	if(chunk) {
97	0	if(chunk == &bset->head) { /* head chunk is empty */
98	0	if(!bset->head.next \|\| (for_offset < bset->head.next->offset)) {
99	0	return &bset->head;
100	0	}
101		/* swap head and next, unlink */
102	0	chunk = bset->head.next;
103	0	memcpy(&bset->head, chunk, sizeof(bset->head));
104	0	memset(chunk, 0, sizeof(*chunk));
105	0	}
106	0	else {
107	0	panchor = chunk->next; / unlink */
108	0	memset(chunk, 0, sizeof(*chunk));
109	0	}
110	0	}
111	0	return chunk;
112	0	}
113
114		static struct uint32_spbset_chunk *uint32_spbset_insert_chunk(
115		struct uint32_spbset bset, struct uint32_spbset_chunk nchunk)
116	0	{
117	0	struct uint32_spbset_chunk chunk, *panchor;
118
119		/* insert nchunk into set's ordered chunk list */
120	0	if(nchunk->offset < bset->head.offset) {
121		/* swap chunk and head */
122	0	uint32_t offset = nchunk->offset;
123	0	memcpy(nchunk, &bset->head, sizeof(*nchunk));
124	0	memset(&bset->head, 0, sizeof(bset->head));
125	0	bset->head.next = nchunk;
126	0	bset->head.offset = offset;
127	0	return &bset->head;
128	0	}
129	0	DEBUGASSERT(nchunk->offset > bset->head.offset);
130	0	panchor = &bset->head.next;
131	0	for(chunk = *panchor; chunk;
132	0	panchor = &chunk->next, chunk = chunk->next) {
133	0	if(chunk->offset > nchunk->offset) { /* insert before this chunk */
134	0	nchunk->next = chunk;
135	0	*panchor = nchunk;
136	0	return nchunk;
137	0	}
138	0	}
139		/* no chunk with larger offset, append */
140	0	*panchor = nchunk;
141	0	return nchunk;
142	0	}
143
144		static struct uint32_spbset_chunk *uint32_spbset_get_chunk(
145		struct uint32_spbset *bset, uint32_t i, bool grow)
146	0	{
147	0	struct uint32_spbset_chunk *chunk;
148	0	uint32_t i_offset = (i & ~CURL_UINT32_SPBSET_CH_MASK);
149
150	0	if(!bset)
151	0	return NULL;
152
153	0	for(chunk = &bset->head; chunk; chunk = chunk->next) {
154	0	if(chunk->offset == i_offset)
155	0	return chunk;
156	0	else if(chunk->offset > i_offset)
157	0	break; /* need new chunk here */
158	0	}
159	0	if(!grow) /* just a check if the chunk exists */
160	0	return NULL;
161
162		/* Is there an empty chunk to reuse? */
163	0	chunk = uint32_spbset_unlink_empty(bset, i_offset);
164	0	if(chunk) {
165	0	chunk->offset = i_offset;
166	0	if(chunk == &bset->head) /* head chunk is empty, stayed linked */
167	0	return &bset->head;
168		/* was really unlinked, need to insert below */
169	0	}
170	0	else {
171		/* need a new one */
172	0	chunk = curlx_calloc(1, sizeof(*chunk));
173	0	if(!chunk)
174	0	return NULL;
175	0	chunk->offset = i_offset;
176	0	}
177
178	0	return uint32_spbset_insert_chunk(bset, chunk);
179	0	}
180
181		bool Curl_uint32_spbset_add(struct uint32_spbset *bset, uint32_t i)
182	0	{
183	0	struct uint32_spbset_chunk *chunk = uint32_spbset_get_chunk(bset, i, TRUE);
184	0	if(!chunk)
185	0	return FALSE;
186
187	0	DEBUGASSERT(i >= chunk->offset);
188	0	i -= chunk->offset;
189	0	DEBUGASSERT(i < (CURL_UINT32_SPBSET_CH_SLOTS * 64));
190	0	chunk->slots[(i / 64)] \|= ((uint64_t)1 << (i % 64));
191	0	return TRUE;
192	0	}
193
194		void Curl_uint32_spbset_remove(struct uint32_spbset *bset, uint32_t i)
195	0	{
196	0	struct uint32_spbset_chunk *chunk = uint32_spbset_get_chunk(bset, i, FALSE);
197	0	if(chunk) {
198	0	DEBUGASSERT(i >= chunk->offset);
199	0	i -= chunk->offset;
200	0	DEBUGASSERT(i < (CURL_UINT32_SPBSET_CH_SLOTS * 64));
201	0	chunk->slots[(i / 64)] &= ~((uint64_t)1 << (i % 64));
202	0	}
203	0	}
204
205		bool Curl_uint32_spbset_contains(struct uint32_spbset *bset, uint32_t i)
206	0	{
207	0	struct uint32_spbset_chunk *chunk = uint32_spbset_get_chunk(bset, i, FALSE);
208	0	if(chunk) {
209	0	DEBUGASSERT(i >= chunk->offset);
210	0	i -= chunk->offset;
211	0	DEBUGASSERT(i < (CURL_UINT32_SPBSET_CH_SLOTS * 64));
212	0	return (chunk->slots[i / 64] & ((uint64_t)1 << (i % 64))) != 0;
213	0	}
214	0	return FALSE;
215	0	}
216
217		bool Curl_uint32_spbset_first(struct uint32_spbset bset, uint32_t pfirst)
218	0	{
219	0	struct uint32_spbset_chunk *chunk;
220	0	uint32_t i;
221
222	0	for(chunk = &bset->head; chunk; chunk = chunk->next) {
223	0	for(i = 0; i < CURL_UINT32_SPBSET_CH_SLOTS; ++i) {
224	0	if(chunk->slots[i]) {
225	0	pfirst = chunk->offset + ((i 64) + CURL_CTZ64(chunk->slots[i]));
226	0	return TRUE;
227	0	}
228	0	}
229	0	}
230	0	pfirst = 0; / give it a defined value even if it should not be used */
231	0	return FALSE;
232	0	}
233
234		static bool uint32_spbset_chunk_first(struct uint32_spbset_chunk *chunk,
235		uint32_t *pfirst)
236	0	{
237	0	uint32_t i;
238	0	for(i = 0; i < CURL_UINT32_SPBSET_CH_SLOTS; ++i) {
239	0	if(chunk->slots[i]) {
240	0	pfirst = chunk->offset + ((i 64) + CURL_CTZ64(chunk->slots[i]));
241	0	return TRUE;
242	0	}
243	0	}
244	0	pfirst = UINT32_MAX; / a value we cannot store */
245	0	return FALSE;
246	0	}
247
248		static bool uint32_spbset_chunk_next(struct uint32_spbset_chunk *chunk,
249		uint32_t last,
250		uint32_t *pnext)
251	0	{
252	0	if(chunk->offset <= last) {
253	0	uint64_t x;
254	0	uint32_t i = ((last - chunk->offset) / 64);
255	0	if(i < CURL_UINT32_SPBSET_CH_SLOTS) {
256	0	x = (chunk->slots[i] >> (last % 64));
257	0	if(x) {
258		/* more bits set, next is `last` + trailing 0s of the shifted slot */
259	0	*pnext = last + CURL_CTZ64(x);
260	0	return TRUE;
261	0	}
262		/* no more bits set in the last slot, scan forward */
263	0	for(i = i + 1; i < CURL_UINT32_SPBSET_CH_SLOTS; ++i) {
264	0	if(chunk->slots[i]) {
265	0	pnext = chunk->offset + ((i 64) + CURL_CTZ64(chunk->slots[i]));
266	0	return TRUE;
267	0	}
268	0	}
269	0	}
270	0	}
271	0	*pnext = UINT32_MAX;
272	0	return FALSE;
273	0	}
274
275		bool Curl_uint32_spbset_next(struct uint32_spbset *bset, uint32_t last,
276		uint32_t *pnext)
277	0	{
278	0	struct uint32_spbset_chunk *chunk;
279	0	uint32_t last_offset;
280
281	0	++last; /* look for the next higher number */
282	0	last_offset = (last & ~CURL_UINT32_SPBSET_CH_MASK);
283
284	0	for(chunk = &bset->head; chunk; chunk = chunk->next) {
285	0	if(chunk->offset >= last_offset) {
286	0	break;
287	0	}
288	0	}
289
290	0	if(chunk && (chunk->offset == last_offset)) {
291		/* is there a number higher than last in this chunk? */
292	0	if(uint32_spbset_chunk_next(chunk, last, pnext))
293	0	return TRUE;
294		/* not in this chunk */
295	0	chunk = chunk->next;
296	0	}
297		/* look for the first in the "higher" chunks, if there are any. */
298	0	while(chunk) {
299	0	if(uint32_spbset_chunk_first(chunk, pnext))
300	0	return TRUE;
301	0	chunk = chunk->next;
302	0	}
303	0	*pnext = UINT32_MAX;
304		return FALSE;
305	0	}