[Bf-blender-cvs] [7f194771f79] soc-2021-adaptive-cloth: bli: generational_arena: test for ensuring next_free list is correct

[ishbosamiya]

Commit: 7f194771f790464b08cb8168da71a961e2f85ee7
Author: ishbosamiya
Date:   Wed Jun 16 19:17:34 2021 +0530
Branches: soc-2021-adaptive-cloth
https://developer.blender.org/rB7f194771f790464b08cb8168da71a961e2f85ee7

bli: generational_arena: test for ensuring next_free list is correct

===================================================================

M	source/blender/blenlib/BLI_generational_arena.hh
M	source/blender/blenlib/tests/BLI_generational_arena_test.cc

===================================================================

diff --git a/source/blender/blenlib/BLI_generational_arena.hh b/source/blender/blenlib/BLI_generational_arena.hh
index c1cdb0ce01f..95a2f962b77 100644
--- a/source/blender/blenlib/BLI_generational_arena.hh
+++ b/source/blender/blenlib/BLI_generational_arena.hh
@@ -60,6 +60,8 @@
 
 #include "BLI_vector.hh"
 
+#include "testing/testing.h"
+
 namespace blender::generational_arena {
 
 namespace extra {
@@ -384,6 +386,27 @@ class Arena {
  private:
   /* all private static methods */
   /* all private non-static methods */
+
+  FRIEND_TEST(generational_arena, GetNextFreeLocations);
+
+  blender::Vector<usize> get_next_free_locations() const
+  {
+    auto next_free = this->next_free_head;
+    blender::Vector<usize> locs;
+    locs.reserve(this->capacity() - this->size());
+
+    while (next_free) {
+      locs.append(*next_free);
+      if (auto entry = std::get_if<EntryNoExist>(&this->data[*next_free])) {
+        next_free = entry->next_free;
+      }
+      else {
+        BLI_assert_unreachable();
+      }
+    }
+
+    return locs;
+  }
 };
 
 } /* namespace blender::generational_arena */
diff --git a/source/blender/blenlib/tests/BLI_generational_arena_test.cc b/source/blender/blenlib/tests/BLI_generational_arena_test.cc
index 4e0e668385a..e677b293434 100644
--- a/source/blender/blenlib/tests/BLI_generational_arena_test.cc
+++ b/source/blender/blenlib/tests/BLI_generational_arena_test.cc
@@ -125,3 +125,73 @@ TEST(generational_arena, GetNoGenIndex)
 }
 
 } /* namespace blender::tests */
+
+namespace blender::generational_arena {
+
+TEST(generational_arena, GetNextFreeLocations)
+{
+  Arena<int> arena;
+  auto i0 = arena.insert(0);
+  auto i1 = arena.insert(1);
+  auto i2 = arena.insert(2);
+  auto i3 = arena.insert(3);
+
+  arena.remove(i0);
+  arena.remove(i1);
+  arena.remove(i2);
+  arena.remove(i3);
+
+  auto locs = arena.get_next_free_locations();
+  EXPECT_EQ(locs.size(), 4);
+  EXPECT_EQ(locs[0], 3);
+  EXPECT_EQ(locs[1], 2);
+  EXPECT_EQ(locs[2], 1);
+  EXPECT_EQ(locs[3], 0);
+
+  i0 = arena.insert(0);
+  i1 = arena.insert(1);
+  i2 = arena.insert(2);
+  i3 = arena.insert(3);
+
+  locs = arena.get_next_free_locations();
+  EXPECT_EQ(locs.size(), 0);
+
+  auto i4 = arena.insert(4);
+  arena.remove(i1);
+  arena.remove(i4);
+  locs = arena.get_next_free_locations();
+  EXPECT_EQ(locs.size(), 5);
+  EXPECT_EQ(locs[0], 4);
+  EXPECT_EQ(locs[1], 2);
+  EXPECT_EQ(locs[2], 5);
+  EXPECT_EQ(locs[3], 6);
+  EXPECT_EQ(locs[4], 7);
+
+  auto i_0 = arena.insert(10);
+  auto i_1 = arena.insert(11);
+  auto i_2 = arena.insert(12);
+  auto i_3 = arena.insert(13);
+  auto i_4 = arena.insert(14);
+
+  EXPECT_EQ(arena.size(), 8);
+  EXPECT_EQ(arena.get(i0), 0);
+  EXPECT_EQ(arena.get(i1), std::nullopt);
+  EXPECT_EQ(arena.get(i2), 2);
+  EXPECT_EQ(arena.get(i3), 3);
+  EXPECT_EQ(arena.get(i4), std::nullopt);
+  EXPECT_EQ(arena.get(i_0), 10);
+  EXPECT_EQ(arena.get(i_1), 11);
+  EXPECT_EQ(arena.get(i_2), 12);
+  EXPECT_EQ(arena.get(i_3), 13);
+  EXPECT_EQ(arena.get(i_4), 14);
+  EXPECT_EQ(arena.get_no_gen(0), 3);
+  EXPECT_EQ(arena.get_no_gen(1), 2);
+  EXPECT_EQ(arena.get_no_gen(2), 11);
+  EXPECT_EQ(arena.get_no_gen(3), 0);
+  EXPECT_EQ(arena.get_no_gen(4), 10);
+  EXPECT_EQ(arena.get_no_gen(5), 12);
+  EXPECT_EQ(arena.get_no_gen(6), 13);
+  EXPECT_EQ(arena.get_no_gen(7), 14);
+}
+
+} /* namespace blender::generational_arena */