rax.h raxRemove recompression not working as expected (redirect from redis project)
- Dominant language
- C
- Stars
- 1.3k
- Forks
- 177
- PR merge metrics
- No merged PRs in 30d
Description
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
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.