From 8fd2b79ca190946fe95d915d19abbe9ddac895e9 Mon Sep 17 00:00:00 2001
From: Aras Pranckevicius <aras@nesnausk.org>
Date: Fri, 15 Jul 2022 10:20:04 +0300
Subject: 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
---
 source/blender/blenlib/BLI_bitmap.h             | 11 ++++++
 source/blender/blenlib/CMakeLists.txt           |  1 +
 source/blender/blenlib/intern/bitmap.c          | 20 +++++++++++
 source/blender/blenlib/tests/BLI_bitmap_test.cc | 46 +++++++++++++++++++++++++
 4 files changed, 78 insertions(+)
 create mode 100644 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
-- 
cgit v1.2.3