/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 = curlx_calloc(nslots, sizeof(uint64_t));
    if(!slots)
      return CURLE_OUT_OF_MEMORY;

    if(bset->slots) {
      memcpy(slots, bset->slots,
             (CURLMIN(nslots, bset->nslots) * sizeof(uint64_t)));
      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);
  curlx_free(bset->slots);
  memset(bset, 0, sizeof(*bset));
}

#ifdef UNITTESTS
UNITTEST uint32_t Curl_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` + trailing0s 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: 2025-12-03 07:13

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