forked from gozfree/gear-lib
-
Notifications
You must be signed in to change notification settings - Fork 0
/
test_librbtree.c
141 lines (122 loc) · 3.83 KB
/
test_librbtree.c
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
/*****************************************************************************
* Copyright (C) 2014-2015
* file: test_librbtree.c
* author: gozfree <gozfree@163.com>
* created: 2015-08-10 22:35
* updated: 2015-08-10 22:35
*****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <libgzf.h>
#include "librbtree.h"
#ifndef false
#define false (0)
#endif
#ifndef true
#define true (!(false))
#endif
struct my_rbnode {
struct rb_node node;
int key;
};
struct rb_root mytree = RB_ROOT;
struct rb_root mytree_uk = RB_ROOT;
struct my_rbnode *my_search(struct rb_root *root, int val)
{
struct rb_node *node = root->rb_node;
while (node) {
struct my_rbnode *data = container_of(node, struct my_rbnode, node);
int result;
result = val - data->key;
if (result < 0)
node = node->rb_left;
else if (result > 0)
node = node->rb_right;
else
return data;
}
return NULL;
}
int my_insert(struct rb_root *root, struct my_rbnode *data)
{
struct rb_node **new = &(root->rb_node), *parent = NULL;
/* Figure out where to put new node */
while (*new) {
struct my_rbnode *this = container_of(*new, struct my_rbnode, node);
int result = (data->key - this->key);
parent = *new;
if (result < 0)
new = &((*new)->rb_left);
// else if (result > 0)
else
new = &((*new)->rb_right);
// else
// return false;
}
/* Add new node and rebalance tree. */
rb_link_node(&data->node, parent, new);
rb_insert_color(&data->node, root);
return true;
}
int input1[] = {-84,170,-85,142,-17,41,170,-85,-17,-71,170,152,-31,161,22,104,-85,160,120,-31,144,115};
int input2[] = {-84,-84,-84,-84,-84,-84,-84,-84,-84,-84,-84,-84,-84,-84,-84,-84,-84,-84,};
int input3[] = {170,-85,170,-85,170,-85,170,-85,170,-85,170,-85,170,-85,170,-85,170,-85,170,-85,170,-85};
int input4[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
static void test(struct rb_root *mytree, int *input, size_t len)
{
struct my_rbnode *entry;
struct rb_node *node;
int res;
int i;
for (i = 0; i < len; i++) {
struct my_rbnode *entry = CALLOC(1, struct my_rbnode);
entry->key = input[i];
res = my_insert(mytree, entry);
printf("insert %d: %d, res %d\n", i, input[i], res);
if (res == false) {
free(entry);
}
}
// test rb_next
printf("RB_NEXT========================\n");
node = rb_first(mytree);
i = 0;
while (node) {
entry = rb_entry(node, struct my_rbnode, node);
printf("%d: %d\n", i++, entry->key);
node = rb_next(node);
}
printf("\n");
// test rb_prev & rb_last
printf("RB_PREV========================\n");
i = 0;
node = rb_last(mytree);
while (node) {
entry = rb_entry(node, struct my_rbnode, node);
printf("%d: %d\n", i++, entry->key);
node = rb_prev(node);
}
printf("\n");
i = 0;
printf("RB_ERASE========================\n");
//test rb_erase
while (!RB_EMPTY_ROOT(mytree)) {
node = rb_first(mytree);
entry = rb_entry(node, struct my_rbnode, node);
printf("%d: %d\n", i++, entry->key);
rb_erase(node, mytree);
free(entry);
}
}
int main(int argc, char **argv)
{
printf("input 1=====================\n");
test(&mytree_uk, input1, (sizeof(input1)/sizeof(input1[0])));
printf("input 2=====================\n");
test(&mytree_uk, input2, (sizeof(input2)/sizeof(input2[0])));
printf("input 3=====================\n");
test(&mytree_uk, input3, (sizeof(input3)/sizeof(input3[0])));
printf("input 4=====================\n");
test(&mytree_uk, input4, (sizeof(input4)/sizeof(input4[0])));
return 0;
}