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

Aperta
#29 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
3/5
Tempo stimato
1-2 giorni
Idoneità per principianti
45/100
Tipo di issue
Bug
Chiarezza
Specificata chiaramente
Stato di attività
Ferma
Stack tecnologico
c
Ambito
backend

Direzione di ricerca

Inizia in rax.c dalla funzione raxRemove e analizza la logica di trycompress, in particolare i casi h->size == 0 e h->size == 1. Riproduci il problema inserendo foo, foobar e foobarzxc, quindi eliminando foobarzxc e foobar. Il lavoro è completato quando l’albero rimanente viene ricompresso nella rappresentazione del percorso foobarzxc prevista.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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

Lingua principale
C
Stelle
1.3k
Fork
175
Metriche di merge delle PR
Nessuna PR unita negli ultimi 30g

Preparare l'ambiente

Questo progetto non fornisce container di sviluppo, Dockerfile né guida per i contributori, quindi l'ambiente è a tuo carico: parti dal suo README e consulta la nostra guida al primo contributo per i passaggi generali.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di antirez/rax

Tutte le issue di antirez/rax

Issue simili

Altre issue su C

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.