use core::fmt::Debug;
use core::ops::{Deref, DerefMut, Index, IndexMut};
use core::ptr::NonNull;
use core::{mem, ptr};
use core::sync::atomic::Ordering;
use crate::raw;
use crate::alloc::{AllocError, Allocator, Global};
use crate::raw::{BufferSize, HeaderBuffer};
use crate::vector::{Vector, RawVector};
use crate::{grow_amortized, AtomicRefCount, DefaultRefCount, RefCount};
/// A heap allocated, atomically reference counted, immutable contiguous buffer containing elements of type `T`.
///
/// <svg width="280" height="120" viewBox="0 0 74.08 31.75" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns="http://www.w3.org/2000/svg"><defs><linearGradient id="a"><stop offset="0" stop-color="#491c9c"/><stop offset="1" stop-color="#d54b27"/></linearGradient><linearGradient xlink:href="#a" id="b" gradientUnits="userSpaceOnUse" x1="6.27" y1="34.86" x2="87.72" y2="13.24" gradientTransform="translate(-2.64 -18.48)"/></defs><rect width="10.57" height="10.66" x="2.66" y="18.48" ry="1.37" fill="#3dbdaa"/><rect width="10.57" height="10.66" x="15.88" y="18.52" ry="1.37" fill="#3dbdaa"/><rect width="10.57" height="10.66" x="29.11" y="18.52" ry="1.37" fill="#3dbdaa"/><circle cx="33.87" cy="18.56" r=".79" fill="#666"/><circle cx="7.41" cy="18.56" r=".79" fill="#666"/><circle cx="20.64" cy="18.56" r=".79" fill="#666"/><path d="M7.38 18.54c.03-2.63-3.41-2.66-3.41-5.31" fill="none" stroke="#999" stroke-width=".86" stroke-linecap="round"/><path d="M20.64 18.56c0-2.91-15.35-1.36-15.35-5.33" fill="none" stroke="#999" stroke-width=".86" stroke-linecap="round"/><path d="M33.87 18.56c0-3.97-27.26-2.68-27.26-5.33" fill="none" stroke="#999" stroke-width=".86" stroke-linecap="round"/><rect width="68.79" height="10.58" x="2.65" y="2.68" ry="1.37" fill="url(#b)"/><rect width="15.35" height="9.51" x="3.18" y="3.21" ry=".9" fill="#78a2d4"/><rect width="9.26" height="9.51" x="19.85" y="3.2" ry=".9" fill="#eaa577"/><rect width="9.26" height="9.51" x="29.64" y="3.22" ry=".9" fill="#eaa577"/><rect width="9.26" height="9.51" x="39.43" y="3.22" ry=".9" fill="#eaa577"/><rect width="9.26" height="9.51" x="49.22" y="3.21" ry=".9" fill="#eaa577"/><circle cx="62.84" cy="7.97" r=".66" fill="#eaa577"/><circle cx="64.7" cy="7.97" r=".66" fill="#eaa577"/><circle cx="66.55" cy="7.97" r=".66" fill="#eaa577"/></svg>
///
/// See [RefCountedVector].
pub type AtomicSharedVector<T, A = Global> = RefCountedVector<T, AtomicRefCount, A>;
/// A heap allocated, reference counted, immutable contiguous buffer containing elements of type `T`.
///
/// <svg width="280" height="120" viewBox="0 0 74.08 31.75" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns="http://www.w3.org/2000/svg"><defs><linearGradient id="a"><stop offset="0" stop-color="#491c9c"/><stop offset="1" stop-color="#d54b27"/></linearGradient><linearGradient xlink:href="#a" id="b" gradientUnits="userSpaceOnUse" x1="6.27" y1="34.86" x2="87.72" y2="13.24" gradientTransform="translate(-2.64 -18.48)"/></defs><rect width="10.57" height="10.66" x="2.66" y="18.48" ry="1.37" fill="#3dbdaa"/><rect width="10.57" height="10.66" x="15.88" y="18.52" ry="1.37" fill="#3dbdaa"/><rect width="10.57" height="10.66" x="29.11" y="18.52" ry="1.37" fill="#3dbdaa"/><circle cx="33.87" cy="18.56" r=".79" fill="#666"/><circle cx="7.41" cy="18.56" r=".79" fill="#666"/><circle cx="20.64" cy="18.56" r=".79" fill="#666"/><path d="M7.38 18.54c.03-2.63-3.41-2.66-3.41-5.31" fill="none" stroke="#999" stroke-width=".86" stroke-linecap="round"/><path d="M20.64 18.56c0-2.91-15.35-1.36-15.35-5.33" fill="none" stroke="#999" stroke-width=".86" stroke-linecap="round"/><path d="M33.87 18.56c0-3.97-27.26-2.68-27.26-5.33" fill="none" stroke="#999" stroke-width=".86" stroke-linecap="round"/><rect width="68.79" height="10.58" x="2.65" y="2.68" ry="1.37" fill="url(#b)"/><rect width="15.35" height="9.51" x="3.18" y="3.21" ry=".9" fill="#78a2d4"/><rect width="9.26" height="9.51" x="19.85" y="3.2" ry=".9" fill="#eaa577"/><rect width="9.26" height="9.51" x="29.64" y="3.22" ry=".9" fill="#eaa577"/><rect width="9.26" height="9.51" x="39.43" y="3.22" ry=".9" fill="#eaa577"/><rect width="9.26" height="9.51" x="49.22" y="3.21" ry=".9" fill="#eaa577"/><circle cx="62.84" cy="7.97" r=".66" fill="#eaa577"/><circle cx="64.7" cy="7.97" r=".66" fill="#eaa577"/><circle cx="66.55" cy="7.97" r=".66" fill="#eaa577"/></svg>
///
/// See [RefCountedVector].
pub type SharedVector<T, A = Global> = RefCountedVector<T, DefaultRefCount, A>;
/// A heap allocated, reference counted, immutable contiguous buffer containing elements of type `T`.
///
/// <svg width="280" height="120" viewBox="0 0 74.08 31.75" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns="http://www.w3.org/2000/svg"><defs><linearGradient id="a"><stop offset="0" stop-color="#491c9c"/><stop offset="1" stop-color="#d54b27"/></linearGradient><linearGradient xlink:href="#a" id="b" gradientUnits="userSpaceOnUse" x1="6.27" y1="34.86" x2="87.72" y2="13.24" gradientTransform="translate(-2.64 -18.48)"/></defs><rect width="10.57" height="10.66" x="2.66" y="18.48" ry="1.37" fill="#3dbdaa"/><rect width="10.57" height="10.66" x="15.88" y="18.52" ry="1.37" fill="#3dbdaa"/><rect width="10.57" height="10.66" x="29.11" y="18.52" ry="1.37" fill="#3dbdaa"/><circle cx="33.87" cy="18.56" r=".79" fill="#666"/><circle cx="7.41" cy="18.56" r=".79" fill="#666"/><circle cx="20.64" cy="18.56" r=".79" fill="#666"/><path d="M7.38 18.54c.03-2.63-3.41-2.66-3.41-5.31" fill="none" stroke="#999" stroke-width=".86" stroke-linecap="round"/><path d="M20.64 18.56c0-2.91-15.35-1.36-15.35-5.33" fill="none" stroke="#999" stroke-width=".86" stroke-linecap="round"/><path d="M33.87 18.56c0-3.97-27.26-2.68-27.26-5.33" fill="none" stroke="#999" stroke-width=".86" stroke-linecap="round"/><rect width="68.79" height="10.58" x="2.65" y="2.68" ry="1.37" fill="url(#b)"/><rect width="15.35" height="9.51" x="3.18" y="3.21" ry=".9" fill="#78a2d4"/><rect width="9.26" height="9.51" x="19.85" y="3.2" ry=".9" fill="#eaa577"/><rect width="9.26" height="9.51" x="29.64" y="3.22" ry=".9" fill="#eaa577"/><rect width="9.26" height="9.51" x="39.43" y="3.22" ry=".9" fill="#eaa577"/><rect width="9.26" height="9.51" x="49.22" y="3.21" ry=".9" fill="#eaa577"/><circle cx="62.84" cy="7.97" r=".66" fill="#eaa577"/><circle cx="64.7" cy="7.97" r=".66" fill="#eaa577"/><circle cx="66.55" cy="7.97" r=".66" fill="#eaa577"/></svg>
///
/// Similar in principle to `Arc<[T]>`. It can be converted into a `Vector<T>` for
/// free if there is only a single reference to the RefCountedVector alive.
///
/// # Copy-on-write "Immutable" vectors
///
/// This type contains mutable methods like `push` and `pop`. These internally allocate a new buffer
/// if the buffer is not unique (there are more than one reference to it). When there is a single reference,
/// these mutable operation simply update the existing buffer.
///
/// In other words, this type behaves like an [immutable (or persistent) data structure](https://en.wikipedia.org/wiki/Persistent_data_structure)
/// Actual mutability only happens under the hood as an optimization when a single reference exists.
#[repr(transparent)]
pub struct RefCountedVector<T, R: RefCount, A: Allocator = Global> {
pub(crate) inner: HeaderBuffer<T, R, A>,
}
impl<T, R: RefCount> RefCountedVector<T, R, Global> {
/// Creates an empty shared buffer without allocating memory.
#[inline]
pub fn new() -> RefCountedVector<T, R, Global> {
Self::try_with_capacity_in(0, Global).unwrap()
}
/// Constructs a new, empty vector with at least the specified capacity.
#[inline]
pub fn with_capacity(cap: usize) -> RefCountedVector<T, R, Global> {
Self::try_with_capacity_in(cap, Global).unwrap()
}
/// Clones the contents of a slice into a new vector.
#[inline]
pub fn from_slice(slice: &[T]) -> RefCountedVector<T, R, Global>
where
T: Clone,
{
Self::try_from_slice_in(slice, Global).unwrap()
}
}
impl<T, R: RefCount, A: Allocator> RefCountedVector<T, R, A> {
/// Creates an empty vector without allocating memory.
pub fn new_in(allocator: A) -> Self {
Self::try_with_capacity_in(0, allocator).unwrap()
}
/// Creates an empty pre-allocated vector with a given storage capacity.
pub fn with_capacity_in(cap: usize, allocator: A) -> Self {
Self::try_with_capacity_in(cap, allocator).unwrap()
}
/// Tries to construct a new, empty vector with at least the specified capacity.
#[inline]
pub fn try_with_capacity_in(cap: usize, allocator: A) -> Result<Self, AllocError> {
raw::assert_ref_count_layout::<R>();
unsafe {
let (ptr, cap) = raw::allocate_header_buffer::<T, A>(cap, &allocator)?;
ptr::write(
ptr.cast().as_ptr(),
raw::Header {
vec: raw::VecHeader {
cap: cap as BufferSize,
len: 0,
},
ref_count: R::new(1),
allocator,
},
);
Ok(RefCountedVector {
inner: HeaderBuffer::from_raw(ptr.cast()),
})
}
}
pub fn try_from_slice_in(slice: &[T], allocator: A) -> Result<Self, AllocError> where T: Clone {
let mut v = Self::try_with_capacity_in(slice.len(), allocator)?;
unsafe {
raw::extend_from_slice_assuming_capacity(v.data_ptr(), v.vec_header_mut(), slice);
}
Ok(v)
}
/// Returns `true` if the vector contains no elements.
#[inline]
pub fn is_empty(&self) -> bool {
self.vec_header().len == 0
}
/// Returns the number of elements in the vector, also referred to as its ‘length’.
#[inline]
pub fn len(&self) -> usize {
self.vec_header().len as usize
}
/// Returns the total number of elements the vector can hold without reallocating.
#[inline]
pub fn capacity(&self) -> usize {
self.vec_header().cap as usize
}
/// Returns number of elements that can be added without reallocating.
#[inline]
pub fn remaining_capacity(&self) -> usize {
let h = self.vec_header();
(h.cap - h.len) as usize
}
/// Returns a reference to the underlying allocator.
pub fn allocator(&self) -> &A {
self.inner.allocator()
}
/// Creates a new reference without allocating.
///
/// Equivalent to `Clone::clone`.
#[inline]
pub fn new_ref(&self) -> Self {
unsafe {
self.inner.as_ref().ref_count.add_ref();
RefCountedVector {
inner: HeaderBuffer::from_raw(self.inner.header)
}
}
}
/// Extracts a slice containing the entire vector.
#[inline]
pub fn as_slice(&self) -> &[T] {
unsafe {
core::slice::from_raw_parts(self.data_ptr(), self.len())
}
}
/// Returns true if this is the only existing handle to the buffer.
///
/// When this function returns true, mutable methods and converting to a `Vector`
/// is very fast (does not involve additional memory allocations or copies).
#[inline]
pub fn is_unique(&self) -> bool {
unsafe { self.inner.as_ref().ref_count.get() == 1 }
}
/// Clears the vector, removing all values.
pub fn clear(&mut self)
where
A: Clone,
{
if self.is_unique() {
unsafe {
raw::clear(self.data_ptr(), self.vec_header_mut());
}
return;
}
*self =
Self::try_with_capacity_in(self.capacity(), self.inner.allocator().clone()).unwrap();
}
/// Returns true if the two vectors share the same underlying storage.
pub fn ptr_eq(&self, other: &Self) -> bool {
self.inner.header == other.inner.header
}
/// Allocates a duplicate of this buffer (infallible).
pub fn copy_buffer(&self) -> Self
where
T: Copy,
A: Clone,
{
self.try_copy_buffer().unwrap()
}
/// Tries to allocate a duplicate of this buffer.
pub fn try_copy_buffer(&self) -> Result<Self, AllocError>
where
T: Copy,
A: Clone,
{
unsafe {
let header = self.inner.as_ref();
let len = header.vec.len;
let cap = header.vec.cap;
if len > cap {
return Err(AllocError);
}
let allocator = header.allocator.clone();
let mut clone = Self::try_with_capacity_in(cap as usize, allocator)?;
if len > 0 {
core::ptr::copy_nonoverlapping(self.data_ptr(), clone.data_ptr(), len as usize);
clone.vec_header_mut().len = len;
}
Ok(clone)
}
}
#[inline]
pub fn data_ptr(&self) -> *mut T {
unsafe { (self.inner.as_ptr() as *mut u8).add(raw::header_size::<raw::Header<R, A>, T>()) as *mut T }
}
// SAFETY: call this only if the vector is unique.
pub(crate) unsafe fn vec_header_mut(&mut self) -> &mut raw::VecHeader {
&mut self.inner.as_mut().vec
}
pub(crate) fn vec_header(&self) -> &raw::VecHeader {
unsafe { &self.inner.as_ref().vec }
}
}
/// Mutable methods that can cause the vector to be cloned and therefore require both the items and
/// the allocator to be cloneable.
impl<T: Clone, R: RefCount, A: Allocator + Clone> RefCountedVector<T, R, A> {
/// Converts this RefCountedVector into an immutable one, allocating a new copy if there are other references.
#[inline]
pub fn into_unique(mut self) -> Vector<T, A> {
self.ensure_unique();
unsafe {
let data = NonNull::new_unchecked(self.data_ptr());
let header = self.vec_header().clone();
let allocator = ptr::read(&self.inner.as_ref().allocator);
mem::forget(self);
Vector {
raw: RawVector {
data,
header,
},
allocator,
}
}
}
/// Appends an element to the back of a collection.
///
/// # Panics
///
/// Panics if the new capacity exceeds `u32::MAX` bytes.
pub fn push(&mut self, val: T) {
self.reserve(1);
unsafe {
raw::push_assuming_capacity(self.data_ptr(), &mut self.vec_header_mut(), val);
}
}
/// Removes the last element from the vector and returns it, or `None` if it is empty.
pub fn pop(&mut self) -> Option<T> {
self.ensure_unique();
unsafe {
raw::pop(self.data_ptr(), &mut self.vec_header_mut())
}
}
/// Removes an element from the vector and returns it.
///
/// The removed element is replaced by the last element of the vector.
///
/// # Panics
///
/// Panics if index is out of bounds.
#[inline]
pub fn swap_remove(&mut self, idx: usize) -> T {
self.ensure_unique();
let len = self.len();
assert!(idx < len);
unsafe {
let data_ptr = self.data_ptr();
let ptr = data_ptr.add(idx);
let item = ptr::read(ptr);
let last_idx = len - 1;
if idx != last_idx {
let last_ptr = data_ptr.add(last_idx);
ptr::write(ptr, ptr::read(last_ptr));
}
self.vec_header_mut().len = last_idx as BufferSize;
item
}
}
/// Appends an element if there is sufficient spare capacity, otherwise an error is returned
/// with the element.
///
/// Like other mutable operations, this method may reallocate if the vector is not unique.
/// However it will not reallocate when there’s insufficient capacity.
/// The caller should use reserve or try_reserve to ensure that there is enough capacity.
pub fn push_within_capacity(&mut self, val: T) -> Result<(), T> {
if self.remaining_capacity() == 0 {
return Err(val);
}
self.ensure_unique();
unsafe {
raw::push_assuming_capacity(self.data_ptr(), &mut self.vec_header_mut(), val);
}
Ok(())
}
/// Clones and appends the contents of the slice to the back of a collection.
pub fn extend_from_slice(&mut self, slice: &[T]) {
self.reserve(slice.len());
unsafe {
raw::extend_from_slice_assuming_capacity(self.data_ptr(), self.vec_header_mut(), slice);
}
}
/// Appends the contents of an iterator to the back of a collection.
pub fn extend(&mut self, data: impl IntoIterator<Item = T>) {
let mut iter = data.into_iter();
let (min, max) = iter.size_hint();
self.reserve(max.unwrap_or(min));
unsafe {
if raw::extend_within_capacity(self.data_ptr(), self.vec_header_mut(), &mut iter) {
return;
}
}
for item in iter {
self.push(item);
}
}
/// Ensures this shared vector uniquely owns its storage, allocating a new copy
/// If there are other references to it.
///
/// In principle this is mostly useful internally to provide safe mutable methods
/// as it does not observaly affect most of the shared vector behavior, however
/// it has a few niche use cases, for example to provoke copies earlier for more
/// predictable performance or in some unsafe endeavors.
#[inline]
pub fn ensure_unique(&mut self) {
if !self.is_unique() {
*self = self.try_clone_buffer(None).unwrap();
}
}
/// Extracts a mutable slice containing the entire vector.
///
/// Like other mutable methods, this will clone the vector's storage
/// if it is not unique to ensure safe mutations.
#[inline]
pub fn as_mut_slice(&mut self) -> &mut [T]
where
T: Clone,
A: Clone,
{
self.ensure_unique();
unsafe {
core::slice::from_raw_parts_mut(self.data_ptr(), self.len())
}
}
/// Allocates a duplicate of this buffer (infallible).
pub fn clone_buffer(&self) -> Self
where
T: Clone,
A: Clone,
{
self.try_clone_buffer(None).unwrap()
}
fn try_clone_buffer(&self, new_cap: Option<BufferSize>) -> Result<Self, AllocError>
where
T: Clone,
A: Clone,
{
unsafe {
let header = self.inner.as_ref();
let len = header.vec.len;
let cap = if let Some(cap) = new_cap {
cap
} else {
header.vec.cap
};
let allocator = header.allocator.clone();
if len > cap {
return Err(AllocError);
}
let mut clone = Self::try_with_capacity_in(cap as usize, allocator)?;
raw::extend_from_slice_assuming_capacity(
clone.data_ptr(),
clone.vec_header_mut(),
self.as_slice()
);
Ok(clone)
}
}
/// Ensures the vector can be safely mutated and has enough extra capacity to
/// add `additional` more items.
///
/// This will allocate new storage for the vector if the vector is not unique or if
/// the capacity is not sufficient to accomodate `self.len() + additional` items.
/// The vector may reserve more space to speculatively avoid frequent reallocations.
#[inline]
pub fn reserve(&mut self, additional: usize) {
let is_unique = self.is_unique();
let enough_capacity = self.remaining_capacity() >= additional;
if !is_unique || !enough_capacity {
// Hopefully the least common case.
self.try_realloc_additional(is_unique, enough_capacity, additional)
.unwrap();
}
}
/// Tries to reserve at least `additional` extra elements to be inserted in the given vector.
///
/// The vector may reserve more space to speculatively avoid frequent reallocations.
/// After calling try_reserve, capacity will be greater than or equal to `self.len() + additional`
/// if it returns `Ok(())`.
/// Does nothing if capacity is already sufficient. This method preserves the contents even if an
/// error occurs.
pub fn try_reserve(&mut self, additional: usize) -> Result<(), AllocError> {
let is_unique = self.is_unique();
let enough_capacity = self.remaining_capacity() >= additional;
if !is_unique || !enough_capacity {
// Hopefully the least common case.
self.try_realloc_additional(is_unique, enough_capacity, additional)?;
}
Ok(())
}
/// Reserves the minimum capacity for at least `additional` elements to be inserted in the given vector.
///
/// Unlike `reserve`, this will not deliberately over-allocate to speculatively avoid frequent allocations.
/// After calling `try_reserve_exact`, capacity will be greater than or equal to `self.len() + additional` if
/// it returns `Ok(())`.
/// This will also allocate if the vector is not unique.
/// Does nothing if the capacity is already sufficient and the vector is unique.
///
/// Note that the allocator may give the collection more space than it requests. Therefore, capacity can not
/// be relied upon to be precisely minimal. Prefer `try_reserve` if future insertions are expected.
pub fn reserve_exact(&mut self, additional: usize) {
self.try_reserve_exact(additional).unwrap();
}
/// Tries to reserve the minimum capacity for at least `additional` elements to be inserted in the given vector.
///
/// Unlike `try_reserve`, this will not deliberately over-allocate to speculatively avoid frequent allocations.
/// After calling `reserve_exact`, capacity will be greater than or equal to `self.len() + additional`.
/// This will also allocate if the vector is not unique.
/// Does nothing if the capacity is already sufficient and the vector is unique.
///
/// Note that the allocator may give the collection more space than it requests. Therefore, capacity can not
/// be relied upon to be precisely minimal. Prefer `try_reserve` if future insertions are expected.
pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), AllocError> {
let is_unique = self.is_unique();
let enough_capacity = self.remaining_capacity() >= additional;
if !is_unique || !enough_capacity {
// Hopefully the least common case.
self.try_realloc_with_capacity(is_unique, additional)?;
}
Ok(())
}
/// Shrinks the capacity of the vector with a lower bound.
///
/// The capacity will remain at least as large as both the length and the supplied value.
/// If the current capacity is less than the lower limit, this is a no-op.
pub fn shrink_to(&mut self, min_capacity: usize) {
let min_capacity = min_capacity.max(self.len());
if self.capacity() <= min_capacity {
return;
}
let is_unique = self.is_unique();
self.try_realloc_with_capacity(is_unique, min_capacity)
.unwrap();
}
/// Shrinks the capacity of the vector as much as possible.
pub fn shrink_to_fit(&mut self) {
self.shrink_to(self.len())
}
/// Moves all the elements of `other` into `self`, leaving `other` empty.
///
/// If `other is not unique, the elements are cloned instead of moved.
pub fn append(&mut self, other: &mut Self) {
self.reserve(other.len());
unsafe {
if other.is_unique() {
// Fast path: memcpy
raw::move_data(
other.data_ptr(), &mut other.inner.header.as_mut().vec,
self.data_ptr(), &mut self.inner.as_mut().vec,
)
} else {
// Slow path, clone each item.
raw::extend_from_slice_assuming_capacity(self.data_ptr(), self.vec_header_mut(), other.as_slice());
*other =
Self::try_with_capacity_in(other.capacity(), self.inner.allocator().clone())
.unwrap();
}
}
}
#[cold]
fn try_realloc_additional(
&mut self,
is_unique: bool,
enough_capacity: bool,
additional: usize,
) -> Result<(), AllocError> {
let new_cap = if enough_capacity {
self.capacity()
} else {
grow_amortized(self.len(), additional)
};
self.try_realloc_with_capacity(is_unique, new_cap)
}
#[cold]
fn try_realloc_with_capacity(
&mut self,
is_unique: bool,
new_cap: usize,
) -> Result<(), AllocError> {
let allocator = self.inner.allocator().clone();
if is_unique && self.capacity() > 0 {
// The buffer is not large enough, we'll have to create a new one, however we
// know that we have the only reference to it so we'll move the data with
// a simple memcpy instead of cloning it.
unsafe {
use crate::raw::{buffer_layout, Header};
let old_cap = self.capacity();
let old_header = self.inner.header;
let old_layout = buffer_layout::<Header<R, A>, T>(old_cap).unwrap();
let new_layout = buffer_layout::<Header<R, A>, T>(new_cap).unwrap();
let new_alloc = if new_layout.size() >= old_layout.size() {
allocator.grow(old_header.cast(), old_layout, new_layout)
} else {
allocator.shrink(old_header.cast(), old_layout, new_layout)
}?;
self.inner.header = new_alloc.cast();
self.inner.as_mut().vec.cap = new_cap as BufferSize;
return Ok(());
}
}
// The slowest path, we pay for both the new allocation and the need to clone
// each item one by one.
let mut new_vec = Self::try_with_capacity_in(new_cap, allocator)?;
new_vec.extend_from_slice(self.as_slice());
mem::swap(self, &mut new_vec);
Ok(())
}
// TODO: remove this one?
/// Returns the concatenation of two vectors.
pub fn concatenate(mut self, mut other: Self) -> Self
where
T: Clone,
A: Clone,
{
self.append(&mut other);
self
}
}
impl<T, R: RefCount, A: Allocator> Drop for RefCountedVector<T, R, A> {
fn drop(&mut self) {
unsafe {
if self.inner.as_ref().ref_count.release_ref() {
let header = self.vec_header().clone();
// See the implementation of std Arc for the need to use this fence. Note that
// we only need it for the atomic reference counted version but I don't expect
// this to make a measurable difference.
core::sync::atomic::fence(Ordering::Acquire);
raw::drop_items(self.data_ptr(), header.len);
raw::dealloc::<T, R, A>(self.inner.header, header.cap);
}
}
}
}
unsafe impl<T: Send + Sync, A: Allocator + Send> Send for AtomicSharedVector<T, A> {}
unsafe impl<T: Send + Sync, A: Allocator + Sync> Sync for AtomicSharedVector<T, A> {}
impl<T, R: RefCount, A: Allocator> Clone for RefCountedVector<T, R, A> {
fn clone(&self) -> Self {
self.new_ref()
}
}
impl<T: PartialEq<T>, R: RefCount, A: Allocator> PartialEq<RefCountedVector<T, R, A>>
for RefCountedVector<T, R, A>
{
fn eq(&self, other: &Self) -> bool {
self.ptr_eq(other) || self.as_slice() == other.as_slice()
}
}
impl<T: PartialEq<T>, R: RefCount, A: Allocator> PartialEq<&[T]> for RefCountedVector<T, R, A> {
fn eq(&self, other: &&[T]) -> bool {
self.as_slice() == *other
}
}
impl<T, R: RefCount, A: Allocator> AsRef<[T]> for RefCountedVector<T, R, A> {
fn as_ref(&self) -> &[T] {
self.as_slice()
}
}
impl<T, R: RefCount> Default for RefCountedVector<T, R, Global> {
fn default() -> Self {
Self::new()
}
}
impl<'a, T, R: RefCount, A: Allocator> IntoIterator for &'a RefCountedVector<T, R, A> {
type Item = &'a T;
type IntoIter = core::slice::Iter<'a, T>;
fn into_iter(self) -> core::slice::Iter<'a, T> {
self.as_slice().iter()
}
}
impl<'a, T: Clone, R: RefCount, A: Allocator + Clone> IntoIterator
for &'a mut RefCountedVector<T, R, A>
{
type Item = &'a mut T;
type IntoIter = core::slice::IterMut<'a, T>;
fn into_iter(self) -> core::slice::IterMut<'a, T> {
self.as_mut_slice().iter_mut()
}
}
impl<T, R, A, I> Index<I> for RefCountedVector<T, R, A>
where
R: RefCount,
A: Allocator,
I: core::slice::SliceIndex<[T]>,
{
type Output = <I as core::slice::SliceIndex<[T]>>::Output;
fn index(&self, index: I) -> &Self::Output {
self.as_slice().index(index)
}
}
impl<T, R, A, I> IndexMut<I> for RefCountedVector<T, R, A>
where
T: Clone,
R: RefCount,
A: Allocator + Clone,
I: core::slice::SliceIndex<[T]>,
{
fn index_mut(&mut self, index: I) -> &mut Self::Output {
self.as_mut_slice().index_mut(index)
}
}
impl<T, R: RefCount, A: Allocator> Deref for RefCountedVector<T, R, A> {
type Target = [T];
fn deref(&self) -> &[T] {
self.as_slice()
}
}
impl<T: Clone, R: RefCount, A: Allocator + Clone> DerefMut for RefCountedVector<T, R, A> {
fn deref_mut(&mut self) -> &mut [T] {
self.as_mut_slice()
}
}
impl<T: Debug, R: RefCount, A: Allocator> Debug for RefCountedVector<T, R, A> {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> Result<(), core::fmt::Error> {
self.as_slice().fmt(f)
}
}
impl<T: Clone, A: Allocator + Clone> From<Vector<T, A>> for SharedVector<T, A> {
fn from(vector: Vector<T, A>) -> Self {
vector.into_shared()
}
}
impl<T: Clone, A: Allocator + Clone> From<Vector<T, A>> for AtomicSharedVector<T, A> {
fn from(vector: Vector<T, A>) -> Self {
vector.into_shared_atomic()
}
}
// In order to give us a chance to catch leaks and double-frees, test with values that implement drop.
#[cfg(test)]
fn num(val: u32) -> Box<u32> {
Box::new(val)
}
#[test]
fn basic_shared() {
basic_shared_impl::<DefaultRefCount>();
basic_shared_impl::<AtomicRefCount>();
fn basic_shared_impl<R: RefCount>() {
let mut a: RefCountedVector<Box<u32>, R> = RefCountedVector::with_capacity(64);
a.push(num(1));
a.push(num(2));
let mut b = a.new_ref();
b.push(num(4));
a.push(num(3));
assert_eq!(a.as_slice(), &[num(1), num(2), num(3)]);
assert_eq!(b.as_slice(), &[num(1), num(2), num(4)]);
let popped = a.pop();
assert_eq!(a.as_slice(), &[num(1), num(2)]);
assert_eq!(popped, Some(num(3)));
let mut b2 = b.new_ref();
let popped = b2.pop();
assert_eq!(b2.as_slice(), &[num(1), num(2)]);
assert_eq!(popped, Some(num(4)));
println!("concatenate");
let c = a.concatenate(b2);
assert_eq!(c.as_slice(), &[num(1), num(2), num(1), num(2)]);
}
}
#[test]
fn empty_buffer() {
let _: AtomicSharedVector<u32> = AtomicSharedVector::new();
let _: AtomicSharedVector<u32> = AtomicSharedVector::new();
let _: SharedVector<()> = SharedVector::new();
let _: SharedVector<()> = SharedVector::new();
let _: AtomicSharedVector<()> = AtomicSharedVector::new();
let _: AtomicSharedVector<()> = AtomicSharedVector::new();
let _: Vector<()> = Vector::new();
}
#[test]
#[rustfmt::skip]
fn grow() {
let mut a = Vector::with_capacity(0);
a.push(num(1));
a.push(num(2));
a.push(num(3));
a.extend_from_slice(&[num(4), num(5), num(6), num(7), num(8), num(9), num(10), num(12), num(12), num(13), num(14), num(15), num(16), num(17), num(18)]);
assert_eq!(
a.as_slice(),
&[num(1), num(2), num(3), num(4), num(5), num(6), num(7), num(8), num(9), num(10), num(12), num(12), num(13), num(14), num(15), num(16), num(17), num(18)]
);
let mut b = SharedVector::new();
b.push(num(1));
b.push(num(2));
b.push(num(3));
assert_eq!(b.as_slice(), &[num(1), num(2), num(3)]);
let mut b = AtomicSharedVector::new();
b.push(num(1));
b.push(num(2));
b.push(num(3));
assert_eq!(b.as_slice(), &[num(1), num(2), num(3)]);
}
#[test]
fn ensure_unique_empty() {
let mut v: SharedVector<u32> = SharedVector::new();
v.ensure_unique();
}
#[test]
fn shrink_to_zero() {
let mut v: SharedVector<u32> = SharedVector::new();
v.shrink_to(0);
}