@@ -532,44 +532,46 @@ impl NthValueEvaluator {
532532 fn valid_index_with_nulls ( & self , valid : & BooleanBuffer ) -> Option < usize > {
533533 match self . state . kind {
534534 NthValueKind :: First => valid. set_indices ( ) . next ( ) ,
535- NthValueKind :: Last => last_set_bit ( valid) ,
535+ NthValueKind :: Last => nth_set_bit_from_end ( valid, 1 ) ,
536536 NthValueKind :: Nth => {
537537 match self . n . cmp ( & 0 ) {
538538 Ordering :: Greater => {
539539 // SQL indices are not 0-based.
540540 let index = ( self . n as usize ) - 1 ;
541541 valid. set_indices ( ) . nth ( index)
542542 }
543- Ordering :: Less => {
544- let reverse_index = ( -self . n ) as usize ;
545- let valid_indices_len = valid. count_set_bits ( ) ;
546- if reverse_index > valid_indices_len {
547- return None ;
548- }
549- valid. set_indices ( ) . nth ( valid_indices_len - reverse_index)
550- }
543+ Ordering :: Less => nth_set_bit_from_end ( valid, ( -self . n ) as usize ) ,
551544 Ordering :: Equal => None ,
552545 }
553546 }
554547 }
555548 }
556549}
557550
558- /// Returns the index of the last set bit in `bits`, or `None` if no bit is set.
551+ /// Returns the index of the `n`th set bit from the end of `bits`, where `n = 1` is the last
552+ /// set bit, or `None` if fewer than `n` bits are set.
559553///
560554/// The bits are read a 64-bit word at a time from the end, so the cost grows with the distance
561- /// from the end to the last set bit rather than with the length of `bits`. Enumerating the set
562- /// bits from the start instead is quadratic for a frame that grows with every row.
563- fn last_set_bit ( bits : & BooleanBuffer ) -> Option < usize > {
555+ /// from the end to that bit rather than with the length of `bits`. Enumerating the set bits
556+ /// from the start instead is quadratic for a frame that grows with every row.
557+ fn nth_set_bit_from_end ( bits : & BooleanBuffer , n : usize ) -> Option < usize > {
558+ debug_assert ! ( n > 0 , "n is 1-based" ) ;
564559 let chunk = UnalignedBitChunk :: new ( bits. values ( ) , bits. offset ( ) , bits. len ( ) ) ;
565560 // The words hold `lead_padding` unset bits before `bits` and `trailing_padding` after it.
566561 let mut word_start = chunk. lead_padding ( ) + bits. len ( ) + chunk. trailing_padding ( ) ;
567- for word in chunk. iter ( ) . rev ( ) {
562+ let mut remaining = n;
563+ for mut word in chunk. iter ( ) . rev ( ) {
568564 word_start -= 64 ;
569- if word != 0 {
570- let bit = 63 - word. leading_zeros ( ) as usize ;
571- return Some ( word_start + bit - chunk. lead_padding ( ) ) ;
565+ let ones = word. count_ones ( ) as usize ;
566+ if ones < remaining {
567+ remaining -= ones;
568+ continue ;
569+ }
570+ // Clear the `remaining - 1` highest set bits, leaving the one we want on top
571+ for _ in 1 ..remaining {
572+ word ^= 1 << word. ilog2 ( ) ;
572573 }
574+ return Some ( word_start + word. ilog2 ( ) as usize - chunk. lead_padding ( ) ) ;
573575 }
574576 None
575577}
@@ -731,7 +733,7 @@ mod tests {
731733 }
732734
733735 #[ test]
734- fn last_set_bit_matches_a_scan_from_the_end ( ) {
736+ fn nth_set_bit_from_end_matches_a_scan_from_the_end ( ) {
735737 // The slices cover every bit offset within a word, byte-aligned and unaligned starts,
736738 // and lengths from empty to several words, which are the cases `UnalignedBitChunk`
737739 // splits into a prefix, aligned words and a suffix.
@@ -752,12 +754,15 @@ mod tests {
752754 for offset in 0 ..70 {
753755 for len in 0 ..=200 {
754756 let slice = bits. slice ( offset, len) ;
755- let expected = ( 0 ..len) . rev ( ) . find ( |& i| slice. value ( i) ) ;
756- assert_eq ! (
757- last_set_bit( & slice) ,
758- expected,
759- "offset {offset}, len {len}"
760- ) ;
757+ for n in [ 1 , 2 , 3 , 63 , 64 , 65 , 130 ] {
758+ let expected =
759+ ( 0 ..len) . rev ( ) . filter ( |& i| slice. value ( i) ) . nth ( n - 1 ) ;
760+ assert_eq ! (
761+ nth_set_bit_from_end( & slice, n) ,
762+ expected,
763+ "offset {offset}, len {len}, n {n}"
764+ ) ;
765+ }
761766 }
762767 }
763768 }
0 commit comments