#![no_std]
#![deny(missing_docs)]
#![feature(min_const_generics)]
pub struct MaxSizeVec<T, const SIZE: usize> {
data: [core::mem::ManuallyDrop<T>; SIZE],
length: usize
}
pub struct MaxSizeVecIter<T, const SIZE: usize> {
data: [core::mem::ManuallyDrop<T>; SIZE],
length: usize,
offset: usize
}
impl<T, const SIZE: usize> core::iter::Iterator for MaxSizeVecIter<T, {SIZE}> {
type Item = T;
fn next(&mut self) -> Option<T> {
if self.offset >= self.length {
None
} else {
self.offset += 1;
Some(unsafe {
core::ptr::read((self.data.as_ptr() as *const T).offset_unsigned(self.offset - 1))
})
}
}
}
pub struct Drain<'a, T, const SIZE: usize> {
vector: &'a mut MaxSizeVec<T, {SIZE}>,
original_start: usize,
start: usize,
end: usize
}
impl<'a, T, const SIZE: usize> core::iter::Iterator for Drain<'a, T, {SIZE}> {
type Item = T;
fn next(&mut self) -> Option<T> {
if self.start >= self.end {
None
} else {
self.start += 1;
Some(unsafe {
core::ptr::read(self.vector.as_ptr().offset(self.start as isize - 1))
})
}
}
}
impl<'a, T, const SIZE: usize> core::ops::Drop for Drain<'a, T, {SIZE}> {
fn drop(&mut self) {
let amount_to_remove = self.end - self.original_start;
unsafe {
for x in self.start..self.end {
core::ptr::drop_in_place(
self.vector.as_mut_ptr().offset_unsigned(x)
);
}
core::ptr::copy(
self.vector.as_ptr().offset_unsigned(self.end),
self.vector.as_mut_ptr().offset_unsigned(self.original_start),
self.vector.length - self.end
);
}
self.vector.length -= amount_to_remove;
}
}
trait OffsetUnsigned {
unsafe fn offset_unsigned(&self, offset: usize) -> Self;
}
impl<T> OffsetUnsigned for *const T {
unsafe fn offset_unsigned(&self, offset: usize) -> *const T {
self.offset(offset as isize)
}
}
impl<T> OffsetUnsigned for *mut T {
unsafe fn offset_unsigned(&self, offset: usize) -> *mut T {
self.offset(offset as isize)
}
}
impl<T, const SIZE: usize> Drop for MaxSizeVec<T, {SIZE}> {
fn drop(&mut self) {
for x in 0..self.length {
unsafe {
core::mem::ManuallyDrop::drop(&mut self.data[x]);
}
}
}
}
impl<T: Clone, const SIZE: usize> Clone for MaxSizeVec<T, {SIZE}> {
fn clone(&self) -> MaxSizeVec<T, {SIZE}> {
MaxSizeVec {
data: self.data.clone(),
length: self.length
}
}
}
impl<T: PartialEq, const SIZE: usize> PartialEq<&[T]> for MaxSizeVec<T, {SIZE}> {
fn eq(&self, other: &&[T]) -> bool {
self.as_slice() == *other
}
}
impl<T: PartialEq, const SIZE: usize, const OTHER: usize> PartialEq<MaxSizeVec<T, {OTHER}>> for MaxSizeVec<T, {SIZE}> {
fn eq(&self, other: &MaxSizeVec<T, {OTHER}>) -> bool {
self.as_slice() == other.as_slice()
}
}
impl<T: PartialEq, const SIZE: usize, const OTHER: usize> PartialEq<[T; {OTHER}]> for MaxSizeVec<T, {SIZE}> {
fn eq(&self, other: &[T; {OTHER}]) -> bool {
self.as_slice() == other
}
}
impl<T: PartialEq, const SIZE: usize, const OTHER: usize> PartialEq<&[T; {OTHER}]> for MaxSizeVec<T, {SIZE}> {
fn eq(&self, other: &&[T; {OTHER}]) -> bool {
self.as_slice() == *other
}
}
impl<T: core::fmt::Debug, const SIZE: usize> core::fmt::Debug for MaxSizeVec<T, {SIZE}> {
fn fmt(&self, fmt: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
unsafe {
core::mem::transmute::<&[core::mem::ManuallyDrop<T>], &[T]>(&self.data[..self.length])
}.fmt(fmt)
}
}
impl<T, const SIZE: usize> MaxSizeVec<T, {SIZE}> {
pub fn new() -> MaxSizeVec<T, {SIZE}> {
MaxSizeVec {
data: unsafe {
core::mem::MaybeUninit::zeroed().assume_init()
},
length: 0usize
}
}
pub fn push(&mut self, val: T) {
if self.length == self.data.len() {
panic!("Attempt to push when there's no room left in a max size vector!");
}
self.data[self.length] = core::mem::ManuallyDrop::new(val);
self.length += 1;
}
pub fn pop(&mut self) {
if self.length == 0 {
panic!("Attempt to pop a max-size vector with underflow!");
}
unsafe {
core::mem::ManuallyDrop::drop(&mut self.data[self.length - 1]);
}
self.length -= 1;
}
pub fn len(&self) -> usize {
self.length
}
pub fn drain<'a, R: core::ops::RangeBounds<usize>>(&'a mut self, range: R) -> Drain<'a, T, {SIZE}> {
use core::ops::Bound;
let start = match range.start_bound() {
Bound::Unbounded => 0usize,
Bound::Included(x) => {
let x = *x;
if x >= self.len() {
panic!("Range out of bounds!")
} else {
x
}
},
_ => unreachable!()
};
let end = match range.end_bound() {
Bound::Unbounded => self.len(),
Bound::Included(x) => if *x + 1 > self.len() {
panic!("Range out of bounds!")
} else {
*x + 1
},
Bound::Excluded(x) => {
let x = *x;
if x > self.len() {
panic!("Range out of bounds!")
} else {
x
}
},
};
Drain {
start,
end,
vector: self,
original_start: start
}
}
pub fn append<const OTHER_SIZE: usize>(&mut self, other: &mut MaxSizeVec<T, {OTHER_SIZE}>) {
if self.length + other.length > self.data.len() {
panic!("Attempt to append beyond the bounds of a max-size vector!");
}
unsafe {
core::ptr::copy_nonoverlapping(
other.as_ptr(),
self.as_mut_ptr().offset_unsigned(self.length),
other.len()
)
}
self.length += other.len();
*other = MaxSizeVec::new();
}
pub fn as_mut_ptr(&mut self) -> *mut T {
self.data.as_mut_ptr() as *mut T
}
pub fn as_mut_slice(&mut self) -> &mut [T] {
unsafe {
core::mem::transmute::<&mut [core::mem::ManuallyDrop<T>], &mut [T]>(&mut self.data[..self.length])
}
}
pub fn as_ptr(&self) -> *const T {
self.data.as_ptr() as *const T
}
pub fn as_slice(&self) -> &[T] {
unsafe {
core::mem::transmute::<&[core::mem::ManuallyDrop<T>], &[T]>(&self.data[..self.length])
}
}
pub fn capacity(&self) -> usize {
self.data.len()
}
pub fn clear(&mut self) {
*self = MaxSizeVec::new();
}
pub fn insert(&mut self, index: usize, element: T) {
if self.length + 1 >= self.data.len() {
panic!("Attempt to insert into a max-sized vector with overflow!");
}
if index > self.length {
panic!("Index out of bounds during insertion into max-sized vector!");
}
if index == self.length {
self.push(element);
} else {
unsafe {
self.length += 1;
core::ptr::copy(
self.as_ptr().offset_unsigned(index),
self.as_mut_ptr().offset_unsigned(index + 1),
self.length - index
);
*self.as_mut_ptr().offset_unsigned(index) = element;
}
}
}
pub fn truncate(&mut self, size: usize) {
if size > self.length {
panic!("Attempt to truncate a max-sized vector to larger length!");
}
if size != self.length {
for x in 0..self.length - size - 1 {
unsafe {
let ptr: *mut core::mem::ManuallyDrop<T> = self.data.as_mut_ptr().offset_unsigned(
self.length - x
);
core::mem::ManuallyDrop::drop(core::mem::transmute::<_, &mut core::mem::ManuallyDrop<T>>(ptr))
}
}
self.length = size;
}
}
pub fn resize_with(&mut self, size: usize, mut f: impl FnMut() -> T) {
if size >= self.data.len() {
panic!("The size passed to the resize function of a max-sized vector was larger than the vector's bounds!");
}
if size >= self.length {
for _ in 0..size - self.length {
self.push(f());
}
} else {
self.truncate(size);
}
}
pub fn retain(&mut self, mut predicate: impl FnMut(&T) -> bool) {
let mut current_length = 0usize;
for x in 0..self.length {
if predicate(&self[x]) {
unsafe {
core::ptr::copy(self.as_ptr().offset_unsigned(x), self.as_mut_ptr().offset_unsigned(current_length), 1usize)
};
current_length += 1;
} else {
unsafe {
core::ptr::drop_in_place(self.as_mut_ptr().offset_unsigned(x))
}
}
}
self.length = current_length;
}
pub fn remove(&mut self, index: usize) {
if index >= self.length {
panic!("Index for removal out of bounds for max-sized vector!");
}
unsafe {
core::ptr::drop_in_place(self.as_mut_ptr().offset_unsigned(index));
}
if index != self.length - 1 {
unsafe {
core::ptr::copy(
self.as_ptr().offset_unsigned(index + 1),
self.as_mut_ptr().offset_unsigned(index),
self.length - index - 1
);
}
}
self.length -= 1;
}
pub fn swap_remove(&mut self, index: usize) {
if index >= self.length {
panic!("Index out of bounds for swap remove operation on max-sized vector!");
}
if index == self.length - 1 {
self.pop();
} else {
unsafe {
core::ptr::swap_nonoverlapping(
self.as_mut_ptr().offset_unsigned(index), self.as_mut_ptr().offset_unsigned(self.length - 1), 1usize
);
}
self.pop();
}
}
pub fn is_empty(&self) -> bool {
self.length == 0
}
}
impl<T, const SIZE: usize> core::ops::Deref for MaxSizeVec<T, {SIZE}> {
type Target = [T];
fn deref(&self) -> &Self::Target {
self.as_slice()
}
}
impl<T, const SIZE: usize> core::ops::DerefMut for MaxSizeVec<T, {SIZE}> {
fn deref_mut(&mut self) -> &mut [T] {
self.as_mut_slice()
}
}
impl<T: Clone, const SIZE: usize> MaxSizeVec<T, {SIZE}> {
pub fn resize(&mut self, size: usize, value: T) {
if size >= self.data.len() {
panic!("The size passed to the resize function of a max-sized vector was larger than the vector's bounds!");
}
if size >= self.length {
for _ in 0..size - self.length {
self.push(value.clone());
}
} else {
self.truncate(size);
}
}
pub fn extend_from_slice(&mut self, other: &[T]) {
if self.len() + other.len() >= self.data.len() {
panic!("Attempt to extend by a slice beyond the bounds of a max-sized vector!");
}
for (n, x) in other.iter().cloned().enumerate() {
unsafe {
*self.data.as_mut_ptr().offset_unsigned(self.length + n) = core::mem::ManuallyDrop::new(x);
}
}
}
}
impl<T, const SIZE: usize> core::iter::Extend<T> for MaxSizeVec<T, {SIZE}> {
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
let mut iter = iter.into_iter();
let mut x = iter.next();
while x.is_some() {
if self.length >= self.data.len() {
panic!("Attempt to extend beyond the bounds of a max-sized vector!");
}
self.data[self.length] = core::mem::ManuallyDrop::new(x.unwrap());
self.length += 1;
x = iter.next();
}
}
}
impl<'a, T: 'a + Copy, const SIZE: usize> core::iter::Extend<&'a T> for MaxSizeVec<T, {SIZE}> {
fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
let mut iter = iter.into_iter();
let mut x = iter.next();
while x.is_some() {
if self.length >= self.data.len() {
panic!("Attempt to extend beyond the bounds of a max-sized vector!");
}
self.data[self.length] = core::mem::ManuallyDrop::new(x.unwrap().clone());
self.length += 1;
x = iter.next();
}
}
}
impl<T, const SIZE: usize> core::ops::Index<usize> for MaxSizeVec<T, {SIZE}> {
type Output = T;
fn index(&self, index: usize) -> &T {
if index >= self.length {
panic!("Index {} out of bounds of fixed size vec!", index);
}
unsafe {
core::mem::transmute(self.data.index(index))
}
}
}
impl<T, const SIZE: usize> core::ops::IndexMut<usize> for MaxSizeVec<T, {SIZE}> {
fn index_mut(&mut self, index: usize) -> &mut T {
if index >= self.length {
panic!("Index {} out of bounds of fixed size vec!", index);
}
unsafe {
core::mem::transmute(self.data.index_mut(index))
}
}
}
impl<T, const SIZE: usize> core::convert::AsMut<[T]> for MaxSizeVec<T, {SIZE}> {
fn as_mut(&mut self) -> &mut [T] {
self.as_mut_slice()
}
}
impl<T, const SIZE: usize> core::convert::AsMut<MaxSizeVec<T, {SIZE}>> for MaxSizeVec<T, {SIZE}> {
fn as_mut(&mut self) -> &mut Self {
self
}
}
impl<T, const SIZE: usize> core::convert::AsRef<[T]> for MaxSizeVec<T, {SIZE}> {
fn as_ref(&self) -> &[T] {
self.as_slice()
}
}
impl<T, const SIZE: usize> core::convert::AsRef<MaxSizeVec<T, {SIZE}>> for MaxSizeVec<T, {SIZE}> {
fn as_ref(&self) -> &Self {
self
}
}
impl<T, const SIZE: usize> core::borrow::Borrow<[T]> for MaxSizeVec<T, {SIZE}> {
fn borrow(&self) -> &[T] {
self.as_slice()
}
}
impl<T, const SIZE: usize> core::borrow::BorrowMut<[T]> for MaxSizeVec<T, {SIZE}> {
fn borrow_mut(&mut self) -> &mut [T] {
self.as_mut_slice()
}
}
impl<T: Eq, const SIZE: usize> Eq for MaxSizeVec<T, {SIZE}> {}
impl<'a, T: Clone, const SIZE: usize> From<&'a [T]> for MaxSizeVec<T, {SIZE}> {
fn from(x: &[T]) -> Self {
let mut v = MaxSizeVec::new();
v.extend(x.iter().cloned());
v
}
}
impl<'a, T: Clone, const SIZE: usize> From<&'a mut [T]> for MaxSizeVec<T, {SIZE}> {
fn from(x: &mut [T]) -> Self {
let mut v = MaxSizeVec::new();
v.extend(x.iter().cloned());
v
}
}
impl<'a, const SIZE: usize> From<&'a str> for MaxSizeVec<u8, {SIZE}> {
fn from(x: &str) -> Self {
let mut v = MaxSizeVec::new();
v.extend(x.as_bytes().iter().cloned());
v
}
}
impl<T, const SIZE: usize> core::iter::FromIterator<T> for MaxSizeVec<T, {SIZE}> {
fn from_iter<I: IntoIterator<Item = T>>(x: I) -> Self {
let mut v = MaxSizeVec::new();
v.extend(x);
v
}
}
impl<T, const SIZE: usize> core::iter::IntoIterator for MaxSizeVec<T, {SIZE}> {
type Item = T;
type IntoIter = MaxSizeVecIter<T, {SIZE}>;
fn into_iter(self) -> MaxSizeVecIter<T, {SIZE}> {
MaxSizeVecIter {
offset: 0usize,
length: self.length,
data: unsafe {
core::mem::transmute_copy(&self.data)
}
}
}
}
impl<'a, T, const SIZE: usize> core::iter::IntoIterator for &'a MaxSizeVec<T, {SIZE}> {
type Item = &'a T;
type IntoIter = core::slice::Iter<'a, T>;
fn into_iter(self) -> core::slice::Iter<'a, T> {
self.iter()
}
}
impl<T: PartialOrd, const SIZE: usize> PartialOrd for MaxSizeVec<T, {SIZE}> {
fn partial_cmp(&self, other: &MaxSizeVec<T, {SIZE}>) -> Option<core::cmp::Ordering> {
PartialOrd::partial_cmp(self.as_slice(), other.as_slice())
}
}
impl<T: Ord, const SIZE: usize> Ord for MaxSizeVec<T, {SIZE}> {
fn cmp(&self, other: &MaxSizeVec<T, {SIZE}>) -> core::cmp::Ordering {
Ord::cmp(self.as_slice(), other.as_slice())
}
}
#[test]
fn dropping_order() {
use core::sync::atomic::*;
#[derive(Clone, Debug)]
struct DropTest;
static DROP_COUNT: AtomicUsize = AtomicUsize::new(0usize);
impl Drop for DropTest {
fn drop(&mut self) {
DROP_COUNT.fetch_add(1usize, Ordering::SeqCst);
}
}
let mut x: MaxSizeVec<DropTest, 1024> = MaxSizeVec::new();
x.extend((1..=1024).map(|_| DropTest));
x.resize(512, DropTest);
x.swap_remove(0usize);
x.pop();
let mut collection: MaxSizeVec<DropTest, 1024> = MaxSizeVec::new();
for v in x.drain(..) {
collection.push(v);
}
x.append(&mut collection);
x.drain(..);
assert_eq!(x.len(), 0);
assert_eq!(DROP_COUNT.load(Ordering::SeqCst), 1534);
}
#[test]
fn operational_correctness() {
let mut x: MaxSizeVec<usize, 1024> = MaxSizeVec::new();
x.push(0usize);
x.swap_remove(0usize);
x.extend(5..10usize);
x.pop();
x.retain(|x| *x > 6);
x.drain(0..1);
x.drain(..1);
x.push(2);
x.insert(1usize, 1usize);
x.insert(0usize, 1usize);
x.remove(0usize);
assert_eq!(x, &[2, 1]);
}