/src/CMake/Utilities/cmcurl/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 struct uint32_spbset_chunk *uint32_spbset_get_chunk(
  struct uint32_spbset *bset, uint32_t i, bool grow)
{
  struct uint32_spbset_chunk *chunk, **panchor = NULL;
  uint32_t i_offset = (i & ~CURL_UINT32_SPBSET_CH_MASK);

  if(!bset)
    return NULL;

  for(chunk = &bset->head; chunk;
      panchor = &chunk->next, chunk = chunk->next) {
    if(chunk->offset == i_offset) {
      return chunk;
    }
    else if(chunk->offset > i_offset) {
      /* need new chunk here */
      chunk = NULL;
      break;
    }
  }

  if(!grow)
    return NULL;

  /* need a new one */
  chunk = curlx_calloc(1, sizeof(*chunk));
  if(!chunk)
    return NULL;

  if(panchor) {  /* insert between panchor and *panchor */
    chunk->next = *panchor;
    *panchor = chunk;
  }
  else {  /* prepend to head, switching places */
    memcpy(chunk, &bset->head, sizeof(*chunk));
    memset(&bset->head, 0, sizeof(bset->head));
    bset->head.next = chunk;
  }
  chunk->offset = i_offset;
  return chunk;
}

bool Curl_uint32_spbset_add(struct uint32_spbset *bset, uint32_t i)
{
  struct uint32_spbset_chunk *chunk;
  uint32_t i_chunk;

  chunk = uint32_spbset_get_chunk(bset, i, TRUE);
  if(!chunk)
    return FALSE;

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

void Curl_uint32_spbset_remove(struct uint32_spbset *bset, uint32_t i)
{
  struct uint32_spbset_chunk *chunk;
  uint32_t i_chunk;

  chunk = uint32_spbset_get_chunk(bset, i, FALSE);
  if(chunk) {
    DEBUGASSERT(i >= chunk->offset);
    i_chunk = (i - chunk->offset);
    DEBUGASSERT((i_chunk / 64) < CURL_UINT32_SPBSET_CH_SLOTS);
    chunk->slots[(i_chunk / 64)] &= ~((uint64_t)1 << (i_chunk % 64));
  }
}

bool Curl_uint32_spbset_contains(struct uint32_spbset *bset, uint32_t i)
{
  struct uint32_spbset_chunk *chunk;
  uint32_t i_chunk;

  chunk = uint32_spbset_get_chunk(bset, i, FALSE);
  if(chunk) {
    DEBUGASSERT(i >= chunk->offset);
    i_chunk = (i - chunk->offset);
    DEBUGASSERT((i_chunk / 64) < CURL_UINT32_SPBSET_CH_SLOTS);
    return (chunk->slots[i_chunk / 64] &
            ((uint64_t)1 << (i_chunk % 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` + trailing0s 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-06-15 07:03

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		#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		#ifdef DEBUGBUILD
37		bset->init = CURL_UINT32_SPBSET_MAGIC;
38		#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 struct uint32_spbset_chunk *uint32_spbset_get_chunk(
78		struct uint32_spbset *bset, uint32_t i, bool grow)
79	0	{
80	0	struct uint32_spbset_chunk chunk, *panchor = NULL;
81	0	uint32_t i_offset = (i & ~CURL_UINT32_SPBSET_CH_MASK);
82
83	0	if(!bset)
84	0	return NULL;
85
86	0	for(chunk = &bset->head; chunk;
87	0	panchor = &chunk->next, chunk = chunk->next) {
88	0	if(chunk->offset == i_offset) {
89	0	return chunk;
90	0	}
91	0	else if(chunk->offset > i_offset) {
92		/* need new chunk here */
93	0	chunk = NULL;
94	0	break;
95	0	}
96	0	}
97
98	0	if(!grow)
99	0	return NULL;
100
101		/* need a new one */
102	0	chunk = curlx_calloc(1, sizeof(*chunk));
103	0	if(!chunk)
104	0	return NULL;
105
106	0	if(panchor) { /* insert between panchor and panchor /
107	0	chunk->next = *panchor;
108	0	*panchor = chunk;
109	0	}
110	0	else { /* prepend to head, switching places */
111	0	memcpy(chunk, &bset->head, sizeof(*chunk));
112	0	memset(&bset->head, 0, sizeof(bset->head));
113	0	bset->head.next = chunk;
114	0	}
115	0	chunk->offset = i_offset;
116	0	return chunk;
117	0	}
118
119		bool Curl_uint32_spbset_add(struct uint32_spbset *bset, uint32_t i)
120	0	{
121	0	struct uint32_spbset_chunk *chunk;
122	0	uint32_t i_chunk;
123
124	0	chunk = uint32_spbset_get_chunk(bset, i, TRUE);
125	0	if(!chunk)
126	0	return FALSE;
127
128	0	DEBUGASSERT(i >= chunk->offset);
129	0	i_chunk = (i - chunk->offset);
130	0	DEBUGASSERT((i_chunk / 64) < CURL_UINT32_SPBSET_CH_SLOTS);
131	0	chunk->slots[(i_chunk / 64)] \|= ((uint64_t)1 << (i_chunk % 64));
132	0	return TRUE;
133	0	}
134
135		void Curl_uint32_spbset_remove(struct uint32_spbset *bset, uint32_t i)
136	0	{
137	0	struct uint32_spbset_chunk *chunk;
138	0	uint32_t i_chunk;
139
140	0	chunk = uint32_spbset_get_chunk(bset, i, FALSE);
141	0	if(chunk) {
142	0	DEBUGASSERT(i >= chunk->offset);
143	0	i_chunk = (i - chunk->offset);
144	0	DEBUGASSERT((i_chunk / 64) < CURL_UINT32_SPBSET_CH_SLOTS);
145	0	chunk->slots[(i_chunk / 64)] &= ~((uint64_t)1 << (i_chunk % 64));
146	0	}
147	0	}
148
149		bool Curl_uint32_spbset_contains(struct uint32_spbset *bset, uint32_t i)
150	0	{
151	0	struct uint32_spbset_chunk *chunk;
152	0	uint32_t i_chunk;
153
154	0	chunk = uint32_spbset_get_chunk(bset, i, FALSE);
155	0	if(chunk) {
156	0	DEBUGASSERT(i >= chunk->offset);
157	0	i_chunk = (i - chunk->offset);
158	0	DEBUGASSERT((i_chunk / 64) < CURL_UINT32_SPBSET_CH_SLOTS);
159	0	return (chunk->slots[i_chunk / 64] &
160	0	((uint64_t)1 << (i_chunk % 64))) != 0;
161	0	}
162	0	return FALSE;
163	0	}
164
165		bool Curl_uint32_spbset_first(struct uint32_spbset bset, uint32_t pfirst)
166	0	{
167	0	struct uint32_spbset_chunk *chunk;
168	0	uint32_t i;
169
170	0	for(chunk = &bset->head; chunk; chunk = chunk->next) {
171	0	for(i = 0; i < CURL_UINT32_SPBSET_CH_SLOTS; ++i) {
172	0	if(chunk->slots[i]) {
173	0	pfirst = chunk->offset + ((i 64) + CURL_CTZ64(chunk->slots[i]));
174	0	return TRUE;
175	0	}
176	0	}
177	0	}
178	0	pfirst = 0; / give it a defined value even if it should not be used */
179	0	return FALSE;
180	0	}
181
182		static bool uint32_spbset_chunk_first(struct uint32_spbset_chunk *chunk,
183		uint32_t *pfirst)
184	0	{
185	0	uint32_t i;
186	0	for(i = 0; i < CURL_UINT32_SPBSET_CH_SLOTS; ++i) {
187	0	if(chunk->slots[i]) {
188	0	pfirst = chunk->offset + ((i 64) + CURL_CTZ64(chunk->slots[i]));
189	0	return TRUE;
190	0	}
191	0	}
192	0	pfirst = UINT32_MAX; / a value we cannot store */
193	0	return FALSE;
194	0	}
195
196		static bool uint32_spbset_chunk_next(struct uint32_spbset_chunk *chunk,
197		uint32_t last,
198		uint32_t *pnext)
199	0	{
200	0	if(chunk->offset <= last) {
201	0	uint64_t x;
202	0	uint32_t i = ((last - chunk->offset) / 64);
203	0	if(i < CURL_UINT32_SPBSET_CH_SLOTS) {
204	0	x = (chunk->slots[i] >> (last % 64));
205	0	if(x) {
206		/* more bits set, next is `last` + trailing0s of the shifted slot */
207	0	*pnext = last + CURL_CTZ64(x);
208	0	return TRUE;
209	0	}
210		/* no more bits set in the last slot, scan forward */
211	0	for(i = i + 1; i < CURL_UINT32_SPBSET_CH_SLOTS; ++i) {
212	0	if(chunk->slots[i]) {
213	0	pnext = chunk->offset + ((i 64) + CURL_CTZ64(chunk->slots[i]));
214	0	return TRUE;
215	0	}
216	0	}
217	0	}
218	0	}
219	0	*pnext = UINT32_MAX;
220	0	return FALSE;
221	0	}
222
223		bool Curl_uint32_spbset_next(struct uint32_spbset *bset, uint32_t last,
224		uint32_t *pnext)
225	0	{
226	0	struct uint32_spbset_chunk *chunk;
227	0	uint32_t last_offset;
228
229	0	++last; /* look for the next higher number */
230	0	last_offset = (last & ~CURL_UINT32_SPBSET_CH_MASK);
231
232	0	for(chunk = &bset->head; chunk; chunk = chunk->next) {
233	0	if(chunk->offset >= last_offset) {
234	0	break;
235	0	}
236	0	}
237
238	0	if(chunk && (chunk->offset == last_offset)) {
239		/* is there a number higher than last in this chunk? */
240	0	if(uint32_spbset_chunk_next(chunk, last, pnext))
241	0	return TRUE;
242		/* not in this chunk */
243	0	chunk = chunk->next;
244	0	}
245		/* look for the first in the "higher" chunks, if there are any. */
246	0	while(chunk) {
247	0	if(uint32_spbset_chunk_first(chunk, pnext))
248	0	return TRUE;
249	0	chunk = chunk->next;
250	0	}
251	0	*pnext = UINT32_MAX;
252		return FALSE;
253	0	}