-
Notifications
You must be signed in to change notification settings - Fork 25
Expand file tree
/
Copy pathtest-rbtree.c
More file actions
142 lines (131 loc) · 2.94 KB
/
test-rbtree.c
File metadata and controls
142 lines (131 loc) · 2.94 KB
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <stdlib.h>
#define RB_RED 0
#define RB_BLACK 1
#define mk_par(p, c) ((unsigned long) (p) | (c))
struct rb_node {
unsigned long __rb_parent_color;
struct rb_node *rb_right;
struct rb_node *rb_left;
};
struct rb_root {
struct rb_node *rb_node;
};
struct number_node {
int v;
struct rb_node rb;
};
struct rb_node naked_node;
struct rb_root empty_tree_root;
struct rb_root singular_tree_root;
struct rb_root full_binary_tree_root;
struct rb_root linear_binary_tree_root;
int
main(void)
{
/* The tree structure cannot be initialized statically (because
* __rb_parent_color is initialized with non-const expression) so
* allocate it in runtime (stack is mostly unused besides these) and
* publish the pointer in the global variable to find it easily via
* gdb. */
struct rb_node singular_tree[] = {
{
.__rb_parent_color = mk_par(NULL, RB_BLACK),
.rb_right = NULL,
.rb_left = NULL,
},
};
singular_tree_root.rb_node = &singular_tree[0];
struct number_node full_binary_tree[] = {
{
.v = 0,
.rb = {
.__rb_parent_color = mk_par(NULL, RB_BLACK),
.rb_right = &full_binary_tree[2].rb,
.rb_left = &full_binary_tree[1].rb,
},
},
{
.v = 1,
.rb = {
.__rb_parent_color = mk_par(&full_binary_tree[0].rb, RB_RED),
.rb_right = &full_binary_tree[4].rb,
.rb_left = &full_binary_tree[3].rb,
},
},
{
.v = 2,
.rb = {
.__rb_parent_color = mk_par(&full_binary_tree[0].rb, RB_RED),
.rb_right = &full_binary_tree[6].rb,
.rb_left = &full_binary_tree[5].rb,
},
},
{
.v = 3,
.rb = {
.__rb_parent_color = mk_par(&full_binary_tree[1].rb, RB_BLACK),
.rb_right = NULL,
.rb_left = NULL,
},
},
{
.v = 4,
.rb = {
.__rb_parent_color = mk_par(&full_binary_tree[1].rb, RB_BLACK),
.rb_right = NULL,
.rb_left = NULL,
},
},
{
.v = 5,
.rb = {
.__rb_parent_color = mk_par(&full_binary_tree[2].rb, RB_BLACK),
.rb_right = NULL,
.rb_left = NULL,
},
},
{
.v = 6,
.rb = {
.__rb_parent_color = mk_par(&full_binary_tree[2].rb, RB_BLACK),
.rb_right = NULL,
.rb_left = NULL,
},
},
};
full_binary_tree_root.rb_node = &full_binary_tree[0].rb;
/* Not a true RB tree but good for testing */
struct number_node linear_binary_tree[] = {
{
.v = 0,
.rb = {
.__rb_parent_color = mk_par(NULL, RB_BLACK),
.rb_right = NULL,
.rb_left = &linear_binary_tree[1].rb,
},
},
{
.v = 1,
.rb = {
.__rb_parent_color = mk_par(&linear_binary_tree[0].rb, RB_RED),
.rb_right = &linear_binary_tree[2].rb,
.rb_left = NULL,
},
},
{
.v = 2,
.rb = {
.__rb_parent_color = mk_par(&linear_binary_tree[1].rb, RB_BLACK),
.rb_right = NULL,
.rb_left = NULL,
},
},
};
linear_binary_tree_root.rb_node = &linear_binary_tree[0].rb;
(void)&empty_tree_root;
(void)&singular_tree_root;
(void)&full_binary_tree_root;
/* We want to give gdb a core dump to work with */
abort();
return 0;
}