{"action":"created","comment":{"url":"https://api.github.com/repos/Gankro/collect-rs/pulls/comments/23646307","id":23646307,"diff_hunk":"@@ -0,0 +1,1832 @@\n+use alloc::heap::{EMPTY, allocate, reallocate, deallocate};\n+\n+// Implemented on top of `core` to demonstrate the ability to substitute HybridVec for Vec\n+use core::borrow::{BorrowFrom, ToOwned};\n+use core::default::Default;\n+use core::fmt;\n+use core::hash::{self, Hash};\n+use core::intrinsics::forget;\n+use core::iter;\n+use core::marker::ContravariantLifetime;\n+use core::nonzero::NonZero;\n+use core::mem;\n+use core::num::{Int, UnsignedInt};\n+use core::ops;\n+use core::ptr;\n+use core::raw::Slice as RawSlice;\n+use core::usize;\n+\n+// Make this configurable?\n+const ARRAY_SIZE: usize = 32;\n+// The number of bytes a type has to be larger than to automatically be allocated on the heap.\n+// This limits the on-stack size of `HybridVec` to a maximum of \n+// `ARRAY_SIZE * HEAP_BYTES_THRESHOLD`.\n+const HEAP_BYTES_THRESHOLD: usize = 64;\n+\n+/// An implementation of `HybridVec` that uses stack-allocated storage below a certain length.\n+/// A drop-in replacement for `Vec` from the stdlib, with a couple minor changes to the API and internal\n+/// behavior.\n+pub enum HybridVec<T> {\n+    Stack {\n+        array: [T; ARRAY_SIZE], \n+        len: usize,\n+    },\n+    Heap {\n+        ptr: NonZero<*mut T>, \n+        len: usize, \n+        cap: usize,\n+    },\n+}\n+\n+//#[inline]\n+fn should_use_heap<T>() -> bool {\n+    // Determine this based on actual available stack space instead?\n+    mem::size_of::<T>() > HEAP_BYTES_THRESHOLD   \n+}\n+\n+//#[inline]\n+fn nonzero_ptr<T>() -> NonZero<*mut T> {\n+    unsafe { NonZero::new(EMPTY as *mut T) }    \n+}\n+\n+macro_rules! hybrid_vec [\n+    // This will need to be adjusted\n+    [$($elem:expr),*] => (HybridVec::from_boxed_slice(Box::new([$($elem),*])))\n+];\n+           \n+impl<T> HybridVec<T> {\n+    pub fn new() -> HybridVec<T> {\n+        // Go directly to heap if the size of the type is greater than our threshold.\n+        if should_use_heap::<T>() {\n+            HybridVec::Heap { \n+                ptr: nonzero_ptr(),\n+                len: 0,\n+                cap: 0,\n+            } \n+        } else {\n+            HybridVec::Stack {\n+                // Allocate the stack space for our array.\n+                // We'll do length checks as usual.\n+                array: unsafe { mem::uninitialized() },\n+                len: 0,\n+            }    \n+        }\n+    }\n+\n+    pub fn with_capacity(cap: usize) -> HybridVec<T> {\n+        if mem::size_of::<T>() == 0 {\n+            HybridVec::Heap { ptr: nonzero_ptr(), len: 0, cap: usize::MAX }\n+        } else if cap > ARRAY_SIZE || should_use_heap::<T>() {\n+            let size_bytes = cap.checked_mul(mem::size_of::<T>())\n+                .expect(\"Capacity overflow!\");\n+            let ptr = unsafe { allocate(size_bytes, mem::min_align_of::<T>()) };\n+            if ptr.is_null() { ::alloc::oom() }\n+\n+            HybridVec::Heap {\n+                ptr: unsafe { NonZero::new(ptr as *mut T) },\n+                len: 0,\n+                cap: cap,\n+            }                \n+        } else {\n+            HybridVec::Stack {\n+                array: unsafe { mem::uninitialized() },\n+                len: 0,\n+            }  \n+        }\n+    }\n+\n+    /// Necessary because `SliceExt::into_vec` goes directly into `Vec`.\n+    pub fn from_boxed_slice(mut slice: Box<[T]>) -> HybridVec<T> {\n+        unsafe { \n+            let vec = HybridVec::from_raw_parts(slice.as_mut_ptr(), slice.len(), slice.len());\n+            mem::forget(slice);\n+            vec\n+        }    \n+    }\n+        \n+    pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> HybridVec<T> {\n+        HybridVec::Heap { ptr: NonZero::new(ptr), len: length, cap: capacity }\n+    }\n+    \n+    pub unsafe fn from_raw_buf(ptr: *const T, elts: usize) -> HybridVec<T> {\n+        let mut dst = HybridVec::with_capacity(elts);\n+        dst.set_len(elts);\n+        ptr::copy_nonoverlapping_memory(dst.as_mut_ptr(), ptr, elts);\n+        dst\n+    }\n+\n+    #[inline]\n+    pub fn len(&self) -> usize {\n+        match *self {\n+            HybridVec::Heap {  ptr: _, len, cap: _ } => len,\n+            HybridVec::Stack { array: _, len } => len,    \n+        }    \n+    }\n+\n+    #[inline]\n+    pub fn is_empty(&self) -> bool {\n+        self.len() == 0\n+    }\n+\n+    #[inline]\n+    pub fn capacity(&self) -> usize {\n+        match *self {\n+            HybridVec::Heap { ptr: _, len: _, cap } => cap,\n+            HybridVec::Stack { array: _, len: _ } => ARRAY_SIZE,    \n+        }    \n+    }\n+    \n+    pub fn insert(&mut self, index: usize, element: T) {\n+        let len = self.len();\n+        assert!(index <= len);\n+        // space for the new element\n+        self.reserve(1);\n+\n+        unsafe { // infallible\n+            // The spot to put the new value\n+            {\n+                let p = self.as_mut_ptr().offset(index as isize);\n+                // Shift everything over to make space. (Duplicating the\n+                // `index`th element into two consecutive places.)\n+                ptr::copy_memory(p.offset(1), &*p, len - index);\n+                // Write it in, overwriting the first copy of the `index`th\n+                // element.\n+                ptr::write(&mut *p, element);\n+            }\n+            self.set_len(len + 1);\n+        }\n+    }\n+\n+    pub fn remove(&mut self, index: usize) -> T {\n+        let len = self.len();\n+        assert!(index < len);\n+        unsafe { // infallible\n+            let ret;\n+            {\n+                // the place we are taking from.\n+                let ptr = self.as_mut_ptr().offset(index as isize);\n+                // copy it out, unsafely having a copy of the value on\n+                // the stack and in the vector at the same time.\n+                ret = ptr::read(ptr as *const T);\n+\n+                // Shift everything down to fill in that spot.\n+                ptr::copy_memory(ptr, &*ptr.offset(1), len - index - 1);\n+            }\n+            self.set_len(len - 1);\n+            ret\n+        }\n+    }\n+    \n+    //#[inline]\n+    pub fn push(&mut self, value: T) {\n+        if mem::size_of::<T>() == 0 {\n+            // zero-size types consume no memory, so we can't rely on the\n+            // address space running out.\n+            // This will automatically use the heap variant.\n+            unsafe {                \n+                let new_len = self.len().checked_add(1).expect(\"length overflow\");\n+                self.set_len(new_len);\n+                mem::forget(value); \n+            }\n+            return\n+        }\n+        \n+        // `HybridVec::push()` had some weird reallocation logic that wasn't explained in the code\n+        // and didn't seem to change much except the growth rate of `HybridVec`.\n+        // This should suffice unless the old behavior is shown to be preferiential.\n+        self.reserve(1);\n+\n+        unsafe {\n+            let len = self.len();\n+            let end = self.as_mut_ptr().offset(len as isize);\n+            ptr::write(&mut *end, value);\n+            self.set_len(len + 1);\n+        }\n+    }\n+\n+    //#[inline]\n+    pub fn pop(&mut self) -> Option<T> {\n+        if self.len() == 0 { return None }\n+        \n+        let new_len = self.len() - 1;\n+\n+        unsafe { \n+            self.set_len(new_len);\n+            Some(ptr::read(self.get_unchecked(self.len())))\n+        }    \n+    }\n+    \n+    pub fn truncate(&mut self, len: usize) {\n+        unsafe {\n+            // drop any extra elements\n+            while len < self.len() {\n+                let curr_len = self.len();\n+                // decrement len before the read(), so a panic on Drop doesn't\n+                // re-drop the just-failed value.\n+                self.set_len(curr_len - 1);\n+                ptr::read(self.get_unchecked(self.len()));\n+            }\n+        }\n+    }\n+\n+    pub unsafe fn set_len(&mut self, new_len: usize) {\n+        match *self {\n+            HybridVec::Heap { ptr: _, ref mut len, cap: _ } => *len = new_len,\n+            HybridVec::Stack { array: _, ref mut len } => *len = new_len,\n+        }\n+    }\n+    \n+    pub fn reserve(&mut self, additional: usize) {\n+        if self.capacity() - self.len() < additional {\n+            let err_msg = \"HybridVec::reserve: `usize` overflow\";\n+            let new_cap = self.len().checked_add(additional).expect(err_msg)\n+                .checked_next_power_of_two().expect(err_msg);\n+            self.grow_capacity(new_cap);\n+        }\n+    }\n+    \n+    fn grow_capacity(&mut self, capacity: usize) {\n+        if mem::size_of::<T>() == 0 { return }\n+\n+        if capacity > self.capacity() {\n+            if self.is_stack() {\n+                self.move_to_heap(capacity);    \n+            } else if let HybridVec::Heap { ref mut ptr, len: _, ref mut cap} = *self {\n+               \n+                let size = capacity.checked_mul(mem::size_of::<T>())\n+                               .expect(\"capacity overflow\");\n+                unsafe {\n+                    let new_ptr = alloc_or_realloc(**ptr, *cap * mem::size_of::<T>(), size);\n+                    if ptr.is_null() { ::alloc::oom() }\n+                    *ptr = NonZero::new(new_ptr);\n+                }\n+                *cap = capacity;\n+            }\n+        }\n+    }\n+\n+    //#[inline]\n+    fn is_stack(&self) -> bool {\n+        match *self {\n+            HybridVec::Stack { array: _, len: _ } => true,\n+            _ => false,    \n+        } \n+    }\n+    \n+    /// Move to the heap if the new capacity requirement is too big for the stack\n+    fn move_to_heap(&mut self, capacity: usize) {\n+        // Sanity checks\n+        if !self.is_stack() { return }\n+        \n+        unsafe { \n+            let temp = mem::replace(self, HybridVec::with_capacity(capacity));\n+            \n+            if let HybridVec::Stack { ref array, len } = temp {\n+                ptr::copy_nonoverlapping_memory(self.as_mut_ptr(), array.as_ptr(), len);\n+                self.set_len(len);\n+            }\n+            \n+            forget(temp);                       \n+        }\n+    }\n+\n+    /// Move back to the stack if the vector can fit\n+    fn move_to_stack(&mut self) {\n+        if self.is_stack() || self.len() > ARRAY_SIZE || should_use_heap::<T>() { return }\n+\n+        unsafe {\n+            let temp = mem::replace(self, HybridVec::new());\n+            self.set_len(temp.len());\n+            ptr::copy_nonoverlapping_memory(self.as_mut_ptr(), temp.as_ptr(), temp.len());\n+            \n+            if let HybridVec::Heap { ptr, cap, len: _ } = temp {\n+                dealloc(*ptr, cap);\n+            }\n+\n+            forget(temp);\n+        }\n+    }\n+\n+    pub fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T] {\n+        match *self {\n+            HybridVec::Heap { ptr, len, cap: _ } => unsafe {\n+                mem::transmute(RawSlice {\n+                    data: *ptr as *const T,\n+                    len: len,\n+                })\n+            },\n+            HybridVec::Stack { ref mut array, len } => &mut array[..len],                     \n+        } \n+    }\n+    \n+    pub fn into_iter(self) -> IntoIter<T> {\n+        let ret = match self {\n+            HybridVec::Stack { ref array, len } => {\n+                let array = unsafe { ptr::read(array) };\n+                \n+                IntoIter::Stack {\n+                    array: array,\n+                    curr: 0,\n+                    len: len,\n+                }\n+            },\n+            HybridVec::Heap { ptr, len, cap } => {        \n+                let end = if mem::size_of::<T>() == 0 {\n+                    (*ptr as usize + len) as *const T\n+                } else {\n+                    unsafe { ptr.offset(len as isize) as *const T }\n+                };\n+                    \n+                IntoIter::Heap {\n+                    ptr: *ptr,\n+                    cap: cap,\n+                    curr: *ptr as *const T,\n+                    end: end,\n+                }\n+            },\n+        };\n+        \n+        unsafe { mem::forget(self) }\n+        \n+        ret                   \n+    }\n+\n+    pub fn retain<F>(&mut self, mut f: F) where F: FnMut(&T) -> bool {\n+        let len = self.len();\n+        let mut del = 0us;\n+        {\n+            let v = self.as_mut_slice();\n+\n+            for i in range(0us, len) {\n+                if !f(&v[i]) {\n+                    del += 1;\n+                } else if del > 0 {\n+                    v.swap(i-del, i);\n+                }\n+            }\n+        }\n+        if del > 0 {\n+            self.truncate(len - del);\n+        }    \n+    }\n+    \n+    //#[inline]\n+    pub fn swap_remove(&mut self, index: usize) -> T {\n+        let length = self.len();\n+        self.swap(index, length - 1);\n+        self.pop().unwrap()\n+    }\n+    \n+    pub fn into_boxed_slice(mut self) -> Box<[T]> {\n+        if self.is_stack() {\n+            let cap = self.len();\n+            self.move_to_heap(cap);\n+        } else {\n+            self.shrink_to_fit(false);\n+        }\n+\n+        unsafe {\n+            let xs: Box<[T]> = mem::transmute(self.as_mut_slice());\n+            mem::forget(self);\n+            xs\n+        }\n+    }\n+    \n+    pub fn shrink_to_fit(&mut self, move_to_stack: bool) {\n+        if mem::size_of::<T>() == 0 { return }\n+\n+        match *self {\n+            HybridVec::Stack { array: _, len: _ } => (),\n+            HybridVec::Heap { ptr: _, cap:_ , len } if len < ARRAY_SIZE && move_to_stack => self.move_to_stack(),\n+            HybridVec::Heap { ref mut ptr, ref mut cap, len } => unsafe {\n+                // Overflow check is unnecessary as the vector is already at\n+                // least this large.\n+                let new_ptr = reallocate(\n+                    **ptr as *mut u8,\n+                    *cap * mem::size_of::<T>(),\n+                    len * mem::size_of::<T>(),\n+                    mem::min_align_of::<T>()\n+                ) as *mut T;\n+\n+                if new_ptr.is_null() { ::alloc::oom() }\n+                *ptr = NonZero::new(new_ptr);\n+                *cap = len;\n+            }\n+        }\n+    }\n+\n+    //#[inline]\n+    pub fn append(&mut self, other: &mut Self) {\n+        if mem::size_of::<T>() == 0 {\n+            // zero-size types consume no memory, so we can't rely on the\n+            // address space running out\n+            let new_len = self.len().checked_add(other.len()).expect(\"length overflow\");\n+            unsafe { \n+                self.set_len(new_len);\n+                other.set_len(0);\n+            }\n+            return;\n+        }\n+        self.reserve(other.len());\n+        let len = self.len();\n+        unsafe {\n+            ptr::copy_nonoverlapping_memory(\n+                self.get_unchecked_mut(len),\n+                other.as_ptr(),\n+                other.len());\n+        }\n+    \n+        let new_len = self.len() + other.len();\n+        unsafe {\n+            self.set_len(new_len);\n+            other.set_len(0); \n+        }\n+    }\n+\n+    pub fn drain<'a>(&'a mut self) -> Drain<'a, T> {\n+        match *self {\n+            HybridVec::Stack { ref mut array, len } => Drain::Stack { array: array, curr: 0, len: len },\n+            HybridVec::Heap { ptr, cap: _, len } => \n+            Drain::Heap { \n+                curr: *ptr as *const T,\n+                end: unsafe { ptr.offset(len as isize) },\n+                marker: ContravariantLifetime,\n+            },\n+        }\n+    }\n+}\n+\n+impl<T> HybridVec<T> where T: Clone {\n+\n+    pub fn resize(&mut self, new_len: usize, val: T) {\n+        let len = self.len();\n+        \n+        if new_len > len {\n+            self.extend(iter::repeat(val).take(new_len - len));    \n+        } else {\n+            self.truncate(new_len);\n+        }\n+    }\n+\n+    pub fn push_all(&mut self, other: &[T]) {\n+        self.extend(other.iter().cloned())    \n+    }\n+}\n+\n+impl<T> Clone for HybridVec<T> where T: Clone {\n+    fn clone(&self) -> HybridVec<T> {\n+        self.iter().cloned().collect()\n+    }\n+    \n+    fn clone_from(&mut self, other: &HybridVec<T>) {\n+        if self.len() > other.len() {\n+            self.truncate(other.len());    \n+        }\n+\n+        for (place, thing) in self.iter_mut().zip(other.iter()) {\n+            place.clone_from(thing)    \n+        }\n+\n+        let slice = &other[self.len()..];\n+        self.push_all(slice);\n+    }    \n+}\n+\n+impl<T> Default for HybridVec<T> {\n+    fn default() -> HybridVec<T> {\n+        HybridVec::new()    \n+    }    \n+}\n+\n+impl<T> ToOwned<HybridVec<T>> for [T] where T: Clone {\n+    fn to_owned(&self) -> HybridVec<T> {\n+        let mut vec = HybridVec::new();\n+        vec.extend(self.iter().cloned());\n+        vec    \n+    }    \n+}\n+\n+impl<T> AsSlice<T> for HybridVec<T> {\n+    fn as_slice<'a>(&'a self) -> &[T] {\n+        match *self {\n+            HybridVec::Heap { ptr, len, cap: _ } => unsafe {\n+                mem::transmute(RawSlice {\n+                    data: *ptr as *const T,\n+                    len: len,\n+                })\n+            },\n+            HybridVec::Stack { ref array, len } => &array[..len],                     \n+        }\n+    }\n+}\n+\n+impl<T> BorrowFrom<HybridVec<T>> for [T] {\n+    fn borrow_from(owned: &HybridVec<T>) -> &[T] {\n+        &**owned    \n+    }    \n+}\n+\n+impl<T> ops::Deref for HybridVec<T> {\n+    type Target = [T];\n+\n+    fn deref<'a>(&'a self) -> &'a [T] { self.as_slice() }    \n+}\n+\n+impl<T> ops::DerefMut for HybridVec<T> {\n+    fn deref_mut<'a>(&'a mut self) -> &'a mut [T] { self.as_mut_slice() }\n+}\n+\n+impl<T> fmt::Debug for HybridVec<T> where T: fmt::Debug {\n+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {\n+        fmt::Debug::fmt(self.as_slice(), f)    \n+    }    \n+}\n+\n+impl<S: hash::Writer + hash::Hasher, T: Hash<S>> Hash<S> for HybridVec<T> {\n+    //#[inline]\n+    fn hash(&self, state: &mut S) {\n+        self.as_slice().hash(state);\n+    }\n+}\n+\n+impl<A, B> PartialEq<HybridVec<B>> for HybridVec<A> where A: PartialEq<B> {\n+    //#[inline]\n+    fn eq(&self, other: &HybridVec<B>) -> bool { PartialEq::eq(&**self, &**other) }\n+    //#[inline]\n+    fn ne(&self, other: &HybridVec<B>) -> bool { PartialEq::ne(&**self, &**other) }\n+}\n+\n+macro_rules! impl_eq {\n+    ($lhs:ty, $rhs:ty) => {\n+        impl<'b, A, B> PartialEq<$rhs> for $lhs where A: PartialEq<B> {\n+            //#[inline]\n+            fn eq(&self, other: &$rhs) -> bool { PartialEq::eq(&**self, &**other) }\n+            //#[inline]\n+            fn ne(&self, other: &$rhs) -> bool { PartialEq::ne(&**self, &**other) }\n+        }\n+\n+        impl<'b, A, B> PartialEq<$lhs> for $rhs where B: PartialEq<A> {\n+            //#[inline]\n+            fn eq(&self, other: &$lhs) -> bool { PartialEq::eq(&**self, &**other) }\n+            //#[inline]\n+            fn ne(&self, other: &$lhs) -> bool { PartialEq::ne(&**self, &**other) }\n+        }\n+    }\n+}\n+\n+impl_eq! { HybridVec<A>, &'b [B] }\n+impl_eq! { HybridVec<A>, &'b mut [B] }\n+\n+#[inline(never)]\n+unsafe fn alloc_or_realloc<T>(ptr: *mut T, old_size: usize, size: usize) -> *mut T {\n+    if old_size == 0 {\n+        allocate(size, mem::min_align_of::<T>()) as *mut T\n+    } else {\n+        reallocate(ptr as *mut u8, old_size, size, mem::min_align_of::<T>()) as *mut T\n+    }\n+}\n+\n+//#[inline]\n+unsafe fn dealloc<T>(ptr: *mut T, len: usize) {\n+    if mem::size_of::<T>() != 0 {\n+        deallocate(ptr as *mut u8,\n+                   len * mem::size_of::<T>(),\n+                   mem::min_align_of::<T>())\n+    }\n+}\n+\n+impl<T> Extend<T> for HybridVec<T> {\n+    fn extend<I: Iterator<Item=T>>(&mut self, mut iter: I) {\n+        let (lower, _) = iter.size_hint();\n+        self.reserve(lower);\n+        for elem in iter {\n+            self.push(elem)    \n+        }    \n+    }\n+}\n+\n+impl<T> iter::FromIterator<T> for HybridVec<T> {\n+    fn from_iter<I: Iterator<Item=T>>(iter: I) -> HybridVec<T> {\n+        let mut vec = HybridVec::new();\n+        vec.extend(iter);\n+        vec\n+    }    \n+}\n+\n+impl<T> ops::Index<usize> for HybridVec<T> {\n+    type Output = T;\n+    //#[inline]\n+    fn index(&self, index: &usize) -> &T {\n+        self.as_slice().index(index)   \n+    }\n+}\n+\n+impl<T> ops::Index<ops::Range<usize>> for HybridVec<T> {\n+    type Output = [T];\n+    //#[inline]\n+    fn index(&self, index: &ops::Range<usize>) -> &[T] {\n+        self.as_slice().index(index)\n+    }\n+}\n+\n+impl<T> ops::Index<ops::RangeTo<usize>> for HybridVec<T> {\n+    type Output = [T];\n+    //#[inline]\n+    fn index(&self, index: &ops::RangeTo<usize>) -> &[T] {\n+        self.as_slice().index(index)\n+    }\n+}\n+\n+impl<T> ops::Index<ops::RangeFrom<usize>> for HybridVec<T> {\n+    type Output = [T];\n+    //#[inline]\n+    fn index(&self, index: &ops::RangeFrom<usize>) -> &[T] {\n+        self.as_slice().index(index)\n+    }\n+}\n+\n+impl<T> ops::Index<ops::FullRange> for HybridVec<T> {\n+    type Output = [T];\n+    //#[inline]\n+    fn index(&self, _index: &ops::FullRange) -> &[T] {\n+        self.as_slice()\n+    }\n+}\n+\n+impl<T> ops::IndexMut<usize> for HybridVec<T> {\n+    type Output = T;\n+    //#[inline]\n+    fn index_mut(&mut self, index: &usize) -> &mut T {\n+        self.as_mut_slice().index_mut(index)\n+    }    \n+}\n+\n+impl<T> ops::IndexMut<ops::Range<usize>> for HybridVec<T> {\n+    type Output = [T];\n+    //#[inline]\n+    fn index_mut(&mut self, index: &ops::Range<usize>) -> &mut [T] {\n+        self.as_mut_slice().index_mut(index)\n+    }\n+}\n+\n+impl<T> ops::IndexMut<ops::RangeTo<usize>> for HybridVec<T> {\n+    type Output = [T];\n+    //#[inline]\n+    fn index_mut(&mut self, index: &ops::RangeTo<usize>) -> &mut [T] {\n+        self.as_mut_slice().index_mut(index)\n+    }\n+}\n+\n+impl<T> ops::IndexMut<ops::RangeFrom<usize>> for HybridVec<T> {\n+    type Output = [T];\n+    //#[inline]\n+    fn index_mut(&mut self, index: &ops::RangeFrom<usize>) -> &mut [T] {\n+        self.as_mut_slice().index_mut(index)\n+    }\n+}\n+\n+impl<T> ops::IndexMut<ops::FullRange> for HybridVec<T> {\n+    type Output = [T];\n+    //#[inline]\n+    fn index_mut(&mut self, _index: &ops::FullRange) -> &mut [T] {\n+        self.as_mut_slice()\n+    }\n+}\n+\n+#[unsafe_destructor]\n+impl<T> Drop for HybridVec<T> {\n+    fn drop(&mut self) {\n+        if self.capacity() == 0 { return }\n+\n+        unsafe {\n+            // We zero self here so the drop glue knows not to run the dtor again\n+            let temp = mem::replace(self, mem::zeroed());\n+\n+            for x in temp.iter() {\n+                ptr::read(x);    \n+            }\n+\n+            match temp {\n+                HybridVec::Heap { ptr, len: _, cap } => dealloc(*ptr, cap),\n+                _ => (),\n+            }\n+\n+            forget(temp);\n+        }\n+    }\n+}\n+\n+pub enum IntoIter<T> {\n+    Stack {\n+        array: [T; ARRAY_SIZE],\n+        curr: usize,\n+        len: usize,\n+    },\n+    Heap {\n+        ptr: *mut T,\n+        cap: usize,\n+        curr: *const T,\n+        end: *const T,\n+    },\n+}\n+\n+impl<T> Iterator for IntoIter<T> {\n+    type Item = T;\n+\n+    fn next(&mut self) -> Option<T> {\n+        match *self {\n+            IntoIter::Stack { ref array, ref mut curr, len } if *curr != len => { \n+                let ret = unsafe { ptr::read(&array[*curr]) };\n+                *curr += 1;\n+                Some(ret)\n+            },\n+            IntoIter::Heap { ptr: _, cap: _, ref mut curr, end } if *curr != end => unsafe {\n+                if mem::size_of::<T>() == 0 {\n+                    *curr = mem::transmute(*curr as usize + 1);\n+                    return Some(ptr::read(mem::transmute(1us)));\n+                }\n+\n+                let ret = ptr::read(*curr);\n+                *curr = curr.offset(1);\n+                Some(ret)\n+            },\n+            _ => None,\n+        }\n+    }\n+\n+    fn size_hint(&self) -> (usize, Option<usize>) {\n+        let exact = match *self {\n+            IntoIter::Stack { array: _, curr, len } => len - curr,\n+            IntoIter::Heap { ptr: _, cap: _, curr, end } => {\n+                let diff = (end as usize) - (curr as usize);\n+                let size = mem::size_of::<T>();\n+                diff / (if size == 0 {1} else {size})\n+            }\n+        };\n+        \n+        (exact, Some(exact))  \n+    }\n+}\n+\n+impl<T> DoubleEndedIterator for IntoIter<T> {\n+    //#[inline]\n+    fn next_back<'a>(&'a mut self) -> Option<T> {\n+        match *self {\n+            IntoIter::Stack { ref mut array, curr, ref mut len } if curr != *len => {\n+                *len -= 1;\n+                Some(unsafe { ptr::read(&array[*len]) })\n+            },\n+            IntoIter::Heap { ptr: _, cap: _, curr, ref mut end } if curr != *end => unsafe {\n+                if mem::size_of::<T>() == 0 {\n+                    *end = mem::transmute(*end as usize - 1);\n+                    Some(ptr::read(mem::transmute(1us)))\n+                } else {\n+                    *end = end.offset(-1);\n+                    Some(ptr::read(mem::transmute(*end)))\n+                }\n+            },\n+            _ => None,\n+        }\n+    }\n+}\n+\n+impl<T> ExactSizeIterator for IntoIter<T> {}\n+\n+impl<T> IntoIter<T> { \n+    pub fn into_inner(mut self) -> HybridVec<T> {\n+        for _ in self {}\n+\n+        let ret = match self {\n+            IntoIter::Stack { ref array, curr: _, len: _ } =>\n+            HybridVec::Stack {\n+                array: unsafe { ptr::read(array) },\n+                len: 0,\n+            },\n+            IntoIter::Heap { ptr, cap, curr: _, end: _, } => unsafe { \n+                HybridVec::from_raw_parts(ptr, cap, 0) \n+            },\n+        };\n+\n+        unsafe { mem::forget(self); }\n+        ret\n+    }    \n+}\n+\n+#[unsafe_destructor]\n+impl<T> Drop for IntoIter<T> {\n+    fn drop(&mut self) {\n+        for _ in *self {}\n+\n+        unsafe { \n+            let temp = mem::replace(self, mem::zeroed());\n+            match temp {\n+                IntoIter::Heap { ptr, cap, curr: _, end: _ } if cap != 0 => dealloc(ptr, cap),\n+                _ => (),\n+            }\n+\n+            mem::forget(temp);","path":"src/proto/hybrid_vec.rs","position":827,"original_position":827,"commit_id":"84382284f99d4cf298e92103590e230436e15d93","original_commit_id":"84382284f99d4cf298e92103590e230436e15d93","user":{"login":"tbu-","id":6666593,"avatar_url":"https://avatars.githubusercontent.com/u/6666593?v=3","gravatar_id":"","url":"https://api.github.com/users/tbu-","html_url":"https://github.com/tbu-","followers_url":"https://api.github.com/users/tbu-/followers","following_url":"https://api.github.com/users/tbu-/following{/other_user}","gists_url":"https://api.github.com/users/tbu-/gists{/gist_id}","starred_url":"https://api.github.com/users/tbu-/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tbu-/subscriptions","organizations_url":"https://api.github.com/users/tbu-/orgs","repos_url":"https://api.github.com/users/tbu-/repos","events_url":"https://api.github.com/users/tbu-/events{/privacy}","received_events_url":"https://api.github.com/users/tbu-/received_events","type":"User","site_admin":false},"body":"@cybergeek94 It doesn't stop the drop glue from running, but what's bad about running the drop glue of `Heap { ..., cap: 0, ... }`?","created_at":"2015-01-27T21:51:40Z","updated_at":"2015-01-27T21:51:40Z","html_url":"https://github.com/Gankro/collect-rs/pull/100#discussion_r23646307","pull_request_url":"https://api.github.com/repos/Gankro/collect-rs/pulls/100","_links":{"self":{"href":"https://api.github.com/repos/Gankro/collect-rs/pulls/comments/23646307"},"html":{"href":"https://github.com/Gankro/collect-rs/pull/100#discussion_r23646307"},"pull_request":{"href":"https://api.github.com/repos/Gankro/collect-rs/pulls/100"}}},"pull_request":{"url":"https://api.github.com/repos/Gankro/collect-rs/pulls/100","id":28090671,"html_url":"https://github.com/Gankro/collect-rs/pull/100","diff_url":"https://github.com/Gankro/collect-rs/pull/100.diff","patch_url":"https://github.com/Gankro/collect-rs/pull/100.patch","issue_url":"https://api.github.com/repos/Gankro/collect-rs/issues/100","number":100,"state":"open","locked":false,"title":"HybridVec: a drop-in replacement for Vec that uses stack storage for small vectors","user":{"login":"cybergeek94","id":3198595,"avatar_url":"https://avatars.githubusercontent.com/u/3198595?v=3","gravatar_id":"","url":"https://api.github.com/users/cybergeek94","html_url":"https://github.com/cybergeek94","followers_url":"https://api.github.com/users/cybergeek94/followers","following_url":"https://api.github.com/users/cybergeek94/following{/other_user}","gists_url":"https://api.github.com/users/cybergeek94/gists{/gist_id}","starred_url":"https://api.github.com/users/cybergeek94/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cybergeek94/subscriptions","organizations_url":"https://api.github.com/users/cybergeek94/orgs","repos_url":"https://api.github.com/users/cybergeek94/repos","events_url":"https://api.github.com/users/cybergeek94/events{/privacy}","received_events_url":"https://api.github.com/users/cybergeek94/received_events","type":"User","site_admin":false},"body":"Inspired by @Gankro's [comment in the thread about SSO on discuss.rust-lang.org][1]. \r\n\r\nThis is a drop-in replacement for `Vec` that dynamically moves between stack and heap for smaller vectors. The threshold is currently governed by two hardcoded constants, the size of the on-stack array and the max number of bytes in the contained type, but perhaps in the future it could be configurable at compile-time or even calculated from a percentage of the running stack size. I didn't know enough about DST to implement a dynamically-sized array so the on-stack array is a constant size.\r\n\r\nThe file is huge mainly because I copied all the tests from `vec.rs` to make sure it was up to snuff. In fact, a lot of code was shamelessly copied from `vec.rs` and adapted to `HybridVec`, mostly with respect to heap storage management.\r\n\r\nI had to comment out the assertions on capacity for smaller vectors because switching to stack storage broke them (`HybridVec::new().capacity() != 0`) and I didn't want to expose the `ARRAY_SIZE` constant for the `tests` submodule or copy it as a magic number for each occurrence. \r\n\r\nSome methods, such as `map_in_place`, `dedup` and `vec::as_vec`, (and their associated tests) were omitted on purpose to limit complexity while others were omitted accidentally because `Vec`'s API is massive and the tests didn't complain. Please let me know of any that should be there but aren't.  \r\n\r\nI made sure all tests passed before submitting this PR. I also ran benchmarks, though I'm not exactly sure if I'm interpreting them correctly because they seem to show regressions when the vector is on-stack: [Pastebin][2]\r\n\r\nOf course, this could just be overhead. I expect some from the widespread use of dynamic dispatch required by this implementation strategy. A real comparison should compare `HybridVec` to `Vec` for vectors of the same size to emphasize any performance improvements/regressions. Additionally, some methods have a more naiive implementation than their `Vec` ancestors for simplicity's sake and should be benchmarked for performance regressions.\r\n\r\nThis is very much still a **work-in-progress**, though I feel it's mature enough already to be included as a working prototype so it can cut its teeth in the wild. \r\n\r\nIn addition to missing needed methods and benchmarks, I neglected to write doc-comments for most of the methods because the public API behaves, for the most part, equivalently to `Vec`'s, with the exception of `shrink_to_fit` which has a new `move_to_stack: bool` parameter, which was needed to make `into_boxed_slice()` work correctly for smaller vectors. \r\n\r\nThe stack-vs-heap behavior happens transparently and is never exposed to the user except for this parameter.\r\n\r\n[1]: http://discuss.rust-lang.org/t/small-string-optimization-remove-as-mut-vec/1320/2\r\n[2]: http://pastebin.com/WVJAtihr","created_at":"2015-01-27T08:19:46Z","updated_at":"2015-01-27T21:51:40Z","closed_at":null,"merged_at":null,"merge_commit_sha":"67b47fc0f69e22cfe84e3ef10cd4aa1c8d772b9a","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/Gankro/collect-rs/pulls/100/commits","review_comments_url":"https://api.github.com/repos/Gankro/collect-rs/pulls/100/comments","review_comment_url":"https://api.github.com/repos/Gankro/collect-rs/pulls/comments/{number}","comments_url":"https://api.github.com/repos/Gankro/collect-rs/issues/100/comments","statuses_url":"https://api.github.com/repos/Gankro/collect-rs/statuses/84382284f99d4cf298e92103590e230436e15d93","head":{"label":"cybergeek94:hybrid_vec","ref":"hybrid_vec","sha":"84382284f99d4cf298e92103590e230436e15d93","user":{"login":"cybergeek94","id":3198595,"avatar_url":"https://avatars.githubusercontent.com/u/3198595?v=3","gravatar_id":"","url":"https://api.github.com/users/cybergeek94","html_url":"https://github.com/cybergeek94","followers_url":"https://api.github.com/users/cybergeek94/followers","following_url":"https://api.github.com/users/cybergeek94/following{/other_user}","gists_url":"https://api.github.com/users/cybergeek94/gists{/gist_id}","starred_url":"https://api.github.com/users/cybergeek94/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cybergeek94/subscriptions","organizations_url":"https://api.github.com/users/cybergeek94/orgs","repos_url":"https://api.github.com/users/cybergeek94/repos","events_url":"https://api.github.com/users/cybergeek94/events{/privacy}","received_events_url":"https://api.github.com/users/cybergeek94/received_events","type":"User","site_admin":false},"repo":{"id":28167107,"name":"collect-rs","full_name":"cybergeek94/collect-rs","owner":{"login":"cybergeek94","id":3198595,"avatar_url":"https://avatars.githubusercontent.com/u/3198595?v=3","gravatar_id":"","url":"https://api.github.com/users/cybergeek94","html_url":"https://github.com/cybergeek94","followers_url":"https://api.github.com/users/cybergeek94/followers","following_url":"https://api.github.com/users/cybergeek94/following{/other_user}","gists_url":"https://api.github.com/users/cybergeek94/gists{/gist_id}","starred_url":"https://api.github.com/users/cybergeek94/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cybergeek94/subscriptions","organizations_url":"https://api.github.com/users/cybergeek94/orgs","repos_url":"https://api.github.com/users/cybergeek94/repos","events_url":"https://api.github.com/users/cybergeek94/events{/privacy}","received_events_url":"https://api.github.com/users/cybergeek94/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/cybergeek94/collect-rs","description":"Miscellaneous Collections","fork":true,"url":"https://api.github.com/repos/cybergeek94/collect-rs","forks_url":"https://api.github.com/repos/cybergeek94/collect-rs/forks","keys_url":"https://api.github.com/repos/cybergeek94/collect-rs/keys{/key_id}","collaborators_url":"https://api.github.com/repos/cybergeek94/collect-rs/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/cybergeek94/collect-rs/teams","hooks_url":"https://api.github.com/repos/cybergeek94/collect-rs/hooks","issue_events_url":"https://api.github.com/repos/cybergeek94/collect-rs/issues/events{/number}","events_url":"https://api.github.com/repos/cybergeek94/collect-rs/events","assignees_url":"https://api.github.com/repos/cybergeek94/collect-rs/assignees{/user}","branches_url":"https://api.github.com/repos/cybergeek94/collect-rs/branches{/branch}","tags_url":"https://api.github.com/repos/cybergeek94/collect-rs/tags","blobs_url":"https://api.github.com/repos/cybergeek94/collect-rs/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/cybergeek94/collect-rs/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/cybergeek94/collect-rs/git/refs{/sha}","trees_url":"https://api.github.com/repos/cybergeek94/collect-rs/git/trees{/sha}","statuses_url":"https://api.github.com/repos/cybergeek94/collect-rs/statuses/{sha}","languages_url":"https://api.github.com/repos/cybergeek94/collect-rs/languages","stargazers_url":"https://api.github.com/repos/cybergeek94/collect-rs/stargazers","contributors_url":"https://api.github.com/repos/cybergeek94/collect-rs/contributors","subscribers_url":"https://api.github.com/repos/cybergeek94/collect-rs/subscribers","subscription_url":"https://api.github.com/repos/cybergeek94/collect-rs/subscription","commits_url":"https://api.github.com/repos/cybergeek94/collect-rs/commits{/sha}","git_commits_url":"https://api.github.com/repos/cybergeek94/collect-rs/git/commits{/sha}","comments_url":"https://api.github.com/repos/cybergeek94/collect-rs/comments{/number}","issue_comment_url":"https://api.github.com/repos/cybergeek94/collect-rs/issues/comments/{number}","contents_url":"https://api.github.com/repos/cybergeek94/collect-rs/contents/{+path}","compare_url":"https://api.github.com/repos/cybergeek94/collect-rs/compare/{base}...{head}","merges_url":"https://api.github.com/repos/cybergeek94/collect-rs/merges","archive_url":"https://api.github.com/repos/cybergeek94/collect-rs/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/cybergeek94/collect-rs/downloads","issues_url":"https://api.github.com/repos/cybergeek94/collect-rs/issues{/number}","pulls_url":"https://api.github.com/repos/cybergeek94/collect-rs/pulls{/number}","milestones_url":"https://api.github.com/repos/cybergeek94/collect-rs/milestones{/number}","notifications_url":"https://api.github.com/repos/cybergeek94/collect-rs/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/cybergeek94/collect-rs/labels{/name}","releases_url":"https://api.github.com/repos/cybergeek94/collect-rs/releases{/id}","created_at":"2014-12-18T03:42:42Z","updated_at":"2014-12-23T02:09:36Z","pushed_at":"2015-01-27T08:02:26Z","git_url":"git://github.com/cybergeek94/collect-rs.git","ssh_url":"git@github.com:cybergeek94/collect-rs.git","clone_url":"https://github.com/cybergeek94/collect-rs.git","svn_url":"https://github.com/cybergeek94/collect-rs","homepage":"","size":574,"stargazers_count":0,"watchers_count":0,"language":"Rust","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"Gankro:master","ref":"master","sha":"0e81ad183ec3f317131bc670fb0968829b3cdba6","user":{"login":"Gankro","id":1136864,"avatar_url":"https://avatars.githubusercontent.com/u/1136864?v=3","gravatar_id":"","url":"https://api.github.com/users/Gankro","html_url":"https://github.com/Gankro","followers_url":"https://api.github.com/users/Gankro/followers","following_url":"https://api.github.com/users/Gankro/following{/other_user}","gists_url":"https://api.github.com/users/Gankro/gists{/gist_id}","starred_url":"https://api.github.com/users/Gankro/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Gankro/subscriptions","organizations_url":"https://api.github.com/users/Gankro/orgs","repos_url":"https://api.github.com/users/Gankro/repos","events_url":"https://api.github.com/users/Gankro/events{/privacy}","received_events_url":"https://api.github.com/users/Gankro/received_events","type":"User","site_admin":false},"repo":{"id":25849693,"name":"collect-rs","full_name":"Gankro/collect-rs","owner":{"login":"Gankro","id":1136864,"avatar_url":"https://avatars.githubusercontent.com/u/1136864?v=3","gravatar_id":"","url":"https://api.github.com/users/Gankro","html_url":"https://github.com/Gankro","followers_url":"https://api.github.com/users/Gankro/followers","following_url":"https://api.github.com/users/Gankro/following{/other_user}","gists_url":"https://api.github.com/users/Gankro/gists{/gist_id}","starred_url":"https://api.github.com/users/Gankro/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Gankro/subscriptions","organizations_url":"https://api.github.com/users/Gankro/orgs","repos_url":"https://api.github.com/users/Gankro/repos","events_url":"https://api.github.com/users/Gankro/events{/privacy}","received_events_url":"https://api.github.com/users/Gankro/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Gankro/collect-rs","description":"Miscellaneous Collections","fork":false,"url":"https://api.github.com/repos/Gankro/collect-rs","forks_url":"https://api.github.com/repos/Gankro/collect-rs/forks","keys_url":"https://api.github.com/repos/Gankro/collect-rs/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Gankro/collect-rs/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Gankro/collect-rs/teams","hooks_url":"https://api.github.com/repos/Gankro/collect-rs/hooks","issue_events_url":"https://api.github.com/repos/Gankro/collect-rs/issues/events{/number}","events_url":"https://api.github.com/repos/Gankro/collect-rs/events","assignees_url":"https://api.github.com/repos/Gankro/collect-rs/assignees{/user}","branches_url":"https://api.github.com/repos/Gankro/collect-rs/branches{/branch}","tags_url":"https://api.github.com/repos/Gankro/collect-rs/tags","blobs_url":"https://api.github.com/repos/Gankro/collect-rs/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Gankro/collect-rs/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Gankro/collect-rs/git/refs{/sha}","trees_url":"https://api.github.com/repos/Gankro/collect-rs/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Gankro/collect-rs/statuses/{sha}","languages_url":"https://api.github.com/repos/Gankro/collect-rs/languages","stargazers_url":"https://api.github.com/repos/Gankro/collect-rs/stargazers","contributors_url":"https://api.github.com/repos/Gankro/collect-rs/contributors","subscribers_url":"https://api.github.com/repos/Gankro/collect-rs/subscribers","subscription_url":"https://api.github.com/repos/Gankro/collect-rs/subscription","commits_url":"https://api.github.com/repos/Gankro/collect-rs/commits{/sha}","git_commits_url":"https://api.github.com/repos/Gankro/collect-rs/git/commits{/sha}","comments_url":"https://api.github.com/repos/Gankro/collect-rs/comments{/number}","issue_comment_url":"https://api.github.com/repos/Gankro/collect-rs/issues/comments/{number}","contents_url":"https://api.github.com/repos/Gankro/collect-rs/contents/{+path}","compare_url":"https://api.github.com/repos/Gankro/collect-rs/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Gankro/collect-rs/merges","archive_url":"https://api.github.com/repos/Gankro/collect-rs/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Gankro/collect-rs/downloads","issues_url":"https://api.github.com/repos/Gankro/collect-rs/issues{/number}","pulls_url":"https://api.github.com/repos/Gankro/collect-rs/pulls{/number}","milestones_url":"https://api.github.com/repos/Gankro/collect-rs/milestones{/number}","notifications_url":"https://api.github.com/repos/Gankro/collect-rs/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Gankro/collect-rs/labels{/name}","releases_url":"https://api.github.com/repos/Gankro/collect-rs/releases{/id}","created_at":"2014-10-28T02:35:00Z","updated_at":"2015-01-27T21:05:48Z","pushed_at":"2015-01-27T21:09:00Z","git_url":"git://github.com/Gankro/collect-rs.git","ssh_url":"git@github.com:Gankro/collect-rs.git","clone_url":"https://github.com/Gankro/collect-rs.git","svn_url":"https://github.com/Gankro/collect-rs","homepage":"","size":5454,"stargazers_count":55,"watchers_count":55,"language":"Rust","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":19,"mirror_url":null,"open_issues_count":23,"forks":19,"open_issues":23,"watchers":55,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/Gankro/collect-rs/pulls/100"},"html":{"href":"https://github.com/Gankro/collect-rs/pull/100"},"issue":{"href":"https://api.github.com/repos/Gankro/collect-rs/issues/100"},"comments":{"href":"https://api.github.com/repos/Gankro/collect-rs/issues/100/comments"},"review_comments":{"href":"https://api.github.com/repos/Gankro/collect-rs/pulls/100/comments"},"review_comment":{"href":"https://api.github.com/repos/Gankro/collect-rs/pulls/comments/{number}"},"commits":{"href":"https://api.github.com/repos/Gankro/collect-rs/pulls/100/commits"},"statuses":{"href":"https://api.github.com/repos/Gankro/collect-rs/statuses/84382284f99d4cf298e92103590e230436e15d93"}}}}