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        // TODO: There is probably a smart way to implement `extend_from_slice`, but it isn't trivial due to alignment.
995
996        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
997            self.values.reserve_for(selves.map(|x| x.values))
998        }
999    }
1000
1001    impl<'a, VC: crate::AsBytes<'a>> crate::AsBytes<'a> for crate::primitive::Bools<VC, &'a [u64]> {
1002        const SLICE_COUNT: usize = VC::SLICE_COUNT + 1;
1003        #[inline]
1004        fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
1005            debug_assert!(index < Self::SLICE_COUNT);
1006            if index < VC::SLICE_COUNT {
1007                self.values.get_byte_slice(index)
1008            } else {
1009                (core::mem::align_of::<u64>() as u64, bytemuck::cast_slice(self.tail))
1010            }
1011        }
1012    }
1013
1014    impl<'a, VC: crate::FromBytes<'a>> crate::FromBytes<'a> for crate::primitive::Bools<VC, &'a [u64]> {
1015        const SLICE_COUNT: usize = VC::SLICE_COUNT + 1;
1016        #[inline(always)]
1017        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
1018            let values = crate::FromBytes::from_bytes(bytes);
1019            let tail: &[u64] = bytemuck::try_cast_slice(bytes.next().expect("Iterator exhausted prematurely")).unwrap();
1020            Self { values, tail }
1021        }
1022        #[inline(always)]
1023        fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
1024            let values = VC::from_store(store, offset);
1025            let (tail, _) = store.get(*offset); *offset += 1;
1026            debug_assert!(tail.len() >= 2, "Bools::from_store: tail slice too short (len {})", tail.len());
1027            Self { values, tail }
1028        }
1029        #[inline(always)]
1030        fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
1031            VC::element_sizes(sizes)?;
1032            sizes.push(8); // tail: [last_word, last_bits]
1033            Ok(())
1034        }
1035        fn validate(slices: &[(&[u64], u8)]) -> Result<(), String> {
1036            if slices.len() < Self::SLICE_COUNT {
1037                return Err(format!("Bools: expected {} slices but got {}", Self::SLICE_COUNT, slices.len()));
1038            }
1039            VC::validate(slices)?;
1040            let vc = VC::SLICE_COUNT;
1041            if slices[vc].0.len() < 2 {
1042                return Err("Bools: tail slice must have at least 2 elements (last_word, last_bits)".into());
1043            }
1044            Ok(())
1045        }
1046    }
1047
1048    impl<VC: Len, TC: IndexAs<u64>> Len for Bools<VC, TC> {
1049        #[inline(always)] fn len(&self) -> usize { self.values.len() * 64 + (self.tail.index_as(1) as usize) }
1050    }
1051
1052    impl<VC: Len + IndexAs<u64>, TC: IndexAs<u64>> Index for Bools<VC, TC> {
1053        type Ref = bool;
1054        #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
1055            let block = index / 64;
1056            let word = if block == self.values.len() {
1057                self.tail.index_as(0)
1058            } else {
1059                self.values.index_as(block)
1060            };
1061            let bit = index % 64;
1062            (word >> bit) & 1 == 1
1063        }
1064    }
1065
1066    impl<VC: Len + IndexAs<u64>, TC: IndexAs<u64>> Index for &Bools<VC, TC> {
1067        type Ref = bool;
1068        #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
1069            (*self).get(index)
1070        }
1071    }
1072
1073    impl<VC: for<'a> Push<&'a u64>> Push<bool> for Bools<VC> {
1074        #[inline]
1075        fn push(&mut self, bit: bool) {
1076            self.tail[0] |= (bit as u64) << self.tail[1];
1077            self.tail[1] += 1;
1078            // If we have a fully formed word, commit it to `self.values`.
1079            if self.tail[1] == 64 {
1080                self.values.push(&self.tail[0]);
1081                self.tail = [0, 0];
1082            }
1083        }
1084    }
1085    impl<'a, VC: for<'b> Push<&'b u64>> Push<&'a bool> for Bools<VC> {
1086        #[inline(always)]
1087        fn push(&mut self, bit: &'a bool) {
1088            self.push(*bit)
1089        }
1090    }
1091
1092
1093    impl<VC: Clear> Clear for Bools<VC> {
1094        #[inline(always)]
1095        fn clear(&mut self) {
1096            self.values.clear();
1097            self.tail = [0, 0];
1098        }
1099    }
1100
1101}
1102
1103pub use duration::Durations;
1104/// A columnar store for `core::time::Duration`.
1105mod duration {
1106
1107    use alloc::{vec::Vec, string::String};
1108    use core::time::Duration;
1109    use crate::{Container, Len, Index, IndexAs, Push, Clear, Borrow};
1110
1111    // `core::time::Duration` is equivalent to `(u64, u32)`, corresponding to seconds and nanoseconds.
1112    #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
1113    #[derive(Copy, Clone, Debug, Default, PartialEq)]
1114    pub struct Durations<SC = Vec<u64>, NC = Vec<u32>> {
1115        pub seconds: SC,
1116        pub nanoseconds: NC,
1117    }
1118
1119    impl crate::Columnar for Duration {
1120        #[inline(always)]
1121        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { other }
1122        type Container = Durations;
1123    }
1124
1125    impl<SC: crate::common::BorrowIndexAs<u64>, NC: crate::common::BorrowIndexAs<u32>> Borrow for Durations<SC, NC> {
1126        type Ref<'a> = Duration;
1127        type Borrowed<'a> = Durations<SC::Borrowed<'a>, NC::Borrowed<'a>> where SC: 'a, NC: 'a;
1128        #[inline(always)]
1129        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
1130            Durations {
1131                seconds: self.seconds.borrow(),
1132                nanoseconds: self.nanoseconds.borrow(),
1133            }
1134        }
1135        #[inline(always)]
1136        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where SC: 'a, NC: 'a {
1137            Durations {
1138                seconds: SC::reborrow(thing.seconds),
1139                nanoseconds: NC::reborrow(thing.nanoseconds),
1140            }
1141        }
1142        #[inline(always)]
1143        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
1144    }
1145
1146    impl<SC: crate::common::PushIndexAs<u64>, NC: crate::common::PushIndexAs<u32>> Container for Durations<SC, NC> {
1147        #[inline(always)]
1148        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: core::ops::Range<usize>) {
1149            self.seconds.extend_from_self(other.seconds, range.clone());
1150            self.nanoseconds.extend_from_self(other.nanoseconds, range);
1151        }
1152
1153        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
1154            self.seconds.reserve_for(selves.clone().map(|x| x.seconds));
1155            self.nanoseconds.reserve_for(selves.map(|x| x.nanoseconds));
1156        }
1157    }
1158
1159    impl<'a, SC: crate::AsBytes<'a>, NC: crate::AsBytes<'a>> crate::AsBytes<'a> for crate::primitive::Durations<SC, NC> {
1160        const SLICE_COUNT: usize = SC::SLICE_COUNT + NC::SLICE_COUNT;
1161        #[inline]
1162        fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
1163            debug_assert!(index < Self::SLICE_COUNT);
1164            if index < SC::SLICE_COUNT {
1165                self.seconds.get_byte_slice(index)
1166            } else {
1167                self.nanoseconds.get_byte_slice(index - SC::SLICE_COUNT)
1168            }
1169        }
1170    }
1171    impl<'a, SC: crate::FromBytes<'a>, NC: crate::FromBytes<'a>> crate::FromBytes<'a> for crate::primitive::Durations<SC, NC> {
1172        const SLICE_COUNT: usize = SC::SLICE_COUNT + NC::SLICE_COUNT;
1173        #[inline(always)]
1174        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
1175            Self {
1176                seconds: crate::FromBytes::from_bytes(bytes),
1177                nanoseconds: crate::FromBytes::from_bytes(bytes),
1178            }
1179        }
1180        #[inline(always)]
1181        fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
1182            Self {
1183                seconds: SC::from_store(store, offset),
1184                nanoseconds: NC::from_store(store, offset),
1185            }
1186        }
1187        #[inline(always)]
1188        fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
1189            SC::element_sizes(sizes)?;
1190            NC::element_sizes(sizes)
1191        }
1192    }
1193
1194    impl<SC: Len, NC> Len for Durations<SC, NC> {
1195        #[inline(always)] fn len(&self) -> usize { self.seconds.len() }
1196    }
1197
1198    impl<SC: IndexAs<u64>, NC: IndexAs<u32>> Index for Durations<SC, NC> {
1199        type Ref = Duration;
1200        #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
1201            Duration::new(self.seconds.index_as(index), self.nanoseconds.index_as(index))
1202        }
1203    }
1204    impl<SC: IndexAs<u64>, NC: IndexAs<u32>> Index for &Durations<SC, NC> {
1205        type Ref = Duration;
1206        #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
1207            Duration::new(self.seconds.index_as(index), self.nanoseconds.index_as(index))
1208        }
1209    }
1210
1211    impl<SC: for<'a> Push<&'a u64>, NC: for<'a> Push<&'a u32>> Push<core::time::Duration> for Durations<SC, NC> {
1212        #[inline]
1213        fn push(&mut self, item: core::time::Duration) {
1214            self.seconds.push(&item.as_secs());
1215            self.nanoseconds.push(&item.subsec_nanos());
1216        }
1217    }
1218    impl<'a, SC: for<'b> Push<&'b u64>, NC: for<'b> Push<&'b u32>> Push<&'a core::time::Duration> for Durations<SC, NC> {
1219        #[inline]
1220        fn push(&mut self, item: &'a core::time::Duration) {
1221            self.push(*item)
1222        }
1223    }
1224    impl<'a, SC: Push<&'a u64>, NC: Push<&'a u32>> Push<(&'a u64, &'a u32)> for Durations<SC, NC> {
1225        #[inline]
1226        fn push(&mut self, item: (&'a u64, &'a u32)) {
1227            self.seconds.push(item.0);
1228            self.nanoseconds.push(item.1);
1229        }
1230    }
1231
1232    impl<SC: Clear, NC: Clear> Clear for Durations<SC, NC> {
1233        #[inline(always)]
1234        fn clear(&mut self) {
1235            self.seconds.clear();
1236            self.nanoseconds.clear();
1237        }
1238    }
1239
1240}
1241
columnar/primitive.rs

columnar/
primitive.rs
