aovec 1.1.0

#![deny(missing_docs)]
//! Append-only concurrent vector
extern crate parking_lot;
use std::cell::UnsafeCell;
use std::ops::Index;

use parking_lot::RwLock;

/// A concurrent vector, only supporting push and indexed access
pub struct Aovec<T> {
    len: RwLock<usize>,
    allocations: [UnsafeCell<Vec<T>>; 16],
    base: usize,
}

unsafe impl<T> Sync for Aovec<T> {}
unsafe impl<T> Send for Aovec<T> {}

impl<T> Aovec<T> {
    /// Creates a new `Aovec`
    ///
    /// The `base` of the vector is how many elements the first allocation
    /// fits. When this value is exceeded, another vector is allocated
    /// with twice the size. Up to 16 allocations are supported, after which
    /// the push will panic.
    ///
    /// A base of 16 gives a maximum number of 104856 elements.
    pub fn new(base: usize) -> Self {
        assert!(base > 0, "Base must be non-zero");
        Aovec {
            len: RwLock::new(0),
            allocations: [
                UnsafeCell::new(vec![]),
                UnsafeCell::new(vec![]),
                UnsafeCell::new(vec![]),
                UnsafeCell::new(vec![]),
                UnsafeCell::new(vec![]),
                UnsafeCell::new(vec![]),
                UnsafeCell::new(vec![]),
                UnsafeCell::new(vec![]),
                UnsafeCell::new(vec![]),
                UnsafeCell::new(vec![]),
                UnsafeCell::new(vec![]),
                UnsafeCell::new(vec![]),
                UnsafeCell::new(vec![]),
                UnsafeCell::new(vec![]),
                UnsafeCell::new(vec![]),
                UnsafeCell::new(vec![]),
            ],
            base,
        }
    }

    // get the allocation and offset within it.
    fn allocation(&self, mut offset: usize) -> (usize, usize) {
        let mut compare = self.base;
        let mut allocation = 0;
        loop {
            if compare > offset {
                return (allocation, offset);
            } else {
                offset -= compare;
            }
            compare = compare << 1;
            allocation += 1;
        }
    }

    #[inline]
    fn _get(&self, idx: usize) -> &T {
        let (index, offset) = self.allocation(idx);
        unsafe { &(*self.allocations[index].get())[offset] }
    }

    #[inline]
    fn valid_index(&self, idx: usize) -> bool {
        *self.len.read() > idx
    }

    /// Returns the length of the `Aovec`.
    pub fn len(&self) -> usize {
        *self.len.read()
    }

    /// Get value at index `idx`
    pub fn get(&self, idx: usize) -> Option<&T> {
        if self.valid_index(idx) {
            Some(self._get(idx))
        } else {
            None
        }
    }

    /// Get value at index `idx`, without checking bounds
    pub unsafe fn get_unchecked(&self, idx: usize) -> &T {
        self._get(idx)
    }

    /// Adds an element to the `Aovec`, returning its index.
    pub fn push(&self, t: T) -> usize {
        let mut guard = self.len.write();
        let idx = *guard;
        *guard += 1;
        let (index, _) = self.allocation(idx);
        unsafe {
            let allocation = self.allocations[index].get();
            if (*allocation).len() == 0 {
                *allocation = Vec::with_capacity(self.base << index);
            }
            (*allocation).push(t);
        }
        idx
    }
}

impl<T> Index<usize> for Aovec<T> {
    type Output = T;
    fn index(&self, idx: usize) -> &Self::Output {
        if self.valid_index(idx) {
            self._get(idx)
        } else {
            panic!("Index out of range");
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::sync::Arc;
    use std::collections::HashSet;

    #[test]
    fn base_one() {
        let vec = Aovec::new(1);
        let n = 1024;

        for i in 0..n {
            vec.push(i);
        }

        for i in 0..n {
            assert_eq!(vec[i], i);
        }
    }

    #[test]
    fn base_thirtytwo() {
        let vec = Aovec::new(32);
        let n = 1_000_000;

        for i in 0..n {
            vec.push(i);
        }

        for i in 0..n {
            assert_eq!(vec[i], i);
            assert_eq!(vec.get(i), Some(&i));
            unsafe {
                assert_eq!(vec.get_unchecked(i), &i);
            }
        }
    }

    #[test]
    fn multithreading() {
        let vec = Arc::new(Aovec::new(32));
        let n = 100_000;

        let n_threads = 16;

        let mut handles = vec![];

        for t in 0..n_threads {
            let vec = vec.clone();
            handles.push(std::thread::spawn(move || for i in 0..n {
                if i % n_threads == t {
                    vec.push(i);
                }
            }))
        }

        for h in handles {
            h.join().unwrap();
        }

        let mut set = HashSet::new();

        for i in 0..n {
            set.insert(vec[i]);
        }

        assert_eq!(set.len(), n);
    }
}