/src/PROJ/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"

/* The last 2 #include files should be in this order */
#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-10-10 06:31

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