1use crate::null_sentinel;
6use arrow_array::types::ByteArrayType;
7use arrow_array::*;
8use arrow_buffer::bit_util::ceil;
9use arrow_buffer::{
10 ArrowNativeType, BooleanBuffer, MutableBuffer, NullBuffer, OffsetBuffer, ScalarBuffer,
11};
12use arrow_data::MAX_INLINE_VIEW_LEN;
13use arrow_schema::{ArrowError, SortOptions};
14use builder::make_view;
15
16pub const BLOCK_SIZE: usize = 32;
18
19pub const MINI_BLOCK_COUNT: usize = 4;
23
24pub const MINI_BLOCK_SIZE: usize = BLOCK_SIZE / MINI_BLOCK_COUNT;
26
27pub const BLOCK_CONTINUATION: u8 = 0xFF;
29
30pub const EMPTY_SENTINEL: u8 = 1;
32
33pub const NON_EMPTY_SENTINEL: u8 = 2;
35
36pub const NULL_VALUE_SENTINEL: u8 = 3;
38
39#[inline]
41pub fn padded_length(a: Option<usize>) -> usize {
42 match a {
43 Some(a) => non_null_padded_length(a),
44 None => 1,
45 }
46}
47
48#[inline]
50pub(crate) fn non_null_padded_length(len: usize) -> usize {
51 if len <= BLOCK_SIZE {
52 1 + ceil(len, MINI_BLOCK_SIZE) * (MINI_BLOCK_SIZE + 1)
53 } else {
54 MINI_BLOCK_COUNT + ceil(len, BLOCK_SIZE) * (BLOCK_SIZE + 1)
57 }
58}
59
60pub(crate) fn decode_nulls_sentinel(
63 rows: &[&[u8]],
64 options: SortOptions,
65) -> Result<Option<NullBuffer>, ArrowError> {
66 let null_sentinel = null_sentinel(options);
67 let nulls = MutableBuffer::try_collect_bool(rows.len(), |x| rows[x][0] != null_sentinel)
68 .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
69 let nulls = BooleanBuffer::new(nulls.into(), 0, rows.len());
70 let nulls = NullBuffer::new(nulls);
71 Ok((nulls.null_count() > 0).then_some(nulls))
72}
73
74pub fn encode<'a, I: Iterator<Item = Option<&'a [u8]>>>(
86 data: &mut [u8],
87 offsets: &mut [usize],
88 i: I,
89 opts: SortOptions,
90) {
91 for (offset, maybe_val) in offsets.iter_mut().skip(1).zip(i) {
92 *offset += encode_one(&mut data[*offset..], maybe_val, opts);
93 }
94}
95
96pub(crate) fn encode_generic_byte_array<T: ByteArrayType>(
98 data: &mut [u8],
99 offsets: &mut [usize],
100 input_array: &GenericByteArray<T>,
101 opts: SortOptions,
102) {
103 let input_offsets = input_array.value_offsets();
104 let bytes = input_array.values().as_slice();
105
106 if let Some(null_buffer) = input_array.nulls().filter(|x| x.null_count() > 0) {
107 let input_iter =
108 input_offsets
109 .windows(2)
110 .zip(null_buffer.iter())
111 .map(|(start_end, is_valid)| {
112 if is_valid {
113 let item_range = start_end[0].as_usize()..start_end[1].as_usize();
114 let item = unsafe { bytes.get_unchecked(item_range) };
117 Some(item)
118 } else {
119 None
120 }
121 });
122
123 encode(data, offsets, input_iter, opts);
124 } else {
125 let input_iter = input_offsets.windows(2).map(|start_end| {
127 let item_range = start_end[0].as_usize()..start_end[1].as_usize();
128 let item = unsafe { bytes.get_unchecked(item_range) };
131 Some(item)
132 });
133
134 encode(data, offsets, input_iter, opts);
135 }
136}
137
138pub fn encode_null(out: &mut [u8], opts: SortOptions) -> usize {
139 out[0] = null_sentinel(opts);
140 1
141}
142
143pub fn encode_empty(out: &mut [u8], opts: SortOptions) -> usize {
144 out[0] = match opts.descending {
145 true => !EMPTY_SENTINEL,
146 false => EMPTY_SENTINEL,
147 };
148 1
149}
150
151pub fn encode_null_value(out: &mut [u8], opts: SortOptions) -> usize {
153 out[0] = match opts.descending {
154 true => !NON_EMPTY_SENTINEL,
155 false => NON_EMPTY_SENTINEL,
156 };
157 out[1] = match opts.descending {
158 true => !NULL_VALUE_SENTINEL,
159 false => NULL_VALUE_SENTINEL,
160 };
161 2
162}
163
164#[inline]
165pub fn encode_one(out: &mut [u8], val: Option<&[u8]>, opts: SortOptions) -> usize {
166 match val {
167 None => encode_null(out, opts),
168 Some([]) => encode_empty(out, opts),
169 Some(val) => {
170 out[0] = NON_EMPTY_SENTINEL;
172
173 let len = if val.len() <= BLOCK_SIZE {
174 1 + encode_blocks::<MINI_BLOCK_SIZE>(&mut out[1..], val)
175 } else {
176 let (initial, rem) = val.split_at(BLOCK_SIZE);
177 let offset = encode_blocks::<MINI_BLOCK_SIZE>(&mut out[1..], initial);
178 out[offset] = BLOCK_CONTINUATION;
179 1 + offset + encode_blocks::<BLOCK_SIZE>(&mut out[1 + offset..], rem)
180 };
181
182 if opts.descending {
183 out[..len].iter_mut().for_each(|v| *v = !*v)
185 }
186 len
187 }
188 }
189}
190
191#[inline]
193fn encode_blocks<const SIZE: usize>(out: &mut [u8], val: &[u8]) -> usize {
194 let block_count = ceil(val.len(), SIZE);
195 let end_offset = block_count * (SIZE + 1);
196 let to_write = &mut out[..end_offset];
197
198 let (chunks, remainder) = val.as_chunks::<SIZE>();
199 let to_write_chunks = to_write.chunks_exact_mut(SIZE + 1);
200 for (input, output) in chunks.iter().zip(to_write_chunks) {
201 let out_block: &mut [u8; SIZE] = (&mut output[..SIZE]).try_into().unwrap();
202
203 *out_block = *input;
204
205 output[SIZE] = BLOCK_CONTINUATION;
207 }
208
209 if !remainder.is_empty() {
210 let start_offset = (block_count - 1) * (SIZE + 1);
211 to_write[start_offset..start_offset + remainder.len()].copy_from_slice(remainder);
212 *to_write.last_mut().unwrap() = remainder.len() as u8;
213 } else {
214 *to_write.last_mut().unwrap() = SIZE as u8;
216 }
217 end_offset
218}
219
220pub fn decode_blocks(row: &[u8], options: SortOptions, mut f: impl FnMut(&[u8])) -> usize {
223 let (non_empty_sentinel, continuation) = match options.descending {
224 true => (!NON_EMPTY_SENTINEL, !BLOCK_CONTINUATION),
225 false => (NON_EMPTY_SENTINEL, BLOCK_CONTINUATION),
226 };
227
228 if row[0] != non_empty_sentinel {
229 return 1;
231 }
232
233 let block_len = |sentinel: u8| match options.descending {
235 true => !sentinel as usize,
236 false => sentinel as usize,
237 };
238
239 let mut idx = 1;
240 for _ in 0..MINI_BLOCK_COUNT {
241 let sentinel = row[idx + MINI_BLOCK_SIZE];
242 if sentinel != continuation {
243 f(&row[idx..idx + block_len(sentinel)]);
244 return idx + MINI_BLOCK_SIZE + 1;
245 }
246 f(&row[idx..idx + MINI_BLOCK_SIZE]);
247 idx += MINI_BLOCK_SIZE + 1;
248 }
249
250 loop {
251 let sentinel = row[idx + BLOCK_SIZE];
252 if sentinel != continuation {
253 f(&row[idx..idx + block_len(sentinel)]);
254 return idx + BLOCK_SIZE + 1;
255 }
256 f(&row[idx..idx + BLOCK_SIZE]);
257 idx += BLOCK_SIZE + 1;
258 }
259}
260
261fn decoded_len(row: &[u8], options: SortOptions) -> usize {
263 let mut len = 0;
264 decode_blocks(row, options, |block| len += block.len());
265 len
266}
267
268pub fn decode_binary<I: OffsetSizeTrait>(
270 rows: &mut [&[u8]],
271 options: SortOptions,
272) -> Result<GenericBinaryArray<I>, ArrowError> {
273 let len = rows.len();
274 let nulls = decode_nulls_sentinel(rows, options)?;
275
276 let values_capacity = rows.iter().map(|row| decoded_len(row, options)).sum();
277 I::from_usize(values_capacity).ok_or(ArrowError::OffsetOverflowError(values_capacity))?;
278 let mut offsets = Vec::<I>::with_capacity(len + 1);
279 offsets.push(I::zero());
280 let mut values = MutableBuffer::try_with_capacity(values_capacity)
281 .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
282
283 for row in rows {
284 let offset = decode_blocks(row, options, |b| values.extend_from_slice(b));
285 *row = &row[offset..];
286 offsets.push(I::usize_as(values.len()))
287 }
288
289 if options.descending {
290 values.as_slice_mut().iter_mut().for_each(|o| *o = !*o)
291 }
292
293 Ok(unsafe {
296 GenericBinaryArray::new_unchecked(
297 OffsetBuffer::new(ScalarBuffer::from(offsets)),
298 values.into(),
299 nulls,
300 )
301 })
302}
303
304fn decode_binary_view_inner<const VALIDATE_UTF8: bool>(
305 rows: &mut [&[u8]],
306 options: SortOptions,
307) -> Result<BinaryViewArray, ArrowError> {
308 let len = rows.len();
309 let inline_str_max_len = MAX_INLINE_VIEW_LEN as usize;
310
311 let nulls = decode_nulls_sentinel(rows, options)?;
312
313 let mut values_capacity = inline_str_max_len;
315 let mut inline_capacity = 0;
316 for row in rows.iter() {
317 let len = decoded_len(row, options);
318 if len > inline_str_max_len {
319 values_capacity += len;
320 } else if VALIDATE_UTF8 {
321 inline_capacity += len;
322 }
323 }
324 let long_values_len = values_capacity - inline_str_max_len;
328 if long_values_len > i32::MAX as usize {
329 return Err(ArrowError::InvalidArgumentError(format!(
330 "{long_values_len} bytes of non-inlined values too long to decode into a view array with a single data buffer"
331 )));
332 }
333 let mut values = MutableBuffer::try_with_capacity(values_capacity)
334 .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
335 let mut view_utf8_validation_buffer = if VALIDATE_UTF8 {
336 Vec::with_capacity(inline_capacity)
337 } else {
338 Vec::new()
339 };
340
341 let null_sentinel = null_sentinel(options);
342 let mut views = vec![0_u128; len];
343 for (i, row) in rows.iter_mut().enumerate() {
344 let start_offset = values.len();
345 let offset = decode_blocks(row, options, |b| values.extend_from_slice(b));
346 let decoded_len = values.len() - start_offset;
350 if row[0] == null_sentinel {
351 debug_assert_eq!(offset, 1);
352 debug_assert_eq!(start_offset, values.len());
353 } else {
354 let val = unsafe { values.get_unchecked_mut(start_offset..) };
356
357 if options.descending {
358 val.iter_mut().for_each(|o| *o = !*o);
359 }
360
361 views[i] = make_view(val, 0, start_offset as u32);
362
363 if decoded_len <= inline_str_max_len {
364 if VALIDATE_UTF8 {
365 view_utf8_validation_buffer.extend_from_slice(val);
366 }
367 values.truncate(start_offset);
368 }
369 }
370 *row = &row[offset..];
371 }
372
373 if VALIDATE_UTF8 {
374 std::str::from_utf8(&values).unwrap();
375 std::str::from_utf8(&view_utf8_validation_buffer).unwrap();
376 }
377
378 Ok(unsafe { BinaryViewArray::new_unchecked(views.into(), [values.into()].into(), nulls) })
381}
382
383pub fn decode_binary_view(
388 rows: &mut [&[u8]],
389 options: SortOptions,
390) -> Result<BinaryViewArray, ArrowError> {
391 decode_binary_view_inner::<false>(rows, options)
392}
393
394pub unsafe fn decode_string<I: OffsetSizeTrait>(
400 rows: &mut [&[u8]],
401 options: SortOptions,
402 validate_utf8: bool,
403) -> Result<GenericStringArray<I>, ArrowError> {
404 let decoded = decode_binary::<I>(rows, options)?;
405
406 if validate_utf8 {
407 return Ok(GenericStringArray::from(decoded));
408 }
409
410 let (offsets, values, nulls) = decoded.into_parts();
411
412 Ok(unsafe { GenericStringArray::new_unchecked(offsets, values, nulls) })
415}
416
417pub unsafe fn decode_string_view(
426 rows: &mut [&[u8]],
427 options: SortOptions,
428 validate_utf8: bool,
429) -> Result<StringViewArray, ArrowError> {
430 let view = if validate_utf8 {
431 decode_binary_view_inner::<true>(rows, options)?
432 } else {
433 decode_binary_view_inner::<false>(rows, options)?
434 };
435 Ok(unsafe { view.to_string_view_unchecked() })
436}
437
438pub fn decode_null_value(rows: &mut [&[u8]], options: SortOptions) {
439 for row in rows.iter_mut() {
440 let (sentinel1, sentinel2) = match options.descending {
441 true => (!NON_EMPTY_SENTINEL, !NULL_VALUE_SENTINEL),
442 false => (NON_EMPTY_SENTINEL, NULL_VALUE_SENTINEL),
443 };
444 debug_assert_eq!(row[0], sentinel1, "Expected NULL_VALUE_SENTINEL at byte 0");
445 debug_assert_eq!(row[1], sentinel2, "Expected NULL_VALUE_SENTINEL at byte 1");
446 *row = &row[2..];
447 }
448}