columnar/
primitive.rs

1//! Types that prefer to be represented by `Vec<T>`.
2
3use std::num::Wrapping;
4
5/// An implementation of opinions for types that want to use `Vec<T>`.
6macro_rules! implement_columnable {
7    ($($index_type:ty),*) => { $(
8        impl crate::Columnar for $index_type {
9            #[inline(always)]
10            fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { *other }
11
12            type Container = Vec<$index_type>;
13        }
14
15        impl crate::HeapSize for $index_type { }
16
17        impl<'a> crate::AsBytes<'a> for &'a [$index_type] {
18            #[inline(always)]
19            fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
20                std::iter::once((std::mem::align_of::<$index_type>() as u64, bytemuck::cast_slice(&self[..])))
21            }
22        }
23        impl<'a> crate::FromBytes<'a> for &'a [$index_type] {
24            #[inline(always)]
25            fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
26                // We use `unwrap()` here in order to panic with the `bytemuck` error, which may be informative.
27                bytemuck::try_cast_slice(bytes.next().expect("Iterator exhausted prematurely")).unwrap()
28            }
29        }
30        impl<'a, const N: usize> crate::AsBytes<'a> for &'a [[$index_type; N]] {
31            #[inline(always)]
32            fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
33                std::iter::once((std::mem::align_of::<$index_type>() as u64, bytemuck::cast_slice(&self[..])))
34            }
35        }
36        impl<'a, const N: usize> crate::FromBytes<'a> for &'a [[$index_type; N]] {
37            #[inline(always)]
38            fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
39                // We use `unwrap()` here in order to panic with the `bytemuck` error, which may be informative.
40                bytemuck::try_cast_slice(bytes.next().expect("Iterator exhausted prematurely")).unwrap()
41            }
42        }
43    )* }
44}
45
46implement_columnable!(u8, u16, u32, u64);
47implement_columnable!(i8, i16, i32, i64);
48implement_columnable!(f32, f64);
49implement_columnable!(Wrapping<u8>, Wrapping<u16>, Wrapping<u32>, Wrapping<u64>);
50implement_columnable!(Wrapping<i8>, Wrapping<i16>, Wrapping<i32>, Wrapping<i64>);
51
52pub use sizes::{Usizes, Isizes};
53/// Columnar stores for `usize` and `isize`, stored as 64 bits.
54mod sizes {
55
56    use crate::*;
57    use crate::common::{BorrowIndexAs, PushIndexAs};
58
59    #[derive(Copy, Clone, Default)]
60    pub struct Usizes<CV = Vec<u64>> { pub values: CV }
61
62    impl Columnar for usize {
63        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { other }
64        type Container = Usizes;
65    }
66
67    impl<CV: BorrowIndexAs<u64> + Len> Borrow for Usizes<CV> {
68        type Ref<'a> = usize;
69        type Borrowed<'a> = Usizes<CV::Borrowed<'a>> where CV: 'a;
70        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
71            Usizes { values: self.values.borrow() }
72        }
73        #[inline(always)]
74        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where CV: 'a {
75            Usizes { values: CV::reborrow(thing.values) }
76        }
77        #[inline(always)]
78        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
79    }
80
81    impl<CV: PushIndexAs<u64>> Container for Usizes<CV> {
82        #[inline(always)]
83        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: std::ops::Range<usize>) {
84            self.values.extend_from_self(other.values, range)
85        }
86
87        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
88            self.values.reserve_for(selves.map(|x| x.values))
89        }
90    }
91
92    impl<CV: Len> Len for Usizes<CV> { fn len(&self) -> usize { self.values.len() }}
93    impl IndexMut for Usizes {
94        type IndexMut<'a> = &'a mut u64;
95        #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> { &mut self.values[index] }
96    }
97    impl<CV: IndexAs<u64>> Index for Usizes<CV> {
98        type Ref = usize;
99        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self.values.index_as(index).try_into().expect("Usizes values should fit in `usize`") }
100    }
101    impl<CV: IndexAs<u64>> Index for &Usizes<CV> {
102        type Ref = usize;
103        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self.values.index_as(index).try_into().expect("Usizes values should fit in `usize`") }
104    }
105    impl<CV: for<'a> Push<&'a u64>> Push<usize> for Usizes<CV> {
106        #[inline]
107        fn push(&mut self, item: usize) { self.values.push(&item.try_into().expect("usize must fit in a u64")) }
108    }
109    impl Push<&usize> for Usizes {
110        #[inline]
111        fn push(&mut self, item: &usize) { self.values.push((*item).try_into().expect("usize must fit in a u64")) }
112    }
113    impl<CV: Clear> Clear for Usizes<CV> { fn clear(&mut self) { self.values.clear() }}
114
115    impl<CV: HeapSize> HeapSize for Usizes<CV> {
116        fn heap_size(&self) -> (usize, usize) {
117            self.values.heap_size()
118        }
119    }
120
121    impl<'a, CV: crate::AsBytes<'a>> crate::AsBytes<'a> for crate::primitive::Usizes<CV> {
122        #[inline(always)]
123        fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
124            self.values.as_bytes()
125        }
126    }
127
128    impl<'a, CV: crate::FromBytes<'a>> crate::FromBytes<'a> for crate::primitive::Usizes<CV> {
129        #[inline(always)]
130        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
131            Self { values: CV::from_bytes(bytes) }
132        }
133    }
134
135
136    #[derive(Copy, Clone, Default)]
137    pub struct Isizes<CV = Vec<i64>> { pub values: CV }
138
139    impl Columnar for isize {
140        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { other }
141        type Container = Isizes;
142    }
143
144    impl<CV: BorrowIndexAs<i64>> Borrow for Isizes<CV> {
145        type Ref<'a> = isize;
146        type Borrowed<'a> = Isizes<CV::Borrowed<'a>> where CV: 'a;
147        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
148            Isizes { values: self.values.borrow() }
149        }
150        #[inline(always)]
151        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where CV: 'a {
152            Isizes { values: CV::reborrow(thing.values) }
153        }
154        #[inline(always)]
155        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
156    }
157
158    impl<CV: PushIndexAs<i64>> Container for Isizes<CV> {
159        #[inline(always)]
160        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: std::ops::Range<usize>) {
161            self.values.extend_from_self(other.values, range)
162        }
163
164        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
165            self.values.reserve_for(selves.map(|x| x.values))
166        }
167    }
168
169    impl<CV: Len> Len for Isizes<CV> { fn len(&self) -> usize { self.values.len() }}
170    impl IndexMut for Isizes {
171        type IndexMut<'a> = &'a mut i64;
172        #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> { &mut self.values[index] }
173    }
174    impl<CV: IndexAs<i64>> Index for Isizes<CV> {
175        type Ref = isize;
176        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self.values.index_as(index).try_into().expect("Isizes values should fit in `isize`") }
177    }
178    impl<CV: IndexAs<i64>> Index for &Isizes<CV> {
179        type Ref = isize;
180        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self.values.index_as(index).try_into().expect("Isizes values should fit in `isize`") }
181    }
182    impl<CV: for<'a> Push<&'a i64>> Push<isize> for Isizes<CV> {
183        #[inline]
184        fn push(&mut self, item: isize) { self.values.push(&item.try_into().expect("isize must fit in a i64")) }
185    }
186    impl Push<&isize> for Isizes {
187        #[inline]
188        fn push(&mut self, item: &isize) { self.values.push((*item).try_into().expect("isize must fit in a i64")) }
189    }
190    impl<CV: Clear> Clear for Isizes<CV> { fn clear(&mut self) { self.values.clear() }}
191
192    impl<CV: HeapSize> HeapSize for Isizes<CV> {
193        fn heap_size(&self) -> (usize, usize) {
194            self.values.heap_size()
195        }
196    }
197
198    impl<'a, CV: crate::AsBytes<'a>> crate::AsBytes<'a> for crate::primitive::Isizes<CV> {
199        #[inline(always)]
200        fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
201            self.values.as_bytes()
202        }
203    }
204
205    impl<'a, CV: crate::FromBytes<'a>> crate::FromBytes<'a> for crate::primitive::Isizes<CV> {
206        #[inline(always)]
207        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
208            Self { values: CV::from_bytes(bytes) }
209        }
210    }
211}
212
213pub use chars::{Chars};
214/// Columnar store for `char`, stored as a `u32`.
215mod chars {
216
217    use crate::*;
218    use crate::common::{BorrowIndexAs, PushIndexAs};
219
220    type Encoded = u32;
221
222    #[derive(Copy, Clone, Default)]
223    pub struct Chars<CV = Vec<Encoded>> { pub values: CV }
224
225    impl Columnar for char {
226        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { other }
227        type Container = Chars;
228    }
229
230    impl<CV: BorrowIndexAs<Encoded>> Borrow for Chars<CV> {
231        type Ref<'a> = char;
232        type Borrowed<'a> = Chars<CV::Borrowed<'a>> where CV: 'a;
233        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
234            Chars { values: self.values.borrow() }
235        }
236        #[inline(always)]
237        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where CV: 'a {
238            Chars { values: CV::reborrow(thing.values) }
239        }
240        #[inline(always)]
241        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
242    }
243
244    impl<CV: PushIndexAs<Encoded>> Container for Chars<CV> {
245        #[inline(always)]
246        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: std::ops::Range<usize>) {
247            self.values.extend_from_self(other.values, range)
248        }
249
250        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
251            self.values.reserve_for(selves.map(|x| x.values))
252        }
253    }
254
255    impl<CV: Len> Len for Chars<CV> { fn len(&self) -> usize { self.values.len() }}
256    impl<CV: IndexAs<Encoded>> Index for Chars<CV> {
257        type Ref = char;
258        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { char::from_u32(self.values.index_as(index)).unwrap() }
259    }
260    impl<CV: IndexAs<Encoded>> Index for &Chars<CV> {
261        type Ref = char;
262        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { char::from_u32(self.values.index_as(index)).unwrap() }
263    }
264    impl<CV: for<'a> Push<&'a Encoded>> Push<char> for Chars<CV> {
265        #[inline]
266        fn push(&mut self, item: char) { self.values.push(&u32::from(item)) }
267    }
268    impl Push<&char> for Chars {
269        #[inline]
270        fn push(&mut self, item: &char) { self.values.push(u32::from(*item)) }
271    }
272    impl<CV: Clear> Clear for Chars<CV> { fn clear(&mut self) { self.values.clear() }}
273
274    impl<CV: HeapSize> HeapSize for Chars<CV> {
275        fn heap_size(&self) -> (usize, usize) {
276            self.values.heap_size()
277        }
278    }
279
280    impl<'a, CV: crate::AsBytes<'a>> crate::AsBytes<'a> for Chars<CV> {
281        #[inline(always)]
282        fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
283            self.values.as_bytes()
284        }
285    }
286
287    impl<'a, CV: crate::FromBytes<'a>> crate::FromBytes<'a> for Chars<CV> {
288        #[inline(always)]
289        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
290            Self { values: CV::from_bytes(bytes) }
291        }
292    }
293}
294
295pub use larges::{U128s, I128s};
296/// Columnar stores for `u128` and `i128`, stored as [u8; 16] bits.
297mod larges {
298
299    use crate::*;
300    use crate::common::{BorrowIndexAs, PushIndexAs};
301
302    type Encoded = [u8; 16];
303
304    #[derive(Copy, Clone, Default)]
305    pub struct U128s<CV = Vec<Encoded>> { pub values: CV }
306
307    impl Columnar for u128 {
308        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { other }
309        type Container = U128s;
310    }
311
312    impl<CV: BorrowIndexAs<Encoded>> Borrow for U128s<CV> {
313        type Ref<'a> = u128;
314        type Borrowed<'a> = U128s<CV::Borrowed<'a>> where CV: 'a;
315        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
316            U128s { values: self.values.borrow() }
317        }
318        #[inline(always)]
319        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where CV: 'a {
320            U128s { values: CV::reborrow(thing.values) }
321        }
322        #[inline(always)]
323        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
324    }
325
326    impl<CV: PushIndexAs<Encoded>> Container for U128s<CV> {
327        #[inline(always)]
328        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: std::ops::Range<usize>) {
329            self.values.extend_from_self(other.values, range)
330        }
331
332        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
333            self.values.reserve_for(selves.map(|x| x.values))
334        }
335    }
336
337    impl<CV: Len> Len for U128s<CV> { fn len(&self) -> usize { self.values.len() }}
338    impl<CV: IndexAs<Encoded>> Index for U128s<CV> {
339        type Ref = u128;
340        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { u128::from_le_bytes(self.values.index_as(index)) }
341    }
342    impl<CV: IndexAs<Encoded>> Index for &U128s<CV> {
343        type Ref = u128;
344        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { u128::from_le_bytes(self.values.index_as(index)) }
345    }
346    impl<CV: for<'a> Push<&'a Encoded>> Push<u128> for U128s<CV> {
347        #[inline]
348        fn push(&mut self, item: u128) { self.values.push(&item.to_le_bytes()) }
349    }
350    impl Push<&u128> for U128s {
351        #[inline]
352        fn push(&mut self, item: &u128) { self.values.push(item.to_le_bytes()) }
353    }
354    impl<CV: Clear> Clear for U128s<CV> { fn clear(&mut self) { self.values.clear() }}
355
356    impl<CV: HeapSize> HeapSize for U128s<CV> {
357        fn heap_size(&self) -> (usize, usize) {
358            self.values.heap_size()
359        }
360    }
361
362    impl<'a, CV: crate::AsBytes<'a>> crate::AsBytes<'a> for U128s<CV> {
363        #[inline(always)]
364        fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
365            self.values.as_bytes()
366        }
367    }
368
369    impl<'a, CV: crate::FromBytes<'a>> crate::FromBytes<'a> for U128s<CV> {
370        #[inline(always)]
371        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
372            Self { values: CV::from_bytes(bytes) }
373        }
374    }
375
376    #[derive(Copy, Clone, Default)]
377    pub struct I128s<CV = Vec<Encoded>> { pub values: CV }
378
379    impl Columnar for i128 {
380        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { other }
381        type Container = I128s;
382    }
383
384    impl<CV: BorrowIndexAs<Encoded>> Borrow for I128s<CV> {
385        type Ref<'a> = i128;
386        type Borrowed<'a> = I128s<CV::Borrowed<'a>> where CV: 'a;
387        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
388            I128s { values: self.values.borrow() }
389        }
390        #[inline(always)]
391        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where CV: 'a {
392            I128s { values: CV::reborrow(thing.values) }
393        }
394        #[inline(always)]
395        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
396    }
397
398    impl<CV: PushIndexAs<Encoded>> Container for I128s<CV> {
399        #[inline(always)]
400        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: std::ops::Range<usize>) {
401            self.values.extend_from_self(other.values, range)
402        }
403
404        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
405            self.values.reserve_for(selves.map(|x| x.values))
406        }
407    }
408
409    impl<CV: Len> Len for I128s<CV> { fn len(&self) -> usize { self.values.len() }}
410    impl<CV: IndexAs<Encoded>> Index for I128s<CV> {
411        type Ref = i128;
412        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { i128::from_le_bytes(self.values.index_as(index)) }
413    }
414    impl<CV: IndexAs<Encoded>> Index for &I128s<CV> {
415        type Ref = i128;
416        #[inline(always)] fn get(&self, index: usize) -> Self::Ref { i128::from_le_bytes(self.values.index_as(index)) }
417    }
418    impl<CV: for<'a> Push<&'a Encoded>> Push<i128> for I128s<CV> {
419        #[inline]
420        fn push(&mut self, item: i128) { self.values.push(&item.to_le_bytes()) }
421    }
422    impl Push<&i128> for I128s {
423        #[inline]
424        fn push(&mut self, item: &i128) { self.values.push(item.to_le_bytes()) }
425    }
426    impl<CV: Clear> Clear for I128s<CV> { fn clear(&mut self) { self.values.clear() }}
427
428    impl<CV: HeapSize> HeapSize for I128s<CV> {
429        fn heap_size(&self) -> (usize, usize) {
430            self.values.heap_size()
431        }
432    }
433
434    impl<'a, CV: crate::AsBytes<'a>> crate::AsBytes<'a> for I128s<CV> {
435        #[inline(always)]
436        fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
437            self.values.as_bytes()
438        }
439    }
440
441    impl<'a, CV: crate::FromBytes<'a>> crate::FromBytes<'a> for I128s<CV> {
442        #[inline(always)]
443        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
444            Self { values: CV::from_bytes(bytes) }
445        }
446    }
447}
448
449/// Columnar stores for non-decreasing `u64`, stored in various ways.
450///
451/// The venerable `Vec<u64>` works as a general container for arbitrary offests,
452/// but it can be non-optimal for various patterns of offset, including constant
453/// inter-offset spacing, and relatively short runs (compared to a `RankSelect`).
454pub mod offsets {
455
456    pub use array::Fixeds;
457    pub use stride::Strides;
458
459    /// An offset container that encodes a constant spacing in its type.
460    ///
461    /// Any attempt to push any value will result in pushing the next value
462    /// at the specified spacing. This type is only appropriate in certain
463    /// contexts, for example when storing `[T; K]` array types, or having
464    /// introspected a `Strides` and found it to be only one constant stride.
465    mod array {
466
467        use crate::{Container, Borrow, Index, Len, Push};
468        use crate::common::index::CopyAs;
469
470        /// An offset container that encodes a constant `K` spacing.
471        #[derive(Copy, Clone, Debug, Default)]
472        pub struct Fixeds<const K: u64, CC = u64> { pub count: CC }
473
474        impl<const K: u64> Borrow for Fixeds<K> {
475            type Ref<'a> = u64;
476            type Borrowed<'a> = Fixeds<K, &'a u64>;
477            #[inline(always)]
478            fn borrow<'a>(&'a self) -> Self::Borrowed<'a> { Fixeds { count: &self.count } }
479            #[inline(always)]
480            fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where Self: 'a {
481                Fixeds { count: thing.count }
482            }
483            #[inline(always)]
484            fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
485        }
486
487        impl<const K: u64> Container for Fixeds<K> {
488            #[inline(always)]
489            fn extend_from_self(&mut self, _other: Self::Borrowed<'_>, range: std::ops::Range<usize>) {
490                self.count += range.len() as u64;
491            }
492
493            fn reserve_for<'a, I>(&mut self, _selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone { }
494        }
495
496        impl<const K: u64, CC: CopyAs<u64>> Len for Fixeds<K, CC> {
497            #[inline(always)] fn len(&self) -> usize { self.count.copy_as() as usize }
498        }
499
500        impl<const K: u64, CC> Index for Fixeds<K, CC> {
501            type Ref = u64;
502            #[inline(always)]
503            fn get(&self, index: usize) -> Self::Ref { (index as u64 + 1) * K }
504        }
505        impl<'a, const K: u64, CC> Index for &'a Fixeds<K, CC> {
506            type Ref = u64;
507            #[inline(always)]
508            fn get(&self, index: usize) -> Self::Ref { (index as u64 + 1) * K }
509        }
510
511        impl<'a, const K: u64, T> Push<T> for Fixeds<K> {
512            // TODO: check for overflow?
513            #[inline(always)]
514            fn push(&mut self, _item: T) { self.count += 1; }
515            #[inline(always)]
516            fn extend(&mut self, iter: impl IntoIterator<Item=T>) {
517                self.count += iter.into_iter().count() as u64;
518            }
519        }
520
521        impl<const K: u64> crate::HeapSize for Fixeds<K> {
522            #[inline(always)]
523            fn heap_size(&self) -> (usize, usize) { (0, 0) }
524        }
525        impl<const K: u64> crate::Clear for Fixeds<K> {
526            #[inline(always)]
527            fn clear(&mut self) { self.count = 0; }
528        }
529
530        impl<'a, const K: u64> crate::AsBytes<'a> for Fixeds<K, &'a u64> {
531            #[inline(always)]
532            fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
533                std::iter::once((8, bytemuck::cast_slice(std::slice::from_ref(self.count))))
534            }
535        }
536        impl<'a, const K: u64> crate::FromBytes<'a> for Fixeds<K, &'a u64> {
537            #[inline(always)]
538            fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
539                Self { count: &bytemuck::try_cast_slice(bytes.next().expect("Iterator exhausted prematurely")).unwrap()[0] }
540            }
541        }
542
543        use super::Strides;
544        impl<const K: u64, BC: Len, CC: CopyAs<u64>> std::convert::TryFrom<Strides<BC, CC>> for Fixeds<K, CC> {
545            // On error we return the original.
546            type Error = Strides<BC, CC>;
547            fn try_from(item: Strides<BC, CC>) -> Result<Self, Self::Error> {
548                if item.strided() == Some(K) { Ok( Self { count: item.length } ) } else { Err(item) }
549            }
550        }
551    }
552
553    /// An general offset container optimized for fixed inter-offset sizes.
554    ///
555    /// Although it can handle general offsets, it starts with the optimistic
556    /// assumption that the offsets will be evenly spaced from zero, and while
557    /// that holds it will maintain the stride and length. Should it stop being
558    /// true, when a non-confirming offset is pushed, it will start to store
559    /// the offsets in a general container.
560    mod stride {
561
562        use std::ops::Deref;
563        use crate::{Container, Borrow, Index, Len, Push, Clear, AsBytes, FromBytes};
564        use crate::common::index::CopyAs;
565
566        /// The first two integers describe a stride pattern, [stride, length].
567        ///
568        /// If the length is zero the collection is empty. The first `item` pushed
569        /// always becomes the first list element. The next element is the number of
570        /// items at position `i` whose value is `item * (i+1)`. After this comes
571        /// the remaining entries in the bounds container.
572        #[derive(Copy, Clone, Debug, Default)]
573        pub struct Strides<BC = Vec<u64>, CC = u64> {
574            pub stride: CC,
575            pub length: CC,
576            pub bounds: BC,
577        }
578
579        impl Borrow for Strides {
580            type Ref<'a> = u64;
581            type Borrowed<'a> = Strides<&'a [u64], &'a u64>;
582
583            #[inline(always)] fn borrow<'a>(&'a self) -> Self::Borrowed<'a> { Strides { stride: &self.stride, length: &self.length, bounds: &self.bounds[..] } }
584            /// Reborrows the borrowed type to a shorter lifetime. See [`Columnar::reborrow`] for details.
585            #[inline(always)] fn reborrow<'b, 'a: 'b>(item: Self::Borrowed<'a>) -> Self::Borrowed<'b> where Self: 'a {
586                Strides { stride: item.stride, length: item.length, bounds: item.bounds }
587            }
588            /// Reborrows the borrowed type to a shorter lifetime. See [`Columnar::reborrow`] for details.
589                #[inline(always)]fn reborrow_ref<'b, 'a: 'b>(item: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { item }
590        }
591
592        impl Container for Strides {
593            fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
594                self.bounds.reserve_for(selves.map(|x| x.bounds))
595            }
596        }
597
598        impl<'a> Push<&'a u64> for Strides { #[inline(always)] fn push(&mut self, item: &'a u64) { self.push(*item) } }
599        impl Push<u64> for Strides { #[inline(always)] fn push(&mut self, item: u64) { self.push(item) } }
600        impl Clear for Strides { #[inline(always)] fn clear(&mut self) { self.clear() } }
601
602        impl<BC: Len, CC: CopyAs<u64>> Len for Strides<BC, CC> {
603            #[inline(always)]
604            fn len(&self) -> usize { self.length.copy_as() as usize + self.bounds.len() }
605        }
606        impl Index for Strides<&[u64], &u64> {
607            type Ref = u64;
608            #[inline(always)]
609            fn get(&self, index: usize) -> Self::Ref {
610                let index = index as u64;
611                if index < *self.length { (index+1) * self.stride } else { self.bounds[(index - self.length) as usize] }
612            }
613        }
614
615        impl<'a, BC: AsBytes<'a>> AsBytes<'a> for Strides<BC, &'a u64> {
616            #[inline(always)]
617            fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
618                let stride = std::iter::once((8, bytemuck::cast_slice(std::slice::from_ref(self.stride))));
619                let length = std::iter::once((8, bytemuck::cast_slice(std::slice::from_ref(self.length))));
620                let bounds = self.bounds.as_bytes();
621                crate::chain(stride, crate::chain(length, bounds))
622            }
623        }
624        impl<'a, BC: FromBytes<'a>> FromBytes<'a> for Strides<BC, &'a u64> {
625            #[inline(always)]
626            fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
627                let stride = &bytemuck::try_cast_slice(bytes.next().expect("Iterator exhausted prematurely")).unwrap()[0];
628                let length = &bytemuck::try_cast_slice(bytes.next().expect("Iterator exhausted prematurely")).unwrap()[0];
629                let bounds = BC::from_bytes(bytes);
630                Self { stride, length, bounds }
631            }
632        }
633
634        impl Strides {
635            pub fn new(stride: u64, length: u64) -> Self {
636                Self { stride, length, bounds: Vec::default() }
637            }
638            #[inline(always)]
639            pub fn push(&mut self, item: u64) {
640                if self.length == 0 {
641                    self.stride = item;
642                    self.length = 1;
643                }
644                else if !self.bounds.is_empty() {
645                    self.bounds.push(item);
646                }
647                else if item == self.stride * (self.length + 1) {
648                    self.length += 1;
649                }
650                else {
651                    self.bounds.push(item);
652                }
653            }
654            #[inline(always)]
655            pub fn clear(&mut self) {
656                self.stride = 0;
657                self.length = 0;
658                self.bounds.clear();
659            }
660        }
661
662        impl<BC: Deref<Target=[u64]>, CC: CopyAs<u64>> Strides<BC, CC> {
663            #[inline(always)]
664            pub fn bounds(&self, index: usize) -> (usize, usize) {
665                let stride = self.stride.copy_as();
666                let length = self.length.copy_as();
667                let index = index as u64;
668                let lower = if index == 0 { 0 } else {
669                    let index = index - 1;
670                    if index < length { (index+1) * stride } else { self.bounds[(index - length) as usize] }
671                } as usize;
672                let upper = if index < length { (index+1) * stride } else { self.bounds[(index - length) as usize] } as usize;
673                (lower, upper)
674            }
675        }
676        impl<BC: Len, CC: CopyAs<u64>> Strides<BC, CC> {
677            #[inline(always)] pub fn strided(&self) -> Option<u64> {
678                if self.bounds.is_empty() {
679                    Some(self.stride.copy_as())
680                }
681                else { None }
682            }
683        }
684    }
685
686    #[cfg(test)]
687    mod test {
688        #[test]
689        fn round_trip() {
690
691            use crate::common::{Index, Push, Len};
692            use crate::{Borrow, Vecs};
693            use crate::primitive::offsets::{Strides, Fixeds};
694
695            let mut cols = Vecs::<Vec::<i32>, Strides>::default();
696            for i in 0 .. 100 {
697                cols.push(&[1i32, 2, i]);
698            }
699
700            let cols = Vecs {
701                bounds: TryInto::<Fixeds<3>>::try_into(cols.bounds).unwrap(),
702                values: cols.values,
703            };
704
705            assert_eq!(cols.borrow().len(), 100);
706            for i in 0 .. 100 {
707                assert_eq!(cols.borrow().get(i).len(), 3);
708            }
709
710            let mut cols = Vecs {
711                bounds: Strides::new(3, cols.bounds.count),
712                values: cols.values
713            };
714
715            cols.push(&[0, 0]);
716            assert!(TryInto::<Fixeds<3>>::try_into(cols.bounds).is_err());
717        }
718    }
719}
720
721pub use empty::Empties;
722/// A columnar store for `()`.
723mod empty {
724
725    use crate::common::index::CopyAs;
726    use crate::{Clear, Columnar, Container, Len, IndexMut, Index, Push, HeapSize, Borrow};
727
728    #[derive(Copy, Clone, Debug, Default)]
729    pub struct Empties<CC = u64> { pub count: CC, pub empty: () }
730
731    impl Columnar for () {
732        #[inline(always)]
733        fn into_owned<'a>(_other: crate::Ref<'a, Self>) -> Self { }
734        type Container = Empties;
735    }
736
737    impl Borrow for Empties {
738        type Ref<'a> = ();
739        type Borrowed<'a> = Empties<&'a u64>;
740        #[inline(always)]
741        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> { Empties { count: &self.count, empty: () } }
742        #[inline(always)]
743        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where Self: 'a {
744            Empties { count: thing.count, empty: () }
745        }
746        #[inline(always)]
747        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
748    }
749
750    impl Container for Empties {
751        #[inline(always)]
752        fn extend_from_self(&mut self, _other: Self::Borrowed<'_>, range: std::ops::Range<usize>) {
753            self.count += range.len() as u64;
754        }
755
756        fn reserve_for<'a, I>(&mut self, _selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone { }
757    }
758
759    impl<CC: CopyAs<u64>> Len for Empties<CC> {
760        #[inline(always)] fn len(&self) -> usize { self.count.copy_as() as usize }
761    }
762    impl<CC> IndexMut for Empties<CC> {
763        type IndexMut<'a> = &'a mut () where CC: 'a;
764        // TODO: panic if out of bounds?
765        #[inline(always)] fn get_mut(&mut self, _index: usize) -> Self::IndexMut<'_> { &mut self.empty }
766    }
767    impl<CC> Index for Empties<CC> {
768        type Ref = ();
769        #[inline(always)]
770        fn get(&self, _index: usize) -> Self::Ref { }
771    }
772    impl<'a, CC> Index for &'a Empties<CC> {
773        type Ref = &'a ();
774        #[inline(always)]
775        fn get(&self, _index: usize) -> Self::Ref { &() }
776    }
777    impl Push<()> for Empties {
778        // TODO: check for overflow?
779        #[inline(always)]
780        fn push(&mut self, _item: ()) { self.count += 1; }
781        #[inline(always)]
782        fn extend(&mut self, iter: impl IntoIterator<Item=()>) {
783            self.count += iter.into_iter().count() as u64;
784        }
785    }
786    impl<'a> Push<&'a ()> for Empties {
787        // TODO: check for overflow?
788        #[inline(always)]
789        fn push(&mut self, _item: &()) { self.count += 1; }
790        #[inline(always)]
791        fn extend(&mut self, iter: impl IntoIterator<Item=&'a ()>) {
792            self.count += iter.into_iter().count() as u64;
793        }
794    }
795
796    impl HeapSize for Empties {
797        #[inline(always)]
798        fn heap_size(&self) -> (usize, usize) { (0, 0) }
799    }
800    impl Clear for Empties {
801        #[inline(always)]
802        fn clear(&mut self) { self.count = 0; }
803    }
804
805    impl<'a> crate::AsBytes<'a> for crate::primitive::Empties<&'a u64> {
806        #[inline(always)]
807        fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
808            std::iter::once((8, bytemuck::cast_slice(std::slice::from_ref(self.count))))
809        }
810    }
811    impl<'a> crate::FromBytes<'a> for crate::primitive::Empties<&'a u64> {
812        #[inline(always)]
813        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
814            Self { count: &bytemuck::try_cast_slice(bytes.next().expect("Iterator exhausted prematurely")).unwrap()[0], empty: () }
815        }
816    }
817}
818
819pub use boolean::Bools;
820/// A columnar store for `bool`.
821mod boolean {
822
823    use crate::common::index::CopyAs;
824    use crate::{Container, Clear, Len, Index, IndexAs, Push, HeapSize, Borrow};
825
826    /// A store for maintaining `Vec<bool>`.
827    #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
828    #[derive(Copy, Clone, Debug, Default, PartialEq)]
829    pub struct Bools<VC = Vec<u64>, WC = u64> {
830        /// The bundles of bits that form complete `u64` values.
831        pub values: VC,
832        /// The work-in-progress bits that are not yet complete.
833        pub last_word: WC,
834        /// The number of set bits in `bits.last()`.
835        pub last_bits: WC,
836    }
837
838    impl crate::Columnar for bool {
839        #[inline(always)]
840        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { other }
841        type Container = Bools;
842    }
843
844    impl<VC: crate::common::BorrowIndexAs<u64>> Borrow for Bools<VC> {
845        type Ref<'a> = bool;
846        type Borrowed<'a> = Bools<VC::Borrowed<'a>, &'a u64> where VC: 'a;
847        #[inline(always)]
848        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
849            Bools {
850                values: self.values.borrow(),
851                last_word: &self.last_word,
852                last_bits: &self.last_bits,
853            }
854        }
855        #[inline(always)]
856        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where VC: 'a {
857            Bools {
858                values: VC::reborrow(thing.values),
859                last_word: thing.last_word,
860                last_bits: thing.last_bits,
861            }
862        }
863        #[inline(always)]
864        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
865    }
866
867    impl<VC: crate::common::PushIndexAs<u64>> Container for Bools<VC> {
868        // TODO: There is probably a smart way to implement `extend_from_slice`, but it isn't trivial due to alignment.
869
870        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
871            self.values.reserve_for(selves.map(|x| x.values))
872        }
873    }
874
875    impl<'a, VC: crate::AsBytes<'a>> crate::AsBytes<'a> for crate::primitive::Bools<VC, &'a u64> {
876        #[inline(always)]
877        fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
878            let iter = self.values.as_bytes();
879            let iter = crate::chain_one(iter, (std::mem::align_of::<u64>() as u64, bytemuck::cast_slice(std::slice::from_ref(self.last_word))));
880            crate::chain_one(iter, (std::mem::align_of::<u64>() as u64, bytemuck::cast_slice(std::slice::from_ref(self.last_bits))))
881        }
882    }
883
884    impl<'a, VC: crate::FromBytes<'a>> crate::FromBytes<'a> for crate::primitive::Bools<VC, &'a u64> {
885        #[inline(always)]
886        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
887            let values = crate::FromBytes::from_bytes(bytes);
888            let last_word = &bytemuck::try_cast_slice(bytes.next().expect("Iterator exhausted prematurely")).unwrap()[0];
889            let last_bits = &bytemuck::try_cast_slice(bytes.next().expect("Iterator exhausted prematurely")).unwrap()[0];
890            Self { values, last_word, last_bits }
891        }
892    }
893
894    impl<VC: Len, WC: CopyAs<u64>> Len for Bools<VC, WC> {
895        #[inline(always)] fn len(&self) -> usize { self.values.len() * 64 + (self.last_bits.copy_as() as usize) }
896    }
897
898    impl<VC: Len + IndexAs<u64>, WC: CopyAs<u64>> Index for Bools<VC, WC> {
899        type Ref = bool;
900        #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
901            let block = index / 64;
902            let word = if block == self.values.len() {
903                self.last_word.copy_as()
904            } else {
905                self.values.index_as(block)
906            };
907            let bit = index % 64;
908            (word >> bit) & 1 == 1
909        }
910    }
911
912    impl<VC: Len + IndexAs<u64>, WC: CopyAs<u64>> Index for &Bools<VC, WC> {
913        type Ref = bool;
914        #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
915            (*self).get(index)
916        }
917    }
918
919    impl<VC: for<'a> Push<&'a u64>> Push<bool> for Bools<VC> {
920        #[inline]
921        fn push(&mut self, bit: bool) {
922            self.last_word |= (bit as u64) << self.last_bits;
923            self.last_bits += 1;
924            // If we have a fully formed word, commit it to `self.values`.
925            if self.last_bits == 64 {
926                self.values.push(&self.last_word);
927                self.last_word = 0;
928                self.last_bits = 0;
929            }
930        }
931    }
932    impl<'a, VC: for<'b> Push<&'b u64>> Push<&'a bool> for Bools<VC> {
933        #[inline(always)]
934        fn push(&mut self, bit: &'a bool) {
935            self.push(*bit)
936        }
937    }
938
939
940    impl<VC: Clear> Clear for Bools<VC> {
941        #[inline(always)]
942        fn clear(&mut self) {
943            self.values.clear();
944            self.last_word = 0;
945            self.last_bits = 0;
946        }
947    }
948
949    impl<VC: HeapSize> HeapSize for Bools<VC> {
950        #[inline(always)]
951        fn heap_size(&self) -> (usize, usize) {
952            self.values.heap_size()
953        }
954    }
955}
956
957pub use duration::Durations;
958/// A columnar store for `std::time::Duration`.
959mod duration {
960
961    use std::time::Duration;
962    use crate::{Container, Len, Index, IndexAs, Push, Clear, HeapSize, Borrow};
963
964    // `std::time::Duration` is equivalent to `(u64, u32)`, corresponding to seconds and nanoseconds.
965    #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
966    #[derive(Copy, Clone, Debug, Default, PartialEq)]
967    pub struct Durations<SC = Vec<u64>, NC = Vec<u32>> {
968        pub seconds: SC,
969        pub nanoseconds: NC,
970    }
971
972    impl crate::Columnar for Duration {
973        #[inline(always)]
974        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self { other }
975        type Container = Durations;
976    }
977
978    impl<SC: crate::common::BorrowIndexAs<u64>, NC: crate::common::BorrowIndexAs<u32>> Borrow for Durations<SC, NC> {
979        type Ref<'a> = Duration;
980        type Borrowed<'a> = Durations<SC::Borrowed<'a>, NC::Borrowed<'a>> where SC: 'a, NC: 'a;
981        #[inline(always)]
982        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
983            Durations {
984                seconds: self.seconds.borrow(),
985                nanoseconds: self.nanoseconds.borrow(),
986            }
987        }
988        #[inline(always)]
989        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where SC: 'a, NC: 'a {
990            Durations {
991                seconds: SC::reborrow(thing.seconds),
992                nanoseconds: NC::reborrow(thing.nanoseconds),
993            }
994        }
995        #[inline(always)]
996        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { thing }
997    }
998
999    impl<SC: crate::common::PushIndexAs<u64>, NC: crate::common::PushIndexAs<u32>> Container for Durations<SC, NC> {
1000        #[inline(always)]
1001        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: std::ops::Range<usize>) {
1002            self.seconds.extend_from_self(other.seconds, range.clone());
1003            self.nanoseconds.extend_from_self(other.nanoseconds, range);
1004        }
1005
1006        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
1007            self.seconds.reserve_for(selves.clone().map(|x| x.seconds));
1008            self.nanoseconds.reserve_for(selves.map(|x| x.nanoseconds));
1009        }
1010    }
1011
1012    impl<'a, SC: crate::AsBytes<'a>, NC: crate::AsBytes<'a>> crate::AsBytes<'a> for crate::primitive::Durations<SC, NC> {
1013        #[inline(always)]
1014        fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
1015            crate::chain(self.seconds.as_bytes(), self.nanoseconds.as_bytes())
1016        }
1017    }
1018    impl<'a, SC: crate::FromBytes<'a>, NC: crate::FromBytes<'a>> crate::FromBytes<'a> for crate::primitive::Durations<SC, NC> {
1019        #[inline(always)]
1020        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
1021            Self {
1022                seconds: crate::FromBytes::from_bytes(bytes),
1023                nanoseconds: crate::FromBytes::from_bytes(bytes),
1024            }
1025        }
1026    }
1027
1028    impl<SC: Len, NC> Len for Durations<SC, NC> {
1029        #[inline(always)] fn len(&self) -> usize { self.seconds.len() }
1030    }
1031
1032    impl<SC: IndexAs<u64>, NC: IndexAs<u32>> Index for Durations<SC, NC> {
1033        type Ref = Duration;
1034        #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
1035            Duration::new(self.seconds.index_as(index), self.nanoseconds.index_as(index))
1036        }
1037    }
1038
1039    impl<SC: for<'a> Push<&'a u64>, NC: for<'a> Push<&'a u32>> Push<std::time::Duration> for Durations<SC, NC> {
1040        #[inline]
1041        fn push(&mut self, item: std::time::Duration) {
1042            self.seconds.push(&item.as_secs());
1043            self.nanoseconds.push(&item.subsec_nanos());
1044        }
1045    }
1046    impl<'a, SC: for<'b> Push<&'b u64>, NC: for<'b> Push<&'b u32>> Push<&'a std::time::Duration> for Durations<SC, NC> {
1047        #[inline]
1048        fn push(&mut self, item: &'a std::time::Duration) {
1049            self.push(*item)
1050        }
1051    }
1052    impl<'a, SC: Push<&'a u64>, NC: Push<&'a u32>> Push<(&'a u64, &'a u32)> for Durations<SC, NC> {
1053        #[inline]
1054        fn push(&mut self, item: (&'a u64, &'a u32)) {
1055            self.seconds.push(item.0);
1056            self.nanoseconds.push(item.1);
1057        }
1058    }
1059
1060    impl<SC: Clear, NC: Clear> Clear for Durations<SC, NC> {
1061        #[inline(always)]
1062        fn clear(&mut self) {
1063            self.seconds.clear();
1064            self.nanoseconds.clear();
1065        }
1066    }
1067
1068    impl<SC: HeapSize, NC: HeapSize> HeapSize for Durations<SC, NC> {
1069        #[inline(always)]
1070        fn heap_size(&self) -> (usize, usize) {
1071            let (l0, c0) = self.seconds.heap_size();
1072            let (l1, c1) = self.nanoseconds.heap_size();
1073            (l0 + l1, c0 + c1)
1074        }
1075    }
1076}
1077
columnar/primitive.rs

columnar/
primitive.rs
