antirez / antirez/rax

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

オープン
#29 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る
主要言語
C
スター
1.3k
フォーク
177
PR マージ指標
30日以内にマージされた PR はありません

説明

in file rax.c, the comment within function `raxRemove` claims the following:
```c++
* 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".

```c++
// 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

コントリビューションガイド

このリポジトリのコントリビューションガイドは索引されていません

評価

この issue はまだ評価されていません。

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。