Fast atomic typed arena in rust.

lib.rs

//! # sync-arena

use std::mem;
use std::marker::PhantomData;
use std::sync::atomic::{AtomicUsize, Ordering};

pub struct TypedArena<T> {
    root: AtomicUsize,
    phantom: PhantomData<Option<InnerArena<T>>>
}

#[derive(Debug)]
struct InnerArena<T> {
    val: T,
    next: AtomicUsize,
    phantom: PhantomData<Option<InnerArena<T>>>
}

impl<T> TypedArena<T> {
    pub fn new() -> Self {
        TypedArena {
            root: AtomicUsize::new(0),
            phantom: PhantomData
        }
    }

    pub fn push(&self, val: T) -> &mut T where T: ::std::fmt::Debug {
        let mut new_root = Box::new(InnerArena {
            val: val,
            next: AtomicUsize::new(0),
            phantom: PhantomData
        });
        let raw_new_root = &mut *new_root as *mut InnerArena<T> as usize;
        let raw_val = &mut new_root.val as *mut T;

        let mut old_root = self.root.load(Ordering::SeqCst);

        loop {
            new_root.next.store(old_root, Ordering::Relaxed);

            let newer_old_root = self.root.compare_and_swap(old_root, raw_new_root, Ordering::SeqCst);

            // The swap succeeded.
            if newer_old_root == old_root {
                mem::forget(new_root);
                return unsafe { &mut *raw_val }
            } else {
                // The swap failed, try again with the new root.
                old_root = newer_old_root;
            }
        }
    }

    pub fn clear(&mut self) {
        let mut current;
        while { current = self.root.load(Ordering::Relaxed); current != 0 } {
            let real = unsafe { Box::from_raw(current as *mut InnerArena<T>) };
            self.root = real.next;
        }
    }
}

impl<T> Drop for TypedArena<T> {
    fn drop(&mut self) {
        self.clear()
    }
}

#[cfg(test)]
mod test {
    use super::TypedArena;

    #[test]
    fn test_it_works() {
        let mut x = TypedArena::new();

        {
            let first = x.push(vec![1, 2, 3]);
            let second = x.push(vec![4, 5, 6]);
            let third = x.push(vec![7, 8, 9]);

            assert_eq!(&**first, &[1, 2, 3]);
            assert_eq!(&**second, &[4, 5, 6]);
            assert_eq!(&**third, &[7, 8, 9]);
        }

        x.clear();

        {
            let first = x.push(vec![1, 2, 3]);
            let second = x.push(vec![4, 5, 6]);
            let third = x.push(vec![7, 8, 9]);

            assert_eq!(&**first, &[1, 2, 3]);
            assert_eq!(&**second, &[4, 5, 6]);
            assert_eq!(&**third, &[7, 8, 9]);
        }
    }
}