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 #ifndef COMMON_RBTREE_IMPL_H
13 #define COMMON_RBTREE_IMPL_H
14
15 #include <common/rbtree.h>
16
17 #define RB_RED (0)
18 #define RB_BLACK (1)
19
20 #define __rb_parent(pc) ((struct rb_node*)((pc) & ~3))
21 #define __rb_color(pc) ((pc)&1)
22 #define __rb_is_black(pc) (__rb_color((pc)) == RB_BLACK)
23 #define __rb_is_red(pc) (__rb_color((pc)) == RB_RED)
24
25 #define rb_parent(node) (__rb_parent((node)->__parent_color))
26 #define rb_color(node) (__rb_color((node)->__parent_color))
27 #define rb_is_black(node) (__rb_is_black((node)->__parent_color))
28 #define rb_is_red(node) (__rb_is_red((node)->__parent_color))
29 #define rb_red_parent(node) ((struct rb_node*)(node)->__parent_color)
30 #define rb_has_red_child(node) \
31 (((node)->left_child && rb_is_red((node)->left_child)) \
32 || ((node)->right_child && rb_is_red((node)->right_child)))
33
34 /*
35 * set parent and color helpers
36 * Due to malloc/kmalloc 4-bytes alignment, and alignment attributes specified
37 * in the defination of rb_node, we can use a compressed layout to store parent
38 * rb_node pointer and color of a node in one field, saving 1 byte per rb_node.
39 *
40 * Thanks to alignment, at least the leftmost 3 bits of a rb_node pointer would
41 * be 0. We leverage MLB of __parent_color to store color of a node. 0
42 * represents a red node, and 1 represents a black one. This also indicates that
43 * a new node is naturally red, which is desired in rbtree.
44 */
rb_set_parent(struct rb_node * this,struct rb_node * parent)45 static inline void rb_set_parent(struct rb_node* this, struct rb_node* parent)
46 {
47 this->__parent_color = (unsigned long)parent | rb_color(this);
48 }
49
rb_set_color(struct rb_node * this,int color)50 static inline void rb_set_color(struct rb_node* this, int color)
51 {
52 this->__parent_color = (unsigned long)rb_parent(this) | (color);
53 }
54
rb_set_parent_color(struct rb_node * this,struct rb_node * parent,int color)55 static inline void rb_set_parent_color(struct rb_node* this,
56 struct rb_node* parent, int color)
57 {
58 this->__parent_color = (unsigned long)parent | (color & 3);
59 }
60
61 #endif /* COMMON_RBTREE_IMPL_H */