Commit: 8fd2b79ca190946fe95d915d19abbe9ddac895e9 Author: Aras Pranckevicius Date: Fri Jul 15 10:20:04 2022 +0300 Branches: master https://developer.blender.org/rB8fd2b79ca190946fe95d915d19abbe9ddac895e9
BLI_bitmap: ability to declare by-value, and function to find lowest unset bit In preparation for a larger change (D14162), some BLI_bitmap functionality that could be submitted separately: - Ability to declare a fixed size bitmap by-value, without extra memory allocation: BLI_BITMAP_DECLARE - Function to find the index of lowest unset bit: BLI_bitmap_find_first_unset - Test coverage of the above. Reviewed By: Campbell Barton, Bastien Montagne Differential Revision: https://developer.blender.org/D15454 =================================================================== M source/blender/blenlib/BLI_bitmap.h M source/blender/blenlib/CMakeLists.txt M source/blender/blenlib/intern/bitmap.c A source/blender/blenlib/tests/BLI_bitmap_test.cc =================================================================== diff --git a/source/blender/blenlib/BLI_bitmap.h b/source/blender/blenlib/BLI_bitmap.h index 19d8525311c..26dc6c7ffc9 100644 --- a/source/blender/blenlib/BLI_bitmap.h +++ b/source/blender/blenlib/BLI_bitmap.h @@ -53,6 +53,11 @@ typedef unsigned int BLI_bitmap; (CHECK_TYPE_INLINE(_mem, MemArena *), \ ((BLI_bitmap *)BLI_memarena_calloc(_mem, BLI_BITMAP_SIZE(_num)))) +/** + * Declares a bitmap as a variable. + */ +#define BLI_BITMAP_DECLARE(_name, _num) BLI_bitmap _name[_BITMAP_NUM_BLOCKS(_num)] = {} + /** * Get the value of a single bit at '_index'. */ @@ -137,6 +142,12 @@ void BLI_bitmap_and_all(BLI_bitmap *dst, const BLI_bitmap *src, size_t bits); */ void BLI_bitmap_or_all(BLI_bitmap *dst, const BLI_bitmap *src, size_t bits); +/** + * Find index of the lowest unset bit. + * Returns -1 if all the bits are set. + */ +int BLI_bitmap_find_first_unset(const BLI_bitmap *bitmap, size_t bits); + #ifdef __cplusplus } #endif diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 95b4987596e..d39a586206f 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -424,6 +424,7 @@ if(WITH_GTESTS) tests/BLI_array_store_test.cc tests/BLI_array_test.cc tests/BLI_array_utils_test.cc + tests/BLI_bitmap_test.cc tests/BLI_bounds_test.cc tests/BLI_color_test.cc tests/BLI_cpp_type_test.cc diff --git a/source/blender/blenlib/intern/bitmap.c b/source/blender/blenlib/intern/bitmap.c index 7fcbc31c066..2cc2fbc3e2f 100644 --- a/source/blender/blenlib/intern/bitmap.c +++ b/source/blender/blenlib/intern/bitmap.c @@ -11,6 +11,7 @@ #include <string.h> #include "BLI_bitmap.h" +#include "BLI_math_bits.h" #include "BLI_utildefines.h" void BLI_bitmap_set_all(BLI_bitmap *bitmap, bool set, size_t bits) @@ -46,3 +47,22 @@ void BLI_bitmap_or_all(BLI_bitmap *dst, const BLI_bitmap *src, size_t bits) dst[i] |= src[i]; } } + +int BLI_bitmap_find_first_unset(const BLI_bitmap *bitmap, const size_t bits) +{ + const size_t blocks_num = _BITMAP_NUM_BLOCKS(bits); + int result = -1; + /* Skip over completely set blocks. */ + int index = 0; + while (index < blocks_num && bitmap[index] == ~0u) { + index++; + } + if (index < blocks_num) { + /* Found a partially used block: find the lowest unused bit. */ + const uint m = ~bitmap[index]; + BLI_assert(m != 0); + const uint bit_index = bitscan_forward_uint(m); + result = bit_index + (index << _BITMAP_POWER); + } + return result; +} diff --git a/source/blender/blenlib/tests/BLI_bitmap_test.cc b/source/blender/blenlib/tests/BLI_bitmap_test.cc new file mode 100644 index 00000000000..fb9e03e3136 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_bitmap_test.cc @@ -0,0 +1,46 @@ +/* SPDX-License-Identifier: Apache-2.0 */ + +#include "BLI_bitmap.h" +#include "testing/testing.h" + +namespace blender::tests { + +TEST(bitmap, empty_is_all_unset) +{ + BLI_BITMAP_DECLARE(bitmap, 10); + for (int i = 0; i < 10; ++i) { + EXPECT_FALSE(BLI_BITMAP_TEST_BOOL(bitmap, i)); + } +} + +TEST(bitmap, find_first_unset_empty) +{ + BLI_BITMAP_DECLARE(bitmap, 10); + EXPECT_EQ(0, BLI_bitmap_find_first_unset(bitmap, 10)); +} + +TEST(bitmap, find_first_unset_full) +{ + BLI_BITMAP_DECLARE(bitmap, 10); + BLI_bitmap_flip_all(bitmap, 10); + EXPECT_EQ(-1, BLI_bitmap_find_first_unset(bitmap, 10)); +} + +TEST(bitmap, find_first_unset_middle) +{ + BLI_BITMAP_DECLARE(bitmap, 100); + BLI_bitmap_flip_all(bitmap, 100); + /* Turn some bits off */ + BLI_BITMAP_DISABLE(bitmap, 53); + BLI_BITMAP_DISABLE(bitmap, 81); + BLI_BITMAP_DISABLE(bitmap, 85); + BLI_BITMAP_DISABLE(bitmap, 86); + + /* Find lowest unset bit, and set it. */ + EXPECT_EQ(53, BLI_bitmap_find_first_unset(bitmap, 100)); + BLI_BITMAP_ENABLE(bitmap, 53); + /* Now should find the next lowest bit. */ + EXPECT_EQ(81, BLI_bitmap_find_first_unset(bitmap, 100)); +} + +} // namespace blender::tests _______________________________________________ Bf-blender-cvs mailing list Bf-blender-cvs@blender.org List details, subscription details or unsubscribe: https://lists.blender.org/mailman/listinfo/bf-blender-cvs
