Hi, i'm trying to implement my own data structures for deeper understanding of how does rust works "under hood" and get more knowledge about data structures themselves.
I was going through video on yt: https://www.youtube.com/watch?v=3OL95gZgPWA
Checked his explanation on single linked list and really liked it.
So i was following his video on vector and at the end he used valgrind and got 0 leaks after implementing drop trait.
12 allocs and 12 frees for him.
And when i used it on mine i got 10 allocs and only 9 frees. Valgrind output:
==65605==
==65605== HEAP SUMMARY:
==65605== in use at exit: 56 bytes in 1 blocks
==65605== total heap usage: 10 allocs, 9 frees, 3,184 bytes allocated
==65605==
==65605== 56 bytes in 1 blocks are possibly lost in loss record 1 of 1
==65605== at 0x48447A8: malloc (vg_replace_malloc.c:446)
==65605== by 0x12A600: std::rt::lang_start_internal (in /home/lf/personal/data_structs/rust/target/release/rust)
==65605== by 0x110064: main (in /home/lf/personal/data_structs/rust/target/release/rust)
==65605==
==65605== LEAK SUMMARY:
==65605== definitely lost: 0 bytes in 0 blocks
==65605== indirectly lost: 0 bytes in 0 blocks
==65605== possibly lost: 56 bytes in 1 blocks
==65605== still reachable: 0 bytes in 0 blocks
==65605== suppressed: 0 bytes in 0 blocks
==65605==
==65605== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
Here is my vector implementation:
#[derive(Debug, PartialEq)]
pub struct Vec<T> {
ptr: NonNull<T>,
len: usize,
cap: usize,
}
impl<T> Vec<T> {
pub fn new() -> Self {
Self {
ptr: NonNull::dangling(),
len: 0,
cap: 0,
}
}
pub fn push(&mut self, val: T) {
if size_of::<T>() == 0 {
panic!("No zero sized types");
}
if self.cap == 0 {
let layout = alloc::Layout::array::<T>(4).expect("Could not allocate");
// SAFETY: the layout is hardcoded to be 4 * size_of<T>
// size_of<T> is > 0
let ptr = unsafe {
alloc::alloc(layout)
} as *mut T;
let ptr = NonNull::new(ptr).expect("Could not allocate memory");
// SAFETY: pointer is NonNull
// and we have just allocated enough sapce for this val (and 3 more).
// The memory previously at ptr is not read.
unsafe {
ptr.as_ptr().write(val);
}
self.ptr = ptr;
self.cap = 4;
self.len = 1;
} else if self.len < self.cap {
let offset = (self.len() + 1)
.checked_mul(size_of::<T>())
.expect("Cannot reach memory location");
assert!(offset < isize::MAX as usize, "Wrapped isize");
// SAFETY: offset cannot wrap around
// And pointer is pointing to valid memory
// Writing to a offset at self.len is valid
unsafe {
self.ptr.as_ptr().add(self.len).write(val);
self.len += 1;
}
} else {
debug_assert!(self.len == self.cap);
let new_cap = self.cap.checked_mul(2).expect("Capacity wrapped");
let align = std::mem::align_of::<T>();
let size = size_of::<T>() * self.cap;
size.checked_add(size % align).expect("Cannot allocate");
let ptr = unsafe {
let layout = alloc::Layout::from_size_align_unchecked(size, align);
let new_size = size_of::<T>() * new_cap;
let ptr = alloc::realloc(self.ptr.as_ptr() as *mut u8, layout, new_size);
let ptr = NonNull::new(ptr as *mut T).expect("Cannot reallocate");
// let offset = (self.len() + 1)
// .checked_mul(size_of::<T>())
// .expect("Cannot reach memory location");
// assert!(offset < isize::MAX as usize, "Wrapped isize");
self.ptr.as_ptr().add(self.len).write(val);
ptr
};
self.ptr = ptr;
self.len += 1;
self.cap = new_cap;
}
}
pub fn get(&self, index: usize) -> Option<&T> {
if index >= self.len {
return None;
}
Some(unsafe {
&*self.ptr.as_ptr().add(index)
})
}
pub fn len(&self) -> usize {
return self.len
}
pub fn cap(&self) -> usize {
return self.cap
}
}
And drop implementation:
impl<T> Drop for Vec<T> {
fn drop(&mut self) {
unsafe {
std::ptr::drop_in_place(
std::slice::from_raw_parts_mut(self.ptr.as_ptr(), self.len)
);
let layout = Layout::from_size_align_unchecked(
std::mem::size_of::<T>() * self.cap,
std::mem::align_of::<T>()
);
alloc::dealloc(self.ptr.as_ptr() as *mut u8, layout);
}
}
}
I found that it could be not about my implementation but rust runtime, but i'm not sure about if it's true at all.
And so to confirm i didn't make any mistakes i'm here. Of course i did rewatch video to be confident that i didn't make mistakes in syntax but anyways
, you accidentally used