[Bf-blender-cvs] [20497c448c3] soc-2021-adaptive-cloth: bli: generational_arena: insert()

[ishbosamiya]

Commit: 20497c448c38c25682dd625ee287624ab497a27a
Author: ishbosamiya
Date:   Tue Jun 15 21:41:04 2021 +0530
Branches: soc-2021-adaptive-cloth
https://developer.blender.org/rB20497c448c38c25682dd625ee287624ab497a27a

bli: generational_arena: insert()

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

M	source/blender/blenlib/BLI_generational_arena.hh

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

diff --git a/source/blender/blenlib/BLI_generational_arena.hh b/source/blender/blenlib/BLI_generational_arena.hh
index 65851467c5b..30a147ba157 100644
--- a/source/blender/blenlib/BLI_generational_arena.hh
+++ b/source/blender/blenlib/BLI_generational_arena.hh
@@ -52,6 +52,7 @@
  */
 /* TODO(ish): need to complete documentation */
 
+#include <limits>
 #include <optional>
 #include <tuple>
 #include <variant>
@@ -60,6 +61,32 @@
 
 namespace blender::generational_arena {
 
+namespace extra {
+template<typename... Ts> struct overloaded : Ts... {
+  using Ts::operator()...;
+};
+template<typename... Ts> overloaded(Ts...) -> overloaded<Ts...>;
+} /* namespace extra */
+
+class Index {
+  using usize = uint64_t;
+
+  usize index;
+  usize generation;
+
+ public:
+  Index(usize index, usize generation)
+  {
+    this->index = index;
+    this->generation = generation;
+  }
+
+  std::tuple<usize, usize> get_raw() const
+  {
+    return std::make_tuple(this->index, this->generation);
+  }
+};
+
 template<
     /**
      * Type of the values stored in this vector. It has to be movable.
@@ -109,6 +136,12 @@ class Arena {
   struct EntryExist {
     T value;
     usize generation;
+
+    EntryExist(T value, usize generation)
+    {
+      this->value = value;
+      this->generation = generation;
+    }
   };
 
   blender::Vector<Entry> data;
@@ -158,6 +191,50 @@ class Arena {
     this->next_free_head = start;
   }
 
+  /* TODO(ish): add optimization by moving `value`, can be done by
+   * returning value if `try_insert()` fails */
+  std::optional<Index> try_insert(T value)
+  {
+    if (this->next_free_head) {
+      auto loc = this->next_free_head;
+      std::visit(extra::overloaded{[this, value](EntryNoExist &data) {
+                                     this->next_free_head = data.next_free;
+                                     data = EntryExist(value, this->generation);
+                                   },
+                                   [](EntryExist &data) {
+                                     /* The linked list created to
+                                      * know where to insert next is
+                                      * corrupted.
+                                      * `this->next_free_head` is corrupted */
+                                     BLI_assert_unreachable();
+                                   }},
+                 this->data[loc]);
+      this->length += 1;
+      return Index(loc, this->generation);
+    }
+    return std::nullopt;
+  }
+
+  Index insert(T value)
+  {
+    if (auto index = this->try_insert(value)) {
+      return index;
+    }
+    else {
+      /* couldn't insert the value within reserved memory space  */
+      /* TODO(ish): might be possible that `this->data.size()` is 0,
+       * needs a special case for that */
+      this->reserve(this->data.size() * 2);
+      if (auto index = this->try_insert(value)) {
+        return index;
+      }
+      else {
+        /* now that more memory has been reserved, it shouldn't fail */
+        BLI_assert_unreachable();
+      }
+    }
+  }
+
  protected:
   /* all protected static methods */
   /* all protected non-static methods */
@@ -167,23 +244,4 @@ class Arena {
   /* all private non-static methods */
 };
 
-class Index {
-  using usize = uint64_t;
-
-  usize index;
-  usize generation;
-
- public:
-  Index(usize index, usize generation)
-  {
-    this->index = index;
-    this->generation = generation;
-  }
-
-  std::tuple<usize, usize> get_raw() const
-  {
-    return std::make_tuple(this->index, this->generation);
-  }
-};
-
 } /* namespace blender::generational_arena */