Implementing Vec final code does not compile #70
Comments
|
I tried to rewrite with latest allocator API, however not sure if this is the exactly right way (together with few tests). There was also logical error in implementation of Drain iterator (both directions called next_back): #![feature(ptr_internals)]
#![feature(allocator_api)]
#![feature(unique)]
use std::ptr::{Unique, self};
use std::mem;
use std::ops::{Deref, DerefMut};
use std::marker::PhantomData;
use std::heap::{GlobalAlloc, Layout, Global};
struct RawVec<T> {
ptr: Unique<T>,
cap: usize,
}
impl<T> RawVec<T> {
fn new() -> Self {
// !0 is usize::MAX. This branch should be stripped at compile time.
let cap = if mem::size_of::<T>() == 0 { !0 } else { 0 };
// Unique::empty() doubles as "unallocated" and "zero-sized allocation"
RawVec { ptr: Unique::empty(), cap: cap }
}
fn grow(&mut self) {
unsafe {
let elem_size = mem::size_of::<T>();
// since we set the capacity to usize::MAX when elem_size is
// 0, getting to here necessarily means the Vec is overfull.
assert!(elem_size != 0, "capacity overflow");
let (new_cap, ptr) = if self.cap == 0 {
let ptr = Global.alloc(Layout::array::<T>(1).unwrap());
(1, ptr)
} else {
let new_cap = 2 * self.cap;
let new_layout = Layout::array::<T>(new_cap).unwrap();
let ptr = Global.realloc(self.ptr.as_ptr() as *mut _,
new_layout,
new_layout.size());
(new_cap, ptr)
};
// If allocate or reallocate fail, oom
if let Some(p) = Unique::new(ptr as *mut _) {
self.ptr = p;
self.cap = new_cap;
} else {
::std::alloc::oom(Layout::new::<T>())
};
}
}
}
impl<T> Drop for RawVec<T> {
fn drop(&mut self) {
let elem_size = mem::size_of::<T>();
if self.cap != 0 && elem_size != 0 {
unsafe {
Global.dealloc(self.ptr.as_ptr() as *mut _,
Layout::array::<T>(self.cap).unwrap());
}
}
}
}
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 }
}
pub fn push(&mut self, elem: T) {
if self.len == self.cap() { self.buf.grow(); }
unsafe {
ptr::write(self.ptr().offset(self.len as isize), elem);
}
// Can't fail, we'll OOM first.
self.len += 1;
}
pub fn pop(&mut self) -> Option<T> {
if self.len == 0 {
None
} else {
self.len -= 1;
unsafe {
Some(ptr::read(self.ptr().offset(self.len as isize)))
}
}
}
pub fn insert(&mut self, index: usize, elem: T) {
assert!(index <= self.len, "index out of bounds");
if self.cap() == self.len { self.buf.grow(); }
unsafe {
if index < self.len {
ptr::copy(self.ptr().offset(index as isize),
self.ptr().offset(index as isize + 1),
self.len - index);
}
ptr::write(self.ptr().offset(index as isize), elem);
self.len += 1;
}
}
pub fn remove(&mut self, index: usize) -> T {
assert!(index < self.len, "index out of bounds");
unsafe {
self.len -= 1;
let result = ptr::read(self.ptr().offset(index as isize));
ptr::copy(self.ptr().offset(index as isize + 1),
self.ptr().offset(index as isize),
self.len - index);
result
}
}
pub fn into_iter(self) -> IntoIter<T> {
unsafe {
let iter = RawValIter::new(&self);
let buf = ptr::read(&self.buf);
mem::forget(self);
IntoIter {
iter: iter,
_buf: buf,
}
}
}
pub fn drain(&mut self) -> Drain<T> {
unsafe {
let iter = RawValIter::new(&self);
// this is a mem::forget safety thing. If Drain is forgotten, we just
// leak the whole Vec's contents. Also we need to do this *eventually*
// anyway, so why not do it now?
self.len = 0;
Drain {
iter: iter,
vec: PhantomData,
}
}
}
}
impl<T> Drop for Vec<T> {
fn drop(&mut self) {
while let Some(_) = self.pop() {}
// allocation is handled by RawVec
}
}
impl<T> Deref for Vec<T> {
type Target = [T];
fn deref(&self) -> &[T] {
unsafe {
::std::slice::from_raw_parts(self.ptr(), self.len)
}
}
}
impl<T> DerefMut for Vec<T> {
fn deref_mut(&mut self) -> &mut [T] {
unsafe {
::std::slice::from_raw_parts_mut(self.ptr(), self.len)
}
}
}
struct RawValIter<T> {
start: *const T,
end: *const T,
}
impl<T> RawValIter<T> {
unsafe fn new(slice: &[T]) -> Self {
RawValIter {
start: slice.as_ptr(),
end: if mem::size_of::<T>() == 0 {
((slice.as_ptr() as usize) + slice.len()) as *const _
} else if slice.len() == 0 {
slice.as_ptr()
} else {
slice.as_ptr().offset(slice.len() as isize)
}
}
}
}
impl<T> Iterator for RawValIter<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
if self.start == self.end {
None
} else {
unsafe {
let result = ptr::read(self.start);
self.start = if mem::size_of::<T>() == 0 {
(self.start as usize + 1) as *const _
} else {
self.start.offset(1)
};
Some(result)
}
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let elem_size = mem::size_of::<T>();
let len = (self.end as usize - self.start as usize)
/ if elem_size == 0 { 1 } else { elem_size };
(len, Some(len))
}
}
impl<T> DoubleEndedIterator for RawValIter<T> {
fn next_back(&mut self) -> Option<T> {
if self.start == self.end {
None
} else {
unsafe {
self.end = if mem::size_of::<T>() == 0 {
(self.end as usize - 1) as *const _
} else {
self.end.offset(-1)
};
Some(ptr::read(self.end))
}
}
}
}
pub struct IntoIter<T> {
_buf: RawVec<T>, // we don't actually care about this. Just need it to live.
iter: RawValIter<T>,
}
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<T> { self.iter.next() }
fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
}
impl<T> DoubleEndedIterator for IntoIter<T> {
fn next_back(&mut self) -> Option<T> { self.iter.next_back() }
}
impl<T> Drop for IntoIter<T> {
fn drop(&mut self) {
for _ in &mut *self {}
}
}
pub struct Drain<'a, T: 'a> {
vec: PhantomData<&'a mut Vec<T>>,
iter: RawValIter<T>,
}
impl<'a, T> Iterator for Drain<'a, T> {
type Item = T;
fn next(&mut self) -> Option<T> { self.iter.next() }
fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
}
impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
fn next_back(&mut self) -> Option<T> { self.iter.next_back() }
}
impl<'a, T> Drop for Drain<'a, T> {
fn drop(&mut self) {
// pre-drain the iter
for _ in &mut self.iter {}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn create_push_pop() {
let mut v = Vec::new();
v.push(1);
assert_eq!(1, v.len());
assert_eq!(1, v[0]);
for i in v.iter_mut() {
*i += 1;
}
v.insert(0, 1);
let x = v.pop();
assert_eq!(Some(2), x);
assert_eq!(1, v.len());
v.push(10);
let x = v.remove(0);
assert_eq!(1, x);
assert_eq!(1, v.len());
}
#[test]
fn iter_test() {
let mut v = Vec::new();
for i in 0..10 {
v.push(Box::new(i))
}
let mut iter = v.into_iter();
let first = iter.next().unwrap();
let last = iter.next_back().unwrap();
drop(iter);
assert_eq!(0, *first);
assert_eq!(9, *last);
}
#[test]
fn test_drain() {
let mut v = Vec::new();
for i in 0..10 {
v.push(Box::new(i))
}
{
let mut drain =v.drain();
let first = drain.next().unwrap();
let last = drain.next_back().unwrap();
assert_eq!(0, *first);
assert_eq!(9, *last);
}
assert_eq!(0, v.len());
v.push(Box::new(1));
assert_eq!(1, *v.pop().unwrap());
}
#[test]
fn test_zst() {
let mut v = Vec::new();
for _i in 0..10 {
v.push(())
}
let mut count = 0;
for _ in v.into_iter() {
count +=1
}
assert_eq!(10, count);
}
} |
|
Alternatively I used also NonNull (instead of Unique) and Alloc trait (instead of AllocGlobal) and it also worked - just wondering which approach is better? |
|
would you be interested in submitting a PR with your fixes?
…On Tue, Jun 12, 2018 at 12:35 PM, Ivan Zderadicka ***@***.***> wrote:
I tried to rewrite with latest allocator API, however not sure if this is
the exactly right way (together with few tests). There was also logical
error in implementation of Drain iterator (both directions called
next_back):
#![feature(ptr_internals)]
#![feature(allocator_api)]
#![feature(unique)]
use std::ptr::{Unique, self};use std::mem;use std::ops::{Deref, DerefMut};use std::marker::PhantomData;use std::heap::{GlobalAlloc, Layout, Global};
struct RawVec<T> {
ptr: Unique<T>,
cap: usize,
}
impl<T> RawVec<T> {
fn new() -> Self {
// !0 is usize::MAX. This branch should be stripped at compile time.
let cap = if mem::size_of::<T>() == 0 { !0 } else { 0 };
// Unique::empty() doubles as "unallocated" and "zero-sized allocation"
RawVec { ptr: Unique::empty(), cap: cap }
}
fn grow(&mut self) {
unsafe {
let elem_size = mem::size_of::<T>();
// since we set the capacity to usize::MAX when elem_size is
// 0, getting to here necessarily means the Vec is overfull.
assert!(elem_size != 0, "capacity overflow");
let (new_cap, ptr) = if self.cap == 0 {
let ptr = Global.alloc(Layout::array::<T>(1).unwrap());
(1, ptr)
} else {
let new_cap = 2 * self.cap;
let new_layout = Layout::array::<T>(new_cap).unwrap();
let ptr = Global.realloc(self.ptr.as_ptr() as *mut _,
new_layout,
new_layout.size());
(new_cap, ptr)
};
// If allocate or reallocate fail, oom
if let Some(p) = Unique::new(ptr as *mut _) {
self.ptr = p;
self.cap = new_cap;
} else {
::std::alloc::oom(Layout::new::<T>())
};
}
}
}
impl<T> Drop for RawVec<T> {
fn drop(&mut self) {
let elem_size = mem::size_of::<T>();
if self.cap != 0 && elem_size != 0 {
unsafe {
Global.dealloc(self.ptr.as_ptr() as *mut _,
Layout::array::<T>(self.cap).unwrap());
}
}
}
}
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 }
}
pub fn push(&mut self, elem: T) {
if self.len == self.cap() { self.buf.grow(); }
unsafe {
ptr::write(self.ptr().offset(self.len as isize), elem);
}
// Can't fail, we'll OOM first.
self.len += 1;
}
pub fn pop(&mut self) -> Option<T> {
if self.len == 0 {
None
} else {
self.len -= 1;
unsafe {
Some(ptr::read(self.ptr().offset(self.len as isize)))
}
}
}
pub fn insert(&mut self, index: usize, elem: T) {
assert!(index <= self.len, "index out of bounds");
if self.cap() == self.len { self.buf.grow(); }
unsafe {
if index < self.len {
ptr::copy(self.ptr().offset(index as isize),
self.ptr().offset(index as isize + 1),
self.len - index);
}
ptr::write(self.ptr().offset(index as isize), elem);
self.len += 1;
}
}
pub fn remove(&mut self, index: usize) -> T {
assert!(index < self.len, "index out of bounds");
unsafe {
self.len -= 1;
let result = ptr::read(self.ptr().offset(index as isize));
ptr::copy(self.ptr().offset(index as isize + 1),
self.ptr().offset(index as isize),
self.len - index);
result
}
}
pub fn into_iter(self) -> IntoIter<T> {
unsafe {
let iter = RawValIter::new(&self);
let buf = ptr::read(&self.buf);
mem::forget(self);
IntoIter {
iter: iter,
_buf: buf,
}
}
}
pub fn drain(&mut self) -> Drain<T> {
unsafe {
let iter = RawValIter::new(&self);
// this is a mem::forget safety thing. If Drain is forgotten, we just
// leak the whole Vec's contents. Also we need to do this *eventually*
// anyway, so why not do it now?
self.len = 0;
Drain {
iter: iter,
vec: PhantomData,
}
}
}
}
impl<T> Drop for Vec<T> {
fn drop(&mut self) {
while let Some(_) = self.pop() {}
// allocation is handled by RawVec
}
}
impl<T> Deref for Vec<T> {
type Target = [T];
fn deref(&self) -> &[T] {
unsafe {
::std::slice::from_raw_parts(self.ptr(), self.len)
}
}
}
impl<T> DerefMut for Vec<T> {
fn deref_mut(&mut self) -> &mut [T] {
unsafe {
::std::slice::from_raw_parts_mut(self.ptr(), self.len)
}
}
}
struct RawValIter<T> {
start: *const T,
end: *const T,
}
impl<T> RawValIter<T> {
unsafe fn new(slice: &[T]) -> Self {
RawValIter {
start: slice.as_ptr(),
end: if mem::size_of::<T>() == 0 {
((slice.as_ptr() as usize) + slice.len()) as *const _
} else if slice.len() == 0 {
slice.as_ptr()
} else {
slice.as_ptr().offset(slice.len() as isize)
}
}
}
}
impl<T> Iterator for RawValIter<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
if self.start == self.end {
None
} else {
unsafe {
let result = ptr::read(self.start);
self.start = if mem::size_of::<T>() == 0 {
(self.start as usize + 1) as *const _
} else {
self.start.offset(1)
};
Some(result)
}
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let elem_size = mem::size_of::<T>();
let len = (self.end as usize - self.start as usize)
/ if elem_size == 0 { 1 } else { elem_size };
(len, Some(len))
}
}
impl<T> DoubleEndedIterator for RawValIter<T> {
fn next_back(&mut self) -> Option<T> {
if self.start == self.end {
None
} else {
unsafe {
self.end = if mem::size_of::<T>() == 0 {
(self.end as usize - 1) as *const _
} else {
self.end.offset(-1)
};
Some(ptr::read(self.end))
}
}
}
}
pub struct IntoIter<T> {
_buf: RawVec<T>, // we don't actually care about this. Just need it to live.
iter: RawValIter<T>,
}
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<T> { self.iter.next() }
fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
}
impl<T> DoubleEndedIterator for IntoIter<T> {
fn next_back(&mut self) -> Option<T> { self.iter.next_back() }
}
impl<T> Drop for IntoIter<T> {
fn drop(&mut self) {
for _ in &mut *self {}
}
}
pub struct Drain<'a, T: 'a> {
vec: PhantomData<&'a mut Vec<T>>,
iter: RawValIter<T>,
}
impl<'a, T> Iterator for Drain<'a, T> {
type Item = T;
fn next(&mut self) -> Option<T> { self.iter.next() }
fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
}
impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
fn next_back(&mut self) -> Option<T> { self.iter.next_back() }
}
impl<'a, T> Drop for Drain<'a, T> {
fn drop(&mut self) {
// pre-drain the iter
for _ in &mut self.iter {}
}
}
#[cfg(test)]mod tests {
use super::*;
#[test]
fn create_push_pop() {
let mut v = Vec::new();
v.push(1);
assert_eq!(1, v.len());
assert_eq!(1, v[0]);
for i in v.iter_mut() {
*i += 1;
}
v.insert(0, 1);
let x = v.pop();
assert_eq!(Some(2), x);
assert_eq!(1, v.len());
v.push(10);
let x = v.remove(0);
assert_eq!(1, x);
assert_eq!(1, v.len());
}
#[test]
fn iter_test() {
let mut v = Vec::new();
for i in 0..10 {
v.push(Box::new(i))
}
let mut iter = v.into_iter();
let first = iter.next().unwrap();
let last = iter.next_back().unwrap();
drop(iter);
assert_eq!(0, *first);
assert_eq!(9, *last);
}
#[test]
fn test_drain() {
let mut v = Vec::new();
for i in 0..10 {
v.push(Box::new(i))
}
{
let mut drain =v.drain();
let first = drain.next().unwrap();
let last = drain.next_back().unwrap();
assert_eq!(0, *first);
assert_eq!(9, *last);
}
assert_eq!(0, v.len());
v.push(Box::new(1));
assert_eq!(1, *v.pop().unwrap());
}
#[test]
fn test_zst() {
let mut v = Vec::new();
for _i in 0..10 {
v.push(())
}
let mut count = 0;
for _ in v.into_iter() {
count +=1
}
assert_eq!(10, count);
}
}
—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
<#70 (comment)>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/ABFY4LCQtDPgcTwCXg99M8fRRLjxvLBXks5t7-3kgaJpZM4UkZp5>
.
|
|
I'll try |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The final example does not compile (just clicking the run button), with following messages:
Also previous examples during Implementing Vec chapter are using even older allocator API then this final code.
The text was updated successfully, but these errors were encountered: