1 #include "ktest.h"
2 #include <ktest/ktest_utils.h>
3
4 #include <common/unistd.h>
5 #include <common/kprint.h>
6 #include <common/bitree.h>
7 #include <common/errno.h>
8
9 #include <mm/slab.h>
10
11 struct test_value_t
12 {
13 uint64_t tv;
14 };
compare(void * a,void * b)15 static int compare(void *a, void *b)
16 {
17 if (((struct test_value_t *)a)->tv > ((struct test_value_t *)b)->tv)
18 return 1;
19 else if (((struct test_value_t *)a)->tv == ((struct test_value_t *)b)->tv)
20 return 0;
21 else
22 return -1;
23 }
24
release(void * value)25 static int release(void *value)
26 {
27 // kdebug("release");
28 return 0;
29 }
30
31 /**
32 * @brief 测试创建二叉树
33 *
34 * @return int
35 */
ktest_bitree_case1(uint64_t arg0,uint64_t arg1)36 static long ktest_bitree_case1(uint64_t arg0, uint64_t arg1)
37 {
38 int val;
39 // ========== 测试创建树
40 struct test_value_t *tv1 = (struct test_value_t *)kmalloc(sizeof(struct test_value_t), 0);
41 tv1->tv = 20;
42 struct bt_node_t *rn = bt_create_node(NULL, NULL, NULL, tv1);
43
44 assert(rn != NULL);
45 assert((int64_t)rn != (-EINVAL));
46 assert(rn->value == tv1);
47
48 struct bt_root_t *tree = bt_create_tree(rn, compare, release);
49 assert(tree != NULL);
50 assert(tree->bt_node == rn);
51 assert(tree->cmp == compare);
52 assert(tree->release == release);
53 assert(tree->size == 1);
54
55 // ========= 向树中插入数据10、30
56 struct test_value_t *tv2 = (struct test_value_t *)kmalloc(sizeof(struct test_value_t), 0);
57 assert(tv2 != NULL);
58 tv2->tv = 10;
59 {
60 int last_size = tree->size;
61 val = bt_insert(tree, tv2);
62 assert(val == 0);
63 assert(last_size + 1 == tree->size);
64 }
65 struct test_value_t *tv3 = (struct test_value_t *)kmalloc(sizeof(struct test_value_t), 0);
66 assert(tv3 != NULL);
67 tv3->tv = 30;
68 {
69 int last_size = tree->size;
70 val = bt_insert(tree, tv3);
71 assert(val == 0);
72 assert(last_size + 1 == tree->size);
73 }
74
75 // 检测树的形状
76 assert(((struct test_value_t *)tree->bt_node->left->value)->tv == tv2->tv);
77 assert(((struct test_value_t *)tree->bt_node->right->value)->tv == tv3->tv);
78
79 // ========= 查询结点
80 // 查询值为tv2的结点
81 struct bt_node_t *node2;
82 assert(bt_query(tree, tv2, (uint64_t*)(&node2)) == 0);
83 assert(node2 != NULL);
84 assert(node2->value == tv2);
85
86 // ========= 插入第4个结点：15
87 struct test_value_t *tv4 = (struct test_value_t *)kmalloc(sizeof(struct test_value_t), 0);
88 assert(tv4 != NULL);
89 tv4->tv = 15;
90 {
91 int last_size = tree->size;
92 val = bt_insert(tree, tv4);
93 assert(val == 0);
94 assert(last_size + 1 == tree->size);
95 }
96
97 assert(((struct test_value_t *)node2->right->value)->tv == tv4->tv);
98
99 // ======= 查询不存在的值
100 struct bt_node_t *node_not_exists;
101 struct test_value_t *tv_not_exists = (struct test_value_t *)kmalloc(sizeof(struct test_value_t), 0);
102 assert(tv_not_exists != NULL);
103 tv_not_exists->tv = 100;
104 assert(bt_query(tree, tv_not_exists, (uint64_t*)(&node_not_exists)) == -1);
105 // kdebug("node_not_exists.val=%d", ((struct test_value_t*)node_not_exists->value)->tv);
106 assert(node_not_exists == NULL);
107
108 // 删除根节点
109 assert(bt_delete(tree, rn->value) == 0);
110 assert(((struct test_value_t *)tree->bt_node->value)->tv != 20);
111 assert(tree->bt_node->right == NULL);
112
113 // 删除树
114 assert(bt_destroy_tree(tree) == 0);
115
116 return 0;
117 }
118
119 static ktest_case_table kt_bitree_func_table[] = {
120 ktest_bitree_case1,
121 };
122
ktest_test_bitree(void * arg)123 int ktest_test_bitree(void* arg)
124 {
125 kTEST("Testing bitree...");
126 for (int i = 0; i < sizeof(kt_bitree_func_table) / sizeof(ktest_case_table); ++i)
127 {
128 kTEST("Testing case %d", i);
129 kt_bitree_func_table[i](0, 0);
130 }
131 kTEST("bitree Test done.");
132 return 0;
133 }