1 /*************************************************************************************************** 2 3 Zyan Core Library (Zycore-C) 4 5 Original Author : Florian Bernd 6 7 * Permission is hereby granted, free of charge, to any person obtaining a copy 8 * of this software and associated documentation files (the "Software"), to deal 9 * in the Software without restriction, including without limitation the rights 10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 11 * copies of the Software, and to permit persons to whom the Software is 12 * furnished to do so, subject to the following conditions: 13 * 14 * The above copyright notice and this permission notice shall be included in all 15 * copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 23 * SOFTWARE. 24 25 ***************************************************************************************************/ 26 27 /** 28 * @file 29 * Implements the bitset class. 30 */ 31 32 #ifndef ZYCORE_BITSET_H 33 #define ZYCORE_BITSET_H 34 35 #include <Zycore/Allocator.h> 36 #include <Zycore/Status.h> 37 #include <Zycore/Types.h> 38 #include <Zycore/Vector.h> 39 40 #ifdef __cplusplus 41 extern "C" { 42 #endif 43 44 /* ============================================================================================== */ 45 /* Enums and types */ 46 /* ============================================================================================== */ 47 48 /** 49 * Defines the `ZyanVector` struct. 50 * 51 * All fields in this struct should be considered as "private". Any changes may lead to unexpected 52 * behavior. 53 */ 54 typedef struct ZyanBitset_ 55 { 56 /** 57 * The bitset size. 58 */ 59 ZyanUSize size; 60 /** 61 * The bitset data. 62 */ 63 ZyanVector bits; 64 } ZyanBitset; 65 66 /** 67 * Defines the `ZyanBitsetByteOperation` function prototype. 68 * 69 * @param v1 A pointer to the first byte. This value receives the result after performing the 70 * desired operation. 71 * @param v2 A pointer to the second byte. 72 * 73 * @return A zyan status code. 74 * 75 * This function is used to perform byte-wise operations on two `ZyanBitset` instances. 76 */ 77 typedef ZyanStatus (*ZyanBitsetByteOperation)(ZyanU8* v1, const ZyanU8* v2); 78 79 /* ============================================================================================== */ 80 /* Exported functions */ 81 /* ============================================================================================== */ 82 83 /* ---------------------------------------------------------------------------------------------- */ 84 /* Constructor and destructor */ 85 /* ---------------------------------------------------------------------------------------------- */ 86 87 #ifndef ZYAN_NO_LIBC 88 89 /** 90 * Initializes the given `ZyanBitset` instance. 91 * 92 * @param bitset A pointer to the `ZyanBitset` instance. 93 * @param count The initial amount of bits. 94 * 95 * @return A zyan status code. 96 * 97 * The space for the bitset is dynamically allocated by the default allocator using the default 98 * growth factor and the default shrink threshold. 99 */ 100 ZYCORE_EXPORT ZYAN_REQUIRES_LIBC ZyanStatus ZyanBitsetInit(ZyanBitset* bitset, ZyanUSize count); 101 102 #endif // ZYAN_NO_LIBC 103 104 /** 105 * Initializes the given `ZyanBitset` instance and sets a custom `allocator` and memory 106 * allocation/deallocation parameters. 107 * 108 * @param bitset A pointer to the `ZyanBitset` instance. 109 * @param count The initial amount of bits. 110 * @param allocator A pointer to a `ZyanAllocator` instance. 111 * @param growth_factor The growth factor. 112 * @param shrink_threshold The shrink threshold. 113 * 114 * @return A zyan status code. 115 * 116 * A growth factor of `1` disables overallocation and a shrink threshold of `0` disables 117 * dynamic shrinking. 118 */ 119 ZYCORE_EXPORT ZyanStatus ZyanBitsetInitEx(ZyanBitset* bitset, ZyanUSize count, 120 ZyanAllocator* allocator, ZyanU8 growth_factor, ZyanU8 shrink_threshold); 121 122 /** 123 * Initializes the given `ZyanBitset` instance and configures it to use a custom user 124 * defined buffer with a fixed size. 125 * 126 * @param bitset A pointer to the `ZyanBitset` instance. 127 * @param count The initial amount of bits. 128 * @param buffer A pointer to the buffer that is used as storage for the bits. 129 * @param capacity The maximum capacity (number of bytes) of the buffer. 130 * 131 * @return A zyan status code. 132 */ 133 ZYCORE_EXPORT ZyanStatus ZyanBitsetInitBuffer(ZyanBitset* bitset, ZyanUSize count, void* buffer, 134 ZyanUSize capacity); 135 136 /** 137 * Destroys the given `ZyanBitset` instance. 138 * 139 * @param bitset A pointer to the `ZyanBitset` instance. 140 * 141 * @return A zyan status code. 142 */ 143 ZYCORE_EXPORT ZyanStatus ZyanBitsetDestroy(ZyanBitset* bitset); 144 145 /* ---------------------------------------------------------------------------------------------- */ 146 /* Logical operations */ 147 /* ---------------------------------------------------------------------------------------------- */ 148 149 /** 150 * Performs a byte-wise `operation` for every byte in the given `ZyanBitset` instances. 151 * 152 * @param destination A pointer to the `ZyanBitset` instance that is used as the first input and 153 * as the destination. 154 * @param source A pointer to the `ZyanBitset` instance that is used as the second input. 155 * @param operation A pointer to the function that performs the desired operation. 156 * 157 * @return A zyan status code. 158 * 159 * The `operation` callback is invoked once for every byte in the smallest of the `ZyanBitset` 160 * instances. 161 */ 162 ZYCORE_EXPORT ZyanStatus ZyanBitsetPerformByteOperation(ZyanBitset* destination, 163 const ZyanBitset* source, ZyanBitsetByteOperation operation); 164 165 /** 166 * Performs a logical `AND` operation on the given `ZyanBitset` instances. 167 * 168 * @param destination A pointer to the `ZyanBitset` instance that is used as the first input and 169 * as the destination. 170 * @param source A pointer to the `ZyanBitset` instance that is used as the second input. 171 * 172 * @return A zyan status code. 173 * 174 * If the destination bitmask contains more bits than the source one, the state of the remaining 175 * bits will be undefined. 176 */ 177 ZYCORE_EXPORT ZyanStatus ZyanBitsetAND(ZyanBitset* destination, const ZyanBitset* source); 178 179 /** 180 * Performs a logical `OR` operation on the given `ZyanBitset` instances. 181 * 182 * @param destination A pointer to the `ZyanBitset` instance that is used as the first input and 183 * as the destination. 184 * @param source A pointer to the `ZyanBitset` instance that is used as the second input. 185 * 186 * @return A zyan status code. 187 * 188 * If the destination bitmask contains more bits than the source one, the state of the remaining 189 * bits will be undefined. 190 */ 191 ZYCORE_EXPORT ZyanStatus ZyanBitsetOR (ZyanBitset* destination, const ZyanBitset* source); 192 193 /** 194 * Performs a logical `XOR` operation on the given `ZyanBitset` instances. 195 * 196 * @param destination A pointer to the `ZyanBitset` instance that is used as the first input and 197 * as the destination. 198 * @param source A pointer to the `ZyanBitset` instance that is used as the second input. 199 * 200 * @return A zyan status code. 201 * 202 * If the destination bitmask contains more bits than the source one, the state of the remaining 203 * bits will be undefined. 204 */ 205 ZYCORE_EXPORT ZyanStatus ZyanBitsetXOR(ZyanBitset* destination, const ZyanBitset* source); 206 207 /** 208 * Flips all bits of the given `ZyanBitset` instance. 209 * 210 * @param bitset A pointer to the `ZyanBitset` instance. 211 * 212 * @return A zyan status code. 213 */ 214 ZYCORE_EXPORT ZyanStatus ZyanBitsetFlip(ZyanBitset* bitset); 215 216 /* ---------------------------------------------------------------------------------------------- */ 217 /* Bit access */ 218 /* ---------------------------------------------------------------------------------------------- */ 219 220 /** 221 * Sets the bit at `index` of the given `ZyanBitset` instance to `1`. 222 * 223 * @param bitset A pointer to the `ZyanBitset` instance. 224 * @param index The bit index. 225 * 226 * @return A zyan status code. 227 */ 228 ZYCORE_EXPORT ZyanStatus ZyanBitsetSet(ZyanBitset* bitset, ZyanUSize index); 229 230 /** 231 * Sets the bit at `index` of the given `ZyanBitset` instance to `0`. 232 * 233 * @param bitset A pointer to the `ZyanBitset` instance. 234 * @param index The bit index. 235 * 236 * @return A zyan status code. 237 */ 238 ZYCORE_EXPORT ZyanStatus ZyanBitsetReset(ZyanBitset* bitset, ZyanUSize index); 239 240 /** 241 * Sets the bit at `index` of the given `ZyanBitset` instance to the specified `value`. 242 * 243 * @param bitset A pointer to the `ZyanBitset` instance. 244 * @param index The bit index. 245 * @param value The new value. 246 * 247 * @return A zyan status code. 248 */ 249 ZYCORE_EXPORT ZyanStatus ZyanBitsetAssign(ZyanBitset* bitset, ZyanUSize index, ZyanBool value); 250 251 /** 252 * Toggles the bit at `index` of the given `ZyanBitset` instance. 253 * 254 * @param bitset A pointer to the `ZyanBitset` instance. 255 * @param index The bit index. 256 * 257 * @return A zyan status code. 258 */ 259 ZYCORE_EXPORT ZyanStatus ZyanBitsetToggle(ZyanBitset* bitset, ZyanUSize index); 260 261 /** 262 * Returns the value of the bit at `index`. 263 * 264 * @param bitset A pointer to the `ZyanBitset` instance. 265 * @param index The bit index. 266 * 267 * @return `ZYAN_STATUS_TRUE`, if the bit is set or `ZYAN_STATUS_FALSE`, if not, Another zyan 268 * status code, if an error occurred. 269 */ 270 ZYCORE_EXPORT ZyanStatus ZyanBitsetTest(ZyanBitset* bitset, ZyanUSize index); 271 272 /** 273 * Returns the value of the most significant bit. 274 * 275 * @param bitset A pointer to the `ZyanBitset` instance. 276 * 277 * @return `ZYAN_STATUS_TRUE`, if the bit is set or `ZYAN_STATUS_FALSE`, if not. Another zyan 278 * status code, if an error occurred. 279 */ 280 ZYCORE_EXPORT ZyanStatus ZyanBitsetTestMSB(ZyanBitset* bitset); 281 282 /** 283 * Returns the value of the least significant bit. 284 * 285 * @param bitset A pointer to the `ZyanBitset` instance. 286 * 287 * @return `ZYAN_STATUS_TRUE`, if the bit is set or `ZYAN_STATUS_FALSE`, if not. Another zyan 288 * status code, if an error occurred. 289 */ 290 ZYCORE_EXPORT ZyanStatus ZyanBitsetTestLSB(ZyanBitset* bitset); 291 292 /* ---------------------------------------------------------------------------------------------- */ 293 294 /** 295 * Sets all bits of the given `ZyanBitset` instance to `1`. 296 * 297 * @param bitset A pointer to the `ZyanBitset` instance. 298 * 299 * @return A zyan status code. 300 */ 301 ZYCORE_EXPORT ZyanStatus ZyanBitsetSetAll(ZyanBitset* bitset); 302 303 /** 304 * Sets all bits of the given `ZyanBitset` instance to `0`. 305 * 306 * @param bitset A pointer to the `ZyanBitset` instance. 307 * 308 * @return A zyan status code. 309 */ 310 ZYCORE_EXPORT ZyanStatus ZyanBitsetResetAll(ZyanBitset* bitset); 311 312 /* ---------------------------------------------------------------------------------------------- */ 313 /* Size management */ 314 /* ---------------------------------------------------------------------------------------------- */ 315 316 /** 317 * Adds a new bit at the end of the bitset. 318 * 319 * @param bitset A pointer to the `ZyanBitset` instance. 320 * @param value The value of the new bit. 321 * 322 * @return A zyan status code. 323 */ 324 ZYCORE_EXPORT ZyanStatus ZyanBitsetPush(ZyanBitset* bitset, ZyanBool value); 325 326 /** 327 * Removes the last bit of the bitset. 328 * 329 * @param bitset A pointer to the `ZyanBitset` instance. 330 * 331 * @return A zyan status code. 332 */ 333 ZYCORE_EXPORT ZyanStatus ZyanBitsetPop(ZyanBitset* bitset); 334 335 /** 336 * Deletes all bits of the given `ZyanBitset` instance. 337 * 338 * @param bitset A pointer to the `ZyanBitset` instance. 339 * 340 * @return A zyan status code. 341 */ 342 ZYCORE_EXPORT ZyanStatus ZyanBitsetClear(ZyanBitset* bitset); 343 344 /* ---------------------------------------------------------------------------------------------- */ 345 /* Memory management */ 346 /* ---------------------------------------------------------------------------------------------- */ 347 348 /** 349 * Changes the capacity of the given `ZyanBitset` instance. 350 * 351 * @param bitset A pointer to the `ZyanBitset` instance. 352 * @param count The new capacity (number of bits). 353 * 354 * @return A zyan status code. 355 */ 356 ZYCORE_EXPORT ZyanStatus ZyanBitsetReserve(ZyanBitset* bitset, ZyanUSize count); 357 358 /** 359 * Shrinks the capacity of the given bitset to match it's size. 360 * 361 * @param bitset A pointer to the `ZyanBitset` instance. 362 * 363 * @return A zyan status code. 364 */ 365 ZYCORE_EXPORT ZyanStatus ZyanBitsetShrinkToFit(ZyanBitset* bitset); 366 367 /* ---------------------------------------------------------------------------------------------- */ 368 /* Information */ 369 /* ---------------------------------------------------------------------------------------------- */ 370 371 /** 372 * Returns the current size of the bitset in bits. 373 * 374 * @param bitset A pointer to the `ZyanBitset` instance. 375 * @param size Receives the size of the bitset in bits. 376 * 377 * @return A zyan status code. 378 */ 379 ZYCORE_EXPORT ZyanStatus ZyanBitsetGetSize(const ZyanBitset* bitset, ZyanUSize* size); 380 381 /** 382 * Returns the current capacity of the bitset in bits. 383 * 384 * @param bitset A pointer to the `ZyanBitset` instance. 385 * @param capacity Receives the size of the bitset in bits. 386 * 387 * @return A zyan status code. 388 */ 389 ZYCORE_EXPORT ZyanStatus ZyanBitsetGetCapacity(const ZyanBitset* bitset, ZyanUSize* capacity); 390 391 /** 392 * Returns the current size of the bitset in bytes. 393 * 394 * @param bitset A pointer to the `ZyanBitset` instance. 395 * @param size Receives the size of the bitset in bytes. 396 * 397 * @return A zyan status code. 398 */ 399 ZYCORE_EXPORT ZyanStatus ZyanBitsetGetSizeBytes(const ZyanBitset* bitset, ZyanUSize* size); 400 401 /** 402 * Returns the current capacity of the bitset in bytes. 403 * 404 * @param bitset A pointer to the `ZyanBitset` instance. 405 * @param capacity Receives the size of the bitset in bytes. 406 * 407 * @return A zyan status code. 408 */ 409 ZYCORE_EXPORT ZyanStatus ZyanBitsetGetCapacityBytes(const ZyanBitset* bitset, ZyanUSize* capacity); 410 411 /* ---------------------------------------------------------------------------------------------- */ 412 413 /** 414 * Returns the amount of bits set in the given bitset. 415 * 416 * @param bitset A pointer to the `ZyanBitset` instance. 417 * @param count Receives the amount of bits set in the given bitset. 418 * 419 * @return A zyan status code. 420 */ 421 ZYCORE_EXPORT ZyanStatus ZyanBitsetCount(const ZyanBitset* bitset, ZyanUSize* count); 422 423 /** 424 * Checks, if all bits of the given bitset are set. 425 * 426 * @param bitset A pointer to the `ZyanBitset` instance. 427 * 428 * @return `ZYAN_STATUS_TRUE`, if all bits are set, `ZYAN_STATUS_FALSE`, if not. Another zyan 429 * status code, if an error occurred. 430 */ 431 ZYCORE_EXPORT ZyanStatus ZyanBitsetAll(const ZyanBitset* bitset); 432 433 /** 434 * Checks, if at least one bit of the given bitset is set. 435 * 436 * @param bitset A pointer to the `ZyanBitset` instance. 437 * 438 * @return `ZYAN_STATUS_TRUE`, if at least one bit is set, `ZYAN_STATUS_FALSE`, if not. Another 439 * zyan status code, if an error occurred. 440 */ 441 ZYCORE_EXPORT ZyanStatus ZyanBitsetAny(const ZyanBitset* bitset); 442 443 /** 444 * Checks, if none bits of the given bitset are set. 445 * 446 * @param bitset A pointer to the `ZyanBitset` instance. 447 * 448 * @return `ZYAN_STATUS_TRUE`, if none bits are set, `ZYAN_STATUS_FALSE`, if not. Another zyan 449 * status code, if an error occurred. 450 */ 451 ZYCORE_EXPORT ZyanStatus ZyanBitsetNone(const ZyanBitset* bitset); 452 453 ///* ---------------------------------------------------------------------------------------------- */ 454 // 455 ///** 456 // * Returns a 32-bit unsigned integer representation of the data. 457 // * 458 // * @param bitset A pointer to the `ZyanBitset` instance. 459 // * @param value Receives the 32-bit unsigned integer representation of the data. 460 // * 461 // * @return A zyan status code. 462 // */ 463 //ZYCORE_EXPORT ZyanStatus ZyanBitsetToU32(const ZyanBitset* bitset, ZyanU32* value); 464 // 465 ///** 466 // * Returns a 64-bit unsigned integer representation of the data. 467 // * 468 // * @param bitset A pointer to the `ZyanBitset` instance. 469 // * @param value Receives the 64-bit unsigned integer representation of the data. 470 // * 471 // * @return A zyan status code. 472 // */ 473 //ZYCORE_EXPORT ZyanStatus ZyanBitsetToU64(const ZyanBitset* bitset, ZyanU64* value); 474 475 /* ---------------------------------------------------------------------------------------------- */ 476 477 /* ============================================================================================== */ 478 479 #ifdef __cplusplus 480 } 481 #endif 482 483 #endif /* ZYCORE_BITSET_H */ 484