use std::cmp;
use std::iter;
use std::mem;
use std::ops::{Bound, Deref, DerefMut, RangeBounds};
use std::ptr;
use std::slice;
use std::borrow::{Borrow, BorrowMut};
use std::hash::{Hash, Hasher};
use std::fmt;
#[cfg(feature="std")]
use std::io;
use std::mem::ManuallyDrop;
use std::mem::MaybeUninit;
#[cfg(feature="serde")]
use serde::{Serialize, Deserialize, Serializer, Deserializer};
use crate::LenUint;
use crate::errors::CapacityError;
use crate::arrayvec_impl::ArrayVecImpl;
use crate::utils::MakeMaybeUninit;
pub struct ArrayVec<T, const CAP: usize> {
xs: [MaybeUninit<T>; CAP],
len: LenUint,
}
impl<T, const CAP: usize> Drop for ArrayVec<T, CAP> {
fn drop(&mut self) {
self.clear();
}
}
macro_rules! panic_oob {
($method_name:expr, $index:expr, $len:expr) => {
panic!(concat!("ArrayVec::", $method_name, ": index {} is out of bounds in vector of length {}"),
$index, $len)
}
}
impl<T, const CAP: usize> ArrayVec<T, CAP> {
const CAPACITY: usize = CAP;
#[inline]
#[track_caller]
pub fn new() -> ArrayVec<T, CAP> {
assert_capacity_limit!(CAP);
unsafe {
ArrayVec { xs: MaybeUninit::uninit().assume_init(), len: 0 }
}
}
pub const fn new_const() -> ArrayVec<T, CAP> {
assert_capacity_limit_const!(CAP);
ArrayVec { xs: MakeMaybeUninit::ARRAY, len: 0 }
}
#[inline(always)]
pub const fn len(&self) -> usize { self.len as usize }
#[inline]
pub const fn is_empty(&self) -> bool { self.len() == 0 }
#[inline(always)]
pub const fn capacity(&self) -> usize { CAP }
pub const fn is_full(&self) -> bool { self.len() == self.capacity() }
pub const fn remaining_capacity(&self) -> usize {
self.capacity() - self.len()
}
#[track_caller]
pub fn push(&mut self, element: T) {
ArrayVecImpl::push(self, element)
}
pub fn try_push(&mut self, element: T) -> Result<(), CapacityError<T>> {
ArrayVecImpl::try_push(self, element)
}
pub unsafe fn push_unchecked(&mut self, element: T) {
ArrayVecImpl::push_unchecked(self, element)
}
pub fn truncate(&mut self, new_len: usize) {
ArrayVecImpl::truncate(self, new_len)
}
pub fn clear(&mut self) {
ArrayVecImpl::clear(self)
}
unsafe fn get_unchecked_ptr(&mut self, index: usize) -> *mut T {
self.as_mut_ptr().add(index)
}
#[track_caller]
pub fn insert(&mut self, index: usize, element: T) {
self.try_insert(index, element).unwrap()
}
pub fn try_insert(&mut self, index: usize, element: T) -> Result<(), CapacityError<T>> {
if index > self.len() {
panic_oob!("try_insert", index, self.len())
}
if self.len() == self.capacity() {
return Err(CapacityError::new(element));
}
let len = self.len();
unsafe { {
let p: *mut _ = self.get_unchecked_ptr(index);
ptr::copy(p, p.offset(1), len - index);
ptr::write(p, element);
}
self.set_len(len + 1);
}
Ok(())
}
pub fn pop(&mut self) -> Option<T> {
ArrayVecImpl::pop(self)
}
pub fn swap_remove(&mut self, index: usize) -> T {
self.swap_pop(index)
.unwrap_or_else(|| {
panic_oob!("swap_remove", index, self.len())
})
}
pub fn swap_pop(&mut self, index: usize) -> Option<T> {
let len = self.len();
if index >= len {
return None;
}
self.swap(index, len - 1);
self.pop()
}
pub fn remove(&mut self, index: usize) -> T {
self.pop_at(index)
.unwrap_or_else(|| {
panic_oob!("remove", index, self.len())
})
}
pub fn pop_at(&mut self, index: usize) -> Option<T> {
if index >= self.len() {
None
} else {
self.drain(index..index + 1).next()
}
}
pub fn retain<F>(&mut self, mut f: F)
where F: FnMut(&mut T) -> bool
{
let original_len = self.len();
unsafe { self.set_len(0) };
struct BackshiftOnDrop<'a, T, const CAP: usize> {
v: &'a mut ArrayVec<T, CAP>,
processed_len: usize,
deleted_cnt: usize,
original_len: usize,
}
impl<T, const CAP: usize> Drop for BackshiftOnDrop<'_, T, CAP> {
fn drop(&mut self) {
if self.deleted_cnt > 0 {
unsafe {
ptr::copy(
self.v.as_ptr().add(self.processed_len),
self.v.as_mut_ptr().add(self.processed_len - self.deleted_cnt),
self.original_len - self.processed_len
);
}
}
unsafe {
self.v.set_len(self.original_len - self.deleted_cnt);
}
}
}
let mut g = BackshiftOnDrop { v: self, processed_len: 0, deleted_cnt: 0, original_len };
#[inline(always)]
fn process_one<F: FnMut(&mut T) -> bool, T, const CAP: usize, const DELETED: bool>(
f: &mut F,
g: &mut BackshiftOnDrop<'_, T, CAP>
) -> bool {
let cur = unsafe { g.v.as_mut_ptr().add(g.processed_len) };
if !f(unsafe { &mut *cur }) {
g.processed_len += 1;
g.deleted_cnt += 1;
unsafe { ptr::drop_in_place(cur) };
return false;
}
if DELETED {
unsafe {
let hole_slot = cur.sub(g.deleted_cnt);
ptr::copy_nonoverlapping(cur, hole_slot, 1);
}
}
g.processed_len += 1;
true
}
while g.processed_len != original_len {
if !process_one::<F, T, CAP, false>(&mut f, &mut g) {
break;
}
}
while g.processed_len != original_len {
process_one::<F, T, CAP, true>(&mut f, &mut g);
}
drop(g);
}
pub unsafe fn set_len(&mut self, length: usize) {
debug_assert!(length <= self.capacity());
self.len = length as LenUint;
}
pub fn try_extend_from_slice(&mut self, other: &[T]) -> Result<(), CapacityError>
where T: Copy,
{
if self.remaining_capacity() < other.len() {
return Err(CapacityError::new(()));
}
let self_len = self.len();
let other_len = other.len();
unsafe {
let dst = self.get_unchecked_ptr(self_len);
ptr::copy_nonoverlapping(other.as_ptr(), dst, other_len);
self.set_len(self_len + other_len);
}
Ok(())
}
pub fn drain<R>(&mut self, range: R) -> Drain<T, CAP>
where R: RangeBounds<usize>
{
let len = self.len();
let start = match range.start_bound() {
Bound::Unbounded => 0,
Bound::Included(&i) => i,
Bound::Excluded(&i) => i.saturating_add(1),
};
let end = match range.end_bound() {
Bound::Excluded(&j) => j,
Bound::Included(&j) => j.saturating_add(1),
Bound::Unbounded => len,
};
self.drain_range(start, end)
}
fn drain_range(&mut self, start: usize, end: usize) -> Drain<T, CAP>
{
let len = self.len();
let range_slice: *const _ = &self[start..end];
self.len = start as LenUint;
unsafe {
Drain {
tail_start: end,
tail_len: len - end,
iter: (*range_slice).iter(),
vec: self as *mut _,
}
}
}
pub fn into_inner(self) -> Result<[T; CAP], Self> {
if self.len() < self.capacity() {
Err(self)
} else {
unsafe { Ok(self.into_inner_unchecked()) }
}
}
pub unsafe fn into_inner_unchecked(self) -> [T; CAP] {
debug_assert_eq!(self.len(), self.capacity());
let self_ = ManuallyDrop::new(self);
let array = ptr::read(self_.as_ptr() as *const [T; CAP]);
array
}
pub fn take(&mut self) -> Self {
mem::replace(self, Self::new())
}
pub fn as_slice(&self) -> &[T] {
ArrayVecImpl::as_slice(self)
}
pub fn as_mut_slice(&mut self) -> &mut [T] {
ArrayVecImpl::as_mut_slice(self)
}
pub fn as_ptr(&self) -> *const T {
ArrayVecImpl::as_ptr(self)
}
pub fn as_mut_ptr(&mut self) -> *mut T {
ArrayVecImpl::as_mut_ptr(self)
}
}
impl<T, const CAP: usize> ArrayVecImpl for ArrayVec<T, CAP> {
type Item = T;
const CAPACITY: usize = CAP;
fn len(&self) -> usize { self.len() }
unsafe fn set_len(&mut self, length: usize) {
debug_assert!(length <= CAP);
self.len = length as LenUint;
}
fn as_ptr(&self) -> *const Self::Item {
self.xs.as_ptr() as _
}
fn as_mut_ptr(&mut self) -> *mut Self::Item {
self.xs.as_mut_ptr() as _
}
}
impl<T, const CAP: usize> Deref for ArrayVec<T, CAP> {
type Target = [T];
#[inline]
fn deref(&self) -> &Self::Target {
self.as_slice()
}
}
impl<T, const CAP: usize> DerefMut for ArrayVec<T, CAP> {
#[inline]
fn deref_mut(&mut self) -> &mut Self::Target {
self.as_mut_slice()
}
}
impl<T, const CAP: usize> From<[T; CAP]> for ArrayVec<T, CAP> {
#[track_caller]
fn from(array: [T; CAP]) -> Self {
let array = ManuallyDrop::new(array);
let mut vec = <ArrayVec<T, CAP>>::new();
unsafe {
(&*array as *const [T; CAP] as *const [MaybeUninit<T>; CAP])
.copy_to_nonoverlapping(&mut vec.xs as *mut [MaybeUninit<T>; CAP], 1);
vec.set_len(CAP);
}
vec
}
}
impl<T, const CAP: usize> std::convert::TryFrom<&[T]> for ArrayVec<T, CAP>
where T: Clone,
{
type Error = CapacityError;
fn try_from(slice: &[T]) -> Result<Self, Self::Error> {
if Self::CAPACITY < slice.len() {
Err(CapacityError::new(()))
} else {
let mut array = Self::new();
array.extend_from_slice(slice);
Ok(array)
}
}
}
impl<'a, T: 'a, const CAP: usize> IntoIterator for &'a ArrayVec<T, CAP> {
type Item = &'a T;
type IntoIter = slice::Iter<'a, T>;
fn into_iter(self) -> Self::IntoIter { self.iter() }
}
impl<'a, T: 'a, const CAP: usize> IntoIterator for &'a mut ArrayVec<T, CAP> {
type Item = &'a mut T;
type IntoIter = slice::IterMut<'a, T>;
fn into_iter(self) -> Self::IntoIter { self.iter_mut() }
}
impl<T, const CAP: usize> IntoIterator for ArrayVec<T, CAP> {
type Item = T;
type IntoIter = IntoIter<T, CAP>;
fn into_iter(self) -> IntoIter<T, CAP> {
IntoIter { index: 0, v: self, }
}
}
pub struct IntoIter<T, const CAP: usize> {
index: usize,
v: ArrayVec<T, CAP>,
}
impl<T, const CAP: usize> Iterator for IntoIter<T, CAP> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
if self.index == self.v.len() {
None
} else {
unsafe {
let index = self.index;
self.index = index + 1;
Some(ptr::read(self.v.get_unchecked_ptr(index)))
}
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.v.len() - self.index;
(len, Some(len))
}
}
impl<T, const CAP: usize> DoubleEndedIterator for IntoIter<T, CAP> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.index == self.v.len() {
None
} else {
unsafe {
let new_len = self.v.len() - 1;
self.v.set_len(new_len);
Some(ptr::read(self.v.get_unchecked_ptr(new_len)))
}
}
}
}
impl<T, const CAP: usize> ExactSizeIterator for IntoIter<T, CAP> { }
impl<T, const CAP: usize> Drop for IntoIter<T, CAP> {
fn drop(&mut self) {
let index = self.index;
let len = self.v.len();
unsafe {
self.v.set_len(0);
let elements = slice::from_raw_parts_mut(
self.v.get_unchecked_ptr(index),
len - index);
ptr::drop_in_place(elements);
}
}
}
impl<T, const CAP: usize> Clone for IntoIter<T, CAP>
where T: Clone,
{
fn clone(&self) -> IntoIter<T, CAP> {
let mut v = ArrayVec::new();
v.extend_from_slice(&self.v[self.index..]);
v.into_iter()
}
}
impl<T, const CAP: usize> fmt::Debug for IntoIter<T, CAP>
where
T: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_list()
.entries(&self.v[self.index..])
.finish()
}
}
pub struct Drain<'a, T: 'a, const CAP: usize> {
tail_start: usize,
tail_len: usize,
iter: slice::Iter<'a, T>,
vec: *mut ArrayVec<T, CAP>,
}
unsafe impl<'a, T: Sync, const CAP: usize> Sync for Drain<'a, T, CAP> {}
unsafe impl<'a, T: Send, const CAP: usize> Send for Drain<'a, T, CAP> {}
impl<'a, T: 'a, const CAP: usize> Iterator for Drain<'a, T, CAP> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.iter.next().map(|elt|
unsafe {
ptr::read(elt as *const _)
}
)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<'a, T: 'a, const CAP: usize> DoubleEndedIterator for Drain<'a, T, CAP>
{
fn next_back(&mut self) -> Option<Self::Item> {
self.iter.next_back().map(|elt|
unsafe {
ptr::read(elt as *const _)
}
)
}
}
impl<'a, T: 'a, const CAP: usize> ExactSizeIterator for Drain<'a, T, CAP> {}
impl<'a, T: 'a, const CAP: usize> Drop for Drain<'a, T, CAP> {
fn drop(&mut self) {
while let Some(_) = self.next() { }
if self.tail_len > 0 {
unsafe {
let source_vec = &mut *self.vec;
let start = source_vec.len();
let tail = self.tail_start;
let ptr = source_vec.as_mut_ptr();
ptr::copy(ptr.add(tail), ptr.add(start), self.tail_len);
source_vec.set_len(start + self.tail_len);
}
}
}
}
struct ScopeExitGuard<T, Data, F>
where F: FnMut(&Data, &mut T)
{
value: T,
data: Data,
f: F,
}
impl<T, Data, F> Drop for ScopeExitGuard<T, Data, F>
where F: FnMut(&Data, &mut T)
{
fn drop(&mut self) {
(self.f)(&self.data, &mut self.value)
}
}
impl<T, const CAP: usize> Extend<T> for ArrayVec<T, CAP> {
#[track_caller]
fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) {
unsafe {
self.extend_from_iter::<_, true>(iter)
}
}
}
#[inline(never)]
#[cold]
#[track_caller]
fn extend_panic() {
panic!("ArrayVec: capacity exceeded in extend/from_iter");
}
impl<T, const CAP: usize> ArrayVec<T, CAP> {
#[track_caller]
pub(crate) unsafe fn extend_from_iter<I, const CHECK: bool>(&mut self, iterable: I)
where I: IntoIterator<Item = T>
{
let take = self.capacity() - self.len();
let len = self.len();
let mut ptr = raw_ptr_add(self.as_mut_ptr(), len);
let end_ptr = raw_ptr_add(ptr, take);
let mut guard = ScopeExitGuard {
value: &mut self.len,
data: len,
f: move |&len, self_len| {
**self_len = len as LenUint;
}
};
let mut iter = iterable.into_iter();
loop {
if let Some(elt) = iter.next() {
if ptr == end_ptr && CHECK { extend_panic(); }
debug_assert_ne!(ptr, end_ptr);
ptr.write(elt);
ptr = raw_ptr_add(ptr, 1);
guard.data += 1;
} else {
return; }
}
}
pub(crate) fn extend_from_slice(&mut self, slice: &[T])
where T: Clone
{
let take = self.capacity() - self.len();
debug_assert!(slice.len() <= take);
unsafe {
let slice = if take < slice.len() { &slice[..take] } else { slice };
self.extend_from_iter::<_, false>(slice.iter().cloned());
}
}
}
unsafe fn raw_ptr_add<T>(ptr: *mut T, offset: usize) -> *mut T {
if mem::size_of::<T>() == 0 {
ptr.cast::<u8>().wrapping_add(offset).cast()
} else {
ptr.add(offset)
}
}
impl<T, const CAP: usize> iter::FromIterator<T> for ArrayVec<T, CAP> {
fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> Self {
let mut array = ArrayVec::new();
array.extend(iter);
array
}
}
impl<T, const CAP: usize> Clone for ArrayVec<T, CAP>
where T: Clone
{
fn clone(&self) -> Self {
self.iter().cloned().collect()
}
fn clone_from(&mut self, rhs: &Self) {
let prefix = cmp::min(self.len(), rhs.len());
self[..prefix].clone_from_slice(&rhs[..prefix]);
if prefix < self.len() {
self.truncate(prefix);
} else {
let rhs_elems = &rhs[self.len()..];
self.extend_from_slice(rhs_elems);
}
}
}
impl<T, const CAP: usize> Hash for ArrayVec<T, CAP>
where T: Hash
{
fn hash<H: Hasher>(&self, state: &mut H) {
Hash::hash(&**self, state)
}
}
impl<T, const CAP: usize> PartialEq for ArrayVec<T, CAP>
where T: PartialEq
{
fn eq(&self, other: &Self) -> bool {
**self == **other
}
}
impl<T, const CAP: usize> PartialEq<[T]> for ArrayVec<T, CAP>
where T: PartialEq
{
fn eq(&self, other: &[T]) -> bool {
**self == *other
}
}
impl<T, const CAP: usize> Eq for ArrayVec<T, CAP> where T: Eq { }
impl<T, const CAP: usize> Borrow<[T]> for ArrayVec<T, CAP> {
fn borrow(&self) -> &[T] { self }
}
impl<T, const CAP: usize> BorrowMut<[T]> for ArrayVec<T, CAP> {
fn borrow_mut(&mut self) -> &mut [T] { self }
}
impl<T, const CAP: usize> AsRef<[T]> for ArrayVec<T, CAP> {
fn as_ref(&self) -> &[T] { self }
}
impl<T, const CAP: usize> AsMut<[T]> for ArrayVec<T, CAP> {
fn as_mut(&mut self) -> &mut [T] { self }
}
impl<T, const CAP: usize> fmt::Debug for ArrayVec<T, CAP> where T: fmt::Debug {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { (**self).fmt(f) }
}
impl<T, const CAP: usize> Default for ArrayVec<T, CAP> {
fn default() -> ArrayVec<T, CAP> {
ArrayVec::new()
}
}
impl<T, const CAP: usize> PartialOrd for ArrayVec<T, CAP> where T: PartialOrd {
fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
(**self).partial_cmp(other)
}
fn lt(&self, other: &Self) -> bool {
(**self).lt(other)
}
fn le(&self, other: &Self) -> bool {
(**self).le(other)
}
fn ge(&self, other: &Self) -> bool {
(**self).ge(other)
}
fn gt(&self, other: &Self) -> bool {
(**self).gt(other)
}
}
impl<T, const CAP: usize> Ord for ArrayVec<T, CAP> where T: Ord {
fn cmp(&self, other: &Self) -> cmp::Ordering {
(**self).cmp(other)
}
}
#[cfg(feature="std")]
impl<const CAP: usize> io::Write for ArrayVec<u8, CAP> {
fn write(&mut self, data: &[u8]) -> io::Result<usize> {
let len = cmp::min(self.remaining_capacity(), data.len());
let _result = self.try_extend_from_slice(&data[..len]);
debug_assert!(_result.is_ok());
Ok(len)
}
fn flush(&mut self) -> io::Result<()> { Ok(()) }
}
#[cfg(feature="serde")]
impl<T: Serialize, const CAP: usize> Serialize for ArrayVec<T, CAP> {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where S: Serializer
{
serializer.collect_seq(self)
}
}
#[cfg(feature="serde")]
impl<'de, T: Deserialize<'de>, const CAP: usize> Deserialize<'de> for ArrayVec<T, CAP> {
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where D: Deserializer<'de>
{
use serde::de::{Visitor, SeqAccess, Error};
use std::marker::PhantomData;
struct ArrayVecVisitor<'de, T: Deserialize<'de>, const CAP: usize>(PhantomData<(&'de (), [T; CAP])>);
impl<'de, T: Deserialize<'de>, const CAP: usize> Visitor<'de> for ArrayVecVisitor<'de, T, CAP> {
type Value = ArrayVec<T, CAP>;
fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
write!(formatter, "an array with no more than {} items", CAP)
}
fn visit_seq<SA>(self, mut seq: SA) -> Result<Self::Value, SA::Error>
where SA: SeqAccess<'de>,
{
let mut values = ArrayVec::<T, CAP>::new();
while let Some(value) = seq.next_element()? {
if let Err(_) = values.try_push(value) {
return Err(SA::Error::invalid_length(CAP + 1, &self));
}
}
Ok(values)
}
}
deserializer.deserialize_seq(ArrayVecVisitor::<T, CAP>(PhantomData))
}
}