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

/* The last 3 #include files should be in this order */
#include "curl_printf.h"
#include "curl_memory.h"
#include "memdebug.h"

#ifdef DEBUGBUILD
#define CURL_UINT_SPBSET_MAGIC  0x70737362
#endif

/* Clear the bitset, making it empty. */
UNITTEST void Curl_uint_spbset_clear(struct uint_spbset *bset);

void Curl_uint_spbset_init(struct uint_spbset *bset)
{
  memset(bset, 0, sizeof(*bset));
#ifdef DEBUGBUILD
  bset->init = CURL_UINT_SPBSET_MAGIC;
#endif
}

void Curl_uint_spbset_destroy(struct uint_spbset *bset)
{
  DEBUGASSERT(bset->init == CURL_UINT_SPBSET_MAGIC);
  Curl_uint_spbset_clear(bset);
}

unsigned int Curl_uint_spbset_count(struct uint_spbset *bset)
{
  struct uint_spbset_chunk *chunk;
  unsigned int i, n = 0;

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

bool Curl_uint_spbset_empty(struct uint_spbset *bset)
{
  struct uint_spbset_chunk *chunk;
  unsigned int i;

  for(chunk = &bset->head; chunk; chunk = chunk->next) {
    for(i = 0; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) {
      if(chunk->slots[i])
        return FALSE;
    }
  }
  return TRUE;
}

UNITTEST void Curl_uint_spbset_clear(struct uint_spbset *bset)
{
  struct uint_spbset_chunk *next, *chunk;

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


static struct uint_spbset_chunk *
uint_spbset_get_chunk(struct uint_spbset *bset, unsigned int i, bool grow)
{
  struct uint_spbset_chunk *chunk, **panchor = NULL;
  unsigned int i_offset = (i & ~CURL_UINT_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 = 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_uint_spbset_add(struct uint_spbset *bset, unsigned int i)
{
  struct uint_spbset_chunk *chunk;
  unsigned int i_chunk;

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

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


void Curl_uint_spbset_remove(struct uint_spbset *bset, unsigned int i)
{
  struct uint_spbset_chunk *chunk;
  unsigned int i_chunk;

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


bool Curl_uint_spbset_contains(struct uint_spbset *bset, unsigned int i)
{
  struct uint_spbset_chunk *chunk;
  unsigned int i_chunk;

  chunk = uint_spbset_get_chunk(bset, i, FALSE);
  if(chunk) {
    DEBUGASSERT(i >= chunk->offset);
    i_chunk = (i - chunk->offset);
    DEBUGASSERT((i_chunk / 64) < CURL_UINT_SPBSET_CH_SLOTS);
    return (chunk->slots[i_chunk / 64] &
            ((curl_uint64_t)1 << (i_chunk % 64))) != 0;
  }
  return FALSE;
}

bool Curl_uint_spbset_first(struct uint_spbset *bset, unsigned int *pfirst)
{
  struct uint_spbset_chunk *chunk;
  unsigned int i;

  for(chunk = &bset->head; chunk; chunk = chunk->next) {
    for(i = 0; i < CURL_UINT_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 uint_spbset_chunk_first(struct uint_spbset_chunk *chunk,
                                    unsigned int *pfirst)
{
  unsigned int i;
  for(i = 0; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) {
    if(chunk->slots[i]) {
      *pfirst = chunk->offset + ((i * 64) + CURL_CTZ64(chunk->slots[i]));
      return TRUE;
    }
  }
  *pfirst = UINT_MAX; /* a value we cannot store */
  return FALSE;
}


static bool uint_spbset_chunk_next(struct uint_spbset_chunk *chunk,
                                   unsigned int last,
                                   unsigned int *pnext)
{
  if(chunk->offset <= last) {
    curl_uint64_t x;
    unsigned int i = ((last - chunk->offset) / 64);
    if(i < CURL_UINT_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_UINT_SPBSET_CH_SLOTS; ++i) {
        if(chunk->slots[i]) {
          *pnext = chunk->offset + ((i * 64) + CURL_CTZ64(chunk->slots[i]));
          return TRUE;
        }
      }
    }
  }
  *pnext = UINT_MAX;
  return FALSE;
}

bool Curl_uint_spbset_next(struct uint_spbset *bset, unsigned int last,
                           unsigned int *pnext)
{
  struct uint_spbset_chunk *chunk;
  unsigned int last_offset;

  ++last; /* look for the next higher number */
  last_offset = (last & ~CURL_UINT_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(uint_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(uint_spbset_chunk_first(chunk, pnext))
      return TRUE;
    chunk = chunk->next;
  }
  *pnext = UINT_MAX;
  return FALSE;
}

Coverage Report

Created: 2025-07-11 06:33

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		#include "uint-bset.h"
27		#include "uint-spbset.h"
28
29		/* The last 3 #include files should be in this order */
30		#include "curl_printf.h"
31		#include "curl_memory.h"
32		#include "memdebug.h"
33
34		#ifdef DEBUGBUILD
35		#define CURL_UINT_SPBSET_MAGIC 0x70737362
36		#endif
37
38		/* Clear the bitset, making it empty. */
39		UNITTEST void Curl_uint_spbset_clear(struct uint_spbset *bset);
40
41		void Curl_uint_spbset_init(struct uint_spbset *bset)
42	0	{
43	0	memset(bset, 0, sizeof(*bset));
44		#ifdef DEBUGBUILD
45		bset->init = CURL_UINT_SPBSET_MAGIC;
46		#endif
47	0	}
48
49		void Curl_uint_spbset_destroy(struct uint_spbset *bset)
50	0	{
51	0	DEBUGASSERT(bset->init == CURL_UINT_SPBSET_MAGIC);
52	0	Curl_uint_spbset_clear(bset);
53	0	}
54
55		unsigned int Curl_uint_spbset_count(struct uint_spbset *bset)
56	0	{
57	0	struct uint_spbset_chunk *chunk;
58	0	unsigned int i, n = 0;
59
60	0	for(chunk = &bset->head; chunk; chunk = chunk->next) {
61	0	for(i = 0; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) {
62	0	if(chunk->slots[i])
63	0	n += CURL_POPCOUNT64(chunk->slots[i]);
64	0	}
65	0	}
66	0	return n;
67	0	}
68
69		bool Curl_uint_spbset_empty(struct uint_spbset *bset)
70	0	{
71	0	struct uint_spbset_chunk *chunk;
72	0	unsigned int i;
73
74	0	for(chunk = &bset->head; chunk; chunk = chunk->next) {
75	0	for(i = 0; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) {
76	0	if(chunk->slots[i])
77	0	return FALSE;
78	0	}
79	0	}
80	0	return TRUE;
81	0	}
82
83		UNITTEST void Curl_uint_spbset_clear(struct uint_spbset *bset)
84	0	{
85	0	struct uint_spbset_chunk next, chunk;
86
87	0	for(chunk = bset->head.next; chunk; chunk = next) {
88	0	next = chunk->next;
89	0	free(chunk);
90	0	}
91	0	memset(&bset->head, 0, sizeof(bset->head));
92	0	}
93
94
95		static struct uint_spbset_chunk *
96		uint_spbset_get_chunk(struct uint_spbset *bset, unsigned int i, bool grow)
97	0	{
98	0	struct uint_spbset_chunk chunk, *panchor = NULL;
99	0	unsigned int i_offset = (i & ~CURL_UINT_SPBSET_CH_MASK);
100
101	0	if(!bset)
102	0	return NULL;
103
104	0	for(chunk = &bset->head; chunk;
105	0	panchor = &chunk->next, chunk = chunk->next) {
106	0	if(chunk->offset == i_offset) {
107	0	return chunk;
108	0	}
109	0	else if(chunk->offset > i_offset) {
110		/* need new chunk here */
111	0	chunk = NULL;
112	0	break;
113	0	}
114	0	}
115
116	0	if(!grow)
117	0	return NULL;
118
119		/* need a new one */
120	0	chunk = calloc(1, sizeof(*chunk));
121	0	if(!chunk)
122	0	return NULL;
123
124	0	if(panchor) { /* insert between panchor and panchor /
125	0	chunk->next = *panchor;
126	0	*panchor = chunk;
127	0	}
128	0	else { /* prepend to head, switching places */
129	0	memcpy(chunk, &bset->head, sizeof(*chunk));
130	0	memset(&bset->head, 0, sizeof(bset->head));
131	0	bset->head.next = chunk;
132	0	}
133	0	chunk->offset = i_offset;
134	0	return chunk;
135	0	}
136
137
138		bool Curl_uint_spbset_add(struct uint_spbset *bset, unsigned int i)
139	0	{
140	0	struct uint_spbset_chunk *chunk;
141	0	unsigned int i_chunk;
142
143	0	chunk = uint_spbset_get_chunk(bset, i, TRUE);
144	0	if(!chunk)
145	0	return FALSE;
146
147	0	DEBUGASSERT(i >= chunk->offset);
148	0	i_chunk = (i - chunk->offset);
149	0	DEBUGASSERT((i_chunk / 64) < CURL_UINT_SPBSET_CH_SLOTS);
150	0	chunk->slots[(i_chunk / 64)] \|= ((curl_uint64_t)1 << (i_chunk % 64));
151	0	return TRUE;
152	0	}
153
154
155		void Curl_uint_spbset_remove(struct uint_spbset *bset, unsigned int i)
156	0	{
157	0	struct uint_spbset_chunk *chunk;
158	0	unsigned int i_chunk;
159
160	0	chunk = uint_spbset_get_chunk(bset, i, FALSE);
161	0	if(chunk) {
162	0	DEBUGASSERT(i >= chunk->offset);
163	0	i_chunk = (i - chunk->offset);
164	0	DEBUGASSERT((i_chunk / 64) < CURL_UINT_SPBSET_CH_SLOTS);
165	0	chunk->slots[(i_chunk / 64)] &= ~((curl_uint64_t)1 << (i_chunk % 64));
166	0	}
167	0	}
168
169
170		bool Curl_uint_spbset_contains(struct uint_spbset *bset, unsigned int i)
171	0	{
172	0	struct uint_spbset_chunk *chunk;
173	0	unsigned int i_chunk;
174
175	0	chunk = uint_spbset_get_chunk(bset, i, FALSE);
176	0	if(chunk) {
177	0	DEBUGASSERT(i >= chunk->offset);
178	0	i_chunk = (i - chunk->offset);
179	0	DEBUGASSERT((i_chunk / 64) < CURL_UINT_SPBSET_CH_SLOTS);
180	0	return (chunk->slots[i_chunk / 64] &
181	0	((curl_uint64_t)1 << (i_chunk % 64))) != 0;
182	0	}
183	0	return FALSE;
184	0	}
185
186		bool Curl_uint_spbset_first(struct uint_spbset bset, unsigned int pfirst)
187	0	{
188	0	struct uint_spbset_chunk *chunk;
189	0	unsigned int i;
190
191	0	for(chunk = &bset->head; chunk; chunk = chunk->next) {
192	0	for(i = 0; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) {
193	0	if(chunk->slots[i]) {
194	0	pfirst = chunk->offset + ((i 64) + CURL_CTZ64(chunk->slots[i]));
195	0	return TRUE;
196	0	}
197	0	}
198	0	}
199	0	pfirst = 0; / give it a defined value even if it should not be used */
200	0	return FALSE;
201	0	}
202
203
204		static bool uint_spbset_chunk_first(struct uint_spbset_chunk *chunk,
205		unsigned int *pfirst)
206	0	{
207	0	unsigned int i;
208	0	for(i = 0; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) {
209	0	if(chunk->slots[i]) {
210	0	pfirst = chunk->offset + ((i 64) + CURL_CTZ64(chunk->slots[i]));
211	0	return TRUE;
212	0	}
213	0	}
214	0	pfirst = UINT_MAX; / a value we cannot store */
215	0	return FALSE;
216	0	}
217
218
219		static bool uint_spbset_chunk_next(struct uint_spbset_chunk *chunk,
220		unsigned int last,
221		unsigned int *pnext)
222	0	{
223	0	if(chunk->offset <= last) {
224	0	curl_uint64_t x;
225	0	unsigned int i = ((last - chunk->offset) / 64);
226	0	if(i < CURL_UINT_SPBSET_CH_SLOTS) {
227	0	x = (chunk->slots[i] >> (last % 64));
228	0	if(x) {
229		/* more bits set, next is `last` + trailing0s of the shifted slot */
230	0	*pnext = last + CURL_CTZ64(x);
231	0	return TRUE;
232	0	}
233		/* no more bits set in the last slot, scan forward */
234	0	for(i = i + 1; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) {
235	0	if(chunk->slots[i]) {
236	0	pnext = chunk->offset + ((i 64) + CURL_CTZ64(chunk->slots[i]));
237	0	return TRUE;
238	0	}
239	0	}
240	0	}
241	0	}
242	0	*pnext = UINT_MAX;
243	0	return FALSE;
244	0	}
245
246		bool Curl_uint_spbset_next(struct uint_spbset *bset, unsigned int last,
247		unsigned int *pnext)
248	0	{
249	0	struct uint_spbset_chunk *chunk;
250	0	unsigned int last_offset;
251
252	0	++last; /* look for the next higher number */
253	0	last_offset = (last & ~CURL_UINT_SPBSET_CH_MASK);
254
255	0	for(chunk = &bset->head; chunk; chunk = chunk->next) {
256	0	if(chunk->offset >= last_offset) {
257	0	break;
258	0	}
259	0	}
260
261	0	if(chunk && (chunk->offset == last_offset)) {
262		/* is there a number higher than last in this chunk? */
263	0	if(uint_spbset_chunk_next(chunk, last, pnext))
264	0	return TRUE;
265		/* not in this chunk */
266	0	chunk = chunk->next;
267	0	}
268		/* look for the first in the "higher" chunks, if there are any. */
269	0	while(chunk) {
270	0	if(uint_spbset_chunk_first(chunk, pnext))
271	0	return TRUE;
272	0	chunk = chunk->next;
273	0	}
274	0	*pnext = UINT_MAX;
275	0	return FALSE;
276	0	}