src/doc/nomicon/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 ```rust,ignore
  12 struct RawVec<T> {
  13     ptr: Unique<T>,
  14     cap: usize,
  15 }
  16
  17 impl<T> RawVec<T> {
  18     fn new() -> Self {
  19         assert!(mem::size_of::<T>() != 0, "TODO: implement ZST support");
  20         unsafe {
  21             RawVec { ptr: Unique::new(heap::EMPTY as *mut T), cap: 0 }
  22         }
  23     }
  24
  25     // unchanged from Vec
  26     fn grow(&mut self) {
  27         unsafe {
  28             let align = mem::align_of::<T>();
  29             let elem_size = mem::size_of::<T>();
  30
  31             let (new_cap, ptr) = if self.cap == 0 {
  32                 let ptr = heap::allocate(elem_size, align);
  33                 (1, ptr)
  34             } else {
  35                 let new_cap = 2 * self.cap;
  36                 let ptr = heap::reallocate(*self.ptr as *mut _,
  37                                             self.cap * elem_size,
  38                                             new_cap * elem_size,
  39                                             align);
  40                 (new_cap, ptr)
  41             };
  42
  43             // If allocate or reallocate fail, we'll get `null` back
  44             if ptr.is_null() { oom() }
  45
  46             self.ptr = Unique::new(ptr as *mut _);
  47             self.cap = new_cap;
  48         }
  49     }
  50 }
  51
  52
  53 impl<T> Drop for RawVec<T> {
  54     fn drop(&mut self) {
  55         if self.cap != 0 {
  56             let align = mem::align_of::<T>();
  57             let elem_size = mem::size_of::<T>();
  58             let num_bytes = elem_size * self.cap;
  59             unsafe {
  60                 heap::deallocate(*self.ptr as *mut _, num_bytes, align);
  61             }
  62         }
  63     }
  64 }
  65 ```
  66
  67 And change Vec as follows:
  68
  69 ```rust,ignore
  70 pub struct Vec<T> {
  71     buf: RawVec<T>,
  72     len: usize,
  73 }
  74
  75 impl<T> Vec<T> {
  76     fn ptr(&self) -> *mut T { *self.buf.ptr }
  77
  78     fn cap(&self) -> usize { self.buf.cap }
  79
  80     pub fn new() -> Self {
  81         Vec { buf: RawVec::new(), len: 0 }
  82     }
  83
  84     // push/pop/insert/remove largely unchanged:
  85     // * `self.ptr -> self.ptr()`
  86     // * `self.cap -> self.cap()`
  87     // * `self.grow -> self.buf.grow()`
  88 }
  89
  90 impl<T> Drop for Vec<T> {
  91     fn drop(&mut self) {
  92         while let Some(_) = self.pop() {}
  93         // deallocation is handled by RawVec
  94     }
  95 }
  96 ```
  97
  98 And finally we can really simplify IntoIter:
  99
 100 ```rust,ignore
 101 struct IntoIter<T> {
 102     _buf: RawVec<T>, // we don't actually care about this. Just need it to live.
 103     start: *const T,
 104     end: *const T,
 105 }
 106
 107 // next and next_back literally unchanged since they never referred to the buf
 108
 109 impl<T> Drop for IntoIter<T> {
 110     fn drop(&mut self) {
 111         // only need to ensure all our elements are read;
 112         // buffer will clean itself up afterwards.
 113         for _ in &mut *self {}
 114     }
 115 }
 116
 117 impl<T> Vec<T> {
 118     pub fn into_iter(self) -> IntoIter<T> {
 119         unsafe {
 120             // need to use ptr::read to unsafely move the buf out since it's
 121             // not Copy, and Vec implements Drop (so we can't destructure it).
 122             let buf = ptr::read(&self.buf);
 123             let len = self.len;
 124             mem::forget(self);
 125
 126             IntoIter {
 127                 start: *buf.ptr,
 128                 end: buf.ptr.offset(len as isize),
 129                 _buf: buf,
 130             }
 131         }
 132     }
 133 }
 134 ```
 135
 136 Much better.