diff options
author | Lioncash <mathew1800@gmail.com> | 2021-01-12 02:47:36 -0500 |
---|---|---|
committer | Lioncash <mathew1800@gmail.com> | 2021-01-12 16:46:36 -0500 |
commit | b15e1a35011629c3b31edd10c1d10b8d7fafcb2c (patch) | |
tree | 6bb48e8e2f65ed47436c4279f0732e45c2041007 /src/common/tree.h | |
parent | 197b5d19bc3de919d315633709eef24cd4b15786 (diff) |
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.
Diffstat (limited to 'src/common/tree.h')
-rw-r--r-- | src/common/tree.h | 1159 |
1 files changed, 629 insertions, 530 deletions
diff --git a/src/common/tree.h b/src/common/tree.h index 4a295f894d..3da49e422f 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 <typename T> +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 <typename T> +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 <typename Node> +[[nodiscard]] RBEntry<Node>& RB_ENTRY(Node* node) { + return node->GetEntry(); +} + +template <typename Node> +[[nodiscard]] const RBEntry<Node>& RB_ENTRY(const Node* node) { + return node->GetEntry(); +} + +template <typename Node> +[[nodiscard]] Node* RB_PARENT(Node* node) { + return RB_ENTRY(node).Parent(); +} + +template <typename Node> +[[nodiscard]] const Node* RB_PARENT(const Node* node) { + return RB_ENTRY(node).Parent(); +} + +template <typename Node> +void RB_SET_PARENT(Node* node, Node* parent) { + return RB_ENTRY(node).SetParent(parent); +} + +template <typename Node> +[[nodiscard]] Node* RB_LEFT(Node* node) { + return RB_ENTRY(node).Left(); +} + +template <typename Node> +[[nodiscard]] const Node* RB_LEFT(const Node* node) { + return RB_ENTRY(node).Left(); +} + +template <typename Node> +void RB_SET_LEFT(Node* node, Node* left) { + return RB_ENTRY(node).SetLeft(left); +} + +template <typename Node> +[[nodiscard]] Node* RB_RIGHT(Node* node) { + return RB_ENTRY(node).Right(); +} + +template <typename Node> +[[nodiscard]] const Node* RB_RIGHT(const Node* node) { + return RB_ENTRY(node).Right(); +} + +template <typename Node> +void RB_SET_RIGHT(Node* node, Node* right) { + return RB_ENTRY(node).SetRight(right); +} + +template <typename Node> +[[nodiscard]] bool RB_IS_BLACK(const Node* node) { + return RB_ENTRY(node).IsBlack(); +} + +template <typename Node> +[[nodiscard]] bool RB_IS_RED(const Node* node) { + return RB_ENTRY(node).IsRed(); +} + +template <typename Node> +[[nodiscard]] EntryColor RB_COLOR(const Node* node) { + return RB_ENTRY(node).Color(); +} + +template <typename Node> +void RB_SET_COLOR(Node* node, EntryColor color) { + return RB_ENTRY(node).SetColor(color); +} + +template <typename Node> +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 <typename Node> +void RB_SET_BLACKRED(Node* black, Node* red) { + RB_SET_COLOR(black, EntryColor::Black); + RB_SET_COLOR(red, EntryColor::Red); +} + +template <typename Node> +void RB_ROTATE_LEFT(RBHead<Node>* 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 <typename Node> +void RB_ROTATE_RIGHT(RBHead<Node>* 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 <typename Node> +void RB_INSERT_COLOR(RBHead<Node>* 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 <typename Node> +void RB_REMOVE_COLOR(RBHead<Node>* 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 <typename Node> +Node* RB_REMOVE(RBHead<Node>* 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 <typename Node, typename CompareFunction> +Node* RB_INSERT(RBHead<Node>* 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 <typename Node, typename CompareFunction> +Node* RB_FIND(RBHead<Node>* 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 <typename Node, typename CompareFunction> +Node* RB_NFIND(RBHead<Node>* 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 <typename Node, typename CompareFunction> +Node* RB_FIND_LIGHT(RBHead<Node>* 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 <typename Node, typename CompareFunction> +Node* RB_NFIND_LIGHT(RBHead<Node>* 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 <typename Node> +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 <typename Node> +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 <typename Node> +Node* RB_MINMAX(RBHead<Node>* 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 <typename Node> +Node* RB_MIN(RBHead<Node>* head) { + return RB_MINMAX(head, true); +} + +template <typename Node> +Node* RB_MAX(RBHead<Node>* head) { + return RB_MINMAX(head, false); +} +} // namespace Common |