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 */ _______________________________________________ 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