smallvec.rs

//! A vector type that allows storing small values directly on the stack.

#![feature(untagged_unions)]

use std::iter::FromIterator;
use std::ptr::drop_in_place;
use std::ops::Deref;
use std::fmt;

pub struct SmallVec8<T> {
    count: usize,
    values: [ManuallyDrop<T>; 8]
}

impl<T> fmt::Debug for SmallVec8<T>
    where T: fmt::Debug {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        self[..].fmt(f)
    }
}

impl<T> Deref for SmallVec8<T> {
    type Target = [T];
    fn deref(&self) -> &Self::Target {
        let values = &self.values[..self.count];
        unsafe { &*(values as *const [_] as *const [T]) }
    }
}

#[allow(unions_with_drop_fields, dead_code)]
union ManuallyDrop<T> {
    value: T,
    empty: ()
}

impl<T> Drop for SmallVec8<T> {
    fn drop(&mut self) {
        for i in 0..self.count {
            unsafe {
                drop_in_place(&mut self.values[i]);
            }
        }
    }
}

#[derive(Debug)]
pub enum MaybeSmallVec8<T> {
    Small(SmallVec8<T>),
    Large(Vec<T>)
}

impl<T> Deref for MaybeSmallVec8<T> {
    type Target = [T];
    fn deref(&self) -> &Self::Target {
        match *self {
            MaybeSmallVec8::Small(ref v) => &v[..],
            MaybeSmallVec8::Large(ref v) => &v[..],
        }
    }
}

impl<T> FromIterator<T> for MaybeSmallVec8<T> {
    fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> MaybeSmallVec8<T> {
        let iter = iter.into_iter();
        if iter.size_hint().1.map_or(false, |n| n <= 8) {
            let mut count = 0;
            let mut values = [
                ManuallyDrop { empty: () },
                ManuallyDrop { empty: () },
                ManuallyDrop { empty: () },
                ManuallyDrop { empty: () },
                ManuallyDrop { empty: () },
                ManuallyDrop { empty: () },
                ManuallyDrop { empty: () },
                ManuallyDrop { empty: () },
            ];
            for el in iter {
                values[count] = ManuallyDrop { value: el };
                count += 1;
            }
            MaybeSmallVec8::Small(SmallVec8 {
                count: count,
                values: values,
            })
        } else {
            MaybeSmallVec8::Large(iter.collect())
        }
    }
}