Skip to content

fix zslGetRank bug#4032

Closed
berg223 wants to merge 1 commit into
redis:unstablefrom
berg223:fix_zslGetElementByRank
Closed

fix zslGetRank bug#4032
berg223 wants to merge 1 commit into
redis:unstablefrom
berg223:fix_zslGetElementByRank

Conversation

@berg223

@berg223 berg223 commented Jun 3, 2017 •
edited
Loading

Copy link
Copy Markdown
Contributor

Issue:
This PR is a fix for #3081

Reproduce Step:
The following code has printed 1 instead of 0.

// file name: test_t_zset.c
#include "server.h"
#include <stdio.h>
    
int main()
{       
        zskiplist* zsl = zslCreate();
        zslInsert(zsl, 2, sdsnewlen("test", 4));
        zslInsert(zsl, 4, sdsnewlen("test", 4));
        int res = zslGetRank(zsl, 3, sdsnewlen("test", 4));
        printf("%d\n", res);
        zslFree(zsl);
        return 0;
}

To compile and run this piece of code. You can:

  1. change main() to any other name in server.c
  2. add test_t_zset.o to REDIS_SERVER_OBJ.
  3. make -f Makefile
  4. run redis-server

@antirez

antirez commented Mar 17, 2018

Copy link
Copy Markdown
Contributor

Hello, the code assumes that repeating elements are impossible.

@berg223 berg223 closed this Sep 11, 2018
@dvoprm

dvoprm commented Aug 5, 2020 •
edited
Loading

Copy link
Copy Markdown 
#include "server.h"
#include <stdio.h>
    
int main()
{       
        zskiplist* zsl = zslCreate();
        zslInsert(zsl, 2, sdsnewlen("2", 1));
        zslInsert(zsl, 4, sdsnewlen("4", 1));
        int res = zslGetRank(zsl, 3, sdsnewlen("2", 1));
        printf("%d\n", res);
        zslFree(zsl);
        return 0;
}

x stops at a point when x->level[i].forward->score=4 > 3 and x -> score=2 < 3.
("2", 1) is equal to ("2", 1), then the rank is returned, even though the score does not match.

@oranagra

oranagra commented Aug 16, 2020

Copy link
Copy Markdown
Member

@xiaocairush i don't see any reason not to fix this (despite not currently being reachable in redis).
mind re-opening the PR?

@berg223

berg223 commented Sep 1, 2020 •
edited
Loading

Copy link
Copy Markdown
Contributor Author

@oranagra I'm glad to hear that u want re-opening the PR! And I will continue to pay attention to this issue if need!

@yangbodong22011

yangbodong22011 commented Jul 13, 2021

Copy link
Copy Markdown
Contributor

I also agree to fix this (skiplist itself should remain independent and complete, that is, to allow the existence of repeated elements)
pls reopen and merge this PR @oranagra @xiaocairush

@oranagra oranagra mentioned this pull request Jul 18, 2021
Merged
@oranagra

oranagra commented Jul 18, 2021

Copy link
Copy Markdown
Member

i couldn't reopen this, so created another PR.

oranagra added a commit that referenced this pull request Jul 22, 2021
@oranagra @berg223
fix zslGetRank bug in dead-code (#9246)
9ca5e8c 
This fixes an issue with zslGetRank which will happen only if the
skiplist data stracture is added two entries with the same element name,
this can't happen in redis zsets (we use dict), but in theory this is a
bug in the underlaying skiplist code.

Fixes #3081 and #4032

Co-authored-by: minjian.cai <cmjgithub@163.com>
JackieXie168 pushed a commit to JackieXie168/redis that referenced this pull request Sep 8, 2021
@oranagra @berg223
fix zslGetRank bug in dead-code (redis#9246)
d8961e7 
This fixes an issue with zslGetRank which will happen only if the
skiplist data stracture is added two entries with the same element name,
this can't happen in redis zsets (we use dict), but in theory this is a
bug in the underlaying skiplist code.

Fixes redis#3081 and redis#4032

Co-authored-by: minjian.cai <cmjgithub@163.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

5 participants

@berg223 @antirez @dvoprm @oranagra @yangbodong22011