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.clone_from_slice(item) }
254 }
255
256
257 pub use index::{Index, IndexMut, IndexAs};
258 /// Traits for accessing elements by `usize` indexes.
259 ///
260 /// There are several traits, with a core distinction being whether the returned reference depends on the lifetime of `&self`.
261 /// For one trait `Index` the result does not depend on this lifetime.
262 /// There is a third trait `IndexMut` that allows mutable access, that may be less commonly implemented.
263 pub mod index {
264
265 use alloc::vec::Vec;
266 use crate::Len;
267 use crate::common::IterOwn;
268
269 /// A type that can be mutably accessed by `usize`.
270 pub trait IndexMut {
271 /// Type mutably referencing an indexed element.
272 type IndexMut<'a> where Self: 'a;
273 fn get_mut(& mut self, index: usize) -> Self::IndexMut<'_>;
274 /// A reference to the last element, should one exist.
275 #[inline(always)] fn last_mut(&mut self) -> Option<Self::IndexMut<'_>> where Self: Len {
276 if self.is_empty() { None }
277 else { Some(self.get_mut(self.len()-1)) }
278 }
279 }
280
281 impl<T: IndexMut + ?Sized> IndexMut for &mut T {
282 type IndexMut<'a> = T::IndexMut<'a> where Self: 'a;
283 #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> {
284 T::get_mut(*self, index)
285 }
286 }
287 impl<T> IndexMut for Vec<T> {
288 type IndexMut<'a> = &'a mut T where Self: 'a;
289 #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> { &mut self[index] }
290 }
291 impl<T> IndexMut for [T] {
292 type IndexMut<'a> = &'a mut T where Self: 'a;
293 #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> { &mut self[index] }
294 }
295
296 /// A type that can be accessed by `usize` but without borrowing `self`.
297 ///
298 /// This can be useful for types which include their own lifetimes, and
299 /// which wish to express that their reference has the same lifetime.
300 /// In the GAT `Index`, the `Ref<'_>` lifetime would be tied to `&self`.
301 ///
302 /// This trait may be challenging to implement for owning containers,
303 /// for example `Vec<_>`, which would need their `Ref` type to depend
304 /// on the lifetime of the `&self` borrow in the `get()` function.
305 ///
306 /// # Performance
307 ///
308 /// A call to `get(index)` will attempt to access member slices at `index`,
309 /// and as these could panic the optimizer cannot eliminate them even if you
310 /// do not then go on to examine the values. If you plan to access a field
311 /// (for tuples or structs) or variant match (for enums) you should perform
312 /// this before calling `get(index)` when able.
313 pub trait Index {
314 /// The type returned by the `get` method.
315 ///
316 /// This trait is most often implemented for lifetimed containers, and the `Ref` type
317 /// will have a lifetime that depends on that of the containers, rather than `&self`.
318 type Ref;
319 /// Returns the reference type for location `index`.
320 ///
321 /// Implementations should most likely be marked `#[inline(always)]`.
322 /// If possible, avoid the potential to panic in these implementations,
323 /// as this prevents Rust/LLVM from eliding the test even if the return
324 /// value is not actually consumed.
325 fn get(&self, index: usize) -> Self::Ref;
326 #[inline(always)] fn last(&self) -> Option<Self::Ref> where Self: Len {
327 if self.is_empty() { None }
328 else { Some(self.get(self.len()-1)) }
329 }
330 /// Converts `&self` into an iterator.
331 ///
332 /// This has an awkward name to avoid collision with `iter()`, which may also be implemented.
333 #[inline(always)]
334 fn index_iter(&self) -> IterOwn<&Self> {
335 IterOwn {
336 index: 0,
337 slice: self,
338 }
339 }
340 /// Converts `self` into an iterator.
341 ///
342 /// This has an awkward name to avoid collision with `into_iter()`, which may also be implemented.
343 #[inline(always)]
344 fn into_index_iter(self) -> IterOwn<Self> where Self: Sized {
345 IterOwn {
346 index: 0,
347 slice: self,
348 }
349 }
350 }
351
352 // These implementations aim to reveal a longer lifetime, or to copy results to avoid a lifetime.
353 impl<'a, T> Index for &'a [T] {
354 type Ref = &'a T;
355 #[inline(always)] fn get(&self, index: usize) -> Self::Ref { &self[index] }
356 }
357 impl<T: Copy> Index for [T] {
358 type Ref = T;
359 #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self[index] }
360 }
361 impl<T: Copy, const N: usize> Index for [T; N] {
362 type Ref = T;
363 #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self[index] }
364 }
365 impl<'a, T> Index for &'a Vec<T> {
366 type Ref = &'a T;
367 #[inline(always)] fn get(&self, index: usize) -> Self::Ref { &self[index] }
368 }
369 impl<T: Copy> Index for Vec<T> {
370 type Ref = T;
371 #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self[index] }
372 }
373
374
375 /// Types that can be converted into another type by copying.
376 ///
377 /// We use this trait to unify the ability of `T` and `&T` to be converted into `T`.
378 /// This is handy for copy types that we'd like to use, like `u8`, `u64` and `usize`.
379 pub trait CopyAs<T> : Copy {
380 fn copy_as(self) -> T;
381 }
382 impl<T: Copy> CopyAs<T> for &T {
383 #[inline(always)] fn copy_as(self) -> T { *self }
384 }
385 impl<T: Copy> CopyAs<T> for T {
386 #[inline(always)] fn copy_as(self) -> T { self }
387 }
388
389 pub trait IndexAs<T> {
390 fn index_as(&self, index: usize) -> T;
391 #[inline(always)] fn last(&self) -> Option<T> where Self: Len {
392 if self.is_empty() { None }
393 else { Some(self.index_as(self.len()-1)) }
394 }
395 }
396
397 impl<T: Index, S> IndexAs<S> for T where T::Ref: CopyAs<S> {
398 #[inline(always)] fn index_as(&self, index: usize) -> S { self.get(index).copy_as() }
399 }
400
401 }
402
403 use crate::{Borrow, Container};
404 use crate::common::index::CopyAs;
405 /// A composite trait which captures the ability `Index<Ref = T>`.
406 ///
407 /// Implement `CopyAs<T>` for the reference type.
408 pub trait BorrowIndexAs<T> : for<'a> Borrow<Ref<'a>: CopyAs<T>> { }
409 impl<T, C: for<'a> Borrow<Ref<'a>: CopyAs<T>>> BorrowIndexAs<T> for C { }
410 /// A composite trait which captures the ability `Push<&T>` and `Index<Ref = T>`.
411 ///
412 /// Implement `CopyAs<T>` for the reference type, and `Push<&'a T>` for the container.
413 pub trait PushIndexAs<T> : BorrowIndexAs<T> + Container + for<'a> Push<&'a T> { }
414 impl<T, C: BorrowIndexAs<T> + Container + for<'a> Push<&'a T>> PushIndexAs<T> for C { }
415
416 /// A type that can remove its contents and return to an empty state.
417 ///
418 /// Generally, this method does not release resources, and is used to make the container available for re-insertion.
419 pub trait Clear {
420 /// Clears `self`, without changing its capacity.
421 fn clear(&mut self);
422 }
423 // Vectors can be cleared.
424 impl<T> Clear for Vec<T> {
425 #[inline(always)] fn clear(&mut self) { self.clear() }
426 }
427 // Slice references can be cleared.
428 impl<T> Clear for &[T] {
429 #[inline(always)] fn clear(&mut self) { *self = &[]; }
430 }
431
432 /// A struct representing a slice of a range of values.
433 ///
434 /// The lower and upper bounds should be meaningfully set on construction.
435 #[derive(Copy, Clone, Debug)]
436 pub struct Slice<S> {
437 pub lower: usize,
438 pub upper: usize,
439 pub slice: S,
440 }
441
442 impl<S> core::hash::Hash for Slice<S> where Self: Index<Ref: core::hash::Hash> {
443 fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
444 self.len().hash(state);
445 for i in 0 .. self.len() {
446 self.get(i).hash(state);
447 }
448 }
449 }
450
451 impl<S> Slice<S> {
452 pub fn slice<R: core::ops::RangeBounds<usize>>(self, range: R) -> Self {
453 use core::ops::Bound;
454 let lower = match range.start_bound() {
455 Bound::Included(s) => core::cmp::max(self.lower, *s),
456 Bound::Excluded(s) => core::cmp::max(self.lower, *s+1),
457 Bound::Unbounded => self.lower,
458 };
459 let upper = match range.end_bound() {
460 Bound::Included(s) => core::cmp::min(self.upper, *s+1),
461 Bound::Excluded(s) => core::cmp::min(self.upper, *s),
462 Bound::Unbounded => self.upper,
463 };
464 assert!(lower <= upper);
465 Self { lower, upper, slice: self.slice }
466 }
467 pub fn new(lower: u64, upper: u64, slice: S) -> Self {
468 let lower: usize = lower.try_into().expect("slice bounds must fit in `usize`");
469 let upper: usize = upper.try_into().expect("slice bounds must fit in `usize`");
470 Self { lower, upper, slice }
471 }
472 pub fn len(&self) -> usize { self.upper - self.lower }
473 /// Map the slice to another type.
474 pub(crate) fn map<T>(self, f: impl Fn(S) -> T) -> Slice<T> {
475 Slice {
476 lower: self.lower,
477 upper: self.upper,
478 slice: f(self.slice),
479 }
480 }
481 }
482
483 impl<S: Index> PartialEq for Slice<S> where S::Ref: PartialEq {
484 fn eq(&self, other: &Self) -> bool {
485 if self.len() != other.len() { return false; }
486 for i in 0 .. self.len() {
487 if self.get(i) != other.get(i) { return false; }
488 }
489 true
490 }
491 }
492 impl<S: Index> PartialEq<[S::Ref]> for Slice<S> where S::Ref: PartialEq {
493 fn eq(&self, other: &[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 impl<S: Index> PartialEq<Vec<S::Ref>> for Slice<S> where S::Ref: PartialEq {
502 fn eq(&self, other: &Vec<S::Ref>) -> bool {
503 if self.len() != other.len() { return false; }
504 for i in 0 .. self.len() {
505 if self.get(i) != other[i] { return false; }
506 }
507 true
508 }
509 }
510
511 impl<S: Index> Eq for Slice<S> where S::Ref: Eq { }
512
513 impl<S: Index> PartialOrd for Slice<S> where S::Ref: PartialOrd {
514 fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
515 use core::cmp::Ordering;
516 let len = core::cmp::min(self.len(), other.len());
517
518 for i in 0 .. len {
519 match self.get(i).partial_cmp(&other.get(i)) {
520 Some(Ordering::Equal) => (),
521 not_equal => return not_equal,
522 }
523 }
524
525 self.len().partial_cmp(&other.len())
526 }
527 }
528
529 impl<S: Index> Ord for Slice<S> where S::Ref: Ord + Eq {
530 fn cmp(&self, other: &Self) -> core::cmp::Ordering {
531 use core::cmp::Ordering;
532 let len = core::cmp::min(self.len(), other.len());
533
534 for i in 0 .. len {
535 match self.get(i).cmp(&other.get(i)) {
536 Ordering::Equal => (),
537 not_equal => return not_equal,
538 }
539 }
540
541 self.len().cmp(&other.len())
542 }
543 }
544
545 impl<S> Len for Slice<S> {
546 #[inline(always)] fn len(&self) -> usize { self.len() }
547 }
548
549 impl<S: Index> Index for Slice<S> {
550 type Ref = S::Ref;
551 #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
552 assert!(index < self.upper - self.lower);
553 self.slice.get(self.lower + index)
554 }
555 }
556 impl<'a, S> Index for &'a Slice<S>
557 where
558 &'a S : Index,
559 {
560 type Ref = <&'a S as Index>::Ref;
561 #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
562 assert!(index < self.upper - self.lower);
563 (&self.slice).get(self.lower + index)
564 }
565 }
566
567 impl<S: IndexMut> IndexMut for Slice<S> {
568 type IndexMut<'a> = S::IndexMut<'a> where S: 'a;
569 #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> {
570 assert!(index < self.upper - self.lower);
571 self.slice.get_mut(self.lower + index)
572 }
573 }
574
575 impl<S: Index + Len> Slice<S> {
576 /// Converts the slice into an iterator.
577 ///
578 /// This method exists rather than an `IntoIterator` implementation to avoid
579 /// a conflicting implementation for pushing an `I: IntoIterator` into `Vecs`.
580 pub fn into_iter(self) -> IterOwn<Slice<S>> {
581 self.into_index_iter()
582 }
583 }
584
585 impl<'a, T> Slice<&'a [T]> {
586 pub fn as_slice(&self) -> &'a [T] {
587 &self.slice[self.lower .. self.upper]
588 }
589 }
590
591 pub struct IterOwn<S> {
592 index: usize,
593 slice: S,
594 }
595
596 impl<S> IterOwn<S> {
597 pub fn new(index: usize, slice: S) -> Self {
598 Self { index, slice }
599 }
600 }
601
602 impl<S: Index + Len> Iterator for IterOwn<S> {
603 type Item = S::Ref;
604 #[inline(always)] fn next(&mut self) -> Option<Self::Item> {
605 if self.index < self.slice.len() {
606 let result = self.slice.get(self.index);
607 self.index += 1;
608 Some(result)
609 } else {
610 None
611 }
612 }
613 #[inline(always)]
614 fn size_hint(&self) -> (usize, Option<usize>) {
615 (self.slice.len() - self.index, Some(self.slice.len() - self.index))
616 }
617 }
618
619 impl<S: Index + Len> ExactSizeIterator for IterOwn<S> { }
620
621 /// A type that can be viewed as byte slices with lifetime `'a`.
622 ///
623 /// Implementors of this trait almost certainly reference the lifetime `'a` themselves.
624 pub trait AsBytes<'a> {
625 /// The number of byte slices this type produces.
626 const SLICE_COUNT: usize;
627 /// Returns the `index`-th byte slice (alignment, data) by random access.
628 ///
629 /// Each composite type dispatches on compile-time-constant `SLICE_COUNT`
630 /// boundaries, so LLVM can constant-fold the branch chain when the caller
631 /// iterates `0..SLICE_COUNT`.
632 fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]);
633 /// Presents `self` as a sequence of byte slices, with their required alignment.
634 ///
635 /// The default implementation iterates `0..SLICE_COUNT` calling `get_byte_slice`.
636 /// The return type is always `Map<Range<usize>, ...>` regardless of type complexity.
637 #[inline]
638 fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
639 (0..Self::SLICE_COUNT).map(|i| self.get_byte_slice(i))
640 }
641 }
642
643 /// A type that can be reconstituted from byte slices with lifetime `'a`.
644 ///
645 /// Implementors of this trait almost certainly reference the lifetime `'a` themselves,
646 /// unless they actively deserialize the bytes (vs sit on the slices, as if zero-copy).
647 ///
648 /// # Overriding methods
649 ///
650 /// The only required method is [`from_bytes`](Self::from_bytes). However, the default
651 /// implementation of [`from_store`](Self::from_store) falls back through `from_bytes`,
652 /// which contains panicking operations that prevent LLVM from eliminating unused fields.
653 /// Implementors should override `from_store` and [`element_sizes`](Self::element_sizes)
654 /// to ensure optimal codegen. Missing overrides are functionally correct but silently
655 /// degrade performance. The `#[derive(Columnar)]` macro generates all overrides
656 /// automatically.
657 pub trait FromBytes<'a> {
658 /// The number of byte slices this type consumes when reconstructed.
659 const SLICE_COUNT: usize;
660 /// Reconstructs `self` from a sequence of correctly aligned and sized bytes slices.
661 ///
662 /// The implementation is expected to consume the right number of items from the iterator,
663 /// which may go on to be used by other implementations of `FromBytes`.
664 ///
665 /// The implementation should aim for only doing trivial work, as it backs calls like
666 /// `borrow` for serialized containers.
667 ///
668 /// Implementations should almost always be marked as `#[inline(always)]` to ensure that
669 /// they are inlined. A single non-inlined function on a tree of `from_bytes` calls
670 /// can cause the performance to drop significantly.
671 fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self;
672 /// Reconstructs `self` from a [`DecodedStore`](crate::bytes::indexed::DecodedStore),
673 /// using direct random access at a given offset.
674 ///
675 /// Each field indexes directly into the store at its compile-time-known offset,
676 /// with no iterator state or sequential dependency. This enables LLVM to fully
677 /// eliminate unused fields.
678 #[inline(always)]
679 fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self where Self: Sized {
680 // Default: decode each slice from the store and delegate to from_bytes.
681 let start = *offset;
682 *offset += Self::SLICE_COUNT;
683 Self::from_bytes(&mut (start..*offset).map(|i| {
684 let (w, tail) = store.get(i);
685 let bytes: &[u8] = bytemuck::cast_slice(w);
686 let len = if tail == 0 { bytes.len() } else { bytes.len() - (8 - tail as usize) };
687 &bytes[..len]
688 }))
689 }
690 /// Reports the element sizes (in bytes) for each slice this type consumes.
691 ///
692 /// Implementors should override this to report their actual element sizes.
693 /// For example, `&[u32]` pushes `4`, while a tuple delegates to each field.
694 /// The default returns `Err`, so that [`validate`](Self::validate) rejects
695 /// data for types that have not implemented this method.
696 fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
697 let _ = sizes;
698 Err(format!("element_sizes not implemented for this type (SLICE_COUNT = {})", Self::SLICE_COUNT))
699 }
700 /// Validates that the given slices are compatible with this type.
701 ///
702 /// The input provides `(&[u64], u8)` pairs: each is a word slice
703 /// and trailing byte count. This type consumes `Self::SLICE_COUNT` entries and checks
704 /// that each slice's byte length is a multiple of its element size.
705 ///
706 /// Built from [`Self::element_sizes`]; generally should not need to be overridden.
707 fn validate(slices: &[(&[u64], u8)]) -> Result<(), String> where Self: Sized {
708 if slices.len() < Self::SLICE_COUNT {
709 return Err(format!("expected {} slices but got {}", Self::SLICE_COUNT, slices.len()));
710 }
711 let mut sizes = Vec::new();
712 Self::element_sizes(&mut sizes)?;
713 for (i, elem_size) in sizes.iter().enumerate() {
714 let (words, tail) = &slices[i];
715 let byte_len = words.len() * 8 - ((8 - *tail as usize) % 8);
716 if byte_len % elem_size != 0 {
717 return Err(format!(
718 "slice {} has {} bytes, not a multiple of element size {}",
719 i, byte_len, elem_size
720 ));
721 }
722 }
723 Ok(())
724 }
725 }
726
727}
728
729/// Roaring bitmap (and similar) containers.
730pub mod roaring {
731
732 use alloc::vec::Vec;
733 use crate::Results;
734
735 /// A container for `bool` that uses techniques from Roaring bitmaps.
736 ///
737 /// These techniques are to block the bits into blocks of 2^16 bits,
738 /// and to encode each block based on its density. Either a bitmap
739 /// for dense blocks or a list of set bits for sparse blocks.
740 ///
741 /// Additionally, other representations encode runs of set bits.
742 pub struct RoaringBits {
743 _inner: Results<[u64; 1024], Vec<u16>>,
744 }
745}
746