antirez / antirez/rax

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

Ouverte
#29 0 commentaires 0 réactions 0 personnes assignées Voir sur GitHub
Langage dominant
C
Étoiles
1.3k
Forks
177
Métriques de merge des PR
Aucune PR mergée en 30 j

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

Guide de contribution

Aucun guide de contribution indexé pour ce dépôt

Évaluation

Cette issue n'a pas encore été évaluée.

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.