伪代码

flow.c

#define HEAD_DEFAULT_SIZE 64 // 表头节点数组的默认最大长度
#define BODY_DEFAULT_SIZE 64 // 尾随节点数组的默认最大长度
#define COLD_HEAD_THRES 16 // 冷块阈值
#define COLD_BODY_THRES 16 // 冷块阈值
#define ID_PREFIX 256 * 256 * 256 // ID 的前缀，由指纹的后缀决定
#define ID_SUFFIX 256 // ID 的后缀，由前缀的出现次数决定；递增。
// 以上的值均需要调整

// 指纹尾为00的表头节点
struct Headnode {
    unsigned long long fp; //160b?
    struct Bodynode* bnp; // 32b/48b?
    unsigned int body_len; // 数组中已存的尾随节点个数 32b
    unsigned int body_size; // 数组中总共可存的最大的尾随节点个数 32b
    unsigned int cold_body_num; // 数组中的冷块个数 32b
    unsigned short heat; // 热度
};

// 其他节点
struct Bodynode {
    unsigned int id; // 32b
    unsigned short heat; // 热度 16b
};

int main() {
    // TODO 新建表头数组
    while (新的写入操作){
        // TODO 获得数据
        // TODO 获得地址
        // TODO 对分块计算指纹;

        if (该节点是表头) {
            // TODO 记录当前表头地址
            for (遍历表头数组) {
                if (指纹匹配) {
                    // TODO 增加热度
                    if (该表头没有尾随数组)
                        // TODO 构造新的尾随节点数组
                    else {
                        for (遍历该表头的所有尾随节点) {
                            // TODO 把 cur_head->bnp[j] 放入 Cache
                            // TODO bnp[j] 热度减1，检查是否变冷，记录第一个冷块位置
                        }
                    }
                }
                // headnode + i 热度减1，检查是否变冷
                else {
                    // TODO 表头热度减小
                    // TODO 如果低于冷块阈值，修改 cold_head_num ，记录第一个冷块位置
                }
            }
            if (未找到匹配) {
                // TODO 把新的 headnode 放到第一个冷块的位置；如果没有，附加一个 headnode 项
                // TODO 把该块数据写入硬盘
            }
        }
        else {
            // 该节点是尾随节点
            while (搜索 Cache) {
                if (maptable 中存在该块对应的指纹前缀) {
                    // TODO 命中，增加热度
                }
            }
            if (maptable 没找到对应的指纹前缀) {
                // TODO 在 maptable 中增加这个块
                // TODO 把新的 bodynode 放到冷块的位置；如果没有，附加一个 bodynode 项
                // TODO 把该块数据写入硬盘
            }
        }

        /**** 后续处理 *****/

        // 清理冷的 headnode
        if (冷的表头超过一半) {
            // TODO 创建新的表头数组，长度为热块数量的两倍
        }
        // 清理冷的 bodynode
        if (冷的尾随节点超过一半) {
            // TODO 在当前表头下创建新的尾随数组，长度为热块数量的两倍
        }
        // 表头节点扩容
        if (表头数组已满) {
            // TODO 创建新的表头数组，长度为原来的两倍
        }
        // 尾随节点扩容
        if (尾随数组已满) {
            // TODO 创建新的尾随数组，长度为原来的两倍
        }
    }
}