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
This commit is contained in:
parent
d8094f9212
commit
8fd2b79ca1
|
@ -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
|
||||
|
|
|
@ -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
|
||||
|
|
|
@ -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;
|
||||
}
|
||||
|
|
|
@ -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
|
Loading…
Reference in New Issue