//! A contiguous growable array type with heap-allocated contents, written Vec<T>
use crate::convert::PFrom;
use crate::alloc::get_idx;
use crate::alloc::MemPool;
use crate::clone::PClone;
use crate::ptr::*;
use crate::stm::*;
use crate::*;
use std::alloc::Layout;
use std::cmp::Ordering;
use std::fmt::{Debug, Display, Formatter};
use std::marker::PhantomData;
use std::ops::Index;
use std::slice::SliceIndex;
use std::vec::Vec as StdVec;
use std::{mem, ptr, slice};
/// A contiguous growable persistent array type, written `Vec<T>` but pronounced
/// 'vector'.
///
/// [`PVec`] is an alias name in the pool module for `Vec`.
///
/// [`PVec`]: ../alloc/default/type.PVec.html
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::new();
/// vec.push(1, j);
/// vec.push(2, j);
///
/// assert_eq!(vec.len(), 2);
/// assert_eq!(vec[0], 1);
///
/// assert_eq!(vec.pop(), Some(2));
/// assert_eq!(vec.len(), 1);
///
/// vec.extend_from_slice(&[1, 2, 3], j);
///
/// for x in vec.as_slice() {
/// println!("{}", x);
/// }
/// assert_eq!(vec, [1, 1, 2, 3]);
///
/// }).unwrap();
/// ```
pub struct Vec<T: PSafe, A: MemPool> {
buf: Slice<T, A>,
len: usize,
has_log: u8,
marker: PhantomData<[T]>,
}
unsafe impl<T: PSafe, A: MemPool> PSafe for Vec<T, A> {}
impl<T, A: MemPool> !Send for Vec<T, A> {}
impl<T, A: MemPool> !Sync for Vec<T, A> {}
impl<T, A: MemPool> !VSafe for Vec<T, A> {}
impl<T: PSafe, A: MemPool> Vec<T, A> {
/// Creates an empty vector with zero capacity for the pool of the give `Journal`
pub const fn new() -> Self {
Self::empty()
}
/// Creates an empty vector and places `x` into it
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::from_slice(&[1, 2], j);
///
/// assert_eq!(vec.len(), 2);
/// assert_eq!(vec[0], 1);
///
/// assert_eq!(vec.pop(), Some(2));
/// assert_eq!(vec.len(), 1);
///
/// vec.extend_from_slice(&[1, 2, 3], j);
///
/// for x in &*vec {
/// println!("{}", x);
/// }
///
/// assert_eq!(vec, [1, 1, 2, 3]);
/// }).unwrap();
/// ```
pub fn from_slice(x: &[T], journal: &Journal<A>) -> Self {
if x.len() == 0 {
Self::empty()
} else {
let buf = unsafe { A::new_slice(x, journal) };
let offset = unsafe { A::off_unchecked(buf) };
Self::from_off_len(offset, buf.len(), buf.len())
}
}
pub(crate) unsafe fn from_slice_nolog(x: &[T]) -> (Self, usize) {
if x.len() == 0 {
(Self::empty(), 0)
} else {
let (buf, off, _, z) = A::atomic_new_slice(x);
(Self::from_off_len(off, buf.len(), buf.len()), z)
}
}
/// Creates an empty `Vec` with the specified capacity
///
/// The vector will be able to hold exactly `capacity` elements without
/// reallocating. If `capacity` is 0, the vector will not allocate.
///
/// It is important to note that although the returned vector has the
/// *capacity* specified, the vector will have a zero *length*. For an
/// explanation of the difference between length and capacity, see
/// *[Capacity and reallocation]*.
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::with_capacity(10, j);
///
/// // The vector contains no items, even though it has capacity for more
/// assert_eq!(vec.len(), 0);
///
/// // These are all done without reallocating...
/// for i in 0..10 {
/// vec.push(i, j);
/// }
///
/// // ...but this may make the vector reallocate
/// vec.push(11, j);
/// }).unwrap();
/// ```
pub fn with_capacity(cap: usize, j: &Journal<A>) -> Self {
if cap == 0 {
Self::empty()
} else {
let layout = Layout::array::<T>(cap).unwrap();
unsafe {
let buf = A::new_uninit_for_layout(layout.size(), j);
Self::from_off_len(A::off_unchecked(buf), cap, 0)
}
}
}
/// Creates a `PVec<T>` directly from the raw components of another vector.
///
/// # Safety
///
/// This is highly unsafe, due to the number of invariants that aren't
/// checked:
///
/// * `ptr` needs to have been previously allocated via [`String`]/`Vec<T>`
/// (at least, it's highly likely to be incorrect if it wasn't).
/// * `ptr` should point to the same pool
/// * `T` needs to have the same size as what `ptr` was allocated with.
/// * `length` needs to be less than or equal to `capacity`.
/// * `capacity` needs to be the capacity that the pointer was allocated with.
///
/// The ownership of `ptr` is effectively transferred to the
/// `PVec<T>` which may then deallocate, reallocate or change the
/// contents of memory pointed to by the pointer at will. Ensure
/// that nothing else uses the pointer after calling this
/// function.
///
/// # Examples
///
/// ```
/// use std::ptr;
/// use std::mem;
/// use corundum::alloc::heap::Heap;
/// use corundum::vec::Vec as PVec;
///
/// let v = vec![1, 2, 3];
///
/// // Prevent running `v`'s destructor so we are in complete control
/// // of the allocation.
/// let mut v = mem::ManuallyDrop::new(v);
///
/// // Pull out the various important pieces of information about `v`
/// let p = v.as_mut_ptr();
/// let len = v.len();
/// let cap = v.capacity();
///
/// unsafe {
/// // Overwrite memory with 4, 5, 6
/// for i in 0..len as isize {
/// ptr::write(p.offset(i), 4 + i);
/// }
///
/// // Put everything back together into a Vec
/// let rebuilt = PVec::<isize, Heap>::from_raw_parts(p, len, cap);
/// assert_eq!(rebuilt, [4, 5, 6]);
/// }
/// ```
#[inline]
pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self {
let off = A::off_unchecked(ptr);
Self {
buf: Slice::<T,A>::from_off_cap(off, capacity),
len: length,
has_log: 0,
marker: PhantomData
}
}
/// Creates an empty vector with zero capacity
pub const fn empty() -> Self {
Self::from_off_len(u64::MAX, 0, 0)
}
/// Returns `true` if the vector contains no elements.
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut v = Vec::new();
/// assert!(v.is_empty());
///
/// v.push(1, j);
/// assert!(!v.is_empty());
/// }).unwrap();
/// ```
pub fn is_empty(&self) -> bool {
self.len == 0
}
/// Splits the collection into two at the given index.
///
/// Returns a newly allocated vector containing the elements in the range
/// `[at, len)`. After the call, the original vector will be left containing
/// the elements `[0, at)` with its previous capacity unchanged.
///
/// # Panics
///
/// Panics if `at > len`.
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::from_slice(&[1,2,3], j);
/// let vec2 = vec.split_off(1, j);
/// assert_eq!(vec, [1]);
/// assert_eq!(vec2, [2, 3]);
/// }).unwrap();
/// ```
#[inline]
pub fn split_off(&mut self, at: usize, j: &Journal<A>) -> Self {
assert!(at <= self.len(), "`at` out of bounds");
let other_len = self.len - at;
let mut other = Vec::with_capacity(other_len, j);
// Unsafely `set_len` and copy items to `other`.
unsafe {
self.set_len(at);
other.set_len_volatile(other_len);
ptr::copy_nonoverlapping(
self.as_ptr().add(at),
other.to_slice_mut().as_mut_ptr(),
other.len(),
);
}
other
}
/// Creates a `Vec` without allocating memory by specifying the `offset`,
/// `capacity`, and the `length` of the vector.
pub(crate) const fn from_off_len(offset: u64, capacity: usize, length: usize) -> Self {
Self {
buf: Slice::from_off_cap(offset, capacity),
len: length,
has_log: 0,
marker: PhantomData,
}
}
/// Returns raw parts in form of (buf: *mut u8, length: usize, capacity: usize)
pub(crate) unsafe fn into_raw_parts(&self) -> (*mut T, usize, usize) {
(
A::get_mut_unchecked(self.buf.off()),
self.len,
self.buf.capacity(),
)
}
#[inline]
fn get(&self, i: usize) -> &T {
self.buf.get(i)
}
#[inline]
fn get_mut(&self, i: usize) -> &mut T {
self.buf.get_mut(i)
}
#[inline]
/// Returns the offset of the vector in the persistent pool
pub fn off(&self) -> u64 {
self.buf.off()
}
#[inline]
/// Returns the available capacity of the vector in the persistent pool
pub fn capacity(&self) -> usize {
self.buf.capacity()
}
#[inline]
/// Forces the length of the vector to `new_len`.
///
/// This is a low-level operation that maintains none of the normal
/// invariants of the type. Normally changing the length of a vector
/// is done using one of the safe operations instead, such as
/// [`truncate`], [`resize`], [`push`], or [`clear`].
///
/// [`truncate`]: #method.truncate
/// [`resize`]: #method.resize
/// [`push`]: #method.push
/// [`clear`]: #method.clear
///
/// # Safety
///
/// - `new_len` must be less than or equal to [`capacity()`].
/// - The elements at `old_len..new_len` must be initialized.
///
/// [`capacity()`]: #method.capacity
pub unsafe fn set_len(&mut self, new_len: usize) {
debug_assert!(new_len <= self.buf.capacity());
self.len = new_len;
}
fn set_len_volatile(&mut self, new_len: usize) {
debug_assert!(new_len <= self.buf.capacity());
self.len = new_len;
}
#[inline]
/// Returns the length of the vector
pub fn len(&self) -> usize {
self.len
}
#[inline]
/// Consumes the vector and converts it into a slice
pub fn as_slice(&self) -> &[T] {
Self::to_slice(self.off(), self.len)
}
#[inline]
/// Returns a raw pointer to data if there is any
pub(crate) unsafe fn as_ptr(&self) -> *mut T {
if self.len == 0 {
std::ptr::null_mut()
} else {
A::get_mut_unchecked(self.off())
}
}
#[inline]
/// Consumes the vector and converts it into a slice.
/// Since we should create a log of the context, this function is transactional
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::from_slice(&[1,2,3], j);
/// let s = vec.as_slice_mut(j);
/// s[1] = 0;
/// assert_eq!(s, [1, 0, 3]);
/// assert_eq!(vec, [1, 0, 3]);
/// }).unwrap();
/// ```
///
pub fn as_slice_mut(&mut self, j: &Journal<A>) -> &mut [T] {
let res = Self::__to_slice_mut(self.off(), self.len());
if self.has_log == 0 {
unsafe {
res.create_log(j, Notifier::NonAtomic(Ptr::from_ref(&self.has_log)));
}
}
self.to_slice_mut()
}
#[inline]
/// Consumes the `corundum::vec::Vec` and converts it into a standard [`std::vec::Vec`](std::vec::Vec)
pub(crate) unsafe fn as_vec(&mut self) -> StdVec<T> {
StdVec::from_raw_parts(self.buf.as_mut_ptr(), self.len, self.buf.capacity())
}
#[inline]
fn to_slice<'a>(off: u64, len: usize) -> &'a [T] {
unsafe { A::deref_slice_unchecked(off, len) }
}
#[inline]
fn __to_slice_mut<'a>(off: u64, len: usize) -> &'a mut [T] {
unsafe { A::deref_slice_unchecked_mut(off, len) }
}
#[inline]
pub(crate) fn to_slice_mut(&mut self) -> &mut [T] {
Self::__to_slice_mut(self.off(), self.len())
}
/// Copy all the elements of `other` into `Self`
///
/// # Panics
///
/// Panics if the number of elements in the vector overflows a `usize`.
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::from_slice(&[1, 2, 3], j);
/// let mut other = vec![4, 5, 6];
/// vec.extend_from_slice(&other, j);
/// assert_eq!(vec.as_slice(), [1, 2, 3, 4, 5, 6]);
/// }).unwrap();
/// ```
pub fn extend_from_slice(&mut self, other: &[T], j: &Journal<A>) {
if other.len() != 0 {
unsafe {
let len = self.len;
let new_cap = self.capacity().max(len + other.len());
self.reserve(new_cap - self.capacity(), j);
let ptr = self.buf.as_mut_ptr();
ptr::copy(other.as_ptr(), ptr.add(len), other.len());
self.len += other.len();
}
}
}
#[inline]
pub fn shrink_to(&mut self, new_cap: usize, j: &Journal<A>) {
let cap = self.capacity();
eprintln!("shrink_to");
// Prevent shrinking to smaller than data
let new_cap = new_cap.max(self.len);
if get_idx(new_cap * mem::size_of::<T>()) != get_idx(cap * mem::size_of::<T>()) {
unsafe {
let buf = self.to_slice_mut();
let (rem, left) = buf.split_at_mut(buf.len().min(new_cap));
if !left.is_empty() {
ptr::drop_in_place(left);
// FIXME: use power of 2 sizes padding to be able to free memory
// of each individual item
}
if rem.is_empty() {
self.buf = Slice::null();
} else {
let new = A::new_slice(rem, j);
self.buf = Slice::from_off_cap(A::off_unchecked(new), new.len());
}
}
}
self.buf.set_cap(new_cap);
}
/// Shrinks the capacity of the vector as much as possible.
///
/// It will drop down as close as possible to the length but the allocator
/// may still inform the vector that there is space for a few more elements.
///
/// # ExamplesSlice
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::with_capacity(10, j);
/// vec.extend_from_slice(&[1, 2, 3], j);
/// assert_eq!(vec.capacity(), 10);
/// vec.shrink_to_fit(j);
/// assert!(vec.capacity() >= 3);
/// }).unwrap();
/// ```
pub fn shrink_to_fit(&mut self, j: &Journal<A>) {
if self.capacity() != self.len {
self.shrink_to(self.len, j);
}
}
/// Copy all the elements of `other` into `Self`
///
/// # Panics
///
/// Panics if the number of elements in the vector overflows a `usize`.
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::from_slice(&[1, 2, 3], j);
/// let mut other = vec![4, 5, 6];
/// vec.extend_from_slice(&other, j);
/// assert_eq!(vec.as_slice(), [1, 2, 3, 4, 5, 6]);
/// }).unwrap();
/// ```
#[inline]
pub fn reserve(&mut self, additional: usize, j: &Journal<A>) {
if additional == 0 {
return;
}
let cap = self.buf.capacity();
let len = self.len;
let new_cap = cap.max(len + additional);
if get_idx(new_cap * mem::size_of::<T>()) == get_idx(len * mem::size_of::<T>()) {
self.buf.set_cap(new_cap);
} else {
unsafe {
let old = self.to_slice_mut();
let layout = Layout::array::<T>(new_cap).unwrap();
let new = A::new_uninit_for_layout(layout.size(), j).cast();
ptr::copy(old.as_ptr(), new, len);
A::free_slice(Self::__to_slice_mut(self.off(), self.capacity()));
self.buf = Slice::new(slice::from_raw_parts(new, new_cap));
}
}
}
/// Shortens the vector, keeping the first `len` elements and dropping
/// the rest.
///
/// If `len` is greater than the vector's current length, this has no
/// effect.
///
/// Note that this method has no effect on the capacity. To shorten the
/// capacity too, use [`shrink_to`] or [`shrink_to_fit`].
///
/// # Examples
///
/// Truncating a five element vector to three elements, then truncating it
/// to two:
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::from_slice(&[1, 2, 3, 4, 5], j);
///
/// vec.truncate(3);
/// assert_eq!(vec, [1, 2, 3]);
/// assert_eq!(vec.capacity(), 5); // No effect on capacity
///
/// vec.truncate(2);
/// assert_eq!(vec.as_slice(), [1, 2]);
/// assert_eq!(vec.capacity(), 5); // Capacity is shrunk to 2
/// }).unwrap();
/// ```
///
/// No truncation occurs when `len` is greater than the vector's current
/// length:
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::from_slice(&[1, 2, 3], j);
/// vec.truncate(8);
/// assert_eq!(vec, [1, 2, 3]);
/// }).unwrap();
/// ```
///
/// Truncating when `len == 0` is equivalent to calling the [`clear`]
/// method.
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::from_slice(&[1, 2, 3], j);
/// vec.truncate(0);
/// assert_eq!(vec, []);
/// }).unwrap();
/// ```
///
/// [`clear`]: #method.clear
/// [`len`]: #method.len
/// [`shrink_to`]: #method.shrink_to
/// [`shrink_to_fit`]: #method.shrink_to_fit
pub fn truncate(&mut self, len: usize) {
// This is safe because:
//
// * the slice passed to `drop_in_place` is valid; the `len > self.len`
// case avoids creating an invalid slice, and
// * the `len` of the vector is shrunk before calling `drop_in_place`,
// such that no value will be dropped twice in case `drop_in_place`
// were to panic once (if it panics twice, the program aborts).
unsafe {
if len > self.len {
return;
}
let s = &mut self.to_slice_mut()[len..];
ptr::drop_in_place(s);
}
self.len = len;
}
/// Removes an element from the vector and returns it.
///
/// The removed element is replaced by the last element of the vector.
///
/// This does not preserve ordering, but is O(1).
///
/// # Panics
///
/// Panics if `index` is out of bounds.
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut v = Vec::from_slice(&[1, 2, 3, 4], j);
///
/// assert_eq!(v.swap_remove(1), 2);
/// assert_eq!(v, [1, 4, 3]);
///
/// assert_eq!(v.swap_remove(0), 1);
/// assert_eq!(v, [3, 4]);
/// }).unwrap();
/// ```
#[inline]
pub fn swap_remove(&mut self, index: usize) -> T {
unsafe {
// We replace self[index] with the last element. Note that if the
// bounds check on hole succeeds there must be a last element (which
// can be self[index] itself).
let hole: *mut T = &mut self.to_slice_mut()[index];
let last = ptr::read(self.buf.get_unchecked(self.len - 1));
self.len -= 1;
ptr::replace(hole, last)
}
}
/// Inserts an element at position `index` within the vector, shifting all
/// elements after it to the right.
///
/// # Panics
///
/// Panics if `index > len`.
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::from_slice(&[1, 2, 3], j);
/// vec.insert(1, 4, j);
/// assert_eq!(vec, [1, 4, 2, 3]);
/// vec.insert(4, 5, j);
/// assert_eq!(vec, [1, 4, 2, 3, 5]);
/// }).unwrap();
/// ```
pub fn insert(&mut self, index: usize, element: T, j: &Journal<A>) {
let len = self.len();
assert!(index <= len);
// space for the new element
if len == self.buf.capacity() {
self.reserve(1, j);
}
unsafe {
// infallible
// The spot to put the new value
{
let p = self.buf.as_mut_ptr().add(index);
// Shift everything over to make space. (Duplicating the
// `index`th element into two consecutive places.)
ptr::copy(p, p.offset(1), len - index);
// Write it in, overwriting the first copy of the `index`th
// element.
ptr::write(p, element);
}
self.set_len(len + 1);
}
}
/// Removes and returns the element at position `index` within the vector,
/// shifting all elements after it to the left.
///
/// # Panics
///
/// Panics if `index` is out of bounds.
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut v = Vec::from_slice(&[1, 2, 3], j);
/// assert_eq!(v.remove(1), 2);
/// assert_eq!(v, [1, 3]);
/// }).unwrap();
/// ```
pub fn remove(&mut self, index: usize) -> T {
let len = self.len();
assert!(index < len);
unsafe {
// infallible
let ret;
{
// the place we are taking from.
let ptr = self.buf.as_mut_ptr().add(index);
// copy it out, unsafely having a copy of the value on
// the stack and in the vector at the same time.
ret = ptr::read(ptr);
// Shift everything down to fill in that spot.
ptr::copy(ptr.offset(1), ptr, len - index - 1);
}
self.set_len(len - 1);
ret
}
}
/// Retains only the elements specified by the predicate.
///
/// In other words, remove all elements `e` such that `f(&e)` returns `false`.
/// This method operates in place, visiting each element exactly once in the
/// original order, and preserves the order of the retained elements.
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::from_slice(&[1, 2, 3, 4], j);
/// vec.retain(|&x| x % 2 == 0);
/// assert_eq!(vec, [2, 4]);
/// }).unwrap();
/// ```
///
/// The exact order may be useful for tracking external state, like an index.
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::from_slice(&[1, 2, 3, 4, 5], j);
/// let keep = [false, true, true, false, true];
/// let mut i = 0;
/// vec.retain(|_| (keep[i], i += 1).0);
/// assert_eq!(vec, [2, 3, 5]);
/// }).unwrap();
/// ```
pub fn retain<F>(&mut self, mut f: F)
where
F: FnMut(&T) -> bool,
{
let len = self.len();
let mut del = 0;
{
let v = self.to_slice_mut();
for i in 0..len {
if !f(&v[i]) {
del += 1;
} else if del > 0 {
v.swap(i - del, i);
}
}
}
if del > 0 {
self.truncate(len - del);
}
}
// /// Removes all but the first of consecutive elements in the vector that resolve to the same
// /// key.
// ///
// /// If the vector is sorted, this removes all duplicates.
// ///
// /// # Examples
// ///
// /// ```
// /// # use corundum::vec::Vec;
// /// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
// /// let mut vec = Vec::from_slice(&[10, 20, 21, 30, 20], j);
// ///
// /// vec.dedup_by_key(|i| *i / 10);
// ///
// /// assert_eq!(vec, [10, 20, 30, 20]);
// /// }).unwrap();
// /// ```
// #[inline]
// pub fn dedup_by_key<F, K>(&mut self, mut key: F)
// where
// F: FnMut(&mut T) -> K,
// K: PartialEq,
// {
// self.dedup_by(|a, b| key(a) == key(b))
// }
// /// Removes all but the first of consecutive elements in the vector satisfying a given equality
// /// relation.
// ///
// /// The `same_bucket` function is passed references to two elements from the vector and
// /// must determine if the elements compare equal. The elements are passed in opposite order
// /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is removed.
// ///
// /// If the vector is sorted, this removes all duplicates.
// ///
// /// # Examples
// ///
// /// ```
// /// # use corundum::vec::Vec;
// /// # use corundum::str::*;
// /// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
// /// let mut vec = Vec::from_slice(&["foo", "bar", "Bar", "baz", "bar"], j);
// ///
// /// vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
// ///
// /// assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
// /// }).unwrap()
// /// ```
// pub fn dedup_by<F>(&mut self, same_bucket: F)
// where
// F: FnMut(&mut T, &mut T) -> bool,
// {
// let len = {
// let (dedup, _) = self.as_mut_slice().partition_dedup_by(same_bucket);
// dedup.len()
// };
// self.truncate(len);
// }
/// Appends an element to the back of a collection.
///
/// # Panics
///
/// Panics if the number of elements in the vector overflows a `usize`.
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::from_slice(&[1, 2], j);
/// vec.push(3, j);
/// assert_eq!(vec, [1, 2, 3]);
/// }).unwrap();
/// ```
#[inline]
pub fn push(&mut self, value: T, j: &Journal<A>) {
// This will panic or abort if we would allocate > isize::MAX bytes
// or if the length increment would overflow for zero-sized types.
if self.len == self.buf.capacity() {
self.reserve(1, j);
}
unsafe {
let end = self.buf.as_mut_ptr().add(self.len);
ptr::write(end, value);
self.len += 1;
}
}
/// Removes the last element from a vector and returns it, or [`None`] if it
/// is empty.
///
/// [`None`]: std::option::Option::None
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::from_slice(&[1, 2, 3], j);
/// assert_eq!(vec.pop(), Some(3));
/// assert_eq!(vec, [1, 2]);
/// }).unwrap();
/// ```
#[inline]
pub fn pop(&mut self) -> Option<T> {
if self.len == 0 {
None
} else {
unsafe {
self.len -= 1;
Some(ptr::read(self.buf.get_unchecked(self.len())))
}
}
}
/// Moves all the elements of `other` into `Self`, leaving `other` empty.
///
/// # Panics
///
/// Panics if the number of elements in the vector overflows a `usize`.
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut vec = Vec::from_slice(&[1, 2, 3], j);
/// let mut vec2 = Vec::from_slice(&[4, 5, 6], j);
/// vec.append(&mut vec2, j);
/// assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
/// assert_eq!(vec2, []);
/// }).unwrap();
/// ```
#[inline]
pub fn append(&mut self, other: &mut Self, j: &Journal<A>) {
unsafe {
self.extend_from_slice(other.as_slice(), j);
other.set_len(0);
}
}
/// Clears the vector, removing all values.
///
/// Note that this method has no effect on the allocated capacity
/// of the vector.
///
/// # Examples
///
/// ```
/// # use corundum::vec::Vec;
/// # use corundum::alloc::heap::*;
/// Heap::transaction(|j| {
/// let mut v = Vec::from_slice(&[1, 2, 3], j);
/// v.clear();
/// assert!(v.is_empty());
/// }).unwrap();
/// ```
#[inline]
pub fn clear(&mut self) {
self.truncate(0);
}
/// Drops content without logging
#[inline]
pub(crate) unsafe fn free_nolog(&mut self) {
if A::valid(self) && self.capacity() > 0 {
A::free_nolog(Self::__to_slice_mut(self.off(), self.capacity()));
}
self.buf.set_cap(0);
self.len = 0;
}
pub fn cast<U, F: Fn(&T) -> U>(&self, f: F) -> std::vec::Vec<U> {
let mut res = std::vec::Vec::<U>::with_capacity(self.len);
for v in self {
res.push(f(v));
}
res
}
}
impl<T: PSafe, A: MemPool> Drop for Vec<T, A> {
fn drop(&mut self) {
unsafe {
let s = self.to_slice_mut();
ptr::drop_in_place(s);
A::free_slice(self.buf.as_slice_mut());
}
}
}
impl<A: MemPool, T: PSafe, I: SliceIndex<[T]>> Index<I> for Vec<T, A> {
type Output = I::Output;
#[inline]
fn index(&self, index: I) -> &Self::Output {
Index::index(&**self, index)
}
}
// impl<A: MemPool, T: PSafe, I: SliceIndex<[T]>> IndexMut<I> for Vec<T, A> {
// #[inline]
// fn index_mut(&mut self, index: I) -> &mut Self::Output {
// let self_mut = self.as_slice() as *const [T] as *mut [T];
// IndexMut::index_mut(unsafe { &mut *self_mut }, index)
// }
// }
// impl<T: PSafe, A: MemPool> Index<usize> for Vec<T, A> {
// fn index(&self, i: usize) -> &T {
// self.get(i)
// }
// }
// impl<T: PSafe, A: MemPool> IndexMut<usize> for Vec<T, A> {
// fn index_mut(&mut self, i: usize) -> &mut T {
// self.get_mut(i)
// }
// }
impl<T: PSafe, A: MemPool> std::ops::Deref for Vec<T, A> {
type Target = [T];
fn deref(&self) -> &[T] {
self.as_slice()
}
}
// impl<T: PSafe, A: MemPool> std::ops::DerefMut for Vec<T, A> {
// fn deref_mut(&mut self) -> &mut [T] {
// self.as_slice_mut()
// }
// }
impl<T: PSafe + Debug, A: MemPool> Debug for Vec<T, A> {
fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
let len = self.len();
write!(f, "[")?;
if len > 0 {
write!(f, "{:?}", self.get(0))?;
}
for i in 1..len {
write!(f, ", {:?}", self.get(i))?;
}
write!(f, "]")
}
}
impl<T: PSafe + Display, A: MemPool> Display for Vec<T, A> {
fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
let len = self.len();
write!(f, "[")?;
if len > 0 {
write!(f, "{}", self.get(0))?;
}
for i in 1..len {
write!(f, ", {}", self.get(i))?;
}
write!(f, "]")
}
}
macro_rules! __impl_slice_eq1 {
([$($vars:tt)*] $lhs:ty, $rhs:ty, $($constraints:tt)*) => {
impl<T: PSafe, U: PSafe, A: MemPool, $($vars)*> PartialEq<$rhs> for $lhs
where
T: PartialEq<U>,
$($constraints)*
{
#[inline]
fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] }
#[inline]
fn ne(&self, other: &$rhs) -> bool { self[..] != other[..] }
}
}
}
__impl_slice_eq1! { [] Vec<T, A>, Vec<U, A>, }
__impl_slice_eq1! { [] Vec<T, A>, &[U], }
__impl_slice_eq1! { [] Vec<T, A>, &mut [U], }
// __impl_slice_eq1! { [] Cow<'_, [T]>, &[U], T: PClone<A> }
// __impl_slice_eq1! { [] Cow<'_, [T]>, &mut [U], T: PClone<A> }
// __impl_slice_eq1! { [] Cow<'_, [T]>, Vec<U, A>, T: PClone<A> }
__impl_slice_eq1! { [const N: usize] Vec<T, A>, [U; N], }
__impl_slice_eq1! { [const N: usize] Vec<T, A>, &[U; N], }
// NOTE: some less important impls are omitted to reduce code bloat
// FIXME(Centril): Reconsider this?
// __impl_slice_eq1! { [const N: usize] Vec<A>, &mut [B; N], }
// __impl_slice_eq1! { [const N: usize] Cow<'a, [A]>, [B; N], }
// __impl_slice_eq1! { [const N: usize] Cow<'a, [A]>, &[B; N], }
// __impl_slice_eq1! { [const N: usize] Cow<'a, [A]>, &mut [B; N], }
/// Implements comparison of vectors, lexicographically.
impl<A: MemPool, T: PSafe + PartialOrd> PartialOrd for Vec<T, A> {
#[inline]
fn partial_cmp(&self, other: &Vec<T, A>) -> Option<Ordering> {
PartialOrd::partial_cmp(&**self, &**other)
}
}
impl<A: MemPool, T: PSafe + PClone<A>> PClone<A> for Vec<T, A> {
fn pclone(&self, j: &Journal<A>) -> Self {
Vec::from_slice(PClone::pclone(&self.as_slice(), j), j)
}
}
impl<A: MemPool, T: PSafe + Eq> Eq for Vec<T, A> {}
/// Implements ordering of vectors, lexicographically.
impl<A: MemPool, T: PSafe + Ord> Ord for Vec<T, A> {
#[inline]
fn cmp(&self, other: &Vec<T, A>) -> Ordering {
Ord::cmp(&**self, &**other)
}
}
impl<T: PSafe, A: MemPool> Default for Vec<T, A> {
fn default() -> Self {
Vec::empty()
}
}
impl<T: PSafe, A: MemPool> RootObj<A> for Vec<T, A> {
fn init(_: &Journal<A>) -> Self {
Vec::empty()
}
}
// Consuming iterator
/// structure helper for consuming iterator.
pub struct IntoIteratorHelper<T> {
iter: std::vec::IntoIter<T>,
}
/// implement the IntoIterator trait for a consuming iterator. Iteration will
/// consume the Words structure
impl<T: PSafe, A: MemPool> IntoIterator for Vec<T, A> {
type Item = T;
type IntoIter = IntoIteratorHelper<T>;
// note that into_iter() is consuming self
fn into_iter(self) -> Self::IntoIter {
unsafe {
IntoIteratorHelper {
iter: std::vec::Vec::from_raw_parts(
self.buf.as_mut_ptr(),
self.len,
self.buf.capacity(),
)
.into_iter(),
}
}
}
}
// now, implements Iterator trait for the helper struct, to be used by adapters
impl<T: PSafe> Iterator for IntoIteratorHelper<T> {
type Item = T;
// just return the str reference
fn next(&mut self) -> Option<Self::Item> {
self.iter.next()
}
}
// non-consuming iterator
/// structure helper for non-consuming iterator.
pub struct IterHelper<'a, T> {
iter: std::slice::Iter<'a, T>,
}
/// implement the IntoIterator trait for a non-consuming iterator. Iteration will
/// borrow the Words structure
impl<'a, T: PSafe, A: MemPool> IntoIterator for &'a Vec<T, A> {
type Item = &'a T;
type IntoIter = IterHelper<'a, T>;
// note that into_iter() is consuming self
fn into_iter(self) -> Self::IntoIter {
IterHelper {
iter: self.as_slice().iter(),
}
}
}
/// now, implements Iterator trait for the helper struct, to be used by adapters
impl<'a, T> Iterator for IterHelper<'a, T> {
type Item = &'a T;
// just return the str reference
fn next(&mut self) -> Option<Self::Item> {
self.iter.next()
}
}
impl<T: PSafe, A: MemPool> AsRef<Vec<T, A>> for Vec<T, A> {
fn as_ref(&self) -> &Vec<T, A> {
self
}
}
// impl<T: PSafe, A: MemPool> AsMut<Vec<T, A>> for Vec<T, A> {
// fn as_mut(&mut self) -> &mut Vec<T, A> {
// self
// }
// }
impl<T: PSafe, A: MemPool> AsRef<[T]> for Vec<T, A> {
fn as_ref(&self) -> &[T] {
self
}
}
// impl<T: PSafe, A: MemPool> AsMut<[T]> for Vec<T, A> {
// fn as_mut(&mut self) -> &mut [T] {
// self
// }
// }
impl<T: Clone + PSafe, A: MemPool> PFrom<&[T], A> for Vec<T, A> {
fn pfrom(s: &[T], j: &Journal<A>) -> Vec<T, A> {
Vec::from_slice(s, j)
}
}
impl<T: Clone + PSafe, A: MemPool> PFrom<&mut [T], A> for Vec<T, A> {
fn pfrom(s: &mut [T], j: &Journal<A>) -> Vec<T, A> {
Vec::from_slice(s, j)
}
}
// impl<'a, T: PSafe, A: MemPool> From<Cow<'a, [T]>> for Vec<T, A>
// where
// [T]: ToOwned<Owned = Vec<T, A>>,
// {
// fn from(s: Cow<'a, [T]>) -> Vec<T, A> {
// s.into_owned()
// }
// }
// note: test pulls in libstd, which causes errors here
impl<T: PSafe, A: MemPool> PFrom<Box<[T]>, A> for Vec<T, A> {
fn pfrom(s: Box<[T]>, j: &Journal<A>) -> Vec<T, A> {
Vec::from_slice(s.into_vec().as_slice(), j)
}
}
// // note: test pulls in libstd, which causes errors here
// impl<T: PSafe, A: MemPool> From<Pbox<[T], A>> for Vec<T, A> {
// fn from(s: Pbox<[T], A>) -> Vec<T, A> {
// let journal = Journal::try_current().expect("This function should be called only inside a transaction").0;
// Vec::from_slice(s.into_vec().as_slice(), &journal)
// }
// }
// // note: test pulls in libstd, which causes errors here
// impl<T: PSafe, A: MemPool> From<Vec<T, A>> for Pbox<[T]> {
// fn from(v: Vec<T, A>) -> Pbox<[T]> {
// v.into_boxed_slice()
// }
// }
impl<A: MemPool> PFrom<&str, A> for Vec<u8, A> {
fn pfrom(s: &str, j: &Journal<A>) -> Vec<u8, A> {
PFrom::pfrom(s.as_bytes(), j)
}
}
impl<A: MemPool> Vec<u8, A> {
pub fn to_str(&self) -> &str {
unsafe { std::str::from_utf8_unchecked(self.as_slice()) }
}
}
#[cfg(test)]
mod test {
use crate::RootObj;
use crate::default::*;
use crate::open_flags::*;
type A = Allocator;
#[test]
fn test_array() {
struct Root {
buf: Pbox<PRefCell<PVec<i32>>>,
}
impl RootObj<A> for Root {
fn init(j: &Journal) -> Self {
Self {
buf: Pbox::new(PRefCell::new(PVec::default()), j),
}
}
}
let root = A::open::<Root>("sb4.pool", O_CFNE).unwrap();
println!("{:?}", root.buf);
// for _ in 0..100 {
println!("usage: {} bytes", A::used());
let _ = A::transaction(|j| {
let mut buf = root.buf.borrow_mut(j);
for _ in 0..5 {
let i = buf.len() as i32;
buf.extend_from_slice(&[i + 1, i + 2, i + 3], j);
}
// let idx_0 = buf[0];
// buf[0] = buf[1];
// buf[1] = buf[2];
if crate::utils::rand() % 2 == 1 {
panic!("test");
}
// buf[2] = idx_0;
});
println!("usage: {} bytes", A::used());
// }
println!("{:?}", root.buf);
}
#[test]
fn test_resize() {
struct Root {
buf: Pbox<PRefCell<PVec<i32>>>,
}
impl RootObj<A> for Root {
fn init(j: &Journal) -> Self {
Self {
buf: Pbox::new(PRefCell::new(PVec::empty()), j),
}
}
}
let root = A::open::<Root>("sb5.pool", O_CFNE).unwrap();
println!("PRE: {:?}", root.buf);
let pre = A::used();
let _ = A::transaction(|j| {
let mut buf = root.buf.borrow_mut(j);
// for _ in 0..5 {
let i = buf.len() as i32;
buf.extend_from_slice(&[i + 1], j);
// panic!("intentional");
// std::process::exit(0);
// }
});
println!("NEXT: {:?}", root.buf);
println!(" pre usage = {} bytes", pre);
println!("post usage = {} bytes", A::used());
}
#[test]
fn test_clear() {
use crate::vec::Vec;
crate::heap::Heap::transaction::<_, _>(|j| {
let mut vec = Vec::from_slice(&[1, 2, 3], j);
vec.truncate(0);
assert_eq!(vec, []);
})
.unwrap();
}
}