73 lines
3.0 KiB
C
73 lines
3.0 KiB
C
#include "c_LinearProbingHashST.h"
|
|
#include "c_Test.h"
|
|
#include <stdlib.h>
|
|
#include <stdio.h>
|
|
|
|
static int lp_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_LinearProbingHashST_ClusterDeleteFlow) {
|
|
c_LinearProbingHashST_t lp_st;
|
|
|
|
// 初始化物理容量仅为 4 的密集探测哈希表，强迫其触发高频扩容与线性碰撞
|
|
c_err_t err = c_LinearProbingHashST_Init(&lp_st, 4, sizeof(char), sizeof(int), lp_compare_chars, NULL, &c_DefaultAllocator);
|
|
ASSERT_INT_EQ(C_ERR_OK, err);
|
|
|
|
char key_A = 'A'; int val_A = 100;
|
|
char key_B = 'B'; int val_B = 200;
|
|
char key_C = 'C'; int val_C = 300;
|
|
|
|
// 1. Put 添加行为断言
|
|
ASSERT_INT_EQ(C_ERR_OK, c_LinearProbingHashST_Put(&lp_st, &key_A, &val_A));
|
|
ASSERT_INT_EQ(C_ERR_OK, c_LinearProbingHashST_Put(&lp_st, &key_B, &val_B));
|
|
ASSERT_INT_EQ(C_ERR_OK, c_LinearProbingHashST_Put(&lp_st, &key_C, &val_C));
|
|
ASSERT_INT_EQ(3, (int)lp_st.size);
|
|
|
|
// 2. Overwrite 相同键覆写更新测试
|
|
int update_val_B = 999;
|
|
ASSERT_INT_EQ(C_ERR_OK, c_LinearProbingHashST_Put(&lp_st, &key_B, &update_val_B));
|
|
int get_verify = 0;
|
|
ASSERT_INT_EQ(C_ERR_OK, c_LinearProbingHashST_Get(&lp_st, &key_B, &get_verify));
|
|
ASSERT_INT_EQ(999, get_verify);
|
|
|
|
// 3. 🌟【硬核断言】：摘除处于连续碰撞探测中央、扮演“桥梁”角色的元素 'B'
|
|
// 修复后的代码由于触发了级联 Cluster 重新散列，'C' 节点会被安全的重新插入，探测绝不断裂！
|
|
ASSERT_INT_EQ(C_ERR_OK, c_LinearProbingHashST_Delete(&lp_st, &key_B));
|
|
ASSERT_INT_EQ(2, (int)lp_st.size);
|
|
ASSERT_TRUE(!c_LinearProbingHashST_Contains(&lp_st, &key_B));
|
|
|
|
// 4. 终极断言：桥梁断裂后，后方的 C 元素依然必须完好无损、可以被常数级 Get 命中！
|
|
ASSERT_INT_EQ(C_ERR_OK, c_LinearProbingHashST_Get(&lp_st, &key_C, &get_verify));
|
|
ASSERT_INT_EQ(300, get_verify);
|
|
|
|
c_LinearProbingHashST_Destroy(&lp_st);
|
|
}
|
|
|
|
TEST_CASE(test_c_LinearProbingHashST_ParamConstraints) {
|
|
c_LinearProbingHashST_t local_lp;
|
|
c_LinearProbingHashST_Init(&local_lp, 8, sizeof(char), sizeof(int), lp_compare_chars, NULL, NULL);
|
|
|
|
char k = 'Z'; int v = 55;
|
|
// 5. 验证拦截机制
|
|
ASSERT_INT_EQ(C_ERR_PARAM, c_LinearProbingHashST_Init(NULL, 8, sizeof(char), sizeof(int), lp_compare_chars, NULL, NULL));
|
|
ASSERT_INT_EQ(C_ERR_PARAM, c_LinearProbingHashST_Put(NULL, &k, &v));
|
|
ASSERT_INT_EQ(C_ERR_EMPTY, c_LinearProbingHashST_Delete(&local_lp, &k)); // 空仓删除安全抛出 C_ERR_EMPTY
|
|
|
|
c_LinearProbingHashST_Destroy(&local_lp);
|
|
}
|
|
|
|
// ==========================================
|
|
// 5. 主集成入口
|
|
// ==========================================
|
|
int main(void) {
|
|
TEST_START(C_LinearProbingHashST_Isolated_TestSuite);
|
|
RUN_TEST(test_c_LinearProbingHashST_ClusterDeleteFlow);
|
|
RUN_TEST(test_c_LinearProbingHashST_ParamConstraints);
|
|
TEST_REPORT();
|
|
return (g_test_registry.failed_count > 0 ? 1 : 0);
|
|
} |