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