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

#ifdef DEBUGBUILD
#define CURL_UINT32_BSET_MAGIC  0x62757473
#endif

void Curl_uint32_bset_init(struct uint32_bset *bset)
{
  memset(bset, 0, sizeof(*bset));
#ifdef DEBUGBUILD
  bset->init = CURL_UINT32_BSET_MAGIC;
#endif
}

CURLcode Curl_uint32_bset_resize(struct uint32_bset *bset, uint32_t nmax)
{
  uint32_t nslots = (nmax < (UINT32_MAX - 63)) ?
                    ((nmax + 63) / 64) : (UINT32_MAX / 64);

  DEBUGASSERT(bset->init == CURL_UINT32_BSET_MAGIC);
  if(nslots != bset->nslots) {
    uint64_t *slots;
    if(nslots > 1) {
      slots = curlx_calloc(nslots, sizeof(uint64_t));
      if(!slots)
        return CURLE_OUT_OF_MEMORY;
    }
    else {
      bset->slot0 = 0;
      slots = &bset->slot0;
    }

    if((bset->slots != slots) && nslots && bset->nslots) {
      memcpy(slots, bset->slots,
             (CURLMIN(nslots, bset->nslots) * sizeof(uint64_t)));
      if(bset->slots != &bset->slot0)
        curlx_free(bset->slots);
    }
    bset->slots = slots;
    bset->nslots = nslots;
    bset->first_slot_used = 0;
  }
  return CURLE_OK;
}

void Curl_uint32_bset_destroy(struct uint32_bset *bset)
{
  DEBUGASSERT(bset->init == CURL_UINT32_BSET_MAGIC);
  if(bset->slots != &bset->slot0)
    curlx_free(bset->slots);
  memset(bset, 0, sizeof(*bset));
}

#ifdef UNITTESTS
/* @unittest 3211 */
UNITTEST uint32_t uint32_bset_capacity(struct uint32_bset *bset);
UNITTEST uint32_t uint32_bset_capacity(struct uint32_bset *bset)
{
  return bset->nslots * 64;
}
#endif

uint32_t Curl_uint32_bset_count(struct uint32_bset *bset)
{
  uint32_t i;
  uint32_t n = 0;
  for(i = 0; i < bset->nslots; ++i) {
    if(bset->slots[i])
      n += CURL_POPCOUNT64(bset->slots[i]);
  }
  return n;
}

bool Curl_uint32_bset_empty(struct uint32_bset *bset)
{
  uint32_t i;
  for(i = bset->first_slot_used; i < bset->nslots; ++i) {
    if(bset->slots[i])
      return FALSE;
  }
  return TRUE;
}

void Curl_uint32_bset_clear(struct uint32_bset *bset)
{
  if(bset->nslots) {
    memset(bset->slots, 0, bset->nslots * sizeof(uint64_t));
    bset->first_slot_used = UINT32_MAX;
  }
}

bool Curl_uint32_bset_add(struct uint32_bset *bset, uint32_t i)
{
  uint32_t islot = i / 64;
  if(islot >= bset->nslots)
    return FALSE;
  bset->slots[islot] |= ((uint64_t)1 << (i % 64));
  if(islot < bset->first_slot_used)
    bset->first_slot_used = islot;
  return TRUE;
}

void Curl_uint32_bset_remove(struct uint32_bset *bset, uint32_t i)
{
  size_t islot = i / 64;
  if(islot < bset->nslots)
    bset->slots[islot] &= ~((uint64_t)1 << (i % 64));
}

bool Curl_uint32_bset_contains(struct uint32_bset *bset, uint32_t i)
{
  uint32_t islot = i / 64;
  if(islot >= bset->nslots)
    return FALSE;
  return (bset->slots[islot] & ((uint64_t)1 << (i % 64))) != 0;
}

bool Curl_uint32_bset_first(struct uint32_bset *bset, uint32_t *pfirst)
{
  uint32_t i;
  for(i = bset->first_slot_used; i < bset->nslots; ++i) {
    if(bset->slots[i]) {
      *pfirst = (i * 64) + CURL_CTZ64(bset->slots[i]);
      bset->first_slot_used = i;
      return TRUE;
    }
  }
  bset->first_slot_used = *pfirst = UINT32_MAX;
  return FALSE;
}

bool Curl_uint32_bset_next(struct uint32_bset *bset, uint32_t last,
                           uint32_t *pnext)
{
  uint32_t islot;
  uint64_t x;

  ++last; /* look for number one higher than last */
  islot = last / 64; /* the slot this would be in */
  if(islot < bset->nslots) {
    /* shift away the bits we already iterated in this slot */
    x = (bset->slots[islot] >> (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(islot = islot + 1; islot < bset->nslots; ++islot) {
      if(bset->slots[islot]) {
        *pnext = (islot * 64) + CURL_CTZ64(bset->slots[islot]);
        return TRUE;
      }
    }
  }
  *pnext = UINT32_MAX; /* a value we cannot store */
  return FALSE;
}

#ifdef CURL_POPCOUNT64_IMPLEMENT
uint32_t Curl_popcount64(uint64_t x)
{
  /* Compute the "Hamming Distance" between 'x' and 0,
   * which is the number of set bits in 'x'.
   * See: https://en.wikipedia.org/wiki/Hamming_weight */
  const uint64_t m1 = 0x5555555555555555LL; /* 0101+ */
  const uint64_t m2 = 0x3333333333333333LL; /* 00110011+ */
  const uint64_t m4 = 0x0f0f0f0f0f0f0f0fLL; /* 00001111+ */
  /* 1 + 256^1 + 256^2 + 256^3 + ... + 256^7 */
  const uint64_t h01 = 0x0101010101010101LL;
  x -= (x >> 1) & m1;             /* replace every 2 bits with bits present */
  x = (x & m2) + ((x >> 2) & m2); /* replace every nibble with bits present */
  x = (x + (x >> 4)) & m4;        /* replace every byte with bits present */
  /* top 8 bits of x + (x << 8) + (x << 16) + (x << 24) + ... which makes the
   * top byte the sum of all individual 8 bytes, throw away the rest */
  return (uint32_t)((x * h01) >> 56);
}
#endif /* CURL_POPCOUNT64_IMPLEMENT */

#ifdef CURL_CTZ64_IMPLEMENT
uint32_t Curl_ctz64(uint64_t x)
{
  /* count trailing zeros in a uint64_t.
   * divide and conquer to find the number of lower 0 bits */
  const uint64_t ml32 = 0xFFFFFFFF; /* lower 32 bits */
  const uint64_t ml16 = 0x0000FFFF; /* lower 16 bits */
  const uint64_t ml8  = 0x000000FF; /* lower 8 bits */
  const uint64_t ml4  = 0x0000000F; /* lower 4 bits */
  const uint64_t ml2  = 0x00000003; /* lower 2 bits */
  uint32_t n;

  if(!x)
    return 64;
  n = 1;
  if(!(x & ml32)) {
    n = n + 32;
    x = x >> 32;
  }
  if(!(x & ml16)) {
    n = n + 16;
    x = x >> 16;
  }
  if(!(x & ml8)) {
    n = n + 8;
    x = x >> 8;
  }
  if(!(x & ml4)) {
    n = n + 4;
    x = x >> 4;
  }
  if(!(x & ml2)) {
    n = n + 2;
    x = x >> 2;
  }
  return n - (uint32_t)(x & 1);
}
#endif /* CURL_CTZ64_IMPLEMENT */

Coverage Report

Created: 2026-08-13 07:18

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
28		#ifdef DEBUGBUILD
29	0	#define CURL_UINT32_BSET_MAGIC 0x62757473
30		#endif
31
32		void Curl_uint32_bset_init(struct uint32_bset *bset)
33	0	{
34	0	memset(bset, 0, sizeof(*bset));
35	0	#ifdef DEBUGBUILD
36	0	bset->init = CURL_UINT32_BSET_MAGIC;
37	0	#endif
38	0	}
39
40		CURLcode Curl_uint32_bset_resize(struct uint32_bset *bset, uint32_t nmax)
41	0	{
42	0	uint32_t nslots = (nmax < (UINT32_MAX - 63)) ?
43	0	((nmax + 63) / 64) : (UINT32_MAX / 64);
44
45	0	DEBUGASSERT(bset->init == CURL_UINT32_BSET_MAGIC);
46	0	if(nslots != bset->nslots) {
47	0	uint64_t *slots;
48	0	if(nslots > 1) {
49	0	slots = curlx_calloc(nslots, sizeof(uint64_t));
50	0	if(!slots)
51	0	return CURLE_OUT_OF_MEMORY;
52	0	}
53	0	else {
54	0	bset->slot0 = 0;
55	0	slots = &bset->slot0;
56	0	}
57
58	0	if((bset->slots != slots) && nslots && bset->nslots) {
59	0	memcpy(slots, bset->slots,
60	0	(CURLMIN(nslots, bset->nslots) * sizeof(uint64_t)));
61	0	if(bset->slots != &bset->slot0)
62	0	curlx_free(bset->slots);
63	0	}
64	0	bset->slots = slots;
65	0	bset->nslots = nslots;
66	0	bset->first_slot_used = 0;
67	0	}
68	0	return CURLE_OK;
69	0	}
70
71		void Curl_uint32_bset_destroy(struct uint32_bset *bset)
72	0	{
73	0	DEBUGASSERT(bset->init == CURL_UINT32_BSET_MAGIC);
74	0	if(bset->slots != &bset->slot0)
75	0	curlx_free(bset->slots);
76	0	memset(bset, 0, sizeof(*bset));
77	0	}
78
79		#ifdef UNITTESTS
80		/* @unittest 3211 */
81		UNITTEST uint32_t uint32_bset_capacity(struct uint32_bset *bset);
82		UNITTEST uint32_t uint32_bset_capacity(struct uint32_bset *bset)
83	0	{
84	0	return bset->nslots * 64;
85	0	}
86		#endif
87
88		uint32_t Curl_uint32_bset_count(struct uint32_bset *bset)
89	0	{
90	0	uint32_t i;
91	0	uint32_t n = 0;
92	0	for(i = 0; i < bset->nslots; ++i) {
93	0	if(bset->slots[i])
94	0	n += CURL_POPCOUNT64(bset->slots[i]);
95	0	}
96	0	return n;
97	0	}
98
99		bool Curl_uint32_bset_empty(struct uint32_bset *bset)
100	0	{
101	0	uint32_t i;
102	0	for(i = bset->first_slot_used; i < bset->nslots; ++i) {
103	0	if(bset->slots[i])
104	0	return FALSE;
105	0	}
106	0	return TRUE;
107	0	}
108
109		void Curl_uint32_bset_clear(struct uint32_bset *bset)
110	0	{
111	0	if(bset->nslots) {
112	0	memset(bset->slots, 0, bset->nslots * sizeof(uint64_t));
113	0	bset->first_slot_used = UINT32_MAX;
114	0	}
115	0	}
116
117		bool Curl_uint32_bset_add(struct uint32_bset *bset, uint32_t i)
118	0	{
119	0	uint32_t islot = i / 64;
120	0	if(islot >= bset->nslots)
121	0	return FALSE;
122	0	bset->slots[islot] \|= ((uint64_t)1 << (i % 64));
123	0	if(islot < bset->first_slot_used)
124	0	bset->first_slot_used = islot;
125	0	return TRUE;
126	0	}
127
128		void Curl_uint32_bset_remove(struct uint32_bset *bset, uint32_t i)
129	0	{
130	0	size_t islot = i / 64;
131	0	if(islot < bset->nslots)
132	0	bset->slots[islot] &= ~((uint64_t)1 << (i % 64));
133	0	}
134
135		bool Curl_uint32_bset_contains(struct uint32_bset *bset, uint32_t i)
136	0	{
137	0	uint32_t islot = i / 64;
138	0	if(islot >= bset->nslots)
139	0	return FALSE;
140	0	return (bset->slots[islot] & ((uint64_t)1 << (i % 64))) != 0;
141	0	}
142
143		bool Curl_uint32_bset_first(struct uint32_bset bset, uint32_t pfirst)
144	0	{
145	0	uint32_t i;
146	0	for(i = bset->first_slot_used; i < bset->nslots; ++i) {
147	0	if(bset->slots[i]) {
148	0	pfirst = (i 64) + CURL_CTZ64(bset->slots[i]);
149	0	bset->first_slot_used = i;
150	0	return TRUE;
151	0	}
152	0	}
153	0	bset->first_slot_used = *pfirst = UINT32_MAX;
154	0	return FALSE;
155	0	}
156
157		bool Curl_uint32_bset_next(struct uint32_bset *bset, uint32_t last,
158		uint32_t *pnext)
159	0	{
160	0	uint32_t islot;
161	0	uint64_t x;
162
163	0	++last; /* look for number one higher than last */
164	0	islot = last / 64; /* the slot this would be in */
165	0	if(islot < bset->nslots) {
166		/* shift away the bits we already iterated in this slot */
167	0	x = (bset->slots[islot] >> (last % 64));
168	0	if(x) {
169		/* more bits set, next is `last` + trailing 0s of the shifted slot */
170	0	*pnext = last + CURL_CTZ64(x);
171	0	return TRUE;
172	0	}
173		/* no more bits set in the last slot, scan forward */
174	0	for(islot = islot + 1; islot < bset->nslots; ++islot) {
175	0	if(bset->slots[islot]) {
176	0	pnext = (islot 64) + CURL_CTZ64(bset->slots[islot]);
177	0	return TRUE;
178	0	}
179	0	}
180	0	}
181	0	pnext = UINT32_MAX; / a value we cannot store */
182		return FALSE;
183	0	}
184
185		#ifdef CURL_POPCOUNT64_IMPLEMENT
186		uint32_t Curl_popcount64(uint64_t x)
187		{
188		/* Compute the "Hamming Distance" between 'x' and 0,
189		* which is the number of set bits in 'x'.
190		* See: https://en.wikipedia.org/wiki/Hamming_weight */
191		const uint64_t m1 = 0x5555555555555555LL; /* 0101+ */
192		const uint64_t m2 = 0x3333333333333333LL; /* 00110011+ */
193		const uint64_t m4 = 0x0f0f0f0f0f0f0f0fLL; /* 00001111+ */
194		/* 1 + 256^1 + 256^2 + 256^3 + ... + 256^7 */
195		const uint64_t h01 = 0x0101010101010101LL;
196		x -= (x >> 1) & m1; /* replace every 2 bits with bits present */
197		x = (x & m2) + ((x >> 2) & m2); /* replace every nibble with bits present */
198		x = (x + (x >> 4)) & m4; /* replace every byte with bits present */
199		/* top 8 bits of x + (x << 8) + (x << 16) + (x << 24) + ... which makes the
200		* top byte the sum of all individual 8 bytes, throw away the rest */
201		return (uint32_t)((x * h01) >> 56);
202		}
203		#endif /* CURL_POPCOUNT64_IMPLEMENT */
204
205		#ifdef CURL_CTZ64_IMPLEMENT
206		uint32_t Curl_ctz64(uint64_t x)
207		{
208		/* count trailing zeros in a uint64_t.
209		* divide and conquer to find the number of lower 0 bits */
210		const uint64_t ml32 = 0xFFFFFFFF; /* lower 32 bits */
211		const uint64_t ml16 = 0x0000FFFF; /* lower 16 bits */
212		const uint64_t ml8 = 0x000000FF; /* lower 8 bits */
213		const uint64_t ml4 = 0x0000000F; /* lower 4 bits */
214		const uint64_t ml2 = 0x00000003; /* lower 2 bits */
215		uint32_t n;
216
217		if(!x)
218		return 64;
219		n = 1;
220		if(!(x & ml32)) {
221		n = n + 32;
222		x = x >> 32;
223		}
224		if(!(x & ml16)) {
225		n = n + 16;
226		x = x >> 16;
227		}
228		if(!(x & ml8)) {
229		n = n + 8;
230		x = x >> 8;
231		}
232		if(!(x & ml4)) {
233		n = n + 4;
234		x = x >> 4;
235		}
236		if(!(x & ml2)) {
237		n = n + 2;
238		x = x >> 2;
239		}
240		return n - (uint32_t)(x & 1);
241		}
242		#endif /* CURL_CTZ64_IMPLEMENT */