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