1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280
//! Specifications for containers
#![forbid(missing_docs)]
pub mod columnation;
pub mod flatcontainer;
/// A container transferring data through dataflow edges
///
/// A container stores a number of elements and thus is able to describe it length (`len()`) and
/// whether it is empty (`is_empty()`). It supports removing all elements (`clear`).
///
/// A container must implement default. The default implementation is not required to allocate
/// memory for variable-length components.
///
/// We require the container to be cloneable to enable efficient copies when providing references
/// of containers to operators. Care must be taken that the type's `clone_from` implementation
/// is efficient (which is not necessarily the case when deriving `Clone`.)
/// TODO: Don't require `Container: Clone`
pub trait Container: Default + Clone + 'static {
/// The type of elements when reading non-destructively from the container.
type ItemRef<'a> where Self: 'a;
/// The type of elements when draining the continer.
type Item<'a> where Self: 'a;
/// The number of elements in this container
///
/// The length of a container must be consistent between sending and receiving it.
/// When exchanging a container and partitioning it into pieces, the sum of the length
/// of all pieces must be equal to the length of the original container. When combining
/// containers, the length of the result must be the sum of the individual parts.
fn len(&self) -> usize;
/// Determine if the container contains any elements, corresponding to `len() == 0`.
fn is_empty(&self) -> bool {
self.len() == 0
}
/// Remove all contents from `self` while retaining allocated memory.
/// After calling `clear`, `is_empty` must return `true` and `len` 0.
fn clear(&mut self);
/// Iterator type when reading from the container.
type Iter<'a>: Iterator<Item=Self::ItemRef<'a>>;
/// Returns an iterator that reads the contents of this container.
fn iter(&self) -> Self::Iter<'_>;
/// Iterator type when draining the container.
type DrainIter<'a>: Iterator<Item=Self::Item<'a>>;
/// Returns an iterator that drains the contents of this container.
/// Drain leaves the container in an undefined state.
fn drain(&mut self) -> Self::DrainIter<'_>;
}
/// A type that can push itself into a container.
pub trait PushInto<C> {
/// Push self into the target container.
fn push_into(self, target: &mut C);
}
/// A type that has the necessary infrastructure to push elements, without specifying how pushing
/// itself works. For this, pushable types should implement [`PushInto`].
// TODO: Reconsider this interface because it assumes
// * Containers have a capacity
// * Push presents single elements.
// * Instead of testing `len == cap`, we could have a `is_full` to test that we might
// not be able to absorb more data.
// * Example: A FlatStack with optimized offsets and deduplication can absorb many elements without reallocation. What does capacity mean in this context?
pub trait PushContainer: Container {
/// Push `item` into self
#[inline]
fn push<T: PushInto<Self>>(&mut self, item: T) {
item.push_into(self)
}
/// Return the capacity of the container.
fn capacity(&self) -> usize;
/// Return the preferred capacity of the container.
fn preferred_capacity() -> usize;
/// Reserve space for `additional` elements, possibly increasing the capacity of the container.
fn reserve(&mut self, additional: usize);
}
impl<T: Clone + 'static> Container for Vec<T> {
type ItemRef<'a> = &'a T where T: 'a;
type Item<'a> = T where T: 'a;
fn len(&self) -> usize {
Vec::len(self)
}
fn is_empty(&self) -> bool {
Vec::is_empty(self)
}
fn clear(&mut self) { Vec::clear(self) }
type Iter<'a> = std::slice::Iter<'a, T>;
fn iter(&self) -> Self::Iter<'_> {
self.as_slice().iter()
}
type DrainIter<'a> = std::vec::Drain<'a, T>;
fn drain(&mut self) -> Self::DrainIter<'_> {
self.drain(..)
}
}
impl<T: Clone + 'static> PushContainer for Vec<T> {
fn capacity(&self) -> usize {
self.capacity()
}
fn preferred_capacity() -> usize {
buffer::default_capacity::<T>()
}
fn reserve(&mut self, additional: usize) {
self.reserve(additional);
}
}
impl<T> PushInto<Vec<T>> for T {
#[inline]
fn push_into(self, target: &mut Vec<T>) {
target.push(self)
}
}
impl<'a, T: Clone> PushInto<Vec<T>> for &'a T {
#[inline]
fn push_into(self, target: &mut Vec<T>) {
target.push(self.clone())
}
}
mod rc {
use std::ops::Deref;
use std::rc::Rc;
use crate::Container;
impl<T: Container> Container for Rc<T> {
type ItemRef<'a> = T::ItemRef<'a> where Self: 'a;
type Item<'a> = T::ItemRef<'a> where Self: 'a;
fn len(&self) -> usize {
std::ops::Deref::deref(self).len()
}
fn is_empty(&self) -> bool {
std::ops::Deref::deref(self).is_empty()
}
fn clear(&mut self) {
// Try to reuse the allocation if possible
if let Some(inner) = Rc::get_mut(self) {
inner.clear();
} else {
*self = Self::default();
}
}
type Iter<'a> = T::Iter<'a>;
fn iter(&self) -> Self::Iter<'_> {
self.deref().iter()
}
type DrainIter<'a> = T::Iter<'a>;
fn drain(&mut self) -> Self::DrainIter<'_> {
self.iter()
}
}
}
mod arc {
use std::ops::Deref;
use std::sync::Arc;
use crate::Container;
impl<T: Container> Container for Arc<T> {
type ItemRef<'a> = T::ItemRef<'a> where Self: 'a;
type Item<'a> = T::ItemRef<'a> where Self: 'a;
fn len(&self) -> usize {
std::ops::Deref::deref(self).len()
}
fn is_empty(&self) -> bool {
std::ops::Deref::deref(self).is_empty()
}
fn clear(&mut self) {
// Try to reuse the allocation if possible
if let Some(inner) = Arc::get_mut(self) {
inner.clear();
} else {
*self = Self::default();
}
}
type Iter<'a> = T::Iter<'a>;
fn iter(&self) -> Self::Iter<'_> {
self.deref().iter()
}
type DrainIter<'a> = T::Iter<'a>;
fn drain(&mut self) -> Self::DrainIter<'_> {
self.iter()
}
}
}
/// A container that can partition itself into pieces.
pub trait PushPartitioned: PushContainer {
/// Partition and push this container.
///
/// Drain all elements from `self`, and use the function `index` to determine which `buffer` to
/// append an element to. Call `flush` with an index and a buffer to send the data downstream.
fn push_partitioned<I, F>(&mut self, buffers: &mut [Self], index: I, flush: F)
where
for<'a> I: FnMut(&Self::Item<'a>) -> usize,
F: FnMut(usize, &mut Self);
}
impl<T: PushContainer + 'static> PushPartitioned for T where for<'a> T::Item<'a>: PushInto<T> {
fn push_partitioned<I, F>(&mut self, buffers: &mut [Self], mut index: I, mut flush: F)
where
for<'a> I: FnMut(&Self::Item<'a>) -> usize,
F: FnMut(usize, &mut Self),
{
let ensure_capacity = |this: &mut Self| {
let capacity = this.capacity();
let desired_capacity = Self::preferred_capacity();
if capacity < desired_capacity {
this.reserve(desired_capacity - capacity);
}
};
for datum in self.drain() {
let index = index(&datum);
ensure_capacity(&mut buffers[index]);
buffers[index].push(datum);
if buffers[index].len() >= buffers[index].capacity() {
flush(index, &mut buffers[index]);
}
}
self.clear();
}
}
pub mod buffer {
//! Functionality related to calculating default buffer sizes
/// The upper limit for buffers to allocate, size in bytes. [default_capacity] converts
/// this to size in elements.
pub const BUFFER_SIZE_BYTES: usize = 1 << 13;
/// The maximum buffer capacity in elements. Returns a number between [BUFFER_SIZE_BYTES]
/// and 1, inclusively.
pub const fn default_capacity<T>() -> usize {
let size = ::std::mem::size_of::<T>();
if size == 0 {
BUFFER_SIZE_BYTES
} else if size <= BUFFER_SIZE_BYTES {
BUFFER_SIZE_BYTES / size
} else {
1
}
}
}