rc_vec/
rc_vec.rs

1#[cfg(doc)]
2use alloc::{boxed::Box, vec::Vec};
3
4use alloc::{rc::Rc, sync::Arc};
5use core::{
6    cmp::max,
7    iter,
8    mem::MaybeUninit,
9    ops::{Deref, DerefMut, RangeBounds},
10    ptr, slice,
11};
12use rc_vec_proc_macro::rc_impl_gen_arc_impl;
13use unique_rc::{UniqArc, UniqRc};
14
15use crate::{
16    raw::{ArcRawVec, RcRawVec},
17    utils,
18};
19
20/// [`RcVec`] based on [`Rc`] and can be converted from Rc without allocation,
21/// just like [`Box`] is converted to [`Vec`]
22///
23/// # Examples
24///
25/// ```
26/// # use std::rc::Rc;
27/// use rc_vec::RcVec;
28///
29/// let rc: Rc<[i32]> = Rc::new([1, 2, 3]);
30/// let mut rc_vec = RcVec::from(rc);
31///
32/// assert_eq!(rc_vec, [1, 2, 3]);
33/// rc_vec.push(4);
34/// assert_eq!(rc_vec, [1, 2, 3, 4]);
35/// ```
36#[rc_impl_gen_arc_impl]
37pub struct RcVec<T> {
38    raw: RcRawVec<T>,
39    len: usize,
40}
41
42#[rc_impl_gen_arc_impl]
43impl<T> Deref for RcVec<T> {
44    type Target = [T];
45
46    fn deref(&self) -> &Self::Target {
47        let ptr = self.raw.as_ptr();
48        unsafe { slice::from_raw_parts(ptr, self.len) }
49    }
50}
51
52#[rc_impl_gen_arc_impl]
53impl<T> DerefMut for RcVec<T> {
54    fn deref_mut(&mut self) -> &mut Self::Target {
55        let ptr = self.raw.as_mut_ptr();
56        unsafe { slice::from_raw_parts_mut(ptr, self.len) }
57    }
58}
59
60#[rc_impl_gen_arc_impl]
61impl<T> Drop for RcVec<T> {
62    fn drop(&mut self) {
63        self.raw.drop_elems(self.len);
64    }
65}
66
67#[rc_impl_gen_arc_impl]
68impl<T> From<UniqRc<[T]>> for RcVec<T> {
69    fn from(value: UniqRc<[T]>) -> Self {
70        let len = value.len();
71        let raw = RcRawVec::from_uniq_slice(value);
72        Self { raw, len }
73    }
74}
75
76#[rc_impl_gen_arc_impl]
77impl<T> Default for RcVec<T> {
78    fn default() -> Self {
79        Self::new()
80    }
81}
82
83#[rc_impl_gen_arc_impl]
84impl<T> RcVec<T> {
85    /// Create a new [`RcVec`]
86    ///
87    /// # Examples
88    ///
89    /// ```
90    /// # use rc_vec::RcVec;
91    /// let mut vec = RcVec::new();
92    /// vec.push(3);
93    /// assert_eq!(vec, [3]);
94    /// ```
95    pub fn new() -> Self {
96        Self { raw: RcRawVec::new(), len: 0 }
97    }
98
99    /// Create a new [`RcVec`] Initial capacity of `capacity`
100    ///
101    /// # Examples
102    ///
103    /// ```
104    /// # use rc_vec::RcVec;
105    /// let vec = RcVec::with_capacity(176);
106    /// assert_eq!(vec.capacity(), 176);
107    /// assert_eq!(vec.len(), 0);
108    /// # assert_ne!(vec, [1]);
109    /// ```
110    pub fn with_capacity(capacity: usize) -> Self {
111        Self { raw: RcRawVec::with_capacity(capacity), len: 0 }
112    }
113
114    /// Readonly permission pointer
115    #[inline]
116    pub fn as_ptr(&self) -> *const T {
117        self.raw.as_ptr()
118    }
119
120    /// Read and Write permission pointer
121    ///
122    /// # Examples
123    ///
124    /// ```
125    /// # use rc_vec::rc_vec;
126    /// let mut vec = rc_vec![1, 2, 3];
127    /// assert_eq!(vec, [1, 2, 3]);
128    /// unsafe { *vec.as_mut_ptr() += 1 }
129    /// assert_eq!(vec, [2, 2, 3]);
130    /// ```
131    #[inline]
132    pub fn as_mut_ptr(&mut self) -> *mut T {
133        self.raw.as_mut_ptr()
134    }
135
136    /// Get initialized datas count
137    ///
138    /// # Examples
139    ///
140    /// ```
141    /// # use rc_vec::RcVec;
142    /// let mut vec = RcVec::with_capacity(4);
143    /// assert_eq!(vec.capacity(), 4);
144    ///
145    /// vec.push(2333);
146    ///
147    /// assert_eq!(vec.len(), 1);
148    /// assert_eq!(vec.capacity(), 4);
149    /// ```
150    #[inline]
151    pub fn len(&self) -> usize {
152        self.len
153    }
154
155    /// Like `.len() == 0`
156    #[inline]
157    pub fn is_empty(&self) -> bool {
158        self.len() == 0
159    }
160
161    /// Get allocated capacity
162    ///
163    /// # Examples
164    ///
165    /// ```
166    /// # use rc_vec::RcVec;
167    /// let vec = RcVec::with_capacity(176);
168    /// assert_eq!(vec.capacity(), 176);
169    /// assert_eq!(vec.len(), 0);
170    /// # assert_ne!(vec, [1]);
171    /// ```
172    #[inline]
173    pub fn capacity(&self) -> usize {
174        self.raw.capacity()
175    }
176
177    #[inline]
178    pub fn push(&mut self, value: T) {
179        if self.len == self.capacity() {
180            self.raw.reserve_for_push(self.len);
181        }
182
183        unsafe {
184            let end = self.as_mut_ptr().add(self.len);
185            end.write(value);
186            self.len += 1;
187        }
188    }
189
190    pub fn reserve(&mut self, additional: usize) {
191        self.raw.reserve(self.len, additional);
192    }
193
194    pub fn reserve_exact(&mut self, additional: usize) {
195        self.raw.reserve_exact(self.len, additional);
196    }
197
198    #[inline]
199    pub fn pop(&mut self) -> Option<T> {
200        if self.len == 0 {
201            None
202        } else {
203            unsafe {
204                self.len -= 1;
205                Some(self.as_ptr().add(self.len).read())
206            }
207        }
208    }
209
210    #[inline]
211    #[track_caller]
212    pub fn remove(&mut self, index: usize) -> T {
213        fn assert_failed(index: usize, len: usize) -> ! {
214            panic!("remove index (is {index}) should be < len (is {len})")
215        }
216
217        let len = self.len();
218        if index >= len {
219            assert_failed(index, len);
220        }
221
222        unsafe {
223            let ret;
224            {
225                let ptr = self.as_mut_ptr().add(index);
226                ret = ptr.read();
227                ptr::copy(ptr.add(1), ptr, len - index - 1);
228            }
229            self.set_len(len - 1);
230            ret
231        }
232    }
233
234    /// Like [`Vec::insert`]
235    ///
236    /// # Panics
237    ///
238    /// - `index > self.len()`
239    ///
240    /// # Examples
241    ///
242    /// ```
243    /// # use rc_vec::rc_vec;
244    /// let mut vec = rc_vec![1, 2, 3];
245    /// vec.insert(1, 4);
246    /// assert_eq!(vec, [1, 4, 2, 3]);
247    /// vec.insert(4, 5);
248    /// assert_eq!(vec, [1, 4, 2, 3, 5]);
249    /// ```
250    #[track_caller]
251    pub fn insert(&mut self, index: usize, element: T) {
252        #[cold]
253        #[inline(never)]
254        #[track_caller]
255        fn assert_failed(index: usize, len: usize) -> ! {
256            panic!("insertion index (is {index}) should be <= len (is {len})");
257        }
258
259        let len = self.len();
260
261        if len == self.capacity() {
262            self.reserve(1);
263        }
264
265        unsafe {
266            let p = self.as_mut_ptr().add(index);
267
268            if index < len {
269                ptr::copy(p, p.add(1), len - index);
270            } else if index == len {
271                // no move
272            } else {
273                assert_failed(index, len);
274            }
275
276            ptr::write(p, element);
277
278            self.set_len(len + 1);
279        }
280    }
281
282    #[inline]
283    #[track_caller]
284    pub fn swap_remove(&mut self, index: usize) -> T {
285        fn assert_failed(index: usize, len: usize) -> ! {
286            panic!("swap_remove index (is {index}) should be < len (is {len})")
287        }
288
289        let len = self.len();
290        if index >= len {
291            assert_failed(index, len);
292        }
293
294        unsafe {
295            let value = self.as_ptr().add(index).read();
296            let ptr = self.as_mut_ptr();
297            ptr.add(index).copy_from(ptr.add(len-1), 1);
298            self.set_len(len-1);
299            value
300        }
301    }
302
303    /// Reallocate to remove excess capacity
304    ///
305    /// # Examples
306    ///
307    /// ```
308    /// # use rc_vec::RcVec;
309    /// let mut vec = RcVec::with_capacity(16);
310    /// vec.push(233);
311    /// assert_eq!(vec.len(), 1);
312    /// assert_eq!(vec.capacity(), 16);
313    ///
314    /// vec.shrink_to_fit();
315    /// assert_eq!(vec.len(), 1);
316    /// assert_eq!(vec.capacity(), 1);
317    /// ```
318    pub fn shrink_to_fit(&mut self) {
319        if self.capacity() > self.len() {
320            self.raw.shrink_to_fit(self.len());
321        }
322    }
323
324    /// Reallocate to max(`min_capacity`, `.len()`)
325    pub fn shrink_to(&mut self, min_capacity: usize) {
326        if self.capacity() > min_capacity {
327            self.raw.shrink_to_fit(max(self.len(), min_capacity));
328        }
329    }
330
331    /// Like [`Vec::set_len`]
332    ///
333    /// # Safety
334    /// See [`Vec::set_len`] for safety concerns and examples.
335    #[inline]
336    pub unsafe fn set_len(&mut self, new_len: usize) {
337        self.len = new_len;
338    }
339
340    /// Like [`Vec::spare_capacity_mut`]
341    ///
342    /// # Examples
343    ///
344    /// ```
345    /// # use rc_vec::RcVec;
346    /// # use std::mem::MaybeUninit;
347    /// let mut vec = RcVec::with_capacity(4);
348    ///
349    /// vec.push(0);
350    /// assert_eq!(*vec, [0]);
351    ///
352    /// let spare = vec.spare_capacity_mut();
353    /// assert_eq!(spare.len(), 3);
354    /// spare[0] = MaybeUninit::new(1);
355    /// assert_eq!(*vec, [0]);
356    ///
357    /// unsafe {
358    ///     // SAFETY: The initialized data has been written to spare
359    ///     vec.set_len(vec.len() + 1);
360    /// }
361    /// assert_eq!(*vec, [0, 1]);
362    /// ```
363    #[inline]
364    pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
365        &mut self.raw.slice_mut()[self.len..]
366    }
367
368    unsafe fn split_at_spare_mut_with_len(
369        &mut self,
370    ) -> (&mut [T], &mut [MaybeUninit<T>], &mut usize) {
371        let (initialized, spare)
372            = self.raw.slice_mut().split_at_mut(self.len);
373        let initialized_ptr = initialized.as_mut_ptr().cast::<T>();
374        let initialized = slice::from_raw_parts_mut(initialized_ptr, self.len);
375
376        (initialized, spare, &mut self.len)
377    }
378
379    /// # Safety
380    /// `slice` `0..len` must be initialized
381    #[inline]
382    pub unsafe fn from_raw_uniq_slice(
383        slice: UniqRc<[MaybeUninit<T>]>,
384        len: usize,
385    ) -> Self {
386        Self { raw: RcRawVec::from_raw_uniq_slice(slice), len }
387    }
388
389    pub fn from_uniq_slice(slice: UniqRc<[T]>) -> Self {
390        slice.into()
391    }
392
393    #[inline]
394    pub fn into_raw_uniq_slice(mut self) -> UniqRc<[MaybeUninit<T>]> {
395        self.raw.take().into_rc()
396    }
397
398    #[inline]
399    pub fn into_raw_uniq_slice_optional(mut self) -> Option<UniqRc<[MaybeUninit<T>]>> {
400        self.raw.take().into_raw_rc()
401    }
402
403    #[inline]
404    pub fn into_uniq_slice(mut self) -> UniqRc<[T]> {
405        self.shrink_to_fit();
406        let len = self.len();
407        debug_assert_eq!(len, self.capacity());
408
409        let raw = UniqRc::into_raw(self.raw.take().into_rc());
410        let slice = ptr::slice_from_raw_parts_mut(raw.cast::<T>(), len);
411        unsafe { UniqRc::from_raw_unchecked(slice) }
412    }
413
414    #[inline]
415    pub fn into_rc_slice(self) -> Rc<[T]> {
416        self.into_uniq_slice().into()
417    }
418
419    #[inline]
420    pub(crate) fn into_raw_vec(mut self) -> RcRawVec<T> {
421        self.raw.take()
422    }
423
424    pub fn truncate(&mut self, len: usize) {
425        let old_len = self.len();
426
427        // NOTE: use `>`, reference from Vec::truncate
428        if len > old_len {
429            return;
430        }
431
432        unsafe {
433            self.set_len(len);
434            self.raw.drop_elems_from_range(len..old_len);
435        }
436    }
437
438    #[inline]
439    pub fn clear(&mut self) {
440        let old_len = self.len();
441        unsafe {
442            self.set_len(0);
443            self.raw.drop_elems(old_len);
444        }
445    }
446
447    pub fn resize_with<F>(&mut self, new_len: usize, f: F)
448    where F: FnMut() -> T,
449    {
450        let len = self.len();
451
452        if new_len > len {
453            self.extend(iter::repeat_with(f).take(new_len-len));
454        } else {
455            self.truncate(len);
456        }
457    }
458
459    pub fn leak(mut self) -> &'static mut [T] {
460        let len = self.len();
461
462        if len == 0 {
463            return Default::default();
464        }
465
466        self.raw.take()
467            .into_raw_rc()
468            .map(UniqRc::into_raw)
469            .map(|raw| {
470                unsafe { slice::from_raw_parts_mut(raw.cast::<T>(), len) }
471            })
472            .unwrap_or_default()
473    }
474
475    pub fn iter(&self) -> slice::Iter<'_, T> {
476        self.into_iter()
477    }
478
479    pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> {
480        self.into_iter()
481    }
482}
483
484#[rc_impl_gen_arc_impl]
485impl<T: Clone> RcVec<T> {
486    pub fn resize(&mut self, new_len: usize, value: T) {
487        let len = self.len();
488
489        if new_len > len {
490            self.extend(iter::repeat_n(value, new_len-len));
491        } else {
492            self.truncate(len);
493        }
494    }
495
496    pub fn extend_from_slice(&mut self, buf: &[T]) {
497        self.reserve(buf.len());
498
499        for ele in buf {
500            let len = self.len();
501            let ele = ele.clone();
502
503            unsafe {
504                self.as_mut_ptr().add(len).write(ele);
505                self.set_len(len + 1);
506            }
507        }
508    }
509
510    pub fn extend_from_within<R>(&mut self, src: R)
511    where R: RangeBounds<usize>,
512    {
513        let range = utils::range(src, ..self.len());
514        self.reserve(range.len());
515
516        let (this, spare, len) = unsafe {
517            self.split_at_spare_mut_with_len()
518        };
519
520        let to_clone = unsafe { this.get_unchecked(range) };
521
522        to_clone.iter().zip(spare)
523            .map(|(src, dst)| dst.write(src.clone()))
524            .for_each(|_| *len += 1);
525    }
526}
527
528#[rc_impl_gen_arc_impl]
529impl<T> RcVec<T> {
530    /// Macro support
531    #[doc(hidden)]
532    #[allow(unused)]
533    pub fn from_elem(elem: T, len: usize) -> Self
534    where T: Clone,
535    {
536        Self::from_iter(iter::repeat_n(elem, len))
537    }
538
539    /// Macro support
540    #[doc(hidden)]
541    #[allow(unused)]
542    pub fn from_array<const N: usize>(arr: [T; N]) -> Self {
543        arr.into()
544    }
545}
rc_vec/rc_vec.rs

rc_vec/
rc_vec.rs
