columnar/
lib.rs

1//! Types supporting flat / "columnar" layout for complex types.
2//!
3//! The intent is to re-layout `Vec<T>` types into vectors of reduced
4//! complexity, repeatedly. One should be able to push and pop easily,
5//! but indexing will be more complicated because we likely won't have
6//! a real `T` lying around to return as a reference. Instead, we will
7//! use Generic Associated Types (GATs) to provide alternate references.
8
9// Re-export derive crate.
10extern crate columnar_derive;
11pub use columnar_derive::Columnar;
12
13pub mod adts;
14pub mod boxed;
15pub mod bytes;
16pub mod lookback;
17pub mod primitive;
18pub mod string;
19pub mod sums;
20pub mod vector;
21pub mod tuple;
22mod arc;
23mod rc;
24
25pub use bytemuck;
26
27pub use vector::Vecs;
28pub use string::Strings;
29pub use sums::{rank_select::RankSelect, result::Results, option::Options};
30pub use lookback::{Repeats, Lookbacks};
31
32/// A type that can be represented in columnar form.
33///
34/// For a running example, a type like `(A, Vec<B>)`.
35pub trait Columnar : 'static {
36    /// Repopulates `self` from a reference.
37    ///
38    /// By default this just calls `into_owned()`, but it can be overridden.
39    fn copy_from<'a>(&mut self, other: Ref<'a, Self>) where Self: Sized {
40        *self = Self::into_owned(other);
41    }
42    /// Produce an instance of `Self` from `Self::Ref<'a>`.
43    fn into_owned<'a>(other: Ref<'a, Self>) -> Self;
44
45    /// The type that stores the columnar representation.
46    ///
47    /// The container must support pushing both `&Self` and `Self::Ref<'_>`.
48    /// In our running example this might be `(Vec<A>, Vecs<Vec<B>>)`.
49    type Container: ContainerBytes + for<'a> Push<&'a Self>;
50
51    /// Converts a sequence of the references to the type into columnar form.
52    fn as_columns<'a, I>(selves: I) -> Self::Container where I: IntoIterator<Item=&'a Self>, Self: 'a {
53        let mut columns: Self::Container = Default::default();
54        for item in selves {
55            columns.push(item);
56        }
57        columns
58    }
59    /// Converts a sequence of the type into columnar form.
60    ///
61    /// This consumes the owned `Self` types but uses them only by reference.
62    /// Consider `as_columns()` instead if it is equally ergonomic.
63    fn into_columns<I>(selves: I) -> Self::Container where I: IntoIterator<Item = Self>, Self: Sized {
64        let mut columns: Self::Container = Default::default();
65        for item in selves {
66            columns.push(&item);
67        }
68        columns
69    }
70    /// Reborrows the reference type to a shorter lifetime.
71    ///
72    /// Implementations must not change the contents of the reference, and should mark
73    /// the function as `#[inline(always)]`. It is no-op to overcome limitations
74    /// of the borrow checker. In many cases, it is enough to return `thing` as-is.
75    ///
76    /// For example, when comparing two references `Ref<'a>` and `Ref<'b>`, we can
77    /// reborrow both to a local lifetime to compare them. This allows us to keep the
78    /// lifetimes `'a` and `'b` separate, while otherwise Rust would unify them.
79    #[inline(always)] fn reborrow<'b, 'a: 'b>(thing: Ref<'a, Self>) -> Ref<'b, Self> {
80        Self::Container::reborrow_ref(thing)
81    }
82}
83
84/// The container type of columnar type `T`.
85///
86/// Equivalent to `<T as Columnar>::Container`.
87pub type ContainerOf<T> = <T as Columnar>::Container;
88
89/// For a lifetime, the reference type of columnar type `T`.
90///
91/// Equivalent to `<ContainerOf<T> as Borrow>::Ref<'a>`.
92pub type Ref<'a, T> = <ContainerOf<T> as Borrow>::Ref<'a>;
93
94/// A type that can be borrowed into a preferred reference type.
95pub trait Borrow: Len + Clone + 'static {
96    /// For each lifetime, a reference with that lifetime.
97    ///
98    /// As an example, `(&'a A, &'a [B])`.
99    type Ref<'a> : Copy;
100    /// The type of a borrowed container.
101    ///
102    /// Corresponding to our example, `(&'a [A], Vecs<&'a [B], &'a [u64]>)`.
103    type Borrowed<'a>: Copy + Len + Index<Ref = Self::Ref<'a>> where Self: 'a;
104    /// Converts a reference to the type to a borrowed variant.
105    fn borrow<'a>(&'a self) -> Self::Borrowed<'a>;
106    /// Reborrows the borrowed type to a shorter lifetime. See [`Columnar::reborrow`] for details.
107    fn reborrow<'b, 'a: 'b>(item: Self::Borrowed<'a>) -> Self::Borrowed<'b> where Self: 'a;
108    /// Reborrows the borrowed type to a shorter lifetime. See [`Columnar::reborrow`] for details.
109    fn reborrow_ref<'b, 'a: 'b>(item: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a;
110}
111
112
113/// A container that can hold `C`, and provide its preferred references through [`Borrow`].
114///
115/// As an example, `(Vec<A>, Vecs<Vec<B>>)`.
116pub trait Container : Borrow + Clear + for<'a> Push<Self::Ref<'a>> + Default + Send {
117    /// Allocates an empty container that can be extended by `selves` without reallocation.
118    ///
119    /// This goal is optimistic, and some containers may struggle to size correctly, especially
120    /// if they employ compression or other variable-sizing techniques that respond to the data
121    /// and the order in which is it presented. Best effort, but still useful!
122    fn with_capacity_for<'a, I>(selves: I) -> Self
123    where
124        Self: 'a,
125        I: Iterator<Item = Self::Borrowed<'a>> + Clone
126    {
127        let mut output = Self::default();
128        output.reserve_for(selves);
129        output
130    }
131
132    // Ensure that `self` can extend from `selves` without reallocation.
133    fn reserve_for<'a, I>(&mut self, selves: I)
134    where
135        Self: 'a,
136        I: Iterator<Item = Self::Borrowed<'a>> + Clone;
137
138
139    /// Extends `self` by a range in `other`.
140    ///
141    /// This method has a default implementation, but can and should be specialized when ranges can be copied.
142    /// As an example, lists of lists are often backed by contiguous elements, all of which can be memcopied,
143    /// with only the offsets into them (the bounds) to push either before or after (rather than during).
144    #[inline(always)]
145    fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: std::ops::Range<usize>) {
146        self.extend(range.map(|i| other.get(i)))
147    }
148}
149
150impl<T: Clone + 'static> Borrow for Vec<T> {
151    type Ref<'a> = &'a T;
152    type Borrowed<'a> = &'a [T];
153    #[inline(always)] fn borrow<'a>(&'a self) -> Self::Borrowed<'a> { &self[..] }
154    #[inline(always)] fn reborrow<'b, 'a: 'b>(item: Self::Borrowed<'a>) -> Self::Borrowed<'b> where Self: 'a { item }
155    #[inline(always)] fn reborrow_ref<'b, 'a: 'b>(item: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { item }
156}
157
158impl<T: Clone + Send + 'static> Container for Vec<T> {
159    fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: std::ops::Range<usize>) {
160        self.extend_from_slice(&other[range])
161    }
162    fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
163        self.reserve(selves.map(|x| x.len()).sum::<usize>())
164    }
165}
166
167/// A container that can also be viewed as and reconstituted from bytes.
168pub trait ContainerBytes : Container + for<'a> Borrow<Borrowed<'a> : AsBytes<'a> + FromBytes<'a>> { }
169impl<C: Container + for<'a> Borrow<Borrowed<'a> : AsBytes<'a> + FromBytes<'a>>> ContainerBytes for C { }
170
171pub use common::{Clear, Len, Push, IndexMut, Index, IndexAs, HeapSize, Slice, AsBytes, FromBytes};
172/// Common traits and types that are re-used throughout the module.
173pub mod common {
174
175    /// A type with a length.
176    pub trait Len {
177        /// The number of contained elements.
178        fn len(&self) -> usize;
179        /// Whether this contains no elements.
180        fn is_empty(&self) -> bool {
181            self.len() == 0
182        }
183    }
184    impl<L: Len + ?Sized> Len for &L {
185        #[inline(always)] fn len(&self) -> usize { L::len(*self) }
186    }
187    impl<L: Len + ?Sized> Len for &mut L {
188        #[inline(always)] fn len(&self) -> usize { L::len(*self) }
189    }
190    impl<T> Len for Vec<T> {
191        #[inline(always)] fn len(&self) -> usize { self.len() }
192    }
193    impl<T> Len for [T] {
194        #[inline(always)] fn len(&self) -> usize { <[T]>::len(self) }
195    }
196
197    /// A type that can accept items of type `T`.
198    pub trait Push<T> {
199        /// Pushes an item onto `self`.
200        fn push(&mut self, item: T);
201        /// Pushes elements of an iterator onto `self`.
202        #[inline(always)] fn extend(&mut self, iter: impl IntoIterator<Item=T>) {
203            for item in iter {
204                self.push(item);
205            }
206        }
207    }
208    impl<T> Push<T> for Vec<T> {
209        #[inline(always)] fn push(&mut self, item: T) { self.push(item) }
210
211        #[inline(always)]
212        fn extend(&mut self, iter: impl IntoIterator<Item=T>) {
213            std::iter::Extend::extend(self, iter)
214        }
215    }
216    impl<'a, T: Clone> Push<&'a T> for Vec<T> {
217        #[inline(always)] fn push(&mut self, item: &'a T) { self.push(item.clone()) }
218
219        #[inline(always)]
220        fn extend(&mut self, iter: impl IntoIterator<Item=&'a T>) {
221            std::iter::Extend::extend(self, iter.into_iter().cloned())
222        }
223    }
224    impl<'a, T: Clone> Push<&'a [T]> for Vec<T> {
225        #[inline(always)] fn push(&mut self, item: &'a [T]) { self.clone_from_slice(item) }
226    }
227
228
229    pub use index::{Index, IndexMut, IndexAs};
230    /// Traits for accessing elements by `usize` indexes.
231    ///
232    /// There are several traits, with a core distinction being whether the returned reference depends on the lifetime of `&self`.
233    /// For one trait `Index` the result does not depend on this lifetime.
234    /// There is a third trait `IndexMut` that allows mutable access, that may be less commonly implemented.
235    pub mod index {
236
237        use crate::Len;
238        use crate::common::IterOwn;
239
240        /// A type that can be mutably accessed by `usize`.
241        pub trait IndexMut {
242            /// Type mutably referencing an indexed element.
243            type IndexMut<'a> where Self: 'a;
244            fn get_mut(& mut self, index: usize) -> Self::IndexMut<'_>;
245            /// A reference to the last element, should one exist.
246            #[inline(always)] fn last_mut(&mut self) -> Option<Self::IndexMut<'_>> where Self: Len {
247                if self.is_empty() { None }
248                else { Some(self.get_mut(self.len()-1)) }
249            }
250        }
251
252        impl<T: IndexMut + ?Sized> IndexMut for &mut T {
253            type IndexMut<'a> = T::IndexMut<'a> where Self: 'a;
254            #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> {
255                T::get_mut(*self, index)
256            }
257        }
258        impl<T> IndexMut for Vec<T> {
259            type IndexMut<'a> = &'a mut T where Self: 'a;
260            #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> { &mut self[index] }
261        }
262        impl<T> IndexMut for [T] {
263            type IndexMut<'a> = &'a mut T where Self: 'a;
264            #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> { &mut self[index] }
265        }
266
267        /// A type that can be accessed by `usize` but without borrowing `self`.
268        ///
269        /// This can be useful for types which include their own lifetimes, and
270        /// which wish to express that their reference has the same lifetime.
271        /// In the GAT `Index`, the `Ref<'_>` lifetime would be tied to `&self`.
272        ///
273        /// This trait may be challenging to implement for owning containers,
274        /// for example `Vec<_>`, which would need their `Ref` type to depend
275        /// on the lifetime of the `&self` borrow in the `get()` function.
276        pub trait Index {
277            /// The type returned by the `get` method.
278            ///
279            /// Notably, this does not vary with lifetime, and will not depend on the lifetime of `&self`.
280            type Ref;
281            fn get(&self, index: usize) -> Self::Ref;
282            #[inline(always)] fn last(&self) -> Option<Self::Ref> where Self: Len {
283                if self.is_empty() { None }
284                else { Some(self.get(self.len()-1)) }
285            }
286            /// Converts `&self` into an iterator.
287            ///
288            /// This has an awkward name to avoid collision with `iter()`, which may also be implemented.
289            #[inline(always)]
290            fn index_iter(&self) -> IterOwn<&Self> {
291                IterOwn {
292                    index: 0,
293                    slice: self,
294                }
295            }
296            /// Converts `self` into an iterator.
297            ///
298            /// This has an awkward name to avoid collision with `into_iter()`, which may also be implemented.
299            #[inline(always)]
300            fn into_index_iter(self) -> IterOwn<Self> where Self: Sized {
301                IterOwn {
302                    index: 0,
303                    slice: self,
304                }
305            }
306        }
307
308        // These implementations aim to reveal a longer lifetime, or to copy results to avoid a lifetime.
309        impl<'a, T> Index for &'a [T] {
310            type Ref = &'a T;
311            #[inline(always)] fn get(&self, index: usize) -> Self::Ref { &self[index] }
312        }
313        impl<T: Copy> Index for [T] {
314            type Ref = T;
315            #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self[index] }
316        }
317        impl<'a, T> Index for &'a Vec<T> {
318            type Ref = &'a T;
319            #[inline(always)] fn get(&self, index: usize) -> Self::Ref { &self[index] }
320        }
321        impl<T: Copy> Index for Vec<T> {
322            type Ref = T;
323            #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self[index] }
324        }
325
326
327        /// Types that can be converted into another type by copying.
328        ///
329        /// We use this trait to unify the ability of `T` and `&T` to be converted into `T`.
330        /// This is handy for copy types that we'd like to use, like `u8`, `u64` and `usize`.
331        pub trait CopyAs<T> : Copy {
332            fn copy_as(self) -> T;
333        }
334        impl<T: Copy> CopyAs<T> for &T {
335            #[inline(always)] fn copy_as(self) -> T { *self }
336        }
337        impl<T: Copy> CopyAs<T> for T {
338            #[inline(always)] fn copy_as(self) -> T { self }
339        }
340
341        pub trait IndexAs<T> {
342            fn index_as(&self, index: usize) -> T;
343            #[inline(always)] fn last(&self) -> Option<T> where Self: Len {
344                if self.is_empty() { None }
345                else { Some(self.index_as(self.len()-1)) }
346            }
347        }
348
349        impl<T: Index, S> IndexAs<S> for T where T::Ref: CopyAs<S> {
350            #[inline(always)] fn index_as(&self, index: usize) -> S { self.get(index).copy_as() }
351        }
352
353    }
354
355    use crate::{Borrow, Container};
356    use crate::common::index::CopyAs;
357    /// A composite trait which captures the ability `Index<Ref = T>`.
358    ///
359    /// Implement `CopyAs<T>` for the reference type.
360    pub trait BorrowIndexAs<T> : for<'a> Borrow<Ref<'a>: CopyAs<T>> { }
361    impl<T, C: for<'a> Borrow<Ref<'a>: CopyAs<T>>> BorrowIndexAs<T> for C { }
362    /// A composite trait which captures the ability `Push<&T>` and `Index<Ref = T>`.
363    ///
364    /// Implement `CopyAs<T>` for the reference type, and `Push<&'a T>` for the container.
365    pub trait PushIndexAs<T> : BorrowIndexAs<T> + Container + for<'a> Push<&'a T> { }
366    impl<T, C: BorrowIndexAs<T> + Container + for<'a> Push<&'a T>> PushIndexAs<T> for C { }
367
368    /// A type that can remove its contents and return to an empty state.
369    ///
370    /// Generally, this method does not release resources, and is used to make the container available for re-insertion.
371    pub trait Clear {
372        /// Clears `self`, without changing its capacity.
373        fn clear(&mut self);
374    }
375    // Vectors can be cleared.
376    impl<T> Clear for Vec<T> {
377        #[inline(always)] fn clear(&mut self) { self.clear() }
378    }
379    // Slice references can be cleared.
380    impl<T> Clear for &[T] {
381        #[inline(always)] fn clear(&mut self) { *self = &[]; }
382    }
383
384    pub trait HeapSize {
385        /// Active (len) and allocated (cap) heap sizes in bytes.
386        /// This should not include the size of `self` itself.
387        fn heap_size(&self) -> (usize, usize) { (0, 0) }
388    }
389
390    impl HeapSize for String {
391        fn heap_size(&self) -> (usize, usize) {
392            (self.len(), self.capacity())
393        }
394    }
395    impl<T: HeapSize> HeapSize for [T] {
396        fn heap_size(&self) -> (usize, usize) {
397            let mut l = std::mem::size_of_val(self);
398            let mut c = std::mem::size_of_val(self);
399            for item in self.iter() {
400                let (il, ic) = item.heap_size();
401                l += il;
402                c += ic;
403            }
404            (l, c)
405        }
406    }
407    impl<T: HeapSize> HeapSize for Vec<T> {
408        fn heap_size(&self) -> (usize, usize) {
409            let mut l = std::mem::size_of::<T>() * self.len();
410            let mut c = std::mem::size_of::<T>() * self.capacity();
411            for item in (self[..]).iter() {
412                let (il, ic) = item.heap_size();
413                l += il;
414                c += ic;
415            }
416            (l, c)
417        }
418    }
419
420    /// A struct representing a slice of a range of values.
421    ///
422    /// The lower and upper bounds should be meaningfully set on construction.
423    #[derive(Copy, Clone, Debug)]
424    pub struct Slice<S> {
425        pub lower: usize,
426        pub upper: usize,
427        pub slice: S,
428    }
429
430    impl<S> std::hash::Hash for Slice<S> where Self: Index<Ref: std::hash::Hash> {
431        fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
432            self.len().hash(state);
433            for i in 0 .. self.len() {
434                self.get(i).hash(state);
435            }
436        }
437    }
438
439    impl<S> Slice<S> {
440        pub fn slice<R: std::ops::RangeBounds<usize>>(self, range: R) -> Self {
441            use std::ops::Bound;
442            let lower = match range.start_bound() {
443                Bound::Included(s) => std::cmp::max(self.lower, *s),
444                Bound::Excluded(s) => std::cmp::max(self.lower, *s+1),
445                Bound::Unbounded => self.lower,
446            };
447            let upper = match range.end_bound() {
448                Bound::Included(s) => std::cmp::min(self.upper, *s+1),
449                Bound::Excluded(s) => std::cmp::min(self.upper, *s),
450                Bound::Unbounded => self.upper,
451            };
452            assert!(lower <= upper);
453            Self { lower, upper, slice: self.slice }
454        }
455        pub fn new(lower: u64, upper: u64, slice: S) -> Self {
456            let lower: usize = lower.try_into().expect("slice bounds must fit in `usize`");
457            let upper: usize = upper.try_into().expect("slice bounds must fit in `usize`");
458            Self { lower, upper, slice }
459        }
460        pub fn len(&self) -> usize { self.upper - self.lower }
461        /// Map the slice to another type.
462        pub(crate) fn map<T>(self, f: impl Fn(S) -> T) -> Slice<T> {
463            Slice {
464                lower: self.lower,
465                upper: self.upper,
466                slice: f(self.slice),
467            }
468        }
469    }
470
471    impl<S: Index> PartialEq for Slice<S> where S::Ref: PartialEq {
472        fn eq(&self, other: &Self) -> bool {
473            if self.len() != other.len() { return false; }
474            for i in 0 .. self.len() {
475                if self.get(i) != other.get(i) { return false; }
476            }
477            true
478        }
479    }
480    impl<S: Index> PartialEq<[S::Ref]> for Slice<S> where S::Ref: PartialEq {
481        fn eq(&self, other: &[S::Ref]) -> bool {
482            if self.len() != other.len() { return false; }
483            for i in 0 .. self.len() {
484                if self.get(i) != other[i] { return false; }
485            }
486            true
487        }
488    }
489    impl<S: Index> PartialEq<Vec<S::Ref>> for Slice<S> where S::Ref: PartialEq {
490        fn eq(&self, other: &Vec<S::Ref>) -> bool {
491            if self.len() != other.len() { return false; }
492            for i in 0 .. self.len() {
493                if self.get(i) != other[i] { return false; }
494            }
495            true
496        }
497    }
498
499    impl<S: Index> Eq for Slice<S> where S::Ref: Eq { }
500
501    impl<S: Index> PartialOrd for Slice<S> where S::Ref: PartialOrd {
502        fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
503            use std::cmp::Ordering;
504            let len = std::cmp::min(self.len(), other.len());
505
506            for i in 0 .. len {
507                match self.get(i).partial_cmp(&other.get(i)) {
508                    Some(Ordering::Equal) => (),
509                    not_equal => return not_equal,
510                }
511            }
512
513            self.len().partial_cmp(&other.len())
514        }
515    }
516
517    impl<S: Index> Ord for Slice<S> where S::Ref: Ord + Eq {
518        fn cmp(&self, other: &Self) -> std::cmp::Ordering {
519            use std::cmp::Ordering;
520            let len = std::cmp::min(self.len(), other.len());
521
522            for i in 0 .. len {
523                match self.get(i).cmp(&other.get(i)) {
524                    Ordering::Equal => (),
525                    not_equal => return not_equal,
526                }
527            }
528
529            self.len().cmp(&other.len())
530        }
531    }
532
533    impl<S> Len for Slice<S> {
534        #[inline(always)] fn len(&self) -> usize { self.len() }
535    }
536
537    impl<S: Index> Index for Slice<S> {
538        type Ref = S::Ref;
539        #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
540            assert!(index < self.upper - self.lower);
541            self.slice.get(self.lower + index)
542        }
543    }
544    impl<'a, S> Index for &'a Slice<S>
545    where
546        &'a S : Index,
547    {
548        type Ref = <&'a S as Index>::Ref;
549        #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
550            assert!(index < self.upper - self.lower);
551            (&self.slice).get(self.lower + index)
552        }
553    }
554
555    impl<S: IndexMut> IndexMut for Slice<S> {
556        type IndexMut<'a> = S::IndexMut<'a> where S: 'a;
557        #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> {
558            assert!(index < self.upper - self.lower);
559            self.slice.get_mut(self.lower + index)
560        }
561    }
562
563    impl<S: Index + Len> Slice<S> {
564        /// Converts the slice into an iterator.
565        ///
566        /// This method exists rather than an `IntoIterator` implementation to avoid
567        /// a conflicting implementation for pushing an `I: IntoIterator` into `Vecs`.
568        pub fn into_iter(self) -> IterOwn<Slice<S>> {
569            self.into_index_iter()
570        }
571    }
572
573    impl<'a, T> Slice<&'a [T]> {
574        pub fn as_slice(&self) -> &'a [T] {
575            &self.slice[self.lower .. self.upper]
576        }
577    }
578
579    pub struct IterOwn<S> {
580        index: usize,
581        slice: S,
582    }
583
584    impl<S> IterOwn<S> {
585        pub fn new(index: usize, slice: S) -> Self {
586            Self { index, slice }
587        }
588    }
589
590    impl<S: Index + Len> Iterator for IterOwn<S> {
591        type Item = S::Ref;
592        #[inline(always)] fn next(&mut self) -> Option<Self::Item> {
593            if self.index < self.slice.len() {
594                let result = self.slice.get(self.index);
595                self.index += 1;
596                Some(result)
597            } else {
598                None
599            }
600        }
601        #[inline(always)]
602        fn size_hint(&self) -> (usize, Option<usize>) {
603            (self.slice.len() - self.index, Some(self.slice.len() - self.index))
604        }
605    }
606
607    impl<S: Index + Len> ExactSizeIterator for IterOwn<S> { }
608
609    /// A type that can be viewed as byte slices with lifetime `'a`.
610    ///
611    /// Implementors of this trait almost certainly reference the lifetime `'a` themselves.
612    pub trait AsBytes<'a> {
613        /// Presents `self` as a sequence of byte slices, with their required alignment.
614        fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])>;
615    }
616
617    /// A type that can be reconstituted from byte slices with lifetime `'a`.
618    ///
619    /// Implementors of this trait almost certainly reference the lifetime `'a` themselves,
620    /// unless they actively deserialize the bytes (vs sit on the slices, as if zero-copy).
621    pub trait FromBytes<'a> {
622        /// Reconstructs `self` from a sequence of correctly aligned and sized bytes slices.
623        ///
624        /// The implementation is expected to consume the right number of items from the iterator,
625        /// which may go on to be used by other implementations of `FromBytes`.
626        ///
627        /// The implementation should aim for only doing trivial work, as it backs calls like
628        /// `borrow` for serialized containers.
629        ///
630        /// Implementations should almost always be marked as `#[inline(always)]` to ensure that
631        /// they are inlined. A single non-inlined function on a tree of `from_bytes` calls
632        /// can cause the performance to drop significantly.
633        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self;
634    }
635
636}
637
638/// Roaring bitmap (and similar) containers.
639pub mod roaring {
640
641    use crate::Results;
642
643    /// A container for `bool` that uses techniques from Roaring bitmaps.
644    ///
645    /// These techniques are to block the bits into blocks of 2^16 bits,
646    /// and to encode each block based on its density. Either a bitmap
647    /// for dense blocks or a list of set bits for sparse blocks.
648    ///
649    /// Additionally, other representations encode runs of set bits.
650    pub struct RoaringBits {
651        _inner: Results<[u64; 1024], Vec<u16>>,
652    }
653}
654
655pub use chain_mod::{chain, chain_one};
656
657pub mod chain_mod {
658    //! Chain iterators, or iterators and an item. Iterators that might improve inlining, at the
659    //! expense of not providing iterator maker traits.
660
661    /// Chain two iterators together. The result first iterates over `a`, then `b`, until both are
662    /// exhausted.
663    ///
664    /// This addresses a quirk where deep iterators would not be optimized to their full potential.
665    /// Here, functions are marked with `#[inline(always)]` to indicate that the compiler should
666    /// try hard to inline the iterators.
667    #[inline(always)]
668    pub fn chain<A: IntoIterator, B: IntoIterator<Item=A::Item>>(a: A, b: B) -> Chain<A::IntoIter, B::IntoIter> {
669        Chain { a: Some(a.into_iter()), b: Some(b.into_iter()) }
670    }
671
672    pub struct Chain<A, B> {
673        a: Option<A>,
674        b: Option<B>,
675    }
676
677    impl<A, B> Iterator for Chain<A, B>
678    where
679        A: Iterator,
680        B: Iterator<Item=A::Item>,
681    {
682        type Item = A::Item;
683
684        #[inline(always)]
685        fn next(&mut self) -> Option<Self::Item> {
686            if let Some(a) = self.a.as_mut() {
687                let x = a.next();
688                if x.is_none() {
689                    self.a = None;
690                } else {
691                    return x;
692                }
693            }
694            if let Some(b) = self.b.as_mut() {
695                let x = b.next();
696                if x.is_none() {
697                    self.b = None;
698                } else {
699                    return x;
700                }
701            }
702            None
703        }
704
705        #[inline]
706        fn fold<Acc, F>(self, mut acc: Acc, mut f: F) -> Acc
707        where
708            F: FnMut(Acc, Self::Item) -> Acc,
709        {
710            if let Some(a) = self.a {
711                acc = a.fold(acc, &mut f);
712            }
713            if let Some(b) = self.b {
714                acc = b.fold(acc, f);
715            }
716            acc
717        }
718    }
719
720    /// Chain a single item to an iterator. The resulting iterator first iterates over `a`,
721    /// then `b`. The resulting iterator is marked as `#[inline(always)]`, which in some situations
722    /// causes better inlining behavior with current Rust versions.
723    #[inline(always)]
724    pub fn chain_one<A: IntoIterator>(a: A, b: A::Item) -> ChainOne<A::IntoIter> {
725        ChainOne { a: Some(a.into_iter()), b: Some(b) }
726    }
727
728    pub struct ChainOne<A: Iterator> {
729        a: Option<A>,
730        b: Option<A::Item>,
731    }
732
733    impl<A: Iterator> Iterator for ChainOne<A> {
734        type Item = A::Item;
735
736        #[inline(always)]
737        fn next(&mut self) -> Option<Self::Item> {
738            if let Some(a) = self.a.as_mut() {
739                let x = a.next();
740                if x.is_none() {
741                    self.a = None;
742                    self.b.take()
743                } else {
744                    x
745                }
746            } else {
747                None
748            }
749        }
750    }
751
752    #[cfg(test)]
753    mod test {
754        use super::*;
755
756        #[test]
757        fn test_chain() {
758            let a = [1, 2, 3];
759            let b = [4, 5, 6];
760            let mut chain = chain(a, b);
761            assert_eq!(chain.next(), Some(1));
762            assert_eq!(chain.next(), Some(2));
763            assert_eq!(chain.next(), Some(3));
764            assert_eq!(chain.next(), Some(4));
765            assert_eq!(chain.next(), Some(5));
766            assert_eq!(chain.next(), Some(6));
767            assert_eq!(chain.next(), None);
768        }
769
770        #[test]
771        fn test_chain_one() {
772            let a = [1, 2, 3];
773            let b = 4;
774            let mut chain = chain_one(a, b);
775            assert_eq!(chain.next(), Some(1));
776            assert_eq!(chain.next(), Some(2));
777            assert_eq!(chain.next(), Some(3));
778            assert_eq!(chain.next(), Some(4));
779            assert_eq!(chain.next(), None);
780        }
781    }
782}
columnar/lib.rs

columnar/
lib.rs
