基于基数树的高并发内存池优

+-------------------+       +-------------------+
| 线程本地缓存（TLS）|       | 全局基数树（Global RT）|
| 每个线程独立实例   |       | 管理跨线程空闲块      |
| 基数树索引空闲块   |       | 支持快速查找/合并     |
+-------------------+       +-------------------+
          ↑                          ↓
          | 分配请求                | 批量申请/释放
          +-------------------------+

// 基数树节点结构体
typedef struct RadixTreeNode {
    uint64_t prefix_mask;  // 前缀掩码（如0xFFFFFFFFFFFF0000表示前48位）
    struct RadixTreeNode* children[2];  // 子节点指针（0/1分支）
    void** free_blocks;    // 空闲块列表（仅叶子节点有效）
    int block_count;       // 空闲块数量
    SpinLock lock;         // 细粒度自旋锁
} RadixTreeNode;

// 内存块元数据（存储在基数树叶节点）
typedef struct MemBlock {
    void* start_addr;      // 起始地址
    size_t size;           // 块大小
    bool is_free;          // 是否空闲
} MemBlock;

// 全局基数树分配函数
void* global_radix_alloc(GlobalRadixTree* tree, size_t size) {
    // 1. 计算对齐后的大小（向上取整到2的幂次）
    size_t aligned_size = align_to_power_of_two(size);
    
    // 2. 从根节点开始查找符合条件的空闲块
    RadixTreeNode* node = tree->root;
    while (node) {
        // 匹配当前节点的前缀（如起始地址的前48位）
        if ((aligned_size & node->prefix_mask) == (node->start_addr & node->prefix_mask)) {
            // 找到候选块，检查是否满足大小需求
            if (node->block_size >= aligned_size) {
                // 从空闲块列表中取出第一个块
                void* block = node->free_blocks[--node->block_count];
                if (node->block_count == 0) {
                    // 空闲块列表为空，删除当前节点
                    radix_tree_remove_node(tree, node);
                }
                return block;
            }
        }
        // 未匹配，进入子节点（根据地址的下一位选择分支）
        uint8_t bit = (aligned_size >> (64 - node->depth)) & 1;
        node = node->children[bit];
    }
    return NULL;  // 无可用空闲块
}

// 线程本地缓存填充函数
void fill_local_cache(ThreadCache* cache, void* block, size_t size) {
    // 1. 计算对齐后的大小和前缀掩码（如前24位）
    size_t aligned_size = align_to_power_of_two(size);
    uint64_t prefix_mask = ~(0xFFFFFFFFFFFFFFFF << 24);  // 前24位掩码
    
    // 2. 插入本地基数树
    RadixTreeNode* node = cache->local_tree.root;
    for (int i = 0; i < 24; i++) {  // 遍历前24位
        uint8_t bit = (block >> (64 - 24 + i)) & 1;
        if (!node->children[bit]) {
            node->children[bit] = create_radix_node();  // 创建新节点
        }
        node = node->children[bit];
    }
    // 3. 将块添加到叶节点的空闲列表
    node->free_blocks[node->block_count++] = block;
}

// 基数树释放函数
void radix_tree_free(RadixTree* tree, void* block, size_t size) {
    // 1. 计算对齐后的大小和前缀掩码
    size_t aligned_size = align_to_power_of_two(size);
    uint64_t prefix_mask = ~(0xFFFFFFFFFFFFFFFF << 24);  // 前24位掩码
    
    // 2. 查找相邻的空闲块（前缀匹配且地址连续）
    RadixTreeNode* parent = find_parent_node(tree, block);
    if (parent) {
        // 检查左邻块（地址-1）
        void* left_block = (void*)((uint64_t)block - aligned_size);
        RadixTreeNode* left_node = find_leaf_node(parent, left_block);
        if (left_node && left_node->is_free) {
            // 合并左邻块
            merge_blocks(parent, left_node, block, size);
        }
        
        // 检查右邻块（地址+size）
        void* right_block = (void*)((uint64_t)block + size);
        RadixTreeNode* right_node = find_leaf_node(parent, right_block);
        if (right_node && right_node->is_free) {
            // 合并右邻块
            merge_blocks(parent, block, right_block, size);
        }
    }
    
    // 3. 将当前块插入基数树
    insert_into_radix_tree(tree, block, size);
}

// 基数树插入操作（带锁保护）
void insert_into_radix_tree(RadixTree* tree, void* block, size_t size) {
    RadixTreeNode* node = tree->root;
    uint64_t addr = (uint64_t)block;
    uint64_t size_aligned = align_to_power_of_two(size);
    
    for (int i = 0; i < PREFIX_DEPTH; i++) {  // 遍历前缀深度（如24位）
        uint8_t bit = (addr >> (64 - PREFIX_DEPTH + i)) & 1;
        if (!node->children[bit]) {
            spin_lock(&node->lock);
            if (!node->children[bit]) {  // 双重检查避免竞态
                node->children[bit] = create_radix_node();
            }
            spin_unlock(&node->lock);
        }
        node = node->children[bit];
    }
    
    // 插入到叶节点的空闲列表（加锁保护）
    spin_lock(&node->lock);
    node->free_blocks[node->block_count++] = block;
    spin_unlock(&node->lock);
}