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

/* The last 2 #include files should be in this order */
#include "curl_memory.h"
#include "memdebug.h"

#ifdef DEBUGBUILD
#define CURL_UINT_BSET_MAGIC  0x62757473
#endif

void Curl_uint_bset_init(struct uint_bset *bset)
{
  memset(bset, 0, sizeof(*bset));
#ifdef DEBUGBUILD
  bset->init = CURL_UINT_BSET_MAGIC;
#endif
}


CURLcode Curl_uint_bset_resize(struct uint_bset *bset, unsigned int nmax)
{
  unsigned int nslots = (nmax < (UINT_MAX-63)) ?
                        ((nmax + 63) / 64) : (UINT_MAX / 64);

  DEBUGASSERT(bset->init == CURL_UINT_BSET_MAGIC);
  if(nslots != bset->nslots) {
    curl_uint64_t *slots = calloc(nslots, sizeof(curl_uint64_t));
    if(!slots)
      return CURLE_OUT_OF_MEMORY;

    if(bset->slots) {
      memcpy(slots, bset->slots,
             (CURLMIN(nslots, bset->nslots) * sizeof(curl_uint64_t)));
      free(bset->slots);
    }
    bset->slots = slots;
    bset->nslots = nslots;
    bset->first_slot_used = 0;
  }
  return CURLE_OK;
}


void Curl_uint_bset_destroy(struct uint_bset *bset)
{
  DEBUGASSERT(bset->init == CURL_UINT_BSET_MAGIC);
  free(bset->slots);
  memset(bset, 0, sizeof(*bset));
}

#ifdef UNITTESTS
UNITTEST unsigned int Curl_uint_bset_capacity(struct uint_bset *bset)
{
  return bset->nslots * 64;
}
#endif

unsigned int Curl_uint_bset_count(struct uint_bset *bset)
{
  unsigned int i;
  unsigned int n = 0;
  for(i = 0; i < bset->nslots; ++i) {
    if(bset->slots[i])
      n += CURL_POPCOUNT64(bset->slots[i]);
  }
  return n;
}

bool Curl_uint_bset_empty(struct uint_bset *bset)
{
  unsigned int i;
  for(i = bset->first_slot_used; i < bset->nslots; ++i) {
    if(bset->slots[i])
      return FALSE;
  }
  return TRUE;
}


void Curl_uint_bset_clear(struct uint_bset *bset)
{
  if(bset->nslots) {
    memset(bset->slots, 0, bset->nslots * sizeof(curl_uint64_t));
    bset->first_slot_used = UINT_MAX;
  }
}


bool Curl_uint_bset_add(struct uint_bset *bset, unsigned int i)
{
  unsigned int islot = i / 64;
  if(islot >= bset->nslots)
    return FALSE;
  bset->slots[islot] |= ((curl_uint64_t)1 << (i % 64));
  if(islot < bset->first_slot_used)
    bset->first_slot_used = islot;
  return TRUE;
}


void Curl_uint_bset_remove(struct uint_bset *bset, unsigned int i)
{
  size_t islot = i / 64;
  if(islot < bset->nslots)
    bset->slots[islot] &= ~((curl_uint64_t)1 << (i % 64));
}


bool Curl_uint_bset_contains(struct uint_bset *bset, unsigned int i)
{
  unsigned int islot = i / 64;
  if(islot >= bset->nslots)
    return FALSE;
  return (bset->slots[islot] & ((curl_uint64_t)1 << (i % 64))) != 0;
}


bool Curl_uint_bset_first(struct uint_bset *bset, unsigned int *pfirst)
{
  unsigned int 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 = UINT_MAX;
  return FALSE;
}

bool Curl_uint_bset_next(struct uint_bset *bset, unsigned int last,
                         unsigned int *pnext)
{
  unsigned int islot;
  curl_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 = UINT_MAX; /* a value we cannot store */
  return FALSE;
}

#ifdef CURL_POPCOUNT64_IMPLEMENT
unsigned int Curl_popcount64(curl_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 curl_uint64_t m1  = 0x5555555555555555LL; /* 0101+ */
  const curl_uint64_t m2  = 0x3333333333333333LL; /* 00110011+ */
  const curl_uint64_t m4  = 0x0f0f0f0f0f0f0f0fLL; /* 00001111+ */
   /* 1 + 256^1 + 256^2 + 256^3 + ... + 256^7 */
  const curl_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 (unsigned int)((x * h01) >> 56);
}
#endif /* CURL_POPCOUNT64_IMPLEMENT */


#ifdef CURL_CTZ64_IMPLEMENT
unsigned int Curl_ctz64(curl_uint64_t x)
{
  /* count trailing zeros in a curl_uint64_t.
   * divide and conquer to find the number of lower 0 bits */
  const curl_uint64_t ml32 = 0xFFFFFFFF; /* lower 32 bits */
  const curl_uint64_t ml16 = 0x0000FFFF; /* lower 16 bits */
  const curl_uint64_t ml8  = 0x000000FF; /* lower 8 bits */
  const curl_uint64_t ml4  = 0x0000000F; /* lower 4 bits */
  const curl_uint64_t ml2  = 0x00000003; /* lower 2 bits */
  unsigned int 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 - (unsigned int)(x & 1);
}
#endif /* CURL_CTZ64_IMPLEMENT */

Coverage Report

Created: 2025-10-10 06:09

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		/* The last 2 #include files should be in this order */
29		#include "curl_memory.h"
30		#include "memdebug.h"
31
32		#ifdef DEBUGBUILD
33	0	#define CURL_UINT_BSET_MAGIC 0x62757473
34		#endif
35
36		void Curl_uint_bset_init(struct uint_bset *bset)
37	0	{
38	0	memset(bset, 0, sizeof(*bset));
39	0	#ifdef DEBUGBUILD
40	0	bset->init = CURL_UINT_BSET_MAGIC;
41	0	#endif
42	0	}
43
44
45		CURLcode Curl_uint_bset_resize(struct uint_bset *bset, unsigned int nmax)
46	0	{
47	0	unsigned int nslots = (nmax < (UINT_MAX-63)) ?
48	0	((nmax + 63) / 64) : (UINT_MAX / 64);
49
50	0	DEBUGASSERT(bset->init == CURL_UINT_BSET_MAGIC);
51	0	if(nslots != bset->nslots) {
52	0	curl_uint64_t *slots = calloc(nslots, sizeof(curl_uint64_t));
53	0	if(!slots)
54	0	return CURLE_OUT_OF_MEMORY;
55
56	0	if(bset->slots) {
57	0	memcpy(slots, bset->slots,
58	0	(CURLMIN(nslots, bset->nslots) * sizeof(curl_uint64_t)));
59	0	free(bset->slots);
60	0	}
61	0	bset->slots = slots;
62	0	bset->nslots = nslots;
63	0	bset->first_slot_used = 0;
64	0	}
65	0	return CURLE_OK;
66	0	}
67
68
69		void Curl_uint_bset_destroy(struct uint_bset *bset)
70	0	{
71	0	DEBUGASSERT(bset->init == CURL_UINT_BSET_MAGIC);
72	0	free(bset->slots);
73	0	memset(bset, 0, sizeof(*bset));
74	0	}
75
76		#ifdef UNITTESTS
77		UNITTEST unsigned int Curl_uint_bset_capacity(struct uint_bset *bset)
78		{
79		return bset->nslots * 64;
80		}
81		#endif
82
83		unsigned int Curl_uint_bset_count(struct uint_bset *bset)
84	0	{
85	0	unsigned int i;
86	0	unsigned int n = 0;
87	0	for(i = 0; i < bset->nslots; ++i) {
88	0	if(bset->slots[i])
89	0	n += CURL_POPCOUNT64(bset->slots[i]);
90	0	}
91	0	return n;
92	0	}
93
94		bool Curl_uint_bset_empty(struct uint_bset *bset)
95	0	{
96	0	unsigned int i;
97	0	for(i = bset->first_slot_used; i < bset->nslots; ++i) {
98	0	if(bset->slots[i])
99	0	return FALSE;
100	0	}
101	0	return TRUE;
102	0	}
103
104
105		void Curl_uint_bset_clear(struct uint_bset *bset)
106	0	{
107	0	if(bset->nslots) {
108	0	memset(bset->slots, 0, bset->nslots * sizeof(curl_uint64_t));
109	0	bset->first_slot_used = UINT_MAX;
110	0	}
111	0	}
112
113
114		bool Curl_uint_bset_add(struct uint_bset *bset, unsigned int i)
115	0	{
116	0	unsigned int islot = i / 64;
117	0	if(islot >= bset->nslots)
118	0	return FALSE;
119	0	bset->slots[islot] \|= ((curl_uint64_t)1 << (i % 64));
120	0	if(islot < bset->first_slot_used)
121	0	bset->first_slot_used = islot;
122	0	return TRUE;
123	0	}
124
125
126		void Curl_uint_bset_remove(struct uint_bset *bset, unsigned int i)
127	0	{
128	0	size_t islot = i / 64;
129	0	if(islot < bset->nslots)
130	0	bset->slots[islot] &= ~((curl_uint64_t)1 << (i % 64));
131	0	}
132
133
134		bool Curl_uint_bset_contains(struct uint_bset *bset, unsigned int i)
135	0	{
136	0	unsigned int islot = i / 64;
137	0	if(islot >= bset->nslots)
138	0	return FALSE;
139	0	return (bset->slots[islot] & ((curl_uint64_t)1 << (i % 64))) != 0;
140	0	}
141
142
143		bool Curl_uint_bset_first(struct uint_bset bset, unsigned int pfirst)
144	0	{
145	0	unsigned int 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 = UINT_MAX;
154	0	return FALSE;
155	0	}
156
157		bool Curl_uint_bset_next(struct uint_bset *bset, unsigned int last,
158		unsigned int *pnext)
159	0	{
160	0	unsigned int islot;
161	0	curl_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` + trailing0s 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 = UINT_MAX; / a value we cannot store */
182		return FALSE;
183	0	}
184
185		#ifdef CURL_POPCOUNT64_IMPLEMENT
186		unsigned int Curl_popcount64(curl_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 curl_uint64_t m1 = 0x5555555555555555LL; /* 0101+ */
192		const curl_uint64_t m2 = 0x3333333333333333LL; /* 00110011+ */
193		const curl_uint64_t m4 = 0x0f0f0f0f0f0f0f0fLL; /* 00001111+ */
194		/* 1 + 256^1 + 256^2 + 256^3 + ... + 256^7 */
195		const curl_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 (unsigned int)((x * h01) >> 56);
202		}
203		#endif /* CURL_POPCOUNT64_IMPLEMENT */
204
205
206		#ifdef CURL_CTZ64_IMPLEMENT
207		unsigned int Curl_ctz64(curl_uint64_t x)
208		{
209		/* count trailing zeros in a curl_uint64_t.
210		* divide and conquer to find the number of lower 0 bits */
211		const curl_uint64_t ml32 = 0xFFFFFFFF; /* lower 32 bits */
212		const curl_uint64_t ml16 = 0x0000FFFF; /* lower 16 bits */
213		const curl_uint64_t ml8 = 0x000000FF; /* lower 8 bits */
214		const curl_uint64_t ml4 = 0x0000000F; /* lower 4 bits */
215		const curl_uint64_t ml2 = 0x00000003; /* lower 2 bits */
216		unsigned int n;
217
218		if(!x)
219		return 64;
220		n = 1;
221		if(!(x & ml32)) {
222		n = n + 32;
223		x = x >> 32;
224		}
225		if(!(x & ml16)) {
226		n = n + 16;
227		x = x >> 16;
228		}
229		if(!(x & ml8)) {
230		n = n + 8;
231		x = x >> 8;
232		}
233		if(!(x & ml4)) {
234		n = n + 4;
235		x = x >> 4;
236		}
237		if(!(x & ml2)) {
238		n = n + 2;
239		x = x >> 2;
240		}
241		return n - (unsigned int)(x & 1);
242		}
243		#endif /* CURL_CTZ64_IMPLEMENT */