summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--editor/tests/path-test.cpp1
-rw-r--r--src/search-astar.cpp3
-rw-r--r--src/search-result.cpp79
-rw-r--r--src/search-result.hpp2
-rw-r--r--test/search-result.cpp77
5 files changed, 113 insertions, 49 deletions
diff --git a/editor/tests/path-test.cpp b/editor/tests/path-test.cpp
index 0b836932..4558fedd 100644
--- a/editor/tests/path-test.cpp
+++ b/editor/tests/path-test.cpp
@@ -157,6 +157,7 @@ void path_test::update_pre(app& a, const Ns&)
auto& w = M.world();
auto& astar = M.astar();
+ result.res = {}; // return back to the pool to preserve cpu cache
auto res = astar.Dijkstra(w, pending.from, pending.to, pending.own_id, pending.max_dist, pending.own_size, 1);
has_result = !!res;
result = {
diff --git a/src/search-astar.cpp b/src/search-astar.cpp
index e86e6bee..77239669 100644
--- a/src/search-astar.cpp
+++ b/src/search-astar.cpp
@@ -135,6 +135,9 @@ void set_result_from_idx(path_search_result& result,
for (auto i = idx; i != (uint32_t)-1; i = nodes[i].prev)
len++;
+ if (!len) [[unlikely]]
+ return;
+
fm_debug_assert(idx != (uint32_t)-1);
arrayResize(temp_nodes, 0);
arrayReserve(temp_nodes, len+1);
diff --git a/src/search-result.cpp b/src/search-result.cpp
index ed9c5194..1afd09df 100644
--- a/src/search-result.cpp
+++ b/src/search-result.cpp
@@ -11,27 +11,11 @@ namespace floormat {
Pointer<path_search_result::node> path_search_result::_pool; // NOLINT
-path_search_result::path_search_result()
-{
- constexpr auto min_length = TILE_MAX_DIM*2;
- if (_pool)
- {
- auto ptr = move(_pool);
- fm_debug_assert(ptr->vec.empty());
- auto next = move(ptr->_next);
- _node = move(ptr);
- _pool = move(next);
- }
- else
- {
- _node = Pointer<node>{InPlaceInit};
- _node->vec.reserve(min_length);
- }
-}
+path_search_result::path_search_result() = default;
path_search_result::~path_search_result() noexcept
{
- if (_node && _node->vec.capacity() > 0) [[likely]]
+ if (_node && _node->vec.capacity() > 0)
{
_node->vec.clear();
_node->_next = move(_pool);
@@ -52,7 +36,7 @@ path_search_result& path_search_result::operator=(const path_search_result& x) n
{
fm_debug_assert(_node);
fm_debug_assert(!_node->_next);
- if (&x != this)
+ if (&x != this) [[likely]]
_node->vec = x._node->vec;
_cost = x._cost;
return *this;
@@ -79,11 +63,59 @@ path_search_result& path_search_result::operator=(path_search_result&& other) no
return *this;
}
-size_t path_search_result::size() const { return _node->vec.size(); }
-bool path_search_result::empty() const { return _node->vec.empty(); }
+void path_search_result::allocate_node()
+{
+ constexpr auto min_length = TILE_MAX_DIM*2;
+
+ if (_node)
+ return;
+
+ if (_pool)
+ {
+ auto ptr = move(_pool);
+ fm_debug_assert(ptr->vec.empty());
+ auto next = move(ptr->_next);
+ _node = move(ptr);
+ _pool = move(next);
+ }
+ else
+ {
+ _node = Pointer<node>{InPlaceInit};
+ _node->vec.reserve(min_length);
+ }
+}
+
+ArrayView<const point> path_search_result::path() const
+{
+ if (!_node)
+ return {};
+ return { _node->vec.data(), _node->vec.size() };
+}
+
+vector_wrapper<point, vector_wrapper_repr::ref> path_search_result::raw_path()
+{
+ if (!_node)
+ allocate_node();
+ return {_node->vec};
+}
+
+size_t path_search_result::size() const
+{
+ return _node ? _node->vec.size() : 0;
+}
+
+bool path_search_result::empty() const
+{
+ return !_node || _node->vec.empty();
+}
+
+path_search_result::operator bool() const
+{
+ return _node && !_node->vec.empty();
+}
+
path_search_result::node::node() noexcept = default;
float path_search_result::time() const { return _time; }
-
uint32_t path_search_result::cost() const { return _cost; }
void path_search_result::set_cost(uint32_t value) { _cost = value; }
void path_search_result::set_time(float time) { _time = time; }
@@ -91,8 +123,5 @@ bool path_search_result::is_found() const { return _found; }
void path_search_result::set_found(bool value) { _found = value; }
uint32_t path_search_result::distance() const { return _distance; }
void path_search_result::set_distance(uint32_t dist) { _distance = dist; }
-path_search_result::operator bool() const { return !_node->vec.empty(); }
-ArrayView<const point> path_search_result::path() const { fm_assert(_node); return {_node->vec.data(), _node->vec.size()}; }
-vector_wrapper<point, vector_wrapper_repr::ref> path_search_result::raw_path() { fm_assert(_node); return {_node->vec}; }
} // namespace floormat
diff --git a/src/search-result.hpp b/src/search-result.hpp
index aa27c374..afbca8af 100644
--- a/src/search-result.hpp
+++ b/src/search-result.hpp
@@ -37,6 +37,8 @@ struct path_search_result final
~path_search_result() noexcept;
private:
+ void allocate_node();
+
Pointer<node> _node;
float _time = 0;
uint32_t _cost = 0, _distance = (uint32_t)-1;
diff --git a/test/search-result.cpp b/test/search-result.cpp
index 600eec69..2d5532c0 100644
--- a/test/search-result.cpp
+++ b/test/search-result.cpp
@@ -1,5 +1,6 @@
#include "app.hpp"
#include "compat/assert.hpp"
+#include "compat/vector-wrapper.hpp"
#include "src/search-result.hpp"
#include "src/search-node.hpp"
@@ -15,34 +16,62 @@ struct path_search_result_pool_access<Test_PathPool> final
{
static const Pointer<node>& get_node(const path_search_result& p) { return p._node; }
static const auto& get_pool() { return path_search_result::_pool; }
+ static size_t pool_size();
};
+size_t path_search_result_pool_access<Test_PathPool>::pool_size()
+{
+ size_t ret = 0;
+ for (const auto* pool = get_pool().get(); pool; pool = pool->_next.get())
+ ret++;
+ return ret;
+}
+
void test_app::test_astar_pool()
{
- auto& pool = psrpa::get_pool();
- fm_assert(!pool);
- {
- auto a = path_search_result{};
- fm_assert(!pool);
- }
- fm_assert(pool);
- auto* pool2 = pool.get();
- {
- auto b = path_search_result{};
- fm_assert(psrpa::get_node(b).get() == pool2);
- auto c = path_search_result{};
- fm_assert(!pool);
- fm_assert(psrpa::get_node(c).get() != pool2);
- fm_assert(psrpa::get_node(b).get() == pool2);
- fm_assert(!psrpa::get_node(b)->_next);
- fm_assert(!psrpa::get_node(c)->_next);
- }
- {
- auto count = 0uz;
- for (const auto* ptr = pool.get(); ptr; ptr = ptr->_next.get())
- count++;
- fm_assert(count == 2);
- }
+ const auto& pool = psrpa::get_pool();
+ fm_assert(psrpa::pool_size() == 0);
+
+ auto a = path_search_result{};
+ fm_assert(psrpa::pool_size() == 0);
+ fm_assert(!psrpa::get_node(a));
+
+ a = {};
+ fm_assert(!psrpa::get_node(a));
+ fm_assert(psrpa::pool_size() == 0);
+
+ a = path_search_result{};
+ (void)a.raw_path();
+ fm_assert(psrpa::get_node(a));
+ fm_assert(psrpa::pool_size() == 0);
+ const void* const first = psrpa::get_node(a).get();
+ fm_assert(first);
+
+ a = {};
+ fm_assert(!psrpa::get_node(a));
+ fm_assert(psrpa::pool_size() == 1);
+ fm_assert(pool.get() == first);
+
+ a = path_search_result{};
+ (void)a.raw_path();
+ fm_assert(psrpa::get_node(a));
+ fm_assert(psrpa::get_node(a).get() == first);
+ fm_assert(psrpa::pool_size() == 0);
+
+ auto b = path_search_result{};
+ (void)b.raw_path();
+
+ fm_assert(psrpa::get_node(a));
+ fm_assert(psrpa::get_node(b));
+ fm_assert(psrpa::pool_size() == 0);
+
+ b = {};
+ a = {};
+
+ fm_assert(!psrpa::get_node(a));
+ fm_assert(!psrpa::get_node(b));
+ fm_assert(psrpa::pool_size() == 2);
+ fm_assert(pool.get() == first);
}
} // namespace floormat
generated by cgit v1.2.3 (git 2.39.1) at 2025-02-25 03:49:22 +0000