图形学图像处理【免费下载链接】mupdfmupdf mirror项目地址https://gitcode.com/gh_mirrors/mu/mupdf点击查看免费下载导读本文聚焦 MuPDF 核心图形库 Fitz即fz前缀来源内置的两套通用数据结构固定长度键哈希表fz_hash_table与字符串到值映射的自平衡二叉树fz_treeAA-tree。这两套结构是 MuPDF 内部文档缓存store、PDF 资源索引、归档文件archive与 HTML 图片去重等高频场景的底层支撑。读完本文你将掌握两套结构的全部公开 API、引用计数语义、扩容/删除等底层行为并能直接在基于 MuPDF 的 C 程序中正确使用它们。概述MuPDF 中的通用数据结构MuPDF 的文档渲染管线中充斥着大量键值查找需求按对象句柄查找缓存条目、按资源编号查找字体/颜色空间/图像、按文件名查找归档内条目、按图片 id 去重等。与其为每种场景各写一套Fitz 内核提供了两个通用容器fz_hash_table固定长度键fixed-length keys的通用哈希表见头文件 include/mupdf/fitz/hash.hfz_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.cCRC32C 的具体查表实现位于 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_ARGUMENThash 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-treeArne 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 archivefz_new_tree_archive直接以fz_tree为底层存储将文件名映射到fz_bufferhas_entry/read_entry/open_entry均通过fz_tree_lookup实现添加条目时用fz_tree_insert更新根节点销毁时用fz_drop_tree(ctx, tree, drop_tree_archive_entry)释放每个 buffersource/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_tablefz_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 插件代码的前提。赞分享图形学图像处理【免费下载链接】mupdfmupdf mirror项目地址https://gitcode.com/gh_mirrors/mu/mupdf点击查看免费下载相关推荐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即时通讯后端本地部署语音上一篇Effect HttpApi 类型化响应头实战指南WithHeaders、encodeToWithHeaders 与响应头覆盖语义下一篇Open-Meteo 免费天气 API 实战Docker 一行命令跑通气象数据服务创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考