Skip to content

fix zslGetRank bug#4032

Closed
berg223 wants to merge 1 commit intoredis:unstablefrom
berg223:fix_zslGetElementByRank
Closed

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

Conversation

@berg223
Copy link
Contributor

@berg223 berg223 commented Jun 3, 2017 •
edited
Loading

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
Copy link
Contributor

antirez commented Mar 17, 2018

Hello, the code assumes that repeating elements are impossible.

@berg223 berg223 closed this Sep 11, 2018
@dvoprm
Copy link

dvoprm commented Aug 5, 2020 •
edited
Loading 

#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
Copy link
Member

oranagra commented Aug 16, 2020

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

@berg223
Copy link
Contributor Author

berg223 commented Sep 1, 2020 •
edited
Loading

@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
Copy link
Contributor

yangbodong22011 commented Jul 13, 2021

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
Copy link
Member

oranagra commented Jul 18, 2021

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 <[email protected]>
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 <[email protected]>
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