Skip to content

Instantly share code, notes, and snippets.

@tomaka
Forked from reem/lib.rs
Created April 18, 2016 08:40
Show Gist options
  • Save tomaka/d7e76bf23d8b87cfd8b691b6f8a42b88 to your computer and use it in GitHub Desktop.
Save tomaka/d7e76bf23d8b87cfd8b691b6f8a42b88 to your computer and use it in GitHub Desktop.
Fast atomic typed arena in rust.
//! # 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 {
println!("Inserting val {:?}", val);
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>;
let raw_val = &mut new_root.val as *mut T;
println!("new_root: {:?}, raw_new_root: {:?}, raw_val: {:?}", new_root, raw_new_root, raw_val);
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 as usize, 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]);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment