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 }