/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

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

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

void Curl_uint32_spbset_destroy(struct uint32_spbset *bset)
{
  DEBUGASSERT(bset->init == CURL_UINT32_SPBSET_MAGIC);
  Curl_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;
}

UNITTEST void Curl_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));
}

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-01-10 07:08

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