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

rc_vec/
rc_vec.rs
