返回主题:内置数据结构的底层实现

知识卡片

普通读书笔记卡 · 3566.k

删除基数树节点后复用

理解等级:中级

ngx_radix_tree_t 自行分配节点,节点的 value 只指向业务数据,无需把树节点嵌入业务结构。删除有子节点的前缀时,先清除该节点的值;只有剪下不再使用的叶及空祖先,才把节点挂到 free 单链表。后续建新节点优先复用,再从池中分配。容器封装了节点内存复用,但不保证每次删除都回收节点。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《深入理解Nginx:模块开发与架构解析(第2版)》第7章7.6.1(源文件:`_epub-src/EPUB/text00058.html`,图7-9 `Image00075.jpg`);[Nginx 1.8.0 `ngx_radix_tree.c`](https://github.com/nginx/nginx/blob/release-1.8.0/src/core/ngx_radix_tree.c)。 - 结论依据:原书列出pool、free、start、size字段,但“每次删除都入free”过于绝对;对应版本源码仅在无子节点且无值时剪枝,内部前缀节点删除只清值,分配函数优先取free。 - 原始内容:在添加新的节点时,会首先查看free中是否还有节点,如果free中有未使用的节点,则会优先使用,如果没有,就会再从pool内存池中分配新内存存储节点。