From 197b5d19bc3de919d315633709eef24cd4b15786 Mon Sep 17 00:00:00 2001 From: Lioncash Date: Tue, 12 Jan 2021 02:32:38 -0500 Subject: common/tree: Remove unused splay tree defines Makes for less code to take care of. --- src/common/tree.h | 251 +----------------------------------------------------- 1 file changed, 2 insertions(+), 249 deletions(-) diff --git a/src/common/tree.h b/src/common/tree.h index a6b636646..4a295f894 100644 --- a/src/common/tree.h +++ b/src/common/tree.h @@ -27,33 +27,10 @@ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ -#ifndef _SYS_TREE_H_ -#define _SYS_TREE_H_ - -/* FreeBSD has a lot of defines we don't really want. */ -/* tree.h only actually uses __inline and __unused, so we'll just define those. */ - -/* #include */ - -#ifndef __inline -#define __inline inline -#endif +#pragma once /* - * This file defines data structures for different types of trees: - * splay trees and red-black trees. - * - * A splay tree is a self-organizing data structure. Every operation - * on the tree causes a splay to happen. The splay moves the requested - * node to the root of the tree and partly rebalances it. - * - * This has the benefit that request locality causes faster lookups as - * the requested nodes move to the top of the tree. On the other hand, - * every lookup causes memory writes. - * - * The Balance Theorem bounds the total access time for m operations - * and n inserts on an initially empty tree as O((m + n)lg n). The - * amortized cost for a sequence of m accesses to a splay tree is O(lg n); + * This file defines data structures for red-black trees. * * A red-black tree is a binary search tree with the node color as an * extra attribute. It fulfills a set of conditions: @@ -66,228 +43,6 @@ * The maximum height of a red-black tree is 2lg (n+1). */ -#define SPLAY_HEAD(name, type) \ - struct name { \ - struct type* sph_root; /* root of the tree */ \ - } - -#define SPLAY_INITIALIZER(root) \ - { NULL } - -#define SPLAY_INIT(root) \ - do { \ - (root)->sph_root = NULL; \ - } while (/*CONSTCOND*/ 0) - -#define SPLAY_ENTRY(type) \ - struct { \ - struct type* spe_left; /* left element */ \ - struct type* spe_right; /* right element */ \ - } - -#define SPLAY_LEFT(elm, field) (elm)->field.spe_left -#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right -#define SPLAY_ROOT(head) (head)->sph_root -#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) - -/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ -#define SPLAY_ROTATE_RIGHT(head, tmp, field) \ - do { \ - SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ - SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ - (head)->sph_root = tmp; \ - } while (/*CONSTCOND*/ 0) - -#define SPLAY_ROTATE_LEFT(head, tmp, field) \ - do { \ - SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ - SPLAY_LEFT(tmp, field) = (head)->sph_root; \ - (head)->sph_root = tmp; \ - } while (/*CONSTCOND*/ 0) - -#define SPLAY_LINKLEFT(head, tmp, field) \ - do { \ - SPLAY_LEFT(tmp, field) = (head)->sph_root; \ - tmp = (head)->sph_root; \ - (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ - } while (/*CONSTCOND*/ 0) - -#define SPLAY_LINKRIGHT(head, tmp, field) \ - do { \ - SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ - tmp = (head)->sph_root; \ - (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ - } while (/*CONSTCOND*/ 0) - -#define SPLAY_ASSEMBLE(head, node, left, right, field) \ - do { \ - SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ - SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field); \ - SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ - SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ - } while (/*CONSTCOND*/ 0) - -/* Generates prototypes and inline functions */ - -#define SPLAY_PROTOTYPE(name, type, field, cmp) \ - void name##_SPLAY(struct name*, struct type*); \ - void name##_SPLAY_MINMAX(struct name*, int); \ - struct type* name##_SPLAY_INSERT(struct name*, struct type*); \ - struct type* name##_SPLAY_REMOVE(struct name*, struct type*); \ - \ - /* Finds the node with the same key as elm */ \ - static __inline struct type* name##_SPLAY_FIND(struct name* head, struct type* elm) { \ - if (SPLAY_EMPTY(head)) \ - return (NULL); \ - name##_SPLAY(head, elm); \ - if ((cmp)(elm, (head)->sph_root) == 0) \ - return (head->sph_root); \ - return (NULL); \ - } \ - \ - static __inline struct type* name##_SPLAY_NEXT(struct name* head, struct type* elm) { \ - name##_SPLAY(head, elm); \ - if (SPLAY_RIGHT(elm, field) != NULL) { \ - elm = SPLAY_RIGHT(elm, field); \ - while (SPLAY_LEFT(elm, field) != NULL) { \ - elm = SPLAY_LEFT(elm, field); \ - } \ - } else \ - elm = NULL; \ - return (elm); \ - } \ - \ - static __inline struct type* name##_SPLAY_MIN_MAX(struct name* head, int val) { \ - name##_SPLAY_MINMAX(head, val); \ - return (SPLAY_ROOT(head)); \ - } - -/* Main splay operation. - * Moves node close to the key of elm to top - */ -#define SPLAY_GENERATE(name, type, field, cmp) \ - struct type* name##_SPLAY_INSERT(struct name* head, struct type* elm) { \ - if (SPLAY_EMPTY(head)) { \ - SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ - } else { \ - int __comp; \ - name##_SPLAY(head, elm); \ - __comp = (cmp)(elm, (head)->sph_root); \ - if (__comp < 0) { \ - SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field); \ - SPLAY_RIGHT(elm, field) = (head)->sph_root; \ - SPLAY_LEFT((head)->sph_root, field) = NULL; \ - } else if (__comp > 0) { \ - SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field); \ - SPLAY_LEFT(elm, field) = (head)->sph_root; \ - SPLAY_RIGHT((head)->sph_root, field) = NULL; \ - } else \ - return ((head)->sph_root); \ - } \ - (head)->sph_root = (elm); \ - return (NULL); \ - } \ - \ - struct type* name##_SPLAY_REMOVE(struct name* head, struct type* elm) { \ - struct type* __tmp; \ - if (SPLAY_EMPTY(head)) \ - return (NULL); \ - name##_SPLAY(head, elm); \ - if ((cmp)(elm, (head)->sph_root) == 0) { \ - if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ - (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ - } else { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ - name##_SPLAY(head, elm); \ - SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ - } \ - return (elm); \ - } \ - return (NULL); \ - } \ - \ - void name##_SPLAY(struct name* head, struct type* elm) { \ - struct type __node, *__left, *__right, *__tmp; \ - int __comp; \ - \ - SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ - __left = __right = &__node; \ - \ - while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ - if (__comp < 0) { \ - __tmp = SPLAY_LEFT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if ((cmp)(elm, __tmp) < 0) { \ - SPLAY_ROTATE_RIGHT(head, __tmp, field); \ - if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ - break; \ - } \ - SPLAY_LINKLEFT(head, __right, field); \ - } else if (__comp > 0) { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if ((cmp)(elm, __tmp) > 0) { \ - SPLAY_ROTATE_LEFT(head, __tmp, field); \ - if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ - break; \ - } \ - SPLAY_LINKRIGHT(head, __left, field); \ - } \ - } \ - SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ - } \ - \ - /* Splay with either the minimum or the maximum element \ - * Used to find minimum or maximum element in tree. \ - */ \ - void name##_SPLAY_MINMAX(struct name* head, int __comp) { \ - struct type __node, *__left, *__right, *__tmp; \ - \ - SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ - __left = __right = &__node; \ - \ - while (1) { \ - if (__comp < 0) { \ - __tmp = SPLAY_LEFT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if (__comp < 0) { \ - SPLAY_ROTATE_RIGHT(head, __tmp, field); \ - if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ - break; \ - } \ - SPLAY_LINKLEFT(head, __right, field); \ - } else if (__comp > 0) { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if (__comp > 0) { \ - SPLAY_ROTATE_LEFT(head, __tmp, field); \ - if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ - break; \ - } \ - SPLAY_LINKRIGHT(head, __left, field); \ - } \ - } \ - SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ - } - -#define SPLAY_NEGINF -1 -#define SPLAY_INF 1 - -#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) -#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) -#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) -#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) -#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) -#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) - -#define SPLAY_FOREACH(x, name, head) \ - for ((x) = SPLAY_MIN(name, head); (x) != NULL; (x) = SPLAY_NEXT(name, head, x)) - /* Macros that define a red-black tree */ #define RB_HEAD(name, type) \ struct name { \ @@ -818,5 +573,3 @@ #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ for ((x) = RB_MAX(name, head); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ (x) = (y)) - -#endif /* _SYS_TREE_H_ */ -- cgit v1.2.3 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 ++- src/common/tree.h | 1159 ++++++++++++++++++--------------- 2 files changed, 666 insertions(+), 592 deletions(-) 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: diff --git a/src/common/tree.h b/src/common/tree.h index 4a295f894..3da49e422 100644 --- a/src/common/tree.h +++ b/src/common/tree.h @@ -43,533 +43,632 @@ * The maximum height of a red-black tree is 2lg (n+1). */ -/* Macros that define a red-black tree */ -#define RB_HEAD(name, type) \ - struct name { \ - struct type* rbh_root; /* root of the tree */ \ - } - -#define RB_INITIALIZER(root) \ - { NULL } - -#define RB_INIT(root) \ - do { \ - (root)->rbh_root = NULL; \ - } while (/*CONSTCOND*/ 0) - -#define RB_BLACK 0 -#define RB_RED 1 -#define RB_ENTRY(type) \ - struct { \ - struct type* rbe_left; /* left element */ \ - struct type* rbe_right; /* right element */ \ - struct type* rbe_parent; /* parent element */ \ - int rbe_color; /* node color */ \ - } - -#define RB_LEFT(elm, field) (elm)->field.rbe_left -#define RB_RIGHT(elm, field) (elm)->field.rbe_right -#define RB_PARENT(elm, field) (elm)->field.rbe_parent -#define RB_COLOR(elm, field) (elm)->field.rbe_color -#define RB_ROOT(head) (head)->rbh_root -#define RB_EMPTY(head) (RB_ROOT(head) == NULL) - -#define RB_SET(elm, parent, field) \ - do { \ - RB_PARENT(elm, field) = parent; \ - RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ - RB_COLOR(elm, field) = RB_RED; \ - } while (/*CONSTCOND*/ 0) - -#define RB_SET_BLACKRED(black, red, field) \ - do { \ - RB_COLOR(black, field) = RB_BLACK; \ - RB_COLOR(red, field) = RB_RED; \ - } while (/*CONSTCOND*/ 0) - -#ifndef RB_AUGMENT -#define RB_AUGMENT(x) \ - do { \ - } while (0) -#endif - -#define RB_ROTATE_LEFT(head, elm, tmp, field) \ - do { \ - (tmp) = RB_RIGHT(elm, field); \ - if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ - RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ - } \ - RB_AUGMENT(elm); \ - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ - else \ - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ - } else \ - (head)->rbh_root = (tmp); \ - RB_LEFT(tmp, field) = (elm); \ - RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ - } while (/*CONSTCOND*/ 0) - -#define RB_ROTATE_RIGHT(head, elm, tmp, field) \ - do { \ - (tmp) = RB_LEFT(elm, field); \ - if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ - RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ - } \ - RB_AUGMENT(elm); \ - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ - else \ - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ - } else \ - (head)->rbh_root = (tmp); \ - RB_RIGHT(tmp, field) = (elm); \ - RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ - } while (/*CONSTCOND*/ 0) - -/* Generates prototypes and inline functions */ -#define RB_PROTOTYPE(name, type, field, cmp) RB_PROTOTYPE_INTERNAL(name, type, field, cmp, ) -#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ - RB_PROTOTYPE_INTERNAL(name, type, field, cmp, static) -#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ - RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ - RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ - RB_PROTOTYPE_INSERT(name, type, attr); \ - RB_PROTOTYPE_REMOVE(name, type, attr); \ - RB_PROTOTYPE_FIND(name, type, attr); \ - RB_PROTOTYPE_NFIND(name, type, attr); \ - RB_PROTOTYPE_FIND_LIGHT(name, type, attr); \ - RB_PROTOTYPE_NFIND_LIGHT(name, type, attr); \ - RB_PROTOTYPE_NEXT(name, type, attr); \ - RB_PROTOTYPE_PREV(name, type, attr); \ - RB_PROTOTYPE_MINMAX(name, type, attr); -#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ - attr void name##_RB_INSERT_COLOR(struct name*, struct type*) -#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ - attr void name##_RB_REMOVE_COLOR(struct name*, struct type*, struct type*) -#define RB_PROTOTYPE_REMOVE(name, type, attr) \ - attr struct type* name##_RB_REMOVE(struct name*, struct type*) -#define RB_PROTOTYPE_INSERT(name, type, attr) \ - attr struct type* name##_RB_INSERT(struct name*, struct type*) -#define RB_PROTOTYPE_FIND(name, type, attr) \ - attr struct type* name##_RB_FIND(struct name*, struct type*) -#define RB_PROTOTYPE_NFIND(name, type, attr) \ - attr struct type* name##_RB_NFIND(struct name*, struct type*) -#define RB_PROTOTYPE_FIND_LIGHT(name, type, attr) \ - attr struct type* name##_RB_FIND_LIGHT(struct name*, const void*) -#define RB_PROTOTYPE_NFIND_LIGHT(name, type, attr) \ - attr struct type* name##_RB_NFIND_LIGHT(struct name*, const void*) -#define RB_PROTOTYPE_NEXT(name, type, attr) attr struct type* name##_RB_NEXT(struct type*) -#define RB_PROTOTYPE_PREV(name, type, attr) attr struct type* name##_RB_PREV(struct type*) -#define RB_PROTOTYPE_MINMAX(name, type, attr) attr struct type* name##_RB_MINMAX(struct name*, int) - -/* Main rb operation. - * Moves node close to the key of elm to top - */ -#define RB_GENERATE_WITHOUT_COMPARE(name, type, field) \ - RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, ) -#define RB_GENERATE_WITHOUT_COMPARE_STATIC(name, type, field) \ - RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, static) -#define RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, attr) \ - RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ - RB_GENERATE_REMOVE(name, type, field, attr) \ - RB_GENERATE_NEXT(name, type, field, attr) \ - RB_GENERATE_PREV(name, type, field, attr) \ - RB_GENERATE_MINMAX(name, type, field, attr) - -#define RB_GENERATE_WITH_COMPARE(name, type, field, cmp, lcmp) \ - RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, ) -#define RB_GENERATE_WITH_COMPARE_STATIC(name, type, field, cmp, lcmp) \ - RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, static) -#define RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, attr) \ - RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ - RB_GENERATE_INSERT(name, type, field, cmp, attr) \ - RB_GENERATE_FIND(name, type, field, cmp, attr) \ - RB_GENERATE_NFIND(name, type, field, cmp, attr) \ - RB_GENERATE_FIND_LIGHT(name, type, field, lcmp, attr) \ - RB_GENERATE_NFIND_LIGHT(name, type, field, lcmp, attr) - -#define RB_GENERATE_ALL(name, type, field, cmp) RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, ) -#define RB_GENERATE_ALL_STATIC(name, type, field, cmp) \ - RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, static) -#define RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, attr) \ - RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, attr) \ - RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, attr) - -#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ - attr void name##_RB_INSERT_COLOR(struct name* head, struct type* elm) { \ - struct type *parent, *gparent, *tmp; \ - while ((parent = RB_PARENT(elm, field)) != NULL && RB_COLOR(parent, field) == RB_RED) { \ - gparent = RB_PARENT(parent, field); \ - if (parent == RB_LEFT(gparent, field)) { \ - tmp = RB_RIGHT(gparent, field); \ - if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field); \ - elm = gparent; \ - continue; \ - } \ - if (RB_RIGHT(parent, field) == elm) { \ - RB_ROTATE_LEFT(head, parent, tmp, field); \ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_RIGHT(head, gparent, tmp, field); \ - } else { \ - tmp = RB_LEFT(gparent, field); \ - if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field); \ - elm = gparent; \ - continue; \ - } \ - if (RB_LEFT(parent, field) == elm) { \ - RB_ROTATE_RIGHT(head, parent, tmp, field); \ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_LEFT(head, gparent, tmp, field); \ - } \ - } \ - RB_COLOR(head->rbh_root, field) = RB_BLACK; \ - } - -#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ - attr void name##_RB_REMOVE_COLOR(struct name* head, struct type* parent, struct type* elm) { \ - struct type* tmp; \ - while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && elm != RB_ROOT(head)) { \ - if (RB_LEFT(parent, field) == elm) { \ - tmp = RB_RIGHT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_LEFT(head, parent, tmp, field); \ - tmp = RB_RIGHT(parent, field); \ - } \ - if ((RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ - (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - } else { \ - if (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \ - struct type* oleft; \ - if ((oleft = RB_LEFT(tmp, field)) != NULL) \ - RB_COLOR(oleft, field) = RB_BLACK; \ - RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_RIGHT(head, tmp, oleft, field); \ - tmp = RB_RIGHT(parent, field); \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ - RB_COLOR(parent, field) = RB_BLACK; \ - if (RB_RIGHT(tmp, field)) \ - RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ - RB_ROTATE_LEFT(head, parent, tmp, field); \ - elm = RB_ROOT(head); \ - break; \ - } \ - } else { \ - tmp = RB_LEFT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_RIGHT(head, parent, tmp, field); \ - tmp = RB_LEFT(parent, field); \ - } \ - if ((RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ - (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - } else { \ - if (RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \ - struct type* oright; \ - if ((oright = RB_RIGHT(tmp, field)) != NULL) \ - RB_COLOR(oright, field) = RB_BLACK; \ - RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_LEFT(head, tmp, oright, field); \ - tmp = RB_LEFT(parent, field); \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ - RB_COLOR(parent, field) = RB_BLACK; \ - if (RB_LEFT(tmp, field)) \ - RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ - RB_ROTATE_RIGHT(head, parent, tmp, field); \ - elm = RB_ROOT(head); \ - break; \ - } \ - } \ - } \ - if (elm) \ - RB_COLOR(elm, field) = RB_BLACK; \ - } - -#define RB_GENERATE_REMOVE(name, type, field, attr) \ - attr struct type* name##_RB_REMOVE(struct name* head, struct type* elm) { \ - struct type *child, *parent, *old = elm; \ - int color; \ - if (RB_LEFT(elm, field) == NULL) \ - child = RB_RIGHT(elm, field); \ - else if (RB_RIGHT(elm, field) == NULL) \ - child = RB_LEFT(elm, field); \ - else { \ - struct type* left; \ - elm = RB_RIGHT(elm, field); \ - while ((left = RB_LEFT(elm, field)) != NULL) \ - elm = left; \ - child = RB_RIGHT(elm, field); \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child) \ - RB_PARENT(child, field) = parent; \ - if (parent) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ - else \ - RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ - if (RB_PARENT(elm, field) == old) \ - parent = elm; \ - (elm)->field = (old)->field; \ - if (RB_PARENT(old, field)) { \ - if (RB_LEFT(RB_PARENT(old, field), field) == old) \ - RB_LEFT(RB_PARENT(old, field), field) = elm; \ - else \ - RB_RIGHT(RB_PARENT(old, field), field) = elm; \ - RB_AUGMENT(RB_PARENT(old, field)); \ - } else \ - RB_ROOT(head) = elm; \ - RB_PARENT(RB_LEFT(old, field), field) = elm; \ - if (RB_RIGHT(old, field)) \ - RB_PARENT(RB_RIGHT(old, field), field) = elm; \ - if (parent) { \ - left = parent; \ - do { \ - RB_AUGMENT(left); \ - } while ((left = RB_PARENT(left, field)) != NULL); \ - } \ - goto color; \ - } \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child) \ - RB_PARENT(child, field) = parent; \ - if (parent) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ - else \ - RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ - color: \ - if (color == RB_BLACK) \ - name##_RB_REMOVE_COLOR(head, parent, child); \ - return (old); \ - } - -#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ - /* Inserts a node into the RB tree */ \ - attr struct type* name##_RB_INSERT(struct name* head, struct type* elm) { \ - struct type* tmp; \ - struct type* parent = NULL; \ - int comp = 0; \ - tmp = RB_ROOT(head); \ - while (tmp) { \ - parent = tmp; \ - comp = (cmp)(elm, parent); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - RB_SET(elm, parent, field); \ - if (parent != NULL) { \ - if (comp < 0) \ - RB_LEFT(parent, field) = elm; \ - else \ - RB_RIGHT(parent, field) = elm; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = elm; \ - name##_RB_INSERT_COLOR(head, elm); \ - return (NULL); \ - } - -#define RB_GENERATE_FIND(name, type, field, cmp, attr) \ - /* Finds the node with the same key as elm */ \ - attr struct type* name##_RB_FIND(struct name* head, struct type* elm) { \ - struct type* tmp = RB_ROOT(head); \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (NULL); \ - } - -#define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ - /* Finds the first node greater than or equal to the search key */ \ - attr struct type* name##_RB_NFIND(struct name* head, struct type* elm) { \ - struct type* tmp = RB_ROOT(head); \ - struct type* res = NULL; \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) { \ - res = tmp; \ - tmp = RB_LEFT(tmp, field); \ - } else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (res); \ - } - -#define RB_GENERATE_FIND_LIGHT(name, type, field, lcmp, attr) \ - /* Finds the node with the same key as elm */ \ - attr struct type* name##_RB_FIND_LIGHT(struct name* head, const void* lelm) { \ - struct type* tmp = RB_ROOT(head); \ - int comp; \ - while (tmp) { \ - comp = lcmp(lelm, tmp); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (NULL); \ - } - -#define RB_GENERATE_NFIND_LIGHT(name, type, field, lcmp, attr) \ - /* Finds the first node greater than or equal to the search key */ \ - attr struct type* name##_RB_NFIND_LIGHT(struct name* head, const void* lelm) { \ - struct type* tmp = RB_ROOT(head); \ - struct type* res = NULL; \ - int comp; \ - while (tmp) { \ - comp = lcmp(lelm, tmp); \ - if (comp < 0) { \ - res = tmp; \ - tmp = RB_LEFT(tmp, field); \ - } else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (res); \ - } - -#define RB_GENERATE_NEXT(name, type, field, attr) \ - /* ARGSUSED */ \ - attr struct type* name##_RB_NEXT(struct type* elm) { \ - if (RB_RIGHT(elm, field)) { \ - elm = RB_RIGHT(elm, field); \ - while (RB_LEFT(elm, field)) \ - elm = RB_LEFT(elm, field); \ - } else { \ - if (RB_PARENT(elm, field) && (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - elm = RB_PARENT(elm, field); \ - } \ - } \ - return (elm); \ - } - -#define RB_GENERATE_PREV(name, type, field, attr) \ - /* ARGSUSED */ \ - attr struct type* name##_RB_PREV(struct type* elm) { \ - if (RB_LEFT(elm, field)) { \ - elm = RB_LEFT(elm, field); \ - while (RB_RIGHT(elm, field)) \ - elm = RB_RIGHT(elm, field); \ - } else { \ - if (RB_PARENT(elm, field) && (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - elm = RB_PARENT(elm, field); \ - } \ - } \ - return (elm); \ - } - -#define RB_GENERATE_MINMAX(name, type, field, attr) \ - attr struct type* name##_RB_MINMAX(struct name* head, int val) { \ - struct type* tmp = RB_ROOT(head); \ - struct type* parent = NULL; \ - while (tmp) { \ - parent = tmp; \ - if (val < 0) \ - tmp = RB_LEFT(tmp, field); \ - else \ - tmp = RB_RIGHT(tmp, field); \ - } \ - return (parent); \ - } - -#define RB_NEGINF -1 -#define RB_INF 1 - -#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) -#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) -#define RB_FIND(name, x, y) name##_RB_FIND(x, y) -#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) -#define RB_FIND_LIGHT(name, x, y) name##_RB_FIND_LIGHT(x, y) -#define RB_NFIND_LIGHT(name, x, y) name##_RB_NFIND_LIGHT(x, y) -#define RB_NEXT(name, x, y) name##_RB_NEXT(y) -#define RB_PREV(name, x, y) name##_RB_PREV(y) -#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) -#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) - -#define RB_FOREACH(x, name, head) \ - for ((x) = RB_MIN(name, head); (x) != NULL; (x) = name##_RB_NEXT(x)) - -#define RB_FOREACH_FROM(x, name, y) \ - for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); (x) = (y)) - -#define RB_FOREACH_SAFE(x, name, head, y) \ - for ((x) = RB_MIN(name, head); ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ - (x) = (y)) - -#define RB_FOREACH_REVERSE(x, name, head) \ - for ((x) = RB_MAX(name, head); (x) != NULL; (x) = name##_RB_PREV(x)) - -#define RB_FOREACH_REVERSE_FROM(x, name, y) \ - for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); (x) = (y)) - -#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ - for ((x) = RB_MAX(name, head); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ - (x) = (y)) +namespace Common { +template +class RBHead { +public: + [[nodiscard]] T* Root() { + return rbh_root; + } + + [[nodiscard]] const T* Root() const { + return rbh_root; + } + + void SetRoot(T* root) { + rbh_root = root; + } + + [[nodiscard]] bool IsEmpty() const { + return Root() == nullptr; + } + +private: + T* rbh_root = nullptr; +}; + +enum class EntryColor { + Black, + Red, +}; + +template +class RBEntry { +public: + [[nodiscard]] T* Left() { + return rbe_left; + } + + [[nodiscard]] const T* Left() const { + return rbe_left; + } + + void SetLeft(T* left) { + rbe_left = left; + } + + [[nodiscard]] T* Right() { + return rbe_right; + } + + [[nodiscard]] const T* Right() const { + return rbe_right; + } + + void SetRight(T* right) { + rbe_right = right; + } + + [[nodiscard]] T* Parent() { + return rbe_parent; + } + + [[nodiscard]] const T* Parent() const { + return rbe_parent; + } + + void SetParent(T* parent) { + rbe_parent = parent; + } + + [[nodiscard]] bool IsBlack() const { + return rbe_color == EntryColor::Black; + } + + [[nodiscard]] bool IsRed() const { + return rbe_color == EntryColor::Red; + } + + [[nodiscard]] EntryColor Color() const { + return rbe_color; + } + + void SetColor(EntryColor color) { + rbe_color = color; + } + +private: + T* rbe_left = nullptr; + T* rbe_right = nullptr; + T* rbe_parent = nullptr; + EntryColor rbe_color{}; +}; + +template +[[nodiscard]] RBEntry& RB_ENTRY(Node* node) { + return node->GetEntry(); +} + +template +[[nodiscard]] const RBEntry& RB_ENTRY(const Node* node) { + return node->GetEntry(); +} + +template +[[nodiscard]] Node* RB_PARENT(Node* node) { + return RB_ENTRY(node).Parent(); +} + +template +[[nodiscard]] const Node* RB_PARENT(const Node* node) { + return RB_ENTRY(node).Parent(); +} + +template +void RB_SET_PARENT(Node* node, Node* parent) { + return RB_ENTRY(node).SetParent(parent); +} + +template +[[nodiscard]] Node* RB_LEFT(Node* node) { + return RB_ENTRY(node).Left(); +} + +template +[[nodiscard]] const Node* RB_LEFT(const Node* node) { + return RB_ENTRY(node).Left(); +} + +template +void RB_SET_LEFT(Node* node, Node* left) { + return RB_ENTRY(node).SetLeft(left); +} + +template +[[nodiscard]] Node* RB_RIGHT(Node* node) { + return RB_ENTRY(node).Right(); +} + +template +[[nodiscard]] const Node* RB_RIGHT(const Node* node) { + return RB_ENTRY(node).Right(); +} + +template +void RB_SET_RIGHT(Node* node, Node* right) { + return RB_ENTRY(node).SetRight(right); +} + +template +[[nodiscard]] bool RB_IS_BLACK(const Node* node) { + return RB_ENTRY(node).IsBlack(); +} + +template +[[nodiscard]] bool RB_IS_RED(const Node* node) { + return RB_ENTRY(node).IsRed(); +} + +template +[[nodiscard]] EntryColor RB_COLOR(const Node* node) { + return RB_ENTRY(node).Color(); +} + +template +void RB_SET_COLOR(Node* node, EntryColor color) { + return RB_ENTRY(node).SetColor(color); +} + +template +void RB_SET(Node* node, Node* parent) { + auto& entry = RB_ENTRY(node); + entry.SetParent(parent); + entry.SetLeft(nullptr); + entry.SetRight(nullptr); + entry.SetColor(EntryColor::Red); +} + +template +void RB_SET_BLACKRED(Node* black, Node* red) { + RB_SET_COLOR(black, EntryColor::Black); + RB_SET_COLOR(red, EntryColor::Red); +} + +template +void RB_ROTATE_LEFT(RBHead* head, Node* elm, Node*& tmp) { + tmp = RB_RIGHT(elm); + RB_SET_RIGHT(elm, RB_LEFT(tmp)); + if (RB_RIGHT(elm) != nullptr) { + RB_SET_PARENT(RB_LEFT(tmp), elm); + } + + RB_SET_PARENT(tmp, RB_PARENT(elm)); + if (RB_PARENT(tmp) != nullptr) { + if (elm == RB_LEFT(RB_PARENT(elm))) { + RB_SET_LEFT(RB_PARENT(elm), tmp); + } else { + RB_SET_RIGHT(RB_PARENT(elm), tmp); + } + } else { + head->SetRoot(tmp); + } + + RB_SET_LEFT(tmp, elm); + RB_SET_PARENT(elm, tmp); +} + +template +void RB_ROTATE_RIGHT(RBHead* head, Node* elm, Node*& tmp) { + tmp = RB_LEFT(elm); + RB_SET_LEFT(elm, RB_RIGHT(tmp)); + if (RB_LEFT(elm) != nullptr) { + RB_SET_PARENT(RB_RIGHT(tmp), elm); + } + + RB_SET_PARENT(tmp, RB_PARENT(elm)); + if (RB_PARENT(tmp) != nullptr) { + if (elm == RB_LEFT(RB_PARENT(elm))) { + RB_SET_LEFT(RB_PARENT(elm), tmp); + } else { + RB_SET_RIGHT(RB_PARENT(elm), tmp); + } + } else { + head->SetRoot(tmp); + } + + RB_SET_RIGHT(tmp, elm); + RB_SET_PARENT(elm, tmp); +} + +template +void RB_INSERT_COLOR(RBHead* head, Node* elm) { + Node* parent = nullptr; + Node* tmp = nullptr; + + while ((parent = RB_PARENT(elm)) != nullptr && RB_IS_RED(parent)) { + Node* gparent = RB_PARENT(parent); + if (parent == RB_LEFT(gparent)) { + tmp = RB_RIGHT(gparent); + if (tmp && RB_IS_RED(tmp)) { + RB_SET_COLOR(tmp, EntryColor::Black); + RB_SET_BLACKRED(parent, gparent); + elm = gparent; + continue; + } + + if (RB_RIGHT(parent) == elm) { + RB_ROTATE_LEFT(head, parent, tmp); + tmp = parent; + parent = elm; + elm = tmp; + } + + RB_SET_BLACKRED(parent, gparent); + RB_ROTATE_RIGHT(head, gparent, tmp); + } else { + tmp = RB_LEFT(gparent); + if (tmp && RB_IS_RED(tmp)) { + RB_SET_COLOR(tmp, EntryColor::Black); + RB_SET_BLACKRED(parent, gparent); + elm = gparent; + continue; + } + + if (RB_LEFT(parent) == elm) { + RB_ROTATE_RIGHT(head, parent, tmp); + tmp = parent; + parent = elm; + elm = tmp; + } + + RB_SET_BLACKRED(parent, gparent); + RB_ROTATE_LEFT(head, gparent, tmp); + } + } + + RB_SET_COLOR(head->Root(), EntryColor::Black); +} + +template +void RB_REMOVE_COLOR(RBHead* head, Node* parent, Node* elm) { + Node* tmp; + while ((elm == nullptr || RB_IS_BLACK(elm)) && elm != head->Root()) { + if (RB_LEFT(parent) == elm) { + tmp = RB_RIGHT(parent); + if (RB_IS_RED(tmp)) { + RB_SET_BLACKRED(tmp, parent); + RB_ROTATE_LEFT(head, parent, tmp); + tmp = RB_RIGHT(parent); + } + + if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) && + (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) { + RB_SET_COLOR(tmp, EntryColor::Red); + elm = parent; + parent = RB_PARENT(elm); + } else { + if (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp))) { + Node* oleft; + if ((oleft = RB_LEFT(tmp)) != nullptr) { + RB_SET_COLOR(oleft, EntryColor::Black); + } + + RB_SET_COLOR(tmp, EntryColor::Red); + RB_ROTATE_RIGHT(head, tmp, oleft); + tmp = RB_RIGHT(parent); + } + + RB_SET_COLOR(tmp, RB_COLOR(parent)); + RB_SET_COLOR(parent, EntryColor::Black); + if (RB_RIGHT(tmp)) { + RB_SET_COLOR(RB_RIGHT(tmp), EntryColor::Black); + } + + RB_ROTATE_LEFT(head, parent, tmp); + elm = head->Root(); + break; + } + } else { + tmp = RB_LEFT(parent); + if (RB_IS_RED(tmp)) { + RB_SET_BLACKRED(tmp, parent); + RB_ROTATE_RIGHT(head, parent, tmp); + tmp = RB_LEFT(parent); + } + + if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) && + (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) { + RB_SET_COLOR(tmp, EntryColor::Red); + elm = parent; + parent = RB_PARENT(elm); + } else { + if (RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) { + Node* oright; + if ((oright = RB_RIGHT(tmp)) != nullptr) { + RB_SET_COLOR(oright, EntryColor::Black); + } + + RB_SET_COLOR(tmp, EntryColor::Red); + RB_ROTATE_LEFT(head, tmp, oright); + tmp = RB_LEFT(parent); + } + + RB_SET_COLOR(tmp, RB_COLOR(parent)); + RB_SET_COLOR(parent, EntryColor::Black); + + if (RB_LEFT(tmp)) { + RB_SET_COLOR(RB_LEFT(tmp), EntryColor::Black); + } + + RB_ROTATE_RIGHT(head, parent, tmp); + elm = head->Root(); + break; + } + } + } + + if (elm) { + RB_SET_COLOR(elm, EntryColor::Black); + } +} + +template +Node* RB_REMOVE(RBHead* head, Node* elm) { + Node* child = nullptr; + Node* parent = nullptr; + Node* old = elm; + EntryColor color{}; + + const auto finalize = [&] { + if (color == EntryColor::Black) { + RB_REMOVE_COLOR(head, parent, child); + } + + return old; + }; + + if (RB_LEFT(elm) == nullptr) { + child = RB_RIGHT(elm); + } else if (RB_RIGHT(elm) == nullptr) { + child = RB_LEFT(elm); + } else { + Node* left; + elm = RB_RIGHT(elm); + while ((left = RB_LEFT(elm)) != nullptr) { + elm = left; + } + + child = RB_RIGHT(elm); + parent = RB_PARENT(elm); + color = RB_COLOR(elm); + + if (child) { + RB_SET_PARENT(child, parent); + } + if (parent) { + if (RB_LEFT(parent) == elm) { + RB_SET_LEFT(parent, child); + } else { + RB_SET_RIGHT(parent, child); + } + } else { + head->SetRoot(child); + } + + if (RB_PARENT(elm) == old) { + parent = elm; + } + + elm->SetEntry(old->GetEntry()); + + if (RB_PARENT(old)) { + if (RB_LEFT(RB_PARENT(old)) == old) { + RB_SET_LEFT(RB_PARENT(old), elm); + } else { + RB_SET_RIGHT(RB_PARENT(old), elm); + } + } else { + head->SetRoot(elm); + } + RB_SET_PARENT(RB_LEFT(old), elm); + if (RB_RIGHT(old)) { + RB_SET_PARENT(RB_RIGHT(old), elm); + } + if (parent) { + left = parent; + } + + return finalize(); + } + + parent = RB_PARENT(elm); + color = RB_COLOR(elm); + + if (child) { + RB_SET_PARENT(child, parent); + } + if (parent) { + if (RB_LEFT(parent) == elm) { + RB_SET_LEFT(parent, child); + } else { + RB_SET_RIGHT(parent, child); + } + } else { + head->SetRoot(child); + } + + return finalize(); +} + +// Inserts a node into the RB tree +template +Node* RB_INSERT(RBHead* head, Node* elm, CompareFunction cmp) { + Node* parent = nullptr; + Node* tmp = head->Root(); + int comp = 0; + + while (tmp) { + parent = tmp; + comp = cmp(elm, parent); + if (comp < 0) { + tmp = RB_LEFT(tmp); + } else if (comp > 0) { + tmp = RB_RIGHT(tmp); + } else { + return tmp; + } + } + + RB_SET(elm, parent); + + if (parent != nullptr) { + if (comp < 0) { + RB_SET_LEFT(parent, elm); + } else { + RB_SET_RIGHT(parent, elm); + } + } else { + head->SetRoot(elm); + } + + RB_INSERT_COLOR(head, elm); + return nullptr; +} + +// Finds the node with the same key as elm +template +Node* RB_FIND(RBHead* head, Node* elm, CompareFunction cmp) { + Node* tmp = head->Root(); + + while (tmp) { + const int comp = cmp(elm, tmp); + if (comp < 0) { + tmp = RB_LEFT(tmp); + } else if (comp > 0) { + tmp = RB_RIGHT(tmp); + } else { + return tmp; + } + } + + return nullptr; +} + +// Finds the first node greater than or equal to the search key +template +Node* RB_NFIND(RBHead* head, Node* elm, CompareFunction cmp) { + Node* tmp = head->Root(); + Node* res = nullptr; + + while (tmp) { + const int comp = cmp(elm, tmp); + if (comp < 0) { + res = tmp; + tmp = RB_LEFT(tmp); + } else if (comp > 0) { + tmp = RB_RIGHT(tmp); + } else { + return tmp; + } + } + + return res; +} + +// Finds the node with the same key as lelm +template +Node* RB_FIND_LIGHT(RBHead* head, const void* lelm, CompareFunction lcmp) { + Node* tmp = head->Root(); + + while (tmp) { + const int comp = lcmp(lelm, tmp); + if (comp < 0) { + tmp = RB_LEFT(tmp); + } else if (comp > 0) { + tmp = RB_RIGHT(tmp); + } else { + return tmp; + } + } + + return nullptr; +} + +// Finds the first node greater than or equal to the search key +template +Node* RB_NFIND_LIGHT(RBHead* head, const void* lelm, CompareFunction lcmp) { + Node* tmp = head->Root(); + Node* res = nullptr; + + while (tmp) { + const int comp = lcmp(lelm, tmp); + if (comp < 0) { + res = tmp; + tmp = RB_LEFT(tmp); + } else if (comp > 0) { + tmp = RB_RIGHT(tmp); + } else { + return tmp; + } + } + + return res; +} + +template +Node* RB_NEXT(Node* elm) { + if (RB_RIGHT(elm)) { + elm = RB_RIGHT(elm); + while (RB_LEFT(elm)) { + elm = RB_LEFT(elm); + } + } else { + if (RB_PARENT(elm) && (elm == RB_LEFT(RB_PARENT(elm)))) { + elm = RB_PARENT(elm); + } else { + while (RB_PARENT(elm) && (elm == RB_RIGHT(RB_PARENT(elm)))) { + elm = RB_PARENT(elm); + } + elm = RB_PARENT(elm); + } + } + return elm; +} + +template +Node* RB_PREV(Node* elm) { + if (RB_LEFT(elm)) { + elm = RB_LEFT(elm); + while (RB_RIGHT(elm)) { + elm = RB_RIGHT(elm); + } + } else { + if (RB_PARENT(elm) && (elm == RB_RIGHT(RB_PARENT(elm)))) { + elm = RB_PARENT(elm); + } else { + while (RB_PARENT(elm) && (elm == RB_LEFT(RB_PARENT(elm)))) { + elm = RB_PARENT(elm); + } + elm = RB_PARENT(elm); + } + } + return elm; +} + +template +Node* RB_MINMAX(RBHead* head, bool is_min) { + Node* tmp = head->Root(); + Node* parent = nullptr; + + while (tmp) { + parent = tmp; + if (is_min) { + tmp = RB_LEFT(tmp); + } else { + tmp = RB_RIGHT(tmp); + } + } + + return parent; +} + +template +Node* RB_MIN(RBHead* head) { + return RB_MINMAX(head, true); +} + +template +Node* RB_MAX(RBHead* head) { + return RB_MINMAX(head, false); +} +} // namespace Common -- cgit v1.2.3