@@ -97,7 +97,12 @@ pub(crate) fn null_runs_holding_elements(
9797/// Drops the elements before the first of the lists laid out back to back, after the last, and
9898/// under the runs of null lists from [`null_runs_holding_elements`], which come out empty.
9999///
100- /// Returns the elements kept and where each list now starts, with room to push one more offset.
100+ /// `end` is where the last list ends. It is a `usize` rather than an `O` because a list view's last
101+ /// list can end past what its offsets' type holds: with `u8` offsets `[1, 5, 105]` and sizes
102+ /// `[4, 100, 200]`, it ends at 305.
103+ ///
104+ /// Returns the elements kept and where each list now starts. A [`ListArray`] needs one more offset,
105+ /// where its last list ends, so the buffer has room to push it without reallocating.
101106pub ( crate ) fn drop_unreferenced_elements < O : IntegerPType > (
102107 elements : & ArrayRef ,
103108 starts : & [ O ] ,
@@ -110,32 +115,16 @@ pub(crate) fn drop_unreferenced_elements<O: IntegerPType>(
110115 // The ranges of elements kept, counted from the first list's start.
111116 let mut kept = Vec :: with_capacity ( null_runs. len ( ) + 1 ) ;
112117 let mut kept_start = 0 ;
118+ let mut offsets = BufferMut :: with_capacity_in ( starts. len ( ) + 1 , allocator. clone ( ) ) ;
119+ offsets. extend_from_slice ( starts) ;
120+ let mut dropped = starts. first ( ) . copied ( ) . unwrap_or_else ( O :: zero) ;
121+ let mut from = 0 ;
113122 for & ( run_start, run_end) in null_runs {
114123 if kept_start < start_of ( run_start) - first {
115124 kept. push ( ( kept_start, start_of ( run_start) - first) ) ;
116125 }
117126 kept_start = start_of ( run_end) - first;
118- }
119- if kept_start < end - first {
120- kept. push ( ( kept_start, end - first) ) ;
121- }
122- let referenced = elements. slice ( first..end) ?;
123- let elements = if let [ ( start, stop) ] = kept[ ..] {
124- referenced. slice ( start..stop) ?
125- } else {
126- let mut bits = BitBufferMut :: new_unset ( end - first) ;
127- for & ( start, stop) in & kept {
128- bits. fill_range ( start, stop, true ) ;
129- }
130- // With the ranges cached on the mask, the filter copies the elements range by range.
131- referenced. filter ( Mask :: from_buffer_with_slices ( bits. freeze ( ) , kept) ) ?
132- } ;
133127
134- let mut offsets = BufferMut :: with_capacity_in ( starts. len ( ) + 1 , allocator. clone ( ) ) ;
135- offsets. extend_from_slice ( starts) ;
136- let mut dropped = starts. first ( ) . copied ( ) . unwrap_or_else ( O :: zero) ;
137- let mut from = 0 ;
138- for & ( run_start, run_end) in null_runs {
139128 for offset in & mut offsets[ from..run_start] {
140129 * offset = * offset - dropped;
141130 }
@@ -146,8 +135,25 @@ pub(crate) fn drop_unreferenced_elements<O: IntegerPType>(
146135 }
147136 from = run_end;
148137 }
138+ if kept_start < end - first {
139+ kept. push ( ( kept_start, end - first) ) ;
140+ }
149141 for offset in & mut offsets[ from..] {
150142 * offset = * offset - dropped;
151143 }
144+
145+ let referenced = elements. slice ( first..end) ?;
146+ let elements = match kept[ ..] {
147+ [ ] => referenced. slice ( 0 ..0 ) ?,
148+ [ ( start, stop) ] => referenced. slice ( start..stop) ?,
149+ _ => {
150+ let mut bits = BitBufferMut :: new_unset ( end - first) ;
151+ for & ( start, stop) in & kept {
152+ bits. fill_range ( start, stop, true ) ;
153+ }
154+ // With the ranges cached on the mask, the filter copies the elements range by range.
155+ referenced. filter ( Mask :: from_buffer_with_slices ( bits. freeze ( ) , kept) ) ?
156+ }
157+ } ;
152158 Ok ( ( elements, offsets) )
153159}
0 commit comments