uint-spbset.c (7464B)
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 #include "uint-spbset.h" 28 29 /* The last 3 #include files should be in this order */ 30 #include "curl_printf.h" 31 #include "curl_memory.h" 32 #include "memdebug.h" 33 34 #ifdef DEBUGBUILD 35 #define CURL_UINT_SPBSET_MAGIC 0x70737362 36 #endif 37 38 /* Clear the bitset, making it empty. */ 39 UNITTEST void Curl_uint_spbset_clear(struct uint_spbset *bset); 40 41 void Curl_uint_spbset_init(struct uint_spbset *bset) 42 { 43 memset(bset, 0, sizeof(*bset)); 44 #ifdef DEBUGBUILD 45 bset->init = CURL_UINT_SPBSET_MAGIC; 46 #endif 47 } 48 49 void Curl_uint_spbset_destroy(struct uint_spbset *bset) 50 { 51 DEBUGASSERT(bset->init == CURL_UINT_SPBSET_MAGIC); 52 Curl_uint_spbset_clear(bset); 53 } 54 55 unsigned int Curl_uint_spbset_count(struct uint_spbset *bset) 56 { 57 struct uint_spbset_chunk *chunk; 58 unsigned int i, n = 0; 59 60 for(chunk = &bset->head; chunk; chunk = chunk->next) { 61 for(i = 0; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) { 62 if(chunk->slots[i]) 63 n += CURL_POPCOUNT64(chunk->slots[i]); 64 } 65 } 66 return n; 67 } 68 69 bool Curl_uint_spbset_empty(struct uint_spbset *bset) 70 { 71 struct uint_spbset_chunk *chunk; 72 unsigned int i; 73 74 for(chunk = &bset->head; chunk; chunk = chunk->next) { 75 for(i = 0; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) { 76 if(chunk->slots[i]) 77 return FALSE; 78 } 79 } 80 return TRUE; 81 } 82 83 UNITTEST void Curl_uint_spbset_clear(struct uint_spbset *bset) 84 { 85 struct uint_spbset_chunk *next, *chunk; 86 87 for(chunk = bset->head.next; chunk; chunk = next) { 88 next = chunk->next; 89 free(chunk); 90 } 91 memset(&bset->head, 0, sizeof(bset->head)); 92 } 93 94 95 static struct uint_spbset_chunk * 96 uint_spbset_get_chunk(struct uint_spbset *bset, unsigned int i, bool grow) 97 { 98 struct uint_spbset_chunk *chunk, **panchor = NULL; 99 unsigned int i_offset = (i & ~CURL_UINT_SPBSET_CH_MASK); 100 101 if(!bset) 102 return NULL; 103 104 for(chunk = &bset->head; chunk; 105 panchor = &chunk->next, chunk = chunk->next) { 106 if(chunk->offset == i_offset) { 107 return chunk; 108 } 109 else if(chunk->offset > i_offset) { 110 /* need new chunk here */ 111 chunk = NULL; 112 break; 113 } 114 } 115 116 if(!grow) 117 return NULL; 118 119 /* need a new one */ 120 chunk = calloc(1, sizeof(*chunk)); 121 if(!chunk) 122 return NULL; 123 124 if(panchor) { /* insert between panchor and *panchor */ 125 chunk->next = *panchor; 126 *panchor = chunk; 127 } 128 else { /* prepend to head, switching places */ 129 memcpy(chunk, &bset->head, sizeof(*chunk)); 130 memset(&bset->head, 0, sizeof(bset->head)); 131 bset->head.next = chunk; 132 } 133 chunk->offset = i_offset; 134 return chunk; 135 } 136 137 138 bool Curl_uint_spbset_add(struct uint_spbset *bset, unsigned int i) 139 { 140 struct uint_spbset_chunk *chunk; 141 unsigned int i_chunk; 142 143 chunk = uint_spbset_get_chunk(bset, i, TRUE); 144 if(!chunk) 145 return FALSE; 146 147 DEBUGASSERT(i >= chunk->offset); 148 i_chunk = (i - chunk->offset); 149 DEBUGASSERT((i_chunk / 64) < CURL_UINT_SPBSET_CH_SLOTS); 150 chunk->slots[(i_chunk / 64)] |= ((curl_uint64_t)1 << (i_chunk % 64)); 151 return TRUE; 152 } 153 154 155 void Curl_uint_spbset_remove(struct uint_spbset *bset, unsigned int i) 156 { 157 struct uint_spbset_chunk *chunk; 158 unsigned int i_chunk; 159 160 chunk = uint_spbset_get_chunk(bset, i, FALSE); 161 if(chunk) { 162 DEBUGASSERT(i >= chunk->offset); 163 i_chunk = (i - chunk->offset); 164 DEBUGASSERT((i_chunk / 64) < CURL_UINT_SPBSET_CH_SLOTS); 165 chunk->slots[(i_chunk / 64)] &= ~((curl_uint64_t)1 << (i_chunk % 64)); 166 } 167 } 168 169 170 bool Curl_uint_spbset_contains(struct uint_spbset *bset, unsigned int i) 171 { 172 struct uint_spbset_chunk *chunk; 173 unsigned int i_chunk; 174 175 chunk = uint_spbset_get_chunk(bset, i, FALSE); 176 if(chunk) { 177 DEBUGASSERT(i >= chunk->offset); 178 i_chunk = (i - chunk->offset); 179 DEBUGASSERT((i_chunk / 64) < CURL_UINT_SPBSET_CH_SLOTS); 180 return (chunk->slots[i_chunk / 64] & 181 ((curl_uint64_t)1 << (i_chunk % 64))) != 0; 182 } 183 return FALSE; 184 } 185 186 bool Curl_uint_spbset_first(struct uint_spbset *bset, unsigned int *pfirst) 187 { 188 struct uint_spbset_chunk *chunk; 189 unsigned int i; 190 191 for(chunk = &bset->head; chunk; chunk = chunk->next) { 192 for(i = 0; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) { 193 if(chunk->slots[i]) { 194 *pfirst = chunk->offset + ((i * 64) + CURL_CTZ64(chunk->slots[i])); 195 return TRUE; 196 } 197 } 198 } 199 *pfirst = 0; /* give it a defined value even if it should not be used */ 200 return FALSE; 201 } 202 203 204 static bool uint_spbset_chunk_first(struct uint_spbset_chunk *chunk, 205 unsigned int *pfirst) 206 { 207 unsigned int i; 208 for(i = 0; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) { 209 if(chunk->slots[i]) { 210 *pfirst = chunk->offset + ((i * 64) + CURL_CTZ64(chunk->slots[i])); 211 return TRUE; 212 } 213 } 214 *pfirst = UINT_MAX; /* a value we cannot store */ 215 return FALSE; 216 } 217 218 219 static bool uint_spbset_chunk_next(struct uint_spbset_chunk *chunk, 220 unsigned int last, 221 unsigned int *pnext) 222 { 223 if(chunk->offset <= last) { 224 curl_uint64_t x; 225 unsigned int i = ((last - chunk->offset) / 64); 226 if(i < CURL_UINT_SPBSET_CH_SLOTS) { 227 x = (chunk->slots[i] >> (last % 64)); 228 if(x) { 229 /* more bits set, next is `last` + trailing0s of the shifted slot */ 230 *pnext = last + CURL_CTZ64(x); 231 return TRUE; 232 } 233 /* no more bits set in the last slot, scan forward */ 234 for(i = i + 1; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) { 235 if(chunk->slots[i]) { 236 *pnext = chunk->offset + ((i * 64) + CURL_CTZ64(chunk->slots[i])); 237 return TRUE; 238 } 239 } 240 } 241 } 242 *pnext = UINT_MAX; 243 return FALSE; 244 } 245 246 bool Curl_uint_spbset_next(struct uint_spbset *bset, unsigned int last, 247 unsigned int *pnext) 248 { 249 struct uint_spbset_chunk *chunk; 250 unsigned int last_offset; 251 252 ++last; /* look for the next higher number */ 253 last_offset = (last & ~CURL_UINT_SPBSET_CH_MASK); 254 255 for(chunk = &bset->head; chunk; chunk = chunk->next) { 256 if(chunk->offset >= last_offset) { 257 break; 258 } 259 } 260 261 if(chunk && (chunk->offset == last_offset)) { 262 /* is there a number higher than last in this chunk? */ 263 if(uint_spbset_chunk_next(chunk, last, pnext)) 264 return TRUE; 265 /* not in this chunk */ 266 chunk = chunk->next; 267 } 268 /* look for the first in the "higher" chunks, if there are any. */ 269 while(chunk) { 270 if(uint_spbset_chunk_first(chunk, pnext)) 271 return TRUE; 272 chunk = chunk->next; 273 } 274 *pnext = UINT_MAX; 275 return FALSE; 276 }