X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/7a6ae0a2b29f83523a6e65a61c7ec49cc9437781..0bd6d68e34bc41cd80cd7fc44aab9cf3884de8dc:/tests/unit/sort.tcl diff --git a/tests/unit/sort.tcl b/tests/unit/sort.tcl index 16a02b3a..5a181641 100644 --- a/tests/unit/sort.tcl +++ b/tests/unit/sort.tcl @@ -1,5 +1,105 @@ -start_server {tags {"sort"}} { - test {SORT ALPHA against integer encoded strings} { +start_server { + tags {"sort"} + overrides { + "list-max-ziplist-value" 16 + "list-max-ziplist-entries" 32 + "set-max-intset-entries" 32 + } +} { + proc create_random_dataset {num cmd} { + set tosort {} + set result {} + array set seenrand {} + r del tosort + for {set i 0} {$i < $num} {incr i} { + # Make sure all the weights are different because + # Redis does not use a stable sort but Tcl does. + while 1 { + randpath { + set rint [expr int(rand()*1000000)] + } { + set rint [expr rand()] + } + if {![info exists seenrand($rint)]} break + } + set seenrand($rint) x + r $cmd tosort $i + r set weight_$i $rint + r hset wobj_$i weight $rint + lappend tosort [list $i $rint] + } + set sorted [lsort -index 1 -real $tosort] + for {set i 0} {$i < $num} {incr i} { + lappend result [lindex $sorted $i 0] + } + set _ $result + } + + foreach {num cmd enc title} { + 16 lpush ziplist "Ziplist" + 1000 lpush linkedlist "Linked list" + 10000 lpush linkedlist "Big Linked list" + 16 sadd intset "Intset" + 1000 sadd hashtable "Hash table" + 10000 sadd hashtable "Big Hash table" + } { + set result [create_random_dataset $num $cmd] + assert_encoding $enc tosort + + test "$title: SORT BY key" { + assert_equal $result [r sort tosort BY weight_*] + } + + test "$title: SORT BY key with limit" { + assert_equal [lrange $result 5 9] [r sort tosort BY weight_* LIMIT 5 5] + } + + test "$title: SORT BY hash field" { + assert_equal $result [r sort tosort BY wobj_*->weight] + } + } + + set result [create_random_dataset 16 lpush] + test "SORT GET #" { + assert_equal [lsort -integer $result] [r sort tosort GET #] + } + + test "SORT GET " { + r del foo + set res [r sort tosort GET foo] + assert_equal 16 [llength $res] + foreach item $res { assert_equal {} $item } + } + + test "SORT GET (key and hash) with sanity check" { + set l1 [r sort tosort GET # GET weight_*] + set l2 [r sort tosort GET # GET wobj_*->weight] + foreach {id1 w1} $l1 {id2 w2} $l2 { + assert_equal $id1 $id2 + assert_equal $w1 [r get weight_$id1] + assert_equal $w2 [r get weight_$id1] + } + } + + test "SORT BY key STORE" { + r sort tosort BY weight_* store sort-res + assert_equal $result [r lrange sort-res 0 -1] + assert_equal 16 [r llen sort-res] + assert_encoding ziplist sort-res + } + + test "SORT BY hash field STORE" { + r sort tosort BY wobj_*->weight store sort-res + assert_equal $result [r lrange sort-res 0 -1] + assert_equal 16 [r llen sort-res] + assert_encoding ziplist sort-res + } + + test "SORT DESC" { + assert_equal [lsort -decreasing -integer $result] [r sort tosort DESC] + } + + test "SORT ALPHA against integer encoded strings" { r del mylist r lpush mylist 2 r lpush mylist 1 @@ -8,172 +108,145 @@ start_server {tags {"sort"}} { r sort mylist alpha } {1 10 2 3} - tags {"slow"} { - set res {} - test {Create a random list and a random set} { - set tosort {} - array set seenrand {} - for {set i 0} {$i < 10000} {incr i} { - while 1 { - # Make sure all the weights are different because - # Redis does not use a stable sort but Tcl does. - randpath { - set rint [expr int(rand()*1000000)] - } { - set rint [expr rand()] - } - if {![info exists seenrand($rint)]} break - } - set seenrand($rint) x - r lpush tosort $i - r sadd tosort-set $i - r set weight_$i $rint - r hset wobj_$i weight $rint - lappend tosort [list $i $rint] - } - set sorted [lsort -index 1 -real $tosort] - for {set i 0} {$i < 10000} {incr i} { - lappend res [lindex $sorted $i 0] - } - format {} - } {} - - test {SORT with BY against the newly created list} { - r sort tosort {BY weight_*} - } $res - - test {SORT with BY (hash field) against the newly created list} { - r sort tosort {BY wobj_*->weight} - } $res - - test {SORT with GET (key+hash) with sanity check of each element (list)} { - set err {} - set l1 [r sort tosort GET # GET weight_*] - set l2 [r sort tosort GET # GET wobj_*->weight] - foreach {id1 w1} $l1 {id2 w2} $l2 { - set realweight [r get weight_$id1] - if {$id1 != $id2} { - set err "ID mismatch $id1 != $id2" - break - } - if {$realweight != $w1 || $realweight != $w2} { - set err "Weights mismatch! w1: $w1 w2: $w2 real: $realweight" - break - } - } - set _ $err - } {} + test "SORT sorted set" { + r del zset + r zadd zset 1 a + r zadd zset 5 b + r zadd zset 2 c + r zadd zset 10 d + r zadd zset 3 e + r sort zset alpha desc + } {e d c b a} - test {SORT with BY, but against the newly created set} { - r sort tosort-set {BY weight_*} - } $res + test "SORT sorted set: +inf and -inf handling" { + r del zset + r zadd zset -100 a + r zadd zset 200 b + r zadd zset -300 c + r zadd zset 1000000 d + r zadd zset +inf max + r zadd zset -inf min + r zrange zset 0 -1 + } {min c a b d max} + + test "SORT regression for issue #19, sorting floats" { + r flushdb + set floats {1.1 5.10 3.10 7.44 2.1 5.75 6.12 0.25 1.15} + foreach x $floats { + r lpush mylist $x + } + assert_equal [lsort -real $floats] [r sort mylist] + } - test {SORT with BY (hash field), but against the newly created set} { - r sort tosort-set {BY wobj_*->weight} - } $res + test "SORT with STORE returns zero if result is empty (github isse 224)" { + r flushdb + r sort foo store bar + } {0} - test {SORT with BY and STORE against the newly created list} { - r sort tosort {BY weight_*} store sort-res - r lrange sort-res 0 -1 - } $res + test "SORT with STORE does not create empty lists (github issue 224)" { + r flushdb + r lpush foo bar + r sort foo alpha limit 10 10 store zap + r exists zap + } {0} - test {SORT with BY (hash field) and STORE against the newly created list} { - r sort tosort {BY wobj_*->weight} store sort-res - r lrange sort-res 0 -1 - } $res + test "SORT with STORE removes key if result is empty (github issue 227)" { + r flushdb + r lpush foo bar + r sort emptylist store foo + r exists foo + } {0} + + test "SORT with BY and STORE should still order output" { + r del myset mylist + r sadd myset a b c d e f g h i l m n o p q r s t u v z aa aaa azz + r sort myset alpha by _ store mylist + r lrange mylist 0 -1 + } {a aa aaa azz b c d e f g h i l m n o p q r s t u v z} + + test "SORT will complain with numerical sorting and bad doubles (1)" { + r del myset + r sadd myset 1 2 3 4 not-a-double + set e {} + catch {r sort myset} e + set e + } {*ERR*double*} + + test "SORT will complain with numerical sorting and bad doubles (2)" { + r del myset + r sadd myset 1 2 3 4 + r mset score:1 10 score:2 20 score:3 30 score:4 not-a-double + set e {} + catch {r sort myset by score:*} e + set e + } {*ERR*double*} + + test "SORT BY sub-sorts lexicographically if score is the same" { + r del myset + r sadd myset a b c d e f g h i l m n o p q r s t u v z aa aaa azz + foreach ele {a aa aaa azz b c d e f g h i l m n o p q r s t u v z} { + set score:$ele 100 + } + r sort myset by score:* + } {a aa aaa azz b c d e f g h i l m n o p q r s t u v z} - test {SORT direct, numeric, against the newly created list} { - r sort tosort - } [lsort -integer $res] + test "SORT GET with pattern ending with just -> does not get hash field" { + r del mylist + r lpush mylist a + r set x:a-> 100 + r sort mylist by num get x:*-> + } {100} - test {SORT decreasing sort} { - r sort tosort {DESC} - } [lsort -decreasing -integer $res] + tags {"slow"} { + set num 100 + set res [create_random_dataset $num lpush] - test {SORT speed, sorting 10000 elements list using BY, 100 times} { + test "SORT speed, $num element list BY key, 100 times" { set start [clock clicks -milliseconds] for {set i 0} {$i < 100} {incr i} { - set sorted [r sort tosort {BY weight_* LIMIT 0 10}] + set sorted [r sort tosort BY weight_* LIMIT 0 10] } set elapsed [expr [clock clicks -milliseconds]-$start] - puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " - flush stdout - format {} - } {} + if {$::verbose} { + puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " + flush stdout + } + } - test {SORT speed, as above but against hash field} { + test "SORT speed, $num element list BY hash field, 100 times" { set start [clock clicks -milliseconds] for {set i 0} {$i < 100} {incr i} { - set sorted [r sort tosort {BY wobj_*->weight LIMIT 0 10}] + set sorted [r sort tosort BY wobj_*->weight LIMIT 0 10] } set elapsed [expr [clock clicks -milliseconds]-$start] - puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " - flush stdout - format {} - } {} + if {$::verbose} { + puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " + flush stdout + } + } - test {SORT speed, sorting 10000 elements list directly, 100 times} { + test "SORT speed, $num element list directly, 100 times" { set start [clock clicks -milliseconds] for {set i 0} {$i < 100} {incr i} { - set sorted [r sort tosort {LIMIT 0 10}] + set sorted [r sort tosort LIMIT 0 10] } set elapsed [expr [clock clicks -milliseconds]-$start] - puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " - flush stdout - format {} - } {} + if {$::verbose} { + puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " + flush stdout + } + } - test {SORT speed, pseudo-sorting 10000 elements list, BY , 100 times} { + test "SORT speed, $num element list BY , 100 times" { set start [clock clicks -milliseconds] for {set i 0} {$i < 100} {incr i} { - set sorted [r sort tosort {BY nokey LIMIT 0 10}] + set sorted [r sort tosort BY nokey LIMIT 0 10] } set elapsed [expr [clock clicks -milliseconds]-$start] - puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " - flush stdout - format {} - } {} - } - - test {SORT regression for issue #19, sorting floats} { - r flushdb - foreach x {1.1 5.10 3.10 7.44 2.1 5.75 6.12 0.25 1.15} { - r lpush mylist $x + if {$::verbose} { + puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " + flush stdout + } } - r sort mylist - } [lsort -real {1.1 5.10 3.10 7.44 2.1 5.75 6.12 0.25 1.15}] - - test {SORT with GET #} { - r del mylist - r lpush mylist 1 - r lpush mylist 2 - r lpush mylist 3 - r mset weight_1 10 weight_2 5 weight_3 30 - r sort mylist BY weight_* GET # - } {2 1 3} - - test {SORT with constant GET} { - r sort mylist GET foo - } {{} {} {}} - - test {SORT against sorted sets} { - r del zset - r zadd zset 1 a - r zadd zset 5 b - r zadd zset 2 c - r zadd zset 10 d - r zadd zset 3 e - r sort zset alpha desc - } {e d c b a} - - test {Sorted sets +inf and -inf handling} { - r del zset - r zadd zset -100 a - r zadd zset 200 b - r zadd zset -300 c - r zadd zset 1000000 d - r zadd zset +inf max - r zadd zset -inf min - r zrange zset 0 -1 - } {min c a b d max} + } }