rax.h raxRemove recompression not working as expected (redirect from redis project)

未关闭
#29 0 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看

还没有人认领这个 Issue。

评估

难度
3/5
预计耗时
1-2 天
新手友好度
45/100
Issue 类型
缺陷
描述清晰度
描述清楚
活跃度
停滞
技术栈
c
领域
backend

调研方向

从 rax.c 中的 raxRemove 函数开始,检查 trycompress 逻辑,尤其是 h->size == 0 和 h->size == 1 的情况。插入 foo、foobar 和 foobarzxc,然后删除 foobarzxc 和 foobar,以重现该问题。当剩余的树被重新压缩为预期的 foobarzxc 路径表示时,即表示完成。

由索引模型根据 Issue 内容生成。

描述

in file rax.c, the comment within function raxRemove claims the following:

* Example of case "1". A tree stores the keys "FOO" = 1 and
     * "FOOBAR" = 2:
     *
     *
     * "FOO" -> "BAR" -> [] (2)
     *           (1)
     *
     * After the removal of "FOO" the tree can be compressed as:
     *
     * "FOOBAR" -> [] (2)
     *

However, the logic associated with variable trycompress didn't take compress node into account.
The two predicates if (h->size == 0) and else if (h->size == 1) don't catch the intermediate compress node obviously.

This demo shows the real scenario:

  1. insertion of key "foo", value 1.
  2. insertion of key "foobar", value 2.
  3. insertion of key "foobarzxc", value 3.
  4. deletion of key "foobarzxc".
  5. deletion of key "foobar".
// after 1/2/3
"foo" -> "bar"=0x7ffc7cbdb69c -> "zxc"=0x7ffc7cbdb64c -> []=0x7ffc7cbdb5fc
// after 4/5
"foo" -> "bar" -> "zxc" -> []=0x7ffc7cbdb5fc

Not "foobarzxc" -> []=0x7ffc7cbdb5fc as expected

Anyway, this only prolongs the recompression and no bug is incurred. @antirez

主要语言
C
星标
1.3k
派生
175
PR 合并指标
30 天内没有已合并 PR

环境准备

这个项目没有提供开发容器、Dockerfile 或贡献指南,环境需要你自己搭建:先看它的 README,通用步骤见我们的新手贡献指南。

从这里开始

  1. 先读完整个 Issue,再读项目的贡献指南。
  2. 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
  3. Fork 仓库,在一个分支上完成修改。
  4. 提交 Pull Request,并在描述里引用这个 Issue 编号。

antirez/rax 的其他 Issue

查看 antirez/rax 的全部 Issue

相似的 Issue

更多 C Issue

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。