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