From b15e1a35011629c3b31edd10c1d10b8d7fafcb2c Mon Sep 17 00:00:00 2001 From: Lioncash Date: Tue, 12 Jan 2021 02:47:36 -0500 Subject: common/tree: Convert defines over to templates Reworks the tree header to operate off of templates as opposed to a series of defines. This allows all tree facilities to obey namespacing rules, and also allows this code to be used within modules once compiler support is in place. This also gets rid to use a macro to define functions and structs for necessary data types. With templates, these will be generated when they're actually used, eliminating the need for the separate declaration. --- src/common/intrusive_red_black_tree.h | 99 +++++++++++++---------------------- 1 file changed, 37 insertions(+), 62 deletions(-) (limited to 'src/common/intrusive_red_black_tree.h') diff --git a/src/common/intrusive_red_black_tree.h b/src/common/intrusive_red_black_tree.h index fb55de94e..c0bbcd457 100644 --- a/src/common/intrusive_red_black_tree.h +++ b/src/common/intrusive_red_black_tree.h @@ -16,17 +16,30 @@ class IntrusiveRedBlackTreeImpl; } struct IntrusiveRedBlackTreeNode { +public: + using EntryType = RBEntry; + + constexpr IntrusiveRedBlackTreeNode() = default; + + void SetEntry(const EntryType& new_entry) { + entry = new_entry; + } + + [[nodiscard]] EntryType& GetEntry() { + return entry; + } + + [[nodiscard]] const EntryType& GetEntry() const { + return entry; + } private: - RB_ENTRY(IntrusiveRedBlackTreeNode) entry{}; + EntryType entry{}; friend class impl::IntrusiveRedBlackTreeImpl; template friend class IntrusiveRedBlackTree; - -public: - constexpr IntrusiveRedBlackTreeNode() = default; }; template @@ -35,17 +48,12 @@ class IntrusiveRedBlackTree; namespace impl { class IntrusiveRedBlackTreeImpl { - private: template friend class ::Common::IntrusiveRedBlackTree; -private: - RB_HEAD(IntrusiveRedBlackTreeRoot, IntrusiveRedBlackTreeNode); - using RootType = IntrusiveRedBlackTreeRoot; - -private: - IntrusiveRedBlackTreeRoot root; + using RootType = RBHead; + RootType root; public: template @@ -121,57 +129,45 @@ public: } }; -protected: - // Generate static implementations for non-comparison operations for IntrusiveRedBlackTreeRoot. - RB_GENERATE_WITHOUT_COMPARE_STATIC(IntrusiveRedBlackTreeRoot, IntrusiveRedBlackTreeNode, entry); - private: // Define accessors using RB_* functions. - constexpr void InitializeImpl() { - RB_INIT(&this->root); - } - bool EmptyImpl() const { - return RB_EMPTY(&this->root); + return root.IsEmpty(); } IntrusiveRedBlackTreeNode* GetMinImpl() const { - return RB_MIN(IntrusiveRedBlackTreeRoot, - const_cast(&this->root)); + return RB_MIN(const_cast(&root)); } IntrusiveRedBlackTreeNode* GetMaxImpl() const { - return RB_MAX(IntrusiveRedBlackTreeRoot, - const_cast(&this->root)); + return RB_MAX(const_cast(&root)); } IntrusiveRedBlackTreeNode* RemoveImpl(IntrusiveRedBlackTreeNode* node) { - return RB_REMOVE(IntrusiveRedBlackTreeRoot, &this->root, node); + return RB_REMOVE(&root, node); } public: static IntrusiveRedBlackTreeNode* GetNext(IntrusiveRedBlackTreeNode* node) { - return RB_NEXT(IntrusiveRedBlackTreeRoot, nullptr, node); + return RB_NEXT(node); } static IntrusiveRedBlackTreeNode* GetPrev(IntrusiveRedBlackTreeNode* node) { - return RB_PREV(IntrusiveRedBlackTreeRoot, nullptr, node); + return RB_PREV(node); } - static IntrusiveRedBlackTreeNode const* GetNext(const IntrusiveRedBlackTreeNode* node) { + static const IntrusiveRedBlackTreeNode* GetNext(const IntrusiveRedBlackTreeNode* node) { return static_cast( GetNext(const_cast(node))); } - static IntrusiveRedBlackTreeNode const* GetPrev(const IntrusiveRedBlackTreeNode* node) { + static const IntrusiveRedBlackTreeNode* GetPrev(const IntrusiveRedBlackTreeNode* node) { return static_cast( GetPrev(const_cast(node))); } public: - constexpr IntrusiveRedBlackTreeImpl() : root() { - this->InitializeImpl(); - } + constexpr IntrusiveRedBlackTreeImpl() {} // Iterator accessors. iterator begin() { @@ -269,8 +265,6 @@ private: ImplType impl{}; public: - struct IntrusiveRedBlackTreeRootWithCompare : ImplType::IntrusiveRedBlackTreeRoot {}; - template class Iterator; @@ -362,11 +356,6 @@ public: } }; -private: - // Generate static implementations for comparison operations for IntrusiveRedBlackTreeRoot. - RB_GENERATE_WITH_COMPARE_STATIC(IntrusiveRedBlackTreeRootWithCompare, IntrusiveRedBlackTreeNode, - entry, CompareImpl, LightCompareImpl); - private: static int CompareImpl(const IntrusiveRedBlackTreeNode* lhs, const IntrusiveRedBlackTreeNode* rhs) { @@ -379,41 +368,27 @@ private: // Define accessors using RB_* functions. IntrusiveRedBlackTreeNode* InsertImpl(IntrusiveRedBlackTreeNode* node) { - return RB_INSERT(IntrusiveRedBlackTreeRootWithCompare, - static_cast(&this->impl.root), - node); + return RB_INSERT(&impl.root, node, CompareImpl); } IntrusiveRedBlackTreeNode* FindImpl(const IntrusiveRedBlackTreeNode* node) const { - return RB_FIND( - IntrusiveRedBlackTreeRootWithCompare, - const_cast( - static_cast(&this->impl.root)), - const_cast(node)); + return RB_FIND(const_cast(&impl.root), + const_cast(node), CompareImpl); } IntrusiveRedBlackTreeNode* NFindImpl(const IntrusiveRedBlackTreeNode* node) const { - return RB_NFIND( - IntrusiveRedBlackTreeRootWithCompare, - const_cast( - static_cast(&this->impl.root)), - const_cast(node)); + return RB_NFIND(const_cast(&impl.root), + const_cast(node), CompareImpl); } IntrusiveRedBlackTreeNode* FindLightImpl(const_light_pointer lelm) const { - return RB_FIND_LIGHT( - IntrusiveRedBlackTreeRootWithCompare, - const_cast( - static_cast(&this->impl.root)), - static_cast(lelm)); + return RB_FIND_LIGHT(const_cast(&impl.root), + static_cast(lelm), LightCompareImpl); } IntrusiveRedBlackTreeNode* NFindLightImpl(const_light_pointer lelm) const { - return RB_NFIND_LIGHT( - IntrusiveRedBlackTreeRootWithCompare, - const_cast( - static_cast(&this->impl.root)), - static_cast(lelm)); + return RB_NFIND_LIGHT(const_cast(&impl.root), + static_cast(lelm), LightCompareImpl); } public: -- cgit v1.2.3