columnar/
primitive.rs

1//! Types that prefer to be represented by `Vec<T>`.
2use alloc::{vec::Vec, string::String};
3
4use core::num::Wrapping;
5
6/// An implementation of opinions for types that want to use `Vec<T>`.
7macro_rules! implement_columnable {
8    ($($index_type:ty),*) => { $(
9        impl crate::Columnar for $index_type {
10            #[inline(always)]
11            fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { *other }
12
13            type Container = Vec<$index_type>;
14        }
15
16        impl<'a> crate::AsBytes<'a> for &'a [$index_type] {
17            const SLICE_COUNT: usize = 1;
18            #[inline]
19            fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
20                debug_assert!(index < Self::SLICE_COUNT);
21                (core::mem::align_of::<$index_type>() as u64, bytemuck::cast_slice(&self[..]))
22            }
23        }
24        impl<'a> crate::FromBytes<'a> for &'a [$index_type] {
25            const SLICE_COUNT: usize = 1;
26            #[inline(always)]
27            fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
28                // We use `unwrap()` here in order to panic with the `bytemuck` error, which may be informative.
29                bytemuck::try_cast_slice(bytes.next().expect("Iterator exhausted prematurely")).unwrap()
30            }
31            #[inline(always)]
32            fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
33                let (w, tail) = store.get(*offset);
34                *offset += 1;
35                let all: &[$index_type] = bytemuck::cast_slice(w);
36                let trim = ((8 - tail as usize) % 8) / core::mem::size_of::<$index_type>();
37                debug_assert!(trim <= all.len(), "from_store: trim {trim} exceeds slice length {}", all.len());
38                all.get(..all.len().wrapping_sub(trim)).unwrap_or(&[])
39            }
40            #[inline(always)]
41            fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
42                sizes.push(core::mem::size_of::<$index_type>());
43                Ok(())
44            }
45        }
46        impl<'a, const N: usize> crate::AsBytes<'a> for &'a [[$index_type; N]] {
47            const SLICE_COUNT: usize = 1;
48            #[inline]
49            fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
50                debug_assert!(index < Self::SLICE_COUNT);
51                (core::mem::align_of::<$index_type>() as u64, bytemuck::cast_slice(&self[..]))
52            }
53        }
54        impl<'a, const N: usize> crate::FromBytes<'a> for &'a [[$index_type; N]] {
55            const SLICE_COUNT: usize = 1;
56            #[inline(always)]
57            fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
58                // We use `unwrap()` here in order to panic with the `bytemuck` error, which may be informative.
59                bytemuck::try_cast_slice(bytes.next().expect("Iterator exhausted prematurely")).unwrap()
60            }
61            #[inline(always)]
62            fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
63                let (w, tail) = store.get(*offset);
64                *offset += 1;
65                let all: &[[$index_type; N]] = bytemuck::cast_slice(w);
66                let trim = ((8 - tail as usize) % 8) / (core::mem::size_of::<$index_type>() * N);
67                debug_assert!(trim <= all.len(), "from_store: trim {trim} exceeds slice length {}", all.len());
68                all.get(..all.len().wrapping_sub(trim)).unwrap_or(&[])
69            }
70            #[inline(always)]
71            fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
72                sizes.push(core::mem::size_of::<$index_type>() * N);
73                Ok(())
74            }
75        }
76    )* }
77}
78
79implement_columnable!(u8, u16, u32, u64);
80implement_columnable!(i8, i16, i32, i64);
81implement_columnable!(f32, f64);
82implement_columnable!(Wrapping<u8>, Wrapping<u16>, Wrapping<u32>, Wrapping<u64>);
83implement_columnable!(Wrapping<i8>, Wrapping<i16>, Wrapping<i32>, Wrapping<i64>);
84
85pub use sizes::{Usizes, Isizes};
86/// Columnar stores for `usize` and `isize`, stored as 64 bits.
87mod sizes {
88
89    use alloc::string::String;
90    use crate::*;
91    use crate::common::{BorrowIndexAs, PushIndexAs};
92
93    #[derive(Copy, Clone, Default)]
94    pub struct Usizes<CV = Vec<u64>> { pub values: CV }
95
96    impl Columnar for usize {
97        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { other }
98        type Container = Usizes;
99    }
100
101    impl<CV: BorrowIndexAs<u64> + Len> Borrow for Usizes<CV> {
102        type Ref<'a> = usize;
103        type Borrowed<'a> = Usizes<CV::Borrowed<'a>> where CV: 'a;
104        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
105            Usizes { values: self.values.borrow() }
106        }
107        #[inline(always)]
108        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where CV: 'a {
109            Usizes { values: CV::reborrow(thing.values) }
110        }
111        #[inline(always)]
112        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
113    }
114
115    impl<CV: PushIndexAs<u64>> Container for Usizes<CV> {
116        #[inline(always)]
117        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: core::ops::Range<usize>) {
118            self.values.extend_from_self(other.values, range)
119        }
120
121        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
122            self.values.reserve_for(selves.map(|x| x.values))
123        }
124    }
125
126    impl<CV: Len> Len for Usizes<CV> { fn len(&self) -> usize { self.values.len() }}
127    impl IndexMut for Usizes {
128        type IndexMut<'a> = &'a mut u64;
129        #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> { &mut self.values[index] }
130    }
131    impl<CV: IndexAs<u64>> Index for Usizes<CV> {
132        type Ref = usize;
133        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self.values.index_as(index).try_into().expect("Usizes values should fit in `usize`") }
134    }
135    impl<CV: IndexAs<u64>> Index for &Usizes<CV> {
136        type Ref = usize;
137        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self.values.index_as(index).try_into().expect("Usizes values should fit in `usize`") }
138    }
139    impl<CV: for<'a> Push<&'a u64>> Push<usize> for Usizes<CV> {
140        #[inline]
141        fn push(&mut self, item: usize) { self.values.push(&item.try_into().expect("usize must fit in a u64")) }
142    }
143    impl Push<&usize> for Usizes {
144        #[inline]
145        fn push(&mut self, item: &usize) { self.values.push((*item).try_into().expect("usize must fit in a u64")) }
146    }
147    impl<CV: Clear> Clear for Usizes<CV> { fn clear(&mut self) { self.values.clear() }}
148
149    impl<'a, CV: crate::AsBytes<'a>> crate::AsBytes<'a> for crate::primitive::Usizes<CV> {
150        const SLICE_COUNT: usize = CV::SLICE_COUNT;
151        #[inline]
152        fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
153            self.values.get_byte_slice(index)
154        }
155    }
156
157    impl<'a, CV: crate::FromBytes<'a>> crate::FromBytes<'a> for crate::primitive::Usizes<CV> {
158        const SLICE_COUNT: usize = CV::SLICE_COUNT;
159        #[inline(always)]
160        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
161            Self { values: CV::from_bytes(bytes) }
162        }
163        #[inline(always)]
164        fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
165            Self { values: CV::from_store(store, offset) }
166        }
167        #[inline(always)]
168        fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
169            CV::element_sizes(sizes)
170        }
171    }
172
173
174    #[derive(Copy, Clone, Default)]
175    pub struct Isizes<CV = Vec<i64>> { pub values: CV }
176
177    impl Columnar for isize {
178        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { other }
179        type Container = Isizes;
180    }
181
182    impl<CV: BorrowIndexAs<i64>> Borrow for Isizes<CV> {
183        type Ref<'a> = isize;
184        type Borrowed<'a> = Isizes<CV::Borrowed<'a>> where CV: 'a;
185        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
186            Isizes { values: self.values.borrow() }
187        }
188        #[inline(always)]
189        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where CV: 'a {
190            Isizes { values: CV::reborrow(thing.values) }
191        }
192        #[inline(always)]
193        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
194    }
195
196    impl<CV: PushIndexAs<i64>> Container for Isizes<CV> {
197        #[inline(always)]
198        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: core::ops::Range<usize>) {
199            self.values.extend_from_self(other.values, range)
200        }
201
202        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
203            self.values.reserve_for(selves.map(|x| x.values))
204        }
205    }
206
207    impl<CV: Len> Len for Isizes<CV> { fn len(&self) -> usize { self.values.len() }}
208    impl IndexMut for Isizes {
209        type IndexMut<'a> = &'a mut i64;
210        #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> { &mut self.values[index] }
211    }
212    impl<CV: IndexAs<i64>> Index for Isizes<CV> {
213        type Ref = isize;
214        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self.values.index_as(index).try_into().expect("Isizes values should fit in `isize`") }
215    }
216    impl<CV: IndexAs<i64>> Index for &Isizes<CV> {
217        type Ref = isize;
218        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self.values.index_as(index).try_into().expect("Isizes values should fit in `isize`") }
219    }
220    impl<CV: for<'a> Push<&'a i64>> Push<isize> for Isizes<CV> {
221        #[inline]
222        fn push(&mut self, item: isize) { self.values.push(&item.try_into().expect("isize must fit in a i64")) }
223    }
224    impl Push<&isize> for Isizes {
225        #[inline]
226        fn push(&mut self, item: &isize) { self.values.push((*item).try_into().expect("isize must fit in a i64")) }
227    }
228    impl<CV: Clear> Clear for Isizes<CV> { fn clear(&mut self) { self.values.clear() }}
229
230    impl<'a, CV: crate::AsBytes<'a>> crate::AsBytes<'a> for crate::primitive::Isizes<CV> {
231        const SLICE_COUNT: usize = CV::SLICE_COUNT;
232        #[inline]
233        fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
234            self.values.get_byte_slice(index)
235        }
236    }
237
238    impl<'a, CV: crate::FromBytes<'a>> crate::FromBytes<'a> for crate::primitive::Isizes<CV> {
239        const SLICE_COUNT: usize = CV::SLICE_COUNT;
240        #[inline(always)]
241        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
242            Self { values: CV::from_bytes(bytes) }
243        }
244        #[inline(always)]
245        fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
246            Self { values: CV::from_store(store, offset) }
247        }
248        #[inline(always)]
249        fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
250            CV::element_sizes(sizes)
251        }
252    }
253}
254
255pub use chars::{Chars};
256/// Columnar store for `char`, stored as a `u32`.
257mod chars {
258
259    use alloc::string::String;
260    use crate::*;
261    use crate::common::{BorrowIndexAs, PushIndexAs};
262
263    type Encoded = u32;
264
265    #[derive(Copy, Clone, Default)]
266    pub struct Chars<CV = Vec<Encoded>> { pub values: CV }
267
268    impl Columnar for char {
269        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { other }
270        type Container = Chars;
271    }
272
273    impl<CV: BorrowIndexAs<Encoded>> Borrow for Chars<CV> {
274        type Ref<'a> = char;
275        type Borrowed<'a> = Chars<CV::Borrowed<'a>> where CV: 'a;
276        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
277            Chars { values: self.values.borrow() }
278        }
279        #[inline(always)]
280        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where CV: 'a {
281            Chars { values: CV::reborrow(thing.values) }
282        }
283        #[inline(always)]
284        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
285    }
286
287    impl<CV: PushIndexAs<Encoded>> Container for Chars<CV> {
288        #[inline(always)]
289        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: core::ops::Range<usize>) {
290            self.values.extend_from_self(other.values, range)
291        }
292
293        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
294            self.values.reserve_for(selves.map(|x| x.values))
295        }
296    }
297
298    impl<CV: Len> Len for Chars<CV> { fn len(&self) -> usize { self.values.len() }}
299    impl<CV: IndexAs<Encoded>> Index for Chars<CV> {
300        type Ref = char;
301        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { char::from_u32(self.values.index_as(index)).unwrap() }
302    }
303    impl<CV: IndexAs<Encoded>> Index for &Chars<CV> {
304        type Ref = char;
305        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { char::from_u32(self.values.index_as(index)).unwrap() }
306    }
307    impl<CV: for<'a> Push<&'a Encoded>> Push<char> for Chars<CV> {
308        #[inline]
309        fn push(&mut self, item: char) { self.values.push(&u32::from(item)) }
310    }
311    impl Push<&char> for Chars {
312        #[inline]
313        fn push(&mut self, item: &char) { self.values.push(u32::from(*item)) }
314    }
315    impl<CV: Clear> Clear for Chars<CV> { fn clear(&mut self) { self.values.clear() }}
316
317    impl<'a, CV: crate::AsBytes<'a>> crate::AsBytes<'a> for Chars<CV> {
318        const SLICE_COUNT: usize = CV::SLICE_COUNT;
319        #[inline]
320        fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
321            self.values.get_byte_slice(index)
322        }
323    }
324
325    impl<'a, CV: crate::FromBytes<'a>> crate::FromBytes<'a> for Chars<CV> {
326        const SLICE_COUNT: usize = CV::SLICE_COUNT;
327        #[inline(always)]
328        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
329            Self { values: CV::from_bytes(bytes) }
330        }
331        #[inline(always)]
332        fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
333            Self { values: CV::from_store(store, offset) }
334        }
335        #[inline(always)]
336        fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
337            CV::element_sizes(sizes)
338        }
339    }
340}
341
342pub use larges::{U128s, I128s};
343/// Columnar stores for `u128` and `i128`, stored as [u8; 16] bits.
344mod larges {
345
346    use alloc::string::String;
347    use crate::*;
348    use crate::common::{BorrowIndexAs, PushIndexAs};
349
350    type Encoded = [u8; 16];
351
352    #[derive(Copy, Clone, Default)]
353    pub struct U128s<CV = Vec<Encoded>> { pub values: CV }
354
355    impl Columnar for u128 {
356        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { other }
357        type Container = U128s;
358    }
359
360    impl<CV: BorrowIndexAs<Encoded>> Borrow for U128s<CV> {
361        type Ref<'a> = u128;
362        type Borrowed<'a> = U128s<CV::Borrowed<'a>> where CV: 'a;
363        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
364            U128s { values: self.values.borrow() }
365        }
366        #[inline(always)]
367        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where CV: 'a {
368            U128s { values: CV::reborrow(thing.values) }
369        }
370        #[inline(always)]
371        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
372    }
373
374    impl<CV: PushIndexAs<Encoded>> Container for U128s<CV> {
375        #[inline(always)]
376        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: core::ops::Range<usize>) {
377            self.values.extend_from_self(other.values, range)
378        }
379
380        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
381            self.values.reserve_for(selves.map(|x| x.values))
382        }
383    }
384
385    impl<CV: Len> Len for U128s<CV> { fn len(&self) -> usize { self.values.len() }}
386    impl<CV: IndexAs<Encoded>> Index for U128s<CV> {
387        type Ref = u128;
388        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { u128::from_le_bytes(self.values.index_as(index)) }
389    }
390    impl<CV: IndexAs<Encoded>> Index for &U128s<CV> {
391        type Ref = u128;
392        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { u128::from_le_bytes(self.values.index_as(index)) }
393    }
394    impl<CV: for<'a> Push<&'a Encoded>> Push<u128> for U128s<CV> {
395        #[inline]
396        fn push(&mut self, item: u128) { self.values.push(&item.to_le_bytes()) }
397    }
398    impl Push<&u128> for U128s {
399        #[inline]
400        fn push(&mut self, item: &u128) { self.values.push(item.to_le_bytes()) }
401    }
402    impl<CV: Clear> Clear for U128s<CV> { fn clear(&mut self) { self.values.clear() }}
403
404    impl<'a, CV: crate::AsBytes<'a>> crate::AsBytes<'a> for U128s<CV> {
405        const SLICE_COUNT: usize = CV::SLICE_COUNT;
406        #[inline]
407        fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
408            self.values.get_byte_slice(index)
409        }
410    }
411
412    impl<'a, CV: crate::FromBytes<'a>> crate::FromBytes<'a> for U128s<CV> {
413        const SLICE_COUNT: usize = CV::SLICE_COUNT;
414        #[inline(always)]
415        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
416            Self { values: CV::from_bytes(bytes) }
417        }
418        #[inline(always)]
419        fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
420            Self { values: CV::from_store(store, offset) }
421        }
422        #[inline(always)]
423        fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
424            CV::element_sizes(sizes)
425        }
426    }
427
428    #[derive(Copy, Clone, Default)]
429    pub struct I128s<CV = Vec<Encoded>> { pub values: CV }
430
431    impl Columnar for i128 {
432        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { other }
433        type Container = I128s;
434    }
435
436    impl<CV: BorrowIndexAs<Encoded>> Borrow for I128s<CV> {
437        type Ref<'a> = i128;
438        type Borrowed<'a> = I128s<CV::Borrowed<'a>> where CV: 'a;
439        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
440            I128s { values: self.values.borrow() }
441        }
442        #[inline(always)]
443        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where CV: 'a {
444            I128s { values: CV::reborrow(thing.values) }
445        }
446        #[inline(always)]
447        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
448    }
449
450    impl<CV: PushIndexAs<Encoded>> Container for I128s<CV> {
451        #[inline(always)]
452        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: core::ops::Range<usize>) {
453            self.values.extend_from_self(other.values, range)
454        }
455
456        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
457            self.values.reserve_for(selves.map(|x| x.values))
458        }
459    }
460
461    impl<CV: Len> Len for I128s<CV> { fn len(&self) -> usize { self.values.len() }}
462    impl<CV: IndexAs<Encoded>> Index for I128s<CV> {
463        type Ref = i128;
464        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { i128::from_le_bytes(self.values.index_as(index)) }
465    }
466    impl<CV: IndexAs<Encoded>> Index for &I128s<CV> {
467        type Ref = i128;
468        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { i128::from_le_bytes(self.values.index_as(index)) }
469    }
470    impl<CV: for<'a> Push<&'a Encoded>> Push<i128> for I128s<CV> {
471        #[inline]
472        fn push(&mut self, item: i128) { self.values.push(&item.to_le_bytes()) }
473    }
474    impl Push<&i128> for I128s {
475        #[inline]
476        fn push(&mut self, item: &i128) { self.values.push(item.to_le_bytes()) }
477    }
478    impl<CV: Clear> Clear for I128s<CV> { fn clear(&mut self) { self.values.clear() }}
479
480    impl<'a, CV: crate::AsBytes<'a>> crate::AsBytes<'a> for I128s<CV> {
481        const SLICE_COUNT: usize = CV::SLICE_COUNT;
482        #[inline]
483        fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
484            self.values.get_byte_slice(index)
485        }
486    }
487
488    impl<'a, CV: crate::FromBytes<'a>> crate::FromBytes<'a> for I128s<CV> {
489        const SLICE_COUNT: usize = CV::SLICE_COUNT;
490        #[inline(always)]
491        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
492            Self { values: CV::from_bytes(bytes) }
493        }
494        #[inline(always)]
495        fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
496            Self { values: CV::from_store(store, offset) }
497        }
498        #[inline(always)]
499        fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
500            CV::element_sizes(sizes)
501        }
502    }
503}
504
505/// Columnar stores for non-decreasing `u64`, stored in various ways.
506///
507/// The venerable `Vec<u64>` works as a general container for arbitrary offests,
508/// but it can be non-optimal for various patterns of offset, including constant
509/// inter-offset spacing, and relatively short runs (compared to a `RankSelect`).
510pub mod offsets {
511
512
513    pub use array::Fixeds;
514    pub use stride::Strides;
515
516    /// An offset container that encodes a constant spacing in its type.
517    ///
518    /// Any attempt to push any value will result in pushing the next value
519    /// at the specified spacing. This type is only appropriate in certain
520    /// contexts, for example when storing `[T; K]` array types, or having
521    /// introspected a `Strides` and found it to be only one constant stride.
522    mod array {
523
524        use alloc::{vec::Vec, string::String};
525        use crate::{Container, Borrow, Index, Len, Push};
526        use crate::common::index::CopyAs;
527
528        /// An offset container that encodes a constant `K` spacing.
529        #[derive(Copy, Clone, Debug, Default)]
530        pub struct Fixeds<const K: u64, CC = u64> { pub count: CC }
531
532        impl<const K: u64> Borrow for Fixeds<K> {
533            type Ref<'a> = u64;
534            type Borrowed<'a> = Fixeds<K, &'a u64>;
535            #[inline(always)]
536            fn borrow<'a>(&'a self) -> Self::Borrowed<'a> { Fixeds { count: &self.count } }
537            #[inline(always)]
538            fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where Self: 'a {
539                Fixeds { count: thing.count }
540            }
541            #[inline(always)]
542            fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
543        }
544
545        impl<const K: u64> Container for Fixeds<K> {
546            #[inline(always)]
547            fn extend_from_self(&mut self, _other: Self::Borrowed<'_>, range: core::ops::Range<usize>) {
548                self.count += range.len() as u64;
549            }
550
551            fn reserve_for<'a, I>(&mut self, _selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone { }
552        }
553
554        impl<const K: u64, CC: CopyAs<u64>> Len for Fixeds<K, CC> {
555            #[inline(always)] fn len(&self) -> usize { self.count.copy_as() as usize }
556        }
557
558        impl<const K: u64, CC> Index for Fixeds<K, CC> {
559            type Ref = u64;
560            #[inline(always)]
561            fn get(&self, index: usize) -> Self::Ref { (index as u64 + 1) * K }
562        }
563        impl<'a, const K: u64, CC> Index for &'a Fixeds<K, CC> {
564            type Ref = u64;
565            #[inline(always)]
566            fn get(&self, index: usize) -> Self::Ref { (index as u64 + 1) * K }
567        }
568
569        impl<'a, const K: u64, T> Push<T> for Fixeds<K> {
570            // TODO: check for overflow?
571            #[inline(always)]
572            fn push(&mut self, _item: T) { self.count += 1; }
573            #[inline(always)]
574            fn extend(&mut self, iter: impl IntoIterator<Item=T>) {
575                self.count += iter.into_iter().count() as u64;
576            }
577        }
578
579        impl<const K: u64> crate::Clear for Fixeds<K> {
580            #[inline(always)]
581            fn clear(&mut self) { self.count = 0; }
582        }
583
584        impl<'a, const K: u64> crate::AsBytes<'a> for Fixeds<K, &'a u64> {
585            const SLICE_COUNT: usize = 1;
586            #[inline]
587            fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
588                debug_assert!(index < Self::SLICE_COUNT);
589                (8, bytemuck::cast_slice(core::slice::from_ref(self.count)))
590            }
591        }
592        impl<'a, const K: u64> crate::FromBytes<'a> for Fixeds<K, &'a u64> {
593            const SLICE_COUNT: usize = 1;
594            #[inline(always)]
595            fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
596                Self { count: &bytemuck::try_cast_slice(bytes.next().expect("Iterator exhausted prematurely")).unwrap()[0] }
597            }
598            #[inline(always)]
599            fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
600                let (w, _) = store.get(*offset); *offset += 1;
601                debug_assert!(!w.is_empty(), "Fixeds::from_store: empty count slice");
602                Self { count: w.first().unwrap_or(&0) }
603            }
604            #[inline(always)]
605            fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
606                sizes.push(8);
607                Ok(())
608            }
609            fn validate(slices: &[(&[u64], u8)]) -> Result<(), String> {
610                if slices.is_empty() || slices[0].0.is_empty() {
611                    return Err("Fixeds: count slice must be non-empty".into());
612                }
613                Ok(())
614            }
615        }
616
617        use super::Strides;
618        impl<const K: u64> core::convert::TryFrom<Strides> for Fixeds<K> {
619            type Error = Strides;
620            fn try_from(item: Strides) -> Result<Self, Self::Error> {
621                if item.strided() == Some(K) { Ok( Self { count: item.head[1] } ) } else { Err(item) }
622            }
623        }
624        impl<'a, const K: u64> core::convert::TryFrom<Strides<&'a [u64], &'a [u64]>> for Fixeds<K, &'a u64> {
625            type Error = Strides<&'a [u64], &'a [u64]>;
626            fn try_from(item: Strides<&'a [u64], &'a [u64]>) -> Result<Self, Self::Error> {
627                if item.strided() == Some(K) { Ok( Self { count: &item.head[1] } ) } else { Err(item) }
628            }
629        }
630    }
631
632    /// An general offset container optimized for fixed inter-offset sizes.
633    ///
634    /// Although it can handle general offsets, it starts with the optimistic
635    /// assumption that the offsets will be evenly spaced from zero, and while
636    /// that holds it will maintain the stride and length. Should it stop being
637    /// true, when a non-confirming offset is pushed, it will start to store
638    /// the offsets in a general container.
639    mod stride {
640
641        use alloc::{vec::Vec, string::String};
642        use core::ops::Deref;
643        use crate::{Container, Borrow, Index, IndexAs, Len, Push, Clear, AsBytes, FromBytes};
644
645        /// Columnar store for non-decreasing `u64` offsets with stride optimization.
646        ///
647        /// `head` holds `[stride, length]`: when the first `length` offsets follow a
648        /// regular stride pattern (`(i+1) * stride`), they are stored implicitly.
649        /// Remaining offsets go into `bounds`. In the owned form `head` is `[u64; 2]`;
650        /// in the borrowed form it is `&[u64]` of length 2.
651        #[derive(Copy, Clone, Debug, Default)]
652        pub struct Strides<BC = Vec<u64>, HC = [u64; 2]> {
653            pub head: HC,
654            pub bounds: BC,
655        }
656
657        impl Borrow for Strides {
658            type Ref<'a> = u64;
659            type Borrowed<'a> = Strides<&'a [u64], &'a [u64]>;
660
661            #[inline(always)] fn borrow<'a>(&'a self) -> Self::Borrowed<'a> { Strides { head: &self.head, bounds: &self.bounds[..] } }
662            #[inline(always)] fn reborrow<'b, 'a: 'b>(item: Self::Borrowed<'a>) -> Self::Borrowed<'b> where Self: 'a {
663                Strides { head: item.head, bounds: item.bounds }
664            }
665            #[inline(always)] fn reborrow_ref<'b, 'a: 'b>(item: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { item }
666        }
667
668        impl Container for Strides {
669            fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
670                self.bounds.reserve_for(selves.map(|x| x.bounds))
671            }
672        }
673
674        impl<'a> Push<&'a u64> for Strides { #[inline(always)] fn push(&mut self, item: &'a u64) { self.push(*item) } }
675        impl Push<u64> for Strides { #[inline(always)] fn push(&mut self, item: u64) { self.push(item) } }
676        impl Clear for Strides { #[inline(always)] fn clear(&mut self) { self.clear() } }
677
678        impl<BC: Len, HC: IndexAs<u64>> Len for Strides<BC, HC> {
679            #[inline(always)]
680            fn len(&self) -> usize { self.head.index_as(1) as usize + self.bounds.len() }
681        }
682        impl<BC: IndexAs<u64>, HC: IndexAs<u64>> Index for Strides<BC, HC> {
683            type Ref = u64;
684            #[inline(always)]
685            fn get(&self, index: usize) -> Self::Ref {
686                let index = index as u64;
687                let length = self.head.index_as(1);
688                let stride = self.head.index_as(0);
689                if index < length { (index+1) * stride } else { self.bounds.index_as((index - length) as usize) }
690            }
691        }
692
693        impl<'a, BC: AsBytes<'a>> AsBytes<'a> for Strides<BC, &'a [u64]> {
694            const SLICE_COUNT: usize = 1 + BC::SLICE_COUNT;
695            #[inline]
696            fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
697                debug_assert!(index < Self::SLICE_COUNT);
698                if index < 1 {
699                    (8u64, bytemuck::cast_slice(self.head))
700                } else {
701                    self.bounds.get_byte_slice(index - 1)
702                }
703            }
704        }
705        impl<'a, BC: FromBytes<'a>> FromBytes<'a> for Strides<BC, &'a [u64]> {
706            const SLICE_COUNT: usize = 1 + BC::SLICE_COUNT;
707            #[inline(always)]
708            fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
709                let head: &[u64] = bytemuck::try_cast_slice(bytes.next().expect("Iterator exhausted prematurely")).unwrap();
710                let bounds = BC::from_bytes(bytes);
711                Self { head, bounds }
712            }
713            #[inline(always)]
714            fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
715                let (head, _) = store.get(*offset); *offset += 1;
716                debug_assert!(head.len() >= 2, "Strides::from_store: head slice too short (len {})", head.len());
717                let bounds = BC::from_store(store, offset);
718                Self { head, bounds }
719            }
720            #[inline(always)]
721            fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
722                sizes.push(8); // head: [stride, length]
723                BC::element_sizes(sizes)
724            }
725            fn validate(slices: &[(&[u64], u8)]) -> Result<(), String> {
726                if slices.is_empty() || slices[0].0.len() < 2 {
727                    return Err("Strides: head slice must have at least 2 elements (stride, length)".into());
728                }
729                BC::validate(&slices[1..])
730            }
731        }
732
733        impl Strides {
734            pub fn new(stride: u64, length: u64) -> Self {
735                Self { head: [stride, length], bounds: Vec::default() }
736            }
737            #[inline(always)]
738            pub fn push(&mut self, item: u64) {
739                if self.head[1] == 0 {
740                    self.head[0] = item;
741                    self.head[1] = 1;
742                }
743                else if !self.bounds.is_empty() {
744                    self.bounds.push(item);
745                }
746                else if item == self.head[0] * (self.head[1] + 1) {
747                    self.head[1] += 1;
748                }
749                else {
750                    self.bounds.push(item);
751                }
752            }
753            /// Removes the last element, if non-empty.
754            ///
755            /// If empty, will trip a debug assert, but wrap in release.
756            #[inline(always)]
757            pub fn pop(&mut self) {
758                debug_assert!(self.len() > 0);
759                if self.bounds.is_empty() { self.head[1] -= 1; }
760                else { self.bounds.pop(); }
761            }
762            #[inline(always)]
763            pub fn clear(&mut self) {
764                self.head = [0, 0];
765                self.bounds.clear();
766            }
767        }
768
769        impl<BC: Deref<Target=[u64]>, HC: IndexAs<u64>> Strides<BC, HC> {
770            #[inline(always)]
771            pub fn bounds(&self, index: usize) -> (usize, usize) {
772                let stride = self.head.index_as(0);
773                let length = self.head.index_as(1);
774                let index = index as u64;
775                let lower = if index == 0 { 0 } else {
776                    let index = index - 1;
777                    if index < length { (index+1) * stride } else { self.bounds[(index - length) as usize] }
778                } as usize;
779                let upper = if index < length { (index+1) * stride } else { self.bounds[(index - length) as usize] } as usize;
780                (lower, upper)
781            }
782        }
783        impl<BC: Len, HC: IndexAs<u64>> Strides<BC, HC> {
784            #[inline(always)] pub fn strided(&self) -> Option<u64> {
785                if self.bounds.is_empty() {
786                    Some(self.head.index_as(0))
787                }
788                else { None }
789            }
790        }
791    }
792
793    #[cfg(test)]
794    mod test {
795        use alloc::vec::Vec;
796        #[test]
797        fn round_trip() {
798
799            use crate::common::{Index, Push, Len};
800            use crate::{Borrow, Vecs};
801            use crate::primitive::offsets::{Strides, Fixeds};
802
803            let mut cols = Vecs::<Vec::<i32>, Strides>::default();
804            for i in 0 .. 100 {
805                cols.push(&[1i32, 2, i]);
806            }
807
808            let cols = Vecs {
809                bounds: TryInto::<Fixeds<3>>::try_into(cols.bounds).unwrap(),
810                values: cols.values,
811            };
812
813            assert_eq!(cols.borrow().len(), 100);
814            for i in 0 .. 100 {
815                assert_eq!(cols.borrow().get(i).len(), 3);
816            }
817
818            let mut cols = Vecs {
819                bounds: Strides::new(3, cols.bounds.count),
820                values: cols.values
821            };
822
823            cols.push(&[0, 0]);
824            assert!(TryInto::<Fixeds<3>>::try_into(cols.bounds).is_err());
825        }
826    }
827}
828
829pub use empty::Empties;
830/// A columnar store for `()`.
831mod empty {
832
833    use alloc::{vec::Vec, string::String};
834    use crate::common::index::CopyAs;
835    use crate::{Clear, Columnar, Container, Len, IndexMut, Index, Push, Borrow};
836
837    #[derive(Copy, Clone, Debug, Default)]
838    pub struct Empties<CC = u64> { pub count: CC, pub empty: () }
839
840    impl Columnar for () {
841        #[inline(always)]
842        fn into_owned<'a>(_other: crate::Ref<'a, Self>) -> Self { }
843        type Container = Empties;
844    }
845
846    impl Borrow for Empties {
847        type Ref<'a> = ();
848        type Borrowed<'a> = Empties<&'a u64>;
849        #[inline(always)]
850        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> { Empties { count: &self.count, empty: () } }
851        #[inline(always)]
852        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where Self: 'a {
853            Empties { count: thing.count, empty: () }
854        }
855        #[inline(always)]
856        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
857    }
858
859    impl Container for Empties {
860        #[inline(always)]
861        fn extend_from_self(&mut self, _other: Self::Borrowed<'_>, range: core::ops::Range<usize>) {
862            self.count += range.len() as u64;
863        }
864
865        fn reserve_for<'a, I>(&mut self, _selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone { }
866    }
867
868    impl<CC: CopyAs<u64>> Len for Empties<CC> {
869        #[inline(always)] fn len(&self) -> usize { self.count.copy_as() as usize }
870    }
871    impl<CC> IndexMut for Empties<CC> {
872        type IndexMut<'a> = &'a mut () where CC: 'a;
873        // TODO: panic if out of bounds?
874        #[inline(always)] fn get_mut(&mut self, _index: usize) -> Self::IndexMut<'_> { &mut self.empty }
875    }
876    impl<CC> Index for Empties<CC> {
877        type Ref = ();
878        #[inline(always)]
879        fn get(&self, _index: usize) -> Self::Ref { }
880    }
881    impl<'a, CC> Index for &'a Empties<CC> {
882        type Ref = &'a ();
883        #[inline(always)]
884        fn get(&self, _index: usize) -> Self::Ref { &() }
885    }
886    impl Push<()> for Empties {
887        // TODO: check for overflow?
888        #[inline(always)]
889        fn push(&mut self, _item: ()) { self.count += 1; }
890        #[inline(always)]
891        fn extend(&mut self, iter: impl IntoIterator<Item=()>) {
892            self.count += iter.into_iter().count() as u64;
893        }
894    }
895    impl<'a> Push<&'a ()> for Empties {
896        // TODO: check for overflow?
897        #[inline(always)]
898        fn push(&mut self, _item: &()) { self.count += 1; }
899        #[inline(always)]
900        fn extend(&mut self, iter: impl IntoIterator<Item=&'a ()>) {
901            self.count += iter.into_iter().count() as u64;
902        }
903    }
904
905    impl Clear for Empties {
906        #[inline(always)]
907        fn clear(&mut self) { self.count = 0; }
908    }
909
910    impl<'a> crate::AsBytes<'a> for crate::primitive::Empties<&'a u64> {
911        const SLICE_COUNT: usize = 1;
912        #[inline]
913        fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
914            debug_assert!(index < Self::SLICE_COUNT);
915            (8, bytemuck::cast_slice(core::slice::from_ref(self.count)))
916        }
917    }
918    impl<'a> crate::FromBytes<'a> for crate::primitive::Empties<&'a u64> {
919        const SLICE_COUNT: usize = 1;
920        #[inline(always)]
921        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
922            Self { count: &bytemuck::try_cast_slice(bytes.next().expect("Iterator exhausted prematurely")).unwrap()[0], empty: () }
923        }
924        #[inline(always)]
925        fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
926            let (w, _) = store.get(*offset); *offset += 1;
927            debug_assert!(!w.is_empty(), "Empties::from_store: empty count slice");
928            Self { count: w.first().unwrap_or(&0), empty: () }
929        }
930        #[inline(always)]
931        fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
932            sizes.push(8);
933            Ok(())
934        }
935        fn validate(slices: &[(&[u64], u8)]) -> Result<(), String> {
936            if slices.is_empty() || slices[0].0.is_empty() {
937                return Err("Empties: count slice must be non-empty".into());
938            }
939            Ok(())
940        }
941    }
942}
943
944pub use boolean::Bools;
945/// A columnar store for `bool`.
946mod boolean {
947
948    use alloc::{vec::Vec, string::String};
949    use crate::{Container, Clear, Len, Index, IndexAs, Push, Borrow};
950
951    /// A store for maintaining `Vec<bool>`.
952    ///
953    /// Packed bits are stored in `values` as complete `u64` words. The `tail`
954    /// holds `[last_word, last_bits]`: the partial word being filled and the
955    /// count of valid bits in it. In the owned form `tail` is `[u64; 2]`;
956    /// in the borrowed form it is `&[u64]` of length 2.
957    #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
958    #[derive(Copy, Clone, Debug, Default, PartialEq)]
959    pub struct Bools<VC = Vec<u64>, TC = [u64; 2]> {
960        /// The bundles of bits that form complete `u64` values.
961        pub values: VC,
962        /// `[last_word, last_bits]`: the partial word and the number of valid bits in it.
963        pub tail: TC,
964    }
965
966    impl crate::Columnar for bool {
967        #[inline(always)]
968        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { other }
969        type Container = Bools;
970    }
971
972    impl<VC: crate::common::BorrowIndexAs<u64>> Borrow for Bools<VC> {
973        type Ref<'a> = bool;
974        type Borrowed<'a> = Bools<VC::Borrowed<'a>, &'a [u64]> where VC: 'a;
975        #[inline(always)]
976        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
977            Bools {
978                values: self.values.borrow(),
979                tail: &self.tail,
980            }
981        }
982        #[inline(always)]
983        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where VC: 'a {
984            Bools {
985                values: VC::reborrow(thing.values),
986                tail: thing.tail,
987            }
988        }
989        #[inline(always)]
990        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
991    }
992
993    impl<VC: crate::common::PushIndexAs<u64>> Container for Bools<VC> {
994        #[inline]
995        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: core::ops::Range<usize>) {
996            self.extend_bits_from(&other, range)
997        }
998
999        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
1000            self.values.reserve_for(selves.map(|x| x.values))
1001        }
1002    }
1003
1004    impl<VC: Len + IndexAs<u64>, TC: IndexAs<u64>> Bools<VC, TC> {
1005        /// The `block`-th word of bits, which is the tail word for `block == self.values.len()`.
1006        #[inline(always)]
1007        fn word(&self, block: usize) -> u64 {
1008            debug_assert!(block <= self.values.len(), "Bools::word: block {block} beyond {} words", self.values.len());
1009            if block < self.values.len() { self.values.index_as(block) } else { self.tail.index_as(0) }
1010        }
1011        /// Reads `count` bits (at most 64) starting at bit `pos`, into the low bits of the result.
1012        ///
1013        /// Bits at positions `count` and above in the result are zero.
1014        #[inline]
1015        pub fn bits_at(&self, pos: usize, count: usize) -> u64 {
1016            debug_assert!(count <= 64, "Bools::bits_at: count {count} exceeds 64");
1017            debug_assert!(pos + count <= self.len(), "Bools::bits_at: range {pos}..{} exceeds length {}", pos + count, self.len());
1018            if count == 0 { return 0; }
1019            let block = pos / 64;
1020            let bit = pos % 64;
1021            let mut word = self.word(block) >> bit;
1022            if bit + count > 64 {
1023                word |= self.word(block + 1) << (64 - bit);
1024            }
1025            if count < 64 { word &= (1u64 << count) - 1; }
1026            word
1027        }
1028    }
1029
1030    impl<VC: for<'a> Push<&'a u64>> Bools<VC> {
1031        /// Appends the low `count` bits of `bits`, for `count` at most 64.
1032        ///
1033        /// Bits at positions `count` and above in `bits` must be zero.
1034        #[inline]
1035        pub fn push_bits(&mut self, bits: u64, count: usize) {
1036            debug_assert!(count <= 64, "Bools::push_bits: count {count} exceeds 64");
1037            debug_assert!(count == 64 || bits >> count == 0, "Bools::push_bits: bits set beyond count {count}");
1038            let valid = self.tail[1] as usize;
1039            self.tail[0] |= bits << valid;
1040            if valid + count >= 64 {
1041                // The tail word is full; commit it and keep the bits that did not fit.
1042                self.values.push(&self.tail[0]);
1043                self.tail[0] = if valid == 0 { 0 } else { bits >> (64 - valid) };
1044                self.tail[1] = (valid + count - 64) as u64;
1045            } else {
1046                self.tail[1] += count as u64;
1047            }
1048        }
1049        /// Appends the bits of `other` in `range`, a word at a time.
1050        pub fn extend_bits_from<VC2: Len + IndexAs<u64>, TC2: IndexAs<u64>>(&mut self, other: &Bools<VC2, TC2>, range: core::ops::Range<usize>) {
1051            assert!(range.end <= other.len(), "Bools::extend_bits_from: range {range:?} exceeds length {}", other.len());
1052            let mut pos = range.start;
1053            while pos < range.end {
1054                let count = core::cmp::min(64, range.end - pos);
1055                self.push_bits(other.bits_at(pos, count), count);
1056                pos += count;
1057            }
1058        }
1059    }
1060
1061    impl<'a, VC: crate::AsBytes<'a>> crate::AsBytes<'a> for crate::primitive::Bools<VC, &'a [u64]> {
1062        const SLICE_COUNT: usize = VC::SLICE_COUNT + 1;
1063        #[inline]
1064        fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
1065            debug_assert!(index < Self::SLICE_COUNT);
1066            if index < VC::SLICE_COUNT {
1067                self.values.get_byte_slice(index)
1068            } else {
1069                (core::mem::align_of::<u64>() as u64, bytemuck::cast_slice(self.tail))
1070            }
1071        }
1072    }
1073
1074    impl<'a, VC: crate::FromBytes<'a>> crate::FromBytes<'a> for crate::primitive::Bools<VC, &'a [u64]> {
1075        const SLICE_COUNT: usize = VC::SLICE_COUNT + 1;
1076        #[inline(always)]
1077        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
1078            let values = crate::FromBytes::from_bytes(bytes);
1079            let tail: &[u64] = bytemuck::try_cast_slice(bytes.next().expect("Iterator exhausted prematurely")).unwrap();
1080            Self { values, tail }
1081        }
1082        #[inline(always)]
1083        fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
1084            let values = VC::from_store(store, offset);
1085            let (tail, _) = store.get(*offset); *offset += 1;
1086            debug_assert!(tail.len() >= 2, "Bools::from_store: tail slice too short (len {})", tail.len());
1087            Self { values, tail }
1088        }
1089        #[inline(always)]
1090        fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
1091            VC::element_sizes(sizes)?;
1092            sizes.push(8); // tail: [last_word, last_bits]
1093            Ok(())
1094        }
1095        fn validate(slices: &[(&[u64], u8)]) -> Result<(), String> {
1096            if slices.len() < Self::SLICE_COUNT {
1097                return Err(format!("Bools: expected {} slices but got {}", Self::SLICE_COUNT, slices.len()));
1098            }
1099            VC::validate(slices)?;
1100            let vc = VC::SLICE_COUNT;
1101            if slices[vc].0.len() < 2 {
1102                return Err("Bools: tail slice must have at least 2 elements (last_word, last_bits)".into());
1103            }
1104            Ok(())
1105        }
1106    }
1107
1108    impl<VC: Len, TC: IndexAs<u64>> Len for Bools<VC, TC> {
1109        #[inline(always)] fn len(&self) -> usize { self.values.len() * 64 + (self.tail.index_as(1) as usize) }
1110    }
1111
1112    impl<VC: Len + IndexAs<u64>, TC: IndexAs<u64>> Index for Bools<VC, TC> {
1113        type Ref = bool;
1114        #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
1115            let block = index / 64;
1116            let word = if block == self.values.len() {
1117                self.tail.index_as(0)
1118            } else {
1119                self.values.index_as(block)
1120            };
1121            let bit = index % 64;
1122            (word >> bit) & 1 == 1
1123        }
1124    }
1125
1126    impl<VC: Len + IndexAs<u64>, TC: IndexAs<u64>> Index for &Bools<VC, TC> {
1127        type Ref = bool;
1128        #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
1129            (*self).get(index)
1130        }
1131    }
1132
1133    impl<VC: for<'a> Push<&'a u64>> Push<bool> for Bools<VC> {
1134        #[inline]
1135        fn push(&mut self, bit: bool) {
1136            self.tail[0] |= (bit as u64) << self.tail[1];
1137            self.tail[1] += 1;
1138            // If we have a fully formed word, commit it to `self.values`.
1139            if self.tail[1] == 64 {
1140                self.values.push(&self.tail[0]);
1141                self.tail = [0, 0];
1142            }
1143        }
1144    }
1145    impl<'a, VC: for<'b> Push<&'b u64>> Push<&'a bool> for Bools<VC> {
1146        #[inline(always)]
1147        fn push(&mut self, bit: &'a bool) {
1148            self.push(*bit)
1149        }
1150    }
1151
1152
1153    impl<VC: Clear> Clear for Bools<VC> {
1154        #[inline(always)]
1155        fn clear(&mut self) {
1156            self.values.clear();
1157            self.tail = [0, 0];
1158        }
1159    }
1160
1161    #[cfg(test)]
1162    mod test {
1163        use alloc::vec::Vec;
1164        use crate::{Borrow, Container, Index, Len, Push};
1165        use super::Bools;
1166
1167        struct Lcg(u64);
1168        impl Lcg {
1169            fn next(&mut self) -> u64 {
1170                self.0 = self.0.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
1171                self.0 >> 11
1172            }
1173        }
1174
1175        fn random_bools(rng: &mut Lcg, len: usize) -> (Bools, Vec<bool>) {
1176            let bits: Vec<bool> = (0..len).map(|_| rng.next() % 3 == 0).collect();
1177            let mut bools: Bools = Bools::default();
1178            for &bit in &bits { bools.push(bit); }
1179            (bools, bits)
1180        }
1181
1182        /// `extend_from_self` agrees with pushing one bit at a time, for random
1183        /// sources, destinations, and ranges, including ones spanning word boundaries.
1184        #[test]
1185        fn extend_from_self_matches_push() {
1186            let mut rng = Lcg(2026);
1187            for _ in 0..500 {
1188                let source_len = (rng.next() % 400) as usize;
1189                let (source, source_bits) = random_bools(&mut rng, source_len);
1190                let target_len = (rng.next() % 200) as usize;
1191                let (mut target, mut expected) = random_bools(&mut rng, target_len);
1192                let lower = if source_bits.is_empty() { 0 } else { (rng.next() as usize) % (source_bits.len() + 1) };
1193                let upper = lower + (rng.next() as usize) % (source_bits.len() - lower + 1);
1194                target.extend_from_self(source.borrow(), lower .. upper);
1195                expected.extend_from_slice(&source_bits[lower .. upper]);
1196                assert_eq!(target.len(), expected.len());
1197                assert!(target.tail[1] < 64);
1198                assert_eq!(target.values.len(), expected.len() / 64);
1199                assert_eq!(target.tail[0] >> target.tail[1], 0, "stale bits above the tail count");
1200                for (index, &bit) in expected.iter().enumerate() {
1201                    assert_eq!(target.get(index), bit, "bit {index} of {}", expected.len());
1202                }
1203            }
1204        }
1205
1206        #[test]
1207        #[should_panic]
1208        fn extend_from_self_out_of_range() {
1209            let (source, _) = random_bools(&mut Lcg(1), 10);
1210            let mut target: Bools = Bools::default();
1211            target.extend_from_self(source.borrow(), 5 .. 11);
1212        }
1213    }
1214
1215}
1216
1217pub use duration::Durations;
1218/// A columnar store for `core::time::Duration`.
1219mod duration {
1220
1221    use alloc::{vec::Vec, string::String};
1222    use core::time::Duration;
1223    use crate::{Container, Len, Index, IndexAs, Push, Clear, Borrow};
1224
1225    // `core::time::Duration` is equivalent to `(u64, u32)`, corresponding to seconds and nanoseconds.
1226    #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
1227    #[derive(Copy, Clone, Debug, Default, PartialEq)]
1228    pub struct Durations<SC = Vec<u64>, NC = Vec<u32>> {
1229        pub seconds: SC,
1230        pub nanoseconds: NC,
1231    }
1232
1233    impl crate::Columnar for Duration {
1234        #[inline(always)]
1235        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { other }
1236        type Container = Durations;
1237    }
1238
1239    impl<SC: crate::common::BorrowIndexAs<u64>, NC: crate::common::BorrowIndexAs<u32>> Borrow for Durations<SC, NC> {
1240        type Ref<'a> = Duration;
1241        type Borrowed<'a> = Durations<SC::Borrowed<'a>, NC::Borrowed<'a>> where SC: 'a, NC: 'a;
1242        #[inline(always)]
1243        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
1244            Durations {
1245                seconds: self.seconds.borrow(),
1246                nanoseconds: self.nanoseconds.borrow(),
1247            }
1248        }
1249        #[inline(always)]
1250        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where SC: 'a, NC: 'a {
1251            Durations {
1252                seconds: SC::reborrow(thing.seconds),
1253                nanoseconds: NC::reborrow(thing.nanoseconds),
1254            }
1255        }
1256        #[inline(always)]
1257        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
1258    }
1259
1260    impl<SC: crate::common::PushIndexAs<u64>, NC: crate::common::PushIndexAs<u32>> Container for Durations<SC, NC> {
1261        #[inline(always)]
1262        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: core::ops::Range<usize>) {
1263            self.seconds.extend_from_self(other.seconds, range.clone());
1264            self.nanoseconds.extend_from_self(other.nanoseconds, range);
1265        }
1266
1267        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
1268            self.seconds.reserve_for(selves.clone().map(|x| x.seconds));
1269            self.nanoseconds.reserve_for(selves.map(|x| x.nanoseconds));
1270        }
1271    }
1272
1273    impl<'a, SC: crate::AsBytes<'a>, NC: crate::AsBytes<'a>> crate::AsBytes<'a> for crate::primitive::Durations<SC, NC> {
1274        const SLICE_COUNT: usize = SC::SLICE_COUNT + NC::SLICE_COUNT;
1275        #[inline]
1276        fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
1277            debug_assert!(index < Self::SLICE_COUNT);
1278            if index < SC::SLICE_COUNT {
1279                self.seconds.get_byte_slice(index)
1280            } else {
1281                self.nanoseconds.get_byte_slice(index - SC::SLICE_COUNT)
1282            }
1283        }
1284    }
1285    impl<'a, SC: crate::FromBytes<'a>, NC: crate::FromBytes<'a>> crate::FromBytes<'a> for crate::primitive::Durations<SC, NC> {
1286        const SLICE_COUNT: usize = SC::SLICE_COUNT + NC::SLICE_COUNT;
1287        #[inline(always)]
1288        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
1289            Self {
1290                seconds: crate::FromBytes::from_bytes(bytes),
1291                nanoseconds: crate::FromBytes::from_bytes(bytes),
1292            }
1293        }
1294        #[inline(always)]
1295        fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
1296            Self {
1297                seconds: SC::from_store(store, offset),
1298                nanoseconds: NC::from_store(store, offset),
1299            }
1300        }
1301        #[inline(always)]
1302        fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
1303            SC::element_sizes(sizes)?;
1304            NC::element_sizes(sizes)
1305        }
1306    }
1307
1308    impl<SC: Len, NC> Len for Durations<SC, NC> {
1309        #[inline(always)] fn len(&self) -> usize { self.seconds.len() }
1310    }
1311
1312    impl<SC: IndexAs<u64>, NC: IndexAs<u32>> Index for Durations<SC, NC> {
1313        type Ref = Duration;
1314        #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
1315            Duration::new(self.seconds.index_as(index), self.nanoseconds.index_as(index))
1316        }
1317    }
1318    impl<SC: IndexAs<u64>, NC: IndexAs<u32>> Index for &Durations<SC, NC> {
1319        type Ref = Duration;
1320        #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
1321            Duration::new(self.seconds.index_as(index), self.nanoseconds.index_as(index))
1322        }
1323    }
1324
1325    impl<SC: for<'a> Push<&'a u64>, NC: for<'a> Push<&'a u32>> Push<core::time::Duration> for Durations<SC, NC> {
1326        #[inline]
1327        fn push(&mut self, item: core::time::Duration) {
1328            self.seconds.push(&item.as_secs());
1329            self.nanoseconds.push(&item.subsec_nanos());
1330        }
1331    }
1332    impl<'a, SC: for<'b> Push<&'b u64>, NC: for<'b> Push<&'b u32>> Push<&'a core::time::Duration> for Durations<SC, NC> {
1333        #[inline]
1334        fn push(&mut self, item: &'a core::time::Duration) {
1335            self.push(*item)
1336        }
1337    }
1338    impl<'a, SC: Push<&'a u64>, NC: Push<&'a u32>> Push<(&'a u64, &'a u32)> for Durations<SC, NC> {
1339        #[inline]
1340        fn push(&mut self, item: (&'a u64, &'a u32)) {
1341            self.seconds.push(item.0);
1342            self.nanoseconds.push(item.1);
1343        }
1344    }
1345
1346    impl<SC: Clear, NC: Clear> Clear for Durations<SC, NC> {
1347        #[inline(always)]
1348        fn clear(&mut self) {
1349            self.seconds.clear();
1350            self.nanoseconds.clear();
1351        }
1352    }
1353
1354}
1355
columnar/primitive.rs

columnar/
primitive.rs
