rust_examples 0.1.11

use std::alloc::{self, Layout};
use std::marker::PhantomData;
use std::mem::{self};
use std::ops::{Deref, DerefMut};
use std::ptr::{self, NonNull};

struct Vec<T> {
    raw: RawVec<T>,
    len: usize,
}
unsafe impl<T: Send> Send for Vec<T> {}
unsafe impl<T: Sync> Sync for Vec<T> {}
impl<T> Vec<T> {
    pub fn new() -> Self {
        Vec {
            raw: RawVec::new(),
            len: 0,
        }
    }
    pub fn cap(&self) -> usize {
        self.raw.cap
    }
    pub fn ptr(&self) -> *mut T {
        self.raw.ptr.as_ptr()
    }

    pub fn push(&mut self, elem: T) {
        if self.len == self.cap() {
            self.raw.grow();
        }
        unsafe { self.ptr().add(self.len).write(elem) }
        self.len += 1;
    }
    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            None
        } else {
            self.len -= 1;
            unsafe { Some(self.ptr().add(self.len).read()) }
        }
    }
    pub fn insert(&mut self, index: usize, elem: T) {
        assert!(index <= self.len, "index out of bounds");
        if self.len == self.cap() {
            self.raw.grow();
        }
        unsafe {
            ptr::copy(
                self.ptr().add(index),
                self.ptr().add(index + 1),
                self.len - index,
            );
            ptr::write(self.ptr().add(index), 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().add(index));
            ptr::copy(
                self.ptr().add(index + 1),
                self.ptr().add(index),
                self.len - index,
            );
            result
        }
    }
    pub fn drain(&mut self) -> Drain<T> {
        let iter = unsafe { RawValIter::new(&self) };
        //    drop()的实际逻辑将由Drain做，所以self虽然还存在，但是已不能再做pop()操作。
        // 因为lifetime绑定，所以self和Drain的销毁时机是一致的。
        // 因为mut，self本身不能再被其他人使用
        self.len = 0;
        Drain {
            vec: PhantomData,
            iter,
        }
    }
}
impl<T> Drop for Vec<T> {
    fn drop(&mut self) {
        while let Some(_) = self.pop() {}
    }
}
impl<T> Deref for Vec<T> {
    type Target = [T];

    fn deref(&self) -> &Self::Target {
        unsafe { std::slice::from_raw_parts(self.ptr(), self.len) }
    }
}
impl<T> DerefMut for Vec<T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        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]) -> RawValIter<T> {
        RawValIter {
            start: slice.as_ptr(),
            end: if mem::size_of::<T>() == 0 {
                // 因为ZST，所以end如果用T的size来计算则和start一致，也就是说丢失了len信息
                let result = (slice.as_ptr() as usize + slice.len()) as *const _;
                result
            } else if slice.len() == 0 {
                slice.as_ptr()
            } else {
                slice.as_ptr().add(slice.len())
            },
        }
    }
}
struct IntoIter<T> {
    // 用于内存回收
    _buffer: RawVec<T>,
    iter: RawValIter<T>,
}
impl<T> Drop for IntoIter<T> {
    fn drop(&mut self) {
        for _ in &mut *self {}
    }
}
impl<T> IntoIterator for Vec<T> {
    type Item = T;

    type IntoIter = IntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        unsafe {
            IntoIter {
                _buffer: ptr::read(&self.raw),
                iter: RawValIter::new(&self),
            }
        }
    }
}
impl<T> Iterator for RawValIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        unsafe {
            if self.start == self.end {
                None
            } else {
                unsafe {
                    if mem::size_of::<T>() == 0 {
                        self.start = (self.start as usize + 1) as *const _;
                        Some(ptr::read(NonNull::<T>::dangling().as_ptr()))
                    } else {
                        let result = Some(ptr::read(self.start));
                        self.start = self.start.offset(1);
                        result
                    }
                }
            }
        }
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        let element_size = mem::size_of::<T>();
        let len = (self.end as usize - self.start as usize)
            / if element_size == 0 { 1 } else { element_size };
        (len, Some(len))
    }
}
impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next()
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }
}
impl<T> DoubleEndedIterator for RawValIter<T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.start == self.end {
            None
        } else {
            unsafe {
                if mem::size_of::<T>() == 0 {
                    self.end = (self.end as usize - 1) as *const _;
                    Some(ptr::read(NonNull::<T>::dangling().as_ptr()))
                } else {
                    self.end = self.end.offset(-1);
                    let result = ptr::read(self.end);
                    Some(result)
                }
            }
        }
    }
}
impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.iter.next_back()
    }
}
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 grow(&mut self) {
        assert!(mem::size_of::<T>() != 0, "capacity overflow");
        let new_cap = if self.cap == 0 { 1 } else { self.cap * 2 };
        let new_layout = Layout::array::<T>(new_cap).unwrap();
        assert!(
            new_layout.size() < i32::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();
            unsafe { alloc::realloc(self.ptr.as_ptr() as *mut u8, old_layout, new_cap) }
        };
        self.ptr = match NonNull::new(new_ptr as *mut T) {
            Some(ptr) => ptr,
            None => alloc::handle_alloc_error(new_layout),
        };
        self.cap = new_cap;
    }

    fn new() -> RawVec<T> {
        // assert!(mem::size_of::<T>() != 0, "We're not ready to handle ZSTs");
        let cap = if mem::size_of::<T>() == 0 {
            usize::MAX
        } else {
            0
        };
        RawVec {
            ptr: NonNull::dangling(),
            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);
            }
        }
    }
}
pub struct Drain<'a, T> {
    vec: PhantomData<&'a mut T>,
    iter: RawValIter<T>,
}
impl<'a, T> Iterator for Drain<'a, T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next()
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }
}
impl<'a, T> Drop for Drain<'a, T> {
    fn drop(&mut self) {
        for _ in &mut *self {}
    }
}
#[cfg(test)]
mod test {
    #[test]
    fn basic() {
        let mut vec = Vec::<i32>::new();
        assert_eq!(vec.pop(), None);
        vec.push(1);
        vec.push(2);
        vec.insert(0, 3);
        let vec_slice = &vec;
        assert_eq!(vec_slice.len(), 3);
        assert_eq!(vec_slice[0], 3);
        assert_eq!(vec.remove(0), 3);
        let vec_slice = &vec;
        assert_eq!(vec_slice.len(), 2);
        assert_eq!(vec_slice[0], 1);
        assert_eq!(vec_slice[1], 2);
        assert_eq!(vec.len(), 2);
        assert_eq!(vec.pop(), Some(2));
        assert_eq!(vec.pop(), Some(1));
    }
}