- 图形学
- 图像处理
【免费下载链接】mupdf
mupdf mirror
导读
本文聚焦 MuPDF 核心图形库 Fitz（即fz前缀来源）内置的两套通用数据结构：固定长度键哈希表（fz_hash_table）与字符串到值映射的自平衡二叉树（fz_tree，AA-tree）。这两套结构是 MuPDF 内部文档缓存（store）、PDF 资源索引、归档文件（archive）与 HTML 图片去重等高频场景的底层支撑。读完本文，你将掌握两套结构的全部公开 API、引用计数语义、扩容/删除等底层行为，并能直接在基于 MuPDF 的 C 程序中正确使用它们。
概述：MuPDF 中的通用数据结构
MuPDF 的文档渲染管线中充斥着大量"键值查找"需求：按对象句柄查找缓存条目、按资源编号查找字体/颜色空间/图像、按文件名查找归档内条目、按图片 id 去重等。与其为每种场景各写一套，Fitz 内核提供了两个通用容器：
fz_hash_table：固定长度键（fixed-length keys）的通用哈希表，见头文件 include/mupdf/fitz/hash.h；fz_tree：将文本字符串映射到任意值的自平衡二叉树（AA-tree 实现），见头文件 include/mupdf/fitz/tree.h。
两者均定义于 Fitz 核心层，通过 include/mupdf/fitz.h 随核心库一起暴露给上层模块使用。
哈希表fz_hash_table
设计要点
fz_hash_table是一个固定长度键的哈希表，即所有键必须具有相同的字节长度（创建时通过keylen参数指定）。键与值均不参与引用计数（not reference counted），由调用方负责在插入/移除时手动维护引用计数。
底层实现为开放寻址 + 线性探测（open addressing with linear probing）。与教科书实现不同，该实现支持正确删除条目而不会引发后续查找行为退化——源码注释明确强调这一点（见 source/fitz/hash.c）。删除时通过do_removal将后续冲突条目向前回填（backward shift），从而保持探测链连续。
哈希函数使用 CRC32C 校验和：hash()内部直接调用fz_crc32c(0, s, len)（见 source/fitz/hash.c），CRC32C 的具体查表实现位于 source/fitz/crc32.c。
创建与销毁
fz_hash_table *fz_new_hash_table(fz_context *ctx, int initial_size, int key_length, int lock, void (*drop_value)(fz_context *ctx, void *value)); void fz_drop_hash_table(fz_context *ctx, fz_hash_table *table);参数说明：
initial_size：初始桶数量。表在"约 80% 满"时会自动扩容为原来的两倍（load > size * 8 / 10触发fz_resize_hash，见 source/fitz/hash.c）。因此初始值不需要精确预估，只需合理即可。key_length：每个键的字节长度。键过长时构造函数会抛出FZ_ERROR_ARGUMENT（"hash table key length too large"）；单键上限为宏FZ_HASH_TABLE_KEY_LENGTH，值为 48（见 include/mupdf/fitz/hash.h）。lock：当前应传0（-1 亦可，语义见下文）。文档明确警告：传其他任何值都会导致不可预测的行为。从源码看（见 source/fitz/hash.c），该字段为-1时表示不加锁，非负时表示持有某个FZ_LOCK，且各操作会调用fz_assert_lock_held校验锁状态——普通用户直接传-1（无锁）即可。注意：fz_new_hash_table的lock参数是锁的索引值，0与-1的语义取决于 MuPDF 版本中的FZ_LOCK枚举，文档以"传零"为安全约定。drop_value：仅用于销毁整张表时释放每个值；插入/移除单个条目时不会调用它。可为NULL。
fz_drop_hash_table释放表空间，并对表中每个值调用drop_value（若非 NULL）后再释放条目数组与表结构本身（见 source/fitz/hash.c）。
查找与插入
void *fz_hash_find(fz_context *ctx, fz_hash_table *table, const void *key); void *fz_hash_insert(fz_context *ctx, fz_hash_table *table, const void *key, void *value);fz_hash_find：返回键关联的值；未找到返回NULL。查找同样使用 CRC32C 定位并线性探测（见 source/fitz/hash.c）。fz_hash_insert：插入键值对。重复键不覆盖旧值——若键已存在，表保持不变并返回旧值指针；若首次插入，键被复制进表内、值所有权移交，返回NULL。不进行引用计数，调用方需自行fz_keep_*值。扩容检查（80% 负载阈值）也在此函数入口执行。
删除与遍历
void fz_hash_remove(fz_context *ctx, fz_hash_table *table, const void *key); void fz_hash_for_each(fz_context *ctx, fz_hash_table *table, void *state, void (*callback)(fz_context *ctx, void *state, void *key, int key_length, void *value));fz_hash_remove：按键移除条目。不释放值（不引用计数），调用方需自行释放。若键不存在，会打印一条警告"assert: remove non-existent hash entry"（见 source/fitz/hash.c）。fz_hash_for_each：对表中每个键值对调用回调。回调签名含key_length参数，便于在固定长度键下安全读取键内容；state为透传的任意上下文指针。遍历顺序即桶数组顺序，与插入顺序无关。
头文件中还提供了头文件中未在文档中单独列出的fz_hash_filter：遍历并移除所有回调返回真的条目（同样不释放值），见 include/mupdf/fitz/hash.h 与 source/fitz/hash.c。
典型用例：MuPDF 内部缓存与资源索引
从源码调用点可以看出这套哈希表承担的核心职责：
- 文档存储缓存：
fz_store用fz_new_hash_table(ctx, 4096, sizeof(fz_store_hash), FZ_LOCK_ALLOC, NULL)建立缓存索引（source/fitz/store.c），并按需fz_hash_insert/fz_hash_remove维护条目（source/fitz/store.c、source/fitz/store.c）。 - PDF 资源表：PDF 文档的字体、颜色空间、图像资源分别建表，键为
sizeof(*key)的结构体，值为 PDF 对象，并使用pdf_drop_obj_as_void作为销毁回调（source/pdf/pdf-resources.c）。 - 颜色空间换算缓存：
colorspace.c中以n * sizeof(float)的浮点数组为键缓存 ICC 换算结果，并使用fz_free释放值（source/fitz/colorspace.c）；颜色转换的 lookup 表也以509为初始桶数建表（source/fitz/colorspace.c）。
自平衡二叉树fz_tree
设计要点
fz_tree是将文本字符串映射到值的自平衡二叉查找树，实现为AA-tree（Arne Andersson 树）：每个节点带level字段，通过skew（左倾修正）与split（层级提升）两种旋转操作维持平衡（见 source/fitz/tree.c）。头文件注释将其概括为 "AA-tree to look up things by strings"（见 include/mupdf/fitz/tree.h）。
关键语义：
- 查找使用
strcmp做简单指针等价比较（source/fitz/tree.c）； - 插入时不复制键内容，也不复制值——节点仅保存
key与value的指针（源码中key实际通过fz_strdup复制，见 source/fitz/tree.c，因此调用方无需为键的生命周期负责；值则仅存指针，由调用方保证存活）。文档层面以"键和值仅作为指针被保存"表述。
无构造函数：根节点即树
fz_tree没有构造函数——不存在"包含根"的容器结构。树的根节点就是fz_tree*本身，初始为空树时直接使用NULL，插入函数返回新的根节点，因此调用方必须用返回值不断更新根指针。
fz_tree *tree = NULL; tree = fz_tree_insert(ctx, tree, "A", my_a_obj); tree = fz_tree_insert(ctx, tree, "B", my_b_obj); tree = fz_tree_insert(ctx, tree, "C", my_c_obj); assert(fz_tree_lookup(ctx, tree, "B") == my_b_obj);注意：插入后必须将返回值赋回根变量，否则后续操作可能基于过期的根节点。同时不要插入重复键（重复插入同一键时strcmp == 0的节点会走右分支继续插入，可能产生语义不明的重复节点，文档明确要求避免）。
查找与销毁
void *fz_tree_lookup(fz_context *ctx, fz_tree *node, const char *key); void fz_drop_tree(fz_context *ctx, fz_tree *node, void (*dropfunc)(fz_context *ctx, void *value));fz_tree_lookup：按字符串查找，命中返回对应值，否则返回NULL。查找过程沿左右子树下降（见 source/fitz/tree.c）。fz_drop_tree：递归释放整棵树。先释放左右子树，再释放节点键副本，并对每个值调用dropfunc（可传NULL跳过值的释放），最后释放节点本身（见 source/fitz/tree.c）。
典型用例：内存归档与 HTML 资源去重
- 内存归档（tree archive）：
fz_new_tree_archive直接以fz_tree为底层存储，将文件名映射到fz_buffer；has_entry/read_entry/open_entry均通过fz_tree_lookup实现，添加条目时用fz_tree_insert更新根节点，销毁时用fz_drop_tree(ctx, tree, drop_tree_archive_entry)释放每个 buffer（source/fitz/archive.c）。 - EPUB 元数据查重：epub 文档用
fz_tree_lookup判断条目是否已存在、以fz_tree_insert累积信息，并以NULL作为 dropfunc 销毁（source/html/epub-doc.c）。 - HTML 图片去重：HTML 解析器以图片 id 为键、
fz_image*为值建树，销毁时以fz_drop_image作为 dropfunc 统一释放（source/html/html-parse.c、source/html/html-parse.c）。
哈希表 vs 二叉树：如何选择
| 维度 | fz_hash_table | fz_tree |
|---|---|---|
| 键类型 | 任意固定长度字节（keylen指定） | C 字符串（strcmp比较） |
| 结构 | 开放寻址线性探测哈希表 | 自平衡 AA-tree |
| 查找复杂度 | 平均 O(1)，冲突时线性探测 | O(log n) |
| 重复键 | 插入返回旧值、不覆盖 | 禁止插入重复键 |
| 引用计数 | 均不计数，调用方自理 | 均不计数，调用方自理 |
| 销毁回调 | 构造函数传入drop_value | 销毁时传入dropfunc |
| 扩容 | 80% 负载自动翻倍 | 无容量概念，动态插入 |
| 典型用途 | 文档缓存 store、PDF 资源表、颜色换算缓存 | 内存归档、HTML/EPUB 资源去重 |
两条选择建议：
- 键是定长二进制结构（如对象句柄、
struct或固定长度数组）时优先fz_hash_table； - 键是文本名称/路径（如文件名、图片 id、URI）且需要按字典序遍历能力时优先
fz_tree。
两者均要求调用方管理值的引用计数：插入前fz_keep_*、移除或销毁时fz_drop_*（或通过 drop 回调），这是使用 MuPDF 容器最需要注意的约定。
总结
fz_hash_table与fz_tree是 MuPDF Fitz 内核提供的两个轻量通用容器：前者以固定长度键 + 线性探测提供平均 O(1) 查找，并支持安全的删除与 80% 负载自动扩容；后者以 AA-tree 提供字符串键的 O(log n) 查找，且无需独立根结构。二者的头文件声明见 include/mupdf/fitz/hash.h 与 include/mupdf/fitz/tree.h，实现分别位于 source/fitz/hash.c 与 source/fitz/tree.c。在 MuPDF 的文档缓存、PDF 资源索引、内存归档与 HTML/EPUB 处理中，它们承担着高频键值查找的职责，理解其语义（尤其是不引用计数与重复键行为）是编写正确 MuPDF 插件代码的前提。
- 图形学
- 图像处理
【免费下载链接】mupdf
mupdf mirror
相关推荐
MuPDF Fitz 通用数据结构指南：fz_hash_table 定长键哈希表与 fz_tree 字符串键自平衡二叉树
MuPDF Fitz 通用数据结构指南：fz_hash_table 定长键哈希表与 fz_tree 字符串键自平衡二叉树 导读 本文以 ext/mupdf/do
桌面应用文档Hello Algorithm树结构：二叉树与平衡树详解
Hello Algorithm树结构：二叉树与平衡树详解 引言：为什么需要树结构？ 在日常编程中，我们经常需要处理具有层次关系的数据。想象一下文件系统、组织结构
教程文档示例工程教育OpenClaw 中文社区版新手教程：7 步 onboard 向导从零配置你的 AI 助手（附常见问题）
OpenClaw 中文社区版新手教程：7 步 onboard 向导从零配置你的 AI 助手（附常见问题） OpenClaw 中文社区版（openclaw cn）
人工智能AI Agent即时通讯后端本地部署语音
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
