## Keyboard shortcuts

Press `←` or `→` to navigate between chapters

Press `S` or `/` to search in the book

Press `?` to show this help

Press `Esc` to hide this help

# RawVec

We've actually reached an interesting situation here: we've duplicated the logic for specifying a buffer and freeing its memory in Vec and IntoIter. Now that we've implemented it and identified actual logic duplication, this is a good time to perform some logic compression.

We're going to abstract out the `(ptr, cap)` pair and give them the logic for allocating, growing, and freeing:

    struct RawVec<T> {
        ptr: NonNull<T>,
        cap: usize,
    }

    unsafe impl<T: Send> Send for RawVec<T> {}
    unsafe impl<T: Sync> Sync for RawVec<T> {}

    impl<T> RawVec<T> {
        fn new() -> Self {
            assert!(mem::size_of::<T>() != 0, "TODO: implement ZST support");
            RawVec {
                ptr: NonNull::dangling(),
                cap: 0,
            }
        }

        fn grow(&mut self) {
            // This can't overflow because we ensure self.cap <= isize::MAX.
            let new_cap = if self.cap == 0 { 1 } else { 2 * self.cap };

            // Layout::array checks that the number of bytes is <= usize::MAX,
            // but this is redundant since old_layout.size() <= isize::MAX,
            // so the `unwrap` should never fail.
            let new_layout = Layout::array::<T>(new_cap).unwrap();

            // Ensure that the new allocation doesn't exceed `isize::MAX` bytes.
            assert!(new_layout.size() <= isize::MAX as usize, "Allocation too large");

            let new_ptr = if self.cap == 0 {
                unsafe { alloc::alloc(new_layout) }
            } else {
                let old_layout = Layout::array::<T>(self.cap).unwrap();
                let old_ptr = self.ptr.as_ptr() as *mut u8;
                unsafe { alloc::realloc(old_ptr, old_layout, new_layout.size()) }
            };

            // If allocation fails, `new_ptr` will be null, in which case we abort.
            self.ptr = match NonNull::new(new_ptr as *mut T) {
                Some(p) => p,
                None => alloc::handle_alloc_error(new_layout),
            };
            self.cap = new_cap;
        }
    }

    impl<T> Drop for RawVec<T> {
        fn drop(&mut self) {
            if self.cap != 0 {
                let layout = Layout::array::<T>(self.cap).unwrap();
                unsafe {
                    alloc::dealloc(self.ptr.as_ptr() as *mut u8, layout);
                }
            }
        }
    }

And change Vec as follows:

    pub struct Vec<T> {
        buf: RawVec<T>,
        len: usize,
    }

    impl<T> Vec<T> {
        fn ptr(&self) -> *mut T {
            self.buf.ptr.as_ptr()
        }

        fn cap(&self) -> usize {
            self.buf.cap
        }

        pub fn new() -> Self {
            Vec {
                buf: RawVec::new(),
                len: 0,
            }
        }

        // push/pop/insert/remove largely unchanged:
        // * `self.ptr.as_ptr() -> self.ptr()`
        // * `self.cap -> self.cap()`
        // * `self.grow() -> self.buf.grow()`
    }

    impl<T> Drop for Vec<T> {
        fn drop(&mut self) {
            while let Some(_) = self.pop() {}
            // deallocation is handled by RawVec
        }
    }

And finally we can really simplify IntoIter:

    pub struct IntoIter<T> {
        _buf: RawVec<T>, // we don't actually care about this. Just need it to live.
        start: *const T,
        end: *const T,
    }

    // next and next_back literally unchanged since they never referred to the buf

    impl<T> Drop for IntoIter<T> {
        fn drop(&mut self) {
            // only need to ensure all our elements are read;
            // buffer will clean itself up afterwards.
            for _ in &mut *self {}
        }
    }

    impl<T> IntoIterator for Vec<T> {
        type Item = T;
        type IntoIter = IntoIter<T>;
        fn into_iter(self) -> IntoIter<T> {
            // need to use ptr::read to unsafely move the buf out since it's
            // not Copy, and Vec implements Drop (so we can't destructure it).
            let buf = unsafe { ptr::read(&self.buf) };
            let len = self.len;
            mem::forget(self);

            IntoIter {
                start: buf.ptr.as_ptr(),
                end: if buf.cap == 0 {
                    // can't offset off of a pointer unless it's part of an allocation
                    buf.ptr.as_ptr()
                } else {
                    unsafe { buf.ptr.as_ptr().add(len) }
                },
                _buf: buf,
            }
        }
    }

Much better.