88 lines
3.2 KiB
C
88 lines
3.2 KiB
C
#include "c_BST.h"
|
||
#include "c_Test.h"
|
||
#include <stdlib.h>
|
||
#include <stdio.h>
|
||
|
||
static int bst_compare_chars(const void* a, const void* b, void* args) {
|
||
(void)args;
|
||
char char1 = *(const char*)a;
|
||
char char2 = *(const char*)b;
|
||
return char1 - char2;
|
||
}
|
||
|
||
|
||
|
||
TEST_CASE(test_c_BST_Dynamic_CRUD) {
|
||
c_BST_t tree;
|
||
// 就地初始化：将 char 作为 Key，int 作为 Value
|
||
c_err_t err = c_BST_Init(&tree, sizeof(char), sizeof(int), bst_compare_chars, NULL, &c_DefaultAllocator);
|
||
ASSERT_INT_EQ(C_ERR_OK, err);
|
||
|
||
// 故意以颠簸顺序插入，构造一个经典的非退化二叉平衡树拓扑
|
||
char key_M = 'M'; int val_M = 40;
|
||
char key_E = 'E'; int val_E = 20;
|
||
char key_S = 'S'; int val_S = 50;
|
||
char key_A = 'A'; int val_A = 10;
|
||
char key_R = 'R'; int val_R = 45;
|
||
|
||
ASSERT_INT_EQ(C_ERR_OK, c_BST_Put(&tree, &key_M, &val_M));
|
||
ASSERT_INT_EQ(C_ERR_OK, c_BST_Put(&tree, &key_E, &val_E));
|
||
ASSERT_INT_EQ(C_ERR_OK, c_BST_Put(&tree, &key_S, &val_S));
|
||
ASSERT_INT_EQ(C_ERR_OK, c_BST_Put(&tree, &key_A, &val_A));
|
||
ASSERT_INT_EQ(C_ERR_OK, c_BST_Put(&tree, &key_R, &val_R));
|
||
ASSERT_INT_EQ(5, (int)tree.size);
|
||
|
||
// 1. Get 状态命中读取验证
|
||
int get_val = 0;
|
||
ASSERT_INT_EQ(C_ERR_OK, c_BST_Get(&tree, &key_S, &get_val));
|
||
ASSERT_INT_EQ(50, get_val);
|
||
|
||
ASSERT_TRUE(c_BST_Contains(&tree, &key_R));
|
||
char key_X = 'X';
|
||
ASSERT_TRUE(!c_BST_Contains(&tree, &key_X));
|
||
|
||
// 2. Overwrite 相同键覆写更新审计
|
||
int update_val_M = 999;
|
||
ASSERT_INT_EQ(C_ERR_OK, c_BST_Put(&tree, &key_M, &update_val_M));
|
||
ASSERT_INT_EQ(5, (int)tree.size); // 大小锁死不能变
|
||
ASSERT_INT_EQ(C_ERR_OK, c_BST_Get(&tree, &key_M, &get_val));
|
||
ASSERT_INT_EQ(999, get_val);
|
||
|
||
// 3. Delete 深度极限压测：删除拥有双向子树的复杂中段根节点 'S'
|
||
// 修复后的 Hibbard 机制应当自动将 'R' 节点提升顶替上来，并原路释放 S 的内存
|
||
ASSERT_INT_EQ(C_ERR_OK, c_BST_Delete(&tree, &key_S));
|
||
ASSERT_INT_EQ(4, (int)tree.size);
|
||
ASSERT_INT_EQ(C_ERR_NOTFOUND, c_BST_Get(&tree, &key_S, &get_val));
|
||
|
||
// 确保与 S 共同历经剧变的邻居节点 R 依然在新树中完好驻留
|
||
ASSERT_INT_EQ(C_ERR_OK, c_BST_Get(&tree, &key_R, &get_val));
|
||
ASSERT_INT_EQ(45, get_val);
|
||
|
||
// 深度级联注销反初始化
|
||
c_BST_Destroy(&tree);
|
||
}
|
||
|
||
TEST_CASE(test_c_BST_ParamConstraints) {
|
||
c_BST_t local_tree;
|
||
c_BST_Init(&local_tree, sizeof(char), sizeof(int), bst_compare_chars, NULL, NULL); // 降格 Fallback
|
||
|
||
char k = 'Q';
|
||
int v = 77;
|
||
// 验证各类非法调用的拦截返回
|
||
ASSERT_INT_EQ(C_ERR_PARAM, c_BST_Init(NULL, sizeof(char), sizeof(int), bst_compare_chars, NULL, NULL));
|
||
ASSERT_INT_EQ(C_ERR_PARAM, c_BST_Put(NULL, &k, &v));
|
||
ASSERT_INT_EQ(C_ERR_EMPTY, c_BST_Delete(&local_tree, &k)); // 空树删除直接拦截抛出 C_ERR_EMPTY
|
||
|
||
c_BST_Destroy(&local_tree);
|
||
}
|
||
|
||
// ==========================================
|
||
// 5. 主集成入口
|
||
// ==========================================
|
||
int main(void) {
|
||
TEST_START(C_BinarySearchTreeST_Isolated_TestSuite);
|
||
RUN_TEST(test_c_BST_Dynamic_CRUD);
|
||
RUN_TEST(test_c_BST_ParamConstraints);
|
||
TEST_REPORT();
|
||
return (g_test_registry.failed_count > 0 ? 1 : 0);
|
||
} |