cKit/Search/c_SeparateChainingHashST.c

#include <c_SeparateChainingHashST.h>

/**
 * @brief 工业级无符号泛型去偏差多项式哈希映射机
 *
 * 采用经典常数乘子 31 逐字节滚动翻滚，完美离散任何变长扁平结构体或内置基础类型
 */
C_STATIC_FORCE_INLINE
c_size_t c_SeparateChainingHashST_HashEngine(const void* key, c_size_t key_size) {
    const unsigned char* bytes = (const unsigned char*)key;
    c_size_t hash = 0;
    for (c_size_t i = 0; i < key_size; i++) {
        hash = 31 * hash + bytes[i];
    }
    return hash;
}

/**
 * @brief 内部辅助：通过哈希码安全计算对应的无符号桶插槽物理下标位置
 */
C_STATIC_FORCE_INLINE
c_size_t c_SeparateChainingHashST_GetBucketSlot(const c_SeparateChainingHashST_t* self, const void* key) {
    c_size_t code = c_SeparateChainingHashST_HashEngine(key, self->key_size);
    // 纯无符号按位安全取模，物理屏蔽符号位回绕风险
    return code % self->m_buckets;
}

/**
 * @brief 就地初始化拉链法哈希映射表
 *
 * @param initial_buckets 哈希桶（拉链容量）的总基数 M。建议传入质数（如 97, 997, 8191）以获得最佳离散度
 */
c_err_t c_SeparateChainingHashST_Init(c_SeparateChainingHashST_t* self, c_size_t initial_buckets, c_size_t key_size, c_size_t val_size, c_SortCompare_t key_cmp, void* args, c_Allocator_t* allocator) {
    if (!self || initial_buckets == 0 || key_size == 0 || val_size == 0 || !key_cmp) {
        return C_ERR_PARAM;
    }

    if (allocator) {
        self->allocator = *allocator;
    } else {
        self->allocator = c_DefaultAllocator;
    }

    self->m_buckets = initial_buckets;
    self->size = 0;
    self->key_size = key_size;
    self->val_size = val_size;
    self->key_cmp = key_cmp;
    self->args = args;

    // 前置无符号乘法整数溢出防御审计
    if (((c_size_t)-1) / sizeof(c_SeqSearchST_t) < initial_buckets) {
        return C_ERR_NOMEM;
    }

    // 一次性静态分配 M 个桶的符号表控制头空间
    self->buckets = (c_SeqSearchST_t*)c_Allocator_Alloc(&self->allocator, initial_buckets * sizeof(c_SeqSearchST_t));
    if (!self->buckets) {
        return C_ERR_NOMEM;
    }

    // 逐个串联并初始化每个桶内部的单链表控制流，强力绑定统一的组合分配器
    for (c_size_t i = 0; i < initial_buckets; i++) {
        c_SeqSearchST_Init(&(self->buckets[i]), key_size, val_size, key_cmp, args, &self->allocator);
    }

    return C_ERR_OK;
}

/**
 * @brief 存入键值对（均摊常数项时间复杂度 O(1)）
 *
 * 如果键已存在于特定拉链桶中则覆写更新；若不存在则头插法压入新节点并刷新全局计数
 */
c_err_t c_SeparateChainingHashST_Put(c_SeparateChainingHashST_t* self, const void* key, const void* val) {
    if (!self || !key || !val) return C_ERR_PARAM;

    // 1. 利用哈希映射机瞬间定位到目标桶
    c_size_t slot = c_SeparateChainingHashST_GetBucketSlot(self, key);
    c_SeqSearchST_t* bucket_st = &(self->buckets[slot]);

    // 2. 顺序探查该拉链。前置提取原拉链大小，用来判别本次操作是“新增”还是“修改覆写”
    c_size_t old_bucket_size = bucket_st->size;

    c_err_t err = c_SeqSearchST_Put(bucket_st, key, val);
    if (err == C_ERR_OK) {
        // 如果引发了当前单链桶节点的空间膨胀，说明是新键插入，递增全局计数
        if (bucket_st->size > old_bucket_size) {
            self->size++;
        }
    }

    return err;
}

/**
 * @brief 依据指定 Key 精准存取读取关联的 Value（均摊常数时间复杂度 O(1)）
 */
c_err_t c_SeparateChainingHashST_Get(const c_SeparateChainingHashST_t* self, const void* key, void* out_val) {
    if (!self || !key || !out_val) return C_ERR_PARAM;
    if (self->size == 0) return C_ERR_EMPTY;

    c_size_t slot = c_SeparateChainingHashST_GetBucketSlot(self, key);
    // 穿透调用单向顺序表的 Get 接口
    return c_SeqSearchST_Get(&(self->buckets[slot]), key, out_val);
}

/**
 * @brief 检查哈希表内是否有效包含指定的 Key
 */
bool c_SeparateChainingHashST_Contains(const c_SeparateChainingHashST_t* self, const void* key) {
    if (!self || !key || self->size == 0) return false;
    c_size_t slot = c_SeparateChainingHashST_GetBucketSlot(self, key);
    return c_SeqSearchST_Contains(&(self->buckets[slot]), key);
}

/**
 * @brief 从指定的哈希桶拉链中斩断并彻底移出其关联的符号对
 */
c_err_t c_SeparateChainingHashST_Delete(c_SeparateChainingHashST_t* self, const void* key) {
    if (!self || !key) return C_ERR_PARAM;
    if (self->size == 0) return C_ERR_EMPTY;

    c_size_t slot = c_SeparateChainingHashST_GetBucketSlot(self, key);
    c_SeqSearchST_t* bucket_st = &(self->buckets[slot]);

    c_err_t err = c_SeqSearchST_Delete(bucket_st, key);
    if (err == C_ERR_OK) {
        self->size--; // 递减总容量计数
    }
    return err;
}

/**
 * @brief 反初始化：级联彻底清理销毁全部哈希桶拉链，原路逆向回收堆空间
 */
void c_SeparateChainingHashST_Destroy(c_SeparateChainingHashST_t* self) {
    if (!self || !self->buckets) return;

    // 1. 迫使每个哈希拉链桶先链式释放其内部的单链物理节点
    for (c_size_t i = 0; i < self->m_buckets; i++) {
        c_SeqSearchST_Destroy(&(self->buckets[i]));
    }

    // 2. 回收哈希桶外壳控制头数组本身
    c_Allocator_Free(&self->allocator, self->buckets);
    self->buckets = NULL;
    self->size = 0;
    self->m_buckets = 0;
}