From a3762299ba5416ae2f85df2fb27b262d088a1e06 Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Thu, 23 Mar 2023 22:29:05 +0100 Subject: src/rtree: store free nodes as linked list --- src/RTree.cpp | 63 ++++++++++++++++++++++++++++++++++++----------------------- src/RTree.h | 31 +++++++++++++++++++++++++++-- src/RTree.hpp | 18 ++++------------- 3 files changed, 72 insertions(+), 40 deletions(-) diff --git a/src/RTree.cpp b/src/RTree.cpp index bee4641c..40343e31 100644 --- a/src/RTree.cpp +++ b/src/RTree.cpp @@ -11,53 +11,68 @@ namespace floormat::detail { -template rtree_pool::rtree_pool() -{ - free_list.reserve(128); -} +#ifdef RTREE_POOL_DEBUG +static size_t fresh_counter, reuse_counter, dtor_counter; // NOLINT +#endif + +template rtree_pool::rtree_pool() noexcept = default; -template rtree_pool::~rtree_pool() +template +rtree_pool::~rtree_pool() { - for (auto* ptr : free_list) - ::operator delete(ptr); - free_list.clear(); - free_list.shrink_to_fit(); +#ifdef RTREE_POOL_DEBUG + auto last = dtor_counter; +#endif + while (free_list) + { +#ifdef RTREE_POOL_DEBUG + ++dtor_counter; +#endif + auto* p = free_list; + free_list = free_list->next; + p->data.~T(); + delete p; + } +#ifdef RTREE_POOL_DEBUG + if (dtor_counter != last) { Debug{} << "rtree-pool: dtor" << dtor_counter; std::fflush(stdout); } +#endif } template T* rtree_pool::construct() { - if (free_list.empty()) + if (!free_list) { #ifdef RTREE_POOL_DEBUG - static unsigned i = 0; Debug{} << "rtree-pool: fresh"_s << ++i; std::fflush(stdout); + Debug{} << "rtree-pool: fresh"_s << ++fresh_counter; std::fflush(stdout); #endif - return new T; + auto* ptr = new node_u; + auto* ret = new(&ptr->data) T; + return ret; } else { - auto* ret = free_list.back(); - free_list.pop_back(); - new (ret) T(); + auto* ret = free_list; + free_list = free_list->next; + new (&ret->data) T(); #ifdef RTREE_POOL_DEBUG - static unsigned i = 0; Debug{} << "rtree-pool: reused"_s << ++i; std::fflush(stdout); + Debug{} << "rtree-pool: reused"_s << ++reuse_counter; std::fflush(stdout); #endif - return ret; + return &ret->data; } } template void rtree_pool::free(T* ptr) { ptr->~T(); - free_list.push_back(ptr); + node_p p = {.ptr = ptr }; + node_u* n = p.data_ptr; + n->next = free_list; + free_list = n; } using my_rtree = RTree; - -template<> std::vector rtree_pool::free_list = {}; // NOLINT -template<> std::vector rtree_pool::free_list = {}; // NOLINT - -template struct floormat::detail::rtree_pool; -template struct floormat::detail::rtree_pool; +template struct rtree_pool; +template struct rtree_pool; } // namespace floormat::detail diff --git a/src/RTree.h b/src/RTree.h index 1a30a735..3ceb64ac 100644 --- a/src/RTree.h +++ b/src/RTree.h @@ -22,6 +22,28 @@ namespace floormat::detail { template struct rtree_pool; } +template struct floormat::detail::rtree_pool final +{ + rtree_pool() noexcept; + rtree_pool(const rtree_pool&) = delete; + rtree_pool& operator=(const rtree_pool&) = delete; + ~rtree_pool(); + T* construct(); + void free(T* pool); + + union node_u { + union { T data; }; + node_u* next; + }; + union node_p { + T* ptr; + node_u* data_ptr; + }; + +private: + node_u* free_list = nullptr; +}; + #ifdef RTREE_STDIO // Fwd decl class RTFileStream; // File I/O helper class, look below for implementation and notes. @@ -45,7 +67,7 @@ class RTFileStream; // File I/O helper class, look below for implementation and /// template -class RTree +class RTree final { public: @@ -65,7 +87,7 @@ public: RTree(); RTree(const RTree& other); - virtual ~RTree() noexcept; + ~RTree() noexcept; RTree& operator=(const RTree&); /// Insert entry @@ -212,6 +234,9 @@ public: Node* m_node; ///< Node }; + floormat::detail::rtree_pool node_pool; + floormat::detail::rtree_pool list_node_pool; + protected: /// Variables for finding a split partition struct PartitionVars @@ -278,6 +303,8 @@ public: }; extern template class RTree; +extern template struct floormat::detail::rtree_pool::Node>; +extern template struct floormat::detail::rtree_pool::ListNode>; //#undef RTREE_TEMPLATE //#undef RTREE_QUAL diff --git a/src/RTree.hpp b/src/RTree.hpp index 45cbb378..046c5e1d 100644 --- a/src/RTree.hpp +++ b/src/RTree.hpp @@ -4,7 +4,6 @@ #include #include -#include #include #include @@ -33,16 +32,7 @@ #endif //Max namespace floormat::detail { -template struct rtree_pool final -{ - rtree_pool(); - ~rtree_pool(); - static T* construct(); - static void free(T* pool); -private: - static std::vector free_list; // NOLINT -}; #ifndef RTREE_NO_EXTERN_TEMPLATE_POOL extern template struct rtree_pool::Node>; @@ -560,7 +550,7 @@ typename RTREE_QUAL::Node* RTREE_QUAL::AllocNode() #ifdef RTREE_DONT_USE_MEMPOOLS newNode = new Node; #else // RTREE_DONT_USE_MEMPOOLS - newNode = floormat::detail::rtree_pool::construct(); + newNode = node_pool.construct(); #endif // RTREE_DONT_USE_MEMPOOLS InitNode(newNode); return newNode; @@ -575,7 +565,7 @@ void RTREE_QUAL::FreeNode(Node* a_node) #ifdef RTREE_DONT_USE_MEMPOOLS delete a_node; #else // RTREE_DONT_USE_MEMPOOLS - floormat::detail::rtree_pool::free(a_node); + node_pool.free(a_node); #endif // RTREE_DONT_USE_MEMPOOLS } @@ -588,7 +578,7 @@ typename RTREE_QUAL::ListNode* RTREE_QUAL::AllocListNode() #ifdef RTREE_DONT_USE_MEMPOOLS return new ListNode; #else // RTREE_DONT_USE_MEMPOOLS - return floormat::detail::rtree_pool::construct(); + return list_node_pool.construct(); #endif // RTREE_DONT_USE_MEMPOOLS } @@ -599,7 +589,7 @@ void RTREE_QUAL::FreeListNode(ListNode* a_listNode) #ifdef RTREE_DONT_USE_MEMPOOLS delete a_listNode; #else // RTREE_DONT_USE_MEMPOOLS - floormat::detail::rtree_pool::free(a_listNode); + list_node_pool.free(a_listNode); #endif // RTREE_DONT_USE_MEMPOOLS } -- cgit v1.2.3