src/doc/nomicon/src/vec/vec-raw.md

   1 # RawVec
   2
   3 We've actually reached an interesting situation here: we've duplicated the logic
   4 for specifying a buffer and freeing its memory in Vec and IntoIter. Now that
   5 we've implemented it and identified *actual* logic duplication, this is a good
   6 time to perform some logic compression.
   7
   8 We're going to abstract out the `(ptr, cap)` pair and give them the logic for
   9 allocating, growing, and freeing:
  10
  11 <!-- ignore: simplified code -->
  12 ```rust,ignore
  13 struct RawVec<T> {
  14     ptr: NonNull<T>,
  15     cap: usize,
  16     _marker: PhantomData<T>,
  17 }
  18
  19 unsafe impl<T: Send> Send for RawVec<T> {}
  20 unsafe impl<T: Sync> Sync for RawVec<T> {}
  21
  22 impl<T> RawVec<T> {
  23     fn new() -> Self {
  24         assert!(mem::size_of::<T>() != 0, "TODO: implement ZST support");
  25         RawVec {
  26             ptr: NonNull::dangling(),
  27             cap: 0,
  28             _marker: PhantomData,
  29         }
  30     }
  31
  32     fn grow(&mut self) {
  33         let (new_cap, new_layout) = if self.cap == 0 {
  34             (1, Layout::array::<T>(1).unwrap())
  35         } else {
  36             // This can't overflow because we ensure self.cap <= isize::MAX.
  37             let new_cap = 2 * self.cap;
  38
  39             // Layout::array checks that the number of bytes is <= usize::MAX,
  40             // but this is redundant since old_layout.size() <= isize::MAX,
  41             // so the `unwrap` should never fail.
  42             let new_layout = Layout::array::<T>(new_cap).unwrap();
  43             (new_cap, new_layout)
  44         };
  45
  46         // Ensure that the new allocation doesn't exceed `isize::MAX` bytes.
  47         assert!(new_layout.size() <= isize::MAX as usize, "Allocation too large");
  48
  49         let new_ptr = if self.cap == 0 {
  50             unsafe { alloc::alloc(new_layout) }
  51         } else {
  52             let old_layout = Layout::array::<T>(self.cap).unwrap();
  53             let old_ptr = self.ptr.as_ptr() as *mut u8;
  54             unsafe { alloc::realloc(old_ptr, old_layout, new_layout.size()) }
  55         };
  56
  57         // If allocation fails, `new_ptr` will be null, in which case we abort.
  58         self.ptr = match NonNull::new(new_ptr as *mut T) {
  59             Some(p) => p,
  60             None => alloc::handle_alloc_error(new_layout),
  61         };
  62         self.cap = new_cap;
  63     }
  64 }
  65
  66 impl<T> Drop for RawVec<T> {
  67     fn drop(&mut self) {
  68         if self.cap != 0 {
  69             let layout = Layout::array::<T>(self.cap).unwrap();
  70             unsafe {
  71                 alloc::dealloc(self.ptr.as_ptr() as *mut u8, layout);
  72             }
  73         }
  74     }
  75 }
  76 ```
  77
  78 And change Vec as follows:
  79
  80 <!-- ignore: simplified code -->
  81 ```rust,ignore
  82 pub struct Vec<T> {
  83     buf: RawVec<T>,
  84     len: usize,
  85 }
  86
  87 impl<T> Vec<T> {
  88     fn ptr(&self) -> *mut T {
  89         self.buf.ptr.as_ptr()
  90     }
  91
  92     fn cap(&self) -> usize {
  93         self.buf.cap
  94     }
  95
  96     pub fn new() -> Self {
  97         Vec {
  98             buf: RawVec::new(),
  99             len: 0,
 100         }
 101     }
 102
 103     // push/pop/insert/remove largely unchanged:
 104     // * `self.ptr.as_ptr() -> self.ptr()`
 105     // * `self.cap -> self.cap()`
 106     // * `self.grow() -> self.buf.grow()`
 107 }
 108
 109 impl<T> Drop for Vec<T> {
 110     fn drop(&mut self) {
 111         while let Some(_) = self.pop() {}
 112         // deallocation is handled by RawVec
 113     }
 114 }
 115 ```
 116
 117 And finally we can really simplify IntoIter:
 118
 119 <!-- ignore: simplified code -->
 120 ```rust,ignore
 121 pub struct IntoIter<T> {
 122     _buf: RawVec<T>, // we don't actually care about this. Just need it to live.
 123     start: *const T,
 124     end: *const T,
 125 }
 126
 127 // next and next_back literally unchanged since they never referred to the buf
 128
 129 impl<T> Drop for IntoIter<T> {
 130     fn drop(&mut self) {
 131         // only need to ensure all our elements are read;
 132         // buffer will clean itself up afterwards.
 133         for _ in &mut *self {}
 134     }
 135 }
 136
 137 impl<T> Vec<T> {
 138     pub fn into_iter(self) -> IntoIter<T> {
 139         unsafe {
 140             // need to use ptr::read to unsafely move the buf out since it's
 141             // not Copy, and Vec implements Drop (so we can't destructure it).
 142             let buf = ptr::read(&self.buf);
 143             let len = self.len;
 144             mem::forget(self);
 145
 146             IntoIter {
 147                 start: buf.ptr.as_ptr(),
 148                 end: buf.ptr.as_ptr().add(len),
 149                 _buf: buf,
 150             }
 151         }
 152     }
 153 }
 154 ```
 155
 156 Much better.