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