1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
/*
*
* Copyright (c) 2018 Huawei Technologies Co.,Ltd.
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at:
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef _UNX_RBTREE_H
#define _UNX_RBTREE_H
#ifdef __cplusplus
/* *INDENT-OFF* */
extern "C" {
/* *INDENT-ON* */
#endif
#include <stdint.h>
#include "types.h"
#include "common_pal_bitwide_adjust.h"
#define rb_parent(a) ((struct rb_node *)((a)->rb_parent_color & ~3))
#define rb_color(a) ((a)->rb_parent_color & 1)
struct rb_node
{
union
{
unsigned long rb_parent_color;
u64 rb_parent_color_a;
};
#define RB_RED 0
#define RB_BLACK 1
union
{
struct rb_node *rb_right;
u64 rb_right_a;
};
union
{
struct rb_node *rb_left;
u64 rb_left_a;
};
};
#define rb_set_red(c) do { (c)->rb_parent_color &= ~1; } while (0)
#define rb_set_black(c) do { (c)->rb_parent_color |= 1; } while (0)
/* The alignment might seem pointless, but allegedly CRIS needs it */
struct rb_root
{
union
{
struct rb_node *rb_node;
u64 rb_node_a;
};
};
#define rb_is_red(e) (!rb_color(e))
#define rb_is_black(e) rb_color(e)
static inline void
rb_set_color (struct rb_node *rb1, int color2)
{
rb1->rb_parent_color = (rb1->rb_parent_color & ~1) | color2;
}
static inline void
rb_set_parent (struct rb_node *rb1, struct rb_node *pa)
{
rb1->rb_parent_color = (rb1->rb_parent_color & 3) | (unsigned long) pa;
}
#define RB_ROOT (struct rb_root) { NULL, }
extern void rb_erase (struct rb_node *, struct rb_root *);
extern void rb_insert_color (struct rb_node *, struct rb_root *);
extern struct rb_node *rb_next (const struct rb_node *);
#define rb_entry(ptr, type, member) container_of(ptr, type, member)
#define RB_EMPTY_ROOT(root1) ((root1)->rb_node == NULL)
#define RB_CLEAR_NODE(node2) (rb_set_parent(node2, node2))
#define RB_EMPTY_NODE(node1) (rb_parent(node1) == node1)
static inline void
rb_link_node (struct rb_node *node1, struct rb_node *parent1,
struct rb_node **rb_link1)
{
node1->rb_left = node1->rb_right = NULL;
node1->rb_parent_color = (unsigned long) parent1;
*rb_link1 = node1;
}
#ifdef __cplusplus
/* *INDENT-OFF* */
}
/* *INDENT-ON* */
#endif
#endif /* _UNX_RBTREE_H */
|
