1 /*
2 * Copyright (c) 2023 Institute of Parallel And Distributed Systems (IPADS), Shanghai Jiao Tong University (SJTU)
3 * Licensed under the Mulan PSL v2.
4 * You can use this software according to the terms and conditions of the Mulan PSL v2.
5 * You may obtain a copy of Mulan PSL v2 at:
6 * http://license.coscl.org.cn/MulanPSL2
7 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR
8 * IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR
9 * PURPOSE.
10 * See the Mulan PSL v2 for more details.
11 */
12
13 #pragma once
14 #include <chcore/container/rbtree.h>
15
16 #define RB_RED (0)
17 #define RB_BLACK (1)
18
19 #define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
20 #define __rb_color(pc) (pc & 1)
21 #define __rb_is_black(pc) (__rb_color(pc) == RB_BLACK)
22 #define __rb_is_red(pc) (__rb_color(pc) == RB_RED)
23
24 #define rb_parent(node) (__rb_parent(node->__parent_color))
25 #define rb_color(node) (__rb_color(node->__parent_color))
26 #define rb_is_black(node) (__rb_is_black(node->__parent_color))
27 #define rb_is_red(node) (__rb_is_red(node->__parent_color))
28 #define rb_red_parent(node) ((struct rb_node *)node->__parent_color)
29 #define rb_has_red_child(node) \
30 ((node->left_child && rb_is_red(node->left_child)) \
31 || (node->right_child && rb_is_red(node->right_child)))
32
33 void __rb_insert_color(struct rb_root *root, struct rb_node *node);
34
35 /*
36 * set parent and color helpers
37 * Due to malloc/kmalloc 4-bytes alignment, and alignment attributes specified
38 * in the defination of rb_node, we can use a compressed layout to store parent
39 * rb_node pointer and color of a node in one field, saving 1 byte per rb_node.
40 *
41 * Thanks to alignment, at least the leftmost 3 bits of a rb_node pointer would
42 * be 0. We leverage MLB of __parent_color to store color of a node. 0
43 * represents a red node, and 1 represents a black one. This also indicates that
44 * a new node is naturally red, which is desired in rbtree.
45 */
rb_set_parent(struct rb_node * this,struct rb_node * parent)46 static inline void rb_set_parent(struct rb_node *this, struct rb_node *parent)
47 {
48 this->__parent_color = (unsigned long)parent | rb_color(this);
49 }
50
rb_set_color(struct rb_node * this,int color)51 static inline void rb_set_color(struct rb_node *this, int color)
52 {
53 this->__parent_color = (unsigned long)rb_parent(this) | (color);
54 }
55
rb_set_parent_color(struct rb_node * this,struct rb_node * parent,int color)56 static inline void rb_set_parent_color(struct rb_node *this,
57 struct rb_node *parent, int color)
58 {
59 this->__parent_color = (unsigned long)parent | (color & 3);
60 }
61
__rb_link_node(struct rb_node * node,struct rb_node * parent,struct rb_node ** child_link)62 static inline void __rb_link_node(struct rb_node *node, struct rb_node *parent,
63 struct rb_node **child_link)
64 {
65 node->__parent_color = 0;
66 rb_set_parent(node, parent);
67 node->left_child = node->right_child = NULL;
68 *child_link = node;
69 }
70