antirez / antirez/rax

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

Open
#29 0 comments 0 reactions 0 assignees View on GitHub
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.